我开始来形容这幅画我的问题： enter image description here 大厦树/图

在图片中，我们可以看到一些点（黑点）。我想要做的是首先存储所有点，然后找到节点点和提示点（红色点）。更重要的是，我需要检查这些红点是否可以通过直线（沿着黑点）连接以找到红线之间的角度。

我不知道我是否足够清楚地解释了它，但是我认为我应该实现一棵树/图并且使用一些路径查找来检查红点是否已连接？

基本上，我开始喜欢的东西：

class Point { 
public: 
int x; 
int y; 
vector<Point> neighbors; 

Point(void); 
Point(int x, int y); 
} 

vector<Point> allPoints;

当我所有的点存放在allPoints载体。比每个Point，我检查他所有的邻居（[x + 1，y]，[x-1，y]，[x + 1，y + 1]，[x-1，y + 1]，... ）并将它们存储在邻居向量Point中。

然后，由邻居矢量的大小，我确定该点是一个节点（3个或更多邻居），一个尖端（1邻居），或只是一些基本的点（2个邻居）。

这里来的部分，我不知道如何实现一些路径查找（检查是否有方法，例如从一个小费点到最近的节点）。另外，我不知道我的“树”表示是否好（可能不是）。所以如果有人能够帮助我实现我想要的，那就太好了。

P.S.我用C++（和OpenCV）和VS2010编写。

编辑：

这是怎么看起来像一个真正的程序（红色线是由我在油漆淹死，但这就是我想要实现）：

enter image description here

来源

2013-12-22 patrykos91

你有标识邻近矢量一些现有的数据结构？或者你刚开始有一组x/y点？树枝是否像图像一样干净地隔离？还是会更杂乱？你可以有循环或重新连接分支（图表），或者你可以说你不会允许循环（一棵树）？看来问题需要更详细的规范。 – KobeJohn

你知道从哪里开始（树的根？） –

所以：我刚开始时只有一组x/y点。可以说，分支是干净地隔离的，我不会允许周期（这将是一棵树）。我知道从哪里开始？那么，如果我不这样做呢？我相信（可能是错误的），哪个“小费”点将成为根本无关紧要。 – patrykos91

我不确定这篇文章是否应该是答案或编辑，因为我不知道是否有人会注意到我添加了一些内容，因此我决定将其作为答案发布。对不起，如果它错了。

关于一个问题。我做了一些编码，我相信我知道如何去做我想要的，但是另一个问题出来了; d。

那么让我们开始用图片：

enter image description here

要看到一个问题，你必须放大上面的图片，约400％，看一看绿色长方形内。图像“骨架”是我的基本线条，图像“temp”是我的输出提示和节点。正如你所看到的，提示很好（紫色的矩形）（有1个邻居的点），但不幸的是有些行的像素有3个或更多的邻居，它们不是节点（“骨架”上的右边绿色矩形是没有节点的线..和“temp”上的绿色矩形是我的虚假节点..因为特定的像素位置而被标记）。当您超级缩放它时，您将注意到我用颜色标记了像素以使其更加清晰。

所以问题是，有时两个节点和“分支”有2楼以上的邻居，导致我一个问题“如何找到它们之间的差别”。我所需要的只是节点（“骨架”图像上的小绿色矩形 - 当你缩放时，你会看到有2个像素可能是一个节点，但只要它们彼此如此接近，这并不重要）。

任何帮助？

如果你需要的代码，只是告诉我将编辑&粘贴。

编辑：

我做了一件事！

我发现了一种方法，以过滤从行冗余象素。但是这使得我的一些骨架线断开连接，这并不好，因为现在有些节点被认为是“技巧”。

只要看看图片： enter image description here

小点是“好”的节点，但里面的红色矩形点，是其断开了（放大一看就知道），而现在被认为是提示节点。

我怎么滤波的像素？下面是代码：

void SKEL::clearPixels(cv::Mat& input) 
{ 
    uchar* data = (uchar *)input.data; 
    for (int i = 1 ; i < input.rows-1 ; i++) 
    { 
     for (int j = 1 ; j < input.cols-1 ; j++) 
     { 
      if (input.at<uchar>(i,j) == 255) //if its part of skeleton 
      { 
       if (input.at<uchar>(i-1,j+1) == 255) 
       { 
        if (input.at<uchar>(i,j+1) == 255) data[i*input.step+(j+1)*input.channels()] = 0; 
        if (input.at<uchar>(i-1,j) == 255) data[(i-1)*input.step+(j)*input.channels()] = 0; 
       } 
       if (input.at<uchar>(i+1,j+1) == 255) 
       { 
        if (input.at<uchar>(i,j+1) == 255) data[i*input.step+(j+1)*input.channels()] = 0; 
        if (input.at<uchar>(i+1,j) == 255) data[(i+1)*input.step+(j)*input.channels()] = 0; 
       } 
       if (input.at<uchar>(i-1,j-1) == 255) 
       { 
        if (input.at<uchar>(i,j-1) == 255) data[i*input.step+(j-1)*input.channels()] = 0; 
        if (input.at<uchar>(i-1,j) == 255) data[(i-1)*input.step+(j)*input.channels()] = 0; 
       } 
       if (input.at<uchar>(i+1,j-1) == 255) 
       { 
        if (input.at<uchar>(i,j-1) == 255) data[i*input.step+(j-1)*input.channels()] = 0; 
        if (input.at<uchar>(i+1,j) == 255) data[(i+1)*input.step+(j)*input.channels()] = 0; 
       } 
      } 
     } 
    } 
}

