Computer School, Wuhan University, Wuhan, Hubei, China. 430072.
IEEE Trans Vis Comput Graph. 2011 Aug;17(8):1122-34. doi: 10.1109/TVCG.2010.226.
This paper presents an efficient exact nearest patch matching algorithm which can accurately find the most similar patch-pairs between source and target image. Traditional match matching algorithms treat each pixel/patch as an independent sample and build a hierarchical data structure, such as kd-tree, to accelerate nearest patch finding. However, most of these approaches can only find approximate nearest patch and do not explore the sequential overlap between patches. Hence, they are neither accurate in quality nor optimal in speed. By eliminating redundant similarity computation of sequential overlap between patches, our method finds the exact nearest patch in brute-force style but reduces its running time complexity to be linear on the patch size. Furthermore, relying on recent multicore graphics hardware, our method can be further accelerated by at least an order of magnitude (≥10×). This greatly improves performance and ensures that our method can be efficiently applied in an interactive editing framework for moderate-sized image even video. To our knowledge, this approach is the fastest exact nearest patch matching method for high-dimensional patch and also its extra memory requirement is minimal. Comparisons with the popular nearest patch matching methods in the experimental results demonstrate the merits of our algorithm.
本文提出了一种高效的精确最近邻补丁匹配算法，该算法可以准确地找到源图像和目标图像之间最相似的补丁对。传统的匹配算法将每个像素/补丁视为独立的样本，并构建分层数据结构，如 kd 树，以加速最近邻补丁的查找。然而，大多数方法只能找到近似的最近邻补丁，而不探索补丁之间的顺序重叠。因此，它们在质量上既不准确，在速度上也不是最优的。通过消除补丁之间顺序重叠的冗余相似性计算，我们的方法以暴力方式找到精确的最近邻补丁，但将其运行时间复杂度降低到与补丁大小成线性关系。此外，依靠最近的多核图形硬件，我们的方法可以通过至少一个数量级（≥10×）进一步加速。这极大地提高了性能，并确保我们的方法可以有效地应用于中等大小的图像甚至视频的交互式编辑框架中。据我们所知，这种方法是用于高维补丁的最快精确最近邻补丁匹配方法，并且它的额外内存需求最小。在实验结果中与流行的最近邻补丁匹配方法的比较证明了我们算法的优点。
