[Talk-GB] building shapes from OS Street View
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.
> 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