# Bitmap border/stroke alogirthm?

I am looking for an algorithm that adds borders to a bitmap image(very much like the photoshop stroke effect) but one that will also have antialiasing to the borders(or one that copies alpha from the original bitmap to make the border look antialiased).

If you can't answer with an algorithm a direction of creating one myself would be great.

*Update*

The part coloured black is the original ellipse and the part coloured green is the stroke.

The stroke is basically adding a contour to the bitmap or edges.

-
Can you post an example before and after picture, I have no idea what the "photoshop stroke effect" is –  Martin Thompson Oct 27 '11 at 9:18
Here I have added an exampleof what I mean. –  Shedokan Oct 27 '11 at 11:19
FYI for anyone not familiar with Photoshop, it seems to use the alpha channel to determine where to apply the stroke. –  datageist Oct 27 '11 at 12:23
Sorry I thought that was implied... –  Shedokan Oct 27 '11 at 12:50
@Shedokan No prob, it's absolutely implied for anyone who has used PS a lot. Just good to emphasize it for those who haven't. –  datageist Oct 27 '11 at 12:58

## 3 Answers

The Euclidean Distance Transform can produce dilations and erosions with suitable parameters and filtering.

The algorithm that Photoshop uses, and the one that is best suited for stroking, is to calculate the Euclidean Distance Transform in integers and without taking the square root (i.e. calculate distance squared). This can be made extremely fast using the technique from Meijster.

To get anti-aliasing, just use the fractional part of the number after taking the square root.

For example:

if (distanceSquared < radius * radius)
{
(fill solid pixel)
}
else
{
distance = sqrt (distanceSquared);

if (distance < radius + 1)
{
alpha = 1 - (distance - radius);

(blend pixel at alpha)
}
}


This techinque is used in my open source library:

https://github.com/vinniefalco/LayerEffects.git

-
Thank you! I ended up using your method, and if I could I would give you +2 just for the AntiAliasing code! –  Shedokan Oct 8 '12 at 13:50

The dilation operator with a structuring element is not the way to go. "Stroking" the contour is not the way to go. The distance transform, on the other hand, is exactly the method used by Photoshop. A thresholded distance transform is the equivalent of dilation of a binary image. But how do we dilate a grayscale image? This is how Photoshop does it: Calculate the Euclidean Distance transform using the Chamfer 5-7-11 metric. This is described in the original paper by G. Borgefors ("Distance Transforms in Digital Images" G. Borgefors, Computer Vision, Graphics, and Image Processing #34). However, instead of using floating point numbers, use integers with 8 bits of fixed point precision for the weights (i.e. all multiplied by 256). If distance <= radius * 256 then output a fully opaque pixel. If distance < (radius + 1) * 256 then output a pixel with transparency = 256 - (distance - (radius * 256)). Else, the pixel is fully transparent. This is implemented in my open source library:

https://github.com/vinniefalco/LayerEffects

Note that this technique is superior to the answer I gave previously, and gives results which are completely identical to Photoshop.

-
Good stuff, Vinnie! I recognize your name from the Juce forums. –  Matt M. Dec 28 '12 at 3:00

This is just like the dilation morphological operator, which doesn't typically anti-alias. I can see a couple solutions based on what OpenCV (and other image processing libraries) can do:

1. Use the dilation operator with an anti-aliased structuring element (not supported in OpenCV)
2. Find contours, then stroke the contours with a wide antialiased brush:
• Use the alpha values to convert the image to a path - the contours
• Then use an antialised brush to stroke them.
3. Use the (Euclidean) distance transform and threshold the result near the desired offset distance (use a soft threshold to prevent edge aliasing):

-
Thank you for your answer! but I found it to be very vague, and it took me a while to understand it. Your second method looks to be perfect for what I need, it would be tricky to find all contours(including holes). –  Shedokan Oct 28 '11 at 11:20