Transformación rápida de Hough

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 6 de septiembre de 2022; las comprobaciones requieren 13 ediciones .

Fast Hough Transform ( Fast Hough Transform , abbr . FHT) es una modificación de la transformada de Hough que le permite identificar paramétricamente líneas (así como, con modificaciones adicionales , segmentos y cuadriláteros ) con menos complejidad computacional debido al uso del hecho. de autointersección de las líneas discretas consideradas.

Historia

El algoritmo fue propuesto por primera vez por M. L. Brady en 1992, [1] posteriormente fue reinventado varias veces por varios autores. [2] [3]

Definición

Deje que se dé una imagen de tamaño . Considere líneas diádicas (líneas rectas de un tipo especial) que consisten en píxeles en la imagen cada una (un píxel por columna). $m\veces n$ $m^{2}$ $norte$

Sea la intensidad del enésimo píxel perteneciente a la recta diádica dada por los parámetros ; — La media imagen de esta línea diádica. ${\ Displaystyle yo ^ {(s, t)} (i)}$ $i$ ${\ estilo de visualización s, t}$ ${\ Displaystyle S^{(s, t)))$

La imagen de la transformada discreta de Hough se define mediante la siguiente fórmula:

S^{(s,t)}=\sum_{i=0}^{n-1}(I^{(s,t)}(i))

El cálculo directo de todos los valores requiere operaciones: enumeración sobre diferentes valores de los parámetros , enumeración para cada par de valores . ${\ Displaystyle S^{(s, t)))$ $O$ ${\ estilo de visualización \ izquierda (m ^ {2} n \ derecha)}$ $metro$ $s$ $t$ $norte$ $i$

A su vez, el algoritmo FHT, basado en tener en cuenta las intersecciones de los segmentos entre sí, requiere acciones, las operaciones son necesarias para una línea recta (para imágenes cuadradas ). Según el teorema formulado por T. M. Khanipov [4] , es imposible sumar líneas diádicas con una complejidad computacional asintóticamente menor. $\Theta$ $\left(mn\log m\right)$ $\Theta$ $\left({\frac {n\log m}{m))\right)$ $\Theta$ $\left(\log n\right)$

Algoritmo

El algoritmo se basa en el principio de " divide y vencerás ". El problema es encontrar las sumas de los valores de píxeles a lo largo de los segmentos que conectan los bordes "izquierdo" y "derecho" de la imagen. La imagen se divide por la mitad, en cada parte el problema se resuelve de forma independiente. Para obtener la suma final de cada uno de los segmentos, se suman las respuestas de las mitades "izquierda" y "derecha".

En el algoritmo FHT, los píxeles de líneas arbitrarias se aproximan discretamente mediante líneas diádicas. Los píxeles de la aproximación diádica de una línea recta en la imagen de tamaño se eliminan de la línea recta original en no más de píxeles. [5] $n\veces n$ $O$ ${\ estilo de visualización (\ log n)}$

Los segmentos están parametrizados por los centros de los píxeles conectados. Por lo tanto, la división de un segmento en subsegmentos solo constituye aproximadamente el segmento original. El error de aproximación con pasos de recursión es acumulativo, pero no más de píxeles. [5] La discretización del segmento a píxeles construido de esta manera se llama aproximación diádica . $O$ ${\ estilo de visualización (\ log n)}$

Patrones diádicos generativos

Además , un patrón es un conjunto de píxeles que contienen un elemento en cada vertical de la imagen. La desviación del patrón será el valor y la coordenada será el valor . Un cambio de patrón se llamará un conjunto ${\displaystyle p=\{(x_{i},i)\}_{i=0}^{2^{k}-1))$ $t(p)=x_{2^{k}-1}-x_{0}$ $s(p)=x_{0}$

pags ↗ ( a , b ) = { ( X i + a , y i + b ) | ( X i , y i ) ∈ pags } {\displaystyle p\narrow (a,b)=\lbrace \left(x_{i}+a,y_{i}+b\right)\ |\ (x_{i},y_{i})\in p \rbrace }

p\narrow (a,b)=\lbrace \left(x_{i}+a,y_{i}+b\right)\ |\ (x_{i},y_{i})\in p \rbrace

Los patrones diádicos generativos de ancho y pendiente se definen recursivamente. Para , el patrón consta de un píxel y para , se expresa en términos de .

2^k

t<2^{k}

{\ estilo de visualización k = t = 0}

k>0

k-1

$P_{t}^{k}={\begin{casos}\{(0,0)\}&,k=0\\\ P_{t/2}^{k-1}\ \ \ \cup \P_{t/2}^{k-1}\ \ \ \ \nearrow (t/2,2^{k})&,k>0,\ \ t\equiv 0\ (mod2)\\ P_{(t-1)/2}^{k-1}\taza \ P_{(t-1)/2}^{k-1}\estrecha ((t+1)/2,2^{k })&,k>0,\ \t\equiv 1\ (mod2)\end{casos}}$

Líneas diádicas

Las líneas diádicas ascendentes predominantemente horizontales se obtienen de todos los patrones generativos desplazados verticalmente , construidos con todas las coordenadas posibles en la imagen . $P_{s,t}^{k}=P_{t}^{k}\estrecho (s,0)$ ${\displaystyle s\en \{0,...,2^{k}-1\},t\en \{0,...,2^{k}-1\))$

Para un cálculo aproximado de la transformada de Hough, se requiere encontrar las sumas de todas las líneas diádicas en la imagen. En esta suma de líneas, hay puntos cada una. Debido a la transición recursiva, esta suma se reduce a contar por separado las mitades izquierdas, por separado las mitades derechas, lo que nos permite reducir el cálculo al cálculo de sumas sobre puntos cada uno. $S_{s,t}=\sum_{(x,y)\in P_{s,t}^{k}}I_{x,y}$ ${\displaystyle 2^{k}\cdot 2^{k))$ $2^k$ $2\cdot 2^{k}\cdot 2^{k-1}$ $2^{k-1}$

Considere las palabras binarias que consisten en los números 0 y 1. El conjunto de palabras diádicas se define recursivamente. se llamará palabra diádica si tiene la forma o , donde es palabra vacía o diádica. Todas las palabras diádicas de longitud no superior a tres: 0, 1, 000, 010, 101, 111. $w$ $w$ ${\ estilo de visualización a0a}$ ${\ estilo de visualización a1a}$ $a$

Para cada palabra diádica , se considera la suma acumulada . Diremos que la secuencia de píxeles es una línea recta diádica que conecta los centros de píxeles y . ${\displaystyle {\overline {b_{1}b_{2}...b_{n))))$ ${\displaystyle \{a_{i}\}_{0}^{2^{k}-1},a_{i}=\sum_{0}^{i}b_{i))$ ${\displaystyle \{(a_{i},i)\}_{0}^{2^{k}-1))$ $(0.0)$ ${\ estilo de visualización (a_{2^{k}-1},2^{k}-1)}$

Hay exactamente líneas diádicas de longitud . Uno para cada par de y . $2^k$ $2^k$ $(0.0)$ ${\displaystyle (h,2^{k}-1),0\leqslant h<2^{k))$

Descripción formal

El algoritmo FHT está estructurado de la siguiente manera: [6]

El estado inicial de la matriz es la imagen original de tamaño . Luego, el cálculo se lleva a cabo en los niveles -th a su vez, comenzando desde el primero: en el nivel -th, la matriz en el estado actual se divide en grupos de acuerdo con el principio de igualdad de la parte entera de la coordenada del segundo eje después de la división por ; se obtienen submatrices ; unir los adyacentes en pares (sin intersecciones, esto es posible, ya que el tamaño de la matriz es una potencia de dos) y en este par llamamos a la primera submatriz que se encuentra en coordenadas más pequeñas a lo largo de la segunda coordenada en la matriz , y el otro - el segundo; en lugar del primero en cada par, su suma se escribe con el segundo correspondiente, y en lugar del segundo, la suma del primero y el segundo con un desplazamiento cíclico de uno a la izquierda. Por lo tanto, la imagen de Hough de tales líneas se considera tal que para cualquier par de puntos con coordenadas de esta línea, se satisface utilizando la aproximación por líneas diádicas. Para calcular la imagen para el resto de las líneas, basta con girar la imagen y realizar la misma operación, y sumar los resultados. ${\ estilo de visualización 2^{p}\veces 2^{q))$ $q-1$ $i$ $2^yo$ ${\displaystyle 2^{p}\times 2^{i))$ ${\ estilo de visualización (x_{1},y_{1}),(x_{2},y_{2})}$ $(x_{1}\neq x_{2})\rightarrow ((y_{1}\neq y_{2})\wedge (x_{1}<x_{2}\Leftrightarrow y_{1}<y_ {2}))$

Las matrices así obtenidas en cada nivel son elementos de la pirámide FHT. Descripción formal de la pirámide FHT : El nivel cero de la pirámide FHT es la imagen original (de tamaño , y la última es la imagen de Hough que contiene sumas a lo largo de líneas rectas diádicas de longitud . Para describir el nivel th de la pirámide , la imagen original se divide en franjas horizontales , donde es el número de franja, Para cada franja, el nivel th de la pirámide FHT almacena sumas de todos los patrones de franja posibles con longitud y parámetros . El número de tales patrones para una franja es , por lo que el nivel th de la pirámide ocupa tanta memoria como la imagen original. $m\veces n$ ${\ estilo de visualización n = 2 ^ {p}}$ $q$ $[0,n-1]\times [k\cdot 2^{q},(k+1)\cdot 2^{q}-1]$ $k$ $k\en [0.2^{pq}-1]$ $q$ ${\ estilo de visualización 2 ^ {q}}$ $s\en [0,n-1],t\en [0,2^{q}-1]$ ${\displaystyle n\cdot 2^{q))$ $q$

La invariancia de la cantidad de memoria gastada y la capacidad de almacenar cada nivel en una matriz del mismo tamaño que la imagen original, sin pérdida de interpretabilidad, otorga la siguiente propiedad: es posible almacenar la pirámide FHT en forma de matriz con una dimensión mayor que la dimensión de la imagen original (a lo largo de un eje - el número de niveles, ), para el resto - el tamaño de la imagen). [7] ${\ estilo de visualización \ registro _ {2} n}$

Implementaciones de software

Un ejemplo de implementación en python:

importar numpy como np W = 2 ** 5 H = 2 ** 5 img = np . al azar aleatorio ([ alto , ancho ]) def calc_sums ( img , xmin , xmax ): res = np . ceros ([ W , xmax - xmin ]) if xmax - xmin == 1 : res [:, 0 ] = img [:, xmin ] else : mid = ( xmin + xmax ) // 2 ans1 = calc_sums ( img , xmin , mid ) ans2 = calc_sums ( img , mid , xmax ) for x in range ( W ): for shift in range ( xmax - xmin ): res [ x , shift ] = ans1 [ x , shift // 2 ] + ans2 [ ( x + shift // 2 + shift % 2 ) % W , shift // 2 ] return res res = calc_sums ( img , 0 , W )

