1 /*
2  * Licensed to the Apache Software Foundation (ASF) under one or more
3  * contributor license agreements.  See the NOTICE file distributed with
4  * this work for additional information regarding copyright ownership.
5  * The ASF licenses this file to You under the Apache License, Version 2.0
6  * (the "License"); you may not use this file except in compliance with
7  * the License.  You may obtain a copy of the License at
8  *
9  *      http://www.apache.org/licenses/LICENSE-2.0
10  *
11  * Unless required by applicable law or agreed to in writing, software
12  * distributed under the License is distributed on an "AS IS" BASIS,
13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and
15  * limitations under the License.
16  */
17 package org.apache.commons.math3.userguide.genetics;
18 
19 import java.awt.Component;
20 import java.awt.Dimension;
21 import java.awt.FlowLayout;
22 import java.awt.Graphics;
23 import java.awt.Graphics2D;
24 import java.awt.event.ActionEvent;
25 import java.awt.event.ActionListener;
26 import java.awt.image.BufferedImage;
27 import java.io.File;
28 import java.io.IOException;
29 import java.util.LinkedList;
30 import java.util.List;
31 
32 import javax.imageio.ImageIO;
33 import javax.swing.Box;
34 import javax.swing.ImageIcon;
35 import javax.swing.JButton;
36 import javax.swing.JLabel;
37 
38 import org.apache.commons.math3.genetics.Chromosome;
39 import org.apache.commons.math3.genetics.ElitisticListPopulation;
40 import org.apache.commons.math3.genetics.GeneticAlgorithm;
41 import org.apache.commons.math3.genetics.Population;
42 import org.apache.commons.math3.genetics.TournamentSelection;
43 import org.apache.commons.math3.genetics.UniformCrossover;
44 import org.apache.commons.math3.userguide.ExampleUtils;
45 import org.apache.commons.math3.userguide.ExampleUtils.ExampleFrame;
46 
47 /**
48  * This example shows a more advanced use of a genetic algorithm: approximate a raster image
49  * with ~100 semi-transparent polygons of length 6.
50  * <p>
51  * The fitness function is quite simple yet expensive to compute:
52  *
53  *   - draw the polygons of a chromosome to an image
54  *   - compare each pixel with the corresponding reference image
55  * <p>
56  * To improve the speed of the calculation, we calculate the fitness not on the original image size,
57  * but rather on a scaled down version, which is sufficient to demonstrate the power of such a genetic algorithm.
58  * <p>
59  * TODO:
60  *  - improve user interface
61  *    - make algorithm parameters configurable
62  *    - add a gallery of results after x iterations / minutes (either automatic or based on button click)
63  *    - allow loading / selection of other images
64  *    - add logging in the user interface, e.g. number of generations, time spent, ...
65  *
66  * @see <a href="http://www.nihilogic.dk/labs/evolving-images/">Evolving Images with JavaScript and canvas (Nihilogic)</a>
67  */
68 @SuppressWarnings("serial")
69 public class ImageEvolutionExample {
70 
71     public static final int   POPULATION_SIZE  = 40;
72     public static final int   TOURNAMENT_ARITY = 5;
73     public static final float MUTATION_RATE    = 0.02f;
74     public static final float MUTATION_CHANGE  = 0.1f;
75 
76     public static final int POLYGON_LENGTH = 6;
77     public static final int POLYGON_COUNT = 100;
78 
79     public static class Display extends ExampleFrame {
80 
81         private GeneticAlgorithm ga;
82         private Population currentPopulation;
83         private Chromosome bestFit;
84 
85         private Thread internalThread;
86         private volatile boolean noStopRequested;
87 
88         private BufferedImage ref;
89 
90         private BufferedImage referenceImage;
91         private BufferedImage testImage;
92 
93         private ImagePainter painter;
94 
Display()95         public Display() throws Exception {
96             setTitle("Commons-Math: Image Evolution Example");
97             setSize(600, 400);
98 
99             setLayout(new FlowLayout());
100 
101             Box bar = Box.createHorizontalBox();
102 
103             ref = ImageIO.read(new File("resources/monalisa.png"));
104             //ref = ImageIO.read(new File("resources/feather-small.gif"));
105 
106             referenceImage = resizeImage(ref, 50, 50, BufferedImage.TYPE_INT_ARGB);
107             testImage = new BufferedImage(referenceImage.getWidth(), referenceImage.getHeight(), BufferedImage.TYPE_INT_ARGB);
108 
109             JLabel picLabel = new JLabel(new ImageIcon(ref));
110             bar.add(picLabel);
111 
112             painter = new ImagePainter(ref.getWidth(), ref.getHeight());
113             bar.add(painter);
114 
115             // set the images used for calculating the fitness function:
116             //   refImage  - the reference image
117             //   testImage - the test image to draw the current chromosome
118             PolygonChromosome.setRefImage(referenceImage);
119             PolygonChromosome.setTestImage(testImage);
120 
121             add(bar);
122 
123             JButton startButton = new JButton("Start");
124             startButton.setActionCommand("start");
125             add(startButton);
126 
127             startButton.addActionListener(new ActionListener() {
128                 public void actionPerformed(ActionEvent e) {
129                     if (isAlive()) {
130                         stopRequest();
131                     } else {
132                         startEvolution();
133                     }
134                 }
135             });
136 
137             // initialize a new genetic algorithm
138             ga = new GeneticAlgorithm(new UniformCrossover<Polygon>(0.5), 1.0,
139                                       new RandomPolygonMutation(MUTATION_RATE, MUTATION_CHANGE), 1.0,
140                                       new TournamentSelection(TOURNAMENT_ARITY));
141 
142             // initial population
143             currentPopulation = getInitialPopulation();
144             bestFit = currentPopulation.getFittestChromosome();
145         }
146 
isAlive()147         public boolean isAlive() {
148             return internalThread != null && internalThread.isAlive();
149         }
150 
stopRequest()151         public void stopRequest() {
152             noStopRequested = false;
153             internalThread.interrupt();
154             internalThread = null;
155         }
156 
startEvolution()157         public void startEvolution() {
158             noStopRequested = true;
159             Runnable r = new Runnable() {
160                 public void run() {
161                     int evolution = 0;
162                     while (noStopRequested) {
163                         currentPopulation = ga.nextGeneration(currentPopulation);
164 
165                         System.out.println("generation: " + evolution++ + ": " + bestFit.toString());
166                         bestFit = currentPopulation.getFittestChromosome();
167 
168                         painter.repaint();
169                     }
170                 }
171             };
172 
173             internalThread = new Thread(r);
174             internalThread.start();
175         }
176 
177         private class ImagePainter extends Component {
178 
179             private int width;
180             private int height;
181 
ImagePainter(int width, int height)182             public ImagePainter(int width, int height) {
183                 this.width = width;
184                 this.height = height;
185             }
186 
getPreferredSize()187             public Dimension getPreferredSize() {
188                 return new Dimension(width, height);
189             }
190 
191             @Override
getMinimumSize()192             public Dimension getMinimumSize() {
193                 return getPreferredSize();
194             }
195 
196             @Override
getMaximumSize()197             public Dimension getMaximumSize() {
198                 return getPreferredSize();
199             }
200 
paint(Graphics g)201             public void paint(Graphics g) {
202                 PolygonChromosome chromosome = (PolygonChromosome) bestFit;
203                 chromosome.draw((Graphics2D) g, ref.getWidth(), ref.getHeight());
204             }
205 
206         }
207 
208     }
209 
main(String[] args)210     public static void main(String[] args) throws Exception {
211         ExampleUtils.showExampleFrame(new Display());
212     }
213 
resizeImage(BufferedImage originalImage, int width, int height, int type)214     private static BufferedImage resizeImage(BufferedImage originalImage, int width, int height, int type) throws IOException {
215         BufferedImage resizedImage = new BufferedImage(width, height, type);
216         Graphics2D g = resizedImage.createGraphics();
217         g.drawImage(originalImage, 0, 0, width, height, null);
218         g.dispose();
219         return resizedImage;
220     }
221 
getInitialPopulation()222     private static Population getInitialPopulation() {
223         List<Chromosome> popList = new LinkedList<Chromosome>();
224         for (int i = 0; i < POPULATION_SIZE; i++) {
225             popList.add(PolygonChromosome.randomChromosome(POLYGON_LENGTH, POLYGON_COUNT));
226         }
227         return new ElitisticListPopulation(popList, popList.size(), 0.25);
228     }
229 
230 }
231