neurospin.spatial_models.hroi

Module: neurospin.spatial_models.hroi

Inheritance diagram for nipy.neurospin.spatial_models.hroi:

This module contains the specification of ‘heierarchical ROI’ object, Which is used in spatial models of the library such as structural analysis

The connection with other classes is not completely satisfactory at the moment: there should be some intermediate classes between ‘Fields’ and ‘hroi’

Author : Bertrand Thirion, 2009

Class

NROI

NROI(parents=None, affine=array([[ 1., 0., 0., 0.],

[ 0., 1., 0., 0.],

[ 0., 0., 1., 0.],

[ 0., 0., 0., 1.]]), shape=None, xyz=None, id='nroi')

Bases: nipy.neurospin.spatial_models.roi.MultipleROI, nipy.neurospin.graph.forest.Forest

Class for ntested ROIs. This inherits from both the Forest and MultipleROI self.k (int): number of nodes/structures included into it parents = None: array of shape(self.k) describing the

hierarchical relationship

affine=np.eye(4), array of shape(4,4),

coordinate-defining affine transformation

shape=None, tuple of length 3 defining the size of the grid

implicit to the discrete ROI definition

Methods

Kruskal
Kruskal_dev
Voronoi_Labelling
Voronoi_diagram
WeightedDegree
adjacency
all_distances
anti_symmeterize
append_balls
append_discrete_ROI
as_multiple_balls
cc
check
check_consistency
check_features
check_header
clean
cliques
complete
complete_roi_feature
compute_children
compute_discrete_position
converse_edge
copy
cut_redundancies
define_graph_attributes
degrees
depth_from_leaves
dijkstra
discrete_to_roi_features
eps
feature_argmax
floyd
from_3d_grid
from_adjacency
from_labelled_image
get_E
get_V
get_children
get_descendents
get_edges
get_k
get_parents
get_roi_feature
get_size
get_vertices
get_weights
is_connected
isleaf
isroot
knn
leaves_of_a_subtree
left_incidence
list_of_neighbors
main_cc
make_forest
make_graph
make_image
merge_ascending
merge_descending
merge_simple_branches
mst
normalize
plot_discrete_feature
plot_roi_feature
propagate_upward
propagate_upward_and
reduce_to_leaves
remove_edges
remove_roi_feature
remove_trivial_edges
reorder
reorder_from_leaves_to_roots
right_incidence
rooted_subtree
set_discrete_feature
set_discrete_feature_from_image
set_discrete_feature_from_index
set_edges
set_euclidian
set_gaussian
set_roi_feature
set_roi_feature_from_image
set_weights
set_xyz
show
skeleton
subforest
subgraph
symmeterize
to_neighb
tree_depth

NROI.Kruskal()

Creates the Minimum Spanning Tree self using Kruskal’s algo. efficient is self is sparse

Returns:

K: WeightedGraph instance :

the resulting MST

NROI.Kruskal_dev()

Creates the Minimum Spanning Tree self using Kruskal’s algo. efficient is self is sparse

Returns:

K: WeightedGraph instance :

the resulting MST

NROI.Voronoi_Labelling(seed)

label = self.Voronoi_Labelling(seed) performs a voronoi labelling of the graph

Parameters:

seed array of shape (nseeds), type (np.int), :

vertices from which the cells are built

Returns:

- labels : array of shape (self.V) the labelling of the vertices

fixme: how is dealt the case of diconnected graph ? :

NROI.Voronoi_diagram(seeds, samples)

Defines the graph as the Voronoi diagram (VD) that links the seeds. The VD is defined using the sample points.

Parameters:

seeds: array of shape (self.V,dim) :

samples: array of shape (nsamples,dim) :

NROI.WeightedDegree(c)

returns the sum of weighted degree of graph self

Parameters:

c (int): side selection :

if c==0 considering left side if c==1 considering right side of the edges

Returns:

wd : array of shape (self.V),

the resulting weighted degree

Note: slow implementation

NROI.adjacency()

Create the adjacency matrix of self

Returns:

A : an ((self.V*self.V),np.double) array

adjacency matrix of the graph

NROI.all_distances(seed=None)

returns all the distances of the graph as a tree

Parameters:

seed=None array of shape(nbseed) with valuesin [0..self.V-1] :

