High speed searching method for large-scale image databases

• US 9,830,530 B2
• Filed: 09/25/2015
• Issued: 11/28/2017
• Est. Priority Date: 07/31/2014
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chiaki, Oishi, Nakano, Hiroki
• Primary Examiner(s): Chang, Jon
• Application Number:
  US14/865,837
• Publication Number:
  US 20160034776A1
• Time in Patent Office: 795 Days
• Field of Search: 382103, 382190, 382201, 382305
• CPC Class Codes: G06F 18/214 Generating training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06F 2218/12 Classification; Matching
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]
• CPC Class Codes: G06V 10/757 Matching configurations of points or features

Abstract

Embodiments are provided to search for a dictionary image corresponding to a target image. The method includes detecting keypoints in a set of dictionary images. The set of dictionary images includes at least one dictionary image having a plurality of pixels. At least one random pair of pixels is selected among the detected keypoints of the dictionary image on the basis of candidate coordinates for pixels distributed around the detected keypoints of the dictionary image. A feature vector of each keypoint of the dictionary image is calculated, including calculating a difference in brightness between the selected pairs of pixels of the dictionary image. The calculated difference in brightness is an element of the feature vector. Keypoints of a target image are detected.

Claims

1. A computer-implemented method for searching an image database comprising:

detecting keypoints in a dictionary image composed of a plurality of pixels, wherein a density of the pixels distributed around a plurality of keypoints form a Gaussian distribution using coordinates of a keypoint as an origin point;

selecting random pairs of pixels among the detected keypoints, the selection based on candidate coordinates for pixels distributed around the detected keypoints;

comparing brightness between the selected pairs of pixels, including calculating a brightness difference between the selected pairs of pixels; and

converting the calculated brightness difference into a feature vector, wherein the conversion includes calculating the feature vector; and

using the feature vector to search for the dictionary image corresponding to an image of a target object.

2. The method of claim 1, wherein the calculated brightness difference is a combination of positive real numbers and negative real numbers.

3. The method of claim 1, wherein the feature vector is a 128-dimensional vector with real number elements.

4. The method of claim 1, wherein a keypoint is a rotation and scale invariant point.

5. The method of claim 1, wherein a keypoint is detected at least in part on shading patterns in the image.

6. The method of claim 1, further comprising:

generating a multi-dimensional tree (K-D tree) using the calculated feature vector;

searching the generated K-D tree for a given keypoint; and

recording a distance between the feature vector and a closest keypoint to the feature vector.

7. The method of claim 6, further comprising limiting selection of keypoints whose distance is less than or equal to a given threshold value.

8. The method of claim 7, further comprising:

providing data on the selected keypoints, including a size (R_m) and direction (θ

_m) of the feature vector, and an offset (O_x, O_y) from the coordinates at a center of the image to coordinates of a feature point;

providing sizes (R_t) and directions (θ

_t) of feature vectors for coordinates (T_x, T_y) of a plurality of feature points in the target image;

calculating coordinates of a virtual center point (F_x, F_y) in the target image derived from data comprising T_x, T_y, O_x, O_y, R_m, R_t, θ

_m, and θ

_t;

counting a number of additional virtual center points within a predetermined radius of the virtual center point (F_x, F_y); and

determining if the number of additional virtual center points exceeds a second threshold.

9. The method of claim 8, wherein

F_x is calculated as F_x=T_x+(O_x·

R_t/R_m)(cos(θ

_t−

θ

_m))+(O_y·

R_t/R_m)(sin(θ

_t−

θ

_m)), and wherein

F_y is calculated as F_y=T_y+(O_x·

R_t/R_m)(−

sin(θ

_t−

θ

_m))+(O_y·

R_t/R_m)(cos(θ

_t−

θ

_m)).

10. The method of claim 8, further comprising:

in response to the second threshold being exceeded, storing the virtual center point (F_x, F_y) and coordinates of a number of additional virtual center points as candidates;

establishing the coordinates of a virtual center point corresponding to a maximum number of additional virtual center points as a center of a target image (M_x, M_y); and

eliminating the additional virtual center points within the predetermined radius of the coordinates of the established virtual center point.