Estudo e Implementação de um Algoritmo Eficaz para Detecção de Retas
Artigo (rev2): asano2.pdf
Artigo: asano.pdf
Introdução
O algoritmo conhecido como Transformada de Hough é o padrão de fato para o problema de detecção de retas a partir de contornos de imagens. Ele aplica o paradigma de dualidade, transformando pontos no espaço primal em curvas no espaço dual e calculando suas interseções.
Uma reta que passa em um ponto de borda é parametrizada pelo ângulo θ e a distância ρ da origem, gerando, assim uma curva senoidal no espaço dual θρ. A interseção de duas curvas corresponde a uma reta no espaço primal. O problema passa, então, a encontrar regiões no espaço dual com interseções acima de um mínimo, e que sejam um máximo local. Estas regiões correspondem às retas detectadas.
Sua fácil implementação e bom desempenho explicam sua popularidade. No entanto, a definição do limiar de detecção e da quantização de θ e ρ definem um compromisso entre a qualidade do resultado e o desempenho. [Asano02] mostra que a complexidade de tempo é O(n4), se todas os possíveis valores de θ e ρ são considerados. Como mostrado em [Asano02], estes valores não são infinitos, devido a divisão em pixels da imagem.
[Asano02] propõe outra dualidade, onde um ponto é transformado em um par de paralelas. O conjuntos de pontos de borda é transformado, então, em um arranjo de retas no plano. O problema passa a ser encontrar neste arranjo as faces máximas, que correspondem as retas detectadas. Isto pode ser feito em O(n²).
Neste trabalho o algoritmo de [Asano02] foi implementado utilizando [CGAL] e comparações com a implementação de Transformada de Hough da OpenCV foram feitas. Foi verificado que, em situações específicas , o algoritmo proposto consegue um desempenho melhor em tempo e detecção e que, com implementações adicionais, pode ser uma alternativa para o problema de detecção de retas,.
Referências:
[Asano02] Tetsuo ASANO, “Algorithmic Evaluation of Line Detection Problem”, Interdisciplinary Information Sciences, Vol. 8, 137-145, (2002) . http://www.jstage.jst.go.jp/article/iis/8/2/8_137/_article/-char/en
[CGAL] http://www.cgal.org