algorithm to trace border in 2D array

Question

I have a 2D array of integers that represent groupings (crystal grains) on a 2D surface. something like this: (each pixel of that image is assigned an integer depending on the group it belongs to, so every red pixel is assigned 1 for example, every blue is 2)

given an X,Y-coordinate on a border between two such groupings (user clicks there) how can I trace that border between these 2 groupings saving every pixel-coordinate that's along the border and get the two endpoint-coordinates (I'm not concerned with the case of an enclosure where there would be no endpoint, but a loop)

whatever algorithm I come up with seems to be so tedious to implement and I just can't imagine noone has done this before. Any help? Preferably would be a solution in c# but any hint about an algorithm is greatly appreciated.

EDIT:

I should have stated that I was going to implement an algorithm to vectorize that line like this:

1. between the two endpoints define a line
2. get the boundary point farthest away from the current line, if it is farther than d, split the line at this point, so there are two line segments
3. repeat until no boundary point is farther away than d from the line strip

I thought that was easy enough to implement that's why I didn't state it. To get there I just needed the solution to the current problem...

Concerning Questions:

how is the raw data formatted? - it's a simple short[,] labeling; with the size being approximately 250x150 something like this:

11111112222
11111222222
11112222222
11112222222 <- user clicks on leftmost 2 or rightmost 1 -> I want to trace that border
11111122222                                                down to the first
11111133322                                                encountered 3 and up to the
11333333333                                                frame-border

what is an endpoint? - as I had been thinking about global solutions, I could describe an endpoint as: a 2x2 area where the 4 pixels consist of color1, color2 and at least one third different color.

what is contiguously connected? - it doesn't really matter for the rest of the algorithm, see below

what about y-shaped regions? - I'm not concerned with them, you can assume the area of color1 behind the border is at least 2 pixels wide, that's why it also doesn't matter if we talk about a 4 or an 8 neighborhood.

what do I currently have? - at first I tried a 'walking'-algorithm, something like mvds posted, but found me doing stepping, neighborcalculation and checking in all 4 directions which was tedious and looked awful. I didn't find a nice representation for "this is the direction the last step came from, don't check that pixel for neighborhood".

I then abandoned the walking algorithm and tried a global approach (like a filter): for each pixel check if it is color1 AND has color2 in its 4-neighborhood. With this I get all boundaries between color1 and color2. I was going to remove all boundaries that are not connected to the user-clicked-coordinate by some kind of floodfill, but then I got the problem of: where are the endpoints?

I'm still thankful for more input. For now I'll see how far I can go with mvds' algorithm.

Answer 1

I'll assume you have already determined the 2 colours in question, e.g. as 'mvds' described, as a preprocessing step.

I think you'll find it helpful to use a coordinate system where each (x,y) represents not a pixel but the point where 4 pixels touch. Then you can write a function to determine whether North is a boundary pixel-border, likewise for South,East,West (or maybe you prefer the terminology up/down/left/right).

Start at a point on the border, e.g. scan the 4x4 neighbourhood for a point which has one of N/S/E/W as a border. Follow this border to the next point, and then scan all 4 directions other than the direction you came in, for the next pixel border. Repeat until you run out of pixel borders. Then you know you're at one endpoint.

Go back to the beginning and trace the border in a different direction to what you initially took, until you reach the other endpoint.

This gives you all the pixel borders. Each pixel border has colour 1 on one side and colour 2 on the other side.

(I would have thought that the vectorisation would be a lot more difficult than identifying the border, but that's not what your question is mainly about, right? To do that I'd start at an end-point and follow the sequence of pixel borders border by border, at each point checking whether the straight line from the end-point to the current point matches the pixel borders. As soon as it doesn't, that's the end of one line and you start a new line.)

Answer 2

Here's a few thoughts and the start of an algorithm:

Finding the outline of an area of equal color is easier than finding a border, especially when the border is not really "binary" (i.e. only 2 colors exactly) as seemingly the case in your image.

Finding adjoining parts of two outlines is not very complicated. For every point on outline A, find the nearest point of outline B. If distance |A-B| < X, the point halfway between A and B is on the border. (X depends on the fuzzyness of your border)

If you can make your users click twice, at both sides of the border, that would be great. If you insist on one click, find the two biggest areas in a radius of X around the clicked point.

Finding the outline of an area is not complicated:

1. take a point (x,y) to start, take a direction (dx,dy)=(1,0) to start
2. take color C of point (x,y) which will be the color to trace
3. run x+=dx,y+=dy until at (x+dx,y+dy) you have another color and are on a boundary
4. peek at (x+dx,y+dy), if it is not the same color C, you are hitting a boundary: turn left and goto 4.
5. x+=dx, y+=dy, i.e. take a step
6. record (x,y) as part of the boundary
7. if ( x==xstart && y==ystart ) you're done
8. turn right and goto 4.

