Plan-Guided Analysis of Noisy Dynamic Images

1. 11fTRODlJCT101f

A wide variety of processes observed in experiments of medicine, biology, or engineering are recorded on video tape or cine film as moving images. Analysis of these images, however, have been tedious tasks of human beings; they .must keep watching a large number of frames to point out feature patterns and measure their parameters. In recent years, computer analysis of moving images [1,2], such as motion analysis of hearts [3,4] or micro organisms [5,6], have been studied to reduce the human labor and extract more reliable information from the records in short time.

Because of a large amount of information content of a moving image, too much computing time is spent if whole areas of consecutive frames are examined in detail. Although a special parallel processor system could significantly reduce the computing time for preprocessing, feature extraction, or change detection, we should avoid to waste the computing power for unnecessary processing. Analysis of moving images does not require all information in the records, but only a small fractions are utilized; for example, we analyze only small subareas covering moving objects for tracking, or abruptly changing frames are more carefully examined than almost still ones for motion pattern analysis. Most motion analyzers have been designed to save the computation by utilizing models of objects in already analyzed frames to predict their locations or shapes in the current frame [1,2].

We have extended these ideas to organize a new system, a plan-guided analyzer lof moving images. The plan-guided analysis is not a new idea, but has been studied to analyze complex static pictures;· for example, identification of human faces [7] and analysis of chest radiographic images [8) . However, the idea is most effectively applied to analysis of a long sequence of high resolution pictures, because the computing time is of primary importance and one can significantly reduce it by utilizing . the contextural information about the images in consecutive frames. The feature of our system is to fully utilize its knowledge, both a priori and acquired knowledge, about the dynamic image so as to extract correct information from the record at an extremely low computation cost. A priori knowledge contains general properties such as 'the moving objects are dark and blob-like.', which is useful to design efficient procedures. However it lacks quantitative information about a particular record, such as locations, velocities, brightness levels, and shapes of objects. The analyzer, therefore, examines a small number of low resolution pictures of the record to collect such information and make a coarse model, a sketch, of the process, by which it can estimate which frame and what regions in it are worthy examining, or what type of a feature extractor is most effective at each point in the regions. Now, the system ma.k.es a plan, specifying (1) frames to be sampled, (2) regions to be examined, 'and (3) effective feature extractors to be applied. Since more accurate knowledge is acquired as a result of this plan-guided analysis of a frame, the coarse model is replaced with a fine and more reliable one, describing exact properties of the objects in the current frame, which is then used to make a more effective plan of sampling and analyzing next pictures. By iterating this process, planning, analyzing and updating, the system constructs a final model of the process, containing all information required.

The purpose of utilizing the plan is not only for minimizing the computation cost, but also for increasing reliability of extracted information. Thus,

the plan selects feature extractors and their parameters, considered to be most reliable, at each point. However, it is not easy to find the correct feature at every point in a noisy dynamic image such as a sequence of radiographic images. Optimization methods [9,10] are known as useful to search noisy pictures for curves or regions of specified properties. We can apply one of them to the dynamic image by embedding the properties of the object in a figure of merits. The optimization method, however, requires too much memory space and computing time, especially when a global shape property such as smoothness over a wide range is speicified, since we are forced to solve it as a high dimensional non-serial optimization problem. We, therefore, propose an improved method which utilizes an efficient search for the optimal sequence of linear segments instead of the already known inefficient search for the optimal series of pixels.

~.HARDWARE SYSTEM

Fig.l shows a block diagram of the hardware system. The computer used is aHP-2108A, a 16bit machine with 32.kw of memory, a disc (l5Mbytes), a printer/plotter, a storage tube display and three terminals under a multi-user operating system. A picture memory, 256kbytes 800nsec/2bytes cycle time, is connected to the computer. We utilize this memory as a flexible buffer for video input and output from/to a VTR (video tape recorder), a TV camera, and a color display. The memory is also used as high speed random access files of dynamic images; a software subsystem swaps picture data in a segment of the memory for necessary data in disc files, on the basis of first in first out [ 11 ].

Our system is provided with a computer controlled film projector, which selects a specified frame by sending 35mm film at a rate of 15 frames/sec. At present, the TV camera is used as the transducer of the projected image, which is transformed into a 256 by 256 6bit digital picture.

S. ANALYSIS OF MOTION PATTERNS

S.l ANALYSIS OF CINE-ANGIOORAMS

