The aim of this paper is to develop accurate and reliable methods for automated detection of the edges of the lung by a knowledge-based approach. First, the system initializes the ROI(Region Of Interest) using ‘unseeded region growing’ algorithm. Then IPE(Image Processing Engine) generates candidates within the ROI. The candidates are matched to an anatomical model of the lung boundary using parametric features. A modular system architecture was developed which incorporates the model, image processing routines, an inference engine and a blackboard.
In postero_anterior(PA) chest images, all edges (costal, mediastinal, apex, and hemidiaphragm) provide useful information on the location, shape, and size of the lung fields. From this information CAD(Computer-Aided Diagnosis) systems can automatically detect various abnormalities such as interstitial disease, pneumothorax, cardiomegaly and pulmonary nodules.
The aim of this paper is to develop accurate and reliable methods for automated detection of the edges of the lung by a knowledge-based approach.
In a knowledge-based approach there is a need for segmentation algorithms, usually a number of them, to interact with the knowledge base. Many computer vision systems, both medical and non-medical, have made use of the blackboard approach to communication and control between the different system components ( "knowledge sources"), that contribute to the image interpretation. The blackboard is a data structure that stores the current solution state, and knowledge sources may read from, and write to, the blackboard in an "opportunistic" manner (Figure 1). Knowledge Space keeps the Modality Knowledge, which specifies what anatomy is expected to be recognisable in a given type of image, the achievable anatomical model and the temporal anatomical model. Image Space stores all images. They can be organised into a tree structure: the original image is the root of the tree
and all derived images are linked as children to their parent images. Blackboard consists of three boards, which are the model, the image and the working board. All models and images are posted to blackboard and the working board contains hypotheses and partial and final mapping results.
For medical image processing by a computer, the image is typically segmented and then interpreted. Generally, the mechanism includes three stages which are based on three different technologies . The first stage is image processing for extraction primitives such as points, lines or rejoins. These primitives are initial candidates of the boundary of the lung. The following image-processing techniques have been employed.
Image segmentation can be accomplished by having an expert operator identify regions of interest in an image manually. Isolating irregularly shaped regions can be done using a mouse, light pen or track ball. Such techniques allow an expert user to bring all of his domain knowledge to bear. However, the process is
laborious and subject to inter- and intra- operator variation that may not be acceptable.
Pixel-based (low-level) algorithms rely solely on pixel intensities (grey0levels) to segment image structures. Some systems, based on signal processing techniques, have proved quite successful in areas such as automatic identification of lung nodules and mammographic microcalcifications. Anatomical and pathological knowledge is often incorporated, largely at an implicit level, during the design process to tailor image processing routines to a particular application. Therefore the methods are not readily generalisable to other medical imaging applications.
Domain knowledge is required to distinguish organs with similar imaging characteristics, (e.g. X-ray attenuation), which cannot be distinguished by pixel intensity values alone. Expert knowledge is used to derive
Figure 1. System architecture and representation
constraints on features such as, the contrast, size and circularity of nodules to distinguish them from end-on vessels, rib-vessel crossings and rib-rib crossings.
The second stage is the quantification of image features such as the size, contrast, and shape of the candidates.
The third stage is data processing for distinction between normal and abnormal patterns, based on the features obtained.
In this paper we discuss the first two stages of image processing and quantification.
The database used for this study included 19 PosteroAnterior(PA) 14”x17” chest radiographs, selected in the Department of Radiology, St Vincents Hospital. The results determined by our system will be confirmed by experienced radiologists. The digital images are obtained by digitizing the chest radiographs with a Kodak Lumiscan Film Digitiser. The resolution of our digital images is 0.175mm with matrix size of 2048*2487. The gray scale of the images is 3601 gray levels(about 12bits).
For each anatomical structure is identified by its name, shape information, structural relationships to other anatomy and imaging characteristics. The model focuses on the lung boundaries: the domes of the diaphragm, mediastinal (and cardiac) silhouette, lung apices and costal margins (bounded by the rib cage). See Figure 2.
In our system, anatomical knowledge is stored in a declarative model. For each anatomical structure, parametric shape and relational attributes are encapsulated
in a frame. The frames have a predefined set of "slots" corresponding to the attributes, in which parameter values are stored. Relationships between anatomical structures are represented by a hierarchical structure. For example, when the lungs are considered together they are viewed as a parent, and a single lung is viewed as a child of the parent lung. Sibling nodes, that is the relationship between left lung and right lung, are in a semantic network(Figure 3).
Figure 2. Edges included in the lung boundary model
Figure 3. The model of lung
4.1 Overall view of our scheme
First, the system initializes the ROI(Region Of Interest) using "unseeded region growing" algorithm. Then IPE(Image Processing Engine) generates candidates by applying the "canny edge detection" algorithm within the
ROI. IE(Inference Engine) chooses the best candidates according to the knowledge base. Next is the quantification
Figure 4. Overview of system operation
of image features such as the size, contrast, and shape of the candidates selected by IE.
IE validates the candidates to accept them as a boundary of the lung. If the validation fails, the blackboard calls IPE to modify the initial ROI. Then, the candidates are generated by IPE again and IE repeats its work until the validation succeeds. Figure 4 shows the overview of the system operation.
The initialization of ROI
An 'Unseed Region Growing' algorithm(Figure 6) was recently developed by Jin at University of Sydney . It gives very rich information about the lung. In this study this algorithm was used to locate the ROI. For example, when locating the left hemidiaphragm, its position in the digitized chest radiograph varies, being at the bottom of the image or even at the top of image.
Therefore, if the system has a fixed knowledge for the position of the diaphragm such as position(0.4, 1.0, 0.3, 1.0), it is difficult to locate the hemidiaphragm as shown in Figure 5. Even the system uses edge gradient analysis methods to detect the diaphragm edges, it is more difficult, and often inaccurate because of the presence of complicated patterns of stomach gas structures and the effects of cardiac edges around the left hemidiaphragm area. The stomach gas patterns are irregular in shape and usually are located close to the left hemidiaphragm edges. Furthermore, the optical densities of stomach gas patterns are similar to those of the lung areas. From 'Unseeded Region Growing' algorithm, the system locates the rough boundary of the lung and system initializes the ROI along the boundary.
Figure 5. The position of the left hemidiaphragm
4.3 Selection of the best candidates
Canny edge detection is performed to extract line primitives from 2-D images. Typically the expected
anatomical structures do not produce a single, continuous edge. The IPE generates candidates by linking different combinations of edge fragments, constrained using knowledge of the expected length and orientation  with standard deviations, = 3, 5, 7, 9, 15. An outline of the algorithm is as follows:
calculate edge points, with their associated gradient magnitude and phase(direction), eg. using Canny or Log
apply magnitude and phase constraints, retaining only those points which satisfy the constrains
form edge fragments from continuous sets of points
subdivide(split) edge fragments at points of high curvature
calculate all possible linkages of edge fragments to form candidates a linkage can occur if the end points of the fragments are close enough, and the angle between them is within the orientation constraint range.
discard all candidates which do not satisfy the length constraints
The best candidate(Figure 7, 8, 9), for matching to a frame is selected on the basis of confidence scores. For each feature associated with a candidate, a confidence is calculated which indicates how well the candidate satisfies the constraint on that feature. There are four issues to be
explored in computing a confidence score for a candidate
generating confidence scores for individual constraints
combining these scores into an overall confidence for the candidate
selecting the best candidate using the confidence scores, and
dealing with the case where no suitable candidates can be found
It is possible to define numerous features based on some mathematical formula but these may not be easily understood by the human observer. However, it is generally useful to define for the validation of the lung candidates, since the lung model in the knowledge base consists of numerical parameters.
Once the system selects the best candidate as a boundary of the lung, the system analyses it to check whether the edges are acceptable. The system checks the position, the gray level, the strength of the edges, length and orientation. For instance, if the position of the left hemidiaphragm is too high, the blackboard communicates with IPE to determine if there are other candidates at the lower position than the current position. If there are no such candidates, the blackboard accepts the best candidate as a left hemidiaphragm and sends the data to the data processing. The data processing engine(DPE) recognizes the diaphragm is too high and it reports to blackboard that the left hemidiaphragm is not normal. At this stage of our research the DPE has not been investigated. If there are possible candidates the blackboard reposition the ROI and repeat from the matching to the validation steps until the best candidate is accepted as a left diaphragm.
Figure 6. Unseeded Region Growing algorithm (threshhod=50)
We are still refining this system, so there are no conclusive findings at this stage. Current work involves manually conducting the 'Initialization of ROI' and 'Validation' steps.
Results so far are dependent on the constraints, which include length, orientation, gray level and position in the knowledge base because each chest xray image has individual properties.
Therefore it would be worthwhile to define the features from the input chest-xray images to update the knowledge base.
Figure 7. (diaphragm) : 3.0, (apex) : 3.0, (costal) : 7.0, (mediastinal) : 9.0, position of the diaphragm (x1=0.5, x2=1.0, y1=0.3, y2=1.0), join distance (mediastinal:20, costal:50, apex:10, diaphragm:10). The upper image shows the candidates of the lung edges and the lower image shows the best candidate.
Figure 8. (diaphragm) : 3.0, (apex) : 3.0, (costal) : 7.0, (mediastinal) : 9.0, position of the diaphragm (x1=0.5, x2=1.0, y1=0.5, y2=1.0), ), join distance (mediastinal:50, costal:250, apex:10, diaphragm:10). The upper image shows the candidates of the lung edges and the lower image shows the best candidate.
Figure 9. (diaphragm) : 5.0, (apex) : 5.0, (costal) : 15.0, (mediastinal) : 15.0, position of the diaphragm (x1=0.5, x2=1.0, y1=0.5, y2=1.0), ), join distance (mediastinal:50, costal:250, apex:10, diaphragm:10). The upper image shows the candidates of the lung edges and the lower image shows the best candidate.
Matthew S.Brown, Laurence S. Wilson, Bruce D Doust, Robert W. Gill, Changming Sun, Knowledge-based method for segmentation and analysis of lung boundaries in chest X-ray images, Coumputerized Medical Imaging and Graphics, 1998, pp463-477
Xin-Wei Xu and Kunoi Doi, Image feature analysis for computer-aided diagnosis: Detection right and left hemidiaphragm edges and delineation of lung field chest radiographs, Medical Physics, 1996, vol.l23(9), pp1613-1624
Hongyi Li, Rudi Dekerck, Bernard De Cuyper, A. Hermanus, Edgard Nyssen, and Jan Cornelis, Object Recognition in Brain CT-Scans: Knoweledge-Based Fusion of Data From Multiple Feature Extractors, IEEE Transactions on medical imaging, 1995, Vol.14. No.2, pp212-229
Kunio Doi, Hever MacMahon, Shigehiko Katsuragawa, Robert M. Nishicawa, Computer-aided diagnosis in ragiology: potential and pitfalls, European journal of Radiology, 1999, pp98-109
Buckley JJ, siler W, Tucker D. , A fuzzy expert system. Fuzzy Sets and Systems v20, pp1-16
Matthew Brown, Medical Image Understanding, PhD thesis, 1996, UNSW
Kunio Doi, Takeshi Kobayashi, Heber MacMahon, and Maryellen L. Development of an improved CAD scheme for automated detection of lung nodules in digital chest images, Medical Physics, 24(9), September 1997 p1395-1403
Nii HP. Blackboard systems: the blackboard model of problem solving and the evolution of blackboard architectures. In: The AI Magazine, 1986:38-53
Minsky, M. A framework for representing knowledge. In The Psychology of Computer vision. Ed. P. Winston. Pp. 211-277. McGraw-Hill. New York
Tatjana Zrimec, Claude Sammut, A Medical Inage-Understanding System, Engineering Application Intelligent. Vol. 10 No. 1 pp31-39, 1997
Felson Benjamin, Weinstein Aaron, and Spitz Harold, Principles of Chest Roentgenology, Saunders company, 1965
Derich Rachid, Fast Algorithms for low-level vision, IEEE transactions on pattern analysis and machine interlligence, vol 2 , no. 1, January 1990
M. Kass, A. Witkin, and D. Terzopoulos, “Snakes: Active contour models”, International Journal of Computer Vision, 1988, 321-331
Eli Saber and A. Murat Tecalp, “Region-Based Shape Matching for Automatic Image Annotation and Query-by-Example
R. H. Bartels, J. C. Beatty, and B. A. Barsky, An Introduction to Splines for Use in Computer Graphics and Geometric Modelling, Morgan Kaufmann, San Mateo, CA, 1987
S. Marshall, Review of shape coding techiques, Image Vision Comput. 7, 1989, pp281-294
W.E.L.Grimson, Object recognition by computer: The role of geometric constraints, MIT Press, Cambridge, MA, 1990.