Method and apparatus for classifying and identifying images

• US 6,549,660 B1
• Filed: 03/17/1999
• Issued: 04/15/2003
• Est. Priority Date: 02/12/1996
• Status: Expired due to Term

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Lipson, Pamela R., Grimson, W. Eric L., Sinha, Pawan, Poggio, Tomaso
• Primary Examiner(s): AHMED, SAMIR ANWAR
• Application Number:
  US09/270,995
• Time in Patent Office: 1,490 Days
• Field of Search: 382/176, 382/171, 382/180, 382/191, 382/199, 382/224, 382/305, 382/306, 382/173, 382/164, 382/225, 707/1, 358/453, 358/455, 358/456, 358/457, 358/458, 358/459, 358/460, 358/461, 345/581-582
• US Class Current: 382/224
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: G06F 16/5862 using texture
• CPC Class Codes: G06F 18/28 Determining representative reference patterns, e.g. by averaging or distorting; Generating dictionaries
• CPC Class Codes: G06V 20/35 Categorising the entire scene, e.g. birthday party or wedding scene

Abstract

An image processing system for generating a class model from an image by identifying relative relationships between different properties of different image regions, includes a region partitioner a relationship processor, a template generator and an image detector. The image processing system utilizes a class model defined by one or more relative relationships between a plurality of image patches. The relative relationships describe the overall organization of images within an image class. The relative relationships are encoded in a global deformable template which can be used to classify or detect images. The class model may be pre-defined or generated by the image processing system. In one embodiment, the class model is generated from a low resolution image.

Claims

1. An image processing method comprising:

(a) first providing a low-frequency subsampled image;

(b) after the providing step, partitioning the low-frequency subsampled image into a plurality of image regions;

(c) identifying a first relative relationship between a photometric property of a first one of the plurality image regions an a photometric property of a second one of the plurality of image regions; and

(d) storing a value representative of the relative relationship in a storage device.

2. The method of claim 1 wherein the first relative relationship is a first one of a plurality of relative relationships, each of the plurality of relative relationships being between a property of the first one of the first plurality of low-frequency subsampled image regions and a like property of the second one of the plurality of low-frequency subsampled image regions.

3. The method of claim 2 further comprising identifying a relative spatial relationship between the first one of the plurality image regions and the second one of the plurality image regions.

4. The method of claim 3 further comprising the steps of:

identifying a plurality of properties in the low-frequency subsampled image;

selecting predetermined ones of the plurality of properties; and

identifying relative relationships between the selected ones of the plurality of properties.

5. The method of claim 1 wherein providing a low-frequency subsampled image includes retrieving an image from an image storage device.

6. The method of claim 5 further comprising:

selecting one of the plurality of low-frequency subsampled transformed images;

identifying a plurality of properties in the selected low-frequency subsampled transformed image; and

representing each of the plurality of properties as a value; and

storing the values in a storage device.

7. The method of claim 3 wherein providing a low-frequency subsampled image includes retrieving an image from an image storage device.

8. The method of claim 7 wherein generating at least one low resolution image includes:

retrieving an original image from the image storage device;

transforming the original image into a plurality of transformed images, each of the plurality of transformed images corresponding to the original image at a different level of low frequency content;

subsampling each of the plurality of transformed images to provide a plurality of low-frequency subsampled images.

9. A method of building a class model comprising:

(a) first selecting a plurality of different low-frequency subsampled images, each of the low-frequency subsampled images belonging to a predetermined class of images;

(b) after the selecting step, partitioning each of the plurality of low-frequency subsampled images into a plurality of image regions;

(c) for each of the plurality of images, performing;

(1) selecting an image region from the plurality of image regions;

(2) computing a plurality of relative relationships between at least one property of the selected image region and a like property of selected ones of other image regions in the image;

(3) selecting a next image region; and

(4) repeating steps (2) and (3) for each of the plurality of image regions in the image; and

(5) identifying relative relationships of region properties in each of the image regions which are consistent between each of the plurality of images; and

(d) for each of the relative relationships, storing a value representative of the relative relationship in a storage device.

10. The method of claim 9 further comprising:

expressing predetermined ones of the relative relationships of each image region as an equivalence class wherein each relative relationship may be expressed as a corresponding one of a plurality of equivalence classes.

11. The method of claim 10 further comprising associating each of the relative relationships from a first image region with a second different image region.

