Knowledge-Based Identification of Artery Branches in Cine-Angiograms

1. INTRODUCTION

Visual inspection of coronary arteries in cine-angiograms, cine-film records of radiographic images of beating hearts, has increased its importance to find diseased portions within the arteries and to assess the severity of the coronary diseases. Semi-automatic inspection systems have been proposed for quantitative analysis [I], but they need careful monjtoring a large number of frames in the records and tracing the diseased parts by experts. Also it is a very difficult and time-consuming task for the experts to localize the detected lesions in the arterial structure, because the records consist of sequences of projections of the moving, complex, three-dimensional arterial system from different directions.

We have studied with Professor Abe's group of Medical School of Osaka University to develop an intelligent system which could help medical doctors by finding diseased portions of the arteries in the cine-angiograms and locating them in a model of the arterial system.

Since the arteriograms are much noisy, low contrasted, and time-varying images, the finding of the artery branches and tracking of their precise boundaries are very difficult image processing tasks . An arteries while X-ray 1paque dye is Intermittently !nJec ted through a catheter. The 1mnges are t aken from several directions such as LAO (left anterior oblique projection) or RAO (right anterior oblique projection) to observe the three-dimensional structure of the arteries. The diseased portions, obstructing lesions, are detected as irregular and narrow or completely occluding portions in the vessel s.

The coronary arteries have very complex structures. Fig . l illustrates a simplified diagram of the entire coronary arterial system which is based on representative coronary arteriograms of healthy subjects [7] . Images of the arterial systems, however, show a wide variety of appearances in both shapes and structures . The left coronary artery has II types of branches (the major branches are shown in Fig.!), and some branches vary in their numbers, lengths, sizes, directions, and the locations of their origins. Fig.2 shows two examples of the left arteries of two subject s in a 60 degree LAO view .

Another difficulty in analyzing the arteriograms is that we need to integrate information obtained from views of different . directions, for example, LAO and RAO. This paper deals with only images of LAO views, but even a small amount of

Fig. 1 Diagram of right and left coronary arteries as views in the left anterior oblique projection. The abbreviations of branches of the left coronary artery in this picture are as follows:

LHCA=Jeft main coronary artery

LAD =left anterior descending branch

ex =circumflex

D =diagonal branch

S =septal branch

OH =obtuse marginal branch

PL ·po~terolateral branch

CB =conus branch

change in the direction or the projection sometimes causes significant changes in structures or the images, and the system needs to compare the interpretations of two views in order to obtain a more reliable interpretation. We should also note that there exist tPmporal changes of the arteriograms in the shapes (and sometimes In the structures of Images) in each cardiac cycle.

UNDERSTAND/NO OF CORONARY ARTERIES

An approach to analyze the images of such complex arteries is to utilize a three-dimensional model or the arterial system and Interpret the images as projections of the model . The method; however, needs a very flexible model to cover the systems . the image deal with different different wide varieties or the arterial ~lso it is very difficult to map jata to the model because we the images which were taken from directions by a camera in time courses .

Instead, we study another approach, the utilization of the expert knowledge on appearances of the arteries in each view. The knowledge, as most or the expert knowledge of other fields, is not definitely defined, therefore the system must be flexible in such a way that we can easily transfer the expertise to the knowledge-base, test its validity and effectiveness by a series or experiments, and modify it. The production system which has been widely used in the consultation systems is also suitable for our purpose. We have constructe~ an image understanding system which acquires rules from·experts, analyzes input line images detected in the artriograms to generate hypotheses on the identification or the input segments, and reports the results. The expertise we use include both the heuristics for identifying each arterial branch and procedures for selecting suitable arterial branch to be examined next.

3. IYITEII DEICRIPTION

IY IT Ell INPUT

