Loading
Apuntes
Study Reminders
Support
Text Version

Transformación Hough

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

El siguiente tema del que vamos a hablar al tratar de emparejar formas o cualquier otra plantilla en una imagen es el método conocido como Hough Transform. Una vez más, estas diapositivas de conferencias también se basan en las excelentes conferencias del profesor Yannis, en Inria Ren, así como las conferencias del profesor Mubarak Shah en la universidad de Florida Central. Ya hemos visto un par de métodos de ajuste de línea. Vimos encajar menos plazas y luego vimos RANSAC. La pregunta que usted va a hacer ahora es, ¿qué hace si hay varias líneas colocadas en una orientación particular o colocadas en una configuración particular en una imagen? Podría ser varias líneas, podría ser un polígono, podría ser un círculo, entonces, ¿cómo se ocupa de encajar una forma en el conjunto de puntos de datos que tiene? Y eso es de lo que vamos a hablar ahora, cuando nos Transformar. (1:30) Este método se remonta a principios de los años 60, por Hough, quien presentó la patente de EE.UU. para esto, pero desde entonces, ha habido muchos esfuerzos que han traducido esto en lo que vemos hoy. A principios de los años 70, se utilizó la Hough Transform para detectar líneas y curvas. Luego a principios de los 80, hubo un método que vino que se llamó una transformación generalizada y veremos todos estos sobre las próximas diapositivas. Empecemos por la simple ecuación de una línea y coordenadas cartesianas, que todos conocemos es y = mx + c, donde decimos que m es la pendiente y c es la e intercepta. Solo podrías jugar con los términos de la ecuación un poco, y luego escribir esto como c = −mx + y. Más bien ahora vivimos en un espacio de m, c donde x es c interceptación, y definir la línea en ese espacio. Así, originalmente estaban en el espacio x, y, donde m definen la pendiente y c definen la intersección y. Podríamos simplemente reorganizar estos términos ligeramente para ir a un espacio de m, c donde − x se convierte en la pendiente y se convierte en la intersección c. En este tipo de contexto, cada punto en m, c espacio se convierte en la ecuación de una línea en el espacio x, y, recordar para cada elección de m y c, usted conseguirá la ecuación de una línea como vemos aquí. Y cada punto en el espacio x y del mismo modo se convertiría en la ecuación de una línea en el espacio m, c. Hay una doble correspondencia entre estos dos espacios. Entonces, ¿qué hacemos con esto? (3:35) Sabemos que para adaptarse a cualquier modelo necesitamos un cierto número de muestras. Por ejemplo, para ajustarse a una línea, necesitamos dos muestras. Si fuera cualquier otro modelo, si estuviera encajando un cuadrado o un círculo, necesitamos un número diferente de puntos. Para ajustarse a una línea, puede necesitar dos puntos. Comencemos con ese ejemplo. Pero incluso si usted tuviera sólo un punto en lugar de dos puntos, usted sabe que podría pertenecer a una cierta familia de líneas. Te da alguna información parcial sobre la ecuación de la línea en sí. Por lo tanto, lo que podemos pedir cada punto en su x, y espacio para hacer es votar por ciertas configuraciones de m y c, en caso de que usted está hablando de una línea, si está alineado. Cada punto puede votar por lo que la configuración de m y c habría resultado en este punto estando en esa ubicación en particular. Y luego recolectas palabras para todos esos puntos y tratas de buscar consenso y donde sea que sea el voto mayoritario, vas a decir que esa es la ecuación de la línea que estoy buscando. Vamos a elaborar sobre esto y pasar lentamente. (4:50) Antes de ir hacia adelante, hablamos de las coordenadas cartesianas en la diapositiva anterior. Desafortunadamente, la formulación cartesiana puede ser problemática para las líneas verticales. Usted puede decir ¿por qué? Cuando tienes una línea vertical, tu pendiente es ilimitada, se hace difícil representar tal línea en tu m, c espacio porque m tiene que ser infinito. Así, en tal escenario, puede ser más sabio utilizar una parametrización ligeramente diferente, la parametrización polar, que está escrita en términos de ρ y θ, donde ρ es la distancia de la línea de origen y θ es el ángulo hecho por lo normal al eje X. También puedes escribir ρ = x cos θ + y sin θ. Se trata de una parametrización polar estándar que se utiliza yendo de coordenadas cartesianas a coordenadas polares. Sabemos ahora que en este espacio, ρ es al menos menor acotado por 0 y θ se encuentra entre 0 y 360. Sabemos que estas cantidades están limitadas, lo que hace que sea un poco más fácil de trabajar. (6:17) Así, cada punto en su espacio original, en su espacio cartesiano (x, y) vota por muchos puntos en su espacio de parámetros. Así que, si tuvieras una cierta línea, cierto punto x1 en tu espacio cartesiano original. Por el momento, vamos a hablar de este método en general, en términos de un espacio cartesiano y encajar una línea o encajar un círculo y así sucesivamente y así sucesivamente. Un poco más tarde en esta conferencia, hablaremos de cómo se usa esto con las imágenes. Si usted ya tiene un sentido de lo que viene, estamos tratando de averiguar cómo utiliza la transformación de Hough para emparejar líneas o círculos o cualquier otra forma en una imagen. Ese es el objetivo de esta conferencia o el método discutido en esta conferencia. Pero antes de ir a una imagen, simplemente vamos a hablar en general sobre las coordenadas cartesianas. Por lo tanto, si usted tiene un punto x en el espacio, usted sabe que hay una familia de líneas que 1 (x, y) puede pasar a través de x, y cada una de esas líneas tiene un corresponsal que va a tener un 1 m, c pendiente y la intersección y, y todos ellos resultarán en los puntos correspondientes en el m, c espacio o el ρ, espacio de θ. Si va al espacio de registro, tendrá una variación ligeramente diferente. Ellos corresponderán a un punto aquí en el espacio r theta. Por lo tanto, para cada punto x, y puede votar por muchos puntos en su espacio de parámetros, que ese punto x en particular podría haber estado mintiendo. Así, cada línea a través de este punto, es un 1 (x,) 1 y1 voto por un punto en un espacio de parámetros que satisface ρ = x cos θ + y sin θ. Veamos algunos ejemplos. (8:12) Aquí hay otra línea que pasa a través de x y que funcionaría para un punto diferente en el espacio de 1 parámetro, que está aquí. (8:23) Aquí hay otra línea que pasa por x, que votaría por un punto diferente en el espacio del parámetro 1. Recuerde que el espacio de parámetros ahora está definido en una parametrización polar. (8:36) Y usted sigue repitiendo esto para varias líneas que podrían haber pasado a través de x y todas ellas obtener votos en el espacio de parámetros. (8:46) Del mismo modo, usted podría tener otro punto x en su espacio original a través del cual usted 2 tendría otro conjunto de líneas que pueden pasar en su espacio cartesiano original y cada una de esas líneas puede votar por ellos para una parametrización diferente en su espacio de parámetros. Puedes ver que de nuevo, aquí, estos son pequeños ejemplos para varias líneas que pasan por x, obtienes varios 2 votos en el espacio de parámetros. (9:17) Tratemos de volver a contar esto a través de un algoritmo. Por lo tanto, tiene sus datos X, tiene un conjunto de parámetros cuantificados, theta min to theta max. Por ejemplo, si toma la parametrización polar, es posible que no desee votar por cada ángulo entre 0 y 360, es posible que desee dividir entre 0 y 360 en intervalos de 10 grados y tener sólo 36 valores posibles de theta. Eso es lo que queremos decir con un parámetro cuantificado aquí. También inicializa una matriz de acumulador, que es simplemente un recuento de frecuencia. Es simplemente un conteo de frecuencia de votos. Puedes mirarlo de esa manera. Por lo tanto, para cada punto (x, y) en su espacio cartesiano, tratamos de ver para theta que pertenece a theta, usted tiene 10 posibilidades thetas. Si escribe ρ = x cos θ + y sin θ. Tratamos de ver para cada conjunto de parámetros de modelo consistentes con la muestra, de modo que rho y que theta se alinearía con este X particular, Y que hemos tomado. Usted incrementa A para esa theta y rho. Por lo tanto, usted imagina que el acumulador es una matriz 2D definida por los valores de teta en un eje y valores rho en el otro eje, que también podría ser cuantificado, usted podría cuantificar la distancia en, distancia de decir un cierto número de unidades. Y cualquiera que sea rho y theta que sepamos corresponde a esta X e Y que tenemos, vas a esa rho y theta y en cada uno de estos casos, podrías comprobar por consistencia e incrementar esa celda en la matriz del acumulador por 1. Y sigues haciendo esto por cada punto X Y que se te da. Esos son tu conjunto de puntos que te son dados y sigues acumulando y al final, haces una supresión no máxima en A. Así que, si tienes muchas papeleras diferentes que tienen un voto alto, haces una supresión no máxima local, local no máxima para ver qué bin tiene los votos realmente más altos y tu define que theta y rho sean correspondientes al modelo que corresponde a tu, que directamente tiene un cojinete en los datos de tu matriz X. Esto te da una manera de estimar la theta y rho o en coordenadas cartesianas, encontrando la ecuación de la línea, correspondiente a este conjunto de puntos que te son dados. Como se puede ver esto es muy similar a un ajuste mínimo cuadrado, pero hacerlo de una manera ligeramente diferente. Todavía estamos tratando de ajustar una línea a un conjunto de puntos que se nos ha dado, pero lo estamos haciendo utilizando el enfoque de votación de Hough. (11:54) Ahora, como prometí, aquí hay un ejemplo de una perspectiva de imagen. Digamos que tenemos una imagen y la imagen tiene varias líneas y queremos encontrar las ecuaciones de esas líneas. Eso podría ser varias aplicaciones en las que esto puede ser requerido. Digamos, por ejemplo, que usted está tratando de tomar imágenes de un chip de computadora y tratando de averiguar cómo esas líneas están alineadas en un chip de computadora y así sucesivamente. Usted quiere encontrar las ecuaciones de esas líneas. (12:24) Por lo tanto, usando el mismo enfoque del que acabamos de hablar en la diapositiva anterior, usted asume una cierta parametrización, usted pide para cada punto de votar a qué parametrización puede haber generado en ese punto en particular, y usted termina obteniendo votos sobre su matriz 2D de acumulador, digamos sólo un ρ y θ. Entonces, usted puede ver aquí que usted tiene un montón de votos que se extiende a través de muchos diferentes contenedores de acumulador, dijimos que se acumuló como una matriz que es rho y theta. (12:54) Ahora, está realizando una supresión no máxima para mantener sólo los mínimos locales en el acumulador. Y una vez que hagas esta maxima local, encuentras que hay cuatro maxima aquí que corresponde a cuatro valores o cuatro parametrizaciones de líneas, que son las cuatro líneas que en realidad tienes en la imagen original. Y esos son los puntos que estaban votando por cada una de esas papeleras acumuladoras. De esta manera podrás averiguar las ecuaciones de esas líneas, así como qué puntos de la imagen original corresponden a esas ecuaciones, para poder extraer esa forma en esa imagen. Por lo tanto, en realidad puede encontrar ecuaciones de líneas en cualquier imagen dada a usted utilizando este enfoque. (13:44) Ahora hagamos esto un poco más difícil. Digamos que ahora queremos encontrar círculos en una imagen. Sí hablamos de detección de bloques antes, pero ahora queremos encontrar exactamente el círculo con su radio y su centro y poder parametrizarlo perfectamente. Por lo tanto, el ajuste de círculo es muy similar a la línea de ajuste, que va a ser el ajuste que usted está buscando (x − x) y). 0 2 + (− y0 2 − r 2 = 0 ¿Cuáles deben ser las dimensiones del acumulador? Para la línea, el acumulador era una matriz 2D. ¿Cuál sería la dimensión del acumulador para el ajuste del círculo? (14:29) Sería un acumulador tridimensional 3D, donde se tiene x, y, que corresponde 0 0 al centro del círculo y r que corresponde al radio del círculo. Esos son los tres votos que cada punto va a votar. Ya que tenemos tres posibilidades aquí, una opción es arreglar uno de los parámetros y generalmente se fija el radio y luego buscar el resto, pedir cada punto para votar cuál es el centro y luego se puede seguir dando vueltas y yendo en una forma redonda Robin para asegurar que cada punto funciona para los tres parámetros al final. Por lo tanto, usted sigue incrementando el acumulador para cada voto que un punto hace a cada uno de estos valores y al final, usted hace un maxima local en a, y de esta manera usted puede realmente estimar la parametrización del círculo que usted está buscando. Aquí hay una ilustración visual, donde dado un conjunto de monedas en una imagen, en realidad ahora se puede averiguar dónde se encuentran esas monedas y cuál es el radio de esa moneda al extraer primero los bordes. Por lo tanto, en esto, usted tiene que extraer primero bordes, y luego ser capaz de utilizar esa información de borde para ser capaz de encontrar las parametrizaciones exactas en la superficie. Así que cuando digo parametrizaciones, quiero decir definir los centros y radios de cada uno de esos círculos que usted tiene, (15:56) Usted no necesita detenerse con sólo líneas o círculos, usted puede obviamente hacer esto para cualquier otra forma. Siempre y cuando usted pueda parametrizar cualquier forma de una manera analítica, usted puede dar un conjunto de ecuaciones para definir una forma. Todo lo que tienes que hacer es tomar un punto en tu imagen original y pedirle que vote por lo que serían los parámetros de un polígono al que ese punto pertenece o miente. Y entonces usted sólo cuenta que la parametrización obtuvo los votos más altos entre todas las posibilidades en su espacio de parámetros, y simplemente definir que ser el polígono o cualquier forma que usted está buscando. Pero qué, si usted está buscando la forma que no tiene una descripción analítica. Por ejemplo, en esta diapositiva, se ve esta forma irregular, que no tiene distribución analítica, que no tiene ninguna definición analítica. ¿Cómo se calcula, cómo se encuentran estas formas en una imagen? Asumimos que la forma nos ha dado. Así que, usted sabe que esta es la forma que usted está buscando en una imagen dada y podría ser de diferentes tamaños, podría ser girada de diferentes maneras, podría ser escalado, todas esas transformaciones son posibles. Pero queremos encontrar donde en la imagen miente. Lo único que sabemos es que la forma en este caso particular puede no tener una definición analítica. No se puede escribir como una ecuación. ¿Qué hace usted en este caso en particular? Puede definir un punto de referencia en la forma. Al igual que usted podría definir, por ejemplo, una x nada y nada como un punto de referencia en esa forma y ahora cada punto de borde de esta forma puede ser definido con respecto a ese punto de referencia. Así que cada punto aquí (x, y) tiene una cierta longitud de su punto de referencia (x,) y un ángulo determinado con respecto al punto de referencia 0 y0 (x,). Como ejemplo, podría ser el centroide de ese objeto que está buscando. 0 y0 (x,) 0 y0 Pero no necesita ser el centroide, podría ser cualquier punto de referencia. Así, una vez que tengas un centroide o cualquier otro punto de referencia, por cada punto de borde que tengas, así que recuerda de nuevo, que dada una nueva imagen, tienes que hacer primero una detección de bordes para conseguir los puntos de borde. A continuación, para cada punto de borde se calcula cuál es la distancia al centroide. Primero haría esto para el objeto de plantilla que tiene antes de ejecutarlo en cualquier imagen nueva. Esto es cuando usted sabe que esta es la forma que usted está buscando, usted define un punto de referencia para cada punto de borde en esta forma particular, usted calcula una distancia al centroide, que es r y una orientación. i I + i y luego crear algo llamado una tabla r. Y lo que dice la tabla r es que, para una orientación de borde dada, ¿cuáles son todas las posibilidades? ¿Cuáles son todos los puntos que podrían tener un determinado radio con la misma orientación, con respecto al punto de referencia? Del mismo modo, para otro punto con otra orientación de orientación, digamos que es este punto de ventaja en particular. Ese 2 de 2 ° 2 tiene un radio determinado con respecto al punto de referencia. Del mismo modo, podría haber otro punto con el mismo ángulo, que tendría un cierto radio r21, podría haber un tercer punto con el mismo ángulo, misma orientación de la imagen y que podría tener un radio r y se crea una tabla r 23, que conecta estas orientaciones y estas distancias a ese centroide del punto de referencia. Así que una vez que haya construido esta tabla r, ¿qué hacemos? (19:31) Aquí está el algoritmo de lo que se conoce como Transformación Dura Generalizada. Por lo tanto, tiene sus datos. A usted se le da su tabla r, que ya ha construido a partir de la forma que le fue dada. Recuerda una vez más, que la forma está definida para ti. No definido se le da a usted, no está bien definido matemáticamente se le da a usted. Utilizando esa forma se construye algo llamado la tabla r y también se construye una matriz acumulador para cuántas de las dimensiones que tiene que estimar. Por lo tanto, si ese punto de referencia tiene dos coordenadas, sólo tiene dos coordenadas para votar. De lo contrario, también puede tener otros parámetros. Si usted permite que su forma cambie de múltiples maneras, usted podría tener otras dimensiones en su acumulador para lo cual también los puntos pueden votar. En este caso en concreto, para mantenerlo sencillo supongamos que la forma va a ser la misma, solo que la forma se podría colocar en cualquier parte de la imagen. Sin escalado, sin rotación. Asumamos que ese es el escenario aquí. Entonces, lo único que estamos tratando de encontrar es ¿dónde estaría el centroide de ese objeto? Por lo tanto, tiene una matriz acumulada, que es de dos dimensiones que van de X a, cmin Xcmax Y cm a Y c son los valores máximos que el centroide puede asumir en el eje X. en max Similarmente, Y c y. E inicializa el acumulador, cada celda del acumulador mín Y cmax a 0. A continuación, por cada punto para cada ri, en su tabla r, usted intenta escribir si su centroide puede ser escrito como este x + r,. i cos i i y + ri sin switi i Si usted puede escribir su centroide con respecto a esto, dado x y utilizando esta fórmula en particular, usted aumentaría el acumulador para ese centroide en particular. Y sigues haciendo esto por varias posibilidades de centroides diferentes, donde tus posibilidades centroides vendrán de Xc a y a, donde discretizar tus posibilidades del centroide y min Xcmax Y cmin Y cmax creás una matriz acumulativa. Esa es la forma en que lo haría. Y al final, conseguirías un conjunto de valores, un conjunto de recuentos de frecuencia en cuanto a lo que votaba cada x y y haces una supresión no máxima para encontrar las máximas locales y eso te va a dar el xc yc final que corresponden a este nuevo conjunto de puntos que se te dan. Hablando en términos de imágenes. Una vez más, supongamos que esta es la forma que usted está buscando. Como he dicho, asumimos en este ejemplo aquí, que sólo estamos buscando la forma como es, sin cambio de escala ningún cambio de rotación. Por lo tanto, lo que significa que la única cosa que puede cambiar es el centro del objeto podría ser todas partes diferentes. Entonces, por eso estamos votando sólo por dónde está el centro. Y así que dada una nueva imagen, usted ejecuta un detector de borde y para cada punto de borde, deja que funcione para donde estaría el centroide y donde quiera que obtenga el máximo de votos para el centroide es donde su centroide potencialmente podría ser. Usted podría utilizar este tipo de un enfoque para decir, encontrar un coche en una imagen. Si supieras que un coche tiene una forma particular, definiste esa forma, ahora te preguntas cada, corres un detector de bordes en la nueva imagen, y luego pide a cada punto en el borde que vote por dónde está el centro del coche y en base a eso, probablemente puedes rastrear dónde se encuentra el coche en la imagen dada. Por lo tanto, podría utilizar un enfoque de este tipo incluso para la detección de objetos. De nuevo, dentro de cambios repentinos en sus formas en las posibilidades de la forma. Si un coche plantea cambios por completo, obviamente este tipo de enfoque no funcionará en ese escenario. Por lo tanto, funciona sólo con cierta tolerancia. (23:23) Para resumir la transformación de Hough, es un enfoque eficaz para la detección de formas, objetos, incluyendo decir múltiples, incluso si hubiera varios coches, usted puede encontrar probablemente todos ellos. Podrías tener múltiples máximas en donde, los bordes votan por los centroides de los coches y cada uno de ellos puede ser diferentes instancias de un coche en una imagen determinada. Por lo tanto, también puede utilizar esto para la detección de varias instancias de objeto en una imagen. Las ventajas de la transformación de Hough es que se trata de oclusión bastante bien porque es un procedimiento de votación. Mientras el número de votos sea alto, no importa si ciertos votos se equivocan. Por lo tanto, incluso si una parte del objeto fuera ocluida puede funcionar. Obviamente, si una parte significativa del objeto se ocluye, no funcionará. También es robusto para el ruido por la misma razón, porque sólo es necesario mirar un cierto conjunto de píxeles, y mientras voten por una mayoría, como mayoría, usted va a obtener su forma u objeto en la imagen. El problema aquí es que puede ser computacionalmente caro porque dependiendo de cómo quantizar su espacio de parámetros. Recuerda que cada punto tiene que emitir un voto por diferentes posibilidades en tu espacio de parámetros, que puede ser de mucho tiempo. Y establecer sus parámetros y cuantificarlos puede no ser fácil para diferentes tipos de formas. Para la línea, el círculo y algunas formas realmente definidas, puede ser sencillo, para ciertas otras formas esto puede no ser fácil o cuantificarlos puede no dar respuestas muy precisas. Esas son algunas limitaciones para trabajar aquí. (25:02) Aquí está la visualización del ejemplo del coche. Por lo tanto, tiene una imagen de modelo y hay algunos puntos clave con respecto a un punto de referencia en el centro de la imagen. Por lo tanto, se registran las coordenadas relativas al punto de referencia en la imagen del modelo y para cada imagen de prueba, se busca la misma configuración de los puntos clave con respecto al centroide del objeto. (25:37) Así, en estos casos particulares, el coche está invertido, pero cuando la imagen de prueba es de la misma conphiguración que el objeto original, se encuentra un partido en este escenario en particular. (25:47) Aquí hay un ejemplo más. Así que si considera que su imagen modelo es la Torre Eiffel y aquí hay una imagen de prueba que también es la Torre Eiffel tomada en una escala diferente en un día diferente con diferentes condiciones de iluminación. (26:02) Entonces usted tiene su acumulador después de encontrar sus puntos de imagen de modelo en su imagen original y su imagen de prueba, usted tiene su acumulador que vota por el centroide del objeto con respecto a varios puntos clave en ese objeto. Usted considera un maxima local, usted no ve muy claramente aquí, pero el maxima local está en algún lugar en el medio. (26:29) Y en base a eso se vota por donde se encuentra la Torre Eiffel en la imagen de prueba. (26:36) Su trabajo en casa para esta conferencia es el Capítulo 4.3 del libro de Szeliski y un par de preguntas para que usted piense. ¿Cómo Huir Transformar para detectar elipsis, cuadrados y rectángulos? Trate de averiguar cuáles son las parametrizaciones o las formas analíticas de cada una de estas formas, e intente averiguar cómo se vería la matriz del acumulador en cada uno de estos casos. Eso debería ayudar a abordar estos problemas. Y un caso de uso del mundo real. Supongamos que su amigo que trabaja en una startup de diagnóstico le pregunta cómo contar el número de glóbulos rojos en una muestra de sangre automáticamente? Así que usted tiene una muestra de sangre, usted quiere una manera automatizada de contar el número de glóbulos rojos usando la transformación de tos. ¿Qué le aconsejaría usted o ella? Algo para que lo penséis. Y aquí están las referencias.