ALE
Image Processing Software

Deblurring, Anti-aliasing, and Superresolution.


Local Operation
localhost
5393119533

[ Up ]

Monte Carlo Error Function

Monte Carlo alignment can decrease the time required to align large images, since performing coordinate transformations and memory accesses at every pixel can be expensive. Sections in this page describe the motivation for Monte Carlo alignment, the ratio calculations used, the sampling algorithm, cache behavior for the algorithm, randomization approaches, typical deviations from the specified ratios, special handling of level-of-detail, and practical observations regarding the use of Monte Carlo alignment.

Motivation

Performing large numbers of coordinate transformations and memory accesses in order to determine alignment error can be computationally expensive. One approach to mitigating this expense is to use reduced level-of-detail. However, using reduced level-of-detail can also reduce alignment precision. In particular, reducing the level of detail by a factor of two can make impossible the task of precisely aligning a horizontal line one pixel high. However, if just a few pixels from the line are sampled at full detail, exact alignment is possible.

Ratio Calculations

In Monte Carlo alignment, a ratio

s = (expected # of pixel samples) / (# of total pixels in the accumulated image)
is specified. From this ratio, a new ratio
u = (expected # of unsampled pixels) / (expected # of sampled pixels)
is calculated. Pixels are sampled in such a manner that u is approximately satisified.

At this stage, the region of overlap with the new frame is not considered. With a limited area of overlap, the number of actual samples contributing to the final error value will typically be reduced proportionally. (Angelo Pesce has pointed out that better approaches may be possible, wherein explicit calculation of overlapping areas reduces the number of coordinate transformations performed.)

Sampling Algorithm

Pixels are considered in order of index, where the accumulated image pixel at position (i, j) is numbered with an index (i * width + j). In order of index, we skip and sample pixels in such a manner that the expected size of a run of consecutive skipped pixels preceding a sampled pixel is u. We select the size of each run of consecutive skipped pixels as follows:

If 2 * u is an integer, then we draw uniformly from integer values in the interval [0,2u]. If it is not an integer, then we draw from integer values in the interval [0,2u + 1] in such a manner that integer values in [0,2u] are equally likely to be chosen. (There is only one probability distribution of this kind that satisfies the expected value u. Version 0.4.3 deviates slightly from this distribution, and so a deviation in the expected value of s occurs, as outlined in this table. This problem is fixed in version 0.4.4.)

(Also, see the section below on interaction with level-of-detail.)

Cache behavior

Since indices are monotonically increasing in memory address, this approach to sampling may make effective use of memory cache where other approaches (e.g. repeated random draws from the entire index space) would not.

Randomization

ALE versions 0.4.7 and earlier do not reseed the pseudorandom number generator, and so a new random subset is selected every time the error function is evaluated. Hence, as more or fewer of the pixels critical to alignment are sampled, the reported alignment can worsen or improve even in the absence of any change in transformation.

With this approach, since many transformations are inspected during the alignment of any given frame, it is likely, especially with greater precision of alignment, that some measured differences between transformations are due to a difference in sample sets rather than a difference in alignment accuracy.

By reseeding the pseudorandom number generator, ALE versions 0.4.8 and later instead use a consistent set of pixels from the accumulated image when comparing two transformations. Tests sampling 3% of pixels from a set of 320x240 frames indicate that this approach improves alignment.

Sampling characteristics

For an image with 100,000 pixels and specified s in the interval [0.005,0.995], ALE's sampling method results in a ratio s within 0.000003 of the specified s. This number improves with image size. These results are outlined in the table linked above. However, note that s only represents an expected value, and the actual number of sampled pixels may vary by more than the numbers given here.

Interaction with level-of-detail

When reduced level-of-detail is used, the number of reduced-detail pixels sampled is taken to be a percentage of the total number of pixels in the full-detail image, rather than as a percentage of the total number of pixels in the reduced-detail image. (When this fraction of pixels in the full-detail image is more than the number of reduced-detail pixels available, all reduced-detail pixels are used.) This may improve the likelihood of successful alignment, but may also add overhead to the alignment process.

Use of Monte Carlo Alignment

If it is not known in advance what settings will work well for a series of frames, it may be desirable to begin by sampling a small percentage of pixels, saving the results of alignment, and then, if the output suggests that proper alignment is occuring, performing more precise alignment with a larger percentage of pixels on later passes, using smaller perturbation upper bounds. If alignment problems occur on the first pass, the percentage of pixels can be increased and alignment performed again.




Copyright 2002, 2003, 2004 David Hilvert

Verbatim copying and distribution of this entire article is permitted in any medium, provided this notice is preserved.