ES2635245T3 - Método implementado por ordenador para la identificación de canales a partir de datos representativos en volumen 3D y un producto de programa de ordenador que implementa el método - Google Patents

Abstract

Un método implementado por ordenador para la identificación de canales a partir de datos representativos en un volumen 3D, que comprende la identificación, en un volumen 3D de un objeto, tres zonas diferentes basándose en los valores de al menos un parámetro físico y/o funcional representativo de propiedades físicas y/o funcionales de dicho objeto, como una zona de un primer tipo (H), una zona de un segundo tipo (BZ) y una zona de un tercer tipo (C), donde dichos primero, segundo y tercero tipos de zona son diferentes entre sí, caracterizado porque el método comprende realizar los pasos siguientes mediante el procesamiento de dichos datos representativos: - identificar automáticamente como un canal candidato (bz) un camino que discurre a través de dicha zona de un segundo tipo (BZ) y que se extiende entre dos puntos de dicha zona de un primer tipo (H); y - llevar a cabo de forma automática, en un espacio topológico (H_and_BZ_topo) que incluye la zona de un primer tipo (H) y la zona de un segundo tipo (BZ) y no incluye la zona de un tercer tipo (C), operaciones homotópicas entre 15 dicho canal candidato (bz) y caminos (h) que discurren sólo a través de dicha zona de un primer tipo (H), y si el resultado de dichas operaciones homotópicas es que el canal candidato (bz) no es homotópico a ningún camino discurriendo sólo a través de la zona de un primer tipo (H) se identifica el canal candidato (bz) como un canal restringido.

Description

Mélodo implementado por ordenador para la identificación de canales a partir de datos representativos volumen 3D y un producto de programa de ordenador que implementa el método

en un

Campo de la técnica

5

La presente invención se refiere, en general, en un primer aspecto, a un método implementado por ordenador para la identificación de canales de datos representativos en un volumen 3D. y mas particularmente a un método que comprende identificar automáticamente los canales restringidos por medio de las relaciones entre caminos homótopicos, en un espacio topológico,

10

La invención se refiere también, en un segundo aspecto, a un producto de programa de ordenador que implementa los pasos del método del primer aspecto de la invención

El término canal tiene que ser entendida en la presente invención en un sentido amplio como cualquier estructurapasaje que se comunica o que habia comunicado en el pasado (en el caso de un pasaje bloqueado) dos zonas distantes, tales como, entre otros, un gas o canal de~ nuido, un canal de la sang re y un canal conductor de la electricidad.

15

Estado de la técnica anterior

20 25

En el campo de las arritmias, la cicatriz producida por un infarto puede generar taquicardia ventricular (VT del inglés Ventricular Tachycardia), debido a la presencia de canales conductores anómalos (CC) dentro del ventriculo izquierdo (LV del inglés Left Ventricle), también Ilam;ados canales re-entrantes. La presencia de CC causando reentradas esta estrechamente conectada con el aislamiento de los trayectos de propagación de estimuladÓn. Re-entrada sólo es posible si el frente de onda de estimuladón se divide en partes que pueden viajar de forma independiente a diferen tes velocidades durante una cantidad de tiempo. Esto requiere al menos que uno de los caminos de estimulación vaya a través del tejido con propiedades conductoras lenlas (tejido Bl del inglés Border lone) con respecto al tejido sano normal. Además una barrera no conductiva entre el camino que atraviesa la 8l y todos los caminos de la estimulación normal es nece~saria, de lo contrario no se generan caminos de activación transversales suavizando el frente de onda y ajustar las velocidades de conducción (Figura 1), Por lo tanto un criterio necesario para un CC es la ausencia de esos caminos de activación transversal a lo largo de una dirección determinada. O, en otras palabras, un obstáculo no conductor (Core del tejido de I¡:¡ dc¡:¡triz) entre el can¡:¡1 en el medio lento (8l) y cualquier camino de acceso en el medio rápido (tejido sano) Por Jo tanto, los canales de conducción son los canales restringidos.

3Q 35 40

Por lo tanto, la identificación de los canales conductores de miocardio se ha convertido en una necesidad en el campo de la electrofisiologia (EP del inglés electrophysiology) , la especialidad cardiológica que trata a los pacientes con arritmia. La arritmia puede ser el resultado de muchas causas, entre ellas la cicatrización del tejido del corazón causada por un ataque al corazón Ademas. la arritmia cardiaca puede ocurrir en cualquiera de las camaras del corazón y también puede ser clasificada de acuerdo a ta frecuencia de latido cardiaca que producen. En particular, en esta invención nos centraremos en arritmias asocialjas a la cicatriz taquicardia ventricular (VT) , y que es sabido se debe a la presencia de canales conductores anómalos (CC) en el ventriculo izquierdo (LV), también llamados canales re-entrantes, Si un ataque al corazón produce tejido de cicatriz dentro del miocardio. y esta cicatriz es tal que tiene canales dentro de si mismo, estos canales , que son debido a la presencia de miocitos viables en el interior del tejido de la cicatriz. pueden generar circuitos reentmntes asociados con VT. El tratamiento eficaz de la VT puede realizarse con ablación por radiofrecuencia utilizando un catéter que se Insena en las anerlas para alcanzar el endocardio o el epicardio. Una vez alli, el catéter se utiliza por el EP para producir una lesión en el CC en el músculo del corazón, en un lugar que detendrá la arritmia. Esta ubicación tiene que ser identificada con cuidado para evitar la creación de lesiones en el tejido viable que no está contribuyendo al problema de arritmia,

45 50 55

Actualmente, EP utiliza un dispositivo de «navegaciónl+ para llevar a cabo un mapeo electro-anatómico (EAM) del endocardio. El dispositivo de navegación utiliza una tec.nologia de seguimiento 3D para determinar ta posición de la punta del catéter. La anatomia del corazón del pacienle está disponible antes de la operación a partir de las exploraciones volumétricas obtenidas a partir de dispositivos de CT o MR Las tomografias volumétricas producen imagenes estaticas al final de la sístote ca rdiaca Mas tarde, durante la intervención con catéter, la exploración volumétrica puede ser ca-registrada con el corazón del paciente, basándose en el sistema de coordenadas recogida por el catéter mientras explora el miocardio. Esto permite que el sistema de navegación pueda visualizar el corazón (e l endocardio aparece por lo general como una malla poligonal eldraida de los datos volumétricos correspondientes a la pared endocardio) junto con una imagen del cateter en su posición 3D. El catéter también puede leer los voltajes de su punta para medir la actividad eléctrica en las paredes del corazón. El caléter se utiliza para mapear las paredes del endocardio y del epicardio, moviendo y arrélstrando la punta a lo largo de la pared para obtener ta mayor cantidad de lecturas como sea posible a fin de obteneir el cuadro más completo posible de los voltajes. El voUaje indica la condición del músculo del corazón, con la serial de tejido cicatricial en el eldremo inferior de la gama, y el tejido sano dando la máxima. Este es un proceso laborioso que reQuiere generalmente cientos de lecturas de punto, Estas lecturas se interpolan por el dispositivo de navegación para producir un mapa de los voltajes. Entonces. el EP intenta inducir arritmia por estimular el corazón en diferentes puntos a lo largo de sus caminos de conducción, con el

2

fin de identificar las fuentes de actividad eléctrica anorrnal. Usando la información visual proporcionada por el mapa de voltaje, el EP tiene que decidir dónde realizar la ablación para eliminar la arritmia _Una vez localizado el mejor punlo para ablación, el catéter se coloca de nuevo en ese punto, y la RF se utiliza para producir una lesión en el musculo. A continuación, el EP trata de inducir la arritmia, y si no se repite, el paciente se considera tratado con éxito.

Este proceso tarda de tres a cuatro horas. Esto limita el número de pacientes que pueden tener acceso a este tratamiento. También son procedimientos fatigosos para el equipo clínico, asl como de riesgo de radiación ya que implica una ciena cantidad de radiación debido al uso de fluoroscopia para controlar la posición del catéter en ciertos intervalos de la intervención Tal proceso de tres a cuatlto horas de largo también implica un alto riesgo para la salud del paciente_

