1. INTRODUCTION
The image processing techniques have been developed in the various of areas such as remote sensing, video processing, image inpainting, medical image processing, pattern recognition, biometrics, traffic systems, image compression, information hiding [1], and printing industry [2]. Image inpainting is the process of reconstructing the damaged image and/or removing an object in an image [3], [4]. The fundamental concept of image inpainting is to fill the missing regions of an image using the surrounding information of that region. Image inpainting techniques entail many applications such as automatic text removal and/or object removal in images/films for special effects [5], deleting of blurs of dust in image, red-eye correction, inventive effect by deleting object [6], [7], remove video logos [8], old image/film restoration [9], and medical image correction (image inpainting use to complete missing or distorted information in medical images) [10]. In general, image inpainting techniques are categorized into five major types which are: (1) Partial differential equation based inpainting, (2) texture synthesis based inpainting, (3) exemplar-based inpainting, (4) semi-automatic and fast inpainting, and (5) hybrid inpainting [11], [12]. Each of these types has its own advantages and limitations and each of them recovers the damaged regions in accordance with certain requirements of expectation of the repaired image content. This paper focuses on the third type, i.e., exemplar-based image inpainting.
The exemplar-based image inpainting is one of the most important types of inpainting techniques and it has been proved to be the most effective type of inpainting [13]. Exemplar-based image inpainting mainly includes two main steps. The first step is the priority assignment, in this step, one patch from the boundary of the missing region with the highest priority must be selected using one of the priority functions and it must be filled at first. The second step involves searching for the best-matched patch based on one of the searching mechanisms. In this area of research, researchers try to improve one or both of these steps to obtain better results in terms of the quality of the reconstructed image. This paper focuses on improving the searching mechanism by taking advantage from the distance between the patch to be inpainted and the other best match patches.
The rest of the paper is organized as follows: In section 2, the literature review is presented. Section 3 illustrates the statement of the problem. Section 4 presents the proposed inpainting approach. The experimental results are shown in Section 5. Finally, our conclusions are given in Section 6.
2. LITERATURE REVIEW
Different categories of image inpainting are mentioned in the previous section. Since the contribution in this paper concerns on the exemplar-based image inpainting, therefore this section is going to review some important approaches related to exemplar-based image inpainting.
The idea of exemplar-based inpainting is first invented by Perez et al. in 2003 [14]. The core of this algorithm is an isophote driven image sampling process, isophote refers to the direction and intensity of the patch center point. Patch can be defined as a small (generally rectangular) piece/block of an image. Essentially, in image inpainting, Ψp refers to the targeted patch in which some of its pixels values are missing and Ψq refers to the best match founded patch. Moreover, one of the most important steps in image inpainting is from which patch (out of all the patches located around the border of the missing area) should the system start to inpainting; this process refers to priority function and it denotes as P(p). In Perez et al. [14], the priority function of their algorithm is defined by a production of confidence term C(p) and data term D(p).
Moreover, the confidence term represents texture information and data term represents structure information. These two parameters decide which patch has the highest priority. Furthermore, Ψp will be filled by the Ψq, only the missing part of the Ψp will replace by the Ψq. In each iteration, once the best match patch Ψq is founded, it will immediately use to fill the missing part of the targeted patch Ψp and then the next iteration will start to find the best match patch Ψq for the next targeted patch Ψp. This process continues until all the targeted patches are filled completely [14].
The extended version of the previous work was published by Perez et al. in 2004 with a more detailed description of the algorithm and extensive experiments [15].
In general, each exemplar-based image inpainting approach includes two main steps. The first one is the priority function that uses to decide from which patch, out of all the patches located around the boundary of the missing area, the algorithm should start. On the other hand, the second phase is the searching mechanism using distance technique, for example, sum of square difference that is used to select the best-matched patch based on the difference between the targeted patch Ψp and the best match patch Ψq. Therefore, all the approaches proposed in this research area are either improve the priority function, improve the way of finding differences between Ψp and Ψq, or improve both steps. In addition, the essential purpose of the competition in this research area is to improve the quality of the reconstructed image.
Wen-Huang et al. highlighted the limitation of the previous algorithm in Perez et al. [14] and Perez et al. [15] in which the defined priority function quickly drops the value of the confidence term C(p) to zero [16]. Consequently, this leads to create a problem in which the priority function P(p) is gradually depend on only structure information D(p) without making the texture information C(p) into consideration; therefore, the priority function is not able to find the highest priority patch correctly. This kind of drawback is known as the dropping effect. To overcome this drawback, Wen-Huang et. al. proposed an algorithm in which defined a regularized function Rc(p) instead of confidence term C(p) as follows:
Where ω is the regularizing factor for controlling curve smoothness and takes a value between 0 and 1. In general, in this work, ω sets to 0.7. Finally, the equation changed as:
Where 0≤α, β≤1, and α+β=1. Authors claimed that their proposed approach is improved the quality of the reconstructed image [16].
In the previously reviewed approaches, only one patch Ψq is used to reconstruct the inpainted patch Ψp. In 2008, Alexander et al. proposed a new mechanism to fill the inpainted patches using multiple samples within the image and weight their contribution according to their similarity to the neighborhood under evaluation. Using the weighted aggregation of multiple patches yields a much-improved result [17].
In 2015, Huang et al. defined a new priority function for exemplar-based image inpainting [18]. Different from the priority function defined in Perez et al. [14], Hsieh et al. [16], this proposed priority function first rely on the structure information D(p), and then used texture information C(p). In other words, this priority function works on the D(p) and C(p) separately. This approach works well for the case of the curve or cross-shaped structures. The presented results in this paper show that this approach is able to recover image geometry and texture well compared to other existing approaches [18].
A new mechanism was proposed by Liu et al., in 2018, in which the proposed algorithm added boundary-constrained similar patches to find more suitable similar patches and boundary filling instead of patch filling. To measure the similarity between boundaries, they used boundary matching distance. This type of distance measurement was applied for the boundary matching algorithm. This proposed algorithm can repair structural and texture complex images very well [19].
Awati et al., in 2018, proposed a new technique to enhance the quality of exemplar-based image inpainting [20]. This algorithm upgrades the image inpainting approaches mainly for these images that involve edges and corner information. This approach uses fractional derivative and additional curvature finding methods for finding data term in patch priority.
The proposed approach presents in this paper will modify the searching mechanism, while uses the same priority function presented in Hsieh et al. [16], more details will be given in the next section.
3. STATEMENT OF THE PROBLEM
The digital image may cause to lose some of it is regions affecting by removing unwanted objects, by image compression, by scratching image, or by image transformation through internet. Image inpainting is becoming a common tool for repairing the scratched or damaged area of an image. It entails reconstructing damaged parts and filling-in regions in which data/color information are missing.
4. PROPOSED APPROACH
This section gives the steps of the proposed approach in detail. It is assumed that the source region, target region, and the boundary denote by Φ, Ω, and δΩ, respectively. Furthermore, the target patch denotes by Ψp in which its center point is p δΩ [21]. The proposed approach consists of the following steps:
4.1. Manually Select the Target Region Ω
Selecting the target region means to select the degraded region or unwanted region to be filled using the surrounding information.
In this step, the target region is selected by marking this area using a specific color, for example, “black color,” and then the mask image is also created. Mask image is a binary image in which zero pixels indicate the target region and the ones are showing the remaining part of the image, as illustrated in Fig. 1.
Fig. 1. (a) Original image, (b) mage with target region, (c) mask image.
4.2. Target Region’s Boundary Detection dΩ
One of the most important steps of developing the inpainting algorithm is the boundary detection of the target region because the selection of the highest priority patch from the boundary of its target region can be decided. The boundary of the target region should be detected using one of the edge detection techniques such as Prewitt, Sobel, Canny, or Laplacian edge detection see Fig. 2.
Fig. 2. Boundary Detection of the Target Region using Laplacian edge detection.
4.3. Patch Priority Function
It is useful to decide which patch on the boundary of the target region must be inpainted first. After patch priority function is computed, the patch Ψp centered at the point p for all p є δΩ with the highest priority is taken, see Fig. 3. In this proposed approach, the same patch priority equation presented in Hsieh et al. [16] is performed.
Fig. 3. Select Ψp from δΩ with the highest priority.
4.4. Searching for the Most Similar Patch
Once the highest priority patch Ψp is selected on the boundary of the target region δΩ in the previous step, the most similar patch to fill the unknown pixels of the Ψp needs to be found. For this sake, the proposed approach developed an improved searching mechanism in which the entire source region Φ of the image should be searched patch by patch from the upper left corner of the image. The source region Φ consists of the whole image without the target region (I-Ω). Now for each patch from the source region that is denoted by Ψq, two different distances between Ψp and Ψqi need to be found. For the first one, the distance between the positions of each patch on the image is calculated.
ʎ is a positive number of uses to make a balance between the position’s distance and Euclidean distance. In this proposed approach ʎ is set to 10, and X_POS calculates a position distance between Ψp and Ψq on the X-axis and Y_POS for Y-axis.
For the second one, the Euclidean distance between these two patches is calculated as follows:
Where, R, G, and B represent the red, green, and blue channels of the image, respectively.
Finally, we perform the summation between these two distances value to obtain the appropriate distance value.
The above equations should repeat between Ψp and the remaining patches in the source region Ψqi. In the end, the minimum distance value is chosen as the best similar patch. This process continues until the entire target region is filled.
The following diagram illustrates the proposed searching mechanism.
Fig. 4 is illustrated our proposed searching mechanism to fill the missing pixels in the highest priority patch Ψp that is selected in section 4.3. Consequently, the algorithm searches the entire image patch by patch. These patches are denoted by Ψqi where i is a number of patches in the image that starts from one to the last patch number. After performing equations of 4, 5, and 6, the result of equation 6 needs to be checked whether it is smaller than the MIN value or not (MIN is a variable used to take the smaller distance value in each iteration that is initially set to 10) if it is smaller than the MIN variable, it means that the current patch (Ψqi) is the most similar to Ψp than the previous patch (Ψqi−1)? This process continues until the last i. Finally, we set Ψbest to the most similar patch and replace the missing pixels of Ψp using Ψbest.
Fig. 4. Block diagram of the proposed searching mechanism.
4.5. Updating Confidence Value
After the patch Ψp has been filled as explained in the previous step, the region of Ψp in the confidence C(p) on the mask image is updated as follow:
C(p)=C(p’) where C(p’) is the region of the Ψp after it is filled.
Fig. 5 shows updating confidence value at the first iteration.
Fig. 5. (a) Mask image before the confidence value is updated, (b) mask image after the confidence value is updated at the first iteration.
Fig. 6 shows the block diagram of the whole steps of the proposed approach.
Fig. 6. Block diagram of the proposed approach.
5. RESULTS AND COMPARISON
To evaluate the performance of the proposed approach, experiments are conducted extensively using different natural and complex images of different file formats such as. JPG and.PNG. These images are common images that are usually used in image inpainting research area and they are from a dataset [22]. Fig. 7 shows some images which are used in the experiments: The second column includes original images and the third column contains images which marked the target region in black color.
Fig. 7. Example of tested images, (a) original images, (b) original images with target region to be inpainted.
The proposed approach is compared with algorithms in Perez et al. [14] and Huang et al. [18]. Two main kinds of quality assessment techniques are performed (objective and subjective). Fig. 8 illustrates the results of reconstructing the target region of the images in Fig. 7 using each of the proposed approaches as well as approaches in Perez et al. [14] and Huang et al. [18]. The reconstructed of the missing region is highlighted in a red circle.
Fig. 8. Results of (a) proposed approach, (b) approach in Perez et al. [14], (c) approach in Huang et al. [18].
In Fig. 8, some of them resulted images cannot be seen subjectively, i.e., visually. The peak signal-to-noise ratio (PSNR) is used as a quality assessment objectively to measure the quality of the reconstructed images. Results demonstrate that the proposed approach obtained the highest PSNR value compared to other tested approaches, Table 1.
TABLE 1 Peak signal-to-noise ratio values
Based on the results present in Table 1, one can see that sometimes the result of Perez et al. [14] is better than the result of Huang et al. [18] and vice versa, while for the proposed approach, for all tested images, the results are better than both Perez et al. [14] and Huang et al. [18]. This is because each of the tested algorithms has limitations for filling different regions such as shapes, edges, textures, and different backgrounds, while the proposed approach exceeds this limitation.
The previous results show how to fill the missing area and how to evaluate the result objectively using PSNR. Now another test is conducted by removing an object from some tested images that are evaluated subjectively, i.e., visually. Fig. 9 shows some images with selecting unwanted objects to be removed by black color.
Fig. 9. (a) Original images (b) selecting unwanted objects.
Fig. 10 presents the results of the reconstructed images in
Fig. 10. Reconstructed images.
6. CONCLUSION
This paper is concerned with developing a new exemplar-based image inpainting algorithm by improving the searching mechanism to find the best similar patch. The proposed algorithm is performed two steps of distances to select the best-matched patch. The first step finds the distance between the position of the selected patches and the patch which needs to be filled. On the other hand, the second step calculates the Euclidean distance between them. Finally, the summation of these two distances is calculated to find the most similar patch. Experimental results demonstrate that the proposed approach is achieved a higher quality in terms of both objectives (i.e. PSNR) and subjective (i.e., visually) compared to other existing approaches.