WO2016142285A1 - Method and apparatus for image search using sparsifying analysis operators - Google Patents

Abstract

In a particular implementation, images are represented by feature vectors, whose sparse representations are computed using an analysis operator. The sparse representations of the images are then used to efficiently compute similarity metrics between the images. Using pair-wise constraints where each pair of images is indicated as similar or dissimilar, the analysis operator can be trained for the task of image matching. Using triplet constraints wherein a first image and a second image are indicated as more similar than the first image and a third image are, the analysis operator can be trained for the task of image ranking. The analysis operator can be computed using an optimization problem based on a penalty function and sparsity constraints, or using a multiple layer neural network. The analysis operator can also be used to compute a Mahalanobis metric transformation matrix.

Description

Method and Apparatus for Image Search Using Sparsifying Analysis Operators

TECHNICAL FIELD

[1] This invention relates to a method and an apparatus for image search, and more particularly, to a method and an apparatus for image search using sparsifying analysis operators.

BACKGROUND

[2] With the increasing size of image collections and the related difficulty in manually annotating them, automated image search and comparison methods have become crucial when searching for relevant images in a large collection. Many systems that currently exist enable such search approaches, including commercial web search engines that admit an image as the query and return a ranked list of relevant web images; copyright infringement detection methods that are robust to image manipulations such as cropping, rotation, mirroring and picture-in-picture artifacts; semantic search systems that enable querying of an unannotated private image collection based on visual concepts (e.g. , cat); object detection systems that are robust to the image background content; automatic face verification methods; and vision-based navigation systems used, for example, as part of the control mechanism of self-driving cars.

[3] A general image search algorithm can be seen as having various goals including: i) finding correctly matching images given a task-specific search criteria and ii) doing so in a time and resource efficient manner, particularly in the context of large image databases. In addressing the first goal, discriminative Mahalanobis metric learning methods have become an important part of the research toolbox. Such methods can be seen as applying an explicit linear transform to the image feature vector with the goal of making distance computations between transformed feature vectors better correspond to the search criteria. The linear transform can be learned using one of a variety of objectives in order to adapt it to various possible search criteria including image classification, face verification, or image ranking. Common to all these methods is the fact that the learned linear transform is a complete or undercomplete matrix that is constant for all image feature vectors.

[4] Concerning the second goal of image search systems, that of time and resource efficiency of the search process, one recent successful method represents all the database images using a product quantizer that enables both a very compact representation and a very efficient comparison to query features. Methods based on sparse coding have also been attempted, as sparse coding can be seen as a generalization of vector quantization. The general aim of these methods is to produce a very compact representation of the input feature vector consisting, for example, of codeword indices and possibly accompanying weights. SUMMARY

[5] According to a general aspect, a method for performing image search is presented, comprising: accessing a first sparse representation of a query image, the first sparse representation being based on a first feature vector corresponding to the query image and an analysis operator; determining a similarity metric between the query image and a second image of an image database using a correlation between the first sparse representation and a second representation, the second sparse representation being based on a second feature vector corresponding to the second image and the analysis operator; and generating an image search output based on the similarity metric between the query image and the second image.

[6] The image search output may indicate one of (1) a rank of the second image and (2) whether the second image matches the query image.

[7] The method for performing image search may receive the first sparse representation from a user device via a communication network, and may further transmit the output to the user device via the communication network.

[8] The first sparse representation may be based on a product of the analysis operator and the first feature vector, and the second sparse representation may be based on a product of the analysis operator and the second feature vector.

[9] At least one of the first sparse representation and the second sparse representation may be binary.

[10] The first sparse representation and the second sparse representation may be non-binary, and the method for performing image search may determine the first sparse representation and the second sparse representation from a third sparse representation and a fourth sparse representation, respectively, wherein the third sparse representation and the fourth sparse representation are binary.

[11] The method for performing image search may determine the analysis operator based on a set of pair- wise constraints, wherein each pair- wise constraint indicates whether a corresponding pair of training images are similar or dissimilar.

[12] The method for performing image search may determine the analysis operator based on a set of triplet constraints, wherein each triplet constraint indicates that a first training image of the triplet is more similar to a second training image of the triplet than to a third training image of the triplet.

[13] The method for performing image search may train the analysis operator such that a similarity metric determined for training images corresponding to a pair- wise constraint or a triplet constraint is consistent with what the pair-wise constraint or the triplet constraint indicates. The analysis operator may be determined using a penalty function. Further, the analysis operator may be determined using a multiple layer neural network.

[14] The analysis operator can be used to determine a Mahalanobis metric transformation matrix.

[15] The present embodiments also provide an apparatus for performing image search, comprising a memory and one or more processors configured to perform any of the methods described above.

[16] The present embodiments also provide a non-transitory computer readable storage medium having stored thereon instructions for performing any of the methods described above.

BRIEF DESCRIPTION OF THE DRAWINGS

[17] FIG. 1 illustrates an exemplary method for performing image search, according to an embodiment of the present principles.

[18] FIG. 2 illustrates an exemplary method for learning the operator for the similarity function.

[19] FIG. 3 shows exemplary pictures from an image training database, where similar images are grouped together, and images from different groups are dissimilar. [20] FIG. 4 illustrates an exemplary analysis encoding process for generating a sparse code z for vector y, according to an embodiment of the present principles.

