最近邻搜索及其图像修复技术的研究.pdf

独创性声明

本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的
研究成果,除了文中特别加以标注和致谢之处外,论文中不包含其他人已经发表
或撰写过的研究成果,也不包含为获得天津大学或其他教育机构的学位或证
书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中
作了明确的说明并表示了谢意。


学位论文作者签名: 签字日期: 年月日

我是爱天大的!!



学位论文版权使用授权书


本学位论文作者完全了解天津大学有关保留、使用学位论文的规定。
特授权天津大学可以将学位论文的全部或部分内容编入有关数据库进行检
索,并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校
向国家有关部门或机构送交论文的复印件和磁盘。
(保密的学位论文在解密后适用本授权说明)



学位论文作者签名: 导师签名:

签字日期: 年月日签字日期: 年月日
摘要
最近邻搜索是许多图像处理算法中的基础,其处理效果很大程度上影响着其
他图像处理算法的结果。搜索效率和准确率较低、无法很好的满足某些图像处理
算法的应用成为当前最近邻搜索算法所面临的主要问题。图像修复是对图像中的
信息缺损区域进行填充的过程,其目的是恢复存在信息缺损的图像,并使观察者
难以察觉图像曾经缺损或已被修复。然而,现有的图像修复方法查找并修复结构
信息过少,且未充分的利用整幅图像的特点进行修复,导致修复结果与人类视觉
习惯仍有一定差距。
针对以上问题,本文提出了一种结合 VP 树(Vantage Point-tree)结构和
图像局部一致性的近似最近邻搜索算法,提高了准确率和搜索效率。针对 VP 树
的特点,我们设计了新的剪枝算法,使得搜索的效率和准确率较过去的算法有了
比较明显的提高;此外,推广上述算法并提出一种完全消除冗余计算的精确最近
邻搜索算法,将精确最近邻搜索的效率提高了常数倍,并且使得计算速度独立于
所选块的尺寸。
其次,本文提出了一种基于域的图像修复新方法。这种方法可以更加完整的
进行图像结构信息的修复。在纹理信息修复时,将相邻的块进行合并,以域的形
式进行修复,从而充分利用图像的局部一致性的特点。此外,通过设计新的待修
复块优先级计算方法,改变已有方法中的贪心修复的过程,从而减小了错误传递
问题对于最终修复结果的影响。实验表明,该方法获得的得图像修复结果更加符
合人类的视觉习惯。

关键词: VP 树 PatchMatch 域局部一致性最近邻搜索图像修复
ABSTRACT
Nearest neighbor search (NNS) problem is the basis of many image processing
algorithms, which largely influences the effect the results of other image processing
algorithms. The main problem that the nearest neighbor search algorithm faces is the
search efficiency and accuracy rate cannot well meet the real applications. Image
inpainting is performed on the image information of the defect area filled with
information process with the aim of restoring image defect information. However,
there is still a certain gap between image inpainting results and human visual habits,
because the existing method cannot find out the structural pletely or
take full advantage of the characteristics of the whole image.
This thesis presents an approximate nearest neighbor search algorithm which
combines the hierarchy based VP-tree and the image-based lo