[potatolicious]

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.

[voodoomagicman]

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?

[Animats]

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.

[VLM]

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?

[mojuba]

Half a zillion idea: use sound echolocation principles.

Edit: http://www.gsmnation.com/blog/2013/06/19/echolocation-app-le...

[Intermernet]

"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.

[1]: http://en.wikipedia.org/wiki/Sensor_fusion

Examples:

http://www.kionix.com/sensor-fusion

http://www.invensense.com/mems/technology.html

http://www.st.com/web/en/catalog/sense_power/FM89?sc=mems

[Guillaume86]

Maybe add beeps and use them like a sonar to refine distance measurement?

[SEMW]

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).

[josephlord]

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.

[mojuba]

> off by ~50%

You should get different results on different phones, but I don't think it would ever be reasonably precise on any one device.

[mojuba]

> 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.

[potatolicious]

> "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.

[mojuba]

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?

[wlesieutre]

> 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.

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.

[JabavuAdams]

I last tried this about 4 years ago, using only linear accelerometer data. Been meaning to try it again, for some Structure from X ideas.

EDIT> ... forgot the point ... years ago it wasn't good enough -- noticeable drift in a matter of seconds.

[graycat]

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).

Ah, Silicon Valley will never do that, not now!

[raverbashing]

A lot of planes use that as well