CN103617431B - Maximum average entropy-based scale-invariant feature transform (SIFT) descriptor binaryzation and similarity matching method - Google Patents

Abstract

The invention relates to a maximum average entropy-based scale-invariant feature transform (SIFT) descriptor binaryzation and similarity matching method and belongs to the image matching field. Scale-invariant feature transform (SIFT) operators have strong matching ability, while, the scale-invariant feature transform (SIFT) operators will bring a huge amount of data, and therefore, binaryzation should be performed on the scale-invariant feature transform (SIFT) operators, however, if unified binaryzation is performed on all the operators, data redundancy or information loss will be brought about. The maximum average entropy-based scale-invariant feature transform (SIFT) descriptor binaryzation and similarity matching method of the invention comprises the following steps that: binaryzation is performed on the scale-invariant feature transform (SIFT) operators; average entropy calculation is performed on each layer of binaryzation results, such that different numbers of binaryzation layers are selected adaptively; new binaryzation descriptors are provided; the Hamming distance is utilized to replace the Euclidean distance so as to calculate the distance between two descriptors; and the distance between the two descriptors is compared with a set threshold value. With the maximum average entropy-based scale-invariant feature transform (SIFT) descriptor binaryzation and similarity matching method of the invention adopted, information of original features is reserved; the amount of data storage can be greatly reduced; computational complexity can be reduced; a requirement for a real-time property can be realized better; the matching results equivalent to original scale-invariant feature transform (SIFT) descriptors can be obtained and are far superior to results of matching by using the unified binaryzation.

Description

Sub- binaryzation and Similarity Match Method are described based on the sift of dominant bit mean entropy

Technical field

The present invention relates to technical field of image matching is and in particular to a kind of sift based on dominant bit mean entropy describes son two Value method and its similarity mode scheme.

Background technology

With the development of the present computer technology, face recognition technology is in the side such as safety certification, man-machine communication, public security system Face is widely used in a variety of applications, and also plays very big effect at aspects such as video conference, file administration, medicals. After U.S.'s the September 11th attacks event and network csdn user profile are occurred by leakage event, biometrics identification technology It is more exposed to everybody concern, and the identification of face biological characteristic is always the focus of living things feature recognition area research, face is known Good recognition performance can not obtained in the case of controlled, but in actual applications, recognition of face suffer from a lot of because Element impact, when human face posture changes, expression changes, ambient light according to changing, face exist and block (wear scarf, Sunglasses) when, the performance of recognition of face will decline a lot, and this just constrains recognition of face application in practice.Cause This, a lot of researchers is devoted to the research of face identification method, and various face identification methods emerge in an endless stream.

Sift (scale-invariant feature transform) Feature Correspondence Algorithm is domestic and international characteristic point at present The focus of matching algorithm research and difficult point, it is the local being proposed preliminary thought in 1999 by Canadian david g.lowe Feature Descriptor, and carried out in original basis in 2004 deeper into development in addition perfect.It is a kind of that sift describes son The local description of image, has yardstick, rotation, the invariance of translation, and illumination variation, affine transformation and 3-dimensional is projected Conversion has certain robustness.In mikolajczyk, ten kinds of local descriptions including sift description are done In invariance contrast experiment, sift and its expansion algorithm have been found to there is vigorousness the strongest in similar description.sift Describe that sub- matching capacity is stronger, possess very strong invariance to the conversion of most of images, be particularly suitable for processing between two width images Translate, rotate, affine transformation when matching problem, its stable characteristic matching ability even can be to arbitrarily angled shooting Image is applied.Sift feature also has good uniqueness, is suitable to be compared fast and accurately in magnanimity property data base Coupling.But, represent that with sift the data volume of facial image is very huge.A general width facial image has 3000 sift Point, each sift is made up of 128 description, and each description is represented by 8 bits, total data volume is 3072000 bits. Wang et al. proposes the thought of binaryzation sift description.The present invention is when describing son to sift and carry out binaryzation, To determine the number of plies of binaryzation with dominant bit mean entropy for criterion, to form new binaryzation description, then use Hamming distance generation Calculate the distance between two description for Euclidean distance, it is compared with given threshold, finally gives matching result.This Sample greatly reduces data volume, reduces the complexity of calculating, can more preferably realize the requirement of real-time.And after binaryzation Description can obtain the basically identical matching result of original sift description when carrying out matching operation, far superior to will Sift description carries out unifying the result that binaryzation is mated.The present invention proposes a kind of sift based on dominant bit mean entropy Sub- binarization method and similarity mode scheme are described.

