|
|
|
|
|
|
|
|
|
|
| Re: checking for connectedness of a given set of pixels [message #73430 is a reply to message #73311] |
Mon, 08 November 2010 11:22   |
![James[2] is currently offline](theme/default/images/xoffline.png.pagespeed.ic.XRkd1fkXye.png "James[2] is currently offline")
James[2]
Messages: 44
Registered: November 2009
|
Member |
|
|
LABEL_REGION's speed relies on a fast implementation of the union and
find operations on disjoint set data structures (http://
en.wikipedia.org/wiki/Disjoint-set_data_structure). I'm guessing that
the IDL programmers have implemented this in C for LABEL_REGION,
probably with a higher speed than you'd be able to get with anything
written in IDL. If they did it "right" (with path compression) then
it's an optimally fast algorithm for this problem (see Wikipedia
article).
One problem is that LABEL_REGION runs over a whole array even if it is
mostly empty (sparse). This is why LABEL_REGION might be slow for
your task - it could be doing a lot of unnecessary extra work. Since
your data is already in 2D coordinates, I'd take the max/min values
and use a tightly-fitted array. Supposing your coordinates are in a 2-
by-N array POINTS:
function ISCONNECTED(points, _extra=ex)
mins = min(points, dimension=2, max=maxs)
shift = mins # replicate(1, n_elements(points)/2)
arr = bytarr(maxs-mins+1)
arr[points - shift] = 1
return, max(label_region(arr, _extra=ex)) le 1
end
the _extra keywords allow you to pass ALL_NEIGHBORS along to choose
between 4- and 8-connectivity. Of course, this function adds a lot of
extra baggage, so it's only going to be faster if your regions are
significantly smaller than the whole array.
|
|
|
|
| Re: checking for connectedness of a given set of pixels [message #73514 is a reply to message #73430] |
Sun, 14 November 2010 13:56 |
guillermo.castilla.ca
Messages: 27
Registered: September 2008
|
Junior Member |
|
|
On Nov 8, 3:22 pm, James <donje...@gmail.com> wrote:
> One problem is that LABEL_REGION runs over a whole array even if it is
> mostly empty (sparse). This is why LABEL_REGION might be slow for
> your task - it could be doing a lot of unnecessary extra work.
Thanks a lot James, very insightful comments, and very nice piece of
code :). After giving it some more thought, I found out that there is
an IDL function called REGI0N_GROW that may be faster than
LABEL_REGION for this purpose when the minimum bounding box for the
input set of pixels is large. I have modified your function to include
the former as an alternative method (below). I'll do some tests and
report back (hopefully within this year :).
function ISCONNECTED, points, method=method, _extra=ex
mins = min(points, max=maxs, dimension=2)-1
dims=maxs-mins+3
npts= n_elements(points)/2
indices= points - mins # replicate(1, npts)
indices= indices[0,*] + dims[0]*indices[1,*]
arr = bytarr(dims)
arr[indices] = 1B
if ~keyword_set(method) then $
return, max(label_region(arr, _extra=ex)) le 1 $
else return, n_elements(region_grow( $
arr, indices[0], thresh=[1B,1B], _extra=ex)) eq npts
end
|
|
|
|
| Re: checking for connectedness of a given set of pixels [message #74182 is a reply to message #73514] |
Mon, 03 January 2011 13:50 |
guillermo.castilla.ca
Messages: 27
Registered: September 2008
|
Junior Member |
|
|
On Nov 14 2010, 5:56 pm, Guillermo
<guillermo.castilla.castell...@gmail.com> wrote:
> ...REGI0N_GROW that may be faster than
> LABEL_REGION for this purpose when the minimum bounding box for the
> input set of pixels is large. I have modified your function to include
> the former as an alternative method (below). I'll do some tests and
> report back (hopefully within this year :).
Just for the record, today I made a test with a 50 megapixel labeled
image derived from the rasterization of a polygon vector layer
containing 185 elongated features (rivers), of which 65 ended up
consisting of disconnected groups of pixels. Checking for
connectedness of the pixels within each feature took almost 3 times
more using the REGI0N_GROW method than using LABEL_REGION (the latter
taking in average 30 millisecs per feature). I quickly looked into the
REGI0N_GROW code and noticed that it is based on LABEL_REGION itself,
so no wonder. Repeated the test with SEARCH2D instead of REGI0N_GROW
and although it was two times faster than the latter, it was still
slower than LABEL_REGION. So it looks like LABEL_REGION, even if it
does a lot of unnecessary extra work for this task, is the method of
choice for checking for connectedness of a set of pixels.
Happy new year!
Guillermo
|
|
|
|
comp.lang.idl-pvwave archive
Members
Search
Help
Login
Home
