Sequential Labeling of Connected Components

Conected4Test.java

/*
 * Copyright (C) 2007/2011 Michael Nischt
 *
 * 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 2
 * 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, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

import static java.util.Arrays.deepEquals;
import static org.junit.Assert.assertTrue;
import org.junit.Test;

/**
 *
 * @author Michael Nischt
 */
public  class Conected4Test {

    private final int[][][] images = {
        {
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 1, 0, 1, 0, 2, 2, 2, 0, 3, 3, 3, 0},
            {0, 1, 0, 1, 0, 2, 0, 0, 0, 3, 0, 3, 0},
            {0, 1, 0, 1, 0, 2, 2, 2, 0, 3, 3, 3, 0},
            {0, 1, 0, 1, 0, 0, 0, 2, 0, 3, 0, 3, 0},
            {0, 1, 1, 1, 0, 2, 2, 2, 0, 3, 0, 3, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
        },
        {
            {0, 0, 0, 0, 0, 0, 0},
            {0, 1, 1, 1, 1, 1, 0},
            {0, 1, 0, 0, 0, 1, 0},
            {0, 1, 0, 2, 0, 1, 0},
            {0, 1, 0, 0, 0, 1, 0},
            {0, 1, 1, 1, 1, 1, 0},
            {0, 0, 0, 0, 0, 0, 0}
        },
        {
            {1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1},
            {1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1},
            {1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1},
            {1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1},
            {1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1},
            {1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1}
        },
        {
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 2, 2, 0, 0, 2, 2, 0},
            {0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 2, 2, 2, 2, 0, 0},
            {0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 2, 2, 2, 2, 0, 0, 0},
            {0, 0, 1, 1, 1, 1, 0, 0, 0, 2, 2, 2, 0, 0, 3, 3, 0},
            {0, 1, 1, 1, 0, 0, 4, 4, 0, 0, 0, 2, 2, 2, 0, 0, 0},
            {0, 0, 1, 1, 0, 0, 0, 0, 0, 5, 5, 0, 0, 0, 6, 6, 0},
            {0, 0, 0, 0, 0, 0, 5, 5, 5, 5, 0, 0, 6, 6, 6, 6, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
        },            
    };

    @Test
    public void testUSA() {
        testExample(0);
    }

    @Test
    public void testInner() {
        testExample(1);
    }
    
    @Test
    public void testSnake() {
        testExample(2);
    } 
    
    @Test
    public void testWikiSample() {
        testExample(3);
    }     

    private void testExample(int i) {
        Image image = new Image(images[i]);
        Connected4 labeler = new Connected4(image.getWidth(), image.getHeight());
        int n = labeler.label(image);

        boolean eq;
        eq = deepEquals(image.pixels, images[i]);
        assertTrue("Labeled Images is not as expected", eq);
        if (!eq) {
            System.out.println("Actual");
            print(image.pixels);
            System.out.println("Expceted");
            print(images[i]);
        }
    }

    private static void print(int[][] image) {
        for (int[] line : image) {
            for (int pixel : line) {
                System.out.printf("%4d ", pixel);
            }
            System.out.println();
        }
        System.out.println();
    }
}

Connected4.java

/*
 * Copyright (c) 2007/2011 Michael Nischt
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 
 * Redistributions of source code must retain the above copyright notice,
 * this list of conditions and the following disclaimer.
 * 
 * Redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution.
 * 
 * Neither the name of the project's author nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 */

import static java.lang.Math.min;
import static java.lang.Math.round;
import static java.util.Arrays.fill;

/**
 * Allows connected component labeling with 4-side-connectivity for a fixed size 2D grid. 
 * The algorithm performs a specialized union-find based a L-shaped window.
 * 
 * @author Michael Nischt
 */
public final class Connected4 {

    private final int width, height;
    // quick-union - find temporary variables
    private final int[] map;
    private int count;

