| |
ISSN 1320-0682 | ||
| Volume 03 | April 1996 | ||
Christopher Choi, Andrew Jennings and John Hulskamp
Email: chris.choi@cse.rmit.edu.au; ajennings@rmit.edu.au; jph@rmit.edu.au
Typically, segmentation methods divide into global methods [11] which are applied to the whole image, including morphological methods [1] and local methods [3] which rely entirely on local properties of the image to determine segmentation methods. Typical of the local methods is the SNAKE method [8], [6] which use local contour-following algorithms to segment the specific regions of a target image. Recently, Chiou and Hwang have described a learning approach to the snake algorithm [2].
It is possible that one of the major difficulties of automatic diagnosis [5], [10] is this obstacle of segmentation of occluded or difficult images. We contend that it is very difficult to construct a universal method that takes no account of context or local characteristics of the image, and that instead, it is necessary to incorporate local information as well as global heuristic information to deal with these cases.
There is a great deal of ambiguity in the segmentation process. Many existing systems attempt to use a set of global constraints combined with heuristic rules to further refine the regions. Although this may be successful in a small number of cases, there are many advantages to a learned approach to labelling. We aim to construct a system that can be presented with a range of images to be segmented, together with a segmentation criteria. With presentation of a number of training images, the labelling algorithm can then be applied to a range of similar images. This is to be preferred to systems that require extensive tuning and adjustment to successfully segment.
Figure 1: ALife Region labelling module
Figure 2: Image Segmenter System
Our system consists of a Mathematical Morphology module (MM module), an ALife Region Labelling module (ARLM) and a Snake (Active Contour) module. The MM module provides us with watershed-transformed [9] images from target images. They are then applied to the ARLM in order to provide local information of the cell image which is, in this case, an external energy function to the Snake module (see Figure 1). However, the scope of this paper is limited to the Mathematical Morphology and the ALife Region Labelling Module (see Figure 2).
An Image Segmentation is the partition of an image into a set of non-overlapping regions whose union is the entire image. The purpose of image segmentation is to decompose the image into parts that are meaningful with respect to a particular application. Generally, image segmentation systems follow the rules below.
Mathematical Morphology is an image-processing technique with its roots in the analysis of the properties of materials and material textures. It provides a set of powerful tools for texture analysis and has been used in a number of image-processing applications since its development in the late 1960s. As a nonlinear branch of image and signal processing, mathematical morphology represents a dramatic break with classical linear processing and facilitates the application of various mathematical disciplines to the processing and analysis of images. These areas include medical image segmentation, nonlinear statistics, logic, geometry, geometrical probability, topology and various algebraic systems such as lattice and group theories. While these disciplines have been used in the classical image-processing techniques, they appear more naturally within the context of mathematical morphology and are central to its development and application. Originally developed by Matheron, (1988) [7], there has been a great expansion of interest in mathematical morphology over the past few years. As a result, a number of productive research avenues ranging from noise analysis to image classification are currently being explored. Although originally developed over binary images, morphological paradigms are being extended into various domains even beyond images such as graphs and symmetry groups.
One of the most useful methods among the mathematical morphology algorithms is a watershed transform. The idea of using the watershed method for image segmentation is that, the watershed of the surface tends to follow the high ground of the original image in terms of the intensity level. Therefore, finding the watershed of the magnitude of the gradient of an image ensures these lines will follow the edges (or regions of high ground) in the image. This achieves a useful result for image segmentation. The watershed of a surface of the image has several useful properties [1]:
This last property plays an important role in our approach.
ALife (Artificial Life) is the name given to a new discipline that investigates the scientific, engineering, philosophical and social issues involved in our rapidly increasing technological ability to synthesise life-like behaviour from scratch in computers, machines, molecules and other alternative media. By extending the horizons of empirical research in biology beyond the territory currently circumscribed by life-as-we-know-it, the study of Artificial Life gives us access to the domain of life-as-it-could-be, and it is within this vastly larger domain that we must found general theories of biology and in which we will discover practical and useful applications of biology in our engineering endeavours [4].
The image set we have used for this paper is the reactive (non-neoplastic) Mesothelial cells (see Figure 3). Due to the inherent characteristics of target images, a 5x5 median filter is applied as a pre-processing step in order to reduce noise level of the background image (see Figure 4).
Figure 3: A typical cell image characteristics
Figure 4: 5x5 Median Filtered Image
Many features impact on the decision to label regions in our approach. One being the fuzziness of its boundaries, which is due to the fact that the original cell image intensity tends to fade toward its boundary. Secondly, a texture of the cell images is normally not uniform, therefore the simple thresholding-type region-labelling methods would not work for this type of image. It is observed that the watershed-transformed images show the particular pattern along the cell boundary.
Watershed Transform and Graph Extraction
The Mathematical Morphology module uses a median-filtered image as an input and produces a negative morphological gradient as an output image. This image is then applied to the watershed transform algorithm in order to produce a watershed-transformed image (see Figure 5). Each watershed basin can be identified with its xy co-ordinates and its gray scale level. The idea of using ALife methods for assisting region labelling is to utilise these xy co-ordinates and its gray scale levels.
Figure 5: Watershed Transformed Image
Next, this image is applied to the graph extraction module to extract graph-like information which contains grey scale level xy co-ordinates of each watershed basin. This extracted information of greyscale levels and xy co-ordinates are applied to the ALife Labelling Module to obtain the labelled graph. Finally, the labelled graph information is used to obtain the correct labelled image.
At the completion of the morphological analysis, several labelling problems have to be resolved. In our approach, fuzziness of the cell boundary plays a major role in labelling the target image correctly; especially, the results of applying the Mathematical Morphology module greatly depended upon a reasonable size and density of the Fuzzy Boundary Cell (FBC) feature from the watershed algorithm process.
The concept of a fuzzy boundary cell is confirmed through watershed algorithms. The results showed the large number of similar sized watershed cells (see Figure 6) along the cell image boundary, therefore defining initial cell boundary. The size variation of the fuzzy boundary cell at a normal boundary segment and the occluded boundary segment could be another useful feature to indicate the difference between them. Thresholding prior to using the watershed algorithm reduces inherent low level noise at the background. It also results in a larger fuzzy boundary cell size. Therefore, increasing the possibility of successful labelling at the Labelling module level.
Figure 6: Local Minima from Watershed Transform
The ALife approach allows consideration of a large number of possible feature selections and combinations. ALife region labelling could be described as the construction of a large number of artificial creatures that follow a trajectory across the image that is part of their initial design. These creatures first attempt to identify which segment of the fuzzy boundary (watershed basin) belongs to which region.
The ALife Region Labelling Module (ARLM) generates creatures and a memory pool according to information from the mathematical morphology module. Next it separates this information into a two domains space, which are grey scale and xy co-ordinate domains.
In the grey scale domain, it generates a number of local domains for creatures to move around between the minimum and maximum values of the watershed basin level; that is, if the input image to the ARLM has a grey scale level difference of 90, then it produces 90 domains. For each domain, it generates creatures at the location of within-the-domain-range watershed basins; that is, if the domain range is between 50 to 58, then ARLM generates creatures at the location of watershed basins which have the same range of the grey scale level. Each creature's movement is limited to their domain and has a unique identification number used in marking a watershed basin as a candidate.
In the xy co-ordinate domain, the identification of the candidate watershed basin is achieved through comparing the watershed level difference between the current location (watershed basin) of a creature and the surrounding watershed basin neighbours. If it is a smaller than predefined difference, then the creature marks the current watershed basin and its neighbour as candidates for labelling with its identification number and proceeds to the next group of watershed basins. Once a creature reaches the watershed basin which has been marked by another creature's identification number, it updates the information of the candidate watershed basins along its path in the generation memory pool (see Figure 7).
Figure 7: Algorithm of ALife Region Labelling
In particular, the predefined difference value for that range is compared to that of other domain ranges. As a result of this merging of multiple watershed basins, the number of watershed basins in each domain range is reduced. Therefore, the whole number of watershed basins in the image is reduced by creating the new set of watershed basins. The size of the merged watershed basins are measured, and the merged watershed cells form the new watershed basin cell.
The performance of the each creature in each grey scale range domain is evaluated in terms of the size of the newly formed watershed basin; that is, the size of them is sorted and creatures with the difference level in the higher 50% in the sorted list are allowed to pass their difference level to the next generation creatures.
At the beginning of the next generation, the grey scale domain range is recalculated according to the previous results; and the previous procedure is applied repetitively until the size of the newly formed watershed basin is larger than the largest object in the binary thresholding from the mathematical morphology module, or the number of generations reaches the predetermined maximum value.
A preliminary result of the proposed methods is obtained. The objective of further study is to identify a group of similar scaled watershed cells or watershed basins along a real cell boundary by "learning" the correlation factor and the difference between the group of watershed basins at the normal cell boundary segment and the occluded boundary segment. This information is remembered as an initial learning set forming the resource pool. During the second pass, the boundary information is used to mark the normal boundary and the occluded boundary.
Learning To Segment using Fuzzy Boundary Cell Features
This document was generated using the LaTeX2HTML translator Version 96.1 (Feb 5, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html csc96f.
The translation was initiated by Pam Milliken on Tue Jan 21 15:10:24 EST 1997