set of vertices from which tehe distances are computed

Returns:

dg: array of shape(nseed, self.V): the resulting distance :

NROI.anti_symmeterize()

self.anti_symmeterize() anti-symmeterize the self , ie produces the graph whose adjacency matrix would be the antisymmetric part of its current adjacency matrix

NROI.append_balls(position, radius)

idem self.as_multiple_balls, but the ROIs are added fixme : should be removed from the class as soon as __add__ is implemented

NROI.append_discrete_ROI(droi)

complete self with a discrete roi only the features that have a common ideas between self and droi are kept

NROI.as_multiple_balls(position, radius)

self.as_multiple_balls(position, radius) Given a set of positions and radii, defines one roi at each (position/radius) couple

Parameters:

position: array of shape (k,3): the set of positions :

radius: array of shape (k): the set of radii :

NROI.cc()

Returns an array of labels corresponding to the different connex components of the graph.

Returns:label: array of shape(self.V), labelling of the vertices :

NROI.check()

Check that the proposed is indeed a graph, i.e. contains no loop

Returns:a boolean b=0 iff there are loops, 1 otherwise :

NROI.check_consistency()

Check the consistency of the input values: affine should be a (4,4) array

all values of xyz should be in the range [0,d1]*[0,d2]*[0,d3] where self.shape = (d1,d2,d3), if shape is defined

NROI.check_features()

check that self.roi_features have the coorect size i.e. f.shape[0]=self.k for f in self.roi_features and that self.discrete features have the correct size i.e. for f in self.roi_features: f is a list of length self.k f[i] is an array with dimensions consistent with xyz

Note: features that are not found consistent are removed

NROI.check_header(image_path)

checks that the image is in the header of self

Parameters:image_path: (string) the path of an image :

NROI.clean(valid)

remove the rois for which valid==0 and update the hierarchy accordingly In case sum(valid)==0, 0 is returned

NROI.cliques()

Extraction of the graphe cliques these are defined using replicator dynamics equations

Returns:

- cliques: array of shape (self.V), type (np.int) :

labelling of the vertices according to the clique they belong to

NROI.complete() makes self a complete graph (i.e. each pair of vertices is an edge)

NROI.complete_roi_feature(fid, values)

completes roi_feature corresponding to fid by appending the values

NROI.compute_children()

self.compute_children() define the children list

Returns:

children: a list of self.V lists, :

that yields the children of each node

NROI.compute_discrete_position()

Create a ‘position’ feature based on self.affine and self.indexes, which is simply an affine transform from self.xyz to the space of self

fixme : if a position is already available it does not need to be computed

the computed position is returned

NROI.converse_edge()

Returns the index of the edge (j,i) for each edge (i,j) Note: a C implementation might be necessary

NROI.copy()

returns a copy of self

NROI.cut_redundancies()

self.cut_redudancies() Remove possibly redundant edges: if an edge (ab) is present twice in the edge matrix, only the first instance in kept. The weights are processed accordingly

Returns:- E(int): the number of edges, self.E :

NROI.define_graph_attributes()

define the edge and weights array

NROI.degrees()

returns the degree of the graph vertices

Returns:

rdegree: array of shape self.V, the right degree :

ldegree: array of shape self.V, the left degree :

NROI.depth_from_leaves()

compute a labelling of the nodes which is 0 for the leaves, 1 for their parents etc and maximal for the roots

Returns:depth: array of shape (self.V): the depth values of the vertices :

NROI.dijkstra(seed=0)

returns all the [graph] geodesic distances starting from seed it is mandatory that the graph weights are non-negative

Parameters:

seed (int, >-1,<self.V) or array of shape(p) :

edge(s) from which the distances are computed

Returns:

dg: array of shape (self.V) , :

the graph distance dg from ant vertex to the nearest seed

NROI.discrete_to_roi_features(fid, method='average')

Compute an ROI-level feature given the discrete features

Parameters:

fid(string) the discrete feature under consideration :

method=’average’ the assessment method :

Results :

—— :

the computed roi-feature is returned :

NROI.eps(X, eps=1.0)

set the graph to be the eps-nearest-neighbours graph of the data

Parameters:

X array of shape (self.V) or (self.V,p) :

where p = dimension of the features data used for eps-neighbours computation

