doc/html-original/ALE/download/ale-0.5.1-tech/alignment/index.html

   1 <html>
   2 <title>Alignment</title>
   3 <style type="text/css">
   4   TABLE.ba { max-width: 678; text-align: center; padding-bottom: 15; padding-top: 5}
   5   TABLE.inline { padding-right: 300; clear: left}
   6   TD.text_table {padding-left: 2; padding-right: 2; border-width: 1}
   7   H2 {clear: left}
   8   P {max-width: none; padding-right: 300; clear: left}
   9   BLOCKQUOTE {padding-right: 400 }
  10   LI {max-width: 640; clear: left}
  11   P.footer {max-width: none; width: auto; padding-left: 0}
  12   P.header {max-width: none; width: auto; padding-left: 0}
  13   HR.main {max-width: 640; clear: left; padding-left: 0; margin-left: 0}
  14   HR.footer {clear: both}
  15 </style>
  16 </head><body>
  17
  18
  19
  20 <table align=right valign=top width=160>
  21 <td valign=top height=600 width=160>
  22 <a href="http://auricle.dyndns.org/ALE/">
  23 <big>ALE</big>
  24 <br>
  25 Image Processing Software
  26 <br>
  27 <br>
  28 <small>Deblurring, Anti-aliasing, and Superresolution.</small></a>
  29 <br><br>
  30 <big>
  31 Local Operation
  32 </big>
  33 <hr>
  34 localhost<br>
  35 5393119533<br>
  36 </table>
  37
  38
  39
  40 <p><b>[ <a href="../">Up</a> | <a href="error/">Error Function</a> ]</b></p>
  41 <h1>Alignment</h1>
  42
  43 ALE aligns each supplemental frame, in sequence, with the merged rendering
  44 representing all previous frames.  This page outlines the three supported
  45 transformation classes, the algorithm used for alignment, and the properties of
  46 the alignment algorithm.  Following this is a discussion of practical use of
  47 alignment options, including alignment classes and alignment in the case of
  48 extended renderings.
  49
  50 <h2>Transformations</h2>
  51
  52 <p>ALE offers three classes of transformations: </p>
  53
  54 <table border>
  55 <tr><td>Translations</td><td>introduced in version 0.0.0</td>
  56 <tr><td>Euclidean transformations (excluding reflections)</td><td>introduced in version 0.1.0</td>
  57 <tr><td>Projective transformations</td><td>introduced in version 0.2.0</td>
  58 </table>
  59
  60 <!-- <p>ALE uses a forward transformation to map from a supplemental frame to the
  61 accumulated image, and an inverse transformation to map from the accumulated
  62 image to the supplemental frame.  Alignment operates on the parameters of the
  63 forward transformation. -->
  64
  65 <h2>Algorithm</h2>
  66
  67 <p>Alignment proceeds by a deterministic search, beginning with an initial
  68 transformation and modifying this transformation through a series of
  69 perturbations.
  70
  71 <p>The initial transformation may be loaded from a file or selected by default.
  72 The default initial transformation is either the identity transformation or
  73 (when the <code>--follow</code> option is specified) the most recently merged
  74 frame's final alignment.  (Note that changes in release 0.5.0 are not reflected
  75 here; these changes affect the interaction of the --follow and --trans-load
  76 flags.)
  77
  78 <p>Once the initial transformation is determined, an initial perturbation
  79 amount is selected, and represents the step size by which each of the
  80 transformation parameters are changed.  In translational or Euclidean
  81 alignment, the perturbation amount is applied to translation -- in units of
  82 pixels on the two image axes -- and rotation -- in units of degrees about the
  83 image center.  (In version 0.4.8 and later, an additional configurable upper
  84 bound constrains rotational perturbation separately, preventing, e.g., a
  85 360 degree perturbation of rotation.)  In the case of projective alignment, the
  86 perturbation amount is applied to the position of the corners of the projected
  87 quadrilateral in units of pixels, where the projection is from the boundary
  88 of the supplemental image into the coordinate system of the accumulated image.
  89
  90 <p>If possible, transformation parameters are changed to decrease the <a
  91 href="error/">error</a> between the two images being
  92 aligned.  The perturbation amount is halved whenever it is determined that no
  93 parameter change of this size improves the alignment of the images.  A lower
  94 bound on the perturbation amount determines when the alignment is complete.
  95
  96 <p>The order in which parameters are considered for change is specified in the
  97 source code, and has the following property: No modified parameter is
  98 considered for further change until all other parameters have been considered.
  99 A consequence of this property is that parameters are always considered in a
 100 fixed (round robin) order.
 101
 102 <p>When multiple levels of detail are used, the error may be calculated on
 103 images with a reduced level of detail.  ALE versions 0.1.1 through 0.4.7 use a
 104 level of detail twice as fine as the perturbation amount for perturbation
 105 amounts larger than two, and full detail otherwise.  Later versions default to
 106 this behavior, but can be configured differently.  Earlier versions do not use
 107 reduced levels of detail.
 108
 109 <h2>Properties</h2>
 110
 111 <p>Several assumptions were made throughout the design and testing of the
 112 algorithm outlined above.  These assumptions are outlined below.
 113
 114 <p>The algorithm is based on a hill-climbing approach, which requires that any
 115 local minimum reachable from the starting point by traveling a path of
 116 decreasing error is also a global minimum (or, in this case, the correct
 117 alignment).  While it is possible that the algorithm outlined above succeeds in
 118 some cases for which hill-climbing fails, it is still susceptible to entrapment
 119 in local minima.
 120
 121 <p>As outlined above, depending on program options, transformation parameters
 122 may be changed by perturbations of several units (degrees or pixels) early in
 123 the alignment process.  As long as no change of this magnitude moves the
 124 transformation out of the 'bowl' in which the minimum error -- and hence
 125 correct alignment -- lies, this is not a problem.  However, it might break in
 126 some cases where a hill-climbing approach would succeed.  (Notably, simulated
 127 annealing suffers from a similar problem, and it seems likely that a case could
 128 be constructed in such a way that the algorithm outlined above -- like
 129 simulated annealing -- could, contrarily, succeed where hill-climbing fails.)
 130
 131 <p>Finally, the use of reduced level-of-detail relies on a high signal-to-noise
 132 ratio at low frequencies.  Fortunately, this assumption seems to generally
 133 hold, but camera defects or radio interference could violate the assumption,
 134 possibly resulting in misalignment.
 135
 136 <h2>Use of Alignment Classes</h2>
 137
 138 <p>ALE is likely to be most useful when corresponding regions of different
 139 frames can be aligned by one of the available alignment classes.
 140
 141 <p>As described by Steve Mann in his work on <a
 142 href="http://wearcam.org/orbits/">Video Orbits</a>, the projective
 143 transformation offers particular versatility for camera imaging of (ideal
 144 Lambertian) flat scenes.  In this case, any change in camera position and
 145 orientation can be corrected as long as points always have a defined projection
 146 onto the rendering plane (for which ALE uses the base of the pyramid
 147 <b>R<sub>1</sub></b>).
 148
 149 <p>In camera imaging of scenes with depth, correction for orientation is almost
 150 the same as for flat scenes, since, if focus and lens distortion is ignored, a
 151 scene with depth is indistinguishable from a flat scene from the perspective of
 152 a camera whose position is fixed.
 153
 154 <p>For sequences of camera images with small changes in position or
 155 orientation, the projective transformations for alignment may closely
 156 approximate Euclidean transformations; in this case, using Euclidean
 157 transformations may achieve similar results and may require less time for
 158 alignment, since there are fewer parameters to tweak (three parameters
 159 instead of eight).
 160
 161 <p>In the case of flatbed scanners that preserve the relative height and width
 162 of scans, any change in the position or orientation of flat objects can be
 163 corrected using the Euclidean alignment class.</p>
 164
 165 <p>If a flatbed scanner does not preserve relative height and width, but does
 166 preserve straight lines, then any change in the position or orientation of flat
 167 objects can be corrected with the projective alignment class.
 168
 169 <p>However, even if a transformation is within the alignment class used, the
 170 alignment algorithm may still be unable to determine large transformations.
 171
 172 <h2>Alignment in the case of Extended Renderings</h2>
 173
 174 <p>By using the --extend flag, ALE can be used to create image mosaics spanning
 175 a spatial region larger than that represented by any single image in the frame
 176 sequence.  In these cases, if adjacent frames in the sequence tend to be more
 177 closely aligned with each other than they are with the original frame, it may
 178 be helpful to also use the --follow flag as a hint to the alignment algorithm.
 179 </p>
 180
 181
 182 <br><br>
 183 <small>
 184 </small>
 185
 186 <hr>
 187 <i>Copyright 2002, 2003 <a href="mailto:dhilvert@auricle.dyndns.org">David Hilvert</a></i>
 188 <p>Verbatim copying and distribution of this entire article is permitted in any
 189 medium, provided this notice is preserved.
 190 </body>
 191 </html>