Algorithm for finding not connected areas (islands) on black white image

Question

I have image with black and white points(pixels). I need to create different sets for every different cluster of white pixels which contains x,y coordinates of that white point ( for example if I have black image with three not connected islands of white images I need to generate three sets with coordinates). Can anyone suggest me algorithm for this ?

Cells are connected if abs(x1-x2) <=1 && abs(y1-y2)<=1

If the image is black-and-white indeed, a more computationally efficient test for connected cells would be `is_not_connected = a[n,m]^a[n-1,m]; // meaning XOR, not exponentiation!`. Is your image B/W? — Arik G, Aug 10 '12 at 08:09

score 3 · Answer 1 · answered Aug 09 '12 at 05:05

3

Connected-component labeling algorithms are intended to isolate and enumerate such clusters

answered Aug 09 '12 at 05:05

MBo

77,366
5
53
86

score 2 · Answer 2 · answered Aug 08 '12 at 20:56

2

Perhaps the flood filling algorithm.

answered Aug 08 '12 at 20:56

Luchian Grigore

253,575
64
457
625

score 2 · Answer 3 · edited May 23 '17 at 10:28

Region growing, which should do the trick. That link is answering a different question, but the basic algorithm should fit your needs just right. You just need to pass another argument, which tells the number of the cluster. Start with 1 and whenever you enter a new cluster, increment this value.

This new argument will take the place of the 1 for foreground and 2 for background. This will give you the total number of all clusters, as well as all their locations.

score 0 · Answer 4 · answered Aug 08 '12 at 21:18

This uses flood filling algorithm. to find the number of connected regions import com.sun.corba.se.spi.presentation.rmi.IDLNameTranslator;

import javax.xml.transform.Source;
import java.awt.*;
import java.awt.font.ImageGraphicAttribute;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;

/**
 * Created by IntelliJ IDEA.
 * User: ruzbeh
 * Date: 6/29/12
 * Time: 12:58 AM
 * To change this template use File | Settings | File Templates.
 */
public class Solution {


    static int[][] img;

    static void compLabel(int i, int j, int m,int  n) {
        if(i<0 || j<0 ||i > n-1||j > n-1) return;
        if (img[i][j] == 1) {
            img[i][j] = m;
            compLabel(i - 1, j - 1, m,n);
            compLabel(i - 1, j, m,n);
            compLabel(i - 1, j + 1, m,n);
            compLabel(i, j - 1, m,n);
            compLabel(i, j + 1, m,n);
            compLabel(i + 1, j - 1, m,n);
            compLabel(i + 1, j, m,n);
            compLabel(i + 1, j + 1, m,n);
        }
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            int n = Integer.parseInt(br.readLine());
            img = new int[n][n];
            int label = 2;
            for (int i = 0; i < n; i++) {
                int j = 0;
                for (String str : br.readLine().split(" ")) {
                    int value = Integer.parseInt(str);

                    img[i][j] = value;

                    j++;
                }

            }
            for (int y = 0; y < n; y++)
                for (int x = 0; x < n; x++)
                    if (img[x][y] == 1) {
                        compLabel(x, y, ++label,n);
                    }

            System.out.println(label - 2);
        }
    }
}

Algorithm for finding not connected areas (islands) on black white image

4 Answers4