Contour of a run-length-coded digital shape

Question

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.

Have you come across a solution ?

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