System and method for content-based querying using video compression format

• US 20040071368A1
• Filed: 10/12/2002
• Published: 04/15/2004
• Est. Priority Date: 10/12/2002
• Status: Active Grant

• Current Assignee: Beijing Zitiao Network Technology Company Limited (ByteDance Ltd.)
• Original Assignee: International Business Machines Corporation
• Inventors: Iyer, Balakrishna Raghavendra, Natsev, Apostol Ivanov, Chadha, Atul
• Granted Patent: US 6,906,719 B2
• Time in Patent Office: Days
• US Class Current: 382/305
• CPC Class Codes: G06F 16/50 of still image data
• CPC Class Codes: G06F 16/53 Querying

Abstract

A visual query system, and associated method and computer program product enhance and accelerate content-based querying, and present a new image similarity measure using known or available software applications and hardware components of video compression systems. The present system encodes images as consecutive frames in a video sequence and uses the ratio between the file length of the compressed sequence and the original file length as a distance measure. The system considers the compression ratio to be an estimate of the entropy of the combined images, which can be used to estimate the amount of new information introduced from one image to the other.

Claims

1. A method of implementing a content based image query, comprising:

encoding at least two images in a sequence of frames;

using an encoding ratio as a distance measure between the two images; and

determining a degree of similarity between the two images by using the distance measure to estimate a differential amount of information between the two images.

2. The method of claim 1, wherein encoding the two images comprises compressing the two images as consecutive frames in a video sequence.

3. The method of claim 2, wherein using the encoding ratio comprises using a video compression ratio.

4. The method of claim 1, wherein the two images comprise a source image.

5. The method of claim 4, wherein the two images further comprise a candidate image from a plurality of candidate images.

6. The method of claim 5, wherein the candidate image is stored on a local repository.

7. The method of claim 5, wherein the candidate image is stored on a networked repository.

8. The method of claim 5, wherein the candidate image is stored on a web-linked repository.

9. The method of claim 5, wherein the source image contains a digital image.

10. The method of claim 5, wherein the source image contains a picture.

11. The method of claim 5, wherein the source image contains a graph.

12. The method of claim 5, wherein the source image contains a visual representation.

13. The method of claim 5, further comprising multiplexing the source image with a candidate image.

14. The method of claim 13, wherein encoding the two images comprises encoding the two images into three separate data streams.

15. The method of claim 14, wherein encoding the two images into three separate data streams comprises:

encoding a first stream that includes the source image to obtain a first compressed data stream with a file length C(A);

encoding a second stream that includes the candidate image to obtain a second compressed data stream with a file length C(B); and

encoding a third stream that includes the source image and the candidate image to obtain a third compressed data stream with a file length C(A&

B).

16. The method of claim 15, further comprising calculating the distance measure, distance (A,B), between the source and candidate object, as follows:

distance (A,B)=[C(A&

B)/(C(A)+C(B))].

17. The method of claim 16, wherein determining the degree of similarity between the two images, similarity (A,B), comprises calculating the similarity between the two images, as follows:

similarity (A,B)=1−

distance (A,B), where;

0≦

similarity (A,B)<

1.

18. The method of claim 5, further comprising retrieving candidate image within a predetermined distance measure from the source image.

19. The method of claim 18, further comprising indexing the candidate images.

20. The method of claim 19, further comprising anchoring the candidate images using selected fixed anchors.

28. The computer program product of claim 13, wherein the first set of instruction codes encodes the two images into three separate data streams:

a first stream that includes the source image to obtain a first compressed data stream with a file length C(A);

a second stream that includes the candidate image to obtain a second compressed data stream with a file length C(B); and

a third stream that includes the source image and the candidate image to obtain a third compressed data stream with a file length C(A&

B).

29. The computer program product of claim 28, wherein the second set of instruction codes calculates the distance measure, distance (A,B), between the source and candidate object, as follows:

distance (A,B)=[C(A&

B)/(C(A)+C(B))], and

further calculates the degree of similarity between the two images, similarity (A,B), as follows;

similarity (A,B)=1−

distance (A,B), where;

0≦

similarity (A,B)<

1.

21. A computer program product having instruction codes for implementing a content based image query, comprising:

a first set of instruction codes for encoding at least two images in a sequence of frames;

the first set of instruction codes uses an encoding ratio as a distance measure between the two images; and

a second set of instruction codes for determining a degree of similarity between the two images by using the distance measure to estimate a differential amount of information between the two images.

22. The computer program product of claim 21, wherein the first set of instruction codes compresses the two images as consecutive frames in a video sequence.

23. The computer program product of claim 22, wherein the encoding ratio includes a video compression ratio.

24. The computer program product of claim 21, wherein the two images comprise a source image and a candidate image from a plurality of candidate images.

25. The computer program product of claim 24, wherein the candidate image is stored on any one or more of a local repository, a networked repository, and a web-linked repository.

26. The computer program product of claim 24, wherein the source image contains any one or more of a digital image, a picture, a graph, and a visual representation.

27. The computer program product of claim 24, further comprising a multiplexer that multiplexes the source image a candidate image.

30. The computer program product of claim 24, further comprising a third set of instruction codes for indexing the candidate images.

31. A visual query system for implementing a content based image query, comprising:

means for encoding at least two images in a sequence of frames;

the encoding means uses an encoding ratio as a distance measure between the two images; and

means for determining a degree of similarity between the two images by using the distance measure to estimate a differential amount of information between the two images.

32. The system of claim 31, wherein the encoding means compresses the two images as consecutive frames in a video sequence.

33. The system of claim 32, wherein the encoding ratio includes a video compression ratio.

34. The system of claim 31, wherein the two images comprise a source image and a candidate image from a plurality of candidate images.

35. The system of claim 34, wherein the candidate image is stored on any one or more of a local repository, a networked repository, and a web-linked repository.

36. The system of claim 34, wherein the source image contains any one or more of a digital image, a picture, a graph, and a visual representation.

37. The system of claim 34, further comprising means for multiplexing the source image and the candidate image.

38. The system of claim 33, wherein the encoding means encodes the two images into three separate data streams:

a first stream that includes the source image to obtain a first compressed data stream with a file length C(A);

a second stream that includes the candidate image to obtain a second compressed data stream with a file length C(B); and

a third stream that includes the source image and the candidate image to obtain a third compressed data stream with a file length C(A&

B).

39. The system of claim 38, wherein the means for determining the degree of similarity calculates the distance measure, distance (A,B), between the source and candidate object, as follows:

distance (A,B)=[C(A&

B)/(C(A)+C(B))], and

further calculates the degree of similarity between the two images, similarity (A,B), as follows;

similarity (A,B)=1−

distance (A,B), where;

0≦

similarity (A,B)<

1.

40. The system of claim 34, further comprising a clustering means for indexing the candidate images.