CN104751459B - Multi-dimensional feature similarity measuring optimizing method and image matching method - Google Patents

Abstract

The invention discloses a method for optimizing similarity measurement of multi-dimensional features, which belongs to the technical field intersecting pattern recognition technology and computer technology. This method first performs binary coding on the original multidimensional feature descriptor based on its own data change characteristics to obtain binary coded features; then uses the Hamming distance between the binary coded features to measure the similarity between the original multidimensional feature descriptors sex. The invention also discloses an image matching method. Compared with the prior art, the present invention can accelerate the speed of feature similarity measurement, reduce the difficulty of feature matching algorithm hardware transplantation and the power consumption of single-point processing modules, reduce the hardware resource occupancy rate of the algorithm, and effectively optimize the performance of the entire feature matching module. performance.

Description

Multi-dimensional feature similarity measurement optimization method and image matching method

technical field

The invention relates to a method for optimizing similarity measurement of multi-dimensional features, which belongs to the technical field intersecting pattern recognition technology and computer technology.

Background technique

With the development of computer technology, feature matching has been widely used in information retrieval, pattern recognition, image processing and many other fields. Feature matching is usually achieved by measuring the similarity between feature descriptors. Taking image feature point matching in image processing technology as an example, it is mainly divided into two categories: one is the linear scanning method based on single-point comparison; the other is The class is a method for fast matching based on partition comparison and data indexing. The existing image feature matching is to first calculate the feature points and their feature descriptors of the reference image and the real-time image, and then calculate the nearest neighbor matching of the key points of the reference image and the real-time image [David MARSHALL.Nearest Neighbor Searching In High Dimensional Metric Space[ EB/OL].http://escience.anu.edu.Au/pro-ject/06S1/DavidMarshall.2006-06-21/2009-12] to judge whether it is a matching point pair. In the traditional technical solution, the Euclidean distance is used for the similarity measurement of the nearest neighbor matching, that is, the SIFT feature points of the reference image and the real-time image are extracted first, and after the feature descriptors are respectively established, according to the size of the nearest neighbor and the next nearest neighbor ratio, judge Whether the feature points in the reference image match those in the real-time image.

With the advancement of science and technology, various feature description methods have been proposed. These features often have extremely high dimensions (for example, the dimension of SIFT features is 128). On the one hand, these features can better perform certain attributes of samples. A more accurate description; on the other hand, it also brings a series of problems to the specific realization of feature similarity measurement. Specifically, the traditional matching scheme based on Euclidean distance has the following disadvantages:

1) The resource usage rate is high. For single-point matching, in general, each SIFT feature point has 128 dimensions, and each dimension is represented by a byte (8 bits) as a floating point number, so a feature point requires 128 bytes of storage space ;

2) Is the hardware transplantation of the algorithm too big? In the process of transplanting the matching algorithm based on Euclidean distance to hardware, it mainly involves summation and product operations (division can also be regarded as a product operation), and the complexity of these two operations (time complexity and space complexity) and The space complexity of the input data is directly proportional to the amount of input data;

3) The operation speed is low. For single-point matching, the clock frequency of the operation is greatly affected by the dimensionality of the input data. Assume that each feature point has 128 dimensions, and each dimension is represented by a byte (8 bits) as a floating point number. After the algorithm is transplanted on the FPGA (model Zynq-7000 XC7Z020-1CLG484C), the highest clock frequency is only 78MHz.

Contents of the invention

The technical problem to be solved by the present invention is to overcome the deficiencies in the prior art and provide a similarity measurement optimization method for multi-dimensional features, which can speed up the measurement of feature similarity and reduce the difficulty of feature matching algorithm hardware transplantation and single-point processing module. Reduce power consumption, reduce the hardware resource occupancy rate of the algorithm, and effectively optimize the performance of the entire feature matching module.

The present invention specifically adopts the following technical solutions to solve the above technical problems:

An optimization method for similarity measurement of multi-dimensional features. Firstly, the original multi-dimensional feature descriptors are binary coded based on their own data change characteristics to obtain binary coded features; then the Hamming distance between binary coded features is used to measure Similarity between original multidimensional feature descriptors.

