Computer implemented method for identifying channels from representative data in a 3d volume and a computer program product implementing the method

1. A computer implemented method for identifying channels from representative data in a 3D volume, the method comprising identifying, in a 3D volume of an object, three different zones based on values of at least one physical and/or functional parameter representative of physical and/or functional properties of said object, as a zone of a first type (H), a zone of a second type (BZ) and a zone of a third type (C), where said first, second and third zone types are different from each other, said object including zones which are susceptible to include constrained channels to be identified including myocardium conductive channels, wherein the method comprises performing the next steps by processing by a computer said representative data:

automatically identifying as a candidate channel (bz) a path running through said zone of a second type (BZ) and extending between two points of said zone of a first type (H); and

automatically performing, on a topological space (H_and_BZ_topo) including the zone of a first type (H) and the zone of a second type (BZ) and not including the zone of the third type (C), homotopic operations between said candidate channel (bz) and paths (h) running only through said zone of a first type (H), and if the result of said homotopic operations is that the candidate channel (bz) is not homotopic to any path running only through the zone of a first type (H) identifying the candidate channel (bz) as a constrained channel.

2. The method according to claim 1 , wherein said physical and/or functional properties relate to propagation velocity properties, said zone of a first type (H) being a fast propagation velocity zone and said zone of a second type (BZ) being a slow propagation velocity zone.

3. The method according to claim 1 , wherein said homotopic operations are performed for several candidate channels, and the method further comprising:

performing a conversion of the 3D volume into said topological space, wherein said topological space is a combined zones topological space (H_and_BZ_topo), the method further comprising performing a conversion of said zone of a first type (H) into a corresponding single zone topological space (H_topo);

processing said topological spaces (H_and_BZ_topo, H_topo) and obtaining equivalence classes for said paths, by means of implementing a first algorithm for obtaining said equivalence classes, which has as inputs both of said topological spaces (H_and_BZ_topo, H_topo) and which generates as output an output set of representatives of channel equivalence classes, one representative path per class, in a topological space; and

performing said homotopic operation only for one representative path per equivalence class, both for channel candidates (bz) and for paths (h) running only through the zone of a first type (H).

4. The method according to claim 3 , wherein said first algorithm comprises the following steps:

choosing two points, Start and End, in the single zone topological space (H_topo);

obtaining equivalence classes in the combined zones topological space (H_and_BZ_topo), for paths between said two points, said equivalent classes being termed ‘ChannelCandidates’;

obtaining equivalence classes in the single zone topological space (H_topo), for paths between said two points, said equivalent classes being termed ‘HealthyPaths’;

checking for every path bz in ChannelCandidates; and

for every path h in HealthyPaths, if bz is homotopic to h discarding bz as constrained channel and advance to next bz, otherwise, i.e. if bz is not homotopic to any h, determining that bz is a constrained channel and adding it to said output set.

5. The method according to claim 4 , further comprising collapsing/contracting said single zone topological space (H_topo) such that there is only one healthy path h having as said Start and End points one and the same point, wherein said step of checking if bz is homotopic to h and so discarding bz as constrained channel and advance to next bz or otherwise determining that bz is a constrained channel and adding it to said output set is performed for said only one healthy path h.

6. The method according to claim 5 , wherein when it is known in advance the channel equivalence class homotopic to said only one healthy path h, said ChannelCandidates include all except said homotopic channel equivalence class, and said step of checking, for every path h in HealthyPaths, if bz is homotopic to h and so discarding bz as constrained channel and advance to next bz is omitted, all of the paths bz in Channel Candidates being added to the output set.

7. The method according to claim 6 , further comprising implementing a channel optimization algorithm for optimizing said representatives of channel equivalence classes of said output set, said channel optimization algorithm comprising:

for one representative ‘c’ of every channel equivalence class, i.e. for every bz of the output set, and for several subpaths ‘subpath’ of ‘c’ finding the shortest path between the start and end of subpath: ‘shortest’; and

if said shortest path, ‘shortest’, is homotopic to said subpath, ‘subpath’ modifying ‘c’ by replacing ‘subpath’ with ‘shortest’.

8. The method according to claim 4 , further comprising implementing a channel optimization algorithm for optimizing said representatives of channel equivalence classes of said output set, said channel optimization algorithm comprising:

for one representative ‘c’ of every channel equivalence class, i.e. for every bz of the output set, and for several subpaths ‘subpath’ of ‘c’ finding the shortest path between the start and end of subpath: ‘shortest’; and

if said shortest path, ‘shortest’, is homotopic to said subpath, ‘subpath’ modifying ‘c’ by replacing ‘subpath’ with ‘shortest’.

