Package edu.cnu.mdi.sim.ga.triimage

Class ImageApproximationProblem

java.lang.Object
edu.cnu.mdi.sim.ga.triimage.ImageApproximationProblem
All Implemented Interfaces:
GAProblem<PolygonChromosome>
public final class ImageApproximationProblem extends Object implements GAProblem<PolygonChromosome>
A GAProblem that evolves a population of PolygonChromosome instances to approximate a target image using semi-transparent triangles.

Fitness

Color fitness is the negated mean squared error (MSE) between the rendered chromosome and target RGB channels: 

   fitness = −MSE
   MSE     = Σ [(ΔR² + ΔG² + ΔB²) / 255²] / (pixels × 3)

Following the GA convention of higher = better, a perfect match has fitness 0.0 and a maximally wrong solution has fitness -1.0. The alpha channel is excluded from the error metric — it affects appearance through blending but is not directly penalized.

ImageFitnessMode.LINE_AWARE blends 70% of this color error with 30% normalized Sobel luminance-edge error. This rewards candidates whose major contours align with the target even before their colors are exact.

Performance

Three optimizations keep fitness evaluation fast enough for interactive population sizes (≥ 100 individuals):

  1. Reduced fitness resolution. The target image is pre-scaled to FITNESS_W × FITNESS_H pixels at construction. All fitness evaluations render at this small size. The view calls PolygonChromosome.render(int, int) at full display resolution independently. Typical speedup: 6–10× over full-resolution evaluation.
  2. Thread-local render buffers. The BufferedImage and pixel array used during each fitness() call are allocated once per thread and reused for every subsequent call on that thread. This eliminates per-evaluation heap allocation and GC pressure. The buffers are stored in ThreadLocal fields, keeping this fitness implementation safe if a caller evaluates individuals concurrently. Typical speedup: 2–3× over per-call allocation.
  3. Integer MSE accumulation. The inner pixel loop accumulates squared channel differences as long integers and divides by 255² exactly once after the loop, avoiding per-pixel floating-point division. Typical speedup: 1.1–1.2×.

Usage


 BufferedImage target = ImageIO.read(new File("mona_lisa.png"));
 GAProblem<PolygonChromosome> problem = new ImageApproximationProblem(target, 50);

 GAOperators<PolygonChromosome> ops = new GAOperators<>(new TournamentSelection<>(5), new UniformBlendCrossover(),
 		new GaussianMutation(0.05), new ElitistReplacement<>(2));

 GeneticAlgorithmSimulation<PolygonChromosome> sim = new GeneticAlgorithmSimulation<>(problem, GAConfig.defaults(),
 		ops);

  • Field Details

    • FITNESS_W

      public static final int FITNESS_W
      Width in pixels used for fitness evaluation rendering.

      Reducing this value increases evaluation speed at the cost of a coarser fitness signal. Values in the range 60–100 work well for triangle counts up to ~100. The view always renders at the original image dimensions via PolygonChromosome.render(int, int).

      See Also:

    • FITNESS_H

      public static final int FITNESS_H
      Height in pixels used for fitness evaluation rendering.
      See Also:

  • Constructor Details

    • ImageApproximationProblem

      public ImageApproximationProblem(BufferedImage target, int numTriangles)
      Construct an image approximation problem for the given target image and triangle count.

      The target image is immediately scaled to FITNESS_W × FITNESS_H using bilinear interpolation and its pixel data is extracted into an int[] array. This pre-processing is done once at construction so that fitness(edu.cnu.mdi.sim.ga.triimage.PolygonChromosome) can operate purely on primitive arrays without touching the original image.

      Parameters:
      target - the image to approximate (non-null; any dimensions)
      numTriangles - number of triangles per chromosome (must be > 0)
      Throws:
      NullPointerException - if target is null
      IllegalArgumentException - if numTriangles is not positive

    • ImageApproximationProblem

      public ImageApproximationProblem(BufferedImage target, int numTriangles, ImageFitnessMode fitnessMode)
      Construct a problem with an explicit fitness metric.
      Parameters:
      target - target image
      numTriangles - number of triangles per chromosome
      fitnessMode - error metric to minimize

  • Method Details

    • fitness

      public double fitness(PolygonChromosome c)
      Compute fitness as the negated configured error between the rendered image and target.

      The chromosome is rendered into a thread-local BufferedImage at FITNESS_W × FITNESS_H pixels. Pixel differences are accumulated as integer squared errors (Fix 3) and normalized to [0, 1] after the loop. The result is negated so that higher fitness corresponds to a closer match.

      Fitness values lie in [-1, 0]:

      • 0.0 — perfect match
      • -1.0 — maximally wrong (every channel maximally wrong)

      This method is safe to call from multiple threads simultaneously because it uses only ThreadLocal buffers, and its one shared mutable field (maxSpanFraction) is volatile for safe cross-thread visibility. In the current implementation nothing ever writes maxSpanFraction after construction (it stays at its initial unconstrained value of 1.0), so it behaves as an effectively immutable configuration value today.

      Specified by:
      fitness in interface GAProblem<PolygonChromosome>
      Parameters:
      c - the chromosome to evaluate (non-null)
      Returns:
      fitness in [-1, 0], higher is better

    • getFitnessMode

      public ImageFitnessMode getFitnessMode()
      Returns:
      configured fitness metric

    • randomIndividual

      public PolygonChromosome randomIndividual(Random rng)
      Generate a random chromosome in which all gene values are drawn independently from Uniform(0, 1).
      Specified by:
      randomIndividual in interface GAProblem<PolygonChromosome>
      Parameters:
      rng - source of randomness (non-null)
      Returns:
      a new randomly initialized PolygonChromosome

    • initialPopulation

      public GAPopulation<PolygonChromosome> initialPopulation(int size, Random rng)
      Generate an initial population of size randomly initialized chromosomes.

      Each individual is produced by randomIndividual(Random) independently. The returned population is a SimpleGAPopulation backed by a fresh ArrayList.

      Specified by:
      initialPopulation in interface GAProblem<PolygonChromosome>
      Parameters:
      size - number of individuals (must be > 0)
      rng - source of randomness (non-null)
      Returns:
      a new population of size random individuals

    • getDisplayWidth

      public int getDisplayWidth()
      Return the original target image width in pixels.

      The view uses this to render chromosomes at display quality via PolygonChromosome.render(int, int).

      Returns:
      display width

    • getDisplayHeight

      public int getDisplayHeight()
      Return the original target image height in pixels.
      Returns:
      display height
      See Also:

    • getNumTriangles

      public int getNumTriangles()
      Return the number of triangles per chromosome for this problem.
      Returns:
      triangle count