Method and system for fast and robust identification of specific product images

• US 9,042,659 B2
• Filed: 06/21/2011
• Issued: 05/26/2015
• Est. Priority Date: 06/25/2010
• Status: Active Grant

• Current Assignee: Catchoom Technologies S.L. (Xerox Holdings Corp.)
• Original Assignee: Telefonica SA
• Inventors: Adamek, Tomasz, Benito, Javier Rodriguez
• Primary Examiner(s): Desire, Gregory M
• Application Number:
  US13/806,788
• Publication Number:
  US 20130202213A1
• Time in Patent Office: 1,435 Days
• Field of Search: 382/201, 382/225, 382/305
• US Class Current: 382/201
• CPC Class Codes: G06F 16/532 Query formulation, e.g. graphical querying
• CPC Class Codes: G06V 10/32 Normalisation of the pattern dimensions
• CPC Class Codes: G06V 10/464 using a plurality of salient features, e.g. bag-of-words [BoW] representations
• CPC Class Codes: G06V 10/753 Transform-based matching, e.g. Hough transform

Abstract

Identification of objects in images. All images are scanned for key-points and a descriptor is computed for each region. A large number of descriptor examples are clustered into a Vocabulary of Visual Words. An inverted file structure is extended to support clustering of matches in the pose space. It has a hit list for every visual word, which stores all occurrences of the word in all reference images. Every hit stores an identifier of the reference image where the key-point was detected and its scale and orientation. Recognition starts by assigning key-points from the query image to the closest visual words. Then, every pairing of the key-point and one of the hits from the list casts a vote into a pose accumulator corresponding to the reference image where the hit was found. Every pair key-point/hit predicts specific orientation and scale of the model represented by the reference image.

Claims

1. Method of identification of objects in images characterised in that it comprises the following stages:

(i) a feature extraction stage, performed by a processor, including the following steps for both;

reference images, i.e. images representing each at least a single reference object, and at least one query image, i.e. an image representing unknown objects to be identified;

(a) identification of key-points, i.e. salient image regions;

(b) post-processing of key-points where key-points that are not useful for the identification process are eliminated;

(c) computation of the descriptors, i.e. representations, of the key-points,

(ii) an indexing stage of reference images, performed by the processor, including the following steps;

(a) key-point extraction;

(b) post-processing of key-points where key-points that are not useful for the identification process are eliminated;

(c) assignment of key-points to visual words of a visual word vocabulary created from a collection of training images, wherein the visual words are centres of clusters of key-point descriptors;

(d) addition of key-points to an inverted file structure, wherein the inverted file structure comprises a hit list for every visual word that stores all occurrences of the word in the reference images and wherein every hit stores an identifier of the reference image where the key-point was detected; and

(iii) a stage of recognition of objects present in the query image, performed by the processor, including the following steps;

(a) key-point extraction;

(b) post-processing of key-points where key-points that are not useful for the identification process are eliminated;

(c) assignment of key-points to visual words of the visual word vocabulary;

(d) for each pairing of a key-point from the query image and one of the hits assigned to the same visual word aggregating a vote into an accumulator corresponding to the reference image of the hit; and

(e) identification of the matching scores corresponding to the reference images based on the votes of the accumulators,

characterised in that the post-processing comprises;

normalizing key-point scales according to the region of interest of reference objects; and

eliminating key-points that cannot effectively contribute to the identification process based on their normalized scales.

2. Method according to claim 1 wherein the stage of recognition (iii) of objects comprises the further step of selecting object or objects that are relevant to the query according to their matching scores.

3. Method according to claim 1 or 2, wherein the post processing includes the automatic detection of regions of interests based on the locations of detected key-points.

4. Method according to claim 3, wherein in the case of reference images the center of the region of interest is estimated as the center of the mass of the set of all detected key-point locations, its initial width and height are computed independently in the horizontal and vertical directions as a function of the standard deviation of key-point locations, the key-point locations being weighted according to the normalized key-point scales, and wherein the initial width and height are shrunk whenever the region of interest covers areas without key-points.

5. Method according to claim 4, wherein the scales of the key-points are normalized as a function of the size of the region of interest, and key-points located outside the region of interest and key-points with a normalized scale smaller than a predetermined value are eliminated.

6. Method according to claim 3, wherein the scales of the key-points are normalized as a function of the size of the region of interest, and key-points located outside the region of interest and key-points with a normalized scale smaller than a predetermined value are eliminated.

7. Method according to claim 1, wherein stages (ii) and (iii) include associating a weighting factor to each key-point reflecting its importance in the process of recognition of objects, which weighting factor is based on the normalized key-points scale.

8. Method according to claim 7, wherein the weighting factor is based on the detected key-points scale, said key-points scale being the normalized key-points scale, and the number of key-points from the same image assigned to the same visual word as the considered key-point and having similar orientation and scale.

9. Method according to claim 7 or 8, wherein in step (iii) (d) the weighting factor is used in the process of aggregating votes, which weighting factor is based on the normalized key-points scale.

10. Method according to claim 1 or 2, wherein in step (ii) (d) every hit stores additionally to the identifier of the reference image where the key-point was detected information about its scale and orientation and every hit has an associated strength of the evidence with which it can support an existence of the corresponding object in response to an occurrence of the visual word in an input image.

11. Method according to claim 10, wherein in step (iii) (d) the accumulator corresponding to the reference image is implemented as a two-dimensional table wherein one dimension of the accumulator corresponds to rotation of the reference object and the other dimension to scaling of the reference object, so that every cell corresponds to a particular rotation and scaling of the reference object and wherein a vote is for the appearance of the reference object with a specific rotation and scaling transformation.

12. Method according to claim 11, wherein in step (iii) (e) the cell with the maximum number of votes in every accumulator is identified.

13. Method according to claim 12, wherein in step (iii) (f) the reference image corresponding with the highest matching score selected as the most relevant object.

14. Method according to claim 12, wherein accumulators are scanned in order to identify bins with the maximum number of votes and the votes accumulated in these maxima are taken as the final matching scores, i.e. scores indicating how well the reference images corresponding to the accumulators where these maxima were found match the query image.

15. A non-transitory computer-readable medium having stored thereon computer program code which, when executed by a processor, causes the processor to perform the steps according to claim 1.

16. System comprising

a processor;

and

a computer-readable medium having stored thereon computer program code which, when executed by the processor, causes the processor to perform the following stages;

(i) a feature extraction stage including the following steps for both;

reference images, i.e. images representing each at least a single reference object, and at least one query image, i.e. an image representing unknown objects to be identified;

(a) identification of key-points, i.e. salient image regions;

(b) post-processing of key-points where key-points that are not useful for the identification process are eliminated;

(c) computation of the descriptors, i.e. representations, of the key-points,

(ii) an indexing stage of reference images including the following steps;

(a) key-point extraction;

(b) post-processing of key-points where key-points that are not useful for the identification process are eliminated;

(c) assignment of key-points to visual words of a visual word vocabulary created from a collection of training images, wherein the visual words are centres of clusters of key-point descriptors;

(d) addition of key-points to an inverted file structure, wherein the inverted file structure comprises a hit list for every visual word that stores all occurrences of the word in the reference images and wherein every hit stores an identifier of the reference image where the key-point was detected; and

(iii) a stage of recognition of objects present in the query image including the following steps;

(a) key-point extraction;

(b) post-processing of key-points where key-points that are not useful for the identification process are eliminated;

(c) assignment of key-points to visual words of the visual word vocabulary;

(d) for each pairing of a key-point from the query image and one of the hits assigned to the same visual word aggregating a vote into an accumulator corresponding to the reference image of the hit; and

(e) identification of the matching scores corresponding to the reference images based on the votes of the accumulators,

characterised in that the post-processing comprises;

normalizing key-point scales according to the region of interest of reference objects; and

eliminating key-points that cannot effectively contribute to the identification process based on their normalized scales.