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

[Qing Liu]

Hello Paul Ramsey,

Thank you very much for your comments.

My GSoC mentor is Pierre Racine <pierre.racine at sbf.ulaval.ca> from
Université Laval.

> 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 would agree that people will be starting from different kinds of
geometry not just points. However, I want to start with point
geometries and think of working with polylines and polygons based on
the work that will be done for the points.
We are trying to avoid rasterizing the source geometries into raster
or as you mentioned "a grid of starting locations". Although many
other GIS package like ArcGIS and GRASS are either using raster data
or rasterized vector layer as the source data, we want to avoid having
to produce an intermediate raster of sources. Because PostGIS is
strong on raster/vector interaction, we want to come up with a
solution to utilize this feature by using the sources coming from a
set of geometries. (Pierre, please correct me if I was wrong.)

I would like to hear your further thoughts on this issue, please.

Also, I would agree with your point that distance surface is a
specialization of a generalized cost surface. Pierre and other
colleagues are also thinking of creating a distance raster as a
specific case of interpolation. So we are thinking of coming up with a
generic solution to implement this on other kind of distances and
interpolation.

Regards,
Qing


> Date: Mon, 18 Jun 2012 09:35:55 -0700
> From: Paul Ramsey <pramsey at opengeo.org>
> Subject: Re: [postgis-devel] GSoC 2012 PostGIS Raster Project -
>        Distance Analysis in PostGIS Raster (Qing Liu)
> To: PostGIS Development Discussion
>        <postgis-devel at postgis.refractions.net>
> Message-ID:
>        <CACowWR2BCnCsMs2v_Zo--Fe3aQXrukdjvrwgGSQm+jYqPjLtkw at mail.gmail.com>
> Content-Type: text/plain; charset=windows-1252
>
> 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
>
>
> ------------------------------
>
> _______________________________________________
> postgis-devel mailing list
> postgis-devel at postgis.refractions.net
> http://postgis.refractions.net/mailman/listinfo/postgis-devel
>
>
> End of postgis-devel Digest, Vol 111, Issue 35
> **********************************************