METHOD AND APPARATUS FOR REPRESENTING AND IDENTIFYING FEATURE DESCRIPTIONS UTILIZING A COMPRESSED HISTOGRAM OF GRADIENTS

• US 20100226575A1
• Filed: 11/12/2009
• Published: 09/09/2010
• Est. Priority Date: 11/12/2008
• Status: Active Grant

• Current Assignee: Nokia Corporation, Stanford University
• Original Assignee: Nokia Corporation, Stanford University
• Inventors: Girod, Bernd, Chandrasekhar, Vijay, Grzeszczuk, Radek, Takacs, Gabriel
• Granted Patent: US 9,710,492 B2
• Time in Patent Office: Days
• US Class Current: 382/190
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06T 9/20 Contour coding, e.g. using detection of edges
• CPC Class Codes: G06T 9/40 Tree coding, e.g. quadtree, octree
• CPC Class Codes: G06V 10/50 by performing operations within image blocks; by using histograms, e.g. histogram of oriented gradients [HoG]; by summing image-intensity values; Projection analysis
• CPC Class Codes: H04N 19/14 Coding unit complexity, e.g. amount of activity or edge presence estimation H04N19/146 takes precedence
• CPC Class Codes: H04N 19/96 Tree coding, e.g. quad-tree coding

Abstract

A method, apparatus and computer program product may be provided for generating a plurality of compressed feature descriptors that can be represented by a relatively small number of bits, thereby facilitating transmission and storage of the feature descriptors. A method, apparatus and computer program product may also be provided for permitting a compressed representation of a feature descriptor to be compared with a plurality of compressed representations of feature descriptors of respective predefined features. By permitting the comparison to be performed utilizing compressed representations of feature descriptors, a respective feature descriptor may be identified without having to first decompress the feature descriptor, thereby potentially increasing the efficiency with which feature descriptors may be identified.

Claims

1. A method comprising:

determining a plurality of gradients for each of a plurality of cells of an image;

assigning the gradients for a respective cell to a respective one of a plurality of bins;

determining a plurality of feature descriptors, wherein each feature descriptor includes a representation of a distribution of gradients between the plurality of bins of a respective cell; and

compressing the plurality of feature descriptors.

2. A method according to claim 1 further comprising entropy coding compressed representations of the plurality of feature descriptors.

3. A method according to claim 1 further comprising providing for at least one of transmission or storage of compressed representations of the plurality of feature descriptors.

4. A method according to claim 1 further comprising selecting a bin configuration prior to assigning the gradients to respective bins, wherein selecting a bin configuration comprises selecting a bin configuration having a bin positioned at a location coinciding with the gradient having a greatest probability and being skewed in a common direction as the distribution of gradients.

5. A method according to claim 1 further comprising dividing the image into a plurality of cells prior to determining the plurality of gradients.

6. A method according to claim 1 wherein compressing the plurality of feature descriptors comprises utilizing tree coding to compress the plurality of feature descriptors.

7. An apparatus comprising at least one processor and at least one memory storing computer program code, wherein the at least one memory and stored computer program code are configured, with the at least one processor, to cause the apparatus at least to:

determine a plurality of gradients for each of a plurality of cells of an image;

assigning the gradients for a respective cell to a respective one of a plurality of bins;

determine a plurality of feature descriptors, wherein each feature descriptor includes a representation of a distribution of gradients between the plurality of bins of a respective cell; and

compress the plurality of feature descriptors.

8. An apparatus according to claim 7 wherein the at least one memory and stored computer program code are further configured, with the at least one processor, to entropy code compressed representations of the plurality of feature descriptors.

9. An apparatus according to claim 7 wherein the at least one memory and stored computer program code are further configured, with the at least one processor, to provide for at least one of transmission or storage of compressed representations of the plurality of feature descriptors.

10. An apparatus according to claim 7 wherein the at least one memory and stored computer program code are further configured, with the at least one processor, to select a bin configuration prior to assigning the gradients to respective bins by selecting a bin configuration having a bin positioned at a location coinciding with the gradient having a greatest probability and being skewed in a common direction as the distribution of gradients.

11. An apparatus according to claim 7 wherein the at least one memory and stored computer program code are further configured, with the at least one processor, to divide the image into a plurality of cells prior to determining the plurality of gradients.

12. An apparatus according to claim 7 wherein the at least one memory and stored computer program code are configured, with the at least one processor, to compress the plurality of feature descriptors by utilizing tree coding to compress the plurality of feature descriptors.

13. A method comprising:

comparing a compressed representation of a feature descriptor with a plurality of predetermined compressed representations of feature descriptors of respective predefined features; and

based upon comparison results, identifying the compressed representation of a feature descriptor to represent a predefined feature without first decompressing the feature descriptor.

14. A method according to claim 13 wherein comparing a compressed representation of a feature descriptor comprises determining a distance between the compressed representation of a feature descriptor and each predetermined compressed representation of a feature descriptor of a respective predefined feature.

15. A method according to claim 14 wherein identifying the compressed representation of a feature descriptor comprises identifying the predefined feature represented by the predetermined compressed representation of a feature descriptor that is separated by a distance less than a predefined threshold from the compressed representation of a feature descriptor.

16. A method according to claim 13 further comprising providing information regarding the predefined feature.

17. An apparatus comprising at least one processor and at least one memory storing computer program code, wherein the at least one memory and stored computer program code are configured, with the at least one processor, to cause the apparatus at least to:

compare a compressed representation of a feature descriptor with a plurality of predetermined compressed representations of feature descriptors of respective predefined features; and

based upon comparison results, identify the compressed representation of a feature descriptor to represent a predefined feature without first decompressing the feature descriptor.

18. An apparatus according to claim 17 wherein the at least one memory and stored computer program code are configured, with the at least one processor, to compare a compressed representation of a feature descriptor by determining a distance between the compressed representation of a feature descriptor and each predetermined compressed representation of a feature descriptor of a respective predefined feature.

19. An apparatus according to claim 18 wherein the at least one memory and stored computer program code are configured, with the at least one processor, to identify the compressed representation of a feature descriptor by identifying the predefined feature represented by the predetermined compressed representation of a feature descriptor that is separated by a distance less than a predefined threshold from the compressed representation of a feature descriptor.

20. An apparatus according to claim 17 wherein the at least one memory and stored computer program code are further configured, with the at least one processor, to provide information regarding the predefined feature.