Feed Forward Genetic Image Network:
Toward Eﬃcient Automatic Construction of
Image Processing Algorithm
Shinichi Shirakawa and Tomoharu Nagao
Graduate School of Environment and Information Sciences, Yokohama National
University, 79-7, Tokiwadai, Hodogaya-ku, Yokohama, Kanagawa, 240-8501, Japanshirakawa@nlab.sogo1.ynu.ac.jp, nagao@ynu.ac.jp

Abstract. A new method for automatic construction of image transformation, Feed Forward Genetic Image Network (FFGIN), is proposed inthis paper. FFGIN evolves feed forward network structured image transformation automatically. Therefore, it is possible to straightforward execution of network structured image transformation. The genotype in FFGIN is a ﬁxed length representation and consists of string which encode
the image processing ﬁlter ID and connections of each node in the network. In order to verify the eﬀectiveness of FFGIN, we apply FFGIN tothe problem of automatic construction of image transformation which is“pasta segmentation” and compare with several method. From the experimental results, it is veriﬁed that FFGIN automatically constructs imagetransformation. Additionally, obtained structure by FFGIN is unique,and reuses the transformed images.

1

Introduction

In image processing, it is diﬃcult to select image processing ﬁlters to satisfy thetransformation from original images to its target images. The system of ACTIT(Automatic Construction of Tree structural Image Transformation)[1–3] havebeen proposed previously. ACTIT approximates adequate image transformationfrom original images to their target images by a combination of several known
image processing ﬁlters. ACTIT constructs tree structured image processing ﬁlters using Genetic Programming (GP)[4, 5]. Recently, the extended method of
ACTIT, Genetic Image Network (GIN)[6], have been proposed. Instead of tree
representation, the representation of GIN is arbitrary network structure. The
output images of each node in GIN changes every step. Thus, in GIN the users
must decide the parameter of “the number of steps”. This parameter is the stepof evaluating the output image.
This paper introduces a new method for automatic construction of imagetransformation. This new method, named Feed Forward Genetic Image Network(FFGIN), uses feed forward network representation. FFGIN evolves the feed
forward network structure of image processing ﬁlters based on instance basedlearning in similar ways of the case of ACTIT. The characteristic of FFGIN is2

Shinichi Shirakawa and Tomoharu Nagao

its structure of connections of image processing ﬁlters (feed forward network
structure). In FFGIN, it is possible to straightforward execution of network
structured image transformation, and it does not need the parameter of ”thenumber of step”. In order to verify the eﬀectiveness of FFGIN, we apply FFGIN to the problem of automatic construction of image transformation which is“pasta segmentation”.
The next section of this paper is an overview of several related works. In section 3, we describe our proposed method, Feed Forward Genetic Image Network(FFGIN). Next, in section 4, we apply the proposed method to the problem of
automatic construction of image transformation and show several experimental
results. Finally, in section 5, we describe conclusion and future work.

2

Related Works

2.1

Genetic Programming and Graph based Genetic Programming

Genetic Programming (GP)[4, 5] is one of Evolutionary Computation techniques,
which was introduced by Koza. GP evolves computer programs, which are usually tree structure, and searches a desired program using Genetic Algorithm(GA). Today, a lot of extensions and improvements of GP are proposed. Parallel Algorithm Discovery and Orchestration (PADO) [7, 8]is one of the graphbased GPs instead of the tree structure. PADO was applied to the object recognition problems. Another graph based GP is the Parallel Distributed Genetic
Programming (PDGP)[9]. In this approach, the tree is represented as a graphwith functions and terminals nodes located over a grid. Cartesian Genetic Programming (CGP)[10, 11] was developed from a representation that was used forthe evolution of digital circuits and represents a programs as a graph. In CGP,
the genotype is an integer string which denotes a list of node connections andfunctions. This string is mapped into phenotype of an index graph. Recently,
Genetic Network Programming (GNP)[12, 13] which has a directed graph structure is proposed. GNP is applied to make the behavior sequences of agents andshows better performances compared to GP.
By the way, in the literature of genetic approaches for neural networks design
or training, many kinds of methods have been proposed[14]. And the evolutionof neural networks using Genetic Algorithm (GA) has shown the eﬀectivenessin the various ﬁelds. The NeuroEvolution of Augmenting Topologies (NEAT)
method for evolving neural networks has been proposed by Stanley[15]. Eachgenome in NEAT includes a list of connection genes, each of which refers to two
node genes being connected.
2.2

