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 ;) robert. _______________________________________________ Talk-GB mailing list Talk-GB@openstreetmap.org http://lists.openstreetmap.org/listinfo/talk-gb
