Hough transform

Usando a direção do gradiente para reduzir o número de votosEditar

Uma melhoria sugerida por O’Gorman e Clowes pode ser usada para detectar linhas se se levar em conta que o gradiente local da intensidade da imagem será necessariamente ortogonal à borda. Como a detecção de borda geralmente envolve o cálculo da magnitude do gradiente de intensidade, a direção do gradiente é frequentemente encontrada como um efeito colateral. Se um dado ponto de coordenadas (x,y) estiver de facto numa linha, então a direcção local do gradiente dá o parâmetro θ correspondente a essa linha, e o parâmetro r é então imediatamente obtido. (Shapiro e Stockman, 305) A direção do gradiente pode ser estimada dentro de 20°, o que encurta o traço sinusoidal dos 180° completos para cerca de 45°. Isto reduz o tempo de computação e tem o interessante efeito de reduzir o número de votos inúteis, aumentando assim a visibilidade dos picos correspondentes às linhas reais na imagem.

Transformada Hough (KHT)Edit

Fernandes e Oliveira sugeriram um esquema de votação melhorado para a transformada Hough que permite a implementação de um software para alcançar um desempenho em tempo real mesmo em imagens relativamente grandes (por exemplo, 1280×960). A transformada Hough baseada no Kernel usa o mesmo ( r , θ ) {\displaystyle (r,\theta )}

parametrização proposta por Duda e Hart mas opera em clusters de pixels aproximadamente colineares. Para cada cluster, os votos são emitidos usando um kernel elíptico-gaussiano orientado que modela a incerteza associada com a linha de melhor ajuste com respeito ao cluster correspondente. A abordagem não só melhora significativamente o desempenho do esquema de votação, mas também produz um acumulador muito mais limpo e torna a transformação mais robusta para a detecção de linhas espúrias.

Transformada Hough 3-D baseada no Kernel para detecção plana (3DKHT)Edit

Limberger e Oliveira sugeriram uma técnica determinística para detecção plana em nuvens de pontos não organizados cujo custo é n log ( n ) {\displaystyle n\log(n)}

no número de amostras, alcançando desempenho em tempo real para conjuntos de dados relativamente grandes (até 10 5 ^{\\possui 10^{5}}

pontos em uma CPU de 3,4 GHz). É baseado em uma estratégia de votação rápida Hough-transform para regiões planares, inspirada na transformada Hough baseada no Kernel (KHT). Esta transformação 3D baseada no Kernel (3DKHT) usa um algoritmo rápido e robusto para segmentar clusters de amostras aproximadamente co-planares, e lança votos para clusters individuais (ao invés de para amostras individuais) em um ( θ , ϕ , ρ {\displaystyle \theta ,\phi ,\rho }

) acumulador esférico usando um grão trivariado gaussiano. A abordagem é várias ordens de magnitude mais rápida do que as técnicas existentes (não determinísticas) para detecção plana em nuvens de pontos, tais como RHT e RANSAC, e escalas melhores com o tamanho dos conjuntos de dados. Pode ser usado com qualquer aplicação que requeira detecção rápida de características planas em grandes conjuntos de dados.

Transformada de curvas, e sua generalização para formas analíticas e não analíticasEditar

Embora a versão da transformação descrita acima se aplique somente para encontrar linhas retas, uma transformação similar pode ser usada para encontrar qualquer forma que possa ser representada por um conjunto de parâmetros. Um círculo, por exemplo, pode ser transformado em um conjunto de três parâmetros, representando seu centro e raio, de modo que o espaço Hough se torne tridimensional. Elipses e curvas arbitrárias também podem ser encontradas desta forma, assim como qualquer forma facilmente expressa como um conjunto de parâmetros.

