Methods and systems for detecting and locating skipped frames in a video sequence

FIELD OF THE INVENTION

0001Embodiments of the present invention relate, in general, to methods and systems for video processing, and more particularly, to methods and systems for video quality measurements and analysis.

BACKGROUND

0002Video quality measurements and analysis may require each frame in a test video sequence to be played at the same time as the corresponding frame of a reference video sequence is played. This may be referred to as temporal registration of the test video sequence and the reference video sequence.

0003Temporal registration may be difficult to perform, either manually or by an automated method, due to differing video formats, differing frame rates, temporal distortions, temporal impairments and other differences between the test video sequence and the reference video sequence. In addition, encoding, transporting, broadcasting, distributing, decoding, and other processing of video, may contribute to one, or more, frames being skipped in a video sequence as illustrated in the exemplary reference and test sequences: <dl id="dl0001"><dt>Reference Sequence:</dt><dd>A B C D E F G</dd><dt>Test Sequence:</dt><dd>A B C D E G H,</dd></dl> where like-letters denote corresponding video frames, also considered frames, between the reference sequence and the test sequence. In this example, frames A, B, C, D and E are aligned. However, because of reference-video-sequence frame F being skipped in the test video sequence, the last two frames are mismatched between the test video sequence and the reference video sequence.

0004Automated methods and systems to measure the number and location of skipped frames in a test video sequence relative to a reference video sequence may be desirable. In particular, it may be desirable to have measurement methods and systems that are robust in the presence of digital compression artifacts, random noise, quantization error, and other non-linear and linear distortions and interferences. Additionally, it may be desirable to have measurement methods and systems that do not require <i>a priori</i> knowledge of the video content, aspect ratio, DUT (Device Under Test) pixel clock, frame rates, video parameters, including relative spatial mapping, for example, horizontal scaling, vertical scaling, offset and cropping, and other video factors. Accurate and computationally efficient methods and systems may also be desirable.

SUMMARY

0005Embodiments of the present invention comprise methods and systems for detecting and locating skipped frames in a test video sequence in relation to a reference video sequence. Some embodiments of the present invention comprise identifying pairs of temporally aligned reference segments and test segments. An alignment offset and freeze-frame count associated with each segment pair may be received and used to calculate a number of skipped frames between a first segment pair and a second segment pair, wherein the second segment pair is temporally subsequent to the first segment pair. In some embodiments of the present invention, a number of skipped frames between the first segment pair and the second segment pair may be determined by calculating a segment offset between the two segment pairs and subtracting the segment offset value from the sum of the number of freeze frames associated with the first segment pair and all temporally intervening segment pairs between the first segment pair and the second segment pair.

0006Some embodiments of the present invention comprise calculating a similarity measure between corresponding frames in segment pairs and identifying discontinuities in the calculated similarity measures. In these embodiments, the location of skipped frames may be determined by resolving the discontinuities using the skipped-frame and freeze-frame counts associated with the segment pairs.

0007The foregoing and other objectives, features, and advantages of the invention will be more readily understood upon consideration of the following detailed description of the invention taken in conjunction with the accompanying drawings.

BRIEF DESCRIPTION OF THE SEVERAL DRAWINGS

0008<figref idref="f0001">Fig. 1</figref> is a chart showing exemplary embodiments of the present invention comprising forming temporally aligned segment pairs and calculating the number of skipped frames using alignment offset and freeze-frame count;

0009<figref idref="f0002">Fig. 2</figref> is a chart showing exemplary embodiments of the present invention comprising similarity-measure calculation, similarity-measure discontinuity identification and discontinuity resolution for locating skipped frames;

0010<figref idref="f0002">Fig. 3</figref> is a chart showing exemplary embodiments of the present invention comprising spatial alignment prior to similarity-measure calculation;

0011<figref idref="f0003">Fig. 4</figref> is a picture illustrating similarity-measure discontinuity resolution, for an exemplary reference segment and test segment, according to embodiments of the present invention;

0012<figref idref="f0003">Fig. 5</figref> is a picture illustrating similarity-measure discontinuity resolution, for an exemplary reference segment and test segment, according to embodiments of the present invention; and

0013<figref idref="f0004">Fig. 6</figref> is a picture illustrating similarity-measure discontinuity resolution, for an exemplary reference segment and test segment, according to embodiments of the present invention.

DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS

0014Embodiments of the present invention will be best understood by reference to the drawings, wherein like parts are designated by like numerals throughout. The figures listed above are expressly incorporated as part of this detailed description.

0015It will be readily understood that the components of the present invention, as generally described and illustrated in the figures herein, could be arranged and designed in a wide variety of different configurations. Thus, the following more detailed description of the embodiments of the methods and systems of the present invention is not intended to limit the scope of the invention but it is merely representative of the presently preferred embodiments of the invention.