Content of the invention

The invention provides a kind of describe sub- binarization method and similarity based on the sift of dominant bit mean entropy criterion Formula case, the method can effectively determine the number of plies that binaryzation is carried out using position mean entropy maximum, forms new binaryzation Description, then replaces with Hamming distance Euclidean distance to calculate the distance between two description, it is carried out with given threshold Relatively, finally give matching result.Original sift in a large number can be retained and describe sub-information, reduce data volume to a great extent, Reduce the complexity of calculating, can more preferably realize the requirement of real-time.And can ensure that matching result and using original The matching result that sift description obtains is basically identical, far superior to carries out unifying what binaryzation was mated by sift description Result.

Sift is described with son and carries out binaryzation, iff carrying out one layer of binaryzation, then a lot of information can be lost, retain The quantity of information of former feature can be seldom.When carrying out multilamellar binaryzation, comprise four kinds of binaryzation strategies: (1) is finishing ground floor two After value, obtain 0 and 1, then always binaryzation is carried out to 0 part.(2) after finishing ground floor binaryzation, obtain 0 He 1, select 0 part to carry out binaryzation and obtain 0 and 1, then always binaryzation is carried out to 1 part.(3) finishing ground floor binaryzation Afterwards, obtain 0 and 1, select 1 part to carry out binaryzation and obtain 0 and 1, then always binaryzation is carried out to 0 part.(4) finishing After ground floor binaryzation, obtain 0 and 1, then always binaryzation is carried out to 1 part.Because comprising a lot in sift description Individual 0, for each layer of binaryzation result, the policy information entropy carrying out binaryzation always to 1 is always maximum, so taking the 4th Plant strategy and carry out multilamellar binaryzation.Entropy can be used to the size of metric amount.Sift describes son and carries out binaryzation number of plies increase, Comentropy can increase therewith.But, concomitantly the greatly increasing of data volume.And, if to all sift extracting Description carries out unifying the binaryzation of the number of plies, then can comprise following two situation: (1) itself does not need binaryzation to proceed to finger Given layer number, position mean entropy has been maxed out.It is maximum for such as doing the position mean entropy after two-layer binaryzation, then only need to retain The result of two-layer.If doing three layers or more layers, data redundancy can be increased, the data of redundancy may cause the mistake of coupling； (2) after the binaryzation finishing the specified number of plies, position mean entropy is also not up to maximum, so can lead to description after binaryzation not The information that original sift description carries can sufficiently be retained, the increase of error hiding degree can be led to.But, to examine from data volume Consider, at most retain four layers of binaryzation result.The present invention proposes and describes submethod based on binaryzation sift of dominant bit mean entropy And similarity mode scheme, by each description is entered with the calculating of line position mean entropy, adaptive to select different two The value number of plies, forms new binaryzation description, then replaces Euclidean distance to calculate between two description with Hamming distance Distance, it is compared with given threshold, finally gives matching result.Algorithm proposed by the present invention retains to a great extent The information of primitive character simultaneously greatly reduces memory data output, reduces the complexity of calculating, can more preferably realize real-time Requirement.And the matching result being equal to original sift description can be obtained, far superior to sift is described son and united The result that one binaryzation is mated.Therefore, the present invention has certain using value and meaning.

In order to realize the problems referred to above, the present invention proposes and a kind of describes sub- binaryzation based on the sift of dominant bit mean entropy Method and similarity mode scheme, the method specifically includes:

A, binaryzation stage, for each width facial image, extract sift Feature Descriptor first, then sift is described Son carries out multilamellar binaryzation, tries to achieve comentropy at all levels, the total bit number of the probability being occurred according to each layer 0 and 1 and reservation, Try to achieve a mean entropy, then find out the dominant bit mean entropy corresponding binaryzation number of plies, retained this which floor binaryzation result, formed new Binaryzation Feature Descriptor.

B, matching stage, for any two width facial images, after extracting its new binaryzation Feature Descriptor respectively, so Replace with Hamming distance Euclidean distance to calculate the distance between two description afterwards, it is compared with given threshold, if Hamming distance is less than or equal to given threshold then it is assumed that the match is successful；Otherwise then it is assumed that coupling is unsuccessful.For the difference extracted The binaryzation Feature Descriptor of level, needs to select different threshold values.

Described step a specifically includes:

A1, for each width facial image, extract sift Feature Descriptor first；

A2, each sift for each width facial image describe son and carry out binaryzation；

A3, the number of statistics 0 and 1, respectively n₁₀And n₁₁；

A4, be labeled as 1 those bytes corresponding description, proceed binaryzation, statistics now 0 and 1 number, point Wei not n₂₀And n₂₁, proceed above-mentioned binarization, obtain n successively₃₀And n₃₁, n₄₀And n₄₁

The comentropy of one layer, two layers, three layers, four layers binaryzation is done in a5, respectively calculating；

A6, the total bit number according to reservation after binaryzation, position mean entropy can be obtained divided by bit number by comentropy；

A7, try to achieve the number of plies corresponding to dominant bit mean entropy, retain the binaryzation result of the corresponding number of plies, form new two-value Change description.

Described step b specifically includes:

B1, for any two width facial images, extract its new binaryzation description；

B2, for each two describe son, calculate its Hamming distance dis_h；

B3, extract binaryzation description of different levels, threshold value t of selection also differs, do one layer, two layers, three layers and The threshold value of four layers of binaryzation is respectively as follows: t₁, t₂, t₃, t₄

If b4 is dis_hLess than or equal to threshold value then it is assumed that the match is successful；Otherwise it is assumed that coupling is unsuccessful.The present invention is with now There is technology to compare, there is following obvious advantage and beneficial effect:

(1) present invention describes son and carries out binaryzation to sift, is Lai adaptive basis according to dominant bit mean entropy principle Each describes son to determine the binaryzation number of plies, compared with carrying out unifying binaryzation, not only reduces data redundancy, and very The information that original sift description carries is retained on big degree.

(2) self adaptation of the present invention obtains new binaryzation description, is mated by Hamming distance, calculates simply fast Victory, complexity reduces, and can better meet the requirement of real-time.

(3) present invention describes son by binaryzation sift that dominant bit mean entropy obtains and is mated, through experimental analysiss, Matching result is equal to the matching result of original sift description, far superior to sift is described son and carries out unifying binaryzation carrying out Mate the result obtaining.

Brief description:

Fig. 1 is the overall flow figure of technical scheme.

Fig. 2 (a) is binaryzation strategy 1 (left)

Fig. 2 (b) is binaryzation strategy 1 (left and right)

Fig. 2 (c) is binaryzation strategy 1 (a right left side)

Fig. 2 (d) is binaryzation strategy 1 (right)

Fig. 3 is similarity mode results contrast figure.

Specific embodiment:

The overall flow of technical solution of the present invention is as shown in Figure of description 1.Our method greatly reduces data and deposits Reserves, reduce the complexity of calculating, can more preferably realize the requirement of real-time.And can obtain and be equal to original sift and retouch State the matching result of son, far superior to carry out unifying the result that binaryzation is mated by sift description.

A, for each width facial image, extract sift Feature Descriptor first, then sift described with son and carries out two-value Change, try to achieve comentropy at all levels, the total bit number of the probability being occurred according to each layer 0 and 1 and reservation, try to achieve a mean entropy, Then find out the dominant bit mean entropy corresponding binaryzation number of plies, retained this which floor binaryzation result, ultimately forms new binaryzation Description.Concrete steps include:

A1, for each width facial image, extract sift Feature Descriptor first

D=(f₁,f₂,…,f₁₂₈)^t∈r¹²⁸

A2, each sift for each width facial image describe son and carry out binaryzation

Intermediate value for vectorial d

A3, the number of statistics 0 and 1, respectively n₁₀And n₁₁；

A4, be labeled as 1 those bytes corresponding description, proceed binaryzation, statistics now 0 and 1 number, point Wei not n₂₀And n₂₁, proceed above-mentioned binarization, obtain n successively₃₀And n₃₁, n₄₀And n₄₁

A5, calculating do the comentropy after each layer binaryzation

The comentropy doing one layer of binaryzation is:

h₁=-p (n₁₀)log₂p(n₁₀)-p(n₁₁)log₂p(n₁₁)

The comentropy doing two layers of binaryzation is:

$h_2=-\underset{i=1}{\overset{2}{\σ}}p\left(n_{i0}\right){\log }_{2}p\left(n_{i0}\right)-p\left(n_{21}\right){\log }_{2}p\left(n_{21}\right)$

The comentropy doing three layers of binaryzation is:

$h_3=-\underset{i=1}{\overset{3}{\σ}}p\left(n_{i0}\right){\log }_{2}p\left(n_{i0}\right)-p\left(n_{31}\right){\log }_{2}p\left(n_{31}\right)$

The comentropy doing four layers of binaryzation is:

$h_4=-\underset{i=1}{\overset{4}{\σ}}p\left(n_{i0}\right){\log }_{2}p\left(n_{i0}\right)-p\left(n_{41}\right){\log }_{2}p\left(n_{41}\right)$

The bit number that a6, calculating retain after each layer binaryzation

The total bytes retaining after doing one layer of binaryzation are:

n₁=n₁₀+n₁₁

The total bytes retaining after doing two layers of binaryzation are:

$n_2=\underset{i=1}{\overset{2}{\σ}}{n}_{i0}+n_{21}$

The total bytes retaining after doing three layers of binaryzation are:

$n_3=\underset{i=1}{\overset{3}{\σ}}{n}_{i0}+n_{31}$

The total bytes retaining after doing four layers of binaryzation are:

$n_4=\underset{i=1}{\overset{4}{\σ}}{n}_{i0}+n_{41}$

A7, position mean entropy can be obtained divided by digit by comentropy

Doing the position mean entropy after one layer of binaryzation is:

${\stackrel{\&overbar;}{h}}_1=h_1/n_1=\[-p\left(n_{10}\right){\log }_{2}p\left(n_{10}\right)-p\left(n_{11}\right){\log }_{2}p\left(n_{11}\right)\]/(n_{10}+n_{11})$

Doing the position mean entropy after two layers of binaryzation is:

${\stackrel{\&overbar;}{h}}_2=h_2/n_2=\[-\underset{i=1}{\overset{2}{\σ}}p\left(n_{i0}\right){\log }_{2}p\left(n_{i0}\right)-p\left(n_{21}\right){\log }_{2}p\left(n_{21}\right)\]/(\underset{i=1}{\overset{2}{\σ}}{n}_{i0}+n_{21})$

Doing the position mean entropy after three layers of binaryzation is:

${\stackrel{\&overbar;}{h}}_3=h_3/n_3=\[-\underset{i=1}{\overset{3}{\σ}}p\left(n_{i0}\right){\log }_{2}p\left(n_{i0}\right)-p\left(n_{31}\right){\log }_{2}p\left(n_{31}\right)\]/(\underset{i=1}{\overset{3}{\σ}}{n}_{i0}+n_{31})$

Doing the position mean entropy after four layers of binaryzation is:

${\stackrel{\&overbar;}{h}}_4=h_4/n_4=\[-\underset{i=1}{\overset{4}{\σ}}p\left(n_{i0}\right){\log }_{2}p\left(n_{i0}\right)-p\left(n_{41}\right){\log }_{2}p\left(n_{41}\right)\]/(\underset{i=1}{\overset{4}{\σ}}{n}_{i0}+n_{41})$

A8, try to achieve the number of plies corresponding to dominant bit mean entropy, retain the binaryzation result of the corresponding number of plies, form new two-value Change description.

B, matching stage, for any two width facial images, after extracting its new binaryzation Feature Descriptor respectively, so Replace with Hamming distance Euclidean distance to calculate the distance between two description afterwards, it is compared with given threshold, if Hamming distance is less than or equal to given threshold then it is assumed that the match is successful；Otherwise then it is assumed that coupling is unsuccessful.For the difference extracted The binaryzation Feature Descriptor of level, needs to select different threshold values.Concrete steps include:

B1, for any two width facial images, extract its new binaryzation description；

B2, sub- x=[b is described for each two₁₁,b₁₂,b₁₃...] and y=[b₂₁,b₂₂,b₂₃...], calculate its Hamming distance From

${\mathrm{dis}}_h(x,y)=x\&circleplus;y$

B3, the Hamming distance obtaining and threshold value are compared, the binaryzation for different levels describes son, the threshold of selection Value also differs, and sets the threshold value of i layer binaryzation as t_i(i=1,2,3,4, t₁=17；t₂=28；t₃=34；t₄=39)

$sgn\left({\mathrm{dis}}_h\right)=\left\{\begin{array}{c}1,di{s}_h\≤t_i\\ 0,{\mathrm{dis}}_h>t_i\end{array}\right.$

If b4 is sgn (dis_h)=1 is then it is assumed that the match is successful；Otherwise it is assumed that coupling is unsuccessful.

As shown in Figure of description 3, (a) is the matching result of original sift description to matching result, and coupling number is 1242；B () is the matching result after unified binaryzation, create the coupling of much mistakes.C () is the coupling knot of the inventive method Really, coupling number is 1161.The matching result of the inventive method is equal to the matching result of original sift description, far superior to Sift description is carried out unifying binaryzation carrying out mating the result obtaining.

Claims (1)

1. a kind of sub- binarization method and similarity mode scheme are described based on the sift of dominant bit mean entropy, walk including following Rapid:

A, binaryzation stage, for each width facial image, extract sift Feature Descriptor first, then son is described to sift and enter Row multilamellar binaryzation, tries to achieve comentropy at all levels, the total bit number of the probability being occurred according to each layer 0 and 1 and reservation, tries to achieve Position mean entropy, then finds out the dominant bit mean entropy corresponding binaryzation number of plies, retains this which floor binaryzation result, forms new two Value Feature Descriptor；

Described step a specifically includes:

A1, for each width facial image, extract sift Feature Descriptor first

D=(f₁,f₂,…,f₁₂₈)^t∈r¹²⁸

A2, each sift for each width facial image describe son and carry out binaryzation

Intermediate value for vectorial d

A3, the number of statistics 0 and 1, respectively n₁₀And n₁₁；

A4, be labeled as 1 those bytes corresponding description, proceed binaryzation, statistics now 0 and 1 number, respectively n₂₀And n₂₁, proceed above-mentioned binarization, obtain n successively₃₀And n₃₁, n₄₀And n₄₁；

A5, calculating do the comentropy after each layer binaryzation

The comentropy doing one layer of binaryzation is:

h₁=-p (n₁₀)log₂p(n₁₀)-p(n₁₁)log₂p(n₁₁)

The comentropy doing two layers of binaryzation is:

$h_2=-\underset{i=1}{\overset{2}{\σ}}p\left(n_{i0}\right){\log }_{2}p\left(n_{i0}\right)-p\left(n_{21}\right){\log }_{2}p\left(n_{21}\right)$

The comentropy doing three layers of binaryzation is:

$h_3=-\underset{i=1}{\overset{3}{\σ}}p\left(n_{i0}\right){\log }_{2}p\left(h_0\right)-p\left(n_{31}\right){\log }_{2}p\left(n_{31}\right)$

The comentropy doing four layers of binaryzation is:

$h_4=-\underset{i=1}{\overset{4}{\σ}}p\left(n_{i0}\right){\log }_{2}p\left(n_{i0}\right)-p\left(n_{41}\right){\log }_{2}p\left(n_{41}\right)$

The bit number that a6, calculating retain after each layer binaryzation

The total bytes retaining after doing one layer of binaryzation are:

n₁=n₁₀+n₁₁

The total bytes retaining after doing two layers of binaryzation are:

$n_2=\underset{i=1}{\overset{2}{\σ}}{n}_{i0}+n_{21}$

The total bytes retaining after doing three layers of binaryzation are:

$n_3=\underset{i=1}{\overset{3}{\σ}}{n}_{i0}+n_{31}$

The total bytes retaining after doing four layers of binaryzation are:

$n_4=\underset{i=1}{\overset{4}{\σ}}{n}_{i0}+n_{41}$

A7, position mean entropy can be obtained divided by digit by comentropy

Doing the position mean entropy after one layer of binaryzation is:

${\stackrel{\&overbar;}{h}}_1=h_1/n_1=\[-p\left(n_{10}\right){\log }_{2}p\left(n_{10}\right)-p\left(n_{11}\right){\log }_{2}p\left(n_{11}\right)\]/(n_{10}+n_{11})$

Doing the position mean entropy after two layers of binaryzation is:

${\stackrel{\&overbar;}{h}}_2=h_2/n_2=\[-\underset{i=1}{\overset{2}{\σ}}p\left(n_{i0}\right){\log }_{2}p\left(n_{i0}\right)-p\left(n_{21}\right){\log }_{2}p\left(n_{21}\right)\]/(\underset{i=1}{\overset{2}{\σ}}{n}_{i0}+n_{21})$

Doing the position mean entropy after three layers of binaryzation is:

${\stackrel{\&overbar;}{h}}_3=h_3/n_3=\[-\underset{i=1}{\overset{3}{\σ}}p\left(n_{i0}\right){\log }_{2}p\left(n_{i0}\right)-p\left(n_{31}\right){\log }_{2}p\left(n_{31}\right)\]/(\underset{i=1}{\overset{3}{\σ}}{n}_{i0}+n_{31})$

Doing the position mean entropy after four layers of binaryzation is:

${\stackrel{\&overbar;}{h}}_4=h_4/n_4=\[-\underset{i=1}{\overset{4}{\σ}}p\left(n_{i0}\right){\log }_{2}p\left(n_{i0}\right)-p\left(n_{41}\right){\log }_{2}p\left(n_{41}\right)\]/(\underset{i=1}{\overset{4}{\σ}}{n}_{i0}+n_{41})$

A8, the number of plies tried to achieve corresponding to dominant bit mean entropy retain the binaryzation result of the corresponding number of plies, form new binaryzation and retouch State son；

B, matching stage, for any two width facial images, after extracting its new binaryzation Feature Descriptor respectively, Ran Houyong Hamming distance replaces Euclidean distance to calculate the distance between two description, it is compared with given threshold, if Hamming Distance is less than or equal to given threshold then it is assumed that the match is successful；Otherwise then it is assumed that coupling is unsuccessful；For the different levels extracted Binaryzation Feature Descriptor, need to select different threshold values；

Described step b specifically includes:

B1, for any two width facial images, extract its new binaryzation description；

B2, sub- x=[b is described for each two₁₁,b₁₂,b₁₃...] and y=[b₂₁,b₂₂,b₂₃...], calculate its Hamming distance

${\mathrm{dis}}_h(x,y)=x\&circleplus;y$

B3, the Hamming distance obtaining and threshold value are compared, the binaryzation for different levels describes son, the threshold value of selection Differ, set the threshold value of i layer binaryzation as t_i, wherein i=1,2,3,4, t₁=17；t₂=28；t₃=34；t₄=39；

$sgn\left({\mathrm{dis}}_h\right)=\left\{\begin{array}{c}1,di{s}_h\≤t_i\\ 0,di{s}_h>t_i\end{array}\right.$

If b4 is sgn (dis_h)=1 is then it is assumed that the match is successful；Otherwise it is assumed that coupling is unsuccessful.