Algoritmo más rápido para transformación de distancia

21

Estoy buscando el algoritmo más rápido disponible para la transformación de distancia.

De acuerdo con este sitio http://homepages.inf.ed.ac.uk/rbf/HIPR2/distance.htm , describe:

La transformación de distancia se puede calcular de manera mucho más eficiente utilizando algoritmos inteligentes en solo dos pasadas (por ejemplo, Rosenfeld y Pfaltz 1968).

Al buscar, encontré: "Rosenfeld, A y Pfaltz, J L. 1968. Funciones de distancia en imágenes digitales. Reconocimiento de patrones, 1, 33-61".

¿Pero creo que deberíamos tener un algoritmo mejor y más rápido que el de 1968? De hecho, no pude encontrar la fuente de 1968, por lo que cualquier ayuda es muy apreciada.

Karl
fuente
Perdón por volver a subir este hilo, pero estoy tratando de implementar el GDT también, pero usando Python. def of_column (dataInput): salida = ceros (dataInput.shape) n = len (dataInput) k = 0 v = ceros ((n,)) z = ceros ((n + 1,)) v [0] = 0 z [0] = -inf z [1] = + inf s = 0 para q en el rango (1, n): while True: s = (((dataInput [q] + q * q) - (dataInput [v [k ]] + v [k] * v [k])) / (2.0 * q - 2.0 * v [k])) si s <= z [k]: k - = 1 más: romper k + = 1 v [ k] = qz [k] = sz [k + 1] = + inf k = 0 para q en el rango (n): mientras que z [k + 1] <q: k + = 1 salida [q] = ((q - v [k]) * (q - v [k]) + entrada de datos [v [k]]) salida de retorno Sin embargo cuando se ofrecei
mkli90
Por favor haga una nueva pregunta. No publique preguntas como respuestas.
MBaz
Bienvenido a Signal Processing SE. Puede hacer una pregunta usando la opción "Hacer pregunta" en la esquina superior derecha.
jojek

Respuestas:

14

Pedro F. Felzenszwalb y Daniel P. Huttenlocher han publicado su implementación para la transformación a distancia . No puede usarlo para imágenes volumétricas, pero tal vez pueda extenderlo para admitir datos en 3D. Solo lo he usado como una caja negra.

bjoernz
fuente
¿Sabes si esto se implementa en OpenCV?
Matt M.
Sí, para ciertos valores de maskSizey distanceType. Ver: opencv.willowgarage.com/documentation/cpp/…
bjoernz
¿Hay alguna implementación para imágenes volumétricas (por ejemplo, imagen de profundidad de cinect) hasta ahora?
zhangxaochen
9

Este artículo analiza todas las transformaciones de distancia exactas modernas:

"Transformaciones de distancia euclidiana 2D: una encuesta comparativa", ACM Computing Surveys, Vol. 40, Número 1, febrero de 2008 http://www.lems.brown.edu/~rfabbri/stuff/fabbri-EDT-survey-ACMCSurvFeb2008.pdf

El artículo cita la técnica de Meijster, et. Alabama. como el propósito general más rápido, transformación exacta. Esta técnica se detalla aquí:

"Un algoritmo general para calcular transformaciones de distancia en tiempo lineal", A. Meijster, JBTM Roerdink y WH Hesselink. http://fab.cba.mit.edu/classes/S62.12/docs/Meijster_distance.pdf

El algoritmo Meijster se usa en mi biblioteca de efectos de código abierto: https://github.com/vinniefalco/LayerEffects

Espero que esto ayude a alguien.

Vinnie Falco
fuente
Sería útil saber en qué parte de su biblioteca podemos encontrar el código en particular.
akaltar
6

Aquí hay un código C # para la transformación de distancia euclidiana al cuadrado 1D según el artículo de Felzenszwald & Huttenlocher :

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]]);
    }
}

Esto se puede usar fácilmente para imágenes binarias y en escala de grises aplicándolas primero en columnas de imagen y luego en filas (o viceversa, por supuesto).

La transformación es de hecho muy rápida.

Aquí están las imágenes de origen y salida:

ingrese la descripción de la imagen aquí

ingrese la descripción de la imagen aquí

Los píxeles negros tienen el valor 0 y los blancos tienen un valor grande (deben ser mayores que la distancia al cuadrado más grande posible en las imágenes pero no infinito) para que la transformación devuelva la distancia de los píxeles negros y se omitan los blancos.

Para obtener una verdadera transformación de distancia euclidiana, simplemente tome una raíz cuadrada de cada píxel de la imagen de salida.

Libor
fuente
Interesante. ¿Cuál es un uso común de la transformación de distancia, Libor?
Spacey
1
Creo que los usos comunes son encontrar caminos, segmentación, medidas geométricas (centro de masa) y efectos (efecto de bisel). Necesitaba una transformación de distancia para la unión de imágenes panorámicas, para encontrar una máscara de mezcla geométricamente óptima. Esto implicaba una distancia de carrera transformada en cada imagen y luego calcular la máscara de mezcla de los pesos.
Libor
1
La transformación de distancia se puede usar para hacer coincidir imágenes [de borde], una técnica es la "coincidencia de chaflán" ( umiacs.umd.edu/~mingyliu/papers/liu_cvpr2010.pdf ). El DT también se puede utilizar para encontrar el eje medial (esqueleto) y para realizar otras tareas como la mencionada Libor.
Rethunk