Week12: Final Project

For my final project of this class, I worked on the first idea in my proposal.
This is an image drawing system with lines based on genetic algorithm.

Although the initial idea was building a system that draws a user’s portrait in real time, I changed my mind to make this system only with a still black&white image.
This is because I found that my sketch isn’t quick enough to draw one’s portrait in real-time.
So this project became rather experimental than artistic.

The algorithm of this system mainly consists of two parts:
1. Double Reproducing
2. Mutating and Growing

In the double reproducing part,
1. the system begins with 2ⁿ drawings and each drawing has 2 random lines. All lines have different positions, lengths, brightnesses and widths.
2. calculate the fitness of each drawing and select the best fitting one and the second best fitting one.
3. make a new drawing combining those two best drawings.
Then generate various different versions of it by transforming it. The extent of the transforming is decided by the transform rate that a user gives.
The total number of drawings has to be 2⁽ⁿ⁻¹⁾
4. iterate the process 2 – 3 until only 1 image remains.

I set n = 12 since I found that this number is appropriate for drawing the images that I gave as an input.
If the number is smaller than that, there aren’t enough lines to draw a portrait.
If it’s bigger than that, it took a long time to get the last image from the double reproducing stage and doesn’t work effectively in the next Mutating and Growing stage.
I also decided the maximum length of the lines as 50 and the transform rate also 50 via trials and errors.

What happens when the transform rate is not big enough

The code below is for the double reproducing(It’s a method of Scribbles class) :

reproduceDouble() {

    let children = new Scribbles(max, this.maxlen, this.transformRate, true);  // drawing

    let newN = this.n/2;  // the number of drawings for the new generation

    let parent = this.select();
    let mum = parent[0];
    let dad = parent[1];

    for(let i=0; i<newN; i++) {

      let childDrawing = new Linedrawing(pow(2, generation), this.maxlen, true);      
      let mumDrawing = []; // this.drawings[mum].lines;
      let dadDrawing = []; // this.drawings[dad].lines;

      let n = this.drawings[mum].lines.length;

      // Copy the mum drawing's lines
      for(let i=0; i<n; i++) {

        let p1x = this.drawings[mum].lines[i].p1.x;
        let p1y = this.drawings[mum].lines[i].p1.y;
        let p2x = this.drawings[mum].lines[i].p2.x;
        let p2y = this.drawings[mum].lines[i].p2.y;
        let b = this.drawings[mum].lines[i].b;
        let w = this.drawings[mum].lines[i].w;

        let p1 = new Point(p1x, p1y);
        let p2 = new Point(p2x, p2y);

        mumDrawing.push(new Line(p1, p2, b, w));
      }

      // Copy the dad drawing's lines
      for(let i=0; i<n; i++) {

        let p1x = this.drawings[dad].lines[i].p1.x;
        let p1y = this.drawings[dad].lines[i].p1.y;
        let p2x = this.drawings[dad].lines[i].p2.x;
        let p2y = this.drawings[dad].lines[i].p2.y;
        let b = this.drawings[dad].lines[i].b;
        let w = this.drawings[dad].lines[i].w;

        let p1 = new Point(p1x, p1y);
        let p2 = new Point(p2x, p2y);

        dadDrawing.push(new Line(p1, p2, b, w));
      }

      for(let i=0; i<n; i++) {
        childDrawing.lines.push(mumDrawing[i]);
        childDrawing.lines.push(dadDrawing[i]);
      }
      
      // Transform each child drawing a little bit except the first one
      if(i!=0) {
        childDrawing.transform(this.transformRate);
      }
       
      children.drawings.push(childDrawing);
      
    }

    this.drawings = children.drawings;
    this.n = newN;

  }

Next, in the mutating and growing stage.
1. mutate the image obtained from the double reproducing stage. Choose some lines based on the mutation rates and replace them with new random lines.
2. add new random lines; it doesn’t always happen though. The better the results of previous additions were, the more likely it happens.
3. if the new image has higher fitness than the current one, overwrite the new image to the current image.
4. iterate 1 – 3

Actually, my original plan was to decrease the mutation rates as the total fitness increases.
However, the changeable mutation rate really didn’t matter in the real sketch.
Instead, I found that the mutation rate needs to be less than 0.005. If it’s bigger than this, the updating(overwriting) rarely happens.

Following code is for the mutating and growing (This is also a method of Scribble class) :

modifyAndGrow(growthSize) {

    let nextDrawing = new Linedrawing(pow(2, reproGen), this.maxlen, true);

    // Copy the current drawing
    let n = this.drawings[0].lines.length;
    for(let i=0; i<n; i++) {
      let p1x = this.drawings[0].lines[i].p1.x;
      let p1y = this.drawings[0].lines[i].p1.y;
      let p2x = this.drawings[0].lines[i].p2.x;
      let p2y = this.drawings[0].lines[i].p2.y;

      let b = this.drawings[0].lines[i].b;
      let w = this.drawings[0].lines[i].w;

      let p1 = new Point(p1x, p1y);
      let p2 = new Point(p2x, p2y);

        nextDrawing.lines.push(new Line(p1, p2, b, w));
    }
    
    let mutationRate;
    let gSize;
    let f = this.drawings[0].fitness;
    

    if(f < 0.8) {
      mutationRate = 0.001;
      gSize = growthSize;
    } else {
      mutationRate = 0.0005;
      gSize = growthSize/2;
    } 

    let isGrown;
    isGrown = nextDrawing.mutateAndGrow(mutationRate, gSize);

    background(255);
    nextDrawing.display();

    nextDrawing.calculateFitness();

    // if the new drawing is better fit to the original image than the current one...
    if(nextDrawing.fitness > f) {

      this.drawings[0] = nextDrawing;

      if(isGrown) { // Growing worked well...?
        goodGrowthNum++;
        totalGrowthAttempt++;
        goodGrowthRate = (goodGrowthNum/totalGrowthAttempt); // Update the growing chance rate
        console.log("Gen " + generation + ", Updating: f = " + nextDrawing.fitness + ", Size +" + gSize);
      } else { 
        console.log("Gen " + generation + ", Updating: f = " + nextDrawing.fitness);
      }
    } 

    // if the new drawing isn't better... 
    else {
      if(isGrown) {  // Growing didn't work well...?
        totalGrowthAttempt++;
        goodGrowthRate = (goodGrowthNum/totalGrowthAttempt);  // Update the growing chance rate
      }
    }
  }

 

The updating speed is getting slower as the fitness increases.
So far, the maximum fitness that I can get is about 0.87 even though I tried with different mutation rates and growth sizes.

A new reproduction algorithm might be needed to get a better result.

I tested my sketch with two images and followings are the original images and the drawing result:

Here is a video that shows the process of the drawing in a high speed!

Lastly, this is the actual sketch:

you can find the source code here.

 

+ Just because of my pure curiosity, I made another drawing sketch using a really simple algorithm (I doubt that I can say it’s genetic algorithm!) to compare it to my algorithm.
The sketch draws a single random line 1000 times in every generation. Then it chooses the one which has the highest fitness and stores it in an array.
Likewise, it can choose a line in every generation iterating the process.
However, it took even much longer time to draw and the quality wasn’t even that good.

Leave a Reply

Your email address will not be published. Required fields are marked *