Rank SIFT

Ranking the Key Point

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

Suppose ${\displaystyle \left\{I_{m},m=0,1,...M\right\}}$ is a training image sequence and ${\displaystyle p}$ is a key point obtained by SIFT detector. The following equation determines the rank of ${\displaystyle p}$ in the key point set. Larger value of ${\displaystyle R(p)}$ corresponds to the higher rank of ${\displaystyle p}$.

${\displaystyle R(p\in I_{0})=\sum _{m}I(\min _{q\in I_{m}}{\lVert H_{m}(p)-q\rVert }_{2}<\epsilon ),}$

where ${\displaystyle I(.)}$ is the indicator function, ${\displaystyle H_{m}}$ is the homography transformation from ${\displaystyle I_{0}}$ to ${\displaystyle I_{m}}$, and ${\displaystyle \epsilon }$ is the threshold.

Suppose ${\displaystyle x_{i}}$ is the feature descriptor of key point ${\displaystyle p_{i}}$ defined above. So ${\displaystyle x_{i}}$ can be labeled with the rank of ${\displaystyle p_{i}}$ in the feature vector space. Then the vector set ${\displaystyle X_{featurespace}=\left\{{\vec {x}}_{1},{\vec {x}}_{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:

${\displaystyle {\begin{array}{lcl}minimize:V({\vec {w}})={1 \over 2}{\vec {w}}\cdot {\vec {w}}\\s.t.\\{\begin{array}{lcl}\forall \ {\vec {x}}_{i}\ and\ {\vec {x}}_{j}\in X_{featurespace},\\{\vec {w}}^{T}({\vec {x}}_{i}-{\vec {x}}_{j})\geqq 1\quad if\ R(p_{i}\in I_{0})>R(p_{j}\in I_{0}).\end{array}}\end{array}}}$

The obtained optimal ${\displaystyle {\vec {w}}^{*}}$ 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 ${\displaystyle {\vec {X}}=\left\{x_{1},...,x_{N}\right\}}$ is the feature vector of a key point and the elements of ${\displaystyle {R}=\left\{r_{1},...r_{N}\right\}}$ is the corresponding rank of ${\displaystyle x_{i}}$ in ${\displaystyle X}$. ${\displaystyle r_{i}}$ is defined as follows:

${\displaystyle r_{i}=\left\vert \left\{x_{k}:x_{k}\geqq x_{i}\right\}\right\vert .}$

After transforming original feature vector ${\displaystyle {\vec {X}}}$ to the ordinal descriptor ${\displaystyle {\vec {R}}}$, 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 ${\displaystyle {\vec {R}}}$ and ${\displaystyle {\vec {R}}^{'}}$, it can be proved that

${\displaystyle \rho ({\vec {R}},{\vec {R}}^{'})=1-{6\sum _{i=1}^{N}(r_{i}-r_{i}^{'})^{2} \over N(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 ${\displaystyle R}$ and ${\displaystyle R^{'}}$ is

${\displaystyle \tau ({\vec {R}},{\vec {R}}^{'})={2\sum _{i=1}^{N}\sum _{j=i+1}^{N}s(r_{i}-r_{j},r_{i}^{'}-r_{j}^{'}) \over N(N-1)},}$

${\displaystyle where\quad s(a,b)={\begin{cases}1,&{\text{if }}sign(a)=sign(b)\\-1,&o.w.\end{cases}}}$