User:SK53/Mad Ideas

From OpenStreetMap Wiki
Jump to navigation Jump to search

These are occasional notes on things which I'd quite like, but have no idea how to even begin coding.

Naive Triangulation from Images

Update: There are much more sophisticated ideas afoot using modern photogrammetry techniques. See Photogrammetry

As I have a GPS with a compass I've wondered about trying to use triangulation for mapping some features, but have usually backed off the idea as too labour intensive. I've started wondering if one can generate triangulations from geo-tagged photos. A week or so ago I took a series of photos which can be stitched together about 400 m apart at either end of a large field. The particular advantage was at the bottom of the field were several tall Lombardy Poplars growing alongside a stream. On the E side of the field was a church with a spire, already marked on OSM. The following two images are examples: the features I was interested in are marked with vertical red lines, and the number of pixels from the left edge of the image is added as well (as these are resized versions).

Photo Triangulation B 7490c.jpg Photo triangulation B 7513c.jpg

Given knowledge of the camera sensor size and focal length it's possible to determine the Angle of view, which is these cases is around 53 degrees. The Church's relative bearing from the left-hand edge of the photograph is therefore 42% of this value: 22 degrees. As the Church's location on OSM is known, the absolute bearing of the two horizontal edges of the photograph can be determined, and therefore the bearing of items of interest in the photo. Repeating this with other photographs gives multiple bearings allowing triangulation. The image below shows the various bearings plotted over OSM data using Kosmos:

Photo triangulation eg.png

Of course for forms sake I should plot these trees on OSM, but life is sometimes just a tad too short! Note that the position of the stream plotted from NPE can be improved from these triangulations. Obviously the interest is this process could be semi-automated. The kind of workflow I would envisage starting with pairs of geotagged images would involve:

  • Identify known locations on OSM
  • Mark these locations on the paired photographs
  • For each unknown point mark its bearing on each photograph
  • Create a gpx file with the 'baseline', and lines marking bearings. Ideally, the point where the lines meet would be marked by a waypoint. The gpx would need to have timepoints for use with OSM editors, but these could be a) photo/gps timestamps for the baseline and b) the time of first or last edit for the bearing lines and waypoints.
  • Use the gpx file as data within JOSM or Potlatch.

Obviously this is highly naive. It does not take account of a large number of sources of error (inaccuracy in geolocation of photos, location inaccuracy on OSM, differences in height, camera tilt, pan, yaw etc), but it does have the virtue that it could be quite a quick process for capturing otherwise awkward features.

Strip Maps

As old as the hills [1], but fun.

The basic idea would be to extract OSM data aligned along a route, and render a map just for some buffer around that route. The rendered map is then chopped into linear pieces which are aligned side-by-side on the page or screen.

Of course its a bit more complicated than that.

Defining a route

For now the easiest way to define a route is via a .GPX file. These can be created using Cloudmade's website or OpenRouteFinder, or using Garmin tools. It may be important to use an OSM based source (see below).

Creating a buffer

Buffers can easily be created in various GIS tools. For instance QGIS offers a buffer tool in its Vector Geoprocessing menu. Once the buffer polygon is available it can be saved as an ESRI shapefile.

Simple Direction Maps

A great little article in Slate inspired these thoughts. Essentially, the article suggests why hand-drawn maps are often easier to use than professionally created ones. This more-or-less boils down in the process of reducing the data on the map to the minimum required for its purpose: finding the destination & being alerted to errors en route.

Obviously it is impossible to capture all the nuances of a hand-drawn map using an automated method, but there are some common themes which do lend themselves to a programmatic approach:

  • Only show detailed information at route choice points.
  • Maps do not have to be to scale, long distances along obvious routes can be reduced to a short line, particularly if annotated with distance or likely time of travel.
  • Topology is more important than geometry. Lots of curves can be lost, or the roads can even be simplified to a grid as in the London Underground map.
  • Only significant features need to be shown. Usually these are: a) ones which alert to an important junction; b) those at a junction; and c) those immediately after a junction which confirm or reject whether one is on the right road. Significant features often belong to a relatively small class of POIs. In Britain pubs are likely to be important. Churches (with towers/steeples), hospitals and overbridges are other features which may be useful.

Starting Out

Defining the route and selecting OSM data would make use of the same techniques as described above.

Determining key points on the Route

