Download MC Eduardo Orbe Trujillo 2003

S.E.P.
S.E.I.T.
D.G.I.T.
CENTRO NACIONAL DE INVESTIGACION Y DESARROLLO
TECNOCOGICO
cendet
DESARROLLO DE UNA HERRAMIENTA PARA EL MODELADO
AUTOMATIC0 DE OBJETOS ALFAFLUIBLES
T
PARA
E
OBTENER
MAESTRO
CIENCIAS
P
R
S
E
EDUARDO
EN
EL
I
GRADO
CIENCIAS
S
DE
EN
COMPUTACIONALES
E ’ N
S
QRBE
T
A
:
TRUJiLLO
DIRECTORES DE TESIS DR. RAUL PINTO ELIAS
CUERNAVACA, MORELOS
JULIO DE 2003
I
IMITmuhn I-f
iw€srGU%rrW&hu
FORMULARIO C3
REVISIÓN DE TESIS
Cuemavaca, Mor., a 3 de Julio de 2003.
Dr. Gerard0 Reyes Salgado
Presidente de la Academia de Ciencias Computacionales
Presente
Nos es grato comunicarle, que‘conforme a los lineamientos para la obtención del grado de
Maestro en Ciencias de este Centro, y después de haber sometido a revisión académica la
tesis denominada: “Desarrollo de una Herramienta para el modelado de Objetos
Alfaflexiblec”, realizada por el C. Eduardo orbe Trujillo, y habiendo realizado las
correcciones que le fueron indicadas, acordamos no’tener objeción para que se le conceda la
autorización de impresión de la tesis.
Sin otro particular, quedamos de usted.
Atentamente
La comisión de revisión de tesis
Lic. Olivia Maquinay Diaz, Jefe del Depto. de Servicios Escolares.
C. Eduardo Ofbe Trujiiio, alumno del programa de maestria.
INTERIOR INTERNADO PALMIRA UN. COL. PALMIRA , A.P. 5-1 64.
lELS.(777)312 2 3 1 4 . 3 1 8 7741,FAX(777) 312 2 4 3 4
EMAIL pazos~rdcenidet.com.mx
CP.62490. CUERNAVACA. MOR. - MEXICO
w~ycm~D(~wcIuoN~
uI*zmuo61TEwaQxII
FORMULARIO C4
AUTORIZACIÓN DE IMPRESIÓN DE TESIS
Cuemavaca, Mor., a 16 de Julio de 2003.
C. Eduardo Orbe Trujillo
Candidato al grado de Maestro en Ciencias
en Ciencias Computacionales
Presente
Después de haber atendido las indicaciones sugeridas por la Comisión Revisora de la
Academia de Ciencias Computacionales en relación a su trabajo de tesis: “Desarrollo de una
Herramienta para el Modelado Automático de Objetos Alfaflexibles”, me es grato
comunicarle, que conforme a los lineamientos establecidos para la obtención del grado de Maestro
en Ciencias en este Centro, se le concede la autorización para que proceda con la impresión de su
tesis.
Y
DESARROLLO
TECNDLOGICO
CIINCIAS E U M P U I A C I D ~
C.C.P.
Lic. Olivia Maquinay Díaz, Jefe Depto. de Servicios Escolares.
INTERIOR INTERNADO PALMlRA S I N . COL. PALMlRA , A.P. 5-164. CP. 62490, CUERNAVACA, MOR. - M W C O
TEE. (777) 312 23 14.318 77 41. FAX (777) 312 24 34
EMAlL pozor@rdcenidel.com.mx
AI arquitecto del universo por permitirme estar compartiendo mi vida en este
mundo.
A ti madre (Benita Trujillo Miranda) por todos los cuidados y consejos que me das.
A ti esposa mía (Irma Gódínez Montaño) por todo el amor, comprensión, apoyo y
la dicha que hemos compartido juntos, por el regalo más grande que me distes, un
hijo (E. Uriel).
A mis hermanos (René e Isabel) por la comprensión que tengo por parte de ellos
¿Quién eres tu, oh hombre, que presumes de tu propia sabiduna?¿Por qué te jactas
de lo que has adquirido? El primer paso que conduce hacia la sabiduría consiste en
conocer que has nacido mortalmente ignorante, y si no quieres ser tenido por necio
según el juicio de los demás desecha la insensatez de ser sabio en tu propia
mortalidad.
Así como un sencillo atavío adorna mejor a una mujer hermosa, así una conducta
decente es el mayor adorno de la sabiduría interna.
Documentos del tihet.
Eduardo Orbe Trujillo
Al director de mi tesis Dr. Raúl Pinto Elías por toda la enseñanza que ha
dejado en mi.
A mi Codirector de tesis M.C. Andrea'Magadán Salazar por las materias que
nos impartió que son la base de mi tesis, por la ayuda y amistad que me
brindó junto con la paciencia que me tuvo en la revisión de mi tesis y por la
comprensión que nos tuvo en clase cuando bromeábamos.
Al Dr. José. L. Liñan Garcia,
Dr. Gerard0 Reyes Salgado
M.C. Matilde Velasco Soni
Por los conocimientos aportados para que esta tesis se pudiera concluir.
A toda la institución (director, administrativos, recursos humanos) que
intervinieron en mi estancia en esta institución.
A todos mis amigos que me brindaron su amistad
AI Consejo del Sistema Nacional de Educación Tecnológica (COSNET) por
brindarme la ayuda económica para realizar mis estudios en esta noble
Institución.
RESUMEN
El análisis de imágenes es un proceso que consiste en descubrir, describir, identificar y
comprender los patrones que son relevantes en las imágenes. Uno de los principales objetivos del
análisis de imágenes por computadora consiste en dotar a una computadora, en algún sentido, de
cierta función como la vista humana, de tal manera que sea una herramienta de apoyo a
especialistas y expertos en sus respectivas áreas.
Sin embargo, existe una gran cantidad de factores que limitan el proceso de análisis de tina
imagen, tales como la rotación de los objetos, la traslación, escala e iluminación de los mismos;
además, de los cambios que pueden sufrir algunos objetos que tienen la capacidad de
transformación, por lo cual el objeto puede ser distinto en su textura, tamaño, forma, etc. Y debido
a los cambios que puede presentar un objeto deformable o alfaflexible (objeto que puede cambiar
en cierto grado de rotación y traslación sin que se modifique totalmente). Esto dificulta aun más el
proceso de reconocimiento del objeto, ya que es más dificil establecer una descripción estándar del
objeto. Estos cambios también pueden ser debidos al medio ambiente que nos rodea, como las
vanaciones en la iluminación natural y con ello en cada cuadro parezca que se procesa una imagcn
distinta a la anterior.
El interés de la presente investigación es contribuir con una metodología para modelar cn
forma automática los objetos alfaflexibles en una secuencia de imágenes. En esta metodologia se
presentan en dos partes técnicas, una llamada snakes que actúa como una envolvente en el objcto
por cada cuadro del vídeo. Esta técnica registra los cambios de los rasgos del objeto que realiza cn
el movimiento, esto permite registrar la forma para la descripción de los objetos. También se
consideraron los cuatro colores que más se registra en el histograma por cada color respecto a RGB
(red,green,blue), se registra el área del objeto en cada cuadro, el centro de gravedad dcl snoke
respecto a x y y. La siguiente técnica permite el conocer la importancia de las variables anteriorcs,
llamada tesfores típicos que obtiene el conjunto mínimo de rasgos del objeto para podcr
identificarlo. Por último se calcula la longiiud de cada tesfor para determinar el orden de
importancia de los rasgos del objeto en orden decreciente. El resultado es el modelo del objeto.
I
TABLA DE CONTENIDO
Lista de figuras
Lista de tablas
Lista de ecuaciones
V
vii
...
Vlll
CAPITULO 1
INTRODUCCI~N
1.1 Antecedentes
2
I .2 Descripción del problema
5
1.3 Propuesta de solución
5
1.4 Metodología de solución
6
1.5 Objetivo
7
1.6 Alcances
7
1.7 Producto esperado
7
1.8 Disciplinas involucradas
8
1.9 Aplicaciones
8
1.10 Organización de la tesis
9
CAPITULO 2
ESTADO DEL ARTE
2.1 Estimación de movimiento de contornos en imágenes secuenciales
II
2.2 Plantillas deformables geométricamente, basadas en segmentación y seguimiento
en imágenes cardiacas
12
2.3 Parámetros libres para registrar en 2 pasos, imágenes elásticas con
puntos descritos y desplazamientos
I3
2.4 Snake pedals, modelos geométricos compactos y versatiles con control
basado en física
14
2.5 Snakes, formas, y flujo del vector gradiente
15
2.6 Un modelo de contorno activo para dibujar la corteza
i6
2.7 Contornos Activos y Modelos defomables
17
2.8 Modelo de Clasificación Supervisada Basado en Conjuntos de Representantes
17
2.9 Enfoque lógico combinatorio al reconocimiento de patrones
18
2.10 Filtro pasa alto
18
CAPITULO 3
SNAKES
3.1 Introducción
19
3.2 Preprocesamiento de snakes
20
3.2.1 Gradiente
3.3 Fundamentos de snakes
20
22
3.3.1 Fundamentos matemáticos
23
3.3.2 Pseudocódigo
29
3.4 Ejemplos del funcionamiento
20
3.5 Comentarios
33
CAPITULO 4
MODELADO
4.1 Selección de rasgos
35
4.2 Enfoque lógico combinatorio
36
4.3 Teoría de testores
38
4.3.1 Algoritmo BT
39
4.3.2 Importancia de los testores tipicos
46
4.4 Rasgos a modelar
47
4.4.1 Color por histograma
48
4.4.2 Centro de gravedad del snake relacionado con "x" y ')"
49
4.4.3 Área
49
4.4.4 Distancias entre todos los puntos de " x" y ')" del snake
49
...
111
4.5 Ejemplo del modelado de un objeto alfafiexible
49
4.6 Comentarios
53
CAPITULO 5
EXPERIMENTACI~N
5.1 Introducción
54
5.2 Casos de estudios realizados
55
5.3 Análisis de los resultados
65
CAPITULO 6
CONCLUSIONES
6.1 Introducción
66
6.2 Metas alcanzadas
67
6.3 Producto esperado
67
6.4 Aportaciones
68
6.5 Trabajos a futuro
68
REFERENCIAS
69
ANEXO A
12
iY
LISTA DE FIGURAS
Figura
Descripción
Página
Figura 1.1
Cambios que presenta la mano en los movimientos que realiza.
4
Figura 1.2
Esquema de solución de este trabajo.
6
Figura 3.1
Imagen de 24 bits, la cual es procesada a niveles de grises.
22
Figura 3.2
Resultado del proceso con filtro gradiente.
22
Figura 3.3
El snake adopta cualquier forma, como si fuera agua, basado en la
23
minimización de la energía:
Figura 3.4
Evolución de la energía externa usando snakes.
23
Figura 3.5
Se muestra la vecindad de los nodos.
26
Figura 3.6
Se muestran los diferentes resultados al cambiar los valores de aJ3,y.
30
Figura 3.8
Inicialización del snake.
31
Figura 3.9
Valores iniciales a) Alfa=lO Beta=l
b) Alfa=20, Beta = I
31
Figura 3.10 Imágenes donde a)l Inicialización del snake b) resultado del snake.
32
Figura 3.11 Resultado del snake con los siguientes valores A) a = l , p = l
32
B) a=I,p=2
C) a=1$=3.
Figura 3.12 Secuencias de imágenes utilizando la técnica del snake.
33
Figura 4.1
imagen con su respectivo histograma.
48
Figura 4.2
El snake se adecua a la forma del movimiento de los labios
SO
Figura 5.1
Se seleccionan los puntos alrededor de los párpados.
55
Figura 5.2
Lectura de los labios con ruido.
60
Figura 5.3
Modelado de labios sin mucho ruido.
62
Figura 5.4
Modelado de la cabeza en un ambiente natural.
64
Figura A.l
Imágenes del modelado del parpado del caso I .
73
Figura A.2
Modelado del objeto alfaflexible para el caso 2.
74
Figura A.3
Continuación del caso 2, Modelado del movimiento de los labios con un poco
75
:I
de mido.
Figura A.4
Modelado de los labios sin mido caso 3.
76
Figura
Descripción
Página
Figura A S Modelado del movimiento de la cabeza utilizando un ambiente natural, caso 4.
77
Figura A.6 Continuacion del caso 4, Modelado del movimiento de la cabeza utilizando u n
78
ambiente natural.
YI
LISTA DE TABLAS
Tablas
Descripción
Página
21
Tabla 3.1
Esta máscara obtiene las líneas verticales
Tabla 3.2
El cálculo de esta máscara permite obtener líneas horizontales.
Tabla 4.1
Representación de los rasgos y clases de los objetos.
3X
Tabla 4.2
Representa una clase con tres objetos.
40
Tabla 4.3
La siguiente clase con dos objetos.
41
Tabla 4.4
Resultado de la matriz de diferencia.
41
Tabla 4.5
Se muestra una fila básica, esta fila básicaes
Tabla 4.6
Resultado de la matriz básica.
44
Tabla 4.7
Testores típicos obtenidos del segundo caso.
51
Tabla 5.1
Distancias de los puntos que conforman el snakes alrededor del snake.
56
Tabla 5.2
Cuatro colores que mas aparecen del formato R.G.B que modela la herramienta.
57
Tabla 5.3
Matriz generada mediante las distancias de los puntos mas los rasgos de la tabla 57
,
S14.
22
42
5.1.
Tabla 5.4
Resultado de la matriz de Diferencia.
5x
Tabla 5.5
Resultado de la matriz Básica.
5X
Tabla 5.6
Testores típicos.
5X
Tabla 5.7
Testores típicos obtenidos del segundo caso.
61
Tabla 5.8
Testores típicos obtenidos del segundo caso.
63
!\
LISTA DE ECUACIONES
Figura
Descripción
Página
Ecuación 3.1
Gradiente en dirección de x .
21
Ecuación 3.2
Gradiente en dirección dey.
21
Ecuación 3.3
Cálculo del gradiente con su máscara en dirección de x
21
Ecuación 3.4
Cálculo del gradiente con su mascara en dirección d e y
21
Ecuación 3.5
Ecuación del snake por [Kass, 871.
23
Ecuación 3.6
Cálculo de la energía interna.
24
Ecuación 3.7
Ecuación del snake por [SHAH, 921.
25
Ecuación 3.8
Ecuación de la energía funcional del snake.
26
Ecuación 3.9
Cálculo de la ecuación de la distancia media de los puntos del snake menos
21
I!
los puntos vecinos.
Ecuación 3.10 Cálculo de distancia media de los puntos del snake.
21
Ecuación 3.11 Normalización de la ecuación (3.9).
27
ij
Ecuación 3.12 Cálculo de energía curva.
21
Ecuación 3.13 Normalización de la ecuación (3.12).
28
Ecuación 3.14 Obtención de la energía minima y máxima de la imagen del gradiente.
28
Ecuación 3.15 Normalización de las magnitudes del gradiente
28
Ecuación 3.16 Ecuación de la curvatura del objeto.
28
Ecuación 4.1
Obtención del peso informacional.
46
Ecuación 4.2
Obtención de la longitud del testor típico.
41
\ill
CAP~TULO1
Desde siempre el hombre ha tratado de inventar mecanismos, adaptándolos
inconscientemente a la estructura de su propia constitución, no existe aparato ni ingeniosa
resoluc¡ón.de problemas mecánicos que no este solucionado en nosotros, especialmente en
aquellas actividades repetitivas Ó dificiles de realizar y que ponen en peligro la vida del ser
humano, debido a que estas requieren una gran precisión manual como intelectual. El ser
humano ha soñado con inventar máquinas que realicen artificialmente tareas afines a él,
esto no supone que no pueda realizar estas actividades, de lo anterior surge una área de la
inteligencia artificial llamada visión por computadora, que realiza las funciones de la vista
humana, esta área observa escenas para procesarlas en una computadora.
De acuerdo con [Maravall, 941 se considera que las tres cuartas partcs de
información que maneja el ser humano es adquirida por imágenes visuales. La Visión por
Computadora es un área que investiga los diferentes procesos naturales del ser humano
relacionados con la vista humana, utilizando un dispositivo que digitalice tal como una
cámara de fotografia o vídeoly una computadora para ver e interpretar dichas imágenes. La
Visión por Computadora es una área de la inteligencia artificial que tiene como una de sus
metas solucionar los problemas relacionados con
la "percepción e interpretación" de
escenas, objetivo excepcionalmente ambicioso y complejo, que aún se encuentra en una
etapa muy primitiva [Maravall, 941.
Es posible hacer una analogía entre un sistema artificial de procesamiento de
imágenes y el sistema visual humano. Por ejemplo, en el humano el proceso de
“percepción” es realizado por el ojo y el de “interpretación” por el cerebro humano. En el
sistema artificial, la adquisición de imágenes es realizada por medio de una cámara digital y
la interpretación es procesada por una computadora [Maraval 941. En la actualidad el
proceso de digitalizar las imágenes es factibie, pero el proceso de interpretación es muy
pobre debido a los pocos avances de la neurociencia relacionada con la función del cerebro
humano. Una de las principales actividades para tener una “interpretación” es contar con
A
una adecuada interpretación, de los rasgos que integran a los objetos de las imágenes
digitales.
1.1 ANTECEDENTES
Desde que el hombre logra capturar las imágenes en una cámara fotográfica surge
un gran interés por mejorarl’y conservar las imágenes con mejor calidad. Debido a esto
surge el tratamiento de imágenes. Los problemas iniciales se presentan en 1920 cuando un
equipo especializado codificaba las imágenes para trasmitirlas por cable y estas eran
reconstruidas en el extremo de la recepción. A partir de los sesentas se pone de manifiesto
el potencial de los conceptos de tratamiento de imágenes debido al avance tecnológico a
través de las computadoras y las naves espaciales que permitieron enviar imágenes de la
luna, algunas de estas imágenes requerían de un proceso digital [González, 19961.
En la actualidad hay una gran necesidad de procesar las imágenes para resolver
problemas en diversidad de áreas, como por ejemplo en imágenes enviadas por los satélites
artificiales, en medicina, en biología, en aplicaciones industriales, etc.
La evolución continúa en el campo de las técnicas de tratamiento de imágenes,
surgiendo un segundo campo de aplicación de éstas que consiste en resolver problemas
relacionados con la percepción automatizada, la cual se centra en procedimientos que
extraen información de la imagen mediante un proceso realizado por una computadora para
poder interpretarla. Este proceso tiene poco en común con respecto a la fomia en cómo lo
realiza el ser humano. Sus aplicaciones, entre otras, son el reconocimiento de caracteres, la
visión por computadora para el control automático de calidad, reconocimiento de huellas
2
dactilares y del iris, predicciones del tiempo a través de las imágenes enviadas por los
satélites [González, 961.
Como ya se mencionó, básicamente el objetivo de la visión por computadora es
automatizar las funciones de inspección visual realizadas por el hombre [Faúndez, 200 I].
Para llevarse a cabo tal proceso, una actividad muy importante es realizar una correcta
descripción de los objetos de trabajo, es decir, obtener ciertos rasgos que permitan modelar
los objetos. De acuerdo a las iaracterísticas que presentan los objetos, es posible agruparlos
en tres clases
a) Objetos rigidos:
Son aquellos que presentan las mismas características durante su movimiento o
desplazamiento, siempre muestran las mismas relaciones geométricas. Por ejemplo
un lápiz, una mesa, un libro, etc.
b) Objetos articulados:
Presentan algunos cambios, pero que sin embargo, estos cambios son totalmente
conocidos o predecibles. Ejemplo de este tipo de objetos lo son las tijeras, las pinzas
eléctricas, el brazo de un robot, etc.
c) Objetos aifiafiexibles:
Este tipo de objetos presentan una gran capacidad de transformación generando una
gran cantidad de instancias del objeto que lo describen de manera distinta en cada
Intervalo de tiempo, debido a lo antenor se vuelve mas complicado obtener una
descripción única. Ejemplo de este tipo de objetos lo son la boca y mano del ser
I,
humano, una lombriz, etc.
Además del tipo de objeto a procesar existen una gran cantidad de factores que
dificultan el proceso de análisis de una imagen, tales como la rotación de los objetos, la
traslación de los mismos y la escala e iluminación. Ya que no se sabe todos los posibles
cambios o deformaciones que puede presentar dicho objeto, sobre todo cuando los cambios
suelen ser variados e impredecibles (pueden ser provocados por el medio ambiente como
respuesta a la traslación, rotación, deformaciones, movimientos rápidos etc.) por naturaleza.
3
Debido a lo anterior, se combinan todos los factores mencionados y el proceso de
descripción de los objetos' alfaf2exibies suele convertirse en un problema de mayor
complejidad.
Como ya se mencionó, la mano de una persona puede considerarse como un objeto
alfqflexibíe ya que ai sufnr cambios en su forma, por los movimientos que realiza, genera
un conjunto de patrones diferentes, dificultando en gran manera establecer el conjunto de
rasgos o caractensticas que permita identificarla en el proceso de reconocimiento de una
imagen o en una secuencia de imágenes, ver figura I . 1.
Figura 1.1 Cambios que sufre la mano en los movimientos que realiza
Para tener un sistema de modelado eficiente es necesario contar con una buena
descripción de los objetos que se están trabajando. Generalmente esta caracterización se
realiza de manera empírica, el experto decide el conjunto de características a utilizar o que
van a integrar la descripción del objeto. Esta manera de obtener la descripción, puede
resultar complicada al tener variables o características no significativas o que .proporcionen
redundancia de información ::en la representación, y con ello el tiempo necesario para
obtener los datos de la descripción puede requerir mucho tiempo de cómputo.
4
1.2 DESCRIPCI~NDEL PROBLEMA
Actualmente, el registro y caracterización de los cambios que puede realizar o sufrir
un objeto deformable se lleva a cabo de manera manual, dando como resultado un proceso
bastante difícil de realizar y en muchos casos con muchos errores. Esto es debido a que el
ojo humano se cansa demasiado rápido, por lo que la vista disminuye la capacidad de
observar a detalle, y algunas veces existe distorsión o perdida de información del objeto
observado. Si se agrega que existe gran cantidad de escenas para extraer los rasgos o
caracteristicas del objeto a analizar, resulta una labor demasiado pesada para el ser humano.
El interés de la presente. investigación es contribuir con una metodología para
generar u obtener de manera automática una descripción o caracterización del objeto
deseado, al registrar los cambios que presenta durante el movimiento del mismo en cada
imagen de la secuencia, como su tamaño, color, área, centro de gravedad. El resultado de
esta información se le aplicará un algoritmo de selección de variables, que elimina la
redundancia de información de las variables del objeto dando como resultado el conjunto
de variables que mejor describan al objeto que se esta modelando.
1.3 PROPUESTA DE S O L U C I ~ N
Como ya se mencionó, esta tesis pretende diseñar e implementar una herramienta
que permita generar de manera automática el mínimo de información de las variables que
conforman la descripción de un objeto alfqflexible.
Pasos a seguir:
¡.-Se establece en la primera imagen digital de la secuencia de imágenes, el obJeto
u objetos que se desean modelar. La imagen es tratada con algún filtro con el
propósito de eliminar el posible ruido
2.- En la segunda fase, es segmentar la imagen para localizar a detalle el objeto que
se desea modelar, por lo cual se utiliza la técnica llamada snakes [kass, 881
5
3. Se localizan, registran y cuantifican, aquellos rasgos considerados en el modelo
que describirá al objeto por medio de un conjunto inicial de características posibles,
de tal forma que se tendrán los mismos descriptores del objeto que se analiza pero
con valores diferentes. Toda esta información será almacenada en una base de
conocimientos que integrará el modelo inicial del objeto y por medio de un
algoritmo de selección de variables como testores típicos [Shulcloper, 991, se
obtienen las mejores variables que representan al objeto.
1.4 METODOLOG~ADE S O L U C I ~ N
Estos pasos se muestran de manera gráfica en la figura 1.2.
a
Carga el video en formato AVI.
a
Selecciona el objeto o los objetos a modelar.
.
.
.
a
a
a
Procesa la imagen de cada cuadro(resu1tado del snake)
Obtiene los rasgos del objeto.
Almacena los rasgos en archivos de texto.
Aplica un algoritmo de selección de variables.
Obtiene el orden de importancia de los rasgos.
Obtención del modelo del objeto.
Carga el video con formato :vi
+I
Selecciona los objetos a modelar
Procesamiento d e cada cuadro del
MODELO DEL OBJETO
Obtiene los rasgos del objeto a
,
Almacena 10s rasgos del objeto en
archivo dc texto
Obtiene el minim, de rasgos, que
mejor describan al objeto
Orden de importancia de los rasgos
en orden ascendente
FiQura 1.2 Esquema de solución.
1.5 OBJETIVO
Desarrollar una herramienta que permita:
Realizar la localización automática de los parámetros
Registrar las variaciones del objeto por cada cuadro en una secuencia de
imágenes
Procesar y analizar la información de cada cuadro y cada parámetro
mediante testores típicos.
Generar modelos primarios de objetos.
1.6 ALCANCES
Se manejarán secuencias de imágenes’ de 24 bits con archivos AVI, con un
tamaño de 250x250 en formato RGB.
0
Se usará un conjunto técnicas que contemplen las características de extracción
de los rasgos.
0
La información que se genera de la extracción de características y de la
deformación del objeto se almacenará en una base conocimientos.
La información en bruto obtenida de los. cambios en los rasgos del objeto
alfqflexible se procesará por medio de un algoritmo de selección de variables
llamado testores típicos para obtener el conjunto mínimo de rasgos
Ó
características que permitan modelar el objeto para el reconocimiento de
patrones.
o
La herramienta será capaz de mostrar al usuario la importancia de los rasgos.
en orden descendente.
La herramienta permitirá modelar hasta 50 objetos como máximo.
1.7 PRODUCTO ESPERADO
o
Una herramienta, que de manera automática obtenga el modelo de un objeto
alJ¿¿jlexible.
1
A
Información primaria del objeto obtenida por los cambios del objeto alfayexxible
por medio de un algoritmo como testores típicos para obtener los parámetros o
características que permitan modelar e l objeto.
1.8 DISCIPLINAS INVOLUCRADAS
Las disciplinas involucradas ,son las siguientes:
1) Procesamiento de imágenes, los cuales se utilizarán los siguientes métodos.
I . 1 Procesamiento de las imágenes a niveles de gns.
1.2 Cálculo del área del objeto.
1.3 Centro de gravedad del snake con respecto a 'k"y "y".
1.4 Histograma.
1.5 Segmentación utilizando snakes.
1.6 Base de conocimientos.
2) Lógica combinatoria para el reconocimiento de patrones, utilizando los siguientes
tópicos.
2.1 Testores tipicos.
2.2 Orden de importancia de los testores típicos.
1.9 APLICACIONES
El contar con una herramienta que realice y proporcione de manera automática una
buena descripción o modelado de objetos es una necesidad actual como se puede observar
en las siguientes aplicaciones:
a) Crecimiento de cepas de bacterias o microbios:
La herramienta es capaz he modelar e l crecimiento, de cepas de microbios al utilizar la
técnica de los snakes ya que permite adecuarse al contorno de la cepa que se desea modelar
o investigar.
8
b)
Seguridad:
El análisis de las deformaciones que presenta el cuerpo humano al caminar, se
puede analizar para estudiar los movimientos de las personas sospechosas o que portan
armas. La herramienta registra la forma de movimientos sospechosos, con esto se genera
información que permite registrar y modelar los rasgos que más cambian en el movimiento
de las personas con arma. Esta información puede ser utilizado en los aeropuertos, centros
públicos, supermercados, bancos.
c) Diseño de prótesis que contemple las deformaciones del cuerpo humano:
La herramienta permite obtener información de las partes en donde el cuerpo
necesita más libertad de movimiento, así como las partes en las cual carece de movimientos
flexibles. Estudios de esta info&ación
pewite crear prótesis que contemple las
deformaciones del cuerpo humano, evitando que la prótesis se vuelva una molestia para el
cuerpo humano.
d) Conjunto mínimo de rasgos para el reconocimiento de objetos:
La herramienta al realizar de forma automática el modelado de los objetos, registra
los cambios o deformaciones que presenta el objeto bajo estudio en la secuencia de video.
Esta información
es redundante o repetitiva,~alaplicar un algoritmo de selección de
variables a toda esta información, se elimina la redundancia de información y el uso de
variables poco discriminantes. Este algoritmo permite encontrar el conjunto mínimo de
rasgos que es posible utilizar en la descripción o representación del objeto que se estudia,
siendo esta representación la base para el reconocimiento del objeto que se modeló en la
secuencia de cuadros del vídeo.
1.10 ORGANIZACI~ND E LA TESIS
El presente trabajo está organizado de la siguiente manera. En el capítulo 2 se
presenta el estado del arte. ,En este capitulo se describen técnicas relacionadas coil la
segmentación y localización de objetos deformables, la obtención de los rasgos, la
estimación de movimiento, el uso de plantillas deformables, y el registro de parámetros en
dos pasos.
9
En el capítulo 3 presenta la técnica de procesamiento para disminuir el ruido en la
imagen; además, este capítulo explica el funcionamiento de los snakes y su fundamento
matemático.
En el capítulo 4 se explica la teoría de selección de variables mejor conocido como
testores típicos. Esta técnica permite obtener los rasgos más importantes del objeto que se
está modelando, estos rasgos permiten en un trabajo posterior, el reconocimiento del objeto
que se ha modelado.
En el capítulo 5 muestra las pruebas realizadas en la fase de experimentación de la
metodología que corresponde a este trabajo.
En el capítulo 6 se presentan las conclusiones generales relacionadas con esta
investigación, así como las aportaciones del trabajo en el área de visión por computadora.
Finalizando con propuestas de trabajos futuros que complementarían la herramienta de
modelado.
IO
~APÍTULO2
1
ESTA1 O DEL ARTE
En este capítulo se realiza un breve análisis de algunos artículos, cuyas
investigaciones describen problemas con objetos deformables, se describen las técnicas que
se utilizan para obtener las caractensticas de los objetos que se deforman en un intervalo de
tiempo, buscando obtener el modelo de los mismos.
contorno tiene un punto correspondiente en el contorno para la siguiente toma.
En esta técnica se incluyen métodos numéricos donde la ecuación es discreta, se
curvatura del contorno que permite localizar los correspondientes puntos en el contomo de
la siguiente imagen.
I
El cálculo de la curvatura en el contorno se realiza a través del punto vecino
más
próximo, se usan dos puntos adyacentes y el punto mismo. Cuando se calcula e
óptico de los puntos del contorno con la primera derivada se obtiene una imagen
,.
.. ...
'I.!
I
1
En esta técnica se incluyen métodos numéricos donde la ecuación es discreta, se
la siguiente imagen.
I
2.2 Plantillas deformables geométricamente, basadas en segmentación y seguimiento
en imágenes cardiacas [Rueckert, 961
Propone el uso de una minimización de energía, la cual puede utilizarse en los
objetos deformables bajo la influencia de la dirección de la imagen. La degradación de la
forma de la plantilla es medida por una función de las dos formas en 2D.
cristalino el cual minimiza su energía. Usando esta analogía, el algoritmo genera
aleatoriamente nuevas configuraciones de la probabilidad de distribución o de deformación.
Relajación deierminisiica. Para seguir un objeto en una secuencia de imágenes
12
comparan objetos con formas conocidas de 2,tipos de plantillas deformables que pueden ser
caracterizados, las plantillas deformables rígidas como escalación, rotación y traslación.
Plantillas deformables no rígidas como el
I
humano, se basa en contornos activos,
se realizaron pruebas en segmentación
utilizando la distribución de Fourier. En
y tracking de superficies relacionadas al
Este trabajo permite
para compararla con
la siguiente imagen, y así obtener cuántos
se ha desplazado o qué dirección está
tomando. También propone segmentar
se deforman mediante la minimización
de energía que se usa en los snakes.
2.3
Parámetros libres para
imágenes elásticas con puntos
descritos y desplazamientos [Peckar, 961
con puntos descritos. Este
Se plantea registrar en 2
método está basado en la teoría de elasticidad1
En el primer paso se
to de correspondencia de algunos límites en
ambas imágenes, usando un contorno
mejor conocido como snakes, que se puede
aplicar a numerosos problemas en
omputadora, detección de arcos, seguimiento
de objetos. Se resuelve la
aproximaciones,
constantes.
el snake, en forma iterativa, realizando
I.
y usando parámetros
Segundo paso, se deforma en forma elástica la plantilla de la imagen usando los
valores de los snarels descritos anteriormente de desplazamiento en los limites de la
estructura obtenidos en el primer paso en a ición a las condiciones de la imagen en su
frontera.
En contraste con los métodos tradi ionales, este planteamiento no depende de
parámetros de la deformación del modelo c
exacta concordancia de las estructuras de la
constantes elásticas lo cual garantiza la
utilizando snakes.
13
Este trabajo permite obtener los primeros puntos en la imagen, que corresponden a
los rasgos del objeto que se van modelar en forma automática, y permite la deformación del
objeto utilizando la técnica de snakes.
2.4 Snake pedals, modelos geométricos compactos y versátiles con control basado en
física [Vemuri, 2000]
En este trabajo se propone un modelo geométrico de formas, el cual permite la
representación de formas globales con detalles locales usando relativamente pocos
parámetros comparado con los modelos híbndos. Esto consiste en representar formas de
curvas pedales. La curva pedal es una curva regular (se utilizan dos variables en dos
dimensiones) con respecto a un punto fijo (pedal). Una curva pedal es capaz de sufrir
deformaciones locales y globales, esta puede ser determinada por parámetros en forma de
vector, por lo cual es un modelo geométrico que se obtiene por medio de la técnica llamada
snakes, utilizada en deformaciones locales geométricas. Una vez que se obtiene el snake, se
forma la curva pedal. Los parámetros globales de estimación se calculan por medio del
descenso del gradiente.
Los parámetros locales de estimación son resueltos por medio de sistemas lineales
en forma de matriz. Se aplica en imágenes de 256x 256 y el tiempo de cálculo es de 258 a
191 segundos en una SGI (Silicon Graphics International). Este modelo sólo funciona con
pocos parámetros.
Las curvas se presentan muy a menudo en los objetos que sufren deformaciones. por
ejemplo los objetos alfqfIexibles y puede ser obtenida a través de los snakes utilizando la
forma x,y en la representación de los puntos de los snuxels que es parecido a los puntos
que representan los rasgos en el presente trabajo
14
2.5 Snakes, formas y flujo del vector gradiente [Xu, 981
Este trabajo presenta una nueva fuerza externa para contornos activos resolviendo
los problemas de fuerza extendida, el cual se llama flujo del vector gradiente. Este es
calculando los vectores de gradiente en niveles de gris o un mapa binario derivado de la
imagen. Difiere fundamentalmente de los tradicionales snakes en que no pueden ser
calculados como un gradiente negativo. Este snake es formulado como una fuerza
balanceada.
Para que se pueda solucionar por este método, el objeto debe de ser cerrado es decir
no debe de estar incompleto en sus bordes, los snakes anteriores tienen problemas en las
concavidades de la imagen, por lo que éste método soluciona los problemas anteriores.
Primero se define un borde de la imagen por lo cual debe de estar en niveles de gris, una
vez hecho lo anterior se obtiene el gradiente que minimiza la energía, donde el gradiente es
el operador Laplaciano. También puede resolverse por métodos numéricos.
Los snakes o contornos activos, son curvas definidas dentro del dominio de la
imagen el cual puede moverse bajo la influencia de fuerzas extemas de la curva misma, y
fuerzas externas calculadas de los datos de la imagen. Hay dos tipos de contomos activos
los paramétricos y los contornos activos geométricos, este documento se enfoca a los
contornos paramétricos. Típicamente las curvas son dibujadas hacia los arcos por fuerzas
potenciales las cuales son definidas como un gradiente negativo, esto hace una fuerza de
presión que comprime las fueizas externas.
Se ha introducido un nuevo modelo de fuerzas externas para superficies
deformables el cual es llamado el flujo del vector gradiente. Este es calculado como vector
gradiente utilizando niveles de gris en la imagen a ser calculada para encontrar
concavidades. Soluciona el problema de la concavidad, a través de la captura de la fuerza
externa del snake.
Los snakes son utilizados en aplicaciones de procesamiento de imágenes
particularmente por adecuarse a la forma del objeto. Los snakes o contornos activos, son
usados ampliamente en visión por computadora para localizar fronteras, problemas
asociados con inicialización y pobre convergencia a las concavidades de fronteras.
Este trabajo sirve como referencia para resolver las concavidades que presenta un
objeto que se deforma, y que está en niveles de gris debido a que cada cuadro de la imagen
es tratada de la misma forma, es decir en niveles de gris.
2.6 Un modelo de contorno activo para dibujar la corteza [Davatzikos, 971
Un nuevo modelo para encontrar y dibujar la corteza de un cerebro. Utiliza el
método de los snakes (contornos activos), mediante la especificación de fuerzas externas
actuando como un contorno activo. Este determina la localización de la superficie del
cerebro que es el primer paso para la visualización del cerebro. Esta técnica esta basada en
contornos activos y sirve para modelar la curva inicial como un objeto físico el cual es
llamado contorno activo, y los datos como fuerza externa, un procedimiento iterativo para
que el contorno activo se mueva hacia los datos que conforman al objeto.
Un contorno activo es caracterizado por tres partes:
1.- Un modelo de fuerzas internas. El cual describe un contorno activo como un
objeto.
2.-Un modelo de fuerzas externas. El cual describe, como el contorno activo es
atraído a los puntos previamente señalados.
3.- Un procedimiento iterativo. El cual intenta encontrar la configuración que mejor
concuerde con la fuerza interna y externa.
Los contornos activos son utilizados por medio de la formulación usando el cálculo
de variación para encontrar las variaciones de la ecuación de Euler. Ecuaciones que
representan su equilibrio de fuerzas balanceadas que permiten una mejor definición de la
forma del objeto.
Esta técnica permite obtener la forma del objeto a través de la energía externa que
son los puntos del objeto a modelar.
2.7 Contornos Activos y Modelos deformables [Young, 951
El problema de obtener contornos de formas complejas es dificil, por io que existe
un método de solución, que consiste en definir la estructura de un contorno activo o snake,
mediante la elasticidad de la energía. La energía se detiene en el borde del gradiente de la
imagen, mediante la combinación de las energías internas y externas, la combinación de
energías permite obtener snakes iterativos y snakes flexibles, este método obtiene contomos
de imágenes en movimiento.
El trabajo se desarrolla sobre formas complejas que están en movimiento, utilizando
snakes para obtener las formas de los contornos de los objetos que se están moviendo.
Sirve de referencia para los contornos de la secuencia del objeto a modelar en cada cuadro.
2.8 Modelo de Clasificación Supervisada Basado en Conjuntos de Representantes
[Ariel, 981.
Para clasificar un objeto normalmente existe información que utiliza un algoritmo
de clasificación supervisada que permite trabajar con clases difusas y disjuntas, con la
información mezclada sobre los objetos, con criterios de analogías no booleanos y
descripciones incompletas de los objetos. Este modelo produce sus decisiones teniendo en
cuenta factores a favor y en contra, evaluando las descripciones parciales de los objetos en
estudio. Se dan procedimientos para la determinación de todos los parámetros.
Conclusión: Lo anterior permite utilizarlo en los rasgos del objeto que se está
modelando, ya que el algoritmo de snakes podría perder información, debido a los
problemas de una inadecuada iluminación.
17
2.9 Enfoque .lógico combinatorio al reconocimiento de patrones [Shulcloper, 991
Se propone un algoritmo de selección de variables conocido como BT (Bottom
Top), el cual se basa en los conceptos de testor y testor típico. Un testor es un conjunto de
rasgos que permite diferenciar los objetos entre dos clases, porque ningún objeto de la
primer clase (mirados a través de los valores de sus rasgos) se confunde con los objetos
pertenecientes a la segunda clase. Y un testor típico es la combinación mínima de rasgos
que caracterizan una clase de objetos, diferenciándola de las demás clases. Este algoritmo
permitirá discriminar entre la información que forma el modelo inicial de objetos
aiJ¿¿Jexibles,en la base de conocimientos.
Conclusión: Esta técnica se utiliza para obtener los mejores rasgos del objeto que
selecciona el usuario al inicio de la secuencia de la imagen, donde el objeto se deforma, la
información es almacenada en un archivo de texto. Esta información se refiere a los rasgos
que se obtienen.
2.10 Filtro pasa alto [González, 961
Filtro pasa alto se emplea, para que la imagen aparezca con los bordes mas
sobresalientes, para reducir el ruido, es útil que la imagen suavice las bajas frecuencias en
algunas etapas de preprocesado, como la eliminación de los pequeños detalles de una
imagen antes de la extracción de un objeto y el relleno de pequeños espacios entre líneas o
curvas.
Conclusión: Esta técnica obtiene un preprocesamiento para obtener esos bordes que
más sobresalen en cada cuadro y permite al snake utilizar la minimización de la energia
para que se adhiera a la forma final que el objeto presenta en cada deformación.
CAPÍTULO 3
SNAKES
3.1 INTRODUCCI~N
Se considera como modelado, al procesa que trata de identificar'el conjunto de
rasgos o Características que mejor describen al objeto u objetos con los que se van a
trabajar.
Los pasos necesarios para realizar u obtener el modelado de un objeto, son los
siguientes:
..
~
1) Segmentar la imagen, que consiste en particionar los objetos que componen la
imagen. Lo anterior produce información en términos de regiones de píxeles,
como el contorno de objeto o la región en donde se encuentra el objeto.
2) El siguiente paso es describir o representar el objeto a través de un conjunto
inicial de características que pueden no ser las adecuadas o conteneiinformación redundante. Estas variables se almacenan en un archivo de tipo
texto para una mayor compatibilidad con herramientas, como ID3 y C4.5.
3) A esta información se le aplica un algoritmo de selección de variables para
obtener el modelo del objeto.
4) Mostrar que variables son las más importantes en orden decreciente.
La segmentación es uno de los procesos fundamentales para el éxito del modelado
del objeto. Sin embargo también es una de las etapas con mayor complejidad en todo
sistema de visión artificial especialmente si se realiza una segmentación con mucho detalle.
i
I
Además de lo anterior, la segmentación en sí misma tiene problemas que influyen
en sus resultados como la iluminación no controlada que produce bordes falsos o
incompletos lo que dificulta la extracción de los rasgos en forma exacta.
II
Si este proceso de segrnentacion se realiza de forma manual, se pueden producir
'!
demasiados errores en la extracción de rasgos, ya que la vista humana se cansa fácilmente,
I
además de que dicha operación debe realizar 30 cuadros por segundo. Por ello en esta
I
investigación se realizó un análisis dellas diferentes técnicas de segmentación encontradas
buscando una técnica que no tuviera problemas con las variaciones de tamaño, traslación y
rotación de los objetos, para poder registrar los parámetros establecidos por el experto. La
técnica que se propone para segmentar y modelar Ips objetos son los snakes.
3.2 PREPOCESAMIENTO DE SNAKES
Una de las técnicas para realizar el proceso de generación automática del modelo de
objetos alfqflexibles, es la utilización de contornos activos. Los contornos activos o snakes
fueron inicialmente propuestos por [Kass, 871, estos contornos son una herramienta que
considera la minimización de energía de un contorno, basándose principalmente en fuerzas
aplicadas. Sin embargo, la primera fase'de los snakes requiere preprocesar la imagen con la
técnica del gradiente para particionar los bordes más sobresalientes.
3.2.1 Cradiente
La detección de bordes con el filtro gradienie, de acuerdo con [Maravall, 941 es
'
esencialmente una operación de detección de cambios de intensidades locales significativos
de acuerdo con un umbral establecido.
,
Este operador tiene como objetivo determinar bordes con independencia de su
dirección en la imagen. Es obvio que esta propiedad es deseable entre los detectores de
bordes ya que no sería bueno que un detector sólo fuera sensible a bordes en determinadas
I .
direcciones, Este tipo de detectores es aplicado a cada punto de la imagen para calcular el
I.
borde independientemente de su orientación.
i
20
Para una imagen digital, con un rango de O I x 5 N-1, O I y5 M-1, (donde N es el
tamaño m k i m o de renglones y M el número máximo de columnas de la imagen) definida
por los valores de luminosidad de sus píxeles de la imagen I(x,y), la ecuación del gradiente
no es posible aplicarla al pie de la letra, ya que la imagen digital que se procesa no tiene
variables independientes, ya que estas son discretas, debido a esto se propone una
aproximación discreta ver ecuación (3.1) y ecuación (3.2).
Ejemplo:
Siendo por lo tanto:
El rango O 5 x I N-I; O I y I M-1 de la imagen, se puede procesar en una computadora
mi
utilizando una matriz de 3x3, los valores de las máscaras para h l y h2 se muestran en la
tabla 3.1 y 3.2.
Tabla 3.1. La mascara h l genera resultados, que son direcciones verticales de la imagen
”“ I
CENIDET
IENl’RO DE INFORMACION
21
Tabla 3.2. La máscara muestra como resultado las direcciones hormntales de la imagen.
O
O
O
Un ejemplo de aplicar dichas máscaras (hl y h2) de acuerdo con las ecuaciones
(3.3) y (3.4), en la imagen en niveles de gns, que se muestra en la figura 3.1, da como
resultado la imagen de la figura 3.2.
Figura 3.1 Imagen de 24 bits.
Figura 3.2. imagen procesada con filtro gradiente.
3.3 FUNDAMENTOS DE SNAKES
De acuerdo con [Kass, 871 los snakes son modelos de contornos activos, los cuales
presentan curvas dinámicas llamadas spline (las curvas splines se refieren a polinomios).
Las curvas spline tienen aplicación en visión por computadora, para propósitos generales de
curvas cuando el objeto no es simple o sufre deformaciones.
El snake es guiado por dos energías, la interna y la externa, la cual puede ser
obtenida por las características de la imagen. La energía interna está basada en la
continuidad y su curvatura. Un snake se basa en un modelo matemático que trata de
preservar el mínimo de energía ver figura 3.3.
22
n
,,--Inicia
del snake
Punto mínima dc
Figura 3.3 Por analogía el snake adopta cualquier forma, como si fuera agua, que se adapta a la
forma del recipiente
La energía externa se obtiene gracias a los atributos del objeto de interés como
líneas y contornos, ver figura 3.4, el resultado de cada iteración que se obtienen a través del
'
cálculo del snake se obtienen valores pequeños donde el snake trata de fluir en esa
localización. Para que la energía adopte la forma del objeto que se desea modelar, para
mejores resultados los bordes deben ser más notorios, esto se logra con la aplicación del
gradiente.
Figura 3.4 Evolución de la energia exferna usando snokes.
3.3.1 Fundamentos Matemáticos
La integral de la energía del snake puede ser escrita como
(3.5)
23
donde:
v(s)
=
(x(s), y(s)), E¡,, representa la energía interna del spline relacionado con
las curvas.
Eimageda origen a las fuerzas de la imagen
E,,,, da origen a las restricciones de las fuerzas y se tiene que:
donde:
Vs
V,,
es la primera derivada
es la segunda derivada
Williams Shah [Shah, 921 menciona que el algoritmo original presentado por kass
[Kass, 871 tiene los siguientes problemas:
I . Las fuerzas de la imagen y restricciones necesitan ser distinguidas en orden para
garantizar la convergencia, de esta manera no es posible la distancia minima
entre los puntos.
2. El método es numéricamente inestable.
3. La primera derivada en términos de la ecuación (3.6) fue aproximada por una
' 1
diferencia finita, (v,? = (xi - xi-1)
+ (yi - ~
1
i -, ~
Esto
)
es equivalente a minimizar
la distancia entre los puntos y tiene el efecto de causar que el contorno se
contraiga.
4. Ninguna directriz fue dada por el método original para determinar los valores dc
ay
Este método utiliza el mismo valor para a y p e n cada punto, y no existe
discusión o ejemplos para explicar como cambiar esos valores que afectan al
contorno, sucede que los valores son críticos y deben de ser escogidos
cuidadosamente para obtener resultados satisfactorios.
5 . Si p e s constante, el snake no envolverá las esquinas en forma adecuada.
. .
24
Amini, Tehran¡ y Weymouth [Arnini 901 proponen un algoritmo dinámico de
programación que resuelve el problema de las ecuaciones (3.5) y (3.6) ya que el algoritmo
de kass [Kass, 871 requiere un consumo muy grande de memoria el tiempo es de O(i7rn’)
(donde n es el número de puntos y m es el número de localizaciones posibles en las cuales
un punto puede moverse en una simple iteración), lo cual es muy lento.
AI notar que los snakes de kass presentan varios problemas, se decidió utilizar en este
trabajo la nueva mejora hecha por [Shah, 921. Este algoritmo es muy versátil para un
modelo de contornos activos el cual se ejecuta en un tiempo O(nm)
Este trabajo presenta las mejoras del algontmq de kass que son resueltas por [Shah 921.
El uso de rejillas para posiciones de puntos y la estabilidad en la programación dinámica,
son conservados en este método. En adición, los valores escogidos para a y D
, , son
fácilmente determinados para balancear las fuerzas relativas en los términos de la
reformulación de primer orden. El término de continuidad causa que los puntos sean
espaciados en el contorno, removiendo la característica anterior de que el contorno se
encoja y haciendo que este término de continuidad de segundo orden sea más exacto. La
irnplementación es más eficiente en tiempo y requerimiento de espacio en memoria.
El algoritmo propuesto por [Shah 921 minimiza lo siguiente:
I
E = /(a(s)Econt +,B(s)Ecuwc
+ y(s)E,m.pe)ds
O
(3.7)
El primero y segundo término corresponden a E¡., en la ecuación (3.5). El último
término mide alguna cantidad de la imagen como los contornos fuertes o intensidad y es el
mismo que ocupa la posición.media de la ecuación (3.5). Observe que no hay términos para
restricciones externas. Los parametros (a,,B y y) ‘son usados para balancear la influencia
relativa de los tres términos. Este algoritmo es iterativo y en cada iteración, un punto vecino
’
[arepresenta a rigidez del objeto a modelar, 3
/ representa la curva o cuadraturd cuando es cero, del objcto a
modelar, y representa la flexibilidad del objeto a modelar]
.
.
2s
de cada punto es examinado; y el punto vecino con la energía mínima es escogido como la
nueva localización de ese punto, todo esto es dividido por el módulo de n(donde n es el
numero máximo de vectores del snake).
Los valores para cada término de la ecuación (3.7) se obtienen de la siguiente manera:
1) Para determinar la aproximación más adecuada para el primer término en la
1
ecuación, se considera la diferencia .del promedio de las distancias entre los
puntos y la distancia de los dos puntos bajo consideración. ver figura 3.5.
2) Para el segundo término en la ecuación (el cual es una curva), 'nótese que la
formulación del término de continuidad causa que los puntos sean espaciados,
iíjí r(ue
lusri' di HM iii?iii~'rl!
fiiimación de la cuma multiP Por
Ililii I
licada
I
li
una
constante, esta formula es computacionalmente eficiente.
3) El tercer término de la ecuación es la fuerza de la imagen, la cual es la magnitud
del gradiente. Para dar una magnitud (mag) en un punto y el máximo (máx.) y
mínimo (min.) lmk.nrLlen
cada yecino. se uriliia la operación (iiiinl-
mag)/(max -min) para normalizar el contorno. Esta magnitud del gradiente es
negativo, así que los puntos con gradientes grandes tendrán valores pequeños.
li
'!
4) Lo anterior se realiza mediante iteraciones. Al final de cada iteración, un
proceso determina la curvatura en cada punto del contorno y si el valor es
mínimo se establece
I
= O para
I
I
la siguiente iteración.
Figura 3.5 Vecindad del nodo anterior
v i.1,
nodo actual
vi, nodo siguiente Vi+,
Energía Funcional. La energía funcional tiene tres términos, uno de continuidad. otro
término de curvatura y el último de imagen, ver ecuación (3.8).
(3.8)
Donde afi) y
I
Pfi)
y &)son
constantes. Se utilizan valores que inicializan G I ,
!I
,&O.
cuando una esquina este presente en el punto actual se inicializa a I o mayor de I en otro
26
caso cuando no existen las esquinas a O. Ahora se describe como son calculados en la
computadora, cada uno de esos términos de la energía funcional.
a) Calculando Eeont, Dado los siguientes n puntos vi =( XI,y1 ) donde i=l ..n.Note que la
aritmética es entera en el tamaño n de snmels del objeto (n es el número de puntos del
contorno) debido a que el contorno es cerrado. Se considera un vecino (N, )de tamaño
m,en el punto actual devi como se muestra abajo, ver también ecuación (3.7).
Entonces se tiene:
'dj
E
KI. , E cont,j. = -d
1
V.-^.
J
1-1
11
(3.9)
Donde d e s la distancia media entre sus puntos es decir:
'I
La desviación de la energía calculada en la ecuación (3.9), es normalizada en la ecuación
(3.1 I), su vecindad & es como sigue:
E =
E cont,j
max
(3.1 I )
b) Calculando Ecurv. El cálculo de la curva de la energía se realiza utilizando la siguiente
fórmula:
(3.12)
27
Esta energía de la c b a es normalizada en su vecindad K, como sigue:
E
Cum, 1
E=j
E
K.(E
(3.13)
.)
CUrV,J
1
c) Calculando Eimage. El cálculo de la energía.de la imagen se obtiene de la intensidad de
las magnitudes dei gradiente de la imagen G,, de todos los puntos en Su vecindad
usando la siguieite ecuación:
si Gmm-
b m i n <üumbrai,
Entonces Gmin = Gmax
- üumbmi,
Aquí, Gumbmi =5
Entonces se normaljza las magnitudes del gradiente como sigue.
"J
E
'i'
Eimage,j
-
G . -G.
min J
G
-G .
max min
(3.15)
La Curvatura se calcula de la siguiente forma:
(3.16)
Donde:
JT
A k , = x , - x , . , y A y , = y , - y , . , yArc,As,= A x . + A y
28
\
A
3.3.2 Pseudocódigo del Snake
A continuación se muestra el pseudocódigo para obtener la envolvente del objeto,
basándose en las ecuaciones anteriores:
Establecer el contorno inicial llobtenidó por la técnica del gradiente.
Nodos a calcular =n
//Número de nodos que tiene el snake.
While (Pts-Mover > Umbral3)
{
for cada punto, vi, En el contorno
I
for cada punto, vj ,en la vecindad Ni del punto vi
calcular la energía E, =a,Econtj+ PjECUWYJ
} / Ipunto v,.
Mover el punto vi al punto vj en Ni con el mínimo de energía.
If vi es movido a una nueva localización, incrementar pts-Mover.
End. // punto,
Vi
Encontrar esquinas donde la curvatura es establecida por
0 4 por cada punto v, 11
/ / e n el contomo.
calcular curvatura ci.
if ((ci > cj., y Ci > ci+l ) //curvatura es más grande que sus vecinos
and (ci > Umbral I ) //curvatura es mayor que el umbral I
and (magnitud del gradiente en vi > Umbral2) /Borde fuerte
{
then
}
pi =O en el punto vi
}//end While
3.4 EJEMPLOS DE FUNCIONAMIENTO
1
Para que los resultados de los snakes sean satisfactorios, hay que saber manipular
las a@, @) y y(c), como ya se mencionó alfa representa la rigidez, beta representa las
curvas que existen en el objeto; que en caso de que existan esquinas, beta se inicializa a
29
cero. gamma representa la flexibilidad que deberá tener para ajustarse en forma adecuada al
objeto, lo anterior permitirá registrar los cambios que presenta el objeto.
A continuación se muestran algunos ejemplos para que se observe el uso de estos
11
parámetros. El primer valor representa (a),el segundo (P), el tercero (y), ver figura 3.6.
a)
o 0.1 0.0 5
a>P>Y
f)
00.1 0.1
I
o
a>P>Y
0.4.0.6.1.0
a>P>Y
0.6.0.4.1.0
a,P,u
0.8.0.2.1.0
'.O,om
a>P>Y
a,P,r
Figura. 3.6 Se muestra los resultados al cambiar los valores de a.8.u.
1.0
1.0, 0.0,l.O
a,P,u
Como puede observarse en la figura 3.6, cuando se disminuye Beta y Gamma se
mantiene igual, el snake no se adhiere a la forma real de la curva, cuando se aumenta Alfa,
se aumenta la rigidez y si el objeto tiene picos no se adhiere a la forma real del objeto.
Cuando se aumenta Gamma y Alfa y se disminuye Beta el snake se adhiere a la forma real
del objeto, debido a que al aumentar la elasticidad se envuelve adecuadamente a la forma
del objeto .
30
La técnica de los Snakes permite que el experto seleccione los puntos que 61
considere más importantes, se pueden seleccionar máximo 50 snakes. Un snake esta
formado por puntos conocidos como snaxels, el conjunto de snaxels corresponden a un
snake; en la figura anterior 3.6 los snaxels son unidos por lineas. El resultado del snake
permite registrar los cambios que presenta el objeto en cada cuadro, utilizando otras
técnicas como histograma, centro de gravedad del snake (con respecto a x e y , de cada
snaxel.) y obtención del área. Los resultados se obtienen por cada cuadro de video, por
ejemplo si existen 40 cuadros, se tendrán 40 resultados por cada snaxel que se esté
modelando.
Otros experimentos que utilizan la técnica de los Snakes con figuras más complejas
I
se pueden observar en las figuras.(3.8, 3.9, y 3.10). El objetivo de este experimento es el
If
segmentar y dar seguimiento a la boca de la persona . Se inicializa el snake seleccionando
los puntos o snaxels en la posición cercana a los labios ver figura 3.8.
'!
l
ike
Con los siguientes valores Alpha = 10 y Alpha =20, con Beta =1 en los dos casos:
Figura 3.9 a) Alfa=iO Beta=¡.
b) Alfa=20. Beta=l
31
Se puede observar que cuando el valor de aya aumenta los snaxels tienden a
juntarse más, es decir el snake se contrae más observe la figura anterior 3.9.
Figura 3.10 a) Inicialización del snake.
b) resultado del snake.
En conclusión, la técnica de los snakes permite adoptar los cambios que presenta el
objeto durante la secuencia de imágenes. Esta técnica es idónea ya que no se necesita
I
ningún conocimiento apriori del objeto y tampoco se requiere saber cuántos cambios
presentará el objeto. Los snakes se amoldan fácilmente a los cambios del contorno que
presente el objeto, por lo que permite registrar en forma fiel las transformaciones del
mismo.
!
!
Otro experimento con Alpha=l y Beta=l, Alpha=I y Beta=2, Alpha=l y Beta=3.
'!
ver figura 3.1 I
Figura 3.11 A ) u = I , p = I .
B)a=l.D=2.
C) a=i.p=3
32
En la figura 3.1 1 se observa que cuando se aumenta beta el resultado del snake no define en
forma exacta las esquinas, dando los valores adecuados se pueden aplicar los snukes en una
secuencia de video ver figura 3.12.
Figura 3.12 Secuencias de imágenes utilizando la técnica del snake.
3.5. COMENTARIOS
La etapa de segmentación es un proceso muy importante, ya que de ésta depende
que se obtengan en forma exacta los rasgos que permitirán modelar los objetos en forma
adecuada, por lo que la metodología propuesta contempla el uso de una técnica que
considerará los cambios que va realizando el objeto debido a la rotación, traslación y
movimiento. La técnica de los snakes evita la necesidad de saber upriori las formas que va
33
1,
adquiriendo el objeto durante el movimiento que éste realiza. Los snokes permiten extraer
los rasgos a partir de la selección que realiza el experto en la primera imagen. Lo anterior
es la base para desarrollar el modelado en forma automática, objetivo final de ésta
investigación.
34
1
CAPÍTULO 4
MODELADO
I
4.1 SELECCIÓN DE RASGOS
La selección de rasgos representativos de un objeto no es una tarea fácil, al
~
contrario, es un proceso bastante complejo que puede realizarse en una computadora. El ser
humano, por ejemplo, normalmente agrupa en categorías generales a los conceptos de
objetos que conforman su ,medio ambiente. Los rasgos que utiliza para representar a dichos
!
objetos son seleccionados de forma tan rápida y confiable que normalmente el ser humano
no se da cuenta del proceso que se realiza en el cerebro. Normalmente en la computadora
no se puede determinar upriori cuales son los rasgos mínimos que representan en forma
I/
adecuada al objeto que se va a modelar. Cuando se desea modelar un objeto, el experto
selecciona ciertos puntos que considera importantes de acuerdo con la experiencia
!
adquirida, ya que él puede tener conocimiento upriori de los cambios en el objeto que se va
modelar. Sin embargo, algunas veces puede no tener ninguna idea de los cambios que
puede presentar el objeto en el movimiento que éste presenta, esto, debido a la falta de
experiencia en el campo o a la falta de conocimiento del comportamiento del objeto. Con la
técnica de los snakes. Los cambios que presenta el objeto quedan registrados en un archivo
de conocimientos.
Como se mencionó en el capítulo anterior, la técnica de snukes pennite obtcner
información de los cambios que presenta el objeto, obtenidos por medio de la secuencia de
movimientos almacenados en un vídeo (secuencia de cuadros). El resultado obtenido es un
35
!
I
conjunto de información repetitiva debido a que el objeto no cambia de un cuadro a otro de
forma demasiado rápida, ya que se esperan cambios suaves (de un pixel a tres pixeles) por
lo que la información puede ser demasiado redundante. Lo que se necesita es una técnica
que permita obtener aquellos rasgos que mejor representen al objeto con el mínimo de
'II
información pero, que sin embargo esté completa o sea la más discriminante para un
reconocimiento posterior del objeto.
El humano cuando adquiere ciertos conceptos de un objeto, normalmente los agmpa
en categonas generales, estas categorías son un conjunto de rasgos seleccionados que
t
cumplen con propiedades que él mismo desea o ha seleccionado, lo cual le permite realizar
una selección fiable. Los rasgos que se han elegido, generalmente dependen, de la
experiencia del experto.
Para que el modelado pueda ser efectivo se debe de poseer métodos eficaces para
manipular las representaciones, por lo que es necesario contar con un método que permita
I
discriminar eficientemente los rasgos obtenidos en el modelado del objeto.
El determinar cuáles son las características iniciales del objeto, permite que se
genere un modelo correcto del objeto que se deforma durante un intervalo de tiempo. Una
técnica que permite obtener el conjunto mínimo de variables del objeto aí/¿¿flexiblees la
teona de testores [Shulcloper, 991.
!
Según [González, 961 un patrón o modelo es una descripción estructural o
cuantitativa. Un modelo es un conjunto de rasgos
Ó
características que mejor describen al
objeto.
4.2 ENFOQUE LOGICO COMBINATORIO
De acuerdo con [Shulcloper, 991, el Reconocimiento de Patrones (W), es la ciencia
de carácter interdisciplinano que se ocupa de los procesos de ingenieria, computacionales y
matemáticos relacionados con objetos físicos y abstractos, la cual tiene el propósito de
extraer por medio de dispositivos computacionales, la información que le permita
36
1
1;
establecer propiedades de los conjuntos de dichos objetos. Entonces, un problema de RP es
aquel que esta relacionado con la clasificación de objetos y fenómenos, con la
I
determinación de los factores que inciden con los mismos. El RP es la ciencia que parte de
los conocimientos clásicos de la clasificación y contempla el problema de la "selección de
rasgos". En este problema se solucionan 2 aspectos fundamentales:
a) Reducir el número de rasgos en términos de los cuales se describen los objetos de
trabajo.
b) Encontrar los rasgos que mayor influencia tienen en el reconocimiento de dichos
objetos, para esto se hace uso de la teoría de testores que se explica en este trabajo.
Como se puede observar, de acuerdo con [Shulcloper 991 en este trabajo de tesis
,
algunos conceptos básicos en la selección de rasgos son los siguientes:
Patrón: objeto ya clasificado.
Clase: Es un conjunto.de objctos, los cuales son semejantes, también se llama clase a
1;
aquellos conjuntos que formen un cubrimiento; es decir, se puede tener intersección no
vacía.
Rasgo: Características o factores que se consideran en el estudio de objetos, esto
permite realizar la descripción de los objetos.
Modelo: [González, 9,6] un patrón o un modelo es una descripción estructural o
cuantitativa de un objeto en una imagen; de acuerdo con [Shulcloper, 991 un objeto es
un concepto con el cual representamos a los elementos sujetos a estudio.
Desde otro punto de vista un modelo es una representación de un sistema que nos
permite simular su comportamiento en diversas condiciones y queda determinado por las
características que se han seleccionado y que permitirá modelar esta información para su
reconocimiento o estudio.
Ejemplos de objetos que representan a los elementos sujetos a estudios [shulcloper, 991:
Un paciente.
Una zona geológica.
!
Un equipo eléctrico.
Un conjunto de personas.
Una fotografia.
Lo objetos anteriores se establece formalmente considerando un universo M de
objetos y un cubrimiento finito K1,...,Kn, de M, por subconjuntos propios, es decir, Ki c M,
para ¡=I,,..+ Sean X I , ....x~los rasgos, en términos de los cuales se describen los objetos.
Cada rasgo xi tiene asociado un conjunto Mi que denominaremos conjunto de valores
admisibles del rasgo. Algunos de los conjuntos de valores admisibles que consideraremos
son:
Tabla 4.1. representación de los rasgos y clases (kl,k2) de los objetos (O,,O,) segun [Shulcloper, 991
XI
E1,l
...
XII
Raseos
Ei,n
Descripción del
objeto Om
compuesto de n
vaiiables
,I
Q , n
4.3 TEORÍA DE TESTORES
AI describir un objeto en términos de rasgos o sus respectivas variables no siempre
son necesarios todos los rasgos o variables para poder diferenciar unas clases de otras. Por
lo que es necesario encontrar qué subconjuntos son suficientes para caracterizar las clases
para ello se ha desarrollado una técnica que permite obtener los rasgos más importantes. El
algoritmo BT (Bottom Top) se basa en los conceptos de fesfory testor fípico. El objctivo
es obtener
una buena descripción de los objetos, obteniendo los mejores rasgos o
características más descriptivas del objeto. Esta selección no siempre es fácil y menos
38
li
menos cuando el vector de características es demasiado grande, o es dificil cuando las
variables tienen dependencia entre ellas.
81
1
De acuerdo con [Shulcloper, 991 testor en su concepto más básico para dos clases es
un conjunto de rasgos (columnas) que permiten diferenciar a un objeto entre dos clases; es
decir se tiene una clase to con n rasgos o variables y otra clase I / con n rasgos o variables, se
t
./
dice que ningún objeto de la clase to tiene descripciones semejantes de la clase 1 1 , un testor
se llama irreducible (típico) si al eliminar cualquiera de dichas columnas deja de ser [estor
para las dos clases (to,tl).
Un testor típico permite obtener los rasgos importantes para el reconocimiento del
objeto. De forma similar obtiene las combinaciopes mínimas de los rasgos de las clases,
't
esto hace la diferencia entre dos clases, a través del conjunto de rasgos, característica
necesaria para mantener la diferencia entre las dos clases. Este proceso explicado de
manera sencilla es lo que realiza el algoritmo BT.
4.3.1 Algoritmo BT.
El algoritmo para el cálculo de testores típicos trabaja con la generación de los n-uplos
booleanos (esto se refiere a los valores binarios, cero o uno que en su conjunto
representan un valor nufnérico) de la siguiente forma a(i)=al..
.a,,. donde el total dc las
alfas representan los rasgos o él número de variables que describen al objeto a modelar.
El algoritmo se basa en la comparación y análisis exhaustivo de todos los subconjuiitos
de los rasgos siendo el total de 2". El algoritmo no contempla todas las combinaciones
ya que realiza saltos cuando encuentra un testor típico, este algoritmo al mostrar los
resultados de la lista de teslores típicos, no determina cuál es el mejor de toda la lista
que fue generando.
El algoritmo se basa en la idea de ir generando a(¡) a partir del número biiiario (O ... I )
hasta 2" ,es decir el orden natural de los vectores característicos de los 2" se inicia el
valor como O...O
y el ultimo valor para a es 1..1 esto se realiza utilizando la
39
11
numeración binaria en orden ascendente, se considera cuando a, =O (i=O,i ...n) el rasgo
'1
no se toma en cuenta en la descripción del objeto y cuando a.=l indica
que el rasgo j
!I
permite diferenciar un objeto que pertenece a una clase de otro que no pertenece a la
misma clase. Por ejemplo cuando el algoritmo encuentra un testor tipico con el
siguiente valor a(i)=000100 los siguientes valores no son tesiores tipicos
a(i+l)=000101, a(i+2)=000110, a(i+3)=000111, ya que así fue diseñado este
algoritmo, que permite saltos para ser más rápido, el algoritmo continúa con el siguiente
valor a(it4)=001000 hasta que se alcance el valor de a(i+n)=lll 11I . El valor máximo
que puede alcanzar depende del número de rasgos del objeto. Por ejemplo para 3 rasgos
empieza con O00 y termina cuando alcanza su máximo valor que es 11 1.
Para llegar a estos resultados el algoritmo sigue una serie de pasos que se listan a detalle a
continuación.
a) Calcular la Matriz de Diferencia
b) Obtener subfila y superfila de la matriz de diferencia para generar la fila básica.
C) Proposiciones que determinan que rasgos son testores típicos.
d) Algoritmo de testores tipicos
a) Matriz de Diferencia (MD)
Se calcula la matriz de diferencia, la cual se obtiene de comparar cada objeto de cada clase
con los objetos de las clases restantes.Tenemos dos matrices que representan dos clases
diferentes la primera clase con tres objetos, la segunda clase con 2 objetos teniendo cinco
rasgos cada clase ver tablas 4.2 y 4.3.
Tabla 4.2. Representa la primera clase con tres objetos.
40
r
11
I
I
Tabla 4.3. Representa la segunda clase con dos objetos.
Utilizando criterios de diferencia, se compara las filas del objeto fo con las de 11, es
decir se toma la primera columna del objeto uno con la primera del otro objeto, la primera
con la segunda y así sucesivamente, por lo que el resultado de filas en total sería las filas
del primer objeto por las filas del segundo objeto (para este caso tenemos 3 objetos de la
primera clase y 2 objetos de la segunda clase, esto es 3 x 2= 6 filas) de la matriz de
diferencia. ver tabla 4.4.
Tabla 4.4. Resultado de la matriz de diferencia
b) Fila Básica
Para obtener la fila básica primero se necesita conocer cuál es subfila y superfila.
Sean p y t dos filas de la matriz de diferencia, se dice que p es subfila de r si en todas las
columnas donde el renglón d e p tiene un I , también I lo tiene,ver inciso a).
a) t'j (ap,
=1 2
a,, = I ) .
Ejemplo:
p
=
10001
t
=
11101
41
L
f
I
10ssiguientes 2
n-k - I
n-upios son listas restores pero no típicos.
L
42
Tabla 4.3. Representa la segunda clase con dos objetos.
Utilizando criterios de diferencia, se compara las filas del objeto
to con
las de I , , es
decir se toma la primera columna del objeto uno con la primera del otro objeto, la primera
I
con la segunda y así sucesivamente, por lo que el resultado de filas en total sena las filas
del primer objeto por las filas del segundo objeto (para este caso tenemos 3 objetos de la
primera clase y 2 objetos de la segunda clase, esto es 3 x 2= 6 filas) de la matriz de
diferencia, ver tabla 4.4.
Tabla 4.4. Resultado de la matriz de diferencia
I
b) Fila Básica
Para obtener la fila básica primero se necesita conocer cuál es subfila y superfila.
Sean p y I dos filas de la matriz de diferencia, se dice que p es subfila de f si en todas las
columnas donde el renglón ,dep tiene un 1, también f lo tiene,ver inciso a).
a) Vj (ap, = I 2 a,, = 1 ) .
Ejemplo:
p
=
10001
I
=
11101
41
'I
I
Existe al menos una <cohnnaen la que t tiene un 1 y p no IO tiene, también se dice
I
que f es superfila d e p ver inciso b).
b) 3k (atk = 1 /\apk
=O
Ejemplo
I
p=( i000001)
f=( 101000I )
se observa que p es subfila de t ya que donde hay un uno en p en f también lo hay.
También f es supefila d e p ya que al menos hay 1 donde p no lo tiene.
!
Con esto se puede definir la matriz básica.
I*
Matriz básica (MB): Sea t una fila de la matriz de diferencia se dice que t es una fila
básica si no existe fila p que sea subfila de t. en otras palabras la fila básica es aquella fila
de la MD que no es superfila de otra ver un ejemplo en la tabla 4.5.
Tabla 4.5 SI4 es un ejemplo de una fila básica, la cual no es supertila de otra
I
I
I
I
I
I
I
I
I
I
I
I
para obtener la lista iesfor,existe un conjunto de proposiciones [Shulcloper, 991.
c) Proposiciones
Proposición 1. La lista a , n o es lista fesforcuando y sólo cuando en MB existe al nienos
P
una fila tal que se cumple la condición
a=@,,. . .,a,,)
Vj = 1, ..., n ( a .
J
A
a,)=O
1
Siendo A el operador booleano de conjunción lógica.
Proposición 2. Sea a una lista [estor típico y k el
10ssiguientes 2
SI
índice del
"-'
- 1 n-upios son listas testores pero no típicos.
I
imo uno en a,entonces
42
Proposición 3. Sea a una lista testor y k el subindice del ultimo uno en a, entonces los
siguientes 2
"-'
- I n-upios son listas testores pero no típicos.
Proposición 4. Sea a=(a,, ...,a,) una fila de MB y k el subindice del Último 1 en a suponga
que también a= (a!,.. .,an)no es lista testor y que para u y a se satisface lo siguiente:
I
i!
V j = 1, ..., n ( a . A a . ) = O
J
1
Sea a=(&/,...,a',)talque.
a.sij<k
a.= 1si j = k
1' lO:ij>k
Entonces ninguna lista comprendida entre a y a' es una lista testor
d) Algoritmo
I
¡. Se genera la primera lista a no nula de longitud n.
Paso
Paso 2. Se determina la proposición I si la lista generada a es una lista testor en MB
(matriz básica).
Paso 3.
a) Si es lista tator aplicamos la proposición 3.
b) Si es lista testor típico se imprime a y se aplica la proposición 2.
c) Si no es lista testor se determina la fila u de la MB que provoca este hecho (de no ser
Única se toma la que tenga el Último 1 más a la izquierda se aplica la proposición 4.
Paso 4. Se genera la lista siguiente a las descartadas en virtud del paso 3 y. se regresa ai
I
paso 2 en caso de que la lista resultante del paso 3 no sea posterior a 1 , l . . . , l , l . Es decir, si
el tadaño es de I 11 1 verificar que no sea mayor a 11 1 1 o igual a 1 1 I 1 1 . La selección de
rasgoj permitirá seleccionar aquellas variables que permitan identificar o reconocer al
I
objeto que se está modelando.
k
43
Proposición 3. Sea a una lista testor y k el subíndice del ultimo uno en a, entonces los
siguientes 2 n-k -1 n-upios son listas testores pero no típicos.
Proposición 4. Sea a=(a,,. ..,a,) una fila de MB y k el subindice del último I en a suponga
que también u=
.,an)no es lista testor y que para u y a se satisface lo siguiente:
(al,..
V j = 1, ...,n ( a . A u . ) = O
J
1
Sea a= (a'!,
...,dn)
tal que.
a.sij<k
a . = Isi j = k
J lOlij>k
I
Entonces ninguna lista comprendida entre a y a' es una lista testor.
d) Algoritmo
Paso 1. Se genera la primera lista a no nula de longitud n.
Paso 2. Se determina la proposición 1 si la lista generada a es una lista testor eii MB
(matriz básica).
Paso 3.
a) Si es lista tesior aplicamos la proposición 3 .
b) Si es lista testor típico se imprime a y se aplica la proposición 2 .
c) Si no es lista testor se determina la tila u de la MB que provoca este hecho (de no ser
única se toma la que tenga el último I más a la izquierda se aplica la proposición 4.
Paso 4. Se genera la lista siguiente a las descartadas en virtud del paso 3 y, se regresa al
paso 2 en caso de que la lista resultante del paso 3 no sea posterior a 1,l.. . , I , I . Es decir, si
el tamaño es de 1 1 11 verificar que no sea mayor a 1 1 I 1 o igual a 1 11 1 I . La selección dc
rasgos permitirá seleccionar aquellas variables que permitan identificar o reconocer al
objeto que se está modelando.
43
A continuación se muestra el siguiente ejemplo:
Se toman los objetos de las tablas 4.2. y 4.3 y el resultado de la matriz de diferencia es la
tabla 4.5, se obtiene la matriz básica que está compuesta por el total de filas básicas y su
resultado es la tabla (4.6).
Tabla 4.6 resultado de la matriz básica
Se inicializa a con el siguiente valor
Paso 1:
EO0001.
Paso 2:
El resultado es que no es lista testor, por la proposición 1.
Paso 3 :
Se aplica c).
Se utiliza la proposición 4.
Paso 4:
Se genera la nueva alfa.
a=010000.
Paso 2:
El resultado es que no es lista testor, por la proposición 1.
Paso 3 :
Se aplica c)
Se utiliza la proposición;4.
Paso 4:
Se genera la nueva alfa. '.
~011000.
44
Paso 2:
El resultado es lista testor.
Paso 3:
Aplicar b).
Es testor típico se imprime y se aplica la proposición 2
a=o 11000.
Paso 4:
Se genera la nueva alfa.
a=100000.
Paso 2:
No es testor.
Paso 3:
Aplicar c).
Se aplica la proposición 4
Paso 4 :
Se genera la nueva alfa
a= 1 10000.
Paso 2:
No es testor.
Paso 3 :
Se aplica c).
Paso 4:
Se aplica la proposición 4
Se genera la nueva alfa.
a=l11000.
Paso 2:
No es lista testor.
Paso 3:
Aplicar c).
Se aplica la proposición 4
45
Se genera la nueva alfa.
a=lll111.
Como en este caso alfa es mayor a 11 111 se termina el proceso.
4.3.2 Importancia de los testores típicos
En algunos casos se generan varios testores típicos como se ha visto anteriormente por
lo que el usuario no conoce qué conjunto de rasgos son los más importantes para una mejor
descripción del objeto. Existen dos métodos que se describen a continuación y que permite
conocer que rasgos son más importantes.
a) Peso Informacional.
b) Longitud del Testor.
a) Peso Informacional:
La manera de obtener este valor en la opinión de [Shulcloper, 991 es la siguiente: Sea I
el numero de festores fípicos que tiene una matriz de aprendizaje y f(i) el numero de
testores típicos en los que aparece la columna correspondiente al xi, se dice que el peso
informacional se obtiene a partir de la siguiente fórmula:
Para i = l . ..n, x, E R.
Ejemplo se tienen los siguientes conjuntos de testores típicos
Y={{ X i l>~x2,xsl,~x2,x3,x4~
I
P(~i)=P(x3)=P(~)=P(~s)=O.33333 y P(~z)=0.666.
Son tres subconjuntos de testores rípicos, el primer subconjunto aparece una vez con la
siguiente variable x,,en el segundo subconjunto aparecen dos variables x2,xj y en el terce
subconjunto tres variables x2.xJ,x4en el segundo y tercer subconjunto se repiten dos veccs la
variable x2=2/3=0.6666.
Todas las demás variables aparecen una vez por lo que su valor es de ( I /3=0.33333) es
natural pensar que el rasgo x , es más importante que los otros rasgos, sin embargo en el
46
resultado numérico no lo demuestra, por lo que este cálculo por si solo no muestra el
resultado coriecto.
b) La longitud del testor:
Resulta natural considerar un rasgo más importante en la medida en que es menor la
longitud del testor típico en que aparece, esto es asociando a cada rasgo una magnitud que
depende de estas longitudes y se denota por L(a:
= Y 1(4.2)
La ecuaci
~
I
(4.2) indica en el numerador la sumatona dc. .estor típico que aparece en cada
conjunto, en el caso de L(XI) aparece solo una.ves {xi}, esto dividido por el numero total
que aparece en todos los conjuntos, el resultado es 1/1/1=1.
L(XI)=l, L(X+0.418, L(X3)= L(&)=0.333 , L(Xs)=0.5.
Estos valores no muestran la verdadera importancia de las variables ya que se esperaba que
X,, sea más importante sin embargo Xj muestra un valor mayor X2, ya que X,
necesita de una variable adicional mientras que XSnecesita dos variables adicionales, se
el rasgo
requiere de una combinación de cálculo adicional como se muestra en el siguiente caso:
p(X)=aP(X) + pL(X) donde a y p >O a + p=l.
a y p son parámetros que ponderan la participación de P(x) y de L(x). Si asignamos los
siguientes valores a = p=0.5, se obtienen los siguientes resultados:
p( XI ) =0.666 p( Xz) ~ 0 . 5 2 4p( X,)= p( Xq =0.333 p( X5)=0.416
este resultado es el que se esperaba, ya que se muestra de acuerdo con su importancia
previamente intuida.
4.4 RASGOS A MODELAR
Como ya se mencionó los rasgos son las características que se toman en cuenta para su
estudio, en este trabajo al utilizar la técnica de snakes, , se registran las distancias entre
todos los puntos de Y yy, que presenta el objeto aífqflexible, estos cambios se almacenan en
47
l
una base de conocimientos, los cuales fueron el resultado de una secuencia de cuadros en
un vídeo. Lo siguientes rasgos que registra la herramienta en la base de conocimientos se
obtienen por medio del histograma, centro de gravedad del snake relacionado con x y y . el
área del objeto, lo anterior una vez almacenados en la base de conocimientos se utiliza la
técnica de tesfores (@cos, esta técnica permite disminuir la redundancia de información,
es decir obtiene un conjunto de rasgos que mejor describan al objeto
4.4.1 Color por Histograma
El histograma [Maravall, 941 de una imagen consiste en un diagrama de frecuencias,
de la propia imagen. Las abscisas (valores de x, de O a 255) corresponden a los niveles de
gris o valor del byte correspondiente al formato RGB (red,green,blue) y las ordenadas es el
número de veces que se presenta el valor de cada pixel (ver figura 4. I), en el formato RGB.
se necesitan tres hictogramas para representar cada valor del formato, se toma los cuatro
valores mas altos de R, G y B del formato, con esto se registran los resultados en una base
de conocimientos que al final contiene un numero que se refiere al objeto que se esta
modelando, por ejemplo si se modelan 3 objetos, existirán 3 bases de conocimientos. El
número al final será del cero al dos, esta información es registrada en bruto en la base de
conocimiento, la cual nos da una idea de cómo se muestran los colores del objeto en cada
cuadro en toda la secuencia del vídeo.
Figura 4.1 Imagen con su respectivo histograma en la pane inferior
48
4.4.2 Centro de gravedad del snake relacionado con "x" y "y"
Es la Suma de todos los snuxels con respecto a ''y" y "x" entre el número de snusds.
Esto representa una medida de tendencia central, se utilizan para indicar un valor que tiende
a tipificar o a ser el más representativo de un conjunto de números. Una representación
física [Stevenson, 811 de la media, es imaginar una barra con un punto de apoyo central que
sostiene pesos iguales en sitios correspondientes a los valores de un conjunto. Esta
información es almacenada en bruto en el archivo de conocimientos.
4.4.3 Area
Área es el número de píxeles que están dentro de
un objeto, esta información
permite conocer los cambios que puede estar presentando el objeto que se está modelando,
respecto a
su tamaño, Esta información es almacenada en bruto en la base de
ennocimientos.
4.4.4 Distancias entre todos los puntos de "x" y "y" del snake
Las distancias de los puntos de snake,. perniite saber cuanto está cambiando la
deformación respecto a la dirección de las
logra obtener los
, ,
'Y'
y la dirección respecto a las 't",con esto se
puntos mas invanantes durante el modelado,
o saber que puntos no se
modificaron o casi no se modificaron, esto se obtiene a través de una combinación de.los
puntos multiplicado por dos ya que es con relación a las ordenadas y las abscisas del
snaxel.
Primero el usuario selecciona los puntos que desea modelar ver figura 4.2. Para este caso se
eligen los labios, los puntos están alrededor de estos. La información que se genera de los
rasgos, como ya se mencionó se almacena en una base de conocimientos.
49
Figura 4.2 El snake se adecua a la forma del movimiento de los labios
Esta información es almacenada en bruto, por lo que existe redundancia de iiiformacii,ii. a
esta información se le aplica la técnica de testores tipicos.
Para este ejemplo se utilizó un conjunto de 60 cuadros, avanzando'tres cuadros poi- cada
iteración y los testores tipicos obtenidos fueron 43 ver la tabla 4.7.
so
En la base de conocimientos se almacenan los siguientes resultados:
Los valores representan las combinaciones de las distancias con su respectiva variable, es
decir la columna ROXl representa la distancia del snaxel respecto a “x” es decir el punto
cero con el punto uno, y así sucesivamente hasta el total de los puntos ( s m m d s ) que el
usuario selecciono.
Distancias obtenidas de los cinco puntos (numerados O a 4) que el usuario
selecciona alrededor de los labios.
“ROXI ,ROYI ,ROX2,ROY2,ROX3,ROY3,ROX4.ROY4,Rl
X2,RIY2,RI X3,RI Y3.R I
X4,RlY4,R2X3,R2Y3,R2X4,R2Y4,R3X4,R3Y4”
Las siguientes cuatro columnas son los primeros cuatro valores que más se presentó
en color Rojo, a continuación los cuatro valores representan los primero cuatro valorcs del
color Verde, los otros cuatro valores representaii los valores del color A d que más sc
presentaron en la imagen, los siguientes dos valores representan el centro de gravedad de
51
las variables de "x" y "y".El último valor representa el valor del área que presentó el
objeto.
Esto genera una matriz que representa las variables de cada punto que se va a
modelar para este caso hay cinco rasgos. Se obtiene la
matriz de Diferencia.
posteriormente se calcula la matriz básica, y por último se calculan los restores t i p m ~ s .
dando como resultado 43 testores típicos con 35 rasgos, que es la combinación de las
distancias de sus puntos, más los colores en formato R.G.B (red, green, blue), el centro de
gravedad de "x" y "y" y el área.
Lo tesrores típicos obtienen los rasgos mínimos del objeto a modelar. AI tener estos
rasgos no sabemos el orden de importancia de estos, por lo que se obtiene la longitud de los
testores.
esto nos permite tener información del orden de importancia de los rasgos. Como
se muestra a continuación:
Variable[28]=[0.134921], Representa el primer valor del color Azul.
Variable[24]=[0. iO7143], Representa el cuarto valor del color Azul.
Vanable[ 13]=[0.099206], Representa la distancia RIY4.
Variable[07]=[0.095238], Representa la distancia ROY4.
Variable[ 16]=[0.083333], Representa la distancia R2X4.
Variable[ I 1]=[0.047619], Representa la distancia RlY3.
Variable[ I2]=[0.0476 191, Representa la distancia R 1x4.
Variable[25]=[0.0476 191, Representa el segundo color Verde.
Variable[26]=[0.047619], Representa el tercer color Verde.
Variable[34]=[0.0476 191, Representa el Área.
Variable[02]=[0.04365 I], Representa la distancia ROX2.
Variable[ 14]=[0.04365 I], Representa la distancia R2X3.
Variable[ I8]=[0.04365 I], Representa la distancia R3X4.
Variable[21]=[0.023810], Representa el segundo color Rojo.
Variable[22]=[0.0238 lo], Representa el tercer color Rojo.
Variable[29]=[0.0238 lo], Representa el segundo color Azul
Variable[00]=[0.007937], Representa la distancia ROXl.
Variable[04]=[0.007937], Representa la distancia ROX3.
Variable[05]=[0.007937], Representa la distancia ROY3.
Variable[08]=[0.007937], Representa la distancia R 1X2.
Variable[33]=[0.007937], Representa el Cgy.
4.6 COMENTARIOS
La técnica de los testores tipicos permite obtener el mínimo de información que se
necesita para describir a un objeto a través del conjunto de los rasgos que en cada cuadro se
registra durante la secuencia de imágenes, mediante la técnica de snakes permite registrar
los cambios que presenta el objeto y que el experto desea analizar al utilizar la teoria de
festores permite al experto modelar los rasgos que ha seleccionado en el objeto, esto
permite eliminar redundancia de información para describir al objeto de la mejor manera
posible, una vez hecho lo anterior es importante conocer el orden de importancia de los
testores de mayor a menor para determinar que variables son las mas importantes ell' la
descripción del objeto modelado.
53
CAPÍTULO5
5.1 INTRODUCCI~N
En este capítulo se presentan los experimentos del modelado automático de objetos
aljaj7exibles. a través de secuencias de imágenes. Los puntos a evaluar son los siguientes:
a) El funcionamiento de la metodología propuesta para el modelado de objetos
ava/iexibles en secuencias de imágenes
b) El desempeño de la herramienta para registrar las deformaciones que puede
presentar el objeto en una secuencia de cuadros de imágenes utilizando le.vfore.s
tipicos.
c) Evaluación la descripción de'los objetos al aplicar testores tipicos.
Para realizar los experimentos anteriores se consideran los siguientes puntos:
1. El sistema de modelado. de objetos alfaj7exibIes en secuencia de imágenes,
realiza su trabajo en imágenes de 24 bits en formato AVI. Los objetos se
encuentran en la imagen. Este sistema no contempla imágenes donde se pierdan
los contornos de los objetos (ocasionado por factores externos como
iluminación no adecuada) y no aporta soluciones a problemas relacionados con
oclusión.
2. Es posible modelar hasta 50 objetos como máximo.
3.
Las secuencias de video son hasta 30 cuadros por segundo y no es necesario
tener conocimiento de las deformaciones que presentará el objeto.
54
5.2 CASOS DE ESTUDIOS REALIZADOS
CASO 1:
El objetivo de esta prueba es evaluar la metodología propuesta para el modelado de
objetos alfqflexibles. Para este ejemplo se realiza el modelado del movimiento del párpado
en un ojo. La secuencia de imágenes se obtuvo de una serie televisiva, la herramienta
modela el movimiento de los párpados de los ojos.
La metodología se compone de los siguientes pasos:
Paso # I :
El usuario define los puntos cerca del objeto que desea modelar (ver figura 5. I).
Figura 5.1 Se seleccionan los puntos alrededor de los parpados
55
Paso I# 2 :
El usuario define a partir de qué número de cuadro desea modelar el objeto en una
secuencia de imágenes.
Paso # 3:
El usuario define los parámetros del snake
L Z , ~ &(ver
capítulo 4)
Los valores que registra el snake son las distancias de los snaxels, para este ejemplo
de cinco puntos se tiene la distancia del punto cero con el punto uno "ROXI"con respecto a
X y "ROY1"es la distancia del punto cero con el punto uno con respecto a Y, hasta el
ultimo punto "R3X4,R3Y4".En total se tiene veinte distancias
"ROX 1 ,ROY1 ,ROX2,ROY2,ROX3,ROY3,ROX4,ROY4,R
IX2,RlY2,RI X3,RlY3,RlX4,K
IY
4,FUX3,R2Y3,R2X4,R2Y4,R3X4,R3Y4,"
ver tabla 5 . I .
Tabla 5.1 Distancias de los puntos que conforman los snaxels alrededor del .snake
Una vez hecho lo anterior, la técnica de los snakes registra las deformaciones que
presenta el objeto, como ya se mencionó en el capitulo 4.Los datos de la deformación que
va presentando el objeto en la secuencia de imágenes se almacenan en una base de
conocimientos, en archivos de tipo texto. Esta información se obtiene del conjunto de
snaxels que conforma el snake. Cada,resultado del snake se adhiere a la forma que va
presentando en cada cuadro el objeto que se esta modelando. Para este ejemplo es el
parpado izquierdo de la persona. También registran los cuatro valores de (R.G.B) que iilás
aparecen en el snake,estos rasgos son presentados en la sicuiente tabla 5.2.
Tabla 5.2 Cuatro colores que mas aparecen del formato R.G.B que modela la hemamiciita
184 166 151 10
15
I
I
1
I
164 158 155 10
I
I
I
I
I
1110163 161 10
I
I
I
I
1209 1141
I
1
1220
1
I
I
Con esta información y con la obtenida inicialmente, tabla 5. I . Se genera la MD que
tiene el numero de rasgos ver tabla 5.3 lo anterior representa las distancias de sus puntos y
los rasgos mencionados en la tabla 5.2.
Tabla 5.3 Matriz generada mediante las distancias de los puntos mas los rasgos de la tabla 5. I
1
1
I
O
I
O
...
O
1
O
I
O
Los resultados se almacenan en una base de conocimientos. Una vez almacenada
esta información, se obtiene la MD, ver tabla 5.4. Esta nos da información sobi-c las
diferencias existentes o las descripciones del objeto obtenida en la MB, por ultimo se
muestra e l conjunto de18 testores tipicos, ver tabla 5.6.
57
Tabla 5.4 Resultado de la matriz de Diferencia
Tabla 5.5. Resultado de la matriz Básica.
Tabla 5.6 .Testores típicos.
AREA
O
O
O
O
O
O
O
O
...
O
O
O
58
Una vez obtenida la minima información, se obtiene la longitud del testor típico, esto
muestra la importancia en orden decreciente.
Variable[OX]=[i.O1851], la variable 8 representa la distancia RIX2.
Variable[l1]=[0.746031],la variable I 1 representa la distancia RlY3.
Variable[ 14]=[0.388888], la variable 14 representa la distancia R2X3.
Variable[ iX]=[O.388888], la variable 18 representa la distancia R3X4.
Variable[33]=[0.11111 I], la variable 33 representa Cgy.
Variable[l2]=[0.074072], la variable I 2 representa la distancia RIX4.
Variable[20]=[0.074072], la variable 20 representa el primer color Verde.
Variable[30]=[0.074072], la variable 30 representa el tercer color Ami.
Variable[06]=[0.027777], la variable 6 representa la distancia ROX4.
Para este resultado se realizaron 2 experimentos de 9 imágenes cada uno, así como
sus respectivos testores típicos,y la importancia de los mismos.
Los resultados obtenidos muestran que:
I . La herramienta modela al objeto y almacena los cambios que presenta el objeto en la
secuencia de cuadros.
2. Se reduce considerablemente el conjunto de rasgos para la representación del objeto (en
este caso el parpado) ya que al el numero mínimo de variables, son suficientes para
modelar el objeto.
CASO 2:
Para este ejemplo se realiza
el modelado del movimiento de los labios. Esta
secuencia de imágenes se obtuvó con una cámara de 8 milímetros con iluminación
semicontrolada, ver figura 5.2. En este caso se tienen 9 imágenes cada uno, mostrando sus
respectivos testores típicos y la importancia de éstos.
59
Figura 5.2 Lectura de labios con ruido.
Para este caso se seleccionan cinco puntos o snaxels en los labios de la persona, durante la
secuencia se realizó el mismo procedimiento que en el caso 1
I . Se obtienen 14 testores tipicos que se muestran en la tabla 5.7
60
Tabla 5.7 Testores iipicos obtenidos del segundo caso
A continuación se muestra la importancia de los rasgos, el orden de importancia es
de mayor a menor. Este resultado es el modelo del objeto.
1. Variable[33]=[0.16666], Representa en Centro de gravedad de "Y"
2. Variable[29]=[0.12222], Representa el cuarto color Azul.
3. Variable[15]=[0.08888], Representa la distancia R2Y3.
4. Variable[O5]= [0.06666], Representa la distancia ROY3.
5. Variable[06]= [0.06666], Representa la distancia ROX4.
6. Variable[07]= [0.06666], Representa la distancia ROY4.
7. Variable[l3] =[0.06666], Representa la distancia RiY4.
8. Variable[ 17]= [0.06666], Representa la distancia R2Y4.
9. Variable[21]= [0.06666], Representa el primer color del Rojo.
IO. Variable[26]= [0.06666], Representa el tercer color del Verde.
11. Variable[30]=[0. 0066661, Representa el tercer color Ami.
12. Variable[l1]=[0.03333], Representa la distancia R1Y3.
13. Variable[l9]=[0.02222], Representa la distancia R3Y4.
61
~
~~~
~
CASO 3 :
Se realiza el modelado de los labios en movimiento en la persona. Estas secuencias de
vídeo fueron obtenidas con una cámara de vídeo de 8 milímetros, con iluminación
semicontrolada ver figura 5.3. Se realizó con 9 imágenes, el cual se muestra sus respectivos
restores típicos e importancia de los mismos. En este caso se obtiene 43 testores típicos, ver
tabla 5.8. La diferencia de este caso con el numero 2 es que este modela exteriormente los
labios y el caso anterior los modela interiormente.
de labios sin mucho ruido,
~
62
Importancia del orden de los testares típicos en orden de mayor a menor.
Variable[28]=[0.134921],Representa el primer valor del color Ami
Variable[24]=[0.107143], Representa el primer valor del color Ami
Variable[ 13]=[0.099206],.Representala distancia RIY4
Variable[07]=[0.095238], Representa la distancia ROY4
Variable[ 16]=[0.083333], Representa la distancia R2X4
Vanable[l1]=[0.047619], Representa la distancia R1Y3
Vanable[ 12]=[0.047619], Representa la distancia RIX4
Vanable[25]=[0.047619], Representa el segundo color Verde
Variable[26]=[0.047619], Representa el tercer color Verde
Vanable[34]=[0.047619], Representa el Área
Variable[02]=[0.04365 11, Representa la distancia ROX2
Variable[ 14]=[0.04365 11, Representa la distancia R2X3
63
Variable[l8]=[0.04365 1J,Representa la distancia R3X4
Vanable[21]=[0.0238 101, Representa el segundo color Rojo
Vanable[22]=[0.023810], Representa el tercer color Rojo
Vanable[29]=[0.0238 lo], Representa el segundo color Ani1
Vanable[OO]=[O.OO7937J, Representa la distancia ROXl
Variabie[04]=[0.007937],Representa la distancia ROX3
Variable[O5]=[0.007937], Representa la distancia ROY3
Variable[08]=[0.007937], Representa la distancia R1X2
Vanable[33]=[0.007937], Representa el Cgy.
CASO 4:
Ahora observe el siguiente experimento donde se modela la cabeza de la persona ver figura
.5.4.
Figura 5.4 Modelado d e la calxza en un ambienic natiir4
64
En este experimento no se obtiene la matriz básica, esto significa que cualquier rasgo es
importante para el modelado del objeto alfnflexible. Se realiza 10 cuadros en incrementos
de 2 en 2. Con un total de cinco puntos (snaxels ) para modelar el objeto alfqfiexible.
5.3 ANALISIS DE LOS RESULTADOS
Los resultados muestran que la herramienta puede modelar objetos deformables,
aún cuando ellos tengan diferente forma y flexibilidad tales como los párpados humanos,
como se muestra en el caso 1, el movimiento de la parte interna de los labios así como la
vista exterior de éstos mismos. Con ello se demuestra que la metodología propuesta
inicialmente si cumple con el objetivos establecido de caracterizar o modelar de manera
automática a objetos deformables a través del análisis del movimiento de los mismos.
De acuerdo con los resultados se observa que la técnica de los snakes es eficiente,
aún con movimiento, de tal forma. que se puede modelar los movimientos del cuerpo
humano. La herramienta es eficiente aún si existiera un objeto con problemas de malos
contornos. Sin embargo, si existen tres cuadros continuos en el video donde no se presentan
contornos de forma adecuada, no puede modelar de forma correcta, pero esto se considera
factores externos ajenos al algoritmo.
65
CAPÍTULO6
CONCLUSIONES
6.1 INTRODUCCI~N
Para que un modelo sea efectivo [Magadán, 991 se deben poseer métodos eficaces
I
que determinen a los objetos a través de la extraccjón de características. Este método queda
establecido en este trabajo a través de la técnica snakes y testores típicos, la información
que se obtiene de la deformación que.presenta el objeto en cada cuadro, es registrada por
los snakes, los testores típicos minimizan la información para describir al objeto. El
modelado es la parte más importante para el proceso de segmentación que se conforma por
los descriptores o rasgos que se registran en las secuencias de cuadros del video.
El modelado de objetos a@Jexibies es un problema donde los rasgos que se
obtienen como resultado de las defonhaciones del objeto, que se generaron en cada cuadro
del conjunto de las secuencias de imágenes, permite generar modelos primarios, los cuales
se utilizan para el reconocimiento de patrones.
La metodología utilizada en este trabajo cumple con el objetivo que se esperaba en
lo siguiente:
Este trabajo permite generar modelos primarios de objetos
!
Realiza el proceso del modelado en forma automática.
Registra las variaciones de cada parámetro del modelo en una secuencia de
imágenes.
Procesa la información de cada cuadro del video mediante testores típicos.
66
6.2 METAS ALCANZADAS
Nomalmente el modelado de objetos, se realiza de forma manual, Por
10
que la
herramienta apoda una gran solución en ei proceso de observación de escenas, en las cuales
un objeto presenta deformaciones. Este &abajo aporta la automatización del modelado de
objetos alfqfleribles y no se necesitan 1,herramientas adicionales, siendo de gran ayuda
I
especialmente donde se requiere utilizarla vista humana.
11
La herramienta permite modelk los objetos alfaflexibles con las siguientes
I
características:
Los cuadros del video que procesa en formato avi son de 24 bits.
1
Se utiliza una técnica llamada snakes que no necesita del conocimiento apriori
del objeto a modelar para registrar los cambios que presenta el objeto.
!
La información que genera del snake, histograma, área, centro de gravedad de x
Y Y-
I
* La información que se obtiene en bruto de los cambios que presenta el objeto se
procesa por medio de testores típicos.
Se muestra ia importancia de los rasgos mínimos en orden descendente,
Los resultados en el modelado,de objetos ai$aJexibles en secuencias de imágenes,
se muestran satisfactorios. Se cumple con el objetivo de desarrollar una herramienta que
modele en forma automática, que permite registrar los cambios que presenta el objeto y
obtener las variables mínimas que permitan caracterizar al objeto modelado, mostrando la
importancia de estas variables para generar modelos primarios de objetos.
6.3 PRODUCTO ESPERADO
Se ha desarrollado una hekamienta, que contemple una metodología, que en
forma automática obtiene el modelo de objetos ai$aj7exib/es.
Procesa la selección de variables de manera automática para describir el objeto
de interés, por medio de un algoritmo de clasificación llamado testores típicos.
Se obtienen modelos primarios de objetos que contienen los mejores rasgos en
orden de importancia decreciente.
67
I
6.3 APORTACIONES
Para un funcionamiento más robusto de la técnica de snakes la herramienta contempla
modificaciones en los parámetros Alfa,:Beta y Gamma. Cuando se desea generar mas
tensión se aumenta Alfa, cuando se desealcrear mas elasticidad se aumenta Gamma, cuando
existen curvas pronunciadas, se establece Beta mayor a cero, y si existen picos muy
pronunciados se inicializa Beta con un valor de cero. También podemos establecer la
cantidad de iteraciones para que el snake l se adapte mejor a la forma del objeto. Otra opción
es modificar el número de cuadros que se requieren para avanzar de uno en uno, de dos en
'I
dos etc, de acuerdo a la suavidad q w s e desea obtener en los cambios que presenta el
objeto.
Para el modelado de objetos alfqfIexibles se aportó el seguimiento del objeto sin utilizar
alguna técnica de seguimiento específica, mediante la técnica de snakes. Esta trabaja en
forma parecida al proceso de inflar ,un balón
para adoptar y seguir al objeto en
movimiento, sin importar que el movimiento sea aleatorio, y sin necesidad de cálculos
~
adicionales de predicción de movimiento, explicado lo anterior permite obtener una
herramienta que modele en forma automática las deformaciones que sufre el objeto en cada
cuadro de imagen de la secuencia de video, por lo que la herramienta se muestra capaz de
modelar los cambios presentados por el 'objeto alJaf7erible.
6.4 TRABAJOS A FUTURO
El desarrollo de esta herramienta sirve para las siguientes investigaciones a futuro:
Modelado y reconocimiento de rostros humanos
Modelado y reconocimiento de personas en movimiento (motion tracking)
Modelado y reconocimiento de objetos
68
I
REFERENCIAS
Bibliografía
[Aminini 901 Amini AA, Weymouth TE, Jain RC. Using Dynamic Programming for
Solving Variational
Problems In vision. IEEE Transactions on Pattern Analysis and
Machine Intelligence,l990; 12(9):855-867.
[Anel, 981 J.Anel Carrasco-Ochoa, “Un Modelo de Clasificación Supervisada Basado en
Conjuntos de Representantes”, Memonas del 111Taller Iberoamencanode Reconocimientos
I
de patrones, México D.F. pp267-278,1998
[Bardinet, 961 Eric. Bardinet. Supercuadratics and Free-Form Deformations: a Global
Model to Fit and Track 3D Medical Data. First International Conference on Computer
Vision, Virtual Reality and Robotics ;in Medicine .(CVRMed’96),April
3-5,1996, Nice,
.
France.
[Davatzikos, 971 Crhis A. Davatzikos and Jeny L. Prince. An Active Contour Model for
Mapping the Cortex. Dept. of Electrical and Computer Engineering, University Baltimore
MD 21218. 1997.
[Decarlo, 961 D Decarlo and D Metaxas “Blended Deformable Models” IEEE trans
Pattern Analysis and Machine Intelligence Vol 18 pp. 443-448, 1996
[Gonzáles, 961 Rafael C. Gonzáles, Richard E. Woods, “Tratamiento digital de Imágenes”.
Editorial Addison Wesley, pp 212-213 ,1996.
[Kass, 881 M. Kass. A. Witkin and Terzopoulos Snakes: Active Contour Models,
Internationational Journal of Computer Vision 1, pp 321-331, 1988.
69
[Leymane, 951 F. Leymarie and M.D. Levine, Tracking Deformable ObJeCtS in the Plane
using an Active Contour Model, IEEE. Vol 15, No. 6 June 1995, pp 617-634.
[Magadán, 991 Magadán Salazar Andrea. "Reconocimiento de Rostros Invariante a
Expresiones Faciales", Tesis Para Obtener el Grado de MC en Ciencias Computacionales,
en el Centro Nacional de Investigación1y Desarrollo Tecnológico. Cuernavaca Morelos,
Noviembre de 1999.
[Peckar, 961 W. Peckar. FEM Two-step Parameter-Free Elastic Image Resgistration with
I
Pescribed Point Displacements. Department Of Computer Science University of Hamburg,
!
November 1996.
[J. Ross Quinlan, 921 J. Ross Quinlan C4.5 Programs For Machine Learning Morgan
Kaufman Publishers, 1992.
[Ruecker, 961 D. Rueckert and P. Burger Geometrically Deformable Templates for ShapeI
based Segmentation and Tracking in Cardiac MR Images, Pages 137-142, Berlin, Germany,
June 2 1-24 1996.
[Shah, 901 D.J. Williams, D.J. and M. Shah, "A fast algorithm for active contours." CVGIP:
Image Understanding. v. 55, n. 1, pp. 14-26, 1990.
[Szelisky, 951 R. Szelisky and S. Lavallee. Matching 3-d Anatomical Surfaces with NonRigid Deformations Using Octree-Splines. In Procedings of the IEEE Worshop on
Biomedical Image Analisis , Seattle Washingtong, June 1995.
[Seung, 971 Jong-Seung Park, Contour Motion Estimation in Sequential Images
Department of Computer Science and Engineering, Pohang University of Science and
i
Technology.IEEE trans. On PAMI, Vol 17, No. 3, Marzo 1997 pp. 294-302.
[Sulcloper, 991 José Ruiz Shulcloper, J. Francisco Martinez Trinidad, instituto politécnico
Nacional Enfoque lógico combinatorio :al reconocimiento de patrones, 1999.
70
[Vemuri, 20001 Baba C. Vemuri Snake Pedals: Compact and Versatile Geometric Models
with Physics-Based Control. Senior Member, IEEE Transactions on Pattern Analysis and
Machine, Vol 22 no. 5 May 2000.
[Xu, 981 Chenyang Xu and Jeny I,., Prince Snakes, Shapes, and Gradient Vector
Flow.1998, IEEE Transactions on Image processing,359-369, March 1998.
DIRECCIONES DE INTERNET
[Blake, 981 Blake A. Isard M. Contornos' Activos Spnnger,1998.
http://www.robots.ox.ac/-contours(Técnicas de aplicaciones graficas, Visión , Teoría de
control y Estadística visual de movimiento de formas)
[Kass, 971 CS 7322 Winter 1997 Modelos de contomos activos (Snakes) 1997.
http://www.cc.gatech.edu/classes/cs7322-97-springlpariicipants/irfan/lectures/lecture.~6/sn
akes.html.
[Shulze, 961 Snakes, Active Contours
Contornos Activos, usando una demostración en Java, Mark A. Schulze,26 de noviembre
1996.
http://www.markschulze.net/snakes/
[Xu, 20001 Gradient Vector Flow Active Contour - Chenyang Xu and Jeny L. Prince /
Image Analysis and Communications Laboratory / Johns Hopkins University
ttp://iacl.ece.j hu.edu/projects/gvU
[Young, 1993]Snakes, Active Contours, and Deformable Models, David Young, January
1993, revised Januaiy I994
http:l/www.cogs.susx.ac.uk/users/davidy/teachvision/vision7.html
71
'!
ANEXO A
BASE DE IMÁGENES
En las siguientes páginas se muestra la base completa de imágenes que fueron
utilizadas para el modelado de objetos alfaflexibles, se utiliza un incremento de dos
imágenes por cada iteracion en cada 'cuadro que se presenta para modelar el objeto
alfaflexible, debido a que si se incrementaba los cuadros de uno en uno no habría cambios
muy significativos.
12
caso I
73
Figura A.2 Modelado del objeto
I
I
.'I
74
Figura A.3 ContinuaciónI del caso 2, Modelado del movimiento de los labiosi con un poco de: ruido
'f