Graph-Based Shape Analysis for MRI Classification

Graph-Based Shape Analysis for MRI Classification

Seth Long (Washington State University, USA) and Lawrence B. Holder (Washington State University, USA)
Copyright: © 2011 |Pages: 15
DOI: 10.4018/jkdb.2011040102
OnDemand PDF Download:


Searching for correlations between brain structure and attributes of a person’s intellectual state is a process which may be better done by automation than by human labor. Such an automated system would be capable of performing classification based on the discovered correlation, which would be means of testing how accurate the discovered correlation is. The authors have developed a system which generates a graph-based representation of the shape of the third and lateral ventricles based on a structural MRI, and classifies images represented in this manner. The system is evaluated on accuracy at classifying individuals showing cognitive impairment to Alzheimer’s Disease. Classification accuracy is 74.2% when individuals with CDR 0.5 are included as impaired in a balanced dataset of 166 images, and 79.3% accuracy when differentiating individuals with CDR at least 1.0 and healthy individuals in a balanced dataset of 54 images. Finally, the system is used to classify MR images according to level of education, with 77.2% accuracy differentiating highly-educated individuals from those for whom no higher education is listed, in a balanced dataset of 178 images.
Article Preview

Previous Work

Some previous work has been focused on the particular problem of automatic recognition of Alzheimer’s Disease from MRI data. For example, Klöppel et al. (2008) consider each voxel to be a feature in a feature vector, and then use a support vector machine to classify the resulting feature vectors. Cocosco et al. (2003) consider features of the image which are points in the gray matter, white matter, or CSF, and prune the resulting set of features to develop a minimum spanning tree which can be used for classification based on a clustering approach. Cuingnet et al. (2010) discuss and compare 10 different methods using a large dataset from 509 participants. As such, the study of automatic detection of Alzheimer’s Disease is well-studied. In contrast, our study of classification of Alzheimer’s Disease is used to validate a general-purpose classifier, which is then applied to level of education, and will be applied to other measures as well in the future.

Elsayed et al. (2010) have used graph-based shape representation to classify MR images using the 2D shape of the corpus callosum as it appears in a midsaggital section. Images were classified as either from a musician, or a non-musician, with up to 95% accuracy. Shape analysis was done by recursively subdividing the image into 4 quadrants to form a quad-tree, terminating a branch if the area to be subdivided was sufficiently uniform in color. These trees were then classified by a frequent sub-tree classification method.

This paper extends the idea of graph-based shape recognition into 3 dimensions. Previous 3D graph-based shape classification used particular features of an image to form a graph representing what features are contained in the image. For example, Joshi and Chang (1988) use shape features such as edges, etc. to form a graph-based representation of machined objects. Similar methods have also been used in 2D, for example, by Mauro, Diligenti, Gori, and Maggini (2003). To date, we are unaware of any work representing a 3D structure as contained herein, while recognizing the extension from 2D methods such as in Elsayed et al. (2010).

Work has also taken place regarding classifying MR images by means other than graph-based shape recognition. For example, Mitchell et al. (2004) analyze fMRI data by considering each voxel to be a feature in a feature vector. These feature vectors are classified according to what the study participant was thinking when the scan was made. Although Mitchell et al. (2004) were using fMRI data rather than structural MRI, the task is still one of classifying a shape derived from the brain according to particular criteria.

Graph Classification

This present work is partly derived from our previous graph classification techniques described in Long and Holder (2011). In both, graphs are classified by creating a feature vector using frequent substructures. In the previous work, Gaston was used to find subgraphs, which were then used to form a feature vector which was classified using a support vector machine. In this paper, Subdue (Cook & Holder, 2000) is used to find frequent subgraphs, and also a new frequent branch miner which is optimized for fast performance on trees. Classification is again by support vector machine.

Other authors had previously used the idea of graph classification by frequent subgraphs to form a feature vector. For example, Deshpande et al. (2005) used this approach to classify chemical compounds. This technique allows common machine learning algorithms to be applied to graph classification.

Besides using a feature-vector based approach, graphs can also be classified using direct comparison. For example, in Gaertner, Flach, and Wrobel (2003) a support vector machine kernel which accepts graphs as input rather than feature vectors is used to create a support vector machine which operates on graphs directly. This technique can correctly make classifications which feature vector techniques may miss, as in Long and Holder (2011), but computation of the kernel was found to be infeasible in the present work.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 7: 2 Issues (2017): 1 Released, 1 Forthcoming
Volume 6: 2 Issues (2016)
Volume 5: 2 Issues (2015)
Volume 4: 2 Issues (2014)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing