PDF de programación - Creación del framework nd-evm/kohonen para la representación, segmentación y compactación de secuencias de vídeo

UNIVERSIDAD TECNOL ÓGICA DE LA MIXTECA

“CREACI ÓN DEL FRAMEWORK nD-EVM/KOHONEN PARA LA
REPRESENTACI ÓN, SEGMENTACI ÓN Y COMPACTACI ÓN DE

SECUENCIAS DE VIDEO”

PROYECTO DE TESIS

PARA OBTENER EL GRADO DE

MAESTRO EN TECNOLOGÍAS DE C ÓMPUTO APLICADO

PRESENTA

ING. JOSÉ YOVANY LUIS GARCÍA

DIRECTOR DE TESIS

DR. RICARDO PÉREZ AGUILA

HUAJUAPAN DE LE ÓN, OAXACA, OCTUBRE DEL 2015

II

Tesis presentada el 19 de Octubre de 2015
ante los siguientes sinodales:

Dr. Felipe de Jesús Trujillo Romero
Dr. Santiago Omar Caballero Morales
Dr. Enrique Guzmán Ramírez
M.C. Gabriel Gerónimo Castillo

Director de tesis:
Dr. Ricardo Pérez Aguila

IV

Dedicatoria

A mis dos amores y la mayor fuente de motivación
para seguir adelante:

Maya y Gaby

de todo corazón

Yovany

V

VI

Agradecimientos

A mis padres María Concepción y José Domingo, por el apoyo incondicional y por comprender mi
deseo por seguir creciendo como persona y profesionalmente.

A mi esposa Gabriela, porque juntos todo es posible y por regalarme lo más hermoso que pudo
haber pasado, mi hermosa nena Maya.

A mi nuevo amor, Maya Gabriela, porque llegaste a nuestras vidas cambiando todo nuestro mundo
y porque ahora el panorama es prometedor y muy divertido.

A mi director de tesis Dr. Ricardo Pérez Aguila, por haber confiado en mis capacidades para
desarrollar este proyecto de investigación y por apoyarme en la comprensión de los fundamentos
teóricos.

VII

VIII

Resumen

Recientemente, las aplicaciones de imagen y video basadas en contenido, han recibido mucho
interés, debido a que entre sus aplicaciones destacan: recuperación y búsqueda, resúmenes,
análisis de eventos y edición, por mencionar algunas. Para su funcionamiento, estas aplicaciones
necesitan identificar lo que sucede en una escena de video, esto es el contenido de la escena.
Ello se logra abstrayendo el contenido semántico, el cual tiene su representación mediante
objetos de interés que conforman dicha escena. De estos objetos, se obtienen sus características
intrínsecas, que los describen de manera explícita y aportan información semántica. A partir de
esta información, se puede realizar procesamiento para interpretar los eventos que tienen lugar en
la escena. Es por ello que, una de las tareas más importantes para procesamiento de imagen y video,
es la separación de la información en sus partes constituyentes, esto es la segmentación de imagen
y video. El proceso de segmentación consiste en la partición de datos en grupos de información que
comparten características similares. Por ello, este proceso es crucial en la extracción de contenido
semántico, en procesamiento de información multimedia digital, reconocimiento de patrones y
visión por computadora. En base a lo anterior, este trabajo de investigación propone la creación
de un framework para representación, segmentación y compactación de secuencias de video. El
cual tendrá como objetivo principal el siguiente flujo de operación: “A partir de un video de entrada
proporcionar una versión segmentada y compactada del mismo”. Para la representación se propone
usar el Modelo de Vértices Extremos (n-Dimensional Extreme Vertices Model, nD-EVM) y para la
segmentación redes de Kohonen.

IX

X

Índice general

Dedicatoria

Agradecimientos

Resumen

Índice de figuras

Índice de tablas

Índice de algoritmos

Índice de códigos

I

Introducción

1. Planteamiento del Proyecto

1.1. Descripción del Problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.1. Un Nuevo Enfoque para la Segmentación de Video . . . . . . . . . . . . . . . .
1.2. Planteamiento del Proyecto de Investigación . . . . . . . . . . . . . . . . . . . . . . .
Justificación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.
1.4. Hipótesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5.1. Objetivo General
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5.2. Objetivos Específicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.6. Metas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.7. Limitaciones y Delimitaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.8. Metodología . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.9. Organización del Documento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

II Marco Teórico

2. Segmentación de Video y sus Aplicaciones

