如何检测图像中的不规则边框？

Question

鉴于下面的图像,我可以使用什么算法来检测区域1和2(由颜色标识)是否有边框？

http://img823.imageshack.us/img823/4477/borders.png

如果那里有一个C#示例,那将是非常棒的,但我真的只是在寻找任何示例代码.

编辑:使用Jaro的建议,我想出了以下内容......

public class Shape
{
    private const int MAX_BORDER_DISTANCE = 15;

    public List<Point> Pixels { get; set; }

    public Shape()
    {
        Pixels = new List<Point>();
    }

    public bool SharesBorder(Shape other)
    {
        var shape1 = this;
        var shape2 = other;

        foreach (var pixel1 in shape1.Pixels)
        {
            foreach (var pixel2 in shape2.Pixels)
            {
                var xDistance = Math.Abs(pixel1.X - pixel2.X);
                var yDistance = Math.Abs(pixel1.Y - pixel2.Y);

                if (xDistance > 1 && yDistance > 1)
                {
                    if (xDistance * yDistance < MAX_BORDER_DISTANCE)
                        return true;
                }
                else
                {
                    if (xDistance < Math.Sqrt(MAX_BORDER_DISTANCE) &&
                        yDistance < Math.Sqrt(MAX_BORDER_DISTANCE))
                        return true;
                }
            }
        }

        return false;
    }

    // ...
}

单击两个共享边框的形状返回相当快,但非常距离的形状或具有大量像素的形状有时需要3秒以上.我有什么选择来优化它？

Answer 1

2个有边界的区域意味着在某个小区域内应该有3种颜色：红、黑、绿。

因此，一个非常低效的解决方案出现了：使用Color pixelColor = myBitmap.GetPixel(x, y);您可以扫描一个区域来查找这 ​​3 种颜色。当然，该面积必须大于边框的宽度。

当然还有足够的优化空间（例如以 50 像素为步长并不断降低精度）。由于黑色是最少使用的颜色，因此您将首先搜索黑色区域。

这应该解释我在本主题的各种评论中所写的内容：

namespace Phobos.Graphics
{
    public class BorderDetector
    {
        private Color region1Color = Color.FromArgb(222, 22, 46);
        private Color region2Color = Color.FromArgb(11, 189, 63);
        private Color borderColor = Color.FromArgb(11, 189, 63);

        private List<Point> region1Points = new List<Point>();
        private List<Point> region2Points = new List<Point>();
        private List<Point> borderPoints = new List<Point>();

        private Bitmap b;

        private const int precision = 10;
        private const int distanceTreshold = 25;

        public long Miliseconds1 { get; set; }
        public long Miliseconds2 { get; set; }

        public BorderDetector(Bitmap b)
        {
            if (b == null) throw new ArgumentNullException("b");

            this.b = b;
        }

        private void ScanBitmap()
        {
            Color c;

            for (int x = precision; x < this.b.Width; x += BorderDetector.precision)
            {
                for (int y = precision; y < this.b.Height; y += BorderDetector.precision)
                {
                    c = this.b.GetPixel(x, y);

                    if (c == region1Color) region1Points.Add(new Point(x, y));
                    else if (c == region2Color) region2Points.Add(new Point(x, y));
                    else if (c == borderColor) borderPoints.Add(new Point(x, y));
                }
            }
        }

        /// <summary>Returns a distance of two points (inaccurate but very fast).</summary>
        private int GetDistance(Point p1, Point p2)
        {
            return Math.Abs(p1.X - p2.X) + Math.Abs(p1.Y - p2.Y);
        }

        /// <summary>Finds the closests 2 points among the points in the 2 sets.</summary>
        private int FindClosestPoints(List<Point> r1Points, List<Point> r2Points, out Point foundR1, out Point foundR2)
        {
            int minDistance = Int32.MaxValue;
            int distance = 0;

            foundR1 = Point.Empty;
            foundR2 = Point.Empty;

            foreach (Point r1 in r1Points)
                foreach (Point r2 in r2Points)
                {
                    distance = this.GetDistance(r1, r2);

                    if (distance < minDistance)
                    {
                        foundR1 = r1;
                        foundR2 = r2;
                        minDistance = distance;
                    }
                }

            return minDistance;
        }

        public bool FindBorder()
        {
            Point r1;
            Point r2;

            Stopwatch watch = new Stopwatch();

            watch.Start();
            this.ScanBitmap();
            watch.Stop();
            this.Miliseconds1 = watch.ElapsedMilliseconds;

            watch.Start();
            int distance = this.FindClosestPoints(this.region1Points, this.region2Points, out r1, out r2);
            watch.Stop();
            this.Miliseconds2 = watch.ElapsedMilliseconds;

            this.b.SetPixel(r1.X, r1.Y, Color.Green);
            this.b.SetPixel(r2.X, r2.Y, Color.Red);

            return (distance <= BorderDetector.distanceTreshold);
        }
    }
}

这很简单。以这种方式搜索只需要大约2 + 4 毫秒（扫描并找到最近的点）。

您还可以递归地进行搜索：首先使用 precision = 1000，然后 precision = 100，最后对于大图像使用 precision = 10。FindClosestPoints 实际上会为您提供边界应位于的估计矩形区域（通常边界就是这样）。

然后你可以使用我在其他评论中描述的向量方法。