🚀 go-pugleaf

Thanks a lot for your reply:

Lester Ingber wrote:
> :  I know many people will say it depends on the MATCH function, but I
> :  would like to find out the central elements that make this TYPE of
> :  optimization efficient and robust.
> 
> Yes, that is what most people will, and _should_ say.

The reason I mentioned that it is coregistration of medical images
is because there are a few "special" characteristics of registering
these images that separate them from any generic nonlinear
optimization. (In fact, the reason for the initial posting is that
these characteristics are so particular to image registration that
most existing optimization strategies are not addressing them
directly.)

Even if I don't know what the MATCH function is, I know (just from
having looked at many similar functions) that
 
1) it is likely to have a parabolic or V-shape landscape around the
   best-match position. However, the width of the shape may be quite
   narrow for some function. (So it's like trying to putt a golf ball
   into a steep but narrow hole on the green.)

             DIFF function (or -1 * MATCH function)
           \         |        /
            \        |       /
             \_      |     _/
               \_    |   _/
                 \_  | _/
                   \_|/ 
   __________________|___________________ Transformation 
                     0                   (i.e. translation or
                                               rotation away from
                                               global extremum)

2) local extrema often creep up at 90 deg, (especially) 180 deg,
   and 270 deg.

(NOTE: How the MATCH function changes at different translation
       and rotation will be referred to as the parameter landscape)

3) Rotation only has the effect of rotating the parameter landscape
   for translation.

4) Translation completely skews the parameter landscape of rotation
   because it changes the center of rotation.

5) 360 deg = 0 deg, so the parameter landscape of rotation is periodic.

6) Especially in pathological case, the parameter landscape is VERY
   noisy, so gradient-following methods require a lot of hacks to
   avoid being trapped at local extrema.

It is ESPECIALLY points 1, 3, 4 and 5 that warrent special attention
into this problem... that it is different from generic nonlinear
optimization. Perhaps, we have take advantage of these properties
for more efficient searches.

> Add noise to the data, and the problems really multiply.  I have
> seen projects trying to optimize brain/head-shapes from MRI data,
> with "standard" deterministic algorithms, fail to get the optimal
> point 50% of the time.  Is this OK for your project?

No, a program with 50% success rate should not even be called
fully automated since half the time, you need an operator to check
the results.

> :- ITERATIVE STEPS FOR ROTATION VERSUS TRANSLATION. When optimizing
> :  orientation in 6 degrees of freedom, one inevitably asks the question,
> :  should I rotate by X degrees or should I translate by Y mm when both
> :  transformation will lead to a better match (i.e. higher value for the
> :  MATCH function). THE QUESTION IS: what is the *functional* equivalence
> :  between rotation and translation? i.e. If both the rotation and the
> :  translation will improve the match by the SAME amount, which is the
> :  better transformation to do? IS IT POSSIBLE TO DECIDE???
> 
> I cannot see how this cannot depend on the "landscape" of the cost function?
> 

Of course, it depends on the "landscape" of the cost function, but
as I mentioned, we are not completely tackling a black-box problem.
We know the typical dimensions of medical images and of the structures
in them, we have ideas about what the landscape looks like
approximately.

> :- INITIAL ESTIMATES are often required to 1) reduce computing time
> :  for optimization, 2) avoid local extrema. I have reported a fully
> :  automated algorithm for determining brain orientation in 3D SPECT
> :  without any initial estimates (J Nucl Med 37(5): 8P. 1996). However,
> :  this algorithm is based on a priori knowledge (i.e. the rules programmed
> :  by me) about the well conserved, overall geometry of the brain.
> :  THE QUESTION IS: has anyone developed any generic algorithms for
> :  resolving the initial pose (i.e. the approximate match between two
> :  images.) Alternately, has anyone developed any algorithms fast enough
> :  that it can be used to test ALL orientations?
> 
> This is a reasonable question that might be answered in the usenet
> groups you have posted.  Has anyone solved/optimized at least parts
> of your particular problem already?

CHEATS TO AVOID GLOBAL SEARCHES i.e. initial pose problem
---------------------------------------------------------
1) NOT a real solution. Constrain your image orientation with
   e.g. head holders. Also use axial images only, etc.
2) Use centroid-based and principal axis transformation (i.e. higher-
   moment-based method to establish rough image orientation).
   PROBLEM: centroid-based method works only for estimating
            translation. Principal axis transformation works (NOT
            REALLY, see later) if the two shapes to be coregistered
            are similar. (e.g. Nat Alpert's work on brain registration)
            Then, one can coregister 2 shapes by overlaping their
            principal axes. ADVANTAGE: Fast because of one-pass
            calculation. DISADVANTAGE: The principal axes have
            no directionality. i.e. Pointing to North is the same
            as pointing to South. Thus, this goes back to the first
            "solution". If you can constrain your image orientation
            by using a head-holder for example. Then, you'd know
            left is left, right is right, etc.

> Another slant on selecting surface versus volume optimization deals
> with the parameterization of the problem.  If you actually are
> trying to fit an m-dim surface, m < n, but are using an n dim volume
> of data + adding constraints for the other n-m dims, then you should
> try to explicity/numerically solve for the m-dim surface in your
> cost function, so you wind up fitting only m parameters.  In the
> context of a sampling technique, it is an extreme waste of sampling
> to have to sample additional dimensions; most often it is a good
> tradeoff to add som nonlinearlity by working with the m dim space.

I'm not slanting surface registration in spirit because that's what
I'm using currently. What I am slanting is the use of just the
outer surface for matching. I think some kind of point reduction
is needed, but using the hat-and-head is a little too simplistic.

> It seems your main concern is CPU time for optimization?  If so,
> the labor of programming is a relatively small concern.  If not,
> then there are administrative decisions to be made similar to those
> mentioned above.

Yip. The labor of programming is a relatively small concern. I'm
a graduate student, so yeah. I'm kinda like a slave.

> And we look forward to your ***long*** summary of replies :>).

Not as long as you might expect, but hopefully will generate some
interesting discussions.


Cordially,

Jeff
----------------------------------------------------------
Jeffrey Tsao
Biomedical Magnetic Resonance Laboratory
University of Illinois at Urbana-Champaign