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