[Talk-GB] building shapes from OS Street View

Robert Scott lists at humanleg.org.uk
Sat Apr 10 16:52:00 BST 2010

On Saturday 10 April 2010, TimSC wrote:
> Converting edge fragments to polygons is the slow step at the moment - 
> about 15 minutes a tile. I am using the approach describe in the link 
> below. Fortunately, I know a bit of Boost.Python and C++ if we need the 
> speed. I suspect a better algorithm in python could improve the speed 
> issue rather than resorting to C++.

If needs be, and other algorithms fall short, the advantages c++ has are things like ability to optimize for cache behaviour, ability to choose algorithms for your data structures (such as lists) which I imagine are getting hammered by your approach. A last resort though.

> http://losingfight.com/blog/2007/08/28/how-to-implement-a-magic-wand-tool/
> I am also seeing the limitations of my approach. Problems arise from the 
> lack of image resolution and the anti-aliasing of the colours in the 
> image. Since I am using a binary classification by colour for selecting 
> pixels, it tends to result in rounded corners (due to the colour 
> blending into the backgound). The polygon simplification then has to 
> descriminate between a rounded corner due to anti-aliasing and corner 
> which is real. Given the resolution, a straight edge might only be 2 or 
> 3 pixels long, and a rounded corner has a radius of about... 2 or 3 
> pixels. But then, these building shapes are also a total nightmare to 
> manually survey. Example attached (you will probably need to zoom in):

Indeed. The approach I was going to take was taking the buildings as anti-aliased grayscale ( which I guess I would have to be generated by tuning a few heuristics about which indexed colours to pick ) and use a corner finding algorithm on them. I was hoping to be able to get sub-pixel accuracy with this approach (corner detectors are perfectly capable of it with grayscale data), but I still have a few papers to read.

I was thinking momentarily of a hybrid approach, using detected corners to more precisely position nodes.

As far as the orthogonalizer idea goes, I think a simple refinement would need to be made - orthogonalization threshold would need to be inversely proportional to segment lengths. Lengths that are short relative to pixel size will have more quantization errors than long segments.

> I have some ideas for a better algorithm (based on active contour 
> models), but that is pretty complex. I will give that some thought. 
> Basically, we need to segment the shape but not by simply binary 
> selecting pixels inside or outside the shape (and it can try to be 
> orthogonal, if possible). The code I have does provide a good 
> initialisation of the model, so it is hardly wasted effort. If anyone 
> has any better ideas, you can have a copy of my python code to try things.

You've done a lot better than me - I'm still at the 'reading papers' stage ;)


More information about the Talk-GB mailing list