Temporal Event Recognition: An Application to Left Ventricular Performance

ABSTRACT

The problem of recognition of time-varying events, particularly molion concepts, is discussed and a framework for the abstraction of such con­ cepts is briefly presented. We have de~igned 11nd im­ plemented a knowledge-based expert system for mo­ tion understanding that incorporates several novel features. A frame-based representation, which in­ cludes exception handling via similarity links and the organizational primitives IS-A and PART-OF is used to construct a knowledge base of temporal concepts. This knowledge base drives the recognition process that integrates the paradigms of hypothesize-and­ tP.qt l'lnrl r.nmpP.t.itinn i'lnd en-operation among con­ ceptually adjacent hypotheses. The recognition stra· tegy also includes a hypothesis rating scheme that. is amenable to empirical performance analysis. This framework has been applied to the problem of human left ventricular performance evaluation from image sequences, and thus the knowledge base also contains much uf lht: cUl'rent understanding of left ventricular dynamics. This paper describes some aspects of this application in detail and presents a complet~> analy~i~ of a typical image sequence, emphasizing compari­ sons between human and computer analysis . Addi­ tional justification of the adequacy of the framework has been obtained using empirical studies of the hy­ pothesis rating scheme.

INTRODUCTION

The problems of recovering three dimen­ sional structure of moving objects from an image se­ quence along with the cone:sponding translational and rotational parameters, and of interpreting "ap­ parent" motions, have received a ~ubstantial amount of attention in the recent past [1], [2], and [3]. Our approach is complementary to these in that we ad­ dress the questions of ''In what contsz:t is this motion information useful ami in what funn is it useful , and how cdn a computer system abstract the motion summat·y from the large amount of quantitat ive data?". Many applications fur motion analysis a.rt: described in r 4], and include outdoor scenes, clini cal iiLtdgt:ry, awl satellite 11nd airborn imagery. ln par­ ticular, two and three-dimensional imagery of the dynamic left ventricle (LV) are becoming increasing popular and useful as clinical aids to diagnosis of di~orden of the heart. The left ve ntricle is perhaps the most important. component of our heart since it supplies blood to the body. Yet, its 11nalysis is per­ formed mostly by human observation of its imagery with little or no computer assistance, even thou,~tb the motions exhibited by the LV are more complex than the human visual system can objectively and

TEMPORAL EVENT RECOCN/TION:

AN APPLICATION TO LEFT VENTRICULAR PI!.'RYORJIANC:X

John K. Tsotsos

Department of Computer Science.

and

Divi~ion of Ct1t·diolo!!,y. Toronto General Hospital University of Toronto Toronto, Ont., Canada

consistently analyse.

This "real world" application i.3 rich with temporal concepts and relationships and motivated our research into time-varying event understanding.

