# Image Inpainting Based on Multi-Patch Match with Adaptive Size
## 3 Proposed Approach
### Multi-Patch Match  
During a single iteration of the existing patch-based methods, including Criminisi's, only one target patch can be filled after the match process, so that a large number of iterations are required to completely fill the missing area. To reduce the total number of iterations, we also propose the strategy of \"multi-patch match\": In each iteration, we appropriately select multiple pixels \(\hat{p}_{i}\) (\(i=1,2,3,\ldots\)) with \"the highest priority\" on filling front, then generate multiple target patches \(\Psi_{\hat{p}_{i}}\) centered at \(\hat{p}_{i}\), and multiple best sample patches \(\Psi_{\hat{q}_{i}}\) are also searched to fill \(\Psi_{\hat{p}_{i}}\) correspondingly. [PERSON] et al. addressed that the filling order based on the priority model is crucial to prevent error inpainting. We also let the filling priority keep working in our approach. At first, the filling priority \(P(\delta\Omega)\) on \(\delta\Omega\) should be calculated by Equation (1). Based on this, we then select multiple pixels \(\hat{p}_{i}\) with \"the highest priority\" on \(\delta\Omega\) by considering its nonuniformity distribution \(T(\delta\Omega)\). According to the idea that \"target patch and its ideal sample patch should have similar content\" mentioned in Section 3.3, and nonuniformity can be used as a scalar descriptor of content in a patch, match process of the two target patches with different nonuniformity levels can be considered independent, because the patch match in rich-textured regions or strong edges may not disturb the patch match in poor-textured or flat regions, and vice versa. Thanks to this, our multi-patch match is feasible. To reach this goal, a reasonable idea is to divide \(\delta\Omega\) into multiple subsections with different nonuniformity intervals, let \(\hat{p}_{i}\) be the highest priority pixel on each subsection, and multiple target patches \(\Psi_{\hat{p}_{i}}\) are generated centered at \(\hat{p}_{i}\). Specifically, we present the following algorithm shown in Algorithm 1 to show how to generate multiple target patches on filling front \(\delta\Omega\). Figure 4: (**a**) Effect of parameter \(\alpha\) on the subregion for search (colored area); (**b**) illustration for searching the ideal sample patches within the subregion (\(\alpha=0.1\)). ```
1. Initialization: let \(i=1\), find the filling front \(\delta\Omega\), calculate its filling priority \(P(\delta\Omega)\) using Equation (1). 2. Find the highest priority pixel \(\hat{p}_{i}\) on \(\delta\Omega\). 3. Define the subsection \(\delta\Omega_{i}\) of \(\delta\Omega\) as: \(\delta\Omega_{i}=\left\{p\right\}\left|T(p)-T(\hat{p}_{i})\right|\leq 2\alpha\), \(p\in\delta\Omega\right\}\), then reset the priorities to zero for all pixels on \(\delta\Omega_{i}\). 4. If there exits any non-zero priority pixels on \(\delta\Omega\), let \(i=i+1\), back to step 2. Otherwise, go to step 5. 5. Generate target patches \(\Psi_{\hat{p}_{i}}\) centered at \(\hat{p}_{i}\) (\(i=1,2,3,\ldots\)), patch sizes are determined by Equation (9). ```  
**Algorithm 1** Determination of Multiple Target Patches on Filling Front. Note that we do not directly divide the filling front into subsections all at once, but in a progressive way that the current patch center \(\hat{p}_{i}\) determines the current subsection \(\delta\Omega_{i}\) and the next patch center \(\hat{p}_{i+1}\) will be born outside the union of existing subsections \(\delta\Omega_{1}\cup\ldots\cup\delta\Omega_{i}\), namely, both subsections and patch centers are generated synchronously. This comes from the idea that the filling priority model always comes the first, then followed by subsection division. Illustration for above steps is shown in Figure 5. Figure 5f shows the final state, the nonuniformity of target patches \(\Psi_{\hat{p}_{i}}\) are in different intervals, and each patch center also owns the highest filling priority on its subsection.