0016Embodiments of the present invention may be implemented within a test and measurement instrument. For example, embodiments of the present invention may be implemented in a video test instrument, such as a picture quality analyzer. Picture quality analyzers such as the TEKTRONIX® PQA500 may incorporate embodiments of the present invention.

0017Elements of embodiments of the present invention may be embodied in hardware, firmware and/or software. While exemplary embodiments revealed herein may only describe one of these forms, it is to be understood that one skilled in the art would be able to effectuate these elements in any of these forms while resting within the scope of the present invention.

0018Embodiments of the present invention may be used to process signals originating from video equipment. These video signals might be produced by playback equipment, such as DVD players, set-top boxes or production equipment used by broadcasters, or other content providers, prior to transmission of content to end-users.

0019Video quality measurements and analysis may require each frame in a test video sequence to be played at the same time as the corresponding frame of a reference video sequence is played. This may be referred to as temporal registration of the test video sequence and the reference video sequence.

0020Temporal registration may be difficult to perform, either manually or by an automated method, due to differing video formats, differing frame rates, temporal distortions, temporal impairments and other differences between the test video sequence and the reference video sequence. In addition, encoding, transporting, broadcasting, distributing, decoding, and other processing of video, may contribute to one, or more, frames being skipped in a video sequence as illustrated in the exemplary reference and test sequences: <dl id="dl0002"><dt>Reference Sequence:</dt><dd>A B C D E F G</dd><dt>Test Sequence:</dt><dd>A B C D E G H,</dd></dl> where like-letters denote corresponding video frames between the reference sequence and the test sequence. In this example, frames A, B, C, D and E are aligned. However, because of reference-video-sequence frame F being skipped in the test video sequence, the last two frames are mismatched between the test video sequence and the reference video sequence.

0021Automated methods and systems to measure the number and location of skipped frames in a test video sequence relative to a reference video sequence may be desirable. In particular, it may be desirable to have measurement methods and systems that are robust in the presence of digital compression artifacts, random noise, quantization error, and other non-linear and linear distortions and interferences. Additionally, it may be desirable to have measurement methods and systems that do not require <i>a priori</i> knowledge of the video content, aspect ratio, DUT (Device Under Test) pixel clock, frame rates, video parameters, including relative spatial mapping, for example, horizontal scaling, vertical scaling, offset and cropping, and other video factors. Accurate and computationally efficient methods and systems may also be desirable.

0022Embodiments of the present invention comprise methods and system for detecting and locating skipped frames in a test video sequence, also considered a test sequence, relative to a reference video sequence, also considered a reference sequence.

0023Some embodiments of the present invention may be described in relation to <figref idref="f0001">Figure 1</figref>. In these embodiments, a test sequence and a reference sequence may be received 10. The reference sequence may be segmented 12, and test-sequence segments may be temporally aligned 14 to the reference-sequence segments, thereby producing pairs of temporally aligned segments. An alignment offset associated with each test-sequence segment may be determined 16. A test-sequence segment alignment offset may be the offset in the test sequence relative to the reference sequence of the starting frame of the reference-sequence segment and the starting frame of the test-sequence segment in a segment pair. The number of freeze frames in each test-sequence segment may be determined 18. The number of skipped frames, which may be denoted <i>SkippedFramesBetween</i>(·,·), between, at least, the middle of a first segment pair, which may be denoted <i>si ,</i> and, at least, the middle of a second segment pair, which may be denoted <i>sj ,</i> may be calculated 20 using the offset values and the number of freeze frames according to: <maths id="math0001"><math display="block"><mi mathvariant="italic">SkippedFramesBetween</mi><mfenced><mi mathvariant="italic">si</mi><mo>⁢</mo><mi mathvariant="italic">sj</mi></mfenced><mo>=</mo><mstyle displaystyle="true"><munderover><mo mathvariant="normal">∑</mo><mrow><mi>s</mi><mo>=</mo><mi mathvariant="italic">si</mi></mrow><mrow><mi mathvariant="italic">sj</mi><mo>-</mo><mn>1</mn></mrow></munderover></mstyle><mi mathvariant="italic">FreezeFrames</mi><mfenced><mi>s</mi></mfenced><mo>+</mo><mi mathvariant="italic">alignOS</mi><mfenced><mi mathvariant="italic">si</mi></mfenced><mo>-</mo><mi mathvariant="italic">alignOS</mi><mfenced><mi mathvariant="italic">sj</mi></mfenced><mo>,</mo></math><img file="EP2227031A2_D0001.tif" /></maths> where <i>FreezeFrames</i> (<i>s</i>) may denote the number of freeze frames in the test-sequence segment of segment pair <i>s</i> and <i>alignOS</i> (<i>s</i>) may denote the alignment offset of the test-sequence segment in segment pair <i>s</i>. The location of the skipped frames may be determined 22 based on the number of skipped frames detected between pairs of segments. In some embodiments of the present invention, an incorrect skipped-frame count may be determined when a skipped frame occurs substantially close to the beginning of the first segment or substantially close to the end of the last segment. These outcomes may be referred to as end-point-based inconsistent results. In some embodiments of the present invention, a skipped frame that is not detected between two segment pairs may be detected between two other segment pairs.

0024Calculation 20 of the number of skipped frames may be understood in relation to the following example. In this illustrative example, a reference sequence comprising a sequence of reference frames and a test sequence comprising a sequence of test frames may be denoted: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z a b c d e f g h i j k l m and A B C D E F I J K L M N N O P R S T U V W X Y Z a b c d d d e f g h i j k l m, respectively, wherein frames G, H and Q are skipped in the test sequence in relation to the reference sequence, and frames N and d in the test sequence are freeze frames with freeze-frame occurrences of one and two, respectively. Exemplary segment alignments may be given by the segment pairs: <dl id="dl0003" compact="compact"><dt>Segment pair 0:</dt><dd><i>s</i> = 0 Reference-sequence segment: A B C D E F G H Test-sequence segment: A B C D E F I J</dd></dl><i>FreezeFrames</i> (0) = 0 and <i>alignOS</i> (0) = 0 <dl id="dl0004" compact="compact"><dt>Segment pair 1:</dt><dd>s = 1 Reference-sequence segment: I J K L M N O P Test-sequence segment: I J K L M N N O</dd></dl><i>FreezeFrames</i> (1) = 1 and <i>alignOS</i> (1) = -2 <dl id="dl0005" compact="compact"><dt>Segment pair 2:</dt><dd>s = 2 Reference-sequence segment: Q R S T U V W X Test-sequence segment: P R S T U V W X</dd></dl><i>FreezeFrames</i> (2) = 0 and <i>alignOS</i> (2) = -2 <dl id="dl0006" compact="compact"><dt>Segment pair 3:</dt><dd>s = 3 Reference-sequence segment: Y Z a b c d e f Test-sequence segment: Y Z a b c d d d</dd></dl><i>FreezeFrames</i> (3) = 2 and <i>alignOS</i> (3) = -2 <dl id="dl0007" compact="compact"><dt>Segment pair 4:</dt><dd>s = 4 Reference-sequence segment: g h i j k l m Test-sequence segment: g h i j k l m</dd></dl><i>FreezeFrames</i> (4) = 0 and <i>alignOS</i> (4) = 0.

0025The number of freeze frames and alignment offsets may be used to calculate 20 the number of skipped frames between segment pairs. The number of freeze frames and alignment information is summarized in Table 1 for this example. <tables id="tabl0001" num="0001"><table frame="all"><title>Table 1: Segment Summary for Example</title><tgroup cols="3"><colspec colnum="1" colname="col1" colwidth="23mm" /><colspec colnum="2" colname="col2" colwidth="37mm" /><colspec colnum="3" colname="col3" colwidth="52mm" /><thead><row><entry align="center" valign="top"><b>SEGMENT</b><i>s</i></entry><entry align="center" valign="top"><b>ALIGNMENT OFFSET</b><i>align OS</i> (<i>s</i>)</entry><entry align="center" valign="top"><b>NUMBER OF FREEZE FRAMES</b><i>FreezeFrames</i> (<i>s</i>)</entry></row></thead><tbody><row><entry align="center"><b>0</b></entry><entry align="center"><b>0</b></entry><entry align="center"><b>0</b></entry></row><row><entry align="center"><b>1</b></entry><entry align="center"><b>-2</b></entry><entry align="center"><b>1</b></entry></row><row><entry align="center"><b>2</b></entry><entry align="center"><b>-2</b></entry><entry align="center"><b>0</b></entry></row><row><entry align="center"><b>3</b></entry><entry align="center"><b>-2</b></entry><entry align="center"><b>2</b></entry></row><row><entry align="center"><b>4</b></entry><entry align="center"><b>0</b></entry><entry align="center"><b>0</b></entry></row></tbody></tgroup></table></tables>

0026The number of skipped frames between, at least, the middle of Segment pair 0 and, at least, the middle of Segment pair 1 may be calculated according to: <maths id="math0002"><math display="block"><mi mathvariant="italic">SkippedFramesBetween</mi><mfenced><mn>0</mn><mo>⁢</mo><mn>1</mn></mfenced><mo>=</mo><mstyle displaystyle="true"><munderover><mo mathvariant="normal">∑</mo><mrow><mi>s</mi><mo>=</mo><mn>0</mn></mrow><mn>0</mn></munderover></mstyle><mi mathvariant="italic">FreezeFrames</mi><mfenced><mi>s</mi></mfenced><mo>+</mo><mi mathvariant="italic">alignOS</mi><mfenced><mn>0</mn></mfenced><mo>-</mo><mi mathvariant="italic">alignOS</mi><mfenced><mn>1</mn></mfenced></math><img file="EP2227031A2_D0002.tif" /></maths><maths id="math0003"><math display="block"><mi mathvariant="italic">SkippedFramesBetween</mi><mfenced><mn>0</mn><mo>⁢</mo><mn>1</mn></mfenced><mo>=</mo><mn>0</mn><mo>+</mo><mn>0</mn><mo>-</mo><mfenced><mo>-</mo><mn>2</mn></mfenced><mo>=</mo><mn>2.</mn></math><img file="EP2227031A2_D0003.tif" /></maths> Thus, the number of skipped frames is determined to be two, which is consistent since reference frames G and H are skipped in the test segment.

