Skip to content

Instantly share code, notes, and snippets.

@michael-nischt
Created July 18, 2012 20:08
Show Gist options
  • Save michael-nischt/3138545 to your computer and use it in GitHub Desktop.
Save michael-nischt/3138545 to your computer and use it in GitHub Desktop.
Sequential Labeling of Connected Components
/*
* 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();
}
}
/*
* 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);
}
}
/*
* 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;
}
}
/*
* 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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment