[Insight-users] region growing from local maxima

[Ara.T.Howard]

sorry - i replied with the attachment and was bounced - here's one sans
attachment:

---------- Forwarded message ----------
Date: Tue, 4 Oct 2005 21:14:16 -0600 (MDT)
From: Ara.T.Howard <Ara.T.Howard at noaa.gov>
To: Richard.Beare at ieee.org
Cc: Insight-users at itk.org
Subject: Re: [Insight-users] region growing from local maxima

On Wed, 5 Oct 2005, Richard Beare wrote:

> Hi,
> 
> I think you'll find that the necessary tools are currently missing.  The
> closest thing I've heard mentioned (in the InsightJournal, I think), is a
> local maximum filter, which finds pixels that are larger than all of their
> neighbors. This might help you get started, but isn't what you really want
> (which is regional maxima (sets of pixels surrounded by pixels of lower
> values).

right.  the vigra toolkit i'm using finds regional maxima - but the
implementation seems flawed (i think):  it starts by labeling strongly
connected components using an equality functor so, if you were using something
simple like dn's within 10, you might get

   label 1               label 2

         42                41
     30     29          30    29
              22                 22
   20            12                12

this is problem one - i don't think 'label 1' is strongly connected in the
sense that for every v,u in S v and u are strongly connected.  it's more of an
eight-neighbor strongly connected kind of thing...

anyhow, the algorithm then iterates labels, assuming all are maxima, if a
pixel is found that has a neighbor from a different label and that pixel is
brighter that the current pixel the current group is marked as NOT being a
maxima.  this is also flawed since the strongly connected components, when
using an equality functor, may easily have this sort of relationship... anyhow
i'm babbling - just frustrated that i'm having such a tough time doing
something which is logically so simple.

> The itk watershed implementation will find the extrema as part of the
> processing, but I don't think they are available externally.

right.  gradient magnitudes are used i think?

> I'm one of what I'm sure is a number of people who are very interested by
> itk, but frustrated that it is missing many of the tools that we're used to,
> so I think you can be sure that the filters you are interested in will be
> along fairly soon.

that would be great - but i don't want to complain - the developers sure have
ton a massive amount of work thus far!

> Your problem looks like a classical blob finding one - very similar to lots
> of problems in a variety of fields. It also appears that you have the luxury
> of a very flat and well defined background as well as flat peaks in the
> lighting. This is a situation that is well tackled using marker based
> watershed approaches (available in matlab with some fiddling).

actually there is 'no' background - the image i posted has had it removed.
any, and __every__ speckle, in the image is a very small city and must not,
under any circumstances, be removed from the final output.  this makes quite a
bit trickier for sure...

> The procedure could be
> 
> find regional maxima (and optionally discard dark ones).  threshold to find
> background

i know background to be 0.  so this is easy - except that the toolkit i'm
currently using has a bug here...

> OR the results together and use a markers for a watershed. The control
> surface of the watershed should be a gradient - the watershed lines will end
> up at the peak of the gradients, which may or may not be what you want. We
> can fill in more details on that later.

you lost me - which results?  at this point we only have regional maxima no?

> If selecting the background threshold is a problem then you might
> think about using 2 stages of watershed. The first stage is on the raw
> image (possibly inverted) and serves to tesselate the image into
> neighborhoods with each neighborhood containing a regional maxima. You
> then use the watershed lines as a marker for the background and
> combine them with the regional maxima and carry out the watershed on
> the image gradient.
> 
> Anyway, an example of the first method is attached - regional max are
> in green, borders of the watershed regions are in red. This wasn't
> generated with itk, but hopefully it will help.

that's really interesting.  the red (watershed) lines along the max gradient
is pretty close to describing the outside of what i'd like to keep.  so,
basically anything that's green only, on green inside a red watershed line is
the desired output.  i noticed there are some watershed lines that contain
minima rather that maxima - obviously don't want these.

working with gradiant magnitudes might be a good place to start - it actually
is meaningful with out data because it at the point where dns drop drastically
that we start to be looking at 'over-glow' and/or geolocation errors : the
image i'm showing you is an average over a year so there is considerable
wobble in the pixel locations.

thanks for the fast response btw!  it seems like itk might be useful if i went
for a gradient magnitude seeded region growing approach eh?  if not can you
reccomend other good computer vision toolkits?  i'm looking at itk, vigra, and
ltilib.  whatever i use has to be idiot proof - i'm a real-time systems
developer not a computer vision specialist.

regards.

-a
-- 
===============================================================================
| email :: ara [dot] t [dot] howard [at] noaa [dot] gov
| phone :: 303.497.6469
| Your life dwells amoung the causes of death
| Like a lamp standing in a strong breeze.  --Nagarjuna
===============================================================================