Memristor-Based Genetic Algorithm for lmage Restoration

Yong-Bin Yu | Chen Zhou | Quan-Xin Deng | Yuan-Jing-Yang Zhong | Man Cheng | Zheng-Fei Kang

Abstract—This paper explores a way of deploying the classical algorithm named genetic algorithm (GA) with the memristor.The memristor is a type of circuit device with both characteristics of storage and computing, which provides the similarity between electronic devices and biological components, such as neurons, and the structure of the memristor-based array is similar to that of chromosomes in genetics.Besides, it provides the similarity to the image gray-value matrix that can be applied to image restoration with GA.Thus, memristor-based GA is proposed and the experiment about image restoration using memristor-based GA is carried out in this paper.And parameters,such as the size of initial population and the number of iterations, are also set different values in the experiment,which demonstrates the feasibility of implementing GA with memristors.

1.lntroduction

Memristor, the abbreviation name of the memory resistor, was first proposed by Chua in 1971[1].From the point of view of the circuit theory, there should also be a circuit element to represent the relationship between the flux-linkage and current, then, the memristor was proposed.However, limited by the production technology at that time, it was not born until 2008 when the HP lab made the first memristor[2], arousing the research upsurge of memristors globally.Due to the special switching mechanism, memory, continuous input and output, and nano scale, memristors have great potential applications.For example, the memristorcomplementary metal-oxide-semiconductor transistor (memristor-CMOS) hybrid circuits could be used to realize neural networks[3].The memristor is also well-behaved in signal processing[4]and cyber-security[5].Recently, its value in image processing has been found with the application in image processing.The memristor bridge-based lowpass filter is designed along with an adaptive Gaussian filter, which is presented for denosing images[6]and has been applied to edge detection[7].Besides, it has good practical value in hand gesture recognition[8],[9].

The genetic algorithm (GA) is a method that Holland[10]draws lessons from the basic principles of genetics to simulate natural evolution.It is used in designing the artificial adaptive system.A computational model is proposed based on natural selection that simulates Darwin’s theory of biological evolution.The basic idea of GA is to select individuals from the initial population, adopt the natural law of “survival of the fittest”, and then produce a new generation of population through hybridization and mutation, so as to evolve generation by generation until the goal is met.Nowadays, it works well in solving complex nonlinear combinatorial optimization problems, such as the traveling salesman problem[11]and image processing[12].

In recent years, image restoration has become important in many fields, such as medical imaging and graphic printing.Digital images are often corrupted by degradation[13].The reason of image blur is complicated, the restoration cannot be processed by the regular linear function.So, it is proper to use GA to restore the image.

Because of the advantage of memristors in storage, the memristor-based array is proposed, which also can be called the memristive network.This array is capable of solving more complex problems compared with the single memristor unit.Besides, it has the similarity to the image gray-value matrix, and its structure is similar to chromosomes and genes.In the memristor-based array, every pixel of the image has a corresponding memristor unit to store its value, making it possible to realize storage for binary, grayscale, and color images.So our goals are to verify the feasibility of deploying GA with memristors, explore mapping rules between GA and the memristor-based array, and deploy GA with memristors through the mapping rules in image restoration.

2.Computing Model

2.1.GA

GA can be divided into three parts.1) The first part is initialization.Engineering problems are mapped into population evolution problems in the biological world.Coding and generating population and feasible solutions of problems can be defined by chromosomes and genes.2) The second part is to design the fitness function, that is, choosing the appropriate standard to quantify the individual’s adaptation to the living environment.Fitness is an important standard to evaluate the individual and the basis of other operations.Because the requirement of the fitness function is not particularly strict and it is not forced to be differentiable,derivable, and so on, GA is suitable to deal with nonlinear problems.3) The third part is the core operations of GA, including selection, crossover, and mutation.Selection is to select individuals with good characters in the current population, which is the basis of crossover and mutation operations.Crossover is the exchange of the segment of parents’ genes, that is, the process of reproduction in biology, which is an important part of GA.And the genes of parents can be continued because of crossover.Mutation is the idea of mutation in biology,sometimes, gene mutation occurs during the process that offspring inherits the parent gene, and mutation is beneficial for the population to jump out of the local optimal solution.The specific process of GA is showed inFig.1.

2.2.Memristor-Based Array

Limited by the computing ability of a single memristor, the memristor-based array was designed for more complex problems.The memristor-based array has the structure similarity to a two-dimensional matrix, which is composed of multiple memristors.Its structure is shown inFig.2.Each memristor can be added to this array through two connecting wires, and the deletion of the memristor only needs to disconnect the two connecting wires between the memristor and array[14].

Fig.1.Process of GA.

Fig.2.Structure of memristor-based array.

There have been applications of using the memristive network to implement other swarm intelligence algorithms.For example, Pershin and Ventra[15]compared the memory characteristics of memristors with the pheromones left by ants on the path, proposed a mapping relationship, and used memristors to deploy the ant colony optimization, which inspires us to explore memristor-based GA.

2.3.Memristor-Based GA

