shapeworks-dev-support

Text archives Help


Re: [shapeworks-dev-support] iterations per split vs optimize iteration


Chronological Thread 
  • From: Allen Sanderson <allen@sci.utah.edu>
  • To: shapeworks-dev-support@sci.utah.edu, Shireen Elhabian <shireen@sci.utah.edu>
  • Cc: Oleks Korshak <oleks.korshak@gmail.com>
  • Subject: Re: [shapeworks-dev-support] iterations per split vs optimize iteration
  • Date: Tue, 30 Jun 2020 14:51:30 -0600
  • Ironport-sdr: QylR55d2+bxE9WyhLLfFaYaEDUMHK5hO2DUS8n2c13a2T+8EL45DLfKBmNjlUY2tbVO2lK02Dx V21Asw121x9bLd1rkAzqcyGYgfkFSt08eFcaCNqkfa0a7C+cT3uCuWeYN0cdYJ/uF/UTIrfMWZ RAudHH9diVKaHfsHGtx2wUEmsVjn5B9iDgrDWQxqgax4DkkFSJi16aF1qFVDEwBE5e7hznXVYU Zo6CquIGWcLWxTrMTZfgu+/FhHAr7n+Z09rSt+5ZX6tJvxtAr8wohGBZ6K0g6XUVbBlkwOf1L6 Obc=


Hi Shireen,

Thanks, I think I finally have a grasp on things. I see two issues for me, overloaded terms and a disconnect between theory, documentation, and the code/GUI

The relative weighting is a weight used to scale/weight the H(Z) term (correspondence or inter-surface term) in the objective. 
BTW, there is only one weight. It is just set differently based on the stage, i.e., initialization vs optimization.


So the formulation is really the following:

Q =  weight H(Z) - sum( H(X) )

In the book chapter you sent me, equation 10.33 has a weight on the other term. And noted that 1 is a good default.

The differences between “initialization” and “optimization” stages/steps are 

(1) how important the correspondence (inter-surface) objective is compared to the surface sampling (intra-surface) term using the relative weighting (hence initial relative weighting is the weight used in initialization and the relative weighing is the weight used for optimization).

I think the part that is missing is clearly noting when which value for the weight is used. Plus only having one value exposed in SW Studio, when in reality there are two. 

(2) how the notion of correspondence (inter-surface) is quantified. In initialization, especially when we don’t have enough particles to describe the geometry of each surface, we use a mean energy (i.e., pushing all shapes in the shape space to the mean shape or in other words, the covariance matrix is assumed to be identity). In optimization, we use the entropy of the shapes distribution (assumed to be gaussian distributed) which is quantified based on the covariance matrix. In the multi-scale setting, we have the option to use shape statistics at later scales where we have more particles that can reveal the covariance structure.

That make some sense to me. 


Intra-surface optimization (point seeding): 
 2 particles   1000 iterations   Inter-surface weight 0.05
 4 particles   1000 iterations   Inter-surface weight 0.15
 8 particles   1000 iterations   Inter-surface weight 0.26
16 particles   1000 iterations   Inter-surface weight 0.36
32 particles   1000 iterations   Inter-surface weight 0.47
64 particles   1000 iterations   Inter-surface weight 0.57
128 particles 1000 iterations   Inter-surface weight 0.68 
256 particles 1000 iterations   Inter-surface weight 0.78
512 particles 1000 iterations   Inter-surface weight 0.89

512 particles 1000 iterations   Inter-surface weight 1.00

How did you get/compute those weights?


Because the documentation says Starting relative weighting, that implies it changes. As such, my thinking was that the initial relative weighting gradually increased to relative weighting. The documentation says the initial value is 0.05 and in SW and the documentation the default is 1. So I just interpolated. 

But what you are saying that is not the case. That during the initialization the initial relative weighting value is used through out. But then for the full optimization the relative weighting value is used. Does it make any sense to gradually increase it in light of (2) above ? it probably does not give an even distribution but if it did then the final optimization step should converge faster.


