(defun ileaf::r (data)<#0a> (tell *load-object* mid:put-data 'ileaf::saved-data<#0a> data)))(ileaf::r '(:il-hleaf-uid-list nil)<#0a> )"> ", Top Margin = 0.0266667 Inches, Bottom Margin = 0.0266667 Inches, Font = F3@Z7@Lnl@i*, Alt Font = F3@Z7@Lnl, Line Spacing = 1.162 lines, Left Tab = 0/1*3 Inches, Composition = Optimum> <"|:bullet", Hidden = yes, Font = F3@i*, Alt Font = F3@Z7@Lnl, Subcomponent = yes, Contents = Shared>S <"|:list", Hidden = yes, Font = F3@i*, Alt Font = F3@Z7@Lnl, Subcomponent = yes, Contents = Shared> S ', Superscript = yes, Diagram = V11, (g9,1,0, (T15,1,12,,0,0,5,127,5,7,127,1,0,2, <"micro:ftnote", Hidden = yes> . ) (E16,0,0,,5,1,1,0.0533333,1,15,0,0,1,0,0,0,1,5,127,7,0,0,7,0,1,1,0.0666667,0.06 66667,6,6,0,0.0666667,6))> <"micro:ftnote", Hidden = yes> ) (E16,0,0,,5,1,1,0.0533333,1,15,0,0,1,-0.0266667,-0.0266667,0,1,5,127,7,0,0,7,0, 1,1,0.0666667,0.0666667,6,6,0,0.0666667,6))> <"para"> <|,"1"> <"Title", Font = F42@Lam> Real-time Single-workstation Obstacle Avoidance Using Only Wide-field Flow Divergence <"authors"> Ted Camus . <"Footnote", Bottom Margin = 0.000 inches, Right Margin = 0.249 inches> . This research was conducted while the first author held a National Research Council Research Associateship at NIST. Current address: Sensar, 121 Whittendale Drive, Moorestown, NJ 08057. email: tedcamus@sensar.com ) (E16,0,0,,5,1,1,0.0533333,1,15,0,0,1,0,0,0,1,5,127,7,0,0,7,0,1,1,0.0666667,0.06 66667,6,6,0,0.0666667,6))> <"Normal", Top Margin = 0.000 inches, Bottom Margin = 0.140 inches, Left Margin = 0.000 inches, Right Margin = 0.000 inches, First Indent = 0.000 inches, Alignment = Center, Font = F7@Lam, Line Spacing = 1.309 lines> , David Coombs, Martin Herman . <"Footnote", Right Margin = 0.249 inches> Current address: NIST, Information Access and User Interfaces Division, 100 Bureau Drive Stop 8940, Gaithersburg MD 20899-8940 ) (E16,0,0,,5,1,1,0.0533333,1,15,0,0,1,0,0,0,1,5,127,7,0,0,7,0,1,1,0.0666667,0.06 66667,6,6,0,0.0666667,6))> <"Normal", Top Margin = 0.000 inches, Bottom Margin = 0.140 inches, Left Margin = 0.000 inches, Right Margin = 0.000 inches, First Indent = 0.000 inches, Alignment = Center, Font = F7@Lam, Line Spacing = 1.309 lines> , Tsai-Hong Hong <"Normal", Top Margin = 0.000 inches, Bottom Margin = 0.140 inches, Left Margin = 0.000 inches, Right Margin = 0.000 inches, First Indent = 0.000 inches, Alignment = Left, Font = F58@Lam, Line Spacing = 1.309 lines> tedcamus@sensar.com, {dcoombs,mherman,thong}@nist.gov <"Normal", Top Margin = 0.000 inches, Bottom Margin = 0.140 inches, Left Margin = 0.000 inches, Right Margin = 0.000 inches, First Indent = 0.000 inches, Alignment = Left, Font = F7@Lam, Line Spacing = 1.309 lines> National Institute of Standards and Technology <"Normal", Top Margin = 0.000 inches, Bottom Margin = 0.140 inches, Left Margin = 0.000 inches, Right Margin = 0.000 inches, First Indent = 0.000 inches, Alignment = Left, Font = F7@Lam, Line Spacing = 1.309 lines> Intelligent Systems Division <"Normal", Top Margin = 0.000 inches, Bottom Margin = 0.140 inches, Left Margin = 0.000 inches, Right Margin = 0.000 inches, First Indent = 0.000 inches, Alignment = Center, Font = F7@Lam, Line Spacing = 1.309 lines> Building 220 (Metrology) Room B-124 <"Normal", Top Margin = 0.000 inches, Bottom Margin = 0.140 inches, Left Margin = 0.000 inches, Right Margin = 0.000 inches, First Indent = 0.000 inches, Alignment = Center, Font = F7@Lam, Line Spacing = 1.309 lines> 100 Bureau Dr Stop 8230 <"Normal", Top Margin = 0.000 inches, Bottom Margin = 0.140 inches, Left Margin = 0.000 inches, Right Margin = 0.000 inches, First Indent = 0.000 inches, Alignment = Left, Font = F7@Lam, Line Spacing = 1.309 lines> Gaithersburg MD 20899-8230 <"Abstract", Bottom Margin = 0.194 inches, Right Margin = 0.196 inches, Font = F15@Lam, Line Spacing = 1.166 lines> ABSTRACT <"Abstract", Bottom Margin = 0.194 inches, Right Margin = 0.196 inches, Alignment = Justified, Font = F15@Lam, Line Spacing = 1.166 lines> This paper describes a real-time robot vision system which uses only the divergence of the optical flow field for both steering control and collision detection. The robot has wandered about the lab at 20 cm/s for as long as 26 minutes without collision.The entire system is implemented on a single ordinary UNIX workstation without the benefit of real-time operating system support. Dense optical flow data are calculated in real-time across the entire wide-angle image. The divergence of this optical flow field is calculated everywhere and used to control steering and collision-avoidance behavior. Divergence alone has proven sufficient for steering past objects and detecting imminent collision. The major contribution is the demonstration of a simple, robust minimal system that u ses flow-derived measures to control steering and speed to avoid collision in real time for extended periods. Such a system can be embedded in a general, multi-leve l perception/control system. <"section", Top Margin = 0.000 inches, Font = F3@Lam, Line Spacing = 1.750 lines> 1Introduction <"body", Bottom Margin = 0.000 inches, Line Spacing = 1.750 lines> Mobile robots that drive at reasonable speeds (e.g., 20 cm/s indoors) must robustly sense and avoid obstacles in real time. Image motion provides powerful cues for understanding scene structure. Divergence of op tical flow (the sum of optical flow derivatives in two perpendicular directions) is theoretically unaffected by camera rotation, so it gives a robust measure of scene structure for a moving observer. The robot system described here uses flow divergence to steer around obstacles while it attempts to achieve a goal (which for now is simply to drive straight ahead). When the obstacle cannot be avoided by changes in steering alone, the divergence data warn the robot of the impending collision. The robot stops, turns, and resumes wandering straight ahead in the new direction. These integrated behaviors have driven the robot around the lab at 20 cm/s for as long as 26 minutes without collision. Because this wandering behavior is already a real-time capability, there is promise that future increases in computational power will fuel development of both increasingly robust basic skills and additional behaviors for robots. <"body", Line Spacing = 1.750 lines> The simplicity of the system improves robustness and makes the system easier to extend. The system uses only a single framegra bber, a single processor, a single image stream, and a single low-level percept for all control functions. Simple robust filters are chosen in lieu of complex filters that require sensitive system modeling and synchronization. These filters are able to ignore momentary noise and artifacts that result from system module interactions, which enables modules to cooperate without delicate synchronization. <"body", Line Spacing = 1.750 lines> In addition, the obstacle avoidance system is extensible. Egocentric hazard maps are derived from divergence data, goals, and steering history. A composite hazard map is used to steer the vehicle. This design supports the use of multiple cues, which can be incorporated with additional hazard maps. Add itional redundant or complementary sensing modes can be exploited by the existing framework. <"body", Line Spacing = 1.750 lines> Our approach achieves real-time intelligent behavior by using minimalist visually-derived representations. In such representat ions, a minimal amount of information required to achieve the given task is extracted from the imagery [2][4]. The representations contain only task-relevant information (i.e., relevant to obstacle avoidance), and the information is only represented in 2-D image coordinates. The control algorithms directly use observable image information represented in t he 2-D image sequence; a 3-D reconstruction is not required [18][31]. Such an approach is particularly useful in closing control loops with vision at lower levels of a multi-leve l control system. The limited body-centered data that are used are mapped into the local visual space for steering and speed control policies. A minimalist approach requires fewer calibrations, fewer scene hypotheses, and less computation. It is, therefore, simpler and fa ster. <"FigureTableTitle", Font = F3@Lam> Figure 1 Obstacle Avoidance System Architecture <"Table:Cell"> <"Body", Alignment = Center> Elemental Move <"Body", Alignment = Center> (E-Move) ) ) > <"Body", Alignment = Center> Primitive (Prim) ) ) > <"Body", Alignment = Center> Servo ) ) > <"Body", Alignment = Center> Behavior Generation (BG) ) ) > <"Body", Alignment = Center> World Modeling (WM) ) ) > <"Body", Alignment = Center> Sensory Processing (SP) ) ) > <"Body", Alignment = Center> 3. Apply spatial and temporal median fil ters ) ) > <"Body", Alignment = Center> 7. Issue steering, speed and gaze commands ) ) > <"Body", Alignment = Center> 6. Determine steer ing, speed; deter mine gaze control ) ) > <"Body", Alignment = Center> 5. Decide desired di rection; detect immi nent collision ) ) > <"Body", Alignment = Center> 2. Compute full optical flow ) ) > <"Body", Alignment = Center> 4. Derive hazard maps from diver gence, goal, history ) ) > <"Body", Alignment = Center> 1. Compute diver gence everywhere ) ) > <"body", Line Spacing = 1.750 lines> <"body", Line Spacing = 1.750 lines> The obstacle avoidance system we describe in this paper is designed in accordance with the Real-Time Control System (RCS) hierarchical architecture described in [1]. RCS decomposes goals both spatially and temporally to meet system objectives. The system monitors its environment with sensors and updates models of the states of the system itself and the world. Figure 1 describes the functionality of the obstacle avoidance system in the first three levels of the RCS hierarchy. <"body", Line Spacing = 1.750 lines> The RCS architecture is composed of three parallel legs (sensory processing (SP), world modeling (WM), and behavior generation (BG)) that interact to control complex systems. The hierarchical levels run in parallel. The present system uses the three lowest levels: elemental-move (e-move), primitive (prim) and servo. Generally, BG modules control physical devices. WM modules supply information to both the BG hierarchy and the SP hierarchy. WM modules maintain a database of system variables and filter and analyze data using support modules. SP modu les monitor and analyze sensory information from multiple sources in order to recognize objects, detect events and filter and integrate information. The world model uses this information to maintain the system's best estimate of the past and current states of the world and to predict future states of the world. <"FigureTableTitle", Font = F3@Lam> Figure 2 Robot and Its View <"Table:Cell"> <"Table:Cell"> <"CellBody"> (a) Test mobile robot <"CellBody"> (b) Robot's view of the lab through its 115-degree wide angle lens <"body", Line Spacing = 1.750 lines> <"body", Line Spacing = 1.750 lines> The testbed mobile robot is shown in Figure 2 (a).Video images are obtained from an onboard uncalibrated camera with a <"body", Line Spacing = 1.750 lines> field of view. The camera is mounted on a pan motor. The robot's view from this camera is shown in Figure 2 (b). Figure 1 sketches the obstacle avoidance system consisting of seven processing modules. The SP modules compute flow and divergence everywhere in the image. The WM modules apply spatial and temporal median filters to reduce momentary fluctuations in the divergence field. The BG modules use divergence to steer the robot around obstacles seen in the wide camera view and provide the body and gaze controllers with desired driving, steering, and gaze velocities. Using active gaze control, the c amera is rotationally stabilized to reduce the magnitude of the flows in the image stream. When the camera points too far away f rom the heading, a saccade is made toward the heading. These saccades introduce momentary disturbances of the flow data, but the temporal median filter effectively eliminates disruptive effects. When divergence data indicate imminent collision ahead because steering alone cannot avoid an obstacle, the robot stops, turns away, and resumes wandering. <"section", Font = F3@Lam, Line Spacing = 1.750 lines> 2Full optical flow estimation <"body", Bottom Margin = 0.000 inches, Line Spacing = 1.750 lines> Robust, real-time optical flow is now becoming a practical means of robotic perception given new fast algorithms and increasingly faster hardware. Given that our entire system (flow, divergence, and body control) is implemented on a single workstation without the benefit of a real-time operating system, it is important to have sufficient processor idle time available to buffer the overhead of the operating system. Otherwise, the image capture frame rate could vary from frame to frame. Camus [7][8] describes a robust, real-time correlation-based optical flow algorithm which returns dense data even in areas of relatively low texture. This is the starting point of our implementation. <"body", Line Spacing = 1.750 lines> In correlation-based flow such as in [5][17][21], the motion for the pixel at <"body", Line Spacing = 1.750 lines> in one frame to a successive frame is defined to be the displacement of the patch <"body", Line Spacing = 1.750 lines> of <"body", Line Spacing = 1.750 lines> pixels centered at <"body", Line Spacing = 1.750 lines> , out of <"body", Line Spacing = 1.750 lines> possible displacements (where <"body", Line Spacing = 1.750 lines> is an arbitrary parameter dependent on the maximum expected motion in the image). We determine the correct motion of the patch of pixels by simulating the motion of the patch for each possible displacement of <"body", Line Spacing = 1.750 lines> and considering a match strength for each displacement. If <"body", Line Spacing = 1.750 lines> represents a matching function which returns a value proportional to the match of two given features (such as the absolute difference between the two pixels' intensity values, <"body", Line Spacing = 1.750 lines> and <"body", Line Spacing = 1.750 lines> respectively), then the match strength <"body", Line Spacing = 1.750 lines> for a point <"body", Line Spacing = 1.750 lines> and displacement (u,w) is calculated by taking the sum of the match values between each pixel in the displaced patch <"body", Line Spacing = 1.750 lines> in the first image and the corresponding pixel in the actual patch in the second image: <"equation"> (1) <"equation"> <"body", Line Spacing = 1.750 lines> The actual motion of the pixel is taken to be that of the particular displacement, out of <"body", Line Spacing = 1.750 lines> possible displacements, with the maximum neighborhood match strength (or equivalently, minimum patch difference); thus this is called a winner-take- all" algorithm. <"body", Line Spacing = 1.750 lines> This algorithm has many desirable properties. Due to the relatively large size of the matching window, the algorithm generally does not suffer from the aperture problem except in extreme cases [5][8], and it tends to be very resistant to random noise. Because the patch of a given pixel largely overlaps with that of an adjacent pixel, match strengths for all displacements for adjacent pixels tend to be similar (except at motion boundaries). Therefore the resultant optical flow field tends to be relatively smooth, without requiring any additional smoothing steps. In gradient-based optical flow, on the other hand, noise usually results in direct errors in the basic optical flow measurements due to the sensitivity of numerical differentiation. Finally, because one optical flow vector is produced for each pixel of input (except for a small <"body", Line Spacing = 1.750 lines> border where flow may not be calculated), optical flow measurement density is 100 percent. <"FigureTableTitle", Font = F3@Lam> Figure 3 Time Delays and Distances <"Table:Cell"> <"Table:Cell"> <"CellBody"> (a) As the maximum pixel shift increases linearly, the search area increases quadratically. <"CellBody"> (b) However, with a constant shift distance and variable discrete time delays, search over time is linear. <"body", Line Spacing = 1.750 lines> <"body", Line Spacing = 1.750 lines> A significant limitation with the traditional correlation-based algorithm is that its time complexity grows quadratically with the maximum possible displacement allowed for the pixel [5][9] (Figure 3 (a)). Intuitively, as the speed of the object being tracked doubles, the time taken to search for its motion quadruples, because the area over which we have to search is equal to a circle centered at the pixel with a radius equal to the maximum speed we wish to detect. <"body", Line Spacing = 1.750 lines> However, note the simple relationship between velocity, distance and time: <"body", Line Spacing = 1.750 lines> <"body", Line Spacing = 1.750 lines> . <"Body"> Normally, in order to search for variable velocities, we keep the inter-frame delay <"Body"> constant and search over variable distances (pixel shifts): <"body", Line Spacing = 1.750 lines> <"body", Line Spacing = 1.750 lines> . <"Body"> However, we can easily see from Figure 3 (b) that doing so results in an algorithm that is quadratic in the range of velocities present. Alternatively, we can keep the shift distance <"Body"> constant and search over variable time delays: <"body", Line Spacing = 1.750 lines> <"body", Line Spacing = 1.750 lines> . <"FigureTableTitle", Font = F3@Lam> Figure 4 Space-time correlation search of Camus' real-time optical flow algorithm <"Table:Cell"> <"Table:Cell"> <"Body", Top Margin = 0.041 inches, Font = F62@Lam> (a) The search area for the example pixel (1,1) in this example is shown in the current frame (Image t). This search begins from a previous frame (2 such previous frames are shown). <"Body", Top Margin = 0.041 inches, Font = F62@Lam> (b) The correlation match is the sum-of-absolute differences between the corresponding pixels' intensity values in a patch centered at the given pixel (a patch size of 7x7 is used in all examples; these patches are not shown for clarity). <"Body", Top Margin = 0.041 inches, Font = F62@Lam> (c) Optical flow is calculated to be the best- matching pixel shift divided by the corresponding frame delay. <"body", Line Spacing = 1.750 lines> <"body", Line Spacing = 1.750 lines> In this case, we generally prefer to keep <"body", Line Spacing = 1.750 lines> as small as possible (for example a single pixel) in order to avoid the quadratic increase in search area. (Note, however, there is nothing preventing an algorithm based on both variable <"body", Line Spacing = 1.750 lines> and <"body", Line Spacing = 1.750 lines> .) This temporal matching concept is depicted in Figure 4. This time-space trade-off reduces a quadratic search in space into a linear one in time (at a cost of measurement precision), resulting in a very fast algorithm: optical flow can be computed on 32x64 images, quantizing flow speeds into 5 bins, at 35 frames per second on an 80 MHz Themis HyperSPARC . <"body", Line Spacing = 1.750 lines> . Certain commercial equipment, instruments, or materials are identified in this paper in order to adequately specify the expe rimental procedure. Such identification does not imply recommendation or endorsement by NIST, nor does it imply that the materia ls or equipment identified are necessarily best for the purpose. ) (E16,0,0,,5,1,1,0.0533333,1,15,0,0,1,0,0,0,1,5,127,7,0,0,7,0,1,1,0.0666667,0.06 66667,6,6,0,0.0666667,6))> <"Normal", Top Margin = 0.000 inches, Bottom Margin = 0.140 inches, Left Margin = 0.000 inches, Right Margin = 0.000 inches, First Indent = 0.000 inches, Alignment = Left, Font = F7@Lam, Line Spacing = 1.309 lines> 10 computer. Although this algorithm is not as accurate as many other optical flow algorithms, it is generally superior in term s of computational efficiency [23]. <"body", Line Spacing = 1.750 lines> In our implementation, an original image of 256x512 pixels, captured with a <"body", Line Spacing = 1.750 lines> field-of-view camera, is subsampled to 32x64 pixels using a simple block-subsampling algorithm which averages an NxN