Tag Archive > Processing

AnTrack

Ricki » 02 May 2009 » In Java, Processing, Uncategorized » No Comments

My friend Kenneth expressed some interest in giving Processing a spin. He is an engineering student and usually deals in C++.

The learing curve in Processing is extremely flat and if you have prior programming experience you will go from having an idea to an actual prototype in minutes. So we thought up a small project: A Processing sketch that could detect a wavy black line on a piece of paper and subsequently play a tone according to the lines y position.

The result was anTrack, it uses the Capture Library to read the bitmaps of a web cam and the Minim sound library to produce a sine wave. It works just fine and my friend was hooked on the simplicity of Processing, he actually wrote most of the implementations.

What to use this for? I have no idea, it resembles a 1979 sci-fi horror film sound effect or a Theremin. We thought about building some sort of a rack in lego mindstorm that would continously scroll a piece of paper infront of the camera. A seismographic reading turned into sound, I guess, but the main goal was to have a little fun with processing for a couple of hours and we achieved that just fine.

anTrack.pde

/*
* author: Kenneth Knudsen & Ricki Gregersen
* description: reads a line from a piece of paper using a webcam
*              and outputs a tone between 440 and 880 Hz
*              according to the lines y coordinate
*/
//use the minim sound library, included in processing 1.0
import ddf.minim.signals.*;
import ddf.minim.*;
import ddf.minim.analysis.*;
import ddf.minim.effects.*;

//CamModule instance for grapping a frame from the webcam
CamModule cam;
//SoundModule instance for outputting a sine wave at a specific frequence
SoundModule sound;
//TrackModule instance for translating a y coordinate to a frequency
TrackModule track;

void setup()
{
  size(640, 480);
  frameRate(30);
  //CamModule constructor takes an input of (PApplet, width to grap, height to grap and offset)
  //this means: we will grap 30x480 pixels from the webcam starting at 320 in the x direction
  cam = new CamModule(this, 30, height, 320);
  sound = new SoundModule(this);
  track = new TrackModule();
}

void draw()
{
  //get the bitmap from the webcam
  PImage frame = cam.bitmap();
  //process it and return the position of the line as a frequency
  float freq = track.processBitmap(frame);
  //feed the frequency to the soundModule
  sound.freq(freq);
  //present the frame grabbed from the webcam to the screen
  image(frame, 320, 0);
}
//remember to close the connection made to the soundcard
void stop()
{
  super.stop();
  sound.stop();
}

The CamModule:

import processing.video.*;

class CamModule
{

  private Capture cam;
  private PImage frame;
  private int w, h, offSet;

  CamModule(PApplet applet, int _w, int _h, int _o)
  {
    w = _w;
    h = _h;
    offSet = _o;
    String[] devices = Capture.list();
    //println(devices);
    //comment in the above line if you don't know which port your webcam is plugged into
    cam = new Capture(applet, width, height, devices[1]);
    frame = createImage(w, h, RGB);
  }

  public PImage bitmap()
  {
    //read the full image from the webcam and copy out the pixels needed
    if (cam.available()) {
        cam.read();
        frame.copy(cam, offSet, 0, w, h, 0, 0, w, h);
    }
    return frame;
  }
}

The SoundModule.pde

class SoundModule
{
  Minim m;
  AudioOutput dac;
  SineWave sine;

  SoundModule(PApplet a)
  {
    m = new Minim(a);
    dac = m.getLineOut(Minim.STEREO);
    sine = new SineWave(0, 0.5, dac.sampleRate());
    //it is all in the minim documentation which is quite good, but portamento means that there
    //will be no pause when changing from one frequency to another, instead there is a 200 ms slide from
    //the original tone to the new one.
    sine.portamento(200);
    dac.addSignal(sine);
  }

  void freq(float f)
  {
    //if a frequency is present, map it to a sine with Hz between 440 and 880 (an octave)
    if(f > 0)
    {
      f = map(f, 0.1, height, 440, 880);
    }
    else{
      f = 0;
    }
    sine.setFreq(f);
  }
  //again remenber to close the connection to the soundcard
  void stop()
  {
    m.stop();
    dac.close();
  }
}

The TrackModule.pde

class TrackModule
{

  private float th = 80; //brightness 0-255
  private int hh = 80; //percent 0-100

    TrackModule()
  {

  }

