IntroductionExtended Graph-Shifts The Hierarchical Graph Structure The Energy Models Extended Graph-Shifts Detection of Pathological Brain Structures Segmenting Tumors Detecting MS Lesions ConclusionDetection and Segmentation of PathologicalStructures by the Extended Graph-Shifts AlgorithmJason J. CorsoCenter for Computational Biology, Laboratory of NeuroimagingUniversity of California at Los AngelesLos Angeles, CA 90095Alan YuilleDepartment of StatisticsUniversity of California at Los AngelesLos Angeles, CA [email protected] L. SicotteDepartment of NeurologyUniversity of California at Los AngelesLos Angeles, CA 90095Arthur TogaCenter for Computational Biology, Laboratory of NeuroimagingUniversity of California at Los AngelesLos Angeles, CA 90095To appear in Proceedings of Medical Image Computing and Computer Aided Intervention(MICCAI). 29 Oct - 2 Nov. 2007.1Detection and Segmentation of Pathological Structuresby the Extended Graph-Shifts AlgorithmJason J. Corso1, Alan Yuille2, Nancy L. Sicotte3, and Arthur Toga11Center for Computational Biology, Laboratory of Neuro Imaging2Department of Statistics3Department of Neurology, Division of Brain MappingUniversity of California, Los Angeles, [email protected]. We propose an extended graph-shifts algorithm for image segmenta-tion and labeling. This algorithm performs energy minimization by manipulatinga dynamic hierarchical representation of the image. It consists of a set of movesoccurring at different levels of the hierarchy where the types of move, and thelevel of the hierarchy, are chosen automatically so as to maximally decrease theenergy. Extended graph-shifts can be applied to a broad range of problems inmedical imaging. In this paper, we apply extended graph-shifts to the detectionof pathological brain structures: (i) segmentation of brain tumors, and (ii) de-tection of multiple sclerosis lesions. The energy terms in these tasks are learnedfrom training data by statistical learning algorithms. We demonstrate accurate re-sults, precision and recall in the order of 93%, and also show that the algorithmis computationally efficient, segmenting a full 3D volume in about one minute.1 IntroductionAutomatic detection of pathological brain structures is a problem of great practicalclinical importance. From the computer vision perspective, the task is to label regionsof an image into pathological and non-pathological components. This is a special caseof the well-known image segmentation problem which has a large literature in computervision [1,2,3] and medical imaging [4,5,6,7,8,9,10]In previous work [11], we developed a hierarchical algorithm called graph-shiftswhich we applied to the task of segmenting sub-cortical structures formulated as energyfunction minimization. The algorithm does energy minimization by iteratively trans-forming the hierarchical graph representation. A big advantage of graph-shifts is thateach iteration can exploit the hierarchical structure and cause a large change in the seg-mentation, thereby giving rapid convergence while avoiding local minima in the energyfunction. The algorithm was limited, however, because it required the number of modellabels to be fixed and the number of model instances to be known. For example, ev-ery brain has a single ventricular system. Nevertheless it was effective for segmentingsub-cortical structures in terms of accuracy and speed. However, such an assumption isnot practical in the case of pathological structures, i.e., the number of multiple sclerosislesions is never known a priori.In this paper, we present a generalization which we call the extended graph-shiftsalgorithm. This is able to dynamically create new model instances and hence deal withN. Ayache, S. Ourselin, A. Maeder (Eds.): MICCAI 2007, Part I, LNCS 4791, pp. 985–993, 2007.c Springer-Verlag Berlin Heidelberg 2007986 J.J. Corso et al.Initial Statem1m1m1m2m2m2m1m1m1m2m2m2DoSpawnShiftm1m1m2m2m2m2m2UpdateGraphFig.1. An intuitive example of the extended graph-shifts algorithm. It shows a spawn shift beingselected (middle panel, double-circle) and then the process of updating the graph hierarchy withthe new root-level model node (right panel).situations where the number of structures in the image is unknown. Hence we can ap-ply extended graph-shifts to the detection of pathological structures. We formulate thesetasks as energy function minimization where statistical learning techniques [12,13] areused to learn the components of the energy functions. As we will show, extended graph-shifts is also a computationally efficient algorithm and yields good results on the detec-tion of brain tumors and multiple sclerosis lesions.The hierarchy is structured as a set of nodes on a series of layers. The nodes at thebottom layer form the image lattice. Each node is constrained to have a single parent.All nodes are assigned a model label which is required to be the same as its parent’slabel. There is a neighborhood structure defined at all layers of the graph. A graph shiftis a transformation of the hierarchical structure and thus, the model labeling on theimage lattice. There are two types of graph-shifts: (1) changing the parent of a node tothe parent of a neighbor with a different model label thus altering the model label of thenode and its descendants, and (2) spawning a new sub-graph from a node to the root-level that creates a new model instance. We refer the reader to [11] for a discussion ofthe first type of shift and restrict the discussion in this paper to the new spawn shift. Thespawn shift is illustrated in figure 1, which shows a node being selected to spawn a newFig.2. Extended graph-shiftscan detect small structures.Left-col.: image and labels.Middle-col.: initialization.Top-right: no spawning(graph-shifts), bottom-right:with spawning.instance of model m2and then the creation of the newroot-level model node. Figure 2 shows a synthetic ex-ample comparing the original graph-shifts with the ex-tended algorithm to demonstrate the importance of thespawn-shift to detect small, detached structures. In thiscase, without spawning, only one of four small structuresis detected properly. The extended graph-shifts algorithmminimizes a global energy function and at each iterationselects the shift that maximally decreases the energy.We apply this algorithm to brain tumor (glioblastomamultiforme, GBM) and multiple sclerosis detection andsegmentation. Due to the clinical importance of automaticdetection for