In order to toncentr~te fundermental problems or understanding the structures or the vessel system in the i·ages, the system analyzes the line i·ages of the arteries obtained from the arteriograms under an assumption that all line segments are round. Each line segement is represented by its starting point. and terminal point (in a 256 by 256 Image array), the mean width or ~he vessel, and the chain-coded segment. Fig.3 shows an example or the ; line image obtained from Fig.2 (a) . We also assume that a user gives the system the direction of ~he image projection and points out the l1ne segment corresponding to the catheter by using a cursor on . a color display.

IYITEII DEI/BN AND KNOWLEDBE REPREIENTATIDN

As mentioned in the previous chapter, we have designed an image understanding system for the anteriograms which is characterized by its flexibility to easily transfer the expert knowledge to its knowledge-base and modify it . We also consider it is very important to provide it with the capability of integrating information obtained from multiple sources. The system needs to compare hypotheses on the arterial structure deduced from each or multiple views and construct ·& model of the arterial system. Utilization of other information than the line images will be also useful to augment the capability of the system . The expert medical doctors effectively use such information for specific decision making . For example, the knowledge that anteriouly located vessels appear to move in a direction opposite to the posteriously located arteries is used to discriminate the anterious descending from the many ventricular branches in a RAO view; otherwise the task is v~ry difficult even for the experts [7] . We have been developing such image processing programs which analyze temporal changes of the arteries in their locations or measure the velocity of blood flow in each branch in the images, and plan to add these programs to the system. Therefore, the system is designed so as to accept information sent from various types of image processing programs .

The main part of our expert system is schematically shown in Fig.4 . It consists of (I) INFERENCE ENGINE, (2) RULES, (3) BLACKBOARD, and (4) INTERACTIVE SYSTEM. An expert gives the system his or her knowledge, rules represented in a si~ple originates from the same vessel as LAD, by examining its shape, origin, and direction relative to the key pattern. Other branches are also detected by evaluating conditions on both their shapes and the relations to the arterial branches detected already.

INTEGRATION Our system uses the same type of reasoning guided by the control rules proposing both a branch to be detected next and a context of identification rules to be used . At present, the system is provided with the expert's procedures for interpreting LAO views.

English-like format, through INTERACTIVE SYSTEM. INFERENCE ENGINE accesses RULES collects necessary data from the user, analyzes the line image data on BLACKBOARD, and ~enerates hypotheses on the structure of the artery in the given image. The results are then shown on a color display .

BLACKBOARD is a data structure for collecting line image data obtained from different views of the coronary arteries and hypothesis trees generated for the views, which are then used to construct a model of the arterial system. It is designed so as to accept image data manipulated by the image processing programs which will be added in future.

The expert knowledge used in this system is a collection of modular type production rules as used in MYCIN and other consultation systems. In most cases, rules for identifying each arterial branch are independently used from those for the other branches and, therefore, we organize the rules in a context tree shown in Fig.5 .

The rules are classified into three types: (I) control rules to specify a rule or a context of rules to be selected next, (2) identification rules to give conditions for reasoning whether a sequence of segments is a specified arterial branch, and (3) judgment rules to give conditions for judging which (or which part) of mutually contradicting hypotheses Is more probable.

XNDWLEDOE FOR INTERPRET/NO ARTERIDORAMS

The experts seem to have heuristics tor interpreting the arteriograms. They first search the input images for large blood vessels which are easily and reliably detectable . For example, the left arterior descending coronary art 0ry (LAD) Is the vessel with the most constant origin, course, and distribution, and it Is used as a key pattern for the interpretation . If LAD is found, the experts search for the next large vessel, tor example ex (circumflex), which At first, the user is asked to point out the segment corresponding to the catheter by an identification rule accessed by a control rulP. The context of LAD detection is accessed next. It contains the following type of identification rules.

RULE 011