eps=1. (float), the neighborhood width :

Returns:

self.E the number of edges of the resulting graph :

NROI.feature_argmax(fid)

Returns for each roi the index of the discrete element that is the within-ROI for the fid feature this makes sense only if the corresponding feature has dimension 1

NROI.floyd(seed=None)

Compute all the geodesic distances starting from seeds it is mandatory that the graph weights are non-negative

Parameters:

seed= None: array of shape (nbseed), type np.int :

vertex indexes from which the distances are computed if seed==None, then every edge is a seed point

Returns:

dg array of shape (nbseed,self.V) :

the graph distance dg from each seed to any vertex

NROI.from_3d_grid(xyz, k=18)

set the graph to be the topological neighbours graph of the thre-dimensional coordinate set xyz, in the k-connectivity scheme

Parameters:

xyz: array of shape (self.V,3) and type np.int, :

k = 18: the number of neighbours considered. (6,18 or 26) :

Returns:

E(int): the number of edges of self :

NROI.from_adjacency(A)

sets the edges of self according to the adjacency matrix M

Parameters:M: array of shape(sef.V,self.V) :

NROI.from_labelled_image(image_path, labels=None, add=True)

All the voxels of the image that have non-zero-value self.k becomes the number of values of the (discrete) image

Parameters:

image_path: string :

path of a label (discrete valued) image

labels=None : array of shape (nlabels)

the set of image labels that shall be used as ROI definitions By default, all the image labels are used

NROI.get_E()

NROI.get_V()

NROI.get_children(v=-1)

returns the list list of children arrays in all the forest if v==-1 or the children of v otherwise

NROI.get_descendents(v)

returns the nodes that are children of v

NROI.get_edges()

NROI.get_k()

NROI.get_parents()

NROI.get_roi_feature(fid)

return sthe searched feature

NROI.get_size()

return the number of voxels per ROI in one array

NROI.get_vertices()

NROI.get_weights()

NROI.is_connected()

States whether self is connected or not

NROI.isleaf()

returns a bool array of shape(self.V) so that isleaf==1 iff the node is a leaf in the forest (has no kids)

NROI.isroot()

returns a bool array of shape(self.V) so that isleaf==1 iff the node is a root in the forest i.e. : is its own parent

NROI.knn(X, k=1)

E = knn(X,k) set the graph to be the k-nearest-neighbours graph of the data

Parameters:

X array of shape (self.V) or (self.V,p) :

where p = dimension of the features data used for eps-neighbours computation

k=1 : is the number of neighbours considered

Returns:

- self.E (int): the number of edges of the resulting graph :

NROI.leaves_of_a_subtree(ids, custom=False)

tests whether the given nodes within ids represent all the leaves of a certain subtree of self

Parameters:

idds: array of shape (n) that takes values in [0..self.V-1] :

custom == False, boolean :

if custom==true the behavior of the function is more specific - the different connected components are considered as being in a same greater tree - when a node has more than two subbranches, any subset of these children is considered as a subtree

NROI.left_incidence()

Returns:

the left incidence matrix of self :

as a list of lists: i.e. the list[[e.0.0,..,e.0.i(0)],..,[e.V.0,E.V.i(V)]] where e.i.j is the set of edge indexes so that e.i.j[0] = i

NROI.list_of_neighbors()

returns the set of neighbors of self as a list of arrays

NROI.main_cc()

Returns the indexes of the vertices within the main cc

Returns:idx: array of shape (sizeof main cc) :

NROI.make_forest()

output an fff.forest structure to represent the ROI hierarchy

NROI.make_graph()

output an fff.graph structure to represent the ROI hierarchy

NROI.make_image(path=None)

write a int image where the nonzero values are the ROIs

Parameters:

path: string, optional :

the desired image path

Returns:

brifti image instance :

NROI.merge_ascending(valid)

Remove the non-valid items by including them in their parents when it exists methods indicates the way possible features are dealt with. (not implemented yet)

Parameters:valid array of shape(self.k) :

NROI.merge_descending(methods=None)

self.merge_descending() Remove the items with only one son by including them in their son

Parameters:

methods indicates the way possible features are dealt with :

(not implemented yet) :

NROI.merge_simple_branches()

merge the branches of the forest that are the only child of the parent branch into their child

NROI.mst(X)

makes self the MST of the array X

Parameters:

X: an array of shape (self.V,dim) :

p is the feature dimension of X

Returns:

tl (float) the total length of the mst :

NROI.normalize(c=0)

Normalize the graph according to the index c Normalization means that the sum of the edges values that go into or out each vertex must sum to 1

Parameters:

c=0 in {0,1,2}, optional: index that designates the way :

according to which D is normalized c == 0 => for each vertex a, sum{edge[e,0]=a} D[e]=1 c == 1 => for each vertex b, sum{edge[e,1]=b} D[e]=1 c == 2 => symmetric (‘l2’) normalization

NROI.plot_discrete_feature(fid, ax=None)

boxplot the distribution of features within ROIs Note that this assumes 1-d features

Parameters:

fid: string, :

the feature identifier

ax: axis handle, optional :

NROI.plot_roi_feature(fid)

boxplot the feature within the ROI Note that this assumes a 1-d feature

Parameters:

fid string, :

the feature identifier

NROI.propagate_upward(label)

label = self.propagate_upward(label) Assuming that label is a certain positive integer field (i.e. labels) that is defined at the leaves of the tree and can be compared, this propagates these labels to the parents whenever the children nodes have coherent properties otherwise the parent value is unchanged

Parameters:label: array of shape(self.V) : Returns:label: array of shape(self.V) :

NROI.propagate_upward_and(prop)

propagates some binary property in the forest that is defined in the leaves so that prop[parents] = logical_and(prop[children])

Parameters:prop, array of shape(self.V), the input property : Returns:prop, array of shape(self.V), the output property field :

NROI.reduce_to_leaves()

create a new set of rois which are only the leaves of self if there is none (this should not happen), None is returned

NROI.remove_edges(valid)

Removes all the edges for which valid==0

Parameters:valid, an array of shape (self.E) :

NROI.remove_roi_feature(fid)

removes the specified feature

NROI.remove_trivial_edges()

Removes trivial edges, i.e. edges that are (vv)-like self.weights and self.E are corrected accordingly

Returns:- self.E (int): The number of edges :

NROI.reorder(c=0)

Reorder the graph according to the index c

Parameters:

c=0 in {0,1,2}, index that designates the array :

according to which the vectors are jointly reordered c == 0 => reordering makes edges[:,0] increasing,

and edges[:,1] increasing for edges[:,0] fixed

c == 1 => reordering makes edges[:,1] increasing,

and edges[:,0] increasing for edges[:,1] fixed

c == 2 => reordering makes weights increasing

NROI.reorder_from_leaves_to_roots()

reorder the tree so that the leaves come first then their parents and so on, and the roots are last the permutation necessary to apply to all vertex-based information

Returns:

order: array of shape(self.V) :

the order of the old vertices in the reordered graph

NROI.right_incidence()

Returns:

the right incidence matrix of self :

as a list of lists: i.e. the list[[e.0.0,..,e.0.i(0)],..,[e.V.0,E.V.i(V)]] where e.i.j is the set of edge indexes so that e.i.j[1] = i

NROI.rooted_subtree(k)

l = self.subtree(k) returns an array of the nodes included in the subtree rooted in k

Parameters:k (int): the vertex from which the subtree is searched : Returns:idx : array of shape>=1 the index of the nodes beneath k

NROI.set_discrete_feature(fid, data)

Parameters:

fid (string): feature identifier :

data: list of self.k arrays with shape(nk,p),with p>0 :

nk = self.xyz[k].shape[0] (number of elements in ROI k) this function simply stores data

NROI.set_discrete_feature_from_image(fid, image_path=None, image=None)

extract some discrete information from an image

Parameters:

fid: string, feature id :

image_path, string, optional :

input image path

image, brfiti image path, :

input image

Note that either image_path or image has to be provided :

NROI.set_discrete_feature_from_index(fid, data)

Assuming that self.discrete_feature[‘index’] exists this extracts the values from data corresponding to the index and sets these are self.discrete_feature[fid]

Parameters:

fid (string): feature id :

data: array of shape(nbitem,k) where nbitem is supposed :

to be greater than any value in self.discrete_feature[‘index’]

NROI.set_edges(edges)

sets self.edges=edges if 1. edges has a correct size 2. edges take values in [1..V]

