代码之家 › 专栏 › 技术社区 › Chris

如何检测图像中的不规则边界?

language-agnostic c#

Chris · 技术社区 · 14 年前

对于下面的图像,我可以使用什么算法来检测区域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秒以上的时间。我有哪些优化选项?

2 回复 | 直到 14 年前

Jaroslav Jandek 14 年前

有边界的两个区域是指在一个小的区域内应该有三种颜色:红色、黑色和绿色。

因此,一个非常无效的解决方案出现了: 使用 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毫秒 (扫描并找到最近的点)。

您还可以递归地进行搜索:首先,对于大型图像,精度为1000,然后精度为100,最后精度为10。 findclosestpoints实际上会为您提供一个估计的矩形区域,边界应该位于该区域(通常边界是这样的)。

然后您可以使用我在其他注释中描述的向量方法。

Sean Edwards 14 年前

我读你的问题是问这两点是否存在于不同的地区。这是正确的吗?如果是这样,我可能会使用 Flood Fill . 实现起来并不太困难(不要递归地实现它,几乎肯定会耗尽堆栈空间),而且它可以看到复杂的情况,比如有边界的U形区域之间两点,但实际上不是不同的区域。基本上运行Flood Fill,当坐标与目标坐标匹配时返回true(或者当它足够接近以满足您的需求时,取决于您的用例)。

[编辑]这里是 an example 我为我的一个项目写的洪水填充。这个项目是CPAL许可的,但是实现对于我使用它的目的是非常具体的,所以不要担心复制它的某些部分。它不使用递归,所以它应该能够缩放到像素数据。

[编辑2]我误解了任务。我没有任何示例代码可以完全满足您的需求,但是我可以说,比较每个像素的像素,整个两个区域并不是您想要做的事情。您可以通过将每个区域划分为一个更大的网格(可能是25x25像素)来降低复杂性,并首先比较这些扇区,如果其中任何一个扇区足够接近,则只在这两个扇区内进行每像素比较。

[第2.5版][四叉树] 3 可能也能帮助你。我对它没有太多的经验,但我知道它在二维碰撞检测中很流行,这类似于你在这里所做的。可能值得研究。