En la patente US 2009(0076375 A1 se describe un catéter de ablación con información de imagen, para uso en un proceso de ablación, lo que permite la identificación automatica del tejido con caminos de conducción dañados Cdamaged conduclion path tissue") mediante el procesado de las imágenes 3D con un programa que se ejecuta en un dispositivo de control, y mediante la implementación de algoritmos de procesado de imagen, por ejemplo los que típicamente permilen la detección de aristas o permiten desviaciones en la estructura en áreas especificas de una imagen o de patrones para ser detectados. La identificación automática se realiza en el lejido que contiene caminos de conducción dañados, pero no en el cam ino de conducción en sí .

Recientemente, con la llegada de un protocolo MR cOl1ocido como realce tardio, se ha hecho posible visualizar el tejido de la cicalriz en el corazón (en pacientes sin un desfibrilador; los desflbriladores de próxima generación seran compatibles con la MR y esta limitación desaparecer~I). Estos volúmenes DE-MRI capturan información desde la salud grupos de celulas musculares para revelar que zonas pertenecen a cicatriz y cuales a tejidos sanos, como se define por un rango de valores de intensidad de señal que ponen la cicatriz como el más alto y el saludable como el más bajo. Se dasifica como lona Fronteriza (Bl de Border lone en inglés) aquellas células todavía viables de la cicatriz que tienen valores de intensidad oscilando entre el rango del núdeo de la cicatriz y el tejido lotalmenle sano. los volúmenes DE-MRI se pueden visualizar de varÍiOis formas para producir una imagen que será interpretada visualmente por el EP, con el fin de determinar dónde se encuentran los posibles puntos del miocardio que inducen arrilmias. Estos CC son estructuras en tres dimensiones y son dificiles de visualizar ya que pueden funcionar dentro del miocardio en cualquier dirección, ya sea a lo largo de las paredes o entre ellas Esto requiere en primer lugar el procesamiento del volumen la MRI-DE para identificar las supeñlcies endo y epicardicas del LV con el fin de ser capaz de enfocar la visualización sobre el miocardio. Una vez identificado el miocardio entonces los valores de la dcatriz, Bl y el tejido sano se pueden interpretar con mayor claridad y no ser confund idas con la sangre contenida dentro del ventriculo izquierdo,

Hay varias formas de visualizar por ordenador el miocardio resultante. La más sencilla es realizar un reformateo multiplanar del volumen, para mostrar los valores COrnlO inlensidades a lo largo de planos que cortan el volumen. Esto se hace generatmente ya sea a lo largo de los planos de adquisición, o mediante la definición de nuevos ejes sobre el volumen correspondiente a la anatomia del paciente, como por ejemplo el eje cono de la LV.

Otro método de visualización de una MRI es reconstruir (render) el miocardio y hacer que aparezca como si fuese visto en la realidad, como un objeto aislado, usando léc,nicas graficas de proyección de perspectiva y "sombreado"

Los presentes inventores desarrollaron una técnica de visualización que comienza a panir de las paredes segmentadas de la endo y epi-Cardium (ver (7) para el método de segmentación utilizado), e interpola un número variable de superficies en el medio (ver [2J para el método de visualización). Estas superficies, o capas, son mallas poligonales, y su número se optimiza para capturar loda la información dentro del miocardio, Con pocas capas se podrían no ver cienos CC, y con demasiadas capas se invertida excesivo tiempo y recursos en información duplicada.

Las superficies interpoladas, siguiendo un principio similar a las capas de una cebolla, cortan el miocardio y toman el valor correspondiente al de la intensidad de la DE-MRI El valor que toman se presenta como un código de colores para ayudar en la visualización. En particular, los valores altos (nucleo de la cicatriz , O SCAR) se asignan al color rojo, los valores bajos al violeta (tejido sano), y los valores intermedios oscilan entre amarillo y verde (Bl). Los umbrales utilizados para asignar colores a valores de superficie pueden ser controlados por el usuario_

El EP inspecciona visualmente cada capa para detectar canales. Dado que los canales transcurren dentro del miocardio, por lo general a una profundidad de al menos un 10% del endocardio, y pueden incluso ser perpendiculares a las capas interpoladas, es facil pas21rlos por alto usando simple inspección visual La inspección de ce en las capas de todo el miocardio depende en gran medida de la experiencia del EP Esto conlleva girar manualmente el miocardio para verlo desde todos 10:5 ángulos posibles, y para hacer esto por todas las capas creadas Cuantas mas capas generadas, mas precisa sera la visualización y el menos las posibilidades de perder un canal conductor que pueda no aparecer al caer entre las capas Pero al mismo tiempo, mayor sera el tiempo de procesado_ Pero eslo s610 cubre aquellos CC cuyo recorrido transcurra Inlegramente a lo largo de una capa Para aquellos CC que no caen claramente en capas, es muy dificil para el ojo humano seguirlos a través de las capas, ya que eslo conlleva visualizar en la mente el cambio entre las capas y el seguimiento de las entradas y salidas de la

CC.

Por otra parte, la referencia [8] también describe la identificación de los canales de conducción en datos volumétricos en 3D obtenidos de RM realzada con realce tardio, por medio de la distribución de intensidad de señal, que hace definir las zonas de tejido Sanas (H), Fronleri2:a (82) y Cicatriz (S) mencionadas anteriormente, aunque en este articuto la 82 se conoce como tejido heterogénno En [8] la identificación final CC se realiza mediante la inspección visual, y se refieren a todo el tejido heterogéneo {Hn como un cana l conductor (llamado canal de HT), y no se especifica si se lleva a cabo una identificación más precisa de un canal conduelor dentro de la zona heterogénea del tejido.

La referencia (16] se describe el estado de la técnica en cuanto a los últimos avances en la cardiologia computacional, incluyendo el uso de. entre otros. la taquicardia ventricular, de los modelos 3D cardiacas y su uso en los procedimientos de diagnóstico. Ninguno de diclhOs desarrollos mas nuevos describe una identificación automática completa de canales.

Una identificación automática de los CC sola se conOCI~ a partir de otra tipa de fuente que na es datas de imagen 3D, coma es el casa de US 6,236,88381 '1 el documenta JP 2008237882 A, en donde el primera usa características de ECG mientras que el segundo usa el 'pace mapping'.

En resumen, los métodos conocidos hasta ahora para idlentiflcar los canales en un volumen 3D sólo son automáticos hasta que las diferentes zonas se muestran en una pantalla con el fin de permitir que el EP pueda identificar visualmente los CC, es decir, este último paso no se realiza de forma automática. Este es el caso de (7] y de una implementación de software del mismo desarrollado por los presentes inventores (5J.

Algunas otras publicaciones están disponibles descri'biendo dicho software '1 los resultados obtenidos con su aplicación en casos reales 11 ] [2J [3].

Otras pUblicaciones están disponibles, que se pueden cl:)nsiderar como técnica anterior a la presente invención, pero que no dan a conocer la identificación automática de los. CC. Algunos grupos de investigación han estado trabajando en el post-procesamiento de OE-MRI imágenes cardiacas, y algunos de ellos han desarrollado y publicado mélodos para evaluar las características de la cicatriz post-infarto asociados con VT Ver [4], [9], [10J Y [11J .

Otros ejemplos de las herramientas comerciales dispiJnibles para la visualización en 30 y la segmentación del corazón son :

•

CMRtools (http://woNw.cmrtools.com)

•

TomTec (hl1p:lfwww.tomtec.de)

, Segmento (hllp:/lmedviso.com/products/segmentl) M

' MEDIS

, PIE MEOICAL

La patente US 20111224962 Al da a conocer un sistema que simula la estimulación de tejido de la cicatri2 identificado en un modelo 3D de un corazón de pacienle obtenido a partir de imagen volumétrica 3D. A partir de la imagen segmentada de dicho corazón del paciente, que contiene tejido normal y deteriorado, se simula la propagación eléctrica de acuerdo con los umbrales de intensidad de luminancia

Un procesador de estimulacio" simula la estimulación eléctrica del corazón del paciente utilizando el modelo para identificar el riesgo de deterioro del corazón.

El sistema identifica automáticamente el riesgo de rápid,:)s, ritmos card iacos potencialmente peligrosos y el infarto de miocardio mediante la simulación de circuitos de laquicardia ventricular utilizando in-vivo MRI y un modelo Simplificada de la electrofisiología cardiaca para la eS'\ratiflcación del riesgo no invasivo para la muerte cardiaca sUbita .

la identificación automatica divulgada en el documento US 20111224962 A 1. Y realizada por imagen volumétrica 30 segmentada, sólo está relacionada con la identificación de las áreas de dicho tejido cicatriz, tejido deteriorado '1 tejido normal.

Aunque US 20111224962 A1 admite la influencia de los circuitos de reentrada alrededor de las cicatrices del infarto en la taquicardia ventricular, lo que indica que dichos circuitos pueden ser las áreas que contienen complejos de conducción lenta y múltiples vías de reentrada, en el documento US 20111224g62 A1 no se divutga la identificación automatica de dichas vias, ni de cualquier canal o de cualquier otro elemento dentro de cualquiera de dichas áreas identificadas En otras palabras, los circuitos de taquicardia ventricutar sólo se simulan pero no idenlifican automáticamente en absoluto.

Ningún método es conocido en el estado de la técnica que realice dicho último paso, es decir, el relativo a la identificación de los canales conductores, de forma automática, con respecto a los canales conductores del miocardio.

Además de dicha identificación de canales conductores del miocardio. hay muchos airas campos de aplicación donde muchos tipos de objetos incluyen las 20nas que son susceptibles de incluir canales restringidos o lim itados para ser identificados, como el gas subterráneo o canales de fluido en el campo de la exploración geofisica. grietas en la industria mecanica o cualquier tipo de canales en BI campo de la medicina o veterinaria.

Ningún método es conocido en el estado de la técnica, que realice la idenlificación automática de tales canales restringidos de dichos otros campos de aplicación

la patente US 8.310,233 B2 describe un método para la reconstrucción de la imagen a partir de datos submuestreados de imágenes médicas, tales como datos de MRI, por minimizar iterativamente una función objetiva que incluye una cóncava métrica que es homotópica con un 10-nonn, En airas palabras, el método descrito en dicha patente utiliza homotopías entre normas, un concepto que no está relacionado con los espacios topológicos si no con espacios vectoriales. Además, dichos homotopías no se utilizan para determinar las propiedades de caminos o canales si no para resolver un problema de minimización.

la patente US 7,991,22181 da a conocer un sistema de procesamiento de datos que utiliza métodos topológicos para manipular y clasificar conjunlos de datos n-dimensionales, para evaluar una convolución de dos o más objetos geométricos utilizando al menos cantidades numéricas dadas por los calculas de un invariante topológico algebraico incluyendo uno de : homologla, cohomologia , homolo!~ia relativa, cohomologia relativa, grupos de homotopía, K-teoría, la homologla generalizada o cohomologia generalizada.

Entre las posibles aplicaciones del sistema de US 7,991 ,221 81 , se menciona la medicina y, más específicamente, el uso de la densidad de homologia para el esludio de vías cerebrales mediante el etiquetado local de la materia según sus densidades de la composición y la investigación de circunvoluciones de homología se describe como una posible aplicación.

Ni el uso de homotopia para la aplicación de dichas 'Ilas cerebrales ni cualquier otra aplicación relacionada con caminos se describe en US 7,991 ,22 1 B1

Los presentes inventores no conocen ninguna propuoesta que describa el uso de la homotopia para identificar automáticamente los canales en un volumen 3D,

Referencias:

[1j A 8erruezo, J. Fernandez-Armenta, O. Cámara, E. Silva, l.l. Mont, D. Andreu. A. Frangi, J Brugada, Threedimensional architeelure 01 sear and eondueting ehannE11s based on high resolution CE-CMR. Insighls lor ventricular /achyeardia ablation, European Hean Joutoal (2011 ) 32 (AbstraCl Supplement), 943.

[2) Fernandez-Armenta, J. Cámara, O. Silva, E. Mont, l.. Andreu, D. Sitges, M. Herzcku, C Frangi, A,F. Brugada, J. Berruezo, A. Three-dimensional Archileelure 01 Sear Afld Conducting Channe/s Based On High Resolution ce-CMR. Insights For Ventn'cular Teehycardia Abla/ion, Heart Rhylhm Soeiety's Annual Seientifie Sessions, Moseone Center, 201 1

[3) Berruezo A, Fernández-Armenta J, Mont L. Zeljko H, Andreu D, Herczku C, Boussy T, Tolosana JM, Arbelo E, Brugada J., Combined Endocamial and Epicardial Catlleter Ablalion in Arrhythmogenic Right Ventricular Dysplasia Incorporating Sear Deehanneling Technique, Circ Arrhythm Electrophysiol. (2011 ) Oec 28

[4J Adrianus PWijnmaalen, Rob J van der Geest, Carine F.B. van Huls van Taxis, Hans-Mare J. Siebelink, lucia

J.M. Kroft. Jeroen J. Bax, Johan H.C Reiber. Martin J. Schalij, and Katja Zeppenfeld Oepartment of Cardiology,

Hesd-to-hesd compsriso" o{ confrsst-enhsnced mst;lnetic resonsnce ;maging snd eleefroanafomical voltage mapping /0 assess pos/·infarct scar characten's/ies in patien/s with ventricular /achycardias: real-time image integra/ion and reversed registra/ion, European Heart JClurnal (2011) 32, 104-114.

15J Valeria Barbarito, luigi Carolenuto, luis Serra, Oscar Cámara, Juan Fernandez-Armenta, Antonio Berruezo, Alejandro Frangi. A software applieation lar Ihree-dimensional visua/iza/ion and Quantifieation of sean; and eondueting ehannels based on pre-procedure CE-MRI;/1 patients with ventn'eular laehyeardia, CARS 2012, June 2730, Pisa, Italy.

[6j larrabide l. Omedas P, Martelli Y, Planes X, Nieber M. Moya JA .. Butakofl C, Sebastian R, Camara O, De Craene M, Bijnens 8H, Frangi AF, GIMIAS: An Open Source f'ramework for Efficien/ Deve/opmenl 01 Research Tools and Cliflical Plololypes, Fum.; IlIIélgifllJ é1IJ(J MudeliTJf} U{ fll~ H~élll, sel. Lecture Notes in Computer Science (2009). vol. 5528, pp. 417426.

[7) Hans e van Assen, Mikhail G. Danilouchkine, Alejandro F. Frangi. Sebastian Ordas, Jos J.M. Westenberg. Johan

H.C. Reiber, Boudewijn P.F. Lelieveldt, SPASM: A 3D-ASM for segmentation of sparse and arbitrarily oriented cardiac MRI data, Medicallmage Analysis 10 (2006) 286-303.

18) Esther Perez-Oavid, Ángel Arenal, José l. Rubio-Guivernau, Roberto del Castillo, Leonardo Alea, Elena Arbelo, Eduardo Caballero, Veronica Celorrio. Tomas Datino, MD. Esteban Gonzalez-Torrecilla, Felipe Atienza, Maria J. Ledesma-Carbayo, Javier Bermejo, Alfonso Medina, Francisco Fernandez-Avilés. Noninvasive Identification 01

Ven/ricular Tachycardia-Related Conducting Channels Using Con/ras/-Enhanced Magnetic Resonance Imaging in Pa/ien/s 1IVi/h Chronic MyocarrJial /n!are/ion Comparisofl o! Signal /ntensity Scar Mapping and Endocardia/ Vol/age Mapping, JACC 2011184-94.

(9) Oakes RS, Badger T J. Kholmovski EG. Akoum N. Burgon NS, Fish EN. Blauer JJ. Rao SN, OiBella EV, Segerson NM, Oaccarett M, Windlelder J, McGann CJ, Parker O, lMacleod RS. Marrouche NF., De/eciion and quantifica/ion of left alrial struclural remode/ing wi/h delayed-enhanc~lment magnetic resonance imaging in palients wi/h alrial fibril/afion, Circulation. 2009 Apr 7; 119(13):1758-67.

(1 al http://www.alumni.utah.edulu-news/au gustQ9/?display::life-saving-companies.html

[11J Marcos Daccarett, Troy J. Badger. Nazem Akoun1. Nathan S. Burgon, Christian Mahnkopf, Gaston Vergara, Eugene Kholmovski, Christopher J. McGann. Dennis Parker, Johannes 8rachmann, Rob S. MacLeod, and Nassir F. Marrouche, Association of Left Atrial Fibrosis De/ected by Delayed-Enhancement Magne/le Resonance Imaging and tlle Risk of Slroke in Patienfs lAIith Atrial Fibrilla/ion. J Arn ColI Cardiol. 2011. 57·831-838.

{12] N Nikopoulos y otros. An efficienl algori/Ilm fOI 3d binary morpllo/ogical /ransfofT1lations with 3d struc/uring elemen/s for arbitrary size and sllape. IEEE Transadions on Image Processing. Vol 9. No. 3. 2000. pp. 283-286.

{13] Dijkstra, E. W A no/e on two problems in connexion wilh graphs. Numerische Mathemalik (1959) 1: 269-271.

(141 Markos G. Tsipouras, Dimilrios 1. Fotiadis, Lambros K. Michalis: IGI Global: Computer-Aided Diagnosis of Cardiac Arrhythmias (9781605660264): Book Chapters

[15J Cormen, Thomas H.; Leiserson, Charles E. . Rivest. Ronald L . Slein. Clifford (2001). "Section 24.3: Dijkstra's algonthm" Introduclion lo Algorithms (Second ed.), MIT Press and McGraw-Hill. pp. 595-601. ISBN 0-262-03293-7.

{16] Compulational cardiology: the hear1 of the maller. Dr. Natalia Trayanova. Departrnent of Biomedical Engineering and Institute for Computational Medicine Johns Hopkins University 2012

Descripción de la invención

Es un objeto de la presente invención proporcionar una alternativa al estado de la técnica anterior, que cubre los huecos que se encuentran en la misma, particularmente los relacionados con la falta de propuestas que realizan una identificación automatica de canales en un volumen 3D.

Para ese fin, la presente invención se refiere a un método implementado por ordenador para la identificación de canales a partir de datos representativos en un volumen 3D. que comprende la identificación, en un volumen 30 de un objelo. de dos o mas zonas diferentes basandose Em los valores de al menos un paramelro fisico y/o funcional representalivo de propiedades físicas y/o funcionales de dicho objeto, como una zona de un primer tipo, una zona de un segundo tipo y una zona de un tercer tipo, donde dichos primero, segundo y tercer tipos de zona son diferentes entre si.

Al contrario de los métodos conocidos, en tos que dichas zonas o partes de ellas (Ial como parches), sólo se visualizan con el fin de permitir a una persona calificada para llevar a cabo visualmente la identificación exacta de los canales, el método de la presente invención comprende, de manera caracteristica, realizar los pasos siguientes mediante el procesamiento de dichos datos representativos:

-

identificar automaticamenle como un canal candida'to un camino que discurre a través de dicha zona de un segundo tipo y que se extiende entre dos puntos de dicha zona de un primer lipo; y

-

llevar a cabo de forma automática, en un espacio topológico que incluye la zona de un primer tipo y la zona de un segundo lipa y no incluye la zona de un tercer tipo, operaciones homotópicas entre dicho canal candidato y caminos que discurren sólo a través de dicha zona de un primer tipo, y si el resultado de dichas operaciones homolópicas es que el canal candidato no es homotópico a ningún camino discurriendo sólo a Iravés de la zona de un primer tipo se identifica el canal candidato como un canal restringido.

A continuación, en la presente descripción, dicha zona de un primer tipo y la zona de un segundo tipo se denominan. respectivamente, una zona bien definida y una zona no--bien definida.

las operaciones homótopicas se realizan preferiblemen'te para varios canales candidalos .

Dependiendo de la realización, dicho parámetro fisico ylo funcional se asocia a al menos uno de los siguienles parámetros: absorción o reflexión de la luz, radiación magmHica o electromagnética. temperatura, electricidad, intensidad de señal, fase de señal, tiempo, frecuencia y color. etc .. o una combinación de los mismos, y Sus valores se obtienen como una respuesta a cualquier técnica conocida de generación volumen 3D, tal como una técnica basada en rayos X para la obtención de parámetros de absorción de rayos X, una lécnica basada en una exploración por ultrasonidos para oblener valore de TOF (tiempo de vuelo) de las ondas reflejadas de ultrasonido, una técnica de resonancia magnética para la obtención de señales de RF emitidas por los tejidos sometidos a un campo magnético, un Mapeo Etectro Anatómico (EAM), etc.

En la presente invención, los términos volumen 3D se refieren a cualquier tipo de volumen 3D, induyendo un volumen sólido, un volumen hueco y también una mall;3 poligonal con una forma 3D, tal como una malla poligonal EAM.

Para una forma de realización preferida, dichas propiedades fisicas ylo funcionales se refieren a las propiedades de velocidad de propagación, en una zona bien definida pC1r ser una zona de velocidad de propagación rápida y en una zona no-bien definida ser una zona de velocidad de propagación lenta

Esta falta de homotopia entre un canal y cualquier camino a través de la zona bien definida es debida a la existencia de un obstácuto entre ellos, lo que provoca la ausencia de caminos de propagación transversal a lo largo de una dirección determinada.

Para una realización, el metodo de los primeros y segundo aspectos de la presente invención se aplica a un campo de la medicina o veterinaria, preferiblemente para la detección automática de los canales en los órganos internos, tales como el corazón, cerebro, pulmones, etc.

Dicha realización preferida se aplica a [os órganos internos, donde dichos canales son generalmente canales conductores de la electricidad, en cuyo caso la zona bien definida es una zona conductora eléctricamente rápida y la zona no-bien definida es una zona conductora eléctricamente lenta, o canales de la sangre, en cuyo caso la zona bien definida es una zona de suministro de sangre de ,,¡pida propagación y la zona no-bien definida es una zona de suministro de sangre de lenta propagación.

En una realización preferida, dichos canales son canales en el miocardio, en donde la zona bien definida correspondiente a una zona de tejido sano y la zona no-bien definida es una zona de tejida fronterizo (BZ), y donde dicho volumen 3D, o un sub-volumen del mismo, es un volumen del miocardio 3D. En este caso, el obstáCulo colocado entre un canal restringido transcurriendo a través de la zona de tejidos BZ y los caminos de estimutación regulares que se ejecutan a través de la zona de tejido sano es un obstáculo no conductor constituido por un núcleo de un tejido cicatricial, lo que provoca la ausencia de activación transversal a lo largo de una dirección determinada.

En otra forma de realización, el método se aplica a la e:(ploración geofisica, para identificar los canales de fluido, en cuyo caso la zona bien definida es una zona que contiene fluido que se propaga a una velocidad rápida y la zona nobien definida es una zona que contiene fluido que se propaga en una velocidad lenta, tal como una zona de arena. En este caso, el obstáculo podria ser una zona que no contiene o no es susceptible de contener fluido, tal como una roca .

En una realización, el método del primer aspecto de la invención comprende:

-

Realizar una conversión del volumen 3D en dicho esp~lcio topológico ,

-

Procesamiento de dicho espacio topológico y obtención de las clases de equivalencia para dichos caminos. y

-

Realizar dicho procesado homotóplco sólo por un carnina representante por clase de equivalencia, tanto para los canales candidatos como para los caminos que sólo pasan a través de la zona bien definida

En una variante preferida de dicha realización. dicho espacio topológico es un espaCio topológico de zonas combinadas, y el método consiste en llevar a cabo una conversión del sub-volumen de la zona bien definida a un correspondiente espacio topOlógiCO de una sola zona, y en la implementación de un primer algoritmo, o Algoritmo 1, para la obtención de dichas clases de equivalencia, que tiene como entradas a ambos de dichos espacios topológicos y que genera como salida un conjunto de satida de representantes de clases de equivalencia de canal, con un camino representativo por clase, en un espacio topológico.

Otras realizaciones del método del primer aspecto de la presente invención se describen de acuerdo a las reivindicaciones adjuntas y en una sección posterior en relación con la descripción detallada de varias realizaciones.

Un segundo aspecto de la presente invención se refiere a un producto de programa de ordenadOr, que incluye instrucciones de CÓdigo que cuando se ejecutan en un ordenador implementan las etapas del método de cualquiera de las reivindicaciones anteriores.

Otro aspecto de la presente invención se refiere a un sistema Mapeo Electro Anatómico (EAM), que comprende:

-

un catéter que tiene uno o más electrodos para la adquisición de los valores de un parámetro eléctrico (por ejemplo, voltaje) y/o de parámetros asociados al mismo, en diferentes puntos de al menos un endocardio y/o epicardio cuando se desplaza a través de los mismos; y

-

medios de navegación por ordenador en comunicación con dicho cateter y que comprende:

-

medios de localización configurados para colaborar con dicho cateter para localizar sus posiciones a lo largo de dicho desplazamiento a traves del endocardio y/o epicar'dio: y

-

medios de lectura configurados para colaborar con dicho catéter para leer los valores adquiridos por el mismo; donde dichos medios de navegación por ordenador es!,in configurados y dispuestos para el acceso a dichos valores leidos y dichas posiciones del cateter, correlacionarlO's y construir y almacenar en unos medios de memoria un volumen con el mismo EAM 3D, en forma de una mall21 poligonal con una forma en 3D, y ademas cuentan con una pantalla para la visualización de al menos parte de dicho volumen EAM 3D.

Contrariamente a los sistemas EAM conocidos, en el sistema de EAM de la presente invención. el sistema de navegación implementa. por medio de uno o mas algoritmos, el metode del primer aspecto de la presente invención para la identificación de canales conductores del miocardio a partir de datos representativos en dicha malla poligonal.

Breve Descripción de los Dibujos

Las anteriores y otras ventajas y caracteristicas se comprenderán más plenamente a partir de la siguiente descripción detallada de unos ejemplos de realización con referencia a los dibujes adjuntes, que deben temarse a titule ilustrativO' y nO' limitalivo, en los que:

La figura 1 es la visualización esquemática de la prepagadón de la estimulación en des medies de cemunicación diferentes con diferentes velocidades de propagación (es decir, a traves de una zena bien definida y una zena nebien definida, de acuerdo cen la terminelegia utilizada "mteriormente), a partir de un único punto de estimulación. El frente de onda se muestra en intervalos periódicos, desde el tiempo t " 1 hasta el tiempo t "4 la velocidad de propagación en el medio a la izquierda (rectángulo blanco) es 2 veces mayor que en el medio a la derecha (rectángulo sombreade). En el caso (a) les des medio$ están separados por una barrera no conductora (tal como una cicatriz para la aplicación relativa al canal de miocardio), que se muestra por medio de una barra vertical negra, en el caso (b) el estimulo puede pasar libremente entre les dos medios.

Figura 2. Frente de onda y camines de activación para el ejemplo de la Figura 1 en elliempo t " 3.

Figura 3: la propagación del frente de onda de un canal conduclor entre dos núcleos (rectángulos negros) que separan el canal que discurre a traves de la zona sombreada (zona no-bien definida) desde la zona blanca (zona bien definida), correspondientes, respectivamente, a teJido zona fronteriza ("border zone") y tejido sano, cuando se aplica el metodo para la identificación de canales conducteres en el miocardio.

Figura 4: (a) Dos caminos homot6picos y su homotopia; (b) -(f) Dos caminos que no son homotópicos' La no homotopia entre ellos se pueden encontrar debido a un obsláculo/agujero en el medio Los dos caminos se conocen como g y f.

Figura 5: homotopías en un espacio topológico inducido por un espacio 3D. (a) El espacio topológico; el volumen de la pared tubular no pertenece al espacio topológico ("agujero", ·obst¡kulo"), todo lo demás si. (b) Dos caminos homotóplcos (mostrados por lineas negras gruesas) dentro del tubo y 3 caminos intermedies (mestrados per las lineas negras más finas) de la homotopia. (e) Dos caminos homotópicos fuera del tubO' y 3 caminos intermedios de la hemotopía. (d) Dos camines no hemotópicos, uno en ElI interior del tubo, el otro fuera. La pared del tubo evita una deformación centinua.

Figura 6: (a) Un parche de la zona no-bien definid;:1 (sombreado) con 2 bloques de núcleo (negro) y (b) los representantes seleccionados de las 3 clases de equivalencia de homotopia.

La figura 7 muestra un ejemplo de la aplicación del Algoritmo l ' (a) se muestran las dos entradas para el algoritmo, es decir, los espacios topológicos H y H+BZ. y también unas representaciones gráficas de la ejecución de las tres primeras lineas del algoritmo ; (b), (e) y (d) muestran representaciones gráficas de la ejecución de las lineas 4. 5 Y 6 del algoritmo para, respectivamente. un primero. un seHundo Y un tercer camino de canal candidato bz, y un cuadro final que indica el estado del conjunto de representantes de las clases de equivalencia de canal (abreviado como conjunto de canales) después de cada secuencia de ejecución.

Figura 8: Flujo de trabajo de la Solución Integrada (Algoritmo 2). los rectángulos redondeados representan los datos y las ruedas dentadas los pasos de procesamiento (incluyendo el Algoritmo 1 insertado). Los números corresponden a los números de linea en el listado de Algoritmo 2.

Figura 9: Transformación de un espacio geometrico con funcionalidad de tejido (a) en una representación gráfica del espacio topológicO' (b) .

Figura 10: Traza de la búsqueda para el metodo "backlraking" (a la izquierda) y búsqueda determinista hacia un área definida (derecha).

Figura 11: (a) Combinación de "Proyección esquelelo" y "Eliminar puntos de Reversión" a partir de ambos caminos pl y p2 para encontrar una homotopia desde ambos pl y p2 a p (para el caso i» e desde ambos caminos q1 y q2 a q (para el caso ii» y. por lanto, una homolopia entre pI y p2 (para el caso i)) y una homotopía entre ql y q2 (para el caso ii», esta último no se encuentra porque ql y q2 son caminos no homotópicas; (b) Leyendas de los elementos mostrados en la Figura 11 a.

La figura 12 muestra un ejemplo de la aplicación del algoritmo 6: (a) se muestran las entradas para el algoritmo, es decir, un esqueleto, una MHT y dos caminos dados pI, p2 cuya homotopia debe ser comprebada; (b) Tabla que muestra la ejecución del algoritmo. incluyendo las proyecciones de esqueleto y la eliminación de los puntos de inversión para ambos caminos (columnas de la izquierda para pI y columnas de la derecha para p2) y la comprobación de igualdad (casilla central en la linea in'ferior de la labia que se muestra) de los caminos finalmente obtenidos.

5 Figura 13: Eliminación de árboles durante el proceso de poda. al Esqueleto completo. b) árboles marcados y e) Esqueleto podado. El rectángulo sombreado es una zona no-bien definida. el blanco circundante corresponde a la zona bien definida y los rectángulos negros correSpOndEln a núcleos/obsl¡kulos que no propagan.

Las Figuras 14a a 14c muestran un ejemplo de la aplicación del Algoritmo 7: (a) las entradas de dicho algoritmo: un grafo y una MHL; (b) Y (c) tablas que muestran la ejecución de los diferentes pasos del Algoritmo 7 para la conslrucción de un esqueleto y un MHI.

La figura 15 muestra esquemáticamente una representación de una sección transversal de parte de un miocardio, para una forma de realización preferida del método del primer aspecto de la invención relativa a la identificación de canales conductores en el miocardio, donde la zona bien definida es una zona de tejido sano H, la zona no-bien definida es una zona de tejido frontera 82, los bloques son núcleos de cicatrices S, y el canal conductor se indica

15 por la referencia CC y está pasando a través de la zona de B2 entre el espacio existente entre los dos bloques C. y tiene un punto de inicio y un punto final situados en la zona H.

La figura 16 muestra esquemáticamente la relación entre caminos nulos homotópicos y pares de caminos homot6picos. La vista a) muestrlJ un camino f nulo hOfllOl6pico y la homotopia entre f y el camino constante g. Las vistas b) a e) muestran la conversión de un camino nulo homotópico f a un par de cam inos f1 y 12 homotópicos, a partir del camino completo nulo homotópico en b), dividiéndolo en componentes f1 y f2 en c), revirtiendo un componente en d) y una homotopía entre los caminos resultantes en el.

Descripción detallada de unos ejemplos de realización

-

Definición Matemática de Canal Restringido'

Con el fin de hacer mas comprensible el método de la presente invención, se dará en esta sección primero una

25 definición matemática de un canal restringido y de hClmotopias y caminos homotópicos. como se entiende en la presente invención.

Caminos de Estimulación Sincronizada Vs Aislada .

La presencia de canales de conducción causando re-entrada (que es un ejemplo de un canal restringido) está firmemente conectada al aislamiento de los caminos de propagación de estimulaciÓn. la re-entrada sólo es posible si el frente de onda de eslimulación se divide en partes que pueden viajar de forma independiente a diferentes velocidades durante una cantidad de tiempo mínima. L21 Figura 1 al muestra como una barrera no conductora puede dividir el frente de onda en 2 panes, cada una de las cuales \liaja a su propia velocidad de propagación determinada por las propiedades fisicas y/o funcionales del medio subyacente (propiedades del tejido, para aplicaciones médicas

o veterinarias). Sin esta barrera en la Figura 1 b) la misma diferencia en la \lelocidad de propagación de los dos 35 medios no resulla en una separación del frente de onda.

Como una buena aproximación, la propagación de esl1mulo puede ser \lista como una reacción en cadena de estimulación de células. Una célula es estimulada por I~I primer estlmulo que llega desde cualquiera de sus células vecinas. Esto significa que su momento de la ac!i\lación se determina por el (no necesariamente más corto) camino más rápido desde el estimulo inicial a la célula, que se I!amarán ~caminos de activación" en lo siguiente.

La Figura 2 muestra varios de esos caminos de activación para la propagación de la Figura 1, en t '" 3. Esto ilustra cómo el frente de onda puede permanecer conectado en el caso (b) , sin tener en cuenta las diferentes velocidades de propagaCión : Mientras que en el caso (a) sólo puede haber caminos de propagación directos que discurren a traves de un solo medio, la barrera que falla en el caso (b) permiten ta existencia de caminos de activación que utilizan et medio más rápido al principio y luego entran en el medio más lento bajo un ángulo determinado por la ley

45 de la refracción de Snell. Estos caminos pueden llegar a puntos en el medio más lento de forma más rápida que a través de un camino directo a través del medio más len10. Cuanto más cerca este el punto a la frontera entre los medios, menor será la distancia que tendrá que recormr en el medio más lento y más cerca estará la velocidad de propagación media del camino a la \leloddad de propagación del medio más rápido. Esto crea una transición continua que mantiene intacto el frente de onda.

En el caso de tener una barrera no conductora que sep;¡¡re los dos medios, no existen los caminos de activaci6n que suavizan el frente de onda, y se evita la "fuga" de eslímulo desde el medio más rápido al más lento. Esto hace que sea posibte tener dos frentes de onda independientes que viajan a diferentes velocidades

Como un canal conductor se caracteriza por la independencia de la propagación de estimulo, la existencia de tales caminos de acti\lación transversal descarta la presencia de un canal de conducción Por lo tanto, un criterio

55 necesario para un canal conductor es la ausencia garantizada de los caminos de acti\lación transversal a lo largo de un cieno trayecto, o en otras palabras la presencia de un obstáculo no conductor (núcleo) entre el canal en el medio lento (tejido B2, para el caso del miocardio) y cualquie;r camino en el medio rápido (el tejido sano. para el caso del miocardio).

la forma de realización preferida relacionada con la identificación de los canales conductores de miocardio se ilustra esquematicamente en la Figura 15, donde la zona bien definida es una zona de tejido sano H, la zona n()-bien definida es una zona de tejido frontera SZ, los bloques son núcleos de cicatrices S, y el canal conductor está indicado por la referencia CC y pasa a traves de la zona 82 entre el espacio existente entre los dos bloques e, y tiene un punto de inicio y un punto final situado en la zona H

Homotopias y Caminos homotópicos:

El melodo de la presente invención se inspira en la de'finición de caminos homol6picos utilizados para caracterizar espacios topológicos. En un espacia topológico X una homotopia entre dos caminos ' y 9 (modelados como funciones continúas de [0,11 a X) es una función h continua a partir de [0,1] )( ]0,1] a X 'tal que:

1.

h(x,O)=f(x) for all x E [0,1)

2.

h(x,1) =g(x)forallxe[0,I)

3.

h(O,f)=f(O)forall t E [O,I]

4. 11(1,f)=f(l ) forall lE [0,1]

Dos caminos f y 9 se llaman homot6picos, si existe una homotopla entre ellos

la interpretación intuitiva de la definición es: Dos caminos (y 9 son homotópicos si y sólo si comienzan y terminan en el mismo punto (las condiciones 3 y 4 aseguran qUE! ' (D) '" 9 (O) Y f (1) = 9 (1) Y hay una deformación continua que deforma el camino f (en t = O) al camino 9 (en t '" 1). El primer parámetro de h puede ser visto como el parámetro de trayectoria que discurre a través del camino (desde el principio x = O hasta el final x = e). El segundo parametro de h puede ser visto como un "control deslizante" que controla la transición (para t = Oel camino es igual a f. en el intervalo ]0, 1[ se transforma continuamente a si mismo hasta que alcanza 9 en f = 1). A esta transformación no se le permite hacer ningun "salto" (esto sería una discontinuidad en el segundo parámetro de h) ni se le permite desgarrar el camino durante el proceso (esto seria una discontinuidad en el primer parámetro de h). Esto es posible si y sólo si no hay ningún "obstáculo" entre los dos caminos que pueda obstruir la deformación.

El ejemplo (a) en la Figura 4 muestra una homotopia entre dos caminos homolópicos , y g, mostrando los caminos intermedios de la transfO/mación (las imagenes de ¡O, 1] en h('. O) =f. h(', 0.25). h(-, 0.5). he", 0.75) y h(', 1) '" g}. En el ejemplo (b) no existe ninguna homotopia entre (y 9 a causa de un agujero en el espacio topológico entre los dos caminos. Diferentes enfoques a la (imposible) tarea de encontrar una homotopía incluyen pasar a Iravés del agujero (se muestra en (e); no permitido porque esto implica qu~~ h toma valores fuera del espacio topol6gico X, por ejemplo, h (112, 112) e X), saltar sobre el agujero (se muestra en (d) ; no perm ilido porque esto significaria una discontinuidad de h en el segundo parámetro). desconectar el camino desde el punto de inicio original o final y volver a conectar despues de alcanzar el otro lado del obstaculo (se muestra en (e); no permitido debido a la condición 3 y 4. que aseguran que el punto de inicio y el punto final se mantienen durante toda la deformación) y el desgarro del camino en dos piezas, cada una pasando por cada lado, y volver a conectar las piezas en el otro lado del obstáculo (se muestra en (1) ; no permitido porque eso implicaría una discontinuidad en el primer parámetro de h).

Mienlras que los ejemplos de la Figura 4 son espacio:; topológicos inducidos por espacios geométricos en 20, la definición de homotopia se aplica principalmente a los espacios inducidos por espacios geométricos 3D en la detección de canales. la figura 5 muestra ejemplos de caminos homotópicos y no homotópicos en un espaCio muy

sencillo de ese lipo,

Se sabe Que la definición anterior de caminos homot6pücos induce una relación de equivalencia que es, por lo tanto reflexiva, simetrica y transitiva. Además, esto nos permite trabajar con clases de equivalenCia y dividir el conjunto de todos los caminos entre dos puntos dados en clases de equivalenCia. Para cada propiedad definida por homotopías sólo un representante de cada equivalencia tiene qUE! ser revisado y el resultado sera el mismo para todos los demas miembros de la clase.

Homotopía en la detección de canales:

En el caso de la detección de canales, el metodo de la presenle invención utiliza la zona no·bien definida y la zona bien definida (es decir, la realización de tejido incluyendo la BZ y los volúmenes de zona sanos. para el miocardio, como se muestra en la Figura 15) como espacio topol6gico y cualquier núcleo como obstáculo que impide la deformación continua. luego, el tener dos caminos A 'i B que no son homotópicos puede interpretarse como dos caminos de activación que estan separados por un obstaculo y. por lanlo. no se pueden sincronizar. Esto es lo que puede causar arritmia, para el caso del miocardio. Asi, para dicho ejemplo de realización, un canal de conducción que puede causar arritmia puede por lo tanto ser cualquier camino que discurre desde tejido sano H a tejido sano H a través de la zona Bl Que no sea homot6pico a un c¡;lmino desdefa los mismos puntos Que pasa sólo a través de lejido sano H

Definición: Canal restringido:

Basado en el razonamiento anterior, 1m canal reslringiclo, lal como se entiende en la presente invención, se puede definir de la siguiente manera: Considerando lodo medio de propagación (todo medio a través del cual una onda puede propagarse), es decir, las anteriormente mencionadas zonas no-bien definida B2 V bien definida H, como el tejido conductor para el ejemplo de realización del miocardio, como espacio topológico, un canal restringido se define como un camino entre dos puntos de una zona bien definida (tejido sano H para el ejemplo de realización del miocardio) que no es homotópico a ningún camino que pasa sólo a través de una zona bien definida (tejida sano H para el ejemplo de realización del miocardio).

Téngase en cuenta que si esta condición se cumple pal'a un camino, entonces se cumple de forma automatica para todos los caminos que son homotópicos a él. Un al!~orilmo que encuentra lodos los caminos que cumplen la condición anterior, por tanto, encuentra un conjunto de clases de equivalencia de caminos en lugar de caminos individuales. El representante mas interesante de esta clase es el que mas probablemente sigue el camino de excitación .

El ejemplo de la Figura 6 consiste en un bloque de la zona no-bien definida (zona B2 en el caso del miocardio) con 2 bloques sólidos de núcleos (rectangulos negros) que dejan un espacio intermedio de zonas no-bien definidas (sombreado) entre ellos. El área que rodea la zona no-bien definida es una zona bien definida (tejido sano H en el caso del miocardio). Para unos puntos fijos de inicio y final los dos bloques de núcleo dividen los caminos en 3 clases de equivalencia, la primera (lineas discontinuas) conliene caminos que pasan por encima de los 2 bloques. la segunda (lineas continuas) contiene los caminos que pasan por el espacio Intermedio y la tercera (lineas de puntos) contiene los caminos que pasan por debajo de los 2 bloques

La única de esas clases de equivalencia que puede beneficiarse por ser un canal restringido es la Que pasa a través del espacio intermedio. Cada una de las otras clases de equivalencia contiene un camino Que discurre por solamente una zona bien definida. particularmente el c;~mino en la parte superior para la clase en linea discontinua y el camino en la parte inferior para la clase en linea de puntos. Por lo tanto todos sus miembros son homotópicos a un camino que atraviesa solamente una zona bien definida (tejido sano en el caso del miocardio).

Solución Algorltmica

Un enfoque de fuerza bruta y sus problemas·

El algoritmo obvio para detectar canales restringidos de acuerdo con la definición dada anteriormente es una traducción directa de la definición en un algoritmo: La dl~finición ofrece un criterio que se puede comprobar con el fin de decidir si un camino dado es un canal restringido. Entonces, un algoritmo simplemente puede comprobar esta condición para todos los caminos posibtes (un conjunto finito, teniendO en cuenta que trabajamos en datos discretos), si es que la condición en si puede traducirse en un algoritmo. La existencia de un camino homotópico que corre a través de sólo el tejido sano se puede comprobar por sondeo de todos los caminos posibles dentro de tejido sano (de nuevo un número finito de caminos). La homotopia entre dos caminos se puede comprobar mediante la creación de todas las combinaciones de homotopias elementales (por ejemplo. usando el hecho de que todos los caminos con el mismo inicio y fin en un espaCio convexo como un lIoxel o un triángulo son homotópicos) y la comprobación, si uno de ellos cumple los criterios para ser una homotopia entre los dos caminos indicados. Mientras que el enfoque de fuerza bruta conduce a un algoritmo teóricamente correcto, no va a ser prácticamente lIiable por las siguientes razones:

1. El numero de caminos que tienen que comprobarse es impracticablemente alto En un espacio continuo, hay un numero infinito de caminos, e incluso en una versión discretizada del espacio el número de caminos crece de forma exponencial en el número de nodos. Esto se aplica tanto a·

a) Los caminos que son candidatos para canales restringidos y para los cuales la condición del canal restringidO tiene que ser revisada

b) Los caminos Que discurren sólo a través de tejido sano cuya homotopia a candidatos de cana l tiene que ser revisada

2. Incluso para un solo par de caminos puede ser muy costoso computacionalmente comprobar la condición de homotopia. La definición matemática utilizéI la existencia de una deformación como condición. pero no da ninguna pista sobre cómo construir uno. El -backtracking" de bús,queda puede solucionar esto sólo a un coste exponencial.

En resumen. el algoritmo consistiria en 3 bucles anidados, cada uno de los cuales tendría un número de iteraciones que es exponencial en el ntimero de puntos discretos en el espacio topológico. Esto descarta el uso del algoritmo en los casos del mundo real.

Algoritmo eficiente:

El algoritmo discutido anteriormente puede ser refinado para superar los problemas de complejidad computacional. para obtener el Algoritmo 1 mencionado y genéricamenle descrito en una sección anterior, para identificar clases de equivalencia de canales conductores ,

El Algoritmo 1 tiene como entradas lanto los espacios topológicos antes mencionados (H_and_BZ_topo, H_topo), es decir, el que incluye la zona no-bie n definida 'J la zona bien definida (H_and_BZ_topo) y el que incluye solamente la zona bien definida (H_topo), y genera como salida un conjunto de los representantes de las clases de equivalencia de canal, un camino representante por clase , en un espacio topológico , El Algoritmo 1 comprende las siguientes etapas:

1) Elegir dos puntos, inicio y frn, en la zona sola espacio topológico (H_topo)

2) ChannelCandidales "" Las clases de equivalencia en el espacio topológico las de zonas combinadas (H_and_8Z_topo), pala los caminas entre dichas dos plintos

3) HeallhyPaths "" Las clases de equivalencia en el espacia topológico de una sola zonao (H_topo). para los caminos entre dichos dos puntos

4) Par cada camina bz obtenida mediante 'ChanneICandidates"

5) Para cada camina h obtenido mediante 'HeallhyPaths"

6) Si bz es homotópico de h'

7) Descartar bz coma canal restringido: avanzar al siguiente bz

8) bz es un canal restringido: agregarlo a dicha conjunta de salida.

El Algoritmo 1 es todavía similar a una simple traducción directa de la definición matemática, pero incluye una serie de cambios que afectan a su complejidad computacional:

•

La selección arbitraria de un punto de inicio y final de todos los canales candidatos reduce el número de caminos que deben comprobarse (aunque no asintóticamenle) Aunque esto puede llevar a una pérdida de los canales restringidas detectados, suponiendo una zona bien definida, bien comunicada (Tejido sano H en el caso del miocardio) que rodea una parte esencial de la zona no-bien definida y del núcleo/obstaculos (zona de frontera y tejido de núcleo para la zona de miocardio). las diferencias se limitan a la trayectoria del canal dentro de la zona bien definida (Tejido sano H en el caso del miocardio) y, por lanto, carecen de importancia práctica.

•

Si un camino bz es un canal restringido de acuerdo a la definición anterior, todos los caminos que son homotópicos a bz son también canales restringidos. Esto se dE~duce directamente de ta transitividad de la relación de equivalencia. Así que sólo un representante de cada clase de equivalenCia de homotopía de caminos tiene que ser comprobado, lo que reduce drásticamente el número de candidatos

•

Asimismo, la iteración sobre caminos que discurren sólo por la zona bien definida (Tejido sano H en el caso del miocardio) se puede reducir a un representante de cada clase de equivalencia de homotopia. Si un camino bz es homotópico a un camino h que discurre sólo a través de! la zona bien definida, entonces bz también es homotópico a todos los caminos homotópicos a h. Esto reduce de nuevo el número de iteraciones.

