如何在OpenCV中找到二值骨架图像的端点？

Question

我有一个由二进制像素构成的骨架，像这样：

我想找到这个骨架的端点坐标（在这个例子中有四个端点），如果可以的话，想用Open CV来实现。

效率很重要，因为我需要实时分析很多这样的骨架，且同时还要做很多其他事情。

（注意，抱歉上面的截图有些变形，但我正在处理的是一个8连通的骨架。）

Answer 1

这是我用Python写的代码：

import cv2
import numpy as np


path = 'sample_image.png'
img = cv2.imread(path, 0)

# Find positions of non-zero pixels
(rows, cols) = np.nonzero(img)

# Initialize empty list of coordinates
endpoint_coords = []

# Loop through all non-zero pixels
for (r, c) in zip(rows, cols):
    top = max(0, r - 1)
    right = min(img.shape[1] - 1, c + 1)
    bottom = min(img.shape[0] - 1, r + 1)
    left = max(0, c - 1)

    sub_img = img[top: bottom + 1, left: right + 1]
    if np.sum(sub_img) == 255*2:
        endpoint_coords.append((r,c))

print(endpoint_coords)

Answer 2

虽然有点晚，但这对大家可能还是有用的！

其实有一种方法可以做到和@rayryeng建议的一样，但我们可以用openCV自带的功能来实现！这样做会更简单，而且可能会更快（特别是如果你用的是Python，就像我一样）。这个方法和这个链接里的解决方案是一样的。

简单来说，我们想找到那些值不为零的像素，并且它们旁边有一个不为零的邻居。所以我们用openCV的filter2D函数，把骨架图像和我们自己制作的一个特殊的“内核”进行卷积。我刚刚学会了卷积和内核的概念，这个页面对理解这些东西非常有帮助。

那么，什么样的内核可以用呢？可以试试这个：

[[1, 1,1],
 [1,10,1],
 [1, 1,1]]? 

然后，在应用这个内核后，任何值为11的像素就是我们想要的！

这是我使用的代码：

def skeleton_endpoints(skel):
    # Make our input nice, possibly necessary.
    skel = skel.copy()
    skel[skel!=0] = 1
    skel = np.uint8(skel)

    # Apply the convolution.
    kernel = np.uint8([[1,  1, 1],
                       [1, 10, 1],
                       [1,  1, 1]])
    src_depth = -1
    filtered = cv2.filter2D(skel,src_depth,kernel)

    # Look through to find the value of 11.
    # This returns a mask of the endpoints, but if you
    # just want the coordinates, you could simply
    # return np.where(filtered==11)
    out = np.zeros_like(skel)
    out[np.where(filtered==11)] = 1
    return out

补充一下：这个技巧对某些骨架图像可能不适用，比如缺少“楼梯”模式的情况：

000
010
110

更多信息请查看评论。

Answer 3

根据你在个人资料中提到的问题和答案标签，我猜测你想要的是C++的实现。当你对一个物体进行骨架化处理时，这个物体的厚度应该是1个像素。因此，我建议你先找到图像中那些非零的像素，然后在这个像素周围的8个相邻像素中进行搜索，数一数那些非零的像素。如果这个数量只有2，那么这个像素就可能是骨架的一个端点。需要注意的是，我会忽略边界，以免超出范围。如果数量是1，那就是一个孤立的噪声像素，我们应该忽略它。如果数量是3个或更多，那就说明你正在检查骨架的某个部分，或者你处于多个线条相连的地方，所以这也不应该是一个端点。

老实说，我想不出其他算法来检查这些骨架像素是否符合这个标准……所以复杂度将是O(mn)，其中m和n分别是你图像的行和列。对于图像中的每个像素，检查8个相邻像素的时间是固定的，这对你检查的所有骨架像素都是一样的。不过，这个过程肯定是亚线性的，因为你图像中大多数像素都是0，所以大部分时间都不会进行8个像素的检查。

因此，我建议你尝试一下，假设你的图像存储在一个叫im的cv::Mat结构中，它是一个单通道（灰度）图像，类型为uchar。我还会把骨架端点的坐标存储在一个std::vector类型中。每次我们检测到一个骨架点时，会同时向这个向量中添加两个整数——检测到的骨架端点的行和列。

// Declare variable to count neighbourhood pixels
int count;

// To store a pixel intensity
uchar pix;

// To store the ending co-ordinates
std::vector<int> coords;

// For each pixel in our image...
for (int i = 1; i < im.rows-1; i++) {
    for (int j = 1; j < im.cols-1; j++) {

        // See what the pixel is at this location
        pix = im.at<uchar>(i,j);

        // If not a skeleton point, skip
        if (pix == 0)
            continue;

        // Reset counter
        count = 0;     

        // For each pixel in the neighbourhood
        // centered at this skeleton location...
        for (int y = -1; y <= 1; y++) {
            for (int x = -1; x <= 1; x++) {

                // Get the pixel in the neighbourhood
                pix = im.at<uchar>(i+y,j+x);

                // Count if non-zero
                if (pix != 0)
                    count++;
            }
        }

        // If count is exactly 2, add co-ordinates to vector
        if (count == 2) {
            coords.push_back(i);
            coords.push_back(j);
        }
    }
}

如果你想在完成后显示坐标，只需检查这个向量中的每一对元素：

for (int i = 0; i < coords.size() / 2; i++)
    cout << "(" << coords.at(2*i) << "," coords.at(2*i+1) << ")\n";

---

为了完整起见，这里还有一个Python的实现。我使用了一些numpy的函数来简化操作。假设你的图像存储在img中，这也是一幅灰度图像，并且导入了OpenCV库和numpy（即import cv2，import numpy as np），以下是等效的代码：

# Find row and column locations that are non-zero
(rows,cols) = np.nonzero(img)

# Initialize empty list of co-ordinates
skel_coords = []

# For each non-zero pixel...
for (r,c) in zip(rows,cols):

    # Extract an 8-connected neighbourhood
    (col_neigh,row_neigh) = np.meshgrid(np.array([c-1,c,c+1]), np.array([r-1,r,r+1]))

    # Cast to int to index into image
    col_neigh = col_neigh.astype('int')
    row_neigh = row_neigh.astype('int')

    # Convert into a single 1D array and check for non-zero locations
    pix_neighbourhood = img[row_neigh,col_neigh].ravel() != 0

    # If the number of non-zero locations equals 2, add this to 
    # our list of co-ordinates
    if np.sum(pix_neighbourhood) == 2:
        skel_coords.append((r,c))

要显示端点的坐标，你可以这样做：

print "".join(["(" + str(r) + "," + str(c) + ")\n" for (r,c) in skel_coords])

---

小提示：这段代码未经测试。我在这台机器上没有安装C++的OpenCV，所以希望我写的能正常工作。如果编译不通过，你可以把我写的内容翻译成正确的语法。祝你好运！