Method of compressing a plurality of video images for efficiently storing, displaying and searching the plurality of video images

• US 6,009,204 A
• Filed: 10/23/1997
• Issued: 12/28/1999
• Est. Priority Date: 09/15/1995
• Status: Expired due to Term

• Current Assignee: Vulcan Patents LLC
• Original Assignee: Interval Research Corporation
• Inventors: Ahmad, Subutai
• Primary Examiner(s): Tadayon, Bijan
• Application Number:
  US08/956,928
• Time in Patent Office: 796 Days
• Field of Search: 382/232, 382/233, 382/234, 382/235, 382/236, 382/238, 382/239, 382/240, 382/241, 382/242, 382/243, 382/244, 382/248, 382/251, 382/252, 382/253, 382/250, 382/107, 348/384, 348/415, 348/416, 348/420, 348/405, 348/413, 348/699, 358/433, 358/539, 358/530, 358/432, 358/261.2, 358/261.3, 364/715.02, 395/94
• US Class Current: 382/236
• CPC Class Codes: G06F 16/7328 Query by example, e.g. a complete video frame or video sequence graphical querying G06F16/7335
• CPC Class Codes: G06F 16/739 in form of a video summary, e.g. the video summary being a video sequence, a composite still image or having synthesized frames
• CPC Class Codes: G06F 16/7847 using low-level visual features of the video content
• CPC Class Codes: G11B 27/28 by using information signals recorded by the same method as the main recording G11B27/22 takes precedence
• CPC Class Codes: H04N 19/107 between spatial and temporal predictive coding, e.g. picture refresh
• CPC Class Codes: H04N 19/132 Sampling, masking or truncation of coding units, e.g. adaptive resampling, frame skipping, frame interpolation or high-frequency transform coefficient masking
• CPC Class Codes: H04N 19/142 Detection of scene cut or scene change
• CPC Class Codes: H04N 19/146 Data rate or code amount at the encoder output
• CPC Class Codes: H04N 19/149 by estimating the code amount by means of a model, e.g. mathematical model or statistical model
• CPC Class Codes: H04N 19/15 by monitoring actual compressed data size at the memory before deciding storage at the transmission buffer
• CPC Class Codes: H04N 19/162 User input
• CPC Class Codes: H04N 19/179 the unit being a scene or a shot
• CPC Class Codes: H04N 19/503 involving temporal prediction adaptive coding with adaptive selection between spatial and temporal predictive coding H04N19/107; adaptive coding with adaptive selection among a plurality of temporal predictive coding modes H04N19/109
• CPC Class Codes: H04N 19/587 involving temporal sub-sampling or interpolation, e.g. decimation or subsequent interpolation of pictures in a video sequence
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/87 involving scene cut or scene change detection in combination with video compression

Abstract

A video image, characterized by a plurality of pixels, is compressed by deriving at least one parameter based upon principal component analysis. An image value for each video image is then determined for the one parameter. The image value associated with each video image is compared to an image value associated with another video image to determine a difference. Any one of the image values of each video image and another video image is discarded in the event the difference is below a threshold. The remaining video images are then stored. Using this method of compression, it becomes possible to search a video database to find a match between an inquiring video scene with a video database comprising a plurality of video scenes with each video scene having a plurality of video images.

Claims

1. A single pass method of compressing a plurality of video images into a lesser number of key images, with the number of said lesser number of key images being specified, with each image characterized by a plurality of pixels, said method comprising the steps of:

deriving at least one parameter for said plurality of video images;

determining an image value for each video image for said one parameter;

calculating a plurality of differences by comparing an image value associated with each video image to an image value associated with another video image;

discarding the smallest difference, and one of the video images associated with an image value of said smallest difference; and

continuing with said step of discarding until the number of video images remaining equal to said lesser number of key images.

2. The method of claim 1 wherein said another video image is immediately adjacent in time to said each video image.

3. The method of claim 1 wherein said deriving step derives a plurality of different parameters, each of which is derived by principal component analysis.

