Method for detecting a plurality of instances of an object

• US 9,158,988 B2
• Filed: 06/12/2013
• Issued: 10/13/2015
• Est. Priority Date: 06/12/2013
• Status: Active Grant

• Current Assignee: Symbol Technologies, LLC (Zebra Technologies Corporation)
• Original Assignee: Symbol Technologies, LLC (Zebra Technologies Corporation)
• Inventors: Patel, Ankur R, Super, Boaz J
• Primary Examiner(s): CONWAY, THOMAS A
• Application Number:
  US13/916,326
• Publication Number:
  US 20140369607A1
• Time in Patent Office: 853 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: G06F 18/2321 using statistics or function optimisation, e.g. modelling of probability density functions
• CPC Class Codes: G06F 18/23211 with adaptive number of clusters
• CPC Class Codes: G06Q 10/087 Inventory or stock management, e.g. order filling, procurement or balancing against orders
• CPC Class Codes: G06V 10/255 Detecting or recognising potential candidate objects based on visual cues, e.g. shapes
• CPC Class Codes: G06V 10/44 Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]
• CPC Class Codes: G06V 10/763 Non-hierarchical techniques, e.g. based on statistics of modelling distributions
• CPC Class Codes: G06V 20/52 Surveillance or monitoring of activities, e.g. for recognising suspicious objects recognising microscopic objects G06V20/69

Abstract

An improved object recognition method is provided that enables the recognition of many objects in a single image. Multiple instances of an object in an image can now be detected with high accuracy. The method receives a plurality of matches of feature points between a database image and a query image and determines a kernel bandwidth based on statistics of the database image. The kernel bandwidth is used in clustering the matches. The clustered matches are then analyzed to determine the number of instances of the object within each cluster. A recursive geometric fitting can be applied to each cluster to further improve accuracy.

Claims

1. A method of determining an instance of an object in a query image, comprising the steps of:

receiving a plurality of matches of feature points between the query image and a database image;

deriving a kernel bandwidth for a clustering method by analyzing statistics of the database image;

applying the clustering method with the derived kernel bandwidth to the matches of feature points between the query image and the database image thereby generating at least one cluster;

determining a number of instances of the object in the database image within the query image; and

determining whether other database images are available; and

repeating the steps of receiving, deriving, applying, and determining, for at least one of the other database images.

2. The method of claim 1, wherein the analyzing statistics of the database image comprises:

determining a unimodal kernel density of a feature point distribution of the database image.

3. The method of claim 1, wherein the clustering method comprises a spatial clustering method.

4. The method of claim 1, wherein determining the number of instances of the object comprises:

fitting and verifying a geometric model to each cluster of the at least one cluster to estimate an object boundary.

5. The method of claim 4, wherein fitting and verifying a geometric model comprises:

recursively fitting and verifying a geometric model to each cluster of the at least one cluster to estimate an object boundary.

6. The method of claim 1, wherein receiving a plurality of matches of feature points between a query image and a database image, further comprises:

extracting features from the query image.

7. The method of claim 1, wherein the kernel bandwidth is automatically derived as a function of a feature distribution of the database image.

8. The method of claim 2, wherein the step of determining a unimodal kernel density of a feature point distribution of the database image comprises:

adaptively computing kernel bandwidths.

9. The method of claim 1, wherein the object comprises a product, the product being located on a shelf.

10. The method of claim 1, wherein estimating the kernel bandwidth is mathematically represented by:

[k_x, k_y] - - - C(G(fk_xk_y(p_x,p_y)))=1

where,

k_x, k_y—

are the kernel bandwidths in the x, y direction

p_x,p_y—

are the spatial coordinates of the database image point distribution

f—

is the kernel density estimate

G—

is the function returning the modes of the density distribution

C—

cardinality of the modes=1 (a unimodal distribution).

11. The method of claim 1, wherein the estimated kernel bandwidths are not a constant scaling of the database image dimensions.

12. A computer implemented process for detecting an object within a query image, comprising the steps of:

analyzing statistics of a database image to determine a kernel bandwidth;

receiving matches of feature points between a database image and a query image; and

applying clustering using the kernel bandwidth to the matches of feature points to detect the object within the query image;

wherein analyzing statistics of a database image, comprises;

determining a unimodal kernel density of a feature point distribution of the database image;

determining a number of instances of the object of the database image within the query image, wherein the query image comprises multiple instances of the object; and

determining whether other database images are available; and

repeating the steps of analyzing, receiving, applying, and determining, for at least one of the other database images.

13. The computer implemented process of claim 12, wherein the multiple instances of the object comprises one or more of:

multiple instances placed next to each other and partially occluding or occluded by each other.

14. The computer implemented process of claim 12, further comprising:

applying a recursive geometric fitting with recursion after the clustering to obtain a plurality of inliers and outliers.

15. The computer implemented process of claim 12, further comprising:

applying a recursive geometric fitting with recursion after the clustering to further improve detection accuracy.