IMAGE MATCHING METHOD BASED ON CASCADED BINARY ENCODING

• US 20170053182A1
• Filed: 04/29/2014
• Published: 02/23/2017
• Est. Priority Date: 04/29/2014
• Status: Active Grant

• Current Assignee: Institute Of Automation Chinese Academy Of Sciences (Chinese Academy of Sciences)
• Original Assignee: Institute Of Automation Chinese Academy Of Sciences (Chinese Academy of Sciences)
• Inventors: Leng, Cong, Wu, Jiaxiang, Cheng, Jian, Lu, Hanqing
• Granted Patent: US 9,996,764 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/56 having vectorial format
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: G06F 16/5866 using information manually generated, e.g. tags, keywords, comments, manually generated location and time information
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]
• CPC Class Codes: G06V 10/761 Proximity, similarity or dissimilarity measures

Abstract

This invention involves an image matching method based on the cascaded binary encoding. The stated method includes: Procedure S1, using the hashing look-up with multiple hashing tables to coarsely filter candidate key-points in the image to produce a candidate subset of key-points; Procedure S2, projecting the candidate subset into a high-dimensional Hamming space; Procedure S3, a “Hamming distance-memory address” hashing table is built, and the optimal matching key-point is discovered by querying this hashing table. The image matching method proposed in this invention has high processing speed and matching quality, which can be used for efficient and accurate image matching.

Claims

1. An image matching method based on cascaded binary encoding, characterized in that the stated method includes:

Procedure S1;

Using the hashing look-up with multiple hashing tables to coarsely filter candidate key-points in the image to produce a candidate subset of the candidate key-points;

Procedure S2;

Projecting the candidate subset of the candidate key-points into a high-dimensional Hamming space;

Procedure S3;

Building a “

Hamming distance-memory address”

hashing table, and obtaining the optimal matching key-point by querying this hashing table.

2. The method described in claim 1, characterized in that the stated Procedure S1 is specified as:

Procedure S11;

Perform the coarse hashing look-up with short hashing codes, in which all the key-points in the images are mapped as m-bit hashing code vectors with the locality sensitive hashing method.

3. The method described in claim 2, characterized in that the stated Procedure S11 is specified as:

For the first key-point p in the first image I, m-bit hashing code vectors are used to build a hashing look-up table, based on which all the key-points in the second image J that fall into the same hashing bucket with the first key-point p are returned,

wherein, L different hashing functions are generated by the locality sensitive hashing method, denoted as g₁(q)=(h_1,l(q), h_2,l(q), . . . , h_m,l(q) , l=1, 2, . . . , L, and a hashing table is then built for each hashing function, and the first key-point p in the first image I is put into the hashing bucket g_l(p), where l=1, 2, . . . , L.

4. The method described in claim 1, characterized in that the stated Procedure S2 is specified as:

All the key-points in the candidate subset are projected into a high-dimensional Hamming space with an n-bit hashing function (n>

m), in which each candidate'"'"'s Hamming distance to the query point is computed and used as the ranking metric.

5. The method described in claim 1, characterized in that the stated Procedure S3 is specified as:

Compute the first Hamming distance between the query point and candidate key-points;

Build a hashing table, using the first Hamming distance as the key and memory address of the candidate key-point as the value;

Traverse the database of the “

Hamming distance-memory address”

hashing table and build the “

Hamming distance-memory address”

hashing table;

The search starts from the table entry with the minimal key, until predetermined candidate key-points have been retrieved, wherein these retrieved key-points are guaranteed to be the top nearest neighbors to the query point in the sense of the Hamming distance.