Rank SIFT explained

Rank SIFT algorithm is the revised SIFT (Scale-invariant feature transform) algorithm which uses ranking techniques to improve the performance of the SIFT algorithm. In fact, ranking techniques can be used in key point localization or descriptor generation of the original SIFT algorithm.

SIFT With Ranking Techniques

Ranking the Key Point

Ranking techniques can be used to keep certain number of key points which are detected by SIFT detector.^[1]

Suppose

\left\{I_m,m=0,1,...M\right\}

is a training image sequence and

is a key point obtained by SIFT detector. The following equation determines the rank of

in the key point set. Larger value of

R(p)

corresponds to the higher rank of

R(p\inI_0)=\sum_m

I(min
	q\inI_m

{\lVertH_m(p)-q\rVert}₂<\epsilon),

where

I(.)

is the indicator function,

H_m

is the homography transformation from

I₀

I_m

, and

\epsilon

is the threshold.

Suppose

x_i

is the feature descriptor of key point

p_i

defined above. So

x_i

can be labeled with the rank of

p_i

in the feature vector space. Then the vector set

X_feature=\left\{\vecx_1,\vecx_2,...\right\}

containing labeled elements can be used as a training set for the Ranking SVM^[2] problem.

The learning process can be represented as follows:

\begin{array}{lcl} minimize:V(\vecw)={1\over2}\vecw ⋅ \vecw\\ s.t.\ \begin{array}{lcl}\forall \vecx_{i and \vec}x_j\inX_feature,\\ \vecw^T(\vecx_i-\vecx_j)\geqq1 if R(p_i\inI₀)>R(p_j\inI_{0).
\end{array}
\end{array}}

The obtained optimal

\vecw^*

can be used to order the future key points.

Ranking the Elements of Descriptor

Ranking techniques also can be used to generate the key point descriptor.^[3]

Suppose

{\vecX}=\left\{x_1,...,x_N\right\}

is the feature vector of a key point and the elements of

{R}=\left\{r_1,...r_N\right\}

is the corresponding rank of

x_i

r_i

is defined as follows:

r_i=\left\vert\left\{x_k:x_k\geqqx_i\right\}\right\vert.

After transforming original feature vector

\vecX

to the ordinal descriptor

\vecR

, the difference between two ordinal descriptors can be evaluated in the following two measurements.

The Spearman correlation coefficient

The Spearman correlation coefficient also refers to Spearman's rank correlation coefficient.For two ordinal descriptors

\vecR

and

\vecR^'

, it can be proved that

\rho(\vecR,\vecR^')=1-

	N(r
{6\sum
	i-r

	')

	i

²\overN(N^2-1)}

The Kendall's Tau

The Kendall's Tau also refers to Kendall tau rank correlation coefficient.In the above case, the Kendall's Tau between

and

R^'

\tau(\vecR,\vecR^')=

	Ns(r
{2\sum
	i-r

_j,

	')\over
r
	j

N(N-1)},

where s(a,b)= \begin{cases} 1,&ifsign(a)=sign(b)\\ -1,&o.w. \end{cases}

Notes and References

Bing Li; Rong Xiao; Zhiwei Li; Rui Cai; Bao-Liang Lu; Lei Zhang; "Rank-SIFT: Learning to rank repeatable local interest points", Computer Vision and Pattern Recognition (CVPR), 2011
Joachims, T. (2003), "Optimizing Search Engines using Clickthrough Data", Proceedings of the ACM Conference on Knowledge Discovery and Data Mining
Toews, M.; Wells, W."SIFT-Rank: Ordinal Description for Invariant Feature Correspondence", Computer Vision and Pattern Recognition, 2009.