Low Cost Interactive Area of Interest Locator

Annie Hii Toderici

Annie Toderici is a graduate student majoring in Computer Science at San Jose State University. Annie has received her B.S. degree from the University of Houston, Texas. Her primary areas of interest are Computer Information Security and Data Mining.


Abstract


While printed maps are broadly used to locate places, interactive maps are still in their infancy. The most popular use of this technology is Global Positioning System Navigation (usually for vehicles). Other than that, most interactive maps are used to locate smaller areas of interest such as stores in the shopping mall. In this paper, we focus on locating items in the libraries. We propose to use the library's existing unique barcode system which identifies books within the library as the key and aisles as the areas of interest.

This research is conducted at the Mountain View Public Library. All the ID ranges of the books are read and stored in a database, and then the data are used to identify the exact shelves in the library. We used SVG to represent the exact aisle and shelf of the book or item in the library.


Table of Contents

Introduction
Development and Implementation
Data Integration
Image Design
Conclusion
Bibliography

Introduction

This project focuses on a subset of the mapping problems. In particular, we focus on localization problems applied to physical structure where there exists a depiction of the map, which has some areas of interest that have to be quickly accessible and made obvious. For instance, a shopper in a mall may want to know where a specific store is located (i.e., the key is the store name, and the area of interest is the store). In a traditional non-interactive mapping system, a normal use-case is looking up the directory of the mall, and spending a significant amount of time locating the numbers presented in the index onto the map. Another use-case is locating the shelf for a specific book in a library, and this paper focuses on this problem

Libraries have their books, journals, articles, multimedia collections, and various other items categorized and placed on the shelves with related topics. However, for someone who is not familiar with the shelves' location, finding the needed book or item is time consuming or even frustrating. There is an open research field trying to address this problem. Some approaches use Radio Frequency Identification (RFID) technology with Bluetooth [1] , while others use Infrared Data (IrDA) Association communication modules with Light Emitting Diode (LED) [2] , or even use GPS [3] technique to locate the target item. However, these methods will be costly since libraries need to install these systems on all the shelves and books in the library. Therefore, we propose to use the library's existing unique barcode system in order to identify books within the library.

This research is conducted at the Mountain View Public Library in California. We stored the ID ranges of the books and their corresponding shelves' location into a database. We use SVG to display the aisle and shelf of the book or library item (i.e., DVDs). We introduce a simple method to locate each of the items in the library by utilizing the existing library's items' IDs, while providing an interactive experience for the user

Development and Implementation

We incorporate the existing maps data with SVG and JavaScript to create a lower cost interactive mapping system. The main advantage of using SVG is that it is scalable, which means the ability to zoom in and out without losing quality. Moreover, the free Inkscape software can be used to draw the map into SVG file and assign for each region of interest a unique ID. Inkscape is fairly simple to use, and it allows users to set attributes and properties in the region drawn. Another reason is that SVG is available directly in the browser, so there is no need to download a third party plugin to visualize. Microsoft has also joined other browsers and announced that they are going to start supporting SVG in Internet Explorer 9.

The mapping between ID codes and locations is stored in a XML "database". An Apache server running PHP provides the pages where the administrators can update or add locations for items. Behind the scenes, SVG, HTML, and JavaScript update the map after processing user's input. We developed a Chrome extension specifically designed to work with the website of the Mountain View Library which allows to quickly locate the book which is currently viewed by the user (i.e., after searching for a book, the extension allows visualizing the book's location on the map).

Since supporting only one browser is not a good idea, we also developed a stand-alone web page which allows users to interact with the map. When looking up an item of interest (in the case of a library this could be a book, whereas in the case of a mall, it could be a store), users are able to type in names, IDs, or aisle numbers into the application and the specific area of the map is highlighted, with the option of having multiple "maps" or "levels" (in the case of multi-story buildings, this is an essential feature).

movies_map.png

Figure 1: Current Map of the Library

final_proposed_map.png

Figure 2: Proposed SVG Version of the Map

