No post anterior implementamos o framework básico que nos permite aplicar o algoritmo a qualquer problema. O desafio agora é encontrar uma maneira de 'traduzir' um vetor de polígonos (nossa aproximação da imagem) em um cromossomo, e implementar um método getFitness que nos diga a qualidade de nossa aproximação. Antes disso vamos definir algumas classes utilitárias para nos auxiliar com as imagens e com a configuração de parâmetros.
Classe ImageUtils
Essa classe nos ajuda a converter objetos Image em BufferedImage, assim como salvar essas imagens em formato .jpg. Segue a classe ImageUtils:
import javax.swing.*; import java.io.*; import java.util.*; import java.awt.*; import java.awt.image.*; import com.sun.image.codec.jpeg.*; public class ImageUtils { public static BufferedImage imageToBufferedImage(Image img) { BufferedImage bi = new BufferedImage(img.getWidth(null), img.getHeight(null), BufferedImage.TYPE_INT_RGB); Graphics2D g2 = bi.createGraphics(); g2.drawImage(img, null, null); return bi; } public static void saveJPG(Image img, String filename) { BufferedImage bi = imageToBufferedImage(img); FileOutputStream out = null; try { out = new FileOutputStream(filename); } catch (java.io.FileNotFoundException io) { System.out.println("File Not Found"); } JPEGImageEncoder encoder = JPEGCodec.createJPEGEncoder(out); JPEGEncodeParam param = encoder.getDefaultJPEGEncodeParam(bi); param.setQuality(1.0f, false); //ou 0.8f encoder.setJPEGEncodeParam(param); try { encoder.encode(bi); out.close(); } catch (java.io.IOException io) { System.out.println("IOException"); } } public static Image loadJPG(String filename) { FileInputStream in = null; try { in = new FileInputStream(filename); } catch (java.io.FileNotFoundException io) { System.out.println("File Not Found"); } JPEGImageDecoder decoder = JPEGCodec.createJPEGDecoder(in); BufferedImage bi = null; try { bi = decoder.decodeAsBufferedImage(); in.close(); } catch (java.io.IOException io) { System.out.println("IOException"); } return bi; } }
Classe Params
Essa classe nos permite usar um arquivo externo para configurar alguns parâmetros do programa, como o número de polígonos, o nome da imagem, etc. A estrutura do arquivo Params.ini é mostrada após a classe:
import java.io.*; import java.util.HashMap; import java.util.Scanner; public class Params { static int VERTICES = 0; static int N_POLY = 0; static float MUTATION_RATE = 0.0f; static int PHOTO_INTERVAL_SEC = 0; static String TARGET_FILE; static boolean RANDOMIZE_START = false; static int MIN_ALPHA = 0; static int MAX_ALPHA = 0; public Params() { Scanner scanner = new Scanner(this.getClass().getResourceAsStream("params.ini")); HashMap<String, String> map = new HashMap<String, String>(); while (scanner.hasNext()) { map.put(scanner.next(), scanner.next()); } TARGET_FILE = map.get("target_file"); VERTICES = Integer.parseInt(map.get("vertices")); N_POLY = Integer.parseInt(map.get("n_poly")); MUTATION_RATE = Float.parseFloat(map.get("mutation_rate")); PHOTO_INTERVAL_SEC = Integer.parseInt(map.get("photo_interval_sec")); RANDOMIZE_START = Boolean.parseBoolean(map.get("randomize_start")); MIN_ALPHA = Integer.parseInt(map.get("min_alpha")); MAX_ALPHA = Integer.parseInt(map.get("max_alpha")); } } //fim da classe
Arquivo params.ini
Salve esse arquivo como 'params.ini', pois a classe Params irá procurar por esse nome ao tentar carregá-lo:
vertices 3 n_poly 80 mutation_rate 0.001f photo_interval_sec 30 target_file apple.jpg randomize_start true min_alpha 10 max_alpha 120
Classe PolygonColor
O objetivo agora é transformar um vetor de polígonos em um BinaryIntChromosome e encontrar uma maneira de comparar nossa aproximação com a imagem alvo. Para começar, vamos definir a classe PolygonColor, que representa um Polígono e sua cor RGBA. A classe é bem simples:
import java.awt.*; public class PolygonColor { protected Color color; protected Polygon polygon; public PolygonColor(){} public PolygonColor(Color color, Polygon polygon) { this.color = color; this.polygon = polygon; } }
Classe PolygonDecoder
Essa classe nos ajuda a decodificar um cromossomo em um vetor de polígonos, além de definir os valores mínimos e máximos que cada gene pode assumir. Esses cálculos dependem basicamente do número de polígonos utilizados e do número de vértices de cada polígono.
O método chromosomeToPolygons recebe o fenótipo de um cromossomo e a configuração dos polígonos, retornando um vetor de objetos PolygonColor. O método getChromosomeBounds recebe as dimensões do 'Canvas' e a configuração dos polígonos, nos retornando dois vetores. Esses vetores representam as variáveis de instância minVals e maxVals de um cromossomo, sendo utilizados uma única vez ao se instanciar a classe HillClimb:
import java.awt.Color; import java.awt.Polygon; public class PolygonDecoder { protected static PolygonColor[] chromosomeToPolygons(int[] data, int verts, int n, int colors) { int index = 0; int genes = 2 * verts + colors; int dim = genes * n; PolygonColor[] polygons = new PolygonColor[n]; int[] x = new int[verts]; int[] y = new int[verts]; int[] col = new int[colors]; for (int i = 0; i < dim; i += genes ) { //vertices int start = i; int end = start + verts; //x vertices int k = 0; for (int m = start; m < end; m++) x[k++] = data[m]; start = end; end = start + verts; //y vertices k = 0; for (int m = start; m < end; m++) y[k++] = data[m]; k = 0; //color for (int c = i + 2 * verts; c < i + 2 * verts + colors; c++) { col[k++] = data[c]; } PolygonColor pc = new PolygonColor(); pc.polygon = new Polygon(x, y, verts); pc.color = new Color(col[0], col[1], col[2], col[3]); polygons[index++] = pc; } return polygons; } protected static int[][] getChromosomeBounds(int w, int h, int verts, int n, int colors,int minAlpha, int maxAlpha) { int genes = 2 * verts + colors; int dim = genes * n; int[] minV = new int[dim]; int[] maxV = new int[dim]; for (int i = 0; i < dim; i += genes ) { int start = i; int end = start + verts; //x vertices for (int m = start; m < end; m++) maxV[m] = w; start = end; end = start + verts; //y vertices for (int m = start; m < end; m++) maxV[m] = h; //color for (int c = i + 2 * verts; c < i + 2 * verts + colors; c++) { //alpha component if (c == i + 2 * verts + colors - 1) { minV[c] = minAlpha; maxV[c] = maxAlpha; } //rgb component else maxV[c] = 255; } } return new int[][]{minV, maxV}; } } //fim da classe
Classe EvolveDraw
Essa é a classe que executa o nosso programa, tentando aproximar a imagem especificada em dentro do arquivo params.ini. Para obter bons resultados é fundamental usar parâmetros sensíveis, que funcionem bem em conjunto:
- vertices - Valores entre 3 e 6 parecem funcionar bem.
- n_poly - Dependendo da complexidade da imagem, valores entre 50 e 300 funcionam bem, porém o consumo de cpu aumenta bastante ao se utilizar um número grande de polígonos.
- mutation_rate - Esse é talvez o parâmetro mais sensível. Valores muito baixos ou muito altos não funcionam bem, uma valor razoável é 1.0/((vertices + 4) * n_poly).
- photo_interval_sec - O intervalo em segundos em que uma nova imagem da aproximação é salva. Caso não queira salvar as imagens, especifique um valor alto, ou comente a chamada ao método checkSnap e recompile.
- target_file - A imagem alvo, em formato .jpg.
- randomize_start - Especifica se o cromossomo inicial é randomizado ao se iniciar o algoritmo. Ao passar false, teremos um 'Canvas' inicialmente vazio. Passar true parece ajudar na velocidade de convergência, mas não estou certo disso.
- minAlpha, maxAlpha - O valor mínimo e máximo do componente alpha da cor, respectivamente. O normal aqui seria especificar 0 e 255, mas podemos cortar um pouco o espaço de busca ao diminuir esse range. Valores entre 0 e 10 para minAlpha e entre 100 e 150 para maxAlpha parecem funcionar bem.
A classe ficou um pouco grande, mas a idéia é bem simples: invocamos o método evolve em um laço infinito e decodificamos o cromossomo atual, que em seguida é desenhado na tela. Repare que implementamos a interface FitnessDelegate, onde novamente decodificamos o cromossomo em um vetor de polígonos, desenhamos esses polígonos em um buffer e fazemos uma comparação pixel-a-pixel com a imagem alvo.
Repare também que a imagem alvo é escaneada uma única vez no método loadTarget, e seus componentes RGBA são salvos em arrays separadas. Por fim, o método checkSnap cria uma imagem da tela e a salva no diretório atual, caso o intervalo especificado em photo_interval_sec tenha passado. Segue a classe EvolveDraw:
import java.awt.*; import java.awt.event.*; import java.awt.image.*; import com.sun.image.codec.jpeg.*; import javax.swing.*; import java.util.concurrent.*; import java.util.*; import java.io.*; public class EvolveDraw extends JPanel implements Runnable, FitnessDelegate { //polygons protected final int VERTICES; protected final int N_POLY; //nao mude COLOR_COMP! protected final int COLOR_COMP = 4; protected final int MIN_ALPHA; protected final int MAX_ALPHA; protected PolygonColor[] polygons; protected int gen = 0; protected Color bgColor = Color.white; //algorithm params protected float MUTATION_RATE; protected BinaryIntChromosome best; protected boolean RANDOMIZE_START; //images protected final String TARGET_FILE; protected int[] offImagePixels; protected BufferedImage targetImage; protected BufferedImage offImage; protected int[] targetPixels; protected int[] redTarget; protected int[] greenTarget; protected int[] blueTarget; protected int[] alphaTarget; protected int w; protected int h; //save drawings protected final int PHOTO_INTERVAL_SEC; protected long lastPhotoTime = 0L; public EvolveDraw() { new Params(); TARGET_FILE = Params.TARGET_FILE; VERTICES = Params.VERTICES; N_POLY = Params.N_POLY; MUTATION_RATE = Params.MUTATION_RATE; PHOTO_INTERVAL_SEC = Params.PHOTO_INTERVAL_SEC; RANDOMIZE_START = Params.RANDOMIZE_START; MIN_ALPHA = Params.MIN_ALPHA; MAX_ALPHA = Params.MAX_ALPHA; this.setDoubleBuffered(true); this.setBackground(bgColor); this.loadTarget(); } private void loadTarget() { this.targetImage = ImageUtils.imageToBufferedImage(ImageUtils.loadJPG(TARGET_FILE)); this.w = targetImage.getWidth(); this.h = targetImage.getHeight(); this.setPreferredSize(new Dimension(w, h)); this.offImage = new BufferedImage(w, h, BufferedImage.TYPE_INT_ARGB); this.targetPixels = new int[w * h]; this.offImagePixels = new int[w * h]; this.targetImage.getRGB(0, 0, w, h, targetPixels, 0, w); this.redTarget = new int[w * h]; this.greenTarget = new int[w * h]; this.blueTarget = new int[w * h]; this.alphaTarget = new int[w * h]; for (int i = 0; i < this.targetPixels.length; i++) { int pixel = targetPixels[i]; int alpha = (pixel >> 24) & 0xff; int red = (pixel >> 16) & 0xff; int green = (pixel >> 8) & 0xff; int blue = (pixel) & 0xff; this.redTarget[i] = red; this.greenTarget[i] = green; this.blueTarget[i] = blue; this.alphaTarget[i] = alpha; } } public void run() { int[][] bounds = PolygonDecoder.getChromosomeBounds(w, h, VERTICES, N_POLY, COLOR_COMP, MIN_ALPHA, MAX_ALPHA); HillClimb evolution = new HillClimb(bounds[0], bounds[1], this, MUTATION_RATE, null, RANDOMIZE_START); do { CountDownLatch signal = new CountDownLatch(1); evolution.signal = signal; new Thread(evolution).start(); try { signal.await(); } catch(InterruptedException ex) { ex.printStackTrace(); } best = evolution.getBest(); polygons = PolygonDecoder.chromosomeToPolygons(best.fenotype, VERTICES, N_POLY, COLOR_COMP); repaint(); gen++; checkSnap(); } while (true); } public void paintComponent(Graphics g) { super.paintComponent(g); if (best == null) return; ((Graphics2D) g).setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON); for (PolygonColor pc : polygons) { g.setColor(pc.color); g.fillPolygon(pc.polygon); } } public BufferedImage createImage(JPanel panel) { int wid = panel.getWidth(); int heig = panel.getHeight(); BufferedImage bi = new BufferedImage(wid, heig, BufferedImage.TYPE_INT_ARGB); Graphics2D g = bi.createGraphics(); g.setBackground(bgColor); g.clearRect(0, 0, wid, heig); panel.paint(g); g.dispose(); return bi; } protected void checkSnap() { long time = System.currentTimeMillis(); long interval = time - lastPhotoTime; if (interval >= PHOTO_INTERVAL_SEC * 1000L) { this.lastPhotoTime = time; ImageUtils.saveJPG(createImage(this), TARGET_FILE + gen + ".jpg"); } } public float getFitness(int[] fenotype) { Graphics2D g = this.offImage.createGraphics(); g.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON); g.setBackground(bgColor); g.clearRect(0, 0, w, h); PolygonColor[] polygons = PolygonDecoder.chromosomeToPolygons(fenotype, VERTICES, N_POLY, COLOR_COMP); for (PolygonColor pc : polygons) { g.setColor(pc.color); g.fillPolygon(pc.polygon); } g.dispose(); this.offImage.getRGB(0, 0, w, h, offImagePixels, 0, w); float diff = 0.0f; for (int i = 0; i < offImagePixels.length; i++) { int pixelOff = offImagePixels[i]; int alphaOff = (pixelOff >> 24) & 0xff; int redOff = (pixelOff >> 16) & 0xff; int greenOff = (pixelOff >> 8) & 0xff; int blueOff = (pixelOff) & 0xff; int alp = alphaTarget[i] - alphaOff; int red = redTarget[i] - redOff; int blue = blueTarget[i] - blueOff; int green = greenTarget[i] - greenOff; diff += alp * alp + red * red + blue * blue + green * green; } return 1.0f/(diff + 1.0f); } //executa public static void main (String[] args) { JFrame frame = new JFrame("Evolve Draw"); final EvolveDraw panel = new EvolveDraw(); frame.getContentPane().add(panel); frame.pack(); frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); frame.setVisible(true); frame.setResizable(false); Thread runnable = new Thread(panel); runnable.start(); } } //fim da classe
Usamos uma abordagem bem simples, mas que ilustra bem o poder de um algoritmo evolucionário. Uma idéia para tentar melhorar o programa seria usar um vetor de polígonos onde o número de vértices não é mantido fixo, isso provavelmente iria acelerar a convergência. Outra idéia consiste em 'injetar' os polígonos pouco a pouco, de acordo com alguma regra que leve em conta a taxa de aproximação.
Era isso, até o próximo post!
Nenhum comentário:
Postar um comentário