Самый быстрый алгоритм для дистанционного преобразования

Я ищу самый быстрый из доступных алгоритмов для преобразования расстояния.

Согласно этому сайту http://homepages.inf.ed.ac.uk/rbf/HIPR2/distance.htm , он описывает:

Преобразование расстояния можно вычислить намного эффективнее, используя умные алгоритмы всего за два прохода (например, Розенфельд и Пфальц, 1968).

Осматривая вокруг, я обнаружил: «Розенфельд, А и Пфальц, Дж. Л. 1968. Функции расстояния на цифровых фотографиях. Распознавание образов, 1, 33-61».

Но я считаю, что у нас должен быть лучший и более быстрый алгоритм, чем уже в 1968 году? На самом деле, я не смог найти источник с 1968 года, поэтому любая помощь высоко ценится.

Pedro F. Felzenszwalb и Daniel P. Huttenlocher опубликовали свою реализацию для преобразования расстояния . Вы не можете использовать его для объемных изображений, но, возможно, вы можете расширить его для поддержки 3D-данных. Я использовал его только как черный ящик.

В этой статье обсуждаются все современные точные преобразования расстояния:

«2D евклидовы преобразования расстояний: сравнительный обзор», ACM Computing Surveys, том 40, выпуск 1, февраль 2008 г. http://www.lems.brown.edu/~rfabbri/stuff/fabbri-EDT-survey-ACMCSurvFeb2008.pdf

В статье цитируется техника из Meijster, et. и др. как самое быстрое общее назначение, точное преобразование. Эта техника подробно здесь:

«Общий алгоритм вычисления дистанционных преобразований в линейное время», А. Мейстер, JBTM Roerdink и WH Hesselink. http://fab.cba.mit.edu/classes/S62.12/docs/Meijster_distance.pdf

Алгоритм Мейстера используется в моей библиотеке эффектов с открытым исходным кодом: https://github.com/vinniefalco/LayerEffects

Я надеюсь, что это помогает кому-то.

Вот код C # для 1- мерного квадратного евклидова преобразования расстояния в соответствии с работой Фельценшвальда и Хуттенлохера :

private static void DistanceTransform(double[] dataInput, ref double[] dataOutput)
{
    int n = dataInput.Length;

    int k = 0;
    int[] v = new int[n];
    double[] z = new double[n + 1];

    v[0] = 0;
    z[0] = Double.NegativeInfinity;
    z[1] = Double.PositiveInfinity;

    double s;

    for (int q = 1; q < n; q++)
    {
        while (true)
        {
            s = (((dataInput[q] + q * q) - (dataInput[v[k]] + v[k] * v[k])) / (2.0 * q - 2.0 * v[k]));

            if (s <= z[k])
            {
                k--;
            }
            else
            {
                break;
            }
        }

        k++;

        v[k] = q;
        z[k] = s;
        z[k + 1] = Double.PositiveInfinity;
    }

    k = 0;

    for (int q = 0; q < n; q++)
    {
        while (z[k + 1] < q)
        {
            k++;
        }

        dataOutput[q] = ((q - v[k]) * (q - v[k]) + dataInput[v[k]]);
    }
}

Это можно легко использовать для двоичных изображений и изображений в градациях серого, применив их сначала к столбцам изображений, а затем к строкам (или наоборот, конечно).

Преобразование действительно очень быстрое.

Вот исходные и выходные изображения:

Черные пиксели имеют значение 0, а белые имеют некоторое большое значение (должно быть больше, чем наибольшее возможное квадратное расстояние на изображениях, но не бесконечность), так что преобразование возвращает расстояние от черных пикселей, а белые пропускаются.

Чтобы получить истинное евклидово преобразование расстояния, просто возьмите квадратный корень каждого пикселя из выходного изображения.