Vivek Pradeep

Gerard Medioni

James Weiland

Piecewise Planar Modeling for Step Detection using Stereo Vision

A mobility aid for the visually impaired should be able to detect and warn about nearby obstacles. Reliable detection of curbs and steps is critical to meet this goal. This paper describes a stereo-vision based algorithm that estimates the underlying planar geometry of the 3D scene to generate hypotheses for the presence of steps. Tensor voting is used to calculate globally consistent normals at each data point and a clustering algorithm is described to generate a piecewise planar model of the scene. Results demonstrate the improvement in plane clustering using tensor voting and the ability of the algorithm to find sufficient evidence for the presence of curbs and steps.

Introduction

There are 10 million blind and visually impaired people in the United States, of which about 110,000 use long canes to get around. A significant part of the population suffers from retinal diseases (such as retinitis pigmentosa and glaucoma) that cause peripheral vision loss/tunnel vision which adversely impacts unaided mobility in indoor and outdoor environments. Recently, there has also been a lot of interest in neural stimulation devices such as the epiretinal prosthesis [START_REF] Weiland | Intraocular retinal prosthesis[END_REF] which employs an external camera to drive an array of microelectrodes implanted onto the retina. Even in the case of such a device, surgical and technological constraints presently limit artificial vision to only the central 20 degrees field of view and therefore, the challenges to independent mobility remain.

Mobility Aids

Autonomous navigation in an unknown environment requires the ability to detect obstacles and efficiently plan routes across the terrain. For the visually impaired, these are often difficult and time-consuming tasks to perform. While the white cane and the guide dog have been popular aids, there have also been attempts to design devices to complement their roles. Several mobility and navigational aids leveraging the concept of sensory substitution [START_REF] Arno | Auditory coding of visual patterns for the blind[END_REF] have been proposed over the years. Sonar has been extensively used ( [START_REF] Russel | Travel path sounder[END_REF], [START_REF] Kay | An ultrasonic sensing probe as a mobility aid for the blind[END_REF], [START_REF] Laurent | A sonar system modeled after spatial hearing and echolocating bats for blind mobility aid[END_REF]) to provide information about the surroundings by means of auditory cues. Popular, commercial mobility aids ( [START_REF] Borenstein | The guidecane-a computerized travel aid for the active guidance of blind pedestrians[END_REF], [START_REF] Dodds | The sonic path finder:an evaluation[END_REF]) are also sonar based, but all these devices need significant training and impose severe information-load onto the user. In [START_REF] Kulyukin | Robot-assisted wayfinding for the visually impaired in structured indoor environments[END_REF], a robotic 'guide dog' based on RF-ID mapping and sonar obstacle detection for indoor environments is proposed.

The availability of cheap cameras and faster processors has encouraged many researchers to investigate computer vision and image processing strategies on information-rich images/videos to build more intelligent mobility aids. The vOICe [START_REF] Meijer | Vision technology for the totally blind[END_REF] is an example of a vision-based device that converts images into sounds, while ASMONC [START_REF] Molton | Robotic sensing for the partially sighted[END_REF] fuses vision and sound sensing modalities to provide scene information. Recently, [START_REF] Saez | First steps towards stereo-based 6dof slam for the visually impaired[END_REF] proposed a system inspired from SLAM literature in robotics that uses a stereo camera to provide orientation information to the visually impaired.

Step Detection

The importance of curb/step detection for autonomous mobility is well established in literature, with a diverse set of sensors (such as in [START_REF] Thorpe | Driving in traffic: Short-range sensing for urban collision avoidance[END_REF]) being used for the purpose. In [START_REF] Yuan | Dynamic environment exploration using a virtual white cane[END_REF], an active range-finder employing a laser and camera system is described that uses Jump-Markov modeling to track distances to the ground plane and detect steps.

Solving the step-detection problem relies on obtaining accurate 3D models of the scene and one might expect ladar sensors to be well suited to the task. However, this accuracy comes at the cost of high price, weight and low speed. Furthermore, these sensors have limited field of view and low information bandwidth. A stereo camera system is a logical alternative and the acquired images enable other functionalities to be integrated.

In [START_REF] Se | Vision-based detection of kerbs and steps[END_REF], a stereo-vision based algorithm is described that finds parallel lines using the Canny edge detector and Hough Transform to identify curbs. Stepups and step-downs are identified by estimating the ground plane parameters on either side of the detected curb. Building on this idea, [START_REF] Lu | Detection and localization of curbs and stairways using stereo-vision[END_REF] combines stereo data with image intensity information to detect steps. Both the methods mentioned here rely on detecting curb-lines in the scene, which might not be trivial in cluttered environments or from certain viewpoints.

Paper Overview

We propose a stereo vision based mobility aid that performs the tasks of obstacle detection and identifying a safe path for traversal. The stereo-vision system is mounted on an eyepiece and allows the subject unrestricted head motions and auditory cues warn about nearby obstacles. Our approach is to combine SIFT features with stereo data for performing 6DOF SLAM and use the resulting 3D maps along with orientation information as input to an interpretation layer. The tasks of obstacle, curb and stair-case detection are done in this interpretation layer by building a piecewise planar model of the scene. In this paper, we focus only on the plane-fitting module that we have developed using tensor voting. This is a more general approach to step detection and plane fitting offers further advantages in modeling the surrounding environment. In the next section, we discuss the issues in plane extraction using stereo data and present our method. We also compare with standard techniques to highlight the advantages of tensor voting for this task. Finally, as this is still a work in progress, we outline future goals to be met before this module can be be successfully integrated into the system. Figure 1 presents a block diagram of our piecewise planar modeling approach for step detection along with the result of each process. The stereo-camera produces a dense 3D point-cloud of the scene. A commercial system (Bumblebee by Point Grey Research), which does stereo processing 30 frames a second, is used to generate this cloud. We first fit planes to this 3D data and cluster parallel planes together. We then proceed to segment within each cluster to separate parallel but distinct planes.

Plane fitting and segmentation

Issues

Depth information obtained by stereo is inherently noisy due to several factors. As objects farther away have smaller disparities, error tends to increase with depth. Incorrect stereo matching, occlusions and shadows lead to patches where there might not be any 3D information. Given this noisy data, our task is to simultaneously fit planes to the various structures in the scene as well as segment these planes from each other. The first step to plane fitting is the estimation of a local normal at each 3D data point. One popular technique is to consider the neighborhood about each point and use PCA-based methods. For example, one may simply use SVD to calculate a plane for each voxel of the 3D point cloud. Since there might be outliers in the data, a RANSAC based algorithm can be devised for robustness. However, since this is based on local processing, the obtained normals do not end up globally consistent. The size of the voxel has a significant impact on the estimated plane. High noise content in the voxel calls for a larger size whereas, potential curvature in the data requires keeping voxel size restricted. [START_REF] Mitra | Estimating surface normals in noisy point cloud data[END_REF] prescribes an adaptive technique to determine voxel size based on curvature and noise content. Since structures belonging to steps and curbs tend to be small (given that the camera is head-mounted and we wish to detect them from a safe distance away), curvature begins to play an early role such that we are still faced with the effects of local processing.

Tensor Voting for Normal Estimation

We employ tensor voting [START_REF] Medioni | Tensor voting: Theory and applications[END_REF] to improve the normal estimates at each point. Specifically, we encode our 3D data as a set of points associated with 3x3 tensors. The tensor structure is obtained from initial normals evaluated by the RANSAC-SVD technique. Suppose the plane at a point is given by P = ai + bj + ck + d, where i, j, k are the orthogonal unit vectors. Then, a, b, c are the eigen-values along the eigen-vectors (1, 0, 0), (0, 1, 0) and (0, 0, 1) respectively. Further details of tensor voting can be found in [START_REF] Medioni | Tensor voting: Theory and applications[END_REF]. The end result of this processing step is a set of refined normals which are more consistent with the underlying 3D structure of the data. The element of noise is taken care of by the low number of votes cast for any consistent normal by outliers.

Once accurate normals have been obtained, clustering is a trivial task. Assuming ground to be the XZ plane, we compute a histogram of the angles θ between the normals at the data points and the normal to the ground plane.

A simple Hough Voting over the space of these angles clusters points belonging to parallel planes together. For instance, all horizontal planes will vote for θ = 0 o while vertical planes vote for θ = 90 o . Currently,we are assuming that the ground plane is known, given the camera height. In our final system, we aim to use the camera orientation information obtained from 6DOF visual SLAM to constrain the search for the ground plane. Parallel planes can then be easily separated from each other by casting votes in the space of their distances from the origin. Figure 2 presents a comparison of the results obtained after tensor voting to that using a RANSAC only based approach. We have manually clustered the points of a curb scene into horizontal and vertical planes to create a ground truth. We show the clusters obtained using the two different approaches. In this result, parallel planes have not yet been segregated and this will be done in the next step. The effect on local processing and noise can be easily seen in the RANSAC result, where globally inconsistent normals lead to several misclassifications. Figure 3 displays similar results for another scene with two steps. Our MATLAB implementation takes about 10 seconds per frame running on a 1.8 GHz PC with 1 GB RAM. Images are of size 320×240. We have not yet optimized our code for performance. Figure 4 shows the final plane clusters obtained for the scenes in figures 2 and 3.

Comparison and Results

To quantitatively analyze the performance of tensor voting, we have computed the fraction of misclassified pixels (e.g., if a horizontal plane pixel was classified as a vertical plane pixel) relative to the manually clustered ground truth. The values for the scenes in figures 2 and 3 are shown in Table 1.

Conclusion and Future work

We have presented a piecewise planar modeling algorithm that can be used in a module for curb/step detection. This is proposed as part of a stereo-vision based mobility aid that performs 6DOF SLAM in conjunction with obstacle detection. Our approach is to use tensor voting to calculate globally consistent normals and perform clustering to fit planes onto the 3D point cloud. This is important because standard, RANSAC-based approaches have been demonstrated to be insufficient given noisy stereo data. We are currently working on a module that can interpret this derived structure to recognize curbs, stairs, step-ups and stepdowns. Using SLAM as the backbone, we hope to be able to track the ground plane after an initial calibration and concurrently apply the piecewise planar modeling module to warn about step changes. Apart from a faster implementation,we also plan to incorporate multi-view integration for increased robustness. Validation on other data-sets and extensive testing on human subjects are also planned in the next few months.

Fig. 1 .

 1 Fig. 1. Block diagram of our piecewise planar modeling algorithm. The stereo camera generates a dense 3D point-cloud, to which we fit normals by RANSAC. These normals are globally inconsistent because they are the result of local processing in each voxel of data. Tensor voting is employed to refine these normals and clustering is finally performed to segment out the fit planes

Fig. 2 .

 2 Fig. 2. Comparison of results obtained before Tensor Voting and after. (a) Original 3D point-cloud (b) Input point-cloud manually clustered into horizontal (red) and vertical (blue) planes to generate ground truth (c) Segmentation after RANSAC processing only (d) Result after tensor voting

Fig. 3 .

 3 Fig. 3. Comparison of results obtained before tensor voting and after. (a) Original gray scale image (b) Input point-cloud manually clustered into horizontal (red) and vertical (blue) planes to generate ground truth (c) Segmentation after RANSAC processing only (d) Result after tensor voting

Fig. 4 .

 4 Fig. 4. Final planes segmented from the scenes in (top) figure 2 and (bottom) figure 3

Table 1 .

 1 Misclassification fractions for the scenes in figures 2 and 3, before and after tensor voting. Lower misclassification fraction indicates better performance

	Scene	RANSAC only After Tensor Voting
	Single Step (figure 2)	0.253	0.073
	Two steps (figure 3)	0.351	0.067

This material is based on work supported by the National Science Foundation under Grant No. EEC-0310723.


Gemstone Team

Vision ⋆1

Bobby Bobo

Rama Chellappa

Cha-Min Tang

Christopher Cheng

Brendan O'leary

Lee Stearns

Steve Caperna

Junghee Cho

Victoria Fan

Avishkar Luthra

Andrew Sun

Roni Tessler

Paul Wong

Developing a Real-Time Identify-and-Locate System for the Blind

It is safe to say that computer vision holds great potential for providing a broad range of benefits to the blind in the foreseeable future. But despite the rapid advances in computer hardware and vision algorithms, robust, self-contained functional systems that can be used by the blind for 'identify-and-locate' tasks are not yet available. This paper describes the challenges encountered and experience gained in building such a functional 'identify-and-locate' system by a group of undergraduates in the Gemstone Program at the University of Maryland, College Park. The greatest resistance to getting this task off the starting block was the need to simultaneously tackle several technical challenges requiring a range of expertise. These included developing a robust and real-time computer vision algorithm, a voice recognition and speech output system, a directional feedback interface, and the means to integrate these components into a single functional unit. With access to a pool of students with differing skills and backgrounds, we overcame the initial resistance. The bulk of the project was completed over a one year period, resulting in a prototype system that the blind can use in controlled environments to reliably identify and locate objects and signs within seconds.

Introduction

Recent technological advancements have prompted the development of numerous assistive technologies for the blind. However, despite the impressive capabilities of these devices, the vast majority of the blind still rely entirely upon the white cane.

In many cases, these new devices are not embraced because they are too specialized, too cumbersome to operate, or demand too much concentration. In contrast, the white cane is compact, intuitive to operate, provides useful feedback in almost any situation, and does not require intense thought to operate. These characteristics have made the white cane ubiquitous in the blind community. If they are to be successful, new devices must have similarly impressive userinterfaces.

There is no doubt that the blind could make great use of a device that identifies and locates navigational landmarks, objects that are misplaced, signs for restrooms and exits, and people walking into a room. A device that could assist in these tasks under a wide range of circumstances could vastly improve a blind or visually impaired person's quality of life. More powerful portable computers are becoming available every year, and computer vision algorithms continue to improve. We believe that an integrated system based on computer vision could soon provide solutions to many of the challenges that the blind and visually impaired face every day.

Developing the Technical Components

There are two possible strategies for the development of an 'identify and locate' system: Design a device with a wireless connection to a central server that would bear the brunt of the computational load, or create an autonomous device. It is difficult to predict which strategy holds the most promise for the future. Each has its strengths and weaknesses, and, ultimately, each may fill its own niche.

Our versatile design strategy is to put network-ready software on an autonomous computational device (see Sec. 2.4). While the heart of this challenge lies in developing a robust and real-time computer vision algorithm, a functional navigation and 'identify and locate' system is critically dependent on other features (Fig. 1). To this end, team members simultaneously assemble critical system components: the computer vision algorithm, the audio interface, and the GPS and inertial navigation system. In this paper, we will only discuss the use of computer vision and an audio interface to address 'identify-and-locate' tasks.

The Computer Vision Algorithm

To obtain fast, robust object recognition, our system implements the scale invariant feature transform (SIFT), proposed by David Lowe in [START_REF] Lowe | Distinctive Image Features from Scale-Invariant Keypoints[END_REF]. We use SIFT to characterize both template images (images of the object we wish to locate), and the video stream captured from the camera worn by the blind subject.

