.
Using direct computer simulation of a LEGION network to segment large 2D images and volume datasets is computationally infeasible because it requires numerically integrating a huge number of differential equations. Based on LEGION's computational components, Wang and Terman [24] gave a straightforward algorithmic implementation of LEGION. In this section, we take a functional viewpoint by showing that the network essentially performs connected labelling of image pixels. We construct an image segmentation algorithm that utilizes a region growing technique to group pixels. First, the LEGION network is formulated with a graph representation. Second, we use a set of graph operations that are directly derived from LEGION's computational components to construct a graph representation of the network in its steady limit cycles. This formulation leads to an image segmentation algorithm called Graph-LEGION, or G-LEGION. Our algorithm is functionally equivalent to LEGION with appropriately chosen network parameters. It differs from the Wang and Terman algorithm in our graph formulation, which leads to a more efficient implementation. In the next section, we show results of the image segmentation algorithm when used to segment medical image datasets.
The LEGION network can be represented by an undirected graph G(V, E, L), where V is the set of vertices, E is the set of edges, and L is a set of integer labels assigned to vertices. Given a LEGION network N, the graph G is constructed using the following steps:
.Only the stimulated oscillators from N are represented in G because only these oscillators will participate in oscillatory groups. Edges in G represent synchronization between coupled oscillators. It is easy to see that G contains a collection of components, each of which is a largest connected subgraph (LCS) of G such that a path exists between any two vertices within the subgraph. A path between any two vertices is a traversal of edges and vertices that starts at one of the two vertices and ends at the other. Also note that all vertices within the same component will have the same label assignment, because synchronization is transitive. The graph representing a network in its initial state may have a large number of small components if oscillators have not synchronized yet. A graph representing the network in its steady limit cycles will assign the same label to all vertices in the same component and assign different labels to vertices in different components.
We define graph operations that construct a graph G representing the network in its steady limit cycles. Each operation is directly derived from the four computational components of LEGION in the following way:
Construct a vertex in G for each stimulated oscillator
Add an edge between two vertices if and only their associated oscillators are coupled and synchronous in the steady limit cycles
Assign a unique label to all vertices in the same LCS
Remove all LCS's in G that do not contain any leading vertex
The first two operations construct LCS's by creating all vertices and establishing appropriate edges. Next, each LCS is assigned a unique label. Finally, LCS's with no leading vertices are removed from the graph, where a leading vertex corresponds to a leading oscillator in the LEGION network and will be described in the following two subsections. This graph formulation reflects some desirable properties of LEGION when applied to image segmentation. First, the topology of G corresponds to spatial proximity (a key grouping principle), which ensures that segmented regions will be connected and can represent arbitrarily complex objects. The edge assignments imply that grouping is local, which allows for effective segmentation of objects with a relatively smooth change in pixel intensities locally, but with a large intensity variation over the entire object. The segmentation is order independent because the construction of the LCS is independent of the assignment of edges and vertex labels. The last graph operation implements a noise removal mechanism to prune small noisy fragments as well as large noisy areas, such as sampling artifacts commonly found in sampled medical images.