Some gdaldem code is derived from public domain GRASS code

[warmerdam]

Hamish reports:

It has come to my attention that some GRASS code has been ported to C++ under the Apache license, and from there is now included in GDAL/trunk as BSD licensed. It is a substantial rewrite, but I have looked through the code and there is IMO a clear lineage of the core. i.e. AFAICT it is a derivative product -- but the the main question is if any GPL'd fixes or enhancements are involved, or just reuse of CERL public domain code & algorithms?

 http://www.perrygeo.net/wordpress/?p=7

 http://perrygeo.googlecode.com/svn/trunk/demtools/slope.cpp

http://trac.osgeo.org/gdal/browser/trunk/gdal/apps/gdaldem.cpp

specifically this code is derived from r.slope.aspect and r.shaded.relief. (I didn't check the color rules code although the rules format is similar.)

Again, these modules are historically derived from really old CERL code, so _originally_ public domain. IMHO at minimum that should be credited. (the oldest version I have on hand to check is GRASS 4.3, 1999/GPL)

But it definitely includes some of our GPL-era enhancements. (e.g. 'r.shaded.relief scale=')

A fuller discussions is at:

 http://lists.osgeo.org/pipermail/grass-psc/2009-May/000648.html

[hobu]

Gee that sucks. Even did a clean room implementation of the color shaded relief stuff because we couldn't raise Paul Surgeon (the author according to Matt's tools) to get him to agree to the relicense -- there should be no issue with that.

The others, on the other hand, we ported the algorithm from Matt's stuff and then fixed up the code to be more GDAL like and more efficient.

Following GRASS's usage of r.shaded.relief scale= is ok as long as we don't use the same code ;)

So, the question is: do we clean room the other tools, go back to the CERL code (is that around), or scrap the whole thing (gdaldem) entirely?

[hobu]

Replying to warmerdam:

I have looked through the code and there is IMO a clear lineage of the core.

Hamish,

Could you point out which parts of http://trac.osgeo.org/gdal/browser/trunk/gdal/apps/gdaldem.cpp you think currently have GPL derived code in them? The entire thing except for the maths is pretty much a whole-scale rewrite of Matt Perry's implementations.

Howard

[rouault]

Hamish,

I've tried to compare gdaldem.cpp and  http://trac.osgeo.org/grass/browser/grass/trunk/raster/r.slope.aspect/main.c, but except from a few lines of maths, it was not obvious to me that gdaldem.cpp contains derived code from it. And do you think the GRASS code contains a modified version of the CERL code (which I can't find) ? (anyway, I've always thought that maths couldn't be copyrighted.)

Otherwise, I think it's perfectly OK to have the same options and file formats, as those aren't covered by the code copyright. For example, the ICC compiler can accept the same options as GCC, and they aren't clearly sharing the same licencing terms...

If this issue could be resolved by crediting GRASS in some way, we would be happy to do that. But I'm not sure how : if we add copyright lines with names from the GRASS source code (which names ?), wouldn't that imply GPL ?

[neteler]

The GRASS 4.2 tarball (1998) is here:  http://grass.osgeo.org/grass42/source/grass42src.tar.Z (the change to GPL took place in Oct 1999). GRASS 4.2 was in public domain but not audited for non-free code as the GPL version is. However, the DEM part should be clean public domain. Just watch out in particular for the non-free "numerical receipes in C" stuff. r.slope.aspect is in src42/src/raster/r.slope.aspect/cmd/ .

Purist may check the last CERL version 4.1 at  http://grass.osgeo.org/grass41/source/

[hamish]

Howard wrote:

Gee that sucks.

don't worry, it's not game over. Luckily this part of GRASS's code is (probably) mostly based on the 1995 public domain version of GRASS, and thus may give us a way out.

Even did a clean room implementation of the color shaded relief stuff because we couldn't raise Paul Surgeon (the author according to Matt's tools) to get him to agree to the relicense -- there should be no issue with that.

ok glad to hear that part of it is clean.

you may take some other hints from our experience there:

• allowing "percent_value% r g b" as well as "value r g b" is very handy. (percent of range)
• allowing "value r:g:b" as well as "value r g b" is more readable.
• allowing "nv r:g:b" instead of "-32768 r:g:b" for generalized nodata value.