Our system, called ALVt:N, is a kno.,..ledl(e­ based expert system for human left ventricular per­ formance assessment. Input is an image sequence obtained by cineradiography of the human le ft ventri­ cle. However, the methodology is applieable to other forms of dynamic card1ac imagery as well. The goal of the ALVEN system is two-fold: to experiment with and study motion understanding methodologies in the context of a rich temporal domain; and, to con­ sistently and objectively. evaluate the performance of the left ventricle and in· doing so, compile and refine the relevant cardiology knowledge, with the intent of providing both a clinical and research tool for car­ diologists .

We will briefty descnbe the interesting features of our representation fonnalisru 11JHi rt:co!l­ nition control structure, and then giYe details about a particular analysis or a left ventricular film.

A FORMALISJI FOR REPRESENTTNC TlME­ VARl'INC EVENTS Oven~iew

In two quite comprchen~ive collection~ of current time-varying imagery research, [ 4], [5}, the issue of repr<'sentation of tP.mpnrAI infnrmi'ltion, p1'1r­ ticularly for molion, seems quite neglected. Yet, it is clearly an important issue, especially for a motion unde rstanding framework such as ours.

The main concern of our representational formalism is how temporal concepts are to be represented and organized into a knowledge base (l<R) . The int.omt. ill t.o provide a formalism for t·epresentinl( 11-enera l temporal concepts sueh that pi'Oblcm-specific ones, in our case, left ventricular molions, can be r epre se nted in t.erms of the general concepts. Furthermore, the form of the Kl:l musl be such that it can be used by an appropriate conlr·ol structure to guide r ecognition of the problem­ specific concepts stored in it. There are several types of temporal coneepts Lhal we are concerned with:

1. event start and end slates;
2. rates of change during an event;
3. form of the changes during the event:
4. changP.s of relationships of the subject of the event with respect to other events or objects;
5. temporal constraints bctwoen events

In addition lo providing a coherent scheme for representing such concepts, the formalism must take several other constraints into account:

1. The data involved often have a "fuzzy" quali­ ty. In real world domains, there are nmges of ac­ ceptable values to contend with, as opposed to single correct values, as well as overlapping ranges of ac­ ceptable values between conflicting concepts. This is particularly important for events whose normal time intervals may be overlapping and which exhibit a temporal precedence relationship (event A must pre­ cede event B, but their temporal boundary is fuzzy) .
2. The representation must have a strong descriptive basis with qualitative concepts related to quantitative ones, thal is, there must be a "bridge" between descriptive and. numerical concepts.
3. The formalism must be capable of represent­ ing concepts at different levels of abstraction, depending on the level of expertise of the person who enters the knowledge. Both types of descriptions must be handled because there are cases where only coarse descriptions are avaiiabl~ Lh11l mu~l I.J~ i.u.­ tegrated with more detailed descriptions.

'F'inlllly, An invest.igation into appropriate reognition-biased knowledge structuring primitives is required for the construction of the knowledge base.

Entities of Lh· RepTiliHin.La.Lion.

The basic entities of the representation are packages of information called /Tames and are used to model abstract temporal concepts such as CON­ TRACT or EXPA..~D. and abstract object concepts such as HEART or LV. Each frame may have an associated description or its internal structure that defines the semantic components of the concept that the frame represents. For temporal concepts, the internal structure or a frame defines the semantic com­ ponents o! the event, such as r11te or duration. On the other band, object concept frames have an inter­ nal structure that defines their physical parts and the properties possessed by them. The internal structure of a frame is defined by slots, each of which has a name and an associated typ·. The type relates the slot to other frames that specify the kind of tokens that can fill (be bound to) it.

Slots may have associated information that specifies a default value, constraints that have to be satisfied by its values, and azcsptions that are to be raised when these constraints are not satisfied, thus driving the recognition process. Exceptions are in­ stances of the exception type frame and contain all relevant information r· equir~d !Jy th~ r~col!uiliou mechanism to characterize the matching failure, and to assist in determining. which alternate hypotheses may be appropriate.

Our representation is closely linked with the PSN formalism [6] and the concepl.!! o! frames and organizational priznitives are borrowed from there. Two primitive relationships are used to organize frames into a knowledge base with different levels of ab.;traction. ThP. PART-Or relAtionship relates a frame. to its parts, which are the types of its slots. Clearly, recognition of an in,tancc of a frame makes heavy use of the PART-OF hierarchy in the recogni­ tion of its parts. This relationship is a tool useful for controlling the level of detail in e. trame, and for pro­ viding a bridge between quantitative and qualitative dP.scriptions. For example, at a coarse level of detail, a concept such as CONTRACT is appropriate while at a much finer level, the motions of the individual com­ pon~nts that t11ken together make up the contraction could be founJ .

The other primitive relationship used to or­ ganize frames is called the IS-.A relationship. lt is in­ tended to capture the notion o! generalization or classes and sub-classes. The use of IS-A economizes on frAme si7.e (through inheritance of properties). and provides a mechanism for imposing more global constraints on specific concepts.

Our representation scheme is clearly biased towards recognition. Perhaps the most impor­ li:Lnl ~- ~presentational featw·e for the purposes of recognition is the nm.ilarity linJ. [7]. These links rP.IAt.P. frAme~ t.hAt. Bre, in Nome sense, similar, and are used to handle situations where one or more matching exceptions have been raised. Frames that h11ve an active similarity link between them are as­ sumed to be mutually exclusive. The information as­ sociated with a similarity link is stored inside a gen­ eric frame . The link remains dormant, I.e., the source frame and the specified destination frame are not connected in any way, until the recognition pro­ cess deems the connection necessary.

Each similarity link carries two types of in­ formation (in addition to its source frame and desti­ nation frame(s)):

• !i) A condition. which determines whether the raised ex.ceptious cau iud~~d b~ haudl~d I.Jy lh~ link; and
• binding infoTm.ation. that indicates hoY. the values of the slots in the source frame are related to those in the destination frame.

The condition is made up of two com­ ponents, a rim.ilcantv ·zpr·srion. , and a diff·Tnac· ·:zyr·ar:rion. The similarity expression contains the necessary conditions which the two linked frames must share in order for the similarity link to be activated (i.e., the "similarities"), Since only one of the frames (the source frame) is active when_ this condition is evaluated, the predicates describe prerequisite components of the destine.tion frame that must also be possened by the. source frame . The difference expression is a list of exc~:p­ tions which may be raised during matchine of the source frame . Each of the list's elements has an as­ sociated time interval that specifies when each elt­ ception should occur if all o! them are observed in the image s~quence. In effect. such an expression in­ dicates the time courlle of the matching failures in the source frame context, that indicate that the des­ tination frame's context would be more relevant (i.e., the "time sequence of differences''). Thus, the simi­ larity links point to alternate frames potentially vi­ able when exceptions are raised.

Tflm.pOTcal Con.crrpts

The temporal concepts of interest for our purposes are those describing two-dimensional spa­ tial changes. However, the representation formalism is not restricted to only these and, we believe, is ex­ tendable to the three-dimensional case as well. In order to adequately represent motion concepts, cer­ tain semantic components must be included; Miller [B] bas done a very good analysis of the semantic components for a large class of English motion verbs. Using Miller's work as a foundation, Eadler [9] refined these concept.,;, gilve clP.t.Ailecl clP.tinit.ions of t.he clirec­ tionals, and outlined a framework within which recog­ nition can be done. The work presented here is strongly based on these · research efforts. Miller's se­ mantic components include changes of location, the reflexive-objective distinction, direction of motion, changes of physical properties of an object, changes of motion, rate of motion and others. Our represen­ tation can handle these, but currently does not deal w1t.h causality.

Motion frames, once defined, are organized into a KB using the IS-A, PART-OF and Similarity rela­ tionships. Motions are divided into two main sub­ classes - simple and aggregate motions. The simple ones are "pure" motions - slrict contraction, strict upwards motion, strict lengthenina. etc. Motions which are combinations of these simple motions, are classified under the class of aggregate motions. This specialization uses the IS-A relationship. The aggre­ gation of several simple and/or other aggregate mo­ tions into an aggregate sub-class is accomplished via the PART-OF relationship. Motions which cannot co­ exist for the same object during the same time inter­ val are represented by including similarity links in their definitional frames. The activation or use of any of these three relationships is determined' during processing by the control structure. Details of the frame definitions for motion classes as well as the or­ ganization of motion classes can be found in [ 10].

THE RECOCN/TION SCHEME

U"erview

The paradigms of competition and co­ operation among hypotheses and hypothesize-and­ test form the basis of our recognition control struc­ ture. The key feature of the control structure is that it 1s dnven by· the organization of the knowledge base, that is, by the primitive relations between knowledge units. Activation of hypotheses proceeds alona the IS-A, PART-OF and Similarity relationships in a con­ strained manner.

Hypotheses are ranked on the basis of cer­ tainty factors. Each hypothesis, when activated, re­ ceives an initial certainty factor equal to that of the hypothesis that activates it. A modified relaxation la­ belling process {RLP) [ 11] is then used to update the certainty factors. The relaxation process is based on conceptucd a.djacency that specifies which hy­ potheses are competitors and which ones are comple­ mentary and in what respect. The compatibilities between hypotheses that are necessary for the RLP are derived in a dynamic fMhion, depending on which conceptual adjacencies are present between hy­ potheses that are active during the course of the in­ put image sequence. The best hypotheses (highest ranked) are used to derive the expectation& for the next image.

A scheme similar to, but not as sophisticat­ ed as [12], is proposed for the vision aspects of pro­ cessing, that is, the use of expectations to guide the search for objects in the image and determine their correspondencies to the previous image. Note that medical researchers have already proposed success­ ful solutions for locating the features in our particu­ lar type of imagery [13]. Changes are described in terms of location changes of points, length changes of axes and perimeters, area changes and shape changes. These four primitive kineses provide an in­ termediate representation for relating quantitative changes to qualitative ones.

This low level data drives the activation of hypotheses that attempt to describe the exhibited motions. The starting set of hypotheses for each ob­ ject in the first image contains only one hypothesill the NO MOTION hypothesis. The kineses for a particu­ lar object are matched against the hypothesized mo­ tions, and matching failures between exptH:ted and actual kineses are recorded. These failures are represented in terms of exception frames which con­ lain any information necessary so that proper selec­ tion can be made of alternate hypotheses. This selec­ tion is made via the similarity links which are present in the frame of which an active hypothesis may be an instance. The activation of more specialized hy­ potheses proceeds along the IS-A axes in the KB. Selection of 1111 appropriate IS-A child frame depends on the matching success of a frame which all · frames have as one of their specializations - the NO SPECIALI­ ZATION frame. This frame inherits all the properties of its IS-A father and adds new constraints to its definition, so that if it succeeds in matching, it ex­ cludes all other specializations of its IS-A father. It al!'!n cont.Rim: a !'IP.t. of !'limilarity links relating it via possible exceptions to the other specializations of ill IS-A father. In this way,: if it fails the matchin& pro­ cess, other specializations are activated. It also al­ lows the system to identify when there are no frames in the KB that are appropriate for describing the ex­ hibited motion. Finally, aggregate hypothesis frames are activated on the success ·Of a component. viR t.hP. corresponding JJAHT-0.1'' link. In other words, the IS-A relationship is a mechanism by which the frames along a particular "path"' in tho network are activat­ ed, each one being a specialization (generalization) of another frame on the path, the PART-OF relationship allows a breadth-first search for frames correspond­ in& to aggregations of frames perhaps on several different IS-A paths, and Similarity links provide a mechanism for selectively adding the frames of other IS-A paths into the active hypothesis set.

Let us, for a moment, compare this with the change of attention mechanisms in two other large application systems HEARSAY-II [14] and INTERNJST-11 [15]. In HEARSAY-II, knowledge sources are activated whenever they see their prerequisite data · on the blackboard, i.e., the activation of knowledge ·sources is data-driven. In INTERNIST-II, hypotheses are also generated from the data. Sians and symptoms are input to the system and the appropriate hypotheses are activated. Therefore, data is continually bema added as a result of questions asked by the system, so that new hypotheses are introduced throughout the diagnostic process. Our :sclltomt< fur adding hy­ potheses diffen in that it takes advantage of both successes and failures in order to determine which alternates are viable. The remainder of this section will concentrate on some of the more interesting features of the control structure. A complete description of the control structure can be found in [16].

Our system maintains a set of active hy­ potheses throughout the recognition process ... Activa­ tion of a hypothesis involves activation of its IS-A ancestors (via the IS-A· hierarchy) and of its com­ ponents (via the PART-OF hierarchy). Active hy­ potheses are organized by their "conceptual adjacen­ cy'": the semantic inter-hypothesis · relationships that are actiYe at any time instant, thus conceptual adja­ cencies are dynlimic. Thi~ mRy hP. likP.nP.cl t.o t.he "structural adjacency" of Hl!:ARSAY-11, which is based on immediate adjacency in the AND/OR tree of hy­ potheses. These relationships correspond · to the features of the representation - IS-A, PART-OF, similarity, and tempo;·o.l p;·ecedence.

An object's sel of possible hypotheses con­ ~i!lt. s of active hypotheses which define motion classes for that object during a common time interval. Hy­ potheses for an object's parts are considered as part of the set for that particular part. In this way, since hypotheses are organized by object, there can be no overlapping sets of hypotheses - no one hypothesis can be a member or more than one set. There is no restriction, however, on the PART-OF relations between sets of hypotheses.

The mechanism for the addition of a hy­ pothesis via an activated similarity link requires ela­ boration. A similarity link in hypothesis H is activat­ ed between hypotheses H and H' when:

• the similarity expression is satisfied, i.e., all properties of H' which mu!lt be true before H' can be activated must hRve been instantiated; and,
• at least. onP of thP. P.Y<'Ppt.ion11 in t.hP. cliffP.rP.nre expression has been instantiate~. It is not necessary that this be the first one in the time course expres­ sion. Noise effects may mask il. One must realize, however, that noise or extraneous information may also erroneously trigger the similarity.

When frame H' is activated by H as its com­ petitor, the slots of H' must be filled up to the time instant of activation. lt. will be true, in many cases, that some of the slots of H will be identical in content to those of H'. The!le are transferred through the binding expression in the similarity link. Those that are not must be computed.

There are several additional considerations that arise when determining similarities between hy­ potheses:

• When a particular exception cannot be handled by the local similarity links, the links of its IS-A ancestors are checked.
• Since activation of a frame automatically ac­ tivates its IS-A ancestors, transfer of parts between the two frames' IS-A ancestors may be accomplished by the binding expressions of the similarity links (if present) between those frames.
• There is also a need to propagate similarities up-.rards along the PART-OF hil'rarchy, because possi­ ble mis-matches of a motion component may require completely new contexts for the newly activated parts. This is done by automatically raising an excep­ tion in the parent hypothesis. When an exception is dP.I.P.ct.P.cl in 1'1 pl'lrt. A of frl'lme B, this automatically generates an additional exception for frame B stating that frame B· has failed. In this way exceptions are propagated up the PART-OF hierarchy. The exception carries with it a special slot "prereq_part" which specifies the newly activated frame name C. The parent frame of B. that is D, can use its similarity links with the added constraint that C must be PART­ OF any newly activated destination frame of D.

llypothr;ris Rating

The hypotheses will be ordered by means of the certainty that the system has in them. The best candida~es are determined for each object; that is, hypothesis certainty values are not compared uule~s the hypotheses define motions for the same object and for the same time interval. Thus, each object would have a leading hypothesis set, and each part of each object would have a leading hypothesis sel. It is not necessarily true that the best hypothesis for an object's part ·is PART-OF related to the best hypolhesis for the object as a whole .

Each hypothesis has a certainty factor asso­ ciiilt!c.l will! il - i:l uuU1Le1· Lt!LWt!t!n 0.0 (completely uncertain) and 1.0 (completely certain). Initial values are set through the conceptual adjacencit!s of each hypothesis when it is activated. lf a hypothesis H, has N competitors (either mutually exclusive ones, through similarity links, or through the temporal precedence constraint), then each hypothesis of the competing set bas an initial certainty of 1/N · cert(H). If a hypothesis has no competitors. then as far as the system is concerned, it is certain that the hypothesis will be instantiated - because there is no other possibility. This is why similarity links are so crucial - matching failures would not. be recorded in a hypothesis' certainty factor through the relaxation process unless they also activate a similarity link Lo a competing frame. The reason for this is that certain­ ty factors are normalized over the set of competing hypotheses. This has necessitated tht! inclusion of control hypotheses: hypothese:! that monitor each set of competing hypotheses. They are frames in the same sense as described above, but their matching constraints succeed if no hypothesis in the compet­ ing set succeeds matching and fail otherwise. They may be likened to the ''no-edge'' label in edge fincling applications of .KLP's, and, in direct analogy, are frames of type NO AGGREGATE or NO SPECIALIZATION for the relevant motion concept. Hypotheses are in­ stantiated when their certainty reaches a particular value. determined by the size of the competing set, the duration of the shortest motion to be recognized and the image sampling rate (see [16], [17]). The in­ stances are related to their definitional frames via t.he in.da.nce-of relationship and must conform to the internal structure of the frame. Hypotheses are deleted when their certainly falls to beloll' a minimum value that is related to the instantiating certainty threshold.

The driving concept used for the updating of certainty factors in our system is generic good tem­ poral continuation of hypotheses. This is direct anal­ ogy to good edge continuation for ed~~:e labels in im­ ages. Global constraints extracted from the knowledge organization and local constraints embo­ died in the hypotheses themselves provide the basis for the determination of good temporal continuation.

Once tbe initial certainties are set for a hy­ pothesis, the certainty is updated for each subse­ quent image. The updating rule that we use is t11kcn from relaxation labelling [11] and has exactly the !!arne form as presented in that paper. The compati­ bilities between hypotheses depend directly on the types of conceptual adjacencies that hypotheses ex­ hibil. The weighting factor assigned to each contri­ buting hypothesis depends on the number of active adjacent hypotheses and their types.

The major change from the standard RLP described by Zucker is that -.re do not iterate until certainty factors converge to stable values. Rather, certainties are updated using only one application of the rule. In this way, each update corresponds to an analyzed image in the sequence. The reason for this change requires a clear understanding of what the RLP does.

For the purposes of this argument, let us as­ sume that there are three competing hypotheses. The initial assignment of certainty factors place the starting point . of the RLP at some point, say A, on the plane formed by the certainly factor vectors \1.0,0!. (0, 1,0!, (0,0, q. The plane is as il is because lhe sum of the certainty factors must remain Bt one; other­ wise, the process is not guaranteed to converge. Now suppose thlit afler the first inter-image description is obtained, from point A, the RLP, using good temporal continuity criteria takes the certainty factor vector through some path to a final convergent labelling after several iterations of the updating rule. Why is thi~ unde~irl'lhle? Recau~e of thP. n<~t.urr. of the RI.P, the system could never· move away from this final stable slate, and therefore after the first pair of im­ ages, lhe certainty factors could not change .

If only one application of the updating rule is used between images, the effect is that the system moves along a short vector tangent to the path Lhat it would have taken if many iterations were done. Two images are enough to rlet.ermine this vector. The system's focus thus has inertia during th~> intPgra­ tion of many image pairs of data from the image se­ quence. It has inertia of location because it does not move very far away from its current location. This is desirable because hypotheses and their compatibility values are uncertain. The length of the vector is determined by how consistent the matchings of hy­ pulheses liml Lhe kineses are with the constraints im­ posed by the organizational axes of the KB. The sys­ tem also has inertia of direction because it moves along a tangent to its current path in the plane formed by the hypothesis space. The problem of ra­ pidly shifting foci of attention, present in other large application systems [14 ], [ lG J, is therefore greatly re­ uuced. However, othet· considerations arise. What arc the limitations of such a process in terms of how many iterations (in other word5, images) are needed in order to determine a consistent labelling, and how is such a process affected by extraneous stimuli? We have conducted several experiments on the hy­ pot.hesis rating scheme m order to study these ques­ tion5 [HI], [17] . The rc~ult$ of t. hP.~c expP.riment. ~ have lead to several empirical relationships relating compat.ihilit.y values for the conceptual adjacency types, maximum number of bypotheso:.s in a single competing set, decision certainty thresholds, signal noise content, scene sampling t·ate, and shortest event in the domain to be recognized. In addition, the results of one particular experiment demonstrate that inclusion of the IS-A hierarchy and its inherent genP.rali7.at.ion of constraints, leads to faster event recognition in terms of the number of image samples that must be analyzed.

THE APPLJC_4TJON TO LV DYNAMICS

In surveying the rapidly growing literature on quantitative left ventricular dynamics, the prob­ lem of consistency in terminology has become ap­ parent to us as well as to other researchers [ 18]. How can we compare and evaluate lhe varying and sometimes conflicting results of studies of ventricu­ lar wall motion? We have attempted to define the usu­ a l terms used by cardiologists in describing LV per­ rormanr:e in t.crm~ of !.he rnolion semantics outlined .. uuvt: t:Lll<.l u~iu~ our representation formalism. A brief diversion is appropriate here in order to dcseriue the proulem uomain so lbat the example

presented will be easier to di~!est.

The Image sequences that are being studied arc obtained by ciner11diography of the left ventricle. Howeve r, the partic ular LVs that we are studyinp; are those that have hau corrt<clivt: ~ut·11ery (cut um11·y l>y­ pass or valve prosthesis) . The goal is to determine how normal their post-operative function is· in order to appraise the effectiveness of surgery. Fol" each LV, during corrective surgery, 9 tiny tantalum helixes (markers) are implanted into the left ventricular wall, all roughly in the same plane . In addition, two clips are attached to the aorta as points of reference. Arter surgerr. follow-up cxarninalion involves relalive­ ly ~imple r.inerarlingr11phy. Figurte 1 display~ the mo­ tion patterns for one such LV, bolb the inward ( Ia) and the outward (1b) motions, with all f~>atur~>s of in­ terest labelled. The marker positions appear as dots. The left ventricle is standardly divided into three seg­ ments: the anterior segment is made up . of markers 3, 1, 5, and 6; the apical ~egment i~ made up of ma!'k­ ers 6. 7, and 9: and, the posterior segment is made up of markers 8, 9, 10, and 11. The aortic clips are mark~>rs 1· and 2. The~"' figur~><: shnw t.hP '"'P"r­ imposed marker positions for a number of consecu­ tive irnagell, separ·aled into the contraction and ex­ pansion phases so that the motion paths arc more ap­ parent . Even still, some marker positions are occlud­ ed in these pict.ures whenever no motion was exhibit­ ed. This particular case was filmed at 30 images/sec.; however, mnre Tflcen~ly, 60 image:o~/,.er. . has become the norm and ALVEN has also been tested on those sequences.

The left ventricular cycle has two main phases - systole (ejection, or, contraction} and dias­ tole (filling, or, expansion). The systolic phase is di­ vided into three parts: the isovolumic contraction phase, the maximum ejection phase and the reduced ejection phase, while diastole is divided into four phases: isovolumic relaxation, rapid filling, diastasis and filling by atrial contraction. Good data is avail­ able on tbe standard normal charactenstics of these events. Using the textbook definitions of each of these phases in terms of minimum start time, max­ imum end time, minimum duration, maximum dura­ tion, minimum and rnlixirnum rat.cs of contraction (expansion), frames were defined for each normal phase . Each constraint of the slots in these· frames has its associated exception: TOO SHORT. TOO FAST CONTRACTION. TOO LATE. TOO EARLY, etc. TOO SHORT/ I.ONG refers to the duration of an event, TOO LATE/EARLY refers to the time slot in which the mo­ tion was recognized with respect to the LV cycle, TOO FAST/SLOW refers to the rate of area change. In ad­ dition, several other abnormalites are defined. ASYN­ CRONY is the term used to denote that the onset of contraction (expansion) is not uniform for all por­ tions of the LV. In our case, the LV is made up of three se~menl s: anterior, apical and posterior. Elich segment in turn is made up or several rnarkors as in Figure 1. Asynchrony, then, applies to each segment, for its markers, and for lhe LV with respect to its sel{­ ments, reflecting the PART-OF hierarchy. HYPOK­ INESIS is the term used to describe a significantly smaller extent of motion in comparison with the object's neighbours and again is defined relative to the PART-OF hierarchy. Finally, abnormal directions of motion with respect to the contraction (expansion) of the LV are described by the term DYSKINESIS. Ot.her motion t.crms usP.ri in t.he ril"script.ion aro: UNI­ FORM contrliction (expansion) - all parts lire' moving inwards (outwards) synchronously, and the super­ part is contracting (expanding) (these are examples of aggregation of simultaneous motions); INWARDS

,uUTWARDS) motion with respect to the dynamic cen­ troid of an object's super-part; length chdnges. both SHORTENING and LENGTHF.NlNG (nnrm~l l.v~ · pr.rimr.­ ter shortens only during contraction and lengthens only during expan!lion): and. others that ha·e a more intuitive melining. A BEAT is defined as a strict con· traction immediately followed by a slricl expansion, while an INVERSE DEAT is the exact opposite (these are examples of an aggregation of a sequence of mo­ tions). Finally, the terms MOVING, TRANSJ.ATF., OB­ JECTIVE. PHYSICAL-CHAN�~!:, AH.J!;A-CHANGI!;. L!!;NGTHCHANGE reflect the IS-A hierarchy for each of their more speciHlized motions. Also note that terms such as NO MOTION, NO TRANSLATION. NO LENGTH CHANGE, etc. are also recognized. Reflexive verbs, although defined in ALVEN. such as UPWARDS. LEFTWARDS. etc. were not included in this desciption. They are not very useful for LV motion since an orientation-free description is required. The term R-TS refers to an instance of a normal rate and lime slot for a particu­ lar area change. The set of such normal instances is U1en put together in determining whether or not the duration is proper.

An area for the LV is defined as the area en­ closed by the outline formed by joinlnA the markers, and an area for a segment is defined as the area !"n­ closed by the outline formed by the markers of lhe segment and the dynamic centroid of the LV. A length is simply the arclength of the line formed by joining the markers of the LV as a whole or of each segment.

ALVEN's classification of the motions of each segment, for the LV as a whole, as well as all excep­ tions to normal motion generated for all markers and the complete descriptions of markers 2 and 7, makes up Figure 2. The goal is to provide a sum­ mary description of the dynamics of the LV as a whole, and then, if the clinician is interested. the seg­ ments' dynamics, marker dynamics and their associ­ ated numerical qunnt.it.iP.!I may he !!electively exam­ ined for the purpose of either verification of the sum­ mAry rleRcript.ion or for precisely locating reasons for an abnormal summary description. This particular example required 17 images for a single LV cycle at 30 images/sec. The radiologist reported that the marker motions indicated a hypokinetic anter-ior seg­

ment and normal motions otherwise.

The description in Figure 2 uses the time units of images. We see by the description, That AL­ YF.N agrees with the radiologist in that hypokinesis is reported for the contraction phase of each anterior marker for at least one time instant during the phase, as well as for the anterior segment as a whole. However, hypokinesis is just. a sign of more severe problems. Obviously. if a part of the LV does not con­ tract. properly, the rale or expulsion of ulootl is im­ paired. This is apparent by the exceptions TOO SLOW CONTRACTION, TOO SHORT REDUCED EJECTION PHASE · .the lack of an instance of the maximum ejec­ tion phase, etc. These are consistent with hypok­ inesis, but are more serious problems with the left ventricle. Also, since the system has objective cri­ teria for judging the motions, several instances of asynchrony and dyskine!iis were found both at the segment. ann ~tt. the T.V level. Thi!l i~< rnt.her rlifficult if not impossible to do by observation only. The remainder of the description gives the complete set of terms used by ALVEN to describe the motions.

We conclude that ALVEN's evaluation is con­ sistent with that of a radioloaist, but is more com­ plete and objective. Other examples that have been analyzed also support this conclusion.

CONCLUSIONS

We have briefly described an approach to the abstraction of time-varying concepts from a se­ quence of images. The system embodying this ap­ proach, called ALVEN, has been implemented and an example of one of the left ventricular motion se­ quences was presented. Testing thus far has shown that ALVEN's evaluation of LV performance is con­ sistent with the radiology reports, but is more objec­ tive and complete. ALVEN has also been tested on ar­ bitrary motions of moving dots and produces quite acceptable, although limited in vocabulary, descrip­ tion~ of their motion!! in t.he planP of t.he image. WP. believe that the recognition strategy is unique in that the semantic relationships of the KB and lime itself are integral components of the recogntion process. Moreover, our recognition control structure provides an approach for reducing the effects of shifting foci during recognition and for dealing with exceptions and temporal constraints. There are several ongoing research topics being pursued using this general framework: interpretation of arrhythmias from elec­ trocardiograms, interpretation of aortic valve func­ tion in the fetus using ultrasound signals, and the representation of causality and its recognition from image sequences. In addition, ALVEN's knowledge is being refined and tested in order to achieve clinicHl acceptance for its results.

RsffiT's"~U:ss

1. Ullman. S.. The ln.trrpreta.tion. of Stnu:tuTS from. Jlotion., MJT Press. 1979.
2. Rashid, R .. "Towards a System for the Interpreta­ tion of Moving Light Displays", IEEE Tran.s. on. Pat­ tern Analysis an.d Jfachine ln.t~tltigsnce, Nov. 1960.
3. flinchbaugh. H .. Chandrasekaran. l:l .. ''A Theory of Spat.io-1'emporal Aggregat.ion for Vision", OSU-CJSRC­ TR-B0-5, Ohio State University. 1960.
4. Nagel, H. -H., "Image Sequence Analysis: What Can We Learn from Applications", University of Hamburg, Ifi-HH-M-79/80, 1979.
5. Badler, N .. Aggarwal, J. (eds.), "Workshop on Com­ puter Analysis of Time-Varying Imagery", University of Pennsylvania, 1979.
6. Levesque, H.. Mylopoulos, M.. ''A Procedural Se­ mantics for Semantic Networks". in Associative
7. Nt~huorlcs, ed. by Findler, Academic Press, 1979.
8. Minsky. M., "A Framework for Representing Knowledge". in Th.a Psycliology of ComputaF Vi­
9. sion., ed. by Winston, McGraw-Hill, 1975.
10. Millt:r, G., "Ent~li~h VeL·bs of Motion: A Case Study in Semantics and Lexical memory", in Coding Processes in. Hum.a.n. JlemtJT71, ed. by Martin and Melton, Winston and Sons. 1972.
11. Badler, N., "Temporal Scene Analysis: Conceptual Descriptions of Object Movements", TR-60, Dept. o! Computer Science, University of Toronto, 1975.
12. Tsolsos, J.K., "A Framework for Visual Motion Understanding", CSRG TR-114, University of Toronto, 1960.
13. Zucker, S .. "Production Systems with Feedback". in Pattn'ft.-Dir~tcted ln.f~c· Svstems, ed. by Waterman and Hayes-Roth, Academic Press, 1976.

12. O'Rourke, J., Badler, N., "Mode1·11ased Jmage Analysis of Human Motion Usina Constraint Propaga· tion", IEEE Tran·. on P·Uenr. AR4lV.U au Jla.chine JnleUigence, Nov. 1980.

13. Gerbrands, J., Booman, F., Reiber, J., "Computer Analysis of Moving Radiopaque Markers from X-Ray Films". in Cowqn&t- Crmpllics ·mad lfftll.ge P.,.­ cesring, Vol.11, 1979.

14. Lesser, V., Erman, L., "A Retrospective View of the HEARSAY-ll Architecture", Proc. IJCAI77, Cam­ bridge, 1977.

15. Poplc, H., "The Formation of Composite Hy· potheses in Diaanostic Problem Solving: An E~rcise in Synthetic Reasoning", Proc. IJCAI77, Cambridge, 1977.

16. Tsotsos, J.K., Mylopoulos, J., Covvey, H.D., Zucker, S.W., "A Framework For Visual Motion Understandina" IEEE Trmns. on PoUern Anolv.U oncl llochine /nteUi.gence, Nov. 1980.

17. Tsotsos, J.K.. "On Classily.ing Time·Varyifll Eventa", Proceedings of Pattern Reco'!nition and Image Procossing Conference, Dallas, 1981

10. Daughters, G., el al., "Methods for Ventricular Wall Motion Assessment: Towards a Uniform Terminology" Proc. IEEE Computers in Cardiology, Geneva, 1979.

_ ....... 1 I

-rur 2 :

110 IDTIOit - a 1- t t· 2

ti)VJJC - u- a ·· a

&UIPLE - u- 2 t· I

~:!:..';~~~wc .. ,;h'!::.!o!·,: -·U· 1- u- I ·· ·

UPMAC8UIC wltb r·· .. ot t· -rbr I - tt- 2 te 8

110 JIIOTIOII - tl- a t· '7

ti)VIl'C - tl- 7 to 8

8 UIPLE - tl- T t· 8

~J~~IIC wl ;II t ;::.:c :· ,: ·rMr I - tt· T to a

APP,..OACIIWC wl tk r·ol"'e t to -rlwr I - t t· T to 8

.. 0 tiOTIOIIII - t l· 8 to 16

-rro~lOI .vroi:JIUI8 - tl· 2

-rker T I

l'tOVIRC - tt .. e to 6

NIPIPI .f.

- tl- e to 6

OBJECTIVE wltb roo.oet t· Apleal ·-at - tl· e to ··

TRAIUoiLATIIIG - t I· e te 6

fiOVIJtC OtrnfAJU)8 wltb roa,..at to Aploal ·-·t - tl· to

IIOVIJtC JlfVARD& wltla roapect to Apical ·.-·· - t I· l to 6

1'0 J«)TJOif

- tl- 6 toT

PtOVII'C - t l· T to te

SJptpLE - t l· 1 to Je

'l"'VJJ9LATJifC - t 1- T to 1·

OBJECTIVE wtlb roo ... cl to Apical ·-··- tl· T to ·· 8

ttOVIftC.. OU'MIAIUJS wltb reopeet to Apical .. _., - tt· 8 to te

JtOV 1 ltC IJIVARD8 wl tb uop.c t to Apleol h-al - l ·- T to

lfO NOTIOif

- t 1-. te to II

1'10\lllfG - t 1 .. II to 13

SII'IPLE - u .. ll to 1:1

~~~t~"c.,; .. '!::.!!.'~o 1 :.teel ·-·t- tl· II to IS

fi)VlftC Otn'VAJU)S wltb roa,.ct to Apical ·-··- tl· lJ to IS

