Tracking Holes: Using Animation to Visualize Absent Features
Tracking Holes:
Extensive work has been done in segmenting images and in identifying and tracking features through successive frames (Arnaud et al. 1992; Samtaney et al. 1994). A more difficult problem arises when the item of interest is the absence of a feature rather than the presence of one. This type of application requires a higher level synthesis of information (Silver and Zabusky, 1993).
The problem considered here is a combustion system in which a flame front forms patterns of cells. Cells in the front may hop, ratchet, rotate or move in disorganized ways depending on the values of the driving parameters (Elhamdi et al. 1993). Image processing is useful for quantifying information about the motion and in assisting viewers in understanding the behavior of these modes.
The combustion experiment is videotaped from overhead and individual frames of videotape are digitized at a rate of 30 frames per second. Each frame is converted to a raster file for later analysis. Four consecutive frames of digitized video are shown in Figure 1. The mode shown in Figure 1 is called a hopping mode because the three inner cells appear to hop among four positions. The outer ring of cells remains approximately stationary.
The combustion experiment exhibits a variety of hopping modes (Gorman et al. 1994) in which different rings of cells hop in various ways. In this paper we use the hopping mode as a vehicle for illustrating the importance of visualization in understanding the behavior of absent objects or objects which are not visible. For the particular mode shown in Figure 1, the missing object is the hole or fourth position.
Figure 2 shows a snapshot of trackx during the tracking of a hopping mode. The left window displays an individual frame of videotape after it has been digitized and segmented to identify the individual cells. The right window displays a time-lapse of the cell center positions. Observe that the hopping cell centers appear to fill a toroidal band and do not exhibit any readily discernible pattern.
From the tracking information we can determine cell center positions, velocities, and areas. Figure 3 shows a plot of the angular displacements of the three hopping cells. The flat portions of the curves correspond to times at which the cells are stationary, while the steep portions indicate hopping. Each cell speeds up and slows down over the course of a single rotation. All of the cells behave similarly, but their phases are shifted from those of their neighbors.
The best linear fits for these curves have the same slopes, indicating all three cells have the same average angular velocity. The cell angular displacement and velocity information does not explain the toroidal track of the cell centers shown in Figure 2. Tracking is insufficient for systems with such complex motion, and high level analysis techniques are needed to illuminate the behavior.
Cells expand in size while they are hopping and undergo a local minimum in their area as a function of frame number while they are stationary. Unfortunately, cells also appear to have a minimum in area when they just start hopping or almost are finished hopping. Another criterion is required to determine whether or not a cell is stationary and to determine the positions of slots.
Careful observation of the motion shows that a stationary cell waits for the cell behind to reach its slot before it starts hopping itself. In other words, there is at least one frame in which two consecutive slots are occupied by two cells. It is sufficient to extract these frames to determine slot positions. We observe that in these frames, the areas of two stationary cells reach a minimum. We call this the minimum area invariant.
Figure 4 shows how the areas of three hopping cells vary as a function of frame number. In the frames that are pointed by arrows, two cells reach their minimum areas. Cell center positions of these frames can be extracted from trackx data to determine the slot positions used in visualization.
Since the slots are not discernible by direct viewing, we have developed several ways of assisting the viewer in visualizing this behavior. The next section describes static approaches in which the pattern of hopping is shown by space-time diagrams and other geometric depictions of behavior. Section V presents visualizationswhich use computer animation.
In a state-count display, state information for one frame is represented by a vertical bar of constant height which is color-coded to show how many cells are in each state. Figure 5 is a snapshot of the state-count display for a hopping mode. The display consists of 257 vertical bars reflecting state information for frames 0 through 256. The number of cells is displayed on the vertical axis, and frame number is displayed on the horizontal axis. The frame number increases as time increases. Each vertical bar is colored in light grey and dark grey. The dark grey portion represents the stationary state, and the light grey portion represents the hopping state. For example, if there are two cells hopping and one cell stationary, two thirds of the vertical bar is light grey, and one third of the bar is dark grey. We choose to always display the dark grey color at the bottom, and the light grey color on the top.
Figure5 shows that in each frame, at least one cell is hopping and one cell is stationary. A third cell may either be hopping or stationary. The number of frames in which two cells are stationary has an uneven distribution. In some of the frames, a second cell stays in the stationary state for a short time (as indicated by the skinny dark grey vertical bars). In some other frames, a second cell stays in the stationary state for a relatively longer time (as indicated by the thicker dark grey vertical bars). The two arrows on the top of Figure 5 indicate an interval of frames in which a second cell stays in the stationary state for a longer time.
A Gantt-chart display is an alternative static visualization of cell state information. Instead of showing the total number of cells in each of the two states,the Gantt-chart display depicts the state information of individual cells separately.
Figure 6 is a snapshot of a Gantt-chart display. The activity of an individual cell is represented by a horizontal bar chart in which the color of the bar indicates the state of the corresponding cell as a function of frame number. The activity of cell 0 is reflected by the horizontal bar at the bottom of the graph. Cell 1 is in the middle, and cell 2 is on the top. The same color scheme is used to represent state information as in the state-count display of Figure 5. The Gantt-chart display reveals that the number of consecutive frames a cell stays in a particular state is distributed unevenly.
Figure 6 shows that cells start and finish hopping in order. Most of the time the cell behind starts hopping before the front cell finishes hopping. We refer to this as hopping in partial order. Occasionally, the rear cell starts hopping after the front cell finishes hopping.This is called hopping in complete order. The arrows in Figure 6 indicate a hopping sequence which is completely ordered. As pointed by the arrow at the bottom, while cell 0 is hopping, the other two cells are stationary. After cell 0 finishes hopping, cell 1 starts hopping, and cells 0 and 2 are stationary. Cell 2 starts hopping after cell 1 finishes hopping. In this frame sequence, two cells stay in their slots while the third cell is hopping. These frames correspond to the thicker dark grey bar indicated by arrows in Figure 5.
Before using the Gantt-chart display, we had the visual impression that cells were hopping in order, but we were unaware of the ordering phenomenon described above. The Gantt-chart confirmed our visual impression but also revealed the additional structure.
Another static visualization is a geometric summary of each individual cell's states, called a Kiviat diagram. Each cell is represented as a spoke on a wheel. The recent average fraction of time the cell spends in the stationary state determines a point on its spoke. The more time a cell spends in the stationary state, the greater the distance between this point and the hub of the wheel. The points on the spokes are connected to form a polygon. The symmetry of the resulting polygon provides a visual model of the symmetry of the underlying process.
An example of a Kiviat diagram for the hopping cells is shown in Figure 7. Since there are three cells, the three points on the spokes form a triangle. There are two triangles in each of the snapshots in Figure 7. The inner triangle depicts the most recent average fraction of time that the three cells spend in the stationary state, while the outer triangle represents the maximum average fraction of time spent in the stationary state so far.
Snapshots (a) and (c) of Figure 7 show a frame interval in which cell 0 spent less time in the stationary state than the other two cells. In frame (b), cell 0 spent the most time in the stationary state followed by cell 1. Cell 2 spent the least time in the stationary state. In frame (d), cell 0 spent the most time in the stationary state, and the other two cells spent less time in the stationary state. In all four frames, the outer triangles are symmetric. Three vertices of each outer triangle are located slightly more than midway between the hub and the outer rim of the wheel. On average the three cells spent about 50 percent of the time in the stationary state and the other 50 percent of the time hopping.
The pattern reflected by the Kiviat diagram had not been discovered by direct observation of the raw images, the tracked images, or any static display mentioned above.
Animation is the presentation of a series of images to give the impression of motion (Pepke, 1995). By analyzing the original images, the designer comes up with a model to describe the object's dynamic behavior and a meaningful way of representing the object using a new and probably more straightforward model. When the resulting images change quickly enough, the human visual system integrates them into continuous motion. The object under study may be either visible or invisible in the original images.
Computer animation provides a tool for visualizing behavior as it changes in time and space, and it helps viewers understand the pattern of slot motion. As mentioned earlier, the slots are the spatial positions in which cells are in the stationary state. They are not directly visible in the original images or even in the tracked images. The minimum area invariant is used to classify the cells by their states, and the tracking information is filtered to extract the slot positions.
Slot motion of the hopping mode has its own characteristics. Direct observation of the original images gives the visual impression that three cells hop among four slots. Careful analysis of the center positions reveals that the slots are approximately arranged on the corners of a rectangle and that the cells move along the edges of the rectangle. The motion is complicated by the fact that the rectangle itself is moving. Figure 8 illustrates this behavior in a sequence of ten consecutive frames.
Our goal was to show how slots move among the four corners of the rectangle and the motion of the rectangle itself. Observe that when a cell is in the process of hopping, its front neighbor stays in its slot for the entire hop, while its rear neighbor stays in its slot for a few frames and then starts hopping. At certain points during each rotation, one cell is about to leave a slot while its neighbor is entering a slot. At these points during the cycle, two cells are in slots. We use the two corners currently occupied by the two stationary cells to represent the entire rectangle. Because the rectangle has reflexive symmetry about the center of the image, two corners are sufficient to determine the position of the entire rectangle and hence the four slot positions.
In frames where only one cell is stationary at a corner, the other two cells are moving along the edges of the rectangle towards their next corner positions. In this case the rectangle cannot be as easily determined from cell positions. However, since the single stationary cell remains in place until a few frames after one of its neighbors reaches a corner, the frames in which two cells are stationary convey complete information about slot position.
Our animation program is based on the POLKA parallel programming animation system (Stasko and Kraemer, 1993). The POLKA Animation Designer's Package implements an animation design toolkit in C++. The package provides a library of simple objects with which to populate a scene and methods for moving and manipulating these objects. We model the underlying system in terms of these objects. The POLKA Animator is event-driven, and the user program schedules changes in state as events to be executed by the POLKA Animator. The user can specify any number of views of the animation which are display windows controlled by the Animator.
Four snapshots of an animation are shown in Figure 9. The animation visualizes how the locations of the cells of minimum area propagate as the experiment evolves. In each snapshot, the outer cells are represented by black lines connecting the center-of-mass of the image. These lines provide a grid upon which the user can visualize the relative positions of the slots.
The animation shows the evolution of the rectangle by extracting only the frames with two stationary cells. These cells are displayed as circles and are connected to help the eye visualize the rectangle and the slot positions. In order to preserve some of the visual history of the motion, a trace of the previous position of the end of the rectangle remains in the display for 20 animation frames. The historical traces gradually fade from view so that the eye gets a visual impression of the motion during the running of the animation.
The minimum area invariant is
specific to the hopping problem, but the techniques are generally
applicable to problems where objects can be classified by a finite
set of state values.
Our animations
used symmetry to help the eye infer hole locations from the
positions of the cells in the slots. Animations tend to be
problem-specific, but they allow more flexibility and creativity inthe design of visual models which convey the essence of the
phenomenon.
MPEG movies of these animations
are
available on World Wide Web
site
[2] M. el-Hamdi, M. Gorman and K. A. Robbins, Deterministic chaos in laminar premixed flames: Experimental classification of chaotic dynamics, Combustion Science & Tech., 94 (1993) p. 87-101.
[3] M. Gorman, M. el-Hamdi and K. A. Robbins, Hopping motion in ordered states of cellular flames, Combustion Science \& Tech., 98 (1994) p. 71-78.
[4] M. T. Heath, Visualizing the performance of parallel programs, IEEE Software, 8:4 (1991) p. 29-39.
[5] M. T. Heath, A. D. Malony and D. T. Rover, Parallel performance visualization: From practice to theory, IEEE Parallel and Distributed Technology, 3:4 (1995) p. 44-60.
[6] K. Konstatinides and J. Rasure, The Khoros software development environment for image and signal processing, IEEE Trans on Image Processing, 3:3 (1994) p. 243-252.
[7] Eric Pepke, Animation and the examination of behavior over time, Computer Visualization, CRC Press, Boca Raton, Ann Arbor, London, Tokyo, 1995.
[8] K. A. Robbins and M. Gorman, A case study using image processing and computer animation to analyze spatial and temporal structure in pattern formation, University of Texas at San Antonio Technical Report 96-2, 1996.
[9] R. Samtaney, D. Silver, N. Zabusky and J. Cao, Visualizing features and tracking their evolution, Computer,27:7 (1994) p. 20-27.
[10] D. Silver and N. Zabusky, Quantifying visualizations for reduced modeling in nonlinear science: Extracting structures from data sets, J. Visual Commun. and Image Representation, 4:1 (1993) p. 46-61.
[11] J. T. Stasko and E. Kraemer, A methodology for building application-specific visualizations of parallel programs, J. Parallel and Distr. Computing, 18:2 (1993) p. 248-264.
