基于改进的Criminisi算法的快速图像恢复方法.pdf-资料库

A Fast Image Restoration Method Based on an Improved Criminisi Algorithm Yue Chi1, Ning He2*, Qi Zhang1 1 Beijing Key Laboratory of Information Services Engineering, Beijing Union University, Beijing 100101, China. 2 College of Information Technology, Beijing Union University, Beijing 100101, China. * Corresponding author. Tel.: +86-138-1115-6835; email: xxthening@buu.edu.cn Manuscript submitted April 18, 2016; accepted July 29, 2016. doi: 10.17706/jcp.12.6.591-601 Abstract: This paper proposes an improved Criminisi image restoration algorithm that produces better repairs and reduces the computational time. First, we improved the priority calculation and included a step that transforms the original confidence term into an index to achieve a more precise repair. Second, in large damaged areas of an image, we use a local searching method to find the optimal matching block to speed up the repair process. Our experimental results show that the improved method significantly increased the speed of the method, effectively retained image structures, and produced better visual effects. Key words: Texture synthesis, image restoration, priority, local matching. 1. Introduction Image restoration refers to reconstructing damaged images or removing excess. Bertalmio [1] first proposed that image restoration can be reduced to a mathematical expression, which can then be automatically solved using a computer. Image restoration has become a major research area in computer graphics and computer vision. It has significant applications such as repairing cultural relics, film and television post-production special effects, virtual reality, and removing unwanted objects. There are currently two types of classic image repair techniques. The first uses structural rehabilitation methods such as the BSCB model (M. Bertalmio-G. Sapiro-V. Caselles-C. Ballester, BSCB) [2], TV model (Total Variation, TV) [3], and the CDD model (Curvature Driven Diffusion, CDD) [4]. TV models repair textural synthesis, and include the Criminisi model. Structural rehabilitation methods require large numbers of calculations, are time consuming, and result in more obvious blurring when considering large areas. Thus, they are more suitable for problems such as small scratches and stains [5]-[8]. Textural synthesis repair methods use pixel block unit feature extraction methods within a known area and select the best matching block. The synthesis is applied to the damaged area and is more suitable for large areas [9]. In 2003, Criminisi et al. [10] proposed an image restoration method based on texture. The largest restoration priority is given to a pixel block with a defect in the border of the source area. This method searches for a block that is most similar to the current pixel block, and then uses it to replace the current pixel block and complete the repair of the damaged area. This algorithm is based on block texture units but not pixel units, so the repair is more time consuming. The algorithm can satisfactorily repair large damaged areas, but the priority calculation and deficiencies in the matching block selection process can have a negative impact on the repair. Journal of Computers591Volume 12, Number 6, November 2017

