Transformación de Hough aleatoria

Una ecuación general para definir elipses es: ${\displaystyle a(xp)^{2}+2b(xp)(yq)+c(yq)^{2}=1}$

con restricción:${\displaystyle ac-b^{2}>0}$

Sin embargo, una elipse puede determinarse completamente si se conocen tres puntos sobre ella y las tangentes que pasan por esos puntos.

RHT comienza seleccionando aleatoriamente tres puntos en la elipse. Sean${\displaystyle X_{1}}$,${\displaystyle X_{2}}$y${\displaystyle X_{3}}$El primer paso consiste en hallar las tangentes de estos tres puntos. Estas se pueden obtener ajustando una línea recta mediante la técnica de mínimos cuadrados a una pequeña ventana de píxeles vecinos.

El siguiente paso es encontrar los puntos de intersección de las líneas tangentes. Esto se puede hacer fácilmente resolviendo las ecuaciones de las líneas encontradas en el paso anterior. Entonces, sean los puntos de intersección${\displaystyle T_{12}}$y${\displaystyle T_{23}}$, los puntos medios de los segmentos de línea${\displaystyle X_{1}X_{2}}$y${\displaystyle X_{2}X_{3}}$ser${\displaystyle M_{12}}$y${\displaystyle M_{23}}$Entonces el centro de la elipse estará en la intersección de${\displaystyle T_{12}M_{12}}$y${\displaystyle T_{23}M_{23}}$Nuevamente, las coordenadas del punto de intersección se pueden determinar resolviendo ecuaciones de línea, y el proceso detallado se omite aquí por brevedad.

Sea la coordenada del centro de la elipse hallada en el paso anterior.${\displaystyle (x_{0},y_{0})}$. Entonces el centro se puede trasladar al origen con${\displaystyle x'=x-x_{0}}$y${\displaystyle y'=y-y_{0}}$de modo que la ecuación de la elipse se pueda simplificar a:

${\displaystyle ax'^{2}+2bx'y'+cy'^{2}=1}$

Ahora podemos calcular el resto de los parámetros de la elipse:${\displaystyle a}$,${\displaystyle b}$y${\displaystyle c}$sustituyendo las coordenadas de${\displaystyle X_{1}}$,${\displaystyle X_{2}}$y${\displaystyle X_{3}}$en la ecuación anterior.

Con los parámetros de la elipse determinados en la etapa anterior, el array acumulador se actualiza en consecuencia. A diferencia de la transformada de Hough clásica, la transformada de Hough inversa (RHT) no mantiene una cuadrícula de cubos como array acumulador. En cambio, primero calcula las similitudes entre la elipse recién detectada y las que ya están almacenadas en el array acumulador. Se pueden usar diferentes métricas para calcular la similitud. Si la similitud supera un umbral predefinido, se reemplaza la elipse en el acumulador con el promedio de ambas y se le suma 1 a su puntuación. De lo contrario, se inicializa esta elipse en una posición vacía en el acumulador y se le asigna una puntuación de 1.

Una vez que la puntuación de una elipse candidata supera el umbral, se determina que existe en la imagen (es decir, se detecta) y debe eliminarse de la imagen y del acumulador para que el algoritmo pueda detectar otras elipses potenciales con mayor rapidez. El algoritmo finaliza cuando el número de iteraciones alcanza un límite máximo o cuando se han detectado todas las elipses.

Pseudocódigo para RHT: ^{[ 3 ]}

mientras (encontramos elipsis Y no alcanzamos la época máxima) { para (un número fijo de iteraciones) { Encuentra una elipse potencial. si (la elipse es similar a una elipse en el acumulador) entonces Reemplaza el valor del acumulador con el promedio de dos elipsis y suma 1 a la puntuación; demás Inserta la elipsis en una posición vacía del acumulador con una puntuación de 1; } Seleccione la elipse con la mejor puntuación y guárdela en una tabla de mejores elipses; Eliminar de la imagen los píxeles de la mejor elipse; Vacía el acumulador; }