The Taub Faculty of Computer Science Events and Talks

The Approximate Nearest Neighbor Field (ANNF) assigns to each patch in one image, a similar patch from another image. It has recently become a basic building block in numerous applications, e.g., denoising, colorization, alignment and image editing. The increase in popularity of ANNF is largely due to the introduction of PatchMatch, an ANNF algorithm that wisely uses image coherency to speed up the computation.

More recent algorithms further improve efficiency by incorporating indexing methods that rely on projection-based hashing or kd-trees. However, such indexing techniques come with a penalty - they have been designed for L2 distances between raw image patches. Therefore, when the similarity is de ned via distance measures other than L2, the performance of these ANNF algorithms could be compromised.

To overcome this limitation we introduce a method for distance-based hashing.

We further propose an algorithm for computing the ANNF that utilizes the proposed hashing. Since our hashing is distance-based, the suggested algorithm maintains generality for any distance measure. When testing on three different applications, our algorithm is shown to outperform previous approaches in both accuracy and in speed.

M.Sc. research under the supervision of Prof. Lihi Zelnik-Manor (EE, Technion).