🚀 go-pugleaf

In article <5d8r08$e8o@vixen.cso.uiuc.edu>,
Residential Student Computing User  <rscuser@housing.uiuc.edu> wrote:
: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)
 
Yes, it does help to know something about your cost function.  However,
even the above info can be deceptive.  For example, the graph you give
could well generically describe the ASA_TEST function that comes with
the ASA code, but this is a function that it extremely hard
(impossible?) to fit with non-sampling techniques.  I doubt whether the
description of a physical system as yours is equivalent to this
function, but I agree that this graph is a "warning" to be careful.
 
This graph does fit the description of the kinds of systems that might
benefit from the approach I mentioned:
} This depends on how much you know about your system.  For example,
} if you have some good idea of the relative values of hills and
} valleys, then you could do a first optimization pass using a coarse
} resolution ("coarse" specific to your problem), and then follow up
} with finer global or possibly even quasi-local optimization.  I
} have done this in several systems, including EEG analyses,
 
: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.
 
I think (2)-(5) are cost-function specific, and that the job is to code
this properly, somewhat an orthogonal project to optimization per se.
 
Re (6), Yes, in these systems, I would think that you require a
sampling algorithm.
 
:> 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.
 
Agreed!
 
:> :- 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.
 
My point is that this info will likely help you only _after_ you
complete at least one full optimization of such a system.  Then, it
likely will make sense to at least try tuning other similar systems
similarly.
 
:...
 
:CHEATS TO AVOID GLOBAL SEARCHES i.e. initial pose problem
:---------------------------------------------------------
 
This of course is a very good idea -- to explore more efficient
algorithms that might be better suited to your system.
 
:1) NOT a real solution. Constrain your image orientation with
:   e.g. head holders. Also use axial images only, etc.
 
Will this work well across a large set of subjects?
 
: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)
 
I think such transformations run into trouble very quickly when dealing
with nonlinear and/or noisy systems, especially in systems where the
noise itself has nonlinear structure (likely true in brain imaging
data).
 
:...
 
:> 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.
 
Good luck, really.  If it's any consolation, if you do a great job in
this project, I'm sure you will have many great offers for postgraduate
positions.
 
Lester

-- 
/*             RESEARCH                            ingber@ingber.com *
 *       INGBER                                 ftp://ftp.ingber.com *
 * LESTER                                     http://www.ingber.com/ *
 * Prof. Lester Ingber __ PO Box 857 __ McLean, VA 22101-0857 __ USA */