To solve optimization problems, the analogy and mapping between GA and the memristor array is then conducted.The structure of the memristor-based array is similar to that of the chromosome, so a single memristor in the array can be abstracted into a gene unit.Then the operation in GA is mapped to the change of the resistance value of the memristor in the memristor-based array.The mapping relationship is shown inTable 1.The memristor is the basic unit of the memristor network and the gene is the basic unit of the chromosome; the sum of information of each pixel constitutes an image, so the memristor is mapped to genes in GA, which corresponds to the gray value information of a pixel in an image.Multiple genes form a chromosome or individual, so the chromosome corresponds to a set of memristors, that is, a memristor network and a set of gray value information of pixels in the memristor network.

Table 1: Mapping rules among nature, GA, memristive network, and image restoration

3.lmage Restoration Based on Memristor-Based GA

This section will introduce the theory of image restoration, detailed design of image restoration based on GA, including the way of coding and generating initial population, the selection of the fitness function, and the selection of the basic operation of GA.

3.1.Theory of lmage Restoration

In the process of image generation, transportation, and processing, the phenomenon of image blur caused by man-made and natural factors, such as the camera jitter, inappropriate light, and haze, is called image degradation.Except image blur, the degradation is often manifested as distortion, additional noise, etc.,resulting in the decline in image quality.In the image degradation model, image degradation is modeled by using the degradation function and adding the external noise.The model is showed inFig.3,xandydenote coordinates in the spatial domain,f(x,y)represents the original clear image in the spatial domain,h(x,y) is the degradation function,n(x,y)represents the noise, andg(x,y) denotes the degraded image.

The mathematical expression of the degenerate model can be expressed as[16]

Fig.3.Image degradation model.

where * denotes the convolution operation.After the Fourier transform, (1) in the frequency domain is

It can be inferred that the restored images in the frequency domain is

G(u,v) is defined in (2), and then substituted into (3):

The restored image is obtained by using the inverse Fourier transform:

wheref′(x,y) denotes the restored image.So, it is possible to restore a blurred image without nois e.

Before the start of GA, the significance and design of image segmentation will be introduced.During the process of image restoration, the number of pixel in a picture is very big, so the computing burden will be heavy.Suppose that the size of the image to be restored is 100×30 pixels, and the image is not divided into blocks.At this time, an image is an individual has 100×30 = 3000 genes, and the range of each gene is an integer of 0 to 255.For one graph, there are 2563000different feasible solutions, which is a very big number.Usually, the size of the initial population is about 20 to 120.In this case, the size of the randomly generated initial population is only about 100/2563000, and the result of this ratio is close to zero.Therefore, the probability of getting individuals with good characters is very small, that is, the fitness of individuals is very low, and the use of improved selection, crossover, and mutation algorithms cannot get good results afterwards.And the speed of convergence is very slow, because the individual does not perform well from the beginning.Furthermore, in order to increase the probability of producing good initial individuals, we have to choose to increase the size of the initial population.However, increasing the size of the initial population means that more space is needed to store individual information, and each additional individual of the initial population needs more 3000 memories to store individual information, so the space cost is very huge.The most critical problem is that even if the size of the initial population is increased to thousands, tens of thousands, or even hundreds of thousands, it is still a very small number compared with 2563000.Moreover,when the size of the picture increases slightly, this number will grow exponentially, and the increasing population size will greatly increase the amount of memristors needed and the space cost.The effect on improving the efficiency of the algorithm is negligible.So, above all, we put forward to process the image by blocks.

3.2.Divide lmage into Small Blocks

In this situation, the size of the image block is set as 3×3 pixels, and the image block is moved according to the rules from left to right and from top to bottom.The 3×3-image block first traverses from left to right,moves one pixel down after traversing a whole line, and continues to traverse a whole row until all pixels have been traversed.

Thus, an individual is not a whole image, but the size of a block, and its structure is like that a chromosome has nine genes.To simplify the operation, the data matrix of a 3×3 block will be converted into a matrix of 1×9.Assuming that the number of the initial population is 20, then the size of the initial population is the two-dimensional matrix of 20×9.Besides, each individual also needs a memory to store the value of fitness, so the size of the matrix is extended to 20×10.This matrix is named as the operation matrix, in which the first nine genes in each row form an individual.The number of rows represents the size of the population,and the last one stores the individual fitness value.So two memristor-based arrays are required, one is to store the blurred image (called MNblur instead), and another is to store the restored image (called MNres instead).In addition, an operation-matrix memristor-based array is also needed, GA operations all happen in the operation-matrix memristor-based array.

3.3.Select GA Operation for lmage Restoration

3.3.1.Coding and Initializing Population

Two-dimensional integer coding is adopted by this paper, because the picture can be seen as a twodimensional matrix storing pixel information.The gray value of the image is expressed as the genetic value directly, which not only retains the similarity between the data and the image, but also avoids the complex coding and decoding operations.It is helpful to improve the operation speed, and then stochastically generate initial population.

3.3.2.Fitness Function