with those you can keep the same color rules files for many different maps instead of having to customize for each one. see the online man page for the GRASS r.colors module for a fuller description:  http://grass.osgeo.org/grass64/manuals/html64_user/r.colors.html

if you can find the 1995 public domain version of GRASS you might(?) find a src/scripts/shells/shade.clr.sh which gives a colorized version of shade.rel.sh, the predecessor to r.shaded.relief, which may be interesting as well. (we never got around to porting that to GRASS 6) I am not sure though, maybe that is a post-CERL Baylor Univ era addon.

Following GRASS's usage of r.shaded.relief scale= is ok as long as we don't use the same code ;)

To be honest, I've always felt that scale= solution was a bit awkward, but have never been able to present a better solution for it. For one thing it assumes that "degrees to meters" is a constant and at the equator. Dividing by a constant (1852m/nm * 60nm/deg) is fairly obvious; my main point with that option is that its presence clearly indicates that the code heritage in gdaldem is from GPL/GRASS not CERL/GRASS as we only added it a couple of years ago.

So, the question is: do we clean room the other tools,

hopefully not necessary,

go back to the CERL code (is that around),

maybe Markus knows if it can be found? Also KerGIS uses it (BSD fork of GRASS), but I couldn't find a copy of it on their download site. But note that the 4.x CERL code lacks floating point and nodata support, so there may well have been some GPL changes since those days.

or scrap the whole thing (gdaldem) entirely?

