IV.9 Sistema Evolutivo
Reconocedor
de Textos
Jesús
Manuel Olivares Ceja*
Resumen
En muchas aplicaciones informáticas se requiere de interpretar información como señales, voz, sonido, etc., para esto existen diversas técnicas, se presenta aquí una propuesta para el reconocimiento de símbolos basada en matrices evolutivas. Para esto se calcula la distancia entre la entrada y cada patrón de la matriz evolutiva y se selecciona el de mayor similaridad; sino se alcanza el mínimo de semejanza aceptable se anexa la entrada como patrón nuevo. Una variante del método presentado puede aplicarse al reconocimiento de otras señales como voz, imágenes de colores, etc.
Introducción
En muchas aplicaciones informáticas se requiere de poder interpretar
información como señales, imágenes, voz, sonido, etc. asignándole un
significado a cada una. Existen diversas alternativas para realizar lo
anterior, en este trabajo se presenta una basada en matrices evolutivas.
En este tipo de problemas
lo primero que se debe hacer es percibir la información mediante el sensor
apropiado: cámara de vídeo, micrófono, scanner, transductor de presión, etc.,
luego se digitaliza y posteriormente se aplica alguna técnica de
reconocimiento.
Existen técnicas de
reconocimiento de patrones basadas en redes neuronales, otras siguen el enfoque
del reconocimiento sintáctico de patrones.
* Jesús Manuel Olivares Ceja escribió este trabajo cuando
comenzaba sus estudios de Doctorado en Ciencias de la Computación del Centro de Investigación en
Computación (CIC) del Instituto Politécnico Nacional en diciembre de 1996
La propuesta que se expone
en este documento se basa en matrices evolutivas, las cuales surgen de la
integración de estudios sobre redes neuronales, conjuntos difusos y sistemas
evolutivos.
I
Adquisición/Digitalización de la Información
En varias aplicaciones informáticas se requiere de interpretar
información proveniente de diversas fuentes como son señales, imágenes, voz,
sonidos, presión, temperatura, etc. La información puede recibirse en forma
analógica o digital, mediante un sensor apropiado. En caso de ser analógica
debe digitalizarse, es decir convertirla a números dentro de un intervalo dado
indicado como [a,b]. La información digitalizada se puede procesar entonces
mediante una computadora digital (figura 1).
|
|
|
|
|
|
SEÑAL DIGITALIZADA: |
1 0 0 1 0 0 ¼ |
0 0 0 24 24 0 ¼ |
0 2080 50 30¼ |
|
INTERVALO: |
[0,1] 1 bit/pixel |
[0,255] 8 bits/pixel |
[0,65535] 16 bits/muestra |
|
SIGNIFICADO: |
Letra: X |
Imagen: Elefante |
Sonido: Hola |
Figura 1. Información y su
digitalización
La información digitalizada
se coloca en un vector para usarla como entrada al reconocedor evolutivo y que este indique el significado asociado a
la información de entrada o bien que reestructure la matriz evolutiva para que
se incluya la entrada nueva (figura 2).
Significado Matriz Evolutiva
Figura 2. Reconocedor Evolutivo
Para convertir a un vector
una matriz, cada fila (renglón) de información se coloca uno delante del siguiente,
como se muestra en el ejemplo del símbolo 2 digitalizado (figura 3).
Digitalización
|
|
1 |
1 |
1 |
1 |
0 |
|
|
0 |
0 |
0 |
0 |
1 |
|
|
0 |
1 |
1 |
1 |
0 |
|
|
1 |
0 |
0 |
0 |
0 |
|
|
1 |
1 |
1 |
1 |
1 |
Vectorización
|
|
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
Figura 3. Vectorización del
símbolo 2 digitalizado
II Búsqueda /Aprendizaje del Patrón
La señal digitalizada se normaliza para obtener valores en el
intervalo [0,1] dividiendo cada uno de los elementos que forman al vector (Xi)
entre el valor máximo que puede tomar la señal, para el ejemplo de la figura 3,
el valor máximo es 1, dado que se trata de una imagen binaria.
El vector normalizado se
compara contra cada uno de los patrones almacenados en la matriz evolutiva, la
cual consiste de una columna de patrones, un umbral y el significado de cada
elemento de la misma (figura 4). El umbral indica cuantos patrones han
coincidido con el que se muestra ahí.
|
|
x0 |
x1 |
x2 |
x3 |
x4 |
. . . |
xn-1 |
h |
significado |
|
|
2 |
3 |
3 |
3 |
2 |
|
0 |
3 |
tres |
|
|
2 |
1 |
2 |
2 |
0 |
|
2 |
2 |
cuatro |
|
|
2 |
4 |
0 |
0 |
0 |
|
1 |
4 |
uno |
|
|
|
|
|
|
|
|
|
|
|
Figura 4. Una matriz evolutiva
Para comparar con cada patrón se usa la distancia siguiente:
|
|
n
- 1 |
|
|
S
= |
å 1 - |
½Xi
¸ max(X) - xi ¸ h½ |
|
|
i=0 |
|
donde n es el número de elementos que tiene el vector de entrada (X)
y coincide con el número de elementos de cada patrón (x) de la matriz
evolutiva; S, es la suma de las semejanzas; max(X), es el valor máximo que
puede tomar un elemento del patrón; el término que se suma (dado como 1 - el
valor absoluto de la diferencia) es la semejanza entre la entrada y el patrón
de la matriz evolutiva.
Para conocer el porcentaje
de semejanza entre 0 y 100% se procede a calcular el factor de semejanza (a) como
sigue:
a = S ¸ n * 100%
Para cada fila de la matriz
evolutiva se obtiene el factor a. De todos los a, se selecciona el mayor y se compara contra el porcentaje mínimo de
semejanza aceptable (d, que debe indicar el usuario para su tipo de información que
maneja). Si a ³ d, entonces se refuerza el patrón existente en la matriz evolutiva
sumando el valor de cada Xi y sumándole uno al umbral (h). Si a < d se
solicita al usuario que indique el significado del símbolo desconocido y se
quiere anexarlo en la matriz evolutiva, si lo adiciona, h es uno, significado,
lo digita el usuario y cada xi del patrón nuevo se copia de cada Xi
del vector de entrada.
Un ejemplo del cálculo de
semejanza es el siguiente: supóngase que se tiene en la entrada el vector del
patrón 2 (figura 3), y en la matriz evolutiva se tiene un patrón llamado tres
con umbral 3 y digitalizado como se observa en la figura 5
|
2 |
3 |
3 |
3 |
2 |
0 |
0 |
0 |
1 |
2 |
0 |
2 |
3 |
3 |
1 |
0 |
0 |
0 |
0 |
3 |
2 |
3 |
3 |
3 |
0 |
Figura 5. Patrón llamado tres en la matriz evolutiva con h=3
Para obtener la semejanza
entre ambos patrones se calcula la semejanza para cada punto con la fórmula
indicada anteriormente como sigue:
S = (1 - ½1¸1 - 2¸3½) + (1 - ½1¸1 - 3¸3½)
+ (1 - ½1¸1 - 3¸3½) + (1 - ½1¸1 - 3¸3½)
+ (1 - ½0¸1 - 2¸3½) + (1 - ½0¸1 - 0¸3½)
+ (1 - ½0¸1 - 0¸3½) + (1 - ½0¸1 - 0¸3½)
+ (1 - ½0¸1 - 1¸3½) + (1 - ½1¸1 - 2¸3½)
+ (1 - ½0¸1 - 0¸3½) + (1 - ½1¸1 - 2¸3½)
+ (1 - ½1¸1 - 3¸3½) + (1 - ½1¸1 - 3¸3½)
+ (1 - ½0¸1 - 1¸3½) + (1 - ½1¸1 - 0¸3½)
+ (1 - ½0¸1 - 0¸3½) + (1 - ½0¸1 - 0¸3½)
+ (1 - ½0¸1 - 0¸3½) + (1 - ½0¸1 - 3¸3½)
+ (1 - ½1¸1 - 2¸3½) + (1 - ½1¸1 - 3¸3½)
+ (1 - ½1¸1 - 3¸3½) + (1 - ½1¸1 - 3¸3½)
+ (1 - ½1¸1 - 0¸3½)
S = 2¸3 + 1 + 1 + 1 + 1¸3 + 1 + 1 + 1 + 2¸3 + 2¸3 + 1 + 2¸3 + 1 + 1 +2¸3 + 0 + 1 + 1 + 1 + 0 + 2¸3 + 1 + 1 + 1 + 0
de donde resulta:
S = 19+1¸3 @ 19.3333
por lo que el factor de semejanza es:
a = 19.3333 ¸ 25 * 100% = 77.33%
Si d = 95%
entonces como a < d y suponiendo que con el
patrón llamado tres es con quien tuvo la máxima semejanza (el mayor a),
entonces pide al usuario que digite el significado de la entrada y se adiciona
como un renglón más en la matriz evolutiva. Si en caso dado, hubiera resultado a ³ d, la
respuesta hubiera sido, “es un tres”.
III Eliminación de Ruido
Después de un proceso de reconocimiento /reforzamiento los patrones
de la matriz evolutiva pueden tener un umbral (h) grande como 50000, en estos
casos lo que puede hacerse es restar un factor (por ejemplo 40000), los
elementos que resulten negativos se asignan con cero, de esta forma algunos
puntos que dentro del patrón sólo eran ruido se eliminan quedando únicamente
los puntos relevantes del patrón.
IV Un Programa que Reconoce Vectores
Digitalizados
En el listado 1, se muestra un programa que reconoce símbolos de
acuerdo a lo presentado en la sección 2 de este documento. La entrada es un
vector con 25 elementos, nombrado Xi cada elemento (se supone que la información está digitalizada
y vectorizada).
Listado 1. Un programa basado en matrices evolutivas para el reconocimiento de símbolos:
#
include <stdio.h>
#
include <string.h>
#
include <conio.h>
#
include <stdlib.h>
#
include <ctype.h>
// ENTRADA:
# define MAX_X 5
# define MAX_Y 5
# define VALOR_MAXIMO 1
int X[MAX_X * MAX_Y] ;
int IX ;
// MATRIZ EVOLUTIVA
# define MAX_MATRIZ 200
typedef struct {
int x[MAX_X * MAX_Y] ;
int h;
char significado[25] ;
} TipoMatriz ;
TipoMatriz Matriz[MAX_MATRIZ]
;
int UMatriz ,IMatriz
,IMasSemejante ;
double Delta ,Alfa
,AlfaMasSemejante ,S ;
char Linea[100] ;
void main(void)
{
int sigue ;
printf("Matriz Evolutiva de reconocimiento de
señales\n\n");
printf("%% Minimo de semejanza aceptable: ");
gets(Linea);
Delta = atoi(Linea);
// INICIALIZA VARIABLES
UMatriz = 0;
sigue = 1;
do
{
printf("Vector del patron (FIN para salir):\n");
gets(Linea);
strupr(Linea);
if( strcmp(Linea,"FIN") ==
0 )
sigue = 0;
else
{
for( IX = 0; IX < MAX_X * MAX_Y; IX++ )
X[IX] = Linea[IX] - '0';
// BUSCA/APRENDE EL PATRON EN LA MATRIZ EVOLUTIVA
AlfaMasSemejante = 0.0;
IMasSemejante = -1;
for( IMatriz = 0; IMatriz < UMatriz; IMatriz++ )
{
S = 0.0;
for( IX = 0; IX < MAX_X *
MAX_Y; IX++ )
S += (1.0 -
abs((double)X[IX] / (double)VALOR_MAXIMO - Matriz[IMatriz].x[IX] /
Matriz[IMatriz].h));
Alfa = S / (double)(MAX_X *
MAX_Y) * 100.0;
if( Alfa >
AlfaMasSemejante )
{
IMasSemejante = IMatriz;
AlfaMasSemejante = Alfa;
}
}
if( IMasSemejante != -1 && AlfaMasSemejante
>= Delta )
{
printf("El simbolo tiene %3.1f%% de semejanza
por lo que es: %s\n",AlfaMasSemejante ,Matriz[IMasSemejante].significado);
// SE
REFUERZA EL PATRON
for( IX = 0; IX < MAX_X *
MAX_Y; IX++ )
Matriz[IMasSemejante].x[IX]
+= X[IX];
Matriz[IMasSemejante].h++;
}
else
{
printf("Digite el significado del simbolo: ");
gets(Matriz[UMatriz].significado);
Matriz[UMatriz].h = 1;
for( IX = 0; IX < MAX_X *
MAX_Y; IX++ )
Matriz[UMatriz].x[IX]
= X[IX];
UMatriz++;
}
}
} while( sigue == 1 );
printf("Gracias\n");
} // fin del listado
Conclusiones
Para resolver el problema de la interpretación de información como
señales, imágenes, etc. se ha presentado una propuesta basada en matrices
evolutivas, ejemplificándolo con el reconocimiento de símbolos, el mismo
algoritmo puede aplicarse al reconocimiento de voz o de otro tipo de señales.
Referencias
[1] GALINDO Soria,
Fernando, Una Representación Matricial para Sistemas Evolutivos, México, 1992