0027The number of skipped frames between, at least, the middle of Segment pair 0 and, at least, the middle of Segment pair 2 may be calculated according to: <maths id="math0004"><math display="block"><mi mathvariant="italic">SkippedFramesBetween</mi><mfenced><mn>0</mn><mo>⁢</mo><mn>2</mn></mfenced><mo>=</mo><mstyle displaystyle="true"><munderover><mo mathvariant="normal">∑</mo><mrow><mi>s</mi><mo>=</mo><mn>0</mn></mrow><mn>1</mn></munderover></mstyle><mi mathvariant="italic">FreezeFrames</mi><mfenced><mi>s</mi></mfenced><mo>+</mo><mi mathvariant="italic">alignOS</mi><mfenced><mn>0</mn></mfenced><mo>-</mo><mi mathvariant="italic">alignOS</mi><mfenced><mn>2</mn></mfenced></math><img file="EP2227031A2_D0004.tif" /></maths><maths id="math0005"><math display="block"><mi mathvariant="italic">SkippedFramesBetween</mi><mfenced><mn>0</mn><mo>⁢</mo><mn>2</mn></mfenced><mo>=</mo><mfenced><mn>0</mn><mo>+</mo><mn>1</mn></mfenced><mo>+</mo><mn>0</mn><mo>-</mo><mfenced><mo>-</mo><mn>2</mn></mfenced><mo>=</mo><mn>3.</mn></math><img file="EP2227031A2_D0005.tif" /></maths> Thus, the number of skipped frames is determined to be three, which is consistent since reference frames G, H and Q are skipped in the test segment.

0028The number of skipped frames between, at least, the middle of Segment pair 0 and, at least, the middle of Segment pair 3 may be calculated according to: <maths id="math0006"><math display="block"><mi mathvariant="italic">SkippedFramesBetween</mi><mfenced><mn>0</mn><mo>⁢</mo><mn>3</mn></mfenced><mo>=</mo><mstyle displaystyle="true"><munderover><mo mathvariant="normal">∑</mo><mrow><mi>s</mi><mo>=</mo><mn>0</mn></mrow><mn>2</mn></munderover></mstyle><mi mathvariant="italic">FreezeFrames</mi><mfenced><mi>s</mi></mfenced><mo>+</mo><mi mathvariant="italic">alignOS</mi><mfenced><mn>0</mn></mfenced><mo>-</mo><mi mathvariant="italic">alignOS</mi><mfenced><mn>3</mn></mfenced></math><img file="EP2227031A2_D0006.tif" /></maths><maths id="math0007"><math display="block"><mi mathvariant="italic">SkippedFramesBetween</mi><mfenced><mn>0</mn><mo>⁢</mo><mn>3</mn></mfenced><mo>=</mo><mfenced><mn>0</mn><mo>+</mo><mn>1</mn><mo>+</mo><mn>0</mn></mfenced><mo>+</mo><mn>0</mn><mo>-</mo><mfenced><mo>-</mo><mn>2</mn></mfenced><mo>=</mo><mn>3.</mn></math><img file="EP2227031A2_D0007.tif" /></maths> Thus, the number of skipped frames is determined to be three, which is consistent since reference frames G, H and Q are skipped in the test segments.

0029The number of skipped frames between, at least, the middle of Segment pair 0 and, at least, the middle of Segment pair 4 may be calculated according to: <maths id="math0008"><math display="block"><mi mathvariant="italic">SkippedFramesBetween</mi><mfenced><mn>0</mn><mo>⁢</mo><mn>4</mn></mfenced><mo>=</mo><mstyle displaystyle="true"><munderover><mo mathvariant="normal">∑</mo><mrow><mi>s</mi><mo>=</mo><mn>0</mn></mrow><mn>3</mn></munderover></mstyle><mi mathvariant="italic">FreezeFrames</mi><mfenced><mi>s</mi></mfenced><mo>+</mo><mi mathvariant="italic">alignOS</mi><mfenced><mn>0</mn></mfenced><mo>-</mo><mi mathvariant="italic">alignOS</mi><mfenced><mn>4</mn></mfenced></math><img file="EP2227031A2_D0008.tif" /></maths><maths id="math0009"><math display="block"><mi mathvariant="italic">SkippedFramesBetween</mi><mfenced><mn>0</mn><mo>⁢</mo><mn>4</mn></mfenced><mo>=</mo><mfenced><mn>0</mn><mo>+</mo><mn>1</mn><mo>+</mo><mn>0</mn><mo>+</mo><mn>2</mn></mfenced><mo>+</mo><mn>0</mn><mo>-</mo><mn>0</mn><mo>=</mo><mn>3.</mn></math><img file="EP2227031A2_D0009.tif" /></maths> Thus, the number of skipped frames is determined to be three, which is consistent since reference frames G, H and Q are skipped in the test segments.

