Method and apparatus for classifying and identifying images

• US 5,963,670 A
• Filed: 02/12/1996
• Issued: 10/05/1999
• 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): Au, Amelia
• Assistant Examiner(s): AHMED, SAMIR ANWAR
• Application Number:
  US08/600,378
• Time in Patent Office: 1,331 Days
• Field of Search: 382/176, 382/180, 382/199, 382/305, 382/306, 382/224
• 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 and methods of operation within such a system are disclosed. 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 predefined or generated by an image processing system.

Claims

1. A method for applying a template to an image comprising the steps of:

(a) providing a first image patch having a first image patch size;

(b) providing a second image patch having a second image patch size;

(c) placing the first image patch in a first image patch position;

(d) placing the second image patch in a second image patch position;

(e) identifying a first non-geometric property of the first image patch;

(f) identifying a first like non-geometric property of the second image patch and;

(g) identifying a first relative relationship between the first property of the first image patch and the first property of the second image patch wherein the relative relationship qualitatively relates the property of the first image patch to the property of the second image patch.

2. The method of claim 1 further comprising the step of defining a relative position between the first image patch and the second image patch wherein the relative position of the first image patch with respect to the second image patch corresponds to one of:

(1) above;

(2) below;

or (3) aligned with.

3. The method of claim 1 wherein:

the first non-geometric property of the first image patch corresponds to a first photometric property of the first image page and is at least one of a chromatic property and a luminance property of the first image patch; and

the first non-geometric property of the second image patch corresponds to a second photometric property of the second image patch and is at least one of a chromatic property and a luminance property of the second image patch.

4. The method of claim 3 wherein the first relative photometric relationship defines a photometric relationship of the first image patch as being one of:

(1) less than;

(2) greater than;

or (3) equal to with respect to the like photometric property.

5. The method of claim 3 further comprising the step of changing the first relative relationship between the first photometric property of the first image patch and the first photometric property of the second image patch including the step of decreasing a distance relationship between the first image patch and the second image patch.

6. The method of claim 5 further comprising the step of changing the size of at least one of the first and second image patches.

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

providing a third image patch; and

identifying a first one of an absolute position and an absolute photometric property of the third image patch with respect to at least one of the first and second image patches.

8. An apparatus for generating a class model from an image, the apparatus comprising:

means for dividing the image into a plurality of image region;

means for identifying a plurality of image region attributes in each of the plurality of image regions;

means for identifying first ones of the plurality of image regions having at least one like image region attribute and at least one like relative relationship to at least one other image region of the plurality of image regions;

means for identifying second ones of the plurality of image regions having at least one like image region attribute and at least one like relative relationship to at least one other image region of the plurality of image regions wherein the first ones of the plurality of image regions have at least one like attribute and one like relative relationship which is different from the at least one like image region attribute and at least one like relative relationship of the second ones of the plurality of image regions; and

means for grouping the first ones of the plurality of image regions into a first image region group and for grouping the second ones of the plurality of image regions into a second image region group.

9. The apparatus of claim 8 further comprising a relation detector coupled to the means for grouping, the relation detector for determining consistent relationships between the first and second image region groups.

10. The apparatus of claim 9 further comprising means for forming an image model from the consistent relationships between the first and second image region groups.

11. A method for processing an image, the method comprising the steps of:

(a) dividing the image into a plurality of image regions;

(b) identifying first ones of the plurality of image regions having at least one like attribute and at least one like relative relationship to at least one other image region of the plurality of image regions;

(c) identifying second ones of the plurality of image regions having at least one like attribute and at least one like relative relationship to at least one other image region of the plurality of image regions wherein the first ones of the plurality of image regions have at least one like attribute and at least one like relative relationship which is different from the like attribute and at least one like relative relationship of the second ones of the plurality of image regions;

(d) grouping the first ones of the plurality of image regions into a first image region group; and

(e) grouping the second ones of the plurality of image regions into a second image region group.

12. The method of claim 11 further comprising the step of determining consistent relationships between the first and second image region groups.

13. The method of claim 12 further comprising the step of forming an image model from the consistent relationships between the first and second image region groups.

14. An image processing system comprising:

(a) an image database;

(b) an image retrieval device coupled to said database for retrieving images from said image database;

(c) a relationship processor, coupled to said image retrieval device, said relationship processor for identifying relationships between image characteristics of images retrieved from said database;

(d) a template generator, coupled to said relationship processor, said template generator for encoding relationships between characteristics which are consistent between images retrieved from said database as an image template; and

(e) an image detector for applying the image template to images in said image database to detect images belonging to a particular class of images stored in said image database.

15. The image processing system of claim 14 wherein said image detector detects novel images having relative relationships between selected image regions thereof which are consistent with the relative relationships encoded in the image template.

16. The image processing system of claim 15 wherein said image detector includes means for aligning, via the image template, a first region of a first image and a second region of a second different image.

17. The method of claim 16 further comprising the step of associating each of the relative relations from a first image region with a second different image region.

18. The method of claim 17 wherein the second different image region has at least one boundary point which contacts the boundary point of the first image region.

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

(a) selecting a first image region from a plurality of image region;

(b) identifying a first relative relationship between a first property corresponding to a first one of a color attribute and a texture attribute of a first one of the plurality of image regions and a first one of a color attribute and a texture attribute of a second one of the plurality of image regions; and

(c) storing the relative relationship in a storage device.

20. The method of claim 19 wherein the first relative relationship is a first one of a plurality of relative relationships, each of the plurality of relative relationships being between the first property of the first one of the first plurality of image regions and the first property of the second one of the plurality of image regions.

21. The method of claim 20 wherein the relative relationships correspond to relative spatial and photometric relationships between the first and second image regions.

22. The method of claim 21 further comprising the step of associating the relative relationships of the second image region with the first image region.

23. The method of claim 22 further comprising the steps of:

retrieving a digital image from a database; and

partitioning the digital image into a plurality of image regions.