如何对骨架提取后的二维点排序以还原连续骨架线条？

输入图像 #

生成骨架代码 #

import cv2
import matplotlib.pyplot as plt
from skimage.morphology import skeletonize

im = cv2.imread('a.png',cv2.IMREAD_GRAYSCALE)
#conts ,_ = cv2.findContours(im, cv2.RETR_TREE, cv2.CHAIN_APPROX_SIMPLE)
#cont = conts[0]
sk = skeletonize(im >0)
plt.imshow(sk)

生成的骨架图像 #

提取点集代码 #

skeleton_yx = np.argwhere(sk > 0)
pts = np.flip(skeleton_yx, axis=None) #yx -> xy
print(pts.shape) #(774, 2)

需要对上述pts点集进行排序，以此还原出上方的sk骨架图像。

补充说明 #

参考相关问题的解决方案，其中Imanol Luengo的首个方案可行，但第4步从所有起点寻找代价最小路径的代码运行速度极慢：

paths = [list(nx.dfs_preorder_nodes(T, i)) for i in range(len(points))]

其他方案大多需要已知排序起始点，但目前还没找到适用于单条连续无序线条场景的通用起始点确定方法（推测可通过遍历所有白色像素或用滤波器找极值点，后续会尝试）。

已尝试方案 #

方案1：旋转排序 #

def rotational_sort(list_of_xy_coords):
  cx, cy = list_of_xy_coords.mean(0)
  x, y = list_of_xy_coords.T
  angles = np.arctan2(x-cx, y-cy)
  indices = np.argsort(angles)
  return list_of_xy_coords[indices]

im = np.zeros_like(im)
pts2= rotational_sort(pts)
cv2.polylines(im, [pts2], False, 255,2)
plt.imshow(im)

排序结果：

方案2：基于PCA的XYclean排序 #

from scipy.signal import savgol_filter
from sklearn.decomposition import PCA
from scipy import interpolate
def XYclean(x,y): 
  xy = np.concatenate((x.reshape(-1,1), y.reshape(-1,1)), axis=1)     
  pca = PCA(2)
  pca.fit(xy)
  #转换至PCA空间   
  xypca = pca.transform(xy) 
  newx = xypca[:,0]
  newy = xypca[:,1]
  indexSort = np.argsort(x)
  newx = newx[indexSort]
  newy = newy[indexSort]
  #添加更多点（可选）
  f = interpolate.interp1d(newx, newy, kind='linear')        
  newX=np.linspace(np.min(newx), np.max(newx), 100)
  newY = f(newX)            
  #转换回原坐标系
  xyclean = pca.inverse_transform(np.concatenate((newX.reshape(-1,1), newY.reshape(-1,1)), axis=1) )
  xc=xyclean[:,0]
  yc = xyclean[:,1]
  return np.hstack((xc.reshape(-1,1),yc.reshape(-1,1))).astype(int)

im = np.zeros_like(im)
X,Y=pts[:,0],pts[:,1]
pts2= XYclean(X,Y)
cv2.polylines(im, [pts2], False, 255,2)
plt.imshow(im)

排序结果：

内容的提问来源于stack exchange，提问作者yazan sayed