The lookup and highlighting is implemented in JavaScript, using the jQuery and jQuery.svg libraries. AJAX allows updating the map without needing to reload the page. When queried by jQuery, a PHP page sends an XML response which contains the ID of the element to be highlighted in the SVG map, along with an error code which indicates whether the request succeeded (i.e., whether the ID was found within any one of the ranges in the database).

Example 1: The queried book was found in aisle with the id "aisle50":

<response>
   <error>0</error>
   <location>aisle50</location>
</response>  
   

Example 2: The querried book was not found in the database:

<response>
   <error>1</error>
   <message>Item Not Found!</message>
</response>
   

Example 3: The Chrome extension (background page):

<script>
   // The last url with book id.
   var last_url = "";

   // Called when a message is passed.  We assume that the content script
   // wants to show the page action.
   function onRequest(request, sender, sendResponse) {
     last_url = request["url"];
 
     // Show the page action for the tab that the sender (content script)
     // was on.
     chrome.pageAction.show(sender.tab.id);

     // Return nothing to let the connection be cleaned up.
     sendResponse({});
   };

   // Listen for the content script to send a message to the background page.
   chrome.extension.onRequest.addListener(onRequest);
      
   // Do nothing
   function doneCreatingTab(tab) {}

   // Handle a click on the extension icon.
   function handleClick() {
     // URL like: http://library.ci.mtnview.ca.us/search~S0?/c782.1092+WAGNER+Cambridge/c782.1092+wagner+cambridge/-3,-1,,B/browse
     var my_last_url = decodeURI(chrome.extension.getBackgroundPage().last_url);
     // Find /c<anything but /><numbers><dot><numbers><anything but />/ which is always part of the url
     var regex = /\/c[^/]*\d+\.\d+[^/]+\//;
     var items = my_last_url.match(regex);
     // This will be like /c782.1029+A+B+C/, so if we split by / the middle item will contain the string.
     var almost_clean = items[0].split('/');
     // Remove c, and ? and everything after, including the first +
     var clean = almost_clean[1].replace('c', '').replace(/\+.*/, '').replace('?', '');
     // Create a new tab with the map for the current book call number
     chrome.tabs.create({ url: "http://localhost/~annietoderici/map.html#" +  clean }, doneCreatingTab);
   };

   // Add event handler for clicks on the extension icon
   chrome.pageAction.onClicked.addListener(handleClick);
</script>

extensions.png

Figure 3: Extension, as installed in Chrome

step1.png

Figure 4: Mountain View Library search page: Once the user searches for a book or item, the extension becomes active. Notice the icon in the address bar. Once the user clicks on it, a new tab opens with the map having the isle highlighted.

step2.png

Figure 5: SVG map displayed with the highlighted aisle for the jQuery book.

This application is useful for customers, since libraries (or stores) rearrange their aisles from time to time, and items may be moved to a different areas without notice, and this framework makes such actions transparent. In addition, since we allow automated updates and item-level granularity, if the library upgrades to a RFID tagging system, then the location of the books could be updated in real time.

The only requirements needed for this application to work are: a map of the library or store must be available, and if not, it must be created and saved in the SVG file format with the appropriate IDs set for the areas of interest (i.e., aisles); and a database mapping the item range ID to an area ID (i.e., book number range to aisle ID). For the Mountain View library case study, it took about three hours to collect the aisle range data for each one of the floors. The total estimated time to create the map, and entering the ID mapping from scratch is under a day (assuming that a graphic artist is available to draw the map). The setup time of the software is less than an hour, which makes our software very appealing to non-profit organizations and institutions on a tight budget.

Data Integration

The first step is to collect the data from the library. We recorded the books' serial numbers on each aisle and then saved the range of serial numbers and aisle IDs into our own XML "database."

On the library website, after typing the search query and clicking the search button, the list of books is displayed. Then users click on the specific title they desire, which brings them to the locator page. Then the plugin retrieves the data by opening a new tab in Chrome which queries the server. We use regular expressions to match up the book's serial number to a range from the database. The range is associated with an aisle identifier, which is retrieved for highlighting the location on the map.

We define our own XML structure which contains the necessary information to be able to map an item ID to an area ID.

Our purposed XML database is very straightforward, and anybody can make modifications at ease. An aisle holds books within a range of serial numbers: the start tag indicates the starting of the serial number while end tag indicates the ending serial number of books in that aisle. Any further modification will most likely be the change of the start tag and/or end tag. Therefore, the librarians will be able to do this task in the future in case of reorganization by either modifying the database file, or by using a frontend.

DTD for the XML storage of the books' information:

<?xml version="1.0" standalone="yes"?>
<!DOCTYPE books [
<!ELEMENT books (floor*)>
<!ELEMENT floor (book*)>
<!ELEMENT book (range)>
<!ELEMENT range (start, end, aisle)>
<!ELEMENT start (#PCDATA)>
<!ELEMENT end (#PCDATA)>
<!ELEMENT aisle (#PCDATA)>
<!ATTLIST floor id ID #REQUIRED>
]>

Example XML database containing information for two books on two different floors:

<books>
   <floor id=”1”>
      <book>
         <range>
            <start>J10</start>
            <end>J90</end>
            <aisle>1</aisle>
         </range>
         <floor>1<floor>
      </book>
   </floor>
   <floor id=”2”>
      <book>
         <range>
            <start>Q11</start>
            <end>Q22</end>
            <aisle>1</aisle>
         </range>
         <floor>2</floor>
      </book>
   </floor>
</books>

Client-side JavaScript called by the Chrome extension to display the map. It issues an AJAX request to the server to retrieve book information:

// JavaScript Source for map.html - it id loaded as map.html#BOOKID
//
// The file contains the following divs:
// #map = location
// #info = debug text
// #svgmap = svg container
// #lookup_book is the lookup button.
// #book_id input box where the book id is typed.
var old_style, old_id="undefined", old_floor; 
var current = "map2.svg";

$(document).ready(
function() {
   // Load default map
   $("#svgmap").svg({loadURL: 'map.svg'});
   // If there's a hash tag, look it up and update map
   if (location.hash.length > 0) {
      var hash = decodeURI(location.hash).replace('#', '');
      $("#book_id").attr("value", hash);
      lookup_book();
   }
});

function lookup_book() {
  // book_id is just whatever the user enters. note that the value to be 
  // retrieved is an attribute, so call the .attr() function.
  var book_id = $("#book_id").attr("value");
  if (book_id.length == 0) {
      alert("Please enter the book ID to lookup.");
      return;
  }
  // Clear the text for the map div.
  $("#map").text("");
  // clear the info div.
  $("#info").text("");
  var url = "book_location.php?id=" + book_id;
  $("#info").append("Issuing AJAX GET request to url: " + url + "<br>");

  // Perform an AJAX request to the given url. This will load the XML output
  // by the php script, and will call parseXml once the GET request finished.
  $.ajax({
    type: "GET",
    url: url,
    dataType: "xml",
    success: parseXml
  });
}

$("#lookup").click(lookup_book);

function doneLoading() {
   var loc = window.loc;
   $("#map").text("Location is " + loc);
   // Fill all polygons blue to highlight the isle. Inkscape uses the fill attribute,
   // but this overrides it.
   $('#' + loc + " > polygon").each(function() {$(this).attr("style","fill:blue")} );
}

function parseXml(xml) {
   $("#info").append("Finished loading AJAX XML.<br>");
   
   // the xml variable now contains a full DOM based on the XML retrieved
   // from the server. The normal jquery functions work on it.
   var error = $(xml).find("error").text(); // text() gives the inside text of a tag
   if (error != 0) {
      alert("Error encountered: " + $(xml).find("message").text());
      return;
   }
   var loc = $(xml).find("location").text();
   var floor = $(xml).find("floor").text(); //which floor map
   if (old_id != "undefined") {
      // Remove the style attribute.
      $('#' + old_id + " > polygon").each(function() { $(this).attr("style", ""); });
   }
   old_id = loc;
   old_floor = floor;
   window.loc = loc;

   // load the correct map (retrieve the floor number)
   if (old_floor != current) {
      $("#svgmap").remove();
      $("#map").after('<div id="svgmap" style="width:540px; height:300px;"></div>');
      current_map = "map" + old_floor + ".svg";
      $("#svgmap").svg({loadURL: current_map, onLoad: doneLoading});
   } else {
      doneLoading();
   }   
}

Image Design

We converted the static map of the library into a SVG formatted map by using Inkscape and Vector Magic. Since this library only has two floors, we had exactly two pictures to be converted. We converted map for second floor using Vector Magic. Vector Magic is a proprietary software which is available online as a web application which offers exactly two free conversions. We uploaded the gif maps (from the Mountain View Library's website) into Vector Magic site, and after a short wait, the final SVG formatted was generated. We chose to use Vector Magic because we wanted to show that it is very simple to transform the existing raster map into SVG and that anyone should be able to perform this conversion.

On the other hand, we also used Inkscape to convert the first floor map by importing the map and then selecting "Path and Trace Bitmap" to generate the SVG map. Since Inkscape is free, we used it to make further modifications.

Once the map was converted, we loaded it into Inkscape and removed the markings and writing. We could either use Inkscape to draw the aisles or we could assign IDs to areas already in the map. The "ID" attribute is very important because we use for locating the aisle.

Conclusion

Since many location technologies, especially the RFID are used in most of the libraries in Mountain View, Santa Clara, and San Jose, this area is a good place to try new algorithms and user interfaces to allow a better user experience. Since the books information is saved in an easy to understand XML "database" file, it should be theoretically possible to integrate directly the already available data into our system. Therefore, our method has the potential of being deployed in libraries with minimal effort.

Bibliography

[1] Jung-Wook Choi. Dong-Ik Oh. Development of an RFID based Library Management and Search System. Journal of the Korean Academic Industrial Society. June 2005. 105-109.

[2] Jung-Wook Choi. Dong-Ik Oh. Tag-only Aging-Counter Localization for the R-LIM2 System. Springer Netherland. March 10, 2009.

[3] Aittola Markus. Ryhanen Tapio. Ojala Timo. SmartLibrary - Location-Aware Mobile Library Service. Springer-Verlag. September 2003. 411-416.

[4] Jung-Wook Choi. Dong-Ik Oh. Il-Yeol Song. R-LIM: an Affordable Library Search System Based on RFID. 2006 International Conference on Hybrid Information Technology. November 11, 2006. 103-108.

[5] William G. Griswold. et al. ActiveCampus: Experiments in Community-Oriented Ubiquitous Computing. IEEE Computer Society. Vol. 37. October 2004. 73-81.

[6] Martin Raubal. Stephan Winter. Enriching Wayfinding Instructions with Local Landmarks. Springer Berlin / Heidelberg. Vol. 2478. September 2002. 243-259.

[7] Birgit Elias. Stephan Winter. Extracting Landmarks with Data Mining Methods. Springer Berlin / Heidelberg. Vol. 2825. October 2003. 375-389.

[8] Martin Raubal. Harvey J. Miller. Scott Bridwell. User Centered Time Geography for Location-Based Services. Geografisker Annaler. Vol. 86. 2004. 245-265.

[9] Jerome P. McDonough. METS: Standardized Encoding for Digital Library Objects. Springer Berlin / Heidelberg. Vol. 6. April 2006. 148-158.

[10] Steve Probets. Julius Mong. David Evans. David Brailsford. Vector Graphics: From PostScript and Flash to SVG. ACM. Vol. 86. 2001. 135-143.

[11] jQuery. http://jquery.com/

[12] Google Chrome Extensions Developer's Guide. http://code.google.com/chrome/extensions/devguide.html

[13] Keith Wood. jQuery SVG Demo. http://keith-wood.name/svg.html

[14] Inkscape. http://www.inkscape.org

[15] Vector Magic. http://vectormagic.com/home