Automatic Construction of Tree structural Image
Transformation (ACTIT)

ACTIT[1–3] constructs tree structured image processing ﬁlters with one-input
one-output ﬁlters and two-inputs one-output ﬁlters by using Genetic Programming (GP) to satisfy the given several image examples. The individual in ACTIT

Feed Forward Genetic Image Network

3

is a tree structured image transformation. The terminal nodes of a tree are theoriginal images and non-terminal nodes are several kinds of image processing
ﬁlters. A root node means an output image. The users give “Training images”,
and ACTIT system constructs appropriate image processing automatically. 3DACTIT[2, 3] is extended method which automatically constructs various 3D image processing procedures, and applies to medical image processing.
2.3

Genetic Image Network (GIN)

Genetic Image Network (GIN)[6] is a method for automatically constructionof image transformation. Instead of tree representation, the representation of
GIN is arbitrary network structure. GIN is composed of several nodes which
are well-known image processing ﬁlters whose input is one or two. The biggest
diﬀerence between GIN and ACTIT is the structure of connections of image processing ﬁlters. Generally, network structure theoretically includes tree structure(i.e. network structure also represent tree structure). Therefore, the description
ability of network representation is higher than that of tree structure. Genotype in GIN consists of a string which indicate image processing ﬁlter type andconnections. The other work shows that GIN automatically constructs a simple
structure for complex image transformation using its network representation[6].
The execution of GIN is as follows. Initially, we set original images to “in” nodes
when GIN executes. All nodes synchronously transform each inputted images,
and output the transformed image to destination nodes. The output images ofeach node changes every steps. After predeﬁned iterations (called “the numberof steps”), the images of output nodes are evaluated.

3

Feed Forward Genetic Image Network (FFGIN)

3.1

Overview

ACTIT uses Genetic Programming (GP) and has a tendency to create image
processing ﬁlters with unnecessarily large size. This problem in GP is called
bloat and increases computational eﬀorts. In GIN, the output images of eachnode changes every step. Thus, the users must decide the parameter of “thenumber of step”. This parameter is the step of evaluating the output image.
However, the optimum value of “the number of steps” does not ﬁnd in advance.
To overcome these problems, we propose Feed Forward Genetic Image Network(FFGIN) whose representation is feed forward network structure. It is possible
to straightforward execution of network structured image transformation, and it
does not need the parameter of ”the number of step”. The genotype of GIN is astring which denotes a list of image processing ﬁlter ID and connections of eachnode in the network.
The features of FFGIN are summarized as follows:– Feed forward network structure of image processing ﬁlters.
– Eﬃcient evolution of image processing programs without bloat through the
genotype of ﬁxed length string.

4

Shinichi Shirakawa and Tomoharu Nagao

3.2

Structure of FFGIN

Feed Forward Genetic Image Network (FFGIN) constructs acyclic network structured image transformation automatically. Figure 1 illustrates an example ofPhenotype (feed forward network structure) and Genotype (string representing
Phenotype) in FFGIN. Each node in FFGIN is well-known image processing ﬁlters. In FFGIN, the feedback structure is restricted in genotype level. The nodes
take their inputs from either the output of a previous node or from the inputs
in a feed forward manner. Therefore, it is possible to straightforward executionof network structured image transformation, and it does not need the parameter of “the number of step”. The main beneﬁt of this type of representationis that it allows the implicit reuse of nodes in the network. To adopt evolutionary method, genotype-phenotype mapping is used in FFGIN system. This
genotype-phenotype mapping method is similar to Cartesian Genetic Programming (CGP). The feed forward network image processing ﬁlters are encodedin the form of a linear string. The genotype in FFGIN is a ﬁxed length representation and consists of string which encode the image processing ﬁlter ID
and connections of each node in the network. However, the number of nodes in
the phenotype can vary but is bounded, as not all of the nodes encoded in the
genotype have to be connected. This allows the existence of inactive nodes. The
length of the genotype is ﬁxed and equals to Nnode ∗ (nin + 1) + Nout , where
Nnode is the number of nodes, nin is the maximum number of inputs of predeﬁned ﬁlters and Nout is the number of output nodes. FFGIN constructs feed
forward network structured image processing ﬁlters, thus it is possible to represent plural outputs. FFGIN enables to simultaneously construct plural imagetransformation using only a single network structure.

3.3

Genetic Operators