In one of the preferred schemes, the original multi-dimensional feature descriptor is binary coded according to the following method:

Let the original multidimensional feature descriptor N is the feature dimension, and the superscript f indicates that its data type is a floating point number; let The superscript 2 indicates that its data type is a binary number, i=1, 2,..., N; that is, the binary encoding feature of the original multidimensional feature descriptor is obtained; among them, according to with The size relationship is determined, more than the but The value of 1/0, otherwise, The value of is 0/1, m∈{m|m=1,2,...,N-1}; according to with The magnitude relationship between the difference and a preset threshold value is determined, with The difference is greater than the threshold, then The value of 1/0, otherwise, The value of is 0/1, m∈{m|m=1,2,...,N-1}.

The second preferred option is to perform binary encoding on the original multi-dimensional feature descriptor according to the following method:

Let the original multidimensional feature descriptor N is the feature dimension, and the superscript f indicates that its data type is a floating point number; let The superscript 2 indicates that its data type is a binary number, i=1, 2,..., N; that is, the binary encoding feature of the original multidimensional feature descriptor is obtained; among them, according to with The size relationship is determined, more than the but The value of 1/0, otherwise, The value of is 0/1, m∈{m|m=1,2,…,N}.

The third preferred option is to perform binary encoding on the original multi-dimensional feature descriptor according to the following method:

Let the original multidimensional feature descriptor N is the feature dimension, and the superscript f indicates that its data type is a floating point number; let The superscript 2 indicates that its data type is a binary number, i=1, 2,..., N; that is, the binary encoding feature of the original multidimensional feature descriptor is obtained; among them, according to with The size relationship is determined, more than the but The value of 1/0, otherwise, The value of is 0/1; Indicates the mean value of each dimension feature component in the original multidimensional feature descriptor.

According to the same inventive idea, the following technical solutions can also be obtained:

An image matching method, which uses the similarity between image features to perform image matching, wherein the similarity between the image features is measured using the similarity measurement optimization method described in any one of the above technical solutions.

Compared with the prior art, the invention can greatly reduce the difficulty of hardware transplantation of the feature matching algorithm, increase the operation speed of the feature matching, greatly reduce the occupation rate of hardware resources, and has wide application prospects.

Description of drawings

Fig. 1 is the flow chart of existing SIFT feature similarity measurement method based on Euclidean distance;

Fig. 2 is the flowchart of similarity measurement optimization method of the present invention;

FIG. 3 is a schematic diagram of the principle of binary encoding of feature descriptors.

Fig. 4 is a kind of binary coding algorithm flow chart that similarity measurement optimization method of the present invention uses;

FIG. 5 is a flowchart of an algorithm for calculating Hamming distance used in the similarity measure optimization method of the present invention.

detailed description

The technical scheme of the present invention is described in detail below in conjunction with accompanying drawing:

In the process of feature matching in the fields of image processing, pattern recognition, information retrieval, etc., due to the high feature dimension and the complicated calculation of Euclidean distance, the feature similarity measurement needs to consume a lot of hardware resources (including storage and computing resources). The hardware requirements are high, and the hardware transplantation is difficult. Taking the image matching algorithm based on SIFT features as an example, the feature points used for matching are generally represented by the 128-dimensional vector information in the scale space. One of the outstanding advantages of the SIFT algorithm is its multiplicity, that is, even if there are few target objects, more feature points can be generated, which makes the reference image with a larger size often have as many as thousands of feature points, and the size is smaller. Small real-time images also have hundreds of feature points. Too much information carried by image feature points has become one of the main factors hindering the improvement of image matching speed and business throughput. The huge hardware resources it requires also bring great difficulties to the hardware transplantation of algorithms.

In order to solve this problem, the present invention proposes a new multi-dimensional feature similarity measurement optimization method, the basic idea of which is to first perform binary encoding on the original multi-dimensional feature descriptor based on its own data change characteristics, and obtain the binary encoding features; and then use the Hamming distance between binary coded features to measure the similarity between the original multidimensional feature descriptors. In order to facilitate the public's understanding, the technical solution of the present invention will be described in detail below still taking image matching based on SIFT features as an example.