In order to simplify the route the first step is to identify all points which may be needed for navigation. No doubt the eventual list of criteria will be longer. Here's a first cut:

  • All junctions
  • All changes of direction, say, greater than 45 degrees.
  • All significant features within, say, 1km of either of the above.

Just looking at this list immediately suggests that the selection process must be iterative. Many junctions can be eliminated because they are orthogonal to the direction of travel, or obviously involve roads with lesser significance than those followed by the route. In fact it is probably only junctions where two roads diverge at narrow angles, or where the relevant junction is close to another similar junction.

Changes of direction must be significant, in the sense that they must persist. We don't want to flag up every turn on an alpine road! However, we do want to avoid the syndrome where a route follows a numbered road, but the numbered route is non-obvious.

Feature selection should occur only once junctions & direction changes have been selected and simplified.

Extracting OSM Data

If we have a defined buffer we can use the Osmosis Bounding Polygon filter to give a deta-set to work with.

Using OSM Data with BASINS

A discussion with a friend about water flows in a local nature reserve, reminded me that I'd looked at open/free-as-in-beer hydrology modelling software two or three years back. Aside from the inherent complexity of such models, there were no viable UK data. So I was prompted to look again. The starting point is BASINS 4.0 from the US EPA. Here follow notes about getting it running and what might be involved in using OSM data. These will be sporadic as and when the enthusiasm takes me.

BASINS installation under Windows

A simple .zip file can be downloaded from the EPA site. Unzip this and run the windows .exe to install. Note that this installs MapWindows components so if you already have this installed there may be problems.

I originally installed this in my standard program directory on an external disk. I like to use this so that things I'm playing with don't clutter up the laptop for when I'm away from home. Although it installed fine, I was unable to run the tutorial package: it failing to find quite a number of external utilities. Uninstalling & installing in C:\BASINS seems to work fine.

BASINS data

The following data can be accessed natively with the basins software:

  • NHD waterways data (presumably in ESRI shape)
  • Landuse in a raster format (GIRAS)
  • TIGER census transport and other stuff
  • Weather gauge timeseries data in .WMD format
  • DEM, format unknown
  • Water quality data.

In order to be able to make use of BASINS for non-US systems it is necessary to understand whether alternative data formats are acceptable or how to massage data to fit those formats. Obviously the first three are prime candidates for OSM sourcing.

XAPI on Postgres/PostGIS

XAPI is currently slow, unreliable and can take ages to deliver a data set. It is also written in a language which is not familiar to many and therefore not heavily maintained. Other annoyances include the absence of a regular (and predictable) syntax and the failure to deliver compressed files. However, I think the basic functionality of XAPI is pretty clear and does not require a huge degree of change.

No doubt there are any number of ways in which it could be re-factored: these are just my thoughts about how data could be transformed in a Postgres/PostGIS db with a view to optimising query performance for the process of identifying OSM elements to be returned. At present all I am considering is how to get a list of nodes, ways & relations satisfying a given set of predicates to be found quickly. I'm working on the assumption that decent index placement would allow this to be done by the Postgres optimiser.

The basic predicates which need to be supported are: bbox, object types (nodes, ways, relations), user, changeset, tag predicates, and a small number of others (untagged, unwayed, etc). My current idea is to have two tables, one for objects with a postgis BBOX geometry column and a second one for tags: roughly as follows:

CREATE TABLE xapi_objects
(  osm_id integer NOT NULL,
  osm_object_type character(1),
  user_id integer,
  user_name character varying(255) NOT NULL,
  changeset_id integer NOT NULL,
  tagged boolean NOT NULL,
  relationed boolean NOT NULL,
  wayed boolean NOT NULL,
  bbox_geom geometry,
  CONSTRAINT enforce_dims_bbox_geom CHECK (st_ndims(bbox_geom) = 2),
  CONSTRAINT enforce_dims_geom CHECK (st_ndims(geom) = 2),
  CONSTRAINT enforce_geotype_bbox_geom CHECK (geometrytype(bbox_geom) = 'POLYGON'::text OR bbox_geom IS NULL));

This could be populated as one off with SQL like (for osmosis 0.38 version of simple schema):

