PROCEDIMIENTO DE INDEXACIÓN Y DE IDENTIFICACIÓN DE DOCUMENTOS MULTIMEDIA.

Procedimiento de indexación de documentos multimedia, que comprende por lo menos las siguientes etapas:

(a) identificar y extraer para cada documento términos ti constituidos por vectores que caracterizan propiedades del documento multimedia que debe indexarse, tales como la forma, la textura, el color o la estructura de una imagen, la energía, la tasa de oscilación o informaciones frecuenciales de una señal de audio, o un grupo de caracteres de un texto, (b) almacenar los términos ti que caracterizan propiedades del documento multimedia en una base de términos (3) que comprende P términos, caracterizado porque comprende además las siguientes etapas: (c) determinar un número máximo N de conceptos deseados que reagrupan los términos ti pertinentes, siendo N un número entero inferior a P, y estando previsto cada concepto Ci para reagrupar todos los términos próximos desde el punto de vista de sus características, (d) calcular la matriz T de distancias entre los términos ti de la base de términos, (e) descomponer el conjunto P de términos ti de la base de términos en N partes Pj (1 ≤ j ≤ N) tales que P = P1 UP2 ··· UPj... UPN, comprendiendo cada parte Pj un conjunto de términos tij y estando representada por un concepto Cj, estando los términos ti repartidos en la base de la matriz T, de tal manera que los términos más alejados unos de otros se encuentran en partes Pl, Pm distintas y los términos próximos unos de otros se encuentran en la misma parte Pl, (f) estructurar el diccionario de conceptos (5) de manera que constituye un árbol binario en el que cada hoja del árbol binario contiene un concepto Ci del diccionario y cada nudo del árbol contiene las informaciones necesarias para el escrutinio del árbol durante una etapa de identificación de un documento multimedia mediante comparación con los documentos indexados anteriormente, y (g) construir una base de huellas (25) constituida por el conjunto de los conceptos Ci que representan los términos ti de los documentos que van a indexarse, estando cada documento asociado a una huella que le es propia.

La presente invención se refiere a los procedimientos de indexación y de identificación de documentos multimedia.

Desde un punto de vista general, la identificación de un documento multimedia comprende dos etapas:

• Una etapa denominada de indexación, en la que se intenta caracterizar cada documento de una base previamente registrada por un número finito de parámetros que pueden fácilmente almacenarse y manipularse más tarde.

• Una etapa denominada de búsqueda, en la que tras una consulta formulada por el usuario, por ejemplo la identificación de una imagen pregunta, se buscan todos los documentos multimedia similares o que responden a esta consulta.

Ya existen varios procedimientos de indexación de imágenes que ponen en práctica la extracción de los atributos de la forma de los objetos que componen la imagen si existen, así como los de la textura o del color de fondo de la imagen.

Sin embargo, los procedimientos conocidos se aplican a campos muy especializados o implican el tratamiento de una cantidad muy grande de información que conduce a una complejidad y una lentitud en el tratamiento de estas informaciones.

Se conoce en particular por el artículo de Y. Chang et al. titulado “Conceptual retrieval based on feature clustering of documents”, publicado en Proceedings of ACM Sigir Workshop on Mathematical-Formal Methods in Information Retrieval, en agosto de 2002, páginas 1-10, un procedimiento de búsqueda de documentos con por lo menos una etapa de identificación y de extracción para cada documento de términos constituidos por vectores que caracterizan las propiedades textuales del documento, y una etapa de descomposición en partes representadas por conceptos.

La presente invención tiende a remediar los inconvenientes mencionados anteriormente y a proporcionar un procedimiento de indexación y de identificación de documentos multimedia de una aplicación general que racionaliza el procedimiento de tratamiento y conduce a tiempos de tratamiento más cortos a la vez que aumenta la calidad de los resultados y su fiabilidad, lo que permite en particular proceder a búsquedas eficaces por el contenido.