1'0 ttOTIOll - t 1- 13 h 14

J'IOVI"C - t 1-. 14 to J6

SJKPLt

- u .. 14 to 16

llW'SLATIIfC - ll- 14 to 1·

PIOVII'C OUT'VAIUJS with roopocl to Apleal .. _., - tl· I

OBJECTIVE with reo.-el to Apteol h-at - tl· 14 to 16

4

to II

I'IOVUG JIIWAIW8 with reap·ct to Apical h-al - tt· II to 16

-rkor 8 I

......... II I

I

1.

Contraction

phase aortic clips

2·

· 3

·

.·

anterior

..

~·

·· 4

hhrlor ·-·t : CORTIIACTIOR AIIYIICBNIIIY - tiNOVINC - t t .. e to 16 f;J ... I.F. - tJ .. e to 16 I'BYM I CAL CIIUCE - t 1- e to 16 TRAIUJUTUte - t 1 .. e to 16 AN:A ClldCE - t 1- e to 16 LEftCTD CB.UCE - t 1- e to 16 OBJECTIVE wltb re·pect to lAit Voatrlclo - 11 .. e to 1 COifi'RACTJIIC - t 1- e to 6 &BORTEIUIIC - t ,.., e to 2 PK)VJIIC IIIVARDS wllh re·awc:t to )Aft Voatrtc:Jo - tl- e to I CONTRACT I OR DYSI:IIIrS IS - 11- 3 LENCntEIIJNC - tl- 2 to S OBJECTIVE with ro·pec:t to lAft Voatrtc:le - ll· 8 to II f;HORttll IJIC - t I.e 3 to 6 CONTMACTIOJI IIYPOKIJI~JS - tl· I to 6 IIOVtlfC IJIWAADS vltb re·peet to Left Voatrlelo- 11 .. 4 to 6 UJUFONILY CO~'l'RACTINC - 11- 3 to 0 00111'1\ACTlOI' DYSKJJf£.818 - t 1- 6 vel' AJIS I OJt MYI'CBROJfY - t ,.. 1 JIOVIIIC 0\n'VAJU>S wltb roopoet to lAit Voatrlc:lo- tl- 6 to 7 VCPAJIDUIC - t ,_. 6 to t· LUC'IliEJIJJfC - II· 6 to 12 BEATJJIC - t a .. e. to 16 EXPARSIOR DYSI:IIIrSIS - 11- 8 lo 14 IIOVIJIC IJIIVARDS wltb roop.et to I.Atl Voatrlc:le- tt .. 7 to 8 F.KrANNIOJI HVPOKIJIF.SIS - t I· 9 MVIJIC OVJ'WARDN with roopect to Lett Voatrlc:lo- tl .. 8 to 11 OIIJEC1'Jvt: vltb roopt~tr.t to Left Vontrlelo - .... 12 to 16 SOORTEJUI'C - tt .. 12 to 13 IIOVIIIC OUTWARDS wltb. roopoct to lAtt Veatrlcle- tl· 12 to 14 LUC1'11EJfJIIC - t 1 .. 13 to 14 COI'TIIACTIOR DYSJI:IRESIS - 11- II COII'J"RACTlftC - t l- 14 to II IRVEIUI! 8£.\TIRG - tl- 6 to II SBORT!IIIRG - 11- 14 to II JmVIftG llnfAJWS wltb r··JMc l to Loft Voatrlc: I· - u- 14 to II EXPAIIDIII'C - t I· II to 16

