Algorithme le plus rapide pour la transformation de distance

21

Je recherche l'algorithme le plus rapide disponible pour la transformation de distance.

Selon ce site http://homepages.inf.ed.ac.uk/rbf/HIPR2/distance.htm , il décrit:

La transformation de distance peut être calculée beaucoup plus efficacement en utilisant des algorithmes intelligents en seulement deux passes (par exemple Rosenfeld et Pfaltz 1968).

En cherchant autour, j'ai trouvé: "Rosenfeld, A et Pfaltz, J L. 1968. Fonctions de distance sur les images numériques. Reconnaissance de formes, 1, 33-61."

Mais je pense que nous devrions déjà avoir un algorithme meilleur et plus rapide que celui de 1968? En fait, je n'ai pas pu trouver la source de 1968, donc toute aide est très appréciée.

Karl
la source
Désolé d'avoir récupéré ce fil, mais j'essaie également d'implémenter le GDT, mais en utilisant Python. def of_column (dataInput): output = zéros (dataInput.shape) n = len (dataInput) k = 0 v = zéros ((n,)) z = zéros ((n + 1,)) v [0] = 0 z [0] = -inf z [1] = + inf s = 0 pour q dans la plage (1, n): tandis que 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 sinon: break k + = 1 v [ k] = qz [k] = sz [k + 1] = + inf k = 0 pour q dans la plage (n): tandis que z [k + 1] <q: k + = 1 sortie [q] = ((q - v [k]) * (q - v [k]) + dataInput [v [k]]) retourne la sortie Cependant quand offeri
mkli90
Veuillez poser une nouvelle question. Ne postez pas de questions comme réponses.
MBaz
Bienvenue dans Signal Processing SE. Vous pouvez poser une question en utilisant la "Poser une question" dans le coin supérieur droit.
jojek

Réponses:

14

Pedro F. Felzenszwalb et Daniel P. Huttenlocher ont publié leur implémentation pour la transformation de distance . Vous ne pouvez pas l'utiliser pour des images volumétriques, mais vous pouvez peut-être l'étendre pour prendre en charge les données 3D. Je ne l'ai utilisé que comme boîte noire.

bjoernz
la source
Savez-vous si cela est implémenté dans OpenCV?
Matt M.
Oui, pour certaines valeurs de maskSizeet distanceType. Voir: opencv.willowgarage.com/documentation/cpp/…
bjoernz
Existe-t-il jusqu'à présent des implémentations pour les images volumétriques (par exemple, l'image de profondeur kinect)?
zhangxaochen
9

Cet article traite de toutes les transformations de distance exactes modernes:

"2D Euclidean distance transforms: a comparative survey", ACM Computing Surveys, Vol 40, numéro 1, février 2008 http://www.lems.brown.edu/~rfabbri/stuff/fabbri-EDT-survey-ACMCSurvFeb2008.pdf

L'article cite la technique de Meijster, et. Al. comme la transformation exacte la plus polyvalente. Cette technique est détaillée ici:

"Un algorithme général pour calculer les transformations de distance en temps linéaire", A. Meijster, JBTM Roerdink et WH Hesselink. http://fab.cba.mit.edu/classes/S62.12/docs/Meijster_distance.pdf

L'algorithme Meijster est utilisé dans ma bibliothèque d'effets open source: https://github.com/vinniefalco/LayerEffects

J'espère que ça aidera quelqu'un.

Vinnie Falco
la source
Il serait utile de savoir où dans votre bibliothèque pouvons-nous trouver le code particulier.
akaltar
6

Voici un code C # pour la transformation de distance euclidienne au carré 1D selon l'article 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]]);
    }
}

Cela peut être facilement utilisé pour les images binaires et en niveaux de gris en l'appliquant d'abord sur les colonnes d'images, puis sur les lignes (ou vice versa, bien sûr).

La transformation est en effet très rapide.

Voici les images source et de sortie:

entrez la description de l'image ici

entrez la description de l'image ici

Les pixels noirs ont la valeur 0 et le blanc a une valeur importante (doit être plus grande que la plus grande distance au carré possible dans les images mais pas l'infini) de sorte que la transformation renvoie la distance des pixels noirs et les blancs sont omis.

Pour obtenir une véritable transformation de distance euclidienne, il suffit de prendre une racine carrée de chaque pixel de l'image de sortie.

Libor
la source
Intéressant. Quelle est l'utilisation courante de la transformation de distance, Libor?
Spacey
1
Je pense que les utilisations courantes sont dans la recherche de chemins, de segmentation, de mesures géométriques (centre de masse) et d'effets (effet de biseau). J'avais besoin d'une transformation de distance pour l'assemblage d'images panoramiques - pour trouver un masque de fusion géométriquement optimal. Cela impliquait la transformation de la distance sur chaque image, puis le calcul du masque de fusion à partir des poids.
Libor
1
La transformation de distance peut être utilisée pour faire correspondre des images [d'arête], une technique étant la "correspondance de chanfrein" ( umiacs.umd.edu/~mingyliu/papers/liu_cvpr2010.pdf ). Le DT peut également être utilisé pour trouver l'axe médial (squelette) et pour effectuer d'autres tâches telles que Libor mentionné.
Rethunk