Estos objetivos se alcanzan según la invención, gracias a un procedimiento de indexación de documentos multimedia, que comprende por lo menos las siguientes etapas:

(a) identificar y extraer para cada documento términos tj constituidos por vectores que caracterizan propiedades del documento multimedia que va a indexarse, tales como la forma, la textura, el color o la estructura de una imagen, la energía, la tasa de oscilación o informaciones frecuenciales de una señal de audio, o un grupo de caracteres de un texto,

(b) almacenar los términos ti que caracterizan propiedades del documento multimedia en una base de términos que comprende P términos, caracterizado porque comprende además las siguientes etapas:

(c) determinar un número máximo N de conceptos deseados que reagrupan los términos ti pertinentes, siendo N un número entero inferior a P, y estando previsto cada concepto Ci para reagrupar todos los términos próximos desde el punto de vista de sus características,

(d) calcular la matriz T de distancias entre los términos ti de la base de términos,

(e) descomponer el conjunto P de términos ti de la base de términos en N partes Pj (1≤j≤N) tales como P = P1 UP2 ··· UPj... UPN, comprendiendo cada parte Pj un conjunto de términos tij y estando representada por un concepto Cj, estando los términos ti repartidos en la base de la matriz T, de tal manera que los términos más alejados unos de otros se encuentran en partes Pl, Pm distintas y los términos próximos unos de otros se encuentran en la misma parte Pl,

(f) estructurar el diccionario de conceptos de manera que constituye un árbol binario en el que cada hoja del árbol binario contiene un concepto ci del diccionario y cada nudo del árbol contiene las informaciones necesarias para el escrutinio del árbol durante una etapa de identificación de un documento multimedia mediante comparación con los documentos indexados anteriormente, y

(g) construir una base de huellas constituida por el conjunto de conceptos ci que representan los términos ti de los documentos que van a indexarse, estando cada documento asociado con una huella que le es propia.

De manera más particular, se asocia a cada concepto ci de la base de huellas un conjunto de informaciones que comprende el número NbT de términos en los documentos en los que el concepto ci está presente.

Según un aspecto particular de la invención, para cada documento en el que está presente un concepto ci, se registra una huella del concepto ci en el documento, comprendiendo esta huella la frecuencia de aparición del concepto ci, la identificación de conceptos que están próximos al concepto ci en el documento y una puntuación que es un valor medio de medidas de similitudes entre el concepto ci y los términos ti del documento que son los más próximos al concepto ci.

Ventajosamente, el procedimiento según la invención comprende una etapa de optimización de la división del conjunto P de términos de la base de términos para descomponer este conjunto P en M clases Ci (1 ≤ i ≤ M, con M ≤ P), de manera que reduce el error del reparto del conjunto P de términos de la base de términos en N partes (P1, P2,... PN) en el que cada parte Pi se representa por el término t

**(Ver fórmula)**

cometido ε tal que

**(Ver fórmula)**

es el error cometido cuando se sustituyen los términos tj de una parte Pi por ti.

En este caso, el procedimiento puede comprender las siguientes etapas:

(i) descomponer el conjunto P de términos en dos partes P1 y P2;

(ii) determinar los dos términos más alejados ti y tj del conjunto P que corresponde a la distancia más grande Dij de la matriz T de distancias;

(iii) para cada término tk del conjunto P, examinar si la distancia Dk; entre el término tk y el término ti es más pequeña que la distancia Dkj entre el término tk y el término tj, si es así asignar el término tk a la parte Pi y si no es así asignar el término tk a la parte P2;

(iv) repetir la etapa (i) hasta obtener el número N de puntos Pi deseado y en cada iteración aplicar las etapas (ii) y (iii) en los términos de las partes Pi y P2.

El procedimiento según la invención puede caracterizarse más particularmente porque comprende una optimización a partir de las N partes desunidas {P1, P2,... PN} del conjunto P así como N términos {t1, t2, tN} que las representan para reducir el error de descomposición del conjunto P en N partes, y porque comprende las siguientes etapas:

(i) calcular los centros de gravedad Ci de las partes Pi

(ii) calcular los errores cuando se sustituyen los términos tj de la parte Pi respectivamente por Ci y por ti,

**(Ver fórmula)**

(iii) comparar εti y εCi y sustituir ti por Ci si εCi ≤εti,

(iv) calcular la nueva matriz T de distancias entre los términos tj de la base de términos y procedimiento de descomposición del conjunto P de términos de la base de términos en N partes, salvo si se cumple una condición

**(Ver fórmula)**

de parada con < umbral, en la que εCt representa el error cometido en el instante t.

Con el fin de facilitar la búsqueda y la identificación de documentos, para efectuar una estructuración del diccionario de conceptos, se produce de manera iterativa en cada iteración una carta de navegación empezando por dividir el conjunto de conceptos en dos subconjuntos, y luego seleccionando un subconjunto en cada iteración hasta la obtención del número de grupo deseado o hasta que se satisface un criterio de parada.

El criterio de parada puede caracterizarse por el hecho de que los subconjuntos obtenidos son todos homogéneos con una pequeña desviación estándar.

De manera más particular, durante la estructuración del diccionario de conceptos, se determinan indicadores de

**(Ver fórmula)**

**(Ver fórmula)**

navegación a partir de una matriz del conjunto C de conceptos en la que ci representa un concepto de p valores, según las siguientes etapas:

(i) calcular un representante w de la matriz M,

~

(ii) calcular la matriz de covarianza M entre los elementos de la... [Seguir leyendo]

1. Procedimiento de indexación de documentos multimedia, que comprende por lo menos las siguientes etapas:

5 (a) identificar y extraer para cada documento términos ti constituidos por vectores que caracterizan propiedades del documento multimedia que debe indexarse, tales como la forma, la textura, el color o la estructura de una imagen, la energía, la tasa de oscilación o informaciones frecuenciales de una señal de audio, o un grupo de caracteres de un texto,

10 (b) almacenar los términos ti que caracterizan propiedades del documento multimedia en una base de términos (3) que comprende P términos, caracterizado porque comprende además las siguientes etapas:

(c) determinar un número máximo N de conceptos deseados que reagrupan los términos ti pertinentes, siendo N un

número entero inferior a P, y estando previsto cada concepto Ci para reagrupar todos los términos próximos 15 desde el punto de vista de sus características,

(d) calcular la matriz T de distancias entre los términos ti de la base de términos,

(e) descomponer el conjunto P de términos ti de la base de términos en N partes Pj (1 ≤ j ≤ N) tales que P = P1 UP2

20 ··· UPj... UPN, comprendiendo cada parte Pj un conjunto de términos tij y estando representada por un concepto Cj, estando los términos ti repartidos en la base de la matriz T, de tal manera que los términos más alejados unos de otros se encuentran en partes Pl, Pm distintas y los términos próximos unos de otros se encuentran en la misma parte Pl,

25 (f) estructurar el diccionario de conceptos (5) de manera que constituye un árbol binario en el que cada hoja del árbol binario contiene un concepto Ci del diccionario y cada nudo del árbol contiene las informaciones necesarias para el escrutinio del árbol durante una etapa de identificación de un documento multimedia mediante comparación con los documentos indexados anteriormente, y

30 (g) construir una base de huellas (25) constituida por el conjunto de los conceptos Ci que representan los términos ti de los documentos que van a indexarse, estando cada documento asociado a una huella que le es propia.

2. Procedimiento de indexación según la reivindicación 1, caracterizado porque se asocia a cada concepto Ci de la

base de huellas (25) un conjunto de informaciones que comprende el número NbT de términos en los documentos 35 en los que el concepto Ci está presente.

3. Procedimiento de indexación según la reivindicación 1 ó 2, caracterizado porque para cada documento en el que está presente un concepto c;, se registra una huella del concepto Ci en el documento, comprendiendo esta huella la frecuencia de aparición del concepto Ci, la identificación de los conceptos que están próximos al concepto Ci en el

