基于骨架图像构建角点节点连通图的技术方案问询

目标 #

• 处理包含多条交叉曲线的骨架化图像
• 用Harris角点检测算法识别角点
• 依据角点在原始图像中的连通关系，将角点构建为图结构

前两步通过scikit-image的skeletonize()和corner_harris()即可轻松完成，但第三步遇到了瓶颈。

以下是处理黑底白线图像的代码，最终得到存储检测角点的KDTree：

import skimage.io as io
from skimage.morphology import skeletonize
from skimage.color import rgb2gray
from skimage.feature import corner_harris, corner_peaks
from scipy.spatial import KDTree

# 加载图像（约1500*900像素）并转为灰度二值图
testimage = io.imread("imagepath.png")[:,:,:3]
testimage = (rgb2gray(testimage) > 0)

# 骨架化并检测角点
skel = skeletonize(testimage)
coords = corner_peaks(corner_harris(skel), min_distance=5, threshold_rel=0.01)

# 生成KDTree并筛选距离范围内的候选连接对
# 避免遍历所有可能的点对
tree = KDTree(coords)
pairs = list(tree.query_pairs(25))    # 距离阈值为经验值

（注：检测到的角点已叠加在测试原图上，可见角点基本对应骨架的交叉、端点等关键位置）

核心问题 #

如何从候选连接对pairs中筛选出在原始骨架图像中真正连通的点对？

• 若线条为直线，可直接检查两点间直线下方的像素，但多数线条是曲线，此方法无效
• 若角点完全位于骨架线上，可从角点出发沿线条遍历到另一节点，但实际角点存在偏移，无法直接使用
• 尝试过active_contour()函数，但参数调优难度大，且容易出现拟合不全导致大量漏检

当前思路 #

1. 将所有角点吸附到最近的骨架白色像素上
2. 检查每个角点周围5x5邻域，确定骨架线条从角点延伸的方向
3. 模拟海龟绘图的方式沿方向遍历线条，直至到达另一节点

但怀疑计算机视觉领域已有成熟方案，希望找到更简便的实现方式。

解决方案推荐 #

方法1：骨架最短路径验证法 #

利用骨架图像的连通性，结合最短路径算法验证候选点对的连通性，适配曲线场景：

1. 角点吸附：先把偏移的角点吸附到最近的骨架像素上，解决角点不在骨架上的问题
2. 路径验证：对每个候选点对，计算骨架上两点间的最短路径，若路径存在且长度合理，则判定为有效连接

可以借助skimage.graph.route_through_array实现最短路径计算，示例代码如下：

import numpy as np
from scipy.ndimage import distance_transform_edt
from skimage.graph import route_through_array

# 角点吸附到最近的骨架像素
def snap_to_skeleton(corner_coord, skel_img):
    dist_transform = distance_transform_edt(1 - skel_img)
    x, y = corner_coord
    # 扩大搜索范围确保找到骨架
    search_window = dist_transform[max(0, x-20):min(skel_img.shape[0], x+20), 
                                   max(0, y-20):min(skel_img.shape[1], y+20)]
    min_dist_pos = np.unravel_index(search_window.argmin(), search_window.shape)
    snapped_x = max(0, x-20) + min_dist_pos[0]
    snapped_y = max(0, y-20) + min_dist_pos[1]
    return (snapped_x, snapped_y)

# 处理所有角点
snapped_coords = [snap_to_skeleton(coord, skel) for coord in coords]

# 筛选有效连接对
valid_pairs = []
skel_inverted = 1 - skel.astype(int)  # 适配路径函数的0值路径要求
for (i, j) in pairs:
    start = snapped_coords[i]
    end = snapped_coords[j]
    try:
        # 计算两点间的骨架路径
        path, cost = route_through_array(skel_inverted, start, end, fully_connected=True)
        # 过滤过长的无效路径（阈值可根据实际调整）
        if cost <= 25 * 1.5:
            valid_pairs.append((i, j))
    except:
        # 无有效路径则跳过
        continue

方法2：直接从骨架提取节点与连接 #

跳过Harris角点检测的偏移问题，直接从骨架中提取天然节点（分支点、端点）并遍历连通关系：

1. 节点检测：识别骨架中的分支点（邻域白色像素数≥3）和端点（邻域白色像素数=1）
2. 遍历连通分支：从每个节点出发沿骨架遍历，直到到达另一个节点，记录连接关系

示例代码：

import numpy as np
from skimage.morphology import square
from scipy.ndimage import convolve
from scipy.spatial import KDTree

# 检测骨架的天然节点（分支点+端点）
def detect_skeleton_nodes(skel_img):
    # 计算每个像素的3x3邻域白色像素数
    kernel = square(3)
    kernel[1,1] = 0  # 排除自身像素
    neighbor_count = convolve(skel_img.astype(int), kernel, mode='constant')
    # 筛选端点和分支点
    endpoints = np.where((skel_img == 1) & (neighbor_count == 1))
    branch_points = np.where((skel_img == 1) & (neighbor_count >= 3))
    # 合并去重
    nodes = np.vstack((np.array(endpoints).T, np.array(branch_points).T))
    nodes = np.unique(nodes, axis=0)
    return nodes

# 获取骨架节点并生成候选对
skeleton_nodes = detect_skeleton_nodes(skel)
tree = KDTree(skeleton_nodes)
candidate_pairs = list(tree.query_pairs(25))

# 遍历构建连通图
def build_skeleton_graph(nodes, skel_img):
    graph = {}
    node_set = set(tuple(n) for n in nodes)
    visited = set()
    directions = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
    
    for node in nodes:
        node_tuple = tuple(node)
        if node_tuple in visited:
            continue
        graph[node_tuple] = []
        x, y = node
        # 遍历所有邻域方向
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < skel_img.shape[0] and 0 <= ny < skel_img.shape[1] and skel_img[nx, ny] == 1:
                current = (nx, ny)
                prev = (x, y)
                # 沿骨架遍历直到遇到下一个节点
                while current not in node_set:
                    next_pixels = []
                    for ddx, ddy in directions:
                        nnx, nny = current[0] + ddx, current[1] + ddy
                        if (nnx, nny) != prev and 0 <= nnx < skel_img.shape[0] and 0 <= nny < skel_img.shape[1] and skel_img[nnx, nny] == 1:
                            next_pixels.append((nnx, nny))
                    if not next_pixels:
                        break
                    prev = current
                    current = next_pixels[0]
                if current in node_set and current != node_tuple:
                    graph[node_tuple].append(current)
                    visited.add(current)
    return graph

# 生成最终连通图
skeleton_graph = build_skeleton_graph(skeleton_nodes, skel)

方法对比 #

• 方法1：保留原有Harris角点检测流程，通过路径验证修正偏移，实现简单，适合需要复用原有角点结果的场景
• 方法2：直接从骨架提取节点，准确性更高，避免了角点偏移问题，是骨架图构建的更原生方案

内容的提问来源于stack exchange，提问作者F. Windram