El algoritmo está implementado en la biblioteca opencv [8] y se puede utilizar, por ejemplo, para encontrar rápidamente el punto de fuga . [9]

Generalizaciones al caso tridimensional

FHT para aviones

La solución de este problema implica el uso de un algoritmo para el caso bidimensional.

La semiimagen de los planos también será tridimensional (el plano se especifica mediante tres coordenadas del vector perpendicular a él). Sea dado por la parametrización , donde es la coordenada de la intersección del plano con el límite de la imagen en el rayo , es la coordenada del punto de intersección con el límite de la imagen paralelo al rayo en el plano , y es la diferencia entre las coordenadas del segundo y primer punto de intersección del plano con los límites de la imagen. El primer punto está en la intersección de los planos que contienen el límite de la imagen y el plano paralelo a . El segundo punto está en la intersección de los planos que contienen el límite de la imagen, paralelo a y . ${\ Displaystyle s, t, t_{2))$ $s$ $X$ $Buey$ ${\ estilo de visualización s+t}$ $X$ $Buey$ $xOz$ $t_{2}$ $X$ $xOz$ $xOy$ $xOy$ $xOz$

Llamaremos a un plano predominantemente perpendicular al eje de coordenadas si la normal a él forma un ángulo menor con este eje que con los otros dos. Consideraremos solo planos que son predominantemente perpendiculares al eje y. Se dividen en 4 tipos de pendientes, como se muestra en la Figura 4. Sin pérdida de generalidad, supondremos que los planos considerados son del tipo I.

La construcción de una imagen de Hough por enumeración de planos tiene una complejidad asintótica (la cantidad de planos multiplicada por la cantidad de operaciones para sumar un plano), donde m, n, k son las dimensiones de la imagen en cada dimensión. $O$ $\left(mnk\cdot (mn+nk+mk)\right)$

La transformada rápida de Hough en este caso será el siguiente algoritmo:

Para cada plano perpendicular al eje con una coordenada a lo largo de este eje, se calcula la transformada rápida de Hough y el resultado se coloca en el espacio tridimensional a lo largo de las coordenadas . ${\ estilo de visualización Oz}$ $z$ ${\ estilo de visualización s, t, z}$
Para cada plano en el espacio tridimensional resultante perpendicular al eje con una coordenada a lo largo de este eje, se calcula la transformada rápida de Hough y el resultado se coloca en un cubo a lo largo de las coordenadas . ${\ estilo de visualización de}$ $t$ ${\ Displaystyle s, t, t_{2))$

La complejidad de tal transformación es la suma de la complejidad del primer paso ( ) y la complejidad del segundo paso ( ), que se calculan como el producto del número de planos considerados y el número de operaciones por plano. Total, , en términos de un plano . $\Theta$ $\left(k\cdot mn\log m\right)$ $\Theta$ $\left(n\cdot mk\log m\right)$ $\Theta$ $\left(mnk\log m\right)$ $\Theta$ ${\ estilo de visualización (\ log m)}$

FHT para líneas 3D

La semiimagen de una recta tridimensional será tetradimensional (dos parámetros para cada uno de los dos puntos de la recta). Sea dado por parametrización . son las coordenadas x, y del punto en el plano , son las coordenadas x, y del punto de intersección de la línea con el límite de la imagen paralela al plano . ${\ estilo de visualización s, t, s_{2}, t_{2))$ ${\ Displaystyle s, s_ {2))$ $xOy$ ${\ Displaystyle s+t,s_{2}+t_{2))$ $xOy$

La construcción de la imagen de Hough por enumeración de líneas tridimensionales tiene una complejidad asintótica (el número de líneas multiplicado por el número de operaciones para sumar una línea), donde m, n, k son las dimensiones de la imagen en cada dimensión. $O$ $\left((mn)^{2}\cdot k\right)$

La transformada rápida de Hough para tal caso se formula de manera similar a la definición para el caso bidimensional. En el caso bidimensional, la posibilidad de desplazamiento era solo a lo largo de un eje, pero ahora el desplazamiento será a lo largo de un eje, a lo largo del segundo eje y a lo largo de dos ejes al mismo tiempo.

Contar patrones de longitud dos requiere (número de grupos de planos sumables) multiplicado por (complejidad de adiciones para cada grupo) operaciones. Contar patrones de longitud 4 requiere operaciones. Longitudes de patrón — , donde se define como , es decir, el número de la longitud de patrón considerada. Sumando los términos (el número de longitudes de patrón posibles para la imagen en cuestión) usando la fórmula para la suma de una progresión geométrica, obtenemos la complejidad del algoritmo y la complejidad en una línea recta . Para , la complejidad será constante. ${\frac{k}{2))$ ${\ estilo de visualización 4 minutos}$ ${\frac {k}{4}}\cdot 16mn$ $d$ ${\frac {k}{d}}\cdot d^{2}mn=mnkd=mnk\cdot 2^{i}$ $i$ ${\ estilo de visualización \ registro _ {2} (d)}$ ${\ estilo de visualización \ registro _ {2} (k)}$ $\Theta$ $\left(\sum_{i=1}^{\log_{2}k}mnk\cdot 2^{i}\right)\equiv$ $\Theta$ $\left({\frac {2mnk\cdot (2^{\log _{2}k}-1)}{2-1}}\right)\equiv$ $\Theta$ ${\ estilo de visualización \ izquierda (mnk ^ {2} \ derecha)}$ $\Theta$ $\left({\frac {k^{2}}{mn}}\right)$ ${\ estilo de visualización m = n = k}$

