We propose a semi-automated region-based color segmentation algorithm to extract anatomical structures, including soft tissues, in the color anatomy slices of the Visible Human data. Our approach is based on repeatedly dividing an image into regions using Voronoi diagrams and classifying the regions based on experimental classification statistics. The user has an option to reclassify regions in order to improve the final boundary. Our results indicate that the algorithm can find very accurate outlines in less than four iterations and that manual interaction can markedly improve the outline. This approach can be extended to 3D color segmentation.
Over the last decade, rapid advances in computer graphics hardware and software have spawned a variety of new fields. Medical informatics has quickly become one of the most active of these pursuits. Research in medical informatics hinges primarily on integrating computer technology into the practice of medicine to improve all areas of the field from education to diagnosis and treatment. In particular, many applications in the field involve the visualization and manipulation of medical image data, such as MRI, CT, and PET scans, which require sophisticated techniques from computer graphics and other disciplines. In an effort to advance the state of the art in medical imaging and to improve upon the current tools available for medical education and diagnosis, the National Library of Medicine initiated the Visible Human Project [1].
Participants in the project are working toward producing a complete library of high-resolution color 3D representations of an adult male and a female cadaver. The initial phase of the project, carried out by the University of Colorado, involved the generation of true-color 2D slides from cryosections of the male and female cadavers [11]. The slides allow for the representation of details which had been all but invisible in more traditional data sets. However, in order to make the best use of the data, an accurate and efficient method must be developed to identify structures within the individual 2D slices. Outlines of the structures can then be used to extract 3D voxel-based models from the 2D data, and the 3D surface-defined wrappings. These models must not only be accurate enough to allow for labeling of all important anatomical structures, but must also be efficient enough to be usable in interactive applications, such as the virtual anatomy book being developed by the Vesalius Project at Stevens Institute of Technology and Columbia University [7]. Generating outlines for the structures, which falls under the umbrella of image segmentation, stands out as one of the most challenging and vital phases of the project, primarily because the results of all subsequent steps in the process depend on the quality of the initial 2D segmentation.
For many years, work focused on segmenting gray scale images, due primarily to the fact that, until recently, computer systems were not powerful enough to display and manipulate large, full-color data sets. Research focused primarily on two different approaches to the segmentation problem : region-based and edge-based methods. Region-based methods take the basic approach of dividing the image into regions and classifying pixels as inside, outside, or on the boundary of a structure based on its location and the surrounding 2D regions. On the other hand, the edge-based approach classifies pixels using a numerical test for a property such as image gradient or curvature [10]. With the advent of more powerful and easily accessible hardware came a shift in the current of research toward the more widely-applicable and more complex problem of color segmentation. Indeed, the field has finally begun to witness the publication of a sizable body of research in the area of color image segmentation as opposed to gray scale [4,6,8]. Much of the work currently being pursued involves the extension of various gray scale methods to the realm of color images. These efforts represent no mean feat considering that working with color images requires one to address various difficult issues, such as conversions between different color spaces and manipulation of larger volumes of data as opposed to gray scale.
Along this line, we propose a new method of 2D color image segmentation based on previous work in gray scale segmentation. Bertin and Chassery have presented a gray scale region-based segmentation method for microscopic data which makes use of Voronoi diagrams to divide the image into regions [3]. In 2D, a Voronoi diagram is a structure which divides a plane, for a given set of input seed points, into regions called Voronoi regions which each contains all the points closer to its seed point than any other seed point \cite{pr:prep}. The gray scale method involves testing each Voronoi region to determine if it is homogeneous, either inside or outside of the structure, or heterogeneous, i.e. on the boundary of the structure of interest. The boundary regions are further subdivided by adding more seed points and the classification is repeated until all regions are found to be homogeneous. Our innovations include applying the method to more general color images by developing new, efficient methods to visit the regions and by experimentally determining appropriate classification statistics for color data. In particular, since it is all but impossible to differentiate between regions which are exterior to a particular structure and those which are on its boundary in a color anatomical image or other general color data, our algorithm uses classification statistics to identify regions as either interior or exterior. After all regions have been classified, exterior regions adjacent to interior regions are reclassified as boundary regions. The algorithm runs for a user-specified number of iterations or in another unique facet of our approach, the user can interactively reclassify regions in order to improve the results. We also make use of another concept from computational geometry, namely Delaunay triangulation, the dual graph of a Voronoi diagram, to connect the final boundary regions to form an outline.
When applied to the Visible Human Project cryosection slides, our semi-automated system produces highly accurate outlines for the lungs, which have in the past presented difficulties for more traditional approaches. Furthermore, our algorithm achieves these results efficiently with a complexity which is linear in the number of pixels in the test image. Our method also benefits from being able to use the resulting boundary points from one slide as the initial seed points for the next slide, since most anatomical structures do not change in shape a great deal within the 1 mm thickness of a slice. This pipeline approach can serve to improve results over a number of slides. In the following sections, we discuss the details of our algorithm and analyze the results.
In approaching the problem of segmenting color anatomical data, we recognized a need for a new method to supplement the traditional techniques used in segmentation. We propose a region-based algorithm which quickly converges to an accurate boundary and requires minimal user interaction. Our basic approach is to subdivide an image into regions, classify each region as either inside or outside the target structure, and then break up the regions on the boundary between the two classifications into smaller regions and repeat the classification and subdivision on the new set of regions. This process can be repeated as many times as the user wishes, within the bounds of hardware limitations, in order to refine the calculated boundary.
We divide an image into regions by distributing, either manually or automatically, a number of seed points throughout the plane of the image and then generating the Voronoi diagram of these points. Each Voronoi region is a convex polygon which can be efficiently analyzed for various statistics, including the mean color intensities and their variances. After collecting data for a region, we can classify it as interior or exterior with respect to the structure of interest. Of course, the classification criteria vary according to the type of image being analyzed and the particular structure being sought (e.g. a color anatomical image, a general purpose video frame etc.). Hence the statistics collected for the regions will also change. For example we used in our experimental statistics the variance in the saturation value and in the red intensity to classify regions in our experiments to segment a lung in an anatomical image cite [5].
Once the regions have been classified, the algorithm identifies as boundary regions all those exterior regions which share an edge with an interior region. We construct the Delaunay triangulation and select those edges which connect the seed points in the neighboring boundary regions. This defines an approximation of the outline of the processed structure. In order to improve the accuracy of the results, we add a seed point on the midpoint of each edge of every boundary region, recalculate the Voronoi diagram with these new seeds, and repeat the process. Before adding new seed points, though, the user has the option of manually reclassifying some boundary regions as exterior regions in order to prevent the algorithm from focusing on unwanted details and to minimize the inaccuracies introduced by deficiencies in the classification statistics. In addition, the user may stipulate that the algorithm run automatically for a fixed number of iterations and then view the results, or he/she can choose to interact with the data after each step. A pseudocode for the algorithm is described in Figure 1.
Our algorithm benefits, in particular, from its robustness. No limitations are imposed by the design on the nature of the statistics used to classify the Voronoi regions, so the algorithm can accommodate a wide variety of measurements for each region. Flexibility in the specification of classification statistics allows the algorithm to operate on virtually any type of image from full-color anatomical images to video frames. In addition, our algorithm can be easily extended to include considerations such as geometric location in an image in its classification scheme due to the region-based nature of our approach. Such extensions could conceivably improve segmentation results in cases in which the search can be concentrated on only one section of an image.
We obtained a number of interesting results while experimenting with our segmentation system. For example, we found that using different sorts of random distributions, such as Poisson and binomial, for the initial seed points make no appreciable difference in the final results. However, a set of manually distributed seed points with a high concentration of points near the edges of the lung will produce a higher quality outline in less iterations than will a random distribution of the same number of points. Figures 2 and 3 show a comparison of the intermediate steps and the final result of running the program in automatic mode for iterations on random and manual initial distributions, respectively.
In addition, as might be expected, human interaction can
greatly improve the results of the segmentation process. As
shown in Figures 4 and 5, the results of four iterations with
interactive reclassification for regions after each step tend to
display a lower density of regions in difficult to segment areas
than do those of a fully automatic run, since the user can force
the program to ignore certain areas on which it might otherwise
concentrate too much effort.
Clearly, our region-based segmentation technique produces accurate results even without any user interaction. More importantly, though, with only a very small amount of user input, the program can produce a highly accurate representation of the boundary of a lung. This low requirement for user input becomes particularly important in our case when one considers that the lungs appear in over 300 slices in the Visible Human data set. Using our approach the slices can be processed efficiently and accurately.
We have proposed a novel method of color image segmentation using a semi-automated region-based approach, and we have proven its effectiveness by implementing it in a system which generates outlines of lungs in slides from the Visible Human Project. Building on the work of \cite{be:bert}, we extended the original gray scale work to full-color data and developed a variety of improvements and modifications, chief among them being the inclusion of user interaction.
Our experimental results clearly indicate the efficacy of our method and point the way toward a number of future developments. More experiments must be carried out to determine classification statistics for a wider variety of anatomical structures so that a more rigorous mathematical description of such structures can be developed. In this regard, our experiments lead us to believe that saturation values will play an important part in distinguishing between structures. Also, as mentioned earlier, our approach allows for easy extension of classification criteria to include measures of geometric location and other statistics which should be implemented and tested on the anatomical data.
The output from our application has already been used as a foundation for creating 3D representations of the lungs. After further refinement, the program will play an important role in providing data for a 3D anatomical imaging system designed to use the Visible Human Project data to improve upon current techniques in anatomy education. Extension of this method to a 3D region-based color segmentation is possible, if we employ the 3D Voronoi diagram to process the input data in color voxel representation.
[1] Ackerman M.J., ``Fact Sheet: The Visible Human Project'', National Library of Medicine, 1995.
[2] Barber C.B., Dobkin D.P., and Huhdanpaa H., ``The Quickhull Algorithm for Convex hulls'', The Geometry Center, University of Minnesota, 1995.
[3] Bertin E., Parazza F., and Chassery J.M., ``Segmentation and Measurement Based on 3D Voronoi Diagram: Application to Confocal Microscopy'', Computerized Medical Imaging and Graphics, vol.17, pp.175-182.
[4] Celenk M., Smith S.H., ``Gross Segmentation of Color Images of Natural Scenes for Computer Vision Systems'', Applications of Artificial Intelligence III, pp.333-344, 1986.
[5] Gong Y., and Sakauchi M., ``Detection of Regions Matching Specified Chromatic Features'', Computer Vision and Image Understanding, vol.61, no.2, pp.263-269, 1995.
[6] Liu J., and Yang Y., Multiresolution Color Image Segmentation'', IEEE Transactions on Pattern Analysis and Machine Intelligence. vol.16, no.7, pp. 689-700, 1994.
[7] Molholt P., Bean C., Imielinska C., Laino-Pepper L., ``The VESALIUS Project: Creating a Network-Based Anatomy Curriculum'', Technical Report No. 9605, Stevens Institute of technology, April 1996.
[8] Ohta Y.I., Kanade T., and Sakai T., ``Color Information for Region Segmentation'', Computer Graphics and Image Processing, vol.13, pp.222-241, 1980.
[9] Preparata F.P., and Shamos M.I., ``Computational Geometry: An Introduction'', Springer-Verlag, New York, 1985.
[10] Ronfard R., ``Region-Based Strategies for Active Contour Models'', International Journal of Computer Vision, vol.13, no.2, pp. 229-251, 1994.
[11]] Spitzer V., et al.. The Visible Human Male: A Technical Report. J.Am. Medical Informatics Assn., 1995.