[OSM-dev] Doing street names from aerial imagery
This is a routing problem, hopefully someone has already solved it. If there is a suburb of streets mapped from aerial imagery and you have several volunteers how do you work out the most efficient path for all the voluneteers to take to grab street names with minimal overlap etc. ___ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev
Re: [OSM-dev] Doing street names from aerial imagery
On 24/03/10 10:52, John Smith wrote: This is a routing problem, hopefully someone has already solved it. If there is a suburb of streets mapped from aerial imagery and you have several volunteers how do you work out the most efficient path for all the voluneteers to take to grab street names with minimal overlap etc. It's basically just a version of the Travelling Salesman Problem which you will find discussed in detail in any Computer Science textbook. Wikipedia discusses it here: http://en.wikipedia.org/wiki/Travelling_salesman_problem Wanting to divide the job among multiple people probably just makes it harder, but as it's NP-complete to start with I'm not sure that matters ;-) Tom -- Tom Hughes (t...@compton.nu) http://compton.nu/ ___ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev
Re: [OSM-dev] Doing street names from aerial imagery
Fundamentally this is a simple application of some of the shortest path algorithms that are studied at university computer science and mathematics departments adnausium. There are however a bunch of complications that make it a little less simple, and is likely best worked out in each individual instance. (You already know this, but for completness:) The way it's generally done at mapping parties is to cut the area up intuitively into a bunch of areas, naturally divided up by natural boundaries (such as main roads, rivers etc) let volunteers allocate themselves areas by ersonal preference. (cutting the cake) However due to the huge number of variables involved, I'd be surprised if there was any way a computer could do it faster or better: Someone says I like driving, so I'll take the furthest away bit; Someone say I have a bike, so i can do that little area with lots of foot paths; someone says I like trees, and I know there are lots of trees in that area (OK, that's a slight exaggeration); When you arrive on the ground you can find that there are names only at one end of a grid of streets, and your carefully pre planned route breaks. There are so many different kinds of areas (grid patterns; modern curvey estates, terraced areas, industrial parks, one way systems) that routing algorithms would have to be tweaked for each area; You could however call every intersection a node, and come up with an algorithm to visit each node once. This is almost the Travelling_salesman_problemhttp://en.wikipedia.org/wiki/Travelling_salesman_problemthough extra complexity is added when you find that some streets only need one end visited. While there are severe problems with finding a perfect solution to the TSP, there are plenty of shortcuts that can be taken in this case. Now reading between the lines of your problem, there are a few questions -- are you willing to assume that if you drive past one end of a street, it's captured, or does both ends need to be captured? Or is some live update system going to be implemented so that volunteers can enter information about when they get a street name, and the route can be recalculated? Are you willing to accept that if a road changes name part way though, and that missing this is a reasonable error? Is it reasonable to assume that all volunteers are especially the same (they all have a car, and have no specific preferences)? Is it reasonable to assume that everyone starts and finishes at a predetermined base? Is it reasonable ot assume that if someone finds a 1 way system, or other restriction, that the route will go wrong, and this is ok? How large an area are we dealing with here? most algorithms for this type of thing get proportionately slower the more data is put in, and as such, will have a point at which they simply fall over or get so slow that it would be quicker to use a pencil and some brain cells. In short: I'd recommend just using intuition, but if that's not an option, give a load more details, and we can work something out. On to a related subject, are there any tools that have been developed to assist with cake cutting tasks? I have personally been tairing my hair out for the last few days trying ot get josm to display cake segments for yahooing tiger data. Thanks, JR On 24 March 2010 10:52, John Smith deltafoxtrot...@gmail.com wrote: This is a routing problem, hopefully someone has already solved it. If there is a suburb of streets mapped from aerial imagery and you have several volunteers how do you work out the most efficient path for all the voluneteers to take to grab street names with minimal overlap etc. ___ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev ___ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev
Re: [OSM-dev] Doing street names from aerial imagery
On 24 March 2010 21:28, Tom Hughes t...@compton.nu wrote: Wanting to divide the job among multiple people probably just makes it harder, but as it's NP-complete to start with I'm not sure that matters ;-) As Gregory points out it would be simple if it was a simple gridded layout and if there was only one person involved, but I was thinking about this from a mapping cake point of view, but simple sectioning may not be the most efficient routing. ___ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev
Re: [OSM-dev] Doing street names from aerial imagery
On 24 March 2010 21:31, John Robert Peterson jrp@gmail.com wrote: Are you willing to accept that if a road changes name part way though, and that missing this is a reasonable error? What is the probability of this occurring? I'm guessing fairly low, although you could minimise this by targeting the intersections closest to the start and end nodes of a way, I don't think every single intersection along the way is worth the effort. Is it reasonable to assume that all volunteers are especially the same (they all have a car, and have no specific preferences)? This could be handled some what by using current cake method to break things up, but with a slight twist where the boundaries can be flexible to make routing more efficient. Is it reasonable to assume that everyone starts and finishes at a predetermined base? I'd assume a fuzzy cake area, rather than a shared start point. Is it reasonable ot assume that if someone finds a 1 way system, or other restriction, that the route will go wrong, and this is ok? I think the intersections are more important than the way itself, any ways that are one way you might only need to use the start intersection. How large an area are we dealing with here? most algorithms for this type of I'd assume a suburb worth, any smaller and it wouldn't be worth using complex routing, any larger and it may not be worth the effort due to inefficients as you point out, depends on the number of volunteers I guess. In short: I'd recommend just using intuition, but if that's not an option, give a load more details, and we can work something out. I was after a general solution, I think it would be useful for OSM... ___ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev
Re: [OSM-dev] Doing street names from aerial imagery
On 24 March 2010 12:31, John Robert Peterson jrp@gmail.com wrote: However due to the huge number of variables involved, I'd be surprised if there was any way a computer could do it faster or better: ... When you arrive on the ground you can find that there are names only at one end of a grid of streets, and your carefully pre planned route breaks. There are so many different kinds of areas (grid patterns; modern curvey estates, terraced areas, industrial parks, one way systems) that routing algorithms would have to be tweaked for each area; To be precise the problem is greatly simplified by the fact that most of the variables are unknown because you only have aerial imagery as a source before you map the area, so you know nothing more than the geometry. A complete algorithm would have to go through each possible combination of all the routing parameters (oneways, traffic calming, label on one end, label on the other end, etc etc) and find a solution that gives the best average result but usually it can assume that all roads are equally passable and that both ends of every street need to be visited, and get a very similar result. Cheers ___ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev
Re: [OSM-dev] Doing street names from aerial imagery
On 24 March 2010 21:47, andrzej zaborowski balr...@gmail.com wrote: geometry. A complete algorithm would have to go through each possible combination of all the routing parameters (oneways, traffic calming, label on one end, label on the other end, etc etc) and find a solution Depending on the resolution of the imagery, you can some times work out direction and one way due to arrows painted on the road surface. Same with traffic calming... ___ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev
Re: [OSM-dev] Doing street names from aerial imagery
On 24 March 2010 04:32, John Smith deltafoxtrot...@gmail.com wrote: On 24 March 2010 21:28, Tom Hughes t...@compton.nu wrote: Wanting to divide the job among multiple people probably just makes it harder, but as it's NP-complete to start with I'm not sure that matters ;-) As Gregory points out it would be simple if it was a simple gridded layout and if there was only one person involved, but I was thinking about this from a mapping cake point of view, but simple sectioning may not be the most efficient routing. ___ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev Divide the sections using impassable barriers such as railways and rivers, then by main roads. The side roads of main roads are less likely to be dead ends, so you don't even need to pass down the main road. In the worst case there is a person either side of the main road doing something odd (noting street signs) and they spot each other and smile/wave. It's nice to bump into mappers, and at London mapping parties I make a note who is doing surrounding slices so I can keep an eye out for them. This planning is a lot easier when you have the full road network to look at before hand. You can identify road sections you don't need to go down. Why don't you just man-up (or nerd-up) and go full out with getting house numbers. http://wiki.openstreetmap.org/wiki/Proposed_features/House_numbers/Karlsruhe_Schema This would avoid missing name changes, and catch things like one-ways, shops, and all the other amenities which makes OSM rich. Similar to the London Mapping Parties. You would want to make smaller areas, but it can also be suitable for evening mapping as smaller areas = can be closer to a meeting point. -- Gregory o...@livingwithdragons.com http://www.livingwithdragons.com ___ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev
Re: [OSM-dev] Doing street names from aerial imagery
On 24/03/2010 10:52, John Smith wrote: This is a routing problem, hopefully someone has already solved it. If there is a suburb of streets mapped from aerial imagery and you have several volunteers how do you work out the most efficient path for all the voluneteers to take to grab street names with minimal overlap etc. You need to bear in mind that there will be errors in the tracing anyway -- roads marked that aren't there, and some paths missed that are there. Your volunteers will need to take this into account as well, so sticking to a pre-defined route won't work very well. Use a cake. Cake is good. -- Jonathan (Jonobennett) ___ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev
Re: [OSM-dev] Doing street names from aerial imagery
So we can assume that a bounding area for what we are interested in will be supplied; Assume that there are no oneway systems in place unless that data is already on the server; Assume that all roads are equally passable unless otherwise staed in the database (either by speed restictions or other metadata); Could road passability be calulated usefully from road cureyness? or would it be bust simply to use length? to summerise what I have read so far: There are a set of nodes (each intersection) a set of ways (each of which is linked ot 1 or more nodes) and a separate routing table between nodes (to contain routing metrics) The routing table would be a sparse data stucture (liked list or database reference system etc) and would be asemetric to accomodate one way systems etc. Each way only need one of it's nodes to be visited. We are working out multiple predetermined psudo-optemistic routes that meet the above. I've studied this stuff (at undergrad level) but you'd need ot be a smarter person than me to figure that one out... (not to put a dapener on things, there are many people who are smarter than me...) JR On 24 March 2010 11:50, John Smith deltafoxtrot...@gmail.com wrote: On 24 March 2010 21:47, andrzej zaborowski balr...@gmail.com wrote: geometry. A complete algorithm would have to go through each possible combination of all the routing parameters (oneways, traffic calming, label on one end, label on the other end, etc etc) and find a solution Depending on the resolution of the imagery, you can some times work out direction and one way due to arrows painted on the road surface. Same with traffic calming... ___ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev
Re: [OSM-dev] Doing street names from aerial imagery
On 24 March 2010 21:58, Jonathan Bennett openstreet...@jonno.cix.co.uk wrote: You need to bear in mind that there will be errors in the tracing anyway -- roads marked that aren't there, and some paths missed that are there. Your volunteers will need to take this into account as well, so sticking to a pre-defined route won't work very well. While this is possible, I'm confident the majority of roads have been covered, so much so that people are mapping foot paths. ___ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev
Re: [OSM-dev] Doing street names from aerial imagery
On 24 March 2010 21:53, Gregory nomoregra...@googlemail.com wrote: Why don't you just man-up (or nerd-up) and go full out with getting house numbers. Think of it as a progressive system, first comes the physical street information (the ways), then comes the names and then comes the street numbering. The map becomes progressively more useful with each step, but each step becomes progressively more labour intensive. Besides, what's more nerdy than designing a routing system to collect the most information possible in the least amount of time? ___ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev
Re: [OSM-dev] Doing street names from aerial imagery
On 24 March 2010 22:08, John Robert Peterson jrp@gmail.com wrote: Could road passability be calulated usefully from road cureyness? or would it be bust simply to use length? Both the length and how tight the curves are important, tighter the curves, the slower you must go and the longer the way the longer it takes to traverse. I've studied this stuff (at undergrad level) but you'd need ot be a smarter person than me to figure that one out... (not to put a dapener on things, there are many people who are smarter than me...) So this would be a good project for university students then? :) ___ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev
Re: [OSM-dev] Doing street names from aerial imagery
2010/3/24 John Smith deltafoxtrot...@gmail.com: On 24 March 2010 21:47, andrzej zaborowski balr...@gmail.com wrote: geometry. A complete algorithm would have to go through each possible combination of all the routing parameters (oneways, traffic calming, label on one end, label on the other end, etc etc) and find a solution Depending on the resolution of the imagery, you can some times work out direction and one way due to arrows painted on the road surface. Same with traffic calming... You can do a lot based on aerial imagery, but even more things you can't derive from them, or you can only derive if you know that it is there. I started to map fences, walls and other barriers, but informal openings in them, their height, whether it is a wall or a fence, etc. you can mostly not get from aerial fotos. You might be astonished when visiting an area for real that you previously traced from aerial imagery how much interesting detail you actually missed. cheers, Martin ___ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev
Re: [OSM-dev] Doing street names from aerial imagery
On 25 March 2010 01:06, Martin Koppenhoefer dieterdre...@gmail.com wrote: You can do a lot based on aerial imagery, but even more things you can't derive from them, or you can only derive if you know that it is there. I started to map fences, walls and other barriers, but informal openings in them, their height, whether it is a wall or a fence, etc. you can mostly not get from aerial fotos. You might be astonished when visiting an area for real that you previously traced from aerial imagery how much interesting detail you actually missed. I never said you could get any of those things from aerial imagery. I'm not attempting to map everything to the nth degree, there is a lot of things not mapped in Australia, at this point of time there is a large number of newly developed areas and even fewer people mapping so I'm trying to do my bit by at least trying to work out the most efficient way to collect the most amount of information with the least amount of people in the least amount of time. ___ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev
Re: [OSM-dev] Doing street names from aerial imagery
On 24 Mar 2010, at 10:52, John Smith wrote: This is a routing problem, hopefully someone has already solved it. If there is a suburb of streets mapped from aerial imagery and you have several volunteers how do you work out the most efficient path for all the voluneteers to take to grab street names with minimal overlap etc. Some variant of the Chinese postman algorithm would be my guess... -- Chris Jones, SUCS Admin http://sucs.org ___ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev
