Union find in a 2d array (Java)

Question

I'm working on a program that can recognise shapes in an image, I have been able to change the image into binary values of 0/1, 0 = black, 1 = white, and then store these values into a 2d array of [height][width] indexes.

I'm trying to search through the array and union the white pixels based on if they are touching another white pixel. If they are then a counter will tally up each of the individual clusters of white pixels, so that the program can print out how many total clusters there are.

My code so far:

import javafx.stage.FileChooser;
import javax.imageio.ImageIO;
import javax.swing.*;
import javax.swing.text.html.ImageView;
import java.awt.*;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.Arrays;
import java.util.BitSet;


public class Image {
    ImageView myImageView;

    public static void main(String args[])
    {
        new Image();

    }

    public Image()
    {
        EventQueue.invokeLater(new Runnable() {
            @Override
            public void run() {
                try {
                    UIManager.setLookAndFeel(UIManager.getSystemLookAndFeelClassName());
                } catch (Exception ex) {
                    }
                JFrame frame = new JFrame("Image");
                frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);            //closes application properly
                frame.add(new ImagePane());
                frame.pack();
                frame.setLocationRelativeTo(null);
                frame.setVisible(true);
            }
        });
    }


public static class ImagePane extends JPanel {

        ImageView myImageView;

    private BufferedImage image;
    private BufferedImage bwImage;

    int width;
    int height;
    int wh = width * height;

    int g;
    int h = 1;

    BitSet bits = new BitSet(wh);

    boolean[][] visited;
    int[][] picture;

    int[][] arr;


    public ImagePane() {
        try {
            FileChooser fileChooser = new FileChooser();
            image = ImageIO.read(new File("C:/Users/Connor/Desktop/image.png"));
            this.image = image;

            bwImage = new BufferedImage(image.getWidth(), image.getHeight(), BufferedImage.TYPE_BYTE_BINARY);
            this.bwImage = bwImage;

            Graphics2D g2d = bwImage.createGraphics();
            g2d.drawImage(image, 0, 0, this);
            g2d.dispose();
        } catch (IOException ex) {
            ex.printStackTrace();
        }

        // PRINTS POS OF WHITE PIXELS
        int width = bwImage.getWidth();
            this.width = width;
        int height = bwImage.getHeight();
            this.height = height;

       int[][] arr = new int[height][width];
        DisjointSet ds = new DisjointSet();


        for (int y = 0; y < height; ++y) {
            for (int x = 0; x < width; ++x) {
                if (bwImage.getRGB(x, y) == 0xffffffff) {
                                                                    //bits.set((y * width + x));
                    System.out.print("1");
                    arr[y][x] = y+1;
                    int i = 1;
                    ds.makeSet(y);
                } else {
                    arr[y][x] = 0;
                    System.out.print("0");
                    ds.makeSet(0);
                }
            }
            System.out.println("");
            /*
          for(int d = 0; d < height; ++d) {
              ds.union(g, h);
              g++;
              h++;
          }
            */
        }
        System.out.println("");
        System.out.println(Arrays.deepToString(arr));           //print 2d array
        System.out.println("");



    } // END OF IMAGEPANE


    public int getBitIndex(int position)
    {
        bits.get(0, width*height);
        return position;
    }

    public Dimension getPreferredSize() {
        Dimension size = super.getPreferredSize();
        if (image != null) {
            size = new Dimension(image.getWidth() * 2, image.getHeight());
        }
        return size;
    }

    @Override
    protected void paintComponent(Graphics g) {
        super.paintComponent(g);
        if (image != null) {

            int x = (getWidth() - (image.getWidth() * 2)) / 2;
            int y = (getHeight() - (image.getHeight()));

            g.drawImage(image, x, y, this);
            x += image.getWidth();
            g.drawImage(bwImage, x, y, this);
        }
    }
} // end of JPanel//

} //end of class

and the disjoint set / union find:

import java.util.HashMap;
import java.util.Map;

public class DisjointSet {

private Map<Integer, Node> map = new HashMap<>();

class Node {
    int data;
    Node parent;
    int rank;
}

//Create a set with one element
public void makeSet(int data) {
    Node node = new Node();
    node.data = data;
    node.parent = node;
    node.rank = 0;
    map.put(data, node);
}

//Combine sets together - Union by rank
public boolean union(int data1, int data2) {
    Node node1 = map.get(data1);
    Node node2 = map.get(data2);

    Node parent1 = findSet(node1);
    Node parent2 = findSet(node2);

    if(parent1.data == parent2.data) {      //if part of the same set do nothing
        return false;
    }

    if(parent1.rank >= parent2.rank) {      //highest rank becomes parent
        parent1.rank = (parent1.rank == parent2.rank) ? parent1.rank +1 : parent1.rank;
        parent2.parent = parent1;
    } else {
        parent1.parent = parent2;
    } return true;
}

//find the rep of the set
public int findSet(int data) {
    return findSet(map.get(data)).data;
}

//find rep recursively and path compression
private Node findSet(Node node) {
    Node parent = node.parent;
    if(parent == node) {
        return parent;
    }
    node.parent = findSet(node.parent);
    return node.parent;
}
}