IF THE CANDIDATE SATISFIES THAT (1) IT BRANCHES AT 70 100% OF THE CAtHETER, AND (2) IT SATISFIES THE CONTINUITY CONDITIONS (AT BRANCHING POINTS), AND (3) ITS WIDtH VARIATION (AT BRANCHING ~O!NTS) IS 70 - 140%, AND (4) ItS DIRECTION IS 80 - 100% OF THE LONGEST SEQUENCE,

THEN

! 1) THE CANDIDATE IS DEFINITELY LAD CF=l.O), AND 2) ADD THE CANDIDATE AS LAD TO HYPOTHESIS.

When this , rule is accessed, the origin, continuity, width, and direction of each candidate, a sequence of segments, are examined, and all candidates satisfying these conditions are registered on the hypothesis tree with the highest certainty factor . The context contains another rule which finds less confident candidates for LAD . Candidates for CX are also examined by accessing the similar rules. MLCA (main left coronary artery) is a short blood vessel from which LAD and CX originate, and it is not observable in many LAO views . LMCA rules examine whether there exist a segment in each LAD's candidate between the end of the catheter and the point where the CX's candidate originates. If so, the segment is added to the hypothesis tree. If not, LMCA is an empty segment and is considered as the cross point of LAD and CX. Now we will show in more . detail how the hypothesis tree is genera t ed.

RULE 024

IF THE CANDIDATE SATISFIES THAT (1) THE CANDIDATE BRANCHES AT 0%- 20% OF LAD, AND

(2) THE CANDIDATE BRANCHES FROM LAD AT 20 - 90 DEGREE . AND

• A~6 THE CANDIDATE IS SHORTER THAN LCX,
• THE CANDIDATE IS SHORTER THAN LAD,
• THEN (1) THERE IS A STRONG EVIDENCE (CF·0.9) THAT THE CANDIDATE IS DIA, AND

(2) ADD THE CANDIDATE AS DIA TO This is one of rules for finding DIAs (diagonal branches) which originate from LAD. ( S i nee a I arge DIA somet i mE>s originates directly from LMCA, we also implement rules for such cases in the knowledge-base.) Suppose that rules for finding three large vessels, LMCA, LAD, and ex. were . accessed and several hypotheses on the identities of these vessels were already generated on RLACKBOARD as shown in Fig.6 with solid lines. In this example, CATH has been uniquely determined with CF=l, and there are three hypotheses on LAD and LCX: (LADl LCXl) (LADl LCX2) (LAD2 LCX2). When RULE 024 is accessed, all possible candidates for the diagonal branches are found on BLACKBOARD and are transferrE>d to a short term memory, then individual premise conditions are evaluated for each candidate. Predicates in the rulE>s are LISP functions which evaluate Tor NIL by evaluating the specified geometrical attributes. Some LISP functions can access FORTRAN programs calculating complex shape parameters or which utilization considerably save the computing time. This link of production rules with FORTRAN programs will be useful for augumenting our system because the production system can control image processing subroutine packages. At present, the system has functions examining attributes on the or1g1n, length, direction, width variation, angle, curvature, continuity, and index of shape complexity of the candidate or the vessels detected already. If the candidate satisfies the premise, the action part is excuted and the result is added to the hypotheses on BLACKBOARD . The dotted lines of Fig.6 shows the hypotheses on DIA generated by the context containing RULE 024 . Note that the system utilizes knowledge on the maximum number of each arterial branch such that LCX and LAD are single vessel but DIA are sometimes more than two hranPh~s .

Fig.7 Hypotheses with the certainty factors generated for taken from different directions. maximum images

The rules for all branches in the context of LAO t view are applied to the input image, and the hypothesis tree is completed for that view, The hypothesis having the highest certainty factor is displayed on the color display.

Ir the input anteriograms . contain another LAO view of which direction. is different · by a small angle, then another hypothesis tree is ~enerated by the same procedure. Then the judgment rules are applied to the · trees and the most reasonable hypothesis is selected. The detailed process will be explained in the next chapter using an example.

