DynamicProgramming

Download DynamicProgramming / Read the documentation / DynamicProgramming source on Github

Processing SeamCarving

An example of SeamCarving, one application of DynamicProgramming implemented in the library.

A library implementing the Dynamic Programming optimization for Processing along with a number of applications of it. Dynamic Programming is a technique for optimizing certain kinds of recursive operations by “memoization”, progressively storing the results of operations in a grid of cells so that recursion becomes unnecssary.

This library includes implementations of a series of techniques that take advantage of Dynamic Programming: seam carving, sequence aligment, and longest common subsequence.

Application: Seam Carving

Seam carving is a technique for resizing an image by removing or adding content in the least important parts of the image.

// import the library
import dynamicprogramming.*;

// declare our SeamCarving object
// and an ArrayList to store the points
// of the current seam
SeamCarving carver;
ArrayList<PVector> seam;

// the output image,
// an image representing the energy,
// and an image representing the score for each pixel
PImage img, energyImage, scoreImage;

void setup() {
 img = loadImage("twins.small.jpg");
 
 size(img.width*3,img.height);
 
 println(img.width + " " + img.height);
 
 carver = new SeamCarving(this, img);
 seam = carver.findMinSeam();
 
 println("calculating energy image");
 energyImage = carver.getGradientImage();
 
 println("calculating score image");
 scoreImage = carver.getScoreImage();

 image(scoreImage,img.width,0);

}

boolean newSeam = false;

void draw() {
  // draw a white "background"
  // behind the final result (since it shrinks)
  fill(255);
  noStroke();
  rect(energyImage.width*2, 0, energyImage.width, img.height);

  image(energyImage, 0, 0);
  image(img, energyImage.width*2, 0);

  if(newSeam){
    pushMatrix();
    translate(energyImage.width,0);
    // draw a white "background"
    // behind the energy image (since it also shrinks)
    fill(255);
    noStroke();
    rect(0, 0, energyImage.width, img.height);
    
    // draw the score image
    image(scoreImage, 0,0 );
    
    // draw the next seam to remove
    stroke(255,0,0);
    for(PVector p : seam){
      point(p.x, p.y);
    }
    popMatrix();
    newSeam = false;
  }
}

void keyPressed(){
  img.loadPixels();
  img = carver.removeColumn();
  img.updatePixels();
  
  carver.setImage(img);
  seam = carver.findMinSeam();
  newSeam = true;
  
  println("calculating score image");
  scoreImage = carver.getScoreImage();
}