Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

The motivation for this research was to design a linear color vector image filter mask using a GA and zooming techniques: the design of such a mask is hard to do, even with the mathematical framework described in [11]. We have successfully done this and found a single filter mask which gives glowing color edges in all directions.

The process of edge detection both in gray and color images, in the spatial (or image) domain, has until now been needed separate masks for each direction of edges (i.e. vertical, horizontal or diagonal). This greatly limits the type of filters that may be realized. Vector image filtering based on a hypercomplex convolution scheme was first introduced by Sangwine [5]. He designed a quaternion based color edge detector, which could detect edges both in horizontal or vertical mask separately with two different masks (horizontal and vertical). Further development in the design of such linear color image filters by mathematical methods was difficult: Sangwine [11] suggested the use of a GA approach for the design of linear vector color image filters. This problem has been successfully resolved by the new approach described in this paper.

2 Representation of Color Image Pixels in Terms of Quaternions

The quaternions are a four-space generalization of the complex numbers consisting one real part and three imaginary parts with imaginary operators i, j and k, which satisfy \(i^2 = j^2 = k^2 = -1\) and \(ij = -ji,\, ki = -ik,\, jk = -kj,\, ijk=-1\).

RGB colour images can be represented using quaternion-valued pixels. Where, the values of the red, green and blue components are stored in the three imaginary parts while the real part is zero, as a pure quaternion. Generally, image filtering may be employed by convolving a filter ‘mask’ with an image and it is generally a convolution with a quaternion-valued mask [5].

However, vector filtering based on a hypercomplex convolution scheme was first reported in Sangwine [5] and according to him, the definition of hypercomplex convolution can be described as:

$$\begin{aligned} \bar{g}(n, m)=\sum _{x=-X}^{X}\sum _{y=-Y}^{Y}h_{L}(x, y)g(n-x\!\!\!\mod N, m-y\!\!\!\mod M)h_{R}(x, y), \end{aligned}$$

where

  • \(\bar{g}(n,m)\) = Filtered image in a quaternion array (\(N+2\times M+2\)).

  • \(g(\cdot )\) = Original image in a quaternion array (\(N\times M\))).

  • \(h_L(x, y)\) = Quaternion left mask (\((2X + 1)\times (2Y + 1)\)).

  • \(h_R(x, y)\) = Quaternion right mask (\((2X + 1)\times (2Y + 1)\)).

Due to the non-commutative nature of quaternions, two masks with quaternion coefficients are needed, one on the left of each pixel and one on the right. These coefficients permit masks to implement linear operations on the pixel values, such as rotation in RGB color space.

3 Genetic Algorithm

Genetic algorithms are based on the theory of natural selection, first described by Charles Darwin, and they belong to the set of evolutionary algorithms used to generate solutions for optimization problems. A genetic algorithm optimization process starts with an initial random population and basically consists of three major operations: selection, crossover and mutation. The selection evaluates each individual and keeps only the fittest ones in the population. In addition to those fittest individuals, some less fit ones would be chosen according to a small probability. The others are discarded from the current population. Crossover recombines two individuals to create new ones which may be fitter. The mutation operator introduces alteration in a small number of individuals. Its purpose is to maintain the population diversity during the optimization process in order to provide a wider search space required for finding a good solution. The process of selection, crossover and mutation continues for a fixed number of generations or until a termination condition is satisfied [1].

There are five simple steps as shown in Fig. 1 of a genetic algorithm technique [4].

Fig. 1.
figure 1

Flow chart of genetic algorithm

Full size image
  1. 1.

    Start with a randomly generated population of N chromosomes, where N is the size of population.

  2. 2.

    Measure the fitness value F(x) of each chromosome x in the population.

  3. 3.

    Repeat until N offspring are created:

    1. (a)

      Probabilistically choose a pair of chromosomes from the current population using the values of the fitness function.

    2. (b)

      Create an offspring \(y_i\) using crossover and mutation operators, where \(i=1,\ldots ,N\).

  4. 4.

    Replace the current population with the newly generated one.

  5. 5.

    Terminate when a stopping criterion is satisfied.

For the work reported in this new scheme, we need floating-point values to be computed as qaternion mask that are totally based on quaternion arithmetic and the more advanced form of genetic algorithms in Matlab provides floating point numbers.