4. EXPERIMENTAL RESULTS

We have implemented the system written in FLISP (a modified version of INTERLISPI and FORTRAN on a minicomputer HP2108A. About 50 rules are currently used for identifying the branches of left coronary arteries in LAO views.

The analysis of the line image with 12 segments obtained from . an input image shown in Fig.2 (b) (a 60 degree LAO view) yields 6 hypotheses, and the interprer tation with the highest certainty factor is shown in Fig. 7 (a). The short I ine segment without any label is not given any identity, since the knowledge-base does not contain rules for such small branches . Most of the identities of the segments are ident i ca I to those by an expert and are considered as true. The branch identified as the third diagonal branch, however, is judged as a septal branch by the expert who examined other images taken from different . directions.

The ?inc-angiogram of this subject contains 1mages taken from a direction different by a small angle; 55 degree LAO views. The system analyzes the line image obtained from one of them, and generates another hypothesis tree. The most confident hypothesis is shown in Fig . 7

(b) . The judgment rules are then applied to find correspondences between the two interpretations shown in Fig . 7 . Starting with the most reliable vessels (LAD in this case), the correspondence of the other arterial branches are examined . If the branches originate from the same vessel in the two views are not same, their certainty factors are re-examine~. In this case, the third branch fr~m LAD IS assigned two different mean1ngs; a diagonal and a septal branch. The system evaluates the certainty factors of both hypotheses on the identity of the branch for the two images. (b) . We have CF[DIA.60°LA0]=0.6. CF[SEP,60°LA0]=0.3 CF[DIA.SS 0 LAO]=O, and CF[SEP,Fig.4(b)] zO.S. Also the system searches the knowledge-base for descriptions on the branches of LAD and finds the knowledge that if LAD has more than two branches, there is suggestive evidence (CF=0 . 7) that LAD has the first DIA and the first SEP and the other. Since the two other branches are identified as DIA, then the rule gives CF[DIA]=-0.7 and CF[SE~]=0.7. By using the method for the 1nexact reasoning [5], the system concludes that the third branch is the fir s t septal, and this interpretation is identical to that by the expert.

We have tested ·the performance of the system for a set of input images .. The hypotheses with the highest certainty factor obtained from sample input images are shown in Fig.ti. The system correctly identifies the major branches : The computing time for the interp~etat1on of one image ranges from 6 m1nutes to 20 minutes depending on the .number of segemnts and the complexity of the structure Our experiences indicate that the utilization of the large computer s~ch as FACOM MlOO will shorten the comput1ng time by a factor of 1/100.

5. DISCUSSIONS

The image understanding sy s tem for the anteriograms currently interpr e ts the line image s of the left coronary art e ry of a 60 degree LAO view . Also it can integrate the hypotheses generated for the ima~e s taken from a slightly different direction and obtain a more reliable model of the artery. Because of the modularity of the knowledge, it seems us easy to eonsru<'l the knowledge-base on other views of the left coronary artery and RAO and LAO vi~ws of the right coronay artery . The integration of hypotheses obtained from RAO and LAO views is more diffi cult and needs further research. The integration of other source of information such as temporal information is also important.

Although we use the rules on the structure of the artery of healthy subjects, the system can interpret the images containing diseased lesions if they appear as narrow portions of the segments . We consider the modification of the rules so as to find completly occluded portions would be easy if the invisible segments of the vessels are short . However, there exsi t images in which total lack of visible parts beyond the diseased lesions is observed, and future research is needed to interpret these images .

We assume that the noise free line image is extracted from the raw image data, but it is very difficult to find small arterial · branches in the cine-angiograms . The knowledge-based line finder [7] controlled by the production system will be useful for automatic inspection of the cine-angiograms.

ACKNOWLEOOEMENT

The authors wish to express their hearty thanks to Professor M. Inoue and Dr. T. Shimazu, Medical School of Osaka University for their kind and valuable discussions.