Image Restoration Based on Hybrid Ant Colony Algorithm

Headnote

Abstract

Image restoration is the process to eliminate or reduce the image quality degradation in the digital image formation, transmission and recording and its purpose is to process the observed degraded image to make the restored result approximate the un-degraded original image. This paper, based on the basic ant colony algorithm and integrating with the genetic algorithm, proposes an image restoration processing method based on hybrid ant colony algorithm. This method transforms the optimal population information of genetic algorithm into the original pheromone concentration matrix of ant colony algorithm and uses it to compute the parameters of degradation function so as to get a precise estimate of the original image. By analyzing and comparing the restoration results, the method of this paper can not only overcome the influence of noises, but it can also make the image smoother with no fringe effects in the edges and excellent visual effects, verifying its practicability.

Keywords: Image Restoration, Ant Colony Algorithm, Genetic Algorithm

Copyright © 2015 Universitas Ahmad Dahlan. All rights reserved.

(ProQuest: ... denotes formulae omitted.)

1. Introduction

Image restoration is to research how to restore the degraded image into real image, or to research how to invert the information obtained into the information related to the real objective [1]. Certain degree of degradation and distortion are inevitable in the formation, transmission, storage, recording and display of the image. Since image quality degradation may be caused in every link of the formation of digital image, in many cases, the image needs to be restored in order to get high-quality digital image [2].

In the past decades, domestic and foreign scholars have made extensive and in-depth research in image restoration technology. Many one-dimensional signal processing and estimation theories, including inverse filtering, minimum mean error estimation and Bayesian estimation, have been used in the field of image restoration, thus forming numerous restoration algorithms. In terms of certain specific restoration problems, the scholars usually integrate many ideas and methods [3]. With the continuous development of signal processing theories, many new processing ideas and restoration methods keep emerging. In drastic contrast with the typical mathematical programming principles, some bionic intelligent optimization algorithms such as ant colony algorithm, genetic algorithm, artificial neural network technology, artificial immune algorithm and swarm intelligence algorithm, have been raised and studied by simulating the natural eco-system to seek the complicated optimization problems. These algorithms have greatly enriched modern optimization technology and provided feasible solutions to those optimization problems which are difficult to be handled by traditional optimization technology. Ant colony algorithm is a heuristic bionic evolutionary system based on population. By adopting distributed plus-feedback parallelization, this algorithm is easy to combine with other methods and it also has strong robustness, however, this algorithm requires long search time and it is easy to result in pre-mature and stagnation behaviors, slowing its convergence rate. On the other hand, genetic algorithm is a randomized adaptive search algorithm by referring to the natural selection and natural genetic mechanism and it can compute the non-linear multi-dimensional data space in a quick and effective manner. Therefore, the integration of these two techniques or algorithms can eliminate their own shortcomings and setbacks and utilize their own advantages in the image restoration [4, 5].

This paper firstly summarizes the theory of image restoration systematically and analyzes the basic principle of ant colony algorithm. Then, it focuses on the research of the hybrid method of ant colony algorithm and genetic algorithm. Finally, it compares the method of this paper with other methods and verifies its practicability through the experimental simulation and analysis of the image restoration.

2. Basic Principle of Image Restoration

Subject to the influence of such factors as optical diffraction imaging, turbulent disturbance, relative motion of imaging objectives, non-ideal characteristics of imaging apparatus, limited transmission medium band, man-made definition and requirements and random environmental noises, the image quality degrades at different degrees in the image formation, transmission and recording [6]. The typical degradations include image blurring, distortion and noises. This process is called image degradation, the key to image restoration is to know the process of image degradation, namely to know the image degradation model, and to seek the original (clear) image by adopting the inverse process on the basis of the model. Since the image usually comes with noises, the noises not only degrade the image quality, but also affect the image restoration effect, therefore, image de-noising is also a research focus of this paper [7].

In the image restoration, it is usually assumed that the image degradation is formed by the image blurring caused by point spread function (PSF) and the noise pollution and its mathematical model is:

... (1)

In this formula, v,g,l are the original image, the PSF and the addictive noises respectively and * is the convolution operator [8]. The purpose of image restoration is to obtain a precise estimation of the original image v from the degraded image f c .

For the above, it can be known that image restoration is an "inverse problem" in the mathematical problems and one important property of the inverse problems is their ill-condition. Image restoration, in accordance with the degradation reasons, analyzes the environmental factors that induce image degradation, builds the corresponding mathematical model and restores the image according to the inverse process of image degradation. Due to noises, the restoration result of the image may deviate from the original image [9].

3. Basic Principle of Ant Colony Algorithm

Ant colony algorithm searches the optimal solutions to the problems adaptively by simulating the ants in the biological world to search the shortest path from their nest to the food sources without any visible substances. The mechanism of ant colony algorithm is: when an ant is searching the food sources, it will release the unique pheromone, making the other ants within a certain distance range can perceive and affect their behaviors. When more and more ants walk a certain path, more and more pheromone will be left in this path, thus, increasing the pheromone intensity and the probability for other ants to choose this path, which will also further increase the pheromone intensity [10].

Here, this paper will briefly introduce the basic ant colony algorithm to be used in travelling salesman problem (TSP) with the TSP in n cities as example. The TSP in n cities in the ant colony algorithm model is to find the shortest path back to the starting point after searching n cities once [11].

Assume that there are n cities and m ants, dij (i,j= 1,2,L,n) is the distance between the cities of i, j and tij (t ) is the pheromone intensity in the paths between the cities of i, j at time t . When Ant k proceeds, its path is determined by the residue pheromone intensities in every path and pikj (t) is the probability for Ant k to move from City i to City j at time t , then [12]:

... (2)

Jk(i)(i=1,2,L,n) tabuk is the city set Ant k may step on next and List tabuk is the Tabu List of Ant k . When n cities have been listed into the tabuk , Ant k has travelled through all the cities and it has finished one traverse after going back to the starting point, then every path Ant k has passed is a feasible solution to this TSP . hi is the heuristic factor, indicating the expectation for Ant k to move from City i to City j , which is usually the reciprocal of dij , a, b are the relatively important procedures of pheromone and heuristic factor in the equation respectively, when all the ants have finished one traverse, global update will be conducted in the pheromone in every path according to Formula (3):

... (3)

In this formula, r (0prp1) is the volatilization coefficient, 1-r is the durability coefficient, Dtij is the pheromone increment after this iteration and Dtik is the residual pheromone of the kth Ant in this iteration. According to different pheromone update strategies, the schematic of ant colony algorithm is indicated in Figure 1.

From the above, it can be seen that ant colony algorithm has such features of parallelism, positive feedback and strong global minimum searching capacity. The ants will select the path according to its pheromone concentration and they will choose the path with high concentration. When there are more and more ants passing a path, the residual pheromone concentration of this path will increase gradually and the probability for the ants to choose this path also increases, suggesting the positive feedback of information. In the meanwhile, with the increase of time, the pheromone intensity will decrease gradually [13, 14].

4. Main Procedures of Image Restoration Based on Hybrid Ant Colony Algorithm

Set the size of an image as L= M' N, M and N are the width and height of the image, the grayscale is K , the chromosome is represented by L two-dimensional array, every element of which corresponds to a gene, use integer coding, namely the real value of grayscale to represent a gene.

In the experiment, limite the image as 256-color two-dimensional grayscale image and code the chromosome as the two-dimensional matrix with the grayscale of every pixel as the element. For example, if the image size is M ' N , then the genic value of the chromosome ... is the grayscale value in the ith row and jth column in the image. Since the grayscale value is the integer within [0,255], the algorithm of this paper adopts integer coding to perform crossover and mutation operations.

The fitness function of every individual (chromosome) is:

... (4)

In this formula, fî is the image represented by Individual i , g is the degraded image to be observed, h is the degradation process and * is convolution.

Therefore, the super-resolution restoration of the image has become the optimization problem of this algorithm.

The ant colony algorithm fails to find an optimal selection of the parameter in advance, making it fail to achieve the optimal performance of any problems. Generally, after analyzing the specific problems, ant colony algorithm will continue to adjust the parameters in the experience, hoping to get the optimal solution. Moreover, the hybrid algorithm of ant colony algorithm and genetic algorithm can further improve the computation efficiency. First, preprocess the image and then take the image as the initial population and perform combined operation of ant colony algorithm and genetic algorithm. Its computation idea is as follows:

(1) Determine the initial parameters of the genetic algorithm and ant colony algorithm and initialize the feasible population.

(2) Operate the genetic algorithm and seek the evolutionary feasible solutions.

Compute the individual fitness in the population, select the genic value in the chromosome according to the fitness of the individual, perform crossover and mutation operations on the genic value in the chromosome, calculate the individual status in the newgeneration population, record the current evolutionary population and evaluate the current optimal individual.

(3) Transform the optimal population information of the genetic algorithm into the initial pheromone concentration matrix of the ant colony algorithm.

Empty the Tabu list which stores the accessed nodes, set the node list which have been accessed by the ants as all sets, determine the starting point of the ants, update the nodes which are allowed to be accessed, the Tabu list and the unaccessed nodes, select the next node to be accessed according to the status transfer probability formula, after the transfer node, update the nodes which are allowed to be accessed, the Tabu list and the unaccessed nodes and judge whether the ants have completed the traverse.

(4) Select the pheromone update mechanism, update the pheromone concentration of every node, evaluate the current paths, update the pheromone concentration of every path, preserve the optimal path the ant search, compare all the feasible paths and output the optimal path.

The flowchart of the image restoration algorithm based on hybrid ant colony algorithm is as follows Figure 2 [15, 16]:

5. Experimental Simulation and Analysis

In order to prove the effectiveness of the algorithm of this paper, we have tested it with binary image. In the restoration, we simulate the operations of hybrid ant colony algorithm. First, we experiment on the binary image and the blur operators use Gaussian blur operators of 10*10. Use three binary images, therefore, all the values are 1 or 0. As indicated in Figure (3), (a), (c) and (e) are three different degree of degraded images, while (b), (d) and (f) are the restored images by the algorithm of this paper.

