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

21

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

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

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

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

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

Карл
источник
Извините за то, что снова завел этот поток, но я тоже пытаюсь реализовать GDT, но с использованием Python. def of_column (dataInput): output = нули (dataInput.shape) n = len (dataInput) k = 0 v = нули ((n,)) z = нули ((n + 1,)) v [0] = 0 z [0] = -inf z [1] = + inf s = 0 для q в диапазоне (1, n): тогда как True: s = (((dataInput [q] + q * q) - (dataInput [v [k] ]] + v [k] * v [k])) / (2,0 * q - 2,0 * v [k])), если s <= z [k]: k - = 1 остальное: break k + = 1 v [ k] = qz [k] = sz [k + 1] = + inf k = 0 для q в диапазоне (n): в то время как z [k + 1] <q: k + = 1 выход [q] = ((q - v [k]) * (q - v [k]) + dataInput [v [k]]) возвращать выходные данные Однако, когда предложить
mkli90
Пожалуйста, задайте новый вопрос. Не публикуйте вопросы как ответы.
MBaz
Добро пожаловать в обработку сигналов SE. Вы можете задать вопрос, используя «Задать вопрос» в правом верхнем углу.
jojek

Ответы:

14

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

bjoernz
источник
Вы случайно не знаете, реализовано ли это в OpenCV?
Мэтт М.
Да, для определенных значений maskSizeи distanceType. См: opencv.willowgarage.com/documentation/cpp/...
bjoernz
Существуют ли какие-либо реализации для объемных изображений (например, изображение глубины Kinect) до сих пор?
zhangxaochen
9

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

«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

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

Винни Фалько
источник
Было бы полезно узнать, где в вашей библиотеке мы можем найти конкретный код.
Акалтар
6

Вот код 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, а белые имеют некоторое большое значение (должно быть больше, чем наибольшее возможное квадратное расстояние на изображениях, но не бесконечность), так что преобразование возвращает расстояние от черных пикселей, а белые пропускаются.

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

ЛИБОР
источник
Интересный. Какое общее использование дистанционной трансформации, Libor?
Спейси
1
Я думаю, что общее использование - это поиск путей, сегментация, геометрические измерения (центр масс) и эффекты (эффект скоса). Мне нужно было преобразовать расстояние для сшивания панорамного изображения - чтобы найти геометрически оптимальную маску наложения. Это включало преобразование дистанции бега на каждом изображении, а затем вычисление маски смешивания по весам.
Libor
1
Преобразование расстояний можно использовать при сопоставлении изображений [ребер], одним из методов является «сопоставление фасок » ( umiacs.umd.edu/~mingyliu/papers/liu_cvpr2010.pdf ). DT также можно использовать для поиска средней оси (скелета) и для выполнения других задач, таких как упомянутый Libor.
Отключено