Systems, circuits, and methods for efficient hierarchical object recognition based on clustered invariant features

• US 9,204,112 B2
• Filed: 02/07/2013
• Issued: 12/01/2015
• Est. Priority Date: 02/07/2012
• Status: Active Grant

• Current Assignee: STMicroelectronics SRL (STMicroelectronics NV)
• Original Assignee: STMicroelectronics SRL (STMicroelectronics NV)
• Inventors: Pasteris, Paolo, Condello, Giovanni, Pau, Danilo Pietro
• Primary Examiner(s): Shah, Utpal
• Assistant Examiner(s): PATEL, PINALBEN V
• Application Number:
  US13/762,267
• Publication Number:
  US 20130216143A1
• Time in Patent Office: 1,027 Days
• Field of Search: 382/225, 382/282, 382/190, 382/103, 382/219, 382/305, 382/173, 706/20
• US Class Current: 1/1
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: G06F 2218/08 Feature extraction
• CPC Class Codes: G06V 10/40 Extraction of image or video features
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]
• CPC Class Codes: G06V 20/20 in augmented reality scenes
• CPC Class Codes: H04N 19/124 Quantisation
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding

Abstract

One embodiment is a method for selecting and grouping key points extracted by applying a feature detector on a scene being analyzed. The method includes grouping the extracted key points into clusters that enforce a geometric relation between members of a cluster, scoring and sorting the clusters, identifying and discarding clusters that are comprised of points which represent the background noise of the image, and sub-sampling the remaining clusters to provide a smaller number of key points for the scene.

Claims

1. A method for selecting and grouping key points extracted by applying a feature detector on a scene being analyzed, the method comprising:

grouping the extracted key points into clusters that enforce a geometric relation between members of a cluster;

scoring and sorting the clusters based on the density of the key points in the clusters;

identifying and discarding clusters that are comprised of key points which represent the background noise of the image based on the densities of the clusters;

compressing the key points of the clusters that have not been discarded;

communicating these compressed key points over a communications network;

searching a reference image database using the compressed key points;

identifying at least one cluster that was not discarded based on the searching of the reference image database;

communicating the identity of the identified at least one cluster over the communications network;

generating feature descriptors from the key points of the identified at least one cluster; and

communicating the generated feature descriptors over the communications network.

2. The method of claim 1 comprising iteratively applying the operations of grouping through sub-sampling to a set of reference images including sets comprised of a single reference image.

3. The method of claim 2 further comprising using clusters information to match clusters in the two images by using a metric which is defined by selected invariant features descriptors and by exploiting the sub-sampled cluster data to reduce the complexity of the matching phase including an early discard of clusters that cannot be probably found between extracted clusters.

4. The method of claim 3 further comprising tracking multiple independently moving objects in the scene being analyzed.

5. The method of claim 3 further comprising detecting multiple objects found in the scene being analyzed.

6. A method for identifying a captured digital image in a reference image database, comprising:

detecting key points in the captured digital image;

grouping the key points into clusters;

selecting at least one of the clusters on the basis of the number of key points contained in each of the clusters;

compressing the key points in each of the selected clusters;

performing an initial search of a reference image database utilizing the compressed key points of the selected clusters;

identifying ones of the clusters for further analysis;

generating feature descriptors for the key points in the identified ones of the clusters;

compressing the generated feature descriptors; and

searching the reference image database using the compressed feature descriptors to identify a reference image or images that correspond to the captured digital image.

7. The method of claim 6 further comprising, after selecting ones of the clusters, generating feature descriptors for the remainder of the clusters in parallel with the operations of compressing the key points in the selected clusters through identifying ones of the clusters for further analysis.

8. The method of claim 6, wherein the feature descriptors comprise SIFT feature descriptors.

9. The method of claim 6 further comprising performing a geometric verification on the captured image and identified reference images.

10. A visual search system, comprising:

a local image capture device configured to capture digital images, detect key points in each of the captured digital images, cluster the key points to generate a plurality of key point clusters, and to subsample the detected key points for each image by selecting key point clusters on the basis of the number of key points contained in each of the clusters, the local image capture device further configured to compress the key points in the selected key point clusters and to communicate these compressed key points over a communications network;

a remote server system coupled to the communications network to receive the compressed key points and configured to perform an initial search of a reference image database based on the compressed key points, and the remote server system further configured to identify ones of the selected clusters for further analysis based on results of the initial search and to communicate the identity of these ones of the selected clusters over the communications network to the local image capture device;

wherein the local image capture device is further configured to receive the identity of the selected clusters for further analysis over the communications network and to generate feature descriptors from the key points of these identified selected clusters, compress the generated feature descriptors, and communicate these compressed feature descriptors over the communications network to the remote server system; and

wherein the remote server system receives the compressed feature descriptors for the identified selected clusters over the communications network and performs further searching of the reference image database using these compressed feature descriptors to identify an image in the reference image database that corresponds to the captured digital image, and to communicate information about the identified image in the reference image database over the communications network to the local image capture device.

11. The visual search system of claim 10 wherein the local image capture device comprises a smartphone including a camera configured to generate the captured digital images.

12. The visual search system of claim 10 wherein the local image capture device comprises at least one camera positioned on a vehicle, each camera configured to generate corresponding captured digital images.

13. The visual search system of claim 10 wherein the remote server system performs feature matching and geometric verification as part of the further searching of the reference image database using the compressed feature descriptors to identify an image in the reference image database.