[MINC-development] beta mincmorph

[Andrew Janke]

On Tue, 3 Dec 2002, Steve ROBBINS wrote:

> > If you look at the code of the Group option (Connected component labelling
> > -- in kernel_ops.c) you'll note I haven't used the classical approach to
> > resolving equivalences. (Building an array of equivalences as you go with
> > redundacies).  Instead I've used an approach that I can't find anywhere
> > else...  but I'm sure has been described before.  The reason for using it is
> > that i can guarantee memory usage will only grow to a finite size this way,
> > something I can't ensure with the classical version especially in 256^3
> > volumes.
>
> I'm not familiar with this stuff, so please forgive a naive question.
> The problem you're solving is the one described here:
>     http://www.dai.ed.ac.uk/HIPR2/label.htm

<tick>  albeit with an arbitrary "connection kernel" or structuring element.
Thus allowing us to do 2d/3d 8-connected/4-connected CCL'ing.

The std thing to do (in 2d) is either 4 or 8 connectivity, mincmorph is written
in such a way with arbitrary kernels such that (i think) one cannot be sure that
already visited neighbouring voxels will have only 2 different values.  (real
ugly to think about i know)

ie:  std 2D connectivity kernels where 0 is the current voxel:
 (use fixed width font M$laves!)

   4 connectivity      8 connectivity

        X                  XXX
       X0X                 X0X
        X                  XXX

To think of an "abberant case" try this structuring element on for size... ;)

   "wierd connectivity"

      X   X
       X X
        0
       X X
      X   X

In this case I think you can get the case whereby there are more than 2 distinct
neighbour values...

> If so, why wouldn't you use parent pointer trees?  They are trivial to
> implement, will use storage linear in the # of voxels.  With union-by-rank and
> path compression, the running time is basically linear too.

As in: http://home.swbell.net/mck9/cobol/tech/tree.html?

I can't quite see how the storage would be linear and how redundant connections
would be resolved?  or can each node have more than 2 kiddies?

At then end I assume this tree would be then traversed (depth first) and the top
value assigned to each value in the tree?

I think i am sort of doing this in my current implementation although doing it
all in a single 1D array! :)


a