Robust Order-based Methods for Feature Description
Raj Gupta, Harshal Patil and Anurag Mittal
Department of Computer Science and Engg.
Indian Institute of Technology Madras, Chennai INDIA - 600036
{rgupta,harshal,amittal}@cse.iitm.ac.in
Abstract
Feature-based methods have found increasing use in
many applications such as object recognition , 3D rec on-
struction and mosaicing. In this paper, we focus o n the
problem of matching such features. While a h istogram-of-
gradients type methods such as SI FT, GLOH and Shape
Context are currently p opular, several papers have sug-
gested using orders of pixels rather than raw intensities an d
shown improved results for some applications. The papers
suggest two different techniques for doing so: (1) A His-
togram of Relative Orders in the Patch and (2) A Histogram
of LB P codes. While these methods have shown g ood per-
formance, they neglect the fact that the orders can be quite
noisy in the presence of Gaussian noise. In this paper, we
propose changes to these approaches to make them robust
to Gaussian noise. We also show how the descriptors can
be matched using recently developed more advanced tech-
niques to obtain better matching performance. Finally, we
show that the two method s have complimentary strengths
and tha t by combining the two descriptors, one obtains
much better results tha n either of them con sid ered sepa-
rately. The re sults are shown on the standard 2D Oxford
and the 3D Caltech datasets.
1. Introduction
The use of features for image repr esentation and
matching has gained tremendous importance and popu-
larity in recent years for problems as diverse as Im-
age Alignment, mosiacing, 3D Reconstruction, Object
Recognition and Tracking. Features are extracted using
methods such as Harris features[4], Harris-affine, Hes-
sian, Hessian-affine[13] , M SER (Maximally Stable Ex-
tremal Regions)[20], DOG (Difference of Gaussians)[10]
and others[6, 25], metho ds for matching (normalized)
patches include the popular SIFT (Scale Invariant Fea-
ture Transform)[10] and its variants such as GLOH ( G ra-
dient Location and Orientation Histog ram)[15], Shape
Context[18] and other modifications of such gradient/edge
based methods such as [1, 7, 8, 18, 12].
More recently, methods have been proposed[11, 3] that
use orders of pixels rather than raw intensities and the re-
sults from these methods are encouraging. In this paper, we
propose new ways of using the orde r be tween pixels that are
more robust to noise in the underlying data. The two meth-
ods propo sed capture complementary properties of a feature
region - one captures the overall distribution of pixels in the
patch and the other captures local gradient properties.
The first method is based on orders of pixels relative to
the entire patch and builds a histogram based on the rela-
tive position of the intensities w.r.t. to the entir e patch. The
second method looks at local orders of pixels and general-
izes the Center-Symmetric Local Binary Patterns (CS-LBP)
descriptor. Specifically, instead of a binary code, we de-
velop a ternary code, which we call Center Symm e tric Lo-
cal Ternary Patterns (CS-LTP). Both these methods are de-
signed to b e more robust to Gaussian noise than previously
considered descriptors. They captu re complementary infor-
mation and a combination of th ese two methods was found
to improve upon either of the two considered separately.
2. Related Work
The idea of matching images/features using order of in-
tensities rather than raw intensities is not new. By consid-
ering only th e orders be twe en pixels rather than their in-
tensities, one o btains invariance to a monotonic change in
the intensities. The Census algorithm[27] transforms the
intensity space to an “order” space, where a bit pattern is
formed by looking at the orders of a given pixel with its
neighbors. This algorithm essentially counts the numbe r of
flipped point pairs in the patch. Bhat and Nayar[2] use an
improved version of this algorithm where they somewhat
alleviate the problem of counting even one salt-and-pepper
error in a pixel multiple times. Mittal and Ramesh [16] pro-
posed a method in which the penalty for a n order flip is pro-
portion al to the intensity difference between the two flipped
pixels. This reduces the error due to pixels whose order
may have got flipped due to Ga ussian noise. Finally, Xie et.
al. [26] and Sing h et al [23] present a statistical approach