Length contour of digital form

Question

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

It can be compactly represented by encoding the path length, that is, by grouping pixels in segments of a horizontal line and preserving the coordinates of the starting point and lengths. Typically, the RLC view stores runs in raster order, that is, in rows and to the right.

For smooth forms, the storage requirement falls from O (N²) to O (N).

The shape contour is a closed chain of pixels that restores the shape when its inner area is filled (using the fill fill algorithm). It is also an O (N) representation. Wen shape is available as a bitmap, the outline can be obtained using the outline .

I am looking for an algorithm that directly calculates the shape contour, given its RLC representation, without drawing it in an intermediate bitmap. It is expected that the algorithm will be executed in time linear in the number of runs.

Have you encountered a solution?

Answer 1

A pixel is a border pixel if it is full, but next to a pixel that is not full. When using RLE coding of filled pixels for each row, we can work with three adjacent lines to calculate the RLE version of the boundary pixels, and then decode it.

Basically, we have a sweep line algorithm. With three type strings

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

we get event points ( ^ ) from RLE:

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

The first thing to do is to designate the middle filled pixels with empty pixels above or below as a border. (If you need guidance, the algorithms for a given difference in the interval list are very similar.)

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

Then for intervals that are filled but not known by boundaries, check if the left endpoint has space on the left and whether the right endpoint has space on the right. If so (respectively), these are boundaries.

Answer 2

Note. This answer assumes that "outlined" means "surrounded by 4 neighbors", so the result will be slightly different from your example (1 pixel is green, not blue).

All edge pixels are pixels in which not all 4 “neighboring pixels” (left, right, above, below the pixel) are set.

When decoding RLC from top to bottom, you can get edge 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) 

Cases A and B mean that you will need to look at pixels above / below the current pixel, so the algorithm must be really pipelined / promising in one line, because case B cannot be detected until the next line has been decrypted.

EDIT: To sort the pixels in clockwise order, you can use the fact that your outline is diagonally connected with a width of one pixel. Choosing one of the pixels in the very top row, you will have two possible next pixels, follow to the right of, below or to the right and below the current pixel. After that, just follow the neighboring pixels that you have not visited until there is a neighboring pixel. Example:

  /----- First pixel you pick, A and B are neighbour candidates, A is the "correct" one v xAxxx B xxx 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 

Answer 3

hint

As stated in other answers, the radiation from the list of contour pixels can be implemented as a sweepline process, during which the neighborhood of 3x3 launch endpoints is investigated.

This procedure will emit pixels in a scrambled manner, as a sequence of forward and reverse arcs that need to be saved and reordered.

An alternative may be based on the idea of ​​introducing a standard Moore neighborhood algorithm, which has the advantage of listing edge pixels in the desired order.

This procedure requires knowing the 8-circle configuration around the current pixel, and the idea is to update this neighborhood every time we switch to another pixel: we support indexes for the run that contains the current pixel, and for the two runs that access it in the lines above and below.

Each time we switch to another pixel, we need to update these three indexes, which will include short sequential searches in the list of sorted runs. This can be considered as a pseudo-random access mechanism for pixels, taking into account that sequential calls are very local and can be cached.

---

Update

In the encoded representation with the string length that I use, only black runs are encoded, in the form of a triple (X, Y, L) . Runs are sorted in rows from top to bottom, and then from left to right in a row.

For convenience, we can proceed to the “linear addressing” scheme, as if all lines of images were added to each other, and each pixel is denoted by one number Z = X + Y.Nx (where Nx is the image width).

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

During processing, we always remember the start index, which begins immediately before or at the current pixel ( R[I].Z <= Z < R[I+1].Z ). We can specify the color of the pixel by checking if we are inside the path or between it and the next one ( Z < R[I].Z + R[I].L ).

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

If we move one position up, Z decreases by Nx , and we may need to retreat a few runs ( I-- to R[I].Z <= Z again).

The figure shows the current pixel and its 4 neighbors, as well as the “influence zones” of the black runs. We can also handle all eight offset directions.

As we see, each step takes several operations, the worst, equal to the number of runs in a row, which is considered small. Using this concept, we can cross the RLC view in any way at a reasonable price without restoring the entire bitmap.

Since the Moore neighborhood algorithm takes time linear in the length of the contour, an implementation based on this addressing with a linear run will also take linear time (for a limited number of runs per line).