A generalização da transformação Hough para detecção de formas analíticas em espaços com qualquer dimensionalidade foi proposta por Fernandes e Oliveira. Ao contrário de outras abordagens baseadas na transformação de Hough para formas analíticas, a técnica de Fernandes não depende da forma que se quer detectar nem do tipo de dados de entrada. A detecção pode ser conduzida a um tipo de forma analítica alterando o modelo de geometria assumido onde os dados foram codificados (por exemplo, espaço euclidiano, espaço projectivo, geometria conformal, etc.), enquanto a formulação proposta permanece inalterada. Além disso, garante que as formas pretendidas são representadas com o menor número possível de parâmetros e permite a detecção simultânea de diferentes tipos de formas que melhor se ajustam a um conjunto de entradas com diferentes dimensionalidades e diferentes definições geométricas (por exemplo, a detecção simultânea de planos e esferas que melhor se ajustam a um conjunto de pontos, linhas rectas e círculos).

Para formas mais complicadas no plano (ou seja A transformada Generalizada Hough é utilizada, o que permite votar numa determinada posição, orientação e/ou escala da forma através de uma tabela pré-definida. A transformada Hough acumula contribuições de todos os pixels na borda detectada.

Processo de detecção de círculosEditar

Alterar o algoritmo para detectar formas circulares em vez de linhas é relativamente simples.

• Primeiro, criamos o espaço do acumulador, que é composto por uma célula para cada pixel. Inicialmente cada célula é definida como 0.
• Para cada ponto de borda (i, j) na imagem, incremente todas as células que de acordo com a equação de um círculo ( i – a ) 2 + ( j – b ) 2 = r 2 {\displaystyle (i-a)^{2}+(j-b)^{2}=r^{2}}}
  

  poderia ser o centro de um círculo. Estas células são representadas pela letra a {\displaystyle a}

  

  na equação.

• Para cada valor possível de um {\displaystyle a}
  

  encontrado no passo anterior, encontre todos os valores possíveis de b {\displaystyle b}

  

  que satisfaçam a equação.

• Procure os máximos locais no espaço do acumulador. Estas células representam círculos que foram detectados pelo algoritmo.

Se não soubermos previamente o raio do círculo que estamos a tentar localizar, podemos usar um espaço tridimensional do acumulador para procurar círculos com um raio arbitrário. Naturalmente, isto é mais caro em termos computacionais.

Este método também pode detectar círculos que estão parcialmente fora do espaço do acumulador, desde que ainda haja suficiente área do círculo dentro dele.

Detecção de objetos 3D (Planos e cilindros)Editar

Tudo a transformação também pode ser usada para a detecção de objetos 3D em dados de alcance ou nuvens de pontos 3D. A extensão da clássica transformada Hough para a detecção de planos é bastante simples. Um plano é representado pela sua equação explícita z = a x x + a y y + d {\displaystyle z=a_{x}x+a_{y}y+d}

para o qual podemos usar um espaço 3D Hough correspondente a um x {\\\i1}displaystyle a_{x}}

, a {\an8} a_{\an8}

e d {\i1}displaystyle d

. Esta extensão sofre dos mesmos problemas que a sua contraparte 2D, ou seja, planos quase horizontais podem ser detectados de forma fiável, enquanto o desempenho se deteriora à medida que a direcção planar se torna vertical (grandes valores de um x {\\i}} a_{x}}

e um estilo de jogo a_{y}}

amplificar o ruído nos dados). Esta formulação do plano tem sido usada para a detecção de planos nas nuvens de pontos adquiridas de escaneamento a laser aéreo e funciona muito bem porque nesse domínio todos os planos são quase horizontais.

Para a detecção generalizada de planos utilizando a transformada Hough, o plano pode ser parametrizado pelo seu vector normal n {\i1}displaystyle n

(usando coordenadas esféricas) e a sua distância da origem ρ {\i1}displaystyle \i}rho

resultando num espaço de Hough tridimensional. Isto resulta em cada ponto na votação dos dados de entrada para uma superfície sinusoidal no espaço Hough. A intersecção destas superfícies sinusoidais indica a presença de um plano. Uma abordagem mais geral para mais de 3 dimensões requer heurística de busca para permanecer viável.