12. The method of claim 11 further comprising:

expressing predetermined ones of the relative relationships of each image region as an equivalence class wherein each relative relationship may be expressed as a corresponding one of a plurality of equivalence classes.

13. The method of claim 12 further comprising determining if any of the plurality of low-frequency subsampled images include a predetermined image property.

14. The method of claim 13 wherein partitioning each of the plurality of low-frequency subsampled images into a plurality of image regions includes partitioning each of the plurality of images into a plurality of like-sized image regions.

15. An image processing system comprising:

means for providing a low-frequency subsampled image from an original image;

a region partitioner means for dividing the low-frequency subsampled image into a plurality of image regions, each of the plurality of image regions having a plurality of properties; and

a relationship processor for identifying a relative relationship between a first property in a first one of the plurality of image regions and a second one of the plurality of image regions.

16. The method of claim 15 wherein partitioning each of the plurality of low-frequency subsampled images into a plurality of image regions includes partitioning each of the plurality of images into a plurality of like-sized image regions.

17. The apparatus of claim 16 further comprising an association processor for associating the relative relationships of the second one of the plurality of image regions with the first one of the plurality of image regions.

18. The apparatus of claim 17 further comprising means for defining at least one absolute relationship between at least one attribute of a first one of said plurality of image regions and a second one of said plurality of image regions.

19. A method of building a class model comprising the steps of:

(a) selecting a plurality of different low resolution images, each of the images belonging to a predetermined class of images;

(b) partitioning each of the plurality of images into a plurality of image regions;

(c) for each of the plurality of images, performing the steps of;

(1) selecting an image region from the plurality of image regions;

(2) computing a plurality of relative relationships between at least one property of the selected image region and a like property of selected ones of other image regions in the image;

(3) selecting a next image region; and

(4) repeating steps (2) and (3) for each of the plurality of image regions in the image; and

(5) identifying relative relationships of region properties in each of the image regions which are consistent between each of the plurality of images; and

(d) for each of the relative relationships, storing a value representative of the relative relationship in a storage device;

(e) expressing predetermined ones of the relative relationships of each image region as an equivalence class wherein each relative relationship may be expressed as a corresponding one of a plurality of equivalence classes; and

(f) associating each of the relative relationships from a first image region with a second different image region, wherein the second different image region has at least one boundary point which contacts the boundary point of the first image region.

20. The method of claim 19 further comprising a step of determining if any of the plurality of low resolution images include a predetermined image property.

21. The method of claim 20 wherein the step of partitioning each of the plurality of images into a plurality of image regions includes a step of partitioning each of the plurality of images into a plurality of like-sized image regions.

22. The method of claim 19 wherein the step of selecting a plurality of different low resolution images includes a step of retrieving an image from an image storage device.

23. The method of claim 19 wherein the relative relationships correspond to relative spatial relationships between at least one property of the selected image region and a like property of selected ones of other image regions in the image.

24. The method of claim 19 wherein the relative relationships correspond to relative photometric relationships between at least one property of the selected image region and a like property of selected ones of other image regions in the image.

25. The method of claim 19 further comprising the steps of:

retrieving a digital image from a database; and

partitioning the digital image into a plurality of image regions.

26. A method of generating a class model comprising the steps of:

providing a reference image;

first eliminating high frequency image components from the reference image to produce a low frequency image;

after the eliminating step, subsampling the low frequency image to provide a low resolution image;

after subsampling, selecting from the low resolution image a first low resolution image region from a plurality of low resolution image regions in the low resolution image, the first low resolution image region comprising an array of pixels and having a plurality of image properties;

identifying a first relative relationship between an image property of the first one of the plurality of low resolution image regions and a like property of a second one of the plurality of low resolution image regions; and

storing, in a storage device, a value representative of the relative relationship between the image property of the first and second low resolution image regions.

27. The method of claim 26 wherein the first relative relationship is a first one of a plurality of relative relationships with each of the relative relationships derived solely from the low resolution image regions.

28. The method of claim 26 further comprising:

partitioning the low resolution image into a plurality of image regions, each of the plurality of image regions having one or more properties; and

computing relative relationships between two or more of the plurality of image regions.

29. The method of claim 28 wherein computing relative relationships between two or more of the plurality of image regions comprises computing relative photometric and spatial