fast texture similarity search using walsh-hadamard transform

In this paper we develop a fast texture similarity search algorithms using hadamard transform. ouralgorithm consists of three steps. in the first step we use gabor filter to extract high dimensional features from eachtexture. next, we use a randomized walsh-hadamard transform to embed high dimensional features of each textureinto features of dimension two. in the third step, we use an o(log n)-approximation algorithm for the earth moverdistance (emd) measure to embed the (dis)similarity of two textures that are represented by features of dimensiontwo into ‘1-norm from which we can approximate the (dis)similarity of two textures fast. there are many knownalgorithms for solving problems under the ‘1-norm and reducing the similarity search among textures to computingthe ‘1-distance between vectors allows us to solve this problem faster. in particular, in order to solve the similaritysearch exactly we need o(n2) time, while using the reduction to ‘1-distance via emd solves this problem approximatelyin time o(n log n). our experiments reveals that this approximation guarantee is fairly good for real textures.