LENCTHEifiJIG - tl· IS to 16

a.teal .. _.t t COU11ACTIOW AIIYIICBIIOIIY - t 1JII)VIJIC - t l- e to 16 ei,.LE - u .. e to 16 PIIYIIICAL CIWIGE - u- e to 16 11tAJI'SUTI"C - t ,_ t to 6 A11!A CIWIG! - 11- e to 16 URC111 CBAIICE - t 1 .. e to 6 COitTRACTIRC - ll- e to 6 L£1fCTH£1fJIIC - tl- e to I CORTIIACTIO" DYSKIR!SIS - 11- II lo 6 OfUECTIVt: with roapt!"c:t to lAft Ventricle - tt- I to 6 =~~~"::~...;,.,··:.~ ;:.:..8t to Left Voatrlelo- II· I to 6 ElO'ARIIIIO" AIIYIICHAORY - tl- 7 JIO l'R.AMIUTIOJI - t a- 6 to 7 RO LERGTD CIWIGE - t 1- 6 to 7 EXPAJIDIRC - t 1- 6 to 14 BE.tTJifC - t ·- e to 16 [XPAPISIOII DYB~JJtUIS - t 1- 8 to 16 'I"RAA'SLATJIIC - 11- T to 16 ~~t:"';.W~~t~~-.. !!;:c:~ :: :!,, voatrtc:l·- "· 1 to 1e ~~:~~r.:~-~~~~~~ !:.!!ct to Lert Ventricle- tl· 1 to 9 NOVINC IIIWAkDS wlth r··r"ftt to lAft Ventricle - tl..e 9 to 1e OBJECTIVE vltb roopeet to Left Vo11trlcle- tl- II to 14 JIIOVJJtC OtTT'WARDS wl tb roapec t to Le f I Voatr l~:: lo - t 1.. II to 14 IBORTEJIJIIC - t l- 13 to 14 CORTIIACTIO" D\'III:IRESIS - tl- IS COifTRACTIIIC - t ,.., 14 to II JJ(VU\S[ B[.t'J'IJ(C - t 1- 6 to IS ~~t:~~lfCwt~h'!::~:~·~.'t.,, Voatrlcl·- u .. II to 16 PIOVINC OUTWARDS wltb re·pect lo L.tt Voatrlelw- ll· 11 to 16 EXPAND INC - t 1- 10 to 16

Poaterlor Se·llllfl·l : COJnl\ACTION ~YNCIIRO"Y - t I.e I flO\' UIC - t 1.. 8 to 16 8UU"LE - tl .. e to 16 PIIYBICAL ClldC£ - t 1 .. e to 16 'I'RAJftiUTIIfC - t 1- e to 6 AN:.\ CIIUC£ - t 1 .. e to 16 LEifCTB CB..U.Ct - 1 1... e to 6 OBJECTIVE: with r··P·ct lo Loft Voatrlcl·- u .. e to 6 CO"'l'RACTU·c - t 1- e to 6 NHORTf.N I ftC - t 1- e to 2 PIOVING lftWAfWS with reopect to Loft Voatrlcle- tt .. e to 6 CONTH.ACTION DVSKINESJS - t 1- 2 to 6 Lt:NC'l1U:N I NG - t I.e 2 to 3 ~oonn:Pt tNC - t ·~ 3 to 6 COPtTRACTIOJf B\TOKIJf£818 - t 1- 6 EXP AJIS 1Oft ASYJIICBROJIY - t t· 7 lfO TRAlfSUTIOR - t 1- 6 to 7 lfO L£JfCT11 CB.AJtCE - t 1- 6 to 7 EXPAitDINC - t I· 6 to 14 BEATifiC - ll· e to 16 EXPAI'ISIOII DYSI:IIfF.SJS - t l· 8 to 16 TRA"SLATUC - t l· 7 to 16 LENCTH CHANCE - t I.e 7 to 16 I.[NCTHt:N I NG - tl- 7 to 8 r.)(t'.t,.SION HVI'OKI"ESIW - II~ 9 ODJt:CTJVE with re·pect to Left Voatrlcle - tt .. 8 to 16 ~OORTEPIIJfC - t 1~ 8 to 9 lllVINC OtrNA.RDS vltb roopeet to Lort Vo·trlcle - U· 8 to 13 LEftCTIIEJfJftC - t 1 .. 9 to 13 SBORTEJflftC - u .. 13 to 14 PIOYJJfC JJIVAJ\DS wttJa ro·P4'ct to Loft Voatrlc:le- tl- 13 to IS CO!ITilo\CTIOJf DYSX:JRT.SIS - t t· IG CONTRACT INC - t 1- 14 to II INVERSE BEAT INC - t 1 .. 6 to 18 LENCTHEftiNC - ll- 14 to 16 PIOVINC OtiTWARDS with ro·peet to Lett Yeatrlclo - 11- IS to 16

t:XJ>AJtUINC - t 1-e HI to 16

!Aft Yo·trlcle r

COR'111ACTIO" AIIYIICDRORY - t 1- I IIOYIIIC - t 1 .. e to 16 SlPD'LE - tl- e to 16 PIIY81CAL CHAliCE - tl- e to 16 'I"RA..fSLAT11fC - t l· · to 16 AN:A CBARC£ - tl· · to 16 LEIICTB CILUCE - t I· e to 16 CO"TRACTINC - 11- e to 6 AHORTEJf I PIC - t 1- e to 6 TOO ~ott.OW COJITRACTION - II- I CUNTttAt:TIO" DYNKINEHIM - tl· 2 to 4 UJIIIf'ORPO...Y COJ.-J'MACTING - t IWI 4 to 6 ltOIUIAL R-1'8 REDUCED EJECT tON - t I~ S to 6 TOO ~DORT REDUCED EJECTIO" PIIASE - tl- T E.XP AJIS I 01' ASYI'CIIROJfY - t 1.. 7 EXPARDI"G - tl- 6 to 14 %:c~~~~.Us;~:'r~RtW~o rtu. - .... 'to 1t BEATIPIC - tl_. e lo 16 EXPANSIOJf DYSICllff.BIS - tt .. 8 lo Ui UN IFORI'ILV EXPAJfDIIfC - tt ... 7 to 1e TOO FAttT t.XPA,.tiiOit f'OR DIASTASIS - tl_. 11 NOMAI. R-~ DIAh'TASIS - tl.e 11 to 12 TOO ~HURT l)JAtnA.14UI - t I-.e 13 to II llOMAL R-TS DIAltTASIS - t IWI 13 to 14 COit11\ACTIOit DYSKlltEBIS - t I.e II COJIITRA.CTIJfC - t a.. 14 to ll ~~=ER~Tl~t.i_ :~~J:Cto - 1 !a .. II to 16 EXPAJIDIJIIC - tl-. 18 to 16