International Journal of Advanced Robotics
and Automation

This paper presents a wearable indoor navigation system that helps visually impaired user to perform indoor navigation. The system takes advantage of the Simultaneous Localization and Mapping (SLAM) and semantic path planning to accomplish localization and navigation tasks while collaborating with the visually impaired user. It integrates multiple sensors and feedback devices as an RGB-D camera, an IMU and a web camera; and it applies the RGB-D based visual odometry algorithm to estimate the user’s location and orientation, and uses the IMU to refine the orientation error. Major landmarks such as room numbers and corridor corners are detected by the web camera and RGB-D camera, and matched to the digitalized floor map so as to localize the user. The path and motion guidance are generated afterwards to guide the user to a desired destination. To improve the fitting between the rigid commands and optimal machine decisions for human beings, we propose a context based decision making mechanism on path planning that resolves users’ confusions caused by incorrect observations. The software modules are implemented in Robotics Operating System (ROS) and the navigation system are tested with blindfolded sight persons. The field experiments confirm the feasibility of the system prototype and the proposed mechanism.

Keywords: Assistive Navigation; Context Based Decision Making; Wearable System; Visually Impaired;

According to the factsheets of the World Health Organization (WHO), 285 million people worldwide are blind or partially sighted [1]. People with normal vision orient them in physical space and navigate from place to place with ease. However, it is a challenging task for people who are blind or have significant visual impairment to access unfamiliar environment even with the help of electronic travel aids and vision techniques. Most of the existing travel aids transform the visual and/or range information to tactile display or audio guidance that informs the user of nearby obstacles. These devices can be cane fitted handheld or wearable devices to warn of obstacles ahead [2-6] or provide ‘turn by turn’ guidance. The ability of visually impaired people to access, understand, and explore unfamiliar environment will improve their inclusion and integration into the society. It will also enhance employment opportunities, foster independent living and produce economic and social self-sufficiency [7].

After consulting with the blind individuals in organizations such as the Lighthouse International NY, Computer Center for Visually Impaired People (CCVIP) at CUNY Baruch College, New York Institute for Special Education (NYISE), and the New York State Commission for the Blind and Visually Handicapped (CBVH), we realize that visually impaired people demand an assistive technology that can provide them with safe and smooth way-finding capabilities. Unfortunately, existing related assistive technologies have various drawbacks and limitations.

SLAM is a process of building a map of unknown environment while at the same time localizing the robot within the map. As an extension of our previous works [17-20, 37] to further improve the existing techniques in visually impaired user navigation, we present the SLAM based navigation system using multiple sensors which specifically fits the demand of visually impaired user navigation in terms of reliability. Figure 1 shows the system at work. It takes advantage of the SLAM technique to fuse the inputs from multiple sensors and localize the user on the floor plan, and represents the information and guidance in a high level semantic map which contains necessary abstracted information for human being.

Path planning for visually impaired is different with those for robots. There are numerical optimal/suboptimal solutions that handle uncertainty and incomplete information for robots. However, as a human-centered system, the navigation system shall seek to provide smooth and reliable user experience while considering the facts that visually impaired users are prone to be confused if conflicted or rigid commands are presented. Thus, we propose a context based decision making mechanism in path planning which fits the need of the navigation system. It takes advantage of the fact that the goal is to reach the destination

while it is not necessary to guarantee the perceptions are always correct during the trip. The mechanism is flexible and capable of being tailored to specific cases based on needs. This work is an extension of our previous works [28-30, 37].

Contributions of this work are two folds. First, we developed a wearable navigation system that guides the user navigating from place to place. To the best of our knowledge, this is the first system that performs SLAM and semantic path guiding on the captured floor map. Second, we proposed a context-based path planning mechanism that efficiently utilizes the user-oriented data with uncertainty and specifically fits the need of visually impaired navigation. The path planning mechanism takes advantage of the property that motions can always be correct even if the partial perceptions during the trip are wrong. To the best of our knowledge, this is the first path planning mechanism that provides smooth and reliable guidance while wrong observation on landmarks may be presented in the context of visually impaired navigation. The prototype is implemented and tested.

This paper is organized as follows. related works; system architecture and illustrates the details and algorithms in the SLAM based navigation; context based decision making on path planning; system implementation with experimental results and ends with conclusion and the future works.

Starting from section III, the term “visually impaired user” with “user” and “door number” with “room number” are interchangeably used.

