[postgis-devel] GSoC 2012 PostGIS Raster Project - Distance Analysis in PostGIS Raster (Qing Liu)

[Paul Ramsey]

Qing Liu,
Who is your GSOC mentor?

On the algorithm side, the first case is "OK", though of limited value
I would imagine (most use cases will involve multiple inputs, and not
just points).

On the multiple inputs side, you really have to grapple with the fact
that people will be starting from many different kinds of geometry, so
your input is best not thought of as  "a multipoint" but "a grid of
starting locations", which could be derived from any kind of geometry.

I also note that the distance grid is actually just a specialization
of a generalized cost surface, where grid values are calculated as
using input of a starting point grid and a friction grid. In the case
of the distance grid you are just assuming a uniform friction grid,
but for maximum utility you might want to consider doing a cost
surface instead.

The algorithm is much less parallelizable, because you have to work
out from the start points, however it's a nice little recursive
function. From each start point you calculate the cost of the
neighbors as a product of the friction of the neighbor and the
distance to the neighbor (one unit in left-right-up-down directions,
root-2 units in the diagonals). If a cell already has a value, skip
it. You can use a threshold as in your algorithm as a stopping
condition.

With a friction grid of 1, this nets out to the distance grid.

P.


On Mon, Jun 18, 2012 at 4:21 AM, Qing Liu <liu.qing.1984 at gmail.com> wrote:
> Hello List,
>
> I am here to present my PostGIS Raster project for this year's GSoC.
> This is my first time to work on a database project like PostGIS,
> which is very challenging to me.  I will appreciate any comment from
> the community on this project very much.
>
> Here is the link to my GSoC proposal:
> http://google-melange.appspot.com/gsoc/proposal/review/google/gsoc2012/kya_na/1
>
> And Here is the link to the wiki page on this project where I post my
> weekly report:
> http://trac.osgeo.org/postgis/wiki/PostGIS_Raster_SoC_Idea_2012/Distance_Analysis_Tools
>
> Up to now, I have written a rough proposal on how to create Euclidean
> distance surface as a single raster from source data point(s) in
> PostGIS Raster. We have been considering some constraints and think
> that we might have to end up with different approaches depending on
> different constraints.
>
> For now, I have been considering creating Eculidean distance surface
> from a single point geometry and muliple point geometries:
>
> Case 1 - One-Point Source
> To create distance surface from source data containing only one point
> geometry as the source point.
>
>    Inputs:
>        geometry - One single PostGIS geometry to create distance surface from
>        geographic extent - Dimension of the output raster
>        georeferencing - Information of how the raster is georeferenced
>        maximum distance - The threshold that the accumulative
> distance values cannot exceed. When exceeding this value, NoData will
> be assigned for the output pixel value. The default threshold is to
> the edge of the output raster extent.
>
>    Output:
>        Generate one single raster (rectan) in which pixel values
> represent the Euclidean distance from the center of the pixels to the
> center of the source point.
>
>    Proposed Algorithm:
>        Calculate Euclidean distance using the coordinates of the
> center of pixel and the center of the source point (d(dx,dy) =
> sqrt(dx^2 + dy^2)).  If distance exceed max_distance specified, NoData
> value is used instead.
>        Create a single raster with distance as pixel value
> (ST_RasterFromText()?) using dimensions and georeferencing information
> specified
>
>
> Case 2 - Multi-point Source
> To create distance surface from source data containing multiple point
> geometries as the source points.
>
>    Inputs:
>        geometry - Multiple PostGIS geometries to create distance surface from
>        geographic extent - Dimension of the output raster
>        georeferencing - Information of how the raster is georeferenced
>        maximum distance - The threshold that the accumulative
> distance values cannot exceed. When exceeding this value, NoData will
> be assigned for the output pixel value. The default threshold is to
> the edge of the output raster extent.
>
>    Output:
>        Generate one single raster (rectan) in which pixel values
> represent the Euclidean distance from the center of the pixels to the
> center of its nearest source point.
>
>    Proposed Algorithm:
>        Scan through pixels, compute the KNN index for each pixel to
> its nearest source point, assign Euclidean distance using the
> coordinates of the center of the pixel and the center of its nearest
> source point (d(dx,dy) = sqrt(dx^2 + dy^2)).  If distance exceed
> max_distance specified, NoData value is used instead.
>        Create a single raster with distance as pixel value
> (ST_RasterFromText()?) using dimensions and georeferencing information
> specified
>
>    Scalability:
>        In case of source data being large size dataset (e.g.
> containing billions of points), the KNN indexing approach should be
> able to help us in quickly identifying the nearest point to the pixel
> without rescanning all the points for every pixel.
>
>    Possibility:
>        It is possible to work with line geometries and polygon
> geometries utilizing the algorithms for the multi-point solution
>            distance will be computed from the center of each pixel to
> the center of its nearest pixel on the line or polygon
>                In case of single line or polygon geometry, the
> default output raster extent will be the same as the source line or
> polygon.
>                Note that pixels within the polygon will be assigned
> “0” distance or NoData value
>
>    Performance:
>        The speed depends on the number of source points, as well as
> the size of the produced raster.
>        By utilizing KNN indexing, we expect the speed to be
> independent from the number of the source points.
>        There are limits of the data structure imposed by the database
> needed to be considered like the fact that all the geometries are
> stored in different rows.
>
>    Flexibility:
>        The solution for calculating Euclidean distance can be
> implemented for other kinds of distances (e.g. cost-weighted
> distance). Euclidean distance will be used as the base layer. The
> cost-weighted distance could be calculated from the Euclidean distance
> surface with the cost surface. ST_MapAlgebraExpr two raster bands
> version could be utilized for computing.
>
> Again, any feedback would be very helpful to me. I would appreciate it
> very much!
>
> With Regards,
> Qing Liu
> _______________________________________________
> postgis-devel mailing list
> postgis-devel at postgis.refractions.net
> http://postgis.refractions.net/mailman/listinfo/postgis-devel