Research On Techniques Of Nearest Neighbor Search And Image Inpainting

Nearest neighbor search (NNS) problem is the basis of many image processingalgorithms, which largely influences the effect the results of other image processingalgorithms. The main problem that the nearest neighbor search algorithm faces is thesearch efficiency and accuracy rate cannot well meet the real applications. Imageinpainting is performed on the image information of the defect area filled withinformation 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 information completely ortake full advantage of the characteristics of the whole image.This thesis presents an approximate nearest neighbor search algorithm whichcombines the hierarchy based VP-tree and the image-based local consistency ofnearest neighbor search algorithm to improve the accuracy and efficiency. Weproposed a new pruning algorithm, to improve the efficiency and accuracy of thesearch process for VP-tree, which performs better than the past algorithms. Besides, acomplete elimination of redundant computation exact nearest neighbor searchalgorithm has been proposed, which improves the efficiency of constant times, andmakes the efficiency independent of the selected patch size.Besides, this thesis proposes a new region based image inpaiting method.. Thismethod can repair the structural information more completely. In the process oftexture repair, in order to take full advantage of the characteristics of the local imageconsistency, we merged adjacent patches to a region. Additionally, through theimprovements of repair patch priority calculation formula and changing the originalgreedy repair process, we reduced the problem of error propagation results for thefinal restoration affected. Combining the above improvements, we have made theresults of image inpainting more consistent with the human visual habits.