# Image Inpainting Based on Multi-Patch Match with Adaptive Size
## 3 Proposed Approach
### Evaluate the Nonuniformity  
Evaluating the nonuniformity is the dependency of the other parts in our work, including the patch size determination, subregion search and multi-patch match. Therefore, the nonuniformity  
Figure 2: The overall framework of the proposed method. Our improvements are depicted in bold.  
needs to be quantified first. Given a patch of pixels that under a certain distribution, the standard deviation in statistics can effectively characterize the nonuniformity of pixel values, also can be seen as a measure of the texture feature [20]. Our nonuniformity is exactly based on the local standard deviation. Concretely, let \(S_{p}\) denote a square window centered at point \(p\) (\(p\in\Phi\)), \(w_{s}\) is the width of \(S_{p}\) determined by the image size \(H\times W\), by default, \(w_{s}=\max(2\Big{[}\frac{\min(H,W)}{100}\Big{]}+1,3)\), where \([\cdot]\) is the rounding operator. The local standard deviation at \(p\) is obtained by computing the standard deviation of all the known pixels in \(S_{p}\):  
\[\sigma(p)=\sqrt{\frac{\sum_{q\in S_{p}\cap\Phi}\left(q-\mu\right)^{2}}{\big{|} S_{p}\cap\Phi\big{|}}}, \tag{6}\]  
where \(\sigma(p)\) is the local standard deviation at \(p\), \(\mu\) is the mean value in \(S_{p}\). Appling Equation (6) for all the pixels in source region, we obtain a map of local standard deviation \(\sigma(\Phi)\), then \(\sigma(\Phi)\) is normalized to the interval [0, 1] as the following equation:  
\[\overline{\sigma}(\Phi)=\frac{\sigma(\Phi)-\min(\sigma(\Phi))}{\max(\sigma( \Phi))-\min(\sigma(\Phi))}, \tag{7}\]  
where \(\overline{\sigma}(\Phi)\) is the normalized local standard deviation map. We find that in most cases if we directly use \(\overline{\sigma}(\Phi)\) as the descriptor of the content without post-processing, its data distribution will be very uneven: The lower part is over-crowded and less distinguishable, while the higher part is too sparse (see Figure 3b for example). In Section 3.2, we intend to evenly divide the interval [0, 1] into subintervals so that every pixel can be categorized and be treated accordingly. Intuitively, it is better to stretch the crowded data to a relatively even distribution to fit the evenly-divided subintervals. We find that the widely-used histogram equalization is a simple and effective way to achieve this purpose, without any parameter to be set manually. Therefore, we equalize the \(\overline{\sigma}(\Phi)\) to make full use of the space [0, 1]. Let \(\text{histeq}(.)\) be the operation of histogram equalization:  
\[T(\Phi)=\text{histeq}(\overline{\sigma}(\Phi)), \tag{8}\]  
where \(T\) is the value equalized from \(\overline{\sigma}\) and we define it as the nonuniformity. For instance, Figure 3c shows the nonuniformity map computed from Figure 3a.  
Figure 3: (**a**) Incomplete image Lena, the missing area is depicted in black; (**b**) map/histogram of \(\overline{\sigma}(\Phi)\) of Lena (non-equalized); (**c**) map/histogram of equalized \(\overline{\sigma}(\Phi)\) of Lena, defined as the nonuniformity \(T(\Phi)\) in our context.  
As shown in Figure 3c, each pixel \(p\) in \(\Phi\) has a certain value of nonuniformity \(T(p)\), which reflects the number of details contained in neighborhood of \(p\). Intuitively, areas with more details (such as textured regions and line structures) will obtain a higher nonuniformity, whereas flatter areas (such as the background) will get a lower nonuniformity. For unknown areas, the nonuniformity makes no sense. If the unknown areas are filled with new pixels during the filling process, the nonuniformity of the new pixels is directly updated from their source pixels.