The accelerometer and gyroscope. The double integral of acceleration is displacement. On iPhones/iOS it's extremely accurate to the point where you can integrate displacement from it and not be far off from the real result - over short timespans/distances anyways.
One of the lesser-appreciated qualities of Apple hardware (more accurately, hardware and drivers) is the quality and accuracy of their sensors.
I have tried this as well - it was definitely not as simple as taking the double integral.
In my experience moving and the stopping the phone would always end up with the two accelerations not exactly canceling out so that the calculated position would drift away from the true position at a constant rate.
Even applying a floor to velocity to eliminate the drift, the distances calculated for simple linear motions were consistently off by ~50% in either direction.
This was a few years ago so sensors may have improved - have you actually done this in practice and found it to work?
I have tried this as well - it was definitely not as simple as taking the double integral.
Right. RoomScan requires you to stop and touch the device to the wall frequently. This allows them to re-zero the velocity. Small IC accelerometers and gyros aren't good enough for dead-reckoning over any substantial distance.
What you really want is 3D SLAM, using the cameras. That's been done on Apple devices, for a rather lame "Ball Invasion" game. That team was acquired by Facebook for their VR effort.
There's source code for SLAM. See "slam6d.sourceforge.net". This is the right way to do indoor localization. The better robot vacuums (Neato and Dyson) use it.
You could play substantial DSP style filtering games such that your average human walks at a very constant speed and is mostly either standing perfectly still or walking at a constant speed. So your non-moving data points are rounded to zero and generate an error signal, and your moving datapoints can be average together to a constant generating an error signal, and the error signals can be shared between the two data sets and analyzed and averaged. Also all data has a resultant spectrum when you ram it thru a FFT, and I'm guessing the data spectrum looks a lot different than a noise spectrum enabling all kinds of fun filtering. Further I'm guessing a FFT analysis will show peaks at stride rate, and variations in stride rate will predictably vary velocity.
My first guess was pure optical, an inside out 3-d scanner basically. OK, image analysis shows there's corners and walls, and the building code requires all doorknobs to be at exactly X inches off the floor, countertops Y off the floor, stairs of certain rise/run combos, and the room dimensions WILL round to closest integer inch so you do some curve fitting and the highest correlation dimensions win. Especially when in the article he described it as placing the phone against all the walls. A simple inertial nav system wouldn't care if you held the phone at an angle or upside down, but optical needs flatness. You'd be making one of those 360 degree panorama pix, kind of, then analyzing it.
Maybe I should be creating a 2 zillion pound startup instead of posting to HN?
"This was a few years ago so sensors may have improved"
Apparently they're much better than previously. When I first tried this around 3 years ago, I had the same problems you did. The errors get cubed by the double integration. Software Kalman filters and other tricks didn't really help.
A lot of the newer sensor chips now do "sensor fusion"[1] on the chip itself, which means that the raw data is much more useful, and requires almost no post-processing.
I assume that this, in combination with higher sampling rates, means that the errors are small enough for the output to be useful over "human interaction" scale.
5m room size / speed of sound in air = around 15ms. Unless the amount of variation in latency in the phone's speaker + microphones is much less than that -- which I suspect it isn't -- that wouldn't be particularly accurate either. (Even that aside, it's going to be rather non-trivial to get anything useful at all with a non-directional speaker in an enclosed room with several other walls, ceiling, floor, and other objects).
If you can record and identify the sound as you emit it and can identify the echo you shouldn't need to worry about jitter in output just the sampling frequency and any jitter there.
I think you are right about the likely cluttered response in a realistic room being hard to analyse into something useful.
> The double integral of acceleration is displacement.
Have you actually tried this? I have and the results were totally unusably off. If the accelerometer that costs a few dollars at best could be that precise, you'd see thousands and thousands of new apps that would use it in creative ways. It's just from my experience you can't calculate displacement using an accelerometer that cheap and therefore you don't see iPhone apps that use it.
> "It's just from my experience you can't calculate displacement using an accelerometer that cheap "
I disagree. You clearly can - the app and the people who use it are proof positive of the sensor's capabilities. Having seen the raw output from these sensors a few times they're also startlingly accurate.
The problem is of course that it's not simple and there's real complexity in the solution. It's (of course) impossible if you blindly take the double integral of raw accelerometer readings.
In the same way we do all kinds of magical things with all kinds of sensors - but it's rarely as simple as plugging a pin into a ADC and reading the bits that come out.
Signal processing, in both hardware and software, is a gigantic field of study unto itself. I fully expect that the app is doing something non-trivial with its sensor readings to gain accuracy - but it's eminently possible, just difficult.
The intersection of "mobile app developer" with "skilled signals engineer" is pretty low. If someone capable wrote a library that did this, you'd bet that we'd see an explosion of apps that use this functionality.
So you've seen raw output from the accelerometer and you think they were fine, but do you realize that the error gets cubed when you calculate displacement from those values?
> One of the lesser-appreciated qualities of Apple hardware (more accurately, hardware and drivers) is the quality and accuracy of their sensors.
Not to mention their consistency across the entire product line. I assume there are some Android phones with similarly good sensors, but it's definitely not something a developer can assume.
Sounds like what used to be called
inertial navigation and was used
on the US SSBN (intercontinental
ballistic missile firing submarines)
before the Navy's version of the
later USAF's GPS.
Inertial navigation was good enough to be
quite useful before the Navy's version
of GPS.
The Navy's version of GPS was done, at least
started, at the Johns Hopkins University
Applied Physics Laboratory (JHU/APL).
They had a receiver on the roof, and it
routinely navigated itself to within
a foot.
I heard about that project because for
a while I was doing applied math
(the fast Fourier transform, power
spectral estimation) and writing software
in the JHU/APL group that did the
orbit determination calculations
for the satellites.
That project was a good example of how
to do the technical side of a very
ambitious project:
(1) Problem. The US Navy very much needed
a means of navigation for the SSBNs.
(2) One or a few physics guys at the
JHU/APL had an idea, of course, in terms
of Doppler shifts from several satellites,
etc., on the back of an envelope.
(3) Not much later, the project was approved.
Biggie Huge Project Point: Not long after
the back of the envelope solution, the
whole project was low risk and high payoff
with, really, only routine, low risk
work remaining.
Lesson 1: The problem sponsors were able
to evaluate the project just on paper.
Lesson 2: After a good evaluation just
on paper, the rest of the project was
low risk and high payoff.
Lesson 3: The Navy did not say: You
do the work, put up the satellites,
show that it all works, and we will
buy receivers for each of the dozen
or so SSBNs.
For Silicon Valley: Want to do great
projects, low risk, high ROI? Part of
what you need to be able to do is to
evaluate projects just on paper.
Of course, what evaluates well just on
paper is mostly just the technical part.
But start with a biggie problem so that
clearly, obviously, no evaluation, no
customer feedback needed, the first good or a
much better solution is a must-have and
not just a nice-to-have and where, due to
the size of the problem
(e.g., number of happy people times
earnings per person), for financial
success all that is left is that first good or
much better solution and that is just
technical and can be evaluated just on paper.
This way of doing projects is much of why the
US has GPS, why the US Navy has it's version of GPS, why
in WWII Patton at the Battle of the Bulge
praised the US proximity fuse (a little
radar set inside an artillery shell that
told the shell when to explode -- great for
exploding near an airplane or over the
heads of troops) from the JHU/APL,
the SR-71, the F-117 (Saddam, sorry
you spent all that money on air defense --
all of it never put even on scratch on
even one F-117).
The page you linked seems to do a reasonable job of answering that:
"Using on your phone’s built-in GPS, Wi-Fi, and gyroscope to determine distances and the orientation of walls, RoomScan can reliably estimate measurements to within about half a foot, which should be adequate if all you need is a rough floor plan. If, you need more precise measurements, you can opt for the $5 Pro version, which allows you to specify exact distances, and will automatically correct the entire room if you adjust a couple dimensions."
Combining GPS, wifi-positioning, and the gyroscope should be fairly accurate for a floor plan. It's a very clever idea.
I was suggesting GPS wouldn't work with most rooms having ceilings. Wifi positioning I would imagine is highly inaccurate, which leaves the gyroscope.
Judging by some screenshots and appstore comments I assume its only roughly accurate, and requires you to move your phone slowly between walls in straight lines (not via your pocket or around furniture for example).
I think I would have immediately dismissed an idea like this because I would have perceived the end result to be inaccurate and inadequate. Yet it's a popular app, so I guess I have learnt something.
Ceilings usually aren't problematic for GPS. They do better out side, but if you get cell service through the ceiling, you'll get GPS signal through it.
What I'm curious about is that GPS is only accurate to within a few meters. If I turn on my GPS and set it on my desk for an hour, the resulting track will look like it's bouncing around the room.
My guess is this app averages a bunch of readings from each wall to correct for the noise, but I'm still surprised that works well enough to give accurate results.
The cell signal is orders of magnitudes more powerful than the GPS one. In fact, GPS even has a noise floor that's higher than the signal.
As for using GPS, WLAN and others, you can get pretty accurate measurements with sensor fusion, even if the individual sensor values are all noisy or inaccurate.
From past experience I'd also expect GPS to not be available unless you're near a window. But if it's there you can use it to get a more accurate location.
The traditional approach in sensor fusion is to use high accuracy, high drift sensors like the phone's accelerometer to provide accurate short term data and then correct for the drift using less accurate but low drift sensors like GPS. Just integrating the accelerometers will work on short time spans, but you also double integrate the noise of the accelerometer, so that measurement of position blows up quickly unless you correct for it.
It really depends. I have an older dedicated GPS receiver that absolutely no way will receive a signal indoors. My iPhones all do a pretty good job. (FYI, you can only get signal strength on an Android phone; Apple's CoreLocation API doesn't provide that or some of the other detailed satellite data.)
GPS is based on triangulating (well, trilateralating) between 3-6 fixed points in space located thousands of kilometers away.
Wifi positioning is based on triangulating (trilateralating) between 3-40 fixed points within 100 meters.
Assuming you can get access to the raw data, Wifi should be extremely accurate for calculating the distance between two points in space separated by less than 30 meters. (And probably pretty accurate up to 100 meters or so.)
What about multipath? I measure a 1/2 decrease in signal strength, is it because I got 1/sqrt(2) times farther away, or because someone opened the fridge door next to the router?
In response to the three replies already here. I've never done this, I'm a game programmer. But I would use a big bag'O'tricks to address this. Getting unrealistically long distances out of your wifi data? Have the user enter a square footage and normalize on a logarithmic scale bounded by heuristics. Use the accelerometer not for tracking but detection like going up and down stairs, walking short vs. long distances.
I'd think the problem with wifi is that the exact position of the base stations are hard to collect. The mass proliferation of telcom wifi networks could help if they are willing to sell the location data, but I don't see how Apple could reasonably know where the access points I see with SSID Holly_guest or TS-Dlink are located to use it as a trilateration point.
>Judging by some screenshots and appstore comments I assume its only roughly accurate, and requires you to move your phone slowly between walls in straight lines (not via your pocket or around furniture for example).
The site claims it's accurate to within 6 inches which, based on a quick trial, seems about right.
You don't have to move it in a straight line as far as I can tell. I just moved it around the room and pressed it against the walls.
Like you, I wouldn't have expected this to work. But it pretty much does. I didn't experiment with what radio signals it needs to work. (Though for most uses I'm not sure it's easier than a laser distance meter and some graph paper.)
One of the lesser-appreciated qualities of Apple hardware (more accurately, hardware and drivers) is the quality and accuracy of their sensors.