Algorithm for drawing an outline or stroke around any alpha transparent image

Question

I'm not sure if there is any name for this algorithm that I am developing now - the “growing neighborhood algorithm” sounds like the corresponding name. So what is my problem?

I would like to draw a stroke around an alpha transparent image to describe it. The size of the stroke should be determined by the user.

I have an array that is filled with zeros and ones, consider each element of the array as a cell, as in Game of Life. Element with 0 is empty (transparent pixel), element with 1 is the cell of the first generation (opaque pixel), the number of generations is determined by the size of the surrounding stroke.

This example shows a rectangle surrounded by alpha values:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

Then I would like them to grow in a new generation, surrounding each neighbor Moore from 0 generations. This is the second generation (move with 1px) - so the array looks like this:

 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 2 2 0 0 0 0 2 1 1 1 1 2 0 0 0 0 2 1 1 1 1 2 0 0 0 0 2 1 1 1 1 2 0 0 0 0 2 1 1 1 1 2 0 0 0 0 2 2 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

3rd and 4th generation (3px move):

 4 4 4 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 4 4 3 2 2 2 2 2 2 3 4 4 3 2 1 1 1 1 2 3 4 4 3 2 1 1 1 1 2 3 4 4 3 2 1 1 1 1 2 3 4 4 3 2 1 1 1 1 2 3 4 4 3 2 2 2 2 2 2 3 4 4 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 

So far so good. I accomplish this simple task with the following code snippet:

 for (int gen = 1; gen <= 4; gen++) { for (int x = 1; x < arrayWidth - 1; x++) { for (int y = 1; y < arrayHeight - 1; y++) { // See if this cell is in the current generation. if (_generation[x + arrayWidth * y] == gen) { // Generate next generation. for (int i = x - 1; i <= x + 1; i++) { for (int j = y - 1; j <= y + 1; j++) { if (_generation[i + arrayWidth * j] == 0 || _generation[i + arrayWidth * j] > gen) { _generation[i + arrayWidth * j] = gen + 1; } } } } } } } 

This approach works great for simple shapes, such as a rectangle. But how can I do this for an ellipse? As soon as we have a view of the stairs in the cells, I get dirty results:

 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 2 2 0 0 0 0 0 0 0 2 2 1 1 1 1 2 2 0 0 0 0 0 2 2 1 1 1 1 1 1 2 2 0 0 0 2 2 1 1 1 1 1 1 1 1 2 2 0 0 2 1 1 1 1 1 1 1 1 1 1 2 0 0 2 1 1 1 1 1 1 1 1 1 1 2 0 0 2 1 1 1 1 1 1 1 1 1 1 2 0 0 2 1 1 1 1 1 1 1 1 1 1 2 0 0 2 1 1 1 1 1 1 1 1 1 1 2 0 0 2 2 1 1 1 1 1 1 1 1 2 0 0 0 0 2 2 1 1 1 1 1 1 2 2 0 0 0 0 0 2 2 1 1 1 1 2 2 0 0 0 0 0 0 0 2 2 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 3 3 3 3 3 3 3 0 0 0 0 0 3 3 2 2 2 2 2 2 3 3 0 0 0 3 3 2 2 1 1 1 1 2 2 3 3 0 3 3 2 2 1 1 1 1 1 1 2 2 3 3 3 2 2 1 1 1 1 1 1 1 1 2 2 3 3 2 1 1 1 1 1 1 1 1 1 1 2 3 3 2 1 1 1 1 1 1 1 1 1 1 2 3 3 2 1 1 1 1 1 1 1 1 1 1 2 3 3 2 1 1 1 1 1 1 1 1 1 1 2 3 3 2 1 1 1 1 1 1 1 1 1 1 2 3 3 2 2 1 1 1 1 1 1 1 1 2 2 3 3 3 2 2 1 1 1 1 1 1 2 2 3 3 0 3 3 2 2 1 1 1 1 2 2 3 3 0 0 0 3 3 2 2 2 2 2 2 3 3 0 0 0 0 0 3 3 3 3 3 3 3 3 0 0 0 

When applying this algorithm to an ellipse, the circuit looks strange due to this problem (left: algorithm result, right: requested result):

The problem here is that I do not want to have these 2 2 and 3 3 duplicate blocks that occur every time I have this “staircase” pattern:

 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 

I want the above calculations of the second and third generations to look like this:

 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 0 0 0 0 0 0 0 0 0 2 1 1 1 1 2 0 0 0 0 0 0 0 2 1 1 1 1 1 1 2 0 0 0 0 0 2 1 1 1 1 1 1 1 1 2 0 0 0 2 1 1 1 1 1 1 1 1 1 1 2 0 0 2 1 1 1 1 1 1 1 1 1 1 2 0 0 2 1 1 1 1 1 1 1 1 1 1 2 0 0 2 1 1 1 1 1 1 1 1 1 1 2 0 0 2 1 1 1 1 1 1 1 1 1 1 2 0 0 0 2 1 1 1 1 1 1 1 1 2 0 0 0 0 0 2 1 1 1 1 1 1 2 0 0 0 0 0 0 0 2 1 1 1 1 2 0 0 0 0 0 0 0 0 0 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 3 3 3 0 0 0 0 0 0 0 0 0 3 2 2 2 2 2 3 0 0 0 0 0 0 3 2 1 1 1 1 2 3 0 0 0 0 0 3 2 1 1 1 1 1 1 2 3 0 0 0 3 2 1 1 1 1 1 1 1 1 2 3 0 3 2 1 1 1 1 1 1 1 1 1 1 2 3 3 2 1 1 1 1 1 1 1 1 1 1 2 3 3 2 1 1 1 1 1 1 1 1 1 1 2 3 3 2 1 1 1 1 1 1 1 1 1 1 2 3 3 2 1 1 1 1 1 1 1 1 1 1 2 3 0 3 2 1 1 1 1 1 1 1 1 2 3 0 0 0 3 2 1 1 1 1 1 1 2 3 0 0 0 0 0 3 2 1 1 1 1 2 3 0 0 0 0 0 0 3 2 2 2 2 2 2 3 0 0 0 0 0 0 0 3 3 3 3 3 3 0 0 0 0 

I have tried many methods to filter these duplicate cell blocks, but I cannot find a simple and general solution to solve the problem.

Any ideas on how to get a stroke / outline as I get from Photoshop or Paint.NET?

Thanks!

Greetings P

Answer 1

Proper name dilation , check morphological operations. You should try the extension with the circle element, this will give you the requested result.

Here is the Matlab code that shows how to do this:

 im = imcircle(70); im = padarray(im,[20,20]); figure;imshow(im); im2 = imdilate(im,strel('disk',8)); figure;imshow(im2);