Bhandarkar et al. [2] reported edge detection using genetic algorithm, in which the process of edge detection is designed as selecting a minimum cost edge configuration. The adaptation of mutation and crossover rates helps a rapid convergence. The experimental results showed the effective convergence rate and noise immunity.

Zhang et al. [8] proposed a combined approach of Sobel detector and a GA for edge detection. The experimental results showed a better performance as compared to Otsu thresholding method.

Yutang and Lulu [7] presented a new scheme for enhancing the convergence rate of edge detection using genetic optimization technique. In this method, the theory of good point a set for redesigning the crossover operation is used. The image is filtered to remove the non-edge pixels prior to edge detection which increases the convergence rate with effective and efficient edge detection and noise-immunity.

Rahebi et al. [9] proposed Ant Colony Optimization based on GA to increase the processing speed of search algorithms. In this scheme, a series of answers made by artificial ants is considered initially then GA is employed to produce the next population. Experimental results showed this method was efficient in edge detection with increase in speed and answers optimum.

Sheta et al. [10] proposed a scheme in which they combined traditional edge detection methods and genetic algorithm approach. The results showed better performance when compared with K-means clustering.

Preeti and Rajesh [12] presented an overview of Sobel and Canny operators and the experiment results showed that the genetic algorithm that works with improved Sobel operator generated much better results in comparison to them with limited to gray scale images. However, the novel approach that maximizes the objective function had been reviewed and found better outputs.

4 History of Linear Color Vector Image Filters

Until recently, no mathematical framework of edge detection filters to gray or color had been reported that could find edges in vertical, horizontal or diagonal direction with only one mask simultaneously. In 1998 Sangwine [5] published the first example of a color image filter based on convolution with hypercomplex or quaternion masks, detecting edges horizontally or vertically with different masks. Further development of linear vector image filtering was hard wth any present mathematical framework [11]. In this paper we rectify this problem by a very general approach with the convolution of hypercomplex coefficients inspired by Sangwine [5] based on the zooming technique using a genetic algorithm.

Fig. 2.
figure 2

Original Lena images used in each fitness function from (left) \(17\times 17\), \(28\times 28\), \(40\times 40\), \(53\times 53\), \(66\times 66\), \(99\times 99\), \(153\times 153\), \(233\times 233\), \(330\times 330\), \(409\times 409\), \(514\times 514\) to (right)

Full size image
Fig. 3.
figure 3

Target Lena images (Photoshopped images) used in each fitness function from (left) \(19\times 19\), \(30\times 30\), \(42\times 42\), \(55\times 55\), \(68\times 68\), \(101\times 101\), \(155\times 155\), \(235\times 235\), \(332\times 332\), \(411\times 411\), \(516\times 516\) to (right)

Full size image

5 Designing Methodology of the New Filter

5.1 Zooming Technique

We applied the zooming technique to produce glowing color edges in all directions. The technique is as follows.

We begin by making a target image in Adobe Photoshop editor using its glowing edges filter, which gives the original image an artistic effect as shown in the left-hand image of Fig. 4. The target image is used by the GA, which attempts to produce a filter (represented to the GA as an array of floating-point numbers) such that, if convolved with the original image, will produce the target image exactly. The fitness function used by the GA has to produce a numeric measure that reduces to zero, if the target image and filtered image (filtered by the proposed filter) are identical. Thus the GA attempts to minimize the fitness measure for each element of the population. The fitness function therefore computes the difference between the target and filtered image (filtered by the proposed filter) and sums the absolute value of the difference across the image.

To glow the color edges in all directions and also to speed up the GA, a ‘zooming’ technique is employed in which the GA initially works with a small portion of the image (a ‘zoomed-in’ view). Let us take an example to describe the zooming technique. Eleven sizes of the original Lena image and eleven sizes of target images are used. The eleven original Lena images are cropped from the full-size one. A \(17\times 17\) pixels section of the Lena image (around the eye) as shown in Fig. 2 and a low resolution \(19\times 19\) pixels target image of full size as shown in Fig. 3 are used in the first optimization stage. The GA computes an initial population using these images.

This computation is relatively fast because of the small number of pixels. It enhances the initial random population but it will not produce a good result, because it is operating only on a small part of the original image and a low resolution target image with small generation and population size. Next, a \(28\times 28\) pixels part-image of the original Lena and a \(30\times 30\) pixels low resolution full-size target image are used in the next optimization stage, producing a better population, but it will again computing somewhat more slowly.

