Revolutionizing Indoor Positioning with Camera-Based System
Modern ML algorithms designed for the cloud face challenges in indoor positioning due to limited computational resources and energy concerns. The CaPSuLe system offers a 500x cheaper and energy-efficient solution using image-based positioning algorithms, achieving high accuracy with on-device computations, reducing reliance on cloud interfaces. This innovative approach addresses issues of high energy consumption and privacy threats associated with cloud-based solutions, presenting a cost-effective and sustainable alternative for accurate indoor positioning.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
CaPSuLe CaPSuLe: Camera Based Positioning System using Learning Yongshik Moon, Soonhyun Noh, Daedong Park, Chen Luo, Anshumali Shrivastava, Seongsoo Hong, Krishna Palem anshumali@rice.edu September 8th 2016 IEEE System on Chip Conference
Motivation Modern ML Algorithms are Designed for the Cloud Massive Computational Requirements Massive Storage Can We Fill the Gap ? Unsuitable for Current ML Routines Very limited computation and memory available Battery life is a major concern
A Challenge Application : Indoor Positioning Indoor Positioning Systems are required to be more accurate GPS signals are further inaccurate due to walls and other obstruction Wifi and other sensor based positioning Requires multiple sources (more than 10) for good accuracy Inaccurate at periphery and near walls
Modern Camera Based Positioning Algorithm Location of Matched Image Image Features Geo Tagged Image DB Significantly more accurate than triangulation based methods Image matching is a costly operation and therefore it needs a cloud interface
Issues Positioning requires matching the current image with a pre-collected database of location-tagged images State-of-the-art Image matching requires a cloud 1. Similarity between images is costly 2. Even matching a resized image (274KB) requires 16 million multiplications 3. With a database of around 700 images, matching a single image requires 2100 Joules (12 billion multiplications) Cloud based Solution Not Sustainable: Does not save energy Privacy Threats: User data on the cloud opens for potential privacy threats Communication: Communication to-and-fro with the cloud can have unpredictable latency
What are we Offering? A 500x cheaper image-based indoor positioning system compared to existing algorithms Our algorithm only needs 3.77 Joules to position a device with on- device computations only In contrast, a single resized (compressed) image (247KB) transfer over 4G takes around 13.77 Joules. Inexactness at work: We achieve 92.11% accuracy a mere 0.89% lower than the state-of-the-art algorithm (Open CV package) which is 537 times more expensive (2100 Joules)
Two Different Worlds 2-5x Cheaper Algorithm Noticeable change Can be usually achieved using clever systems or algorithmic tricks Mobile + Cloud Computation + Privacy threats 500x Cheaper Algorithm Changes the technology disruptively Usually requires a paradigm shift in both algorithm and system These is more than a quantitative change, it is qualitative!
Some Result from CaPSuLe CaPSuLe 92.11% accuracy, in 1.92 seconds, with mere 3.77 Joules Energy, as evaluated on Samsung Galaxy S4 All computations are local Traditional procedure (Open CV) requires 2100 Joules to achieve 93%.
The Bottleneck The bottleneck step is computing similarity scores between images Requires 16 million multiplications Needs all pairwise comparisons of extracted descriptor No hope if we want to do things exactly. . Clustering and cheap Bag-of-Words features are inaccurate (75% accuracy) Supervised Learning using cheap features does not help (77% accuracy)
Hope: Inexactness via Probabilistic Hashing Probabilistic hashing for efficient sub-linear search Generate random and cheap fingerprints of the descriptors extracted from the Images in the databases. Finger Print Matches, a noisy indicator of similarity. Create few hash tables using few independent fingerprints. During Querying Extract feature from query image, generate their cheap fingerprints. Probe only few buckets and corresponding descriptors for potential matches and scoring. Only very few comparisons. References: 1) Anshumali Shrivastava Probabilistic Hashing Techniques for Big-Data 2015 2) Karp, Richard M.; Rabin, Michael O. "Efficient randomized pattern-matching algorithms 1987 3) Michael O. Rabin. "Fingerprinting by Random Polynomials 1981 4) Carter, Larry; Wegman, Mark N. "Universal Classes of Hash Functions 1979
Traditional Hashing Techniques Alone are Not Enough for 500x+ Many more algorithmic and system choices Use Cheap Hash Function Cheap Ranking Bit Arrays Load Buckets on Demand Pruning Empty Buckets
Key Choices Cheap Sign Bit Hashing: From many multiplications to few addition Cheap Ranking: Hashing also gives many false positives and exact similarity computation to filter candidates is too expensive. Estimate rankings cheaply based on bit-matches only Buckets of Bit Array: Instead of storing ids, create bit arrays Load Buckets to Main Memory on Demand: Hash tables heavy on memory, buckets addresses are fixed and hence can be loaded on demand using fseek Ignore Noisy Buckets: Cheap hash function leads to few heavy buckets which can slow query time. Just ignore them
Target Location: LOTTE Shopping Mall, Main Branch, Seoul, Korea Dataset: Total 871 pictures from 45 different locations. (719 images as Database and 152 for testing). Device: Samsung Galaxy S4 . Brute Force: Standard Image Matching from in OpenCV package.
Comparisons on Samsung Galaxy S4 Evaluations for CaPSuLe and Bruteforce Parameters K22L24 Bruteforce Accuracy 92.11% 93.42% Energy Consumption 3.78J 2103.22J Response Time 1.92 sec 1030.43 sec Required Storage Space 294.39 MB 393 MB Required Memory Space 78.90 MB 171.41 MB
Conclusions Bringing Cloud Level Machine Learning (ML) to handheld form factors is an exciting research direction Probabilistic hashing algorithms are quite powerful ML algorithms were never designed keeping handheld platform resource constraints in mind Plenty of opportunities to make machine learning significantly resource frugal through inexactness by sacrificing a small amount accuracy for huge gains in resource requirements. With the ever increasing computational power of mobile devices, we believe that cheap cloud-independent, private, and sustainable solutions are the future of handheld embedded platforms is the next horizon
