CN102033933A - Distance metric optimization method for maximizing mean average precision (MAP) - Google Patents

Abstract

The invention discloses a distance metric optimization method for maximizing a mean average precision (MAP). The method comprises the following steps of: (1) acquiring an image database which comprises an inquired image-image to be inquired pair set; (2) approximating the MAP by using a smooth function, converting the approximated MAP into a target function and adding a regularization item, so that the target function is continuously differentiable; (3) optimizing the target function by using an inquired image-image to be inquired pair in the image database and gradient descent-based optimization technology and repeating the optimization process, wherein a result which maximizes the MAP is taken as the optimal linear transformation matrix; and (4) acquiring a distance metric which is defined by the optimal linear transformation matrix. The method has the characteristics of direct optimization process and target. The distance metric obtained by the method can reach higher image retrieval performance.

Description

Maximize the distance measure optimization method of average precision ratio average

Technical field

The present invention relates to a kind of distance measure optimization method that is used to improve the image retrieval performance, relate in particular to a kind of distance measure optimization method that maximizes average precision ratio average.

Background technology

(Content-Based Image Retrieval, basic thought CBIR) is that visual feature of image is extracted to CBIR, realizes the image retrieval of higher level as index with visual signature.The CBIR technology can provide support and helps for managing image data, clinical diagnosis, medical teaching etc.Especially, the retrieval of similar focus in the medical image can improve the integrality of reliability of clinical diagnosis and relevant information.

Usually, the CBIR system is in order to allow Query Result return according to similarity order from big to small, need in image feature space distance measure of definition or similarity measurement to come the difference between image to be checked and query image in the measure database, during return results, image to be checked is according to the ordering of difference size.Distance measure commonly used has: Euclidean distance, mahalanobis distance, Cauchy's distance etc.The retrieval performance of CBIR system depends on two aspects to a great extent: 1. the visual signature that is used to express picture material and semantic concept; 2. distance measure that in feature space, defines or similarity measurement.Usually adopt the low layer visual signature in the CBIR system, describe picture material as color, texture, shape, edge etc.Yet the descriptive power of low layer visual signature is limited, and information has loss when expressing image, thereby the high-level semantic of image generally can not directly be expressed or reflect to the low layer visual signature.Like this, in the low-level feature space, we are difficult to promptly have so-called " semantic wide gap " with one of the above-mentioned general distance measure definition similarity measurement with the semantic concept tight association, make the retrieval performance of CBIR system and actual demand that certain distance be arranged.

Related feedback (Relevance Feedback) and distance measure study (Distance Metric Learning) method can be used to reduce semantic wide gap, improve the retrieval performance of CBIR.The data that are used to learn in the related feedback are difficult to obtain, and system needs repeatedly to adjust just can reach promising result, and it is not very convenient that the user uses.The distance measure learning method can be set up the mapping between low layer characteristics of image and the high-level semantic according to the image pattern of prior mark, thereby the distance measure of definition reflection semantic difference improves retrieval performance.Existing distance measure learning method, spininess is to cluster or the design of k nearest neighbour classification problem, and its learning objective is in order to improve the accuracy rate of cluster or k nearest neighbour classification.Yet, the retrieval precision index and the classification accuracy of CBIR system are very different, as average precision ratio average (Mean Average Precision, MAP), NDCG (Normalized DiscountedCumulative Gain), all with database in the ordering of image to be checked relation is arranged, use the objective function of optimizing at cluster or classification problem design to carry out distance measure study, differing obtains the distance measure of retrieval performance the best surely.And, because the retrieval precision index is not continuously differentiable, it is optimized the certain difficulty of existence.

Summary of the invention

The object of the present invention is to provide a kind of distance measure optimization method that maximizes average precision ratio average, this method has optimizing process and target is direct, optimize the semantic difference that the distance measure that obtains can reflect image, the distance measure that obtains with this method can reach the better pictures retrieval performance.

Purpose of the present invention can realize by following technical measures:

A kind of distance measure optimization method that maximizes average precision ratio average may further comprise the steps:

(1) obtains the image data base that comprises query image-image pair set to be checked;

(2) adopt smooth function that MAP is approached, be converted into objective function and add regularization term, make that objective function is continuously differentiable;

(3) query image-image to be checked in the use image data base is right, adopts the method that descends based on gradient to be optimized to objective function, and repeats optimizing process, gets the matrix of a linear transformation of separating the conduct optimum that makes the MAP maximum;

(4) image pitch comprises dual mode from obtaining of estimating: the optimum linearity transformation matrix in the usefulness step (3) is to the advanced line translation of the characteristics of image in the image data base, again with the distance measure between the Euclidean distance definition image of transform characteristics; Or with the optimum linearity transformation matrix in the step (3) definition mahalanobis distance as the distance measure between image.

Image data base in the described step (1) is made of image or image-region feature, image category.

In the described step (1) according to whether comprising definite images such as same anatomical, same type focus to whether relevant, to inquiry-image to be checked to marking.

The process of in the described step (2) MAP being approached is: to given query image, the ordering sequence number of arbitrary image to be checked uses the Sigmoid type function smoothly to approach, and then obtains smoothly approaching of MAP.

The ordering sequence number of described image to be checked compares definite by the distance between this image to be checked and other all images to be checked and the query image.

The transformation matrix that the initial solution of transformation matrix can be a stochastic matrix or obtained by additive method in the described step (3).

Adopting at random in the described step (3), gradient descent algorithm comes the optimization aim function.

The inventive method has following beneficial effect with respect to prior art:

1, this method relates to technology such as image retrieval, statistical learning and numerical optimization, and (Mean Average Precision MAP), can be used for image retrieval, cluster analysis, data and subtracts approximately etc. directly to optimize average precision ratio average by statistical learning.This method is mainly carried out statistical learning to the view data of mark, obtain a matrix of a linear transformation, with primitive character spatial mappings to a new feature space that has more resolving ability, in new feature space, retrieve as image similarity tolerance with Euclidean distance, reach higher MAP.

2, the inventive method is directly separated the matrix of a linear transformation, the positive semidefinite planning algorithm that need not working costs is found the solution, and can carry out dimension to primitive character by the dimension of direct adjustment transformation matrix and subtract approximately, rather than the order of positive semidefinite matrix is retrained or regulate indirectly regularization parameter realize that dimension subtracts approximately.This method is an objective function with smoothly approaching of retrieval precision index MAP, and with respect to some other distance measure learning method, optimizing process and target are more direct, and low layer characteristics of image after the mapping and high-level semantic feature are got in touch more tight, and retrieval performance is more excellent.In content-based medical image retrieval was used, the present invention can reach the better retrieval performance than the distance measure that some other distance measure learning method obtains.

3, because very big to the calculated amount of calculating target function and gradient to all query image-image to be checked, therefore, adopt in this method at random that gradient descent algorithm is optimized, can reduce to calculator memory demand, accelerate algorithm the convergence speed; In addition, because objective function is non-protruding, there are a lot of Local Extremum in the solution space, be absorbed in Local Extremum for avoiding separating, estimate one near the initial solution of optimum solution by other distance measure learning methods faster, repeatedly the repeated optimization process is got optimum solution then.

Description of drawings

Fig. 1 is the process flow diagram of the distance measure optimization method of the average precision ratio average of maximization of the present invention;

Fig. 2 is that the present invention optimizes in the retrieval precision index MAP process MAP with the convergence situation synoptic diagram of optimized Algorithm iterations;

Fig. 3 be distance measure that the present invention and other distance measure optimization methods obtain be used to retrieve look into complete-precision ratio curve;

The precision ratio average curve map that Fig. 4 is four kinds of distance measures when returning image and be 50 width of cloth;

The distance measure that Fig. 5 is to use optimization of the present invention to obtain is used for the example of the sick retrieval of brain tumor T1 weighting Contrast-enhanced MRI image

Embodiment

Fig. 1 shows the idiographic flow of the distance measure optimization method of the average precision ratio average of maximization of the present invention, may further comprise the steps:

(1) obtains the image data base of the right set of query image-image to be checked of comprising artificial mark; Image data base is made of image or image-region feature, image category.

(2) adopt smooth function that MAP is approached, be converted into objective function and add regularization term, make that objective function is continuously differentiable; Desirable stochastic matrix of transformation matrix initial solution or the transformation matrix of estimating by other distance measure learning methods faster.The process that MAP is approached is: to given query image, the ordering sequence number of arbitrary image to be checked uses the Sigmoid type function smoothly to approach, and then obtains smoothly approaching of MAP.

The ordering sequence number of image to be checked compares definite by the distance between this image to be checked and other all images to be checked and the query image.

(3) use the query image-image to be checked in the image data base and adopt at random that gradient descent algorithm comes the optimization aim function, the repeated optimization process is got and is made the separating as the optimum matrix of a linear transformation of MAP maximum;

(4) distance measure between image is used for image is retrieved, the use-pattern of the optimum linearity transformation matrix in the step (3) comprises two kinds: a kind of is to the advanced line translation of the characteristics of image in the image data base with the matrix of a linear transformation, the Euclidean distance of usefulness transform characteristics defines the distance measure between image again, thereby carries out image querying; Another kind is to carry out image querying with matrix of a linear transformation definition mahalanobis distance as the distance measure of image.

Below in conjunction with brain T1 weighting Contrast-enhanced MRI image retrieval problem, set forth principle of work of the present invention and step.

Step 1 reads the histological type of tumour MRI image, the figure and the focus profile that the doctor delineates by hand from image data base, extracts features such as focus area grayscale, texture, shape and edge, and proper vector is expressed as x _iThe image that definition comprises the same type tumour is an associated picture, otherwise is uncorrelated image.The task of image retrieval is that image identical with focus zone histological type in the query image in the database is returned to the user.

Step 2, because MAP is relevant with the ordering of image to be checked, the at first definite and ordering sequence number of approaching each image to be checked according to the distance between query image and the image to be checked.If L is one d * D (real number matrix of d≤D), positive semidefinite matrix W=L ^TL, then x _iWith x _jBetween mahalanobis distance (square) be

d _ij＝||Lx _i-Lx _j|| ²＝(x _i-x _j) ^TL ^TL(x _i-x _j)＝(x _i-x _j) ^TW(x _i-x _j)，

Here ^TThe matrix transpose operation of representing matrix.If query feature vector is x _q, inquiry-to be checked to being (x _q, { x _i, i=1,2 ..., N}), N is a total number of images to be checked here, proper vector x to be checked _iThe ordering sequence number can be expressed as

$\mathrm{\π}\left(x_i\right)=1+\underset{k,k\≠i}{\mathrm{\Σ}}1\{d_{\mathrm{qi}}>d_{\mathrm{qk}}\}=1+\underset{k,k\≠i}{\mathrm{\Σ}}1\{\mathrm{\Δ}{d}_{\mathrm{ik}}>0\},$

Δ d wherein _Ik=d _Qi-d _Qk, 1{} is an indicator function.Since discontinuous, the non-differentiability of indicator function, ordering sequence number π (x _i) as apart from d _QiOr the function of L also is discontinuous, non-differentiability.Indicator function can be designated as S (Z) with continuously differentiable Sigmoid type function.Ordering sequence number π (x _i) smoothly approach into

(Average Precision AP) is defined as the average precision ratio of retrieval precision index

Rel (x wherein _i) { 0,1} represents the label that two-stage is relevant, N to ∈ ⁺Be the total number of images relevant with query image,

MAP be average precision ratio all inquiries on average.AP can be write as following form

$\mathrm{AP}=\frac{1}{N^{+}}\underset{i}{\mathrm{\Σ}}(\frac{\mathrm{rel}\left(x_i\right)}{\mathrm{\π}\left(x_i\right)}+\underset{i,i\≠j}{\mathrm{\Σ}}\mathrm{rel}\left(x_i\right)\mathrm{rel}\left(x_j\right)\frac{1\{\mathrm{\Δ}{d}_{\mathrm{ij}}>0\}}{\mathrm{\π}\left(x_i\right)}).$

