Feature interpolation

• US 9,424,484 B2
• Filed: 07/18/2014
• Issued: 08/23/2016
• Est. Priority Date: 07/18/2014
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Shen, Xiaohui, Lin, Zhe, Brandt, Jonathan W.
• Primary Examiner(s): Carter, Aaron W
• Application Number:
  US14/335,059
• Publication Number:
  US 20160019440A1
• Time in Patent Office: 767 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/5846 using extracted text
• CPC Class Codes: G06F 18/214 Generating training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/04 Inference or reasoning models
• CPC Class Codes: G06V 10/426 Graphical representations
• CPC Class Codes: G06V 10/464 using a plurality of salient features, e.g. bag-of-words [BoW] representations

Abstract

Feature interpolation techniques are described. In a training stage, features are extracted from a collection of training images and quantized into visual words. Spatial configurations of the visual words in the training images are determined and stored in a spatial configuration database. In an object detection stage, a portion of features of an image are extracted from the image and quantized into visual words. Then, a remaining portion of the features of the image are interpolated using the visual words and the spatial configurations of visual words stored in the spatial configuration database.

Claims

1. A computer-implemented method comprising:

receiving an image;

extracting a portion of features of the image from the image;

quantizing the extracted features into visual words; and

interpolating a remaining portion of features of the image using the visual words and spatial configurations of visual words generated from a collection of training images and stored in a spatial configuration database.

2. The computer-implemented method of claim 1, wherein interpolating the remaining portion of the features further comprises, for a remaining feature:

accessing neighbor lists of neighboring visual words that are neighbors of the remaining feature in the image from the spatial configuration database;

determining a common visual word that is included in at least two of the neighbor lists of the neighboring visual words; and

interpolating the feature using the common visual word.

3. The computer-implemented method of claim 2, wherein the determining the common visual word further comprises:

determining the common visual word based on the common visual word occurring in the greatest number of neighbor lists of the neighboring visual words; and

if multiple common visual words are included in a same number of neighbor lists of the neighboring visual words, selecting the common visual word with a highest total occurrence value as the common visual word.

4. The computer-implemented method of claim 2, wherein determining the common visual word comprises:

accessing a right neighbor list associated with a left neighboring visual word positioned to the left of the remaining feature in the image;

accessing a bottom neighbor list associated with a top neighboring visual word positioned above the remaining feature in the image;

accessing a left neighbor list associated with a right neighboring visual word positioned to the right of the remaining feature in the image;

accessing a top neighbor list associated with a bottom neighboring visual word positioned below the remaining feature in the image; and

determining the common visual word by determining a visual word that is in at least two of the right neighbor list of the left neighboring visual word, the bottom neighbor list of the top neighboring visual word, the left neighbor list of the right neighboring visual word, and the top neighbor list of the bottom neighboring visual word.

5. The computer-implemented method of claim 1, wherein interpolating the remaining portion of the features further comprises:

in a first stage, interpolating a first subset of the remaining features based on the visual words of the extracted features; and

in a second stage, interpolating a second subset of the remaining features based on the visual words of the extracted features and the interpolated first subset of remaining features.

6. The computer-implemented method of claim 1, wherein extracting the portion of features from the image comprises extracting approximately one out of every two features from the image.

7. The computer-implemented method of claim 1, wherein extracting the portion of features from the image comprises extracting approximately one out of every four features from the image.

8. The computer-implemented method of claim 1, further comprising detecting one or more objects in the image based on the extracted features and the interpolated features.

9. A system comprising:

a spatial configuration database that stores visual words extracted from a collection of training images, and neighbor lists for each visual word that include neighboring visual words that neighbor the visual word in the training images;

one or more processors;

one or more memories comprising instructions stored thereon that, responsive to execution by the one or more processors, implement an interpolation module configured to;

receive visual words of an image, the visual words quantized from a portion of features extracted from the image;

for each remaining feature that was not extracted from the image;

access neighbor lists of neighboring visual words that are neighbors of the remaining feature;

determine a common visual word that is included in two or more of the neighbor list of the neighboring visual words that are neighbors of the remaining feature; and

interpolate the remaining feature using the common visual word.

10. The system of claim 9, wherein each of the neighbor lists comprises:

a neighbor field for each of multiple neighboring visual words; and

an occurrence field, associated with each neighbor field, that indicates a number of occurrences of the corresponding neighboring visual word in the training images.

11. The system of claim 9, wherein the instructions, responsive to execution by the one or more processors, further implement an object detection application configured to detect one or more objects in the image based on the extracted features and the interpolated features.

12. The system of claim 9, wherein the feature interpolation module determines the common visual word by:

accessing a right neighbor list associated with a left neighboring visual word positioned to the left of the remaining feature in the image;

accessing a bottom neighbor list associated with a top neighboring visual word positioned above the remaining feature in the image;

accessing a left neighbor list associated with a right neighboring visual word positioned to the right of the remaining feature in the image;

accessing a top neighbor list associated with a bottom neighboring visual word positioned below the remaining feature in the image; and

determining the common visual word by determining a visual word that is in at least two of the right neighbor list of the left neighboring visual word, the bottom neighbor list of the top neighboring visual word, the left neighbor list of the right neighboring visual word, and the top neighbor list of the bottom neighboring visual word.