Using a model tree of group tokens to identify an object in an image

• US 8,676,733 B2
• Filed: 01/22/2010
• Issued: 03/18/2014
• Est. Priority Date: 02/02/2006
• Status: Active Grant

• Current Assignee: Honda Motor Co., Ltd. (Honda Motor Company)
• Original Assignee: Honda Motor Co., Ltd. (Honda Motor Company)
• Inventors: Heisele, Bernd, Sharon, Yoav
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): Seck, Ababacar
• Application Number:
  US12/692,475
• Publication Number:
  US 20100121794A1
• Time in Patent Office: 1,516 Days
• Field of Search: 706/13
• US Class Current: 706/13
• CPC Class Codes: G06F 18/231 Hierarchical techniques, i.e. dividing or merging pattern sets so as to obtain a dendrogram

Abstract

Object recognition techniques are disclosed that provide both accuracy and speed. One embodiment of the present invention is an identification system. The system is capable of locating objects in images by searching for local features of an object. The system can operate in real-time. The system is trained from a set of images of an object or objects. The system computes interest points in the training images, and then extracts local image features (tokens) around these interest points. The set of tokens from the training images is then used to build a hierarchical model structure. During identification/detection, the system computes interest points from incoming target images. The system matches tokens around these interest points with the tokens in the hierarchical model. Each successfully matched image token votes for an object hypothesis at a certain scale, location, and orientation in the target image. Object hypotheses that receive insufficient votes are rejected.

Claims

1. A computer-implemented method for identifying a target object in a target image using a plurality of object models organized into a tree data structure, wherein the target image comprises a plurality of pixels, and wherein each node of the tree represents an object model and includes a list of tokens that represent local image features from training images, the method comprising:

automatically selecting, from the plurality of pixels, without user input, a subset of pixels that are interest points;

extracting tokens associated with the interest points, wherein a token associated with an interest point comprises an image feature of an image region surrounding the interest point; and

comparing the extracted tokens with tokens in the tree to identify matches, comprising comparing the extracted tokens with a list of tokens in a first node of the tree.

2. The method of claim 1, further comprising the preliminary steps of:

receiving the target image; and

formatting the target image so that the target image can be processed according to the method.

3. The method of claim 1, further comprising determining whether a token match threshold is satisfied.

4. The method of claim 3, further comprising:

in response to determining that the token match threshold is satisfied, accepting a hypothesis that the target object satisfies the object model represented by the first node; and

in response to determining that the token match threshold is not satisfied, rejecting a hypothesis that the target object satisfies the object model represented by the first node.

5. The method of claim 3, further comprising repeating the selecting, extracting, comparing, and determining for a plurality of target images.

6. The method of claim 1, further comprising responsive to the extracted tokens matching the list of tokens in the first node, comparing the extracted tokens with a list of tokens in a child node of the first node.

7. The method of claim 1, wherein an object model represented by a first node of the tree is more specific than an object model represented by a parent node of the first node.

8. A non-transitory machine-readable storage medium encoded with instructions that, when executed by a processor, cause the processor to perform a method for identifying a target object in a target image using a plurality of object models organized into a tree data structure, wherein the target image comprises a plurality of pixels, and wherein each node of the tree represents an object model and includes a list of tokens that represent local image features from training images, the method comprising:

automatically selecting, from the plurality of pixels, without user input, a subset of pixels that are interest points;

extracting tokens associated with the interest points, wherein a token associated with an interest point comprises an image feature of an image region surrounding the interest point; and

comparing the extracted tokens with tokens in the tree to identify matches, comprising comparing the extracted tokens with a list of tokens in a first node of the tree.

9. The medium of claim 8, wherein the method further comprises the preliminary steps of:

receiving the target image; and

formatting the target image so that the target image can be processed according to the method.

10. The medium of claim 8, wherein the method further comprises determining whether a token match threshold is satisfied.

11. The medium of claim 10, wherein the method further comprises:

in response to determining that the token match threshold is satisfied, accepting a hypothesis that the target object satisfies the object model represented by the first node; and

in response to determining that the token match threshold is not satisfied, rejecting a hypothesis that the target object satisfies the object model represented by the first node.

12. The medium of claim 10, wherein the method further comprises repeating the selecting, extracting, comparing, and determining for a plurality of target images.

13. The medium of claim 8, wherein the method further comprises responsive to the extracted tokens matching the list of tokens in the first node, comparing the extracted tokens with a list of tokens in a child node of the first node.

14. The medium of claim 8, wherein an object model represented by a first node of the tree is more specific than an object model represented by a parent node of the first node.

15. A system for identifying a target object in a target image using a plurality of object models organized into a tree data structure, wherein the target image comprises a plurality of pixels, and wherein each node of the tree represents an object model and includes a list of tokens that represent local image features from training images, the system comprising:

a machine-readable storage medium encoded with machine-readable instructions for performing a method, the method comprising;

automatically selecting, from the plurality of pixels, without user input, a subset of pixels that are interest points;

extracting tokens associated with the interest points, wherein a token associated with an interest point comprises an image feature of an image region surrounding the interest point; and

comparing the extracted tokens with tokens in the tree to identify matches, comprising comparing the extracted tokens with a list of tokens in a first node of the tree; and

a processor configured to execute the machine-readable instructions encoded on the machine-readable storage medium.

16. The system of claim 15, wherein the method further comprises determining whether a token match threshold is satisfied.

17. The system of claim 15, wherein the method further comprises responsive to the extracted tokens matching the list of tokens in the first node, comparing the extracted tokens with a list of tokens in a child node of the first node.