    /**
     * Creates a new instance for a 2D grid of the specified size
     * @param width number of columns
     * @param height number of rows
     */
    public Connected4(int width, int height) {
        if(width <= 0 || height <= 0) {
            throw new IllegalArgumentException("Grid must have at least a single cell");
        }
        this.width = width;
        this.height = height;        
        // maximum possible unique labels
        this.map = new int[round(width * height / 2.0f) + 1];
    }
 
    /**
     * Labels all components from 1 to n, where n the number if isolated components. 
     * All elements of a connected component will share the same label.
     * @param labels the input grid 
     * @return the number of individual components
     */
    public int label(Labels labels) {        
        // reset temp variables
        if(count > 0) {
            fill(map, 0);            
        }
        count = 0;
        
        // move L-shape (top, left, center) window along the image 
        // and perform a quick-union find for matching labels 
        int top = 0 , left = 0;
        for(int x=0, y=0; x<width; x++) {                                
            int label = labels.get(x, y) != 0 ? apply(top, left) : 0;
            labels.set(x, y, label);
            left = label;
        }
        for(int y=1; y<height; y++) {            
            left = 0;
            for(int x=0; x<width; x++) {
                top = labels.get(x, y-1);
                int label = labels.get(x, y) != 0 ? apply(top, left) : 0;
                labels.set(x, y, label);
                left = label;
            }
        }

        // unifying the list of labels
        int num = 0;
        for (int i = 1; i <= count; i++) {
            if (i != map[i]) {
                map[i] = map[ map[i]];
            } else {
                num++;
                map[i] = num;
            }
        }
        count = num;
         
        // updating the labels to the new unified values
        for (int y = 0; y < height; y++) {
            for(int x=0; x<width; x++) { 
                labels.set(x, y, map[labels.get(x, y)]);
            }
        }
        return num;
    }  
    
    private int apply() {
        ++count;
        return map[count] = count;
    }

    private int apply(int a) {
        return (a != 0) ? map[a] : apply();
    }

    private int apply(int a, int b) {
        if (a != 0 && b != 0) {
            return apply(union(a, b));
        } else if (a != 0) {
            return apply(a);
        } else if (b != 0) {
            return apply(b);
        } else {
            return apply();
        }
    }

    private int union(int a, int b) {
        int valueMin = min(a, b);
        int labelMin = min(map[a], map[b]);        
        return map[a] = map[b] = min(labelMin, valueMin);
    }
}

Image.java

/*
 * Copyright (c) 2007/2011 Michael Nischt
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 
 * Redistributions of source code must retain the above copyright notice,
 * this list of conditions and the following disclaimer.
 * 
 * Redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution.
 * 
 * Neither the name of the project's author nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 */

/**
 *
 * @author Michael Nischt
 */
final class Image implements Labels {
    final int[][] pixels;

    Image(int[][] pixels) {
        this.pixels = pixels.clone();
        for (int i = 0; i < this.pixels.length; i++) {
            this.pixels[i] = this.pixels[i].clone();
        }        
    }

    int getWidth() {
        return pixels[0].length;
    }

    int getHeight() {
        return pixels.length;
    }

    @Override
    public int get(int x, int y) {
        return pixels[y][x];
    }

    @Override
    public void set(int x, int y, int label) {
        pixels[y][x] = label;
    }    
}

Labels.java

/*
 * Copyright (c) 2007/2011 Michael Nischt
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 
 * Redistributions of source code must retain the above copyright notice,
 * this list of conditions and the following disclaimer.
 * 
 * Redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution.
 * 
 * Neither the name of the project's author nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 */

/**
 * Accessor interface for integer labels in a 2D grid.
 * 
 * @author Michael Nischt
 */
public interface Labels {
    
    /**
     * Returns the label at the [x, y] location
     * @param x column index
     * @param y row index
     * @return the label at the specified location
     */
    int get(int x, int y);
    
    /**
     * Updates the label at the [x, y] location
     * @param x column index
     * @param y row index
     * @param label the new label for the specified location
     */
    void set(int x, int y, int label);
}