4. The method of claim 3 wherein said principal component analysis is performed locally with a different parameter for a different portion of each video image.

5. The method of claim 3 wherein said principal component analysis is performed globally with the same parameter used for the entirety of each video image.

6. The method of claim 5 wherein said determining step determines a plurality of image values for each video image, with one image value associated with one parameter.

7. The method of claim 6 wherein said calculating step calculates said difference in accordance with:

##EQU4## where k is an index to the plurality of parameters P is the total number of parameters

I_ik is the k parameter of image value I_i

I_jk is the k parameter of image value I_j

W_k is a weighing factor for parameter k.

8. The method of claim 7 wherein each of said weighing factor W_k for all parameters k are the same.

9. The method of claim 8 wherein each of said weighing factor W_k for all parameters k are not the same.

10. The method of claim 7 wherein I_i and I_j are image values associated with video images immediately adjacent in time.

11. The method of claim 7 wherein I_i and I_j are image values associated with video images not immediately adjacent in time.

12. The method of claim 1 wherein said one parameter is derived by discrete cosine transform.

13. The method of claim 1 wherein said one parameter is derived by Gabor filters.

14. The method of claim 1 wherein said one parameter is derived by wavelets.

15. The method of claim 1 wherein the number of key images is specified by a user.

16. The method of claim 1 wherein the number of key images is specified by a computer.

17. A single pass method of browsing by a user, a plurality of video images by compressing said plurality of video images into a lesser number of key images, with the number of said lesser number of key images being specified, with each image characterized by a plurality of pixels, said method comprising the steps of:

deriving at least one parameter for said plurality of video images;

determining an image value for each video image for said one parameter;

calculating a plurality of differences by comparing an image value associated with each video image to an image value associated with another video image;

discarding the smallest difference, and one of the video images associated with an image value of said smallest difference;

continuing with said step of discarding until the number of video images remaining equal to said lesser number of key images; and

displaying said video images not discarded.

18. The method of claim 17 further comprising the step of:

displaying the video images remaining after the discarding step to said user for browsing.

19. The method of claim 17 further comprising the step of:

printing the video images remaining after the discarding step to said user for printing.

20. In a video database having a plurality of video scenes, each scene having a plurality of video images, each of said video images characterized by a plurality of pixels, a method for searching said video database to find a match to a first plurality of video images, said method comprising:

compressing the video images of each video scene by;

determining an image value for each video image for said one parameter for said video scene;

calculating a plurality of differences by comparing an image value associated with each video image for said video scene to an image value associated with another video image of said video scene;

discarding the smallest difference, and one of the video images associated with an image value of said smallest difference of said video scene;

continuing with said step of discarding until the number of video images remaining equal to said lesser number of key images;

storing said video images remaining and their image values; and

comparing said image values associated with said first plurality of video images to said stored image values associated with each video scene to find a match between said first plurality of video images and one of said video scenes.

21. The method of claim 20 wherein said another video image for each scene is immediately adjacent in time to said each video image.

22. The method of claim 20 wherein said another video image for each scene is not adjacent in time to said each video image.

23. The method of claim 20 wherein said one parameter is derived by principal component analysis.

24. The method of claim 20 further comprising the steps of:

compressing said first plurality of video images into a lesser number of key images, with the number of said lesser number of key images being specified by a user, by;

deriving at least one parameter for said first plurality of video images;

determining an image value for each video image for said one parameter;

calculating a plurality of differences by comparing an image value associated with each video image to an image value associated with another video image;

discarding the smallest difference, and one of the video images associated with an image value of said smallest difference;

continuing with said step of discarding until the number of video images remaining equal to said lesser number of key images; and

storing said video images remaining and their associated image values.

25. The method of claim 20 wherein said one parameter is derived by discrete cosine transform.

26. The method of claim 20 wherein said one parameter is derived by Gabor filters.

27. The method of claim 20 wherein said one parameter is derived by wavelets.