To give an example of my confusion:


Grammatical issues aside here is the current description of the optimization is the following:

The optimization is consists [o]f two part[s]: the initialization of correspondence and [the] optimization.

The initialization of the particles is in itself an optimization and defining the optimization as an optimization is not really optimal (pun intended - sorry).

Really it is an optimization of the configuration space (intra-surface) and the shape space (inter-surface) and is done as series of steps.

Here my attempt to explain the process, please correct me.

As it is not feasible to do the optimization of the configuration space (intra-surface) and the shape space (inter-surface) with a full set of correspondence points in one step, the optimization is performed as a multi-step process where points are added at each step until the desired number of points is reached. For these steps the optimization of the configuration space (intra-surface) and the shape space (inter-surface)  is weighted (default = 0.05) to the configuration space (intra-surface) which gives an evenly* spaced distribution of points across each surface. These steps are collectively called the initialization steps.

* Sidebar - In the documentation the word uniform is used, that is incorrect as uniform implies regularization.

Once the desired number of correspondence  points is reached one additional step is taken. For this step the optimization of the configuration space (intra-surface) and the shape space (inter-surface) are weighted equally (default) to both. This step is called the final step or full optimization.

For both the initialization steps and the finial step the weighting to the shape space may be set by the user. Further, as each step of the optimization is an iterative process and the number of iterations may be set by the user.

For example a Single Scale Optimization would be ….

 2 particles   500 iterations   Inter-surface weight 0.05
 4 particles   500 iterations   Inter-surface weight 0.05
 8 particles   500 iterations   Inter-surface weight 0.05
16 particles   500 iterations   Inter-surface weight 0.05
32 particles   500 iterations   Inter-surface weight 0.05
64 particles   500 iterations   Inter-surface weight 0.05
128 particles 500 iterations   Inter-surface weight 0.05
256 particles 500 iterations   Inter-surface weight 0.05
512 particles 500 iterations   Inter-surface weight 0.05

512 particles 1000 iterations   Inter-surface weight 1.00



It is also possible to do a Multi-Scale Optimization where the full optimization step is performed after each initialization step.

 2 particles   500 iterations   Inter-surface weight 0.05
 2 particles 1000 iterations   Inter-surface weight 1.00
 4 particles   500 iterations   Inter-surface weight 0.05
 4 particles 1000 iterations   Inter-surface weight 1.00
 8 particles   500 iterations   Inter-surface weight 0.05
 8 particles 1000 iterations   Inter-surface weight 1.00
16 particles   500 iterations   Inter-surface weight 0.05
16 particles 1000 iterations   Inter-surface weight 1.00
32 particles   500 iterations   Inter-surface weight 0.05
32 particles 1000 iterations   Inter-surface weight 1.00
64 particles   500 iterations   Inter-surface weight 0.05
64 particles 1000 iterations   Inter-surface weight 1.00
128 particles 500 iterations   Inter-surface weight 0.05
128 particles 1000 iterations   Inter-surface weight 1.00
256 particles 500 iterations   Inter-surface weight 0.05
256 particles 1000 iterations   Inter-surface weight 1.00
512 particles 500 iterations   Inter-surface weight 0.05
512 particles 1000 iterations   Inter-surface weight 1.00

There are still a few additional minor points but I think this gives the general idea.

Cheers,

Allen


Allen Sanderson
SCI Institute
University of Utah











thanks and best regards
Shireen


------------------------------------------
Shireen Elhabian, M.Sc., Ph.D.
Research Assistant Professor
School of Computing
Scientific Computing and Imaging Institute
University of Utah
WEB 2815
72 Central Campus Drive, Salt Lake City, UT, 84112
Phone (801) 587-3206
Fax (801) 585-6513
Home Page: http://www.sci.utah.edu/~shireen

On Jun 29, 2020, at 4:28 PM, Allen Sanderson <allen@sci.utah.edu> wrote:

Hi Shireen,

Oleks and I had a very productive call today. He helped fill in a few blanks for me. Regarding my confusion over the iterations per split (initialization) vs optimize iterations (optimization) setting. The energy being reported is the following:



But what was not clear is that there are weights assigned to each value that depends on whether one is doing the initialization or optimization. Oleks noted that when one is doing the initialization the weights are 1 and .1, whereas when doing the optimization the weights are 1 and 10 respectively. Given one specifies the iterations separately it initially seemed that there were no weights (e.g. 1/0 and 0/1) and each were separate. Once I understood that was not the case then the single-stage and multi-stage also made sense.

Because the terms optimization, configuration, and correspondence are overloaded to help myself in our discussion I used the terms, intra-surface and inter-surface. The points (particles) are considered correspondence positions but there is a correspondence configuration. Both of which have separate optimization steps depending on the weightings. It might be clearer to discuss the optimization in terms of the following:

The optimization is based on optimizing the correspondence position in configuration space (intra-surface optimization), while simultaneously optimizing the correspondence configuration (inter-surface optimization).

The GUI could be the following:

Iterations for 
 Intra-surface optimization (point seeding)
 Inter-surface optimization (point correspondence)


The output would look like:

Intra-surface optimization (point seeding): 

64 particles   1000 iterations 
128 particles 1000 iterations
256 particles 1000 iterations
512 particles 1000 iterations 

Inter-surface optimization  (point correspondence) :
1000 iterations

It would also be good to have something better in the GUI on the relative weightings 

  • relative_weighting: (default: 1) Relative weight between the sampling and correspondence terms of the objective function
  • initial_relative_weighting: (default: 0.05) Starting relative weighting to make sure that initially the surfaces are covered uniformly (usually in order of ~0.1 or 0.01)
Only the relative is in the gui and neither makes sense in terms what Oleks explained to me. Does that mean for the optimization the weights would be:

Intra-surface optimization (point seeding): 
 2 particles   1000 iterations   Inter-surface weight 0.05
 4 particles   1000 iterations   Inter-surface weight 0.15
 8 particles   1000 iterations   Inter-surface weight 0.26
16 particles   1000 iterations   Inter-surface weight 0.36
32 particles   1000 iterations   Inter-surface weight 0.47
64 particles   1000 iterations   Inter-surface weight 0.57
128 particles 1000 iterations   Inter-surface weight 0.68 
256 particles 1000 iterations   Inter-surface weight 0.78
512 particles 1000 iterations   Inter-surface weight 0.89

Inter-surface optimization  (point correspondence) :
1000 iterations    Inter-surface weight 1

The Intra-surface weight is always 1.0

On one level that makes sense for the single stage, but not sure for the multi-stage. Happy to discuss more in a zoom chat.

Cheers,

Allen


On Jun 23, 2020, at 4:50 PM, Allen Sanderson <allen@sci.utah.edu> wrote:
  • In ShapeWorks there are iterations for the splitting then the iterations for the optimization. It is not clear to be in the context of the output. It would indicate that the particles are split independently of the correspondence then the last step “optimize” for the correspondence. But It says the splitting process, followed by optimization, is then repeated until a specific number of particles
    have been produced. That makes sense. So I am confused as to what I see for 512 particles in the in ShapeWorks output:

    64 particles 1000 iterations 
    128 particles 1000 iterations
    256 particles 1000 iterations
    512 particles 1000 iterations
     
    optimize  1000 iterations

I would have expected:
 
64 particles 1000 iterations - optimize  1000 iterations
128 particles 1000 iterations - optimize  1000 iterations
256 particles 1000 iterations - optimize  1000 iterations
512 particles 1000 iterations - optimize  1000 iterations

On Jun 24, 2020, at 10:32 AM, Shireen Elhabian <shireen@sci.utah.edu> wrote:

Currently, the initialization iterations are only run after splitting and optimization is run at the end. What you expect make sense and this is what we call multi-scale. In the python use cases, we have a multi-scale settings that does a similar flow. Alan is working on integrating this into the c++ Optimize library.








Archive powered by MHonArc 2.6.18.

Top of page