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.)