Rank SIFT

Ranking the Key Point

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

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

R ( p ∈ I 0 ) = ∑ m I ( min q ∈ I m ∥ H m ( p ) − q ∥ 2 < ϵ ) ,

where I ( . ) is the indicator function, H m is the homography transformation from I 0 to I m , and ϵ 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 f e a t u r e s p a c e = { x → 1 , x → 2 , . . . } containing labeled elements can be used as a training set for the Ranking SVM problem.

The learning process can be represented as follows:

m i n i m i z e : V ( w → ) = 1 2 w → ⋅ w → s . t . ∀   x → i   a n d   x → j ∈ X f e a t u r e s p a c e , w → T ( x → i − x → j ) ≧ 1 i f   R ( p i ∈ I 0 ) > R ( p j ∈ I 0 ) .

The obtained optimal 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.

Suppose X → = { x 1 , . . . , x N } is the feature vector of a key point and the elements of R = { r 1 , . . . r N } is the corresponding rank of x i in X . r i is defined as follows:

r i = | { x k : x k ≧ x i } | .

After transforming original feature vector X → to the ordinal descriptor R → , the difference between two ordinal descriptors can be evaluated in the following two measurements.

The spearman correlation coefficient also refers to Spearman's rank correlation coefficient. For two ordinal descriptors R → and R → ′ , it can be proved that

ρ ( R → , R → ′ ) = 1 − 6 ∑ i = 1 N ( r i − r i ′ ) 2 N ( N 2 − 1 )

The Kedall's Tau also refers to Kendall tau rank correlation coefficient. In the above case, the Kedall's Tau between R and R ′ is

τ ( R → , R → ′ ) = 2 ∑ i = 1 N ∑ j = i + 1 N s ( r i − r j , r i ′ − r j ′ ) N ( N − 1 ) ,

w h e r e s ( a , b ) = { 1 , if  s i g n ( a ) = s i g n ( b ) − 1 , o . w .