将开放曲线转换为有序像素列表：使用numpy的Python测试代码

Question

我有一张开放曲线的图像，存储在一个numpy数组里，我需要根据曲线上的位置，生成一个点的坐标列表。

我写了一个草稿脚本，使用了numpy和mahotas。不过这个脚本可能不是最优的。

我知道OpenCV可以处理闭合曲线，那它能更快地处理开放曲线吗？

比如，如果原始曲线是：

[[0 0 0 0 0 0 0]
 [0 1 0 0 1 0 0]
 [0 0 1 0 0 1 0]
 [0 0 0 1 1 0 0]
 [0 0 0 0 0 0 0]]

我可以用np.where(myarray==1)来获取像素的索引：

(array([1, 1, 2, 2, 3, 3]), array([1, 4, 2, 5, 3, 4]))

但是这不是我需要的。我的脚本会根据曲线上的像素顺序来生成索引：

i= 0 ( 1 , 1 )
i= 1 ( 2 , 2 )
i= 2 ( 3 , 3 )
i= 3 ( 3 , 4 )
i= 4 ( 2 , 5 )
i= 5 ( 1 , 4 )

我想优化我的脚本，有什么建议吗？

Answer 1

假设在这个矩阵或图像中只存在一条曲线，并且曲线上的每个点都有1到2个邻居，下面这个函数就能给你想要的结果。

它的工作原理是，从左上角最近的点开始，逐步找到下一个最近的、还没有被访问过的点，形成一个点的链条，直到没有更多的点可以访问为止。对于一个闭合的曲线，链条的第一个点和最后一个点之间的平方欧几里得距离会小于2。

import numpy as np

def find_chain(mat):
  locs=np.column_stack(np.nonzero(mat))
  chain=[np.array([0,0])]
  while locs.shape[0]>0:
    dists=((locs-np.vstack([chain[-1]]*locs.shape[0]))**2).sum(axis=1)
    next=dists.argmin()
    if dists.min()<=2 or len(chain)==1:
      chain.append(locs[next,:])
      locs=locs[np.arange(locs.shape[0])!=next,:]
    else:
      chain=[chain[0]]+chain[1::][::-1]
  return np.vstack(chain[1::]),((chain[1]-chain[-1])**2).sum()<=2

对于一个开放的曲线：

>>> mat1=np.array([[0, 0, 0, 0, 0, 0, 0],
...                [0, 1, 0, 0, 1, 0, 0],
...                [0, 0, 1, 0, 0, 1, 0],
...                [0, 0, 0, 1, 1, 0, 0],
...                [0, 0, 0, 0, 0, 0, 0]])
>>> points,isclosed=find_chain(mat1)
>>> points
array([[1, 1],
       [2, 2],
       [3, 3],
       [3, 4],
       [2, 5],
       [1, 4]])
>>> isclosed
False

而对于一个闭合的曲线：

>>> mat2=np.array([[0, 0, 0, 0, 0],
...                [0, 0, 1, 0, 0],
...                [0, 1, 0, 1, 0],
...                [0, 1, 0, 1, 0],
...                [0, 0, 1, 0, 0],
...                [0, 0, 0, 0, 0]])
>>> points,isclosed=find_chain(mat2)
>>> points
array([[1, 2],
       [2, 1],
       [3, 1],
       [4, 2],
       [3, 3],
       [2, 3]])
>>> isclosed
True

还有一种情况是，起始点（离原点最近的点）把曲线分成了两部分。

>>> mat3=np.array([[0, 0, 0, 0, 0],
...                [0, 1, 1, 1, 0],
...                [0, 1, 0, 0, 0],
...                [0, 1, 0, 0, 0],
...                [0, 0, 0, 0, 0],
...                [0, 0, 0, 0, 0]])
>>> points,isclosed=find_chain(mat3)
>>> points
array([[1, 3],
       [1, 2],
       [1, 1],
       [2, 1],
       [3, 1]])
>>> isclosed
False