The sizes of original Lena image to be filtered (\(40\times 40\), \(53\times 53\), \(66\times 66\), \(99\times 99\), \(153\times 153\), \(233\times 233\), \(330\times 330\), \(409\times 409\), \(514\times 514\) pixels) and target image (\(42\times 42\), \(55\times 55\), \(68\times 68\), \(101\times 101\), \(155\times 155\), \(235\times 235\), \(332\times 332\), \(411\times 411\), \(516\times 516\) pixels) are increased in each optimization stage, step by step. At each stage of optimization, the already converged population from the previous one is moved as the initial population in the next one.

5.2 Benefits of the Zooming Technique

There are four benefits of using the zooming technique.

  1. 1.

    First and the most powerful aspect of using the zooming technique is that it guides GA to glow color edges in all directions with only one mask. The filtered results using our new filter are much better than the target image.

  2. 2.

    Second, the image sizes increase step by step, and because most of the computation time is taken up with convolution, so the total computation time is reduced by approximately 90 %, compared to working with the full-size image from the start.

  3. 3.

    Third benefit is that the already converged population towards the best fitness values is moved to the next stage of the optimization as the initial population, which makes the fitness functions more effective to find the best result.

Initially, a function ‘qmask’ is made for a \(3\times 3\) Quaternion matrix from a \(1\times 36\) real vector. In edge detection the number of variables is the number of filter coefficients. For the \(3\times 3\) mask, the number of coefficients is 36. The genetic algorithm helps to find the coefficients of the proposed filter that was difficult manually.

The generations used here are 935 and population size is double of generations size; that is 1870 (85 generations and a population size of 170 are used in each optimization stage). The time consumption is approximately 1 h, crossover and mutation are selected heuristic and gaussian respectively while the elite children used here are 10.

The \(fitness\;function\;(errror)\) is designed as follows:

\(fitness\;function = mean(mean(abs(conv2(\{qmask,conj(qmask)\},qp) -qt\)))).

where

qp = Original Lena image (to be filtered by the proposed filter), in a quaternion array.

qt = Target image (Photoshopped Lena image), in a quaternion array.

\(conv2(\{qmask,conj(qmask)\},qp)\) = Filtered Lena image by the proposed filter, in a quaternion array.

qmask = Quaternion left mask (\(3\times 3\)) generated by GA.

cqmask = Quaternion right mask (\(3\times 3\)) generated by GA.

Fig. 4.
figure 4

Target Lena image (left) and filtered Lena image by the proposed filter (right)

Full size image
Fig. 5.
figure 5

Original Tulips image (left) and filtered Tulips image by the proposed filter (right)

Full size image

6 Experimental Results

We used our filter on a color Lena image. It produced glowing color edges in all directions, i.e. a sudden change of color, with the remaining parts of the image convert to black as shown in the right-hand image of Fig. 4. The Lena image as filtered by the proposed filter is much better than the actual target image, because it has more detail, fine and thin color edges in all directions. Although the quality of the GA is measured by the closeness of the proposed filter and the target image, the use of the zooming technique produces the better result than the target image. The filter has been tested on different types of color images and the results show that the performance of the new filter is outstanding.

Table 1 shows the coefficients of the Quaternion left mask (qmask) of the proposed filter. Quaternion right mask (cqmask) is created by negating the vector parts of the qmask (taking the conjugate of the Quaternion left mask), where qmask.s represents the scalar part and qmask.x, qmask.y and qmask.z represent the vector parts of the proposed filter mask (Figs. 5, 6 and 7).

Fig. 6.
figure 6

Original Monarch image (left) and filtered Monarch image by the proposed filter (right)

Full size image
Fig. 7.
figure 7

Original Peppers image (left) and filtered Peppers image by the proposed filter (right)

Full size image
Table 1. Quaternion left mask (qmask) of the proposed filter
Full size table

7 Conclusion

We can see from the experimental results that the proposed filter not only produces glowing color edges, but also finer detail than the target image due to the use of the zooming technique. Further advances after [5] in the design of linear vector image filters now becomes possible: this was a challenge using any mathematical approach as suggested in Sangwine [11]. We used zooming and GA techniques for the design of a linear color vector image filter. This new filter uses only one mask and produces color glowing edges in all directions. The proposed filter has been tested on different kind of color images and the experimental results show that the new filter is real need for glowing color edges in all directions with only one mask.