2.1. Procesamiento de Imagen y Video . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2. Framework General para Sistemas de Procesamiento de Imagen y Video . . . . . . .
2.3. Definición Formal del Problema de Segmentación . . . . . . . . . . . . . . . . . . . .
2.4. Aplicaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3. Modelo de Vértices Extremos en el Espacio n-Dimensional (nD-EVM)

3.1.
3.2. Fundamentos de los Pseudo-Politopos Ortogonales n-Dimensionales (nD-OPPs)

Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. .

XI

V

VII

IX

XV

XIX

XXI

XXI

1

3
3
4
5
6
6
6
6
7
7
7
8
9

11

13
13
14
15
16

19
19
20

XII

Índice general

3.3. Fundamentos del modelo nD-EVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4. Secciones y Slices de un nD-OPP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5. Cálculo de Couplets y Secciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6. Operación XOR Regularizada para el nD-EVM . . . . . . . . . . . . . . . . . . . . . . .
3.7. Algoritmos del nD-EVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.7.1. Algoritmo de Operaciones Booleanas
. . . . . . . . . . . . . . . . . . . . . . .
3.7.2. Operaciones Booleanas para 1D-EVMs . . . . . . . . . . . . . . . . . . . . . . .
3.7.3. Ejemplo de Operaciones Booleanas para dos 3D-EVMs . . . . . . . . . . . . .
3.7.3.1. Aplicación de la Operación Unión . . . . . . . . . . . . . . . . . . . .
3.7.3.2. Aplicación de la Operación Intersección . . . . . . . . . . . . . . . .
3.7.3.3. Aplicación de la Operación Diferencia . . . . . . . . . . . . . . . . . .
3.7.3.4. Aplicación de la Operación XOR . . . . . . . . . . . . . . . . . . . . .
3.7.4. Algoritmo de Cálculo de Contenido n-Dimensional
. . . . . . . . . . . . . . .
3.7.5. Algoritmo de Cálculo de Compacidad Discreta . . . . . . . . . . . . . . . . . .

4. Mapas Auto-Organizados de Kohonen

Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.
4.2. El Modelo de Kohonen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.1. Proceso de Competencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.2. Proceso de Cooperación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.3. Proceso de Adaptación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.4. Algoritmo de Entrenamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . .

III Desarrollo

5. Procesamiento de video usando el modelo nD-EVM

5.1. Representación de Secuencias de Frames . . . . . . . . . . . . . . . . . . . . . . . . .
5.1.1. Representación de Frames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.1.2. Cálculo de Couplets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.1.3. Archivos Binarios de los Couplets . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2. Segmentación de Video usando Compacidad Discreta y Mapas Auto-organizados de
Kohonen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.1. Generacion de Máscaras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.2. Cálculo de Compacidad Discreta para Sub-animaciones
. . . . . . . . . . . .
5.2.3. Generación del Conjunto de Entrenamiento a partir de la Compacidad
Discreta de Sub-animaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . .

65
5.2.4. Agrupamiento de Sub-animaciones con un Mapa Auto-Organizado de Kohonen 68
5.2.5. Estimación del Tiempo de Ejecución . . . . . . . . . . . . . . . . . . . . . . . .
70
5.2.6. Cómputo Concurrente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
71

23
25
26
27
28
30
31
34
35
37
38
39
41
42

47
47
48
49
49
50
50

53

55
55
56
60
61

63
63
64

6. Implementación en C++

6.2.

6.1.

75
Implementación de Métodos del nD-EVM . . . . . . . . . . . . . . . . . . . . . . . . .
75
6.1.1. Obtención de Secciones a partir de Couplets y viceversa . . . . . . . . . . . . .
77
6.1.2. Obtención de una Secuencia de Secciones y una Secuencia de Couplets
78
. . .
79
6.1.3. Operaciones Booleanas
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.1.4. Cálculo de Contenido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
82
6.1.5. Cálculo de Compacidad Discreta . . . . . . . . . . . . . . . . . . . . . . . . . .
83
Implementación de los Métodos para Procesamiento de Video . . . . . . . . . . . . .
85
6.2.1. Generación de una animación en el nD-EVM a partir de una secuencia de frames 85
6.2.2. Generación de máscaras nD . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
86
6.2.3. Convolución de una máscara y una animación en el nD-EVM . . . . . . . . .
87
6.3. Generación de Ejecutables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
91

7. Pruebas y Resultados

93

Índice general

XIII

7.1. Pruebas con un Video de Vigilancia Aérea . . . . . . . . . . . . . . . . . . . . . . . . .
94
95
7.1.1. Pruebas con 5 neuronas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .