Opened 6 years ago

Closed 3 years ago

#2368 closed enhancement (fixed)

Python version of r.grow does not support shrinking

Reported by: wenzeslaus Owned by: grass-dev@…
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)

r.grow.distance.patch (1.6 KB) - added by mmetz 6 years ago.
new flag to shrink (distance to nearest null cell)

Download all attachments as: .zip

Change History (20)

comment:1 in reply to:  description ; Changed 6 years ago by glynn

Replying to wenzeslaus:

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.

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).

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.

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.

comment:2 in reply to:  1 ; Changed 6 years ago by wenzeslaus

Replying to glynn:

Replying to wenzeslaus:

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.

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.

comment:3 in reply to:  2 ; Changed 6 years ago by 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).

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 Changed 6 years ago by wenzeslaus

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 Changed 6 years ago by wenzeslaus

Priority: normalminor

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.

comment:6 in reply to:  3 ; Changed 6 years ago by mmetz

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.

Changed 6 years ago by mmetz

Attachment: r.grow.distance.patch added

new flag to shrink (distance to nearest null cell)

comment:7 in reply to:  6 ; Changed 5 years ago by 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.

comment:8 Changed 4 years ago by neteler

Milestone: 7.1.07.2.0

Milestone renamed

comment:9 in reply to:  7 Changed 4 years ago by 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...

comment:10 Changed 4 years ago by 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'

comment:11 in reply to:  10 Changed 4 years ago by hellik

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"                                                                 |
 |                                                                            |
 +----------------------------------------------------------------------------+

comment:12 in reply to:  10 ; Changed 4 years ago by 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

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 in reply to:  12 Changed 4 years ago by mmetz

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.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.

Support for shrinking with negative radius added to r.grow in r69110. Please try the example in the manual.

comment:14 Changed 4 years ago by neteler

Milestone: 7.2.07.2.1
Priority: minornormal

comment:15 Changed 3 years ago by martinl

Milestone: 7.2.17.2.2

comment:16 Changed 3 years ago by martinl

Milestone: 7.2.27.4.0

All enhancement tickets should be assigned to 7.4 milestone.

comment:17 Changed 3 years ago by neteler

Milestone: 7.4.07.4.1

Ticket retargeted after milestone closed

comment:18 Changed 3 years ago by martinl

What is status of this issue?

comment:19 Changed 3 years ago by annakrat

Resolution: fixed
Status: newclosed

Seems to be solved.

Note: See TracTickets for help on using tickets.