Combinación de BPH y el principio de los cuatro rusos

A pesar de que el número de operaciones por línea es constante para el mismo tamaño de imagen en cada dimensión, para todas las líneas es necesario gastar . Pero si no se necesitan todas las líneas, sino solo una parte de ellas, entonces uno puede precalcular los primeros pasos [10] , almacenarlos en la memoria y luego calcular las sumas solo para aquellas líneas que se necesitan. ${\ estilo de visualización n^{4))$ $X$

Este concepto fue consagrado en el método de cuatro rusos. El método lleva el nombre de los descubridores V. Arlazarov , M. Kronrod, E. Dinits, I. Faradzhev.

En el algoritmo FHT original para líneas tridimensionales, se realiza un cálculo en cada nivel para líneas de cierta longitud. Por otro lado, puede hacer un cálculo previo solo para los primeros pasos y luego calcular para las líneas necesarias. ${\ estilo de visualización \ registro _ {2} k}$ $X$

Para determinar el número óptimo de pasos de precálculo, es necesario resolver la siguiente ecuación ( es el número de líneas que necesita encontrar el algoritmo): $a$

$\Theta \left(mnk2^{x}\right)=\Theta \left(a2^{\log _{2}kx}\right)$

A la izquierda está el número de operaciones para realizar el precálculo. A la derecha está el número de operaciones para encontrar sumas a lo largo de las líneas solicitadas. Sea necesario encontrar todas las rectas, entonces , entonces la solución de la ecuación será , y los lados izquierdo y derecho son iguales , que es menor que sin precálculo. Sin embargo, para reducir el número de operaciones, es necesario pagar con memoria en la misma cantidad que ocupa la imagen de Hough (propiedad de invariancia de la memoria ocupada en cada nivel de conteo por el algoritmo FHT). $a=mnk$ $x={\frac {1}{2}}\log _{2}k=\log _{2}{\sqrt {k}}$ $\Theta \left(mnk{\sqrt {k}}\right)$ ${\ estilo de visualización {\ sqrt {k))}$

Cálculo de la suma de un segmento en una imagen

El principio de cálculo se basa en el uso de valores no solo del último nivel de la pirámide FHT (es decir, la propia imagen de Hough), sino también de otros niveles de la pirámide FHT.

La tarea se divide en dos subtareas:

Encuentre una línea diádica que pase por dos píxeles dados
De la suma de valores a lo largo de esta línea recta, seleccione la parte de la suma que se refiere al patrón entre los píxeles dados

Encontrar una línea diádica que pase por dos píxeles dados

Suponemos sin pérdida de generalidad que . Aquí consideraremos solo patrones predominantemente verticales con una inclinación a la derecha, es decir, y . También se utiliza la parametrización y el valor es igual a , donde es el tamaño de la imagen a lo largo del eje . ${\displaystyle y_{2}\geq y_{1))$ $x_{2}\geq x_{1}$ ${\displaystyle y_{2}-y_{1}\geq x_{2}-x_{1))$ ${\ estilo de visualización (s, t)}$ $pags$ $\ log _ {2} n$ $norte$ $y$

Deje que la expansión binaria del parámetro de línea recta diádica se vea como Entonces, el patrón se puede escribir de la siguiente manera ( - redondeando al entero más cercano): $t$ $t=\sum_{i=0}^{p-1}t_{i}2^{i}$ $\left[\cdot \right]$

$x=s+\sum _{r=0}^{p-1}t_{r}\left[{\frac {s^{r}y}{2^{p}-1}}\right ]$

${\ estilo de visualización \ Delta x=x_{2}-x_{1))$ calculado a partir de los datos de la tarea. es el número de cambios del patrón considerado en la banda , que también se conoce. Así, solo es necesario restaurar los bits . $\delta _{r}^{y_{1},y_{2}}=\left(D_{r}(y_{2})-D_{r}(y_{1})\right)$ ${\ estilo de visualización (y_{1},y_{2})}$ ${\displaystyle t_{0},t_{1},\ldots,t_{p-1))$

Se utiliza un algoritmo codicioso para la recuperación: todos los bits son cero primero. Dado que , por lo tanto, la enumeración se realiza desde un mayor número de turnos a uno menor, desde el nivel hasta el nivel 0. Si , entonces el bit correspondiente a este nivel se establece en 1 y disminuye en . El paso se repite hasta que llega a 0. $t_{r}$ $i>j\rightarrow \delta _{i}^{y_{1},y_{2}}\geq \delta_{j}^{y_{1},y_{2}}$ $p-1$ $\Delta y\geq \delta _{r}^{y_{1},y_{2))$ $\Delta y$ ${\ estilo de visualización \ delta _ {r} ^ {y_ {1}, y_ {2}}}$ $\Delta y$

El valor del parámetro se calcula mediante . A través de este parámetro, el parámetro se calcula de acuerdo con la siguiente fórmula: $t_{yo}$ $t$ $s$

$s=D(y_{1},t)-\sum_{r=0}^{p-1}t_{r}D_{r}(y_{1})$

$\#\lbrace \delta _{r}^{y_{1},y_{2}}\rbrace =p=\log _{2}n$ , por lo que la complejidad del algoritmo . [7] $\Theta$ ${\ estilo de visualización (\ log n)}$

