el árbol de formas de una imagen y su aplicación a la...
Transcript of el árbol de formas de una imagen y su aplicación a la...
![Page 1: el árbol de formas de una imagen y su aplicación a la ...dev.ipol.im/~coco/website/docs/pres_2005_montevideo.pdf · Propiedades algoritmícas del árbol de formas I El árbol de](https://reader034.fdocumento.com/reader034/viewer/2022042213/5eb7911cd39c297dbe4f5014/html5/thumbnails/1.jpg)
el árbol de formas de una imagen y suaplicación a la segmentación
enric meinhardt llopis
departament de tecnologiauniversitat pompeu fabra
24–08–2005
![Page 2: el árbol de formas de una imagen y su aplicación a la ...dev.ipol.im/~coco/website/docs/pres_2005_montevideo.pdf · Propiedades algoritmícas del árbol de formas I El árbol de](https://reader034.fdocumento.com/reader034/viewer/2022042213/5eb7911cd39c297dbe4f5014/html5/thumbnails/2.jpg)
Outline
Introducción
Definición del árbol
Aplicación: segmentación
Apéndice: observación “filosófica”
![Page 3: el árbol de formas de una imagen y su aplicación a la ...dev.ipol.im/~coco/website/docs/pres_2005_montevideo.pdf · Propiedades algoritmícas del árbol de formas I El árbol de](https://reader034.fdocumento.com/reader034/viewer/2022042213/5eb7911cd39c297dbe4f5014/html5/thumbnails/3.jpg)
Outline
Introducción
Definición del árbol
Aplicación: segmentación
Apéndice: observación “filosófica”
![Page 4: el árbol de formas de una imagen y su aplicación a la ...dev.ipol.im/~coco/website/docs/pres_2005_montevideo.pdf · Propiedades algoritmícas del árbol de formas I El árbol de](https://reader034.fdocumento.com/reader034/viewer/2022042213/5eb7911cd39c297dbe4f5014/html5/thumbnails/4.jpg)
El problema de la segmentaciónEncontrar los diferentes tipos de células que aparecen en la imagen
=⇒
![Page 5: el árbol de formas de una imagen y su aplicación a la ...dev.ipol.im/~coco/website/docs/pres_2005_montevideo.pdf · Propiedades algoritmícas del árbol de formas I El árbol de](https://reader034.fdocumento.com/reader034/viewer/2022042213/5eb7911cd39c297dbe4f5014/html5/thumbnails/5.jpg)
Posibles soluciones para el problema de lasegmentaión
Aproximaciones “variacionales”
I Contornos activosI Regiones activasI Ventaja: encuentran el mejor contorno según un criterioI Inconveniente: requieren una buena inicialización
Aproximación “morfológica”
I Los bordes de los objetos son pedazos de curvas de nivelI Inconveniente: eso no es siempre ciertoI Ventaja: muchas veces es una buena aproximaciónI Ventaja: el conjunto de las curvas de nivel es manejable
![Page 6: el árbol de formas de una imagen y su aplicación a la ...dev.ipol.im/~coco/website/docs/pres_2005_montevideo.pdf · Propiedades algoritmícas del árbol de formas I El árbol de](https://reader034.fdocumento.com/reader034/viewer/2022042213/5eb7911cd39c297dbe4f5014/html5/thumbnails/6.jpg)
Outline
Introducción
Definición del árbol
Aplicación: segmentación
Apéndice: observación “filosófica”
![Page 7: el árbol de formas de una imagen y su aplicación a la ...dev.ipol.im/~coco/website/docs/pres_2005_montevideo.pdf · Propiedades algoritmícas del árbol de formas I El árbol de](https://reader034.fdocumento.com/reader034/viewer/2022042213/5eb7911cd39c297dbe4f5014/html5/thumbnails/7.jpg)
Una imagen se puede ver como un mapa topográfico
Los conjuntos de nivel de una imagen son las componentesconnexas de las imágenes umbralizadas.Las curvas de nivel son las fronteras de los conjuntos de nivel.
![Page 8: el árbol de formas de una imagen y su aplicación a la ...dev.ipol.im/~coco/website/docs/pres_2005_montevideo.pdf · Propiedades algoritmícas del árbol de formas I El árbol de](https://reader034.fdocumento.com/reader034/viewer/2022042213/5eb7911cd39c297dbe4f5014/html5/thumbnails/8.jpg)
¿Cómo son las curvas de nivel de una imagen?(vamos a suponer que la imagen es suave, sin trozos planos, y nosolvidamos de los lados de la imagen)
I la mayoría de las curvas son curvas de Jordan
I dos curvas de nivel, o bien son disjuntas o bien una está dentrode la otra
I por lo tanto, el conjunto de todas las curvas de nivel tiene unaestructura de árbol
I este árbol ha sido llamado el “árbol de las formas” de la imagen
![Page 9: el árbol de formas de una imagen y su aplicación a la ...dev.ipol.im/~coco/website/docs/pres_2005_montevideo.pdf · Propiedades algoritmícas del árbol de formas I El árbol de](https://reader034.fdocumento.com/reader034/viewer/2022042213/5eb7911cd39c297dbe4f5014/html5/thumbnails/9.jpg)
Árbol de una imagen sintética
![Page 10: el árbol de formas de una imagen y su aplicación a la ...dev.ipol.im/~coco/website/docs/pres_2005_montevideo.pdf · Propiedades algoritmícas del árbol de formas I El árbol de](https://reader034.fdocumento.com/reader034/viewer/2022042213/5eb7911cd39c297dbe4f5014/html5/thumbnails/10.jpg)
Árbol de una imagen sintética con bordes suavizados
![Page 11: el árbol de formas de una imagen y su aplicación a la ...dev.ipol.im/~coco/website/docs/pres_2005_montevideo.pdf · Propiedades algoritmícas del árbol de formas I El árbol de](https://reader034.fdocumento.com/reader034/viewer/2022042213/5eb7911cd39c297dbe4f5014/html5/thumbnails/11.jpg)
Árbol de una imagen sintética
![Page 12: el árbol de formas de una imagen y su aplicación a la ...dev.ipol.im/~coco/website/docs/pres_2005_montevideo.pdf · Propiedades algoritmícas del árbol de formas I El árbol de](https://reader034.fdocumento.com/reader034/viewer/2022042213/5eb7911cd39c297dbe4f5014/html5/thumbnails/12.jpg)
El árbol de formas facilita algunas tareas deprocesamientoAquí vemos el efecto de un filtro de grano
imagenoriginal(tiene 2717regiones)
podarlas regionesmenores que 2píxels(quedan 293regiones)
podarlas regionesmenores que 4píxels(quedan 10regiones)
![Page 13: el árbol de formas de una imagen y su aplicación a la ...dev.ipol.im/~coco/website/docs/pres_2005_montevideo.pdf · Propiedades algoritmícas del árbol de formas I El árbol de](https://reader034.fdocumento.com/reader034/viewer/2022042213/5eb7911cd39c297dbe4f5014/html5/thumbnails/13.jpg)
Espacio de escala podando las formas pequeñas
imagenoriginal(tiene 18476regiones)
regionesmayores que 100(3366)
regionesmayores que 1000(817)
![Page 14: el árbol de formas de una imagen y su aplicación a la ...dev.ipol.im/~coco/website/docs/pres_2005_montevideo.pdf · Propiedades algoritmícas del árbol de formas I El árbol de](https://reader034.fdocumento.com/reader034/viewer/2022042213/5eb7911cd39c297dbe4f5014/html5/thumbnails/14.jpg)
Propiedades algoritmícas del árbol de formas
I El árbol de formas es una partición jerárquica de la imagenI Para una imagen de n píxels, el coste de construir el árbol
es O(n log n).I Las operaciones siguientes tienen un coste proporcional a
su output:I Ver si un píxel pertenece a una región o noI Recorrer el borde de una regiónI Recorrer todos los píxeles de una regiónI Dado un píxel, encontrar la región más pequeña que lo
contieneI Dado un píxel, ver de qué regiones es fronterizo
![Page 15: el árbol de formas de una imagen y su aplicación a la ...dev.ipol.im/~coco/website/docs/pres_2005_montevideo.pdf · Propiedades algoritmícas del árbol de formas I El árbol de](https://reader034.fdocumento.com/reader034/viewer/2022042213/5eb7911cd39c297dbe4f5014/html5/thumbnails/15.jpg)
Bibliografía sobre el árbol de formas
I Artículo The tree of shapes of an image (Ballester,Caselles, Monasse, 2001). Definición formal del árbol paraimágenes semicontínuas.
I Tesis doctoral de Pascal Monasse. Algoritmo eficiente deconstrucción del árbol.
I Software Megawave. Implementación del algoritmo demonasse.
![Page 16: el árbol de formas de una imagen y su aplicación a la ...dev.ipol.im/~coco/website/docs/pres_2005_montevideo.pdf · Propiedades algoritmícas del árbol de formas I El árbol de](https://reader034.fdocumento.com/reader034/viewer/2022042213/5eb7911cd39c297dbe4f5014/html5/thumbnails/16.jpg)
Outline
Introducción
Definición del árbol
Aplicación: segmentación
Apéndice: observación “filosófica”
![Page 17: el árbol de formas de una imagen y su aplicación a la ...dev.ipol.im/~coco/website/docs/pres_2005_montevideo.pdf · Propiedades algoritmícas del árbol de formas I El árbol de](https://reader034.fdocumento.com/reader034/viewer/2022042213/5eb7911cd39c297dbe4f5014/html5/thumbnails/17.jpg)
Segmentación como una selección de nodos del árbol
I Seleccionar unos cuantos nodos del árbol da lugar a unasegmentación
I Se trata de decidir cuáles son los nodos interesantes
![Page 18: el árbol de formas de una imagen y su aplicación a la ...dev.ipol.im/~coco/website/docs/pres_2005_montevideo.pdf · Propiedades algoritmícas del árbol de formas I El árbol de](https://reader034.fdocumento.com/reader034/viewer/2022042213/5eb7911cd39c297dbe4f5014/html5/thumbnails/18.jpg)
Selección de nodos mediante un umbral
curvasdel nivel 140
curvasdel nivel 200
![Page 19: el árbol de formas de una imagen y su aplicación a la ...dev.ipol.im/~coco/website/docs/pres_2005_montevideo.pdf · Propiedades algoritmícas del árbol de formas I El árbol de](https://reader034.fdocumento.com/reader034/viewer/2022042213/5eb7911cd39c297dbe4f5014/html5/thumbnails/19.jpg)
Selección de nodos de Desolneux et al.
I Seleccionar aquellas curvas que sean suficientementelargas y suficientemente contrastadas
I El contraste de una curva se define como el mínimomódulo del gradiente de la imagen sobre la curva
I Para cada curva de longitud n y contraste µ se calcula laprobabilidad que una curva de esas característicasaparezca en una imagen de ruido
I Si tal probabilidad es muy pequeña, se acepta la curvaI El umbral de aceptación se elige para que en imágenes de
ruido aparezca como máximo una curva (principio deHelmholz)
![Page 20: el árbol de formas de una imagen y su aplicación a la ...dev.ipol.im/~coco/website/docs/pres_2005_montevideo.pdf · Propiedades algoritmícas del árbol de formas I El árbol de](https://reader034.fdocumento.com/reader034/viewer/2022042213/5eb7911cd39c297dbe4f5014/html5/thumbnails/20.jpg)
Ejemplo de selección de nodos de Desolneux et al.
![Page 21: el árbol de formas de una imagen y su aplicación a la ...dev.ipol.im/~coco/website/docs/pres_2005_montevideo.pdf · Propiedades algoritmícas del árbol de formas I El árbol de](https://reader034.fdocumento.com/reader034/viewer/2022042213/5eb7911cd39c297dbe4f5014/html5/thumbnails/21.jpg)
Selección de nodos con otra definición del contraste.
![Page 22: el árbol de formas de una imagen y su aplicación a la ...dev.ipol.im/~coco/website/docs/pres_2005_montevideo.pdf · Propiedades algoritmícas del árbol de formas I El árbol de](https://reader034.fdocumento.com/reader034/viewer/2022042213/5eb7911cd39c297dbe4f5014/html5/thumbnails/22.jpg)
Otros criterios para la selección de nodos
I La selección por umbrales y áreas utiliza los descriptoresnivel de gris y área
I La selección de Desolneux utiliza los descriptoresperímetro y contraste mínimo
I En ambos casos, se selecciona una región (convexa) delespacio de descriptores
I Tal vez convendría utilizar espacios de descriptores másgrandes
![Page 23: el árbol de formas de una imagen y su aplicación a la ...dev.ipol.im/~coco/website/docs/pres_2005_montevideo.pdf · Propiedades algoritmícas del árbol de formas I El árbol de](https://reader034.fdocumento.com/reader034/viewer/2022042213/5eb7911cd39c297dbe4f5014/html5/thumbnails/23.jpg)
Espacios de descriptores
Algunos descriptores interesantes
I área, perímetroI nivel de grisI nivel de gris medio del interiorI varianza del nivel de gris del interiorI contraste mínimo en el bordeI contraste medio en el borde
![Page 24: el árbol de formas de una imagen y su aplicación a la ...dev.ipol.im/~coco/website/docs/pres_2005_montevideo.pdf · Propiedades algoritmícas del árbol de formas I El árbol de](https://reader034.fdocumento.com/reader034/viewer/2022042213/5eb7911cd39c297dbe4f5014/html5/thumbnails/24.jpg)
Visualización del espacio de descriptoresProyección sobre el plano área / nivel medio de gris del interior
![Page 25: el árbol de formas de una imagen y su aplicación a la ...dev.ipol.im/~coco/website/docs/pres_2005_montevideo.pdf · Propiedades algoritmícas del árbol de formas I El árbol de](https://reader034.fdocumento.com/reader034/viewer/2022042213/5eb7911cd39c297dbe4f5014/html5/thumbnails/25.jpg)
Visualización del espacio de descriptoresProyección sobre el plano área / nivel medio de gris del interior
![Page 26: el árbol de formas de una imagen y su aplicación a la ...dev.ipol.im/~coco/website/docs/pres_2005_montevideo.pdf · Propiedades algoritmícas del árbol de formas I El árbol de](https://reader034.fdocumento.com/reader034/viewer/2022042213/5eb7911cd39c297dbe4f5014/html5/thumbnails/26.jpg)
Visualización del espacio de descriptoresProyección sobre el plano área / nivel medio de gris del interior
![Page 27: el árbol de formas de una imagen y su aplicación a la ...dev.ipol.im/~coco/website/docs/pres_2005_montevideo.pdf · Propiedades algoritmícas del árbol de formas I El árbol de](https://reader034.fdocumento.com/reader034/viewer/2022042213/5eb7911cd39c297dbe4f5014/html5/thumbnails/27.jpg)
Visualización del espacio de descriptoresProyección sobre el plano área / nivel medio de gris del interior
![Page 28: el árbol de formas de una imagen y su aplicación a la ...dev.ipol.im/~coco/website/docs/pres_2005_montevideo.pdf · Propiedades algoritmícas del árbol de formas I El árbol de](https://reader034.fdocumento.com/reader034/viewer/2022042213/5eb7911cd39c297dbe4f5014/html5/thumbnails/28.jpg)
Visualización del espacio de descriptoresProyección sobre el plano área / nivel medio de gris del interior
![Page 29: el árbol de formas de una imagen y su aplicación a la ...dev.ipol.im/~coco/website/docs/pres_2005_montevideo.pdf · Propiedades algoritmícas del árbol de formas I El árbol de](https://reader034.fdocumento.com/reader034/viewer/2022042213/5eb7911cd39c297dbe4f5014/html5/thumbnails/29.jpg)
Conclusiones
I El árbol de formas es una descomposición jerárquica de laimagen en regiones
I La estructura de árbol facilita el cálculo de muchosdescriptores de región
I La segmentación se puede ver como una selección deregiones en el espacio de descriptores
![Page 30: el árbol de formas de una imagen y su aplicación a la ...dev.ipol.im/~coco/website/docs/pres_2005_montevideo.pdf · Propiedades algoritmícas del árbol de formas I El árbol de](https://reader034.fdocumento.com/reader034/viewer/2022042213/5eb7911cd39c297dbe4f5014/html5/thumbnails/30.jpg)
Trabajo actual y futuro
I Desarrollar buenos criterios para trabajar en el espacio dedescriptores
I Interfaz de visualización del espacio de descriptoresI Construcción eficiente del árbol de formas en 3D
![Page 31: el árbol de formas de una imagen y su aplicación a la ...dev.ipol.im/~coco/website/docs/pres_2005_montevideo.pdf · Propiedades algoritmícas del árbol de formas I El árbol de](https://reader034.fdocumento.com/reader034/viewer/2022042213/5eb7911cd39c297dbe4f5014/html5/thumbnails/31.jpg)
¿preguntas?
![Page 32: el árbol de formas de una imagen y su aplicación a la ...dev.ipol.im/~coco/website/docs/pres_2005_montevideo.pdf · Propiedades algoritmícas del árbol de formas I El árbol de](https://reader034.fdocumento.com/reader034/viewer/2022042213/5eb7911cd39c297dbe4f5014/html5/thumbnails/32.jpg)
Outline
Introducción
Definición del árbol
Aplicación: segmentación
Apéndice: observación “filosófica”
![Page 33: el árbol de formas de una imagen y su aplicación a la ...dev.ipol.im/~coco/website/docs/pres_2005_montevideo.pdf · Propiedades algoritmícas del árbol de formas I El árbol de](https://reader034.fdocumento.com/reader034/viewer/2022042213/5eb7911cd39c297dbe4f5014/html5/thumbnails/33.jpg)
Formación de sonidos versus formación de imágenes
Formación de sonidoI Un objeto, al vibrar, emite una onda de sonidoI Si hay varios objetos, el sonido resultante es la suma de
todos ellosI Por lo tanto, descomponer un sonido como suma de
sonidos más simples es un buen análisis
Formación de imagenes
I Un objeto, al ser iluminado, produce una imagenI Si hay varios objetos, la imagen resultante es la
superposición de los más cercanos sobre los más lejanosI Por lo tanto, descomponer una imagen como suma de
imágenes más simples no tiene mucho sentido