40 documento y una puntuación que es un valor medio de las mediciones de similitudes entre el concepto Ci y los términos ti del documento que son los más próximos al concepto Ci.

4. Procedimiento de indexación según cualquiera de las reivindicaciones 1 a 3, caracterizado porque comprende una etapa de optimización de la división del conjunto P de los términos de la base de términos para descomponer

45 este conjunto P en M clases Ci (1 ≤ i ≤ M, siendo M ≤ P), de manera que reduce el error del reparto del conjunto P de los términos de la base de términos en N partes (P1, P2,... PN) en el que cada parte Pi se representa por el término ti

**(Ver fórmula)**

que

**(Ver fórmula)**

es el error cometido cuando se sustituyen los términos tj de una parte Pi por ti.

50 5. Procedimiento de indexación según la reivindicación 4, caracterizado porque comprende las siguientes etapas:

(i) descomponer el conjunto P de términos en dos partes P1 y P2;

(ii) determinar los dos términos más alejados ti y tj del conjunto P que corresponde a la distancia más grande Dij de 55 la matriz T de distancias;

(iii) para cada término tk del conjunto P, examinar si la distancia Dki entre el término tk y el término ti es más pequeña que la distancia Dkj entre el término tk y el término tj, si es así, asignar el término tk a la parte P1 y si no es así, asignar el término tk a la parte P2;

60

(iv) repetir la etapa (i) hasta obtener el número N de puntos Pi deseado y en cada iteración se aplican las etapas (ii) y

5

15

25

35

45

55

(iii) en los términos de las partes P1 y P2.

6. Procedimiento de indexación según la reivindicación 4 ó 5, caracterizado porque comprende una optimización a partir de las N partes desunidas {P1, P2,... PN} del conjunto P así como de los N términos {t1, t2, tN} que las representan para reducir el error de descomposición del conjunto P en N partes, y porque comprende las siguientes etapas:

(i) calcular los centros de gravedad Ci de las partes Pi

**(Ver fórmula)**

cuando se sustituyen los términos tj de la parte Pi respectivamente por Ci y por ti,

(iii) comparar εti y εCi y sustitución de ti por Ci si εCi ≤εti,

(iv) calcular la nueva matriz T de distancias entre los términos ti de la base de términos y procedimiento de descomposición del conjunto P de los términos de la base de términos (3) en N partes, salvo si se cumple una

condición de parada con

**(Ver fórmula)**

7. Procedimiento de indexación según cualquiera de las reivindicaciones 1 a 6, caracterizado porque para efectuar una estructuración del diccionario de conceptos (5), se produce de manera iterativa en cada iteración una carta de navegación empezando por dividir el conjunto de los conceptos en dos subconjuntos, y luego seleccionando un subconjunto en cada iteración hasta la obtención del número de grupos deseado o hasta que se satisface un criterio de parada.

8. Procedimiento de indexación según la reivindicación 7, caracterizado porque el criterio de parada está constituido por el hecho de que los subconjuntos obtenidos son todos homogéneos con una pequeña desviación estándar.

9. Procedimiento de indexación según la reivindicación 7 u 8, caracterizado porque durante la estructuración del diccionario de conceptos (5), se determinan indicadores de navegación a partir de una matriz

**(Ver fórmula)**

del conjunto C de los conceptos

**(Ver fórmula)**

(i) calcular un representante w de la matriz M

~

(ii) calcular la matriz de covarianza M entre los elementos de la matriz M y el representante w de la matriz M,

(iii) calcular un eje de proyección u de los elementos de la matriz M,

(iv) calcular el valor pi = d(u,ci) -d(u, w) y descomponer el conjunto de conceptos C en dos subconjuntos C1 y C2 de la siguiente manera:

(v) almacenar en el nudo asociado a C las informaciones {u, w, |p1|, p2} en la que p1 es el máximo de todos los pi ≤ 0 y p2 es el mínimo de todos los pi > 0, constituyendo el conjunto de las informaciones {u, w, |p1|, p2} los indicadores de navegación en el diccionario de conceptos (5).

**(Ver fórmula)**

10. Procedimiento de indexación según cualquiera de las reivindicaciones 1 a 9, caracterizado porque se analizan a la vez las componentes estructurales y el complemento de estas componentes estructurales constituido por las componentes texturales de una imagen del documento, y porque:

(a) durante el análisis de las componentes estructurales de la imagen

(a1) se procede a un reparto de las zonas fronteras de las estructuras de la imagen en diferentes clases según la orientación de la variación local de intensidad de manera que define los elementos de soporte

5

15

25

35

45

55

estructural (ESS) de la imagen, y

(a2) se procede por análisis estadístico a la construcción de términos constituidos por vectores que describen las propiedades locales y globales de los elementos de soporte estructurales,

(b) durante el análisis de las componentes texturales de la imagen

(b1) se procede a una detección y una caracterización paramétrica de una componente puramente aleatoria de la imagen,

(b2) se procede a una detección y una caracterización paramétrica de una componente periódica de la imagen,

(b3) se procede a una detección y una caracterización paramétrica de una componente direccional de la imagen,

(c) se reagrupa en un número limitado de conceptos el conjunto de los elementos descriptivos de la imagen constituidos por una parte, por los términos que describen las propiedades locales y globales de los elementos de soporte estructurales y por otra parte, por los parámetros de las caracterizaciones paramétricas de las componentes aleatoria, periódica y direccional que definen las componentes texturales de la imagen, y

(d) se define para cada documento una huella a partir de las apariciones, de las posiciones y de las frecuencias de dichos conceptos.

11. Procedimiento de indexación según la reivindicación 10, caracterizado porque las propiedades locales de los elementos de soporte estructurales tenidas en cuenta para la construcción de términos comprenden por lo menos el tipo de soporte seleccionado de entre una banda lineal o un arco de curva, las dimensiones de longitud y anchura del soporte, la dirección principal del soporte y la forma y las propiedades estadísticas de los píxeles que constituyen el soporte.

12. Procedimiento de indexación según la reivindicación 10 u 11, caracterizado porque las propiedades globales de los elementos de soporte estructurales tenidas en cuenta para la construcción de términos comprenden por lo menos el número de cada tipo de soportes y su disposición espacial.

13. Procedimiento de indexación según cualquiera de las reivindicaciones 10 a 12, caracterizado porque durante el análisis de las componentes estructurales de la imagen se procede a una prueba previa de detección de la presencia de por lo menos una estructura en la imagen y, en caso de ausencia de estructura, se pasa directamente a la etapa del análisis de las componentes texturales de la imagen.

14. Procedimiento de indexación según cualquiera de las reivindicaciones 10 a 13, caracterizado porque para proceder a un reparto de las zonas fronteras de las estructuras de la imagen en diferentes clases, a partir de la imagen digitalizada definida por el conjunto de los píxeles y(i,j) en la que (i,j) ∈ I x J, designando I y J respectivamente el número de líneas y el número de columnas de la imagen, se calcula la imagen gradiente vertical gv (i,j) con (i,j) ∈ I X J y la imagen gradiente horizontal gh con (i,j) ∈ I x J y se procede a la división de la imagen según la orientación local de su gradiente en un número finito de clases equidistantes, definiéndose la imagen que contiene la orientación del gradiente por la fórmula

**(Ver fórmula)**

se identifican las clases que constituyen regiones de soporte susceptibles de contener elementos de soporte significativos, y a partir de las regiones de soporte, se determinan los elementos de soporte significativos y se catalogan según criterios predeterminados.

15. Procedimiento de indexación según cualquiera de las reivindicaciones 1 a 9, caracterizado porque durante la indexación de un documento multimedia que comprende señales de vídeo, se eligen términos ti constituidos por imágenes clave que representan grupos de imágenes homogéneas consecutivas, y se determinen conceptos Ci mediante reagrupamiento de términos ti.

