Rice University computer scientists have created a new system for mobile users to quickly determine their location indoors without communicating with the cloud, networks or other devices. The battery-saving scheme uses image recognition and “hashing,” a method that reduces key details in a photo to short strings of numbers called hashes. To determine a location, the system hashes a photo from the user's camera and compares it against a pre-downloaded, highly compressed location database called a hash table.
The indoor mobile positioning system called CaPSuLe, short for “Camera-based Positioning System Using Learning,” was presented in September at the Institute for Electrical and Electronics Engineers System-On-Chip Conference (IEEE SOCC) in Seattle.
In tests on a commercially available smartphone, CaPSuLe calculated locations in less than two seconds with greater than 92 percent accuracy using less than 4 joules of energy, said system co-inventor Anshumali Shrivastava, assistant professor of computer science at Rice. "The core of our system is a hashing-based image-matching algorithm that is more than 500 times cheaper -- both in terms of energy and computational overhead -- than state-of-the-art image-matching techniques."
Shrivastava said CaPSuLe is a proof-of-concept application that uses a combination of machine learning and inexact computing to address three of the primary problems facing mobile application designers.
"Privacy, computations and energy are the big challenges," he said. "Inexact computing helps with all three. In short, it allows us to determine answers with something less than 100 percent confidence. There are many situations where a miniscule loss of confidence, say 1 percent or less, works just as well as the golden solution. Yet that tiny difference in accuracy can give us exponential gains in computations and energy. Certainty, or confidence, is a resource that can be traded, and as always, the sweet spot is not the extreme."
For example, a traditional brute-force image-matching technique that Shrivastava and colleagues used for comparison with CaPSuLe consumed greater than 500 times the energy and took almost 17 minutes to complete a single location query when computations were performed on the mobile. For that extra energy and time, the accuracy improved to 93.4 percent -- less than 2 percentage points better than the accuracy of CaPSuLe.
In describing how CaPSuLe might be used, Shrivastava cited the example of a shopping mall. The mall owner would need a gallery of images of the interior of the mall; CaPSuLe would scan those images for key features like store marques, escalators, benches, kiosks, etc. Rather than storing the images, the system stores a table of hashes, which serve as image fingerprints. These fingerprints are lightweight and can be computed very fast, Shrivastava said.
To test CaPSuLe, study co-authors from Korea's Seoul National University made a CaPSuLe app that ran on a smartphone. Tests were conducted in a Seoul shopping mall, and the hash table was prepared using 871 reference photos.
"Cloud-based machine-learning applications are getting a great deal of attention, but cloud-based solutions have inherent privacy drawbacks, and they are typically computationally and energy- intensive," Shrivastava said. "CaPSuLe shows that a 'cloudless,' probabilistic approach can be a viable and more sustainable alternative."
This effort is a part of Rice University's Center for Computing at the Margins (RUCCAM), which is led by study co-author Krishna Palem. Additional co-authors include Rice's Chen Luo and Seoul National University's Yongshik Moon, Soonhyun Noh, Daedong Park and Seongsoo Hong.
RUCCAM brings together researchers from Rice and universities around the world to explore solutions to the physical and energy limitations currently restricting the continued expansion of computing capacity needed to solve emerging workload problems. The researchers intend to change the manner in which computational resources are utilized, even at the margins of stability and accuracy, to increase the efficiency at which answers can be calculated.