ES2241342T4

ES2241342T4 - Metodo y aparato de clasificacion.

Info

Publication number: ES2241342T4
Application number: ES99958432T
Authority: ES
Inventors: Gaston Baudat
Original assignee: Mars Inc
Current assignee: Mars Inc
Priority date: 1998-12-02
Filing date: 1999-12-01
Publication date: 2006-05-16
Anticipated expiration: 2019-12-01
Also published as: WO2000033262A1; ES2241342T3; EP1522970A1; DE69925155D1; EP1138026B1; CN101154301A; CN100354897C; US20030192765A1; US7073652B2; JP4723724B2; JP2002531906A; GB9826494D0; DE69925155T2; AU1580100A; CN1334944A; CN101154301B; US6588571B1; GB2344446A; EP1138026A1

Abstract

Un método de derivación de una función de clasificación para clasificar artículos de moneda (3) en dos o mas clases, que comprende la medida de muestras conocidas de cada clase, y derivando vectores característicos a partir de las muestras medidas, seleccionando una función de correlación correspondiente a una correlación no lineal del espacio vectorial característico hasta un segundo espacio, correlacionando los vectores característicos con los vectores de la imagen, en el que la función de correlación mencionada expresa un producto escalar en el segundo espacio en términos de una función en dos elementos del espacio vectorial característico, y derivando los coeficientes que representan N-1 ejes, en donde N es el numero de clases, en el segundo espacio, en el que los coeficientes se derivan por la optimización de la separación de las proyecciones de los grupos de vectores de las imágenes para cada clase en los ejes, obteniéndose los valores que representan las proyecciones de los vectoresde la imagen para las muestras medidas sobre los ejes, y utilizando dichos valores para derivar una función de separación para separar las clases equivalentes a una función de separación en las N-1 dimensiones.

Description

Método y aparato de clasificación.

La invención se refiere a un método y aparato para clasificar elementos. La invención se refiere especialmente a la clasificación de monedas o billetes de banco.

Las monedas y los billetes de banco insertados en mecanismos, tales como las máquinas de venta, máquinas de cambio de moneda y similares, se clasifican, por una parte, de acuerdo con el valor, y/o, por otra parte, entre los originales y las copias o falsificaciones de los mismos. Son conocidos distintos métodos para llevar a cabo dicha clasificación. Como ejemplo puede citarse el documento GB 2 238 152 A, cuyo contenido se incorpora a esta descripción como referencia. Por ejemplo, las mediciones se toman a partir de una moneda insertada que representa las distintas características de la moneda, tal como el material y el grosor. Dichas mediciones se comparan con los pares de valores almacenados, correspondiendo cada par a un valor aceptable correspondiente de una moneda. Cuando cada valor medido se encuentra dentro del rango respectivo para un valor determinado, la moneda insertada es clasificada como perteneciente a dicho valor.

En el tipo de clasificación expuesto anteriormente, los valores medidos pueden ser considerados como elementos en un vector de características, y las mediciones aceptables para los distintos valores corresponden a zonas en un espacio de características, conocidas como las zonas de aceptación. En el ejemplo expuesto anteriormente, el espacio de características es de dos dimensiones, y las zonas de aceptación son rectángulos, pero el espacio de características puede tener varias dimensiones, con una complejidad correspondiente en las zonas de aceptación. Por ejemplo, el documento GB 2 254 949 A describe zonas de aceptación elipsoidales en un espacio de características de tres dimensiones.

Se describen otros ejemplos de métodos y aparatos para clasificar billetes y monedas en los documentos EP 0 067 898 A, EP 0 472 192 A, EP 0 165 734 A. Otros métodos de clasificación incluyen el uso de redes neurales, tal como se describe, por ejemplo, en los documentos EP 0 553 402 A y EP 0 671 040 A.

Un problema significativo en la clasificación de monedas es la dificultad de separar los distintos valores. Las distribuciones estadísticas de los distintos valores de interés pueden ser tales que no es posible fácilmente definir los límites de aceptación apropiados, con los cuales poder separar adecuadamente los valores. Otro problema es que con el fin de conseguir una separación adecuada, puede ser necesario considerar unos vectores de características que tengan un gran número de elementos, lo cual hace más difícil comprender las distintas distribuciones y por tanto hace más difícil obtener los límites de aceptación adecuados. Estos problemas son semejantes a los problemas de clasificación generales en el análisis de datos, los cuales han sido estudiados y han conducido a distintas técnicas que incluyen métodos estadísticos.

Como ejemplo de un método estadístico de análisis de datos, el análisis de componentes principales ("PCA"), es un método por el cual los datos expresados en un espacio son trasformados utilizando una transformación lineal en un nuevo espacio, en el cual la mayor parte de las variaciones dentro de los datos puede explicarse utilizando menos dimensiones que en el primer espacio. El método PCA incluye la localización de vectores propios (eigenvectors) y valores propios (eigenvectors) de la matriz de la covariancia de las variables. Los vectores propios son los ejes en el nuevo espacio, en que el vector propio que tiene el valor propio más alto es el primer "componente principal", y así sucesivamente con la disminución del tamaño. Los detalles del PCA pueden encontrarse en los libros de texto de análisis multivariado, tal como en el documento "Introducción al análisis multivariado", de Chatfield y Collins, Capítulo 4.

