doc/localhost/ALE/download/ale-0.6.0-tech/index.html

   1 <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
   2 <html>
   3 <head>
   4   <title>ALE Version 0.6.0 Technical Description</title>
   5
   6 <style type="text/css">
   7   TABLE.ba { max-width: 678; text-align: center; padding-bottom: 15; padding-top: 5}
   8   TABLE.inline { padding-right: 300; clear: left}
   9   TD.text_table {padding-left: 2; padding-right: 2; border-width: 1}
  10   H2 {clear: left}
  11   P {max-width: none; padding-right: 300; clear: left}
  12   BLOCKQUOTE {padding-right: 400 }
  13   LI {max-width: 640; clear: left}
  14   P.footer {max-width: none; width: auto; padding-left: 0}
  15   P.header {max-width: none; width: auto; padding-left: 0}
  16   HR.main {max-width: 640; clear: left; padding-left: 0; margin-left: 0}
  17   HR.footer {clear: both}
  18 </style>
  19 </head><body>
  20
  21
  22
  23 <table align=right valign=top width=160>
  24 <td valign=top height=600 width=160>
  25 <a href="http://auricle.dyndns.org/ALE/">
  26 <big>ALE</big>
  27 <br>
  28 Image Processing Software
  29 <br>
  30 <br>
  31 <small>Deblurring, Anti-aliasing, and Superresolution.</small></a>
  32 <br><br>
  33 <big>
  34 Local Operation
  35 </big>
  36 <hr>
  37 localhost<br>
  38 5393119533<br>
  39 </table>
  40
  41
  42
  43 <p><b>[ <a href="../../tech/">Up</a> | <a href="merging">Merging</a>  | <a href="drizzling">Drizzling</a> | <a href="enhance/">Enhancement</a> | <a href="iterative/">Irani-Peleg</a> | <a href="alignment/">Alignment</a> ]</b></p>
  44 <h1>ALE Version 0.6.0 Technical Description <!-- <small>(or the best approximation to date)</small> --> </h1>
  45
  46 <h2>Abstract</h2>
  47
  48 <p>ALE combines a series of input frames into a single output image possibly
  49 having:</p>
  50
  51 <ul>
  52 <li>Reduced noise.
  53 <li>Reduced aliasing.
  54 <li>Increased tonal resolution.
  55 <li>Increased spatial resolution.
  56 <li>Increased spatial extents.
  57 </ul>
  58
  59 <p>This page discusses related work, models of program input, renderers used by
  60 ALE, the alignment algorithm used, an overview of the structure of the
  61 program, and examples for which the above output image characteristics are
  62 satisfied.</p>
  63
  64 <p>ALE's approach to exposure registration and certainty-based rendering is not
  65 discussed in the current version of this document.  See the source code for
  66 implementation details.
  67
  68 <p><b>Note: This document uses HTML 4 character entities. &nbsp;Sigma is '&Sigma;'; summation is '&sum;'</b>.</p>
  69
  70 <h2>Related Work</h2>
  71
  72 <p>The <a href="drizzling/">drizzling renderer</a> used in ALE is based on
  73 Richard Hook and Andrew Fruchter's <a
  74 href="http://www.cv.nrao.edu/adass/adassVI/hookr.html">drizzling technique</a>.
  75
  76 <p>Steve Mann's discussions (e.g. <a
  77 href="http://wearcam.org/orbits/">here</a> and <a
  78 href="http://wearcam.org/comparam.htm">here</a>) of increased spatial extents, projective
  79 transformations, image processing on linear data, and weighting by certainty
  80 functions, have influenced features incorporated by ALE.
  81
  82 <p>ALE incorporates an <a href="iterative/">iterative solver</a> based on Michal Irani and Shmuel
  83 Peleg's iterative deblurring and super-resolution technique (see <a
  84 href="http://www.wisdom.weizmann.ac.il/~irani/abstracts/superResolution.html">here</a>).
  85
  86 <h2>Models of Program Input</h2>
  87
  88 <h3>Scalars</h3>
  89
  90 <p>The following conventions are used in this document to denote sets of scalar values:</p>
  91
  92 <table>
  93 <tr><th>Symbol</th><th>Meaning</th>
  94 <tr><td><b>NN</b><td>Set of integers &ge; 0.
  95 <tr><td><b>R</b><td>Set of real numbers.
  96 <tr><td><b>R<sup>+</sup></b><td>Set of real numbers &ge; 0.
  97 </table>
  98
  99 <h3>RGB triples</h3>
 100
 101 An <i>RGB triple</i> is a member of the set
 102 <b>R<sup>+</sup>&times;R<sup>+</sup>&times;R<sup>+</sup></b>.  Components of an
 103 RGB triple <b>t</b> are denoted <b>t<sub>R</sub>, t<sub>G</sub>,
 104 t<sub>B</sub></b>.
 105
 106 <h3>Discrete Images</h3>
 107
 108 <p>For <b>d<sub>1</sub>, d<sub>2</sub> &isin; NN</b>, A <i>discrete image</i>
 109 <b>D</b> of size <b>(d<sub>1</sub>, d<sub>2</sub>)</b> is a function
 110
 111 <blockquote>
 112 <b>D: {0, 1, &hellip;, d<sub>1</sub> - 1}&times;{0, 1, &hellip;, d<sub>2</sub> - 1} &rarr; R<sup>+</sup>&times;R<sup>+</sup>&times;R<sup>+</sup></b>
 113 </blockquote>
 114
 115 <p>The set of all discrete images is denoted <b>DD</b>.
 116
 117 <h3>Continuous Images</h3>
 118
 119 <p>For <b>c<sub>1</sub>, c<sub>2</sub> &isin; R<sup>+</sup></b>, a <i>continuous image</i> <b>I</b> of size <b>(c<sub>1</sub>, c<sub>2</sub>)</b> is a function
 120
 121 <blockquote>
 122 <b>I: [0, c<sub>1</sub>]&times;[0, c<sub>2</sub>] &rarr; R<sup>+</sup>&times;R<sup>+</sup>&times;R<sup>+</sup></b>
 123 </blockquote>
 124
 125 <p>The set of all continuous images is denoted <b>CC</b>.
 126
 127 <!--
 128 An <i>infinite continuous image</i> <b>I</b> is a function
 129
 130 <blockquote>
 131 <b>I: (-&infin;, &infin;)&times;(-&infin;, &infin;) &rarr; R<sup>+</sup>&times;R<sup>+</sup>&times;R<sup>+</sup></b>
 132 </blockquote>
 133 -->
 134
 135 <h3>Position and Direction</h3>
 136
 137 <p>A <i>position</i> is a point in Euclidean 3-space <b>R<sup>3</sup></b>.
 138
 139 <p>A <i>direction</i> is a point on the unit 3-sphere <b>S<sub>3</sub></b>.
 140
 141 <h3>Scene</h3>
 142
 143 <p>A <i>scene</i> <b>S</b> is a function
 144
 145 <blockquote>
 146 <b>S: R<sup>3</sup> &times; S<sub>3</sub> &rarr; R<sup>+</sup>&times;R<sup>+</sup>&times;R<sup>+</sup></b>
 147 </blockquote>
 148
 149 <p>mapping a position and direction to an RGB triple.  The set of all scenes is denoted <b>SS</b>.
 150
 151 <h3>View</h3>
 152
 153 <p>A <i>view</i> <b>V</b> is a function
 154
 155 <blockquote>
 156 <b>V: SS &rarr; CC</b>
 157 </blockquote>
 158
 159 <h3>Camera Snapshots</h3>
 160
 161 <p>A <i>camera snapshot</i> is defined as a triple consisting of:</p>
 162
 163 <ul>
 164 <li>A scene <i><b>S</b></i>.
 165 <li>A view <i><b>V</b></i>.
 166 <li>A function <i><b>d: CC &rarr; DD</b></i>.
 167 </ul>
 168
 169 <h3>Camera Input Frame Sequences</h3>
 170
 171 <p>For positive integer <b>N</b>, a sequence of camera snapshots
 172 <b>{ K<sub>1</sub>, K<sub>2</sub>, &hellip;, K<sub>N</sub> }</b>, defined by the
 173 triples <b>{ K<sub>j</sub> = (S<sub>j</sub>, V<sub>j</sub>, d<sub>j</sub>)
 174 }</b> is a <i>camera input frame sequence</i> if, for all <b>j</b> and
 175 <b>j'</b>, <b>S<sub>j</sub> = S<sub>j'</sub></b>.
 176
 177 <h3>Projective transformations</h3>
 178
 179 <p>A <i>projective transformation</i> is a transformation that maps lines to
 180 lines.  For more details, see:
 181
 182 <blockquote>
 183 Heckbert, Paul.  "Projective Mappings for Image Warping."  Excerpted from his
 184 Master's Thesis (UC Berkeley, 1989).  1995.  <a href="http://www.cs.cmu.edu/afs/cs/project/classes-ph/862.95/www/notes/proj.ps">http://www.cs.cmu.edu/afs/cs/project/classes-ph/862.95/www/notes/proj.ps</a>
 185 </blockquote>
 186
 187 <h3>Projective Snapshots</h3>
 188
 189 <p>A <i>projective snapshot</i> is defined as an <i>n</i>-tuple consisting of:</p>
 190
 191 <ul>
 192 <li>A continuous image <i><b>&Sigma;</b></i>.
 193 <li>A projective transformation <i><b>q</b></i> with restricted domain, such that <i><b>composite(&Sigma;, q) &isin; CC</b></i>
 194 <li>A function <i><b>d: CC &rarr; DD</b></i>.
 195 </ul>
 196
 197 <h3>Projective Input Frame Sequences</h3>
 198
 199 <p>For positive integer <b>N</b>, a sequence of projective snapshots <b>{
 200 P<sub>1</sub>, P<sub>2</sub>, &hellip;, P<sub>N</sub> }</b>, defined by the
 201 <i>n</i>-tuples <b>{ P<sub>j</sub> = (&Sigma;<sub>j</sub>, q<sub>j</sub>,
 202 d<sub>j</sub>) }</b>, is a <i>projective input frame sequence</i> if, for all
 203 <b>j</b> and <b>j'</b>, <b>&Sigma;<sub>j</sub> = &Sigma;<sub>j'</sub></b>.
 204
 205 <p>The first frame in the sequence of input frames is called the <i>original
 206 frame</i>, and subsequent frames are called <i>supplemental frames</i>.
 207
 208 <h3>Construction of Projective Input Frame Sequences from Camera Input Frame Sequences</h3>
 209
 210 <p>Given a camera input frame sequence <b>{ K<sub>j</sub> = (S, V<sub>j</sub>,
 211 d<sub>j</sub>) }</b>, if there exists a continuous image <b>&Sigma;</b> and a
 212 sequence <b>{ q<sub>j</sub> }</b> of projective transformations with restricted
 213 domain such that, for all <b>j</b>, <b>V<sub>j</sub>(S) =
 214 q<sub>j</sub>(&Sigma;)</b>, then this camera input frame sequence admits a
 215 corresponding projective input frame sequence <b>{ P<sub>j</sub> = (&Sigma;,
 216 q<sub>j</sub>, d<sub>j</sub>) }</b>.
 217
 218 <p>Informally, two cases where such construction is possible for an ideal
 219 pinhole camera are:
 220
 221 <ul>
 222 <li>A sequence of frames taken from a fixed position in space, but with variable
 223 orientation.
 224 <li>A sequence of frames depicting a single flat, diffuse surface, taken from
 225 arbitrary positions and orientations.
 226 </ul>
 227
 228 <p>For more information about the properties of projective transformations,
 229 see the first of Steve Mann's papers referenced in the Related Work section above.
 230
 231 <h3>Projective Renderer without Extension</h3>
 232
 233 <p>For a projective input frame sequence <b>{ P<sub>j</sub> = (&Sigma;,
 234 q<sub>j</sub>, d<sub>j</sub>) }</b>, a <i>projective renderer without
 235 extension</i> is an algorithm that outputs a discrete image approximation of
 236 <b>composite(&Sigma;, q<sub>1</sub>)</b>.  The assumptions used in calculating the approximation
 237 vary across rendering methods.
 238
 239 <h3>Projective Renderer with Extension</h3>
 240
 241 <p>For a projective input frame sequence <b>{ P<sub>j</sub> = (&Sigma;,
 242 q<sub>j</sub>, d<sub>j</sub>) }</b>, a <i>projective rendering method with
 243 extension</i> is an algorithm that outputs a discrete image approximation of
 244 <b>composite(&Sigma;', q<sub>1</sub>')</b>, where <b>q<sub>1</sub>'</b> extends
 245 the domain of <b>q<sub>1</sub></b> so that its range is a superset of the
 246 domain of <b>&Sigma;</b>, and <b>&Sigma;'</b> extends <b>&Sigma;</b> to match
 247 the range of <b>q<sub>1</sub>'</b>.  The assumptions used in calculating the
 248 approximation vary across rendering methods.
 249
 250 <!--
 251 <h3>Diffuse Surfaces</h3>
 252
 253 Given a camera input frame sequence <b>{ C<sub>1</sub>, C<sub>2</sub>,
 254 &hellip;, C<sub>N</sub> }</b>, defined by the <i>n</i>-tuples
 255 <b>{&nbsp;C<sub>j</sub> = (S, R<sub>j</sub>, I<sub>j</sub>, D<sub>j</sub>,
 256 d<sub>j</sub>)&nbsp;}</b>, a surface in <b>S</b> is <i>diffuse</i> if the
 257 radiance of each point on the surface (as measured by the canonical sensor) is
 258 the same for all views <b>R<sub>j</sub></b> from which the point is visible.
 259
 260 <h3>The Extended Pyramid</h3>
 261
 262 <p>If the view pyramids <b>{ R<sub>1</sub>, R<sub>2</sub>, &hellip;,
 263 R<sub>N</sub> }</b> of a sequence of <b>N</b> camera input frames share a
 264 common apex and can be enclosed in a single rectangular-base pyramid <b>R</b>
 265 sharing the same apex and having base edges parallel to the base edges of
 266 <b>R<sub>1</sub></b>, then the smallest such <b>R</b> is the <i>extended pyramid</i>.
 267 Otherwise, the extended pyramid is undefined.</p>
 268
 269 <p>If a camera input frame sequence has an extended pyramid <b>R</b>, then an
 270 <i>extended image</i> is defined from <b>R</b> in a manner analogous to the definition
 271 of the image <i><b>I</b></i> from the view pyramid <i><b>R</b></i> in the
 272 definition of a camera snapshot.
 273 -->
 274
 275 <h2>Renderers</h2>
 276 <!--
 277 <h3>Examples</h3>
 278
 279 Examples of rendering output are available on the <a href="../render/">rendering
 280 page</a>.
 281 -->
 282
 283 <h3>Extension</h3>
 284
 285 <p>All renderers can be used with or without extension (according to whether
 286 the --extend flag is used).  The target image for approximation (either
 287 <b>composite(&Sigma;, q<sub>1</sub>)</b> or <b>composite(&Sigma;',
 288 q<sub>1</sub>')</b>) is generically called <b>T</b>.
 289
 290 <h3>Renderer Types</h3>
 291
 292 <p>Renderers can be of incremental or non-incremental type.  Incremental
 293 renderers update the rendering as each new frame is loaded, while
 294 non-incremental renderers update the rendering only after all frames have been
 295 loaded.</p>
 296
 297 <p>Incremental renderers contain two data structures that are updated with each
 298 new frame: an accumulated image <b>A</b> with elements <b>A<sub>x, y</sub></b>
 299 and the associated weight array <b>W</b> with elements <b>W<sub>x, y</sub></b>.
 300 The accumulated image stores the current rendering result, while the weight
 301 array stores information about contributions to each accumulated image pixel.
 302
 303 <h3>Renderer Details</h3>
 304
 305 These pages offer detailed descriptions of renderers.
 306
 307 <ul>
 308 <li>Incremental Renderers</li>
 309         <ul>
 310         <li><a href="merging/">Merging</a>
 311         <li><a href="drizzling/">Drizzling</a>
 312         </ul>
 313 <li>Non-incremental Renderers</li>
 314         <ul>
 315         <li><a href="enhance/">Unsharp Masking</a>
 316         <li><a href="iterative/">Irani-Peleg</a>
 317         </ul>
 318 </ul>
 319
 320 <h3>Rendering Predicates</h3>
 321
 322 <p>The following table lists predicates which may be useful in determining
 323 whether the discrete-image output of a rendering method approximates <b>T</b>.
 324 The section following this lists, for each renderer, a collection of predicates
 325 which should result in <b>T</b> being approximated.</p>
 326
 327 <blockquote>
 328 <table border cellpadding=5>
 329 <tr>
 330 <th>Predicate</td>
 331 <th>Explanation</th>
 332 <tr>
 333 <td>Alignment</td>
 334 <td>The projective input frame transformations <b>q<sub>j</sub></b> are known.</td>
 335 <tr>
 336 <td>Translation</td>
 337 <td>All projective input frame transformations <b>q<sub>j</sub></b> are
 338 translations.</td>
 339 <tr>
 340 <td>Point sampling</td>
 341 <td><b>(&forall;j) (&forall;x &isin; Domain[q<sub>j</sub>]) (d<sub>j</sub>(composite(T, q<sub>j</sub>))(x) = composite(T, q<sub>j</sub>)(x))</b>.
 342 <tr>
 343 <td>Box Filter Approximation</td>
 344 <td>An acceptable discrete approximation of <b>T</b> can be achieved by
 345 partitioning it into a square grid and representing each square region by its
 346 mean value.
 347 <tr>
 348 <td>Jittering Assumption 1</td>
 349 <td>The average of several point samples drawn uniformly from a region of
 350 <b>T</b> is an acceptable approximation for the mean value of the region.
 351 <tr>
 352 <td>Jittering Assumption 2</td>
 353 <td>Each region in <b>T</b> corresponding to an output pixel has been sampled several
 354 times at points drawn uniformly from the region.
 355 <tr>
 356 <td>Small radius</td>
 357 <td>The radius parameter used for drizzling is chosen to be sufficiently small.
 358 <tr>
 359 <td>Barlett filter approximation</td>
 360 <td>Convolution of <b>T</b> with a Bartlett (aka triangle) filter remains an
 361 acceptable approximation of <b>T</b>.
 362 <tr>
 363 <td>Linear PSF only</td>
 364 <td>There is no non-linear PSF component.
 365 <tr>
 366 <td>USM approximation</td>
 367 <td>The Unsharp Mask technique provides an acceptable approximation of the
 368 inverse convolution for the given linear point-spread function.
 369 <tr>
 370 <td>Correct PSF</td>
 371 <td>The behavior of <b>d<sub>j</sub></b> is equivalent to convolution with the
 372 given point-spread functions.
 373 <tr>
 374 <td>Low Response Approximation</td>
 375 <td>Frequencies to which <b>d<sub>j</sub></b> has low response need not be
 376 accurately reconstructed in the program output.
 377 <tr>
 378 <td>Convergence</td>
 379 <td>The Irani-Peleg technique converges to the desired output for the given
 380 input sequence.  This condition is proven for special cases in the source
 381 paper.
 382 </table>
 383 </blockquote>
 384
 385 <h3>Rendering Predicates by Renderer</h3>
 386
 387 <p>For each renderer, the following table gives a collection of rendering
 388 predicates that should result in rendered output being an acceptable
 389 approximation of <b>T</b>.  Note that renderers may produce acceptable output
 390 even when these predicates are not satisfied.  Justification for the entries in
 391 this table should appear in the detailed descriptions; if this is not the case,
 392 then the values given should be considered unreliable.</p>
 393
 394 <ul>
 395 <li><b>M</b> = Merging
 396 <li><b>D</b> = Drizzling
 397 <li><b>U</b> = USM Renderer after merging
 398 <li><b>V</b> = USM Renderer after drizzling
 399 <li><b>I</b> = Irani-Peleg Iterative Image Reconstruction
 400 </ul>
 401
 402 <blockquote>
 403 <table border cellpadding=5>
 404 <tr>
 405 <th>&nbsp;</td>
 406 <th>M</th>
 407 <th>D</th>
 408 <th>U</th>
 409 <th>V</th>
 410 <th>I</th>
 411 <tr>
 412 <td>Alignment</td>
 413 <td>X</td>
 414 <td>X</td>
 415 <td>X</td>
 416 <td>X</td>
 417 <td>X</td>
 418 <tr>
 419 <td>Translation</td>
 420 <td>X</td>
 421 <td>&nbsp;</td>
 422 <td>X</td>
 423 <td>X</td>
 424 <td>&nbsp;</td>
 425 <tr>
 426 <td>Point sampling
 427 <td>X</td>
 428 <td>X</td>
 429 <td>&nbsp;</td>
 430 <td>&nbsp;</td>
 431 <td>&nbsp;</td>
 432 <tr>
 433 <td>Box Filter Approximation
 434 <td>X</td>
 435 <td>X</td>
 436 <td>X</td>
 437 <td>X</td>
 438 <td>&nbsp;</td>
 439 <tr>
 440 <td>Jittering Assumption 1
 441 <td>X</td>
 442 <td>X</td>
 443 <td>X</td>
 444 <td>X</td>
 445 <td>&nbsp;</td>
 446 <tr>
 447 <td>Jittering Assumption 2
 448 <td>X</td>
 449 <td>X</td>
 450 <td>X</td>
 451 <td>X</td>
 452 <td>&nbsp;</td>
 453 <tr>
 454 <td>Small radius</td>
 455 <td>&nbsp;</td>
 456 <td>X</td>
 457 <td>&nbsp;</td>
 458 <td>X</td>
 459 <td>&nbsp;</td>
 460 <tr>
 461 <td>Bartlett filter approximation</td>
 462 <td>X</td>
 463 <td>&nbsp;</td>
 464 <td>X</td>
 465 <td>&nbsp;</td>
 466 <td>&nbsp;</td>
 467 <tr>
 468 <td>Linear PSF</td>
 469 <td>&nbsp;</td>
 470 <td>&nbsp;</td>
 471 <td>X</td>
 472 <td>X</td>
 473 <td>&nbsp;</td>
 474 <tr>
 475 <td>USM approximation</td>
 476 <td>&nbsp;</td>
 477 <td>&nbsp;</td>
 478 <td>X</td>
 479 <td>X</td>
 480 <td>&nbsp;</td>
 481 <tr>
 482 <td>Correct PSF</td>
 483 <td>&nbsp;</td>
 484 <td>&nbsp;</td>
 485 <td>X</td>
 486 <td>X</td>
 487 <td>X</td>
 488 <tr>
 489 <td>Low Response Approximation</td>
 490 <td>X</td>
 491 <td>X</td>
 492 <td>X</td>
 493 <td>X</td>
 494 <td>X</td>
 495 <tr>
 496 <td>Convergence</td>
 497 <td>&nbsp;</td>
 498 <td>&nbsp;</td>
 499 <td>&nbsp;</td>
 500 <td>&nbsp;</td>
 501 <td>X</td>
 502 </table>
 503 </blockquote>
 504
 505 <h3>Space Complexity</h3>
 506
 507 Image storage space in memory for all renderers without extension is
 508 <i>O(1)</i> in the number of input frames and <i>O(n)</i> in the number of pixels per
 509 input frame.  The worst-case image storage space in memory for all renderers
 510 with extension is <i>O(n)</i> in the size of program input.
 511
 512 <h2>Alignment Algorithm</h2>
 513
 514 Details on the alignment algorithm used in ALE are <a href="alignment/">here</a>.
 515
 516 <h2>Program Structure</h2>
 517
 518 <p>First, a <a href="merging/">merging</a> renderer is instantiated.  Then,
 519 program flags are used to determine what other renderers should be
 520 instantiated.
 521
 522 <p>An iterative loop supplies to the renderers each of the frames in sequence,
 523 beginning with the original frame.  The <a href="drizzling/">drizzling</a> and
 524 <a href="merging/">merging</a> renderers are incremental renderers, and
 525 immediately update their renderings with each new frame, while the <a
 526 href="enhance/">USM</a> and <a
 527 href="iterative/">Irani-Peleg</a> renderers do not act until the final frame
 528 has been received.
 529
 530 <p>In the case of the incremental renderers, the original frame is used without
 531 transformation, and each supplemental frame is transformed according to the
 532 results of the <a href="alignment/">alignment</a> algorithm, which aligns each
 533 new frame with the current rendering of the <a href="merging/">merging</a>
 534 renderer.
 535
 536 <p>Once all frames have been aligned and merged, non-incremental renderers
 537 produce renderings based on input frames, alignment information, and the output
 538 of other renderers.</p>
 539
 540 <h2>Examples</h2>
 541
 542 Sections below outline examples of cases in which output images satisfy various criteria.
 543
 544 <p>For a projective input frame sequence <b>{ P<sub>k</sub> = (&Sigma;, q,
 545 d<sub>k</sub>) }</b>, these examples use the shorthand
 546
 547 <blockquote><b>I = composite(&Sigma;, q)</b></b></blockquote>
 548
 549 and
 550
 551 <blockquote><b>D<sub>k</sub> = d<sub>k</sub>(I).</b></blockquote></p>
 552
 553 <h3>Reduced Noise</h3>
 554
 555 <p>Assume a projective input frame sequence <b>{ P<sub>k</sub> }</b> of <b>K</b> frames, defined
 556 by n-tuples <b>{ P<sub>k</sub> = (&Sigma;, q, d<sub>k</sub>) }</b>, such that
 557 <b>(&exist;a &gt; 0) (&forall;x &isin; Domain[q]) (&forall;y &isin; {R, G, B})
 558 (I(x)<sub>y</sub> &gt; a/2)</b> and, for one
 559 such <b>a</b>, <b>(&forall;x) (&forall;y) (D<sub>k</sub>(x)<sub>y</sub> =
 560 I(x)<sub>y</sub> + n<sub>k,x,y</sub>)</b>, where <b>n<sub>k,x,y</sub></b> are
 561 i.i.d. additive noise terms having uniform distribution over the interval
 562 <b>(-a/2, a/2)</b>.
 563
 564 <p>In this case, rendering input frames by merging or drizzling averages the
 565 additive noise terms of the input images to produce an output additive noise
 566 term; when <b>K &ge; 2</b>, this output noise has a smaller expected absolute value than that of
 567 any given input noise term.
 568
 569 <p>To prove this, first observe that rendered output image <b>O</b> (for drizzling or merging) averages the <b>K</b> inputs with
 570 equal weight:
 571
 572 <blockquote><b>O(x)<sub>y</sub> = &sum;<sub>k</sub> (D<sub>k</sub>(x)<sub>y</sub> / K)</b></blockquote>
 573
 574 Substituting for <b>D<sub>k</sub></b>:
 575
 576 <blockquote><b>O(x)<sub>y</sub> = &sum;<sub>k</sub> [(I(x)<sub>y</sub> + n<sub>k,x,y</sub>) / K]</b></blockquote>
 577
 578 Moving the constant outside of the sum:
 579
 580 <blockquote><b>O(x)<sub>y</sub> = (I(x)<sub>y</sub> / K) * K + &sum;<sub>k</sub> (n<sub>k,x,y</sub> / K)</b></blockquote>
 581 <blockquote><b>O(x)<sub>y</sub> = I(x)<sub>y</sub> + &sum;<sub>k</sub> (n<sub>k,x,y</sub> / K)</b></blockquote>
 582
 583 The last term in the equation above is the noise term for the output image.  Leaving location
 584 and channel implicit, the expected absolute value for this term is:
 585
 586 <blockquote><b>E<sub>out</sub> = E[|&sum;<sub>k</sub> (n<sub>k</sub> / K)|]</b></blockquote>
 587
 588 Since there is nonzero probability that both strictly negative and strictly positive terms appear in the sum, this gives rise to the strict inequality:
 589
 590 <blockquote><b>E<sub>out</sub> &lt; E[&sum;<sub>k</sub> |n<sub>k</sub> / K|]</b></blockquote>
 591
 592 By linearity of expectation, this is equivalent to:
 593
 594 <blockquote><b>E<sub>out</sub> &lt; &sum;<sub>k</sub> E[|n<sub>k</sub> / K|]</b></blockquote>
 595 <blockquote><b>E<sub>out</sub> &lt; &sum;<sub>k</sub> E[|n<sub>k</sub>|] / K</b></blockquote>
 596
 597 Since the input noise distributions are identical, this reduces to:
 598
 599 <blockquote><b>E<sub>out</sub> &lt; E<sub>in</sub> * K / K</b></blockquote>
 600 <blockquote><b>E<sub>out</sub> &lt; E<sub>in</sub></b></blockquote>
 601
 602 where <b>E<sub>in</sub> = E[|n<sub>k</sub>|]</b> for any choice of k.
 603
 604 <h3>Reduced Aliasing</h3>
 605
 606 Assume that an image has been sampled at the highest frequency to which the
 607 sensors respond (i.e., half of the Nyquist frequency), resulting in aliasing,
 608 and that four such images are available, dithered (i.e., in this case,
 609 translated) so that the collection of samples from all images forms a regular
 610 grid with twice the sampling rate of the original image.  Rendering these four
 611 images with correct alignment into an output image having the same dimensions
 612 as this grid results in an image with no aliased frequencies.
 613
 614 <h3>Increased Tonal Resolution</h3>
 615
 616 <p>Assume a projective input frame sequence <b>{ P<sub>k</sub> }</b> of
 617 <b>K</b> frames, defined by n-tuples <b>{ P<sub>k</sub> = (&Sigma;, q,
 618 d<sub>k</sub>) }</b>, such that components of <b>I</b> assume a real value in
 619 the interval <b>[0, 1]</b> and <b>(&forall; x, y, k)
 620 (Probability[D<sub>k</sub>(x)<sub>y</sub> = 1] = 1 - Probability[D<sub>k</sub>(x)<sub>y</sub> = 0] = I(x)<sub>y</sub>])</b>.
 621
 622 <p>Since the transformations of all frames are identical, rendering with
 623 merging or drizzling averages the values for each pixel <b>D<sub>k</sub>(x)</b>
 624 over all values of <b>k</b>.  Since the expected value of <b>D<sub>k</sub>(x)</b>
 625 is equal to <b>I(x)</b>, the expected value of the corresponding pixel in the rendered
 626 output is always equal to <b>I(x)</b>.  However, the probability of obtaining a value
 627 within a small neighborhood of <b>I(x)</b> is generally not high for small numbers of
 628 frames.
 629
 630 <p>As the number of frames increases, however, the probability of
 631 obtaining a value within a neighborhood of any given size approaches 1.  Hence,
 632 arbitrarily high tonal resolution can be achieved with arbitrarily small (but
 633 non-zero) likelihood of error.  The exact probability can be determined
 634 according to the binomial distribution.
 635
 636 <p>(The above constitutes an outline of a proof, but there may be holes in it.)
 637
 638 <h3>Increased Spatial Resolution</h3>
 639
 640 The reduced aliasing example, above, serves also as an example of increased
 641 spatial resolution.
 642
 643 <h3>Increased Spatial Extents</h3>
 644
 645 <p>Assume a projective input frame sequence such that each snapshot can be
 646 associated with a point in the scene invisible from that snapshot, but visible
 647 from some other snapshot.
 648
 649 <p>In this case, for every snapshot in the input sequence, the output rendering
 650 will include at least one point not present in that snapshot.
 651
 652 <small>
 653
 654 </small>
 655
 656 <br>
 657 <hr>
 658 <i>Copyright 2002, 2003, 2004 <a href="mailto:dhilvert@auricle.dyndns.org">David Hilvert</a></i>
 659 <p>Verbatim copying and distribution of this entire article is permitted in any medium, provided this notice is preserved.
 660
 661
 662 </body>
 663 </html>