MÉTODO Y SISTEMA PARA IDENTIFICAR ELEMENTOS QUE PERTENECEN A UNA REGIÓN CONEXA.

Método y sistema para identificar elementos en una región limitada que pertenecen a una región conexa,

dichos elementos se almacenan (101, 106) para ser procesados (104) y posteriormente marcados (107) y para evaluar si el elemento cumple las condiciones de pertenencia a la región conexa y, en caso afirmativo, se almacenan (105) y se elige, al menos otro elemento adyacente al elemento evaluado, cumpliendo ser no-marcado para evaluar si cumple las condiciones de pertenencia.

Gracias a la presente invención no es necesario procesar todos los elementos del espacio fuera de la periferia de la ROI. La presente invención es aplicable para procesar conjuntos de datos espaciales escasos, como en la segmentación y registro de imágenes y en la proyección y retroproyección en la reconstrucción tomográfica de imágenes.

Tipo: Patente de Invención. Resumen de patente/invención. Número de Solicitud: P201130705.

Solicitante: UNIVERSIDAD POLITECNICA DE MADRID.

Nacionalidad solicitante: España.

Inventor/es: SPORTELLI,GIANCARLO, SANTOS LLEO,ANDRÉS.

Fecha de Publicación: .

Clasificación Internacional de Patentes:

  • G06K9/48 FISICA.G06 CALCULO; CONTEO.G06K RECONOCIMIENTO DE DATOS; PRESENTACION DE DATOS; SOPORTES DE REGISTROS; MANIPULACION DE SOPORTES DE REGISTROS (impresión per se B41J). › G06K 9/00 Métodos o disposiciones para la lectura o el reconocimiento de caracteres impresos o escritos o el reconocimiento de formas, p. ej. de huellas dactilares (métodos y disposiciones para la lectura de grafos o para la conversión de patrones de parámetros mecánicos, p.e. la fuerza o la presencia, en señales eléctricas G06K 11/00; reconocimiento de la voz G10L 15/00). › codificando el contorno de la forma.
MÉTODO Y SISTEMA PARA IDENTIFICAR ELEMENTOS QUE PERTENECEN A UNA REGIÓN CONEXA.

Fragmento de la descripción:

Método y sistema para identificar elementos que pertenecen a una región conexa.

SECTOR TÉCNICO

La presente invención pertenece al campo del análisis numérico y la computación. En particular, esta invención describe un método y aparato para buscar todos los elementos de un subconjunto conexo incógnito dentro de una matriz genérica dada. Más en el específico, la invención proporciona las coordenadas en n dimensiones del subconjunto conexo de la matriz dada, definido mediante una o más propiedades sobre sus elementos.

ANTECEDENTES DE LA INVENCIÓN

Los problemas que involucran grandes matrices multi-dimensionales pueden ser prohibitivos sin el uso de estrategias eficientes de aceleración de procesado. En las ciencias de la computación, varios algoritmos se aceleran típicamente usando las siguientes técnicas: paralelización y procesado selectivo. La primera es aplicable cuando es posible exponer la independencia entre elementos de forma que múltiples elementos pueden ser procesados concurrentemente en varias unidades de computación. La aceleración alcanzable de esta forma es entonces aproximadamente proporcional al número de unidades de computación disponibles. En la última década, la paralelización ha empezado a ser considerada un paradigma estándar de computación más que una especifica técnica de aceleración, tal como proponen: J. Wawrzynek, D. Patterson, M. Oskin, Shin-Lien Lu, C. Kozyrakis, J. C. Hoe, D. Chiou & K. Asanovic. RAMP: Research Accelerator for Multiple Processors. Micro, IEEE, vol. 27, no. 2, pp. 46 -57, 2007.

El procesado selectivo es aplicable más generalmente, aunque es conveniente sólo bajo dos condiciones. Primero, los elementos que necesitan ser procesados, o actualizados, tienen que ser una pequeña fracción de todo el conjunto de datos en entrada. Segundo, la técnica de discriminación de elementos tiene que ser lo suficientemente rápida para no contrastar la aceleración obtenida por ignorar parte de los datos en entrada. En tal caso, la aceleración depende fuertemente del problema específico y puede superar de órdenes de magnitud la aceleración proporcionada por la computación paralela, así que podría hacer viable una técnica que no lo sería de otra forma.

