Как обнаружить нерегулярные границы на изображении?

Question

Учитывая изображение ниже, какой алгоритм я мог бы использовать, чтобы определить, имеют ли области один и два (обозначенные цветом) границу?

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

Если есть пример C # изтам, это было бы здорово, но я просто искал пример кода.

Редактировать: Используя совет Джаро, я придумал следующее ...

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

Я прочитал ваш вопрос как вопрос о том, существуют ли эти две точки в разных регионах. Это правильно? Если это так, я бы, вероятно, использовал вариант Flood Fill . Это не супер сложно реализовать (не реализуйте это рекурсивно, вы почти наверняка исчерпаете пространство стека), и оно сможет смотреть на сложные ситуации, такие как U-образная область, которая имеет границу между две точки, но на самом деле это не разные регионы. Обычно запускайте заливку и возвращайте значение true, если ваша координата соответствует целевой координате (или, возможно, когда она достаточно близка для вашего удовлетворения, в зависимости от вашего варианта использования)

[Редактировать] Вот пример заливки, которую я написал для моего проекта. Проект лицензирован по CPAL, но реализация в любом случае довольно специфична для того, для чего я его использую, поэтому не беспокойтесь о копировании его частей. И он не использует рекурсию, поэтому он должен иметь возможность масштабирования до пиксельных данных.

[Edit2] Я неправильно понял задачу. У меня нет примера кода, который бы выполнял именно то, что вы ищете, но я могу сказать, что сравнивать пиксель за пикселем целые две области - это не то, что вы хотите делать. Вы можете уменьшить сложность, разбив каждую область на более крупную сетку (может быть, 25x25 пикселей) и сравнив сначала эти сектора, и, если какие-либо из них достаточно близки, проведите сравнение пикселей на пиксель только внутри этих двух секторов. *

[Edit2.5] [Quadtree] 3 может также помочь вам. У меня нет большого опыта с этим, но я знаю, что это популярно в 2D обнаружении столкновений, которое похоже на то, что вы делаете здесь. Может быть стоит исследовать.

Answer 2

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 мс (сканирование и поиск ближайших точек).

Вы также можете выполнить поиск рекурсивно: сначала с точностью = 1000, затем с точностью = 100 инаконец, точность = 10 для больших изображений.FindClosestPoints фактически даст вам приблизительную прямоугольную область, где должна располагаться граница (обычно границы такие).

Тогда вы можете использовать векторный подход, который я описал в других комментариях.