# Contour tracing in Processing

2010/07/09

I recently read the book Aarons code, and with that the thought of writing some contour tracing functions came up. When I also, a few days later got an idea for a project, I got to it. Do searches on Google pointed me in the direction of the blob extraction algorithm that OpenCV uses, and so I found “A linear-time component labeling algorithm using contour tracing technique”.

Lately I have also started looking into using NetBeans as an IDE for programming with the Processing library, so I decided that I would implement the algorithm in the paper in java, using Processing.

The code is provided below, and is provided as is. It can probably be optimized a bit, and/or rewritten to be better. But for now it works for me.

If you have any suggestions to changes, or you use it, please leave a comment so I can check it out.

/* * An implementation of * «A linear-time component labeling algorithm using contour tracing technique» * by Fu Chang, Chun-Jen Chen, and Chi-Jen Lu * * Written in Java for use with the Processing (www.processing.org) library. * * Code written by Greger Stolt Nilsen * (gregersn@gmail.com / http://gregerstoltnilsen.net) * Copyright 2010, Greger Stolt Nilsen * * Code is provided «as is», and no warrenty is given. Use at your own risk. * * This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see <http://www.gnu.org/licenses/>. */ /* * Create a new instance with: * ComponentFinder finder = new ComponentFinder(this, image); * where "image" is the PImage (or PGraphics) to be traced. * use the find()-function, to get all the contours in the contours arraylist. * Each contour is by itself an ArrayList of PVectors. * * render_blobs() will return a PImage object that is a rendering of all the * blobs in the traced image. * * The Image to be traced need to be black (0x000000) objects on white background. * So use the threshold-filter to get to that. * * Also, unless the outer border of pixles is white, the finder will hang. */ package ComponentFinder; import processing.core.*; import java.util.ArrayList; public class ComponentFinder { PApplet parent; public ArrayList contours; int[] inout; int[] L; PImage I; int C; // An array with the 8 direction coordinates (x1, y1, x2, y2... x8, y8) int cd[] = {1, 0, 1, 1, 0, 1, -1, 1, -1, 0, -1, -1, 0, -1, 1, -1 }; public ComponentFinder(PApplet p, PImage img) { parent = p; I = img; C = 1; L = new int[I.width*I.height]; } int getNumContours() { if(contours != null) return contours.size(); else return 0; } public int find() { // Initialize the blob map to zero. for(int i = 0; i < I.width*I.height; i++) { L[i] = 0; } // Make a new array list to store each contour. contours = new ArrayList(); C = 1; int pos = I.width; // Start analyzing the image at the second line I.loadPixels(); // Label the first line as blank pixels. for(int x = 0; x < I.width; x++) L[x] = -1; for(int y = 1; y < I.height; y++) { for(int x = 0; x < I.width; x++) { if(L[pos] == 0) // Only process unlabeled pixels { if(((I.pixels[pos]&0xffffff) != 0x000000)) { // White pixel L[pos] = -1; } else if(((I.pixels[pos]&0xffffff) == 0x000000)) { if((I.pixels[pos-I.width]&0xffffff) != 0x000000) { // If the pixel above is a white pixel, // then this is the start of an outer contour L[pos] = C; // Start tracing an outer contour contours.add(contourTrace(new PVector(x, y), 0, C)); C++; } if(((I.pixels[pos+I.width]&0xffffff) != 0x000000) && (L[pos+I.width] == 0)) { // If the pixel below is a white pixel, then it is the start of an // inner contour, and we get the id for the outer contour // then start tracing the inner contour int l; if(L[pos] != 0 ) l = L[pos]; else l = L[pos-1]; if(L[pos] != 0) L[pos] = l; contours.add(contourTrace(new PVector(x, y), 1, l)); } if(L[pos] == 0) if(L[pos-1] > 0) L[pos] = L[pos-1]; } } pos++; } } I.updatePixels(); return getNumContours(); } // Traces a countour at the given pixel S, // r is set to 0 for outer contours, and 1 for inner contours. // c is the label to give the contour ArrayList contourTrace(PVector S, int r, int c) { int next = 8; ArrayList cont = new ArrayList(32); PVector current = new PVector(); cont.add(S.get()); if(r == 0) // Outer contour next = Trace((PVector)cont.get(cont.size()-1), 7, c); else if(r == 1) // Inner contour next = Trace((PVector)cont.get(cont.size()-1), 3, c); if(next == 8) return cont; // The pixel is isolated. PVector T = new PVector(S.x + cd[next<<1], S.y + cd[(next<<1)+1]); cont.add(T.get()); next = Trace((PVector)cont.get(cont.size()-1), (next+6)%8, c); if(next == 8) return cont; while(true) { current.x = (float)((PVector)cont.get(cont.size()-1)).x + cd[(next<<1)%16]; current.y = (float)((PVector)cont.get(cont.size()-1)).y + cd[((next<<1)+1)%16]; next = Trace(current, (next+6)%8, c); // Check if we are back at start position if((current.x == S.x) && (current.y == S.y) && (current.x + cd[next<<1] == T.x) && (current.y + cd[(next<<1)+1] == T.y)) { return cont; } else { cont.add(current.get()); } } } int Trace(PVector P, int n, int c) { for(int i = 0; i < 8; i++) { // if pixel at position n+i is black, return n+i PVector ni = new PVector(P.x+cd[((i+n)%8)*2], P.y+cd[((i+n)%8)*2+1]); if((I.pixels[(int)(ni.y)*I.width+(int)(ni.x)]&0xffffff) == 0x000000) { L[(int)(ni.y)*I.width+(int)(ni.x)] = c; return (i+n)%8; } // if not, mark with a negative number else { if(L[(int)(ni.y)*I.width+(int)(ni.x)] == 0) L[(int)(ni.y)*I.width+(int)(ni.x)] = -1; } } return 8; // Should only happen for isolated pixels. } public PImage render_blobs() { PImage blobs = parent.createImage(I.width, I.height, PApplet.RGB); blobs.loadPixels(); parent.colorMode(PApplet.HSB); for(int i = 0; i < L.length; i++) { if(L[i] > 0) blobs.pixels[i] = parent.color(PApplet.map(L[i], 1, C, 0, 255), 255, 255);//|0xff000000; if(L[i] == -1) blobs.pixels[i] = parent.color(0, 0, 255); if(L[i] == -2) blobs.pixels[i] = parent.color(0, 0, 0); if(L[i] == 0) blobs.pixels[i] = parent.color(0, 0, 128); } blobs.updatePixels(); return blobs; } }

Hi, this work is very interesting. Can you provide an exemple of the code usage in processing? thanks.