It's bugging me that I can't understand how it works, at least not in a way that would produce accurate results in most environments (i.e. No GPS).
http://www.digitaltrends.com/home/roomscan-app-iphone-floor-...
Anyone have any ideas?
One of the lesser-appreciated qualities of Apple hardware (more accurately, hardware and drivers) is the quality and accuracy of their sensors.
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.
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.
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.
For an unfortunate example of an game release delayed by Android sensors, check out http://gameovenstudios.com/bounden-on-android-delayed/
The video is sad but hilarious.
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).
Ah, Silicon Valley will never do that, not now!
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?
You should get different results on different phones, but I don't think it would ever be reasonably precise on any one device.
I think you are right about the likely cluttered response in a realistic room being hard to analyse into something useful.
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?
Edit: http://www.gsmnation.com/blog/2013/06/19/echolocation-app-le...
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.
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.
[1]: http://en.wikipedia.org/wiki/Sensor_fusion
Examples:
http://www.kionix.com/sensor-fusion
EDIT> ... forgot the point ... years ago it wasn't good enough -- noticeable drift in a matter of seconds.
"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.
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.
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.
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.
Download one of the apps that shows individual GPS satellite signal strengths and tell me if you still believe this. Definitely not true for my phone.
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.)
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.)