Analyzing Oriented Patterns

Oriented patterns, such as those produced by propagation, accretion, <>r deformation, ore common in nature and therefore an important class for visual analysis. Our approach to understanding such patterns is to decompose them into two parts: a flow field, describing the direction of anisotropy, and the residual pattern obtained by describing the image in a coordinate system built, from the flow field. We develop a method for the local estimation of anisotropy and a method for combining the estimates to construct a flow coordinate system. Several examples of the use of these methods are presented. These included the use of the (low coordinates to provide preferred directions for edge detection, detection of anomalies, fitting simple models to the straightened pattern, and detecting singularities in the flow field. I I n t r o d u c t i o n A central focus in recent computational vision has been the decomposition of the original intensity image into intrinsic images (Horn 1977, Barrow & Tenenbaum, 1978; Marr, 1982), representing such properties as depth, reflectance, and illuminance. These intrinsic properties are believed to be more meaningful than image intensity because they describe basic independent constituents of the image formation process. Thus, for example, in separating shape from illumination, we can recognize an invaxiance of shape regardless of changing illumination. The advantages of decomposing what we see into its more-orless independent parts extends beyond the image formation process to the shapes and patterns on which that process operates. For instance, decomposing a bent rod into a straight rod and a bending transformation reveals the similarity between a bent rod and one that hasn't been bent, or some other solid that's been bent the same way (Barr, 1984). Just as we need to understand the image-forming process to decompose an image into intrinsic images, we need to understand the processes that generate patterns to decompose them into their intrinsic parts. But, whde there is only one imageforming process, a staggering variety of processes shape and color the world around us. Our only hope of dealing with this complexity is to begin with some basic pattern classes that recur in nature, and understand how to decompose and describe them. One such class are oriented patterns, notably those produced by propagation, accretion, or deformation. To understand an oriented pattern we must be able to say (l) what is propagating, accreting, or deforming, and (2) which way and how much. More precisely, we must estimate everywhere the direction and magnitude of anistropy (which we will call the flow field,) and describe the residual pattern, independent of that field. Why this decomposition leads to simpler, more regular descriptions is best illustrated by example: • A typical oriented pattern created by propagation is the streaked trail left by a paint brush dipped in variegated paint. The flow field describes the trajectory of the brush, the residual pattern depending only on the distribution of paint on the brush. • Accretion typically results in laminar structures, such as wood grain. Here, the flow field gives isochrones (the moving accretion boundary,) and the residual pattern describes the change in color or brightness of the accreting material over time. • If an isotropic body is deformed, the flow field principally describes the bending and stretching it has undergone, while the residual pattern describes the undeformed body. In all these cases, separate descriptions of the flow field and the residual pattern are appropriate because they describe different processes. The path of propagation for many physical processes is controlled by very different mechanisms than control the coloration of the trail left behind. Similarly, the mechanisms which control the shape of an accretion boundary are frequently unrelated to the processes controlling the color of the accreted material. Finally, the forces which deform a piece of material are often completely unrelated to the process which created the piece of material in the first place By separately describing these processes, we can create descriptions of the whole which are often simpler than is possible without the separation because each of the pieces may have different regularities. Orientation selective mechanisms have been extensively stud ied by physiologists since Ilubel and Wiesel's (1962) discovery of orientation selective cells in mammalian visual cortex (see Schiller et. al. (1976) for a comprehensive example). There has also been considerable interest among psychologists in the perception of oriented patterns, particularly dot patterns (Glass, 1969). Only recently have the computational issues involved received attention. Stevens (1978) examined the groupmg of tokens in Glass patterns based on orientation. While successful with Glass patterns, his methods were never extended to natural imagery. Zucker (1983) investigated the estimation of orientation by combining the outputs of linear operators. Zucker's estimation method for what he calls "Type II" patterns, while differing in many respects, is quite close in spirit to our own. Little progress has been made in using local orientation estimates to interpret patterns, perhaps because reliable estimates have proved difficult to obtain. The key difference between our work and earlier efforts lies in our use of the flow field to build a natural coordinate system for analyzing the pattern. The remainder of the paper covers the computation of the flow field by local estimation of orientation, the construction of a coordinate system using the flow field, and some examples of analysis and description using flow coordinates. In Section 2 we develop an estimator for the local flow direction, that direction in which intensity tends to vary most slowly M. Kass and A. Witkin 945 due to an underlying anisotropic process. The estimator, based on the direction of least spatial variance in the output of an ori­ ented filter, is computed as follows: After initial filtering, the intensity gradient is measured at each point in the image. The gradient angle, 0, is then doubled (by treating the gradient vec­ tors as complex numbers and squaring them) to map directions differing by π into a single direction. The transformed vectors are then summed over a weighted neighborhood around the point of interest. The angle of the summed vector is halved, undoing the previous transformation. This gives an estimate for the direction of greatest variance, which is then rotated by π/2 to yield the flow direction. In section 3, we describe the construction and use of coordi­ nate systems based on the result of local estimation. Integral curves in the flow field are computed numerically, by following the estimated vectors from point to point. A coordinate system is constructed in which the integral curves are parameter lines. Transforming the image into these "flow coordinates" straight­ ens the pattern, removing the effects of changing orientation. We present several examples of analysis and description of the flow field and the straightened pattern. I I F l o w C o m p u t a t i o n For intensity patterns created by anisotropic processes such as propagation, accretion, or deformation, variation in the flow direction is much slower than variation in the perpendicular di­ rection. Anisotropy in such patterns will be evident in the local power spectrum. The high frequency energy will tend to cluster along the line in the Fourier domain perpendicular to the flow orientation. A simple way to detect this clustering is to sum the energy in an appropriate region of the power spectrum and examine how the sum is affected by rotations. This can be done by examining the energy in the output of an appropriate orientation-selective linear filter. The orientation at which the energy is maximal can be expected to be perpendicular to the flow orientation. Selection of the filter involves a number of tradeoffs. Very low spatial frequencies are affected more strongly by illumina­ tion effects than surface coloration, so they are inappropriate for measuring textural anisotropy. Very high spatial frequencies are sensitive to noise and aliasing effects so they too are inappropri­ ate. Hence some type of roughly bandpass filtering is required. The orientation specificity of the filter is also quite important If the filter is too orientation-specific then a large spatial neighbor­ hood will be required in order to make a reliable measurement of the energy. Conversely, if the filter responds over a wide range of orientations then it will be difficult to localize the orientation very accurately. Thus there is a trade-off between angularand spatialresolution. The filter is bandpass with passband determined by and a2In our experience, ratios of the sigmas in the range of 2.0 to 10.0 work well. The orientation specificity or tuning curve is provided by the cosine dependence of the filter on 0. This appears to strike a reasonable balance between angularand spatialresolutions for the range of patterns we have examined. The filter's power spectrum is shown in figure 1 The cosine orientation tuning-curve of the filter has some un­ usually good properties for computing the filter output at dif­ ferent orientations. The impulse response S(xyy) of the filter 946 M. Kass and A. Witkin One might be tempted to believe that smoothing the gradient vectors G(x,y) would be nearly as good a measure of anisotropy as smoothing the rotated squared gradient vectors J(x,y). This is emphatically not the case Consider an intensity ridge such as /(x,y) = exp(x). The gradient vectors on the left halfplane all point to the right and the gradient vectors on the right half-plane all point to the left. Adding them together results in cancellation. By contrast, if they are first rotated to form the J vectors, they reinforce. The types of oriented patterns we are concerned with of