It is clear from the experimental result that this algorithm makes the restored images mother with no fringe effects and excellent visual effects, improves the subjective effects to a certain extent; reduces the ringing phenomenom near the image edges, makes the edges sharper and the outline clearer and reduces the blurriness of the local areas. It suggests that the post-processing algorithm in this paper can improve the geometry regularity of the edges and texture of the restored image and enhances subjective and objective quality of the restored image.

6. Conclusion

Having wide application fields, image restoration technology has become one of the research hot spots in the image field at home and abroad. This paper has integrated the ant colony algorithm and genetic algorithm and applied to the image restoration processing. This hybrid algorithm can search the solutions in many global points simultaneously and it has parallelism, positive feedback mechanism and strong universality. The experiment result has shown that the method of this paper has better effect in restoring the image resolution and quality.

Sidebar

Received August 23, 2015; Revised October 28, 2015; Accepted November 12, 2015

References

References

[1] Pablo Ruiz, Hiram Madero-Orozco, Javier Mateos, Osslan Osiris Vergara-Villegas, Rafael Molina, Aggelos K. Katsaggelos. Combining Poisson Singular Integral and Total Variation Prior Models in Image Restoration. Signal Processing. 2014; 103(10): 296-308.

[2] Stanley J Reeves. Image Restoration: Fundamentals of Image Restoration. Academic Press Library in Signal Processing. 2014; 4: 165-192.

[3] Moez Kallel, Rajae Aboulaich, Abderrahmane Habbal, Maher Moakher. A Nash-game Approach to Joint Image Restoration and Segmentation. Applied Mathematical Modelling. 2014; 38(11): 30383053.

[4] Richard Frans, Yoyong Arfiadi. Sizing, Shape, and Topology Optimizations of Roof Trusses Using Hybrid Genetic Algorithms. Procedia Engineering. 2014; 95: 185-195.

[5] Umera Farooq, Muhummad Tariq Siddique. A Comparative Study on User Interfaces of Interactive Genetic Algorithm. Procedia Computer Science. 2014; 32: 45-52.

[6] Zhai Xueming, Zhang Dongya, Dewen Wang. Feature Extraction and Classification of Electric Power Equipment Images Based on Corner Invariant Moments. TELKOMNIKA Indonesian Journal of Electrical Engineering. 2012; 10(5): 1051-1056.

[7] Renbo Luo, Wenzhi Liao, Youguo Pi. Discriminative Supervised Neighborhood Preserving Embedding Feature Extraction for Hyper spectral image Classification. TELKOMNIKA Indonesian Journal of Electrical Engineering. 2014; 12(6): 4200-4205.

[8] A Bouhamidi, R Enkhbat, K Jbilou. Conditional Gradient Tikhonov Method for A Convex Optimization Problem in Image Restoration. Journal of Computational and Applied Mathematics. 2014; 255(1): 580-592.

[9] Xiao-Guang Lv, Yong-Zhong Song, Shun-Xu Wang, Jiang Le. Image Restoration with A High-order Total Variation Minimization Method. Applied Mathematical Modelling. 2013; 37(16): 8210-8224.

[10] Miroslaw Tomera. Ant Colony Optimization Algorithm Applied to Ship Steering Control. Procedia Computer Science. 2014; 35: 83-92.

[11] Tianjun Liao, Thomas Stützle, Marco A. Montes de Oca, Marco Dorigo. A Unified Ant Colony Optimization Algorithm for Continuous Optimization. European Journal of Operational Research. 2014; 234(3): 597-609.

[12] RM Rizk-Allah, Elsayed M Zaki, Ahmed Ahmed El-Sawy. Hybridizing Ant Colony Optimization with Firefly Algorithm for Unconstrained Optimization Problems. Applied Mathematics and Computation. 2013; 224(1): 473-483.

[13] Pourya Hoseini, Mahrokh G. Shayesteh. Efficient Contrast Enhancement of Images Using Hybrid Ant Colony Optimisation, Genetic Algorithm, and Simulated Annealing. Digital Signal Processing. 2013; 23(3): 879-893.

[14] M Verdaguer, N Clara, O Gutiérrez, M Poch. Application of Ant-Colony-Optimization Algorithm for Improved Management of First Flush Effects in Urban Wastewater Systems. Science of the Total Environment. 2014; 485(1): 143-152.

[15] Ali Roozbeh Nia, Mohammad Hemmati Far, Seyed Taghi Akhavan Niaki. A Fuzzy Vendor Managed Inventory of Multi-Item Economic Order Quantity Model under Shortage: An Ant Colony Optimization Algorithm. International Journal of Production Economics. 2014; 155(9): 259-271.

[16] Rachid Hedjam, Mohamed Cheriet. Historical Document Image Restoration Using Multispectral Imaging System. Pattern Recognition. 2013; 46(8): 2297-2312.