•

La comprobaci6n de homotopía entre dos caminos dados se encapsula sin hacer suposiciones sobre su funcionamiento interno. Esto deja espacio para optimi2:aciones en función de la estructura de datos utilizada para representar el espacio topológico.

A diferencia del algoritmo de fuerza bruta, el Algoritmo 1 ya no es inherentemente exponencial. El número de iteraciones de sus bucles se determina únicamente por la complejidad de la estructura de los espacios topológicos y ya no es exponencial en el numero de nodos.

Esto no dispersa de forma automática los problemas de complejidad del algoritmo. Si sus sub-algoritmos ploblemáticos (cálculo de las clases de equivalencia y de verificación de homotopia) son exponenciales. esto todavía afecta a todo el algoritmo. Pero las partes criticas se encapsulan y se pueden resolver por separado como soluciones a los siguientes problemas matemáticos bien definidos

1. Cálculo de las clases de equivalencia de homotopia die caminos entre los puntos dados de inicio y final

2 Comprobar si dos caminos dados son homotópicos

Algoritmos para resolver estos problemas de manera eficiente para una representación particular del espacio topológico se discuten a continuación,

Un ejemplo gráfico de la aplicación del Algoritmo t se muestra en la Figura 7 En la Figura 7a, se muestran tas dos entradas para el algoritmo, es decir, los espacios topológicos H y H+8Z, y también una representación gráfica de la ejecución de las tres primeras lineas del algoritmo.

