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

[Qing Liu]

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