[21] FIG. 5A shows a parametrized hinge loss function, and FIG. 5B shows a continuous hinge loss function. [22] FIG. 6 illustrates an exemplary process for learning analysis operator A using pair- wise constraints, according to an embodiment of the present principles.

[23] FIG. 7A shows exemplary sparse codes for images in a database, and FIG. 7B is an expanded view of the upper-right portion of FIG. 7A.

[24] FIG. 8A illustrates an exemplary process for performing image matching, according to an embodiment of the present principles, and FIG. 8B illustrates an exemplary process for performing image ranking for a query image, according to an embodiment of the present principles.

[25] FIG. 9 illustrates an exemplary method for performing image search based on a Mahalanobis metric, according to an embodiment of the present principles.

[26] FIG. 10 illustrates a block diagram of an exemplary system in which multiple user devices are connected to an image search engine according to the present principles.

[27] FIG. 11 illustrates a block diagram of an exemplary system in which various aspects of the exemplary embodiments of the present principles may be implemented.

DETAILED DESCRIPTION

[28] The present principles are directed to image search and provide various features compared to the existing methods. First, the proposed approaches may rely on a correlation metric to compare different items instead of a distance metric as in the majority of earlier works. This enables a more flexible framework than those based on the distance metric while offering computational efficiency. Secondly, the proposed methods may use sparse representations in the proposed correlation metrics. This enables efficient storage of the data items in a database and improves the computation speed when used together with the proposed correlation metrics. Thirdly, the proposed methods can also be adapted for use with query items for which the sparse representation is not initially available so that correlation comparison can still be performed quickly while still providing the advantages mentioned above.

[29] In the present application, we denote scalars, vectors and matrices using, respectively standard, bold, and uppercase-bold typeface (e.g., scalar a, vector a and matrix A). We use \_k to denote a vector from a sequence , V2 , ... , v_N, and v_k to denote the k-t coefficient of vector v. We let [a_fe]_fe (respectively, [<¾]_¾) denotes concatenation of the vectors a_fe (scalars a_k) to form a single column vector. The transpose of a vector v is denoted by v^T (similarly for a matrix). Finally, we use ¾ to denote the Jacobian matrix with (i, j)-t entry

[30] FIG. 1 illustrates an exemplary method 100 for performing image search, according to an embodiment of the present principles. At step 110, a query image is input and image search will be performed in an image database to return one or more matching images for the query image. At step 120, a feature vector is calculated for the query image.

[31] A feature vector of an image contains information describing an image's important characteristics. Image search algorithms usually rely on an image encoding function to compute the feature vector y £ M,^N from a given image. Common image feature construction approaches consist of first densely extracting local descriptors x_£ £ M,^d such as SIFT (Scale-invariant feature transform) from multiple resolutions of the input image and then aggregating these descriptors into a single vector y . Common aggregation techniques include methods based on K^"-means models of the local descriptor distribution, such as bag- of-words and VLAD (Vector of Locally Aggregated Descriptors) encoding, and Fisher encoding, which is based on a GMM (Gaussian Mixture Model) model of the local descriptor distribution.

[32] At step 130, a compact representation is calculated for the feature vector. In many applications, a compact representation of a given data is a point of interest since these representations provide a better understanding of the underlying structures in the data. Compact representation can be any representation that represents original vectors by smaller data. Compact representation can be obtained by linear projection on a subspace resulting in smaller vectors than the original data size, or can be sparse representation, for example, obtained using a synthesis model and an analysis model as described below.

[33] Synthesis Model and Dictionary Learning

[34] Representing a data vector y £ M,^N as a weighted sum of M known atoms £ ,^N as in

is called the synthesis model, and vector x is called the representation of vector y in dictionary D. This representation is often more useful when the representation x has only few non-zero entries, z.e. , when x is sparse. For a given dictionary D, one can obtain a sparse representation of data vector y by using an encoder function so that x = E(y, D) . The encoder function E() enforces sparsity on x while keeping the distance to the original data vector, d(y, Dx), sufficiently small. A common example of such an encoder function is the lasso regression defined as

E(y, D) = argmin ||y— Dx||i + λ||χ||ι

x (Z) in which the 1 -norm and Z₂-^norm °f ^a vector of size N are defined respectively as

The regression parameter λ in Eq. (2) defines the tradeoff between the sparsity and the distance.

[35] When many data points in a training set are available, , e T, one can try to find a common dictionary that can sparsely represent all the points in the set. This procedure is called dictionary learning, commonly used in machine learning and signal processing. In general the dictionary learning methods can be posed as an optimization problem:

x_{1 ;} . . . . X7-. D

in which function δ() enforces a small distance between each data vector y_t and its sparse representation Dx_{i ;} the regularization function φ() enforces sparse representations and the regularization function ψ() enforces certain structures within the dictionary D such as unit norm columns.

[36] Analysis Model and Analysis Operator Learning

[37] As an alternative to representing a data vector as a sum of few essential components as in the synthesis model, one can inspect specific properties of the data vector which is called the analysis model. A linear analysis operator, A, can be applied to data point y as in