The fitness function is a function to evaluate the fitness of an individual, which is generally required to be non-negative.The purpose of image restoration is to obtain the best original image, but the restoration quality of an image can only be known by comparing with the original image and restored image, especially, the original image is unknown.However, we discussed the image degradation model in subsection 3.1, and the degraded imageg(x,y) is degraded from the original imagef(x,y). If the restored imagef′(x,y) can also produce another degraded imageg′(x,y) after the same degradation function, then bothg(x,y) andg′(x,y)are known and can be compared.If the finalg′(x,y) is closer tog(x,y),f′(x,y) will be more similar tof(x,y),so the fitness function is designed by[8]

3.3.3.Selection Function

The selection function in this research adopts the roulette selection: The probability of each individual being selected is defined as

wherexirepresents individual, andf(xi) denotes the fitness value of individualxi.

3.3.4.Crossover Function

As we discussed before, we designed image block processing, and one image block is an individual.The number of genes is very small, so instead of the complex way of crossover, one-point crossover is used.The crossing point is selected by a random function.According to the position of the selected crossing point, a chromosome is divided into two parts before and after the crossing point, where the matching parents exchange the front or back gene values of the crossing point.

3.3.5.Mutation Function

The mutation function imitates the mutation of biological genes in nature.First, a gene bit on the chromosome is selected randomly, and the decimal gray value on the gene position is converted into the binary code of 8 bits, then one bit is randomly selected to change, and finally the changed binary value is converted into the decimal gray value.

4.Simulation Results

4.1.Data of Experiment

The experimental data is the captured picture shown inFig.4, and the size is 101×26 pixels.The degraded image is obtained from the original image by a 4×4-point spread function, as shown inFig.5.

Fig.4.Test image.

Fig.5.Degraded image.

4.2.Experiment Results

We discussed the design of dividing image into blocks, so in Experiment 1, the results of dividing the image into blocks or not are compared.The set of parameters is shown inTable 2and the results are shown inFig.6.

Figs.6(a) and (b) are the image restoration results of Case 1 and Case 2, designed inTable 2,respectively.They are set with the same value of the initial population and iteration, and the only difference is the operation of dividing image into blocks or not.Obviously, as shown inFig.6(b), by dividing the image into blocks, Case 2 has a better restoration result.Because of the large number of pixels and the wide range of pixels in the image processed without blocks, it is difficult to get good individuals by randomly generating the initial population.As a result, the convergence speed is very slow in the later stage, and the individual performance is still very poor after the same number of iterations.And it is less likely to obtain more information through the restored image in Case 1.

Then in Experiment 2, different values of the population size and iterations are set inTable 3.For all cases inTable 3, the dividing operation with the block size of 3×3 pixels is adopted.

Table 2: Case design

Table 3: Different parameter values

Fig.6.Image restoration results of case design in Table 2:(a) result of Case 1 and (b) result of Case 2.

Then, we get different results and their running time, as shown inFig.7.

Fig.7.Experiment 2 results: (a) ID = 2 and t = 50 min, (b) ID = 3 and t = 22 min, (c) ID = 4 and t = 10.5 min, and (d) ID = 5 and t = 7 min.

4.3.Comparative Study

The contrastive study is shown in this subsection inTable 4.And experiment results are shown inFig.8.

Fig.8.Comparative study results: (a) Gaussian filter, (b) median filter, and (c) our proposed model.

Figs.8(a) and (b) are the results of applying the Gaussian and median filters, respectively, andFig.8(c) is the results by applying the proposed model, which is better than the other two.From bothTable 4andFig.8, it can be seen that image restoration results are not good by directly performing the filtering operation on the image, and our proposed model performs better, which verifies the improvement of our model.

Table 4: Compare the proposed method with filters

Compared with Case 4, Case 3 has a larger number of iterations, leading to longer running time and a better result.Compared with Case 5, Case 4 has a larger population size, leading to longer running time and a clearer result.Cases 1 to 5 all demonstrate the feasibility of deploying GA with memristors in image restoration.Besides, when the initial population and the number of iterations are too small (as shown inFig.7(d)), the restoration result of the image is the worst: The words and numbers are vague.After increasing the size of the initial population and the number of iterations, the restoration results are improved,but it is not that: The larger the size of population and the number of iterations are, the better the results.Therefore, the appropriate population size and iteration time should be chosen according to the actual needs,without blindly pursuing the large size of the initial population and iterations.Although the restoration result could be improved, the time cost is very large.So both the improvement of restoration and time cost should be taken into consideration.

5.Conclusions

In this paper, memristor-based GA for image restoration is proposed.The mapping rules between the memristor and GA are shown.According to the rules, memristor-based GA is designed and carried out successfully.The comparative study shows that the proposed method has better performance.It is demonstrated that using memristors to implement GA is possible and memristor-based GA for image restoration is feasible.

Memristor, GA, and image restoration all have wide applications in different fields.There are still some other algorithms, like the ant colony optimization, which can be implemented in a similar way.But the existing methods are not completely unified yet.Once unified, more different algorithms can be implemented with the memristor-based array, which is helpful to increase the use of memristors.So more efforts are needed to design a unified system and enrich the application cases.

Disclosures

The authors declare no conflicts of interest.