Feature-based methods have found increasing use in many applications such as object recognition, 3D reconstruction and mosaicing. In this paper, we focus on the problem of matching such features. While a histogram-of-gradients type methods such as SIFT, GLOH and Shape Context are currently popular, several papers have suggested using orders of pixels rather than raw intensities and shown improved results for some applications. The papers suggest two different techniques for doing so: (1) A Histogram of Relative Orders in the Patch and (2) A Histogram of LBP codes. While these methods have shown good performance, 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 techniques to obtain better matching performance. Finally, we show that the two methods have complimentary strengths and that by combining the two descriptors, one obtains much better results than either of them considered separately. The results are shown on the standard 2D Oxford and the 3D Caltech datasets. ©2010 IEEE.