z = Ay (5) so that the output vector z contains essential information on y. The analysis operators can be very useful if the output, z , is known to be sparse. However unlike synthesis representations, given the vector z the original vector y is often not unique. Hence one can distinguish two types of utilizing analysis operators and sparsity. The first one is finding a vector close to y_s that would have a sparse output vector (or sparse code) with A, where y_s represents a vector for which Ay_s is sparse and y_s and y are as close as possible. A common optimization method for this purpose is

= argmin ||y - y_J ||5 + ||Ay|| ₁

y (6) which is similar to lasso regression used in sparse coding. Similar to dictionary learning, analysis operators can also be learned for large datasets to be used in tasks such as denoising or deconvolution.

[38] The second possible approach is simply finding a sparse code z close to Ay_s. This is more useful for applications in which z is more of interest than y. Since Ay is already known, this operation is often much simpler than solving Eqs. (2) and (6). [39] Referring back to FIG. 1, distance or similarity measures are calculated between the query image and database images at step 140. The measures can be calculated using the feature vectors of the query image and database images, or using compact representations of the query image and the database images, for example, using a Mahalanobis metric. Based on the distance or similarity measures, images are ranked at step 150. One or more matching images are then output at step 160.

[40] The aim of Mahalanobis metric learning is to learn a task- specific distance metric function

£>M(yi _! y2) = (yi - y2)^r M^rM (_{y i} - y₂) ^ for comparing two feature vectors y-^ and y₂ , where M (or M^rM) is the Mahalanobis metric transformation matrix. Such learned distances have been used extensively to adapt feature vectors to various image search related tasks. For example, the Mahalanobis metric can be used in a face verification problem where the feature vectors y_{ and y₂ are extracted from images of faces and the aim is to learn M so that the test

specifies whether the face images are of the same person.

[41] The Mahalanobis metric can also be used in nearest-neighbor-based classification methods. In this case, a set of labeled image feature vectors {y^ y, e { 1 , . . . , C}}, belonging to one of c classes is used as a classifier. Given a new test feature y, the class label γ_£ assigned to it is that of the nearest y_t under the Mahalanobis metric, ji s.t. = argminZ½(y, y./)-

J (9) Extensions of this approach can also use a voting scheme based on the closest n features.

[42] Another task that can be addressed by Mahalanobis metric learning is that of image ranking. In this case, we are given a query feature vector y^q and we wish to sort a database of features { j^ so that

D_M(y^q, yi, ) < D_M(y^q, y_ij , ). ^

In this case, matrix M is learned so that the resulting ranking operation corresponds to human visual perception.

[43] In the present application, we consider the problem of efficiently comparing and ranking items taken from a large set. An example of such a setup can be the comparison of images or a set of image features. In the following, we propose several optimization approaches that make use of both the sparse representations and some given constraints to determine a better estimate for the similarity function that is adapted to the tasks of verification and ranking.

[44] FIG. 2 illustrates an exemplary method 200 for determining the operator for the similarity function. A training set is input at step 210, which may be a database with annotations, for example, indicating whether pictures are similar or dissimilar. The database imposes constraints on the similarity function at step 220, for example, if two pictures are indicated as similar in the training database, the learned similarity function should provide a high similarity score between these two pictures. Given the constraints on similarity between pictures, the operator for the similarity function can be learned at step 230. In the following, the similarity constraints and various learning methods are described in further detail.

[45] Constraints

[46] Let / represent one of many items that we would like to compare. Let it also be given that every data item / is associated with a data vector y £ ,^N . For the example of comparing images, the items represent the images to be compared whereas the data vectors are features extracted from each image for easier processing. We denote S^* (/i J₂) as the similarity function that tracks the human perception for every item pair (7i ,/₂), and we aim to design a similarity function that is close to S^* (/i J₂) . From the training images, a set of constraints over S* () and a training set /,-, / = \ , . . . , T (with corresponding data vectors _y, e T) can be obtained. In one embodiment, we consider two types of constraints each related to a different task of interest.

[47] Pair- wise Constraints and Matching:

[48] In a simpler case, each constraint is defined by a pair of data points and an indicator variable as

- {_lp, _Jp, y_p I y_p I _f . _s« _{Ijp ._{p ) < Sc} Ϊ _{( 12)} for a constant s_c that tracks human perception so that the variable y_p is 1 if two data points are sufficiently similar (or in the same cluster) and —1 if not. Such pairwise constraints are relevant to a task such as matching. Without loss of generality, we define the task of matching as finding a function, S(vi , v₂), given the constraints {C_pail,p }'p₌ , such that for any given pair of query items and their corresponding data vectors, (y_?1 , y₉₂) , the function s() satisfies S(y_9l ,y_¾ ) > 0 if S* ¾_i J_¾ )≥_'*c ^and S(y_3l ,y_?2 ) < 0 otherwise.

[49] FIG. 3 shows exemplary pictures from an image training database, where similar images are grouped together, and images from different groups are dissimilar. Particularly, pictures in the same row (310, 320, 330, or 340) are grouped together in FIG. 3. The pair- wise constraints between two images within a group are set to 1, and the pair- wise constraints between two images from different groups are set to -1.

[50] The task of matching can be described as determining whether a given query data belongs to a cluster in a dataset. For example, in face recognition systems, the given facial picture of a person is compared to other facial data of the same person within the database to perform verification. It is also possible to perform matching between two given data points even though these points belong to a cluster different from the observed clusters in the database.

[51] Triplet Constraints and Ranking:

[52] A more informative set of constraints are defined by a triplet of data points as

,I_Jp) > S* (I,_p ,I_kp )} (₁₃)

That is, in one triplet, item I_ip is more similar to item Ij_p than to item I_kp . The constraints over triplets provide more information on the similarity function and are useful for tasks such as ranking. The task of ranking can be defined as finding a function, S(vi , v₂) given the constraints

, such that for any given triplet of items (<7_ΐ , ¾, <¾) obeying S* (I_qi ,l_q2 ) > S* (/„ , I_q3 ), the function s () satisfies the condition s (y_f/1 , y_q2 ) > S (_y<?1 , y_¾ ). Ranking enables sorting the database items based on the similarity to a query item and it is an essential part of applications such as data search and retrieval. An example for this application can be seen as image based search from a large database of images based on specific similarity criteria. [53] Analysis Similarity

[54] As discussed above, we can define an analysis operator A £ ,^MXN such that sparse code z can be obtained from Ay. FIG. 4 illustrates an exemplary analysis encoding process 400 (z = E_A(A, y)) for generating a sparse code z for vector y, according to an embodiment of the present principles. At step 410, given vector y and analysis operator A, the analysis encoder computes Ay, for example, using liner projection. At step 420, the analysis encoder generates sparse code z using a non-line sparsifying function. The processed vector is then output as sparse code z.

[55] The non-linear sparsifying function can be, for example, but not limited to, hard thresholding, soft thresholding, or a function to select some values to zero and modify other values. The non-linear sparsifying function can also be a step function or a sigmoid function.

[56] The analysis encoding process can also be used to generate sparse binary codes, z_b, if the sparsifying function is simply the step function such that z_{b i} = step(A_{b i}y) = (1 if A_{b i}y > 0

(0 if A y < 0 ^wnere ^b-i *^s ^^e i^_th ^row °^ ^^{e matr}i^x linear projection matrix A_b . The binary codes can directly be used to compare two images with their binary representations in a computationally fast and efficient manner.

[57] In another example, the non-linear sparsifying function that generates non-binary sparse codes is a function that utilizes the binary representations, z_b, by simply selecting the analysis encoding process as Z; = A_{b i}y = = z_{b i} Ajy , or equivalently, z =

E_A(A, y) = z_b O Ay. [58] The approach for computing the sparse codes in the simplest case is equivalent to defining a number of linear features among which only a few are active for each data vector. In more complicated cases the features can also be computed in a non-linear way. Such a representation can be powerful since the comparison using information only on the relevant features can be much more discriminative than simply using a linear projection of the original data vectors. Furthermore, given an analysis operator A, an encoder function to retrieve ζ_έ can be much simpler (for example simple thresholding) than the encoder functions used for dictionaries.

[59] Given an analysis operator A and the encoder function E_A (), we propose to utilize a similarity function of the form

(Analysis Similarity) S_a„ (y,- , y, ) = zjz j , ζ,· = E_A (y_t- , A) , zj = E_A (y, , A) ( \ 4)

It should be noted that, rather than learning distances as described in Eq. (7), this approach learns a similarity function based on a correlation metric.

[60] Here, we need to be careful with the choice of the analysis operator A, since there can be infinitely many sparsifying analysis operators that does not provide information needed for the given task. Hence we propose learning the analysis operator A using the constraints given for the specific task at hand. In general A can be learned with an optimization of the form,

m

A = argmin Y i(C_p) + ψ(Α) s.t. z, = E_A(y, , A) , t = 1 , . . . , T

^A P= I (15) in which the function £(c_p) is selected as £(y_pzj_pz_jp) for the pair-wise constraints for verification, or i{z z_jp - z z_kp) for the triplet constraints for ranking. The function I Q in Eq. (15) is a function that penalizes the incorrectly estimated similarities in the training set, i.e., when y '„ VZ; ^Lp ^TZ J:p or z, ^L-p ^TZ J:p— z, ^L-p ^Tz ^_kp is neg ⁰ative.

[61] Two possible examples for the penalty function are the hinge loss functions as shown in FIG. 5A and FIG. 5B. In particular, FIG. 5A shows a parametrized hinge loss function l x) = min(— (x— a), 0) , and FIG. 5B shows a continuous hinge loss function, l (x) = log(exp(— x) + 1) / . It should be noted that in order to learn binary representations that are generated by the step function, the step function must be replaced by a continuous function with a non-zero derivative during the learning process. An example is using the sigmoid function, sgm_a (x) = ^__ax. The regularization function ψ() is optional and can be used to enforce additional constraints on the operator A. For example, when the binary sparse representations are being learned, the regularization function can be selected as the sum of all the coefficients in the binary representations of the training data, Ψ(Α) = β∑^₌₁[1 ... l]z_{b t} =

- Another example for the regularization function ψ() is an indicator

function that penalizes the choices of A that do not obey a certain property such as having normalized rows. The vectors yi , . . . , y_r are all the vectors used in the constraints (and equivalently in the training set T).

[62] For the case that the sparse codes are generated via the sparse binary codes, one can also jointly learn A and A_b , by setting the analysis encoding process as E_A(A, y) = sgm_a(A_by) O Ay during the optimization for learning, and learn both A_b and A jointly.

[63] FIG. 6 illustrates an exemplary process 600 for learning analysis operator A using pair- wise constraints, according to an embodiment of the present principles. The input of the learning process includes many training vector pairs, { yi_£, y₂i)i, each pair of which is marked as similar or dissimilar (γ_£ = 1 or —1). The set of annotations, {γ_£}_£, is also input to the learning process. Assuming an analysis operator A, for a pair of vectors yi_£, y_{2 £}, analysis encoder (610) can generate sparse codes z_l£, z_{2 £} , respectively. Subsequently, a similarity function (620) can be used to calculate the similarity between y_l£ and y_2£, for example, as $αη (Ύιί_> Υ₂ί) ^{= ζ}ΐίι^ζ ₂ί · Using the estimated similarity metric S_an(y_li, y₂i) and annotated similarity result γ_£, a penalty function (630), for example, as described in Eq. (15), can be applied. Optionally, constraints on analysis operator A can be applied (640), for example, using function ψ() as described in Eq. (15). Generally the penalty function sets a large value when the estimated similarity metric does not match the annotated result. The penalty function is accumulated over the training vector pairs, and the analysis operator that minimizes the penalty function, i.e., the analysis operator that provides the closest similarity measures to the annotation results is chosen as the solution A.

[64] The learning process when triplet constraints are used for training is similar to process 600. However, the input now includes training vector triplets { Υιί, Υ₂ί_> Υ3ί)ί , where y_l£ and y_{2 £} are more similar than y_l£ and y_3£ are. The analysis encoder generates sparse codes z_l£j z_{2 £}, z_3£ for each training vector triplet Υιί, Υ₂ί_> Υ3ί · The similarity function is applied to z_l£, z_2£ and to z_l£, z_3£ to get S_an(y_lit y_{2 i}) and S_an (y_lit y_3i), respectively. The penalty function takes S_an(y_li, y₂i) and S_an (yi_£, y_3£) as input, and penalizes the function when S_an (y_lit y_2i) indicates less similarity than S_an (y_lit y_3i) .

[65] It is possible to solve the minimization problem of Eq. (15) directly using steepest descent methods. It is also possible to simplify it further by relaxing the constraint in Eq. (15), so that the objective function is smoother and easier to optimize. For a simple encoder function such as

E_A (y, A) = argmin ||z— H^ + λ||ζ|| ι

z (16) one can relax the equality constraint in Eq. (15) and perform the joint minimization

A, zi , . . . , z_T—

in which the function t(c_p) is selected according to the task as in Eq. (15) and the constants λι , λ₂ > 0 determine the tradeoff between the performance in the task, the sparsity of the codes and the distance between z, and E_A(y, , A).

[66] FIG. 7A shows exemplary sparse codes for images in a database, where FIG. 7B is an expanded view of the upper-right portion of FIG. 7A. In the visualization of the sparse coefficients (vertical axis) of the first 2000 images (horizontal axis), a dark pixel (710) indicates "0" in the vector, and a gray pixel (720) indicates the magnitude of the non-zero in the vector. We can see that most pixels in FIG. 7 are dark (i.e., coefficients are sparse), and thus, our methods successfully learned sparse representation. Therefore a similarity function can be computed very fast given the sparse representation. [67] FIG. 8A illustrates an exemplary process 800A for performing image matching, according to an embodiment of the present principles. Two input images are represented by feature vectors y-^ and y₂, respectively (810). Analysis encoder (820) with learned operator A is used to sparsify vectors y-^ and y₂ to generate sparse codes Z-L and z₂ , respectively. Then a similarity metric (830) can be calculated based on the sparse codes, for example, using the correlation metric as Eq. (14). Based on whether the similarity metric exceeds a threshold or not, we decide whether the two input images are matching or not.

[68] FIG. 8B illustrates an exemplary process 800B for performing image ranking for a query image, according to an embodiment of the present principles. For the query image and the database images, feature vectors y^ and y_lt . . . , y_n are generated (850), respectively. Analysis encoder (860) with learned operator A is used to sparsify vectors y^ and y_1; . . . , y_n to generate sparse codes z_q and z_1; . . . , z_n, respectively. Then a similarity metric (870) can be calculated based on the sparse codes for the pair of { z_q, ζ_έ}, i = 1, ... , n, for example, using the correlation metric as Eq. (14). Based on the values of the similarity metrics, we can decide the order of similarity to the query image among the database images and images are ranked (880). [69] A post processing step to the encoder function can be added that adds an extra entry to vector z that is equal to 1, which would further improve the flexibility of the proposed encoding algorithms. A pre-processing step to the encoder function can be added that adds an extra entry to the vector y that is equal to 1, which would further improve the flexibility of the proposed matching and ranking algorithms.

[70] It should be noted that for image databases, the process of computing the sparse codes z-L, . . . , z_n can be performed offline. Thus, for feature vectors yi, . . . , y_n representing images from the databases, the corresponding encoding functions can be pre-computed offline and the sparse codes can be stored.

[71] Multilayer Analysis Similarity

[72] It is possible to interpret the analysis encoder function E_A(y, A) (such as Eq. (16)) as a single layer neural network realization with the network coefficients given by the operator A. It is already known that the performance of neural networks are significantly improved by deep architectures that have multiple layers. This idea can also be used for the proposed analysis similarity computation by replacing the analysis encoder function E_A(y, A) with the N-layer analysis encoder function

E ^ _!, ... ^) = E_A (... E_A (E_A(y, A₁), A₂) ... , A_N ) (27) in Eq. (15). In one embodiment, where E_A(y, A) = soft( Ay), where soft thresholding is defined as

(| Oi | - Af) sign Of if la^Af

soft( a) = [ (28)

0 el s

the N-layer analysis encoder becomes

E ^ _!, ... ^) = spft( A_yv ... soft( A₂ soft( A₁y)) ... ). (29)

The operators A_1; ... , A_N and parameters _1; ... , λ_Ν can be trained using a training database, for example, using pair- wise constraints or triplet constraints. [73] Metric Learning with Automatic Rank Minimization

[74] The analysis operator can also be used to learn a low rank Mahalanobis metric transformation matrix W such that the similarity function is simply

s{yi, yj) = yj^Tw_yi (30) where W = A^TA, as described in an article by K. Simonyan, O. M. Parkhi, A. Vedaldi, and A. Zisserman, entitled "Fisher Vector Faces in the Wild," In British Machine Vision Conference, 2013. In metric learning, it is known that when the Mahalanobis matrix is low rank, it can be used to generalize the characteristics of the overall system. However the rank of matrix W must often be explicitly defined before the optimization. Alternatively, some methods penalize the nuclear norm of the matrix W in the classical Mahalanobis metric learning so that a low rank Mahalanobis matrix can be learned. However this approach requires a singular value decomposition of the matrix W (or A) at every iteration of the learning algorithm and can significantly slow down the learning algorithm when the training dataset is large.

[75] The analysis similarity learning processes as described above, which enforce sparse codes, also enforce the matrix A to be composed of rows that provide the most contribution to the similarity function for the ranking task. As a result, one can train the system by minimizing the same objective function as described in Eq. (15), and then use the similarity function in Eq. (30) with W = A^TA where A is formed by using N most significant rows of A, namely, N rows of A with largest norm (power), or N rows of A that lead to largest average power among the resulting sparse codes of the training data. This enables finding a low rank matrix without the need to perform singular value or eigenvalue decompositions during the learning stage and it can be performed on large databases using a stochastic gradient descent type of algorithm.

[76] If we consider the vectors ζ_έ = Ay_i; z_;- = Ay_;- as the feature vectors, then similarity function in Eq. (30) is a correlation based function since S(y£, y/) = y JWy^ = ζ_; ^Γζ_έ. The same approach can be used also for the classical Mahalanobis metric learning based on the distances in which the distance between two items are estimated as

D (yt, yj) = V( ; - ;)^rw( ; - ;) = IPto - y;)ll₂ (³¹⁾ where W is a low rank and positive semi-definite matrix. We can enforce the transformed difference of the training pairs, A( _£— y,), to be sparse to obtain a low rank W. Hence we can replace the similarity function in Eq. (15) with S(yi, y_;) =— D² (yi, y_;) that is based on distances rather than correlations to learn an analysis operator A, and then use W = A^TA as the low rank Mahalanobis matrix in Eq. (31) where A is formed by using most significant rows of A. Note that in Eq. (15), the term zjz^ in C_p is the predefined similarity function as mentioned in Eq. (14), which can be replaced with a distance-based metric. Generally, the proposed training/learning method can obtain a low rank matrix for metric learning in an efficient and low-complexity manner. [77] The automatic rank minimization can be used for image matching and search. FIG. 9 illustrates an exemplary method 900 for performing image search based on a Mahalanobis metric, according to an embodiment of the present principles. At step 910, a query image is input. At step 920, we can calculate analysis operator A, for example, using the analysis similarity learning process as described before. Alternatively, we can use a modified version of the learning process that uses distance-based instead of correlation-based similarity function. Matrix A can then be obtained by using most significant rows of A. At step 930, we can calculate Mahalanobis metric transformation matrix W = A^TA. Then at step 940, we can calculate a similarity metric using Eq. (30) or (31) between the query image and images from an image database. At step 950, we can rank the order of similarity to the query image among the images of the image database based on output similarity metrics. Subsequently, we choose the best match(es) as the matching image(s) and output the matching image(s) at step 960.

[78] Initial experiments have been performed using the proposed similarity metric in Eq. (14) and enforcing normalized rows for matrix A. The image descriptors and the datasets described in an article by K. Simonyan and A. Zisserman, entitled "Very Deep Convolutional Networks for Large-Scale Image Recognition," CoRR, Sept. 2014, are used to train and test the learned similarity metric with the only difference being normalizing the descriptors. The resulting false positive rates for 95% recall are shown in Table 1. For comparison, the performance of using the normalized descriptors (by computing correlation or equivalently i distance) without any learning has also been shown. The proposed metric provides a good similarity estimation performance.

TABLE 1. False positive rate corresponding to 95% recall

[79] FIG. 10 illustrates an exemplary system 1000 that has multiple user devices connected to an image search engine according to the present principles. In FIG. 10, one or more user devices (1010, 1020, and 1030) can communicate with image search engine 1060 through network 1040. The image search engine is connected to multiple users, and each user may communicate with the image search engine through multiple user devices. The user interface devices may be remote controls, smart phones, personal digital assistants, display devices, computers, tablets, computer terminals, digital video recorders, or any other wired or wireless devices that can provide a user interface.

[80] The image search engine 1060 may implement various methods as discussed above. Image database 1050 contains one or more databases that can be used as a data source for searching images that match a query image or for training the parameters.

[81] In one embodiment, a user device may request, through network 1040, a search to be performed by image search engine 1060 based on a query image. Upon receiving the request, the image search engine 1060 returns one or more matching images and/or their rankings. After the search result is generated, the image database 1050 provides the matched image(s) to the requesting user device or another user device (for example, a display device).

[82] When a user device sends a search request to the image search engine, the user device may send the query image directly to the image search engine. Alternatively, the user device may process the query image and send a signal representative of the query image. For example, the user device may perform feature extraction on the query image and send the feature vector to the search engine. Or the user device may further perform sparsifying function and send the sparse representation of the query image to the image search engine. These various embodiments distribute the computations needed for image search between the user device and image search engine in different manners. The embodiment to use may be decided by the user device's computational resources, network capacity, and image search engine computational resources.

[83] The image search may also be implemented in a user device itself. For example, a user may decide to use a family photo as a query image, and to search other photos in his smartphone with the same family members.

[84] FIG. 11 illustrates a block diagram of an exemplary system 1100 in which various aspects of the exemplary embodiments of the present principles may be implemented. System 1100 may be embodied as a device including the various components described below and is configured to perform the processes described above. Examples of such devices, include, but are not limited to, personal computers, laptop computers, smartphones, tablet computers, digital multimedia set top boxes, digital television receivers, personal video recording systems, connected home appliances, and servers. System 1100 may be communicatively coupled to other similar systems, and to a display via a communication channel as shown in FIG. 11 and as known by those skilled in the art to implement the exemplary video system described above. [85] The system 1100 may include at least one processor 1110 configured to execute instructions loaded therein for implementing the various processes as discussed above. Processor 1110 may include embedded memory, input output interface and various other circuitries as known in the art. The system 1100 may also include at least one memory 1120 (e.g., a volatile memory device, a non-volatile memory device). System 1100 may additionally include a storage device 1140, which may include non-volatile memory, including, but not limited to, EEPROM, ROM, PROM, RAM, DRAM, SRAM, flash, magnetic disk drive, and/or optical disk drive. The storage device 1140 may comprise an internal storage device, an attached storage device and/or a network accessible storage device, as non-limiting examples. System 1100 may also include an image search engine 1130 configured to process data to provide image matching and ranking results.

[86] Image search engine 1130 represents the module(s) that may be included in a device to perform the image search functions. Image search engine 1130 may be implemented as a separate element of system 1100 or may be incorporated within processors 1110 as a combination of hardware and software as known to those skilled in the art. [87] Program code to be loaded onto processors 1110 to perform the various processes described hereinabove may be stored in storage device 1140 and subsequently loaded onto memory 1120 for execution by processors 1110. In accordance with the exemplary embodiments of the present principles, one or more of the processor(s) 1110, memory 1120, storage device 1140 and image search engine 1130 may store one or more of the various items during the performance of the processes discussed herein above, including, but not limited to a query image, the analysis operator, synthesis operator, sparse codes, equations, formula, matrices, variables, operations, and operational logic.

[88] The system 1100 may also include communication interface 1150 that enables communication with other devices via communication channel 1160. The communication interface 1150 may include, but is not limited to a transceiver configured to transmit and receive data from communication channel 1160. The communication interface may include, but is not limited to, a modem or network card and the communication channel may be implemented within a wired and/or wireless medium. The various components of system 1100 may be connected or communicatively coupled together using various suitable connections, including, but not limited to internal buses, wires, and printed circuit boards.

[89] The exemplary embodiments according to the present principles may be carried out by computer software implemented by the processor 1110 or by hardware, or by a combination of hardware and software. As a non-limiting example, the exemplary embodiments according to the present principles may be implemented by one or more integrated circuits. The memory 1120 may be of any type appropriate to the technical environment and may be implemented using any appropriate data storage technology, such as optical memory devices, magnetic memory devices, semiconductor-based memory devices, fixed memory and removable memory, as non-limiting examples. The processor 1110 may be of any type appropriate to the technical environment, and may encompass one or more of microprocessors, general purpose computers, special purpose computers and processors based on a multi-core architecture, as non-limiting examples. [90] The implementations described herein may be implemented in, for example, a method or a process, an apparatus, a software program, a data stream, or a signal. Even if only discussed in the context of a single form of implementation (for example, discussed only as a method), the implementation of features discussed may also be implemented in other forms (for example, an apparatus or program). An apparatus may be implemented in, for example, appropriate hardware, software, and firmware. The methods may be implemented in, for example, an apparatus such as, for example, a processor, which refers to processing devices in general, including, for example, a computer, a microprocessor, an integrated circuit, or a programmable logic device. Processors also include communication devices, such as, for example, computers, cell phones, portable/personal digital assistants ("PDAs"), and other devices that facilitate communication of information between end-users.

[91] Reference to "one embodiment" or "an embodiment" or "one implementation" or "an implementation" of the present principles, as well as other variations thereof, mean that a particular feature, structure, characteristic, and so forth described in connection with the embodiment is included in at least one embodiment of the present principles. Thus, the appearances of the phrase "in one embodiment" or "in an embodiment" or "in one implementation" or "in an implementation", as well any other variations, appearing in various places throughout the specification are not necessarily all referring to the same embodiment. [92] Additionally, this application or its claims may refer to "determining" various pieces of information. Determining the information may include one or more of, for example, estimating the information, calculating the information, predicting the information, or retrieving the information from memory.

[93] Further, this application or its claims may refer to "accessing" various pieces of information. Accessing the information may include one or more of, for example, receiving the information, retrieving the information (for example, from memory), storing the information, processing the information, transmitting the information, moving the information, copying the information, erasing the information, calculating the information, determining the information, predicting the information, or estimating the information.

[94] Additionally, this application or its claims may refer to "receiving" various pieces of information. Receiving is, as with "accessing", intended to be a broad term. Receiving the information may include one or more of, for example, accessing the information, or retrieving the information (for example, from memory). Further, "receiving" is typically involved, in one way or another, during operations such as, for example, storing the information, processing the information, transmitting the information, moving the information, copying the information, erasing the information, calculating the information, determining the information, predicting the information, or estimating the information.

[95] As will be evident to one of skill in the art, implementations may produce a variety of signals formatted to carry information that may be, for example, stored or transmitted. The information may include, for example, instructions for performing a method, or data produced by one of the described implementations. For example, a signal may be formatted to carry the bitstream of a described embodiment. Such a signal may be formatted, for example, as an electromagnetic wave (for example, using a radio frequency portion of spectrum) or as a baseband signal. The formatting may include, for example, encoding a data stream and modulating a carrier with the encoded data stream. The information that the signal carries may be, for example, analog or digital information. The signal may be transmitted over a variety of different wired or wireless links, as is known. The signal may be stored on a processor-readable medium.

Claims

1. A method for performing image search, comprising:

accessing (130) a first sparse representation of a query image, the first sparse representation being based on a first feature vector corresponding to the query image and an analysis operator;

determining (140) a similarity metric between the query image and a second image of an image database using a correlation between the first sparse representation and a second representation, the second sparse representation being based on a second feature vector corresponding to the second image and the analysis operator; and

generating (160) an image search output based on the similarity metric between the query image and the second image.

2. The method according to claim 1, wherein the image search output indicates one of (1) a rank of the second image and (2) whether the second image matches the query image.

3. The method according to claim 1 or 2, wherein the first sparse representation is received from a user device via a communication network, further comprising transmitting the output to the user device via the communication network.

4. The method according to any of claims 1-3, wherein the first sparse representation is based on a product of the analysis operator and the first feature vector, and wherein the second sparse representation is based on a product of the analysis operator and the second feature vector.

5. The method according to any of claims 1-4, wherein at least one of the first sparse representation and the second sparse representation is binary.

6. The method according to any of claims 1-5, wherein the first sparse representation and the second sparse representation are non-binary, and wherein the first sparse representation and the second sparse representation are determined from a third sparse representation and a fourth sparse representation, respectively, wherein the third sparse representation and the fourth sparse representation are binary.

7. The method according to any of claims 1-6, wherein the analysis operator is determined based on a set of pair- wise constraints, wherein each pair-wise constraint indicates whether a corresponding pair of training images are similar or dissimilar.

8. The method according to any of claims 1-7, wherein the analysis operator is determined based on a set of triplet constraints, wherein each triplet constraint indicates that a first training image of the triplet is more similar to a second training image of the triplet than to a third training image of the triplet.

9. The method according to claim 7 or 8, wherein the analysis operator is trained such that a similarity metric determined for training images corresponding to a pair-wise constraint or a triplet constraint is consistent with what the pair-wise constraint or the triplet constraint indicates.

10. The method according to claim 9, wherein the analysis operator is determined using a penalty function.

11. The method according to any of claims 1-10, wherein the analysis operator is determined using a multiple layer neural network.

12. The method according to any of claims 1-11, wherein the analysis operator is used to determine a Mahalanobis metric transformation matrix.

13. An apparatus for performing image search, comprising:

an input configured to access a first sparse representation of a query image, the first sparse representation being based on a first feature vector corresponding to the query image and an analysis operator; and

one or more processors (1130) configured to:

determine a similarity metric between the query image and a second image of an image database using a correlation between the first sparse representation and a second representation, the second sparse representation being based on a second feature vector corresponding to the second image and the analysis operator, and

generate an image search output based on the similarity metric between the query image and the second image.

14. An apparatus for performing image search, comprising a memory and one or more processors configured to perform the method according to any of claims 1-12.

15. A non-transitory computer readable storage medium having stored thereon instructions for implementing a method according to any of claims 1-12.