Defensa Tesis Doctorado Mariano Tepper

• Título: Detectando agrupamientos y contornos: un estudio doble sobre representación de formas
• Directores: Dr. Andrés Almansa y Dra. Marta Mejail
• Jurados:
  Dr.Gregory Randall, UDeLaR, Uruguay.
  Dr. Alvaro Pardo Piccone, UCUDAL, Uruguay.
  Dr. Alfred Bruckstein, TECHNION, I.I.T.
• Resumen:

Las formas juegan un rol clave en nuestro sistema cognitivo: en la percepción de las formas yace el principio de la formación de conceptos. Siguiendo esta línea de pensamiento, la escuela de la Gestalt ha estudiado extensivamente la percepción de formas como el proceso de asir características estructurales encontradas o \emph{impuestas sobre} el material de estímulo.En resumen, tenemos dos modelos de formas: pueden existir físicamente o ser un producto de nuestros procesos cognitivos.

El primer grupo está compuesto por formas que pueden ser definidas extra\-yendo los contornos de objetos sólidos. En este trabajo nos restringiremos al caso bidimensional. Decimos entonces que las formas del primer tipo son formas planares. Atacamos el problema de detectar y reconocer formas planares. Ciertas restricciones teóricas y prácticas nos llevan a definir una forma planar como cualquier pedazo de línea de nivel de una imagen.

Comenzamos por establecer que los métodos a contrario existentes para detectar líneas de nivel son usualmente muy restrictivos: una curva debe ser enteramente saliente para ser detectada. Esto se encuentra en clara contradicción con la observación de que pedazos de líneas de nivel coinciden con los contornos de los objetos. Por lo tanto proponemos una modificación en la que el algoritmo de detección es relajado, permitiendo la detección de curvas parcialmente salientes.

En un segundo acercamiento, estudiamos la interacción entre dos maneras diferentes de determinar la prominencia de una línea de nivel. Proponemos un esquema para competición de características donde el contraste y la regularidad compiten entre ellos, resultando en que solamente las líneas de nivel contrastadas y regulares son consderedas salientes.

Una tercera contribución es un algoritmo de limpieza que analiza líneas de nivel salientes, descartando los pedazos no salientes y conservando los salientes. Está basado en un algoritmo para detección de multisegmentos que fue extendido para trabajar con entradas periódicas.

Finalmente, proponemos un descriptor de formas para codificar las formas detectadas, basado en el Shape Context global. Cada línea de nivel es codificada usando shape contexts, generando así un nuevo descriptor semi-local. A continuación adaptamos un algoritmo existente de matching de formas a contrario para nuestro caso particular.

El segundo grupo está compuesto por formas que no se corresponden con un objeto sólido, pero que están generadas por la integración de varios objetos sólidos. La formas más simples en este grupo son configuraciones de puntos en dos dimensiones. Las técnicas de agrupamiento pueden resultar útiles en estas situaciones.

En un trabajo fundacional de 1971, Zahn trató el problema de encontrar agrupamientos perceptuales de acuerdo a la gestalt proximidad y propuso tres principiops básicos para algoritmos de clustering: (1) solamente importan las distancias entre puntos, (2) resultados estables entre diferentes ejecuciones e (3) independencia de la estrategia de exploración. Un tercer requerimiento implícito es crucial: los grupos pueden tener formas arbitrarias y un algoritmo para detectarlos debe ser capaz de lidiar con esto. En esta parte nos concentraremos en el diseño de algoritmos de agrupamiento que cumplan completamente los requemrimientos anteriores, imponiendo suposiciones mínimas sobre los datos a agrupar.

Comenzamos por analizar el problema de la validación de agrupamientos en una estructura jerárquica. Basándonos en métodos no-paramétricos para estimación de la densidad, proponemos calcular la prominencia de un determinado grupo. Luego, es posible elegir los grupos más salientes dentro de la jerarquía. En la práctica, el método muestra una preferencia por los grupos compactos y proponemos una simple heurística para corregir este tema.

En general, los métodos jerárquicos basados en grafos requieren calcular primero el grafo completo de distancias entre puntos. Por esta razón los métodos jerárquicos son considerados lentos. El más comúnmente utilizado, y el más rápido, algoritmo de entre ellos es el basado en el Árbol Generador Mínimo (AGM). Proponemos por lo tanto un algoritmo para calcular el AGM evitando el paso intermedio de calcular el conjunto completo de distancias. Adicionalmente, el algoritmo puede ser fácilmente paralelizado. El método exhibe una buena performance para datos de baja dimensionalidad y permite un cálculo aproximado pero robusto en más altas dimensiones.

Finalmente proponemos un método para elegir subárboles agrupados dentro del AGM, mediante el cálculo de estadísticas de ejes simples. El método permite recuperar grupos con formas arbitrarias. También trabaja en situaciones ruidosas, donde el ruido es considerado como datos sin agrupar, permitiendo separarlos de los datos agrupados. También mostramos que la aplicación iterativa del algoritmo permite resolver un fenómeno llamado enmascaramiento, donde un grupo muy populoso impide la deteccion de otros menos populosos.