Otro método de análisis de datos para los objetivos de la clasificación es el análisis de discriminación lineal ("LDA"). El sistema LDA es útil cuando se sabe que los datos se encuentran en grupos separados. El sistema LDA está enfocado a transformar los datos en un nuevo espacio, con el fin de hacer máxima la distancia entre el centro de cada grupo de datos, tal como se proyecta sobre los ejes en el nuevo espacio y también a minimizar la variancia de cada grupo a lo largo de los ejes. Métodos para la realización están descritos, por ejemplo, en el documento "Introducción al reconocimiento de patrones estadísticos", de Fukunaga ("Fukunaga"). En un ejemplo, la maximación se lleva a cabo mediante la determinación de una transformación lineal que haga máximo el valor del trazo de C^{-1}V, en donde V es la matriz de covariancia interclase y C es la matriz de covariancia de todas las muestras. Según se expone en el método de Fukunaga, esto significa la determinación de los vectores propios y a los valores propios de C^{-1}V. Los vectores propios son los ejes del nuevo espacio. Tal como se describe en el documento, en donde existen N clases, el nuevo espacio tiene N-1 dimensiones.

En muchas situaciones, ni el método PCA ni el método LDA proporcionan una separación adecuada de los grupos de datos. Un método adicional de análisis de datos es el análisis de componentes no lineal (NCA), el cual está basado en el método PCA. En el método NCA, los datos son proyectados a un nuevo espacio utilizando una correlación no lineal, y después el método PCA se lleva a cabo en el nuevo espacio. Los detalles del método NCA se proporcionan en el artículo "Análisis de componentes no lineal como un problema de valores propios del núcleo", por Bernhard Scholkopf, Alexander Smola y Klaus-Robert Muller, Computación Neural 10, 1299-1319 (1998), ("Scholkopf").

Un problema con el método NCA es que la dimensión del espacio no lineal puede ser muy grande, y por tanto el número de componentes principales es también muy grande. Para un problema determinado, no se sabe cuantos componentes principales serán necesarios para una clasificación satisfactoria.

Los aspectos de la invención están expuestos en las reivindicaciones adjuntas 1, 8, 9, 16, 17.

Se describirá una realización de la presente invención con referencia a los dibujos adjuntos, en los que:

La figura 1 es un diagrama de bloques de un sistema de clasificación.

La figura 2 es un gráfico que muestra una distribución de datos de monedas; y

La figura 3 es un gráfico que muestra una proyección de los datos de la figura 2 sobre unos ejes nuevos.

La invención se describirá con referencia a un validador de monedas.

En la figura 1, el bloque 1 designa un sistema de medición, el cual incluye una entrada 2, un sistema de transporte en forma de una entrada de la moneda y una trayectoria de transporte de la moneda (no mostrada) para presentar una muestra 3 y un sistema sensor (no mostrado) para medir las magnitudes físicas de la muestra. El sistema de medición 1 está conectado a un sistema de procesamiento 4 por medio de un bus de datos 5. El sistema de procesamiento 4 está conectado a un clasificador 6 por medio de un bus de datos 7. La salida del clasificador 6 está conectada a un sistema de utilización 8 por medio de un bus de salida de datos 9. El sistema de utilización 8 en este ejemplo es una máquina de venta, pero puede ser también, por ejemplo, una máquina de cambio de moneda.

El sistema de medición 1 mide las características de la moneda insertada 3. Las características de medición se ensamblan en un vector de características que tiene n elementos, en donde cada elemento corresponde a una característica de medición mediante el sistema de procesamiento 4. En el presente ejemplo, el sistema sensor mide los valores representativos del material, grosor y diámetro de la moneda insertada, utilizando técnicas conocidas (véase por ejemplo el documento GB 2 254 949 A) y cuyos valores son los tres elementos del correspondiente vector de características. En resumen, cada sensor comprende una o más bobinas en un circuito auto-oscilante. En el caso de los sensores del diámetro y del grosor, un cambio en la inductancia de cada bobina, provocado por la proximidad de una moneda insertada, provocará que se altere la frecuencia del oscilador, por lo que puede derivarse una representación digital de la propiedad respectiva de la moneda. En el caso del sensor de conductividad, un cambio del factor Q de la bobina provocado por la proximidad de una moneda insertada provocará que se altere el voltaje a través de la bobina, por lo que puede derivarse una salida digital representativa de la conductividad de la moneda. Aunque la estructura, posicionado y orientación de cada bobina, y la frecuencia del voltaje aplicado a las mismas, se encuentran configurados de forma que la bobina suministre una salida predominantemente dependiente de una en particular de las propiedades de conductividad, diámetro y grosor, se observará que cada medición se realizará en cierta medida según otras propiedades de la moneda.

Por supuesto, pueden medirse muchas características distintas representativas de los elementos de dinero y que se usan como elementos de los vectores de características. Por ejemplo, en el caso de un billete de banco, las características de medición pueden incluir, por ejemplo, el ancho del billete, la longitud del billete, y la intensidad de la luz reflejada o transmitida por la totalidad o parte del mismo. Como ejemplo, puede configurarse un sistema de medición para escanear un billete de banco a lo largo de N líneas utilizando sensores ópticos. Cada línea escaneada contiene L áreas individuales, las cuales se escanean en sucesión. En cada área, existen mediciones de M características distintas. Más específicamente, para cada área, se hacen mediciones de las intensidades de la reflectancia del rojo, verde y de la radiación de infrarrojos. El número total de mediciones para un billete de bando es por tanto L x M x N. Estas mediciones forman los componentes de un vector de características de la muestra respectiva, de forma que el vector de características tiene L x M x N componentes. Alternativamente, las mediciones pueden ser procesadas de una forma diferente para obtener un vector de características representativo de la muestra medida. Por ejemplo, los vectores de características locales de cada área medida pueden ser formados por las M medidas de dicha área, de forma que cada vector de características local tenga M componentes. Los vectores de características locales pueden ser sumados sobre el área
del billete de banco para obtener un vector de características dimensional M representativo de la muestra completa.

El vector de características es entonces introducido en el clasificador 6. El clasificador 6 determina si la muestra pertenece a cualquiera de las clases predeterminadas, utilizando el vector de características y los criterios de clasificación predeterminados, incluyendo una función de separación. Si la muestra se identifica como perteneciente a un valor aceptable de un billete de banco, entonces se acepta y el valor correspondiente del billete queda acreditado. Si la muestra se identifica como perteneciente a un grupo de falsificación conocido, entonces se rechazará.

En este ejemplo, el sistema es para clasificar dos valores de monedas y un tipo conocido de falsificación. En la figura 2 se muestra una representación bidimensional de la distribución del espacio de medición. Las cruces representan muestras del primer valor, los puntos representan las falsificaciones del primer valor y los círculos representan muestras del segundo valor.

La derivación de la función de separación se describirá más adelante en términos generales. El método de clasificación será descrito entonces, también en términos generales, seguido por una explicación de la aplicación del método general para el ejemplo específico.

En resumen, un método para deducir una función de separación de acuerdo con una realización de la invención determina la topografía del espacio de entrada, es decir el espacio de los vectores de características medidos utilizando un mapa no lineal, en un espacio dimensional mayor con propiedades lineales. Los hiperplanos de separación están construidos en el espacio determinado topográficamente utilizando datos de entrenamiento, utilizando el equivalente de un análisis LDA en el espacio estudiado topográficamente.

La distribución estadística de los valores se analiza tal como se explica a continuación.

Inicialmente, las muestras de cada uno de los valores de interés y cada una de las falsificaciones conocidas son medidas y se forman los correspondientes vectores de características. Los vectores de características de las muestras, al ser representados gráficamente, por ejemplo en un gráfico de dispersión de n dimensiones (en donde n es el numero de características de medición), se encuentran aproximadamente en grupos, conocidos como agrupaciones. Estas muestras medidas son entonces utilizadas para deducir una función de separación, según lo descrito más adelante. En este ejemplo, se utilizaron 50 muestras para cada valor y 50 muestras de las falsificaciones.

Antes de continuar, se facilita una explicación general de la notación utilizada.

El espacio de entrada, es decir, el espacio de los vectores de características, está definido como X.

x = \bigcup\limits^{N}_{l=1} X_{1},

en donde N es el número de agrupaciones. La cardinalidad del subespacio X_{1} es indicada por n_{1}, y el numero de elementos en X es M. Así pues:

\sum\limits^{N}_{l=1} n_{1} = M. \ x^{t}

es el transpuesto del vector x.

En el espacio de entrada, C es la matriz de covariancia, y

(1)C = \frac{1}{M} \sum\limits^{M}_{j=t} x_{j} x^{t}{}_{j}

El método de la invención utiliza una función de núcleo k que define un producto escalar en un espacio determinado topográficamente. Suponiendo que 43 es una función no lineal que correlaciona X en un espacio F de Hilbert.

\Phi:X \rightarrow F

(2)x \rightarrow \Phi (x)

y

k(x,y) = \Phi (x)\cdot \Phi (y) = \Phi^{1} (x) \Phi (y)

Tal como se aclarará a partir de la siguiente explicación, no es necesario explícitamente construir \Phi para un valor de k determinado, aunque puede ser mostrado, mediante el teorema de Mercer, si para cualquier valor de k es un núcleo continuo de un operador integral positivo el cual es positivo, entonces existirá un \Phi (véase la Sección 3 y Apéndice C de Schölkopf). Tampoco es necesario realizar el producto escalar explícitamente en F, que puede ser un espacio dimensional infinito.

En F, V es la matriz de covariancia, y

(3)V = \frac{1}{M} \sum\limits^{M}_{j=1} \Phi(x_{i})\Phi^{t}(x_{j})

\newpage

Se supone que las observaciones están centradas en F, es decir, que:

\sum\limits^{M}_{j=1} \Phi(x_{j}) = 0

Se describirá posteriormente un método centrado de datos. B es la matriz de covariancia de los centros de la agrupación, y

(4)B = \frac{1}{M} \sum\limits^{N}_{l=1} n_{1} \overline{\Phi_{1} \Phi^{t}{}_{1}}

en donde \overline{\Phi_{1}} es el valor medio de la agrupación 1, es decir:

(5)\overline{\Phi_{1}} = \frac{1}{n_{1}} \sum\limits^{n_{j}}_{k=l} \Phi (x_{ij})

en donde x_{ij} es el elemento j de la agrupación l.

B representa la inercia del interagrupamiento en F.

V puede ser expresado también utilizando las agrupaciones como

(6)V = \frac{1}{M} \sum\limits^{N}_{l=1} \sum\limits^{n_{1}}_{k=1} \Phi (x_{lk}) \Phi^{t} (x_{lk})

V representa la inercia total en F,

Se supondrá:

K_{ij} = K(X_{i}, X_{j})

y:

(K_{ij})_{pq} = (\Phi^{t} (X_{pi}) \Phi (X_{qj}))

Si K es una matriz (M x M) definida en los elementos de la agrupación por:

100

en donde (K_{pq}) es la matriz de covariancia entre la agrupación _{P} y la agrupación _{q},

101

K_{pq} es una matriz (n_{p} x n_{q})

y K es simétrica de forma que: K'_{pq} = K_{pq}

W es el centro de la matriz, y

(9)W = (W_{l})_{l = l}...N

en donde W_{1} es una matriz (n_{l} x n_{l}) con todos los términos iguales a 1/n_{l}.

W es una matriz diagonal de M x M bloques.

El método realiza esencialmente el análisis discriminatorio lineal en el espacio determinado topográficamente F para hacer máxima la inercia inter-agrupación y minimizar la inercia intra-agrupación. Esto es equivalente a la resolución propia, tal como se muestra en el documento de Fukunaga. Puede ser derivada, entonces, una función de separación adecuada.

\newpage

Más específicamente, el método incluye la localización de los valores propios \lambda y los vectores propios v que satisfacen:

(10)\lambdaVv = Bv

Los vectores propios son combinaciones lineales de los elementos de F y por tanto existen los coeficientes:

\alpha_{pq} (p=1...N, q=1...n_{p})

de forma tal que:

(11)v = \sum\limits^{N}_{p=1} \sum\limits^{n_{p}}_{q=1} \alpha_{pq} \Phi (x_{pq})

Los vectores propios de la ecuación (10) son los mismos que los vectores propios de:

(12)\lambda \Phi^{i} (x_{ij}) Vv = \Phi' (x_{ij}) Bv

(véase el documento de Scholkopf).

Utilizando las definiciones de K y W, y las ecuaciones (6) y (11), la parte de la derecha de (12) puede ser expresada de la forma siguiente:

V\nu = \frac{1}{M} \sum\limits^{N}_{l=1} \sum\limits^{n_{i}}_{k=1} \Phi (x_{lk}) \Phi^{t} (x_{lk}) \sum\limits^{N}_{p=1} \sum\limits^{n_{p}}_{q=1} \alpha_{pq} \Phi (x_{pq})

\hskip0.8cm = \frac{1}{M} \sum\limits^{N}_{p=1} \sum\limits^{n_{p}}_{q=1} \alpha_{pq} \sum\limits^{N}_{l=1} \sum\limits^{nt}_{k=1} \Phi (x_{lk}) [\Phi^{t} (x_{lk}) \Phi (x_{pq})]

y

\lambda \Phi^{t} (x_{ij})V\nu = \frac{\lambda}{M} \sum\limits^{N}_{p=1} \sum\limits^{n_{p}}_{q=1} \alpha_{pq} \Phi^{t} (x_{ij}) \sum\limits^{N}_{l=1} \sum\limits^{n_{j}}_{k=1} \Phi (x_{lk}) [\Phi' (x_{lk}) \Phi (x_{pq})]

\hskip1.7cm= \frac{\lambda}{M} \sum\limits^{N}_{p=1} \sum\limits^{n_{p}}_{q=1} \alpha_{pq} \sum\limits^{N}_{l=1} \sum\limits^{n_{j}}_{k=1} [\Phi' (x_{ij}) \Phi (x_{lk})][\Phi' (x_{lk}) \Phi (x_{pq})]

Utilizando esta fórmula para todas las agrupaciones i y para todos los elementos j, se obtendrá:

\lambda(\Phi'(x_{ll}, ..., \Phi'(x_{ln_{q}}), ..., \Phi'(x_{ij}), ..., \Phi'(x_{M}), ..., \Phi'(x_{Nn_{N}}))V\nu = \frac{\lambda}{M} KK\alpha

en donde:

102

en donde:

\alpha p = (\alpha_{pq})q = 1...n_{p}

\newpage

Utilizando las ecuaciones (4), (5) y (11), para el término derecho de (14):

B\nu = \frac{1}{M} \sum\limits^{N}_{p=1} \sum\limits^{n_{p}}_{q=1} \alpha_{pq} \Phi(x_{pq}) \sum\limits^{N}_{l=1} n_{l} \left[\frac{1}{n_{l}} \sum\limits^{n_{l}}_{k=1} \Phi(x_{lk})\right]\left[\frac{1}{n_{l}} \sum\limits^{n_{l}}_{k=1} \Phi(x_{lk})\right]

\vskip1.000000\baselineskip

\hskip0.2cm = \frac{1}{M} \sum\limits^{N}_{p=1} \sum\limits^{n_{p}}_{q=1} \alpha_{pq} \sum\limits^{N}_{l=1} \left[\sum\limits^{n_{l}}_{k=1} \Phi(x_{lk})\right]\left[\frac{1}{n_{l}}\right]\left[\sum\limits^{n_{l}}_{k=1} \Phi'(x_{lk}) \Phi(x_{pq})\right]

y

\Phi'(x_{ij}) B\nu = \frac{1}{M} \sum\limits^{N}_{p=1} \sum\limits^{n_{p}}_{q=1} \alpha_{pq} \sum\limits^{N}_{l=1} \left[\sum\limits^{n_{l}}_{k=1} \Phi'(x_{ij}) \Phi(x_{lk})\right]\left[\frac{1}{n_{l}}\right]\left[\sum\limits^{n_{l}}_{k=1} \Phi' (x_{lk} \Phi(x_{pq})\right]

Para todas las agrupaciones i y para todos los elementos j se obtendrá:

(14)(\Phi' (x_{ll}),..., \Phi' (x_{ln_{l}}),... \Phi' (x_{ij}),..., \Phi' (x_{Nl}),..., \Phi' (x_{Nn_{N}})) B\nu = \frac{1}{M} KWK\alpha

Combinando (13) y (14) se obtendrá:

\lambdaKK\alpha = KWK\alpha

Así pues,

(15)\lambda = \frac{\alpha' KWK\alpha}{\alpha' KK\alpha}

K puede descomponerse como K = QR (Wilkinson, 1971), de forma que K\alpha = QR\alpha

R es triangular superior y Q es ortonormal, es decir Q^{t}Q = I.

Q es una matriz Mxr y R es una matriz rxM, en donde r es el rango de K. Se sabe que la descomposición QR existe siempre para una matriz rectangular general.

Entonces, se supondrá

(16)R\alpha = \beta

Dado que las filas de R son linealmente independientes, para una \beta dada, existe al menos una solución \alpha.

Por tanto K\alpha = Q\beta, y \alpha^{t}K = \beta^{t}Q^{t} (K es simétrica).

Sustituyendo en (15):

(17)\lambda = \frac{\alpha' KWK\alpha}{\alpha' KK\alpha}

Q es ortonormal, por tanto:

(18)\lambda\beta = Q^{t} WQ\beta

La ecuación (18) tiene la forma de una ecuación de vectores propios estándar. Dado que K es singular, la descomposición QR permite operar en un subespacio Q\beta, el cual simplifica la resolución.

A continuación los coeficientes a pueden ser derivados de \beta de la ecuación (16), y después los vectores propios de la ecuación (11).

Estos coeficientes \alpha están normalizados, requiriendo que los vectores correspondientes v en F sean normalizados. Es decir:

(19)v^{t}v = 1

o bien (desde la ecuación 11):

V^{t}V = \sum\limits^{N}_{p=1} \sum\limits^{n_{p}}_{q=1} \sum\limits^{N}_{l=1} \sum\limits^{n_{l}}_{h=1} \alpha_{pq} \alpha_{lh} \Phi'(x_{pq}) \Phi (x_{lh}) = 1

\hskip-1.8cm = \sum\limits^{N}_{p=1} \sum\limits^{N}_{l=1} \alpha'_{p} K_{pl} \alpha_{l} = 1

\hskip-3.5cm = \alpha' K\alpha

de forma que:

(20)(19) \longrightarrow \alpha' K\alpha = 1

Las etapas indicadas anteriormente determinan la forma de encontrar los vectores propios v de la ecuación (10).

Tal como se conoce a partir del análisis discriminante lineal (véase por ejemplo el documento de Fukunaga), el numero de vectores propios = N-1 en donde N es el numero de agrupaciones. La imagen de los agrupamientos en el subespacio abarcado por los vectores propios se encuentra proyectando sobre los vectores propios. Esto se realiza utilizando la siguiente ecuación para un vector propio v y un vector v de características:

(\Phi^{t} (x)\nu) = \sum\limits^{N}_{p=1} \sum\limits^{n_{p}}_{q=1} \alpha_{pq} \Phi^{t} (x_{pq}) \Phi(x)

(21)\hskip0.7cm = \sum\limits^{N}_{p=1} \sum\limits^{n_{p}}_{q=1} \alpha_{pq} k(x_{pq}, x)

Tal como puede apreciarse de lo anterior, el cálculo no precisa del conocimiento de \Phi, o la necesidad de calcular un producto escalar en F.

Se ha demostrado en experimentos que mediante el uso de una función de núcleo adecuada, las imágenes de los agrupamientos en el subespacio de los vectores propios son separadas satisfactoriamente y, más específicamente, pueden ser separables linealmente, es decir que pueden ser separadas por líneas, planos o hiperplanos.

A continuación puede derivarse fácilmente una función de separación adecuada mediante la clasificación de elementos medidos, utilizando una técnica conocida, tal como inspección, promediado, distancia de Malalanobis, en comparación con los vecinos más próximos k.

Tal como se ha mencionado anteriormente, se ha supuesto que las observaciones están centradas en F. Se expondrá a continuación el centrado con más detalle. En primer lugar, para una observación dada x_{ij}, elemento j del agrupamiento i, la imagen \Phi(x_{ij}) está centrada de acuerdo con:

(22)\overline{\Phi}(x_{ij}) = \Phi(x_{ij}) - \frac{1}{M} \sum\limits^{N}_{l=1} \sum\limits^{n_{l}}_{k=1} \Phi (x_{lk})

Entonces se tiene que definir la matriz de covariancia K con puntos centrados:

(\overline{K}_{ij})_{pq} = (\overline{\Phi} (x_{pi})\cdot \overline{\Phi} (x_{qj}))

para una agrupación dada p y q.

(\overline{k}_{ij})_{pq} = \left[\Phi(x_{pi}) - \frac{1}{M} \sum\limits^{N}_{l=1} \sum\limits^{n_{l}}_{k=1} \Phi (x_{lk})\right]\left[\Phi(x_{qj}) - \frac{1}{M} \sum\limits^{N}_{h=1} \sum\limits^{N_{m}}_{m=1} \Phi(x_{hm})\right]

\newpage

(\overline{k}_{ij})_{pq} = (k_{ij})_{pq} - \frac{1}{M} \sum\limits^{N}_{l=1} \sum\limits^{n_{l}}_{k=1} (1_{ik})_{pl} (k_{kj})_{lq} - \frac{1}{M} \sum\limits^{N}_{h=1} \sum\limits^{n_{m}}_{m=1} (k_{im})_{ph}(1_{mj})_{hp} + \frac{1}{M^{2}} \sum\limits^{N}_{l=1} \sum\limits^{n_{l}}_{k=1} \sum\limits^{N}_{h=1} \sum\limits^{n_{m}}_{m=1}

\overline{k}_{pq} = k_{pq} - \frac{1}{M} \sum\limits^{N}_{l=1} 1_{pl} k_{lq} - \sum\limits^{N}_{h=1} k_{ph} 1_{hq} + \frac{1}{M^{2}} \sum\limits^{N}_{l=1} \sum\limits^{N}_{h=1} 1_{pl} k_{lh} 1_{hq}

\overline{k} = k - \frac{1}{M} 1_{N} k - \frac{1}{M} k1_{N} + \frac{1}{M^{2}} 1_{n} k1_{N}

En donde se ha introducido al siguiente matriz:

l_{pl} = (l_{ik})_{i} = 1,...,n_{p};k=1,..., n_{l}), (n_{p}xn_{l})

matriz cuyos elementos son todos iguales a 1.

l_{N} = (l_{pl})_{p=1,...,N;l=1,..., N,} (MxM)

matriz cuyos elementos son todos matrices de bloques.

Así pues, para los puntos no centrados \Phi(x_{ij}), se puede derivar \overline{K} de K y después resolver los vectores propios de \overline{K}. A continuación, para un vector de características x, la proyección de la imagen \Phi centrada de x sobre los vectores propios v es dada por:

(\overline{\Phi}' (x)\nu) = \sum\limits^{N}_{lp1} \sum\limits^{n_{p}}_{q=1} \overline{\alpha}_{pq} \overline{\Phi}' (x_{pq}) \overline{\Phi} (x)

La exposición anterior establece en términos generales el método del análisis de discriminación general. Los principios generales se ilustrarán a continuación con referencia al ejemplo específico del validador de monedas.

Volviendo al ejemplo del validador de monedas al comienzo de la descripción, los vectores de características tienen cada uno tres elementos, y existen tres agrupaciones, correspondientes a cada uno de los dos valores de interés y a la falsificación conocida respectivamente.

Se introdujeron en el sistema de medición 1 las 50 muestras de cada valor, y las 50 muestras de las falsificaciones. Tal como se expuso anteriormente, los sistemas sensores midieron las muestras para obtener los valores representativos del grosor, material y diámetro en cada caso. Los vectores de características correspondientes están formados a partir de las características de medición para cada muestra.

A partir de las 50 muestras de vectores de características para cada agrupación, se seleccionaron aleatoriamente 37 para su utilización en la generación de la función de separación.

Se elige entonces una función del núcleo. La función del núcleo se selecciona sobre la base del sistema de prueba y error, con el fin de seleccionar cualquier función que proporcione los mejores resultados de la separación. Existe un gran número de funciones de núcleo, que satisfacen el teorema de Mercer, las cuales podrán ser adecuadas. Los ejemplos de las funciones del núcleo son el núcleo polinómico:

k (x,y) = (x.y)^{d};

el núcleo gaussiano:

k(x,y) = exp \frac{(-||x - y||^{2})}{\sigma^{2}};

el núcleo tangente hiperbólico:

k(x,y) = tanh ((x.y)+\theta);

\newpage

y el núcleo sigmoide:

k(x,y) = \left(\frac{1}{1+e^{-((x.y)+\theta)}}\right).

En este ejemplo se utiliza el núcleo gaussiano, con \sigma^{2} = 0,01.

Utilizando las muestras seleccionadas y la función del núcleo, se calculan las matrices K y W. (Ecuaciones (8) y (9)).

A continuación K se descompone utilizando la descomposición QR.

A continuación se calculan los vectores propios \beta y los vectores propios correspondientes (ecuación (18)).

A continuación se calculan y se normalizan los coeficientes a (ecuaciones (16) y (20)).

Posteriormente, los vectores de características de las 13 muestras restantes de cada agrupación se proyectan sobre los vectores propios v (ecuación 21) y los resultados se representan en un gráfico para una inspección fácil. En este ejemplo, existen 3 agrupaciones, de forma que son 2 vectores propios, y la separación se encuentra en un espacio de 2 dimensiones. Esto se muestra en la figura 3. Tal como puede verse, las agrupaciones están perfectamente separadas. Más específicamente, cada agrupación está proyectada en un punto, el cual es el centro de gravedad. La separación de la proyección de las agrupaciones con los vectores propios se analiza posteriormente, y se utiliza para derivar la función de separación. En este ejemplo, la función de separación lineal puede derivarse fácilmente mediante la inspección. Por ejemplo, una función de separación adecuada es:

para los vectores v_{1}, v_{2}:

y el vector de entrada x

Si:

[(\Phi'(x)\nu_{1}) > 0 \hskip0.5cm y \hskip0.5cm (\Phi'(x)\nu_{2}) > 0] entonces

x pertenece al grupo 1 (es decir, es del primer valor);

Si:

[(\Phi'(x)\nu_{1}) > 0 \hskip0.5cm y \hskip0.5cm (\Phi'(x)\nu_{2}) < 0]

entonces x pertenece al grupo 2 (es decir, es del segundo valor); y

si:

[(\Phi'(x)\nu_{1}) < 0 \hskip0.5cm y \hskip0.5cm (\Phi'(x)\nu_{2}) > 0]

entonces x pertenece al grupo 3 (es decir, es una falsificación del primer valor).

La clasificación de las monedas de un valor no conocida se realiza entonces de la forma siguiente. La moneda insertada es detectada, y se obtienen las mediciones representativas del material, grosor y diámetro, al igual que para las muestras. Se deriva entonces un vector de características de los valores medidos. El vector de características es entonces proyectado sobre los vectores propios calculados (utilizando la ecuación 21), y la moneda se clasifica de acuerdo con los valores de proyección y la función de separación, tal como se ha descrito anteriormente.

El análisis de los valores de las muestras para el análisis de datos inicial y la derivación de la función de separación puede realizarse, por ejemplo, utilizando un microprocesador. De forma similar, el clasificador 6 puede ser un microprocesador.

Como alternativa, el clasificador 6 puede ser una red neuronal, tal como una red neuronal probabilística, o un perceptrón. Por ejemplo, la red neuronal puede incluir N-1 neuronas de salida lineales y M neuronas ocultas, en donde cada cálculo del núcleo es una neurona oculta. A continuación, los valores ponderados de entrada son los valores x_{pq}, y los coeficientes a son los valores ponderados entre las neuronas ocultas y la capa de salida.

Asimismo, el clasificador puede ser un clasificador lineal, o bien una máquina vectorial de soporte.

\newpage

Los métodos de la realización descrita anteriormente son igualmente aplicables a un billete de banco o bien a una clasificación de otras clases de elementos de dinero. Son posibles también otros métodos de resolución (10), por ejemplo mediante la descomposición K utilizando la descomposición de vectores propios.

En la realización se utiliza una correlación no lineal en un espacio dimensional mayor. Asimismo, la correlación podría ser un espacio dimensional menor, o un espacio de la misma dimensión que el espacio vectorial característico.

Claims

1. Método de derivación de una función de clasificación para clasificar elementos de dinero (3) en dos o más clases, que comprende la medición de muestras conocidas de cada clase y la derivación de vectores de características a partir de las muestras medidas, seleccionando una función de correlación correspondiente a una correlación no lineal del espacio vectorial característico hasta un segundo espacio, correlacionando los vectores de características con los vectores de la imagen, en el que la función de correlación mencionada expresa un producto escalar en el segundo espacio en términos de una función en dos elementos del espacio vectorial característico, y derivando los coeficientes que representan N-1 ejes, en donde N es el número de clases, en el segundo espacio, en el que los coeficientes se derivan por la optimización de la separación de las proyecciones de los grupos de vectores de las imágenes para cada clase en los ejes, obteniéndose los valores que representan las proyecciones de los vectores de la imagen para las muestras medidas sobre los ejes, y utilizando dichos valores para derivar una función de separación para separar las clases equivalentes a una función de separación en el espacio N-1 dimensional.

2. Método, según la reivindicación 1, en el que el segundo espacio tiene una dimensionalidad más alta que el primer espacio.

3. Método, según la reivindicación 1 ó 2, que comprende la derivación de una matriz V, en donde V es la matriz de covariancia en el segundo espacio, y una matriz B en donde B es la matriz de covariancia de los centros de las clases en el segundo espacio, derivando las soluciones a la ecuación \lambdaVv = Bv, y derivando los mencionados coeficientes a partir de las soluciones v.

4. Método, según cualquiera de las reivindicaciones anteriores, en el que la mencionada función de correlación es k(x,y),

en donde k (x, y ) = (x, y)^{d}.

5. Método, según cualquiera de las reivindicaciones anteriores, en el que la mencionada función de correlación es k (x,y)

en donde:

K(x,y) = exp \frac{(-||x - y ||^{2})}{\sigma^{2}}

6. Método, según cualquiera de las reivindicaciones anteriores, en el que la mencionada función de correlación es k(x,y), en donde k(x, y) = tanh ((x, y) + \Phi).

7. Método, según cualquiera de las reivindicaciones anteriores, en el que la mencionada función de correlación es k(x,y), en donde:

k(x y) = \left(\frac{1}{1+e^{-((x.y)+\theta)}}\right)

8. Método para clasificar un elemento de dinero (3) que comprende la medición de características del elemento, generando un vector de características a partir de los valores medidos, y clasificando el elemento (3) utilizando una función de clasificación derivada por un método de acuerdo con cualquiera de las reivindicaciones 1 a 7.

9. Aparato para clasificar elementos de dinero que comprende medios de medición (1) para medir las características de un elemento de dinero (3), medios de generación de vectores de características (4), para generar un vector de características a partir de los valores medidos, y medios de clasificación (6) para clasificar un elemento utilizando datos que representen la función de correlación no lineal correspondiente a una correlación del espacio vectorial característico en un segundo espacio, vectores de características de correlación a los vectores de las imágenes, en el que la mencionada función de correlación expresa un producto escalar en el segundo espacio en términos de una función en dos elementos del espacio vectorial característico y los mencionados medios de clasificación utilizando coeficientes representativos de N-1 ejes, en donde N es el numero de clases que pueden ser clasificadas por el aparato, y una función equivalente a una función de separación en el espacio N-1 dimensional, para separar las proyecciones de los vectores de las imágenes en este espacio dimensional N-1.

10. Aparato, según la reivindicación 9, en el que los medios de clasificación (6) comprenden medios para derivar los valores correspondientes a la proyección de la imagen del vector de características del elemento de medición sobre cada uno de los ejes.

11. Aparato, según la reivindicación 9 ó 10, en el que los medios de clasificación (6) comprenden una red neural.

\newpage

12. Aparato, según cualquiera de las reivindicaciones 9 a 11, que comprende una entrada de monedas (2) y en el que los medios de medición comprenden medios sensores para detectar una moneda.

13. Aparato, según la reivindicación 12, en el que los medios sensores son para detectar el material y/o el grosor y/o el diámetro de una moneda.

14. Aparato, según cualquiera de las reivindicaciones 9 a 11, que comprende una entrada de billetes de banco (2) y en el que los medios de medición comprenden medios sensores para detectar un billete de banco.

15. Aparato, según la reivindicación 14, en el que los medios sensores son para detectar la intensidad de la luz reflejada y/o transmitida a través de un billete de banco.

16. Validador de monedas que comprende un aparato según cualquiera de las reivindicaciones 9 a 13.

17. Validador de billetes de banco que comprende un aparato según cualquiera de las reivindicaciones 9 a 11, 14 ó 15.