Hay muchas aplicaciones en las cuales el problema a resolver respeta la primera condición, en particular las relacionadas al uso de de datos espacio-temporales.

Los conjuntos de datos espacio-temporales se usan más comúnmente en rendering gráfico, imágenes médicas y simulaciones físicas de elementos finitos. La segmentación (S. C. Zhu & A. Yuille. Region competition: Unifying snakes, region growing, and Bayes/MDL for multiband image segmentation. Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 18, no. 9, pp. 884-900, 1996) y el registro (B. Zitova & J. Flusser. Image registration methods: a survey. Image and vision computing, vol. 21, no. 11, pp. 977-1000, 2003) (R. J. Althof, M. G.

J. Wind & J. T. Dobbins III. A rapid and automatic image registration algorithm with subpixel accuracy. Medical Imaging, IEEE Transactions on, vol. 16, no. 3, pp. 308-316, 1997) de imágenes, la proyección, retro-proyección y reconstrucción tomográfica (J. L. Herraiz, S. Espana, J. M. Udias, J. J. Vaquero & M. Desco. Statistical Reconstruction Methods in PET: Resolution Limit, Noise, Edge Artifacts and considerations for the design of better scanners. In Nuclear Science Symposium Conference Record, volume 4, p. 5. IEEE, 2005) representan aplicaciones típicas que involucran grandes conjuntos de datos en dos, tres o cuatro dimensiones, en los que la región de interés (ROI) constituye sólo una pequeña parte de todo el campo de vista (FOV) .

Para todos estos tipos de problemas, el grado de conveniencia del procesado selectivo depende directamente de la segunda condición: la complejidad de la técnica de búsqueda de elementos.

Una familia de técnicas de búsqueda se basa en la partición jerárquica. El ejemplo más común de partición jerárquica se basa en los quadtrees (R. A. Finkel & J. L. Bentley. Quad trees a data structure for retrieval on composite keys. Acta informatica, vol. 4, no. 1, pp. 1-9, 1974) .

Los quadtrees, así como sus variantes (árboles binarios, octrees, kd-trees) , permiten procesar múltiples elementos a la vez. Esto es posible a través de la búsqueda de los máximos cuadrantes que contienen elementos iguales (que en nuestro caso serían los elementos que pertenecen a la ROI) , de manera que todos los elementos de los cuadrantes pueden ser almacenados y procesados como si fueran uno.

La definición de quadtree implica que su construcción se hace de forma “top-down". En la practica, el proceso es “bottom-up" y para grandes imágenes puede ser computacionalmente muy costoso, debido al gran numero de operaciones de unión (H. Samet. The design and analysis of spatial data structures, volume 85. Addison-Wesley Reading, MA, 1990) .

Patentes recientes abordan la optimización de los algoritmos de construcción tal como indica US 7, 805, 013 y algoritmos de recorrido como US20040024779 de estructuras tipo quadtree. Aunque la patentes citadas optimizan el uso de las estructuras jerárquicas, todavía requieren el procesado del FOV entero al menos una vez.

Otra familia de técnicas de discriminación, más rápidas a la hora de construir la matriz, son los algoritmos de dibujo. Estos algoritmos son más rápidos en cuanto no requieren procesar todos los elementos, pero son utilizables sólo cuando la condición discriminatoria se relaciona a la posición espacial del elemento dentro del FOV. Un ejemplo común es el algoritmo de Bresenham (J. E. Bresenham. Algorithm for computer control of a digital plotter. IBM Systems journal, vol. 4, no. 1, pp. 25-30, 1965) , el cual determina cuales puntos en un espacio n-dimensional tienen que ser trazados para formar una aproximación de una línea recta entre dos puntos dados. El algoritmo es particularmente rápido además porque requiere sólo sumas de enteros y operaciones de desplazamiento de bits.

Por último, variantes específicas de los algoritmos de dibujo han sido diseñados para optimizar el tiempo de procesado de los elementos extraídos. El algoritmo de Siddon (R. L. Siddon. Fast calculation of the exact radiological path for a three-dimensional CT array. Medical Physics, vol. 12, page 252, 1985) y sus variantes mejoradas (F. Jacobs, E. Sundermann, B. De Sutter, M. Christiaens & I. Lemahieu. A fast algorithm to calculate the exact radiological path through a pixel or voxel space. Journal of computing and information technology, vol. 6, no. 1, pp. 89-94, 1998) son ejemplos de algoritmos de dibujo de líneas, optimizados específicamente para proporcionar información morfológica sobre los elementos extraídos sin ningún coste adicional de computación.

El algoritmo de Siddon fue propuesto para proyectar líneas de respuesta (LOR) en la reconstrucción de imágenes PET y CT en modo lista.

De forma más general, se emplea también para calcular integrales de línea en imágenes médicas (A. Kalemis, D. M. Binnie, M. A. Flower & R. J. Ott. Image intensity normalisation by maximising the Siddon line integral in the joint intensity distribution space. Medical Image Analysis, vol. 13, no. 6, pp. 900-909, 2009) .

La reconstrucción en modo lista superaría varias limitaciones presentes en las técnicas de reconstrucción en modo histograma (A. J. Reader. The promise of new PET image reconstruction. Physica Medica, vol. 24, no. 2, pp. 49-56, 2008) .

Sin embargo, se ha demostrado que el uso del algoritmo de Siddon para la proyección de LOR es sub-óptima e imprecisa (A. Rahmim, J. C. Cheng, S. Blinder, M. L. Camborde & V. Sossi. Statistical dynamic image reconstruction in state-of-the-art high-resolution PET. Physics in medicine and biology, vol. 50, p. 4887, 2005) . Esto es sobre todo porque en el algoritmo de Siddon no se puede configurar el espesor de las líneas, es decir no se pueden proyectar tubos de respuesta (TOR) , mucho más precisos a la hora de evaluar las propiedades estadísticas de la imagen durante la reconstrucción.

En tomografía por emisión (PET y SPECT) , la propiedad evaluada para determinar si un elemento i pertenece a la ROI es la probabilidad que uno o dos fotones detectados sobre la LOR j hayan sido emitidos desde el punto i. Por consiguiente, la forma de la ROI corresponde a la distribución de probabilidades a lo largo de todo el FOV. Aunque idealmente el punto de emisión tiene que pertenecer a la LOR, por efecto de varios fenómenos físicos, puede alejarse de ella. Por esta razón se buscan tubos más que líneas de respuesta. Sin embargo la distribución de probabilidad...

 


Reivindicaciones:

1. Método para identificar elementos en una región de interés que pertenecen a una región conexa (501) a partir de un elemento semilla (504) perteneciente a la región de interés, caracterizado por que comprende las siguientes etapas:

(a) a partir del elemento anterior, generar al menos un elemento adyacente (505, 506, 510, 517) dentro de la región conexa, comprobar si el elemento generado es no-marcado y,

(b) en caso afirmativo, marcar el elemento generado y evaluar si cumple las condiciones (404) para pertenecer a la región de interés y almacenar el resultado correspondiente,

(c) repetir las etapas (a) y (b) hasta que todos los elementos adyacentes de elementos de la región conexa sean elementos marcados.

2. Método según reivindicación 1, caracterizado por que el paso de generar al menos un elemento adyacente comprende también almacenar dicho elemento en una memoria de trabajo (106) .

3. Método según reivindicación 1 ó 2, caracterizado por que el paso de marcar el elemento generado comprende también almacenar dicho elemento en una memoria de marcas (107) .

4. Método según una cualquiera de las reivindicaciones 1 a 3, caracterizado por que el paso de evaluar si el elemento generado cumple las condiciones para pertenecer a la región de interés comprende almacenar dicho elemento en una memoria de nodos (105) .

5. Método según una cualquiera de las reivindicaciones 1 a 4, caracterizado por que la región limitada es una imagen tomográfica.

6. Método según una cualquiera de las reivindicaciones 1 a 4, caracterizado por que la región limitada es una imagen espacio-temporal segmentada.

7. Método según una cualquiera de las reivindicaciones anteriores, caracterizado por que las condiciones para pertenecer a la región de interés se establecen de acuerdo con criterios geométricos y se evalúan mediante unos medios de procesamiento (104, 805) .

8. Sistema para identificar elementos en una región de interés que pertenecen a una región conexa (501) a partir de un elemento semilla (504) perteneciente a la región de interés, caracterizado por que comprende:

- medios de procesamiento (104, 805) configurados para, a partir del elemento anterior, generar al menos un elemento adyacente (505, 506, 510, 517) dentro de la región conexa, comprobar si el elemento generado es nomarcado y, en caso afirmativo, marcar el elemento generado y evaluar si cumple las condiciones (404) para pertenecer a la región de interés y para almacenar el resultado correspondiente en unos medios de almacenamiento (101, 103, 105, 106, 107, 803) .