Encontrar una suma a lo largo de un segmento en una línea diádica conocida

Método 1

Con referencia a la figura, se puede ver que un segmento arbitrario en una línea recta se calcula encontrando el número mínimo de patrones diádicos que contienen partes desde el comienzo de la línea hasta el final del segmento dado, inclusive, y el número mínimo de patrones que contienen el segmento desde el comienzo de la línea recta hasta el comienzo del segmento dado, excluyendo el primer píxel del segmento original. Es decir, debe encontrar las sumas de dos segmentos con el comienzo en el borde de la imagen y diferentes coordenadas finales. $norte$

Para calcular la suma sobre este tipo de segmento de longitud (su expansión binaria ) , donde es la suma sobre el patrón en la -ésima banda del -ésimo nivel de FHT=pirámide para una línea recta con parámetros . $yo$ $\sum _{j=0}^{p}\left(l_{j}\cdot 2^{j}\right)$ $\sum_{q=0}^{p}\left[l_{q}\cdot H^{s,t}\left(q,\sum_{j=q+1}^{p} l_{j}\cdot 2^{jq}\right)\right]$ $H^{s,t}\left(q,k\right)$ ${\ estilo de visualización 2 ^ {q}}$ $k$ $q$ ${\ estilo de visualización (s, t)}$

La suma interna no requiere un cálculo completo en cada paso, ya que se obtiene del anterior en tiempo constante. Así, la complejidad del algoritmo es proporcional al número de términos de la suma externa, es decir, es . Dado que el resultado se calcula para dos segmentos de este tipo, la complejidad resultante del algoritmo también es . Además, vale la pena señalar que un píxel puede ser multicanal. [7] $\Theta$ ${\ estilo de visualización (\ log n)}$ $\Theta$ ${\ estilo de visualización (\ log n)}$

Método 2

El segmento puede estar compuesto por el número mínimo de patrones dentro del segmento. Para buscar dichos patrones, debe observar los niveles de la pirámide FHT, comenzando con los últimos y terminando con los primeros. Puede filtrar inmediatamente aquellos patrones que no están incluidos en el segmento. Si se encuentra un patrón que se encuentra completamente dentro del segmento, su suma se incluye en la suma requerida y no se consideran sus divisiones en los siguientes niveles. Este método es computacionalmente más complejo que el primero, ya que requiere la enumeración de todos los patrones que son más de . $norte$

Cálculo de la suma sobre un cuadrilátero en una imagen

Similar a calcular la suma sobre un segmento para calcular la suma sobre un cuadrilátero a partir de los cálculos intermedios de la imagen de Hough para planos, es decir, la pirámide FHT para el caso de planos.

Suponiendo que se conocen los parámetros del plano en el que se encuentra el cuadrilátero dado, la suma deseada se calcula mediante la fórmula de inclusión-exclusión tomando la suma de cuatro rectángulos, uno de los cuales es el vértice de la esquina del plano diádico (nosotros señálelo con la letra , y los segmentos con este vértice con los segmentos de esquina ). Denotemos las coordenadas de los puntos más cercanos y más lejanos de los vértices del cuadrilátero dado por y respectivamente. Las sumas de los segmentos de esquina marcados con vértices en y se toman con un signo más, y las sumas de aquellos con vértices en y se toman con un signo menos. ${\ estilo de visualización (s, t, t_ {2})}$ $mi$ $mi$ ${\ estilo de visualización (i_ {1}, j_ {1})}$ ${\ estilo de visualización (i_ {2}, j_ {2})}$ ${\ estilo de visualización (i_{1}-1,j_{1}-1)}$ ${\ estilo de visualización (i_ {2}, j_ {2})}$ ${\ estilo de visualización (i_ {1}-1, j_ {2})}$ ${\ estilo de visualización (i_ {2}, j_ {1} -1)}$

Para encontrar la suma sobre un segmento angular arbitrario, es necesario dividirlo en segmentos que están presentes en la pirámide FHT. Es necesario considerar expansiones binarias del ancho y alto del segmento. De manera similar al caso unidimensional, el segmento se divide horizontalmente en franjas verticales y verticalmente en no más que franjas horizontales. Su intersección no dará más que los segmentos presentes en una pirámide FPH tridimensional. Así, la complejidad de calcular la suma sobre un segmento arbitrario equivale a operaciones. [7] $\ log _ {2} n$ $\ log _ {2} n$ $\ log _ {2} n$ $\Theta$ ${\ estilo de visualización (\ log n)}$

Aplicaciones del algoritmo FHT

Aunque hay algún error en la aproximación de una línea recta por un patrón diádico, los experimentos muestran que este error es lo suficientemente pequeño como para que en la resolución de problemas sea posible reemplazar el algoritmo tradicional de transformada de Hough con el algoritmo FHT. [once]

Solución robusta de un problema de regresión lineal mediante el cálculo de estimaciones M utilizando FHT

Al aplicar estimaciones M al problema de regresión lineal , se pueden obtener funciones de base radial . Forman una imagen "continua", que a su vez se muestrea en un histograma 2D.

A continuación, se realiza la convolución de la imagen con un núcleo discretizado correspondiente al estimador M seleccionado. En función de la imagen de Hough recibida, se calcula utilizando FHT. La coordenada del máximo en el espacio de parámetros - y será la estimación M deseada. $k$

Agrupación binaria lineal rápida

