大廈樹/圖

Question

我開始來形容這幅畫我的問題：

在圖片中，我們可以看到一些點（黑點）。我想要做的是首先存儲所有點，然後找到節點點和提示點（紅色點）。 更重要的是，我需要檢查這些紅點是否可以通過直線（沿着黑點）連接以找到紅線之間的角度。

我不知道我是否足夠清楚地解釋了它，但是我認爲我應該實現一棵樹/圖並且使用一些路徑查找來檢查紅點是否已連接？

基本上，我開始喜歡的東西：

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編寫。

編輯：

這是怎麼看起來像一個真正的程序（紅色線是由我在油漆淹死，但這就是我想要實現）：

Answer 1

我不確定這篇文章是否應該是答案或編輯，因爲我不知道是否有人會注意到我添加了一些內容，因此我決定將其作爲答案發布。對不起，如果它錯了。

關於一個問題。我做了一些編碼，我相信我知道如何去做我想要的，但是另一個問題出來了; d。

那麼讓我們開始用圖片：

要看到一個問題，你必須放大上面的圖片，約400％，看一看綠色長方形內。圖像「骨架」是我的基本線條，圖像「temp」是我的輸出提示和節點。正如你所看到的，提示很好（紫色的矩形）（有1個鄰居的點），但不幸的是有些行的像素有3個或更多的鄰居，它們不是節點（「骨架」上的右邊綠色矩形是沒有節點的線..和「temp」上的綠色矩形是我的虛假節點..因爲特定的像素位置而被標記）。當您超級縮放它時，您將注意到我用顏色標記了像素以使其更加清晰。

所以問題是，有時兩個節點和「分支」有2樓以上的鄰居，導致我一個問題「如何找到它們之間的差別」。我所需要的只是節點（「骨架」圖像上的小綠色矩形 - 當你縮放時，你會看到有2個像素可能是一個節點，但只要它們彼此如此接近，這並不重要）。

任何幫助？

如果你需要的代碼，只是告訴我將編輯&粘貼。

編輯：

我做了一件事！

我發現了一種方法，以過濾從行冗餘象素。但是這使得我的一些骨架線斷開連接，這並不好，因爲現在有些節點被認爲是「技巧」。

只要看看圖片：

小點是「好」的節點，但裏面的紅色矩形點，是其斷開了（放大一看就知道），而現在被認爲是提示節點。

我怎麼濾波的像素？下面是代碼：

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）鄰居，如果是這樣，我檢查鄰居旁邊是否有鄰居，並刪除它們。這是我唯一的想法，而且它非常緩慢，但現在，我的腦海裏沒有更好的了。

所以，現在，我的主要問題是。如何重新連接斷開的節點？ ..

Answer 2

這是遲到了，但我得到了一些工作，並把它放在一個github repo: pixeltree（這是太大了，只是把整個事情粘貼在這裏）。我在python而不是C++中工作，但我希望如果你或其他人需要它，這個想法會有所幫助。免責聲明 - 這可能是一些可以接受的方法，但我沒有找到它。

方法

1. 獨立的圖像轉換成你想要儘可能多的地區（如黑/白）
2. 對於每一個區域，選擇任意像素
3. 建立從覆蓋每一個像素一個完整的樹該區域的像素
4. 切回樹的非有意義分支，直到它是一個最小的樹

詳ILS

難的是削減樹的最後一步。這是我使用的方法：

1. 對於每個地區再次，選擇一個「遙遠」像素（技術上，圖中最長路徑的一端）的根。
2. 對於該樹中的每個葉子，執行廣度優先搜索直到遇到另一個分支。如果高度小於遇到的像素，則消除該葉子的分支。

例子

尷尬大函數，它的大部分工作：

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