Many researchers have attempted to solve these disadvantages of the Criminisi algorithm. Bing et al. [11] increased the border priorities to improve the method, and selected different parameters for different types of images. These changes did improve the repair to some extent, but increased blurring. Wang et al. [12] proposed a robust exemplar-based image repair method. Their model used a regularisation factor to adjust the repair block priority function. They considered the SSD (sum of squared differences) of the modified values and the NCC (normalised cross correlation) to search for the best matching block. This method produced better repairs, but involves complicated calculations and is time consuming. Wong et al. [13] proposed determining the matching blocks based on the varied degree of similarity between the block and the block to be repaired. This algorithm can achieve an excellent repair, but it is time consuming and is too dependent on the similarity of the repair block and sample blocks. In the same year, Lei et al. [14] proposed a fast image restoration algorithm based on an adaptive template and the Criminisi algorithm. It first considers the repair point gradients with respect to neighbouring pixels to effectively estimate the point to be repaired. When considering the direction of the illumination line, the illumination characteristics along the line to be repaired adaptively determine the size of the template. The algorithm performs well with respect to edge details and smooth regions. For large areas, the repair will always be a discontinuity. Zhou et al. [15] analysed the information structure that must be repaired with respect to the intensity of the image block. Their improved algorithm can perfectly repair structural edges. These studies were all based on the Criminisi algorithm and focused on repairing textural information. In this paper, we propose an improved Criminisi priority calculation algorithm, which precisely restores the confidence and image data using a joint decision image sequence. This method is quicker than existing techniques, because it uses a local search method to find the optimal matching block. Our experimental results show that the improved method significantly reduced the computational time and effectively repaired the structure of the image. 2. Criminisi Algorithm The Criminisi algorithm for texture synthesis is a classical algorithm for repairing large areas. It combines the advantages of “texture synthesis” and “image repair” techniques. The basic principle of the is an image containing a damaged area that we wish to repair, Criminisi algorithm is shown in Fig. 1. is the damaged area, is the border region, is a known source area of the image, is a unit pixel boundary, is considered the centre of , the target block. is the tangential direction of the illumination line and is the damaged boundary tangent vector method. Fig. 1. Basic schematic of the Criminisi algorithm. The Criminisi algorithm is described as follows. We first calculate the priority of the block. The priority depends on the combination of two values, the confidence and the data . corresponds to the centre pixel ( ) of the patch block ( ), which is proportional to the original image. A larger corresponds to a greater priority, which reflects that a region containing more of the original IPpPpIpn)(pC)(pD)(pCpp)(pCJournal of Computers592Volume 12, Number 6, November 2017

information should be given priority. represents the normal , which belongs to the boundary ( ) of point and the intact area of the product of the edge gradient vector, . A larger value of corresponds to a higher priority, which reflects that the boundary of the original patch has a significant relationship with the structural strength, and should be given priority. , where The priority formula of the Criminisi algorithm is is the confidence term defined as and is the data term defined as (1) . (2) Here, is the area of the template of , that is, the total number of pixel template points. is the confidence value for pixel point , which must satisfy the initial conditions . (3) is the normalised factor; =255×3 for a 24-bit RGB image. Second, we search for the best matching block and use it for the repair. The Criminisi algorithm is a global search method. It searches in undamaged areas for similar blocks to use to repair the damage. To repair sample , we use and the sum of squares difference to find the colour of the sample with the minimum sum of squares difference, which we use as the best matching module, . The repair pixels in are filled with the corresponding pixels in . This simultaneously repairs the textural information and structural characteristics. The minimum sum of squares difference (SSD) is and we calculate the colour sum of square differences using , (4) . (5) Here, I and correspond to pixel points in and , respectively. Third, we update the confidence value. Each repair block is at the edge of the area to be repaired, and the edges of the repair area constantly change after a texture block is repaired. When the highest priority target block is repaired, its confidence is updated using . We repeat these three steps until the repair is complete. The Criminisi algorithm performs well but it is time consuming, and the priority calculation and matching )(pDpnpppI)(pD)()()(pDpCpP)(pC||)()()(pIqqCpCp)(pD||)(ppnIpD||ppp)(qCqqIqqC10)(pq),(qpcdqpq),(minargqpcqqd])()()[(),(222BBGGRRqpcIIIIIIdIpqpppCpC),()(Journal of Computers593Volume 12, Number 6, November 2017

block selection are not optimal. The algorithm is based on the texture units of blocks rather than pixel units, so it takes longer to repair large damaged areas. The priority calculation used to select areas and method of finding matching blocks affect the texture of the damaged areas, which affects the accuracy. Improved priority formulas can reduce the repair time. We propose using a local range search for the best matching block to significantly improve the computational speed. 3. Improved Criminisi Algorithm 3.1. Priority Calculation The key idea of the proposed algorithm is to consider restorative effects of the structure and the texture in terms of the order of the repair blocks. The priority order must depend on two factors: the template , and structural features around the area to be repaired, i.e., the data window, i.e. the confidence items . The Criminisi algorithm’s priority formula is . During the image restoration process, the confidence gradually reduces to zero, leading to incorrect filling orders. We propose using the priority , where . According to (1), a larger undamaged proportion of the block to be repaired corresponds to a larger confidence. According to (2), if the filling point is nearer the edge, is larger and the angle between and is smaller. Then, is larger and the area will be repaired sooner. The light intensity of portions of the image’s linear structure determines the size of data items. Edges of the image are repaired first to retain the structure and reduce has more of an influence on the priority. The image edges and gradients reflect diffusion. Therefore, the image texture features. Pixels with large gradients represent a rich textured image. To increase the gradient transform (that is, increase the influence of by weakening ), we set . Then, , the confidence decreases, and the importance of the data items increases. This improves the textural details, and increases the accuracy of the repair. In our experimental results, when gradually increased from 2 the repair was more effective, the optimal results where for , and the result was inaccurate when =5. 3.2. Local Area Search for the Optimal Matching Block The original Criminisi algorithm searches the entire image to find the most similar block. But many similar blocks are in the vicinity of the target area, so a global search reduces the efficiency of the algorithm. To reduce the search space and achieve satisfactory repairs, we use a local area search. Fig. 2. Local search for matching block. Fig. 2 shows an image containing a damaged area. is the damaged area, is the border region, )(pC)(pD)()()(pDpCpP)()()(pDpCpP1ppIpIpn)(pD)(pD)(pD)(pC1||)()()(pIqqCpCp)()(pCpC3Journal of Computers594Volume 12, Number 6, November 2017

is a known source area, is a unit pixel boundary, and is the centre of (the target block). is the tangential direction of the illumination line, and is the damaged boundary tangent vector. In the Criminisi algorithm, we set the block size of the patch (red box) to a 9×9 pixel block, and search through all the matching blocks in the entire undamaged area. This is time consuming, and reduces the repair efficiency. However, the most similar blocks are typically located in the general vicinity of the block to be repaired. We determine the pixel with the highest priority, and then extend down 13 pixels (i.e., in a local 27×27 pixel block). With this in mind, the proposed method uses a local search block matching method to solve the original Criminisi algorithm and reduce the computational time. Fig. 2 shows the basic principles of the local search method. It uses the following steps. 1) The current pixel has the highest priority. Extend down 13 pixels, within the scope of a partial 27×27 pixel block to find the best matching block. 2) Search within the 27×27 pixel block using a 9×9 sample template. That is, start in the upper left corner from the first point, and using a 9×9 pixel template traverse from left to right, down one line, and continue to traverse from left to right, until you have traversed all the pixels. 3) After repairing this section of the image using the best matching block, update the boundary information and return to Step (2) until the entire image is repaired. 4. Results and Analysis We ran our experiment using a 3.4GHz processor, 8GB of memory, and MATLAB R2010b. We applied the algorithm to natural and character image restoration, and single and multitarget removal, to illustrate its adaptability and robustness. The image dimensions were 100×100, 350×262, 371×432 before applying the algorithm and the images were jpg files. After applying the algorithm, the image dimensions were 256×256, 512×512, and there were two groups. We evaluated our algorithm in terms of the computational time and the peak signal to noise ratio (PSNR), that is, , where MSE represents the difference between the original and restored image [16]-[19]. If are the original pixel values, are the repaired the pixel values, and is the number of pixels, . Although PSNR is not a standard evaluation for small-scale defect image restoration, it can reflect the effect of the repair [20]-[23]. 4.1. The Improved Algorithm Results before and after Comparison and Analysis Fig. 3 illustrates the results when repairing a manual obstruction. The image has a simple structure and minimal colours, so the results of the two algorithms are similar. Fig. 4 shows the removal of some targets from an image. The image had many targets that were distributed across regions of different colours, so this image was more difficult to repair [24]. The Criminisi algorithm’s result was not ideal; there were green pixels throughout the blue lake area. The results of the proposed algorithm were more successful. Fig. 5 contains a scratch. The results obtained by Criminisi algorithm showed an affective background repair, but there were white lines on the image due to the scratches. The proposed algorithm produced better results. PpPpIpn)255lg(102MSEPSNRiIiJNNJIMSENiii12)(Journal of Computers595Volume 12, Number 6, November 2017

Table 1 compares the run times of the algorithms. The computational time of the proposed algorithm depended on the size of the image, but was significantly less that the original algorithm. The proposed algorithm performed better in terms of the PSNR than the Criminisi algorithm (Table 2), and produced better visual improvements. (a) Original (b) Damaged (c) Criminisi (d) This paper Fig. 3. Image repair for a subjective obstruction. (a) Original (b) Damaged (c) Criminisi (d) This paper Fig. 4. Multitarget removal. (a) Original (b) Damaged (c) Criminisi (d) This paper Fig. 5. Photo restoration to remove crease. Fig. 2 Fig. 3 Fig. 4 Table 1. Comparison of Running Times Image size 100×100 350×262 371×432 3663.980 3372.670 Criminisi/s 38.531 This paper/s 3.364 36.338 30.819 Table 2. Comparison of Peak Signal to Noise Ratio This paper 30.903 23.128 32.367 Fig. 2 Fig. 3 Fig. 4 Image size 100×100 350×262 371×432 Criminisi 29.148 21.931 31.030 4.2. Experimental Results Compared to Control and Analysis To demonstrate the effectiveness of the improved algorithm, we compared it with the Criminisi algorithm, TV algorithm, and MCA algorithm [25], [26]. We considered edge restoration, regular texture restoration, checkerboard mask corrosion restoration, and striped mask corrosion restoration. We used the program running time and peak signal to noise ratio (PSNR) to measure the efficiency of the algorithm. In our control experiments, we set the TV model algorithm [27], [28] to use 500 iterations. 4.2.1. Analysis of edge and regular texture regions The edge and regular texture areas restoration experiments verified that the improved algorithm can Journal of Computers596Volume 12, Number 6, November 2017

effectively maintain object connectivity and compliance in terms of a subjective evaluation. The edges of Fig. 6–Fig. 9 show that the proposed method and the Criminisi algorithm outperformed the other algorithms. The PSNRs for the proposed method were higher and a visual evaluation shows that the repair was the most effective. The TV algorithm result is partially smoothed and has poor connectivity (Fig.6), and breaks some edges (Fig. 7) producing obvious blurring. The MCA algorithm was time consuming and did not produce optimal results. In Fig. 6, we can see that the MCA distorted the image. For the regular texture repair examples, the proposed method produced better results and more completely restored the image, while the other three methods have varying degrees of defect. Original Damaged Criminisi TV MCA This paper Fig. 6. Repairing edges (boat). Original Damaged Criminisi TV MCA This paper Fig. 7. Repairing edges (hat). Table 3. Comparison of Running Times Fig. 6 Fig. 7 Image size 256×256 256×256 Damaged size Criminisi/s 50×50 50×50 1.342 1.893 TV/s 2.414 3.089 MCA/s 2.711 3.289 This paper/s 0.928 1.034 Fig. 6 Fig. 7 Image size 256×256 256×256 Table 4. Comparison of Peak Signal to Noise Ratio (PSNR) MCA 20.848 20.819 Criminisi 21.842 22.277 TV 20.972 21.082 Damaged size 50×50 50×50 This paper 23.114 23.109 Original Damaged Criminisi TV MCA This paper Fig. 8. Repairing regular texture regions (table cloth). Original Damaged Criminisi TV MCA This paper Fig. 9. Repairing regular texture regions (brick). Table 5. Comparison of Running Timed Image size Damaged size Criminisi TV Fig. 8 Fig. 9 256×256 256×256 50×50 50×50 1.209 1.343 2.014 2.189 MCA 2.431 2.389 This paper 0.312 0.294 Journal of Computers597Volume 12, Number 6, November 2017

Table 6. Comparison of Peak Signal to Noise Ratio Fig. 8 Fig. 9 Image size 256×256 256×256 Damaged size 50×50 50×50 Criminisi 21.106 20.934 TV 19.072 19.142 MCA 18.712 18.803 This paper 22.487 22.675 4.2.2. Checkerboard and Stripe Mask Image Restoration Our checkerboard and striped mask corrosion restoration experiments verified that the improved algorithm can effectively restore the complex structure of an image in a subjective evaluation. The results for the checkerboard mask are shown in Fig. 10 and Fig. 11, and the results for the striped mask are shown in Fig. 12 and Fig. 13. The proposed algorithm produced the best results in terms of the PSNR and a visual evaluation. The checkerboard results in Fig. 10 and Fig. 11 are relatively similar, but the proposed algorithm performs subjectively better. The striped mask results in Fig. 12 and Fig. 13 show a large loss in image information, so the repairs were challenging. Our results show that the other three methods produce blurring. The eyes and mouths in the Lena and Barbara images are not clear. However, the proposed method effectively restored the image information, and the results had a high signal to noise ratio. Original Damaged Criminisi TV MCA This paper Fig. 10. Repairing an image with a checkerboard mask (Lena). Original Damaged Criminisi TV MCA This paper Fig. 11. Repairing an image with a checkerboard mask (Barbara). Table 7. Comparison of Running Time MCA/s TV/s Fig. 10 Fig. 11 Image size 512×512 512×512 Criminisi/s 3899.273 3903.142 1731.892 1756.231 2350.692 2397.811 This paper/s 50.331 51.255 Table 8. Comparison of Peak Signal to Noise Ratio Fig. 10 Fig. 11 Image size 512×512 512×512 Criminisi 24.831 24.665 TV 24.095 24.243 MCA 24.355 23.536 This paper 25.844 25.682 Original Damaged Criminisi TV MCA This paper Fig. 12. Repairing an image with a striped mask (Lena). Journal of Computers598Volume 12, Number 6, November 2017

资料库

基于改进的Criminisi算法的快速图像恢复方法.pdf

相关推荐

开发技术

热门标签

最新资料