[Insight-users] Region growing on a mesh

[David Doria]

I am trying write some classes to allow region growing on a mesh - that is,
specify a seed node, then, based on some criteria, find which nodes in the
mesh are "connected" to the seed. A simple example is to find all nodes that
can be reached by traveling less than a distance threshold from a neighbor
already in the region. Here is an example:

If '0' represents a node and '.' represents a unit of distance, if the seed
on this simple mesh was the left most '0', and the distance threshold was
set to 5, the five nodes on the left would be "connected" and the node on
the far right would not be connected to that group:

      0..0
      .
      .
      .
0...0...0.....................0

I have a few questions as I get started:

1) itkMesh vs itkQuadEdgeMesh
Should this be based on itkMesh or itkQuadEdgeMesh? itkQuadEdgeMesh seems to
have better functions for traversal - however it is not currently part of
ITK. (if my code is useful and QEMesh doesn't end up getting added to ITK,
then my code becomes not as easily usable for people - how is this typically
handled?)

2) Ways to store the result:
a) An in-place filter where somehow a boolean is attached to each node (this
could be very difficult as the user could have overridden DefaultMeshTraits
to store other data in the nodes already...)
b) Return a separate sub-mesh. The problem with this is that the user would
have a hard time iterating over the original mesh and asking "is this node
part of the segmented region?"
c) Return a separate sub-mesh as well as a boolean version of the original
mesh. That is - create a new mesh the same size and with the same
coordinates as the input mesh, but store as PointData a boolean that
indicates whether each node belongs to the region that was grown. I was
leaning toward this method.

3) How to iterate over the mesh?
I was going to do something like this:
- Create a queue of NodeIds that are part of the region (initialized to be
the seed node).
- Check all of the seed node's neighbors and see if the pass the "connected
criteria" test
- Add each node that passes the test to a list of nodes that belong to the
region. Add the node to the process queue if it is not already on the list
of nodes that belong to the region
- do until the queue is empty

Does that sound reasonable?

4) There would not need to be such a complex class hierarchy as with region
growing on an itkImage. The only thing that would need to be provided is a
class that has a Compare() function that takes two nodes that are known to
be connected.

Does anyone have any comments on any of these issues?

Thanks,

David
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.itk.org/pipermail/insight-users/attachments/20090902/a6e652f2/attachment.htm>