Opened 10 years ago
Closed 7 years ago
#2368 closed enhancement (fixed)
Python version of r.grow does not support shrinking
| Reported by: | wenzeslaus | Owned by: | |
|---|---|---|---|
| Priority: | normal | Milestone: | 7.4.1 |
| Component: | Raster | Version: | svn-trunk |
| Keywords: | r.grow, r.grow.distance, r.buffer, r.buffer.lowmem | Cc: | |
| CPU: | Unspecified | Platform: | Unspecified |
Description
While C version of r.grow supports shrinking (negative distance/radius) since r59735, the Python version of r.grow based on C module r.grow.distance and r.mapcalc expression supports only growing (positive distance/radius). Shrinking (negative buffer) is a useful feature, so I think we should add it.
I'm not sure if negative distances can be added to r.grow.distance.
If not, I would say that we need to use C implementation of r.grow (which might be even faster then the Python script version which calls several modules and creates temporary maps).
If duplication of code would be an issue in case of C r.grow and r.grow.distance, we may consider adding some functions to the library if they are useful for more modules.
r.buffer and r.buffer.lowmem does not seem to support it neither, as far as I know.
v.buffer supports negative distances ("inward buffer" / "negative buffer").
Attachments (1)
Change History (20)
follow-up: 2 comment:1 by , 10 years ago
follow-up: 3 comment:2 by , 10 years ago
Replying to glynn:
Replying to wenzeslaus:
While C version of
r.growsupports shrinking (negative distance/radius) since r59735, the Python version ofr.growbased on C moduler.grow.distanceandr.mapcalcexpression supports only growing (positive distance/radius). Shrinking (negative buffer) is a useful feature, so I think we should add it.For me, the question isn't whether it's useful, but whether it belongs in r.grow, as opposed to a separate r.shrink module. The two operations are quite different (growing has to determine the correct value for "new" cells, shrinking only discards data).
r.shrink, this makes sense. But maybe the difference is not so big. What about shrinking the original values but putting there some new ones.
I'm not sure if negative distances can be added to
r.grow.distance.Shrinking can be implemented using r.grow.distance by first generating an "inverted" map (null if the input is non-null, non-null if the input is null), growing the inverted map, inverting the result, then using it as a mask.
Creating yet another intermediate map, this is what I'm afraid of, this is always slow.
Whether this will be faster than the C version depends upon the size of the buffer and the proportion of non-null cells. The worst-case time for r.grow.distance is proportional to the size of the input, whereas the worst-case time for the C version of r.grow is also proportional to the size of the buffer (specifically, to its area, i.e. the square of its radius).
For a sufficiently large buffer, r.grow.distance will be faster. Unless the cross-over point is unreasonably large, it may be worth implementing an r.grow.distance-based version even if the C version of r.grow is provided.
Having two versions of the same module is inconvenient. What about moving C version of r.grow to addons under a different name. I don't have any suggestion right now but perhaps somebody else has.
follow-up: 6 comment:3 by , 10 years ago
Replying to wenzeslaus:
I'm not sure if negative distances can be added to
r.grow.distance.
Having thought about this some more ...
In the case where you're interested in the distance= map (rather than the value= map), distance inside is just as meaningful as distance outside.
An r.shrink.distance module would be structurally similar (i.e. a near clone), so it makes sense to try to keep them in the same module.
The easiest change would be to have an "invert" flag which caused the distance= map to contain the distance from the nearest null cell (currently, it's the distance from the nearest non-null cell, so the non-null cells themselves have a distance of 0).
The value= map (which normally contains the value of the nearest non-null cell) would be meaningless in this case; the value of the nearest null cell is always null.
Alternatively, it could calculate both positive and negative distances simultaneously, and could probably even use the same arrays for both calculations.
(Would we need to add a flag to enable negative distances? It's an incompatible change, but the module is new in 7.0. Are the 7.0 betas something with we now need to retain compatibility?).
For non-null cells, the {old,new}_{x,y}_row and dist_row arrays always contain zero (i.e. the x and y offsets and the distance to the nearest non-null cell are always zero), and the {old,new}_val_row arrays (the value of the nearest non-null cell) always contain the current cell's value. This is all information which can be deduced directly from the current input row.
It's only for null cells where the arrays contain accumulated results.
The only drawback is that lookups would be complicated slightly, but the performance impact should be trivial.
comment:4 by , 10 years ago
As a quick solution to enable functionality of C version of r.grow I would suggest to move it to addons under a different name (r.grow.c, r.grow2, r.grow.negative, r.grow.inside, r.grow.shrink?). This will provide convenient access to this functionality before what glynn is suggesting gets implemented.
comment:5 by , 10 years ago
| Priority: | normal → minor |
|---|
C version of r.grow moved to addons as r.grow.shrink in r62819, so the shrinking functionality is available for all without compiling.
However, I would like to see this ticket resolved by adding the functionality as suggested earlier.
follow-up: 7 comment:6 by , 10 years ago
Replying to glynn:
Replying to wenzeslaus:
I'm not sure if negative distances can be added to
r.grow.distance.Having thought about this some more ...
In the case where you're interested in the distance= map (rather than the value= map), distance inside is just as meaningful as distance outside.
An r.shrink.distance module would be structurally similar (i.e. a near clone), so it makes sense to try to keep them in the same module.
The easiest change would be to have an "invert" flag which caused the distance= map to contain the distance from the nearest null cell (currently, it's the distance from the nearest non-null cell, so the non-null cells themselves have a distance of 0).
Attached is a minimally invasive patch to add a new flag to r.grow.distance, calculating the distance to the nearest null cell.
by , 10 years ago
| Attachment: | r.grow.distance.patch added |
|---|
new flag to shrink (distance to nearest null cell)
follow-up: 9 comment:7 by , 9 years ago
Replying to mmetz:
Replying to glynn:
The easiest change would be to have an "invert" flag which caused the distance= map to contain the distance from the nearest null cell (currently, it's the distance from the nearest non-null cell, so the non-null cells themselves have a distance of 0).
Attached is a minimally invasive patch to add a new flag to r.grow.distance, calculating the distance to the nearest null cell.
Patch applied to trunk in r67620.
comment:9 by , 8 years ago
Replying to neteler:
Replying to mmetz:
Replying to glynn:
The easiest change would be to have an "invert" flag which caused the distance= map to contain the distance from the nearest null cell (currently, it's the distance from the nearest non-null cell, so the non-null cells themselves have a distance of 0).
Attached is a minimally invasive patch to add a new flag to r.grow.distance, calculating the distance to the nearest null cell.
Patch applied to trunk in r67620.
Can I backport this to 7.2.0? Again I need a negative buffer...
follow-ups: 11 12 comment:10 by , 8 years ago
Just tested r.grow with a negative radius and the following error occurs:
# NC sample dataset v.in.region box v.to.rast input=box output=box use=val val=1 r.grow input=box output=box_shrink radius=-20.01 Reading raster map <box>... 100% Writing output raster maps... 100% ERROR 1: PredictorSetup:Horizontal differencing "Predictor" not supported with 64-bit samples ERROR 1: PredictorSetup:Horizontal differencing "Predictor" not supported with 64-bit samples ERROR 1: PredictorSetup:Horizontal differencing "Predictor" not supported with 64-bit samples ERROR 1: PredictorSetup:Horizontal differencing "Predictor" not supported with 64-bit samples 100% ERROR 1: PredictorSetup:Horizontal differencing "Predictor" not supported with 64-bit samples ERROR 1: PredictorSetup:Horizontal differencing "Predictor" not supported with 64-bit samples Color table for raster map <box_shrink> set to 'box'
comment:11 by , 8 years ago
Replying to neteler:
Just tested r.grow with a negative radius and the following error occurs:
# NC sample dataset v.in.region box v.to.rast input=box output=box use=val val=1 r.grow input=box output=box_shrink radius=-20.01 Reading raster map <box>... 100% Writing output raster maps... 100% ERROR 1: PredictorSetup:Horizontal differencing "Predictor" not supported with 64-bit samples ERROR 1: PredictorSetup:Horizontal differencing "Predictor" not supported with 64-bit samples ERROR 1: PredictorSetup:Horizontal differencing "Predictor" not supported with 64-bit samples ERROR 1: PredictorSetup:Horizontal differencing "Predictor" not supported with 64-bit samples 100% ERROR 1: PredictorSetup:Horizontal differencing "Predictor" not supported with 64-bit samples ERROR 1: PredictorSetup:Horizontal differencing "Predictor" not supported with 64-bit samples Color table for raster map <box_shrink> set to 'box'
tested your example by
System Info GRASS Version: 7.3.svn GRASS SVN revision: r69040 Build date: 2016-07-29 Build platform: x86_64-w64-mingw32 GDAL: 2.1.0 PROJ.4: 4.9.2 GEOS: 3.5.0 SQLite: 3.7.17 Python: 2.7.5 wxPython: 2.8.12.1 Platform: Windows-8-6.2.9200 (OSGeo4W)
r.grow --verbose input=rbox@user1 output=rbox_shrink2 radius=-500.1 Lese Rasterkarte <rbox@user1> ... Schreibe Ausgabe-Rasterkarten... Color table for raster map <rbox_shrink2> set to 'rbox@user1'
result raster is the same as the input raster, but no shrinking
r.info map=rbox@user1 +----------------------------------------------------------------------------+ | Map: rbox@user1 Date: Sat Aug 06 21:16:35 2016 | | Mapset: user1 Login of Creator: hkmyr | | Location: nc_spm_08_grass7 | | DataBase: D:\grassdata | | Title: Rasterized vector map from values | | Timestamp: none | |----------------------------------------------------------------------------| | | | Type of Map: raster Number of Categories: 1 | | Data Type: CELL | | Rows: 1350 | | Columns: 1500 | | Total Cells: 2025000 | | Projection: Lambert Conformal Conic | | N: 228500 S: 215000 Res: 10 | | E: 645000 W: 630000 Res: 10 | | Range of data: min = 1 max = 1 | | | | Data Source: | | Vector Map: box@user1 | | Original scale from vector map: 1:1 | | | | Data Description: | | generated by v.to.rast | | | | Comments: | | v.to.rast input="box@user1" layer="1" type="point,line,area" output=\ | | "rbox" use="val" value=1 memory=300 | | | +----------------------------------------------------------------------------+ (Sat Aug 06 21:22:58 2016) Befehl ausgeführt (0 Sek) (Sat Aug 06 21:23:06 2016) r.info map=rbox_shrink2@user1 +----------------------------------------------------------------------------+ | Map: rbox_shrink2@user1 Date: Sat Aug 06 21:19:58 2016 | | Mapset: user1 Login of Creator: hkmyr | | Location: nc_spm_08_grass7 | | DataBase: D:\grassdata | | Title: rbox_shrink2 | | Timestamp: none | |----------------------------------------------------------------------------| | | | Type of Map: raster Number of Categories: 0 | | Data Type: DCELL | | Rows: 1350 | | Columns: 1500 | | Total Cells: 2025000 | | Projection: Lambert Conformal Conic | | N: 228500 S: 215000 Res: 10 | | E: 645000 W: 630000 Res: 10 | | Range of data: min = 1 max = 1 | | | | Data Description: | | generated by r.mapcalc | | | | Comments: | | if(!isnull(rbox@user1), rbox@user1, if(r.grow.tmp.7272.dist < | | 25010001, r.grow.tmp.7272.val, null())) | | r.grow.py "--verbose" "input=rbox@user1" "output=rbox_shrink2" "radius= | | -500.1" | | | +----------------------------------------------------------------------------+
follow-up: 13 comment:12 by , 8 years ago
Replying to neteler:
Replying to neteler:
Replying to mmetz:
Replying to glynn:
The easiest change would be to have an "invert" flag which caused the distance= map to contain the distance from the nearest null cell (currently, it's the distance from the nearest non-null cell, so the non-null cells themselves have a distance of 0).
Attached is a minimally invasive patch to add a new flag to r.grow.distance, calculating the distance to the nearest null cell.
Patch applied to trunk in r67620.
Can I backport this to 7.2.0? Again I need a negative buffer...
This is a new feature and as such does not qualify for backport.
If you want to shrink you can use
r.mapcalc "input_inv = if(isnull(input), 1, null())" r.grow input=input_inv
Replying to neteler:
Just tested r.grow with a negative radius and the following error occurs:
# NC sample dataset v.in.region box v.to.rast input=box output=box use=val val=1 r.grow input=box output=box_shrink radius=-20.01
The example is wrong because there are no NULL cells in the current region for the input raster. When growing, for each NULL cell the distance to the nearest non-NULL cell is calculated. When shrinking, for each non-NULL cell the distance to the nearest NULL cell is calculated. That means there must be both NULL and non-NULL cells in the input raster for the current region, otherwise nothing can be grown or shrunk.
The example can not work because r.grow does not support negative distances. A test needs to be added to the script to call r.grow.distance with the new flag if the radius is negative, and a different r.mapcalc expression must be used to create the final output:
"$output = if($dist < $radius,null(),$old)"
Reading raster map <box>... 100% Writing output raster maps... 100% ERROR 1: PredictorSetup:Horizontal differencing "Predictor" not supported with 64-bit samples ERROR 1: PredictorSetup:Horizontal differencing "Predictor" not supported with 64-bit samples ERROR 1: PredictorSetup:Horizontal differencing "Predictor" not supported with 64-bit samples ERROR 1: PredictorSetup:Horizontal differencing "Predictor" not supported with 64-bit samples 100% ERROR 1: PredictorSetup:Horizontal differencing "Predictor" not supported with 64-bit samples ERROR 1: PredictorSetup:Horizontal differencing "Predictor" not supported with 64-bit samples Color table for raster map <box_shrink> set to 'box'
These look like GDAL errors, they are definitively not GRASS errors.
comment:13 by , 8 years ago
Replying to mmetz:
Replying to neteler:
Replying to neteler:
Replying to mmetz:
Replying to glynn:
The easiest change would be to have an "invert" flag which caused the distance= map to contain the distance from the nearest null cell (currently, it's the distance from the nearest non-null cell, so the non-null cells themselves have a distance of 0).
Attached is a minimally invasive patch to add a new flag to r.grow.distance, calculating the distance to the nearest null cell.
Patch applied to trunk in r67620.
Can I backport this to 7.2.0? Again I need a negative buffer...
This is a new feature and as such does not qualify for backport.
If you want to shrink you can use
r.mapcalc "input_inv = if(isnull(input), 1, null())" r.grow input=input_inv
I meant r.grow.distance, not r.grow.
Replying to neteler:
Just tested r.grow with a negative radius and the following error occurs:
# NC sample dataset v.in.region box v.to.rast input=box output=box use=val val=1 r.grow input=box output=box_shrink radius=-20.01The example is wrong because there are no NULL cells in the current region for the input raster. When growing, for each NULL cell the distance to the nearest non-NULL cell is calculated. When shrinking, for each non-NULL cell the distance to the nearest NULL cell is calculated. That means there must be both NULL and non-NULL cells in the input raster for the current region, otherwise nothing can be grown or shrunk.
The example can not work because r.grow does not support negative distances.
Support for shrinking with negative radius added to r.grow in r69110. Please try the example in the manual.
comment:14 by , 8 years ago
| Milestone: | 7.2.0 → 7.2.1 |
|---|---|
| Priority: | minor → normal |
comment:15 by , 8 years ago
| Milestone: | 7.2.1 → 7.2.2 |
|---|
comment:16 by , 7 years ago
| Milestone: | 7.2.2 → 7.4.0 |
|---|
All enhancement tickets should be assigned to 7.4 milestone.
Replying to wenzeslaus:
For me, the question isn't whether it's useful, but whether it belongs in r.grow, as opposed to a separate r.shrink module. The two operations are quite different (growing has to determine the correct value for "new" cells, shrinking only discards data).
Shrinking can be implemented using r.grow.distance by first generating an "inverted" map (null if the input is non-null, non-null if the input is null), growing the inverted map, inverting the result, then using it as a mask.
Whether this will be faster than the C version depends upon the size of the buffer and the proportion of non-null cells. The worst-case time for r.grow.distance is proportional to the size of the input, whereas the worst-case time for the C version of r.grow is also proportional to the size of the buffer (specifically, to its area, i.e. the square of its radius).
For a sufficiently large buffer, r.grow.distance will be faster. Unless the cross-over point is unreasonably large, it may be worth implementing an r.grow.distance-based version even if the C version of r.grow is provided.