Presenta: Leopoldo Hernández Guevara

UNIVERSIDAD DON BOSCO

MAESTRIA EN MANUFACTURA INTEGRADA POR COMPUTADORA

ASIGNATURA: SISTEMAS DE VISION ARTIFICIAL

Miércoles 7 de enero 2015.-

Comparación y reconocimiento

de patrones (Pattern Matching)

Clasificadores, Correlación

El Reconocimiento de Patrones es una disciplina

encargada de asignar a los objetos una clase determinada

(clasificación).

Los objetos no sólo proceden de las imágenes sino

también de señales unidimensionales (p.ej. reconocimiento

de voz o patrones en el electrocardiograma, ECG) o en

cualquier otra medida sobre los objetos.

La tarea de clasificación es una combinación del vector

de características de los objetos y del conocimiento a

priori que se tenga del universo del problema.

Para poder asignar una etiqueta de clasificación a un

objeto se debe de tener reglas de pertenecías a cada

clase. Estas reglas se consiguen a través del

conocimiento que se tenga de cada clase.

Los enfoques que se pueden emplear para la

clasificación se basan bien en una función discriminante

que divida el espacio de las características

(clasificadores estadísticos) o bien empleen relaciones

geométricas asociadas a los objetos (clasificadores

sintácticos).

Existe una tercera vía basada en las redes neuronales

artificiales, las cuales se parecen a los clasificadores

estadísticos, en cuanto que tratan de particionar el

espacio de las características, pero emulando a los

sistemas biológicos, empleando etapas previas de

aprendizaje.

TIPOS DE CLASIFICADORES

Clasificadores a priori y a posteriori.

Los clasificadores apriorísticos construyen el clasificador en un solo

paso, utilizando la muestra de aprendizaje para el cálculo de las

funciones discriminantes. Los clasificadores a posteriori se

construyen siguiendo un procedimiento iterativo, en el cual el

clasificador aprende a reconocer de una manera progresiva los

patrones de la muestra de aprendizaje.

Clasificadores deterministas y no deterministas (probabilistas).

Atendiendo a la forma en que se distribuyen los patrones de la muestra

se puede hablar de que se cumple o no una hipótesis determinista (ej.

distancia)

Clasificadores supervisados y no supervisados.

Según la información que se proporciona en el proceso de

construcción del clasificador se puede hablar de dos tipos de

clasificadores: con maestro o supervisados, sin maestros o no

supervisados.

Adquisición de la imagen

Pre-procesado

Segmentación Extracción (matching)

Reconocimiento (clasificación)

SECUENCIA DEL PROCESAMIENTO DE RECONOCIMIENTO DE PATRONES

Bajo Nivel

Nivel Intermedio

Alto Nivel

PATRONES, PATTERNS O TEMPLATES

Para el reconocimiento de patrones, es importante que:

• Patrones que describen objetos de una misma clase,

presenten características similares.

• Patrones que describen objetos de diferentes clases

presenten características diferenciadas

EN TODO CASO DEBERA BUSCARSE LA

CARACTERISTICA MAS DISCRIMINANTE DEL

PATRON, O UNA COMBINACIÓN DE

CARACTERISTICAS QUE DEFINAN POR

COMPLETO EL PATRON SIN LUGAR A

CONFUSION, O EN TODO CASO, SEA MINIMA.

ESTA PUEDE SER:

COLOR, TAMAÑO, DISTANCIA, ETC.

COMPARACION DE IMÁGENES

Cuando se necesita comparar una imagen con otra, o bien

identificar determinado patrón conocido presente en una imagen,

siempre surge la pregunta de como se puede medir la semejanza

entre dos determinadas imágenes.

Pareciera se la forma más sencilla , si dos imágenes son iguales,

su diferencia debe ser cero. Esto podría ser válido en el caso de

imágenes consecutivas con una iluminación constante. Sin

embargo, esta forma de comparación tan sencilla no es válida, por

ejemplo, al cambiar la iluminación entre imágenes , o un pequeño

