395
1 INTRODUCTION
The main goal of the “Voice Maps” project was to
designandimplementafullyoperationalnavigation
system supporting movement of the blind. The
system should work properly in dense urban areas.
Thedevelopmentprocessconsistedoftwomainparts:
the creation of the prototype and the product
commercializationphase.Thesecondphaseincluded
fieldtestswithendusers.
Therearetwomainapproachestothevectordata
(Shekharetal.1999)storagemechanisms.Firstoneis
theremotedatabaseaccess(Google2013).Secondone
istokeepallthenecessarymapdatainalocalmobile
device
memory(Nokia2013).
Alloftheknownandinvestigatedbytheauthors
applications supporting navigation of the blind use
localmemory. Processed geographical dataisstored
onthe navigational devices, suchas smartphonesor
tablets (Sendero GPS 2013, Trekker 2013, LoadStone
2013).
In the first phase of the “Voice Maps” project,
whichconsistedofresearchandpreliminarysoftware
development, the systemprototype wassuccessfully
implemented.Itconsistedofmainmobileapplication
and,storedinlocaldevicememory,exemplaryspatial
datagatheredbytheauthorsandcooperatingproject‐
teammembersusingboth existing data sources (e.g.
OpenStreetMap)andin‐situdataacquisition
methods
(Kaminskietal.2011).
The application User Interface (UI) had to be
designed for the blind users. Developed solution
consistsofatouchscreen‐basedmainmenu,whichis
dividedinto12equalsquarefragments(Fig.1).The
options are chosen by moving the finger on the
screen.
Client-server Approach in the Navigation System for
the Blind
Ł.Markiewicz,K.Drypczewski,B.Wiśniewski&Ł.Kamiński
GdanskUniversityofTechnology,Gdansk,Poland
ABSTRACT: The article presents the client‐server approach in the navigation system for the blind‐ “Voice
Maps”.Theauthorswereamongthemaincreatorsoftheprototypeandcurrentlythecommercializationphase
isbeingfinished.Intheimplementedprototypeonlyexemplary,limitedspatialdata
wereused,thereforethey
couldbestoredandanalyzed(forpathfindingprocess)inthemobiledevice’smemorywithoutanydifficulties.
The resulting increase of spatialdata scale and complexity required a modification of the data storage and
operation. Consequently, the decision was made to maintain a central spatial database, which is
accessed
remotely.After that modification, themobileapplicationfetchestherequiredbatch of spatial data(with the
pathfindingandsearchresults)fromthecentralserverthroughthemobileinternetconnection,whichhasalso
become necessary for other purposes (e.g. voice recognition). The authors present the advantages and
disadvantagesofthis
newapproachalongwiththeresultsoftheserveroperationaltests.
http://www.transnav.eu
the International Journal
on Marine Navigation
and Safety of Sea Transportation
Volume 7
Number 3
September 2013
DOI:10.12716/1001.07.03.11
396
Figure1. Main menu of the application (Kamiński et al.
2011).
All of the available options are read to the user
usingthespeechsynthesis. Inputdata,e.g.addresses
or Point of Interest (POI) names, is entered using
dedicated and customized software keyboards (e.g.
gesture or voice recognition keyboard) built‐in into
theapplication(Fig.2).
In the preliminarydesign variousversions of
the
mobile application were to be created for different
mobileoperating systemsand they would be linked
by shared Java libraries. In the later stages of the
developmentprocessadecisionwasmadetofocuson
GoogleAndroidoperatingsystemanditscompatible
devices.Thischangewasbasedonthe
factthatother
planned platforms did not offer sufficient
functionality and have lostmost of its market share
(mainly Symbian and BlackBerry supported by
JavaME–Fig.3).
Figure2. Gesture keyboard for the blind (Kamiński et al.
2011).
Figure3. “Voice Maps” application on Android, Symbian
andJavaME(Kamiński2012).
The Android operating system definitely
dominatescurrentsmartphonemarket(Gartner2012)
and offers key features for the navigational systems
fortheblind.
The preparations for the commercialization are
currentlybeingfinished.Duringthelastprojectphase
itwasnecessarytoassesstheprototypeversionofthe
system,especiallythemobileapplication,
intermsof
using the system on the large scale. This evaluation
could not be performed only in the limited testing
environment. It quickly became apparent that the
datalocallystoredonthedevicewerenottheoptimal
option. Spatial data scale and complexity changed
significantlyandthesystemhad
toberedesignedin
ordertomodifythedatastorageandaccess.
After the modification, the mobile application
downloads through the internet necessary parts of
spatialdataon‐the‐fly,asitisneeded,remotelyfrom
the central server. This approach is new in the
navigationalsystemsfortheblindand
itsadvantages
and drawbacks, along with the data transition, are
beinganalyzedinthispaper.
2 COMPARISONOFTHEOLDANDNEW
SOLUTIONS
2.1 Theprevioussolution–datastoredontheclient
Figure4.Thefirstversionofthe“VoiceMaps”system.
The simplified diagram of the “Voice Maps”
system prototype is presented in the Figure 4. The
systemmodulesusedforthespatialdataacquisition,
storageandaccessare visualized at the bottom.The
firstversionofthesystemstoredallthespatialdatain
the central database. The data was then
converted
into“VoiceMaps”nativeformat(quadtreestructure)
and copied, as a whole, onto the mobile device
memory. The pathfinding between the current
position and the chosen destination (i.e. POI or
address) was performedon mobiledevice. Thiswas
donelocally,withoutneedtoestablishconnectionto
thecentraldatabase
(Stepnowskietal.2011).
397
Precision of built‐in Global Positioning System
(GPS) receiver is sufficient in the most cases
(Zandbergen & Barbeau 2011) and therefore it was
usedforpositioning.Thereisalsoanoptiontoreplace
itwithexternalDifferentialGlobalPositioningSystem
(DGPS) module in order to further increase the
accuracy.
While
performing the operational analysis of the
system prototype the project team have identified a
fewimportantissues.Those problems concernedthe
system design, authors recognized the modules that
needed to be redesigned and required to be
reimplemented. During the prototype phase of the
systemdevelopmentthespatialdatawaslimited
and
notverycomplex.Thereforethesolutioninwhichthe
spatial data were stored and processed locally
performed very well. With the acquisition of
consecutive data from other parts of Gdansk and
other cities it became apparent, that the
aforementioned solution was increasingly
inconvenientinthetermsof“VoiceMaps”navigation
system.
The spatial data updates in the previous system
version had to be done manually on each of the
devices.Theupdateprocessconsistedofcopyingall
the data from the central database onto the
smartphone. Despite providing the notification
mechanism implemented in the application, user
action was required during
each update.
Additionally, storage of the considerable amount of
data on the mobile device, in terms of the software
and hardware limitations, imposed the
implementationofthecomplexalgorithms,thatwere
optimizingthespatialdataaccesstime(i.e. quadtree
structure).Alsotheoptimalpathfindingbetweentwo
pointswasdoneonthe
mobiledevice,whichbecame
great issue due to limited computational power
comparedtothedesktopcomputer.
In order to solve these problems the authors
decided to change the model of data storage,access
andprocessing.Itwasdecidedtomoveapartofthe
functionality from the mobile device to
the remote
server.Alltherequiredchangesaredescribedinthe
nextchaptersofthispaper.
2.2 Thenewsolution–datastorage,searchingand
pathfindingontheserver
Duringthepreparationphaseitwasdecidedthatthe
bestsolutionistomoveallthegathereddataintothe
centraldatabase,
fromwhichonlynecessarypiecesof
information will be downloaded via wireless
connection by the mobile application. All the ma in
advantages and disadvantages of that decision are
presentedinthenexttwoparagraphsofthisarticle.
Themobileapplicationhasbecome a client,used
mainlytosendrequeststo the
database,providethe
user interface, positioning, navigation and to store
user’s configuration preferences. The server has
become more extensive as three new modules were
addedtoitsarchitecture(Fig.5).
Thosemodulesare:
Data sharing module, which allows mobile
application to download selected data from the
database,
POIFetcher,thatallows
tosearchfortherequested
PointsofInterest,
Routino (Routino 2013), a specialized module
whichfindsapathbetweentwogivenpoints.
The new solution is to provide the mobile
applicationwithfragmentsofdatathatdescribearea
in the closestsurroundings of their current location.
Provideddatadynamically
changewhenusersmove
toadifferentlocation,soapplicationalwayscontains
onlyinformationthatisneededtoguideusertoward
hiscurrentdestination.
In addition, the announcement module, which
used the voice synthesis, was also extended in the
mobileapplication.Itbecameapparentthatmessages
shouldsoundmorehuman‐like,
thereforespecialized
modulewas implemented toprocess the description
data of the nearest surroundings and prepare a
naturallanguagemessage.
All the data are not stored on the device in this
new solution, so the mobile application cannot
provide full search of the path whenever the
requesteddestinationpointis
outsidethetemporary
graph, because of this fact part of the new solution
was to transfer path searching algorithms onto the
server.Themechanismofpathsearchingisprovided
bythespecializedservermodule–Routino.
To keep up the most accurate Point of Interest
data,POIsalsoweremovedto
theserver‐sidecentral
database. The new solution is to keep POIs data on
the server and provide users with categories and
searchmechanisms.
Figure5. Changesinthe systemarchitecture forced bythe
adoptionofremotedatabaseaccess.
Application is always supplied with the most
current data and users can select categories (e.g.
“shops”,“restaurants”)andserverwillfindashortest
path from the userʹs current position to the nearest
POI from that category. The graph used in the
applicationistemporaryandthegivenrouteisstatic.
There is a need tosynchronize thesetwo sources of
dataeverytimeagraphofthenearestarea changes,
this functionality is performed by the mobile
398
application. The effect of this synchronization is
describedonFig.6.
Themostimportantpartofthedatastoredinthe
server is the graph representation of geographical
features.DataformatisstandardizedforGeographic
InformationSystem(GIS).OpenStreetMap(OSM)is
incorporated as the base layer of the spatial
data.
OSM is an open source project aiming to create an
editableworldmap(Hazzard2011).Dataisavailable
under a Creative Commons open content license.
OSMcontributorsperformregularsurveyswithGPS
devices,governmentandcommercialdatasourcesare
alsoused.
OSMspatialdatasetconsistsofthreetypes
ofdata
structures:
points,
lines(multilines),
polygons.
Points represent discrete places with defined
geographical position such as address points, Points
ofInterests(POI)orPointsofAttention(POA).Lines
consist of a set of points and segments which
represent linear objects (e.g. roads, sidewalks, rivers
orcrossroads).Polygons
includeasetoflineswhich
create bounded areas which represent buildings,
countryborders,etc.
Figure6. Graphof nearest surrounding synchronized with
foundpath.
Voice Maps is a system created for the
navigational assistance of the blind or visually
impaired. It requires a different data set than the
typical navigation systems (i.e. purposed for cars)
(Mayetal.2003).Accuratespatialinformationabout
sidewalks and pedestrian crossings are especially
importantandarenottypicallyincluded
inOSMand
otherpopulardatabasesasshownonFig.7.
It was decided that additional data is required.
Survey was performed by the project cooperator,
OPEGIEKALLC,forthetestareaofthecityofElbląg
inPoland.Acquireddatacontainsinformationabout
crossings, addresses, surroundings description (i.e.
POI
/POA)andcorrectionstotheOSMdata.
Client application is a front end of the “Voice
Maps” system. The mobile application, a client, is a
proxybetweentheuserandserver‐sidemodules(e.g.
geospatial database, algorithms). Touch screen
interface allows blind user to utilizeall functions of
theproject.
“VoiceMaps”canalsobecontrolledwith
the voice commands. Voice recognition is
implemented using Google API. When user selects
thisoptionthevoicesampleisrecordedonthedevice
andthensentthroughtheinternettoGoogleservers,
whereitisanalyzedina matterofseconds.Afterthat
the set of the most probable text strings, which
represent the content of the user’s speech, are sent
back to the mobile application. These strings are
mainlyusedtochooseoptionsinthemainmenuorto
input data (i.e. addresses, POI). This method is
provedtobethemostcomfortable
fortheblindusers,
whereas the visually impaired preferred dedicated
softwarekeyboards.
Figure7.OSMdatawithoutsidewalksandzebracrossings.
Using touch screen the application can be
configuredwith several options, whichare available
in the “Settings” menu. It allows to change the
application‐user communication. User can decide to
be additionally informed about the azimuth or
distance to the current path destination or the next
pathnode.Applicationcanalso
informtheuserabout
thedetailsofthesurroundingarea(i.e.surfacetype,
obstacles)andtheclosestPOI,POA,addresses.
“VoiceMaps”systemismainlytargetedforusers
in the urban areas. It requires not only
aforementioned spatial data but also high accuracy
positioning. Depending on available hardware,
applicationcan
receivecurrentgeographicalposition
from built‐in GPS device or external DGPS receiver
whichtypicallyprovideshigheraccuracy(Monteiroet
al.2005).
3 FEATURESOFTHENEWSOLUTION
3.1 Theadvantagesofthenewsolution
Applications purposed for the blind should be
maximallyeasyto use. Alltheactivitiestakenby
its
users have to be repetitious and also should take
minimumefforttobelearntandremembered(Farrel
1956). Number of actions performed bythe blind to
achieve their goal must be minimal. All of the user
actionsrequire simplicity,forexample intheremote
data access the latest version
of the software is
399
acquired in the easiest manner possible, simply by
running the application and sending queries to the
server.Sincethemostofthedata,whichisthegraph
representationofgeographicalfeaturesalongwithits
description,iskeptontheserverside,noactionfrom
the user is required to receive
updated data.
Moreover, some enhancements and improvements,
likepathfindingorPOIsearch,canbeaddedwithout
changingtheclient.
Navigation system forthe blind isdifferent from
typicalcarnavigationsystems(Millonig&Schechtner
2005, Aslan et al. 2006). Providing direction for
sightlesspedestrian requires muchmorepreciseand
accurate
data including userʹs current position,
directions and information about the nearest
surroundings.Thetargetusersof“VoiceMaps”have
thelimitedability to orientate and identify obstacles
in their nearest surroundings – given information
mustbe as exactas possible.One of theelements is
thehighdensitygraphrepresentation
ofmetropolitan
areas’ geographical features, which may contain a
largeamountofverticesandedges.
Significant computational power is required to
performprocessingofthatamountofdata.It isalso
required to assure considerable memory capacity.
Since “Voice Maps” system is targeted for the
Android‐based smartphones the issue
of the mobile
device capabilities becomes important.Moving most
of thegeospatial data from client to server not only
reducesthe size of thesoftware, but alsolowers the
systemrequirements.Itisespeciallyimportantforthe
olderdevices.
What is also worth mentioning, the spatial
databaseandelementsofthe
server‐sidesoftwarecan
be used in other Geographic Information Systems
(GIS). The existing high‐density data and advanced
graph algorithms can be easily adapted to become
elements of different (e.g. car or pedestrian)
navigationapplications.
Thenewsolutionmakesapplicationdevelopment
lessdifficult.Thoroughandwidetestingofsoftware
is easier to perform thanks to the availability of the
serverlogs.Moreover,itenables thepossibilitytoadd
severalenhancementstothesystem,forexamplethe
functionalitytoremotelymonitorthebehaviourofthe
blind.
3.2 Thedisadvantagesoftheremoteserveraccess
Remote spatial database access in “Voice Maps”
requiresstablewirelessinternetconnection.Sincethe
navigationsystemfortheblindmustbeveryreliable,
various problems with network (including lost
connection, transfer speed or limits and lost signal)
may become very important. However, nowadays,
coverageof the cellular networkin themetropolitan
areasisusuallyhighandshould
besufficient.When
userreceivesinformationaboutgeographicalfeatures
located in a fixed distance from his position,
additional data are sent only if he leaves the
aforementionedarea.Thiskindofapproachnotonly
limitstheneededtransfertominimumbutalso,ifthe
connection is temporarily lost, ensures data
availability.
Itis also worth mentioningthat module
for spatial database access is not the only software
component that needs stable internet connection.
Sincethevoicerecognitionsoftwareisincorporatedin
“Voice Maps”, wireless internet connection is
necessary.
Intheprevioussolution,themosttime‐consuming
operations,likepathfindingandsearch
forrequested
vertexinagraph,wereperformedontheclientside.
In the new solution all of those operations are
executed on the server. This approach requires a
sophisticated server infrastructure. Moreover,
considering the characteristics of blind users, the
qualityofthatservicemustmaintainaveryhighlevel
of
reliability. Therefore, the new solution enforces
keepingconsiderablyexpensivedatacenter.
Communication with remote spatial database
created non‐trivial problems in the software
development. The issues of synchronization with
database processes (such as response time, network
delay)andclient‐sidethreadsareonlyapartofthem.
Ontheother
hand,newversionof“VoiceMaps”does
notrequireadvancedmethodsforoptimizingthesize
of the files containing information about the
geographicalfeatures(e.g.quadtree).
4 SERVEROPERATIONALTESTS
After the system prototype completion a set of
software simulators were implemented in order to
check server operation in various conditions,
regarding the performance of commands executions
anddatatransfereffectiveness.Themaingoalwasto
measuretheaverageresponsetimeoftheserverwhen
1000queriesarebeingsentatthesametimefromthe
simulatedmobileapplications.
The first test evaluated the time needed for the
creation of the
graph based on the OSM geospatial
data.Queriesweresenttotheserverandtheaverage
time of the graph creation was 297 milliseconds
(Figure 8). This delay is not noticeable for the user.
The maximum value was about 2.6 seconds, but it
wasconcludedtobecausedbythemobile
connection
problems,notthemobileapplicationorserveritself.
During the next test the effectiveness of the POI
generation for the nearest area of the user current
geographical position was measured. The average
response time was about 60 milliseconds, so taking
intotheconsiderationthattypicaluserwillnotmove
fasterthan1m/s,theprocessisalmostinstantaneous
anditissufficientforpedestrianmovement.
Figure8. Distribution graph of the measured system
responsetimetoarequestforgraphcreation.
400
Figure9. Distribution graph of the measured system
responsetimetoarequestforgenerationofanewroute.
The third and the last test was checking the
performance of the Routino pathfinding module on
theserver.Queriesforvariouspathswere sentfrom
the mobile applications and the average time of the
shortest path generation for the selected destination
(within one city) was 110 milliseconds and the
maximumtime
was190milliseconds(Figure9).From
these values it can assumed that the pathfinding
server module response time is sufficient for
navigationalassistance during the typicalpedestrian
movementintheurbanareas.
Theresultsoftheservertestsalongwithsuccessful
field tests of the mobile application show that the
“VoiceMaps”serverisoperationalandthesystemas
awholeisreadyforthecommercialdeployment.
5 SUMMARY
Test results of the new solution are verypromising.
Instead of performing difficult and time‐consuming
calculations, the application now focuses on a user
and navigation interaction. There is still room for
some improvements in the future, but for the time
beingthesolutioniswellratedbytheendusers.Most
offunctionalitytrials,alongwithapartofreliability
andservertests,wereperformedbytheendusers.
The main advantage of the new solution is an
increase of time
efficiency for both the users and
developers of the system. Updates are no longer an
issue,astheyarenowperformedontheserver.This
assures that user always gets the most current data.
The application is lighter and, which is important,
needslesscomputationalpower–thatalsomeansless
battery consumption. Main calculations are
performed on the server and downloading data
became the most time‐consuming task. However,
remotedataaccesscausesthemaindisadvantage,i.e.
a need for the server and a reliable network
connection.Thefirstoneisanimportantarchitectural
problem, while the second is not
very significant in
theeraoffastandomnipresentinternet.
Asignificantadvantageofthepresentedsolution’s
strengthsoveritsdrawbacks,aswellasencouraging
testresults,confirmourbeliefthatthesystemdivision
into client and server side (along with the remote
databaseaccess)isthebestsolutioninthe
navigation
systemsfortheblind.
ACKNOWLEDGEMENTS
This research work is a part of the “Voice Maps”
project,whichwassupportedbyNarodoweCentrum
Badan i Rozwoju (National Center of Research and
Development) within theʺIniTechʺ program (project
code:ZPB/37/67901/IT2/10).
We are highly grateful to Polski Zwiazek
Niewidomych (Polish
Association of the Blind) in
Elblag(ledbyMrs. JaninaMaksymowicz),Mr.Rafał
Charłampowicz and Dr. Ryszard Kowalik for
participatinginoursystem’stestsandsupportingthe
teamwithusefulsuggestions.
REFERENCES
AslanI.,SchwalmM.,BausJ.,KrügerA.,SchwartzT.2006.
Acquisitionofspatialknowledgeinlocationaware
mobilepedestriannavigationsystems.MobileHCIʹ06
Proceedingsofthe8thconferenceonHuman‐computer
interactionwithmobiledevicesandservices:105‐108.ISBN
1‐59593‐390‐5
FarrelG.1956.TheStory
ofBlindness.HarvardUnversity
Press.
Gartner.2012.WorldwideSalesofMobilePhonesDeclined3
PercentinThirdQuarterof2012;
SmartphoneSalesIncreased47Percent,source:
http://www.gartner.com/it/page.jsp?id=2237315
Google2013.GoogleMapsDeveloperDocumentation,source:
https://developers.google.com/maps/documentation/
HazzardE.2011.OpenLayers2.10BeginnerʹsGuide.Packt
Publishing.ISBN978‐1849514125.
KamińskiŁ.,ChybickiA.,BrunieckiK.&StepnowskiA.
2011.Smartphoneapplicationsupportingindependent
movementoftheblind.TheFuturewithGIS.Hrvatski
InformatickiZbor‐GISForum2011,Croatia.
Kamiński,Ł.2012.Mobilnysysteminformacjiprzestrzennej
wspomagającynawigacjęosóbniewidomychwterenie
miejskim(inPolish).PhDthesis,Gda
ńsk,Poland.
LoadStone2013.LoadStone,source:http://www.loadstone‐
gps.com
MayA.J.,RossT.,BayerS.H.2003.Pedestriannavigation
aids:informationrequirementsanddesignimplications.
PersonalandUbiquitousComputing7(6):331‐338.
MillonigA.,SchechtnerK.2005,DevelopingLandmark‐
BasedPedestrian‐NavigationSystems.Intelligent
TransportationSystems,IEEETransactions8(1).
MonteiroL.S.,Moore
T.,HillC.2005.Whatistheaccuracy
ofDGPS.JournalofNavigation58(2):207‐225.
Nokia2013.NokiaMapsUserGuide,source:
http://nds1.nokia.com/
files/support/global/phones/guides/Maps_3_0_UG_SR1_
1_No_Touch_EN.pdf
Routino2013.Routino,source:http://www.routino.org/
SenderoGPS2013.SenderoGPS,source:
http://www.senderogroup.com
ShekharS.,ChawlaS.,RavadaS.,FettererA.,LiuX.& Lu
C.
1999.SpatialDatabases‐Accomplishmentsand
ResearchNeeds.IEEETransactionsonKnowledgeand
DataEngineering11(1).
StepnowskiA.,KamińskiŁ.,DemkowiczJ.2011.Voice
Maps–thesystemfornavigationofblindinurbanarea.
Proceedingsofthe10thWSEASInternationalConferenceon
AppliedComputerandAppliedComputationalScience,
Venice,Italy.
Trekker2013.Trekker,source:
http://www.humanware.com/en‐usa/products
Zandbergen P. & Barbeau S. 2011. Positional Accuracy of
Assisted GPS Data from High‐Sensitivity GPS‐enabled
MobilePhones.JournalofNavigation64(03):381‐399.