I think that would be a real shame, and that we can clear this up by auditing against the old CERL/GRASS code. As I wrote earlier today on the GRASS-PSC list however, "confirming that some bits of it were in the public domain does not confirm that other bits of it are not." Also, I think either rewriting or getting permission from the GPL author for relicense will not be difficult in this case, as long as we can prove the core part of the code is unchanged from the public domain. (ie authors probably won't mind as any such GPL additions should be minor)

Could you point out which parts of gdaldem.cpp you think currently have GPL derived code in them? The entire thing except for the maths is pretty much a whole-scale rewrite of Matt Perry's implementations.

yeah, that's the thing though. The part which is derived from the GPL code is the most important part: the implementation of the core method. i.e. the expression of the algorithm.

The C libgrass wrapper glue has been removed and replaced by a C++ libgdal wrapper glue, but that code is not the interesting or novel part of the work worth protecting. The implementation of the core method is.

rouault wrote:

but except from a few lines of maths, it was not obvious to me that gdaldem.cpp contains derived code from it.

again, those lines of maths are the core of the program and crux of the issue.

And do you think the GRASS code contains a modified version of the CERL code

Do you mean: "have those core maths changed since GRASS was public domain code?". I can not say; it needs to be audited before commenting.

FWIW, as I understand the history: The current GPL GRASS code is the direct descendant of the latest US Army Corps of Engineers CERL office GRASS version 4.1 published in 1995 as public domain. At that time Newt Gingrich and his cronies came to power in US politics and passed a number of laws, one of which stated that the US gov't should not be in the [$foo] business and wherever possible they should buy commercial-off-the-shelf solutions rather than develop their own. So after 10+ years of development GRASS had its funding pulled and USACE got out of the GIS game. The Open GRASS Consortium (OGC) was formed to take over, but after some time they decided to go their own way and become the Open GIS Consortium. Things languished for a little bit but then Baylor University in Texas and Markus N in Germany took stewardship, did a GPL/copyright audit, and released GRASS 4.3 as GPL in 1999. This is when the surviving GRASS CVS/SVN history begins.

The history page references a "1995 Unofficial GRASS 5.0 version from USA-CERL", including floating point and Null support. Probably better to audit against that line than look at Markus's 1999 GPL (non FP) version 4.3. ????

(which I can't find) ?

hopefully someone can, because it could clear all of this up rather quickly. As it stands the core methods of gdaldem is a derived work of GPL GRASS code without attribution or respect for upstream license.

(anyway, I've always thought that maths couldn't be copyrighted.)

Algorithms can not [well, should not] be [patented].

The expression/implementation of an algorithm as code can absolutely be copyrighted. What else is worth protecting? To my mind the wrapper bits and error message text are not what constitute the original work.

I think it's perfectly OK to have the same options and file formats

that's not at issue here. AFAIAC the more interoperability and the more we learn from each other, the better.

If this issue could be resolved by crediting GRASS in some way, we would be happy to do that.

attribution is requested, but it doesn't obviate the need for a GPL audit.

But I'm not sure how : if we add copyright lines with names from the GRASS source code (which names ?), wouldn't that imply GPL ?

yes it would. but there's no point to credit folks who contributed GPL libgrass wrapper code which has now been replaced with MIT/X libgdal wrapper code.

perhaps to start with, some text could be added to the header of gdaldem.cpp along the lines of

""" Slope and aspect calculations based on original method for GRASS GIS 4.1(??) by Michael Shapiro, U.S.Army Construction Engineering Research Laboratory Olga Waupotitsch, U.S.Army Construction Engineering Research Laboratory Marjorie Larson, U.S.Army Construction Engineering Research Laboratory

as found in GRASS's r.slope.aspect module.

(dx,dy used in your version?: ) Horn's formula is used to find the first order derivatives in x and y directions for slope and aspect calculations: Horn, B. K. P. (1981). "Hill Shading and the Reflectance Map", Proceedings of the IEEE, 69(1):14-47.

---

Shaded relief based on original method for GRASS GIS 4.1(??) by Jim Westervelt, U.S. Army Construction Engineering Research Laboratory

as found in GRASS's r.shaded.relief (formerly shade.rel.sh) module.

ref(?): "r.mapcalc: An Algebra for GIS and Image Processing", by Michael Shapiro and Jim Westervelt, U.S. Army Construction Engineering Research Laboratory (March/1991) """

Matt has in his code:

• References:
• Burrough, P.A. and McDonell?, R.A., 1998. Principles of Geographical Information Systems. p. 190.

does that have any relevance? If it is possible to cite the original textbook source of the algorithms I think that as a service to future travelers we should mention that in the source code. In this case both modules almost surely predate 1998 so I'm not sure how Burrough & McDonell? are involved in Matt's code.

e.g. if you read through the man pages for the GRASS modules they discuss possible bias in the methods and bounding box adjustments that your users may want to know about.

 http://grass.osgeo.org/grass64/manuals/html64_user/r.slope.aspect.html  http://grass.osgeo.org/grass64/manuals/html64_user/r.shaded.relief.html

best, Hamish

[neteler]

Replying to hamish:

Howard wrote:

...

go back to the CERL code (is that around),

maybe Markus knows if it can be found?

See my comment above.... I have now attached r.slope.aspect, shade.clr.sh and shade.rel.sh from public domain GRASS 4.1 to this ticket.

or scrap the whole thing (gdaldem) entirely?

Please don't. We'll find a solution. ...

FWIW, as I understand the history: The current GPL GRASS code is the direct descendant of the latest US Army Corps of Engineers CERL office GRASS version 4.1 published in 1995 as public domain.

At the same time also an inofficial GRASS 5.0 floating point version (public domain) came out:  http://grass.osgeo.org/grass_cerl_fp_1995/

At that time Newt Gingrich and his cronies came to power in US politics and passed a number of laws, one of which stated that the US gov't should not be in the [$foo] business and wherever possible they should buy commercial-off-the-shelf solutions rather than develop their own. So after 10+ years of development GRASS had its funding pulled and USACE got out of the GIS game. The Open GRASS Consortium (OGC) was formed to take over, but after some time they decided to go their own way and become the Open GIS Consortium. Things languished for a little bit but then Baylor University in Texas and Markus N in Germany took stewardship, did a GPL/copyright audit, and released GRASS 4.3 as GPL in 1999. This is when the surviving GRASS CVS/SVN history begins.

We put it in CVS the week before the "year 2000 bug" - a good incentive.

The history page references a "1995 Unofficial GRASS 5.0 version from USA-CERL", including floating point and Null support. Probably better to audit against that line than look at Markus's 1999 GPL (non FP) version 4.3. ????

GRASS 4.2 was not GPL, my 4.2.1 is currently lost. So just check the attached extract.

...

perhaps to start with, some text could be added to the header of gdaldem.cpp along the lines of """ Slope and aspect calculations based on original method for GRASS GIS 4.1(??) by

yes ...

--- Shaded relief based on original method for GRASS GIS 4.1(??) by Jim Westervelt, U.S. Army Construction Engineering Research Laboratory as found in GRASS's r.shaded.relief (formerly shade.rel.sh) module.

find code attached as well.

Markus

[neteler]

GRASS 4.1 public domain code extract from  http://grass.osgeo.org/grass41/source/

[rouault]

Hamish, Markus,

I've compared gdaldem.cpp with the extract from GRASS 4.1 public domain code and it clearly shows that the formulas used to compute slope and aspect are derived from it, but gdaldem.cpp also seems to include a later improvement that I can see in  http://trac.osgeo.org/grass/browser/grass/branches/releasebranch_5_5/src/raster/r.slope.aspect/cmd/main.c?rev=3 (the first version I could found in GRASS SVN). This is the computing of the aspect as an angle, in addition of the percentage value. Otherwise than that, I, personnaly, don't see any potential issue for slope and aspect computations.

For the hillshade computation, shade.rel.sh from GRASS 4.1 seems to be pretty close to gdaldem.cpp. Except that gdaldem.cpp adds a multiplication by a z variable, and a division by a scale variable, that I can now see in  http://trac.osgeo.org/grass/browser/grass/trunk/scripts/r.shaded.relief/r.shaded.relief.py. Is this an issue ?

Do you think that those improvements are sufficient to justify that they are placed under a newer licence (GPL), instead of the original licence (Public domain) ?

I (and I also speak on Howard's behalf) think we already have spent too much time on this. If you are OK with us adding Hamish's suggested attribution text and that solves the whole issue, then we'll be happy to do that. Otherwise, we won't make you and us lose more time on that, and we'll just 'svn delete' gdaldem.cpp (or put it in the /spike part of our SVN repository, where we have already put all stuff with licencing issues, and add a note about that discussion)

[helena]

I have been involved quite a bit in r.slope.aspect development at CERL especially as it was ported to FP - I worked with Olga closely. I looked at the gdaldem code and I agree that too much time has been spent on this - the computation is clearly based on the original CERL public domain code and the equations are in fact general knowledge (you could have just taken Horn's 1981 paper and code it based on what is there, or from the GRASSbook appendix, and I am guessing that the same equation is also in Burroughs book). The later modifications are nice conveniences but you cannot really put restrictions on feet to meters conversions or degree to percent.

So I don't see a reason for it to be removed from GDAL, but PLEASE, add the attribution to pre-GPL GRASS code.

Helena

[neteler]

Replying to helena: ...

So I don't see a reason for it to be removed from GDAL, but PLEASE, add the attribution to pre-GPL GRASS code.

From what I know about the development of these modules and from the subtle differences you identified, I agree with Helena.

 http://grass.osgeo.org/download/index.php#citing

Markus

[hamish]

Thank you Markus for digging out the CERL code. Thank you Even and Helena for taking the time to review it.

to summarize-

hillshade

Thanks to Even and Markus we can now confirm that, as suspected, the bulk of it is in fact derived from the CERL version. Great.

only two completely trivial changes adapted from the GPL version:

• z-mult: added by Michael Barton in rev 13204.
• scale for lat/lon: added by Gordon Keith to shade.rel.sh grass5 CVS rev 1.7

As it is somewhat irrelevant if I think someone else's change is completely trivial, obvious, or not, and because it is more than just a typo-fix, in an effort to respect the spirit of their contribution I've emailed them both asking them to give their blessing - even if strictly it shouldn't be required for something so simple. Better to waste their/our time than to violate someone's trust.

slope and aspect

Again, thanks to Even and Markus we can now confirm that, as suspected, the bulk of it is in fact derived from the CERL version. Also great. Helena confirms that FP updates now in the code which are not seen in the GRASS 4.1 file were done with/by CERL. Also great.

only change adapted from the GPL version Even could locate:

• compute aspect in degrees instead of percent

(aspect in percent? do you mean slope?)

but in the CERL version Markus attached to this bug in cmd/main.c there is slope_fmt (degrees,percent) already there so I'm not sure what you're referring to.

other than that, as far as I can tell it's is all in the clear.

TODO

• In the header comments of gdaldem please cite the GRASS 4.1 authors (respect the past), and the Horn paper (encourage the future).
• Once that is done ask Matt to apply the same patch to his version.
• Go on our merry way.

comments

• I too have spent altogether way too much time on this. But bordom does not absolve us from performing due diligence.
• more on the GRASS-PSC list thread.

regards, Hamish

[rouault]

Helena, Markus, Hamish,

Yes, my comment was obviously wrong : the computation in degrees instead of percent was for the slope, not the aspect.

I'm attaching a patch that corrects gdaldem.cpp header with proper attribution (based on Hamish's proposal), mentions the names of Michael Shapiro, Olga Waupotitsch, Marjorie Larson, Jim Westervelt and GRASS 4.1 in the Authors section of the man page/HTML page and adds a line in our PROVENANCE.TXT file with appropriate information.

If you think it is appropriate, I'll commit it and can close that ticket ?

I would note that Matt is in the CC list of this ticket, but we, the GDAL project, have no actual way of forcing him to change his version.

I'll probably work on the parsing of the text file used by the color-relief utility to improve interoperability with what is supported by GRASS. The funny thing is that before this whole discussion and being aware that GRASS also used it, I also had the idea of adding the percent_value% syntax...

[rouault]

Proposal to add proper attribution to gdaldem.cpp

[neteler]

Well done - I suggest to patch and close as fixed.

Markus

[hamish]

Gordon sent me this email re the lat/lon scale param in hillshade:

Hamish

Thanks for your consideration and attention to detail.

I'm happy for my changes to be included in GDAL under the appropriate license.

I'm also not sure whether or not it is a trivial change (it probably is) and
in any case it's primarily a rough approximation to work around a problem
rather than an elegant fix.

These days I tend to use GDAL more than GRASS anyway.

Regards
Gordon

More from Michael soon..

re. the patch- apps/gdaldem.cpp: I think you can remove the 4x (c) CERL (lines 12-15), as US Gov't work is by law "without copyright", hence why it is in the public domain.

the "calculations based on original method for GRASS GIS 4.1" section is perfect, thank you.

I'm still not sure how Burrough & McDonell? fit in.

PROVENANCE.TXT: again (AIUI) CERL won't be copyright holders, and the rest after "Derived from modules of GRASS 4.1 (public domain)" with this bug # may be redundant, but whatever you like.

Even:

I would note that Matt is in the CC list of this ticket, but we, the GDAL project, have no actual way of forcing him to change his version.

As the code turns out to be in the clear I wouldn't think of forcing him to do anything. But once we are done here I'll send along a patch and request he commits.

I'll probably work on the parsing of the text file used by the color- relief utility to improve interoperability with what is supported by GRASS. The funny thing is that before this whole discussion and being aware that GRASS also used it, I also had the idea of adding the percent_value% syntax...

well, once again it is a fairly obvious solution to the problem, so not that strange they might happen in parallel. You might also have a look at GMT's CPT color rules format which is a bit more complicated and allows HSV rules (but I think their implementation HSV is slightly busted, or at least awkward and slightly inconsistent; or I'm missing some subtle point..)

a reason to pay attention to CPT is that there's a large collection of tables already out there:

 http://sview01.wiredworkplace.net/pub/cpt-city/

you can look at my shell script for converting them to grass's rules format:

 http://grass.osgeo.org/wiki/GRASS_AddOns#r.cpt2grass

If you find anything in r.cpt2grass of interest, you have my permission to use it as MIT/X with attribution to Jim or myself as appropriate. Again it borrows from CERL code, but that's ok. Anyway I've been thinking for a while to replace the hexagonal color space conversion with a proper cone geometry one so fidelity is not lost, but that's just another thing on the "attention to detail" wish list. :)

I do think you should add an alias for the nodata value though as it would make the rules much more portable. (we use "nv")

regards, Hamish

[hobu]

I have applied a slightly modified version of Even's patch based on the comments in Hamish's post r16943. I also claimed some authorship, though my input has been mostly contained to starting this fiasco ;)

[rouault]

Closing now and changing the summary to reflect the outcome of the discussion...