A number of works implemented inertial sensor to track and localize the users [9-11]; however they lack accuracy and reliability for blind user navigation. GPS/ GIS based approaches fit to outdoor navigation demands but are powerless in indoor applications [12-15].

Yang et al. proposed a localization system that uses accelerometer embedded in a mobile phone to track a person in a pre-collected RSS (received signal strength) map [16]. However, the RSS finger print based corrections requires considerable pre-installations and pre-processing in creating the RSS map. Moreover, it uses step counters and compasses for pose estimation, which has accumulative errors over time. The same problem happens to the localization and tracking system using WiFi signal proposed by Kannan [17].

In recent years, there have been a few attempts to apply SLAM technology in assistive navigation for visually impaired people. The SWAN project [15] developed a software engine using the Monte Carlo Localization and count on GPS for pedestrian outdoor navigation. The research emphasis is placed on sonification to guide the blind user; leaving many research issues untouched such as how to detect environment features for updating believe.

The “Navatar project” [18] employs an IMU in the smartphone and use a particle filter algorithm to help visually impaired persons for indoor navigation. However, it assumes the indoor map is known as a priori through manual annotation and uses human as sensor to detect simple landmarks (i.e., intersections of hall ways and open doors). This landmark confirmation by the user is prone to false alarms since the multiple landmarks may not be distinguishable by touch.

Lan et al., proposed an indoor localization system that tracks a person using the accelerometer embedded in a waist mounted mobile phone. It utilizes a floor-plan map to calibrate the direction errors from the gyroscope by comparing the layout of the building and the trajectory taken by the user [19]. However, the localization is based on dead reckoning and lacks landmark correction.

A Co-robot Cane prototype is developed to aid the visually impaired navigation. It uses a mounted 3-D camera to estimate the pose, and a web-camera to recognize the major objects while traveling. A reasonable possibility of success is proved in the experiment. However, how to handle to failures is not mentioned.

Researchers have made significant progress in applying advanced technologies in computer vision, robotics and artificial intelligence to improve mobility and navigation of people with special needs Y.H. Lee et al [20-22]. used a Kinect sensor to extract orientation information of the blind users, by incorporating visual odometry and feature based metric-topological SLAM [27]. An improved work utilizes the spatial feature and IMU to guarantee the correctness of localization, under the condition that the scenario has to be a traveled place [38].

Although a good number of navigation solutions for visually impaired are presented, little of them provides a feasible solution while incorrect observations are presented. The interactions are not truly considered human-centric since the needs of visually impaired are not taken good care. Be different with normal sighted user, the visually impaired may not be able to provide that feedback to correct error caused by sensor. On the other hand, incorrect observation may frustrate the user while navigating, especially when being guided walk back and forth. Fortunately, in indoor navigation, the paths to the destination are very limited, one or more wrong perceptions on landmarks do not instantly lead to a different path. As long as later perceptions can correct the overall understanding of the on environment so that the user can be guided to the destination smoothly.

Our system uses a web camera and a 3-D camera to percept the landmarks to localize the user on a digitalized floor plan. A semantic map is abstracted to make the navigation feasible. A context based path planner generates path and motion guidance to user.

SLAM is a technology successfully used in robotic navigation, which maintains a probabilistic representation of both the subject’s pose and the locations of landmarks (i.e., the “belief” of subject’s location and a “map” denoted with landmarks), and refines recursively the pose representation and map in two steps (i.e., motion and correction steps) [23-26]. In the motion step, the robot pose is predicted using the robot motion model. In the correction step, observations of landmarks are used to refine the probabilistic pose representation on the map while simultaneously updating the map with latest detected landmarks.

The SLAM principle is analogous to the navigation scenario where a visually impaired user is required to find a conference room in an office building. If a floor plan is accessible, i.e., captured by head mounted camera or downloaded from the internet, the system can digitalize it into a map before performing path planning and navigation. The system can localize the walking user by comparing the salient landmarks (e.g., door numbers) on the map. The motion and observation steps continue until the user reaches the target place.

Assistive navigations are challenging because the user not only needs decent perception of the map of surroundings but also demands suitable planned path to accomplish the navigation.

Figure 2 illustrates the system architecture. The hardware includes wearable sensors including camera, IMU and RGBD camera, interactive devices including speaker and bone headphone and processing units including a laptop. The software is composed of nine cooperative sub-modules. As follows, to clarify their functionality, we introduce the software sub-modules in the presence of a navigation scene.

