In techniques for fast dense patch search and quantization, partition center patches are determined for partitions of example image patches. Patch groups of an image each include similar image patches and a reference image patch that represents a respective patch group. A partition center patch of the partitions is determined as a nearest neighbor to the reference image patch of a patch group. The partition center patch can be determined based on a single-nearest neighbor (1-NN) distance determination, and the determined partition center patch is allocated as the nearest neighbor to the similar image patches in the patch group. Alternatively, a group of nearby partition center patches are determined as the nearest neighbors to the reference image patch based on a k-nearest neighbor (k-NN) distance determination, and the nearest neighbor to each of the similar image patches in the patch group is determined from the nearby partition center patches.