With

Substitute π (x _i), and use Sigmoid approximation of function indicator function once more, AP smoothly approach into

$\hat{A}P=\frac{1}{N^{+}}\underset{i=1}{\overset{N}{\mathrm{\Σ}}}(\frac{\mathrm{rel}\left(x_i\right)}{\widehat{\mathrm{\π}}\left(x_i\right)}+\underset{k,k\≠i}{\mathrm{\Σ}}\frac{\mathrm{rel}\left(x_i\right)\mathrm{rel}\left(x_k\right)S\left(\mathrm{\Δ}{d}_{\mathrm{ik}}\right)}{\widehat{\mathrm{\π}}\left(x_i\right)}).$

The regularization term of transformation matrix L is expressed as Reg (L).Desirable trace (the L of Reg (L) ^TL), the mark of trace (M) representing matrix M here; Reg (L) is other norm forms of desirable L also.

Maximization MAP is equivalent to and minimizes 1-MAP.Define average precision ratio loss function:

${\mathrm{Loss}}_{\mathrm{AP}}\left(L\right)=1-\hat{A}P,$

The objective function of the present invention's definition has following form:

R(L)＝Loss _AP(L)+γReg(L)，

Wherein γ is a weight coefficient, is used to control the balance between loss function and the regularization term.R (L) is continuously differentiable.

Distance measure optimization problem of the present invention is expressed as:

$L*=\underset{L\∈R^{d\×D}}{\arg \min }\frac{1}{M}\underset{m=1}{\overset{M}{\mathrm{\Σ}}}{R}_m\left(L\right),$

Wherein M for inquiry-image to be checked to sum, R _m(L) be m inquiry-image to be checked on objective function.