When the appropriate command is received from the user interface, our system initializes all available templates for the requested object of interest. Initialization consists of extracting SIFT features from the templates and reading annotation data. Annotation data, which is stored in an ASCII text file, consist of a pair of points per template image. The pair of points defines a rectangle bounding the object within the corresponding template.

After initialization, the video stream from the camera is analyzed to search for the object of interest. Searching for the object of interest follows a six-step process (Fig. 2). First, a frame is captured from the camera. Second, SIFT features are extracted from the still frame. Third, a Best-Bin-First (BBF) search is executed using a kd-tree to match features between the template images and the still frame [START_REF] Samet | Foundations of Multidimensional and Metric Data Structures (The Morgan Kaufmann Series in Computer Graphics and Geometric Modeling[END_REF]. Features in the template image that are outside the bounding rectangle are ignored. Fourth, a random sample consensus (RANSAC) fit based on least-squares planar homography is used to discard bad feature matches [START_REF] Fischler | Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[END_REF]. Fifth, a perspective transform matrix is computed from the remaining feature matches [START_REF] Hartley | Multiple View Geometry in Computer Vision[END_REF]. Finally, using the perspective transform matrix, we obtain the location of the object in the frame. Vertical and horizontal angles to the object are computed by assuming that the camera has a ±20 degree field-of-view in both the horizontal and vertical directions and by using linear interpolation based on the location of the center of the object in the still frame. Steps two and three follow the methods and suggestions outlined by Lowe in [START_REF] Lowe | Distinctive Image Features from Scale-Invariant Keypoints[END_REF], with one exception: In step two, extraction of SIFT features, Lowe recommends doubling the size of the input image by linear interpolation. We skip this computation in the interest of speed. This results in fewer features detected in the still frames, but a faster BBF search. Unlike the still frames, however, the size of the template image is still doubled prior to calculating SIFT features.

The algorithm described in this section is implemented in C++ using the Boost, GNU Scientific, and Open Computer Vision libraries. The SIFT, BBF, RANSAC, and perspective transform implementations are modified versions of the free software available from Rob Hess of Oregon State University [START_REF] Hess | Sift feature detector[END_REF].

Voice Recognition and Speech Output

Typing on a keyboard while standing would be a challenge even for the sighted. A user friendly interface would allow the blind to simply speak into a microphone while walking. We have begun development on an in-house audio computer interface. The technical challenge can be broken down into five components: accurately recognize user commands, parse the commands, send the relevant information to the proper subsystems, receive data from those subsystems, and communicate the requested information back to the user. The experience should be as intuitive and natural as possible.

Software Implementation We chose to use the Microsoft .Net 3.0 Speech Library and the Microsoft Office Speech Engine to accomplish most of these goals. The library is free to Windows users, has many advanced capabilities and text-to-speech options, and extensive documentation available from multiple sources. The text-to-speech engine could be easily replaced with any other speech engine. We are programming the interface in C# to simplify the software coding, avoid problems with 'memory leaks', and take advantage of some features that are only available in .Net 3.0 languages. Using .Net 3.0 will also make the system easier to update and maintain in the future. The DirectSound library included in DirectX 9 is being used to provide additional functionality and will be discussed in Sec. 2.3.

Speech Recognition Accuracy

Through careful consideration and design, we have developed an speech recognition system that is both robust and accurate. To prevent the recognition engine from interpreting normal conversation as commands, a push-to-talk button has been built into the device. The computer only listens for input from the user while this button is depressed. This has the added benefit of decreasing the load on the processor, which leaves more resources available for other computational threads and conserves battery power.

Ambient noise can interfere with a system's ability to understand the user. Throat microphones, which use a vibration sensor on the neck near the vocal cord to capture sound, will be used to capture user input. This will reduce or eliminate interference from noisy surroundings. Even with the elimination of ambient noise, recognizing speech is a difficult computational problem. To simplify it, a "grammar" file is being developed. This file tells the computer what it should expect to hear. It defines vocabulary and syntax. It anticipates the user's sentence structure and allows for variations on object names. Because it is an external XML file, it can be updated dynamically as new objects are added. No software modifications are necessary to do this. The capability to quickly and easily update the grammar file will make this system a more viable long-term aid.

Syntax The computer can dynamically create and output speech to respond to any of the requests defined in the grammar file. If asked to "Find the restroom," our computer can dynamically generate a sound file that replies, for instance "Searching for the Restroom." Output files are created by the text-to-speech engine as needed and then deleted.

Directional Feedback

Because the primary purpose of the computer vision component is to determine the location of a target object relative to the user, an effective method to pass along directional information to the user is important. Direction can be provided both through plain spoken English and through an intuitive 3D sound output. For example, if the vision system detects the target object 20 degrees to the left of the direction the user is facing, the sound output is adjusted so that it seems to come from 20 degrees to the left of the user's head while it is suggesting that the user change his or her orientation. This intuitive directional effect can be duplicated using any single-channel sound file.

In an alternative interface, a continuous audio "beacon" guides the user to the proper orientation. When the object is to the far left, a low-frequency static sound is sent to the user's left ear. As the user turns toward the sound and the object approaches center, the sound gets louder and is ultimately sent to both ears. As the object crosses center, a brief "pop" sound is sent to the user. A corresponding effect is created when the object is on the right side. Vertical localization is achieved through pitch. As the object moves closer to center, the pitch of the sound sent to the user is decreased.

The 'beacon interface' has four distinct types of feedback: an initial virtual direction, a continuous graded signal as the user orients, a precise 'pop' when the target is centered, and vertical pitch feedback that is distinct from, and does not interfere with, the horizontal static feedback. The continuous feedback is particularly important. A user cannot be expected to successfully locate a target based on one impulse signal. To do so would require extensive practice and intense concentration. An iterative localization technique based on multiple distinct impulse signals would not demand the same perfection from the user, but it would demand the same amount of concentration during each impulse. Localization with a continuous feedback signal, like the one the beacon interface provides, should enable a user to locate a target with minimal effort and concentration.

System Integration

Our software system consists multiple programs written in multiple languages and running in separate processes. For our system to be effective, real time information from each of these programs needs to be assembled and translated into a form that is practical for the user. This task is not trivial with a system that has multiple threads running in each of multiple programs. However, through the use of sockets, inter-process communication is achievable.

A socket is a communication channel that is used by programs to send data over the Internet. However, sockets can also be used by a single computer to send information to itself over its network card. It only takes fractions of a millisecond for separate programs to communicate with each other this way.

The speed and versatility afforded by the socket method make it an elegant solution to a difficult communication problem. The ability to communicate between programs written in any language makes our system far easier to augment than systems that communicate through more conventional pathways. Adding a new program to our system requires only a slight modification to the interface program and no modification to any of the other existing programs. This makes our system extremely adaptable and forwards compatible.

Better still, using the socket method makes the system network-ready. Future compact, networked, handheld devices could outsource the difficult, battery draining, and processor intensive computational tasks to a central server over a WiMAX or equivalent wide area wireless network using the socket communication methods we have already built into our software.

Hardware

Current Computer and Accessories Our test system is a Toshiba Satellite A75-S2311 running Windows XP Professional (32-bit) with Service Pack 2.

Our test system has a 3.3 GHz Pentium 4 processor, 1.5 GB of RAM, a firstgeneration Logitech QuickCam for Notebooks Pro (mounted on sunglasses), a USB microphone, and over-the-ear headphones.

Future Computer Our current system is slow, bulky, energy inefficient, and plagued by tangling cables. Pentium 4 is an eight-year-old technology. Not only are modern multi-core processors better suited to handle our programs, but they are also far more energy efficient. We will build a light, compact computer with a high-speed multi-core processor, a solid-state flash hard drive, ample high-speed DDR2-1300 SDRAM, a small, efficient wireless networking card, and Bluetooth capability. More importantly, the core system will not have unnecessary powerdraining and weight-adding components. It will not have a screen, keyboard, mouse, or CD/DVD-ROM drive. The use of a flash hard drive means that our computer will not have any moving parts, making it more durable and efficient.

Future Accessories Perhaps more important than our core system are the peripherals our users will interact with. A Bluetooth push-to-talk button will be built directly into the handle of a standard white cane, enabling the user to operate our system while keeping one hand free. A throat contact microphone will pick up only the sound resonating in the user's larynx, eliminating the speech recognition errors that could result from ambient noise and enabling use of the system in loud environments. A higher-resolution camera with good autofocus and zoom capabilities will improve our object detection recognition capabilities. Finally, to achieve the best intuitive directional feedback, we will use Etymotic Research, Inc's ER2 insert earphones. Sound will be delivered via thin tubes into the external ear canal. The advantage is that it will be possible to make ear molds that can hold the tubes in place but not block ambient sounds. One of the most important caveats of providing assistance to the blind is not to hinder their hearing. An alternative to tube inserts are bone conduction earphones, but they do not provide very high quality sounds and therefore would not be optimal for providing intuitive directional feedback. When Etymotic tube insert earphones were used with a head related transfer function, subjects perceived direction as well as if it was produced naturally [START_REF] Kulkarni | Role of spectral detail in sound-source localization[END_REF].

System Evaluation

Reliability and Speed of Object Detection

In preliminary tests, which were done at near real-time rates, the algorithm successfully distinguished between a one dollar bill and a twenty dollar bill (Fig. 3(a)). In addition, the algorithm did not falsely identify the one dollar bill even when it occluded many of the most distinct features on the twenty dollar bill. In fact, it still successfully identified the twenty dollar bill (Fig. 3(b)). In the tests run so far, the algorithm has identified objects with exceptional accuracy.

However, there have been instances of the algorithm failing to find matches while an object of interest was in-frame. Even if the algorithm initially identifies the object, it does not always successfully track it when it or the camera is moved. Identification is not always continuous in real-time.

The camera is capable of providing the algorithm with thirty image framesper-second; however, the algorithm easily consumes all of the processing power of our test system while only analyzing up to 20 frames per second.

Nonetheless, in three weeks of testing, there were no false positive matches. We tested two classes of objects. The algorithm had no trouble distinguishing between the signs in Fig. 4(a). In addition, during 'real-world' testing (Fig. 6), the algorithm never misidentified a cane, box of tissues, cup, or mug as any of the other objects.

Sign Identification Tests Despite impressive research aimed at making signs more accessible to the blind [START_REF] Coughlan | Cell Phone-based Wayfinding for the Visually Impaired. 1st International Workshop on Mobile Vision[END_REF][START_REF] Coughlan | Functional Assessment of a Camera Phone-Based Wayfinding System Operated by Blind Users[END_REF], infrastructure changes are expensive, and there will always be environments with limited accessibility. We are designing our system to be flexible enough to identify signs in such environments. Fig. 4. The subject was asked to point at the signs after the computer informed him that he had centered the image.

The subject was asked to center a sign on a wall in front of him both vertically and horizontally in the camera's view. After the subject held the image within three degrees of center for five frames, the computer would inform him that the sign had been found. He was then asked to point to the sign. The signs were then repositioned, and the exercise was repeated.

We used three of the signs pictured in Fig. 4(a) throughout testing: the dog sign, the bird sign, and the restroom sign. The system had no trouble identifying the restroom sign continuously as the subject moved his head. The dog sign was identified with only a few discontinuities. In many cases, the Bird sign could only be identified intermittently. The algorithm is most successful when asked to identify signs with sharp, high-contrast features. It detects corners, but not curves. Both the restroom sign and the dog sign provide this type of feature. The gray background of the bird sign gives it a lower contrast ratio than the other two signs, and the curves of the bird's feathers are more difficult to detect than the edges of the restroom sign illustrations (Fig. 5) and the spots on the Dalmatian.

Object Identification Tests After the sign tests, the subject sat at a table that had a uniform cloth draped down from the wall over its surface. Objects and people did not cast significant shadows in the environment, which was lit with overhead fluorescent fixtures. A modified white cane (Fig. 6), a cup (or sometimes mug), and a box of tissues were quietly placed in front of the subject. He was then asked to identify one of the objects and center it within three degrees of vertical and horizontal in the camera's view. After the object was centered for 5 frames, the computer would inform the subject that the object had been found. He then reached out and touched the object without searching with his hand.

The vision algorithm also successfully identified three-dimensional objects, though under tightly controlled conditions. Successful identification is highly dependent upon the object templates. In order to account for all possible object orientations, a significant number of templates must be used. Unfortunately, increasing the number of templates too much can slow down the algorithm. Image resolution can also become a constraint. The hardware had difficulty processing images larger than 320 × 240 pixels in real-time. This limited the number of visible features on the object when it was not close enough to the camera. When suitable objects were placed in the same orientation as the template images, within the limited focal depth of the camera, and close enough that a 320 × 240 frame could capture enough features, the algorithm performed well and identification was continuous.

Though our system still has difficulty identifying three-dimensional objects, it is a successful sign identification and location system.

Voice Recognition

The voice recognition system performed excellently. The grammar file (see Sec. 2.2) allowed users to direct the computer a number of different ways. For example, saying, "find dog," "find the dog," "find my dog," would all result in the computer initiating a search for the dog sign. Even more variations can be added to make the feature as robust as possible. As the search is initiated, the computer gives confirmation, replies with "searching for the dog." If the computer misunderstands the user, a rare occurrence, the user simply presses the push-to-talk button and repeats the command. After the user has held the dog sign in the center of the frame for a configurable amount of time, the computer says "Dog found." Blind users liked that they could speak naturally to the computer, and that it would respond in plain English.

Directional Feedback

We evaluated two interface concepts. In one interface, a continuous sound is generated to guide the user to the object. We will refer to this as the 'beacon interface'. In a second interface, the computer outputs verbal instructions on how to angle the camera. Because the feedback from this interface is not continuous, we will refer to it as the 'discrete interface'. We tested both interfaces with a blind subject and obtained both quantitative and qualitative data. Quantitative data was obtained with two-dimensional sign location. Before testing, the subject familiarized himself with each interface by listening to the output as the computer tracked a target that he held in his hand (Fig. 7). Localization with the Discrete Interface Using the discrete interface, the subject was able to locate signs in an average of just over 16 seconds. This number includes any initial search time to get the signs in-frame as well as the time the subject had to keep the signs in the center of the frame. The signs were in-frame about 76% of the time.

When using the discrete interface, the subject tended to locate the signs iteratively. An instruction like "up 20 [degrees] right 4 [degrees]" would often prompt movement in the correct general direction, but of an incorrect distance. The subject would often overshoot the sign. In general, when using the discrete interface, the magnitude of the error vector would decrease with each iteration, but its direction would change dramatically.

Use of the discrete interface also led the subject to accelerate his head rapidly in the given direction, and then hold for instruction. The high jerk resulted in blurry frames and discontinuous identification. However, because the interface only needed information from one frame every time he moved his head, this did not impede localization.

Localization with the Beacon Interface With the elimination of one outlier (see below), the beacon interface enabled sign localization in an average of under 12 seconds. Again, this number includes initial search time and object centering time. The signs were in-frame about 83% of the time.

When the algorithm could not locate a sign continuously, the interface was difficult to use, resulting in our outlier. The beacon interface stops sending sound when the vision algorithm cannot locate the object of interest in three consecutive attempts (this number is configurable). It is designed to be continuous, and, when it is not, using it can be confusing.

However, when the algorithm recognized a sign continuously, the subject could locate it in an average time of just over 5 seconds using the beacon interface. In addition, the subject exhibited a perfectly damped response. He did not overshoot the sign. Centering was accomplished in one smooth motion with little concentration or effort. As our vision algorithms improve, this interface should result in very rapid localization.

Subject Preference

The subject preferred the beacon interface when object identification was continuous and the discrete interface when it was not. His preference stems from his heavy reliance on environmental sounds for information. Use of an overly distracting interface could impair his ability to keep himself safe. After little practice, he could use it intuitively and automatically. The discrete interface required more attention to use, and would interfere with his ability to process environmental sounds.

Conclusion and Future Work

The early 'alpha' prototype system discussed here enabled a blind subject to identify and locate signs in only 5 seconds under ideal conditions. The innovative 'beacon interface' was well-received and required little concentration to use. In situations where identification was discontinuous, the 'discrete interface' enabled the subject to identify and locate signs in only 16 seconds. In addition, our blind subject was able to successfully identify, locate, and touch real-world objects without searching with his hand using either interface.

Our 'beta' prototype will enable the user to select between three options: a beacon mode, a discrete mode, and an automatic mode where the computer chooses which interface to use based on how well it is tracking an object. Furthermore, users will be able to configure these settings in the same way that they can already direct the alpha system to search for specific objects: by speaking in natural, intuitive sentences. And, as the alpha system already does, the beta system will respond and provide confirmation in plain English.

Our alpha prototype system has many limitations, but there are established methods available to improve it. Processing time can be reduced with a more powerful computer. Implementation of hierarchical image matching schemes, as recently described by Nister and Stewenius [START_REF] Nister | Scalable recognition with a vocabulary tree[END_REF], could also speed up the system. In addition, the ability to rapidly match a live video image against a large number of templates could markedly improve the system's reliability. A better camera with a higher resolution and better auto focus and zoom capabilities could also dramatically improve the system.

More than anything, the system discussed here demonstrates the incredible potential that flexible, computer vision based systems have to improve the quality of life for the blind and visually impaired. Given time and resources, this potential can be realized.

Fig. 1 .

 1 Fig. 1. Functional design of a vision/audio guided system for the blind.

Fig. 2 .

 2 Fig. 2. Process for obtaining object location.

Fig. 3 .

 3 Fig. 3. Even when rotated or partially occluded, the algorithm successfully distinguished between one and twenty dollar bills. Template images are shown above the video feed. The computer automatically generates the pink lines between corresponding features and maps the border of the bill with a green line.

  (a) Sign experiment setup. (b) Bird sign identification.

Fig. 5 .

 5 Fig. 5. Feature matches from the image (left) to the real-time video (right) of the restroom sign.

Fig. 6 .

 6 Fig. 6. Subject locating a white cane.

Fig. 7 .

 7 Fig. 7. Subject training with the beacon directional feedback system.

Acknowledgements

We are grateful to Aswin Sankaranarayanan, Pavan Turaga, and Ashok Veeraraghavan for their guidance and advice. We also thank our team librarians, Bob Kackley and Dan Newsome.


Juan Manuel Sáez Martínez

Francisco Escolano Ruiz

Stereo-based Aerial Obstacle Detection for the Visually Impaired

In this paper, we present a novel approach for aerial obstacle detection using a stereo vision wearable device in the context of the visually impaired assistance. This kind of obstacles are specially dangerous because they could not be detected by the walking stick. The algorithm maintains a local 3D map of the vicinity of the user, which is estimated through a 6DOF egomotion algorithm. The trajectory is used to predict the next movement of the blind and the 3D information of the local map is used to evaluate a possible aerial obstacles in the next pose. A key stabilization algorithm is introduced in order to maintain the floor of the map continuously aligned with the horizontal plane. This is a very important task, because in a wearable 3D device, the relative transformation of the camera reference system with respect to the user and the environment is continuously changed. In the experimental section, we show the results of the algorithm in several situations using real data.

Introduction

In the visually impaired context, the walking stick is the most extended tool for obstacle avoidance, because it is simple to use and allows to detect a long variety of obstacles. However, aerial obstacles could not be detected by this tool, that is, salient obstacles without a direct projection to the floor (for example a branch of a tree or an open awning). In this paper, we propose and validate a novel approach for aerial obstacle detection using a stereo wearable device.

In a first look, this could be considered a trivial problem, because the stereo head provides a very rich 3D information of the scene. Some elements must be taken into account in order to evaluate the difficulty of the problem: (i) we consider obstacles around 1.5m from the user. At this distance, a camera with a field of view (fov) (60 ∼ 70 • ) only detects a little part of the obstacle, but in order to evaluate if the obstacle is aerial or not we need the whole fov; (ii) the orientation between the focal axis of the camera and the displacement vector of the user is continuously changing, because each part of the body transfers a different movement to the wearable device (a totally fixed mounting on the body is not possible). Then, the camera observation usually differs from the part of the environment in front of the user. In order to obtain a complete description of the obstacles, a local map of the surroundings is needed. This map is composed by integrating the individual observations of the trajectory followed by the user. In order to do that, the information of the trajectory is needed, that is, the pose (transformation with respect to a global reference system) of each observation. This transformation could be obtained from different sensors like inclinometers, accelerometers, GPS, and so on. In this paper, we estimate the trajectory through a 6DOF egomotion algorithm (visual odometry).

Visual odometry approaches using stereo vision usually follow a matchingbased scheme in three steps: i) feature extraction; ii) feature matching and iii) transformation estimation. For example, in [START_REF] Olson | Rover navigation using stereo ego-motion[END_REF] corners of the reference images are matched using an approach inspired in stereo correspondence with classical algorithms. Then, a least squares approach is proposed to estimate the transformation from the correspondences. In [START_REF] Se | Mobile robot localization and mapping with uncertainty using scale-invariant visual landmarks[END_REF], SIFT (Scale Invariant Feature Transform [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF]) are selected from reference images and matched through the distance between feature vectors. The transformation estimation is computed by a least squares approach too. The same approach is applied in [START_REF] Ihrke | Digital elevation mapping using stereoscopic vision[END_REF] although selecting the corners of the reference images and matching them by correlation.

