Fast Texture Similarity Search Using Walsh-Hadamard Transform

In this paper we develop a fast texture similarity search algorithms using Hadamard transform. Our algorithm consists of three steps. In the first step we use Gabor filter to extract high dimensional features from each texture. Next, we use a randomized Walsh-Hadamard Transform to embed high dimensional features of each texture into features of dimension two. In the third step, we use an O(log n)-approximation algorithm for the earth mover distance (EMD) measure to embed the (dis)similarity of two textures that are represented by features of dimension two into ‘1-norm from which we can approximate the (dis)similarity of two textures fast. There are many known algorithms for solving problems under the ‘1-norm and reducing the similarity search among textures to computing the ‘1-distance between vectors allows us to solve this problem faster. In particular, in order to solve the similarity search exactly we need O(n2) time, while using the reduction to ‘1-distance via EMD solves this problem approximately in time O(n log n). Our experiments reveals that this approximation guarantee is fairly good for real textures.