A Video Inpainting Method Based On K-Dimension Tree Structure And Approximate Nearest Matching In Time-spatial Space

In recent years, with the rapid development of personal digital camera products and Internet industry, the researching in computer graphics and image processing get more and more researchers'attention and image and video inpainting technology has gradually become a hot topic in this field. Image inpainting is the technology that restores the defect area using the valid information around it. Image inpainting technology is mainly used to restore the broken part (such as stains and scratches) in photos and paintings and to remove the specified object in images. Video inpainting is the technology based on the traditional image inpainting technology to restore several frames in a video.The starting point of this paper is the traditional digital image inpainting technology; the paper analyzed some kinds of typical inpainting method and compared them. So far, image inpainting methods can be divided into two categories, one is based on partial differential equations (PDE) and the other is based on the texture. The two types of inpainting methods are described in great detail in the second chapter of this paper and are explained with specific examples in the third chapter.The inpainting method based on partial differential equations can better fix the color and structural features of the defect area. The method doesn't relate to complex processes, avoiding the detection and segmentation of the object in the target image. But use the method to inpaint large hole area, if the distance between the pixel which is fixing and the boundary of the hole area is too far, the result of the inpainting will be unclear. Therefore, the result that inpaint images using the method based on partial differential equations is well in terms of structural information but is lack in terms of texture information. So, this method is suitable for inpainting small defect area (such as scratches in the image, etc.).The main idea of the inpainting method based on texture can inpaint well in terms of texture information, so it is suitable for inpainting large hole area but not for inpainting small hole area than the method based on partial differential equations.In this paper, these two methods has been developed to be applied on video inpainting, According to the analysis above, a new video inpainting method-A Video Inpainting Method Based on K-Dimension Tree Structure and Approximate Nearest Matching in Time-Spatial Space-is proposed in the fourth chapter. It is a iterative algorithm and each iteration of the algorithm only to repair one pixel, so the algorithm can avoid the lack of the result that inpaint using the method based on texture in terms of continuity. In addition, since the algorithm is to fix images from the external of the hole area to the internal, so the structural information can be fixed well.Another innovation of this paper is that the K-Dimension tree data structure is used in the video inpainting algorithm for the first time, the advantage of this structure is that searching and matching operations for multidimensional vector can be finished in lower time complexity by using K-Dimension tree structure. Using this structure can greatly reduce the calculation of the inpainting process caused by the searching and matching and improving the efficiency of the algorithm.The second half in the fourth chapter shows the experimental results for several groups of different experimental data. Each group of experimental data represents a typical kind of video inpainting problems. According to the analysis and comparison to the experimental results, it could be seen that the video inpainting method that proposed in this paper is better than traditional video inpainting methods. In the last part of the fourth chapter, this view is proven to be correct by using objective evaluation criteria.Chapter V summarizes the full text and points out the deficiency and made several recommendations for improvements. Due to the limitations of current level of the development of computer hardware, this algorithm has not yet reached the desired results, but it is believed that with the development of the computer science and technology, the algorithm that is proposed in this paper can have large improvement in terms of efficiency and inpainting effect.