Shape indexing and its optimization in medical image databases

This thesis focuses on the search of efficient indexing structures for similarity retrievals based on the shape of organs present in medical images.; To abstract and compare shapes, we adopt the elegant shape space theory based on the study of landmarks along object contours. Shape is defined as the equivalence class under similarity transformations, which include rigid motion and uniform scaling. Shape spaces are curved non-Euclidean manifolds, where a few natural metrics measuring shape difference are well defined.; For shape similarity retrieval, we wish to retrieve images with similar shapes to the query shape as fast as possible. A naive brute-force search of all the shapes in the database is feasible using the shape distances in shape spaces. But this exhaustive method scales linearly with the size of database. It is intolerable for large image databases because even assessing the degree of similarity between a database shape and the query shape can be time-consuming. In the thesis, we point out two significant problems for shape indexing and develop our solutions.; First, since shape space is non-Euclidean, traditional coordinate-based indexing trees in vector spaces are not directly applicable to index shape. It appears that metric-based indexing is the only choice. In this thesis, we employ both metric-based and coordinate-based indexing and compare their performance. For coordinate-based shape indexing, we first derive an optimal shape embedding algorithm by re-embedding shapes back into the pre-shape space. Our embedding algorithm minimizes the distortion of the original metric in shape space. Since the embedding shape space is now Euclidean; we can implement a kd tree to index embedded shapes. We also propose weighted shape distances in both the original shape space and the embedding space for the support of complete shape retrieval as well as partial shape retrieval.; Second, retrieval based on indexing structures can give sub-linear computational cost with respect to database size. But the performance of indexing structures deteriorates quickly with the increasing data dimension. We derive a probabilistic formula to evaluate the average computational cost during the retrieval. The formula shows how indexing performance is related with the probability distributions of feature sets and validates the common belief that the intrinsic dimension or the feature distribution is the dominant factor of indexing performance. Based on this formula, we derive a greedy and an optimal adaptation procedure to adapt indexing trees to the feature distribution. Both of the adaptation procedures enhance the retrieval performance of traditional indexing trees in vector spaces as well as metric-based indexing trees. In addition, we find that indexing trees in vector spaces (e.g. kd trees) are usually more efficient than metric-based indexing trees (e.g. clustering trees) for the same data set.; Both coordinate-based and metric-based shape indexing strategies are applied to NHANES II database maintained in the National Library of Medicine at NIH. The comparison of indexing performance shows that the indexing after shape embedding performs consistently better than the straightforward metric-based indexing before and after tree adaptation. In addition, the weighted shape distances measuring the difference between partial shapes have marginally higher correlation with expert-given diagnostic rankings than the original shape distances.