NROI.set_euclidian(X)

Compute the weights of the graph as the distances between the corresponding rows of X, which represents an embdedding of self

Parameters:

X array of shape (self.V, edim), :

the coordinate matrix of the embedding

NROI.set_gaussian(X, sigma=0)

Compute the weights of the graph as a gaussian function of the dinstance between the corresponding rows of X, which represents an embdedding of self

Parameters:

X array of shape (self.V,dim) :

the coordinate matrix of the embedding

sigma=0, float : the parameter of the gaussian function

NROI.set_roi_feature(fid, data)

this function simply stores data

Parameters:

fid (string): feature identifier, e.g. :

data: array of shape(self.k,p),with p>0 :

NROI.set_roi_feature_from_image(fid, image_path, method='average')

extract some roi-related information from an image

Parameters:

fid: feature id :

image_path(string): path of the feature-defining image :

method=’average’ (string) : take the roi feature as

the average feature over the ROI

NROI.set_weights(weights)

Parameters:weights : an array of shape(self.V), edges weights

NROI.set_xyz(xyz)

set manually the values of xyz xyz is a list of arrays that contains the coordinates of all ROIs voxels

NROI.show(X=None, ax=None)

a = self.show(X=None) plots the current graph in 2D

Parameters:

X=None, array of shape (self.V,2) :

a set of coordinates that can be used to embed the vertices in 2D. if X.shape[1]>2, a svd reduces X for display By default, the graph is presented on a circle

ax: ax handle, optional :

Returns:

ax: axis handle :

NROI.skeleton()

returns a MST that based on self.weights Note: self must be connected

NROI.subforest(valid)

creates a subforest with the vertices for which valid>0 and with the correponding set of edges the children of deleted vertices become their own parent

Parameters:valid: array of shape (self.V) : Returns:a new forest instance :

NROI.subgraph(valid)

Creates a subgraph with the vertices for which valid>0 and with the correponding set of edges

Parameters:valid array of shape (self.V): nonzero for vertices to be retained : Returns:G WeightedGraph instance, the desired subgraph of self :

NROI.symmeterize()

symmeterize the graphself , ie produces the graph whose adjacency matrix would be the symmetric part of its current adjacency matrix

NROI.to_neighb()

converts the graph to a neighboring system The neighboring system is nothing but a (sparser) representation of the edge matrix

Returns:

ci, ne, we: arrays of shape (self.V+1), (self.E), (self.E) :

such that self.edges, self.weights is coded such that: for j in [ci[a] ci[a+1][, there exists en edge e so that (edge[e,0]=a,edge[e,1]=ne[j],self.weights[e] = we[j])

NROI.tree_depth()

return the maximal depth of any node in the tree

Functions

nipy.neurospin.spatial_models.hroi.NROI_from_field(Field, affine, shape, xyz, refdim=0, th=-inf, smin=0)

Instantiate an NROI object from a given Field and a referntial (affine, shape)

Parameters:

Field : nipy.neurospin.graph.field.Field instance

in which the nested structure is extracted It is meant to be a the topological representation of a masked image or a mesh

affine=np.eye(4), array of shape(4,4) :

coordinate-defining affine transformation

shape=None, tuple of length 3 defining the size of the grid :

implicit to the discrete ROI definition

xyz: array of shape (Field.V, 3) that represents grid coordinates :

of the object

th is a threshold so that only values above th are considered :

by default, th = -infty (numpy)

smin is the minimum size (in number of nodes) of the blobs to :

keep.

nipy.neurospin.spatial_models.hroi.NROI_from_watershed(Field, affine, shape, xyz, refdim=0, th=-inf)

Instantiate an NROI object from a given Field and a referential

Parameters:

Field nipy.neurospin.graph.field.Field instance :

in which the nested structure is extracted It is meant to be a the topological representation of a masked image or a mesh

affine=np.eye(4), array of shape(4,4)

coordinate-defining affine transformation

shape=None, tuple of length 3 defining the size of the grid

implicit to the discrete ROI definition

xyz: array of shape (Field.V,3) that represents grid coordinates

of the object

refdim=0: dimension fo the Field to consider (when multi-dimensional) th is a threshold so that only values above th are considered

by default, th = -infty (numpy)