neurospin.graph.field

Module: neurospin.graph.field

Inheritance diagram for nipy.neurospin.graph.field:

Field processing (smoothing, morphology) routines. Here, a field is defined as arrays [eA,eB,eD,vF] where. (eA,eB,eC) define a graph and vF a dunction defined on the edges of the graph Author: Bertrand Thirion (INRIA Futurs, Orsay, France), 2004-2006.

Field

class nipy.neurospin.graph.field.Field(V, edges=None, weights=None, field=None)

Bases: nipy.neurospin.graph.graph.WeightedGraph

This is the basic field structure,

which contains the weighted graph structure plus an array of data (the ‘field’)

field is an array of size(n,p)

where n is the number of vertices of the graph and p is the field dimension

Methods

Kruskal
Kruskal_dev
Voronoi_Labelling
Voronoi_diagram
WeightedDegree
adjacency
anti_symmeterize
cc
cliques
closing
complete
constrained_voronoi
converse_edge
copy
custom_watershed
cut_redundancies
degrees
diffusion
dijkstra
dilation
eps
erosion
floyd
from_3d_grid
from_adjacency
geodesic_kmeans
get_E
get_V
get_edges
get_field
get_local_maxima
get_vertices
get_weights
is_connected
knn
left_incidence
list_of_neighbors
local_maxima
main_cc
mst
normalize
opening
print_field
remove_edges
remove_trivial_edges
reorder
right_incidence
set_edges
set_euclidian
set_field
set_gaussian
set_weights
show
skeleton
subfield
subgraph
symmeterize
threshold_bifurcations
to_neighb
ward

__init__(V, edges=None, weights=None, field=None)

Parameters:

V (int >0) the number of vertices of the graph :

edges=None: the edge array of the graph :

weights=None: the asociated weights array :

field=None: the field data itself :

Kruskal()

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

Returns:

K: WeightedGraph instance :

the resulting MST

Kruskal_dev()

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

Returns:

K: WeightedGraph instance :

the resulting MST

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 ? :

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) :

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

adjacency()

Create the adjacency matrix of self

Returns:

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

adjacency matrix of the graph

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

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 :

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

closing(nbiter=1)

Morphological closing of the field data. self.field is changed

Parameters:nbiter=1 : the number of iterations required

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

constrained_voronoi(seed)

performs a voronoi parcellation of the field starting from the input seed

Parameters:

seed: int array of shape(p), the input seeds :

Returns:

label: The resulting labelling of the data :

Fixme : what happens if there are several ccs in the graph ?

converse_edge()

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

copy()

copy function

custom_watershed(refdim=0, th=-inf)

watershed analysis of the field. Note that bassins are found aound each maximum (and not minimum as conventionally)

Parameters:

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

by default, th = -infty (numpy) :

Returns:

idx: array of shape (nbassins) :

indices of the vertices that are local maxima

depth: array of shape (nbassins) :

topological the depth of the bassins depth[idx[i]] = q means that idx[i] is a q-order maximum Note that this is also the diameter of the basins associated with local maxima

major: array of shape (nbassins) :

label of the maximum which dominates each local maximum i.e. it describes the hierarchy of the local maxima

label : array of shape (self.V)

labelling of the vertices according to their bassin

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 :

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 :

diffusion(nbiter=1)

diffusion of a field of data in the weighted graph structure Note that this changes self.field

Parameters:

nbiter=1: the number of iterations required :

(the larger the smoother)

Note : The process is run for all the dimensions of the field

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

dilation(nbiter=1)

Morphological dimlation of the field data. self.field is changed

Parameters:nbiter=1 : the number of iterations required

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 :

erosion(nbiter=1)

self.erosion(nbiter=1) Morphological openeing of the field IMPUT nbiter=1 : the number of iterations required

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

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 :

from_adjacency(A)

sets the edges of self according to the adjacency matrix M

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

geodesic_kmeans(seeds=None, label=None, maxiter=100, eps=0.0001, verbose=0)

Geodesic k-means algorithms: i.e. obtention of clusters that are topologically connected and minimally variable concerning the information of self.field

Parameters:

seeds= None : array of shape (p)

initial indices of the seeds within the field if seeds==None the labels are used as initialization

labels= None array of shape(self.V) initial labels :

it is expected that labels take their values in a certain range (0..lmax) if Labels==None, this is not used if seeds==None and labels==None, an ewxception is raised

maxiter=100, int: maximal number of iterations :

eps=1.e-4, float : :

increase of inertia at which convergence is declared

Returns:

seeds: array of shape (p) the final seeds :

label : array of shape (self.V) the resulting field label

J: inertia value :

get_E()

get_V()

get_edges()

get_field()

get_local_maxima(refdim=0, th=-inf)

Look for the local maxima of one dimension (refdim) of self.field

Parameters:

refdim (int) the field dimension over which the maxima are looked after :

th = -np.infty (float,optional) :

threshold so that only values above th are considered

Returns:

idx: array of shape (nmax) :

indices of the vertices that are local maxima

depth: array of shape (nmax) :

topological depth of the local maxima : depth[idx[i]] = q means that idx[i] is a q-order maximum

get_vertices()

get_weights()

is_connected()

States whether self is connected or not

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 :

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

list_of_neighbors()

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

local_maxima(refdim=0)

Look for all the local maxima of a field

Parameters:

refdim (int) field dimension over which the maxima are looked after :

Returns:

depth: array of shape (nmax) :

a labelling of the vertices such that depth[v] = 0 if v is not a local maximum depth[v] = 1 if v is a first order maximum ... depth[v] = q if v is a q-order maximum

main_cc()

Returns the indexes of the vertices within the main cc

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

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 :

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

opening(nbiter=1)

Morphological opening of the field data. self.field is changed

Parameters:nbiter=1 : the number of iterations required

print_field()

remove_edges(valid)

Removes all the edges for which valid==0

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

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 :

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

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

set_edges(edges)

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

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

set_field(field)

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

set_weights(weights)

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

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 :

skeleton()

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

subfield(valid)

Returns a subfield of self, with only the vertices such that valid >0

Parameters:

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

nonzero for vertices to be retained

Returns:

F: Field instance, :

the desired subfield of self

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 :

symmeterize()

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

threshold_bifurcations(refdim=0, th=-inf)

analysis of the level sets of the field: Bifurcations are defined as changes in the topology in the level sets when the level (threshold) is varied This can been thought of as a kind of Morse analysis

Parameters:

th=-np.infty (float) :

threshold so that only values above th are considered

Returns:

idx: array of shape (nlsets) :

indices of the vertices that are local maxima

height: array of shape (nlsets) :

the depth of the local maxima depth[idx[i]] = q means that idx[i] is a q-order maximum Note that this is also the diameter of the basins associated with local maxima

parents: array of shape (nlsets) :

the label of the maximum which dominates each local maximum i.e. it describes the hierarchy of the local maxima

label: array of shape (self.V) :

a labelling of thevertices according to their bassin

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])

ward(nbcluster)

Ward’s clustering of self

Parameters:

nbcluster: int, :

the number of desired clusters

Returns:

label: array of shape (self.V) :

the resulting field label

J (float): the resulting inertia :