SELECT 
	nodes.id as osm_id, 
	'N' as osm_object_type, 
	user_id, 
	COALESCE(users.name,'Anon') user_name, 
	changeset_id, 
        -- Kludge to make all rows have a polygonal BBOX, add a small buffer to node geometries
        -- no doubt can be refined at some point
	ST_SETSRID(Box2D(ST_BUFFER(nodes.geom,0.000001)),4326) as bbox_geom, 
	CASE WHEN way_id IS NULL THEN 0 ELSE 1 END wayed, 
	CASE WHEN char_length(cast(avals(tags) as character varying))>2 
		THEN 1 
		ELSE 0 
	END  tagged, 		
	CASE WHEN rm.relation_id IS NULL THEN 0 ELSE 1 END relationed
FROM nodes 
    LEFT JOIN users 
	ON nodes.user_id = users.id
    LEFT JOIN way_nodes 
	ON nodes.id = way_nodes.node_id
    LEFT JOIN relation_members rm 
	ON nodes.id = rm.member_id
	AND rm.member_type IN ('n','N')

SELECT 
	ways.id as osm_id, 
	'W' as osm_object_type, user_id, 
	COALESCE(users.name,'Anon') user_name, 
	changeset_id, 
	-- ST_MAKEBOX2D (nodes.geom, nodes.geom) as bbox, 
	1 wayed, 
	CASE WHEN 
		char_length(cast(avals(tags) as character varying))>2 
	     THEN 1 
	     ELSE 0 
	   END  tagged,
	COALESCE(rm.relation_id, 0) relationed
FROM ways LEFT JOIN users on ways.user_id = users.id
LEFT JOIN relation_members rm on ways.id = rm.member_id
AND rm.member_type IN ('w','W')

/* stuff for relations using with recursive to handle nested rels 
   , but I doubt if it copes with relations containing themselves */
INSERT INTO xapi_objects (
	osm_id
      , osm_object_type
      , user_id
      , user_name
      , changeset_id
      , relationed
      , wayed
      , tagged
      , bbox_geom
 )
WITH RECURSIVE search_graph(par_id, child_id, obj_type, depth) AS (
        SELECT g.relation_id, g.member_id, g.member_type, 1
        FROM relation_members g
      UNION ALL
        SELECT g.relation_id, g.member_id, g.member_type, sg.depth + 1
        FROM relation_members g, search_graph sg
        WHERE g.relation_id = sg.child_id
)
SELECT a.par_id as osm_id
, 'R' as osm_object_type
, r.user_id
, u.name as user_name
, r.changeset_id 
, TRUE AS relationed
, CASE WHEN count(CASE WHEN obj_type = 'W' THEN 1 ELSE 0 END) > 0 THEN TRUE ELSE FALSE END wayed
, 	CASE WHEN 
		char_length(cast(avals(tags) as character varying))>2 
	     THEN TRUE 
	     ELSE FALSE
	   END  tagged
, ST_SETSRID(ST_EXTENT(xo.bbox_geom),4326) as bbox_geom
FROM search_graph a,
xapi_objects xo,
relations r,
users u
WHERE a.child_id = osm_id
AND a.obj_type = xo.osm_object_type
and a.obj_type <> 'R'
and a.par_id = r.id
and r.user_id = u.id
group by a.par_id, r.user_id, u.name, r.changeset_id, 	CASE WHEN 
		char_length(cast(avals(tags) as character varying))>2 
	     THEN TRUE 
	     ELSE FALSE 
	   END ;

Tag table is much simpler:

CREATE TABLE xapi_tags
(
  osm_id integer NOT NULL,
  osm_object_type character(1) NOT NULL,
  k character varying(255) NOT NULL,
  v text NOT NULL
)

and very simple to populate

INSERT INTO xapi_tags (osm_id, osm_object_type, k, v)
SELECT id, 'N', (each(tags)).key, (each(tags)).value FROM nodes	  
UNION ALL
SELECT id, 'W', (each(tags)).key, (each(tags)).value FROM ways
UNION ALL
SELECT id, 'R', (each(tags)).key, (each(tags)).value FROM relations 

Basic form of query:

SELECT
	  xo.osm_id
	, xo.osm_object_type
--	, xo.xml_text
FROM xapi_objects xo
LEFT JOIN xapi_tags xt
ON xo.osm_id = xt.osm_id
AND xo.osm_object_type = xt.osm_object_type
WHERE
-- e.g., bbox predicate

-- e.g., tag predicate
xt.k = 'amenity'
AND xt.v ='hospital'

Things to think about: