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

Método y sistema para identificar elementos en una región limitada que pertenecen a una región conexa y divisible en sub-regiones convexas,

dichos elementos se almacenan (101) para ser procesados (104) como nodos de un esquema a árbol, en el que se mantienen en memoria sólo los nodos padres (106) de cada nodo procesado. El árbol se construye eligiendo elementos entre ellos adyacentes según unas reglas de partición por dimensiones.

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. Además los bajos requisitos en memoria hacen la técnica especialmente adapta para ejecutarse en unidades de procesamiento gráfico.

Método y sistema para identificar elementos que pertenecen a una región convexa 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 convexo 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. Esto por ejemplo es el caso de las reconstrucciones tomográficas, de la segmentación y del registro de imágenes, donde las matrices a procesar son imágenes tridimensionales de alta resolución y sus elementos representan características físicas o funcionales en el espacio de un objeto observado. En tomografía por emisión también se computan matrices espaciales de probabilidad a posteriori y de verosimilitud, que describen la probabilidad de emisión dentro un campo de vista, dado un conjunto de fotones observados.

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...

1. Método para identificar elementos que pertenecen a una región de interés convexa (1001) m-dimensional de un campo de visión (508) caracterizado por que comprende:

- para una línea (LOR) que intersecta la región de interés (1001) , hallar las coordenadas de los puntos de intersección (510, 511) pertenecientes a la región de interés (722) ,

- definir una dimensión primaria (507) como aquella dimensión para la cual, la diferencia entre las coordenadas de dichos puntos de intersección es máxima,

- establecer al menos uno de los puntos de intersección (510, 511) como nodo padre primario,

- efectuar, para cada una de las dimensiones de la región de interés (505, 506, 507) , incluida la dimensión primaria:

- una propagación en una dimensión dada, a través de cambiar en al menos una unidad la coordenada de dicha dimensión del nodo padre para definir al menos un nodo hijo (723) ,

- comprobar si el nodo hijo (723) pertenece a la región de interés (1001) para, en caso afirmativo, establecerlo como nodo padre (512) en una próxima propagación en dicha dimensión, y para, en caso negativo, finalizar la propagación en dicha dimensión.

2. Método según reivindicación 1, caracterizado por que la propagación en una dimensión dada se realiza mediante incrementos en la coordenada de dicha dimensión.

3. Método según reivindicación 1, caracterizado por que la propagación en una dimensión dada se realiza mediante decrementos en la coordenada de dicha dimensión.

4. Método según reivindicación una cualquiera de las reivindicaciones anteriores, caracterizado por que el campo de visión es una imagen bidimensional y los elementos de dicha imagen son píxeles con un rango de color dado.

5. Método según una cualquiera de las reivindicaciones anteriores 1 a 3, caracterizado por que el campo de visión es una imagen tomográfica tridimensional captada y los elementos de dicha imagen son vóxeles asociados a la probabilidad de emisión de unos fotones en un volumen.

6. Método según una cualquiera de las reivindicaciones anteriores, caracterizado por que comprende un paso para elegir la línea de respuesta (LOR) basado en un análisis de simetría de la región de interés para asociar dicha línea de respuesta a un eje de revolución.

7. Método según una cualquiera de las reivindicaciones anteriores, caracterizado por que comprende el paso de almacenar las coordenadas de los nodos que pertenecen a la región de interés (1001) .

8. Sistema para identificar elementos que pertenecen a una región de interés (ROI) convexa m-dimensional de un campo de visión (508) caracterizado por que comprende:

- unos medios de procesamiento (104) configurados para trazar una línea (LOR) que intersecta la región convexa y determinar la dimensión primaria como aquella para la que la diferencia entre coordenadas de dichos puntos de intersección es máxima,

- unos medios de almacenamiento (101, 103, 105, 106, 107, 1303) configurados para almacenar las coordenadas de los puntos de intersección (P1, P2) ,

- los medios de procesamiento (104) configurados además para:

- establecer al menos uno de los puntos de intersección (510, 511) como nodo padre primario,

- efectuar, para cada una de las dimensiones (505, 506, 507) de la región de interés (1001) , incluida la dimensión primaria:

- una propagación en una dimensión dada, a través de cambiar en al menos una unidad la coordenada de dicha dimensión del nodo padre para definir al menos un nodo hijo (723) ,

- comprobar si el nodo hijo (723) pertenece a la región de interés (1001) para, en caso afirmativo, establecerlo como nodo padre (512) en una próxima propagación en dicha dimensión, y para, en caso negativo, finalizar la propagación en dicha dimensión.

9. Sistema según la reivindicación anterior, caracterizado por que los medios de almacenamiento comprenden una memoria de entrada (101) para almacenar las coordenadas de los elementos del campo de visión (508) , siendo dicha memoria de entrada accesible por los medios de procesamiento (104) .

10. Sistema según una cualquiera de las reivindicaciones anteriores 8 a 9, caracterizado por que comprende una 5 interfaz cliente (108) configurado para establecer las condiciones que debe cumplir un elemento del campo de visión (508) para pertenecer a la región de interés (1001) .