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 ?
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
(whereNx
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 by1
and we may have to select the previous run (I--
).If we move one position up,
Z
decreases byNx
and we may have to backtrack by several runs (I--
untilR[I].Z <= Z
again).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).