Search algorithms for using related decode and display timelines

• US 7,796,693 B2
• Filed: 04/25/2005
• Issued: 09/14/2010
• Est. Priority Date: 04/25/2005
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Bushell, John Samuel
• Primary Examiner(s): VO, TUNG T
• Application Number:
  US11/115,085
• Publication Number:
  US 20060239357A1
• Time in Patent Office: 1,968 Days
• Field of Search: 375/240.01, 375/240.23, 375/240.25, 375/240.26, 386/52, 386/55, 715723-726
• US Class Current: 375/240.23
• CPC Class Codes: H04N 19/44 Decoders specially adapted therefor, e.g. video decoders which are asymmetric with respect to the encoder
• CPC Class Codes: H04N 19/46 Embedding additional information in the video signal during the compression process H04N19/517, H04N19/68, H04N19/70 take precedence
• CPC Class Codes: H04N 19/61 in combination with predictive coding

Abstract

A sequence of video images represented using multiple related timelines can be searched by identifying a first point on a first timeline associated with the sequence of video images, wherein the sequence of video images is comprised of one or more samples, determining a search range on a second timeline associated with the sequence of video images based on a positive offset and a negative offset associated with the one or more samples, and searching the second timeline based on the determined search range for a second point that corresponds to the identified first point. A display offset can be associated with each of the samples comprising the sequence of video images, wherein one or more of the display offsets can comprise a negative value. Additionally, the search range can be based on a maximum positive display offset and maximum negative display offset associated with the one or more samples.

Claims

1. A method of searching multiple related timelines representing a sequence of video images, the method comprising:

identifying a first point on a first timeline associated with a sequence of video images, wherein the sequence of video images is comprised of one or more samples;

determining a search range on a second timeline associated with the sequence of video images based on a positive offset and a negative offset associated with the one or more samples; and

searching the second timeline based on the determined search range for a second point that corresponds to the identified first point.

2. The method of claim 1, further comprising associating a display offset with each of the samples comprising the sequence of video images, wherein one or more of the display offsets comprises a negative value.

3. The method of claim 2, wherein determining a search range further comprises determining a search range on the second timeline based on a maximum positive display offset and a maximum negative display offset associated with the one or more samples.

4. The method of claim 3, further comprising adjusting the search range if the first point occurs within a decode duration or a display duration.

5. The method of claim 4, wherein the search range is extended backward in time by a period equal to the decode duration or the display duration in which the first point occurs.

6. The method of claim 2, further comprising storing the display offsets associated with the samples comprising the sequence of video images in a data structure, wherein the display offsets are run length encoded.

7. The method of claim 1, further comprising identifying a sample number associated with the second point.

8. A system for searching multiple related timelines representing a sequence of video images, the system comprising processor electronics configured to:

identify a first point on a first timeline associated with a sequence of video images, wherein the sequence of video images is comprised of one or more samples;

determine a search range on a second timeline associated with the sequence of video images based on a positive offset and a negative offset associated with the one or more samples; and

search the second timeline based on the determined search range for a second point that corresponds to the identified first point.

9. The system of claim 8, wherein the processor electronics are further configured to associate a display offset with each of the samples comprising the sequence of video images and one or more of the display offsets can comprise a negative value.

10. The system of claim 9, wherein the processor electronics are further configured to determine a search range on the second timeline based on a maximum positive display offset and a maximum negative display offset associated with the one or more samples.

11. The system of claim 10, wherein the processor electronics are further configured to adjust the search range if the first point occurs within a decode duration or a display duration.

12. The system of claim 11, wherein the processor electronics are further configured to extend the search range backward in time by a period equal to the decode duration or the display duration in which the first point occurs.

13. The system of claim 9, wherein the processor electronics are further configured to store the display offsets associated with the samples comprising the sequence of video images in a data structure, wherein the display offsets are run length encoded.

14. The system of claim 8, wherein the processor electronics are further configured to identify a sample number associated with the second point.