M.Sc Thesis

M.Sc StudentFriedman Itamar
SubjectDistance-Based Hashing for ANN Fields
DepartmentDepartment of Electrical and Computer Engineering
Supervisor PROF. Lihi Zelnik-Manor


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 defined 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.