  float processBitmap(PImage bm)
  {
    int index;
    int hits;
    int successive_hits = bm.width * (hh / 100);

    /*  this is a sort of filter.
     we run through the pixels one horizontal line at the time
     if we find a pixel with a brightness below the threshold (th)
     we add a hit. So if 80 percent of a line is dark enought to
     trigger the filter we count that as a dark line spotted and we retun the
     y value were it was spotted.
     */

    for(int y = 0; y < bm.height; y++)
    {
      hits = 0;
      index = y * bm.width;
      for(int x = 0; x < bm.width; x++)
      {
        color c = bm.pixels[index + x];
        if( brightness(c) < th)
        {
          hits++;
          if(hits > successive_hits)
          {
            return y;
          }
        }
      }
    }
    return 0.0;
  }
}

There is an Applet here, I haven’t gone through the steps to make it work in a browser so the visitor
can use their own web cam, it’s mostly done so you can get the source code.

Continue reading...

Tags: , , ,

Kruskals algorithm in Processing

Ricki » 18 March 2009 » In Processing, Uncategorized » 2 Comments

Minimum Spanning Tree (red path)

Minimum Spanning Tree (red path)

I was reading Robert Sedgewicks “Algorithms in Java” and had skipped to part 5 concerning Graphs.

I know I ought not skip portions of a book concerning something that difficult, but 130 pages into the first part I needed to see where all this theory was going.

I stumbled over the Kruskal/Prims/Dijkstra algorithms and the visual representations caught my eye. They were really simple to look at but you could sense there was some sort of genius system behind it. That is one of my favorite reasons for opening up Processing and start sketching.

A few need to know things on Graphs:

Thinking in 2 dimensions, a Graph consists of a number of points on a surface. A point is called a vertex and each vertex can be connected to a number of other vertices. Such a connection between 2, or more, vertexes is called and edge.

simple graph

simple graph

There are many different types of Graphs: directed graphs, where directed means, that two vertices that are connected also states which direction you can travel from one vertex to the other, e.g. V1 ->V2 means you can go from V1 to V2 but not the other way. Undirected Graphs is then, of course, a graph where it does not matter which way you travel. Directed and undirected graphs can also be weighted or not. This means that “it takes a certain amount of energy” to travel from one vertex to another.

simple directed weighted graph

simple directed weighted graph

This comes clear when we think back to the 2 dimensions and that a graph can be points/vertices on a surface. If we were looking to connect three vertices using the least amount of “energy”  and vertex v1 is situated a distance of 9 meters from vertex V2 and vertex V1 is situated 4 meters from vertex V3 and vertex V2 is situated 3 meters from vertex V3, we would connect them as such: V1-V3-V2

Euclidian weighted graph

Euclidian weighted graph

Minimum Spanning Tree

Having scratched the surface of Graphs it is now a bit easier to understand what a minimum spanning tree is.

In the “Algorithms in Java” book the minimum spanning tree(MST) is defined as:

In a weighted graph, find a minimum-weight set of edges that connects all the vertices.

It is also defined as:

A minimum spanning tree of a weighted graph is a spanning tree whose weight(the sum of weights of it’s edges) is no larger than the weight of any other spanning tree.

It is good to dwell on that last definition for a second. It says that there might be lots and lots of spanning trees in a graph, and that some of them can have the same combined weight. According to the definition this is okay, the more the merrier, as long as it is still a minimum spanning tree.

This means, that from any vertex you should be able to travel to any other vertex, not necessarily along the shortest path, that is another algorithm altogether, but all the vertices is connected in a way that adds up to the combined shortest edges.

There are quite a few algorithms that strives to solve this problem, two of them is Prim’s and Kruskal’s algorithm.

Prim’s algorithm, it goes under many different names as it has been discovered and implemented by more than one person, but that is a story for Wikipedia and not this very short post.

Prim’s algorithm looks at a graph, selects an arbitrary vertex and starts testing all the edges connected to this vertex, once it finds the shortest edge, the edge with the smallest weight, it adds this to the tree, e.g. V12-V65. It then goes on to look for the next shortest edge from either V12 or V65. Before the algorithm can add another edge it must test that it is not creating a cycle. A cycle is if V1-V2 and V2-V3 and V3-V1 is connected, meaning you could start out from V1 and then end up in V1 again. A cycle is redundant in a minimum spanning tree and not desired.

If the algorithm consists of N vertices the MST will be finished when N-1 edges has been added to the MST, regarding no cycles has been made.

The Kruskla’s algorithm works in a very similar way, the main difference is that Kruskal’s algorithm starts at the first vertex, i.e V1 and then works it’s way outwards from that.

This means that an identical graph will yield the same MST each time when using Kruskal and that Prim’s can yield different MST’s depending on which vertex was set as the starting point(remember the second definition…)

Here is the Processing code for the sketch shown at the beginning

There are 101 vertices, this adds up to 5050 possible edges, they are drawn in using a transparant white. The MST will be the red path as in the picture in the start of the post.

Continue reading...

Tags: , , ,