5

A digital shape is a set of connected pixels in a binary image (a blob).

It can be compactly represented by run-length coding, i.e. grouping the pixels in horizontal line segments and storing the starting endpoint coordinates and the lengths. Usually, the RLC representation stores the runs in raster order, i.e. row by row and let to right.

For smooth shapes, the storage requirement drops from O(N²) to O(N).

The outline of a shape is a closed chain of pixels which restores the shape when its interior is filled (by a flood filling algorithm). It is also an O(N) representation. Wen the shape is available as a bitmap, the outline can be obtained by a contouring algorithm.

I am looking for an algorithm that directly computes the outline of a shape given its RLC representation, without drawing it in an intermediate bitmap. The algorithm is expected to run in time linear in the number of runs.

enter image description here

Have you come across a solution ?

  • 1
    Please have a look at your outline, it seems wrong. There's a pixel in the near the bottom left corner that is completely surrounded by blue and green pixels but nevertheless part of the outline. All other outline pixels seem to define "non-outline" as pixels that are surrounded by 4 neighbours, but this one pixel sticks out. – schnaader Sep 02 '15 at 14:08
  • 1
    What format do you expect the output to be in? A list of outline points? If so, do they need to be sorted in a particular order (e.g. clockwise winding)? – Jerry Federspiel Sep 02 '15 at 14:08
  • 1
    @schnaader: I fixed this. The figure is there for illustrative purposes. –  Sep 02 '15 at 14:29
  • @JerryFederspiel: yep, clockwise winding. –  Sep 02 '15 at 14:32

3 Answers3

1

A pixel is a boundary pixel if it is filled but adjacent to a pixel that is not filled. Given a per-row RLE encoding of the filled pixels, we can operate on three adjacent rows to compute a RLE version of the boundary pixels, then decode it.

Basically, we have a sweep line algorithm. With three rows like

   ***********   ****
************************
  ****        ******

we get event points (^) from the RLE:

   ***********   ****
************************
  ****        ******
^ ^^  ^       ^  ^  ^^  ^

The first thing to do is to designate middle filled pixels that have empty pixels above or below as boundary. (If you need guidance, the algorithms for set difference on a list of intervals are very similar.)

   ***********   ****
BBB***BBBBBBBBBBB***BBBB
  ****        ******

Then, for the intervals that are filled but not known to be boundaries, check whether left endpoint has space to the left and whether the right endpoint has space to the right. If so (respectively), they're boundaries.

David Eisenstat
  • 64,237
  • 7
  • 60
  • 120
  • Sorry, I didn't state it clearly, the outline should be produced as a chain, i.e. in clockwise order. Part of the challenge is to reorder the pixels found to be outline. –  Sep 02 '15 at 14:36
0

Note: This answer assumes that "non-outline" means "surrounded by 4 neighbours", so the result will be slightly different to your example (1 pixel green instead of blue).

All outline pixels are pixels where not all of the 4 "neighbour pixels" (left, right, above, below of the pixel) are set.

When decoding the RLC from top to bottom, you can get the outline pixels with the following pseudo code algorithm:

 For the first line
   All decoded pixels are outline pixels
 For the subsequent lines
   Leftmost and rightmost pixels of each RLC run are outline pixels
   All other pixels are outline pixels if:
     The pixel above isn't set (case A)
     The pixel below isn't set (case B)

Case A and B mean that you'll have to look at pixels above/below the current pixel, so the algorithm should actually be kind of pipelined/looking ahead one line, because case B will not be able to be detected until the next line was decoded.

EDIT: To sort the pixels in clockwise order afterwards, you can use the fact that your outline is a diagonally connected one-pixel-width line. Picking one of the pixels in the topmost line, you'll have two possible next pixels, follow the one that is right of, below or right and below the current pixel. After that, just follow the neighbour pixels that you haven't visited yet until there is no neighbour pixel. Example:

  /----- First pixel you pick, A and B are neighbour candidates, A is the "correct" one
  v
  xAxxx           
 B     x        
 x    x      xxx
 x     xxxxxx   x
  xx           x
    xxxxxxxxxxx

  s0123             Result after following the neighbours (s = start, e = end),
 e     4            numbers from 0-9 show order of traversal
 1    5      234
 0     678901   5
  98           6
    76543210987
schnaader
  • 49,103
  • 10
  • 104
  • 136
  • Sorry, I didn't state it clearly, the outline should be produced as a chain, i.e. in clockwise order. Part of the challenge is to reorder the pixels found to be outline. –  Sep 02 '15 at 14:35
  • @YvesDaoust: Added instructions on how to do the clockwise order sorting – schnaader Sep 03 '15 at 05:15
  • 1
    Clockwise winding doesn't mean by increasing angle, it means following the natural order of the chain of pixels when you turn around the shape clockwise. Due to concavities, the angles may not grow monotonically. –  Sep 03 '15 at 07:22
  • @YvesDaoust: You're correct. I think I found a better way for sorting, see my edit. – schnaader Sep 03 '15 at 07:42
  • That's conceptually right. One can show that the outline pixels have exactly two 8-connected neighbors so chain following is possible. But when you are at a pixel, how do you know which are these two neighbors ? Looking up the whole list would be too costly. –  Sep 03 '15 at 07:52
0

Hint:

As said in other answers, emitting the list of the outline pixels can be implemented as a sweepline process, during which the 3x3 neighborhoods of the run endpoints are examined.

This procedure will emit the pixels in a scrambled way, as a sequence of direct and reverse arcs that need to be stored and reordered.

An alternative could be based on the idea of implementing the standard Moore Neighborhood algorithm that has the advantage to enumerate the outline pixels in the desired order.

This procedure requires to know the 8-neighborhood configuration around the current pixel, and the idea is to update this neighborhood on every move to another pixel: we maintain indexes to the run that contains the current pixel and to the two facing runs in the rows above and below.

On every move to another pixel, we need to update these three indexes, which will involve short sequential searches in the list of sorted runs. This can be seen as a pseudo-random access mechanism to pixels, taking into account that the successive accesses are strongly local and can be sort-of cached.

Update:

In the run-length-coded representation that I use, only the black runs are coded, as triples (X, Y, L). The runs are sorted by rows top to bottom, and then left to right in a row.

For convenience, we can switch to a "linear adressing" scheme, as if all image rows had been appended after each other, and every pixel is designated by a single number Z = X + Y.Nx (where Nx is the image width).

So we have a list of black runs, and the white runs are implicitly found between two consecutive black ones.

During processing, we can remember at all times the index of the run that starts immediately before or on the current pixel (R[I].Z <= Z < R[I+1].Z). We can tell the color of the pixel by checking if we are inside the run or between it and the next (Z < R[I].Z + R[I].L).

If we move one position to the left, Z decreases by 1 and we may have to select the previous run (I--).

If we move one position up, Z decreases by Nx and we may have to backtrack by several runs (I-- until R[I].Z <= Z again).

enter image description here

The picture shows the current pixel and its 4-neighbors, as well as the"influence zones" of the black runs. We can handle all eight displacement directions similarly.

As we see, every move takes a number of operations at worse equal to the number of runs in a row, deemed to be a small value. Using this concept, we can traverse the RLC representation following an arbitrary path at a reasonable cost, without reconstructing the whole bitmap.

As the Moore Neighborhood algorithm takes time linear in the length of the outline, an implementation based on this linear run addressing will also take linear time (for a bounded number of runs per row).