Figure 1 shows the basic flow of the existing Euclidean distance-based SIFT feature similarity measurement method. For a 128-dimensional SIFT feature descriptor (The superscript f indicates that the data type of the current descriptor is a floating-point number, so as to distinguish it from the following binary-valued descriptors). In general, each dimension of the descriptor is represented by a floating-point number. When the algorithm is transplanted to hardware, at least 8 bits are required to represent the floating point number, so a feature point descriptor needs 128×8=1024 bits.

Fig. 2 shows the basic flow of the similarity measure optimization method of the present invention. As shown in Figure 2, first read in the data to be encoded A sequence and B sequence, where A sequence is the single-point data of the reference image, and B sequence is the single-point data of the real-time image. The A and B sequences are respectively 128 dimensions, and each dimension is represented by a byte (8 bits); then the A sequence and the B sequence are respectively binary-coded; finally, the binary-coded A sequence and the B sequence are encoded XOR operation to calculate its Hamming distance. The binary encoding method is the core part of the present invention, which encodes based on the data change characteristics of the original feature descriptor (A sequence, B sequence) itself, which is equivalent to taking the original feature descriptor as the object and then extracting its own data change characteristics. The present invention preferably performs binary encoding according to the change relationship between the current dimension feature component and the dimension feature component separated from it by a certain distance. The specific description of the scheme is as follows:

Let the original multidimensional feature descriptor N is the feature dimension, and the superscript f indicates that its data type is a floating point number; let The superscript 2 indicates that its data type is a binary number, i=1, 2,..., N; that is, the binary encoding feature of the original multidimensional feature descriptor is obtained; among them, according to with The size relationship is determined, more than the but The value of 1/0, otherwise, The value of is 0/1, m∈{m|m=1,2,...,N-1}; according to with The magnitude relationship between the difference and a preset threshold value is determined, with The difference is greater than the threshold, then The value of 1/0, otherwise, The value of is 0/1, m∈{m|m=1,2,...,N-1}.

For example, when the value of m is 1, the following binary encoding method can be used:

Let the original multidimensional feature descriptor N is the feature dimension, and the superscript f indicates that its data type is a floating point number; let The superscript 2 indicates that its data type is a binary number, i=1, 2,..., N; that is, the binary encoding feature of the original multidimensional feature descriptor is obtained; among them, according to with The size relationship is determined, more than the but The value of is 1 (or 0), otherwise, The value of is 0 (is 1); according to with The size relationship between the difference and a preset threshold Threshold is determined, with The difference is greater than the threshold, then The value of is 1 (or 0), otherwise, has a value of 0 (was 1).

Alternatively, let the original multidimensional feature descriptor N is the feature dimension, and the superscript f indicates that its data type is a floating point number; let The superscript 2 indicates that its data type is a binary number, i=1, 2,..., N; that is, the binary encoding feature of the original multidimensional feature descriptor is obtained; among them, according to with The size relationship is determined, more than the but The value of is 1 (or 0), otherwise, The value of is 0 (is 1); according to with The size relationship between the difference and a preset threshold Threshold is determined, with The difference is greater than the threshold, then The value of is 1 (or 0), otherwise, has a value of 0 (was 1).

The principle of the above-mentioned binary encoding method is shown in FIG. 3 . After adopting this encoding scheme, the SIFT feature descriptor that originally required 1024 bits of storage space only needs 128×2=256 bits, which greatly reduces the required storage space. In addition, in the above binary coding scheme, the introduction of d _i2 ² is to improve the uniqueness of the data, and it may not be used in practical applications, that is, each dimension component of the original feature is coded with only one binary number, thereby further reducing storage space. The lower the value of Threshold, the better the uniqueness of the obtained binary descriptor, but at the same time it will reduce the recall rate of the algorithm. The specific value of Threshold can be determined through experiments according to the original features targeted. It has been verified by experiments that for the SIFT feature, the value of 0.05 is better.

Of course, specific binary encoding can also be done in other ways, for example, using a component of a specific dimension of the original feature (such as the first dimension component) as a reference, and using the size relationship between the feature components of each dimension and the reference to determine the corresponding binary code. value, as follows:

Let the original multidimensional feature descriptor N is the feature dimension, and the superscript f indicates that its data type is a floating point number; let The superscript 2 indicates that its data type is a binary number, i=1, 2,..., N; that is, the binary encoding feature of the original multidimensional feature descriptor is obtained; among them, according to with The size relationship is determined, more than the but The value of is 1 (or 0), otherwise, The value of is 0 (is 1), m∈{m|m=1,2,...,N}.

Or, take the mean value of each dimensional component of the original feature as the benchmark, and determine the corresponding binary number based on the size relationship between the feature component of each dimension and the benchmark, as follows:

Let the original multidimensional feature descriptor N is the feature dimension, and the superscript f indicates that its data type is a floating point number; let The superscript 2 indicates that its data type is a binary number, i=1, 2,..., N; that is, the binary encoding feature of the original multidimensional feature descriptor is obtained; among them, according to with The size relationship is determined, more than the but The value of 1/0, otherwise, The value of is 0/1; Indicates the mean value of each dimension feature component in the original multidimensional feature descriptor.

The above two schemes can further introduce d _i2 ² like the first preferred scheme, so as to improve the uniqueness of the data.

Fig. 4 and Fig. 5 have shown an algorithm example that adopts the method of the present invention to carry out SIFT feature similarity measurement, wherein Fig. 4 is the algorithm implementation flow of binary encoding, Fig. 5 is the algorithm flow of calculating Hamming distance.

The specific steps of binary encoding are shown in Figure 4, including:

Step 1: First, read the 128 floating-point data of sequence A into FIFO (first-in, first-out) sequentially, and name this FIFO F_A, F_A is composed of 128 8-bit registers; then, read the 128 floating-point data of sequence B Floating-point data are read into FIFO (first-in-first-out) sequentially, and this FIFO is named as F_B, and F_B is composed of 128 8-bit registers.

Step 2: Perform binary encoding on sequence A, and store the encoded data in register C, which is a 256-bit register. Among them, the encoding of C[0] and C[1] is determined by A[0] and A[127]:

If 0<A[0]-A[127]<threshold, then C[0]=1, C[1]=0;

If A[0]-A[127]>threshold, then C[0]=1, C[1]=1;

If 0<A[127]-A[0]<threshold, then C[0]=0, C[1]=0;

If A[0]-A[127]>threshold, then C[0]=0, C[1]=1.

The encoding of C[2×k] and C[2×k+1] is determined by A[k] and A[k-1], where 1<k<127:

If 0<A[k]-A[k-1]<threshold, then C[2×k]=1, C[2×k+1]=0;

If A[k]-A[k-1]>threshold, then C[2×k]=1, C[2×k+1]=1;

If 0<A[k-1]-A[k]<threshold, then C[2×k]=0, C[2×k+1]=0;

If A[k-1]-A[k]>threshold, then C[2×k]=0, C[2×k+1]=1.

Step 3: Perform binary encoding on sequence B, and store the encoded data in register D, which is a 256-bit register. Among them, the encoding of D[0] and D[1] is determined by B[0] and B[127]:

If 0<B[0]-B[127]<threshold, then D[0]=1, D[1]=0;

If B[0]-B[127]>threshold, then D[0]=1, D[1]=1;

If 0<B[127]-B[0]<threshold, then D[0]=0, D[1]=0;

If B[0]-B[127]>threshold, then D[0]=0, D[1]=1.

The encoding of D[2×k] and D[2×k+1] is determined by B[k] and B[k-1], where 1<k<127:

If 0<B[k]-B[k-1]<threshold, then D[2×k]=1, D[2×k+1]=0;

If B[k]-B[k-1]>threshold, then D[2×k]=1, D[2×k+1]=1;

If 0<B[k-1]-B[k]<threshold, then D[2×k]=0, D[2×k+1]=0;

If B[k-1]-B[k]>threshold, then D[2×k]=0, D[2×k+1]=1.

The calculation steps of the Hamming distance are shown in Figure 5, and the details are as follows:

Step 1: Bitwise XOR the binary data obtained in the encoding steps 2 and 3 and stored in the C register and the D register respectively, and store the result in the E register, where E is a 256-bit register.

Step 2: Find the Hamming distance of the binary sequence in the register E: First, judge whether E[0] is equal to 1, and if it is equal to 1, the counter sum will be incremented by 1; otherwise, it will remain unchanged. At the next clock, the E sequence is shifted to the right by 1 bit, and at the same time, the E[0] is repeatedly judged to determine whether the sum is increased by 1 until all 256 bits of the E sequence are judged. Then the final result of the counter sum is the Hamming distance after the sequences A and B are converted into binary sequences.

Using the SIFT feature point matching method of the feature similarity measurement optimization method of the present invention, because binary encoding is performed, and the Hamming distance is used instead of the Euclidean distance as the feature matching measurement method, it only needs one-step XOR operation to achieve similarity. The performance measurement greatly reduces the difficulty of hardware transplantation of the matching algorithm, improves the operation speed of image matching, and greatly reduces the occupation rate of hardware resources, which has a wide application prospect.

In order to verify the effect of the present invention, compared on the same hardware platform (FPGA) using the traditional similarity measure based on Euclidean distance and adopting the similarity measure optimization method of the present invention, the hardware resources taken by the SIFT feature matching algorithm and the performance reach the highest rate. Table 1 shows the comparison results, wherein the Euclidean distance means that the traditional similarity measure based on Euclidean distance is used, and the Hamming distance means that the similarity measure method of the present invention is used.

Table 1 Comparison of hardware resources and matching speed under different similarity measurement methods

As can be seen from Table 1, under the same platform (FPGA), the matching method using the similarity measurement method of the present invention takes up less resources than the traditional method (the former is about 27.4% of the latter), but has a faster processing speed (about 304% faster).

Claims (5)

1. A similarity measurement optimization method of multi-dimensional feature, it is characterized in that, at first based on the self data change characteristic of original multi-dimensional feature descriptor it carries out binary encoding, obtains binary encoding feature; Then utilizes binary encoding feature The Hamming distance is used to measure the similarity between the original multidimensional feature descriptors; specifically, the original multidimensional feature descriptors are binary coded according to the following method: Let the original multidimensional feature descriptor N is the feature dimension, and the superscript f indicates that its data type is a floating point number; let The superscript 2 indicates that its data type is a binary number, i=1, 2,..., N; that is, the binary encoding feature of the original multidimensional feature descriptor is obtained; among them, according to with The size relationship is determined, more than the but The value of 1/0, otherwise, The value of is 0/1, m∈{m|m=1,2,...,N-1}; according to with The magnitude relationship between the difference and a preset threshold value is determined, with The difference is greater than the threshold, then The value of 1/0, otherwise, The value of is 0/1, m∈{m|m=1,2,...,N-1}; Alternatively, let the original multidimensional feature descriptor N is the feature dimension, and the superscript f indicates that its data type is a floating point number; let The superscript 2 indicates that its data type is a binary number, i=1, 2,..., N; that is, the binary encoding feature of the original multidimensional feature descriptor is obtained; among them, according to with The size relationship is determined, more than the but The value of 1/0, otherwise, The value of is 0/1, m∈{m|m=1,2,...,N}; Alternatively, let the original multidimensional feature descriptor N is the feature dimension, and the superscript f indicates that its data type is a floating point number; let The superscript 2 indicates that its data type is a binary number, i=1, 2,..., N; that is, the binary encoding feature of the original multidimensional feature descriptor is obtained; among them, according to with The size relationship is determined, more than the but The value of 1/0, otherwise, The value of is 0/1; Indicates the mean value of each dimension feature component in the original multidimensional feature descriptor. 2. the similarity measurement optimization method of multi-dimensional feature as claimed in claim 1, is characterized in that, the value of m is 1. 3. The similarity measure optimization method of multi-dimensional feature as claimed in claim 1 or 2, is characterized in that, described original multi-dimensional feature descriptor is image SIFT feature descriptor. 4. The similarity measure optimization method of multi-dimensional feature as claimed in claim 3, is characterized in that, described threshold is 0.05. 5. An image matching method, which uses the similarity between image features to perform image matching, characterized in that the similarity between the image features is measured using the similarity measurement optimization method described in any one of claims 1-4.