0:04
Hola.
En este vídeo aprenderemos a extraer componentes conexas de las imágenes.
En el vídeo anterior vimos que el resultado de una clasificación sobre
descriptores de pixel nos daba una imagen binaria donde se distinguía el
fondo del objeto.
Pues bien, hoy tomaremos estas imágenes binarias y agruparemos los
pixeles de tal manera que podamos pasar de pixeles a regiones,
lo que llamaremos componentes conexas.
Las extracción de componentes conexas está relacionada con la localización de los
objetos dentro de la imagen.
La localización es un problema esencial en la detección automática de objetos, puesto
que el número de ventanas candidatas a contener objetos puede ser muy grande.
Y por tanto tiene una especial relevancia en el diseño del detector.
Así pues en el esquema que vamos siguiendo en el curso,
la clase de hoy está bien enfocada a la localización de objetos y por tanto se
relaciona con el módulo de generación de candidatos.
En el esquema general la generación de candidatos puede aparecer antes o después
de la extracción de características pero siempre antes de la clasificación.
Sin embargo en el esquema simplificado que estamos usando en estos primeros vídeos,
que estamos dedicando a la detección de manos,
la localización de los objetos viene en el paso final.
Una vez hemos clasificados los pixeles como pertenecientes o no a la clase mano.
Así pues dentro de este esquema el objetivo será la generación de
ventanas que directamente localizarán el objeto dentro de la imagen.
Puesto que en este caso el objeto viene dado por las componentes conexas formadas
por pixeles clasificados como piel.
Así pues para recordar el esquema de trabajo diremos que he dado una imagen
de entrada, se aplica un clasificador sobre el descriptor de color.
Recordemos los pixeles en blanco representan pixeles clasificados como
de color piel y los pixeles en negro representan los que no han sido
clasificados como piel.
A partir de este resultado ahora nos planteamos la generación de las
ventanas que han de localizar las manos encontradas.
Pues bien, esta generación de ventanas se realizará en dos pasos.
Primero se etiquetarán las componentes conexas de la imagen,
es el procedimiento conocido como labeling en inglés.
Y seguidamente para cada región etiquetada se calculará la ventana que la contiene.
Vamos a ver, pues, cómo se lleva a termino esta generación de ventanas.
Primero explicaremos cómo se etiquetan las regiones conectadas.
Para la extracción de componentes conexas se aplica pues el algoritmo de etiquetaje.
El objetivo del algoritmo es dar una misma etiqueta a cada región
conexa que aparece en la imagen.
Hay varias versiones de este algoritmo.
Aquí explicaremos el más básico que se basa en hacer dos recorridos
sobre la imagen.
Los recorridos serán pixel a pixel empezando de izquierda a derecha y de
arriba a abajo.
Supondremos que en la imagen binaria que queremos etiquetar los
pixeles que forman parte de una región están a uno y los pixeles que
forman parte del fondo están a cero.
En el primer recorrido se asignará una etiqueta a cada pixel que esté a uno.
El valor de la etiqueta dependerá de sus vecinos superior e izquierdo y
guardará posibles equivalencias.
En el segundo recorrido se resolverán todas las equivalencias que se
han encontrado y se volverán a etiquetar los pixeles que así lo requieran.
Antes de continuar con el algoritmo de etiquetaje debemos considerar un
concepto previo.
Es el concepto de conectividad.
En las imágenes digitales que usamos podemos considerar dos tipos de
conectividad, la conectividad a cuatro y la conectividad a ocho.
La conectividad a cuatro considera como vecinos conexos de un
pixel los que están en dirección horizontal y vertical.
Mientras que la conectividad a ocho considera además como conectados los
que están en la diagonal.
Según qué tipo de conectividad consideremos,
el algoritmo de etiquetaje deberá dar resultados diferentes.
Para un ejemplo concreto en este caso suponemos
que los objetos están en negro y el fondo en blanco.
Si consideramos la conectividad a cuatro al resultado de
etiquetar dará cuatro regiones con diferentes etiquetas.
Mientras que si consideramos la conectividad a ocho el
resultado dará solamente dos regiones,
puesto que en este caso la región verde y la roja formarán parte de la misma región
por una vecindad diagonal y lo mismo pasa con la azul de la amarilla.
Volvamos pues a los pasos del algoritmo.
you hemos dicho que en el primer recorrido se asignará
una etiqueta a cada pixel que esté a uno.
El valor de la etiqueta dependerá de sus vecinos superior e izquierdo y guardará
las posibles equivalencias.
Nos podremos encontrar con tres situaciones diferentes,
vamos a analizarlas una a una.
El caso más simple es cuando el pixel actual que se analiza
que por tanto está a uno y sus vecinos superior e izquierdo están todos a cero.
Este es el caso en que podríamos decir que nos acabamos de encontrar una
nueva región.
Para cada caso mostraremos la vecindad de los pixeles según que
estemos en conectividad a cuatro, sería este caso de aquí o que nos
encontremos a conectividad a ocho que corresponde a este caso de aquí.
En conectividad a cuatro se evalúan los pixeles izquierdo y superior.
En conectividad a ocho se evalúan
además el que va en diagonal y el derecho superior.
Así pues, para este caso de toda la vecindad a cero se
asigna el pixel al pixel una etiqueta nueva.
Se deberá mantener un contador de etiquetas que vaya creciendo a medida que
vamos encontrando nuevas regiones.
Segundo caso, es cuando el pixel actual
tiene un vecino distinto a cero pero solo uno.
En este caso se asignará al pixel actual la misma etiqueta que la del vecino que
está a uno.
Simplemente estamos encontrando un nuevo pixel de una región que you conocíamos.
Vamos a por el caso tres.
En el caso tres es cuando el pixel actual tiene más de un vecino que está a uno.
En este caso nos encontramos con que podríamos asignarle dos etiquetas.
La solución será asignar una de estas diversas etiquetas con
un criterio preestablecido, por ejemplo la más inferior a la izquierda.
Y se guardará la equivalencia que nos acabamos de encontrar.
Acabamos de encontrar un pixel que por los vecinos que tiene puede pertenecer
a dos regiones.
Por tanto a partir de ahora la región etiquetada como E1 y la etiquetada como E2
van a ser la misma región.
Por tanto guardamos esta equivalencia.
En el segundo recorrido lo que haremos será primero
resolver todas las equivalencias que nos hemos ido encontrando y entonces
se volverán a etiquetar los pixeles que así lo requieran según las equivalencias.
Vamos a ver un ejemplo de aplicación de este algoritmo.
Dada una imagen muy simple consideráramos que los pixeles negros,
los de objeto están a uno y los pixeles blanco de fondo están a cero.
Supondremos primero el caso de cuatro conectividad para el paso uno,
es decir para el primer recorrido de la imagen.
Nos encontramos un primer pixel,
es el que está a uno con vecinos sin etiquetas, caso uno.
Entonces creamos una etiqueta nueva.
Nos encontramos un pixel con un vecino etiquetado, es decir el caso dos.
Entonces le asignamos la misma etiqueta que al anterior.
Otro nuevo pixel sin vecino etiquetado, caso uno.
Entonces nueva etiqueta y así sucesivamente vamos
encontrando nuevas regiones por tanto nuevas etiquetas.
En el caso este del dos y el tres hemos encontrado casos dos,
es decir vecinos you etiquetados.
Y aquí llegamos a la primera equivalencia.
Este es el caso tres.
Hemos llegado a un pixel que tiene en la parte superior una etiqueta de cuatro,
en la parte izquierda tiene una etiqueta de tres.
La resolveremos asignado la etiqueta de tres, por ejemplo la de la izquierda.
Y nos guardaremos la equivalencia.
A partir de ahora la etiqueta tres y la etiqueta cuatro son iguales.
Si continuamos encontrándonos, encontramos una nueva equivalencia.
La etiqueta cinco va a ser equivalente a la etiqueta tres.
Vamos así sucesivamente iremos etiquetando todo.
Aparece una nueva región, una nueva región, estamos en conectividad a cuatro.
Y hasta aquí acabamos.
Empecemos con el paso dos.
Primero resolveremos las equivalencias.
Esto es las etiquetas tres, cuatro y cinco van a pasar a ser la misma.
Una vez resueltas todas las etiquetas que habíamos encontrado en el recorrido uno.
Y le asignamos una de ellas.
En este caso le asignaremos el tres la más pequeña.
Entonces recorremos otra vez la imagen que hemos etiquetado en el
primer paso y donde había un cuatro vamos a poner
un tres y donde hay un cinco vamos a poner también un tres.
El resto quedará igual.
Así pues en conectividad a cuatro you tenemos la imagen etiquetada.
Ahora vamos a analizar el caso de conectividad a ocho.
En el primer recorrido repetimos el mismo proceso solo que ahora cambiará
la conectividad que vayamos a considerar.
De esta manera nos iremos encontrando nuevas regiones igual que antes,
y aquí es cuando cambia con respecto a la primera.
En este pixel a la vecindad que consideramos es también la superior
derecha, entonces este pixel tiene un vecino etiquetado,
el que va en diagonal entonces coge la etiqueta uno.
Continuamos, primera equivalencia el tres en
diagonal con el uno en el vecino superior derecho, otra vez nos encontramos
en este caso una equivalencia y así sucesivamente vamos aplicando los mismos
casos simplemente cambiando el tipo de conectividad que consideramos.
Aquí viene otro caso que en el anterior hacía aparecer una etiqueta nueva, en este
mantiene la etiqueta porque en diagonal tenemos un uno y así sucesivamente.
Vamos al paso dos.
Resolvemos todas las equivalencias, solo tenemos unas y definimos que a la
equivalencia uno igual a tres vamos a asignarla a la etiqueta uno,
por tanto en el segundo recorrido vamos a sustituir todas las etiquetas
tres por etiquetas tipo uno.
Y a partir de aquí you tenemos el resultado final de este ejemplo.
Si cambiamos etiquetas por colores podemos ver mucho mejor los resultados.
Con conectividad cuatro aparecen más regiones conexas de menos tamaño,
en conectividad a ocho tenemos menos regiones más grandes y con
ramificaciones debidas a las conectividades de las diagonales.
Una vez hemos visto el algoritmo de etiquetaje de regiones,
pasaremos al último paso donde se calcula la localización de cada región.
El paso de la localización es el más simple,
para cada etiqueta de la imagen se buscarán los extremos superior
izquierdo e inferior derecho como localizadores de la ventana del objeto.
Estos se encontrarán a partir de minimizar,
maximizar los valores de las coordenadas de los pixeles dentro de la imagen.
Para concluir, aquí resumimos todos los pasos de la detección de manos según el
modelo simplificado que hemos usado.
Dada una imagen de entrada se aplica un clasificador sobre el descriptor de color,
recordemos pixeles en blanco representan pixeles de color piel,
pixeles en negro representan los que no han sido clasificados como piel.
A partir de este resultado la generación de las ventanas que
han de localizar las manos encontradas se realizará en dos pasos.
Primero, se etiquetan las componentes conexas de la imagen con el
algoritmo de etiquetaje que acabamos de ver y seguidamente para cada
región etiquetada se calcula la ventana que la contiene.
you para acabar y como resumen de esta clase podemos decir que en este vídeo
hemos empezado a trabajar con el módulo de generación de ventanas candidatas,
en este caso ha sido a partir de las imágenes binarias que habíamos tenido con
el clasificador de piel que diseñamos en un vídeo anterior.
Hemos visto un algoritmo de etiquetaje de regiones conexas que nos permite conectar
todos los pixeles clasificados como piel que pertenecen a una misma región.
El algoritmo que hemos visto consigue el etiquetaje de la
imagen haciendo dos recorridos de la imagen y lo hemos visto
para dos tipos de conectividad que pueden presentarse a la hora de definir vecindad,
es la conectividad a cuatro y la conectividad a ocho.
Finalmente hemos visto cómo extraer las ventanas del objeto a partir de la región.
Y hasta aquí este vídeo sobre componentes conexas.