0030The number of skipped frames between, at least, the middle of Segment pair 1 and, at least, the middle of Segment pair 2 may be calculated according to: <maths id="math0010"><math display="block"><mi mathvariant="italic">SkippedFramesBetween</mi><mfenced><mn>1</mn><mo>⁢</mo><mn>2</mn></mfenced><mo>=</mo><mstyle displaystyle="true"><munderover><mo mathvariant="normal">∑</mo><mrow><mi>s</mi><mo>=</mo><mn>1</mn></mrow><mn>1</mn></munderover></mstyle><mi mathvariant="italic">FreezeFrames</mi><mfenced><mi>s</mi></mfenced><mo>+</mo><mi mathvariant="italic">alignOS</mi><mfenced><mn>1</mn></mfenced><mo>-</mo><mi mathvariant="italic">alignOS</mi><mfenced><mn>2</mn></mfenced></math><img file="EP2227031A2_D0010.tif" /></maths><maths id="math0011"><math display="block"><mi mathvariant="italic">SkippedFramesBetween</mi><mfenced><mn>1</mn><mo>⁢</mo><mn>2</mn></mfenced><mo>=</mo><mn>1</mn><mo>+</mo><mfenced><mo>-</mo><mn>2</mn></mfenced><mo>-</mo><mfenced><mo>-</mo><mn>2</mn></mfenced><mo>=</mo><mn>1.</mn></math><img file="EP2227031A2_D0011.tif" /></maths> Thus, the number of skipped frames is determined to be one, which is consistent since reference frame Q is skipped in the test segment.

0031The number of skipped frames between, at least, the middle of Segment pair 1 and, at least, the middle of Segment pair 3 may be calculated according to: <maths id="math0012"><math display="block"><mi mathvariant="italic">SkippedFramesBetween</mi><mfenced><mn>1</mn><mo>⁢</mo><mn>3</mn></mfenced><mo>=</mo><mstyle displaystyle="true"><munderover><mo mathvariant="normal">∑</mo><mrow><mi>s</mi><mo>=</mo><mn>1</mn></mrow><mn>2</mn></munderover></mstyle><mi mathvariant="italic">FreezeFrames</mi><mfenced><mi>s</mi></mfenced><mo>+</mo><mi mathvariant="italic">alignOS</mi><mfenced><mn>1</mn></mfenced><mo>-</mo><mi mathvariant="italic">alignOS</mi><mfenced><mn>3</mn></mfenced></math><img file="EP2227031A2_D0012.tif" /></maths><maths id="math0013"><math display="block"><mi mathvariant="italic">SkippedFramesBetween</mi><mfenced><mn>1</mn><mo>⁢</mo><mn>3</mn></mfenced><mo>=</mo><mfenced><mn>1</mn><mo>+</mo><mn>0</mn></mfenced><mo>+</mo><mfenced><mo>-</mo><mn>2</mn></mfenced><mo>-</mo><mfenced><mo>-</mo><mn>2</mn></mfenced><mo>=</mo><mn>1.</mn></math><img file="EP2227031A2_D0013.tif" /></maths> Thus, the number of skipped frames is determined to be one, which is consistent since reference frame Q is skipped in the test segments.

0032The number of skipped frames between, at least, the middle of Segment pair 1 and, at least, the middle of Segment pair 4 may be calculated according to: <maths id="math0014"><math display="block"><mi mathvariant="italic">SkippedFramesBetween</mi><mfenced><mn>1</mn><mo>⁢</mo><mn>4</mn></mfenced><mo>=</mo><mstyle displaystyle="true"><munderover><mo mathvariant="normal">∑</mo><mrow><mi>s</mi><mo>=</mo><mn>1</mn></mrow><mn>3</mn></munderover></mstyle><mi mathvariant="italic">FreezeFrames</mi><mfenced><mi>s</mi></mfenced><mo>+</mo><mi mathvariant="italic">alignOS</mi><mfenced><mn>1</mn></mfenced><mo>-</mo><mi mathvariant="italic">alignOS</mi><mfenced><mn>4</mn></mfenced></math><img file="EP2227031A2_D0014.tif" /></maths><maths id="math0015"><math display="block"><mi mathvariant="italic">SkippedFramesBetween</mi><mfenced><mn>1</mn><mo>⁢</mo><mn>4</mn></mfenced><mo>=</mo><mfenced><mn>1</mn><mo>+</mo><mn>0</mn><mo>+</mo><mn>2</mn></mfenced><mo>+</mo><mfenced><mo>-</mo><mn>2</mn></mfenced><mo>-</mo><mfenced><mn>0</mn></mfenced><mo>=</mo><mn>1.</mn></math><img file="EP2227031A2_D0015.tif" /></maths> Thus, the number of skipped frames is determined to be one, which is consistent since reference frame Q is skipped in the test segments.