16. Procedimiento de indexación según la reivindicación 15, caracterizado porque para determinar imágenes clave que constituyen términos ti, se elabora en primer lugar un vector de puntuación VS que comprende un conjunto de elementos VS(i) que materializan la diferencia o la similitud entre el contenido de una imagen de índice i y el de una imagen de índice i-1, y se analiza el vector de puntuación VS con el fin de determinar las imágenes clave que corresponden a los máximos de los valores de los elementos VS(i) del vector de puntuación VS.

17. Procedimiento de indexación según la reivindicación 16, caracterizado porque una imagen de índice j se considera como una imagen clave si el valor VS(j) del elemento correspondiente del vector de puntuación VS es un máximo y el valor VS(j) se sitúa entre dos mínimos min G y min D y el mínimo M1 tal que M1 = (|VS(j) -min G|, |VS(j) min D|) es superior a un umbral dado.

18. Procedimiento de indexación según cualquiera de las reivindicaciones 1 a 9, caracterizado porque durante la indexación de un documento multimedia que comprende componentes de audio, se toman muestras y se descompone el documento en tramas, que se reagrupan a continuación en clips de los que cada uno se caracteriza por un término ti constituido por un vector de parámetro.

19. Procedimiento de indexación según la reivindicación 18, caracterizado porque una trama comprende entre aproximadamente 512 y 2048 muestras del documento de audio del que se han tomado muestras.

20. Procedimiento de indexación según la reivindicación 18 ó 19, caracterizado porque los parámetros tenidos en cuenta para la definición de los términos ti comprenden informaciones temporales que corresponden a por lo menos uno de los siguientes parámetros: la energía de las tramas de la señal de audio, la desviación estándar de las energías de las tramas en los clips, la relación de las variaciones sonoras, la relación de baja energía, la tasa de oscilación alrededor de un valor predeterminado, la alta tasa de oscilación alrededor de un valor predeterminado, la diferencia entre el número de tasa de oscilación por encima y por debajo de la tasa de oscilación media de las tramas de clips, la varianza de la tasa de oscilación, la relación de las tramas silenciosas.

21. Procedimiento de indexación según cualquiera de las reivindicaciones 18 a 20, caracterizado porque los parámetros tenidos en cuenta para la definición de los términos ti comprenden informaciones frecuenciales que corresponden a por lo menos uno de los siguientes parámetros: el centro de gravedad del espectro de frecuencia de la transformada de Fourier corta de la señal de audio, la anchura de banda de la señal de audio, la relación entre la energía en una banda de frecuencia y la energía total en toda la banda de frecuencia de la señal de audio de la que se han tomado muestras, el valor medio de la variación del espectro de dos tramas adyacentes en un clip, la frecuencia de corte de un clip.

22. Procedimiento de indexación según cualquiera de las reivindicaciones 18 a 21, caracterizado porque los parámetros tenidos en cuenta para la definición de los términos ti comprenden por lo menos la modulación de energía a 4 Hz.

23. Procedimiento de indexación según cualquiera de las reivindicaciones 1 a 14, caracterizado porque se analizan las formas de una imagen de un documento según las siguientes etapas:

(a) proceder a una multirresolución seguida por una decimación de la imagen,

(b) definir la imagen en el espacio logarítmico polar,

(c) representar la imagen o la porción de la imagen afectada por su transformada de Fourier H,

(d) proceder a una caracterización de la transformada de Fourier H de la siguiente manera:

(d1) se proyecta H en varias direcciones para obtener un conjunto de vectores cuya dimensión es igual a la dimensión del movimiento de proyección,

(d2) se calculan las propiedades estadísticas de cada vector de proyección, y

(e) se representa la forma de la imagen por un término ti constituido por los valores de las propiedades estadísticas de cada vector de proyección.