Hierarchical, probabilistic, localized, semantic image classifier

• US 20020122596A1
• Filed: 01/02/2001
• Published: 09/05/2002
• Est. Priority Date: 01/02/2001
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bradshaw, David Benedict
• Granted Patent: US 7,194,134 B2
• Time in Patent Office: Days
• US Class Current: 382/226
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06V 30/248 involving plural approaches, e.g. verification by template match; Resolving confusion among similar patterns, e.g. "O" versus "Q" G06V30/242 takes precedence

Abstract

Described herein is a technology for semantically classifying areas of an image (and/or the images themselves) as one of a number of multiple discriminating categories. More particularly, the technology employs one or more hierarchical, probabilistic techniques for performing such classification. Such technology is particularly useful in fields of image classification and image retrieval. The architecture of such technology employs multiple hierarchical layers. The architecture is based on modeling class likelihoods at each of such layers separately and then combining these to form an overall estimate of the posterior, conditioned on the data. The task of combining the estimated class likelihoods at each layer is made more efficient by assuming statistical independence between layers. This abstract itself is not intended to limit the scope of this patent. The scope of the present invention is pointed out in the appending claims.

Claims

1. A method of semantically classifying an image, the method comprising:

obtaining an image and sub-dividing such image into multiple hierarchical layered blocks, the blocks within a layer being at least partially coextensive;

determining a posterior estimate of class membership of a group of hierarchical layered blocks, the estimate being based upon class likelihoods of the hierarchical layered blocks in the group, such likelihood being conditioned on data extracted from hierarchical layered blocks in the group;

semantically classifying a portion of such image based upon the posterior estimate of class membership conditioned on the data extracted from the group of hierarchical layered blocks local to such portion.

2. A method as recited in claim 1, wherein the determining comprises:

determining an estimated class likelihood of each block in the group of hierarchical layered blocks;

combining the estimated class likelihoods of hierarchical layered blocks in the group into a posterior estimate of semantic class membership.

3. A method as recited in claim 1 further comprising:

repeating the classifying for each of multiple portions that substantially cover the entire image;

categorizing the entire image based upon the result of such repeating of the classifying.

4. A method as recited in claim 1, wherein each successively lower layer of the multiple hierarchical layered blocks is comprised of one or more blocks which are smaller than and at least partially coextensive with one or more blocks in a layer immediately above.

5. A method as recited in claim 1, wherein the determining comprises extracting low-level features from blocks.

6. A method as recited in claim 5, wherein the low-level features comprise color and textures.

7. A method as recited in claim 6, wherein the extracting extracts color low-level features by an Ohta decomposition.

8. A method as recited in claim 6, wherein the extracting extracts texture low-level features by a complex wavelet transform.

9. A method as recited in claim 1, wherein the class likelihoods are estimated in one-dimensional space.

10. A method as recited in claim 1, wherein a classification that results from the semantically classifying step is binary.

11. A method as recited in claim 1, wherein a classification that results from the semantically classifying step is selected from a group consisting of these binary sets:

sky or not-sky;

grass or not-grass;

natural or man-made;

inside or outside;

hair or not-hair;

face or not-face.

12. An image retrieval method comprising:

a semantic image classification method as recited in claim 1;

searching for images matching a given query in an image library containing images having portions thereof classified using the semantic image classification method.

13. A computer-readable medium having computer-executable instructions that, when executed by a computer, performs the method as recited in claim 1.

15. A system as recited in claim 14 further comprising a hierarchy definer configured to subdivide the image into multiple hierarchical sets of blocks, each successively lower layer of a hierarchical set of blocks comprising one or more blocks which are smaller than and at least partially coextensive with one or more blocks in a layer immediately above.

16. A system as recited in claim 14, wherein the low-level features comprise color and textures.

17. A system as recited in claim 16, wherein the block analyzer extracts color low-level features by an Ohta decomposition.

18. A system as recited in claim 16, wherein the block analyzer extracts texture low-level features by a complex wavelet transform.

19. A system as recited in claim 14, wherein the class likelihoods are estimated in one-dimensional space.

20. A system as recited in claim 14, wherein the discriminating semantic classifications are selected from a group consisting of these binary sets:

sky or not-sky;

grass or not-grass;

natural or man-made;

inside or outside;

hair or not-hair;

face or not-face.

22. A computer-readable medium having stored thereon a data structure, comprising an image library containing images having portions thereof classified using a semantic image classification system as recited in claim 14.

14. A semantic image classification system, comprising:

a block analyzer configured to extract low-level features of blocks of an image and estimate class likelihoods for each block, a class being a discriminating semantic classification and a block being a portion of the image;

a combiner configured to generate a posterior estimate of class membership based on combining estimated class likelihoods of hierarchical sets of blocks, a hierarchical set of blocks being a hierarchical organized and associated blocks that are, at least, partially coextensive;

an image classifier configured to determine and classify one of multiple discriminating semantic classifications to localized portions of the image based upon the posterior estimate of class membership of blocks comprising such portions.

21. An image retrieval system comprising:

a semantic image classification system as recited in claim 14;

a semantic image querier configured to search for images matching a given query in an image library containing images having portions thereof classified using the semantic image classification system.

23. A computer-readable medium having stored thereon a data structure, comprising:

a first data field containing data representing an image;

a second data field derived from the first field by determining one of multiple discriminating semantic classifications of portions of the image via hierarchical and probabilistic analyses;

a third data field functioning to delimit the end of the data structure.

24. A computer-readable medium having computer-executable instructions that, when executed by a computer, performs the method comprising:

obtaining an image and sub-dividing such image into multiple hierarchical layered and at least partially coextensive blocks;

determining posterior estimate of class membership by combining estimated likelihoods of hierarchical layered blocks;

classifying a portion of such image as one of the multiple discriminating semantic classifications based upon the posterior estimate of class membership of hierarchical layered blocks local to such portion.