La tarea se formula de la siguiente manera: es necesario encontrar un hiperplano que divida la imagen en 2 clases. La imagen se representa como un histograma de imagen normalizado . $PAGS$

$L$ es el hiperplano deseado que divide las imágenes en dos clases , es la clase de todos los elementos del histograma. ${\ estilo de visualización A_ {L}, B_ {L}}$ $\Omega$

Estadísticas aditivas usadas ( --ésima coordenada ): $X\subconjunto \Omega$ $x_{yo}$ $i$ $X$

$D^{0}(X)=\sum_{x\in X}P(x)$
$D_{i}^{1}(X)=\sum_{x\in X}x_{i}P(x)$
$D_{ij}^{2}(X)=\sum_{x\in X}x_{i}x_{j}P(x)$

Hay una serie de funcionales adecuados para problemas de separación de conglomerados con diferentes propiedades conocidas a priori, y al mismo tiempo computables en términos de estadística aditiva. Vale la pena mencionar una vez más que estos funcionales generalmente no son convexos y la única forma confiable de encontrar su valor óptimo es la enumeración exhaustiva en la cuadrícula en el espacio de parámetros de las superficies de separación.

Algoritmo ingenuo: hay líneas discretas que se cruzan con el histograma con un tamaño lineal . Para cada uno de ellos se requiere realizar operaciones para calcular los pesos, las matrices de covarianza y, finalmente, los valores de los criterios. Por lo tanto, la complejidad computacional del algoritmo ingenuo son las operaciones. De manera similar, se puede demostrar que para el caso tridimensional, la complejidad computacional del algoritmo será . $O(n^{2})$ $norte$ $O(n^{2})$ $O(n^{4})$ ${\ estilo de visualización O (n ^ {6})}$

En esta etapa, se aplica la suma acumulativa: la suma de los elementos correspondientes de todas las capas de la imagen de entrada con un índice que no exceda se escribe en el elemento de capa con el número de la imagen de salida . $i$ $i$

La suma de los valores de píxeles de cualquier línea de la imagen de salida es igual a la suma de la parte de la imagen original que no está debajo de esta línea. Además, la suma a lo largo de cualquier línea recta predominantemente horizontal en la imagen de salida es igual a la suma a lo largo del semiplano superior delimitado por ella en la imagen original. Para una expresión similar de las sumas sobre los semiplanos izquierdos a través de rectas predominantemente verticales, en lugar de la vertical, es necesario realizar la suma acumulativa horizontal de la imagen.

Algoritmo:

calcular un conjunto de imágenes que contengan los valores de las estadísticas aditivas requeridas para cada elemento del histograma de entrada ( ) (6 en el caso bidimensional, 10 en el caso tridimensional) ${\displaystyle D^{0},D_{i}^{1},D_{ij}^{2))$
calculando la suma acumulada a lo largo de cada uno de los ejes, obtenemos una tupla de imágenes. Para cualquier imagen de esta tupla relacionada con la dimensión , la suma sobre cualquier hiperplano, predominantemente perpendicular al eje con índice , es igual a la estadística aditiva correspondiente calculada sobre el semiespacio, incluido el origen y acotado por el hiperplano elegido. Conociendo el valor de la estadística aditiva para un semiespacio, es fácil obtener el valor de la misma estadística para el segundo restando de la estadística calculada sobre toda la imagen. $d$ $d$
Ahora, habiendo calculado las estadísticas aditivas sobre todas las separaciones de los hiperplanos, podemos calcular los valores del criterio para elegir la agrupación óptima.

Si simplemente sumamos todos los hiperplanos, entonces en el caso bidimensional la complejidad es , en el caso tridimensional . (En -dimensional ) $O(mn^{3})$ $O(mn^{5})$ $k$ $O(mn^{2k-1})$

La suma sobre hiperplanos (líneas rectas en 2D, planos en 3D...) se puede realizar mediante FHT. Esto ayuda a reducir la complejidad de a para cada una de las imágenes. Es decir, ahora la complejidad está en el caso bidimensional , en el tridimensional . ${\ estilo de visualización O (n ^ {2k-1})}$ $O(n^{k}\log {\left(n\right)})$ $metro$ $O(mn^{2}\log {\left(n\right)})$ $O(mn^{3}\log {\left(n\right)})$

Entonces el algoritmo final es:

suma acumulativa
Estadísticas aditivas de conteo
HBP
Encontrar el máximo en el espacio de Hough

Complejidad: tiempo , memoria . $O(mn^{k}\log {\left(n\right)})$ $O(mn^{k})$

En el caso bidimensional con más detalle:

Suma acumulada: $O(n^{2})$
Preparación para calcular estadísticas aditivas: $O(n^{2})$
HBP: $O\left(n^{2}\log {\left(n\right)}\right)$
Encontrar el máximo en el espacio de Hough: $O(n^{2})$

Dificultad final: $O(n^{2}\log {\left(n\right)})$

En el caso 3D con más detalle:

Suma acumulada: $O(n^{3})$
Preparación para calcular estadísticas aditivas: $O(n^{3})$
HBP: $O\left(n^{3}\log {\left(n\right)}\right)$
Encontrar el máximo en el espacio de Hough: $O(n^{3})$

Dificultad final: $O(n^{3}\log {\left(n\right)})$

Otros usos

Los siguientes son solo algunos de los problemas que se pueden resolver usando la transformada de Hough.

Seguimiento de objetos en movimiento uniforme utilizando la diferencia de imagen fotograma a fotograma. Estos objetos dejan líneas rectas pronunciadas en sus huellas. [12] [13]
Detección de puntos de fuga en una imagen. Un punto de fuga es un punto en el plano de la imagen en el que se cruzan las proyecciones de líneas paralelas en una escena 3D. [14] [15]
restauración tomográfica. El procedimiento para formar proyecciones de la imagen del objeto analizado mediante rayos X suele modelarse mediante las transformadas de Hough y Radon, y la obtención de la estructura tridimensional del objeto en estudio se reduce muchas veces a resolver la transformada inversa de Hough o Radon. [dieciséis]
Análisis de imágenes médicas. [17]
En la implementación de algoritmos para la calibración ciega de la distorsión radial, siempre que se encuentren objetos rectilíneos en el escenario. A través de la optimización de la nueva funcionalidad de la imagen de Hough, se seleccionan los parámetros de compensación de la distorsión radial. [Dieciocho]
Determinación del grado de caída de la cámara. Basado en el cálculo de la FHT a partir del patrón epipolar y la búsqueda de una línea recta sobre la que se sitúan los puntos de las líneas de interés en el patrón epipolar.
Reconocimiento de escritura a mano. [19]
Determinación de la inclinación de la fuente. Basado en el hecho de que la fuente tiene caracteres que consisten en segmentos rectos ubicados en un ángulo, a lo largo de ese ángulo, la media imagen tendrá un valor mayor. [veinte]
Reconocimiento de código de barras. [21] [22]
Determinación del grado de similitud de las formas. [23]
Vectorización de imágenes tridimensionales. [24]
Detección de huellas de satélite a partir de imágenes de larga exposición. [25]
Detección de objetivos de radar. [26] [27]
Análisis de deformación de perfiles subterráneos. [28]
Análisis de la estructura de la topología de microcircuitos a partir de fotografías. [29]
Contar el número de ejes del vehículo a partir de las huellas del detector de ruedas de las imágenes tomadas desde una cámara tomada desde el costado. [treinta]
Reconstrucción 3D de caras planas de minerales transparentes a partir de un conjunto de imágenes. [31]
Análisis de imágenes SAR. [32]

Notas

↑ Martin L. Brady, Whanki Yong. Algoritmos de aproximación discreta paralelos rápidos para la transformada de radón // Actas del cuarto simposio anual de ACM sobre algoritmos y arquitecturas paralelos. - Nueva York, NY, EE.UU.: ACM, 1992. - S. 91-99 . — ISBN 9780897914833 . -doi : 10.1145/ 140901.140911 .
↑ JE Vuillemin. Transformación de Hough lineal rápida // Conferencia internacional sobre sistemas, arquitecturas y procesadores específicos de aplicaciones, Actas. - IEEE, 1994. - ISBN 0-8186-6517-3 . — ISSN 1063-6862 . -doi : 10.1109/ ASAP.1994.331821 .
↑ SM Karpenko, D.P. Nikolaev, P. P. Nikolaev, V. V. Postnikov. Transformación rápida de Hough con robustez controlada // Sistemas inteligentes artificiales y CAD inteligente. Actas de la conferencia internacional IEEE AIS "04 y CAD-2004. - Fizmatlit, 2004. - V. 2 , número 2. - S. 303-309 .
↑ Timur M. Khanipov. Límites inferiores de complejidad computacional de ciertas aproximaciones de transformadas de Radon discretas . — 2018-01-03. Archivado desde el original el 15 de julio de 2020.
↑ 1 2 S. M. Karpenko, E. I. Ershov. Transformada rápida de Hough y propiedades de aproximación de patrones diádicos . — 2017-12-15. Archivado el 9 de mayo de 2019.
↑ E. I. Ershov, A. P. Terekhin, D. P. Nikolaev. Generalización de la transformada rápida de Hough para imágenes tridimensionales // Journal of Communications Technology and Electronics. — 2018-06-01. — vol. 63 , edición. 6 _ — pág. 626–636 . — ISSN 1555-6557 . -doi : 10.1134/ S1064226918060074 .
↑ 1 2 3 4 KV Soshin, DP Nikolaev, SA Gladilin, EI Ershov. Aceleración de la suma sobre segmentos utilizando la pirámide de transformación rápida de Hough // Modelado matemático, programación y software informático de la Universidad Estatal de los Urales del Sur : Alevtina V. Keller, Natalia A. Manakova, Georgy A. Svirdyuk, Vladimir I. Zalyapin, Alena A. Zamyshlyaeva. - Chelyabinsk: Universidad Estatal de los Urales del Sur, 2020. - Vol. 13 , no. 1 . - S. 129-140 . -doi : 10.14529 / mmp200110 .
↑ OpenCV: referencia de archivo opencv2/ximgproc/fast_hough_transform.hpp . docs.opencv.org. Consultado el 9 de mayo de 2019. Archivado desde el original el 9 de mayo de 2019. (indefinido)
↑ Alejandro Krotov. Ejemplo de transformación rápida Hough de OpenCV . — 2017-09-05. Archivado desde el original el 9 de julio de 2021.
↑ Bulatov KB, Chukalina MV, Nikolaev DP Algoritmo de cálculo de suma de rayos X rápido para tomografía computarizada (inglés) // SUSU MMP Bulletin. - 2020. - T. 13 , núm. 1 . - S. 95-106 . -doi : 10.14529 / mmp200107 .
↑ E. I. Ershov. Transformación rápida de Hough como herramienta para analizar imágenes 2D y 3D en problemas de búsqueda lineal y agrupamiento lineal . — 2018. (Ruso)
↑ AE Cowart, WE Snyder, WH Ruedger. La detección de objetivos no resueltos utilizando la transformada de Hough // Visión artificial, gráficos y procesamiento de imágenes. - 1983. - T. 21 , núm. 2 . - S. 222-238 . (Ruso)
↑ A. Mitiche, P. Bouthemy. Computación y análisis del movimiento de la imagen: una sinopsis de los problemas y métodos actuales (inglés) // Revista internacional de visión por computadora. - 1996. - vol. 19 , edición. 1 . - P. 29-55 .
↑ E. Lutton, H. Maitre, J. López-Krahe. Contribución a la determinación de puntos de fuga usando transformada de Hough // Transacciones IEEE sobre análisis de patrones e inteligencia artificial. - 1994. - vol. 16 , edición. 4 . - Pág. 430-438 .
↑ D. Nikolaev et al. Transformada de Hough: herramienta subestimada en el campo de la visión artificial // Actas de la 22.ª Conferencia Europea sobre Modelado y Simulación. - 2008. - P. 238-246 .
↑ V. Prun et al. Técnica efectiva de reconstrucción algebraica regularizada para tomografía computarizada // Informes de cristalografía. - 2013. - Vol. 58 , edición. 7 . - P. 1063-1066 .
↑ Z.-H. Cho, JP Jones, M. Singh. Fundamentos de la imagen médica . — Wiley Nueva York, 1993. (Ruso)
↑ IA Kunina, SA Gladilin, DP Nikolaev. Compensación ciega de la distorsión radial en una sola imagen utilizando la transformación rápida de Hough // Computer Optics. - 2016. - Vol. 40 , edición. 3 . - Pág. 395-403 .
↑ A. Mozgovoi. Transformación de Hough en problemas de reconocimiento automático de escritura a mano . - 2012. - Edición. 9 _ - S. 62-64 . (Ruso)
↑ E. Limonova, P. Bezmaternykh, D. Nikolaev, V. Arlazarov. Slant Rectiﬁcation in Russian Passport OCR System usando Fast HoughTransform (inglés) // 9th International Conference on Machine Vision, ICMV 2016. - SPIE, 2017. - P. 103410P . -doi : 10.1117/ 12.2268725 .
↑ V. A. Fursov, S. A. Bibikov, P. Yu. Yakimov. Localización de contornos de objetos en imágenes con variaciones de escala utilizando la transformada de Hough // Computer Optics. - 2013. - T. 37 , núm. 4 . (Ruso)
↑ R. Muñiz, L. Junco, A. Otero. Un lector de código de barras de software robusto que utiliza la transformada de Hough // Conferencia internacional sobre sistemas e inteligencia de la información, 1999. Actas.. - IEEE, 1999. - P. 313-319 .
↑ A. Rubis et al.. Comparación morfológica en forma de patrones de puntos e imágenes de contorno basadas en la transformada de Hough y sus modificaciones // Bulletin of Computer and Information Technologies. - 2011. - Edición. 7 . - S. 9-16 . (Ruso)
↑ M. Kudrina [et al.] Vectorización de imágenes raster usando la transformada de Hough // Actas del Simposio Internacional "Confiabilidad y Calidad". - 2013. - T. 1 . (Ruso)
↑ B. Vandame. Transformación rápida de Hough para una detección robusta de pistas de satélite // Mining the Sky. - Springer, 2001. - Pág. 595-597 .
↑ A. Semenov. Detección de objetivos de radar utilizando la transformada de Hough // Ciencia y educación: edición científica de la Universidad Técnica Estatal de Moscú. NE Bauman. - 2014. - Edición. 12 _ (Ruso)
↑ B. Carlson, E. Evans, S. Wilson. Detección de radar de búsqueda y seguimiento con la transformada de Hough. tercero Rendimiento de detección con integración binaria (inglés) // Transacciones IEEE en sistemas aeroespaciales y electrónicos. - 1994. - vol. 30 , edición. 1 . - P. 116-125 .
↑ A. Dolgy, A. Khatlamadzhiyan. Un modelo híbrido para la interpretación de deformaciones en un prisma de balasto y el área de subrasante principal basado en la transformada de Hough objetivo y la red neuronal de Kohonen // Boletín de la Universidad Federal del Sur. ciencia técnica. - 2007. - T. 77 , núm. 2 . (Ruso)
↑ A. Dudkin, D. Vershok, A. Selikhanovich. Aislamiento de contornos sobre imágenes en escala de grises de capas topológicas de circuitos integrados // Inteligencia artificial. - 2004. - Edición. 3 . - S. 453-458 . (Ruso)
↑ A. Grigoriev, T. Khanipov, D. Nikolaev. Determinación del número de ejes de un vehículo a partir de la secuencia de video del pasaje // 54.a Conferencia Científica del Instituto de Física y Tecnología de Moscú. - 2011. - T. 10 . - S. 31 . (Ruso)
↑ V. Gaganov, A. Ignatenko, M. Lomonosov. Reconstrucción tridimensional de caras planas de minerales transparentes a partir de un conjunto de imágenes de un microscopio // Actas de la conferencia Graphon. - 2008. - S. 227-233 . (Ruso)
↑ J. Skinley, A. Rye. La transformada de Hough aplicada a imágenes SAR para la detección de líneas finas // Letras de reconocimiento de patrones. - 1987. - vol. 6 , edición. 1 . — págs. 61–67 .