An interesting alternative to pure matching-based approaches is Iterative Closest Point (ICP) [START_REF] Besl | A method for registration of 3D shapes[END_REF],which applies registration and transformation estimations steps iteratively until convergence. Registration is solved by computing the closest points in each iteration and transformation is usually solved by least squares.

Here, we present a 6DOF visual odometry algorithm based on our previous work [START_REF] Sáez | First steps towards stereo-based 6DOF SLAM for the visually impaired[END_REF] [START_REF] Sáez | 6DOF entropy minimization SLAM[END_REF], with a novel transformation estimation step where the anisotropic stereo noise is implicitly taken into account. This new step significantly improves the results obtained with the original one.

On the other hand, and in order to solve the problem of the camera orientation, a stabilization algorithm of the local map is needed. In [START_REF] Se | Stereo vision-based obstacle detection for partially sighted people[END_REF] we find an obstacle detection algorithm that looks for the floor plane in the 3D stereo image using a RANSAC approach and tracks the obstacles on the floor using a Kalman Filter. The algorithm fails when the camera is not oriented with respect to the floor, because only the last observation is used. In [START_REF] Coughlan | Terrain analysis for blind weelchairs users: Computer vision algorithms for finding curbs and other negative obstacles[END_REF] we find an interesting approach that detects curbs in the floor for blind wheelchairs users. In this case, an explicit search of the floor is not needed because the stereo head is rigidly mounted on the wheelchair and maintains the orientation approximately constant. In our case, we present an energy minimization approach that maintains the local map continuously aligned with the horizontal plane, without an explicit search algorithm. Using the aligned local map and the trajectory information, we propose an algorithm that detects and classifies the possible obstacles in the future pose of the user.