la Figura 7b muestra representaciones graficas de la ejecución de las lineas 4, 5 Y 6 del Algoritmo 1 para un primer canal candidato bz, y una casilla final (a la derecha) que indica el eslado del conjunto de representantes de las clases de equivalencia de canal (abreviado como Conjunto de canales) tras cada secuencia de ejecución, que para este primer bz se mantiene sin cambios (vado), dado que dicho primer bz es homotópico al primer h.

5 la Figura 7c es similar a la Figura 7b. pero para un segundo canal candidalo bz y un primer y segundo caminos sanos h, y donde se indica en el cuadro final que dicho segundo bz se añade como canal restringido (de hecho, como representanle de la clase de equivalencia de Célnal), porque no es homotópico a ninguno de los primero y segundo camino sanos.

la Figura 7d muestra la ejecución de las lineas 4, 5 Y 6 del Algoritmo 1 para un tercer camino de canal de candidato bz y el primer y segundo caminos sanos h, en donde la ultima caja de la figura indica que el conjunto de representantes de las clases de equivalencia de canal permanece sin cambios porque dicho tercer bz es homotópico a uno de los caminos sanos, en particular al segundo camino sano h.

Para una forma de realización (no ilustrada). el metodo de la presente invención comprende el colapso/contratación de dicha zona única de espacio topológico (H_topo) de tal manera que sólo hay un camino sano h que tiene como

15 dichos puntos de inicio y de final el mismo punto, en ed que dichos pasos (6), (7) Y (8) del Algoritmo 1 se llevan a cabo para dicho sólo un sano camino h. Cuando se sabe de antemano la clase de equivalencia homotópica a dicho único camino sano h. dichos ·ChanneICandidates" (Candidatos de Canal) incluyen a todos excepto a dicha clase de equivalencia de canal, homotópica y dichas etapas (~i) , (6) Y (7) se omiten, siendo añadidos la totalidad de los caminos bz en ·ChanneICandidates· (Candidatos de Canal) al conjunto de salida.

Para otra forma de realización (no ilustrada), el método comprende la implementación de un algoritmo de optimización de canal para la optimización de dichos representanles de las clases de equivalencia de canal de dicho conjunto de salida, dicho algoritmo de optimización de canal comprende los siguientes pasos'

1) Para un representante 'c' de cada clase de equivalencia de canales (es decir, para cada miembro bz del conjunto de salida):

25 2) Para varios sub-caminos 'sub-camino' de 'c':

3) 'shortest' " camina mas corto entre el inicio y el final ele 'sub-camino'

4) En caso que 'shortest' sea homolópico a 'sub-camino'

5) Modificar 'c': Reemplazar 'sub-camino' por 'shortest'

-

Solución integrada:

El Algoritmo 1, presentado arriba, se puede ulilizar para detectar Canales de Conducción, u otro tipo de canales restringidos. Sin embargo, se basa en:

• los dos espacios topológicos que representan:

a) todo el volumen 'conductor'. zonas bien definida!. y zonas no-bien definidas (Healthy+8Z, en el caso del miocardio): y

35 b) lona bien definida (tejido sano en el caso del miocardio) .

• Implementaciones suficientemente eficientes de operaciones topológicas (comprobaCión de homotopia y calculo de las clases de eqUivalenCia de homotopia) en los espacios topológicos.

Con el fin de satisfacer esas necesidades, un pre-procesamiento de los datos es necesario. En primer lugar, los datos de entrada estan por lo general disponibles en alguna forma de espacio geométrico (por ejemplo, malla de volumen, imagen 3D) con información de funcionalidad asignada que permite distinguir entre las 3 zonas: zona bien definida, zona no-bien definida y una zona mas identificada en el volumen 3D como zona de un tercer tipo y correspondiente a un núcleofobstaculo (zona de tejido sano H, zona de frontera o 8l y Núcleo C, en el caso del miocardio) Estos datos tienen que ser convertidos a una estructura de datos haciendo hincapié en el aspecto topológico y de forma que facilite las operaciones topológicas sin tener que extraer las caracteristicas topológicas

4:5 contenidas en la información geométrica en cada paso. Ademas, un pre-procesamlento de los datos ayudara a que las operaciones topológicas sean mas eficienles cuando se realicen a lo largo del algoritmo.

Para ese fin, el método del primer aspecto de la presente invención comprende la aplicación de un segundo algoritmo, o Algoritmo 2, que integra dicho primer algoritmo, y que tiene como dalas de entrada un espacio geométrico, relativo al volumen 3D, con información de la funcionalidad asignada para permitir llevar a cabo la identiflcaci6n de dichos al menos dos sub-volúmenes diferentes (H, 8l) Y ademas de dichos sub-volumenes (C), y que genera como salida dicho conjunto de representantes de las clases de equivalencia de canal, en un espacio geométrico.

El Algoritmo 2 comprende las siguientes etapas:

1) (H, Bl, e) = SeparateAccordingToFunctionality (Espacio Geométrico),

2) H_and_Bl_topo '" eonvertToTopologicalSpace (H O I3l),

3) H_IOpo =eonvertToTopologicalSpace (H),

4) H_and_Bl_topo '"" Preprocess TopologicalSpace (H_and_Bl_topo),

5) H_topo '. Preprocess TopologicalSpace (H_topo),

6) ChannelEquivalenceClasses = Algoritmo 1 (H_topo', H_and_Bl_IOpo')

7) GeometricChannels = TopologicalToGeometrical (ChanneIEquivalenceClasses. GeometricalSpace, H_and_ BZ_topo').

La función SeparateAccordingToFunctiona/ify separa el espacio geométrico en 3 subespacios disjuntos conslituidos por dichos tres sub-volumenes H, Bl Y C, es decir, por los mencionados tres sub-volumenes. Para una forma de realización preferida aplicada a la identificación de canales conductores en el miocardio. o en otro órgano. H contiene todos los punlos en el espacio original que e:sten ocupadas por tejido sano, Bl los puntos ocupados por tejido Bl y C los puntos ocupados por tejido de nudeo. Esta operación puede ser tan simple como la aplicación de un filtro umbral de una imagen DE-MRI al volumen 3D.

l a función ConverlToTopologicalSpace elimina toda la sobrecarga geométrica y transforma la información topológica

en una estructura de datos que es más adecuada para procesamiento topOlógico. Más abajo se discute una opción posible para que la estrudura de datos (un grafo de conectividad con un Mapa Local Homotópico) y cómo datos geométricos comunes 20 y 3D se pueden convertir en esa estructura de datos.

El pre-procesamiento realizado por la función PreprocessTopologicalSpace añade información auxiliar ad icional para el espacio topotógico. Esa información auxiliar facilita las operaciones topológicas realizadas en el Algoritmo 1, especialmente la comprObación de homotopia y el cálculo de las clases de equivalencia de homotopla. Cómo es esta información auxiliar y cómo se genera depende en gran medida de la estructura de datos elegida para el espacio topológico. Este pre-procesamiento para el CéISO de un espacio topológico representado por un grafo de conectividad y un Mapa local Homotópico se discutirá a continuación.

La función Topo/ogiealToGeometrie extrae información de los datos brutos de canal, que puede ser util, por ejemplo, para la intervención clinica. cuando se aplica a una aplicación médica o veterinaria. Mientras Algoritmo 1 detecta Canales de Conducción (u otro tipo de canales restringidos), sólo lo hace en un espacio topológico que no contiene información geométrica. La transformación de los caminos resultantes de vuelta al espacio geométrico original es esencial para la extracción de información útil para lél intervención clinica Además, la salida del Algoritmo 1 se compone de una clase de equivalencia de homotopia (conjunto de caminos), y no solo de un camino por canal. Sobre la base de la información geométrica, se puede seleccionar ya sea el miembro de la clase de equivalencia que mejor representa el camino de estimulación potencial o se puede extraer el volumen Bl responsable de esos caminos de estimulaciÓn.

La Figura 8 muestra un flujo de trabajo de la solución integrada mencionada, es decir, de la aplicación del Algoritmo 2, Los rectángulos redondeados representan los datos y los engranajes los pasos de procesamiento (incluyendo el Algoritmo 1). Los numeras corresponden a los numeras de linea en el lisiado de Algoritmo 2,

-

Operaciones topológicas eficientes:

Representación discreta de espacios topológicos '

Los espacios lopológicos cubren esencialmente la conectividad enire los miembros de un conjunto de puntos. Mientras que las representaciones comunes de espacios geométricos, como mallas de superlicie. mallas de volumen, imágenes 20 y 3D incluyen esta información. éstas se centran en la distribución geométrica de los puntos y están optimizadas para operaciones geométricas, Esto complica el procesado topológico y hace depender su implementación de la estructura de datos utilizada para el espacio geométrico Por lo tanto se desea una conversión del espacio geométrico a una estructura de datos que represente la topología y se iocalice en las operaciones topológicas necesarias para el Algoritmo 1.

Como todas las operaciones que se realizarán en el espacio topológico implican a caminos, que son esencialmente listas de aristas, una representación del espacio topológico basada en aristas es razonable. Un grafo que contiene un conjunto discreto de puntos como nodos y todas tas conexiones directas entre esos puntos como aristas todavía representa la conectividad y es independiente de la representación geométrica (por ejemplo, dimensiones -20 vs . 3D, tiP05 de celula5 -triányulu:>, cubu5. Quad5. '. im;;'!~ene:> \/5 malla:». p~ro la r~ducción a un conjunto finito de puntos crea agujeros en el espacio topológico. Deformaciones continuas de caminos (como en la definición de la homotopia entre caminos) no son posibles en un conjunto de puntos discretos. Así que hay que añadir explícitamente la información de homotopla.

Una posible representación de esta información puede ser un Mapa de Homotopia Local (Local Homotopy Map). Contiene para cada arista del grafo un conjunto de carninas que son homotópicos a ella. No es necesario para esta tabla que sea completa y explícitamente declarar todcls los caminos homotópicos para cada arista (que sería de tamaRo exponencial). Homotopias ausentes pueden ser deducidas mediante la explotación de la transitividad de la relación de homotopia. siempre y cuando haya suficientes homolopias explicitas para contener implicitamente (a través de la deducción) todas las homotopias.

Ese tipo de mapa de homolopia se llama "local", porque una forma tipica de llenarlo con las suficientes homotopias explicitas es induír a todas las homotopias entre aristas y caminos de un mismo elemento de volumen en la representación geométrica original (por ejemplo. un tetmedro en una malla 3D).

El siguiente algoritmo, denominado Algoritmo 3, utiliza este enfoque para convertir un espacio geométrico en un espacio topológico representado por un grafO y un Mapa de Homotopia Local (Local Homotopy Map). Por lo tanto. el Algoritmo 3 puede verse como una implementación de la función "ConvertToTopologicaISpace" del Algoritmo 2. De este modo, el espacio geometrico puede ser representado por un conjunto de nodos (por ejemplo, nodos de una malla 20 o 3D, centros de pixeles o centros de voxe!!, etc.) y elementos (por ejemplo, vóxeles telraédricos, los pixeles, etc.) que conectan dichos nodos, siempre y cuando los elementos están en la envolvente convexa de sus nodos· que es el caso para la mayoria de mallas lineales 20 y 3D, asi como imágenes 20 y 3D.

En otras palabras, la estructura de datos mencionalda anteriormente es, para la realización del ejemplo de realización aqui descrito. un grafo de conectividad con un Mapa de Homotopia Local (Local Homotopy Map) que contiene para cada arista del grafo un conjunto de caminos que son homotópicos a ella. y el método comprende la aplicación de un tercer algoritmo, llamado Algoritmo 3. para convertir el volumen 3D o la malla poligonal con una forma en 3D (o una superficie obtenida de la misma) en dicho grafo y en dicho Mapa de Homotopia Local, dicho tercer algoritmo que liene como enlrada el espacio geométrico representado por nodos oS y elementos e/s que conectan dichos nodos os, siempre y cuando los elennentos e/s sean la envolvente convexa de sus nodos ns, y genera como salida el espacio topOlógico representado por dicho grafo '1 dicho Mapa de Homotopia Local o MHL

Un ejemplo de una transformación de un espacio geométrico con funcionalidad de tejido (a) en una representación de un grafo del espacio topológico (b) se da en la Figura 9.

El Algorilmo 3 comprende las siguientes etapas:

1) Para cada elemento e[ en e[s :

2) Para cada nodo ni en nodos(e[):

3) Para cada nodo n2 en nodos(e[) \ {nI}:

4) Agregar los nodos nI y n2 en el grafo

5) Ai"ladir la arista (nI, n2) en el grafo

6) Para cada nodo n3 en nodos(el) \ {n1 , n2}:

7) Ai"ladir la homotopia entre (n1, n2) y In1, n3, n2] en cd MHL

Definici6n: Detección de Homotopia:

El metodo de la presente inl/ención también comprende la implementación de una "Detección de Homotopia", que es un algoritmo que transforma [a siguiente entrada en [a Siguiente salida: Entrada (espacio topológico) ·

•

Grafo: Conjunto de nodos y aristas;

•

Mapa de Homotopía Local (MHl): Mapea a cada arista una lista de caminos homotópicos. Este mapa debe tener suficientes entradas de forma que para cada arista e '1 cada caminos p homotópico a e [a homotopia entre e '1 p se puede deducir por [as entradas de la MHL utilizando las propiedades matemáticas de homotopias (por ejemplo transitividad).

Salida:

. La anteriormente mencionada (en [a descripción del Algoritmo 2) información auxiliar adiclona[, conslituida por [as siguientes dos estruc1UfilS de datos:

•

Esque[eto: Un subconjunto de arislas (a partir de [as aristas de dicho grafo) que cumplan [as condiciones indicadas aqui abajo;

•

Mapa de Homotopía Transitivo (MHT): Una tabla que: asigna cada arista que no forma parte del esqueleto a un camino homotópico de una manera que es compatible c,on las condiciones indicadas aquí abajo .

•

Condiciones:

1 No hay referencias ciclicas en MHT: A la envo~vente transitiva de la relación OependsOn definida por DependsOn(a. b) e::> b E MHT{a} no se le permite lener ninguna entrada reflexiva.

2 las referencias en MHT tienen que ser cubiertas por homotopías reales (representadas por el MHl): Esta permitido que el MHT mapee una arista e a un camino p, sólo si se puede deducir por el MHL y las propiedades matematicas de la homotopia (por ejemplo, transitividad) que e es homotópico a p.

3. El esqueleto tiene que ser minimo. o lo mínimo posible, entre los conjuntos que cumplen las condiciones 1 y 2.

Notas sobre la definición:

El MHl de acuerdo con su defiOición anterior no tiene por qué contener una lista completa de todos los caminos homotópicos a cada arista. En cambiO, es suficiente incluir sólo tantas homolopias como sea necesario de modo que todas las otras homotopias salen automaticamente a partir de ellas.

El MHl se llama "Mapa de Homotopia Local" porque es practico para incluir sólo las homotopias entre aristas y caminos cuyos nodos son todos vecinos. Por ejemplo. al convertir un volumen al formato de entrada para la Detección de Homotopia y el volumen esta representado por elementos convexos extendidos por un numero finito de nodos (por ejemplo, los cubos entre cada 8 centro!; de vóxeles vecinos en una ma lla 3D, los triangulos en un malla simple de superficie, el tetraedro en una malla de volumen simplex), se puede demostrar que un MHl creado por el Algoritmo 3 "Convertir volumen a Grafo" cumple lélS condiciones.

Aplicación de la Detección de Homotopia:

La "Detección de Homotopia" puede ser llamada "Detección de Homolopia" porque sus salidas, el esqueleto y el Mapa de Homotopia Transitivo, simplifican significativamente 2 problemas técnicos de las homotopias: El problema de la comprobación, si dos caminos dados son homotópicos (problema 2 de la definición de canal restringido), asi como la búsqueda de clases de equivalencia de homotopia (con el fin de reducir el número de caminos a tener en cuenta, problema 1 de la definición de canal restringido)

Comprobar la homotopia entre dos caminos dados'

Con el fin de comprobar, si dos caminos arbitrarios dados p1 y p2 en un espacio topológico dado son homotópicos, la existencia de una homotopía entre ellos tiene que ser probada (por ejemplo. mediante la búsqueda de una homotopi¡:¡ concreta) o refutada (por ejemplo, tr¡:¡!¡:¡ndo toda!'. I¡:¡!'. funciones po!'.ible!'. y mostrando que ningLln;:¡ e!'. Llna homotopia entre los dos caminos). Esto se puede hacer usando las homotopias en el MHL mediante la aplicación de una búsqueda "backtraking" recursiva empezando en p1 y con la esperanza de llegar a p2 Pero si el algoritmo aplica ciegamente homotopias del MHL, el esfuerzo de hacerlo es exponencial al numero de aristas. Así una forma mas dirigida a combinar las homotopias de la MHL es necesaria.

Aqui es donde el MHT ayuda. Considerando que el MHL con!enia una lista de homotopias para cada arista, el MHT sólo contiene una única homotopia para cada arista -la que nos guía hacia el Esqueleto. Asi que en lugar de aplicar homotopias alealoriamente (y yendo hacia airas, si elegimos mal) para encontrar una secuencia de p1 a p2, se puede comenzar a partir de los dos p1 Y p2 Y utilizar las homotopias del MHT para encontrar caminos homotópicos p1' y p2' que estan ambos en el esqueleto, lo que se hace, para una realización, por medio de un algoritmo de proyeCCión del Esqueleto, o Algoritmo 4, para proyectar los caminos p1, p2, que estan, en general, fuera del esqueleto. pero dentro del grafo, hacia los caminos p1'. p2' dentro del esqueleto. siendo el Algoritmo 4 el que tiene el camino p como entrada y que comprende los siguientes pasos '

1) mientras que no todas las aristas de p están en el esqueleto:

2) para cada arista e en p:

3) si la arista e no esta en el esqueleto:

4) modificar p: Sustituir e por MHT[e)

5) retornar p ,

En dicho Algoritmo 4, la terminación del bucle en la instrucción (1) se deduce directamente de la exigencia de que el MHT no debe contener referencias ciclicas. Esto limita et bucle "mientras" para un numero de iteraciones que no exceda el numero de aristas en el grafa.

Prueba por contradicción : Vamos a asumir que el bucle tiene mas iteraciones que el número de aristas en el grafo. Luego. en una secuencia de sustitución tendría que haber una repetición. Pero esto implicaría un ciclo en el MHT una contradicción con el hecho de que el MHT tiene que ser libre de ciclos por definición de la salida de la "Detección de Homotopia".

La Figura 10 ilustra el beneficio del MHT junto con ta IF'royección del Esqueleto (Algoritmo 4) en el contexto de la búsqueda de homotopias entre caminos, en comparación con el mas simple, pero la búsqueda "backtracking" es mas costosa utilizando sólo el MHL. Si bien la búsqueda "backtracking" en a) tiene que atravesar muChas ramas de búsqueda sin éxito hasta que encuentra la homolopia, las Proyecciones del Esqueleto en b) encuentran gran par1e de las homotopias de una manera determinista.

Por desgracia. el Esqueleto sigue siendo demasiado grande para garantizar el éxito: Con el fin de garantizar que la búsqueda de homotopia a partir de dos caminos homotópicos pI y p2 llega al mismo camino p' en el Esqueleto, no puede haber 2 caminos en el Esqueleto que sean homotópicos. Pero este no es el caso, como muestra el ejemplo de la Figura 10: Ambos caminos pI' y p2' (es decir, caminos resultantes de la proyección de caminos pI y p2) se encuentran completamente dentro del esqueleto. son homotópicos y no son iguales.

Pero si el espacio esta restringido aún mas mediante la exclusión de caminos que contienen "puntos de inversión" (un punto en el que se pasa la misma arista en una dirección y acto seguido en la dirección contraria), uno de hecho puede garantizar que la búsqueda de homotopia a partir de caminos homotópicos p1 y p2 siempre llega al mismo camino. Esto se lleva a cabo mediante la implementadón de la aplicación de un algoritmo para Eliminar los Puntos de Inversión, o Algoritmo 5, a los caminos proyectados p1', p2' dentro del Esqueleto, para excluir caminos que contienen puntos de inversión, para obtener caminos pr':lyectados en el Esqueleto y sin puntos de inversión pI", p2", en el que dicho Algoritmo S tiene el camino p' como entr.ada y comprende los siguientes pasos:

1) hacer'

2) encontrar cualquier subcamino en p' que coincide con el patrón [nI , n2, n11

3) modificar p': sustituir el subcamino [nI , n2 , nI] por [nI J

4) mientras haya cambios en p'

S) retornar p"

Gracias a este hecho. uno puede comprobar la homotopia entre 2 caminos haciendo la Proyección del Esqueleto y Eliminar los Puntos de Inversión para ambos caminos y comprobar si los resultados son iguales. Esto se realiza mediante el siguiente algoritmo de comprobación de Homotopia o Algoritmo 6, que tiene como entradas los caminos que estan, en general, fuera del Esqueleto (p1, p2), Y también el Esqueleto y el MHT, y que comprende los siguientes pasos:

1) pI '::: SkeletonProjection(p 1)

2) p2'::: SkeletonProjection(p2)

3) pI" = RemoveReversaIPoints(pl')

4) p2" = RemoveReversaIPoints(p2')

S) retornar pI" == p2"

donde los pasos (1) y (2) implernentan la aplicaciÓn d~~1 Algoritmo 4 pala, respectivi:lrnente, proyectar los caminos (pI, p2) que están, en general, fuera del Esqueleto pmo dentro del grafo, hacia los caminos (p1', p2') dentro del Esqueleto, y los pasos (3) y (4) implementan la aplicación del Algoritmo 5 a dichos caminos proyectados (p1', p2') dentro del Esqueleto, para la exclusión de caminos que contienen puntos de inversión, y en el que el comando retornar pI" := p2" del paso (5) del Algoritmo 6 realiza diCha comprobación de homotopia comprobando si los LJltimo!'; caminos (p1". p2") (e!'; decir. lo!'; proyectados en el Esqueleto y sin puntos de inversión) son igu<lles

Para una forma de realización preferida, uno de dictlos caminos proyectados en el Esqueleto y sin puntos de inversión pI" es uno de dichos canales candidatos bZ)l el otro p2" es un camino h que discurre sólo a través de la zona bien definida. Por lo tanto si el paso (S) del Algoritmo 6 da como resultado que bz = h, dicho bz no se identifica como un canal restringido.

Además de la aplicación relacionada con dicha realización preferida. el Algoritmo 6 tiene otras aplicaciones. para otras formas de realización. Se puede aplicar, por ejemplo, a la anteriormente descrita "Optimización de Canales". para realizar la comprobación de homotopia entre 'shor1esl" y 'subcamino' (ver la Unea 4) del algoritmo 4).

La figura 11 muestra gráficamente la aplicadón de los pasos del AlgOritmo 6, es decir, la "Proyección del Esqueleto", el "Eliminar puntos de inversión" y la comparación flnéll de la igualdad de los caminos obtenidos, para dos casos diferentes .

Un primer caso incluye caminos pI y p2, que, como $e muestra en la figura, se proyectan en el esqueleto como caminos p1', p2' Y se convierten en caminos p1", p2" después de haber quitado los puntos de inversión, y el resultado de su comparación demuestra que son caminos homotópicos, es decir, que p1" = p2".

Un segundo caso induye caminos ql y q2, que, como se muestra en la Figura se proyectan en el Esqueleto como caminos q1', q2' Y se convierten en caminos ql", q2 " después de haber quitado los puntos de inversión, y el resultado de su comparación muestra que son caminos no homotópicos, es decir, que ql" 'i q2""

La Figura 11 b muestra las leyendas de los elementos que se muestran en la Figura 11 a.

La Figura 12 muestra otro ejemplo de la aplicación del Algoritmo 6, en este caso por medio de una tabla.

La Figura 12a muestra las entradas para el algoritmo, el; decir:

-

Un Esqueleto que tiene tres aristas «1, 4), (2, 4) Y (3, 4» representado en líneas continuas,

-

Un MHT que mapea cada arista que no es parte del esqueleto «1 , 2), (1 , 3) y (2, 3), se muestra en lineas de puntos en el esqueleto) a un camino homotópico, y

-

Dos caminos dados pI. p2, cuya homotopía debe ser comprobada;

La figura 12b es una tabla que muestra gráficamente las diferentes operaciones realizadas en los caminos pI , p2 de acuerdo con el Algoritmo 6, incluyendo las proyecciones al esqueleto y la etiminación de los puntos de inversión para ambos caminos (columnas de la izquierda para pI y columnas de la derecha para p2) y el control de la igualdad (casilla central en la linea inferior de la tabla mostrada) ele los caminos obtenidos finalmente.

Las columnas etiquetadas como "stale pI" y "state p2" incluyen los caminos antes de realizar cualquier operación sobre el mismo, es decir. caminos pI y p2. en el priml~r miembro de las columnas , y debajo de ellos los caminos obtenidos después de la ejecución de las diferentes opl~raciones, es decir. p1' y p2' después de tas proyecciones al esqueleto, y pI" Y p2" después de la eliminación de puntos de inversión.

Se puede observar en la última fila de la tabla de la figura 12b que pI" y p2" son iguales, ya que ambos se refieren al mismo camino (2, 4, 3], Y por lo lanto son caminos homotópicos

Encontrar las clases de equivalencia homolópicas.

Se ha demostrado anteriormente que si la definición de un canal restringido se cumple para un camino, entonces se cumple automáticamente para todos los caminos homotópicos al mismo. Así que cuando se busca un canal reslringido no hay necesidad de revisar todos los posibles caminos de la zona bien definida para la zona bien definida a través de la zona no-bien definida (es decir, de tejido Sano a Sano a traves de Border-Zone, en el caso del miocardio). En cambio, es suficiente evaluar un reprE!Sentante de cada clase de equivalencia que contenga un camino que cumpla los requisitos. Hay que tener en cu·enta que la búsqueda también puede ser limitada a caminos sin puntos de inversión, porque cada camino con pun!os de inversión tiene un camino homotápico sin puntos de inversión en el Esqueleto (Demostración: Terminación del Algoritmo 5 "RemoveReversaIPoints", que se ha mostrado anteriormente).

Esto reduce significativamente el número de caminos para comprobar, especialmente cuando se considera el hecho siguiente:

Para cada camino posible en el grafo existe un camino l1omot6pico en el Esqueleto. Esto se deduce directamente de la definición del Algoritmo 4 ""Proyección del Esqueleto" (mod ifica un camino dado. manteniendo la homotopía al camino original hasta que todas las aristas están dentro del esqueleto) y su terminación (demostrado anteriormente en esta seCCión).

Así que en lugar de comprobar todos los caminos posibles de Sano a Sano en el grafo completo, sólo hay que comprobar aquellos que están en el Esqueleto. Esta 4~S una reducción importante porque, aunque el número de aristas en el Esqueleto es estadísticamente. sólo por un fador fijo pequeño (dependiendo sólo del método de discretización). menor que el número de aristas en el grafo original, la mayoría de estas aristas son parte de arboles que s610 están conectados at resto del grafo en sus raíces y por lo tanto no puede contribuir a ningún camino de la zona bien definida a la zona bien definida que tiene que ser cíclico y sin puntos de inltersión. La Figu ra 13 muestra un ejemplo con esos árboles irrelevanles eliminados, por medio de un proceso de poda, que da una idea visual inmediata de las 3 clases de equivalencia de homotopia: caminos que viajan de un lado a otro por encima de, entre y debajo de los obstáculos.

Dependiendo de la realización, este proceso de poda puede aplicarse o no de acuerdo con el metodo de la presente invención, con el fin de podar el Esqueleto para ser utilizado en el Algoritmo 6, ya que dicho algoritmo funciona también con un Esqueleto sin podar.

Primera Aplicación de la Detección de Homolopia: Eliminación iterativa de las aristas de esqueleto: Con el fin de construir el esqueleto y el MHT, el método comprende, para una realización, el uso de un Algorilmo de

Eliminación de Aristas lIeralivo, o Algoritmo 7, que utiliza como entradas el grafo y el MHL, dicho Algorilmo 7 que 5 comprende los siguientes pasos: 1) Inicializar el esqueleto como un conjunto de todas las aristas del grafo de entrada 2) Comenzar con un MHT vacio 3) Para cada arista e en el esqueleto en orden aleatorio 4) Mientras la arista e es parte del esqueleto: 10 5) Elegir un camino homotópico p a e de la lista MHl[eJ 6a) p '" SkeletonProjection{p) 6b) p" :: RemoveReversalPoints(p ') 7) Si p" no contiene la arista original e: 8) Elim inar e del esqueleto 15 9) Madir la entrada [e->p"] al MHT

10) Retomar (Esqueleto, MHT). El algoritmo 7 retorna un esqueleto y un MHT que curnplen dos de los tres criterios indicados anteriormente en la definición de "Detección de Homotopia"' No hay referencias ciclicas en el MHT (condición 1) y cada referencia en el

20 MHT está cubierta por una verdadera homotopia repres,entada por el MHl (condición 2). Demostración: Condiciones 1 y 2 como invariantes de bucle: Demostración: Ambas condiciones son invariantes del bucle "Mientras" en la instrucción (4) del Algoritmo 7 y por lo

25 tanto son automáticamente invariantes del bucle ~Para cada" en ta instrucción (3). Las condiciones son, evidentemente, satisfechas al principio del algoritmo: El MHT vado no puede contener ninguna referencia ciclica y todas las referencias que hay en el MHT (¡no hay ninguna!) estan cubiertas por homotopias reales, Asi que tiene que ser probado que se cumplen las 2 condiciones al final de cada ileración del bucle "Mientras', suponiendo que se cumplieron en el comienzo de la iteración, Hay 2 casos: o bien la condición (7) es falsa, Entonces no se realiza

30 ningún cambio en el MHT ni en el Esqueleto: asi, las 2 condiciones que se pretenden demostrar permanecen ciertas.

o la condición (7) es verdadera. En este caso la entrada [e->p"J se añade al MHT. Esta entrada está cubierta por una homotopia real porque p" se obtuvo por:

35 • Sustitución de e por un camino homotópico de MHL' Homot6pico según MHL

• Sustitución iterativa de sus sub-caminos homotópicos: Manteniendo la homotopia según MHT, Esto implica que las homotopias de acuerdo con MHL se mantienen porque asumimos que al comienzo de la iteración todas las referencias en MHT eslán cubiertas por homotopias en MHL

-

RemoveReversalPoints (Eliminación de puntos de invmsión): Manteniendo siempre la homotopía por su naturaleza (independientemente de MHL).

Además, no puede haber ninguna referencia clcHca en MHT al final de la iteraclOn, porque uno puede suponer que 45 no había ninguna referencia ciclica en el MHT en el comienzo de la iteración y la nueva entrada [e->p'] no puede cerrar ningún ciclo debido a la condición (7)'

Si [e->p"] fuera a cerrar un ciclo entonces tiene que halber habido antes una cadena de referencia [e1 -> ". -> el a partir de una arista e1 en p" en el MHT Pern Inda!; la!; arista!; F'n p" !;nn p,qr1f'! nF'1 f'!!;queleto y por lo tanto no tienen

50 ninguna referencia real en MHT l a llnica posibilidad que queda es la cadena de referencia [e1J trivial (longitud O) con e1 =e, Esto significa que la arista e original es p¿lrte de p" Pero este caso se comprueba V se evita por la condición (7) ,

Condición 3: Minimalidad

5

Condición 3, la minimalidad del esqueleto entre los que Cllmplen las condiciones 1 y 2, no esta garantizada para el Algoritmo 7. El resultado es mínimo sólo en el sentido de que usando esta tecnica en particular no se pueden quitar mas aristas del esqueleto. Pero -en función de la complejidad de la entrada y la suerte al elegir el orden aleatorio en el bucle principal -el resultado puede no ser minimo entre aq uellos que reúnan las condiciones 1 y 2. Así el Algoritmo 7 sólo puede ser visto como una heurística para la "Detección de Homotopia"

Este problema puede ser tratado mediante la ejecución del Algoritmo 7 repetidamente con distintos órdenes aleatorios para el bucle "Para cada" en la linea (3) y la combinación de los resultados. Haciendo esto con suficiente frecuencia garantiza que se llegara a un esqueleto mínimo. En la práctica. las pruebas empiricas han demostrado que induso un pequeño número de repeticiones ya conduce a un esqueleto mlnimo.

t5

Los efectos de trabajar con un esqueleto no-mínimo asumiendo la minimalidad pueden ser vistos como trabajar con una relaci6n de equivalencia de homotopia demasiado fi na (es decir, caminos que son homotópicos en la realidad serán tratados como no homotópicos), pero no tiene ninguna aira consecuencia negativa. Esto pOdría causar falsos positivos en la detección del canal restringido, pero , en la práctica , dichos posibles falsos positivos pueden eliminarse fácilmente por un procesamiento posterior.

25

Para resumir. en la práctica. la aplicación del método ,:le la presente invención no genera falsos positivos. ya que comprende la aplicación de la tecnica de la ejecución del Algoritmo de Eliminación Iterativa de Aristas descrito anteriormente , o Algoritmo 7, va rias veces y combinar los resultados. Sin embargo, una garantía de un 100% de probabilidades de no tener ningún falso positivo, es decir, de lograr un mínimo Esqueleto, se alcanza para un número muy elevado de iteraciones. y el porcentaje de probabilidades aumenta con cada iteración. Entonces, por lo tanto, se debe llegar a un compromiso entre el porcentaje de probabilidad de evitar falsos positivos yel costo de los recursos necesarios y el tiempo de procesamiento.

Las Figuras 14a a 14c muestran un ejemplo de la aplicación del Algoritmo 7.

En particular, la Figura 14a muestra las entradas de dicho algoritmo, es decir:

-Un grafo que tiene seis aristas «1 , 2), (1 , 3), (1. 4), (2, 3) , (2, 4) Y (3, 4»

representadas por lineas sólidas, y

35 45

-Un MHL que contiene por cada arista del grafo un conj unto de caminos que son homotópicos a ella . las figuras 14b y 14c son tablas que muestran graficamente la ejecución de las diferentes lineas de Algoritmo 7, comenzando con un Esqueleto incluyendo todas las aristas. en la Linea (1). y un MHT vacio, en la Linea (2) . y continuando mediante la aplicación de la operación de la linea (3) para la selección de todas las aristas e, la operación de las Lineas (4)/(5) para elegir, para cada arista e en el esqueleto. un camino homotópico p en el MHl. la ejecución de la Linea (6a) para proyectar p en el esqUE~leto como p' . la ejecución de la Linea (6b) para eliminar los puntos de inversión de p' para obtener p", y si la cond ición de la linea (7) se cumple la ejecución de la Linea (8) para eliminar e del esqueleto (las aristas eliminadas e s·e muestran en lineas discontinuas) y la ejecución de la línea (9) para agregar al MHT una entrada que mapea e a p" SI la condición de la línea (7) no se cumple , entonces tanto el esqueleto corno el MHT se mantienen sin cambios. Piara la realización ilustrada, los resultados de la linea (10), es decir. el esqueleto oblenido y el MHT, son los que se mllestran en la Figura 12a

Segunda Implementación de la Detección de Homotopia:

El melado de la presente invención comprende , como una alternativa al Algoritmo 7 descrito anteriormente. es decir, al Algoritmo de Eliminación de Aristas Iterativo del esqueleto, con el fin de construir el Esqueleto y el MHT, para otra forma de realización, utilizar un Algoritmo de Eliminación de Ciclos Homotópicos-Nulos, o Algoritmo a, utilizando las mismas entradas que el Algoritmo 7, es decir, el grafo y el MHl

55

Antes de describir el Algoritmo 8, se da una descripción de los conceptos en los que dicho algoritmo se basa con referencia a la Figura 16.

Definición de Caminos Homotópicos-Nulos.

Un camino homotópico-nulo es un camino que es homot6pico a un camino constante (que contiene sólo un punto). Debido a la restricción de que el punto inicial y el punto final de ambos caminos tienen que coincidir para la homotopia, sólo los caminos ciclicos pueden se r homotópicos a caminos constantes . Pero no lodos los caminos cíclicos son homotópicos-nulos, los que rodean a un agujero en el espacio topológico no lo son. la Figura 16a muestra un ejemplo de un camino f homotópico-nulo y su contraparte homotópico constante 9

65

los caminos homotópicos-nulos pueden ser útiles para encontrar caminos homotópicos de longitud arbitraria . la

20

división de un camino homotópico-nulo y la inversión de uno de sus componenles da como resultado dos caminos homotópicos (véase la Figura 16b a e). la elección del punto de división permite la regulación de la longitud de ambos caminos Esto permite dividir un camino homolópico-nulo en un camino Que contiene sólo una arista y otro camino homotópico a esa arista -un par adecuado para una entrada en el MHT.

Mirandolo al revés, dos caminos homotópicos se pueden utilizar para crear un camino homotópico-nulo invirtiendo uno de los caminos y concatenándolos. l os dos homotópicos pueden venir. por ejemplo, de un MHl.

De esla manera, los caminos homolópicos-nulos pueden ser el enlace perdido enlre las entradas del MHl y las entradas del MHT.

El Algoritmo 8 comprende los siguientes pasos:

1) Inicializar el Esqueleto como un conjunto de todas las arislas en el grafo de enlrada 2) Empezar con un Mapa de Homotopia Transitivo (MH"T) vacío 3) Empezar con una cola vacia 4) Para cada entrada [an'sta __ altemativePath] en MHL ' 5) ciclo" [arista] oH-Reverse{altemativePath) 6) enqueue(coJa, ciclo) 7) Mientras la cola no esté vacía: 8) ciclo" pop(co/a) 9) skelelonCycJe '" RemoveReversaIPoints(SkeletonProjection(ciclo)) 1 O Sí hay una arista singleOccuranceEdge que ocurre exactamenle una vez en skeletonCycle: 11) Dividir skeletonCycle: Calcular el prefijo y el sufijo tal que Prefijo H [singleOccuranceEdge) H sufijo == skeletonGyclc 12) allemativePath =Reverse(sufljo +-lo prefijo) 13) Eliminar singleOccuranceEdge del Esqueleto 14) Añadir la entrada [singleOccuranceEdge -+ altemativePath] en el MHT 15) Si no: 16) Para cada arista edgeToReplace en el cido: 17) Para cada edgeAlternative en MHl[edgeToReplacel 18) alternativeCycle = Reemplazar edgeToReplace por edgeAltemalive en cic:lo 19) cnqucuc(co/a, al/cmatívcCycfc) 20) enqueue (cola, ciclo) 21) Relornar (Esqueleto, MHD la función Reverse calcula el camino inverso a un c<lmino delerminado. El operador +-t-concatena dos caminos

dados. la variable cofa es una cola FIFO que contiene lodos los ciclos homolópicos-nulos cuya cobertura por el MHT sigue

pendiente o sin marcar. la operación enqueue añade un nuevo objeto al final de la lista. la operación pop elimina el primer elemento de la lisia y lo relorna. Al comienzo la cola contiene lodos los ciclos homotópicos-nulos que se pueden deducir directamente del Mapa de

Homotopia local. Cada uno de estos ciclos es proyectado en el Esqueleto adual y limpiado de puntos de inversión. El ciclo resultante es entonces todavia homotópico-nulo y puede ayudaf a crear una nueva entrada en MHT que cubre la homotopia local (lineas 11 a 14 del Algoritmo 8). En caso que no sea posible -lo que sólo ocurre en casos patológicos -enlonces el Mapa de Homotopia local se utiliza pafa construir ciclos homotópicos-nulos alternativos Que podrían ser más féciles de traducir a las entradas del MHT los ciclos de nueva construcción, asi como el ciclo inicial se ponen en cola para su procesamiento.

Eliminación de Ciclos Homotópicos-Nulos como Detección de Homolopia: Condición 1: No hay referencias ciclicas

El objetivo altemativePalh del MHT no incluye la arista singleOccuranceEdge porq ue no hay una segunda ocurrencia de singleOccuranceEdge en skeletonCycJe. Esto aseguró que no existen entradas directamente ciclicas en el MHT El hecho de que todas las aristas de altemativePath sean parte del Esqueleto en el momento de la inserción descarta entradas cíclicas indirectamente. Esto satisfacElla condición 1 de la Detección de Homotopia.

Condición 2: l as entradas del MHT cubiertas por homotlJpias reales (representadas por el MHl)

Cada camino en la cola es homotópico-flUlo: los ciclos que se insertan inicialmente en la linea 6 son homotÓpicos· nulos porque cada uno de ellos consiste en la concatenación de un primer camino «(arista]) y la inversa de un segunda camino (aftemalivePalh) que es homotópico al primer camino. l os ciclos que se insertan en la linea 19 del Algoritmo 8 son homotópicos-nulos porque se derivan de un ciclo homolópico-nulo (procedente de la cola) por sólo modificaciones homolópicas. las ciclos que se insertan en la linea 20 del Algoritmo 8 son las entradas que han estada en la cola antes '1 por lo tanta son homatópicas-rlulas. también.

Cada camina ske/elanCycle es homotópico-nulo: Como las salidas de SkeletonProjection y RemoveReversalPoinls son homotópicas a sus respectivas entradas. el camino skeletonCycle es homotópico al ciclo (que viene de la cola y. por tanto. es homotópico-nulo) y por lo tanto es homotópico-nulo. lambién.

la arista singleOccuranceEdge '1 el camino altemativl~Path son homotópicas porque han sido construidos cama componentes del ciclo skefetonCycle que es homot6pico-nulos con uno de ellos invertido. Esto asegura que la condición 2 de la Detección de Homotopla (las entradas de MHT estan cubienas por homotoplas reales derivadas del MHl) se cumple

Condición 3: Minimalidad del esqueleto entre los conjuntos que cumplen las condiciones 1 y 2

la terminación del bucle ··Mientras". en el Algoritmo 8. implica que por cada ciclo que haya estado alguna vez en la cola la rama del condicional "Si" entre las lineas 11 a 14 se ha ejecutado una vez (siempre que el algoritmo entra en la rama "Si na". el ciclo se vuelve a agregar a la cola después).

Demostración indirecta: Se supone que el Esqueleto no es mínimo entre los conjuntos que cumplen las condiciones 1 '12. Esto implica que todavía hay una arista (llamada e) en el Esqueleto que se puede eliminar al tiempo que se añade una referencia a otro (según el MHl usando 'Iransilividad) camino homotópico (llamado p) sin introducir referencias cíclicas, El hecho de que esta homotopia SEla derivada del MHl significa que hay una secuencia p(l)..... p(n) de caminos donde p(l)"le] '1 p(n)"p Y para cada par p(i), p(i+1) debe haber una entrada Ile(i) ...... Ip(i)J que soporta directamente la homotopia entre p(i) '1 p{i+l). Como p{n)=p no es homotópico a p(l)=le] de acuerdo con el supuesto. debe haber un minimo m con p(m) que no sea homotópico a p{m+l) de acuerdo con el MHT. Pero el ciclo derivado de la entrada Ile(m) __ Ip(m)] del MHT debe haber sido procesado por el algoritmo y por lo tanto debe ser

