从图像点构建树/图 [英] Building tree/graph from image points

问题描述

我开始用这张照片描述我的问题：

I start to describe my problem with this picture:

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

In the picture, we can see some points (black dots). What I want to do is to first store all the points and then find the node points and the tip points (red dots). What is more, I need to check if these red points can be connected by straight lines (along the black points) to find angles between the red lines.

我不知道我是否解释得很清楚，但我想到的是我应该实现一个树/图，而不是使用一些路径查找来检查红点是连接？

I don't know if I explained it clearly enough, but what I figured is that I should implement a tree/graph and than use some path finding to check if the red points are connected?

基本上，我开始用类似：

Basically, I started with something like:

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 的邻居向量中。

Where I store all the points in allPoints vector. Than for each Point, I check all his neighbors ([x+1,y], [x-1,y], [x+1,y+1], [x-1, y+1], ...) and store them in neighbors vector for that Point.

然后，根据邻居向量的大小，确定点是节点（3个或更多邻居），提示（1个邻居），或者只是一些基本点（2个邻居）。

Then, by the size of the neighbors vector, I determine if the Point is a node (3 or more neighbors), a tip (1 neighbor), or just some basic point (2 neighbors).

这里是部分，我不知道如何实现一些路径查找（检查是否有一个方法，例如从一个提示点到最近的节点点）。

And here comes the part, where I have no idea how to implement some path finding (to check whether there is a way for example from a tip point to the closest node point).

此外，我不知道我的树表示是否好（可能不是）。所以如果有人会帮助我实现我想要的，这将是巨大的。

What is more, I have no idea if my "tree" representation is good (probably is not). So if anyone would help me to achieve what I want, it would be great.

我在C ++（和OpenCV）和VS2010写。

P.S. I'm writing in C++ (and OpenCV) and VS2010.

编辑：

这是它在一个真正的程序（红线被我淹没在油漆，但这是我想要实现的）看起来像：

This is how it looks like in a real program (red lines are drown by me in paint, but this is what i want to achieve):

推荐答案

我不知道这个帖子应该是一个答案或编辑，因为我不知道是否有人会注意到我添加了一些东西，我决定发布它作为答案。对不起，如果它的错误。

I'm not sure if that post should be an answer or edit, because i have no idea if anyone would notice that I added something, co i decided to post it as an answer. Sorry if its wrong.

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

About a problem. I did some codding, I belive I know how to do what I wanted, but another problem came out ;d.

好，让我们从图片开始：

Well lets start with picture:

要查看问题在哪里，你必须放大图片，大约400％，并看看绿色矩形。图像骨架是我的基本线，和图像temp，是我的输出提示和节点。正如你可以看到，提示是好的（紫色矩形）（点与1邻居），但不幸的是有像素有3个或更多的邻居，他们不是节点的线（右边的绿色矩形在骨架是没有节点的线..和temp上的绿色矩形是我的虚假节点，因为特定的像素位置标记）。当你超级缩放它，你会注意到我用颜色标记像素，使它更清楚。

To see where is a problem, you have to zoom above picture, about 400%, and take a look inside green rectangles. Image "skeleton" are my basic lines, and image "temp", are my output tips and nodes. As you can see, tips are fine (violet rectangles) (points with 1 neighbor) but unfortunately there are lines where pixel have 3 or more neighbors and they are not nodes (right green rectangle on "skeleton" is the line which have no nodes.. and green rectangle on "temp" are my false nodes .. marked because of the specific pixels positions).When You super zoom it, You are going to notice that I marked pixels with colors to make it more clear.

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

So the problem is that sometimes both nodes and "branches" have more than 2 neighbors which leads me to a problem "how to find a difference between them". All i need are nodes (small green rectangle on "skeleton" image - when you zoom you will see that there are 2 pixels that could be a node, but this is not important as long as they are so close to each other).

任何帮助？

如果您需要代码，粘贴它。

If you need code, just tell and I will edit & paste it.

编辑：

我做了什么！

我发现了一种从行中过滤冗余像素的方法。但是这使我的一些骨架线断开，这是不好的，因为一些节点被认为是提示现在。

I found a way to filter redundant pixels from the lines. But that made some of my skeleton lines to disconnect, and that is not good, because some nodes are considered as "tips" now.

只要看看图片：

Just look at the picture:

小点是好节点，但是红色矩形内的点是断开连接的节点认为是提示。

Small dots are "good" nodes, but dots inside red rectangles, are nodes which got disconnected (zoom in to see that), and are now considered as tips.

如何过滤像素？下面是代码：

How did I filtered the pixels? Here is the code:

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;
                }
            }
        }
    }
}

$ b b

对于每个像素，检查其是否具有（x + 1，y-1）（x + 1，y + 1）（x-1，y + 1）如果它，我检查是否有邻居只是旁边的邻居，并删除它们。这是我唯一的想法，它很慢，但现在，没有什么更好的我的想法。

For each pixel I checked if it has (x+1,y-1) (x+1,y+1) (x-1,y+1) (x-1, y-1) neighbor and if it does , i checked if there are neighbors just next to that neighbor and removed them. It was the only idea that I had , and its quite slow, but for now , nothing better comes to my mind.

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

So now, my main problem is. How to reconnect broken nodes ? ..

这篇关于从图像点构建树/图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！