Maps have repeatedly revolutionised the world since the dawn of civilisation. The most recent iteration is based on the widespread adoption of smartphone technology and the location-based applications that it allows.
Anybody with one of these devices has access to the global satellite positioning system, a huge database of highly accurate maps and other layers of additional information, such as road names, local coffee shops and even the locations of friends.
But all this stops as soon as you enter a building. GPS famously stops working indoors and few maps are available for indoor locations.
Google and others have begun to change this by making maps of some large shopping malls in the US and Japan. But progress is slow, largely because these maps have to be painstakingly created more or less by hand.
Today, that looks set to change thanks to an innovative idea from Moustafa Alzantot and Moustafa Youssef at Alexandria University in Egypt. These guys have developed an app that crowdsources data from smartphone sensors to construct indoor floorplans automatically. The new app is called CrowdInside.
Clearly, the type and quality of the data is crucial. These guys point out that smartphones are equipped with a wide variety of sensors: GPS devices, magnetometers (compasses), accelerometers and even WiFi signals strength meters that give a rough estimate of the distance to the nearest hotspot. They use all this data in a remarkably innovative way.
The basic technique is dead-reckoning using an accelerometer as a pedometer and the magnetometer as a direction finder. The number of steps in a specific direction give a rough idea of the distance walked.
The problem, of course, is that dead-reckoning is notoriously susceptible to errors, which build rapidly in time. To get around this, the system needs to be constantly re-calibrated using points at a known location.
This is the clever part of the system. Alzantot and Youssef start by using the location where GPS data becomes unavailable to determine the entrance to the building. That gives a starting point for the dead-reckoning.
Next, they use the sensor data to spot when the users are in an elevator, using an escalator or simply walking up or down stairs. In each case, the movement produces a unique pattern of acceleration that is different from walking and so makes them easy to spot.
Since all these locations are fixed in a building, they can be used as anchor points to recalibrate the dead-reckoning calculations. The result is an app that trace a user’s movements in a building with reasonable accuracy.
The great power of this system comes from taking data from many users, in other words crowdsourcing it. This sharpens the floorplan, making it more accurate.
It also allows them to infer higher level data, such as the shape of rooms by looking at the spread of traces, or the position of doors by looking for the intersection between corridors and rooms.
The map above comes from about 150 traces.
That’s a clever idea with significant commercial potential. Alzantot and Youssef don’t say whether they will make CrowdInside widely available. Whatever their plans, they need to make sure they’ve protected their intellectual property, a task that may be more challenging in North Africa than in other parts of the world.
Let’s wish them luck with it.
Ref: arxiv.org/abs/1209.3794: CrowdInside: Automatic Construction of Indoor Floorplans