Study Of Digital Image Completion Algorithms

As a research hotspot in digital image processing, the purpose of digital image completion is to fill the data missing region, keep the continuity of the structure and texture at the same time, and ensure a natural and reasonable completion result.Digital image completion method is mainly comprised of two categories: inpainting technique and completion technique. The former one is used to restore smaller damaged region, such as scratch and spot. While the later one is used for inpainting larger damaged region, e.g. filling the data missing region after removing larger target. Currently, the inpainting technology are mainly realized based on the high order partial differential equation. The image inpainting technology is not involved in this thesis since it is relatively mature. Current researches mainly focus on the image completion technology, so we tend to discuss this problem in the thesis in detail.Firstly, this thesis presents the research background and significance of digital image completion algorithms and summarizes their research status. Then we deeply discuss two optimal image patch matching method. One is the Walsh-Hadamard transformation method, which can significantly reduce the computation of patch matching and realize the acceleration of algorithm. Another one is a fast searching algorithm based on randomized correspondence, which can take advantage of the relationship between the adjacent optimal patches efficiently and find all the matching relationship rapidly and accurately.Secondly, the thesis improves the traditional energy function, and introduces the LM algorithm to obtain the optimal parameters. After patches searching, we employ the mean value filling method to restore the data missing region. With the hierarchy method for a coarse-to-fine optimization, we finally realize the expansion in both rotation and scale space. Experimental results show that the proposed method can reduce the matching error effetely even when rotation and scaling transformation exist, and achieve perfect completion results.Finally, the thesis discusses two completion algorithms based on pyramid in detail. One is the shift map algorithm, which use data term and smoothness term as cost function, construct pyramid model, use graph cuts technique for a optimal graph labeling, and fill the damaged region according to the shift map relation. Another one is the image melding method based on convolution pyramids, which utilize convolution pyramids model, apply the optimized filter set on the residual image, and perform the errors compensation. Experimental results show that the image after melding can significantly reduce discontinuity on the boundary of the damaged region and obtain more natural and feasible completion result.