To obtain the optimum structure of FFGIN, an evolutionary method is adopted.
The genotype of FFGIN is a linear string. Therefore, FFGIN is able to use ausual Genetic Algorithm (GA). In this paper we use uniform crossover andmutation as the genetic operators. The uniform crossover operator aﬀects two
individuals, as follows:– Select several genes randomly according to the crossover rate Pc for eachgene.
– The selected genes are swapped between two parents, and generate oﬀspring.
The mutation operator aﬀects one individual, as follows:– Select several genes randomly according to the mutation rate Pm for eachgene.
– The selected genes are randomly changed.

Feed Forward Genetic Image Network

2JGPQV[RG

0Q

E

0Q

C

0Q

KPRWVPQFG

0Q
0Q

KP

D

0Q

QWV

KPCEVKXGPQFG

0Q

0Q

QWVRWVPQFG

H

C

0Q

KOCIGHKNVGT

H

I

0Q

KP

5

EQPPGEVKQP

QWV

G

0Q

0Q

F

I

KPCEVKXGEQPPGEVKQP)GPQV[RG
0Q
C

0Q




D





0Q
F

0Q




G





0Q

HKNVGT+& EQPPGEVKQPԘ

H

0Q




E





0Q
H

0Q




I





0Q

EQPPGEVKQPԙ

I

0Q




C





QWV QWVQPGKPRWVKOCIGHKNVGTFig. 1. Structure of FFGIN (phenotype) and the genotype which denotes a list of ﬁlter
ID and connections.

4

Experiments and Results

In this section, we apply FFGIN to the problem of automatic construction ofimage transformation. Additionally, the eﬀectiveness of FFGIN, GIN and ACTIT
are compared.
4.1

Settings of Experiments“Training images” we used in the experiments appear in Figure 2 (four training images). “Training images” consist of original images and target images.
The number of “Training images” is four. Target images are the images thatusers require after the image processing (ideal results). This “pasta segmentation problem” is proposed as subject of a competition at Genetic and Evolutionary Computation Conference 2006 (GECCO 2006)1 . The problem consistsin evolving a detection algorithm capable of separating pasta pixels from nonpasta pixels in pictures containing various kinds of (uncooked) pasta randomly
placed on textured backgrounds. The problem is made harder by the varying
lighting conditions and the presence, in some of the images, of “pasta noise”(i.e., small pieces of pasta representing alphanumeric characters) which must belabeled as background. All images used in the experiments are gray scale images
and the size of 128 × 96 pixel.
1

http://cswww.essex.ac.uk/staﬀ/rpoli/GECCO2006/pasta.htm

6

Shinichi Shirakawa and Tomoharu Nagao

Original image 1

Original image 2

Original image 3

Original image 4

Target image 1

Target image 2

Target image 3

Target image 4

Fig. 2. “Training images” used in the experiments. The number of “Training images”
is four.
Table 1. Parameters of each algorithm.

Parameter
FFGIN GIN
ACTIT
The number of generations
5000 5000
5000
Population size N
150
150
150
Crossover rate Pc
0.9
0.9
N/A
Mutation rate Pm
0.03 0.03 0.9 (for individual)
Generation alternation model
MGG MGG
MGG
Tournament size
55
5The maximum number of nodes
50
50
50
The number of steps
N/A
10
N/A
The number of independent runs 101010

We use the mean error on the “Training images” as a ﬁtness function. The
ﬁtness function used in the experiments is:


W ∑
H
∑

n 
n

|oij − tij | 

N 

1 ∑
i=1 j=1
f itness =1−(1)
N n=1 W · H · Vmax 






where on is the transformed image and tn is its target one. The numbers of pixelin the direction i and j are W , H respectively, and the number of training image
set is N . The range of this ﬁtness function is [0.0, 1.0]. The higher the numericalvalue indicates the better performance.
We use Minimal Generation Gap (MGG) as the generation alternation model.
The MGG model [16, 17] is a steady state model proposed by Satoh et al. The

Feed Forward Genetic Image Network

7

MGG model has a desirable convergence property maintaining the diversity ofthe population, and shows higher performance than the other conventional models in a wide range of applications. We use the MGG model in the experiments
as follows:
1. Set generation counter t = 0. Generate N individuals randomly as the initial
population P (t).
2. Select a set of two parents M by random sampling from the population P (t).
3. Generate a set of m oﬀspring C by applying the crossover and the mutation
operation to M .
4. Select two individuals from set M + C. One is the elite individual and theother is the individual by the tournament selection. Then replace M withthe two individuals in population P (t) to get population P (t + 1).
5. Stop if a certain speciﬁed condition is satisﬁed, otherwise set t = t + 1 andgo to step 2.
In the experiments we use m = 50.
The parameters used by FFGIN, GIN and ACTIT are shown in Table 1. The
common parameters between the three methods are identical. We prepare simple
and well-known image processing ﬁlters in the experiments (27 one-input oneoutput ﬁlters and 11 two-inputs one-output ﬁlters). For instance, Mean ﬁlter,
Maximum ﬁlter, Minimum ﬁlter, Sobel ﬁlter, Laplacian ﬁlter, Gamma correction
ﬁlter, Binarization, Linear transformation, Diﬀerence, Logical sum, Logical prod
and so on. FFGIN, GIN and ACTIT construct complex image processing fromcombination of these ﬁlters. Results are given for 10 diﬀerent runs with the same
parameter set.
4.2

Results and Discussion

Figure 3 shows the output images of “Training images” using FFGIN, and theﬁtness of this image transformation is 0.9676. FFGIN scored very high, andthe output images are extremely similar to target images. FFGIN automaticallyconstructs feed forward network structured image transformation.
Figure 4 is obtained structure (feed forward network structured image processing ﬁlters) using FFGIN. FFGIN constructs the structure of reusing thetransformed images in its network. This structure cannot be constructed using
ACTIT. We only give the “Training images”, FFGIN constructs the ideal image
processing automatically.
Next, we apply the constructed feed forward network structured image processing ﬁlters using FFGIN to “Test images”. “Test images” are not used inevolutionary process (non-training images which are similar to training images).
“Test images” used in the experiments are shown in Figure 5 (four images). The
number of “Test images” is four. The results (output images) also appear in
Figure 5. From the output images, FFGIN transforms the test images to theideal images which extracted “pasta” in the varying lighting conditions and thepresence. It shows that FFGIN automatically construct general image transformation through learning.

8

Shinichi Shirakawa and Tomoharu Nagao

Output image 1

Output image 2

Output image 3

Output image 4

Fig. 3. Output images of “Training images” using FFGIN.

$KPCTK\CVKQP&KUETKOKPCPV#PCN[UKU/KPKOWO$QWPFGF2TQF

5QDGN&GRNQ[/CZ&TCUVKE5WO#NIGDTCKE5WO$QWPFGF2TQF$QWPFGF2TQF$KPCTK\CVKQP $QWPFGF2TQF

QWVRWVKOCIG

5QDGN&CTM'FIGKPRWVKOCIG.CTIG#TGC.KIJV2KZGN&TCUVKE5WO%QPVTCEVKQP.KIJV2KZGN&TCUVKE2TQF.CRNCEKCP

Fig. 4. An example of obtained structure (image processing ﬁlters) by FFGIN.

Figure 6 shows transition of average ﬁtness of 10 independent runs. According to the result, we can evaluate all algorithms constructed adequate image
processing algorithms. The performance of FFGIN is comparable with GIN and
ACTIT.
Finally, we discuss the computational time of the experiments. We generate
the results presented in this paper using a Intel Core 2 Duo E6400 processor with
1GB of memory. Table 2 shows the comparison of computational time between
FFGIN, GIN and ACTIT. The computational time of FFGIN is about 8 times
faster than GIN and about 5 times faster than ACTIT because of the evolutionof without bloat. FFGIN allows the reuse of nodes, and the constructed structure(image processing ﬁlters) tends to compact. Therefore, the computational timedecreases.

Feed Forward Genetic Image Network

Test image 1

Test image 2

Test image 3

Test image 4

Output image 1

Output image 2

Output image 3

Output image 4

9Fig. 5. “Test images” which are not used in evolutionary process (four images), andthe output images of the obtained structure by FFGIN.

0.97
0.96
0.95

Fitness

0.94
0.93
0.92
0.91
0.9

FFGIN
GIN
ACTIT

0.89
0.88
0

1000

2000
3000
4000
Number of generations

5000

Fig. 6. The transition of ﬁtness of FFGIN, GIN and ACTIT. Each curve is an averageof 10 independent runs.

5

Conclusion and Future WorkIn this paper, we proposed a new method for automatic construction of imagetransformation, Feed Forward Genetic Image Network (FFGIN), which evolves
feed forward network structured image transformation programs. We applied
FFGIN to evolve image processing algorithm of “pasta segmentation” and con-

10

Shinichi Shirakawa and Tomoharu Nagao

Table 2. Average computational time in seconds for each algorithm (average of 10
independent runs).
FFGIN GIN ACTIT
Computational time 5427 42620 28130

ﬁrmed that the optimum solution in each problem was obtained by the FFGIN
system. From the experimental results, the performance of FFGIN is comparable with GIN and ACTIT, and the computational time of FFGIN is about 5
times faster than ACTIT. In future work we will apply FFGIN to other problemsof image processing, in particular on larger problems and other types of problems. Moreover, we will introduce to the mechanisms of evolution of numericalparameters simultaneously in FFGIN.

References
1. Aoki, S., Nagao, T.: Automatic construction of tree-structural image transformation using genetic programming. In: Proceedings of the 1999 International
Conference on Image Processing (ICIP-99). Volume 1., Kobe, Japan, IEEE (1999)
529–533
2. Nakano, Y., Nagao, T.: 3D medical image processing using 3D-ACTIT; automaticconstruction of tree-structural image transformation. In: Proceedings of the International Workshop on Advanced Image Technology (IWAIT-2004), Singapore(2004) 529–533
3. Nakano, Y., Nagao, T.: Automatic construction of abnormal signal extraction
processing from 3D diﬀusion weighted image. In: Proceedings of the International Workshop on Advanced Image Technology (IWAIT-2007), Bangkok, Thailand (2007)
4. Koza, J.R.: Genetic Programming: On the Programming of Computers by Meansof Natural Selection. MIT Press, Cambridge, MA, USA (1992)
5. Koza, J.R.: Genetic Programming II: Automatic Discovery of Reusable Programs.
MIT Press, Cambridge, MA, USA (1994)
6. Shirakawa, S., Nagao, T.: Genetic image network (GIN): Automatically construction of image processing algorithm. In: Proceedings of the International Workshop
on Advanced Image Technology (IWAIT-2007), Bangkok, Thailand (2007)
7. Teller, A., Veloso, M.: Algorithm evolution for face recognition: What makes apicture diﬃcult. In: International Conference on Evolutionary Computation, Perth,
Australia, IEEE Press (1995) 608–613
8. Teller, A., Veloso, M.: PADO: A new learning architecture for object recognition.
In Ikeuchi, K., Veloso, M., eds.: Symbolic Visual Learning. Oxford University Press(1996) 81–116
9. Poli, R.: Evolution of graph-like programs with parallel distributed genetic programming. In: Proceedings of the Seventh International Conference on Genetic
Algorithms, East Lansing, MI, USA, Morgan Kaufmann (1997) 346–353
10. Miller, J.F., Smith, S.L.: Redundancy and computational eﬃciency in cartesian
genetic programming. IEEE Transactions on Evolutionary Computation 10 (2006)
167–174

Feed Forward Genetic Image Network

11

11. Miller, J.F., Thomson, P.: Cartesian genetic programming. In: Genetic Programming, Proceedings of EuroGP’2000. Volume 1802 of LNCS., Edinburgh, SpringerVerlag (2000) 121–132
12. Hirasawa, K., Okubo, M., Hu, J., Murata, J.: Comparison between genetic network
programming (GNP) and genetic programming (GP). In: Proceedings of the 2001
Congress on Evolutionary Computation (CEC01), Seoul, Korea, IEEE Press (2001)
1276–1282
13. Eguchi, T., Hirasawa, K., Hu, J., Ota, N.: A study of evolutionary multiagent
models based on symbiosis. IEEE Transactions on Systems, Man and Cybernetics
Part B 36 (2006) 179–193
14. Yao, X.: Evolving artiﬁcial neural networks. Proceedings of the IEEE 87 (1999)
1423–1447
15. Stanley, K.O.: Eﬃcient evolution of neural networks through complexiﬁcation.
Technical Report AI-TR-04-314, Ph.D. Thesis; Department of Computer Sciences,
The University of Texas at Austin (2004)
16. Satoh, H., Yamamura, M., Kobayashi, S.: Minimal generation gap model for considering both exploration and exploitations. In: Proceedings of the IIZUKA’96.
(1996) 494–497
17. Kita, H., Ono, I., Kobayashi, S.: Multi-parental extension of the unimodal normal
distribution crossover for real-coded genetic algorithms. In: Proceedings of the 1999
Congress on Evolutionary Computation (CEC99). Volume 2. (1999) 1581–1587