9. Sistema según la reivindicación 8, caracterizado por que comprende además una interfaz de usuario (108) para introducir las condiciones a evaluar que definen la región de interés.

10. Sistema según la reivindicación 8 ó 9, caracterizado por que los medios de almacenamiento (101, 103, 105, 106, 107, 803) comprenden una memoria para elementos marcados (107) y una memoria para elementos de la región de interés (105) .


 

Patentes similares o relacionadas:

Representación de una forma con la ayuda de Transformadas de Fourier, del 27 de Junio de 2012, de MONRO, DONALD MARTIN: Un método de aproximación de un contorno de iris, que comprende las etapas de: (a) adquirir una imagen de un ojo, incluyendo un contorno de iris; (b) señalar una pluralidad […]

PROCEDIMIENTO PARA EL RECONOCIMIENTO OPTICO DE CARACTERES ALFANUMERICOS., del 1 de Diciembre de 2006, de SICK AG: Procedimiento para el reconocimiento óptico de caracteres alfanuméricos con las siguientes etapas: a) en una base de datos se depositan los contornos exteriores y los contornos […]

APARATO Y METODOS PARA RECONOCER UNA IMAGEN ESPECIFICA A PARTIR DE UNA SEÑAL DE IMAGEN DE ENTRADA., del 16 de Septiembre de 2002, de RICOH COMPANY, LTD.: SE OBTIENE UN RECTANGULO CIRCUNSCRITO DURANTE UNA PARTE DE LA IMAGEN CONTINUA NEGRA USANDO UNA SEÑAL DE IMAGEN DE DOS TONOS. SI SE DETERMINA (EN S105) […]

PROCEDIMIENTO PARA DERIVAR CARACTERISTICAS DE UN CARACTER EN UN SISTEMA DE RECONOCIMIENTO DE CARACTERES., del , de KONINKLIJKE PTT NEDERLAND N.V.: UN METODO PARA DEDUCIR CARACTERISTICAS DE CARACTERES EN UN SISTEMA DE RECONOCIMIENTO DE CARACTERES PARA EL RECONOCIMIENTO DE CARACTERES TALES COMO LETRAS Y NUMEROS, Y UN […]

METODO Y APARATO PARA EL TRATAMIENTO DE IMAGENES CON SIMBOLOS CON BORDES DENSOS., del 1 de Agosto de 1999, de UNITED PARCEL SERVICE OF AMERICA, INC.: SE PRESENTA UN SISTEMA PARA LOCALIZAR UN OBJETO POR LO MENOS DENTRO DE UNA IMAGEN DE INTENSIDAD. EL SISTEMA INCLUYE UN ELEMENTO PARA ANALIZAR LA IMAGEN DE INTENSIDAD […]

METODO PARA LA CREACION AUTOMATICA DE MODULOS DE EXPLORACION., del 16 de Junio de 1995, de FMC CORPORATION: METODO PARA LA CREACION AUTOMATICA DE MODULOS DE EXPLORACION EN UN SISTEMA DE TRATAMIENTO DE ARTICULOS QUE FUNCIONA PARA HACER DETERMINACIONES DE DISCRIMINACION-IDENTIFICACION […]

SENSOR DE CAMARA DE ALTA DEFINICION QUE CONTIENE UNA MATRIZ LINEAL DE PIXELS Y METODO PARA EXPLORAR LA POSICION DE UN BORDE MARGINAL DE UN OBJETO., del 1 de Julio de 1994, de FMC CORPORATION: SENSOR DE CAMARA DE ALTA DEFINICION QUE TIENE UNA MATRIZ LINEAL DE PIXELS Y METODO PARA EXPLORAR LA POSICION DE UN BORDE MARGINAL DE UN OBJETO QUE SIRVE […]

SISTEMA DE IDENTIFICACION DE LLAVES., del 1 de Marzo de 2007, de THE HILLMAN GROUP, INC.: Método para identificar una llave en bruto a partir de una llave maestra , comprendiendo el método: asegurar una primera fuente de luz uniforme en una posición […]

Utilizamos cookies para mejorar nuestros servicios y mostrarle publicidad relevante. Si continua navegando, consideramos que acepta su uso. Puede obtener más información aquí. .