# Image Inpainting Based on Multi-Patch Match with Adaptive Size
## 2 Related Work  
We choose [PERSON]'s algorithm [10] as the baseline of our work since it is the pioneer work and has the most representative framework in patch-based inpainting methods. In this section, we first briefly introduce how it works, and then give some analysis about its shortcomings and the improvements in other related works. For the convenience of expression, we define some notations first. As shown in Figure 1, \(I\) represents the entire incomplete image, the missing area (target region) is represented by \(\Omega\), \(\Phi\) is the known area (source region) and is defined as \(\Phi=I-\Omega\). \(\delta\Omega\) is 1-pixel-wide outer boundary of \(\Omega\) (\(\delta\Omega\subset\Phi\)), which is called the filling front, other symbols will be introduced later. The central idea of [PERSON]'s algorithm is that in each iteration, find the point with the highest priority on the filling front, and establish a target patch centered at the point, then globally search for the best sample patch; finally, the best sample patch is copied to the target patch to fill its unknown part. Repeat the above steps iteratively until the missing area is completely filled. Specifically, the algorithm consists of the following three steps:  
1. Calculate the priorities along the filling front  
In order to determine the filling order, the priorities need to be computed for all pixels along the filling front \(\delta\Omega\). Given a pixel \(p\) (\(p\in\delta\Omega\)), the priority \(P(p)\) is defined as follows:  
\[P(p)=C(p)D(p)\ \forall p\in\delta\Omega, \tag{1}\]  
where \(C(p)\) is the confidence term and \(D(p)\) is the data term, they are defined as follows:  
\[C(p)=\frac{\sum_{q\in\
abla_{p}\cap\Phi}C(q)}{\left|\
abla_{p}\right|}, \tag{2}\]  
\[D(p)=\frac{\left|\
abla I_{p}^{\perp}\cdot n_{p}\right|}{255}, \tag{3}\]  
Figure 1: Notation diagram for [PERSON]’s algorithm. where \(\Psi_{p}\) is a \(9\times 9\) patch centered at \(p\), and \(\left|\Psi_{p}\right|\) is the area of \(\Psi_{p}\),\(\
abla l_{p}\) represents the gradient at \(p\) and \(\bot\) is the orthogonal operator, so \(\
abla l_{p}^{\bot}\) denotes the isophote vector. \(n_{p}\) is a unit vector orthogonal to the filling front \(\delta\Omega\) at the point \(p\) (see Figure 1). It can be seen that \(C(p)\) represents the amount of known information contained in patch, while \(D(p)\) shows how strong a linear structure contained in \(\Psi_{p}\). The priority model encourages those areas with more known pixels and strong linear structures to be filled first. The initial value of \(C(p)\) is set to \(C(p)=1\) (\(\forall p\in\Phi\)), \(C(p)=0\) (\(\forall p\in\Omega\)). 2. Search for the best sample patch to fill one target patch  
After calculating the priorities of all pixels on the filling front \(\delta\Omega\), find the pixel \(\hat{p}\) with the highest priority, establish a target patch \(\Psi_{\hat{p}}\) centered at \(\hat{p}\), use a sample patch \(\Psi_{q}\) of the same size as \(\Psi_{\hat{p}}\) to traverse the entire source region \(\Phi\) to search the best sample patch \(\Psi_{\hat{q}}\) that is most similar to \(\Psi_{\hat{q}}\). The similarity metric is the sum of squared difference (SSD) between the known pixels in \(\Psi_{\hat{p}}\) and corresponding pixels in \(\Psi_{\hat{q}}\). The best sample patch \(\Psi_{\hat{q}}\) satisfies the following equation:  
\[\Psi_{\hat{q}}=\underset{\Psi_{q}}{argmin}\text{SSD}(\Psi_{\hat{p}},\Psi_{q}), \tag{4}\]  
then the \(\Psi_{\hat{q}}\) is copied to the unknown part of the \(\Psi_{\hat{p}}\) so that one target patch is filled. 3. Update information  
After \(\Psi_{\hat{p}}\) is filled, the update rule of confidence term for new pixels \(p^{\prime}\) in \(\Psi_{\hat{p}}\) is as follows:  
\[C(p^{\prime})=C(\hat{p})\ \forall p^{\prime}\in\Psi_{\hat{p}}\cap\Omega, \tag{5}\]  
the data term of \(p^{\prime}\) is directly copied from its source pixel. Finally, update the source region \(\Phi\), the missing region \(\Omega\), and the filling front \(\delta\Omega\). So far, a single iteration is finished.