cambio como una rotación o desplazamiento de la imagen.

La idea fundamental de la comparación de imágenes

(template o pattern matching) es que el patrón a encontrar se

mueve sobre todos los pixeles de la imagen como si fuera un

filtro lineal y se mide la semejanza entre el patrón y los

correspondientes pixeles de la imagen que abarca.

Es necesario asegurarse que esta medida sea confiable en

casos que la imagen patrón esté escalada, rotada o

distorsionada.

A continuación se analizan algunas formas de comparación

utilizadas.

Geometría del problema de la comparación de imágenes. La imagen de

referencia R(i,j) es desplazada a través de la imagen I(x,y), en donde el

origen de la imagen (0,0) sirve como punto de referencia. El tamaño entre

las imágenes I y R determinan el campo de búsqueda para la realización

de la comparación

COMPARACION O CLASIFICACION DE IMÁGENES

UTILIZANDO DISTANCIA ENTRE PATRONES

Este método de matching utiliza el calculo del punto

donde existe la máxima coincidencia entre la imagen a

evaluar I(x,y) y la imagen del patrón o referencia R(i,j) para

lo cual es necesario determinar la distancia entre la

referencia desplazada y la sección correspondiente de la

imagen para cada posición.

Para medir la distancia entre dos funciones

bidimensionales existen diferentes definiciones, a

continuación se mencionan algunas de las principales:

a. La suma de la diferencias:

b. El máximo de las diferencias:

c. La suma de las distancias cuadráticas:

SUMA DE LAS DIFERENCIAS

Tomaremos como ejemplo las siguientes imágenes para

comparación y referencia:

Donde (a) es la imagen de comparación donde se realizará la

búsqueda y (b) la imagen de referencia o patrón.

Al aplicar el siguiente algoritmo en MATLAB para comparar la

imagen de referencia con las diferentes secciones de la imagen

principal:

[m n]=size(Im);

[mt nt]=size(T);

Imd=double(Im);

Td=double(T);

suma=0;

for re=1:m-mt

for co=1:n-nt

for re1=0:mt-1

for co1=0:nt-1

suma=abs(Imd(re+re1,co+co1)-Td(re+re1,co+co1))+suma;

end

end

da(re,co)=suma;

suma=0;

end

end

Imagen resultante, donde se puede apreciar en color más oscuro

las zonas de distancia de suma de diferencias más pequeños, lo

que significa que existe mayor coincidencia entre esa región y la

referencia.

Resultados de aplicar las fórmulas de (a) máximo de las

diferencias y (b) distancia de la suma de las distancias

cuadráticas.

DISTANCIA Y CORRELACION

La ecuación que define la suma de las distancias cuadráticas,

llamada también distancia euclidiana, es especialmente

importante debido a sus propiedades estadísticas.

Para esto es necesario minimizar el cuadrado de esta distancia

de la siguiente forma:

La expresión B en la ecuación anterior representa la suma al

cuadrado de todos los valores de la imagen de referencia R(i,j).

Como estos valores no dependen del desplazamiento (r,s) este

factor es constante, por lo que B puede ser ignorado par a la

minimización de la expresión.

C(r,s) corresponde a la llamada correlación cruzada entre I(x,y) y

R(i,j). Dicha correlación cruzada se define como:

Debido a que las imágenes I(x,y) y R(i,j) son consideradas cero

sin sus dimensiones, la ecuación puede reformularse como:

La correlación es fundamentalmente la misma

operación que la convolución excepto que en la

convolución el kernel de la operación se

encuentra invertido sobre si mismo.

También es posible aplicar la correlación

cruzada normalizada para minimizar el efecto

en los cambios de intensidad de pixeles.

BIBLIOGRAFIA

• Procesamiento digital de imágenes usando MATLAB

y SIMULINK, Cuevas,Zaldivar y Pérez,

• Digital Imaging Processing Using MATLAB, Gonzalez

y Wood

• Apuntes de Visión Artificial, Platero

• Curso de Visión Artificial, Universidad Rey Juan

Carlos