Next: Creating the Initial Regions Up: Theory Previous: Cost Function Formulation

## The Region Merging Algorithm

An alternative solution to the problem is to treat it as a set of potentially inconsistent constraints:

 (7)

The problem is then one of finding the set of consistent constraints which lead to a low (ideally minimal) cost.

Let .

Consider the difference in cost between and . The cost difference is:

 (8)

Since, by definition of rounding, , then for both cases, confirming that is (locally) the best solution.

The smallest cost difference is:

 (9)

Choose the interface where this cost difference is the largest. That is, choose the pair of regions where getting the offset wrong'' is the most disastrous.

Therefore, select the pair of regions according to:

 (10)

Once this pair is selected, merge them into a new, single region using the optimal'' offset . Update the statistics for all interfaces to this new region. That is, for all regions , the new statistics are:

 (11) (12)

From these, calculate , and then and then repeat the selection process to choose a new pair of regions to merge.

Keep merging regions until there are no more interfaces between regions (usually when only one region remains if there is a single connected set of regions initially).

As each iteration of this algorithm merges two regions, the number of iterations required is . Within each iteration a search for the maximum value must take place, followed by the updating or deletion of all constraints related to the two selected regions.

Next: Creating the Initial Regions Up: Theory Previous: Cost Function Formulation
Mark Jenkinson 2001-10-12