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

Question

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

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

到目前为止我的代码:

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) 开始逐步遍历 2D 数组。如果组成部分相同(均为 0 或 1)，则为其东邻和南邻建立并集。边界条件包括在迭代最后一行或最后一列时不检查其邻居之一。 最后，所有邻居都将被检查，剩下的树都是由 0 和 1 组成的。您的 UF 实现必须检查创建的白色簇。如果您有兴趣，我可以发布我的 UF 实现。

您的问题更多地与如何迭代二维矩阵有关，如下所示:

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

}