centro nacional desarrollo · 2014-02-13 · s.e.p. s.e.i.t. d.g.i.t. centro nacional de...
TRANSCRIPT
-
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 E S I S P A R A O B T E N E R E L G R A D O D E M A E S T R O EN C I E N C I A S EN C I E N C I A S C O M P U T A C I O N A L E S
P R E S E ’ N T A :
EDUARDO QRBE TRUJiLLO
DIRECTORES DE TESIS DR. RAUL PINTO ELIAS
CUERNAVACA, MORELOS JULIO DE 2003
-
IMITmuhn I-f
FORMULARIO C3 REVISIÓN DE TESIS
I iw€srGU%rrW&hu
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. CP. 62490. CUERNAVACA. MOR. - MEXICO lELS.(777)312 2314.318 7741,FAX(777) 312 2434 EMAIL pazos~rdcenidet.com.mx
-
w ~ y c m ~ D ( ~ w c I u o N ~ 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 [email protected]
-
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
-
Lista de figuras
Lista de tablas
Lista de ecuaciones
CAPITULO 1
INTRODUCCI~N
1.1 Antecedentes
I .2 Descripción del problema
1.3 Propuesta de solución
1.4 Metodología de solución
1.5 Objetivo
1.6 Alcances
1.7 Producto esperado
1.8 Disciplinas involucradas
1.9 Aplicaciones
1.10 Organización de la tesis
TABLA DE CONTENIDO V
vii ...
V l l l
2
5
5
6
7
7
7
8 8
9
CAPITULO 2 ESTADO DEL ARTE
2.1 Estimación de movimiento de contornos en imágenes secuenciales I I
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
2.5 Snakes, formas, y flujo del vector gradiente 2.6 Un modelo de contorno activo para dibujar la corteza
2.7 Contornos Activos y Modelos defomables
2.8 Modelo de Clasificación Supervisada Basado en Conjuntos de Representantes 2.9 Enfoque lógico combinatorio al reconocimiento de patrones
2.10 Filtro pasa alto
CAPITULO 3
SNAKES
3.1 Introducción
3.2 Preprocesamiento de snakes
3.2.1 Gradiente
3.3 Fundamentos de snakes
3.3.1 Fundamentos matemáticos
3.3.2 Pseudocódigo
3.4 Ejemplos del funcionamiento
3.5 Comentarios
CAPITULO 4
MODELADO
4.1 Selección de rasgos
4.2 Enfoque lógico combinatorio
4.3 Teoría de testores 4.3.1 Algoritmo BT
4.3.2 Importancia de los testores tipicos
4.4 Rasgos a modelar
4.4.1 Color por histograma 4.4.2 Centro de gravedad del snake relacionado con "x" y ')"
4.4.3 Área
4.4.4 Distancias entre todos los puntos de " x" y ')" del snake
14
15
i6
17
17
18
18
19
20
20
22
23
29
20
33
35
36
38
39
46
47
48
49
49
49 . . . 111
-
4.5 Ejemplo del modelado de un objeto alfafiexible
4.6 Comentarios
CAPITULO 5
EXPERIMENTACI~N
5.1 Introducción
5.2 Casos de estudios realizados
5.3 Análisis de los resultados
CAPITULO 6
CONCLUSIONES
6.1 Introducción
6.2 Metas alcanzadas
6.3 Producto esperado
6.4 Aportaciones
6.5 Trabajos a futuro
REFERENCIAS
ANEXO A
49
53
54
55
65
66
67
67
68
68
69
12
i Y
-
LISTA DE FIGURAS Figura Descripción Página
Figura 1.1
Figura 1.2
Figura 3.1
Figura 3.2
Figura 3.3
Figura 3.4
Figura 3.5
Figura 3.6
Figura 3.8
Figura 3.9
Figura 3.10
Figura 3.11
Figura 3.12
Figura 4.1
Figura 4.2
Figura 5.1
Figura 5.2
Figura 5.3 Figura 5.4
Figura A.l
Figura A.2
Figura A.3
Figura A.4
Cambios que presenta la mano en los movimientos que realiza.
Esquema de solución de este trabajo.
Imagen de 24 bits, la cual es procesada a niveles de grises.
Resultado del proceso con filtro gradiente.
El snake adopta cualquier forma, como si fuera agua, basado en la
4
6
22
22
23
minimización de la energía:
Evolución de la energía externa usando snakes. 23
Se muestra la vecindad de los nodos. 26
Se muestran los diferentes resultados al cambiar los valores de aJ3,y. 30
Inicialización del snake. 31
Valores iniciales a) Alfa=lO Beta=l b) Alfa=20, Beta = I 31
Resultado del snake con los siguientes valores A) a= l , p= l
Secuencias de imágenes utilizando la técnica del snake.
imagen con su respectivo histograma.
El snake se adecua a la forma del movimiento de los labios
Se seleccionan los puntos alrededor de los párpados.
Imágenes donde a)l Inicialización del snake b) resultado del snake. 32
32
B) a=I,p=2 C) a=1$=3.
33
48
SO
55
60
62 64
73
74
75
Lectura de los labios con ruido.
Modelado de labios sin mucho ruido. Modelado de la cabeza en un ambiente natural.
:I
Imágenes del modelado del parpado del caso I .
Modelado del objeto alfaflexible para el caso 2. Continuación del caso 2, Modelado del movimiento de los labios con un poco
de mido.
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.
Figura A.6 Continuacion del caso 4, Modelado del movimiento de la cabeza utilizando u n
ambiente natural.
77
78
Y I
-
LISTA DE TABLAS Tablas Descripción Página
Tabla 3.1 Esta máscara obtiene las líneas verticales 21
Tabla 3.2 El cálculo de esta máscara permite obtener líneas horizontales. , 22 Tabla 4.1
Tabla 4.2
Tabla 4.3
Tabla 4.4
Tabla 4.5
Tabla 4.6
Tabla 4.7
Tabla 5.1
Tabla 5.2
Representación de los rasgos y clases de los objetos.
Representa una clase con tres objetos.
La siguiente clase con dos objetos.
Resultado de la matriz de diferencia.
Se muestra una fila básica, esta fila básicaes S14.
Resultado de la matriz básica.
Testores típicos obtenidos del segundo caso.
Distancias de los puntos que conforman el snakes alrededor del snake.
Cuatro colores que mas aparecen del formato R.G.B que modela la herramienta.
3X
40
41
41
4 2
44
51
56
57
Tabla 5.3 Matriz generada mediante las distancias de los puntos mas los rasgos de la tabla 57
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
Ecuación 3.2
Ecuación 3.3
Ecuación 3.4
Ecuación 3.5
Ecuación 3.6
Ecuación 3.7
Ecuación 3.8
Ecuación 3.9
Gradiente en dirección de x .
Gradiente en dirección dey.
Cálculo del gradiente con su máscara en dirección de x
Cálculo del gradiente con su mascara en dirección dey
Ecuación del snake por [Kass, 871.
Cálculo de la energía interna.
Ecuación del snake por [SHAH, 921.
Ecuación de la energía funcional del snake.
Cálculo de la ecuación de la distancia media de los puntos del snake menos
los puntos vecinos.
Ecuación 3.10 Cálculo de distancia media de los puntos del snake.
Ecuación 3.11 Normalización de la ecuación (3.9). ij
Ecuación 3.12 Cálculo de energía curva.
Ecuación 3.13 Normalización de la ecuación (3.12).
Ecuación 3.14 Obtención de la energía minima y máxima de la imagen del gradiente.
Ecuación 3.15 Normalización de las magnitudes del gradiente
Ecuación 3.16 Ecuación de la curvatura del objeto.
Ecuación 4.1 Obtención del peso informacional.
Ecuación 4.2 Obtención de la longitud del testor típico.
I!
21
21
21
21
23
24
25
26
21
21
27
2 1
28
28
28
28
46
41
\ i l l
-
CAP~TULO 1
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.
http://resoluc��n.de
-
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
una adecuada interpretación, de los rasgos que integran a los objetos de las imágenes
digitales.
A
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
humano, una lombriz, etc. I,
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~N DEL 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~A DE SOLUCI~N Estos pasos se muestran de manera gráfica en la figura 1.2.
a
a
a . a .
Carga el video en formato AVI.
Selecciona el objeto o los objetos a modelar.
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. a Obtención del modelo del objeto.
I Carga el video con formato :vi
+ Selecciona los objetos a modelar
Procesamiento de cada cuadro del
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
MODELO DEL OBJETO
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.
Se usará un conjunto técnicas que contemplen las características de extracción
de los rasgos.
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.
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.
0
0
o
1.7 PRODUCTO ESPERADO o Una herramienta, que de manera automática obtenga el modelo de un objeto
alJ¿¿jlexi ble.
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 el 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,~al aplicar 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~N DE 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ÍTULO 1 2 O DEL ARTE
En este capítulo se realiza un breve análisis de algunos artículos,
investigaciones describen problemas con objetos deformables, se describen las técnicas
se utilizan para obtener las caractensticas de los objetos que se deforman en un intervalo
tiempo, buscando obtener el modelo de los mismos.
ESTA1
cuyas
que de
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
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
curvatura del contorno que permite localizar los correspondientes puntos en el contomo
la siguiente imagen.
, . . . . ..
'I.!
de
1 I
-
En esta técnica se incluyen métodos numéricos donde la ecuación es discreta, se
I
la siguiente imagen.
-
2.2 Plantillas deformables geométricamente, basadas
en imágenes cardiacas [Rueckert, 961
Propone el uso de una minimización de energía,
objetos deformables bajo la influencia de la dirección de
forma de la plantilla es medida por una función de las dos
en segmentación y seguimiento
la cual puede utilizarse en los
la imagen. La degradación de la
formas en 2D.
12
cristalino el cual minimiza su energía. Usando esta aleatoriamente nuevas configuraciones de la probabilidad
Relajación deierminisiica. Para seguir un objeto
analogía, el algoritmo genera
de distribución o de deformación.
en una secuencia de imágenes
-
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.
humano, se basa en contornos activos, se realizaron pruebas en segmentación
I Plantillas deformables no rígidas como el utilizando la distribución de Fourier. En
y tracking de superficies relacionadas al
Este trabajo permite para compararla con
se ha desplazado o qué dirección está se deforman mediante la minimización
la siguiente imagen, y así obtener cuántos
tomando. También propone segmentar
2.3 Parámetros libres para imágenes elásticas con puntos
con puntos descritos. Este
de energía que se usa en los snakes.
descritos y desplazamientos [Peckar, 961 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 el snake, en forma iterativa, realizando
aproximaciones, y usando parámetros
constantes.
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. I. 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 contenei- informació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. I I
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, además de que dicha operación debe realizar 30 cuadros por segundo. Por ello en esta
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.
' !
I
I
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
direcciones, Este tipo de detectores es aplicado a cada punto de la imagen para calcular el
borde independientemente de su orientación.
I . I .
20 i
-
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 mkimo 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
utilizando una matriz de 3x3, los valores de las máscaras para h ly 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 mi ”““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
-
,,--Inicia del snake n
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.
Eimage da origen a las fuerzas de la imagen
E,,,, da origen a las restricciones de las fuerzas y se tiene que:
donde:
Vs es la primera derivada
V,, 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
diferencia finita, (v,? = (xi - xi-1) + (yi - ~ 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
a y Este método utiliza el mismo valor para a y pen 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.
' 1 1
. .
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 (3.7) O
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
ecuación, se considera la diferencia .del promedio de las distancias entre los 1 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, li imación de la cuma multi licada or una iíjí r(ue lusri' di HM iii?iii~'rl! fii Ililii I I P P
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 li del gradiente. Para dar una magnitud (mag) en un punto y el máximo (máx.) y
mínimo (min.) lmk.nrLl en 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.
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 = O para la siguiente iteración. !I I
I
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 I término de curvatura y el último de imagen, ver ecuación (3.8).
(3.8)
Donde afi) y Pfi) y &)son constantes. Se utilizan valores que inicializan G I , ,&O. cuando una esquina este presente en el punto actual se inicializa a I o mayor de I en otro
I 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 K . , E . = d V.-^. I cont,j - 1 J 1-1
Donde d e s la distancia media entre sus puntos es decir:
11
(3.9)
'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 cont,j max E = (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)
2 7
-
Esta energía de la c b a es normalizada en su vecindad K, como sigue:
E (3.13) Cum, 1 E=-
j E K. (E .) 1 CUrV,J
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:
s i G m m - b m i n
-
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 } / I punto 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 / / en 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
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
1
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 o
a>P>Y
0.4.0.6.1.0 0.6.0.4.1.0 0.8.0.2.1.0 ' .O,om 1.0 1.0, 0.0,l.O
a>P>Y a,P,u a>P>Y a , P , r a,P,u Figura. 3.6 Se muestra los resultados al cambiar los valores de a.8.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 .
I
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
se pueden observar en las figuras.(3.8, 3.9, y 3.10). El objetivo de este experimento es el
I
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:
31 Figura 3.9 a) Alfa=iO Beta=¡. b) Alfa=20. Beta=l
-
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
presentará el objeto. Los snakes se amoldan fácilmente a los cambios del contorno que
I
ningún conocimiento apriori del objeto y tampoco se requiere saber cuántos cambios !
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
adecuada al objeto que se va a modelar. Cuando se desea modelar un objeto, el experto
I/
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 información pero, que sin embargo esté completa o sea la más discriminante para un
reconocimiento posterior del objeto.
'I I
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.
I 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
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í/¿¿flexible es 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 11 36
-
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
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:
I
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.
http://conjunto.de
-
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
X I ... XII Raseos
E1,l 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 fesfor y 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
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).
t ./
' t 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,
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 1 1 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
-
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
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 I a(i+l)=000101, a(i+2)=000110, a(i+3)=000111, ya que así fue diseñado este
!I
permite diferenciar un objeto que pertenece a una clase de otro que no pertenece a la
11
I
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 11 I . 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 1 1 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
-
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 10s siguientes 2 n-k - I n-upios son listas restores pero no típicos. f
I 42 L
-
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
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.
I
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
-
I
Existe al menos una
-
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 V j = 1, ..., n ( a . A a. )=O
J 1 Sea a=(&/, ...,a',) talque.
i!
a . s i j < k
a.= 1s i j = k 1 ' lO:ij>k
Entonces ninguna lista comprendida entre a y a' es una lista testor
d) Algoritmo
Paso ¡. Se genera la primera lista a no nula de longitud n. I 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 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
objeto que se está modelando.
I
I 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= (al,.. .,an) no es lista testor y que para u y a se satisface lo siguiente:
V j = 1, ..., n ( a . A u . ) = O
Sea a= (a'!, ..., dn) tal que. J 1
a . s i j < k
a . = I s i j = k J I l O l i j > k
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. '.
~ 0 1 1 0 0 0 .
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 1 1000. 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).
Se aplica la proposición 4 Paso 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 11 1 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,x4 en 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:
1 = Y -
(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
el rasgo X, , sea más importante sin embargo Xj muestra un valor mayor X2, ya que X, necesita de una variable adicional mientras que XS necesita dos variables adicionales, se
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 4 p( 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