====== Estudo e Implementação de um Algoritmo Eficaz para Detecção de Retas ======

//[[andre.cerqueira@gmail.com|André M L G Cerqueira]]//

Artigo (rev2): {{:cursos:visao:2008-1:grupo13:asano2.pdf}}

Artigo: {{:cursos:visao:2008-1:grupo13: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.

{{:cursos:visao:2008-1:grupo13:hough.png|:cursos:visao:2008-1:grupo13:hough.png}}

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²).

{{:cursos:visao:2008-1:grupo13:arrang.png|:cursos:visao:2008-1:grupo13:arrang.png}}

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]]

[OPENCV] [[http://sourceforge.net/projects/opencvlibrary/]]