Step 3 is at first estimated initial solution L ₀, L ₀Can be one d * D stochastic matrix or get separating that other distance measure learning methods obtain.During the t time iteration, generation inquiry from image data base at random-to be checked to (x _q, { x _i, i=1,2 ..., N _t) _t, calculate R (L _t) this inquiry on about L _tGradient g _t, upgrade L _t=L _T-1-η _tg _t, here

T=1,2 ..., T is an iterations, the maximum iteration time of T for setting, η _tIt is the step-length of the t time iteration; Iteration is until reaching maximum iteration time or separating the condition of convergence.Repeatedly repeat said process, choose and make the separating of retrieval precision index maximum as L ^*As get trace (L ^TL) as regularization term, gradient g then _tFor:

$g_t=\frac{\∂R\left(L_t\right)}{\∂L_t}=-\frac{\∂{\mathrm{Loss}}_{\mathrm{AP}}\left(L_t\right)}{\∂L_t}+2\mathrm{\γ}{L}_t$

Loss function is about L _tLocal derviation

Obtain by chain rule.

Algorithm parameter α, γ can adjust by the crosscheck method, and experience ground α gets 1～10, and γ gets 0.0001～0.01 can reach promising result.The desirable η of step-length that gradient descends _t=η ₀(2t/T), t is the current iteration number of times to exp, also can adopt other modes to adjust step-length.Fig. 2 shows the present invention and optimizes in the retrieval precision index MAP process MAP with the convergence situation of optimized Algorithm iterations.

Step 4, the linear transformation L that obtains for step 3 ^*, have the mode of two kinds of equivalences to be applied to image retrieval.The one, use L ^*Original feature vector is mapped to new feature space, use the similarity measurement of the Euclidean distance of standard then as image; The one, directly use L ^*The definition mahalanobis distance is retrieved as the similarity measurement of image, and the former can reduce the required storage space of feature, accelerate image retrieval speed.

What the distance measure that Fig. 3 obtains for the present invention and other distance measure learning methods was used to retrieve looks into entirely-the precision ratio curve, experimental data wherein is a brain T1 weighting Contrast-enhanced MRI image, the image that comprises the same type tumour is an associated picture, otherwise is uncorrelated image.Relatively the distance measure of usefulness comprise standard Euclidean distance, by large-spacing nearest neighbour classification (LMNN) and the acquistion of local Fisher discriminatory analysis (LFDA) methodology to mahalanobis distance.As seen the inventive method can reach higher MAP, is better than Euclidean distance and other two kinds of distance measure learning methods.

The precision ratio average curve that Fig. 4 is four kinds of distance measures when returning image and be 50 width of cloth, used view data is identical with Fig. 3.Distance measure optimization method among the present invention, during the 5-50 image, the precision ratio average is higher than other three kinds of distance measures before returning.

Fig. 5 is used for the example of the sick retrieval of brain tumor T1 weighting Contrast-enhanced MRI image for the distance measure that uses the present invention to obtain, the image in the upper left corner is a query image among the figure, add the associated picture (the expression tumor type is identical) that the expression of solid box (white wire frame) retrieves, add the uncorrelated image (the expression tumor type is inequality) that the expression of frame of broken lines (white dashed line frame) retrieves, the tumor region profile is manually ticked among the figure.Above-mentioned experimental data shows that the present invention can reach the better retrieval performance than the distance measure that some other distance measure learning method obtains.

Be not limited thereto in embodiments of the present invention, other similar MAP are by the retrieval precision index of image ordering sequence number to be checked definition, as Prec@k and NDCG etc., also can use similar above-mentioned formula and method to approach, find the solution with optimization method of the present invention then, do not enumerate one by one at this; Some other optimisation technique and step-length that descends based on gradient adjusted mode, also can be used for realizing the object of the invention as the conjugate gradient descent algorithm; According to foregoing of the present invention; ordinary skill knowledge and customary means according to this area; do not breaking away under the above-mentioned basic fundamental thought of the present invention prerequisite, the present invention can also make equivalent modifications, replacement or the change of other various ways, all drops within the rights protection scope of the present invention.

Claims (6)

1. One kind the maximization average precision ratio average the distance measure optimization method, may further comprise the steps:

   (1) obtains the image data base that comprises query image-image pair set to be checked;

   (2) adopt smooth function that MAP is approached, be converted into objective function and add regularization term, make that objective function is continuously differentiable;

   (3) query image-image to be checked in the use image data base is right, adopts the method that descends based on gradient to be optimized to objective function, and repeats optimizing process, gets the matrix of a linear transformation of separating the conduct optimum that makes the MAP maximum;

   (4) image pitch comprises dual mode from obtaining of estimating: the optimum linearity transformation matrix in the usefulness step (3) is to the advanced line translation of the characteristics of image in the image data base, again with the distance measure between the Euclidean distance definition image of transform characteristics; Perhaps use the optimum linearity transformation matrix in the step (3) to define mahalanobis distance as the distance measure between image.
2. 2. the distance measure optimization method of the average precision ratio average of maximization according to claim 1 is characterized in that: the image data base in the described step (1) is made of image or image-region feature, image category.
3. 3. the distance measure optimization method of the average precision ratio average of maximization according to claim 1, it is characterized in that: the inquiry in the described step (1)-right set of image to be checked is that whether foundation comprises same anatomical, the same type focus determines that image to whether similar, marks.
4. 4. the distance measure optimization method of the average precision ratio average of maximization according to claim 1 is characterized in that: the transformation matrix that obtains with stochastic matrix or other distance measure learning methods in the described step (2) is as the initial solution of the matrix of a linear transformation.
5. 5. the distance measure optimization method of the average precision ratio average of maximization according to claim 1, it is characterized in that: the process of in the described step (2) MAP being approached is: to given query image, the ordering sequence number of arbitrary image to be checked uses the Sigmoid type function smoothly to approach, and then obtains smoothly approaching of MAP.
6. 6. the distance measure optimization method of the average precision ratio average of maximization according to claim 1 is characterized in that: adopting at random in the described step (3), gradient descent algorithm comes the optimization aim function.

Images