0033The number of skipped frames between, at least, the middle of Segment pair 2 and, at least, the middle of Segment pair 3 may be calculated according to: <maths id="math0016"><math display="block"><mi mathvariant="italic">SkippedFramesBetween</mi><mfenced><mn>2</mn><mo>⁢</mo><mn>3</mn></mfenced><mo>=</mo><mstyle displaystyle="true"><munderover><mo mathvariant="normal">∑</mo><mrow><mi>s</mi><mo>=</mo><mn>2</mn></mrow><mn>2</mn></munderover></mstyle><mi mathvariant="italic">FreezeFrames</mi><mfenced><mi>s</mi></mfenced><mo>+</mo><mi mathvariant="italic">alignOS</mi><mfenced><mn>2</mn></mfenced><mo>-</mo><mi mathvariant="italic">alignOS</mi><mfenced><mn>3</mn></mfenced></math><img file="EP2227031A2_D0016.tif" /></maths><maths id="math0017"><math display="block"><mi mathvariant="italic">SkippedFramesBetween</mi><mfenced><mn>2</mn><mo>⁢</mo><mn>3</mn></mfenced><mo>=</mo><mfenced><mn>0</mn></mfenced><mo>+</mo><mfenced><mo>-</mo><mn>2</mn></mfenced><mo>-</mo><mfenced><mo>-</mo><mn>2</mn></mfenced><mo>=</mo><mn>0.</mn></math><img file="EP2227031A2_D0017.tif" /></maths> Thus, the number of skipped frames is determined to be zero, which is inconsistent due to end-point conditions.

0034The number of skipped frames between, at least, the middle of Segment pair 2 and, at least, the middle of Segment pair 4 may be calculated according to: <maths id="math0018"><math display="block"><mi mathvariant="italic">SkippedFramesBetween</mi><mfenced><mn>2</mn><mo>⁢</mo><mn>4</mn></mfenced><mo>=</mo><mstyle displaystyle="true"><munderover><mo mathvariant="normal">∑</mo><mrow><mi>s</mi><mo>=</mo><mn>2</mn></mrow><mn>3</mn></munderover></mstyle><mi mathvariant="italic">FreezeFrames</mi><mfenced><mi>s</mi></mfenced><mo>+</mo><mi mathvariant="italic">alignOS</mi><mfenced><mn>2</mn></mfenced><mo>-</mo><mi mathvariant="italic">alignOS</mi><mfenced><mn>4</mn></mfenced></math><img file="EP2227031A2_D0018.tif" /></maths><maths id="math0019"><math display="block"><mi mathvariant="italic">SkippedFramesBetween</mi><mfenced><mn>2</mn><mo>⁢</mo><mn>4</mn></mfenced><mo>=</mo><mfenced><mn>0</mn><mo>+</mo><mn>2</mn></mfenced><mo>+</mo><mfenced><mo>-</mo><mn>2</mn></mfenced><mo>-</mo><mfenced><mn>0</mn></mfenced><mo>=</mo><mn>0.</mn></math><img file="EP2227031A2_D0019.tif" /></maths> Thus, the number of skipped frames is determined to be zero, which is inconsistent due to end-point conditions.

0035The number of skipped frames between, at least, the middle of Segment pair 3 and, at least, the middle of Segment pair 4 may be calculated according to: <maths id="math0020"><math display="block"><mi mathvariant="italic">SkippedFramesBetween</mi><mfenced><mn>3</mn><mo>⁢</mo><mn>4</mn></mfenced><mo>=</mo><mstyle displaystyle="true"><munderover><mo mathvariant="normal">∑</mo><mrow><mi>s</mi><mo>=</mo><mn>3</mn></mrow><mn>3</mn></munderover></mstyle><mi mathvariant="italic">FreezeFrames</mi><mfenced><mi>s</mi></mfenced><mo>+</mo><mi mathvariant="italic">alignOS</mi><mfenced><mn>3</mn></mfenced><mo>-</mo><mi mathvariant="italic">alignOS</mi><mfenced><mn>4</mn></mfenced></math><img file="EP2227031A2_D0020.tif" /></maths><maths id="math0021"><math display="block"><mi mathvariant="italic">SkippedFramesBetween</mi><mfenced><mn>3</mn><mo>⁢</mo><mn>4</mn></mfenced><mo>=</mo><mfenced><mn>2</mn></mfenced><mo>+</mo><mfenced><mo>-</mo><mn>2</mn></mfenced><mo>-</mo><mfenced><mn>0</mn></mfenced><mo>=</mo><mn>0.</mn></math><img file="EP2227031A2_D0021.tif" /></maths> Thus, the number of skipped frames is determined to be zero, which is consistent since no frames are skipped in the test segment.

