Bitmap border/stroke alogirthm?

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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):