homotópico-nulo segun el MHT. Por lo tanto le(m) d.~be ser homotópico a Ip(m) y por lo tanto p(m) debe ser homotópico a p(m + 1) -una contradicción.

"Eliminación de Ciclos Homotópicos-Nulos " frente a "Eliminación de Aristas Iterativa":

Tanto el Algoritmo Iterativo de Eliminación de Aristas (Algoritmo 7) como el Algoritmo de Eliminación de Ciclos Homotópicos-Nulos (Algoritmo 8) comienzan can un Esqueleto completo '1 eliminan de forma iterativa las aristas del mismo mediante la adición de caminos alternativos al MHT

Dif.eren. sin embargo. en la forma que encuentran esas alternativas homotópicas. Mientras que el bucle principal de

Eliminación de Aristas lIerativo se ejecuta a través de una lista de ladas las aristas e intenta sustituirlos por alternativas que se encuentran a través de indicios desde sus vecinos. la Eliminación de Ciclos Homotópicos-Nulos itera sobre todas las homotopias locales que deben ser incorporadas en el MHT y no termina hasta que todas esas homotopias locales están cubiertas. Esto garantiza un Esqueleto minimo y. por tanto. de que se cumplen todas las condiciones establecidas por la definición de ta Detección de Homotopia. Esta garantia viene con el precio de una complejidad computacional asintótica para el peor caso mas elevada. que a pesar de ello no parece ser relevante en la práctica -no ha habido un solo caso practico que hubiera requerida al algoritmo para entrar ni siquiera una sola vez en la rama "Si no". cuya existencia es la razón de la complejidad teórica peor.

Una perSOna experta en la materia pOdria introducir cambios '1 modificaciones en las realizaciones descritas sin apartarse del alcance de la invención tal como se define en las reivindicaciones adjuntas.

Claims (11)

1. REIVINDICACIONES

   1 -Un método implementado por ordenador para la identificación de canales a partir de datos representativos en un volumen 3D, que comprende la identificación. en un volumen 3D de un objeto, tres zonas diferentes bas:tndose en los valores de al menos un parámetro fisico ylo funcional representativo de propiedades fisicas ylo funcionales de dicho objeto, como una zona de un primer tipo (H) , un<l zona de un segundo tipo (BZ) y una zona de un tercer tipo (C), donde dichos primero, segundo y tercero lipos de ;zona son diferentes entre si, caracterizado porque el método comprende realizar los pasos siguienles mediante el procesamiento de dichos datos representativos:

   -

   identificar automáticamente como un canal candidato (bz) un camino que discurre a través de dicha zona de un segundo tipo (B2) y que se extiende entre dos puntos d4~ dicha zona de un primer tipo (H); y

   -

   llevar a cabo de foona automática, en un espacio topológico (H_and_B2_topo) que incluye la zona de un primer tipo (H) y la zona de un segundo lipo (82) y no incluye la zona de un tercer tipo (C) , operaciones homotópicas entre dicho canal candidato (bz) y caminos (h) que discurren s610 a través de dicha zona de un primer tipo (H) , y si el resultado de dichas operaciones homotópicas es que el canal candidato (bz) no es homotópico a ningún camino discurriendo sólo a través de la zona de un primer tipo (H) se Identifica el canal candidato (bz) como un canal restringido.

   2 -. El método de acuerdo con la reivindicaCión 1. en el que dichas propiedades físicas ylo funcionales se refieren a las propiedades de velocidad de propagación, dicha zona de un primer tipo (H) siendo una 20na de velocidad de propagadón rápida y dicha zona de un segundo tipo (8Z) siendo una zona de velocidad de propagación lenta.
2. 3.-El método de acuerdo con la reivindicación 1 o 2, que comprende realizar dichas operaciones homotópicas para varios canales candidatos. y que comprende además '

   -

   realizar una conversión del volumen 3D a dicho espacia topológico, en el que dicho espacio topológico es un espacio topológico de zonas combinadas (H_and_82_topo). donde el metodo comprende además la realización de una conversión de dicha zona de un primer tipo (H) en un correspondiente espado topOlógico de una sola zona (H_topo) .

   -

   procesar dichos espacios topológicos (H_and_B2_topo, H_IOpo) y obtener las clases de equivalencia para dichos caminos. medianle la implementación de un primer aluoritmo para la oblención de dichas clases de equivalencia, que tiene como entradas ambos de dichos espacios topológicos (H_and_82_topo, H_topo) y que genera como salida un conjunto de salida de representantes de cla.ses de equivalencia de canal, un camino representante por clase, en un espacio topológico, y

   -

   realizar dicha operación homolópica sólo para un camino representativo por clase de equivalencia, tanto para los canales candidatos (bz) como para los caminos (h) que discurren sólo a través de la zona de un primer tipo (H).

   4 -El método de acuerdo con la reivindicadón 3. en E~I que dicho primer atgoritmo, o Algoritmo 1. comprende las siguientes etapas'

   1) Elegir dos puntos. de inicio y finalización, en 1<l1.:on<l de solo espacio topOlógico (H_lopo):

   2) obtener. a través de la instrucción 'ChannelCandidatcs', clases de equivalencia en el espacio topológico de zonas combinadas (H_and_BZ_topo). para caminos entre dichos dos puntos,

   3) obtener. a traves de la instrucción 'HeallhyPaths'. clases de equivalencia en el espacio topOlógico de una sola zona (H_topo), para caminos entre dichos dos puntos;

   4) comprobar para cada camino bz obtenido mediante 'ChanneICandldates"

   5) Y para cada camino h obtenido mediante 'HeallhyPalhs"

   6) si bz es homotópico de h:

   7) descal1ando bz como canal restringido y avanzar al siguiente bz

   B) de 10 contrario, es decir. si b1.: no es homol6pico a h. determinar que bz es un canal restringido y agregarlo a dicho conjunto de salida
3. 5.-El método según la reivindicación 4, que comprende el colapso/conlracción dicho espacio topológico de una sola zona (H_topo) de tal manera que sólo haya un camino sano h teniendo como dichos puntos de inicio y de finalización el mismo punto, en el Que dichas etapas 6), 7) Y 8) se llevan a cabo para dicho sólo un camino sano h.
4. 6.-El método de acuerdo con la reivindicación 5, en el que cuando se sabe de antemano la dase de equivalenCia de canal homotópica a dicho sólo un camino sano h, el re:sultado de 'ChannelCandidates' incluye todas excepto dicha clase de equivalencia de canal homotópica, y dichas etapas de 5), 6) Y 7) se omiten. y todos los caminos bz obtenidos mediante 'ChannelCandidates' se añaden al conjunto de salida.
5. 7 ._ Et método de acuerdo con la reivindiC"..ación 4, 5 CI 6, que comprende la implementación de un algoritmo de optimización para optimizar dichos representantes de las clases de equivalencia de canal de dicho conjunto de salida, comprendiendo dicho algoritmo de optimización:

   1) para un representante 'c' de cada clase de equivalencia de canal, es decir, para cada bz del conjunto de salida:

   2) Y para varios sub-caminos 'sub-camino' de 'c':

   3) buscar el camino mas corto entre el inicio y el final del sub-camino: 'shortest';

   4) si dicho camino mas corto, 'shortesl', es homotópico ~I dicho sub-camino, 'sub-camino':

   5) modificar 'c', sustituyendo 'sub-camino' con 'shortest'.
6. 8.-El método de acuerdo con una cualquiera de las reivindicaciones 4 a 7, que comprende la implementación de un segundo algoritmo que inlegra a dicho primer algoritme), leniendo dicho segundo algoritmo como datos de entrada un espacio geométrico, con respecto a dicho volumen 3D, con información de funcionalidad asignada permitiendo llevar a cabo la identificación de dichas tres zonas djfE~rentes (H, BZ, C), llevando a cabo dichas conversiones en dichos espacios topológicos (H_and_BZ_topo, H_topo) en la forma de al menos una estructura de datos adecuada para el procesamiento topológico y de información auxiliar adicional añadida, y que genera como salida dicho conjunto de representantes de clases de equivalencia de canal, en un espacio geométrico.
7. 9.-El método según la reivindicación 8, en el que dicha al menos una estructura de datos es un grafo de conectividad con un Mapa de Homotopia local que contiene para cada arista del grafo un conjunto de caminos que son homotópicos a ella .
8. 10.-El método de acuerdo con la reivindicación 9, que comprende la implementación de un tercer algoritmo, o Algoritmo 3, para convertir el volumen 3D en dicho grafo y en dicho Mapa de Homotopia local, teniendo dicho tercer algoritmo como entrada el espacio geométrico representado por nodos ns y elementos e/s que conectan a dichos nodos ns, siempre y cuando tos elementos e/s sean el casco convexo de sus nodos ns, y generando como salida el espacio topológico representado por dicho grafo y dicho Mapa de Homotopia local, o MHl, en el que dicho Algoritmo 3 comprende:

   1) para cada elemento el en e/s:

   2) para cada nodo n1 en nodos (el):

   3) para cada nodo n2 en nodos (el) \ {n1}:

   4) añadir nodos n1 y n2 al grafo

   5) añadir arista (n1, n2) al grafo

   6) para cada nodo n3 en nodos (el) \ (nl , n2}:

   7) afladir homotopla entre (n1 , n2) y [n1, n3, n2) para MHl.
9. 11 .-El método segun la reivindicación lO, que comprende la implementación de un algoritmo de detección de homotopia que tiene como entrada dicho grafo y dicho MHl, y transformar dicha entrada en una salida que incluye las dos estructuras de datos siguientes, que constituyen dicha información auxiliar adicional.

   • Esqueleto: un subconjunto de las aristas de dicho gr;3fo, que satisfacen las siguientes condiciones;

   Mapa de Homotopia Transitivo o MHT: una tabla que asigna cada arista que no forma parte del esqueleto a un camino homot6pico de una manera que sea compatible con las siguientes condiciones;

   en el que dichas condiciones son:

   1. no hay refererlClas c1clicas en MHT: al casco transitivo de la relación definida por dependsOn como: dependsOfl

   (a. b) ~b e MHT (a) no se le permite tener ninguna entrada refiexiva,

10. 2.

    las referencias en MHT tienen que estar cubier1as por homotopias reales, representadas por el MHl. al MHT se le permite asignar una arista e a un camino p, sólo si se puede deducir por el MHL y las propiedades matemáticas de homotopia que e es homotópico de p;

11. 3.

    el Esqueleto tiene que ser mínimo, o el mínimo posible. entre conjuntos que satisfagan las condiciones 1 y 2. 12.-El método segun la reivindicación 11, que comprende la implementación de un algoritmo de comprobación de

    Homolopla o Algoritmo 6, que tiene como entradas caminos que estan, en general, fuera del Esqueleto (p1. p2) Y también al Esqueleto y al MHT. y que comprende la aplicación de las siguientes funciones: 1) p1'" SkeletonProjection (pI) 2) p2' '" SketetonProjection (p2) 3) p1" = RemoveReversalPoints (pI') 4) p2" =" RemoveReversalPoints (p2')

    5) Retornar pI M "': p2"

    donde pI' = SkeletonProjection (pI) y p2' '" SkeletonProjection (p2) implementan la aplicación de un algoritmo de proyección en el Esqueleto, o Algoritmo 4, respectivamente, para la proyección de caminos (pI . p2) que eslán, en general, fuera del Esqueleto pero dentro del grafo, hacia caminos (pI', p2') en el inlerior del Esqueleto, teniendo dicho Algoritmo 4 al camino p como entrada y que comprende'

    1) mientras que no todas las aristas en p estan en el Esqueleto: 2) para cada arista e en p: 3) si la arista e no esla en el Esqueleto' 4) modificar p sustituyendo e por MHT fe] 5) retornar p' donde pI H RemoveReversalPoints (pI') y p2" '" RemoveReversalPoints (p2') del Algoritmo 6 implementan la

    '"

    aplicación de un algoritmo de eliminación de puntos de inversión, o Algoritmo 5, a los caminos proyectados (pI ', p2') en el interior del Esqueleto, para exchJlr caminos que contienen punlos de inversión, para obtener caminos proyeclados en el Esqueleto y sin puntos de inversión (pI ", p2"), en el que dicho Algoritmo 5 1iene el camino p' como entrada y comprende:

    1) hacer: 2) encontrar cualquier sub-camino en p' que coincide con el patrón (nI , n2, nI] 3) modificar p' mediante la :sustitución del sub-camino fnl, n2, nI) por Inl) 4) mientras que hay cambios en p' 5) retornar pM yen donde Retornar pI" == p2" del Algoritmo 6 realiza dicha comprobación de homotopia medianle la comprobación

    de si estos ultlmos caminos (p1 ". p2") son iguales 13 -Et método segun la reivindicación 12, en et que uno de dichos caminos proyectados en el Esqueleto y sin puntos de inversión (pI") es uno de dichos canales canljidatos (bz) y el otro (p2·') es un camino (h) que discurre sólo a través de la zona de un primer tipo (H).

    14,· El método de acuerdo con una cualquiera de las reivindicaciones 11 a 13, que comprende!Jn algoritmo de

    Eliminación Iterativa de Aristas, o Algoritmo 7, para la construcción de dicho Esqueleto y dicho MHT utilizando como

    entradas el grafo y el MHl, dicho Algoritmo 7 incluyendo los pasos siguientes:

    1) inicializar el Esqueleto como un conjunto de lodas las aristas del grafo de entrada

    2) a partir de un MHT vado

    3) para cada arista e en el Esqueleto en orden aleatorio:

    4) mientras que la arista e es parte del Esqueleto:

    5) elegir un camino homotópico p a e de la lista MHl(e]

    6a) p' "" SkelelonProjeclion (p)

    6b) pM =RemoveReversalPoints (p')

    7) si p.' no contiene la arista original e:

    8) retirar e del Esqueleto

    9) añadir entrada [e .> pHI para MHT 10) retornar (Esqueleto, MHT), para relornar como salida el Esqueleto construido y el MHT construido. 15.-Un producto de programa de ordenador, que incluye instrucciones de código Que cuando se ejecutan en un

    ordenador implementan las etapas del método de una cualquiera de las reivindicaciones anteriores