System and method for determining a level of similarity among more than one image and a segmented data structure for enabling such determination

• US 6,373,979 B1
• Filed: 01/29/1999
• Issued: 04/16/2002
• Est. Priority Date: 01/29/1999
• Status: Expired due to Term

• Current Assignee: LG Electronics, Inc. (LG Corporation)
• Original Assignee: LG Electronics, Inc. (LG Corporation)
• Inventors: Wang, Jia
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): SHERALI, ISHRAT I
• Application Number:
  US09/239,972
• Time in Patent Office: 1,173 Days
• Field of Search: 382/162, 382/164-165, 382/190, 382/195, 382/205, 382/209, 382/215-220, 382/221, 382/224-225, 382/305, 382/170-171, 382/173, 382/236, 382/103, 382/107, 345/968, 345/431, 345/326, 345/348, 345/328, 345/589, 345/700, 345/835, 707/104, 707/3-6, 707/104.1, 348/699-700, 348/722
• US Class Current: 382/165
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/10024 Color image
• CPC Class Codes: G06T 2207/20021 Dividing image into blocks, subimages or windows
• CPC Class Codes: G06T 7/337 involving reference images or patches
• CPC Class Codes: G06T 7/90 Determination of colour characteristics
• CPC Class Codes: G06T 7/97 Determining parameters from multiple pictures depth or shape recovery from multiple images G06T7/55; stereo camera calibration G06T7/85
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors

Abstract

A system and method is disclosed for determining a level of similarity among more than one image. Anticipated spatial characteristics of an image are used for automatically identifying segments within the image and for identifying weights to be added to the color characteristics associated with the identified segments. To determine similarity, comparisons are made between weighted color characteristics of corresponding segments of different images. The identified segments have attributes such as size, position and number which are based on the anticipated spatial characteristics of the image. The anticipated spatial characteristics of the image include, among other things, differences in image characteristics that are anticipated at relative positions within the image. Additionally, a standard for representing image data including feature descriptors for color characteristics is disclosed, the color feature descriptor being divided into plural units corresponding to segments within the image identified based on anticipated spatial characteristics therefor.

Claims

1. A method for determining similarity among more than one image, comprising:

automatically identifying segments within an image by recursively identifying segments within the image using a number of iterations of the recursive identification of segments based on a variance detected among color characteristics of image data within segments previously identified, and the identified segments having attributes that are based on anticipated spatial characteristics of the image; and

comparing color characteristics of image data within the identified segments of the image to color characteristics of image data within corresponding segments of at least one other image to determine similarity among the images.

2. The method recited by claim 1, wherein the anticipated spatial characteristics of the image include differences in image characteristics that are anticipated at relative positions within the image.

3. The method recited by claim 1, wherein the anticipated spatial characteristics of the image include at least one of an anticipated position of an object within the image and an anticipated difference in coloration between two positions of the image.

4. The method recited by claim 1, wherein the attributes of identified segments include at least one of number, position and size of segments.

5. The method recited by claim 4, wherein the size of segments is nonuniform so as to apply unequal emphasis on features within the image being characterized.

6. The method recited by claim 1, wherein the color characteristics are compared to determine an occurrence of change in image characteristics.

7. The method recited by claim 1, wherein the color characteristics are compared to identify similar images.

8. A method for determining similarity among more than one image, comprising:

identifying segments within an image with recursive identification of segments using a number of iterations based on a variance detected among color characteristics of image data within segments previously identified;

computing color characteristics of image data within each of several identified segments of an image;

comparing the color characteristics of image data within the identified segments of the image to color characteristics of image data within corresponding segments of at least one other image;

biasing to achieve a greater emphasis for comparisons of color characteristics between selected segments within the images; and

determining a similarity among the images based on the results of the comparison which reflect the bias.

9. The method recited by claim 8, wherein the biasing involves applying weights to the color characteristics associated with each of the identified segments based on anticipated spatial characteristics of the images.

10. The method recited by claim 9, wherein the comparing involves:

comparing the weighted color characteristics of image data within the identified segments of the image to the weighted color characteristics of image data within corresponding segments of at least one other image; and

applying a greater emphasis;

to comparisons of segments whose color characteristics are weighted more heavily when determining the similarity among images.

11. The method recited by claim 9, wherein the anticipated spatial characteristics of the image include differences in image characteristics that are anticipated at relative positions within the image.

12. The method recited by claim 9, wherein the anticipated spatial characteristics of the image include at least one of an anticipated position of an object within the image and an anticipated difference in coloration between two positions of the image.

14. The method recited by claim 8, wherein weighted color characteristics are compared to determine an occurrence of change in image characteristics.

15. The method recited by claim 8, wherein weighted color characteristics are compared to identify similar images.

13. The method recited by clam 8, further comprising:

determining a number, position and size of segments to be identified within the image based on spatial characteristics of the image.

16. A method for determining similarity among more than one image, comprising:

automatically identifying segments within an image by recursively identifying segments within the image using a number of iterations of the recursive identification of segments based on a variance detected among color characteristics of image data within segments previously identified, and at least one of the identified segments overlapping other of the identified segments; and

comparing color characteristics of image data within the identified segments to color characteristics of image data within corresponding segments of at least one other image to determine similarity among the images.

17. The method recited by claim 16, wherein the overlapping segment is completely overlapping other identified segments.

18. The method recited by claim 16, further comprising:

determining attributes of segments identified within the image based on spatial characteristics of the image.

19. The method recited by claim 16, wherein the segments identified within the image include attributes of at least one of number, position and size.

20. The method recited by claim 19, wherein the size of segments is nonuniform so as to apply unequal;

emphasis on features within the image being characterized.

21. The method recited by claim 19, wherein the images have anticipated spatial characteristics including differences in image characteristics that are anticipated at relative positions within the image.

22. The method recited by claim 19, wherein the images have anticipated spatial characteristics including at least one of an anticipated position of an object within the image and an anticipated difference in coloration between two positions of the image.

23. The method recited by claim 16, wherein the color characteristics are compared to determine an occurrence of change in image characteristics.

24. The method recited by claim 16, wherein the color characteristics are compared to identify similar images.

25. A data structure comprising:

an image data field corresponding to data representing an image; and

a color feature descriptor field that includes multiple units representing color characteristics of corresponding segments identified within the images,

wherein the segments are automatically identified with recursive identification of segments using a number of iterations based on a variance detected among color characteristics of image data within segments previously identified.

26. The data structure of claim 25, wherein the segments identified within the image are based on anticipated spatial characteristics of the image so that the units of the color feature descriptor field are based on the anticipated spatial characteristics of the image.