二维数组中的联合查找(Java)

Question

我正在开发一个可以识别图像形状的程序，我已经能够将图像转换为0/1，0=黑色，1=白色的二进制值，然后将这些值存储到高度索引的二维数组中。

我尝试在数组中搜索，并根据它们是否接触到另一个白像素来合并白像素。如果是，那么计数器将对每个单独的白色像素簇进行计数，这样程序就可以打印出总共有多少簇。

到目前为止我的代码如下：

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

和不相交的集合/并集查找：

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;
}
}

我以前没有做过这样的事情，所以我不完全确定该怎么做，我想我需要检查所有方向(N，E，S，W)，看看像素是否匹配，但到目前为止，我还没有任何运气让它工作，所以我想知道有没有更简单的方法？

Answer 1

为了演示如何在2D数组上执行联合查找(以确定连接的组件)，编写了以下测试用例(见下文)

每个元素的节点Id由方法getId()唯一定义，并基于行和列的位置(0，1，2..)。该算法从左上角(0,0)开始逐步执行二维数组。如果两个组件相同(都是0或1)，则为其东部邻居和南部邻居创建并集。边界条件包括在迭代最后一行或最后一列时不检查它的邻居之一。最后，所有邻居都将被检查，剩下的树既有0也有1。您的UF实现将必须检查创建的白色簇。如果你感兴趣，我可以发布我的UF实现。

您的问题更多地涉及如何迭代2D矩阵，如下所示：

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;
}

}

接口：

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

实施：

/**
 * 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();
}

}