Friday, April 11, 2008

[MP 1] Version "MultiLevel6"

Collective Relaxation

  • In each relaxation step, all nodes are now moving SIMULTANEOUSLY along there negative gradient vectors.
  • The step width of each node is proportional to the magnitude of its gradient, i.e. nodes move different amounts.
  • In my experience, this strategy avoids problems connected with the wrong order of successive node movements.
  • The numerical effort of the collective optimization is the same as with successive optimization.

Naive Optimization Strategy

  • The global gradient ( = derivatives of the mismatch potential with respect to all node coordinates) is computed.
  • All nodes move simultaneously a small step.
  • The global gradient is computed again and so on.
  • Normally, line search is done in a different way: First walk in one direction until no more improvement is possible, and only then choose a new direction.
  • For some reason, the naive approach seems to work better. Don't really understand why.

New Graphics Function

  • The original intensity distribution is plotted in red.
  • The momentary fit is plotted in blue.
  • The goal intensity distribution is plotted in green.
  • All colors are plotted on top of each other, with slightly different pixel sizes.
  • So, in the end, the blue fit should coincede with the green goal.
  • Graphics windows can be advanced by clicking with the mouse somewhere inside.

Performance of Multilevel-Version-6

  • Amazingly, many test problems created with GenerateRndImages() or GenerateFullRndImages() (see [7]) are solved nicely, without any elastic forces.
  • However, the amount by which the mismatch potential can be relaxed, depends on the individual case.
  • Here, also the exact setting of the step width in the relaxation routine has an influence.
  • The real cell images with LoadRealImages() are not working at all (- so far..) .
  • Elastic forces don't seem to improve the results.

Elastic Forces

  • Are implemented.
  • Pure elastic relaxation on single grid level has been tested.
  • Combination of mismatch and elastic forces don't really seem to work well yet.

Random Test Images

  • GenerateRndImages(128,100,0.0,1.5) : Generates an orig and goal picture with resolution 128x128 pixels. Pixels are dark by default, but 100 random pixels have a finite random brightness. In the goal image, those pixels (more precisely: the underlying nodes) are shifted into a random direction by a random amount between 0.0 and 1.5 pixel sizes.

  • GenerateFullRndImages(32,0.0,1.5): Similar to above, but here ALL 32x32 pixels will have some random brightnesses.

  • To generate a new random case, change the integer variable SIT in DefParameters().

Idea: Separate Registration and Traction Computation

  • If the mismatch potential can really be relaxed without any elastic forces, this would be numerically effecient for images with many dark pixels.

  • Then, after we know where each bright node has moved to, the elastic problem and force calculation could be done as a second step.

Simplified Point Spread Function

  • Since the new minimization strategy does not need second derivatives, it was possible to go back to the lower-order, triangle-like PSF, leading to a second order B-function.

  • COI based Coarsification and Refinement

  • Lolo's idea is used, i.e. in the coarsification step each low-level supernode is placed at the center of intensity (COI) of its associated high-level component nodes.
  • In the refinement step, the group of component nodes is shifted, as a whole, by the same amount their supernode has been shifted in the grid below.

  • Coarsification, low-level relaxation and refinement together now comprise a true correction: Low-level and high-level information are combined.

  • It is ensured by the COI method that mere rigid shifts between the orig and goal images are treated exactly.

  • With the COI method, low-level grids are not uniform any longer. Thus, elastic springs have different rest lengths.

  • It is not clear yet how to implement a given Poisson ratio (requiring different spring constants for vertical/horizontal and diagonal springs) on such a non-uniform grid.

Beyond Powers of 2

  • Ben had the idea to use more flexible schemes for the multigrid method coarsification, so that the linear picture sizes doent need to be powers of two each time.

  • For example, one could also use 3x3 groupings instead of 2x2.

  • Or, one could be satisfied with a lowest grid resolution of, say, 5x5, instead of 1x1, but still use the normal 2x2 refinement.

No comments:

Post a Comment