当前位置:首页 >> >>

Navigation and Information System for Visually Impaired People

w A| y 5 4 3 2 1 0 . , +   ' &  $  " !       

Faculty of Informatics Masaryk University

Navigation and Information System for Visually Impaired People
by Ivan Kopeˇ ek c Pavel Smr?

FI MU Report Series Copyright c 1997, FI MU

FIMU-RS-97-05 May 1997

Navigation and Information System for Visually Impaired People
Ivan Kope?ek and Pavel Smr?
Faculty of Informatics, Masaryk University Brno Botanická 68a, 602 00 Brno, Czech Republic E-mail: {kopecek,smrz}@fi.muni.cz Abstract. Orientation is one of the most important problems of visually impaired people. The aim of this paper is to suggest a contribution to the solution of this problem using computer technology. The basic idea is the detection of motion and orientation using sensors and consequent position identi?cation. The detected trajectory is compared with a map and is corrected by means of the algorithm described in the paper. Some problems concerning sensor detection of human motion are also discussed. Based on the determined position other relevant information is provided to the user of system (information describing the neighbourhood of the actual position, optimal way to the chosen destination, possible warnings).



Contemporary information technology o?ers various possibilities for solving many problems of handicapped people. Serious impairment of sight is a considerable limitation for such people. The main problem is a substantial information de?cit and its feedback — communication barrier. Under normal circumstances about 80% of the processed information is mediated by the dominant sense – sight which is only inadequately substituted by touch, hearing and other senses. One of the most important problems of visually impaired people is orientation. This problem is usually solved in such a way that sightless people learn only several basic routes. Their orientation outside these routes is di?cult without additional information and can be, to a certain extent, even dangerous. Despite the growing attention paid to the problem of the orientation of blind people during the last years (see [1], [2], [3]), the problem is not su?ciently solved yet. The main goal of this paper is a presentation of some principles of navigation and information system for sight handicapped people. The purpose of the system is not to solve all the problems involved in orientation and route control of blind people but to serve as an additional tool which can help sightless people respecting their psychology and social feeling. Our idea is based on the following forethought: – State authorities own detailed town maps in a digital form of GIS (Geographical Information System) and they are likely to agree with their use for

orientation of sightless. – Multimedia sensors connected to computer system allow the orientation to be determined. This feature can be used for trajectory estimation. – It is possible to determine the position comparing the digital map in the computer memory and the calculation of trajectory of sightless using selfcorrecting algorithm. It is also possible to ?nd a certainty factor for the position determined and to tell to which extent this position is reliable. – In order to help the self-correcting algorithm to avoid situations when position determination is unreliable, estimating of the position by means of radio beacons on the frequency assigned for this purpose (88,790 MHz in the Czech Republic) and by the global estimation of position by GPS (Global Positioning Satellite System) can be used. – Graph algorithms allow the optimal path to be found from a given place to the chosen one (the shortest way need not be optimal from the view point of safety). – Using speech synthesis it is possible to inform the user about possible roadblocks and dangerous places and to pass him (requested) information about his environment. The system can work in two di?erent modes: 1. Navigation mode is based on the map. The system navigates and informs the user about the actual environment. 2. Learning mode is used when no map data are available. The system memorises the trajectory which can be used in future processing as a part of memorised map. For visually impaired people it is advantageous to choose a way that passes as few as possible crossroads and other dangerous places. For this purpose the length of each path section is weighted by safety factor. Then the common shortest path algorithm can be applied to ?nd the optimal path.


Position, Itinerary and Map — Formalisation

In this section we formalise the notions of position, itinerary and map. This is suitable for use of formal apparatus and for exact formulation of some intuitive terms. We will consider an itinerary as an indexed system of positions after each step. Each position in an itinerary can be described by system of attributes. For the real implementation of system such attributes as determined physical position, global or local changes of direction, sound environment, terrain characteristics, etc. can be used. From this point of view, the set of all positions forming an itinerary can be considered as a special case of Pawlak information system. Let us brie?y recall that Pawlak information system (see, e.g. [4]) is an ordered quadruple S = (U, A, V, f ) , where U is a set of objects, A is a set of attributes, V is a set of attribute values and f is a mapping of the set U × A into V . The sets U , A, V are supposed to be ?nite. 2

De?nition 1. A Pawlak information system P = (P, A, V, f ) with indexed set P is said to be itinerary. More formally, we suppose that a bijection I from P onto the interval (1, . . . , n) (where n is cardinality of P ) is de?ned. The elements of P will be called positions. The position P indexed by i (i.e. the position for which I(P ) = i) will be denoted by P (i). For 1 ≤ i ≤ n we denote P(i) the itinerary derived from an itinerary P by reduction of set P to the set {P (1), . . . , P (i)}. (This means, that P(i) forms a “subpath” of P from starting position to the position indexed by i.) The theory of Pawlak information system can be used e.g. for reducing of possible redundant attributes and for application of some algebraical methods (see [4, 5, 6]). De?nition 2. A map is a pair M = (Z, d), where Z is a set of itineraries with common set of attributes and d is a metric on the set of all possible positions (for any itinerary). For real implementation, d can be used in the form of weighted sum d(Pi , Pj ) =

αi da (fi (Pi , a), fj (Pj , a)),


where da is the metric associated to the attribute a and indices i, j are used to distinguish positions Pi and Pj . Suppose for instance that an attribute is of the type of local terrain characterisation. Then the metric associated to this attribute should express the measure of similarity between two instances of local terrain characterisation (value of the attribute of such type can be more complex than a real number, e.g. it can be a vector or matrix). The weights αi can be determined by heuristics or they can be obtained by experimenting and consequent evaluation of the optimal weights (for experiments done) by optimization methods. Determination of the values of position attributes for a map can be performed mostly automatically by computing the values of attributes from GIS maps (e.g. coordinates of position, global or local terrain characterisation, etc. ) and partly by experimenting with the system in the learning mode. If some data are incomplete the number of attributes can be reduced for the time before completion.


Algorithm For Computed Position Correcting

User trajectory is computed from a starting point at each step by determining the physical position of the feet by sensors. Error that appears in this process can be essentially reduced by comparing the attributes of actual position with the map. Unfortunately, the actual position of the user may not correspond to the path position (in the map) with the same index because step length can vary and because of physical position error. We use a modi?cation of DTW (Dynamic 3

Time Warping) algorithm (see, e.g. [7]) to overcome these di?culties. Let P1 , P2 be two itineraries belonging to a map M . We want to ?nd a correspondence f ? {P1 (1), . . . , P1 (n)} × {P2 (1), . . . , P2 (m)} which minimizes the expression d(P, P )
(P,P )∈f


under the following assumptions: 1. The correspondence f includes the pairs (P1 (1), P2 (1)) and (P1 (n), P2 (m)) 2. if (P1 (i), P2 (j)) ∈ f then exactly one of the following cases holds: (a) (P1 (i + 1), P2 (j)) ∈ f (b) (P1 (i), P2 (j + 1)) ∈ f (c) (P1 (i + 1), P2 (j + 1)) ∈ f Minimal value of the expression (2) under these assumptions will be denoted D(P1 , P2 ). (This value can be obtained by nonlinear programming methods.) It is easy to see, that {x|(x, y) ∈ f } = {P1 (1), . . . , P1 (n)} and {y|(x, y) ∈ f } = {P2 (1), . . . , P2 (m)} (4) Now, let P1 , P2 be itineraries belonging to a map M = (Z, d) and suppose P2 is the chosen “sample” itinerary whose physical positions were determined from a (physical) map. The user chooses this itinerary as the path he wants to follow. Suppose P1 is the path that was determined by the system from the starting position to the position indexed by i (i.e. position after i-th step). For the itinerary P1 the attribute of computed physical position is not precise and should be corrected. The correction is now obtained by the following steps: 1. Determine the index j, (1 ≤ j ≤ m) which minimises D(P1 , P2 (j)). 2. Substitute the value of the computed physical position attribute of the position P1 (i) by the analogous attribute value of the position P2 (j). This application of the DTW algorithm is motivated by the analogy with application of DTW algorithm for comparing spoken words (represented by sequences of acoustic vectors) and shows good practical results. (3)


Step Detection by Sensors

In this section we would like to illustrate some problems arising in sensor detection of human motion. We are searching for methods which are suitable for determination of a particular stage of each step, e.g. the moment of treading (i.e. when the foot is laid on the ground, risen, etc. ). These methods could be based on the following principles: – Detection of the de?exion from horizontal plane 4

– Detection of the side deviation from the vertical plane perpendicular to the walking direction – Detection of sensor vibration at treading The detection of the de?exion from horizontal plane can be used for step detection if the sensor (Virtual i-O 3D Sensor) is attached to tarsus. In Fig. 1 the change of the de?exion is shown for this case. When the foot is risen at walk the de?exion increases till the maximum value is achieved, it is changed in a particular way during the course of the step, and, ?nally, depending on treading style it returns from the maximum positive or negative value to the starting position. It may be concluded from our experiments that the use of this method is the most advantageous for detecting the time point of rising the foot from the ground. We are thus searching for places when the de?exion from the horizontal plane changes from zero value to maximal negative value. The most serious problems of this method are connected with shambling which is characteristic for old people. Also “tiptoeing” may lead to distorted results.

Fig. 1. Change of the de?exion from horizontal plane

Side deviation from vertical plane perpendicular to the walking direction can be used for step detection in case when sensors are attached to the thigh or shin. In Fig. 2 the changes of deviations from the vertical plane perpendicular to the walking direction are given. In most cases the maximum value is achieved at the moment of treading on the ground. This is the reason why we seek the maximum value in the graphic representation of step course. The method does not give good results for “marching”. When both above mentioned methods were tested problems appeared which were caused by the fact that sensors could not be ?xed on the leg tightly enough to prevent minor vibrations. In Fig. 3 the in?uence of these minor vibration on the change of the angle between monitored vector and reference vector (1, 1, 1) can be observed. Experiments showed that system behaviour in such case is rather regular. 5

Fig. 2. Change of the de?exion from vertical plane

This led us to attempts to use sensor vibrations at treading for step detection. In the graphic representation of angle changes we seek points near which the value is changing rapidly in all co-ordinates. The method works well in the case of quick paces, however, it gives wrong results if sensor vibrations are caused by other factors than treading.

Fig. 3. Sensor vibration at strong treading

From the above discussion it can be concluded that no step detection method gives satisfactory results in all cases. For this reason we have chosen a combination of the methods which is able to compensate a failure of one method by the reliable function of other methods. If one method detects a step a “voting” of all methods proceeds in which the vote of each method has a particular weight. These weights are generally dependent on the ground, walk characteristics, etc. 6

At present we are trying to estimate weights in particular cases on the basis of experiments. We are also testing the utilization of the learning mechanisms, especially neural networks [8], for automatic determination of weights from the experimental data.



The presented framework for trajectory determination and correcting combines the advantages of a system that can learn trajectory with determining the position using GIS and GPS and correcting it by other attributes detected or measured by sensors. Our present research concerns, besides the above mentioned problem, the topics of communication which should be carry out mostly by speech synthesis and recognition (see [9]). The further development of the presented framework will be directed toward experiments with precision and reliability of the sensors and building software components allowing to transform GIS data into a form suitable for system evaluation and testing the prototype of the system.

1. T. Aoki, Y. Yonezawa, K. Itoh, and M. Hashimoto. Intelligent guide system for parametric sound beam for the visually impaired. In J. Klaus et al, editor, Proceedings of ICCHP ’96, pages 637–644. Oldenbourg, Wien, 1996. 2. D. D. Clark-Carter, A. D. Heyes, and C. I. Howarth. The e?ciency and walking speed of visually impaired people. Ergonomics, 29(6):779–789, 1986. 3. H. Petrie and V. Johnson. Evaluation methodologies for navigational aids for blind people. In J. Klaus et al, editor, Proceedings of ICCHP’96, pages 653–660. Oldenbourg, Wien, 1996. 4. M. Novotn?. On sequents de?ned by means of information systems. Fundamenta Informaticae, 4:1041–1048, 1981. 5. M. Novotn? and Z. Pawlak. On a representation of rough sets by means of information systems. Fundamenta Informaticae, 6:289–296, 1983. 6. M. Novotn? and Z. Pawlak. Algebraic theory of independence in information systems. Fundamenta Informaticae, 14:454–476, 1991. 7. C. Myers, L. R. Rabiner, and A. E. Rosenberg. Performance tradeo?s in dynamic time warping algorithms for isolated word recognition. IEEE Transactions on ASSP, 28(6):623–635, 1980. 8. P. Smr?. Hybrid connectionist-symbolic models — integrating neural networks and rule-based approaches, 1997. (manuscript). 9. I. Kope?ek. Speech synthesis of Czech language in time domain and applications for visually impaired. In Matou?ek et al, editor, Proceedings of the 2nd SQEL Workshop, pages 141–144, Plzeň, 1997.

A This article was processed using the L TEX macro package with LLNCS style


Copyright c 1997, Faculty of Informatics, Masaryk University. All rights reserved. Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

Publications in the FI MU Report Series are in general accessible via WWW and anonymous FTP: http://www.fi.muni.cz/informatics/reports/ ftp ftp.fi.muni.cz (cd pub/reports) Copies may be also obtained by contacting: Faculty of Informatics Masaryk University Botanická 68a 602 00 Brno Czech Republic


walking : D:don't trust in others : 答案: 答案: B (3)、According to Marty Klein, a movie ____is most suitable for visually impaired people. ...
大学英语 A3
walking D:don't trust in others 答案: 答案: B (3)、 (3)、According to Marty Klein, a movie ____is most suitable for visually impaired people. ...
第四章 Visible Light Communications_图文
The neighbor information distribution system from a traffic light ? Indoor Navigation System:Indoor Navigation Prototype for the VisuallyImpaired using Visible ...
fact, moviemakers work very hard to make their films interesting visually....Marty Klein, a movie ____is most suitable for visually impaired people. ...
information on: 除了以上的那些,残疾员工还需要针对...for visually impaired guests their desire to be ...people have cleared the stairs before descent ...
time and space or objects and events 40 How can we increase the visually impaired person’s ability to travel through his physical and social environment...
The following information may help you. New Delhi,India British builders ...people worldwide are either blind or considered visually impaired(受损).They...

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。