9. The method according to claim 4 , further comprising implementing a second algorithm integrating said first algorithm, said second algorithm having as input data a geometrical space, regarding said 3D volume, with assigned functionality information allowing to perform said identifying of said three different zones (H, BZ, C), performing said conversions into said topological spaces (H_and_BZ_topo, H_topo) in the form of at least one data structure suitable for topological processing and added additional auxiliary information, and which generates as output said set of representatives of channel equivalence classes, in a geometrical space.

10. The method according to claim 9 , wherein said at least one data structure is a connectivity graph with a Local Homotopy Map (LHM) which contains for every edge of the graph a set of paths that are homotopic to it.

11. The method according to claim 10 , further comprising implementing a third algorithm for converting the 3D volume into said graph and LHM, said third algorithm having as input the geometrical space represented by nodes ns and elements els connecting said nodes ns, as long as the elements els are the convex hull of their nodes ns, and generating as output the topological space represented by said graph and said LHM, wherein said third algorithm comprises:

for every element el in els, and

for every node n1 in nodes(el), and

for every node n2 in nodes(el) \ {n1}:

adding nodes n1 and n2 to graph; and

adding edge (n1, n2) to graph; and

for every node n3 in nodes(el) \ {n1, n2}:

adding homotopy between (n1, n2) and [n1, n3, n2] to LHM.

12. The method according to claim 11 , further comprising implementing a homotopy detection algorithm having as input said graph and said LHM, and transforming said input into an output including the following two data structures, which constitute said additional auxiliary information:

Skeleton: a subset of edges, from the edges of said graph, meeting the conditions below; and

Transitive Homotopy Map (THM): a table that maps every edge that is not part of the Skeleton to one homotopic path in a way that is compatible with the conditions below;

wherein said conditions are:

a first condition comprising no cyclic references in THM: the transitive hull of a relation dependsOn defined by dependsOn(a, b)⇔b∈THM[a] is not allowed to have any reflexive entries;

a second condition comprising that references in THM have to be covered by real homotopies, represented by the LHM: the THM is allowed to map an edge e to a path p, only if it can be deduced by the LHM and the mathematical properties of homotopy that e is homotopic to p; and

a third condition comprising that Skeleton has to be minimal, or as minimal as possible, among sets meeting said first and second conditions.

13. The method according to claim 12 , further comprising implementing a Homotopy check algorithm having as inputs paths which are, in general, out of the Skeleton (p1, p2) and also the Skeleton and the THM, and comprising applying at first a Skeleton Projection algorithm and then a Reversal Point Removal algorithm to both paths p1 and p2 and further comparing a result obtained, where said Skeleton Projection algorithm consists of the iterative replacement of all edges e in the input path that are not in the Skeleton by THM[e], until all edges in the path are in the Skeleton, and where said Reversal Point Removal algorithm consists of the iterative replacement of all sub-sequences matching the pattern [n1, n2, n1] in a node list representation of the path by a simplified node sequence [n1], until no sub-sequences matching said pattern occur in the path.

14. The method according to claim 13 , wherein one of said paths projected into the Skeleton and without reversal points (p1″) is one of said channel candidates (bz) and the other (p2″) is one path (h) running only through the zone of a first type (H).

15. The method according to claim 14 , further comprising an Iterative Edge Removal algorithm for constructing said Skeleton and said THM using as inputs the graph and the LHM, said Iterative Edge Removal algorithm including the following steps:

initializing the Skeleton as a set of all edges in the input graph;

starting with an empty THM; and

iteratively applying an Edge Removal Step until no more changes can be made to the Skeleton by:

choosing an edge e from the Skeleton,

choosing a homotopic path p from the LHM entry corresponding to e,

applying the Skeleton Projection and Reversal Point Removal algorithms to said homotopic path p, and

if the resulting projected path does not contain the edge e, then removing e from the Skeleton and adding a mapping from the edge e to the projected path to the THM.

16. The method according to claim 12 , further comprising an Iterative Edge Removal algorithm for constructing said Skeleton and said THM using as inputs the graph and the LHM, said Iterative Edge Removal algorithm including the following steps:

initializing the Skeleton as a set of all edges in the input graph;

starting with an empty THM; and

iteratively applying an Edge Removal Step until no more changes can be made to the Skeleton by:

choosing an edge e from the Skeleton,

choosing a homotopic path p from the LHM entry corresponding to e,

applying the Skeleton Projection and Reversal Point Removal algorithms to said homotopic path p, and

if the resulting projected path does not contain the edge e, then removing e from the Skeleton and adding a mapping from the edge e to the projected path to the THM.

17. The method according to claim 1 , further comprising implementing a second algorithm integrating said first algorithm, said second algorithm having as input data a geometrical space, regarding said 3D volume, with assigned functionality information allowing to perform said identifying of said three different zones (H, BZ, C), performing said conversions into said topological spaces (H_and_BZ_topo, H_topo) in the form of at least one data structure suitable for topological processing and added additional auxiliary information, and which generates as output said set of representatives of channel equivalence classes, in a geometrical space.