On The Application Of Multidimensional Scaling In Image Ranking

Image ranking is a fundamental problem in image retrieval.Given a labeled image dataset(referred as the training set),image ranking is to find the most relevant images for a query image based on the training set.In this paper,we analyze the large margin nearest neighbor classification algorithm and study the linear distance metric learning for image ranking.At the same time,we propose a new image ranking algorithm.The new approach is based on metric learning,and uses the idea of multidimensional scaling and Euclidean distance matrix.It can find the desired image from the training set accurately and efficiently.Firstly,we decompose the metric matrix,and the problem is cast as looking for a linear map between two sets of points.A set of points is the initial point,and the other set of points is the embedding points of the initial points.Secondly,we obtain the embedding points in a low-dimensional space by constructing a dissimilarity matrix and utilizing classical multidimensional scaling.During the construction of the dissimilarity matrix,we add the ordinal information.This makes the distances between the embedding points layered.Consequently,the learned metric matrix maintains the ordinal relationship of the labels.Also,we prove that the constructed matrix is a Euclidean distance matrix.The resulting model is an unconstrained and nonconvex model,and the objective function is the least square form,while can better fit the data structure.Numerical experiments are performed using UMIST and FG-NET datasets.Extensive numerical results demonstrate the improvement of the new approach both in ranking performance and speed.