Aerial Obstacle Detection

In Fig. 1 we show a summary scheme which contains the three key steps of our approach: (i) local map building (middle left) using the 3D observations obtained from the stereo camera and the poses of the trajectory estimated with the egomotion algorithm, (ii) stabilization of the local map (middle center), where the local map is aligned with the horizontal plane in order to recover the reference of the ground and (iii) obstacle detection and classification (middle right), where the next pose of the user is predicted using the trajectory information and a possible obstacle is detected and classified using the 3D information of the map. In the next sections, we provide an in-depth overview of each step.

Local Map Building

Here, we propose a variant of our previous 6DOF visual odometry algorithm proposed in [START_REF] Sáez | First steps towards stereo-based 6DOF SLAM for the visually impaired[END_REF] [START_REF] Sáez | 6DOF entropy minimization SLAM[END_REF] with a significant change that implicity takes into account the anisotropic noise of a stereo system. The overlapped parts of the approach will be summarized paying more attention to our contribution with respect to the latter authors.

In this paper, we use a discrete definition of the trajectory that consists of a sequence of N observations {O 0 , O 1 , . . . , O N -1 } obtained by the camera from N respective poses {p 0 , p 1 , . . . , p N -1 }. Each observation at time t is composed by a set of 3D points of the environment O t = {M i t = [x t , y t , z t ] T } and each pose p t at time t represents the robot position and orientation with respect to a global reference system defined by the first pose p 0 . The pose contains six parameters p t = [x t , y t , z t , θ X t , θ Y t , θ Z t ] T , that is, a full transformation in 3D. Then, the environment map at time t integrates all the observations in their respective poses:

A t = t j=0 {R j M i j + t j }, M i j ∈ O j (1)
where R j and t j are respectively the 3×3 rotation matrix and 3×1 translation vector obtained from p j .

Usually, the trajectory is approximated in terms of actions. Each action a t defines the local transformation between two consecutive observations O t-1 and O t , that is, a pose increment: a t = [δx t , δy t , δz t , δθ X t , δθ Y t , δθ Z t ] T . Then, each pose p t is obtained by integrating all of the previous actions {a 0 , a 1 , . . . , a t }.

The goal of egomotion is to estimate the actions of the trajectory by using only visual cues. To this end, each action is estimated using local information, that is, previous and next observations to each action. The steps to solve the egomotion are described as follows:

Feature Extraction Let O t the complete 3D point cloud observed from the tth pose, and let I t (u, v) the right intensity image of the t-th stereo pair (reference image). For the sake of both efficiency and robustness, instead of considering all points M i t = [x t , y t , z t ] T ∈ O t of the observation, we retain only a significant subset of them that we call reduced observation Õt ⊆ O t . This observation is composed by the 3D points Feature Matching In order to find correspondences between points M i t-1 ∈ Õt-1 and M j t ∈ Õt we will measure the similarity between the local appearances in the neighborhoods of their respective projections m i t-1 and m j t . As we need certain degree of invariance to changes of texture appearance, matching similarity S(M i t-1 , M j t ) relies on Pearson's correlation ρ between the log-polar transforms LP of the windows W i t-1 and W j t centered in both points. Then, we must maximize the score S(

M i t = [x t , y t , z t ] T ∈ O t whose 2D projections m i t = [u t , v t ] T ∈ I t (u, v)
M i t-1 , M j t ) = |ρ(Z i t-1 , Z j t )|, being ρ(Z i t-1 , Z j t ) ∈ [-1, 1
] the correlation coefficient of the random variables associated to the grey intensities of the log-polar mappings Z i t-1 = LP(W i t-1 ) and Z j t = LP(W j t ). Pearson's correlation measures the linear relation between two random variables, regardless of its scales, which is used to measure the similarity between the points with different illumination conditions. Moreover, the log-polar space attenuates the texture deformation effects which are produced when an object is observed from two different poses.

Another effect that must be considered is the texture orientation. The only component of the action that produces rotations in textures is the roll angle δθ Z t ∈ a t . In order to compare the textures correctly, we estimate the orientation of W j t centered at point m j t = [u t , v t ] T through the image gradient vector at this point, that is, ∇I(u t , v t ). Then, we rotate the log-polar transform LP(W j t ) to fit the gradient vector with the horizontal axis of the image. Making the same correction in all of the polar transforms, the correlation ρ(.) is always performed with the textures with respect to the same angle. We may find similar approaches to compute the texture orientation in the literature (for instance, the SIFT descriptor [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF]). However, the proposed method is very fast and simple and it is robust enough to solve the texture rotation effects.

In order to ensure the quality of the matching we reject unidirectional correspondences, that is, correspondences between Õt-1 and Õt must be the same in both directions. Then, considering M j t the element that maximizes S(M i t-1 , M j t ) and M k t-1 the ones that maximizes S(M j t , M k t-1 ), we reject candidates with i = j.

Matching Refinement Despite considering the unidirectional filter, the matching process is prone to outliers. Thus, after computing the best correspondences for all points, we proceed to identify and remove potential outliers. Suppose that the i-th point M i t of Õt matches the j-th point M j t-1 of Õt-1 , and similarly

M k t matches M l t-1 . Let d ik = ||M i t -M k t || and d jl = ||M j t-1 -M l t-1 ||.
Let also D ikjl be the maximum between the ratios d ik /d jl and d jl /d ik . Then, in order to preserve structural coherence it is better to retain correspondences where D ikjl is close to the unit and remove the others. More globally, in order to consider whether M i t matches M j t-1 or not, we evaluate the quantity D ij = ( k l D ikjl )/|M|, where M is the current set of correspondences, that is, for testing whether a given match should be removed or not, we consider the averaged sum of its maxima.

Leaving-the-worst-out is an iterative process in which we remove the match in M, and their associated points, with higher D ij and then proceed to re-compute, in the next iteration, the maxima for the rest of correspondences. We stop the process when either such a deviation is near to zero or a minimum number of correspondences |M| min is reached.

Transformation Estimation

The purpose of the leaving-the-worst-out process is to provide a set of good-quality correspondences in order to face action estimation directly. The idea is to perform both the matching and action estimation only once, to avoid an interleaved EM-like estimation process.

Let M = {(i, j)} the robust set of correspondences obtained after refinement, that relates 3D points M i t-1 of Õt-1 with other M j t of Õt . The optimal action is the one yielding the transformation (rotation and translation) that maximizes the degree of alignment between both set of 3D points, that is, the one that minimizes the energy function:

E(R k , t k ) = (i,j)∈M D pp (M i t-1 , Mj t ) (2)
where R k and t k are 3 × 3 rotation matrix and 3 × 1 translation vector respectively, associated to the action a t ; Mj t represents the application of the above transformation to the point M j t , that is:

Mj t = R k M j t + t k . D pp (.
) is a distance function between the 3D points. The usual choice is the well-known Euclidean distance. However, it is only applicable when the noise of the points is isotropic. In the stereo vision case, each point M i t is contaminated with an anisotropic noise whose maximum amplitude falls in the associated camera ray r i t defined by the line that contains M i t , and the center of projection C t (pinhole camera model assumption). This noise comes from some sources both intrinsic (correspondence errors, pixel size, calibration accuracy and so on) and extrinsic (illumination conditions, ambiguity of the data, texture of the scene and so on). On the other hand, the noise in the other two principal directions (XY plane) comes from the pixel size, and is relatively much smaller than that of the former one (see Fig. 2 left). t falls in the camera ray r i t , defined by the line that contains M i t and the center of projection Ct. Proposed point-to-point distance (right). In order to obtain the distance between two points Dpp(M i t-1 , Mj t ), we correlate two point-to-ray distances: Dpr(M i t-1 , rj t ) and Dpr( Mj t , r i t-1 ) (in green).

The common tradeoff to avoid de undesirable effects of anisotropic noise is the standard reprojection error (see for instance [START_REF] Komodakis | 3D visual reconstruction of large scale natural sites and their fauna[END_REF]), where the distance between points is measured between the 2D projections of the 3D points, assuming a logarithmic decreasing in the image plane. This method avoids the effects of the principal noise axes of the points, but discards all of the depth information. Here, we propose a tradeoff that consists of a 3D distance function D pp (.) which takes into account the difference between the points in the directions associated with less noise to a greater extent, but without discarding the depth information of the points:

D pp (M i t-1 , Mj t ) = D pr (M i t-1 , rj t )D pr ( Mj t , r i t-1 ) (3)
where rj t represents the camera ray r j t transformed, that is, the line containing both Ĉt = R k C t + t k and Mj t = R k M j t + t k . On the other hand, D pr represents the point-to-ray distance. Note that the distance D pr (M i t-1 , rj t ) avoids the principal noise component of Mj t . The same effect is obtained in D pr ( Mj t , r i t-1 ) with the principal noise component of M i t-1 (see Fig. 2 right). Our previous experiments reveals that correlation between both distances provides better results than other methods like mid-point, for example.

Once we have a distance between two matched D pp (M i t-1 , Mj t ), we can evaluate the goodness of a candidate transformation (R k , t k ) through the energy expression E(R k , t k ). In order to to obtain the best alignment, we perform a conjugate gradient descent scheme with an adaptive step that finds the values of the action a t that produces the transformation with the minimum energy (R * , t * ). Note that this method do not imposes any image model.

Local Map Building At time t, egomotion provides the action a t between the new observation O t and the previous one O t-1 . If a t is meaningful enough (transformation with a rotation component greater than 5 o or a traslation component greater than 5cm in our experiments), O t is integrated with the 3D map A t in the respective pose p t . Otherwise, O t and a t are discarded.

Another significant situation could happen when O t and O t-1 do not contain significant overlapped data (large and fast transformations) and consequently egomotion fails. In this situation, the Feature Matching step produces a unstructured set of correspondences M and the Leaving the Worst Out process removes all of them. Then, the final number of correspondences is a good measurement of the robustness of the estimation. When |M| is less than a threshold |M| min the last transformation could not be ensured. Then we consider that the current local map is corrupted. Consequently, all of the information contained in A t is removed, and a new map is built which contains only the last observation O t and a null related action a t = [0, 0, 0, 0, 0, 0].

In order to face the obstacle detection problem, only the 3D information in the surroundings of the user is needed. Then, when a new observation O t is integrated in the map, we remove all of the 3D points of the map M i ∈ A t whose distance to the new pose

p t = [x t , y t , z t , θ X t , θ Y t , θ Z t ] T is greater than a threshold ||[x t , y t , z t ] T -M i || ≤ K dmin .
On the other hand, and in order to remove the overlapped information contained in A t (objects captured from more than one observation) we divide the bounding box that contains A t in a fine and homogeneous grid of cells. For each occupied cell, we replace the points of the map contained in the cell by only one point, obtained as the centroid of such points. This is a very simple approach that maintains the density of the points and drastically reduces the information contained in the local map (for instance, using a grid of cells with length 15cm, the memory requirements are typically reduced to an 11%).

In the summary scheme (Fig. 1) we show a local map construction example from an outdoor sequence (center left). Note that all of the information farther than K dmin = 7.0m is removed from the map.

Stabilization of the Local Map

The orientation of the local map obtained in the last section depends on the local orientation of the first camera pose p 0 . This pose determines the global traslation and rotation of the map, and depends on the first action a 0 which could not be estimated by the egomotion process (there is no observation before the first one) and consequently is set to zero a 0 = [0, 0, 0, 0, 0, 0] T at the beginning. In order to face the obstacle detection problem, a reference of the floor plane is needed which is difficult to obtain if the orientation of the camera is unknown. In this section we propose a novel approach to stabilize the map, that is, a method that finds the optimum values of a 0 that maintain the floor of the local map parallel to the horizontal plane XZ continuously.

Consider the 1D marginal distribution over the Y axis (height) obtained from the 3D point cloud of the local map A t . When the floor of the map is perpendicular to the Y axis, the resultant distribution is crisper than in other case (a high density of points is produced around the height of the floor). Consequently, in this case the entropy of such distribution H Y (A t ) is minimum too. Then, and in order to stabilize the map, we find the values of a 0 that minimize the value of the entropy H Y (A t ). Only two values of a 0 must be adjusted to stabilize the local map: the angle over the X axis δθ X 0 (pitch) and the angle over the Z axis δθ Z 0 (roll). The rest of values of the transformation do not change the cited entropy. In Fig. 3 we can see the evolution of H Y (A t ) with respect to the values of δθ Z 0 and δθ X 0 respectively. The best map (minimum entropy) is obtained with δθ Z 0 = -30.57 • and δθ X 0 = 0.49 • . In order to find the values of δθ Z 0 and δθ X 0 that minimize H Y (A t ), we use a Conjugate Gradient Descent schema with an adaptive step, and the well-know 3-points based numerical approximation of the gradient. The stabilization of the map is a continuous process, because as the camera advances, little errors of the egomotion approximation are integrated with the trajectory, increasing the global drift. Then, the stabilization is performed each time that the map is changed (when the egomotion process inserts a new observation and action), not only at the begining of the navigation.

Entropy approximation from a discrete set of samples is not a trivial task. Cell-based approaches produce a tesselation in the entropy measurement proportional to the size of the cell which complicates the search of the minimum. Then, a continuous approximation of the entropy is needed. In order to do that, we use a non plug-in method [START_REF] Hero | Asymptotic theory of greedy aproximations to minimal kpoint random graphs[END_REF] that estimates the Rényi's α-entropy through the Minimal Spanning Tree of the data, defined as follows:

H α (X) = d γ ln L γ (X) n α -ln β Lγ ,d (4)
where α ∈ [0, 1[ is the order of the entropy (we use α = 0.99), X = {x 1 , ..., x n } is the discrete set of n samples, d is the dimension of the data (1 in our case) and γ = d -αd. ln β Lγ ,d is a constant factor that must be estimated for the problem, but could be omitted in a minimization context. Finally, L γ (X) depends on the MST of the data, defined as:

L M ST γ (X) = min M (X) e∈M (X) | e | γ (5)
where M (X) are the edges that compose the Minimal Spanning Tree obtained from X.

The bottleneck of this entropy estimator is in the MST computation. In our case, the data is in a one dimensional space (Y marginal distribution of A t ). Then, we compute the MST by simply sorting the points of the map in the Y axis. Then, the MST is composed by the n -1 edges that link each pair of consecutive points. Consequently, the complexity of the entropy estimation method is θ(N log(N )), that is, the same as the sorting algorithm (quick-sort in our case).

As we can see, this method is an information based alternative to a direct plane finding through classical methods (i.e. RANSAC or Hough transform) or more recent ones like M-estimators [START_REF] Chen | Robust regression with projection based m-estimators[END_REF].

Experimental Results

In this section we show the benefits and limitations of our approach through some selected experiments using real data. In order to perform our experiments, we have built a wearable stereo device that consist of a stereo camera (Bumblebee Stereo Vision System T M , distributed by Point Grey Research Inc.) and a smallsize laptop (Intel Centrino Core 2 DUO 1.83GHz 2GB RAM) that we carry in a little backpack (Fig. 5). The whole system weighs approximately two kilograms. Bumblebee is a binocular stereo head with a 12cm baseline which provides 1024 × 768 × 2 color images at 14fps. The camera is pre-calibrated using Tsai's classic method [START_REF] Tsai | A versatile camera calibration technique for high-accuracy 3D machine vision metrology using off-the-shelf tv cameras and lenses[END_REF]. The system provides a software library that solves image acquisition, low level preprocesses, stereo correspondence and 3D reconstruction, with sub-pixel accuracy and different 3D filtering criteria.

The parameters of the experiments are described as follows: For the sake of efficiency, we use the minimum resolution of the camera (320 × 240). Given our previous experimental evaluations of the stereo head, our maximum range is 12m, being the average error below 0.91m for such distance. Under this resolution, the camera produces clouds of 10, 000 points on average which are typically reduced to 400 points in the feature extraction step, using |W| = 7 × 7 (size of appearance windows). The minimum number of correspondences to ensure the transformation is set to |M| min = 10. Local map building is performed with a maximum distance of K dmin = 7.0m. In the obstacle detection step, the distance to estimate the moving vector is K vm = 0.5m, the ratio between the boxes to classify as an aerial obstacle is set to K r = 3 and the minimum number of points to consider a obstacle is K np = 3.

The experiments are performed in an outdoor unstructured environment composed by grass and trees. The user followed an only trajectory composed by 753 observations, where only 315 were accepted (the ones whose transformation was meaningful enough), taken along 136.15m. In this case, no egomotion failures have been obtained. Then, the re-initialization of the map was not needed. The environment contains a lot of aerial (tree branches) and common obstacles (tree trunks). In Fig. 6 we show the eight parts of the environment where the algorithm detects an aerial obstacle. Only seven of them are real aerial obstacles. An only false positive is generated, where a trunk of a palm tree is classified as an aerial obstacle (second row, fourth column), while it should been classified as a common obstacle. Note that in some cases, the obstacle is not captured by the last observation (this is one of the reasons that force to use a local map).

In Fig. 7 In our implementation, we have divided the algorithm into two parallelized proceses: a first one that solves the local map building (image acquisition, stereo computation and egomotion) and a second one that solves the stabilization of the local map, obstacle detection and classification. The parallelization takes advance from the dual-core processor and the nature of the approach (that allows the separation) in order to minimize the time consumed by the algorithm (this parallelization saves arround a 31% of the computation time with respect to a linear one). At the bottom right part of Fig. 7 we show the time consumed by both processes. The red line represents the time consumed by the local map building process (318ms in average) in each iteration. The blue line represents the time consumed by the local map stabilization and the obstacle detection and clasification (306ms in average). The time consumed by the whole algorithm in each iteration is the maximum of both processes, that is, 364ms in average, that allows to perform the aerial obstacle detection at 2.75f ps.

Conclusions and Future Work

In this paper, we propose a novel approach for aerial obstacle detection using a stereo vision camera. The algorithm uses a local 3D map of the surroundings of the user in order to detect and classify the obstacles. The local map is approximated by a 6DOF egomotion algorithm and stabilized by an entropy minimization schema which continuously rectifies the global drift integrated with the trajectory. The use of a local map instead of a global one maintain the memory requirements and the processing time approximately constant. Once the map is built and stabilized, a geometric approach to predict the next pose of the user and detect the possible aerial obstacle is used. At the end of the paper we present some selected experiments, performed with a wearable prototype, in order to test our algorithm in a real situation.

Our future research includes a miniaturization of the prototype and a comparison with a 3D infrared camera, which combines infrared and vision technologies. IR cameras are usually more compact, faster and precise than stereo vision ones. Another future research consist of testing our prototype with a real blind in a more dynamic environment (for instance urban scenarios), in order to find all of the exceptional situations of the final user.

Acknowledgment

This research is partially funded by the projects the projects TIC2002-02792 and DPI2005-01280 of the Spanish Government.

Fig. 1 .

 1 Fig. 1. Aerial obstacle detection summary scheme. When a new observation is obtained, the egomotion algorithm estimates the related action using the new observation and the last one (top). Both elements (new observation and action) are registered in the local map (middle left). Then, the map is stabilized (middle center) in order to detect the obstacles (middle right). Red and green boxes (middle right in 3D and projected on the 2D reference images at bottom) represent the obstacle search volumes.

Fig. 2 .

 2 Fig. 2. Noise representation under the pinhole model (left). The larger noise of a point M it falls in the camera ray r i t , defined by the line that contains M i t and the center of projection Ct. Proposed point-to-point distance (right). In order to obtain the distance between two points Dpp(M i t-1 , Mj t ), we correlate two point-to-ray distances: Dpr(M i t-1 , rj t ) and Dpr( Mj t , r i t-1 ) (in green).

Fig. 3 .

 3 Fig. 3. Evolution of the entropy of the map over the Y marginal distribution HY (At) with respect to δz0 (top) and δx0 (bottom). The best aligned map (center) is obtained with the values that produces the minimum entropy.

Fig. 5 .

 5 Fig. 5. Wearable stereo device used in our experiments that consists of a Bumblebee stereo camera and a small laptop, carried in a little backpack.

Fig. 6 .

 6 Fig. 6. Outdoor trajectory in an outdoor unstructured environment. The eight points where an aerial obstacle is detected. See the text for more details.

Fig. 7 .

 7 Fig. 7. Number of points contained in the upper (top left) and the lower (bottom left) boxes in each iteration, and the ratio between them (top right). Time consumed by the algorithm in each iteration (bottom right). See the text for more details.

  we show some numerical information about the experiments. In the left part of the figure, we show the number of points contained in the upper

	(top) and lower (bottom) boxes (|B u t | and |B l t | respectively) in each iteration, as well as the ratio (1 + |B u t |)/(1 + |B l t |) (top right). As we can see, the eight aerial obstacles cited above are represented by the peaks with |B u t | > 2 and a
	ratio greater than 2.

Obstacle Detection and Classification

Once the local map is built and aligned with the horizontal plane, we proceed with the last step, that is, the obstacle detection and classification. First of all, we must approximate the user's 3D moving vector -→ v t in order to know the direction where we will look for the obstacles (note that the last pose provides the orientation of the camera, which differs from the moving direction). We extract -→ v t from the trajectory information as follows.

Consider the last pose of the camera p t and the previous one p k with the highest value of k which satisfy ||[x t , y t , z t ]-[x k , y k , z k ]|| > K vm . Then, the vector between both points provides our moving direction:

Note that K vm determines the smoothing of the resulting moving direction. In our experiments, we use K vm = 0.5m in order to avoid the little local movements of the user that differ from the real displacement.

Using -→ v t , the last pose p t and the magnitude of the last action a t (defined as l t = ||[δx t , δy t , δz t ]||), we can predict the 3D point where the camera could be in the next iteration: In this case, the user is notified by a high frequency sound. In other case, no warning is produced (when the number of points are similar or the number of points in the bottom box is greater, the obstacle could be detected by the walking stick). In Fig. 4 we show some representative situations.