A transformação Hough também tem sido usada para encontrar objetos cilíndricos em nuvens de pontos usando uma aproximação de dois passos. O primeiro passo encontra a orientação do cilindro e o segundo passo encontra a posição e o raio.

Utilizando características ponderadasEditar

Um detalhe de variação comum. Ou seja, encontrar as caixas com a maior contagem numa etapa pode ser utilizado para restringir a gama de valores procurados na próxima.

Espaço de parâmetros cuidadosamente escolhidoEditar

Um espaço de parâmetros de alta dimensão para a transformação Hough não só é lento, mas se implementado sem premeditação pode facilmente ultrapassar a memória disponível. Mesmo que o ambiente de programação permita a alocação de um array maior do que o espaço de memória disponível através da memória virtual, o número de trocas de páginas necessárias para isso será muito exigente, pois o array do acumulador é usado de forma aleatória, raramente parando na memória contígua, pois ele salta de índice para índice.

Considerar a tarefa de encontrar elipses em uma imagem 800×600. Assumindo que os raios das elipses são orientados ao longo dos eixos principais, o espaço de parâmetros é tetradimensional. (x,y) define o centro da elipse, e a e b denotam os dois raios. Permitindo que o centro esteja em qualquer parte da imagem, adiciona a restrição 0<x<800 e 0<y<600. Se aos raios forem dados os mesmos valores das restrições, o que resta é um conjunto de acumuladores escassamente preenchidos com mais de 230 bilhões de valores.

Um programa assim concebido é improvável que seja permitido alocar memória suficiente. Isto não significa que o problema não possa ser resolvido, mas apenas que novas formas de restringir o tamanho da matriz do acumulador devem ser encontradas, o que o torna viável. Por exemplo:

1. Se for razoável assumir que as elipses estão cada uma totalmente contida dentro da imagem, o alcance dos raios pode ser reduzido. O maior dos raios pode ser se o centro da elipse estiver no centro da imagem, permitindo que as bordas da elipse se estiquem até as bordas. Neste caso extremo, os raios só podem ser metade da magnitude da dimensão da imagem orientada na mesma direcção. Reduzindo o alcance de a e b desta forma reduz a matriz do acumulador para 57 bilhões de valores.
2. A precisão comercial para o espaço na estimativa da transformação Hough acumula contribuições de todos os pixels na borda detectada. A transformada Hough acumula contribuições de todos os pixels na borda detectada. ele centraliza: Se a previsão é de que o centro esteja desligado por 3 nos eixos x e y, isso reduz o tamanho da matriz do acumulador para cerca de 6 bilhões de valores.
3. Comercializar precisão para o espaço na estimativa dos raios: Se os raios forem estimados para que cada um deles esteja desligado por 5 reduções adicionais do tamanho da matriz do acumulador, em cerca de 256 milhões de valores.
4. Cortar a imagem para áreas de interesse. Isto é dependente da imagem, e portanto imprevisível, mas imagine um caso em que todas as bordas de interesse em uma imagem estejam no quadrante superior esquerdo dessa imagem. A matriz do acumulador pode ser reduzida ainda mais neste caso restringindo todos os 4 parâmetros por um fator de 2, para um fator de redução total de 16,

Aplicando apenas as três primeiras destas restrições ao exemplo citado, o tamanho da matriz do acumulador é reduzido por quase um fator de 1000, reduzindo-o para um tamanho que é muito mais provável de caber dentro da memória de um computador moderno.

Algoritmo eficiente de detecção de elipseEdit

Yonghong Xie e Qiang Ji dão uma forma eficiente de implementar a transformação Hough para detecção de elipse, superando os problemas de memória. Como discutido no algoritmo (na página 2 do artigo), esta abordagem usa apenas um acumulador unidimensional (para o eixo menor) a fim de detectar elipses na imagem. A complexidade é O(N3) no número de pontos não-zero na imagem.