# Image Inpainting Based on Multi-Patch Match with Adaptive Size
## 2 Related Work
Repeat the above steps until \(\Omega\) is completely filled. [PERSON]'s algorithm has obtained relatively satisfactory results in filling large-area holes or removing objects in a picture, although shortcomings exit, some of them have been fixed by related works, they are listed as follows:  
1. The confidence term in the priority model may encounter a sharp decline after multiple iterations, while the fluctuation of the data term is relatively stable. Thus, the priority is more likely to be restricted by lower confidence term and become unreliable, leaving incorrect filling order and structural error propagation. Later, [PERSON] et al. [11] demonstrated that different weighted-priority should be chosen for specific structures to get better inpainting results. [PERSON] [12] and [PERSON] et al. [13] changed the priority formula into the exponential and addition form respectively to prevent the confidence term from falling too quickly. [PERSON] et al. [14] eliminated the dependence on the shape of the target region and preserved the stability of confidence term by introducing the gray entropy;
2. The similarity criterion between sample patch and target patch used in [PERSON]'s algorithm is the sum of squared differences (SSD) of corresponding pixels in two patches, which only takes the pixel value into account and does not make full use of the structural information. [PERSON] et al. [15] added the Hellinger distance to measure the similarity of the probability distribution between two patches. [PERSON] [16] introduced a metric of the structural similarity between two patches. [PERSON] et al. [17] also defined a new match rule by taking structure tensor into consideration. These works have successfully reduced the rate of mismatch;
3. [PERSON] et al. chose a fixed patch size of \(9\times 9\) pixels, which is unreasonable, since the patch size directly affects its capability to capture the local texture features and has an important influence on inpainting quality. Different sizes of patch should be applied on regions with different uniformity levels. Generally, smaller patches should be applied on high-frequency areas with more texturesand structures to achieve a finer filling, while larger patches are appropriate for flatter areas to speed up the filling process, this idea was also demonstrated in Reference [1]. There are relatively few researches about this issue. [PERSON] et al. [18] determined the patch size automatically with gradient histograms involved, and this was implemented as an optimization problem that requires extra continuous iterations. However, this process is computationally expensive and takes a longer time;
4. Global search in source region is required in [PERSON]'s method in order to find the best sample patch for the target patch, which needs a large amount of calculation and match time. [PERSON] et al. [17] narrowed the match area by picking out those candidates whose sum of the pixel values is close to the target patch's, but this cannot guarantee that the bad candidates are excluded;
5. [PERSON]'s and related patch-based inpainting techniques require a large number of iterations to completely fill the unknown area, since only one target patch can be filled in a single iteration. At present, there is no related research to handle this deficiency. Compared with problems 1 and 2, there are relatively fewer studies on problems 3 and 4. Aiming at problems 3-5 mentioned above, we provide a novel solution: We first introduce the nonuniformity model, by which the patch size will be determined adaptively to address problem 3. Besides, the strategy of subregion search is proposed to address problem 4 in an effective way. Moreover, the strategy of a multi-patch match is proposed to handle problem 5 for the first time.