Sigma*

[snibgo]

I'd like a fast Euclidean algorithm. Creating a spiral mask for video transitions, 2M pixels, Euclidean:2 takes 24 minutes. I only need it once per edit session rather than once per frame (phew!), but it would be great if it was faster.

Yeah, I know, a good feature comes along, and then I moan that I want it faster. And IM is open source, so if I was reasonable programmer (I can't even compile IM under Windows), I'd do it myself.

Meantime, I have a good excuse for long coffee breaks.

[thevinn]

NOTE normal distance kernels in IM use 100 as the orgongonal neighbour distance scale, where chamfor uses a scale of '5'
It may be a interesting 'specialized' distance kernel appropriate to images needing HIGH distances, and a good interger distance results.

I use these weights:

Code: Select all

    // Kernel values from
    //
    // Muhammad Akmal Butt and Petros Maragos
    //  "Optimum Design of Chamfer Distance Transforms"
    //
    // Optimal values for 5x5 neighborhood:
    //  0.9866, sqrt(2), 2.2062
    //
    // The kernel is designed to also convert to fixed point.
    //
    static int const d1 = 253; // 252.6 = 256 * 0.9866
    static int const d2 = 362; // 362.0 = 256 * 1.4142
    static int const d3 = 566; // 565.8 = 256 * 2.2062

The reason I am using these values is because it will also convert to fixed point integers (with 8 bits of fractional precision) at no additional cost. The application of the Box Blur after the distance transform has to be done with fractional precision in order to maintain accuracy, or else you get banding when applying the contour curve.

My open source project which implements these effects in real time is here:

https://github.com/vinniefalco/LayerEffects

Here are some example results using the latest technique I described:

[anthony]

I'd like a fast Euclidean algorithm. Creating a spiral mask for video transitions, 2M pixels, Euclidean:2 takes 24 minutes. I only need it once per edit session rather than once per frame (phew!), but it would be great if it was faster.

Euclidean:2 that is a long time for a simple two pass algorithm! How big is your image? Also what version of IM. The 2 pass (on forward on reverse) distance transform system was added to IM v6.6.9-4

The multi or iterative distance method is still available but is only really needed for constrained distance methods.