Improving lat,lng label estimate without depth data

[jonfroehlich]

As posted here (https://github.com/ProjectSidewalk/SidewalkWebpage/issues/2362), Google no longer provides depth data for any city. This was confirmed via private email with some of our Google contacts. :(

This is unfortunate because it affects the precision with which we can infer a label's lat,lng location: that is, we use the GSV depth data to translate a label's position from the panorama (which, with depth data, is in 3D space) to an actual lat,lng position.

As posted here (https://github.com/ProjectSidewalk/SidewalkWebpage/issues/2362#issuecomment-726346629), we can still estimate lat, long position by:

In the worst case, we simply assign a label's lat,lng position with the same lat,lng as the current pano. This is not horrible but certainly not as precise as before.

A slightly better version might be to set a fixed distance between the label and the pano lat,lng.

We can improve upon this by not using a fixed distance but, instead, examining the average distance between a pano's lat,lng and a label's lat,lng for each label type in our collected data thus far (400k labels) and using this as a heuristic. We can even do better than this: we can create a simple regression incorporating the user's POV, the y-position of the label on the pano, and the previously estimated distance between that labels lat,lng and the pano's lat,lng. (We could also possibly add in user's POV angle with respect to the road).

[misaugstad]

What we are doing now is assuming that you are placing a label directly in front of where the camera is facing, 10 meters in front of you. Here are the approximations that could be improved upon (the first few you already listed):

1. Actually compute an average distance instead of assuming it is 10 meters
2. Compute the average distance per label type
3. Use the x position of the label to get the heading instead of just the camera heading
4. As you said, a simple regression that takes into account the y position as well
5. Using great circle method to compute new lat/lng instead of approximating one degree as 111,111 meters

[jonfroehlich]

Thanks @misaugstad. I think Step 0 is to quickly setup some experimental testbed code that uses our previously collected data (with depth information) and lat,lng estimates as "ground truth." We can then do the following:

1. First, calculate a baseline difference between the "ground truth" lat,lngs and our current non-depth dependent estimate. We can calculate the overall difference in meters across all labels but then also by label type. We can also explore distance as a function of y-position.

2. Second, we can begin to improve upon our basic non-depth dependent estimate with some of the proposed ideas above and compare them to baseline. And then iterate on our algorithms from there...

Also, as part of this analysis, we should look at how our clustering algorithms are affected.

Thoughts? This is likely a task that either you or I should do (given my current set of TODOs, I would prefer you but we can discuss, of course).

[misaugstad]

I agree with that step 0. And I think it is a task for me. I don't expect to be able to get to it this week since some other high priority stuff has come up (like #2377), but I will have time in the near-ish future.

[jonfroehlich]

Thanks Mikey. Should be a fun/interesting task but also unfortunate how much unexpected effort we've had to put into this breaking change from Google. :(

[jonfroehlich]

Here's an obvious example of where the lat,lng distance estimate is now broken. The two obstacles in path should be estimated at different distances but obviously we can no longer do this:

[misaugstad]

TLDR; I did some linear regressions, and now I've got a lat/lng approximation method that is off by a median 1.47 meters, a 70% improvement over our current method with a median error of 4.85 meters.

Our current method just assumes that a label is 10 meters directly in front of you. The method I've come up with predicts heading angle using a linear regression with canvas_x as a predictor, and a separate linear regression predicts the distance from the panorama lat/lng using sv_image_y and canvas_y. I actually found the best performance by running a separate regression for each of the 3 zoom levels, meaning a total of 6 regressions.

I started out with about 492k labels. Filtered out about 97k (20%) for various reasons. Of that, I put 80% into a training set (about 316k labels), and tested the various estimation methods on the remaining 79k labels.

I will put the analysis report in a Github repo and link to it soon. After that, I'll incorporate the updated predictions into the code and send some screenshots of what it looks like :)

[jonfroehlich]

This is wonderful and so important. I can't wait to read more about the analysis. It sounds like a lot of work but I hope you enjoyed it too (I love this sort of stuff!).

Jon

On Fri, Jan 1, 2021 at 6:34 PM Mikey Saugstad notifications@github.com wrote:

TLDR; I did some linear regressions, and now I've got a lat/lng approximation method that is off by a median 1.47 meters, a 70% improvement over our current method with a median error of 4.85 meters.

Our current method just assumes that a label is 10 meters directly in front of you. The method I've come up with predicts heading angle using a linear regression with canvas_x as a predictor, and a separate linear regression predicts the distance from the panorama lat/lng using sv_image_y and canvas_y. I actually found the best performance by running a separate regression for each of the 3 zoom levels, meaning a total of 6 regressions.

I started out with about 492k labels. Filtered out about 97k (20%) for various reasons. Of that, I put 80% into a training set (about 316k labels), and tested the various estimation methods on the remaining 79k labels.

I will put the analysis report in a Github repo and link to it soon. After that, I'll incorporate the updated predictions into the code and send some screenshots of what it looks like :)

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/ProjectSidewalk/SidewalkWebpage/issues/2374#issuecomment-753419929, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAML55NDAP43NCKWLF7H5JLSX2A2ZANCNFSM4TYSS7KQ .

-- Jon E. Froehlich https://jonfroehlich.github.io/ (he/him https://www.mypronouns.org/he-him) | @jonfroehlich https://twitter.com/jonfroehlich Associate Professor, Allen School of Computer Science & Engineering Core Faculty, Urban Design and Planning, College of Built Environments Director, Makeability Lab https://makeabilitylab.cs.washington.edu/ | Associate Director, CREATE http://create.uw.edu/ University of Washington Help make sidewalks more accessible: http://projectsidewalk.io

[misaugstad]

Here is the analysis markdown document. That just shows the results. Here is the link to the full code. Incorporating into Sidewalk will happen later this week!

[jonfroehlich]

This is awesome. Great write up. Found one lil double word issue: “finding traveling”. Just need one of those words in that sentence.

Terrific work Mikey!

[misaugstad]

Thanks @jonfroehlich and nice catch!