[GRASS-dev] point cloud analysis: new features
Paulo van Breugel
p.vanbreugel at gmail.com
Wed Jan 7 03:35:44 PST 2015
On Mon, Jan 5, 2015 at 12:17 PM, Benjamin Ducke <benducke at fastmail.fm>
wrote:
> On 04/01/15 23:00, Paulo van Breugel wrote:
> > Tried it out, and it works like a charm, great!
> >
> > One question/request, would it be terribly difficult to add an option to
> > compute an user-defined number of clusters of equal size?
> >
>
> I think you are looking for a completely different algorithm
> there. There are many clustering methods that will produce
> exactly k clusters. But what do you mean by size: number of
> points per cluster or spatial extent/area?
>
Yes, I was looking at something similar to what the function stratify in
the R spcosa package does: "Methods for partitioning a spatial object into
compact strata by means of k-means. The objective function to minimize is
the mean squared shortest distance (MSSD). Optionally, the strata may be
forced to be of equal size. This facilitates field work in case of
stratified simple random sampling for composites". The key here is to
create as compact strata as possible, optionally of equal size (number of
points per cluster).
> In both cases, I am not sure how you would reconcile the
> two opposing goals: (A) find the actual cluster shapes,
> (B) make the cluster shapes so that all clusters are of
> equal size.
>
> (please see also my comment to Markus below).
>
> >
> >
> > On Sun, Jan 4, 2015 at 9:02 PM, Markus Metz
> > <markus.metz.giswork at gmail.com <mailto:markus.metz.giswork at gmail.com>>
> > wrote:
> >
> >
> > Done in trunk r63952 as v.cluster. It is not a GRASS7 addon because
> it
> > does not work with G7.0. At the moment it only identifies and labels
> > clusters. Connectivity graphs and cluster shapes are not implemented.
> > In future, I would like to add OPTICS because OPTICS can better
> handle
> > different clusters with different densities.
> >
>
> Thanks Markus, this is excellent progress.
> It seems to me that the approximation of cluster shapes from grouped
> points is a generic problem that would best be solved with a separate
> module. As long as the shapes are roughly convex, the existing v.hull
> should work fine. For concave shapes, AFAIK things become messy because
> common methods such as alpha shapes require the user to provide
> threshold values.
>
> Cheers,
>
> Ben
>
> > Markus M
> >
> > >
> > > There is a reference implementation (albeit in Java) that you can
> > > use to compare it with other clustering algorithms:
> > >
> > > http://elki.dbs.ifi.lmu.de/
> > >
> > > An implementation in C (that I have not tried) is here:
> > >
> > > https://github.com/siddharth950/DBSCAN
> > >
> > > The one drawback of DBSCAN is that it needs an efficient spatial
> > > index to perform well -- and you have just taken care of that!
> > >
> > >> - point cloud thinning: a sample can be generated from a large
> point
> > >> cloud by specifying a minimum distance between sample points. To
> be
> > >> implemented.
> > >>
> > >> The new k-d tree is now used by v.clean tool=snap
> > (Vect_snap_lines()),
> > >> reducing both memory consumption and processing time.
> > >>
> > >
> > > I would also like to point out that SAGA GIS is moving into
> > > the same direction, i.e. more efficient processing of very
> > > large point clouds. The latest release includes a number
> > > of new point cloud tools. Perhaps it's worth a look.
> > >
> > > Most importantly, SAGA GIS has introduced a new file format,
> > > the SAGA Pointcloud (.spc) format. It is compact and yet
> > > flexible enough for a variety of purposes. I recommend to
> > > consider implementing import/export of this format in GRASS 7,
> > > preferably not via v.in.ogr, to avoid the OGR model conversion
> > > overhead.
> > >
> > > If you think this would be an interesting option, then you can
> > > find a summary on our tracker:
> > >
> > > http://gvsigce.sourceforge.net/mantis/view.php?id=595
> > >
> > > (we are going to implement ".spc" in gvSIG CE, as well).
> > >
> > > Best wishes,
> > >
> > > Ben
> > >
> > >>
> > >> More technical:
> > >> the new k-d tree finds the exact nearest neighbor(s), not some
> > >> approximation. It supports up to 255 dimensions. It is dynamic,
> i.e.
> > >> points can be inserted and removed at any time. It is balanced to
> > >> improve search performance. It provides k nearest neighbor search
> > >> (find k neighbors to a given coordinate) as well as radius or
> > distance
> > >> search (find all neighbors within radius, i.e. not farther away
> than
> > >> radius to a given coordinate).
> > >>
> > >> Markus M
> > >> _______________________________________________
> > >> grass-dev mailing list
> > >> grass-dev at lists.osgeo.org <mailto:grass-dev at lists.osgeo.org>
> > >> http://lists.osgeo.org/mailman/listinfo/grass-dev
> > >>
> > >
> > >
> > >
> > > --
> > > Dr. Benjamin Ducke
> > > {*} Geospatial Consultant
> > > {*} GIS Developer
> > >
> > > Spatial technology for the masses, not the classes:
> > > experience free and open source GIS at http://gvsigce.org
> > > _______________________________________________
> > > grass-dev mailing list
> > > grass-dev at lists.osgeo.org <mailto:grass-dev at lists.osgeo.org>
> > > http://lists.osgeo.org/mailman/listinfo/grass-dev
> > _______________________________________________
> > grass-dev mailing list
> > grass-dev at lists.osgeo.org <mailto:grass-dev at lists.osgeo.org>
> > http://lists.osgeo.org/mailman/listinfo/grass-dev
> >
> >
>
>
>
> --
> Dr. Benjamin Ducke
> {*} Geospatial Consultant
> {*} GIS Developer
>
> Spatial technology for the masses, not the classes:
> experience free and open source GIS at http://gvsigce.org
> _______________________________________________
> grass-dev mailing list
> grass-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/grass-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/grass-dev/attachments/20150107/f95ae7ac/attachment-0001.html>
More information about the grass-dev
mailing list