对于我检查每个像素，如果它有（X + 1，Y-1）（X + 1，Y + 1）（X-1，Y + 1）（x轴1，y-1）邻居，如果是这样，我检查邻居旁边是否有邻居，并删除它们。这是我唯一的想法，而且它非常缓慢，但现在，我的脑海里没有更好的了。

所以，现在，我的主要问题是。如何重新连接断开的节点？ ..

来源

2013-12-26 18:56:34 patrykos91

这是很好，你正在取得进展。当我有时间时，我仍然一点一点地在努力。由于您的代码正在工作，您可能有运气让它在[CodeReview]（http://codereview.stackexchange.com/）上查看？这听起来像你的问题是线不完全是一个像素。这很困难。此外，它看起来像线路中有部分损坏。是对的吗？ – KobeJohn

那么最大的问题是，线条不是一个像素，这是真的。如果你的意思是“temp”上的行被破坏 - 它们不是，我只是没有故意画出所有这些行，以便更容易地看到多像素行的确切位置：P 我提出了一些想法，我今天会试一试，并发布结果。 – patrykos91

你有没有得到一些有用的东西？我实际上尝试过5种不同的算法，它们工作正常，但对各种输入不稳健。 – KobeJohn

这是迟到了，但我得到了一些工作，并把它放在一个github repo: pixeltree（这是太大了，只是把整个事情粘贴在这里）。我在python而不是C++中工作，但我希望如果你或其他人需要它，这个想法会有所帮助。免责声明 - 这可能是一些可以接受的方法，但我没有找到它。

方法

独立的图像转换成你想要尽可能多的地区（如黑/白）
对于每一个区域，选择任意像素
建立从覆盖每一个像素一个完整的树该区域的像素
切回树的非有意义分支，直到它是一个最小的树

详ILS

难的是削减树的最后一步。这是我使用的方法：

对于每个地区再次，选择一个“遥远”像素（技术上，图中最长路径的一端）的根。
对于该树中的每个叶子，执行广度优先搜索直到遇到另一个分支。如果高度小于遇到的像素，则消除该叶子的分支。

例子

Pre-reduced hand Image with large areas Image with various test sections

尴尬大函数，它的大部分工作：

def treeify(image, target_families=None): 
    # family map is used everywhere to identify pixels, regions, etc. 
    family_map = _make_family_map(image) 
    target_families = target_families or np.unique(family_map) 
    trees = list() 
    rows, cols = family_map.shape 
    remaining_points = set((r, c) for r in range(rows) for c in range(cols) 
          if family_map[r, c] in target_families) 
    # the "tree" here is actually just a non-cyclic undirected graph which could 
    # be rooted anywhere. The basic graph is done with each pixel pointing to some neighbors (edges) 
    edges = np.empty_like(family_map, dtype=object) 
    edges.flat = [set() for _ in edges.flat] 
    # continue until all regions within the graph are handled 
    while remaining_points: 
     # grow a tree from any remaining point until complete 
     start_p = remaining_points.pop() 
     family = family_map[start_p] 
     tree = {'family': family, 
       'any_point': start_p} 
     trees.append(tree) 
     q = [(None, start_p)] 
     while q: 
      # pushright + popleft --> breadth first expansion 
      # random within left part of q - roughly BFS with less pattern 
      source, p = q.pop(random.randrange(0, max(1, len(q)//2))) 
      try: 
       remaining_points.remove(p) 
      except KeyError: 
       pass # tree start point is always already gone 
      # send qualifying neighbors for expansion 
      q_points = tuple(qp for sp, qp in q) 
      expansion_points = [n for n in _neighbors(p, 'all', family_map) 
           if all((n != source, 
             n in remaining_points, 
             n not in q_points, 
             family_map[n] == family))] 
      expansion_pairs = [(p, n) for n in expansion_points] 
      q.extend(expansion_pairs) 
      # document all edges for this point 
      if source is None: 
       all_connections = list(expansion_points) 
      else: 
       all_connections = expansion_points + [source] 
      edges[p].update(all_connections) 

    # prune all but "best" branches within each area 
    for tree in trees: 
     family = tree['family'] 
     # root graph at one end of the longest path in the graph 
     distant_point = _most_distant_node(tree['any_point'], edges) 
     # for choosing best paths: document the height of every pixel 
     heights = _heights(distant_point, edges) 
     remaining_leaves = set(_leaves(distant_point, edges)) 
     # repeatedly look for a leaf and decide to keep it or prune its branch 
     # stop when no leaves are pruned 
     while remaining_leaves: 
      leaf = remaining_leaves.pop() 
      # identify any degenerate path to next branching pixel 
      # this path is ignored when testing for nearby branches 
      ignore = set(_identify_degenerate_branch(leaf, edges)) 
      # BFS expansion to find nearby other branches 
      expansion_q = deque() 
      expansion_q.append(leaf) 
      while expansion_q: 
       p = expansion_q.popleft() # pushright + popleft for BFS 
       ignore.add(p) 
       # decide what to do with each neighbor 
       for n in _neighbors(p, 'sides', family_map): 
        if n in ignore: 
         continue # already decided to ignore this point 
        elif n in expansion_q: 
         continue # already slated for expansion testing 
        elif family_map[n] != family: 
         ignore.add(n) # ignore other families 
         continue 
        elif len(edges[n]) == 0: 
         expansion_q.append(n) # expand into empty spaces 
        elif _disqualified(leaf, n, edges, heights): 
         _prune_branch_of_leaf(leaf, edges, heights) 
         expansion_q.clear() # this leaf is done. stop looking 
         break 
        else: 
         expansion_q.append(n) 
    return trees, edges

来源

2014-03-13 18:29:03 KobeJohn

大厦树/图

回答

方法

详ILS

例子

尴尬大函数，它的大部分工作：

相关问题