In recent years, people have studied computer analysis of a cine-angiogram, a cine film record of a radiographlE: image of a beating heart in which Xray opaque dye is intermittently injected through a catheter. Their primary interest is in measuring temporal change in the volume of the heart; the computer detects the internal surface of the heart in each frame, and calculates the volume by utilizing a three dimensional model of a heart.

In this paper, a more advanced analysis is described, which detects both internal and . external surfaces of the heart, and measures the spatial and temporal change in thickness of the heart wall, which gives us important measure of heart diseases.

The usual methods detect a boundary of a left ventricle by rather simple procedures; for example, an adaptive threshold method detects candidates points for the boundary, and then a simple statistical method examines their neighbors to fit line segments to the boundary [3]. A reason why such a level detecting method is applicable is that the film is taken and developed so as to show rather sharp contrast in gray values between the light :ventricle and the dark background. Such a photographic noise reduction technique, however, is not applicable to a cine-angiogram for analyzing a heart wall, which has usually intermediate gray values in our radiographic images. As a result, the pictures contain much noise, masking small gray value changes on or near the surfaces. Moreover, an accurate detection of both surfaces is needed, since small errors in the locations of points on a surface cause considerable errors in the thickness measurement of the heart wall.

Another important problem, which has been already discussed, .is the computation efficiency. The computer needs to examine a large number of high resolution pictures, because the heart wall occupies only a small fraction of each horizontal scan of the input pictures.

S.2 PLAN-GUIDED ANALYSIS OF W AU THICKNESS

We have developed a plan-guided analyzer for detecting both surfaces of a wall of a left ventricle and measuring temporal changes in thickness at each portion of the wall. The features of the system are as follows: (I) detection of edge points in the first frame is guided by a plan which specifies regions to be examined and promising feature extractors to be used, (2) smooth boundaries of the wall are obtained by an efficinet search method, and (3) another plan is utilized to analyze consecutive frames; it selects next frame to be sampled and guides the analyzer so as to examine it in a much more efficient manner than the first frame.

The analysis is divided into the following five phases.

• (l) planning of feature extraction of first frame.
• search for smooth boundaries.
• selection of next sampling frame.
• ( 4) analysis of consecutive frames.
• measurement of thickness.

S.S INPUT PICTl!RES

Input of the system is a sequence of Xray images of a left ventricular chamber recorded on 35mm cine film at a rate of 60 frames/sec; thus, a record of one beating cycle contains about 50 frames. A frame is converted into a 256 by 256 6bit digital picture. Fig.2 shows an example and the result of applying a simple 3 by 3 gradient operator to it. The picture contains much noise, especially significant non-uniformity of gray values is observed in the ventricular chamber near the internal surface, where muscles and tissues attached on the surface generate much noise.

Contrast of gray values between both sides of each surface is very low, since the gray values in the wall gradually increase, as the mean, with the distance from the external surface.

S.4 PLANNING OF FE.A TUR£ EXTRACTION

Because of the low picture . quality of a cine-angiogram, such as low contrast and much noise, a level detecting method cannot reliably find a heart wall. If we apply a gradient operator to a small area, say a 3 by 3 window, around every point in the picture, then the enhanced noise by the operator masks the boundaries of the wall. In order to reliably detect edge points in a noisy picture, edge features should be extracted from averaged gray values in some larger local areas. Since the heart wall is a narrow region, a group of paired rectangular areas of different directions shown in Fig.3 are used as the smoothing areas. A pair of local areas, of which absolute difference of average gray values is largest in the group, are selected at every point in the picture. Each selected pair gives reliable features of the edge at that point; the edge strength and direction are decided from the already computed maximum difference and the direction of the selected areas. When this procedure is applied to a point on the boundary of the wall, it automatically selects parallelly directed areas to the boundary, therefore its output is less sensitive to the noise and is not blurred by the averaging.

This method, however, requires too much time. If differences of averaged gray values in a pait of 10 by 1 areas are computed and compared for 12 different directions at every point in a 256 by 256 picture, then a minicomputer HP-2108A spends about one hour for the computation.

We, therfore, have developed a plan-guided edge detection method to shorten the computation time. The system first compresses a 256 by 256 original picture into a small picture of 64 by 64 picture. Each point in the small picture is the averaged value of the 16 points in a 4x4 neighborhoods in the original picture. Applying a simple 3 by 3 gradient operator to every point in the compressed picture and thresholding it, the system decides ( 1) analysis regions, regions to be examined further, and (2) an approximate direction of an edge at each point in them. Fig.4 (a) shows edges detected in the compressed picture by the gradient operator. This picture is less noisy than Fig.2 (b), the result of applying the same operator to the original picture, because of noise reduction by the averaging in the windows. A plan of the next edge detection is described as a map containing the analysis region and the directions of edges in them, as shown in Fig.4 (b). The analyzer utilizes this map to efficiently find features; an edge feature at each point in the analysis regions is detected by a pair of rectanglar areas perpendicular to the direction. Since the analysis regions occupy 1/3 of the input picture (we could considerably reduce them by using a higher threshold value or utilizing more heuristics) and only one selected edge direction from 12 variations is· examined at each point, the computation for edge finding by this method is (1/3)x(l/12)=1/36 of that without the plan. The gradient operation to each point in the compressed image is iterated about 4000 times, 1/16 of that required for the original picture, and the operation is much simpler, therefore its computation cost is also inexpensive. The result of applying the plan-guided edge detecting method to Fig.2 (a) is shown in Fig.S, which seems much better than Fig.2 (b).

3.5 EFFICE.NT SEARCH FOR SMOOTH BOUNDARIES

Next phase to the edge detection is to recover the outer and inner boundaries of the heart wall in the analysis regions. Since the edge picture still contains considerable noise, and since precise detection of the boundaries is needed, usual curve followers are not applicable. Optimization methods are known as useful to find a curve of specified properties in a noisy picture. They embed the property into a figure of merit and search for the curve as a sequence of consecutive points which minimize the figure of merit, by a dynamic programming technique [9] or a heuristic method [10]. Many practical examples, and also this analysis of the heart wall, need to find smooth curves over a wide range, since smalJ unevenness on a detected curve is considered as statistically meaningless.

In order to find a smooth curve hidden in noise, the usual methods embed a property of smoothness of a curve into a part of the figure of merit as a sum of a curvature at each point. If the smoothness over a wide range is embedded, then we are forced to sove it as a high dimensional non-serial optimization problem, which requires too much computing time and memory space.

A different approach has been studied to avoid this difficulty [12]. Since the curve to be detected is smooth, we can approximate it with a sequence of linear segments. We embed the smoothness over a wide range of a sequence of linear segments connecting points x · . X1 , ... , Xn into a figure of merit C( X1 , Xl , ... , Xn ) as

Where e( Xm , Xn ) is a mean of edge strength along the segment connecting Xm and Xn , 0 ( Xm , Xn ) is the inclination angle of the segment, and k1 is a constant.

Now, we apply this method to detection of the wall boundaries in the edge picture. Starting points of the search are decided from a priori knowledge about the boundaries; the both boundaries have directions between 0 ° and 90 ° at the upper part of the ventricle. A sequence of 10 successive edge points on a ridg~ of such a direction are selected as starting points.

We apply a heuristic search to find a solution of this optimization problem, and the results are successful to many input pictures. The search, however, sometimes fails, when the outer and inner boundaries are close together at the end of the expansion period of the ventricle. Since the edge strength on the inner boundary is much larger than that of the outer one, a search for the external surface happens to cross the wall and follow the inner boundary. In order to avoid this difficulty, we utilize another knowledge that gray values on the outer boundary are darker than those on the inner one. Thus, we use a figure of merit evaluating edge strength, smoothness, and gray values, as follows.

Where g( Xm , Xn ) is the mean gray value of points on the line segment connecting Xm and Xn , G is a mean gray value of a group of candidates for starting points, and k1 , k2 are constants. Fig.S shows an example of results obtained by this method. The detected bounda.rles are arranged into a model which guides the selection and analysis of consecutive frames.

:S.tl SELECTION OF FRAMES FOR ANALYSIS

In order to reduce computation for the consecutive frames, we effectively utilize the model obtained from the result of the previous analysis. First of all, narrow analysis regions are selected on the both sides of the detected boundaries, as shown in Fig.6. At present, the width of the regions is set at a length of 7 pixels. We can save the computation by examining only picture data in these regions, which are much smaller than those used for the analysis of the first frame .