As requested by the Fire Departments in most cities in US, floor plans shall be posted at the entrances to all required exit stairs, every elevator landing, and immediately inside all public entrances to the public buildings. Thus, the user can use the head mounted camera to scan and extract the floor plan before digitalizing it into a grid/semantic map, by using the floor plan digitalization module, right after he enters a building or leaves an elevator. The user needs to let the system know the destination room through the speech recognition module so as to trigger the navigation. While moving, the user is localized by the visual odometry module using RGB-D camera [21]. The user

can request the detection of room number by the door number extraction module using camera when he touches the door. In the meantime, the corners will be automatically detected by the corner and wall detection module using depth images from RGB-D camera. The door numbers and corners are regarded as landmarks so as to match with the digitalized floor plan map as well as update the particles through SLAM module. The IMU is equipped to complement the orientation errors. A further orientation revising is performed through the corner and wall detection module. The path is planed through the path planning module, where the context based decisions are made and delivered to the user as motion commands and hints through the text to speech module.

We apply our previous work -- fast visual odometry using RGB-D camera [8] to provide raw pose of the user. It aligns sparse features observed in the current RGB-D image on a model of previous features. The model is persistent and is dynamically updated from new observations using a Kalman filter. The algorithm is capable of closing small-scale loops in indoor environments online without any additional SLAM back-end techniques; but like all other visual odometry approaches, it has accumulative drifts over long time in the motion from place to place. The drifts are revised using the IMU and further corrected using the wall border extracted from depth images as described later.

At the same time, the depth images which are obtained by the RGB-D sensor and presented in the form of 3D point clouds are projected onto the planar coordinate and then stacked together based on the corresponding poses estimated by the visual odometry. Particularly, the system keeps only the depth planar map with respect to the recent poses within certain travel displacement as shown in Figure 3.

In order to make the user aware of their physical locations, contextual information from visual landmarks such as floor plan with signage, room number and corners are parameterized to the

digitalized semantic map as in Figure 4.

Floor map digitalization: A heuristic method of extracting layout information from a floor plan that employs room numbers and corners, etc. to infer landmarks and way points are used [29]. A rule-based method is implemented to localize the position of all room number labels as in Figure 5. Then the range of the rooms and positions of their doors in the floor map are searched by using a vertical and horizontal scan from the region of room number. Assuming that all the rooms have their doors on the hallway, anchor points are generated by using the room number labels and corners.

Landmark extraction and matching: The visual landmarks in the immediate vicinity of the user such as room numbers and corners are extracted to localize the user.

A) An optical character recognition algorithm [31] is used to localize the user when the user travels to the corresponding physical locations. Specifically, the door number is extracted after the user actively triggers the recognition through a verbal command “door number detection” after he perceives the existence of the door through the sense of touch. The benefits are of two folds: one is to minimize the false alarm of un-wanted misdetection; another is to greatly save the processing power by image processing. If the detection fails to get any meaningful result, it will prompt the user to trigger detection again.
B) The real-time depth images from the RGB-D camera are used to detect corners. Specifically, the consequential depth images from time to time are aligned using the raw poses obtained by visual odometry. Thus, at a given time, the depth image to be processed is the stacked depth image after overlapping recent depth images according to their poses in the visual odometry. The period is restricted by the measurement of physical displacement calculated through visual odometry. Since the visual odometry drift in a short period is not heavy, the resulting stacked depth image is a good approximation to the shape of the surrounding as shown in Figure 3.

Then the border is extracted after projecting the depth image into horizontal plane. A revised Hough Transform [32] after the Harris operator [33] is applied to obtain the corner candidates from the image of extracted borders. The corner candidates are confirmed as detected landmarks only if being

further confirmed by a shape filter of the stacked depth image. The intuition is straight forward: since the stacked depth images are always within an arbitrarily given displacement, it is easy to perceive corners because the depth image is changing from long and thin to short and thick (or long and thick) when approaching a corner.

After being confirmed, the corner candidates are matched with the corner sets in the floor map to update the particles. Particularly, the matching criterion is loosened, and thus a corner perception will enlarge the weight of particles around a few similar corners. This eliminates the possible failure caused by false alarm and yet is sufficient in application.

C) At the same time, the scale between the metrics in the floor plan and the real time scan can be obtained. As shown in Fig. 6, the right hand side is the planar surrounding obtained from the depth image of RGB-D while detecting a landmark and the left hand side is the corresponding surrounding of the same landmark on the floor plan. By comparing the width of the corridor next to the corresponding landmark, the scale between the metrics in the real time navigation and the floor plan can be easily calculated and recursively updated.

Speech recognition module and text to speech module are used to bridge the perceptions of the user and the system. Details of the implementation using open source libraries [34, 35] are illustrated in Implementation and Experiments section.

If the digitalized floor plan is treated as a map and the doors and corners as landmarks, the localization of the user on the floor plan with doors and corners labels is analogous to the localization of a moving object on the map with preregistered landmarks. Taking advantage of the integrated sensors, the prediction phase adopts motion estimations from visual odometry module and IMU, while the correction phase receives landmark confirmations from door number extraction as well as corner and wall detection.

Particle filter: Particle filter is used to estimate the pose distribution of the subject. x is used to denote the state, u the motion input from visual odometry, s the measurement of door number, z the measurement of corner and λ the measurement of wall angle.

The localization state is represented through a set of particles in the 2D planar space $\{x^{(i)}={(x,y,\theta )}^{(i)}\}\in {\Re }^2\times [\mathrm{0...2}\pi )$ as $$p(x)\approx \frac{1}{N}{\displaystyle \sum _{i=0}^N{\delta }_{x(i)}(x)}\text{ (1)}$$ $$p(z_t,s_t,{\lambda }_t|x_t)=p(z_t|x_t)p(s_t|x_t)p({\lambda }_t|x_t)$$ $$R(\alpha )=\left[\begin{array}{cc}\cos \alpha & -\sin \alpha \\ \sin \alpha & \cos \alpha \end{array}\right]\text{ (3)}$$ $\begin{array}{l}\overline{\underset{\_}{\underset{\_}{\text{Algorithm 1 }}}}\\ \text{1: Initialization}\\ \text{2: stage}\leftarrow \text{preliminary }\\ \text{3: }{}^A{\theta }^{\prime }={}^A\theta -{}^B\theta \\ \text{4: }while\text{ (undone) }\\ \text{5: updateVisualOdom}({}^A\upsilon ,{}^A\theta )\\ \text{6: }{}^A{\theta }^{″}\leftarrow {}^A{\theta }^{\prime }+{}^B\theta \\ \text{7: }if(\text{newLandmarkDetected \& stage==preliminary})\\ \text{8: }if{(}^W{\upsilon }^{\prime }\text{==null})\\ {\text{9: }}^W{\upsilon }^{\prime }\leftarrow \text{landmark position on }W\\ \text{10: }{}^A{\upsilon }^{\prime }\leftarrow {}^A\upsilon \\ \text{11: }else\\ {\text{12: }}^W{\upsilon }^{″}\leftarrow \text{landmark position on }W\\ \text{13: }{}^A{\upsilon }^{″}\leftarrow {}^A\upsilon \\ \text{14: }{}_A{}^{W}t{\leftarrow }^W{\upsilon }^{″}-{}^A\upsilon \\ \text{15: }\alpha \leftarrow \angle {(}^W{\upsilon }^{″}{-}^W{\upsilon }^{\prime })-\angle {(}^A{\upsilon }^{″}{-}^A{\upsilon }^{\prime })\\ \text{16: }{}_A{}^{W}R\leftarrow R(\alpha )\\ \text{17: stage}\leftarrow \text{Normal }\\ \text{18: }end-if\\ \text{19: }end-if\\ \text{20: }if(\text{newLandmarkDetected \& stage==Normal})\\ \text{21: }if\text{ (door||corner) }\\ \text{22: partileCorrectionPhase() }\\ \text{23: }{}_A{}^{W}t\leftarrow \text{localizationStateUpdate(partiles) }\\ \text{24: }end-if\\ \text{25: }if\text{ (wall) }\\ \text{26: }{}^A{\theta }^{\prime }\leftarrow {}^w\theta {}_{wall}+({}^A\theta -{}^A\theta {}_{wall})-{}^B\theta -\alpha \\ \text{27: }end-if\\ \text{28: }end-if\\ \text{29: (}{}^W\upsilon ,{}^W\theta {)}_{current}={}_A{}^{W}T({}^A\upsilon ,{}^A{\theta }^{″})\\ \text{30: (}{\delta }_{trans},{\delta }_{rot})\leftarrow {\text{(}}_{{}^W\upsilon }-{\text{(}}_{{}^W\upsilon }\\ \text{31: partilePredictionPhase() }\\ \text{32: }end-while\\ \overline{\overline{}}\end{array}$