turn left means: (dx',dy') = (dy,-dx), revolutions++

turn right means: (dx',dy') = (-dy,dx), revolutions--

revolutions will end up positive or negative, depending on the trace direction (inside/outside)

There is one corner case in which this loops indefinitely, namely when you start in an area of 1 pixel. This is easily checked. Furthermore you may want to check x/y boundaries. "Same color" and "other color" may of course also be implemented as some kind of color distance limit (i.e. |(r,g,b)-(R,G,B)|<D)

disclaimer this is a working, but simple, slow algorithm I cooked up once without the burden of any relevant knowledge or experience.

Answer 3

Your description isn't a hundred percent clear to me, but if I understand you correctly, you want to compute the following:

• the set of contiguously connected points of colour A which are adjacent to a point of colour B
• that contains the given starting point.

Given that specification, your code practically writes itself. The only thing you need to decide on now is what "contiguously connected" means (e.g., are pixels adjacent only at their corners connected or not?).

Also, your description is ambiguous. Consider a y-shaped region where the arms of the region are a single pixel wide: this would have three "endpoints" if you define endpoint to mean "member of the set with only one neighbour also in the set". If you relax your requirement to allow any number of endpoints then your code can collect the set of endpoints as it goes.

EDIT

Glad you solved your problem. I sketched out a solution which produces this for your sample problem:

1111***2222
111**222222
111*2222222
111*2222222
111***22222
11111*33322
11333333333

Here's the code, provided only since I need validation for having coded it :-) It's written for clarity rather than speed.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Drawing;

namespace StackOverflowEdgeDetection
{
    class Program
    {
        private static HashSet<Point> FindBorder(char[,] grid, Point start, char inside, char outside)
        {
            var border = new HashSet<Point> {};
            var endpoints = new HashSet<Point> { start };

            while (endpoints.Count != 0)
            {
                var p = endpoints.First();
                endpoints.Remove(p);
                border.Add(p);
                var newEndpoints = Neighbours(p).Where(q =>
                        Grid(grid, q) == inside &&
                        !border.Contains(q) &&
                        Neighbours(q).Any(r => Grid(grid, r) == outside)
                    );
                endpoints.UnionWith(newEndpoints);
            }

            return border;
        }

        private static IEnumerable<Point> Neighbours(Point p)
        {
            yield return new Point(p.X - 0, p.Y - 1);
            yield return new Point(p.X + 1, p.Y - 1);
            yield return new Point(p.X + 1, p.Y + 0);
            yield return new Point(p.X + 1, p.Y + 1);
            yield return new Point(p.X + 0, p.Y + 1);
            yield return new Point(p.X - 1, p.Y + 1);
            yield return new Point(p.X - 1, p.Y - 0);
            yield return new Point(p.X - 1, p.Y - 1);
        }

        public static char Grid(char[,] grid, Point p) {
            var x = p.X;
            var y = p.Y;
            var height = grid.GetLength(0);
            var width = grid.GetLength(1);
            return (0 <= x && x < width && 0 <= y && y < height) ? grid[y, x] : '\0';
        }

        static void Main(string[] args)
        {
            var border = FindBorder(TestGrid, TestStart, TestInside, TestOutside);

            var points = Enumerable.Range(0, TestHeight)
                                   .SelectMany(y => Enumerable.Range(0, TestWidth)
                                                              .Select(x => new Point(x, y)));

            foreach (var p in points) {
                Console.Write(border.Contains(p) ? '*' : Grid(TestGrid, p));
                if (p.X + 1 == TestWidth) Console.WriteLine();
            }

            Console.ReadLine();
        }

        private static readonly char[,] TestGrid = new char[,] {
            { '1', '1', '1', '1', '1', '1', '1', '2', '2', '2', '2' }, 
            { '1', '1', '1', '1', '1', '2', '2', '2', '2', '2', '2' }, 
            { '1', '1', '1', '1', '2', '2', '2', '2', '2', '2', '2' }, 
            { '1', '1', '1', '1', '2', '2', '2', '2', '2', '2', '2' }, 
            { '1', '1', '1', '1', '1', '1', '2', '2', '2', '2', '2' }, 
            { '1', '1', '1', '1', '1', '1', '3', '3', '3', '2', '2' }, 
            { '1', '1', '3', '3', '3', '3', '3', '3', '3', '3', '3' }
        };
        private static readonly Point TestStart = new Point(3, 3);
        private static readonly Point TestAdjacent = new Point(4, 3);
        private static readonly char TestInside = Grid(TestGrid, TestStart);
        private static readonly char TestOutside = Grid(TestGrid, TestAdjacent);
        private static readonly int TestWidth = TestGrid.GetLength(1);
        private static readonly int TestHeight = TestGrid.GetLength(0);
    }
}