Changes between Version 72 and Version 73 of PostGIS_Raster_SoC_Idea_2012/Distance_Analysis_Tools

Timestamp:

Jul 13, 2012, 10:41:08 PM (12 years ago)

Author:

qliu

Comment:

—

PostGIS_Raster_SoC_Idea_2012/Distance_Analysis_Tools

@@ -55 +55 @@
 <LI><A href=http://trac.osgeo.org/postgis/wiki/PostGIS_Raster_SoC_Idea_2012/Distance_Analysis_Tools#Week6Report>Week 6 Report (June 25th - June 29th)</A></LI>
 <LI><A href=http://trac.osgeo.org/postgis/wiki/PostGIS_Raster_SoC_Idea_2012/Distance_Analysis_Tools#Week7Report>Week 7 Report (July 2nd - July 6th)</A></LI>
+<LI><A href=http://trac.osgeo.org/postgis/wiki/PostGIS_Raster_SoC_Idea_2012/Distance_Analysis_Tools#Week8Report>Week 8 Report (July 9th - July 13th)</A></LI>
 </UL>
 <br>
@@ -716 +717 @@
 
  * Start to work on implementing a plpgsql prototype of the preferred solution in the document
+
+----
+{{{
+#!html
+<div style='float: right; width:100px;'>
+<a href="#PostGISRasterSoCIdea2012-DistanceAnalysisToolsforPostGISRaster">&nbsp;&nbsp;&nbsp;<img src="https://lh3.googleusercontent.com/-YR7gUJULQrM/T8nEPQ-AtzI/AAAAAAAAA1M/T_6vRjE8E4Q/s40/scroll_to_top_icon_40x40.png"><br>back to top</a>
+</div>
+}}}
+
+== Week 8 Report ==
+
+'''What did you get done this week?'''
+ * Did research on the scanning algorithm used by GDAL and GRASS
+
+ * Second revised document of "Creating an Euclidean Distance Raster in PostGIS" is here:
+[http://trac.osgeo.org/postgis/wiki/PostGIS_Raster_SoC_Idea_2012/Distance_Analysis_Tools/document]
+[[BR]][[BR]]
+'''"gdalproximity" for euclidean distance in GDAL and the "r.grow.distance" in GRASS'''
+
+ * Both of them require source features in raster format
+ * Both of them create distance raster (and temporary file during computation) from the source raster, which dosenot allow source features to fall outside of the resulted distance raster
+ * Both of them use linescan to iterate among pixels to find the nearest target to the current pixel and the shortest distance
+ * "gdalproximity" in GDAL allocates buffer for two scanlines of distance, one loop from top to bottom of the raster, the other loop from bottom to top. For each current rows, it scans colums from left to right, and right to left. Each scanline also iterate among the source points, and replace current distance value with the shorter one (from above,below,left,right) if that applies. (Although ArcGIS doesn't reveal their scanning algorithm, from what was briefly described in their documentation, it is very likely that they are using a similar way of scanning method)
+ * "r.grow.distance" in GRASS dose it in another way. It computes the distance to the source points from current pixel at the same time of creating the output distance raster. It iterates among rows and then columns in each scan row, scanning left, right, and then top-left,above,top-right, replacing distance value while shorter one found. And then does another scanning while writing the output distance raster, in a reversed way of scanning (first top-left,above, top-right, and then left and right).
+ * Both methods could be very inefficient if the target points (features) come in a very large size.
+
+'''Source code:'''
+
+ * "gdalproximity" (both c++ and java implementation):
+  [http://code.metager.de/source/xref/gdal/alg/gdalproximity.cpp]
+  [http://code.metager.de/source/xref/gdal/swig/java/apps/GDALProximity.java]
+
+ * grass/r.grow.distance (C implementation)
+  [http://trac.osgeo.org/grass/browser/grass/branches/develbranch_6/raster/r.grow.distance/main.c]
+
+{{{
+'''Comments from Mentor'''
+>> Do those algorithms have known names?
+
+> They are called "sequential algorithms" in distance mapping,
+with which the distance surface will ideally be created across the
+entire image(raster) in one scan. ArcGIS also uses sequential
+algorithms in the scanning process.
+
+> The distance for the current pixel
+under scanning is computed using recently computed values from the
+present scan in the neighborhood. For example, in one row scan,
+Dist_row(col) is determined by comparing current Dist_row(col) with
+the distance value assigned in its neighbor (say, Dist_row(col-1))
+plus the distance from current pixel to its neighbor. If the computed
+distance is greater than Dist_row(col), then do nothing; otherwise
+Dist_row(col) will be replaced with the newly computed distance.
+
+> GRASS's "r.grow.distance" is computing octagonal distance, while GDAL
+"gdalproximity" is doing a chessboard scanning manner. GRASS
+"r.grow.distance" creates the distance surface in a "growing" manner
+from the source points, computing distance from it's neighbor to the
+left/right/above/top-left/top-right. GDAL computes from the neighbor
+to the left/right, above/below, topright/bottomleft.
+
+>> What is important here is "how many times each algorithm scan the whole
+>> raster?". Is one more efficient than the other one?
+
+> In terms of scanline, both approaches do only one scan for the whole
+raster, row by row.
+In terms of pixels,
+GDAL "gdalproximity" scan all the pixel once. It has two scanlines
+from top to bottom and bottom
+ to top, then for each row, it also has two scanlines from right to
+left and left to right.
+(ArcGIS says they are using a "two-scan sequential process", however,
+they didn't explain it in details in the document, so I would assume
+they are using similar algorithms as GDAL.)
+
+> GRASS actually scans columns in each row 4 times. The first time is to
+assign distance value of "0" to source pixels. Then 3 times for the
+neighbor to the left, right, and topleft/above/topright.
+
+> So in terms of scanning times, it looks like GDAL is more efficient.
+
+>> To which one of those two algorithms our approach is similar (or
+>> comparable)?
+
+> Our approach will scan the whole
+raster only once. So we could use a similar scanning algorithm as GDAL
+in terms of utilizing scanlines to do multiple scans simultaneously.
+
+>> Could you describe, in two short sentences, how each of them decide which
+>> source is the nearest for each pixel?
+
+> I think both approaches don't have a specific
+process to actually determine the nearest source pixel to the current
+one, but use this sequential scanning to replace distance with shorter
+one from their neighbors. So it's like an accumulative method and
+scanning in a "growing" manner. I actually think this algorithms could
+be reusable for cost-weighted distance computation. 
+
+>> Are you still confident in our approach now that you understand better
+>> those two algorithms? Why?
+
+> Yes, I think our approach utilizing KNN indexing will show its
+efficiency while dealing with vary large source dataset and very high
+resolution resulted distance raster. Because both methods in GDAL and
+GRASS require the source data come in a raster format, and create
+resulted raster from the input source raster, and also will create
+temporary files during the computing process which will be very memory
+intensive when dealing with large dataset. Also, they don't provide
+the scalability for large tiled coverage and flexibility for source
+data being outside of the resulted distance extent.
+}}}
+
+
+[[BR]][[BR]]
+''' What do you plan on doing next week?'''
+
+ * Continue to work on implementing a plpgsql prototype for Approach 3 in the document