c# - 使用霍夫线变换的最长线检测

Question

我想 detect longest line 在使用霍夫变换的图像中。

输入图片

预期输出

当前输出

我们可以看到它检测到了不正确的行。

在下面的代码中，我应该在哪里寻找错误？

不过有一个问题。如果我将阈值从 50 增加到 150，源代码似乎会产生正确的输出。但是，对我来说，这没有任何意义，因为增加阈值意味着排除低投票行。

.

源代码

HoughLineTransform.cs

public class Line
{
    public Point Start { get; set; }
    public Point End { get; set; }
    public int Length 
    {
        get 
        {
            return (int)Math.Sqrt(Math.Pow(End.X - Start.X, 2) + Math.Pow(End.Y - Start.Y, 2)); ;
        }
    }
    public Line()
    {

    }
    public Line(Point start, Point end)
    {
        Start = start;
        End = end;
    }
}

public class HoughLineTransform
{
    public HoughMap Accumulator { get; set; }

    public HoughLineTransform() {}

    public Line GetLongestLine()
    {
        List<Line> lines = GetLines(50);

        int maxIndex = 0;
        double maxLength = -1.0;

        for (int i = 0; i < lines.Count; i++)
        {
            if (maxLength < lines[i].Length)
            {
                maxIndex = i;
                maxLength = lines[i].Length;
            }
        }

        return lines[maxIndex];
    }

    public List<Line> GetLines(int threshold)
    {
        if (Accumulator == null)
        {
            throw new Exception("HoughMap is null");
        }

        int houghWidth = Accumulator.Width;
        int houghHeight = Accumulator.Height;
        int imageWidth = Accumulator.Image.GetLength(0);
        int imageHeight = Accumulator.Image.GetLength(1);

        List<Line> lines = new List<Line>();

        if (Accumulator == null)
            return lines;

        for (int rho = 0; rho < houghWidth; rho++)
        {
            for (int theta = 0; theta < houghHeight; theta++)
            {
                if ((int)Accumulator[rho, theta] > threshold)
                {
                    //Is this point a local maxima (9x9)
                    int peak = Accumulator[rho, theta];

                    for (int ly = -4; ly <= 4; ly++)
                    {
                        for (int lx = -4; lx <= 4; lx++)
                        {
                            if ((ly + rho >= 0 && ly + rho < houghWidth) && (lx + theta >= 0 && lx + theta < houghHeight))
                            {
                                if ((int)Accumulator[rho + ly, theta + lx] > peak)
                                {
                                    peak = Accumulator[rho + ly, theta + lx];
                                    ly = lx = 5;
                                }
                            }
                        }
                    }

                    if (peak > (int)Accumulator[rho, theta])
                        continue;

                    int x1, y1, x2, y2;
                    x1 = y1 = x2 = y2 = 0;

                    double rad = theta * Math.PI / 180;

                    if (theta >= 45 && theta <= 135)
                    {
                        //y = (r - x Math.Cos(t)) / Math.Sin(t)
                        x1 = 0;
                        y1 = (int)(((double)(rho - (houghWidth / 2)) - ((x1 - (imageWidth / 2)) * Math.Cos(rad))) / Math.Sin(rad) + (imageHeight / 2));
                        x2 = imageWidth - 0;
                        y2 = (int)(((double)(rho - (houghWidth / 2)) - ((x2 - (imageWidth / 2)) * Math.Cos(rad))) / Math.Sin(rad) + (imageHeight / 2));
                    }
                    else
                    {
                        //x = (r - y Math.Sin(t)) / Math.Cos(t);
                        y1 = 0;
                        x1 = (int)(((double)(rho - (houghWidth / 2)) - ((y1 - (imageHeight / 2)) * Math.Sin(rad))) / Math.Cos(rad) + (imageWidth / 2));
                        y2 = imageHeight - 0;
                        x2 = (int)(((double)(rho - (houghWidth / 2)) - ((y2 - (imageHeight / 2)) * Math.Sin(rad))) / Math.Cos(rad) + (imageWidth / 2));
                    }

                    lines.Add(new Line(new Point(x1, y1), new Point(x2, y2)));
                }
            }
        }

        return lines;
    }
}

Answer 1

该算法实际上很容易理解，即使乍一看似乎恰恰相反。 它基于以下行公式:

ρ = cos(θ) * x + sin(θ) * y  

其中ρ是原点到直线的垂直距离，θ是这条垂直线与水平轴的夹角。

如果您知道 ρ 和 θ，您就知道这条直线。如果您采用所有可能的对(在给定的精度内) ρ 和 θ 你实际上得到了图像中可能存在的所有可能的线。那是什么 Map[ρ, θ ] 存储。如果希望角度的精度为 1 度，则需要 180 列。对于 ρ，可能的最大距离是图像的对角线长度。所以取一个像素精度，行数可以是图像的对角线长度。但不是你的 图像，正方形(在 HoughMap.cs 中):

int maxTheta = 180;
int houghHeight = (int)( Math.Sqrt( 2 ) * Math.Max( imgWidth, imgHeight ) ) / 2;
int doubleHoughHeight = houghHeight * 2;

doubleHoughHeight 是正方形的对角线，这就是它需要 Math.Max 的原因!

图像的每个点都被映射到您的 Map 数组上:

     ρ                      θ    number of points in that line( pair (ρ, θ) )
Map  0                      0    num0
     0                      1    num1
     0                      2    num2
     .                      .    .
     .                      .    .
     doubleHoughHeight – 1  179  numN

threshold 过滤掉小于 50 点的线。以下代码还过滤掉了行:

//Is this point a local maxima (9x9)
int peak = Accumulator[ rho, theta ];

for( int ly = -4; ly <= 4; ly++ ) {
    for( int lx = -4; lx <= 4; lx++ ) {
        if( ( ly + rho >= 0 && ly + rho < houghWidth ) && ( lx + theta >= 0 && lx + theta < houghHeight ) ) {
            if( (int)Accumulator[ rho + ly, theta + lx ] > peak ) {
                peak = Accumulator[ rho + ly, theta + lx ];
                    ly = lx = 5;
             }
         }
     }
 }

 if( peak > (int)Accumulator[ rho, theta ] )
     continue;

您遇到的实际问题可以在下图中看到:

您得到的结束和开始点实际上是直线和两个轴的交点:

int x1, y1, x2, y2;
x1 = y1 = x2 = y2 = 0;

double rad = theta * Math.PI / 180;

if( theta >= 45 && theta <= 135 ) {
    //y = (r - x Math.Cos(t)) / Math.Sin(t)
    x1 = 0;
    y1 = (int)( ( (double)( rho - ( houghWidth / 2 ) ) - ( ( x1 - ( imageWidth / 2 ) ) * Math.Cos( rad ) ) ) / Math.Sin( rad ) + ( imageHeight / 2 ) );
    x2 = imageWidth - 0;
    y2 = (int)( ( (double)( rho - ( houghWidth / 2 ) ) - ( ( x2 - ( imageWidth / 2 ) ) * Math.Cos( rad ) ) ) / Math.Sin( rad ) + ( imageHeight / 2 ) );
}
else {
    //x = (r - y Math.Sin(t)) / Math.Cos(t);
    y1 = 0;
    x1 = (int)( ( (double)( rho - ( houghWidth / 2 ) ) - ( ( y1 - ( imageHeight / 2 ) ) * Math.Sin( rad ) ) ) / Math.Cos( rad ) + ( imageWidth / 2 ) );
    y2 = imageHeight - 0;
    x2 = (int)( ( (double)( rho - ( houghWidth / 2 ) ) - ( ( y2 - ( imageHeight / 2 ) ) * Math.Sin( rad ) ) ) / Math.Cos( rad ) + ( imageWidth / 2 ) );
}

lines.Add( new Line( new Point( x1, y1 ), new Point( x2, y2 ) ) );

编辑

您的代码工作正常，但它不计算实际长度。我找到的一个解决方案是存储二维 Map 数组每个位置的所有点。在 你的HoughMap.cs:

public List<Point>[] lstPnts { get; set; }

public void Compute() {
    if( Image != null ) {
        ...
        ...
        ...
        Map = new int[ doubleHoughHeight, maxTheta ];

        //Add this code////////////////////////////////////////////////
        //lstPnts is an doubleHoughHeight * maxTheta size array of list Points
        lstPnts = new List<Point>[ doubleHoughHeight * maxTheta ];

        for(int i = 0; i < doubleHoughHeight * maxTheta; i++ ) {
            lstPnts[ i ] = new List<Point>();
        }
        ///////////////////////////////////////////////////////////////
        ....
        ....
        ....
        if( ( rho > 0 ) && ( rho <= Map.GetLength( 0 ) ) ) {
            Map[ rho, theta ]++;
            //Add this line of code////////////////////////////////////////
            lstPnts[ rho * maxTheta + theta ].Add( new Point( x, y ) );
            ///////////////////////////////////////////////////////////////
            PointsCount++;
        }
        ....
    }
}

在HoughLineTransform.cs

public List<Line> GetLines( int threshold ) {
    if( Accumulator == null ) {
        throw new Exception( "HoughMap is null" );
    }

    int houghWidth = Accumulator.Width;
    int houghHeight = Accumulator.Height;
    int imageWidth = Accumulator.Image.GetLength( 0 );
    int imageHeight = Accumulator.Image.GetLength( 1 );

    List<Line> lines = new List<Line>();

    if( Accumulator == null )
        return lines;

    for( int rho = 0; rho < houghWidth; rho++ ) {
        for( int theta = 0; theta < houghHeight; theta++ ) {
            if( (int)Accumulator[ rho, theta ] > threshold ) {
                //Is this point a local maxima (9x9)
                int peak = Accumulator[ rho, theta ];
                int dd = 10;

                for( int ly = -dd; ly <= dd; ly++ ) {
                    for( int lx = -dd; lx <= dd; lx++ ) {
                        if( ( ly + rho >= 0 && ly + rho < houghWidth ) && ( lx + theta >= 0 && lx + theta < houghHeight ) ) {
                            if( (int)Accumulator[ rho + ly, theta + lx ] > peak ) {
                                peak = Accumulator[ rho + ly, theta + lx ];
                                ly = lx = dd + 1;
                            }
                        }
                    }
                }

                if( peak > (int)Accumulator[ rho, theta ] )
                    continue;

                //Map[ rho, theta ] contains these points -> lstPnts[ rho * houghHeight + theta ].
                //The points in that list with min and max X coordinate are the Start and End ones
                int x1 = houghWidth, y1 = 0, x2 = -1, y2 = 0;

                for(int i = 0; i < Accumulator.lstPnts[ rho * houghHeight + theta ].Count; i++ ) {
                    if( Accumulator.lstPnts[ rho * houghHeight + theta ][ i ].X > x2 ) {
                        x2 = Accumulator.lstPnts[ rho * houghHeight + theta ][ i ].X;
                        y2 = Accumulator.lstPnts[ rho * houghHeight + theta ][ i ].Y;
                    }

                    if( Accumulator.lstPnts[ rho * houghHeight + theta ][ i ].X < x1 ) {
                        x1 = Accumulator.lstPnts[ rho * houghHeight + theta ][ i ].X;
                        y1 = Accumulator.lstPnts[ rho * houghHeight + theta ][ i ].Y;
                    }
                }


                //Remove this code
                /*int x1, y1, x2, y2;
                x1 = y1 = x2 = y2 = 0;

                double rad = theta * Math.PI / 180;

                if( theta >= 45 && theta <= 135 ) {
                    //y = (r - x Math.Cos(t)) / Math.Sin(t)
                    x1 = 0;
                    y1 = (int)( ( (double)( rho - ( houghWidth / 2 ) ) - ( ( x1 - ( imageWidth / 2 ) ) * Math.Cos( rad ) ) ) / Math.Sin( rad ) + ( imageHeight / 2 ) );
                    x2 = imageWidth - 0;
                    y2 = (int)( ( (double)( rho - ( houghWidth / 2 ) ) - ( ( x2 - ( imageWidth / 2 ) ) * Math.Cos( rad ) ) ) / Math.Sin( rad ) + ( imageHeight / 2 ) );
                }
                else {
                    //x = (r - y Math.Sin(t)) / Math.Cos(t);
                    y1 = 0;
                    x1 = (int)( ( (double)( rho - ( houghWidth / 2 ) ) - ( ( y1 - ( imageHeight / 2 ) ) * Math.Sin( rad ) ) ) / Math.Cos( rad ) + ( imageWidth / 2 ) );
                    y2 = imageHeight - 0;
                    x2 = (int)( ( (double)( rho - ( houghWidth / 2 ) ) - ( ( y2 - ( imageHeight / 2 ) ) * Math.Sin( rad ) ) ) / Math.Cos( rad ) + ( imageWidth / 2 ) );
                }*/

                lines.Add( new Line( new Point( x1, y1 ), new Point( x2, y2 ) ) );
            }
        }
    }

    return lines;
}