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.
Respostas:
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.
fonte
maskSize
edistanceType
. Veja: opencv.willowgarage.com/documentation/cpp/…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.
fonte
Aqui está um código C # para a transformação de distância euclidiana quadrada 1D de acordo com o artigo de Felzenszwald & Huttenlocher :
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:
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.
fonte