I haven't done anything like this before so i'm not entirely sure what to do, I think I need to check in all directions (N E S W) to see if a pixel matches, but I haven't had any luck getting that to work so far, so i'm wondering is there an easier way?

Answer 1

To demonstrate how to perform a Union-Find (to determine connected components) on a 2D array, the following test case was written (see below)

The node Id of each element is uniquely defined by the method getId() and is based on the row and col position (0, 1, 2..). The algorithm steps through the 2D array, starting at the top left (0,0). A union is made for it's East neighbour, and its South neighbour, if the components are the same (both a zero, or a one). Boundary conditions include not checking one of it's neighbours when iterating either the final row or final column. At the end, all neighbours will have been checked, and you are left with trees of both zeroes and ones. Your UF implementation will have to examin the white clusters created. I can post my implementation of UF if you are interested.

Your question related more to how to iterate the 2D matrix, which follows:

public class UnionFindArray {

@Test
public void test() {

    int a[][] = {{ 1, 0, 0, 1 }, {1, 0, 0, 1}, {0, 1, 1, 0}, {0, 1, 1, 0}};

    int nRows = a.length;
    int nCols = a[0].length;

    UnionFind uf = new QuickUnionFind(nRows*nCols);  // This is my implementation - you need to substitute yours

    // Examine all neighbours
    for (int row = 0; row < nRows; row++) {
        for (int col = 0; col < nCols; col++) {
            if (row < nRows-1 && a[row][col]==a[row+1][col])
                uf.union(getId(row,col,nCols), getId(row+1,col,nCols));
            if (col < nCols-1 && a[row][col]==a[row][col+1])
                uf.union(getId(row,col,nCols), getId(row,col+1,nCols));
        }
    }

    assertEquals(6, uf.getNumberOfTrees());  // True - there are 3 trees of zeros, and 3 trees of ones

}

private int getId(int row, int col, int nCols) {
    return row*nCols + col;
}

}

Interface:

public interface UnionFind {
    public void union(int p, int q);
    public boolean connected(int p, int q);
    public int getNumberOfTrees();
}

Implementation:

/**
 * Uses weighting and path compression to improve efficiency
 * The nodes will form trees; each connected node will point to 
 * a parent.  In this way, union is of order O(1).
 * To keep the find as close to O(1) as possible, the tree
 * must stay flat.
 * To keep it flat:
 * 1)  Use weighting: merge the SMALLER tree into the larger
 * 2)  Use path compression; during the find(root), use the
 * fact that you are traversing the tree to help flatten it.
 * @author Ian McMaster
 *
 */
public class QuickUnionFind implements UnionFind {

private final int N;        // Number of nodes in the forest
private final int id[];     // The parent of node n (a node in a tree)
private final int sz[];     // The number of nodes in a tree; allows weighted union to work (flatter tree)

/**
 * Nodes (zero based) are initialized as not connected
 * @param n Number of nodes
 */
public QuickUnionFind(int n) {
    N = n;
    id = new int[N];
    sz = new int[N];

    /*  Initialize all nodes to point to themselves.
     *  At first, all nodes are disconnected 
     */
    for (int i=0; i<N; i++) {
        id[i] = i;
        sz[i] = 1;  // Each tree has one node
    }
}

private int root(int i) {
    while (i != id[i]) {
        id[i] = id[id[i]];  // Path compression
        i = id[i];
    }
    return i;
}

@Override
public void union(int p, int q) {
    int i = root(p);
    int j = root(q);
    /*
     * Here we use weighting to keep the tree flat.
     * The smaller tree is merged to the large one
     * A flat tree has a faster find root time
     */
    if (sz[i] < sz[j]) {
        id[i] = j;
        sz[j] += sz[i];
    } else {
        id[j] = i;
        sz[i] += sz[j];
    }

}

@Override
public boolean connected(int p, int q) {
    return root(p) == root(q);
}

@Override
public int getNumberOfTrees() {
    Set<Integer> s = new HashSet<Integer>();
    for (int i=0; i<N; i++)
        s.add(id[i]);
    return s.size();
}

}