0036In some embodiments of the present invention, temporal alignment 14, offset determination 16 and freeze-frame determination 18 for each segment pair may be performed according to methods and systems developed by Kevin M. Ferguson, the present inventor, and described in <patcit id="pcit0001" dnum="US10438008A"><text>U.S. Patent Application Serial Number 12/104,380</text></patcit>, hereinafter the '380 application, entitled "Systems and Methods for Robust Video Temporal Registration," filed on April 16, 2008, and which is hereby incorporated herein by reference in its entirety. The '380 application claims the benefit of <patcit id="pcit0002" dnum="US91216707P"><text>U.S. Provisional Patent Application Serial Number 60/912,167</text></patcit> entitled "Systems and Methods for Robust Video Temporal Registration," filed on April 16, 2007, and which is hereby incorporated herein by reference in its entirety. In these embodiments, the methods and systems of the '380 application may be applied successively using each segment result to initialize the next search.

0037In alternative embodiments of the present invention, temporal alignment 14, offset determination 16 and freeze-frame determination 18 may be performed according to alternative methods. Exemplary alternative methods may include manual methods, automated methods and other methods known in the art.

0038In some embodiments of the present invention described in relation to <figref idref="f0001">Figure 1</figref> and <figref idref="f0002">Figure 2</figref>, determining 22 the location of skipped frames within one, or more, pairs of segments may comprise measuring 30 the similarity between reference-sequence frames and test-sequence frames in the segment pairs. Exemplary similarity measures may comprise calculating peak-signal-to-noise ratio (PSNR), a correlation or other measures of similarity known in the art. Frame-level discontinuities in similarity may be identified 32 and resolved 34 to locate the skipped frames.

0039In some embodiments of the present invention described in relation to <figref idref="f0001">Figure 1</figref> and <figref idref="f0002">Figure 3</figref>, determining 22 the location of skipped frames may comprise spatial alignment 40 prior to similarity calculation 42, discontinuity identification 44 and discontinuity resolution 46. In some embodiments of the present invention, spatial alignment 40 may be performed according to methods and systems developed by Kevin M. Ferguson, the present inventor, and described in <patcit id="pcit0003" dnum="US94405007A"><text>U.S. Patent Application Serial Number 11/944,050</text></patcit>, hereinafter the '050 application, entitled "Measurement Apparatus and Method of Measurement of Video Spatial Scale, Offset and Cropping," filed on November 21, 2007, and which is hereby incorporated herein by reference in its entirety. The '050 application claims the benefit of <patcit id="pcit0004" dnum="US86708706P"><text>U.S. Provisional Patent Application Serial Number 60/867,087, filed on November 22, 2006</text></patcit>, and which is hereby incorporated herein by reference in its entirety.

0040In some embodiments of the present invention, discontinuity resolution 34, 46 may comprise alignment compensation for freeze frames.

0041In some embodiments of the present invention, multiple skipped frames per segment pair may be located by alignment adjustment of the segments within the segment pair to favor the portion with the poorest alignment at a previously determined skipped-frame discontinuity and successively locating, according to the above-described embodiments, additional skipped frames.

0042Discontinuity resolution according to some embodiments of the present invention may be understood in relation to the following examples depicted in <figref idref="f0003">Figure 4, Figure 5</figref> and <figref idref="f0004">Figure 6</figref>.

0043<figref idref="f0003">Figure 4</figref> depicts an exemplary reference segment 50 and an exemplary test segment 52. The exemplary reference segment 50 comprises eight frames 60-67 labeled A, B, C, D, E, F, G and H, respectively, and the exemplary test segment 52 comprises eight frames 70-77, wherein, relative to the reference segment 50, frame C has been skipped and segment F 74, 75 appears twice. The freeze-frame count for this exemplary segment pair is one, and the skipped-frame count is one. An exemplary similarity plot 78 is shown, wherein similar frames yield high 90, 98 similarity-measure values, and dissimilar frames yield low 94 similarity-measure values. Discontinuities 92, 96 occur at the transitions between high and low similarity-measure values. Thus, in this example: reference frame A 60 and test frame A 70 are aligned and yield a high similarity-measure value 80; reference frame B 61 and test frame B 71 are aligned and yield a high similarity-measure value 81; reference frame C 62 and test frame D 72 are not aligned and yield a low similarity-measure value 82; reference frame D 63 and test frame E 73 are not aligned and yield a low similarity-measure value 83; reference frame E 64 and test frame F 74 are not aligned and yield a low similarity-measure value 84; reference frame F 65 and test frame (freeze frame) F 75 are aligned and yield a high similarity-measure value 85; reference frame G 66 and test frame G 76 are aligned and yield a high similarity-measure value 86; and reference frame H 67 and test frame H 77 are aligned and yield a high similarity-measure value 87. Since frame C is missing in the test segment 52 relative to the reference segment 50, a discontinuity 92 occurs at the location of frame C in the reference segment 50, and thus the location of the skipped frame is known. The similarity measure stays at a low value 94 until the freeze frame brings the segments back into alignment, wherein another discontinuity 96 in the plot of the similarity measure occurs.

