A video segment is processed to identify frames representing shot boundaries in the video segment. Initially, a partial block-based comparison technique is used to determine the amount of change (i.e., a first difference) that occurs between a pair of distant (i.e., not consecutive) frames. Additionally, edge and/or color differences are computed between the pair of frames to confirm that a change has occurred. If the change is confirmed, a step variable technique is used to locate the change between two consecutive frames between the distant frames. If the partial block-based comparison technique obtains a difference between the consecutive frames that exceeds the first threshold, then an abrupt change is detected. Otherwise, the edge and/or color differences are used to determine whether a gradual transition has occurred.