Algoritmo mais rápido para transformação de distância

21

Estou procurando o algoritmo mais rápido disponível para a transformação à distância.

De acordo com este site http://homepages.inf.ed.ac.uk/rbf/HIPR2/distance.htm , ele descreve:

A transformação de distância pode ser calculada com muito mais eficiência usando algoritmos inteligentes em apenas duas passagens (por exemplo, Rosenfeld e Pfaltz 1968).

Pesquisando, descobri: "Rosenfeld, A e Pfaltz, J. L. 1968. Funções de Distância em Imagens Digitais. Reconhecimento de Padrões, 1, 33-61".

Mas acredito que já deveríamos ter um algoritmo melhor e mais rápido do que o de 1968? De fato, não consegui encontrar a fonte de 1968, então qualquer ajuda é muito apreciada.

Karl
fonte
Desculpe por atualizar esse encadeamento novamente, mas também estou tentando implementar o GDT, mas usando Python. def of_column (dataInput): output = zeros (dataInput.shape) n = len (dataInput) k = 0 v = zeros ((n,)) z = zeros ((n + 1)) v [0] = 0 z [0] = -inf z [1] = + inf s = 0 para q no intervalo (1, n): enquanto True: s = (((dataInput [q] + q * q)) - (dataInput [v [k ]] + v [k] * v [k])) / (2,0 * q - 2,0 * v [k])) se s <= z [k]: k - = 1 mais: quebra k + = 1 v [ k] = qz [k] = sz [k + 1] = + inf k = 0 para q na faixa (n): enquanto z [k + 1] <q: k + = 1 saída [q] = ((q - v [k]) * (q - v [k]) + dataInput [v [k]]) retorna a saída No entanto, quando offeri
mkli90
Por favor, faça uma nova pergunta. Não poste perguntas como respostas.
MBaz 27/03
Bem-vindo ao Signal Processing SE. Você pode fazer uma pergunta usando o "Fazer pergunta" no canto superior direito.
jojek

Respostas:

14

Pedro F. Felzenszwalb e Daniel P. Huttenlocher publicaram sua implementação para a transformação à distância . Você não pode usá-lo para imagens volumétricas, mas talvez possa estendê-lo para suportar dados 3D. Eu só usei como uma caixa preta.

bjoernz
fonte
Você sabe se isso é implementado no OpenCV?
Matt M.
Sim, para certos valores de maskSizee distanceType. Veja: opencv.willowgarage.com/documentation/cpp/…
bjoernz
existem implementações para imagens volumétricas (por exemplo, imagem de profundidade kinect) até agora?
Zhangxaochen
9

Este artigo discute todas as transformações exatas da distância moderna:

"Transformações de distância euclidiana em 2D: uma pesquisa comparativa", ACM Computing Surveys, Vol. 40, edição 1, fevereiro de 2008 http://www.lems.brown.edu/~rfabbri/stuff/fabbri-EDT-survey-ACMCSurvFeb2008.pdf

O artigo cita a técnica de Meijster, et. al. como o objetivo geral mais rápido, transformação exata. Esta técnica é detalhada aqui:

"Um algoritmo geral para transformações de distância computacional em tempo linear", A. Meijster, JBTM Roerdink e WH Hesselink. http://fab.cba.mit.edu/classes/S62.12/docs/Meijster_distance.pdf

O algoritmo Meijster é usado na minha biblioteca de efeitos de código aberto: https://github.com/vinniefalco/LayerEffects

Espero que isso ajude alguém.

Vinnie Falco
fonte
Seria útil saber onde em sua biblioteca podemos encontrar o código específico.
Akaltar
6

Aqui está um código C # para a transformação de distância euclidiana quadrada 1D de acordo com o artigo 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]]);
    }
}

Isso pode ser facilmente usado para imagens binárias e em escala de cinza, aplicando-o primeiro nas colunas de imagens e depois nas linhas (ou vice-versa, é claro).

A transformação é realmente muito rápida.

Aqui estão as imagens de origem e de saída:

insira a descrição da imagem aqui

insira a descrição da imagem aqui

Os pixels pretos têm valor 0 e o branco tem algum valor grande (deve ser maior que a maior distância quadrada possível nas imagens, mas não o infinito), de modo que a transformação retorne a distância dos pixels pretos e os brancos sejam omitidos.

Para obter a verdadeira transformação de distância euclidiana, basta obter uma raiz quadrada de cada pixel na imagem de saída.

Libor
fonte
Interessante. Qual é o uso comum da transformação à distância, Libor?
Spacey
1
Eu acho que os usos comuns estão em encontrar caminhos, segmentação, medidas geométricas (centro de massa) e efeitos (efeito chanfrado). Eu precisava da transformação de distância para a costura da imagem panorâmica - para encontrar uma máscara de mistura geometricamente ideal. Isso envolveu a transformação da distância percorrida em cada imagem e a computação da máscara de mistura a partir dos pesos.
Libor
1
A transformação de distância pode ser usada em imagens [de borda] correspondentes, uma técnica sendo "correspondência de chanfro" ( umiacs.umd.edu/~mingyliu/papers/liu_cvpr2010.pdf ). O TD também pode ser usado para encontrar o eixo medial (esqueleto) e executar outras tarefas, como a Libor mencionada.
Rethunk 19/09/12