Formal extraction of biomedical objects by subgraph matching in attributed hierarchical region adjacency graphs

Extraction of objects from biomedical images is the fundamental task for many high level applications in medical image processing such as cytometry or diagnostic decision support. Therefore, a formal specification of sought objects is required along with an extraction procedure. On the basis of a hierarchical image decomposition objects are described by image regions of characteristic shape, texture, and visual context. For example, a cell consists of a circular core, a surrounding body containing organelles, which is in turn surrounded by the nutrition agent, and other cells. This is modeled by hierarchical graph representation of the region topology as nodes and the region properties as node attributes. In a hierarchical region representation, an object is described by subregions which again may contain subregions, thus object extraction becomes the matching of the respective region nodes. Obviously, graph matching is a NP-complete problem and therefore, it requires heuristics to become computable. This even holds for subtree matching. We propose a new approach which makes strongly use of the inclusion property of regions in a hierarchical image decomposition along with the visually descriptive attributes. The algorithm iterates a top-down bottom-up sequence over the region hierarchy to restrict the search space. Hence at each step, a layer of tree-node attributes must be compared to the attributes of the sought objects root node description. The bottom-up analysis is only invoked for the subtree depending on those nodes. Thus, each node is visited according to the topology of its visual occurrence in an image.