Page History

...

• At its core, the EWA algorithm looks at the cell-to-cell delta in source to target cell mapping, both along and across track. These deltas are used to compute the parameters for a quadratic equation defining an “ellipse of influence” from a source cell to one or more target cells.
• The “ellipse of influence” is used both to compute which target cells are affected by a source cell – a bounding box to the ellipse of influence – and to compute a weighting factor for a weighted averaging of source cells per target cell. The weighting is defined in terms of the distance of the source cell center location to the target cell center (radius of the ellipse).  Those source cells closer to the target cell are weighted more heavily than a simple linear cell-to-cell distance.

• The “ellipse of influence” provides an important technique for calculating the area of influence, in the target grid.  It is an efficient way of finding target cells when forward projecting the source data grid to the output grid. This permits a reasonably efficient “forward navigation” approach, versus more typical reverse projection algorithms.

• For forwards projection, the source data is processed forwards to the target grid by calculating the target projected location and “ellipse of influence” for each source cell.  At the end, each target cell has potentially multiple source cells that map to the target cell.  The algorithm calculates a weighted average of all source cells that map to a given target cell.  It  
• It calculates - during the processing of source data points , - the target points of reference, the weighted-values accumulated as the numerator, and the weights themselves summed as the denominator.  After the source data is processed, the end result is the quotient of numerator to denominator values per target grid cell.
• This technique allows a single pass through the source data grid - to both identify the target cells and compute a partial solution to the output value - the numerator and denominator values.  This is followed by a simple pass through the target cells to divide the numerator (weighted sum of values) by the denominator (sum of weights).

Anti-aliasing Filter

• An important but not always evident aspect of the EWA algorithm is a further adjustment of the weighting factors to implement a gaussian filter to the projection processing. The gaussian filter is important to minimizing the possible aliasing and moiré effects when down-sampling a larger array of source data to a smaller set of target data.

• Expand
  title More details...
  The topic of aliasing and moiré effects in digital image processing is complex. In brief, and perhaps unsatisfyingly so, anytime you digitize at a specific resolution, or "down-sample" from a higher resolution to lower resolution, it is possible to introduce patterns of imaging that suggest lines or curves that are not present in the original or source image. Here is one article that describes the effect, both in terms of audio sampling (where I first encountered this) and in video sampling:  https://matthews.sites.wfu.edu/misc/DigPhotog/alias/index.html.  (That is from a physics professor at Wake-Forest U., in North Carolina.  An interesting site, and not a bad explanation of what is happening). There is another article that correlates the frequency domain analysis and the various discrete filtering techniques in image processing, suggesting further that the gaussian filter used in EWA is an important if not perfect mechanism to reducing aliasing and moire patterns.  I can’t claim to fully understand this, but it does appear to again correlate the image processing world with our reprojection efforts.  https://www.strollswithmydog.com/downsizing-algorithms-effects-on-resolution/#more-954.  Note that wherever the reprojection mapping of source data to target projection results in “downsampling” of an input area to an output area - aliasing can occur if some kind of interpolation filtering is not applied.  This is not uniform across the output dataset, as reprojection itself is not uniform, but very often applies in some area of the output: https://www.strollswithmydog.com/downsizing-algorithms-effects-on-resolution/#more-954. I’m reminded that HEG chooses a higher output resolution that minimizes downsampling effects (eliminates?), while GDAL chooses an output resolution that preserves overall grid sizing, generally at a lesser resolution, and that can introduce downsampling artifacts.  While HEG's approach may not eliminate the issue (TBD), it certainly does seems to minimize the issue somewhat. Subjectively I'll note that aliasing and moiré effects have been very visible in previous reprojection efforts.  In the development of the Swath-Projector application both forward (EWA) and reverse (nearest-neighbor, bi-linear) projection/interpolation options were implemented. Very often the nearest-neighbor and bi-linear (without filters) introduced these effects, along with a kind of "fingers" of data along the edges, which I think is a similar result.  The end results was that EWA "looked" much better.  Even the Elliptically-Weighted-Nearest-Neighbor option, which uses the elliptical weights to pick the highest-weighted as the nearest value - without averaging the source data - was a significant improvement.   I believe in the image processing world, there is a trade-off of "sharpness" and full resolution access vs. the introduction of these effects.  I.e., a kind of minor "blurring" of the image is introduced, but I don't think in practice this was very significant. I suspect the gaussian filter's reduction of aliasing effects far outweigh any loss of "sharpness" in the output data. The "Stalls with my dog" link above describes a metric of processing shown in the frequency domain on something called the MTF chart.  The ideal has the filter following source data up to something called the "nyquist frequency" and then sharply dropping off above that frequency.  It can be seen that e.g., Nearest-Neighbor interpolation without filtering does quite poorly on this metric, while the gaussian filter used in the EWA technique does quite well.

...