0044<figref idref="f0003">Figure 5</figref> depicts an exemplary reference segment 50 and an exemplary test segment 102. The exemplary reference segment 50 comprises eight frames 60-67 labeled A, B, C, D, E, F, G and H, respectively, and the exemplary test segment 102 comprises eight frames 110-117, wherein, relative to the reference segment 50, frames C and E have been skipped and segment F 113, 114 appears twice. The freeze-frame count for this exemplary segment pair is one, and the skipped-frame count is two. An exemplary similarity plot 118 is shown, wherein similar frames yield high 130 similarity-measure values, and dissimilar frames yield low 134 similarity-measure values. A discontinuity 132 occurs at the transition between the high and the low similarity-measure values. Thus, in this example: reference frame A 60 and test frame A 110 are aligned and yield a high similarity-measure value 120; reference frame B 61 and test frame B 111 are aligned and yield a high similarity-measure value 121; reference frame C 62 and test frame D 112 are not aligned and yield a low similarity-measure value 122; reference frame D 63 and test frame F 113 are not aligned and yield a low similarity-measure value 123; reference frame E 64 and test frame (freeze frame) F 114 are not aligned and yield a low similarity-measure value 124; reference frame F 65 and test frame G 115 are not aligned and yield a low similarity-measure value 125; reference frame G 66 and test frame H 116 are not aligned and yield a low similarity-measure value 126; and reference frame H 67 and test frame I 117 are not aligned and yield a low similarity-measure value 87. Since frame C is missing in the test segment 102 relative to the reference segment 50, a discontinuity 132 occurs at the location of frame C in the reference segment 50, and thus the location of the skipped frame is known. The similarity measure stays at a low value 134 even past the freeze frame, thereby indicating the location of the second skipped frame.

0045<figref idref="f0004">Figure 6</figref> depicts an exemplary reference segment 50 and an exemplary test segment 138. The exemplary reference segment 50 comprises eight frames 60-67 labeled A, B, C, D, E, F, G and H, respectively, and the exemplary test segment 138 comprises eight frames 140-147, wherein, relative to the reference segment 50, frames C and E have been skipped and segment D 142, 143 appears twice. The freeze-frame count for this exemplary segment pair is one, and the skipped-frame count is two. An exemplary similarity plot 148 is shown, wherein similar frames yield high 160, 168 similarity-measure values, and dissimilar frames yield low 164, 172 similarity-measure values. Discontinuities 162, 166, 170 occur at the transitions between high and low similarity-measure values. Thus, in this example: reference frame A 60 and test frame A 140 are aligned and yield a high similarity-measure value 150; reference frame B 61 and test frame B 141 are aligned and yield a high similarity-measure value 151; reference frame C 62 and test frame D 142 are not aligned and yield a low similarity-measure value 152; reference frame D 63 and test frame (freeze frame) D 143 are aligned and yield a high similarity-measure value 153; reference frame E 64 and test frame F 144 are not aligned and yield a low similarity-measure value 154; reference frame F 65 and test frame G 145 are not aligned and yield a low similarity-measure value 155; reference frame G 66 and test frame H 146 are not aligned and yield a low similarity-measure value 156; and reference frame H 67 and test frame I 147 are not aligned and yield a low similarity-measure value 157. Since frame C is missing in the test segment 138 relative to the reference segment 50, a discontinuity 162 occurs at the location of frame C in the reference segment 50, and thus the location of a first skipped frame is known. The similarity measure jumps 166 from a low value 164 to a high value 168 when the freeze frame brings the segments back into alignment. A subsequent discontinuity 170 indicates a second skipped frame since the freeze frame corresponding to the freeze-frame count of one has already been consumed in the discontinuity resolution. Thus, the two skipped frames and one freeze frame have been resolved.

0046The above-described examples are intended to illustrate discontinuity resolution, and are not intended to be considered an exhaustive description of rules for discontinuity resolution.

0047The terms and expressions which have been employed in the foregoing specification are used therein as terms of description and not of limitation, and there is no intention in the use of such terms and expressions of excluding equivalence of the features shown and described or portions thereof, it being recognized that the scope of the invention is defined and limited only by the claims which follow.