As mentioned before, the system should select frames worthy examining from a great number of frames in the record. Because of intermittent movement of the heart, it is reasonable that the analyzer skips over consecutive frames in which little changes from the previously analyzed one are observed. We use a simple temporal differnce method to measure the degrees of changes. If the wall boundaries move to some extent, then there exist significant changes in the analysis regions. Sums of a gray value change at each point in the regions from that of the previously analyzed one are computed for a coming input frame, and if at least one of the sums is greater than a threshold, then the frame is analyzed, else it is skipped. Utilizing this criterion for sampling, the system analyzes about l/3 of frames in a record as a mean, and only 1/16 at the end of the contraction or expansion period, when a wall shows very slow movement.

:S. 7 ANALYSIS OF CONSECUTIVE· FRAMES

Edge detection and search for the boundaries in the sampled frame is guided by the model of the previously analyzed frame. The analyzer measures an edge component parallel to the nearest boundary at every point in the analysis regions. Then it searches each analysis region for a boundary using the figure of merit of (2).

:S.8 MEASUREMENT OF WALL THICKNESS

In order to measure the dynamic behavior of the heart wall, we establish a correspondence between portions of the wall in successvely analyzed frames . Those areas having tissues or mustles on the Jnternal surface of the heart are useful for finding the correspondence. Therefore, we first determine such areas having characteristic gray-level distribution along the internal boundary in the first frame. The variance of gray levels· in the local area of 7x7 points is examined at every point along the internal boundary. Then, the areas where the variance of gray levels in it is the local maxima in its neighborhood and is larger than a certain threshold are selected as the areas to make correspondence.

The selected areas are then matched to those along the internal boundary in the next analyzed frame by a simple correlation method. The thickness of the heart wall is measured at these corresponded points in each frame. Fig. 7 shows the result of thickness measurement at those corresponded points of the internal boundary between the frames.

4. CONCLUSION

The plan-guided analysis is very effective to extract correct information from noisy dynamic images such the cine-angiogram. The system is efficient since plans select (I) frames to be sampled, (2) analysis regions of small areas, and (3) directions of edges to be detected. We have also developed a new efficient search method for a smooth curve in a noisy picture. The computation time was about 6 minutes for lst frame, 14 seconds for analyzing a next sampled frame, and less than 1 second for deciding whether an input frame is skipped or not. We believe this approach is essential for analysis of high resolution dynamic images.

REFERENCE

• [ 1] W. N. Martin and J. Aggarwal : Dynamic Scene Analysis, Computer Graphics and Image Processing, 7, pp356-374, No.3, 1978.
• H. H. Nagel : Analysis for Image Sequences, Proc. 4th Intern. Joint Conf. on Pattern Recongnition, ppl86-211, 1978.
• T. Kaneko and P. Mancini : Straight-line Approximation for the Boundary of the Left Venticular Chamber from a Cardiac Cineangiogram, IEEE Trans. on BME 20, pp413-416, Nov. 1973.
• L. P. Jong and C. J. Slager: Automatic Detection of the Left Venticular Outline in Angiographs Using Television Signal Processing Technique, IEEE Trans. on BME 22, pp230-237, May 1975.
• J. 0. Greaves : The Software Structure for Reduction of Quantized Video Data of Movi ng Organisms, Proc. of IEEE, 63, ppl415- 1425, Oct. 1975.
• Y. Ariki, T. Kanade and T. Sakai : An Interactive Image Modeling and Tracing System for Moving Pictures, /!roc. 4th Intern. Joint Conf. on Pattern Recongnitlon, pp681-685, 1978.
• M. Kelly : Visual Identification of People by Computer, Artificial Intelligence Project Memo No. 121, Stanford Univ., July, 1970.
• C. A. Harlow and S. A. Eisenbis : The Analysis of Radiographic Images, IEEE Trans. on Comput. 22, pp678-689, July, 1973.
• U. Montanari : On the Optimal Detection of Curves in Noisy Pictures, Commun. ACM., 14, pp335-345, May 1971.
• [ 10] A. Martelli : An Application of Heuristic Search Methods to Edge and Contour Detection, Commun. ACM., 19, pp73-83, Feb. 1976.
• [ 11] M. Yachida et al. : An Interactive System for Digital Processing of Moving Images, Trans. Inst. Elect. Commun. Engineers of Japan, 0-56, Oct. 1978 (in Japanese).
• [ 12] M. Yachida, M. Ikeda and S. Tsuji : A Knowledge Directed Line Finder for Analysis of Complex Scenes, 6th IJCAI.