Improved apodization and bias correction

Following on the relatively recent addition of LSF correction to Imatest, I decided to revisit some of the implementation details of MTF Mapper.

The brutal truth is that MTF Mapper used an empirical correction factor (shock, shock, horror!) to remove the observed bias in measured MTF curves. The empirical correction factor (or rather, family of correction factors) was obtained by generating a synthetic image with a known, analytical MTF curve, and calculating the resulting ratio of the measured curve (as produced by MTF Mapper) to the expected analytical curve.

This had the advantage that it would remove both known distortions, such as that generated by the finite-difference approximation to the derivative (which Imatest refers to as the LSF correction factor), and other distortions which were produced by processes that I did not fully understand at the time.

This post will deal with two of the distortions that I have identified, and I will propose solutions that will enable MTF Mapper to do away with the empirical correction approach.

Apodization

Apodization, also called "windowing", is a way to attenuate some of the artifacts resulting from the application of the FFT (or DFT, if you like) to a signal of a finite length. The DFT/FFT assumes that the signal is periodic, that is, the first (leftmost) sample is preceded (circularly) by the last (rightmost) sample. Applying the FFT to a signal that is discontinuous when treated in this circularly wrapped-around way usually results in significant energy spuriously appearing on the high frequency end of the frequency spectrum.

A common windowing function is the Hamming window, which looks like a cosine function centered on the center of the sequence of samples. The samples are multiplied component-wise with the window function, effectively producing a new set of samples such that the leftmost and rightmost samples are scaled to very low magnitudes. Since the left- and rightmost samples are now all close to zero, we are guaranteed to have a signal that no longer has a discontinuity when wrapping around the left/right ends.

So why would we use apodization as part of the slanted edge method? First, recall how the slanted edge method works:

Step 1: generate the edge spread function (ESF)

This diagram shows how the individual pixel intensities are projected along a line that coincides with the edge we are analyzing. Owing to the angle of the edge relative to the pixel grid, the density of the projected values (along the direction perpendicular to the edge) is much greater than the original pixel spacing. The densely-spaced projected values are binned to form a regularly-spaced set of samples at (usually) 4x or 8x oversampling relative to the pixel grid. This allows us to measure frequencies above the Nyquist limit imposed by the original pixel grid.

Now we can compute the MTF as illustrated here:

Step 2: Compute MTF from PSF using FFT

Notice that the PSF is usually quite compact, i.e., most of the area under the PSF curve is located close to the centre of the PSF curve. This is typical of a PSF extracted from a real-world edge. We see some noise on the tails of the PSF, with visibly more noise on the right side --- this is an artifact of photon shot noise being relative to the signal level, so the noise magnitude is larger in the bright parts of the image.

Anyhow, since the noise is random, we might end up with large values on the edges, such as can be seen on the right end of the PSF samples. This is exactly the scenario which we would like to avoid, so we can apply a window to "squash" the samples near the edges of the PSF.

MTF Mapper had been using a plain Hamming window up to now --- this resulted in a systematic bias in MTF measurements, particularly affecting edges with an MTF50 value below 0.1 cycles per pixel.

Hamming window

Two things are visible here: the noise is suppressed reasonably well (on the ends of the green curve) after multiplying the PSF by the Hamming window function (see right side of illustration), and the PSF appears to contract slightly, effectively becoming slightly narrower after windowing.

The apparent narrowing of the PSF has the expected impact on MTF50 values: they are overestimated slightly.

I identified three possible methods to address this systematic overestimation of MTF50 values (on the low end of MTF50 values): empirical correction (as MTF Mapper has been doing so far), deconvolution, and using a different window function.

We can "reverse" the effect of the windowing after we have applied the FFT to obtain the MTF. By the convolution theorem, we know that convolution in the time domain becomes multiplication in the frequency domain. Since we multiply the PSF by the window function in the time domain, it stands to reason that we must deconvolve the MTF by the Fourier transform of the window function. Except that deconvolution is a black art that is best avoided.

I have tried many different approaches, but the high noise levels in the PSF makes for a poor experience, more apt to inject additional distortion into our MTF than to undo the slight distortion caused by windowing in the first place.


That leaves us only with the last option: choose a different window function. Purely based on aesthetics, I decided on the Tukey window with an alpha parameter of 0.6:

Tukey window

Notice that we may get slightly less noise suppression, but in return we distort the PSF far less. In fact, at this level (MTF50 = 0.05) the distortion is negligible, and no further correction factors are required. This is the new apodization method employed by MTF Mapper.

LSF correction and beyond

As already mentioned, the finite-difference method used to calculate the PSF (or LSF, if you are pedantic) from the ESF is not identical to the ideal analytical derivative of the ESF. A sin(x)/(x) correction factor can be employed to effectively remove this distortion. The Imatest article on this topic does a fine job of explaining the maths behind this correction; the method was originally published by Burns while working at Kodac.

Since MTF Mapper employs 8x oversampling, we must divide the calculated MTF by the function sin(π * f/4)/(π * f/4). Clarification: This stems from the sample spacing that is 0.125 pixels. Plugging this into the finite-difference derivative calculation as explained in the Imatest article we see that for 8x oversampling we will have a correction factor of sin(π * f/4)/(π * f/4) as opposed to the sin(π * f/2)/(π * f/2) we would have had for 4x oversampling.

Even after applying this correction factor, though, we can see a systematic difference between the expected ideal MTF and the MTF produced by the slanted edge method. To understand this (final?) distortion, we have to rewind back to the step where we construct the ESF (helpfully captioned "Step 1" above...).

The projection used to form the dense ESF samples produces a dense set of points, but these points are no longer spaced at convenient regular intervals. The FFT rather depends on being fed regularly spaced samples, so the simplest solution is to bin the samples at our desired oversampling factor. An oversampling factor of 8x thus produces bins that are 0.125 pixels wide.

Again following the path of least resistance, we simply average all the values in each bin to obtain our regularly-sampled ESF. This seems like such a harmless little detail, but if we stop and think about it, we realize that this must be a low-pass filter. Why?

Well, consider first a continuous interpolation function passing through all the ESF samples before binning. We would like to sample this function at regular intervals (0.125 pixels, to be exact), but we know that point sampling will produce horrible aliasing artifacts. The correct approach is to apply a low-pass filter, i.e., convolve our interpolating function with some filter. Let us choose a simple box filter of width 0.125 pixels. If we first convolve the interpolating function with this box filter, and then point-sample at intervals of 0.125 pixels, we end up with exactly the same result as we would obtain from binning followed by averaging all the values in each bin. This approach is optimal in terms of noise suppression for a Gaussian noise source, so even though it sounds simplistic, it is a good solution.

Fortunately, this process is easily reversible by indiscriminate application of the convolution theorem: convolution in the time domain can be reversed by dividing the MTF (in the frequency domain) by the Fourier transform of our low-pass filter. And by now we know that the Fourier transform of a box filter is the sinc() function --- all we have to do is choose the proper frequency.

At 8x oversampling, our bin width is 0.125 pixels, resulting in a low-pass filter of rect(8x). In the Fourier domain, this means we must divide the MTF by sinc(π * f/8) --- this will effectively reverse the attenuation of the MTF induced by the low-pass filter.

To illustrate the effect of these two components (discrete derivative and binning low-pass filter) we can look at a simple example using a Gaussian PSF, with no added noise, and no apoditization. We start with the dense ESF of an edge with an MTF50 value of exactly 0.25 cycles/pixel:

Figure 1: Dense ESF

This ESF is binned into bins of width 0.125 pixels:

Figure 2: binned ESF

Next we calculate the discrete derivative to obtain the PSF:

Figure 3: discrete PSF

 This PSF is passed through the FFT to obtain the following MTF curve:

Figure 4: measured MTF curve

That MTF curve looks pretty good. And it looks very much like half of a Gaussian, just as we would expect. But looks can be deceiving at this scale. We know the true analytical MTF curve that we would expect: a Gaussian with a standard deviation of about 0.2123305 (and change). So next we plot the measured MTF curve divided by the expected MTF curve:

Figure 5: Uncorrected MTF ratio (red)

The dashed blue curve is the sin(π * f/4)/(π * f/4) function, corresponding to the discrete derivative correction, and the red curve is the ratio of measured to expected MTF. Clearly these two curves have roughly the same shape. Let us take our measured MTF curve, divide it by the sinc(f) curve to apply the discrete derivative correction, and plot the ratio of the corrected curve to the expected curve:

Figure 6: Partially corrected MTF ratio (red)

Note how the red curve (corrected MTF divided by expected MTF) has flattened out --- keep in mind that we would expect this curve to flatten out into a straight line. The black dashed line is the function sin(π * f/8)/(π * f/8), i.e., the Fourier transform of the rect(8x) low-pass filter induced by the binning process. Now we can combine the two corrections, i.e., take the measured MTF, divide by the discrete derivative correction, and then divide the result by the low-pass correction; this gives us the "fully corrected" MTF curve. Plotting the fully corrected MTF curve divided by the expected analytical MTF curve yields this:

Figure 7: Fully corrected MTF ratio (red)

The red curve is almost, but not quite, a constant value of 1.0. This demonstrates that the low-pass correction helps to bring us closer to the expected ideal MTF curve.

If we zoom out a bit on the last plot, we see things are not entirely rosy:

Figure 8: Fully corrected MTF ratio (red), wide view

Once we move past a frequency of 1 cycle per pixel, the corrected curve does not match the expected curve so well anymore, at least not when expressed as a ratio. But looking back at Figure 4 above, we see that the measured MTF curve is practically zero beyond 1 cyc/pixel anyway, so we should expect some numerical instability when dividing the measured curve by the expected curve. This also explains my choice of scale in a few of the plots above.

If we express the difference between the fully corrected curve and the expected analytical curve as a percentage of the magnitude of the analytical curve, we see that the fully corrected curve deviates only about 0.15% at 1 cyc/pixel, and only about 0.05% at 0.5 cyc/pixel (Nyquist). For reference, the relative deviation of a completely uncorrected curve is about 10% and 3% at 1 and 0.5 cyc/pixel respectively. Applying only the discrete derivative correction leaves a deviation of about 2.8% and 0.6%.

So adding the correction for the low-pass filter effect of the binning is definitely in the diminishing returns category, but I certainly aim to make MTF Mapper the most accurate tool out there, so no expense is spared.

Summary: The full correction to take care of both the finite-difference correction, and the removal of the attenuation induced by the low-pass filter (implicitly part of the binning operation) is the product of the two individual term, i.e.,

c(f) = sin(π * f/4)/(π * f/4) * sin(π * f/8)/(π * f/8),

The MTF curve is corrected by dividing by this correction factor.

Accuracy evaluation

To demonstrate the effect of the new apoditization and MTF correction approaches, we can look at the MTF50 accuracy over a range of MTF50 values. For each of the MTF50 levels shown below, a number of synthetic images were rendered without adding any simulated noise --- this is to emphasize the inherent bias in measured MTF50 values. All edges were kept at a relative angle of 4.5 degrees, with 30 repetitions rendered using small sub-pixel shifts of the rectangle.

Figure 9: Relative MTF50 deviation on a Gaussian PSF

Our three contestants are MTF Mapper v0.4.16, which employs a Hamming windowing function and empirical MTF curve correction, followed by an implementation that uses a Hamming window with only the discrete derivative correction, and finally the new implementation using a Tukey windowing function with both discrete derivative and binning low-pass corrections.

It is clear that the Hamming window + derivative correction (blue curve) produces a significant bias at low MTF50 values, raising their values artificially (as expected from the apparent narrowing of the PSF). Also note how the MTF50 values are underestimated at higher MTF50 values, which is again consistent with the effects of the binning low-pass filter.

Both the empirical correction method (red curve) and the new Tukey window plus full correction (black curve) display much lower bias in their MTF50 estimates, as seen in Figure 9.

What happens when we use a different PSF to generate our synthetic images? This time I chose the Airy + photosite aperture (square aperture, 100% fill factor) as a representative. This corresponds to something like a D7000 sensor without an OLPF, but without noise.

Figure 10: Relative MTF50 deviation on an Airy+box PSF

Firstly, we see some shockingly large errors on the low MTF50 side. The data points correspond to a simulated aperture of f/64, followed by f/32, f/16, f/8, f/5.6, f/4 and finally f/2.8. A reasonable explanation for the difference between the results in Figure 9 and 10 might be the wider support of the Airy PSF. Typically, the central peak of the Airy PSF is narrower than a Gaussian, but the Gaussian also drops off to zero more quickly, i.e., the Airy PSF has more energy in the tails of the PSF. This means that a wide (f/64) Airy PSF will be affected more strongly by the windowing function, and may even suffer from some truncation of the PSF --- this notion seems to be supported by the difference between the Tukey and Hamming window curves (black vs blue).

Interestingly the empirical correction performed better than expected, doing almost as well as the Tukey + full correction method. This is somewhat unexpected, since the empirical correction factors were calculated from a Gaussian PSF.

Since these experiments were all performed in the absence of simulated noise, they really only test the inherent bias of the various methods. The good news is that the Tukey + full correction approach appears to be an overall improvement over the existing empirical correction, even thought the improvement is really quite small.

Adding in some noise

It always makes sense to look at both bias and variance when comparing the quality of two competing models. In this spirit, the experiments above were repeated under mild noise conditions, corresponding to roughly ISO 800 on a D7000 sensor. First up, the Gaussian PSF:

Figure 11: Standard deviation of relative MTF error on Gaussian PSF

Figure 11 presents the standard deviation of the relative MTF50 error, expressed as a percentage. We see the impact of the Tukey windowing function quite clearly: since the Tukey window does not attenuate such a large part of the PSF (i.e., less of the edge of the PSF is attenuated), we see a small increase in the standard deviation of the relative error. As expected, both the methods using the Hamming window perform nearly identically.

Conclusion

MTF Mapper will employ the new apodization function (Tukey window) as well as the analytically-derived full correction in lieu of the older Hamming window + empirical correction, starting from the next release. This should be v0.4.17 onwards.

The new correction method is more elegant, and makes fewer assumptions regarding the shape of the MTF curve, unlike the empirical correction that was trained on only Gaussian MTFs. But throwing out the empirical correction brings back the strong attenuation of the PSF at lower MTF50 values, so the Hamming window had to be replaced with the Tukey window.

We pay a small price for using the Tukey window, but realistically the MTF50 error should remain below 5% (for an expected MTF50 value of 0.5 c/p) even under quite noisy conditions.

In theory it should be possible to incorporate strong low-pass filtering of the PSF, followed by suitable reversal-via-division of the low-pass filter in the frequency domain. In practice, I have not seen any worthwhile improvement in accuracy. I suspect that some non-linear adaptive filter may be able to strike the right balance, but that will have to wait for now.

Trust, but verify

A while back I wrote:
  "I could not find any synthetic images rendered with specific, exactly known point spread functions. This meant that the only way that I could tell if MTF Mapper was working correctly was to compare its output to other slanted edge implementations." (here)

This was the main motivation for developing mtf_generate_rectangle.

It turns out that Imatest recently updated their SFR measurement algorithm to include the well-known finite-difference-correction (here). I first encountered this correction in one of Burns' papers. According to the Imatest news article, this correction is now included in the ISO 12233:2014 standard.

I have yet to test the new version of Imatest against the synthetic images produced by mtf_generate_rectangle, but I do recall that some quick-and-dirty testing a few years back hinted at Imatest underestimating MTF50 slightly, which would be consistent with an algorithm that does not apply the finite difference correction. As pointed out in the Imatest news article, this difference is really only noticeable when dealing with higher MTF50 values, so this does not imply that all older Imatest results are now suddenly obsolete.


It does raise an important point about traceability and independent verification, though.

Analogue image zoom: comparing 6 megapixel images with 16 megapixel images

The problem

Let us say you have captured a shot of a test chart with a D40, and repeated the process (same lens) with a D7000. The D40 gives you a 6 megapixel image, and the D7000 gives you a 16 megapixel image. You would like to compare the sharpness of the one camera to that of the other.

There several options for executing this comparison:

1. Print both shots at the same size. This is probably the way to go if you intend to print a lot of uncropped photos.
2. Scale down the 16 MP image to 6 MP, and compare at 100% view.
3. Scale up the 6 MP image to 16 MP, and compare at 100% view.
4. Scale both images to some other resolution, e.g., 8 MP (like DxO labs do), or maybe 24 MP.

There is at least one sound reason why option 4 is the better choice amongst options 2 through 4: scaling artifacts. Performing an MTF analysis of an image upscaled with a popular cubic scaling algorithm (Mitchell) reveals that there is some effective contrast enhancement that takes places as part of the scaling process, visible as overshoot and undershoot in an edge profile plot. By scaling both images, you are at least trying to compare apples to apples, especially if you are unsure of exactly what sharpening algorithm your software will employ.

Of course, this entire post deals with visual interpretation of test chart images. If you are interested in other properties (e.g., MTF) then go ahead and use MTF Mapper to perform such measurements directly. The normal slanted edge MTF analysis does not really tell you what your aliasing will look like after dropping the OLPF from your sensor, nor how apparent sharpness is influenced by demosaicing algorithms. For such evaluations visual interpretation might prove useful still.

Another option: simulation

Once you embrace simulated images, such as those produced with mtf_generate_rectangle, you have a fifth option: directly produce a 16 MP (equivalent) image but keep the point spread function (PSF) of the 6 MP camera. I call this feature "analogue scaling", mostly because it effectively resamples the 6 MP image to 16 MP, but without using a discretized 6 MP image as the source. Instead, the usual "infinite precision" analytical description of the target scene is simply scaled down (relative to the photosite pitch), and the sample spacing of the rendered image is adjusted accordingly.

Here is a comparison between a simulated D40 (photosite pitch 7.8 micron, f/4, green light, 4-dot OLPF) and a D7000 (photosite pitch 4.73 micron, f/4, green light, 4-dot OLPF):

Simulated D40 image, effectively magnified by a factor of ~1.65 (click for full-size)

Simulated D7000 image (click for full-size)

These images were generated with the following commands:

mtf_generate_rectangle.exe --target-poly doc/pinch.txt -p airy-box -n 0 --analogue-scale 0.606410 --pixel-pitch 7.8 --aperture 4 -o pinch_d40.png

and

mtf_generate_rectangle.exe --target-poly doc/pinch.txt -p airy-4dot-olpf -n 0  --pixel-pitch 4.73 --aperture 4 -o pinch_d7k.png

respectively. Note that the analogue scale factor is ~0.606, which is 4.73/7.8, i.e., the ratio between the photosite pitch of the D7000 and D40. Specifying an --analogue-scale factor of greater than 1.0 will produce aliasing (and an apparent increase in sharpness), while a factor of less than 1.0 will produce smoothing, as would be expected from upscaling.

Note that the "-n 0" switch turns off simulated sensor noise. Since sensor noise is currently computed in the domain of the output image, this switch is required to produce a correct pair of images. If noise is left on, you would obtain a scaled D40 image with image noise appearing at the size of D7000 pixels, which will clearly cause the D40 image to appear better than it should. This can be fixed (in the mtf_generate_rectangle code) by scaling the "noise image" correctly, but I honestly only thought of this problem now as I am busy writing this blog post :)

Discusssion

Does this approach work? Well, take a look at the point where the converging lines blur into a gray mess in the D40 image (top image above). This appears to happen after the tick marked "2" in the horizontal set of lines --- maybe about one-third of the way from "2" to "1".

In the D7000 image, the extinction point (gray mess) appears almost exactly at the tick marked "1" in the horizontal set of converging lines. This appears about right, since we know the linear resolution of the D40 is about 0.606 that of the D7000. Not really a rigorous proof, but at least reassuring.

To summarize: the --analogue-scale option of mtf_generate_rectangle will allow you to produce a pair of synthetic images of a test chart to simulate two different cameras, with different photosite pitch values, but without the hassle or potential artifacts introduced by upscaling the discrete image produced by the lower-resolution camera.

Of course, this type of simulation will allow you to investigate potential future sensors too. How would a 50 MP APS-C camera render a resolution test chart .... ?

ps: MTF Mapper version 0.4.16 is finally available here --- this is the first version to support all the required features to produce the results found in this post.

mtf_generate_rectangle grows up

Fed up with squares?

If you have used mtf_generate_rectangle before you will know why it is called mtf_generate_rectangle. A bit over two years ago, when I started working on the first release of MTF Mapper, I ran into a specific problem: I could not find any synthetic images rendered with specific, exactly known point spread functions. This meant that the only way that I could tell if MTF Mapper was working correctly was to compare its output to other slanted edge implementations.

While this is sufficient for some, it did not sit well with me. What if all those other implementations were tested in the same way? If that was the case, then all slanted edge implementations (available on the Internet) could be flawed. Clearly, some means of verifying MTF Mapper independently of other slanted edge algorithm implementations was required.

Thus mtf_generate_rectangle was born. The original implementation relied on sampling a dense grid, but quickly progressed to an importance sampling rendering algorithm tailored to a Gaussian PSF. The Gaussian PSF had some important advantages over other (perhaps more realistic) PSFs: the analytical MTF curve was know, and simple to compute (the MTF of a Gaussian PSF is just another scaled Gaussian). Since the slanted edge algorithm requires a step edge as input, it seemed logical to choose a square as the target shape; this would give us four step edges for the price of one.

Such synthetic images, composed of a black square on a white background, are perfectly suited to the task of testing the slanted edge algorithm. Unfortunately, they are not great for illustrating the visual differences between different PSFs. There are a few well-know target patterns that are found on resolution test charts designed for visual interpretation. The USAF1951 pattern consists of sets of three short bars (see examples later on); the width of these bars are decreased in a geometric progression, and the user is supposed to note the scale at which the bars are no longer clearly distinguishable.

Another popular test pattern is the Siemens star. This pattern comprises circular wedges radiating from the centre of the design. The main advantage of the Siemens star is that resolution (spacing between the edges of the wedges) decreases in a continuous fashion, as opposed to the discrete intervals of the USAF1951 chart. I am not a huge fan of the Siemens star, though, mostly because it is hard to determine the exact point at which the converging bars (wedges) blur into a gray mess. It is far too easy to confuse aliasing with real detail on this type of chart. Nevertheless, other people seem to like this chart.

Lastly, there is the familiar "pinched wedge" pattern (also illustrated later in this post), which contains a set of asymptotically convergent bars. The rate of convergence is much slower than the Siemens star, and a resolution scale usually accompanies the pattern, making it possible to visually measure resolution in a fashion similar to the USAF1951 chart, but with slightly more accuracy. I rather like this design, if only for the fact that the resulting pictures are aesthetically pleasing.

Today I announce the introduction of a fairly powerful new feature in mtf_generate_rectangle: the ability to render arbitrary polygon shapes.

The implementation

You can now pass fairly general polygonal targets using the "--target_poly <filename>" command line option. The format of the file specified using <filename> is straightforward: any number of polygons can be specified, with each polygon defined by an integer <n> denoting the number of vertices, followed by <n> pairs of <x,y> coordinates. I usually separate these components with newline characters, but this is not critical.

The polygons themselves can be convex or concave. In theory, non-trivial self intersections should be supported, but I have not tested this myself yet. There is currently no way to associate multiple contours with a single polygon, thus you cannot specify any polygons containing holes. I work around this by simply splitting the input polygons with a line passing through such a hole: for example, a polygon representing the number "0" can be split down the middle, producing two concave polygons that touch on the split line.

General polygon intersections

For a while now I have cheated by relying on the Sutherland-Hodgeman algorithm to compute the intersection between two polygons. Specifically, this operation is required by all the importance sampling algorithms involving a non-degenerate photosite aperture (e.g., "airy-box" and "airy-4dot-olpf" PSF options specified with the "-p" command to mtf_generate_rectangle). This article explains the process in more detail, but the gist is that each "sample" during the rendering process is proportional to the area of the intersection between the target polygon geometry and a polygon representing the photosite aperture (suitably translated). If we assume that the photosite aperture polygon is simply a square (or more general, convex) then we can rely on the Sutherland-Hodgeman algorithm to compute the intersection: we simply "clip" the target polygon with the photosite aperture polygon, and compute the area of the resulting clipped polygon.

Now this is where the cheat comes in: the clipped result produced by the Sutherland-Hodgeman algorithm is only correct if both polygons are convex. If the target polygon (the clipee) is concave, and the clipping polygon is convex, the Sutherland-Hodgeman algorithm may produce degenerate vertices. (see figure 1 below). The cheat that I employed relied on the observation that degenerate sections of a polygon have zero area, thus they have no influence on the sampling process.

Fig 1: Clipping a concave polygon with the Sutherland-Hodgeman algorithm

This allowed me to continue using the Sutherland-Hodgeman algorithm, mostly because the algorithm is simple to implement, and very efficient. This efficiency stems from the way in which an actual intersection vertex is only computed if an edge of the clipee polygon is known to cross an edge of the clipper polygon. This is a huge saving, especially if one considers that the photosite aperture polygon (clipper) will typically be either entirely outside the target polygon, or entirely inside the target polygon, except of course near the edges of the target polygon.

All this comes apart when the photosite aperture polygon becomes concave. To solve that problem requires significantly more effort. For a start, a more general polygon clipping algorithm is required. I chose the Greiner-Hormann algorithm, with Kim's extensions to cater for the degenerate cases. In this context, the degenerate cases occur when some of the vertices of the clipee polygon coincide with vertices (or edges) of the clipper polygon. This happens fairly often when constructing a quadtree (more on that later). At any rate, the original Greiner-Hormann algorithm is fairly straightforward to implement, but adding Kim's enhancements for handling the degenerate cases required a substantial amount of effort (read: hours of debugging). The Greiner-Hormann algorithm is quite elegant, and I can highly recommend reading the original paper.

Internally, mtf_generate_rectangle classifies polygons as being either convex or concave. If the photosite aperture is convex, the Sutherland-Hodgeman algorithm is employed during the sampling process, otherwise it will fall back to Kim's version of the Greiner-Hormann algorithm. The performance impact is significant: concave photosite polygons render 20 times more slowly than square photosite polygons when rendering complex scenes. For simpler scenes, the concave photosite polygons will render about four times more slowly than squares; circular (well, 60-sided regular polygons, actually) will render about two times more slowly than squares.

Part of this difference is due to the asymptotic complexity of the two clipping algorithms, expressed in terms of the number of intersection point calculations: the Sutherland-Hodgeman algorithm has a complexity of O(c*n), where "c" is the number of crossing edges, i.e., c << m, where "m" is the number of vertices in the clipee polygon, and "n" is the number of edges in the clipper. The Greiner-Hormann algorithm has a complexity of O(n*m); on top of that, each intersection vertex requires a significant amount of additional processing.

Divide and conquer

To offset some of the additional complexity of allowing arbitrary target polygons to be specified, a quadtree spatial index was introduced. The quadtree does for 2D searches what a binary tree does for linear searches: it reduces the number of operations from O(n) to O(log(n)).

First up, each polygon is wrapped with an axis-aligned bounding box (AABB), which is just an educated-sounding way of saying that the minimum and maximum values of the vertices are recorded for both x and y dimensions of a polygon. This step already offers us a tremendous potential speed-up, because two polygons can only intersect if their bounds overlap. The bounds check is reduced to four comparisons, which can be implemented using short-circuit boolean operators, so non-overlapping bounds can be detected with as little as a single comparison in the best case.

Once each individual polygon has a bounding box, we can start to aggregate them into a scene (internally, mtf_generate_rectangle treats this as a multipolygon with its own bounding box). The quadtree algorithm starts with this global bounding box, and splits it into four quadrants. The bounding box of each quadrant is taken as a clipping polygon, clipping all the polygons to fit exactly inside the quadrant.

After one iteration, we have potentially reduced the number of intersection tests by a factor of four. For example, if we determine (using the bounding boxes) that the photosite aperture polygon falls entirely inside the top-right quadrant, then we only have to process the (clipped) polygons found inside that quadrant. If a quadrant is empty, we can simply skip it; otherwise, we can shrink the bounding box to fit tightly around the remaining clipped polygons (see figure 2 below).

The next logical step is to apply this quadrant subdivision recursively to each of the original quadrants. We can keep on recursively subdividing the quadrants until a manageable number of polygons (or more correctly, a manageable number of polygon edges) is reached in each quadrant subtree. We must balance the cost of further subdivision against the gains of reducing the number of edges in each subdivided quadrant. Every time that we add another level to the quadtree we add four additional bounds checks --- eventually the cost of the bounds checks add up.

Fig 2: Levels 0 (green), 1 (blue) and 2 (magenta) of the Quadtree decomposition of the scene (light gray)

Fig 3: Levels 2 (green), 5 (blue), and 6 (magenta) of the Quadtree decomposition

If the number of quadtree levels is sufficient, we end up "covering" the target polygons with rectangular tiles (the bounding boxes of the quadrants), providing a coarse approximation of the target polygon shape (see figure 3 above). Every sampling location outside these bounding boxes can be discarded early on, so rendering time is not really influenced by the size of the "background" any more.

If the quadtree is well-balanced, the amount of work (number of actual polygon-polygon intersection tests) can be kept almost constant throughout the entire rendered image, regardless of the number of vertices in the scene. I have confirmed this with some quick-and-dirty tests: halving the number of vertices in a scene (by using a polygon simplification method) has almost no impact on rendering time.

Some examples

Enough talk. Time for some images:

USAF1951-style chart with 4 levels

Siemens star chart

Pinch chart (click for full size)

All the charts above were rendered with a photosite pitch of 4.73 micron, using the Airy + square photosite (100% fill-factor) model at an aperture of f/4, simulating light at 550 nm wavelength. The command for generating the last chart would look something like this:

mtf_generate_rectangle.exe --pixel-pitch 4.73 --aperture 4 -p airy-box -n 0 --target-poly pinch.txt 

where "pinch.txt" is the file specifying the polygon geometry (which happens to be in the same folder as mtf_generate_rectangle.exe in my example above). These target polygon geometry files are included in the MTF Mapper package from version 0.4.16 onwards (their names are usaf1951r.txt, siemens.txt, and pinch.txt.)

OLPF demonstration

The "pinch chart" provides a very clear demonstration of the effects of the Optical Low-Pass Filter (OLPF) found on many DSLRs (actually, most, depending on when you read this).

Before I present some images, first a note about effective chart magnification. Most real-world test charts are printed at a known size, i.e., you can say with confidence that a particular target (say, a USAF1951 pattern) has a known physical size, and thus measures physical resolution expressed in line pairs per millimetre (lp/mm). It is relatively straightforward to extend this to synthetic images generated with mtf_generate_rectangle by carefully scaling your target polygon dimensions. For the time being, though, I prefer to fall back to a pixel-centric view of the universe. In other words, I chose to specify my target polygon geometry in terms of pixel dimensions. This was mostly motivated by my desire to illustrate specific effects (aliasing, etc.) visually. Just keep that in mind: the images I present below are not intended to express resolution in physical units; they are pretty pictures.

With that out of the way, here is a sample of a hypothetical D7000 without an OLPF --- this could be something like the Pentax k5-IIs.

Hypothetical D7000 without OLPF, f/4

And here is the same simulated image, but this time using an OLPF, i.e., this should be quite close to the real D7000:

D7000 (with OLPF), f/4

I repeated the simulations using an f/8 aperture:

Hypothetical D7000 without OLPF, f/8

and again, the D7000 (with OLPF) simulated at f/8:

D7000 (with OLPF), f/8

Here is a crop comparing the interesting part of the chart across these four configurations:

First up, notice the false detail in the "f/4, no OLPF" panel, occurring to the right of the scale bar tick labelled "1". This is a good example of aliasing --- compare that to the "f/4, OLPF" panel, which just fades to gray mush to the right of its tick mark. In the bottom two panels we can see the situation is significantly improved at f/8, where diffraction suppresses most of the objectionable aliasing.

Simulating microlenses: kicking it up a notch

Preamble

My first stab at simulating microlenses made some strong assumptions regarding the effective shape of the photosite aperture. Reader IlliasG subsequently pointed me to an illustration depicting a more realistic photosite aperture shape --- which happens to be a concave polygon.

At first, it might seem trivial to use this photosite aperture shape in the usual importance sampling algorithm employed by mtf_generate_rectangle. It turns out to be a bit more involved than that ....

The mtf_generate_rectangle tool relied on an implementation of the Sutherland-Hodgeman polygon clipping routine to compute the area of the intersection of the photosite aperture and the target polygon (which is typically a rectangle). The Sutherland-Hodgeman algorithm is simple to implement, and reasonably efficient, but it requires the clipping polygon to be convex, so I required a new polygon clipping routine to allow concave/concave polygon intersections (astute readers may spot that I could simply exchange the clipping/clippee polygons, but I wanted concave/concave intersections anyway). After some reading, it seemed that the Greiner-Hormann algorithm had a fairly simple implementation ...

... but it did not handle the degenerate cases (vertices of clipping/clippee polygons coinciding, or a vertex falling on the edge of the other polygon). Kim's extension solves that problem, but it took me a while to implement.

Effective photosite aperture (with microlenses)

The Suede (on dpreview forums) posted a diagram of the effective aperture shape after taking the microlenses into account. I thumb-sucked an analytical form for this shape, which looks like this (my shape in cyan overlaid on The Suede's image):

The fit of my thumb-sucked approximation is not perfect, but I declare it to be good enough for government work. I decided to call this the rounded-square photosite aperture (that is the identifier used by mtf_generate_rectangle).

I am not sure how to scale this shape relative to the 100% fill-factor square. Intuitively, it seems that the shape should remain inscribed within the square photosite, or otherwise the microlens would be collecting light from the neighbouring photosites too. This type of scaling (as illustrated above) still leaves the corners of the photosite somewhat darkened, which is what we were aiming for. Incidentally, this scaling only gives me a fill-factor of ~89.5%. I guess the "100% fill-factor" claim sometimes seen in connection with microlenses applies to equivalent light-gathering ability, rather than geometric area.

Results

MTF curves for 0-degree step edge

MTF curves for 45-degree step edge

The two plots above illustrate the MTF curves of three possible photosite aperture shapes, combined with an Airy PSF (aperture=f/5.6, photosite pitch=4.73 micron, lambda=550 nm). The first plot is obtained by orienting the step edge at 0 degrees, i.e., our MTF cross-section is along the x-axis of the photosite. In the second plot, the step edge was oriented at 45 degrees relative the photosite, i.e., it represents the diagonal across the photosite.
Both plots include the MTF curves for an inscribed circle aperture, for comparison. Note that the fill-factors have not been normalized, that is, each aperture appears at its native size, which maximizes aperture area without going outside the square photosite's bounds.

Purely based on its fill factor of ~90%, we would expect the first zero of the rounded-square aperture's MTF curve to land between the 100% fill-factor square and the 78% fill factor circle, which is clearly visible in the first plot. In fact, the rounded-square aperture's MTF curve appears to be a blend of the square and circle curves, which makes sense.

The second plot above shows that the rounded-square aperture still exhibits some anisotropic behaviour, but that the effect is less pronounced than that observed with a square photosite (see this article for more details on anisotropic behaviour); this also seems logical given the shape.

In the real world (well, simulated real world, at least)

The MTF curves show some small but measurable differences between the 100% fill-factor square photosite aperture and the ~90% rounded-square photosite aperture response to a step edge. But can you see these differences in an image?

USAF1951-style chart, f/1.4, 100% fill-factor square photosite aperture

USAF1951-style chart, f/1.4, ~90% fill-factor rounded square photosite aperture

Well ... not really (click on the image to see full-size version). I even opened up the aperture to f/1.4 to accentuate the differences in the photosite apertures. Just to show you something, here is a rendering using a highly astigmatic photosite aperture (a rectangle that is 0.01 times the photosite pitch in height, but one times the pitch wide):

USAF1951-style chart, f/1.4, 2% fill-factor thin rectangular photosite aperture

Note that this is basically point-sampling in the vertical direction, but box-sampling in the horizontal direction. This shows up as rather severe aliasing (jaggies) in the vertical direction.

In the real real world

So how do these simulated MTF curves compare to actual measured MTF curves? In a previous post I described the method I used to capture the MTF of a Nikon D40 camera with a sharp lens set to an aperture of f/4. Here is a comparison of the simulated MTF curves to the empirically measured MTF curve.

Nikon D40 at f/4

At first glance it might seem that the 100% fill-factor square photosite aperture simulation is marginally closer to the measured curve, but keep in mind that these simulations were both performed with an OLPF split factor of 0.375. This value of 0.375 was determined by trial and error using the 100% fill-factor photosite simulation --- it is likely that the optimal OLPF split factor for the rounded-square photosite aperture model is different. In fact, I would expect a slightly larger value, say around 0.38 or 0.385 to perform better, purely on the difference in fill factor (100% vs ~90%) between the two simulations.

So yes, you could say I am lazy for not optimizing the OLPF split factor for the rounded-square photosite aperture model right now, but I do not feel comfortable doing any sort of quantitative comparison between the models with only one empirical sample at hand (one measured D40 MTF curve). Until such time as I have sufficient data to perform a proper optimization and evaluation of the models, I will leave it at the following statement: it certainly appears that the rounded-square model is a viable approximation of the photosite aperture of the D40.

Simulating microlenses, first take.

Up to now, mtf_generate_rectangle assumed that the simulated sensor had square pixels with a 100% fill factor. This assumption does not reflect reality all that well, but it does simplify the derivation of analytical MTF curves for certain cases.

The effect of fill factor on a square photosite (assuming that the active part of the photosite is just a smaller square centred in the outer square representing the photosite) is fairly straighforward: we are keeping the sampling rate the same, since the photosite pitch is unaffected, but we are reducing the size of the square being convolved with the incoming image. As a result, we would expect a lower fill factor to yield a better MTF curve, i.e., contrast will be higher than the 100% fill factor baseline. But it is still a good idea to test this, just to be sure ...

Implementing variable fill factors

Using the importance sampling algorithm described here, all we have to do is replace the square polygon representing the active area of the photosite with a smaller one, and we are done. The resulting PSF is thus the convolution of the photosite aperture and the Airy function (representing diffraction through the lens aperture). Unless otherwise stated, results were obtained at a wavelength of 550 nm, a photosite pitch of 4.73 micron, and an aperture of f/8, using a simulated system without an optical low-pass filter (OLPF), which appears to be all the rage lately.

MTF curve of Airy + square photosite PSF, at 100% and 50% fill factors

This result confirms our suspicions: if we decrease the fill factor by shrinking the square photosite aperture, the cut-off frequency of the low-pass sinc() filter is increased correspondingly (see here for an overview of diffraction and box functions). The MTF50 of the 50% fill factor sensor is ≈0.38, compared to an MTF50 of ≈0.34 for the 100% fill factor case.

So what are the downsides to using a smaller fill factor? Well, we are allowing substantially more contrast through above the Nyquist frequency (0.5 cycles per pixel), which will definitely increase the chances of aliasing artifacts (moiré, and/or "jaggies"). In the limit, we can imagine the fill factor approaching zero, which gives us a point-sampler, which will result in severe aliasing artifacts, such as the typical jagged edges we see when we render a polygon by taking only one sample at the centre of each pixel.

There is another effect that photographers care deeply about: noise. The relative magnitude of photon shot noise increases inversely with fill factor, since the photon shot noise is directly proportional to the active area of the photosite. The simulation above was conducted with zero noise, mostly to illustrate the pure geometric effects of the fill factor.

Speaking of geometric effects, a slight diversion into the interaction between edge orientation and photosite aperture shape is in order.

Square photosites are anisotropic

It is rather important to recall that an MTF curve is only a 1D cross-section of the true 2D MTF. If the 2D MTF is radially symmetric (e.g., the Airy MTF due to a circular lens aperture), then the orientation of our 1D cross-section is irrelevant.

The 2D sinc() function representing the MTF of a square aperture is not radially symmetric, hence the 1D MTF curve is only representative of the specific orientation that was chosen. The results in this post were all derived using a combined Airy and photosite aperture simulation; since the Airy MTF is radially symmetric, and the photosite aperture MTF is not, we can expect the combined system MTF to lack perfect radial symmetry. The question remains, though: is the combined MTF symmetric enough to ignore this matter entirely?

Feeling somewhat lazy today, I chose to evaluate this empirically, rather than deriving the analytical combined MTF at arbitrary orientations. Since we can directly simulate the edge spread function of a given PSF using mtf_generate_rectangle, I decided to vary the orientation of the simulated step edge relative to the simulated photosite grid, which is equivalent to taking our 1D cross-section of the 2D MTF at the chosen orientation.

Before we get to the results, first some predictions: We saw that the first zero of the sinc() low-pass filter of the square photosite aperture moved to a higher frequency when we decreased the fill factor. Intuitively, a wider photosite aperture produces stronger low-pass filtering. The length of the diagonal of a square is √2 × side_length, so we might expect a stronger low-pass filtering effect if the step edge is parallel to a diagonal of the square photosite aperture. And now the results ...

MTF curves of a square photosite (plus diffraction) at different edge orientations

Notice that there is a minute difference: the 45-degree edge orientation produced a slightly weaker low-pass filtering effect!
Subtracting the 45-degree MTF curve from the 0-degree MTF curve gives us a better view of the difference:

MTF difference between 0-degree edge and 45-degree edge

The difference certainly appears to by structured, and not in the expected direction. Well, certainly not the direction that I expected.

Fortunately the explanation is relatively simple. Consider the following diagram:

Representation of the area of the photosite (orange) covered by the step edge (blueish), for 0-degree and 45-degree edge orientations

If w represents the side length of our square, then the left-hand diagram shows us that the area covered by the 0-degree step edge is simply t × w over the range 0 < t < w/2. The right-hand diagram illustrates that the area covered by the 45-degree step edge (bluish rectangle) is √0.5 × t × t, over the range 0 < t < √0.5 × w (in both cases we only have to integrate up to the midpoint to study the behaviour in question). The area covered by the step edge can be plotted as functions:

We can see that although the 45-degree case starts out with a lead (the first part of the corner starts at roughly -0.2071 if we align them so that they reach an area of 0.5 simultaneously), the 0-degree case catches up near t=0.1. From that point onwards, the 0-degree step edge covers a larger part of the photosite aperture than the 45-degree step edge does. In practise, this means that although the 45-degree case is technically "wider", the 0-degree case presents a stronger low-pass filter. Keep in mind that on top of this rather small difference due to the anisotropy of the square photosite aperture, we are blending in the radially symmetric Airy MTF, which further suppresses the anisotropy.

The size of this effect is minute, as can be seen in the MTF difference diagram above. The MTF50 values are ≈0.3407 and ≈0.342 for the 0-degree and the 45-degree cases, respectively. In conclusion, we see that the anisotropy of the square photosite aperture is mostly masked by the strong isotropy of the Airy MTF at f/8. At larger apertures, the anisotropy is likely to be more apparent, but further analyses will be performed with a step edge orientation of 0 degrees only.

Approximating microlenses

It has been suggested that the microlenses alter the effective shape of the active area of a photosite. (For example, reader IlliasG contributed this info here). A regular polygon approximating a circle seems to be a reasonable starting point for simulating more realistic microlenses. Similar to the fill factor implementation, this merely requires swapping out the polygon used to specify the geometry of the active part of the photosite, and performing importance sampling as usual. (If you can point me at a more accurate description of the effective shape of the combined microlens and photosite aperture, I would be happy to incorporate that into MTF Mapper).

Before we look at the results, first a prediction: modelling the active area of the photosite as a circular disc, we should see a net decrease of the geometric fill factor, hence the low-pass filtering effect is expected to decrease. 

MTF curve of square photosite aperture (1x1) versus circular photosite aperture (radius 1)

No real surprises in these results. For a circular photosite aperture, I chose the inscribed circle to the square photosite, since this seemed more reasonable. Note that the fill factor of the circular photosite aperture is ≈78.4%, rather than the expected π/4 ≈ 0.7854, because I approximated the circle as a 60-sided regular polygon. So how much of the difference between the 100% fill factor square aperture and the 78% fill factor circular aperture is due directly to fill factor, and how much is due to the actual shape?

By subtracting the MTF curves as indicated in the legend of the plot above, we can see that, after matching the effective fill factor, the remaining differences are quite small. From the red dashed curve we can see that the circular (well, 60-sided regular polygon) photosite aperture behaves isotropically, whereas the 78% fill factor square photosite aperture still exhibits anisotropy (dashed blue curve).

Conclusion

I have not performed sufficient experiments to make any inferences regarding behaviour at larger apertures, but at f/8 on a 4.73 micron pitch, it definitely appears as if the geometric fill factor of the photosite is responsible for the bulk of the difference between a 100% fill factor square photosite and a 78% fill factor inscribed circular photosite aperture.

Once we match the effective fill factors, the difference between the square aperture and the circular aperture are of the same magnitude as the differences due to the anisotropy of the square aperture. At larger apertures, we should see more significant differences, but at f/8 the differences are not as significant as one might suspect.

I would like to revisit my D40 experiment armed with the new fill factor and photosite geometry functionality in MTF Mapper. Stay tuned for that!

MTF Mapper will include new options for controlling photosite aperture fill factor and shape from version 0.4.16 onwards, which should be released relatively shortly.

How sharpness interacts with the accuracy of the slanted edge method

How MTF50 error varies with sharpness (click for a larger version)

Just a brief post to show how the absolute error in MTF50 measurement increases with increasing MTF50 values. The chart above is a box plot of the the MTF50 error at a range of MTF50 values.

Before we jump into a discussion of the chart itself, I would like to quickly explain how these values were obtained. Inside the MTF Mapper package you will find a tool called mtf_generate_rectangle.exe (in the Windows distribution). This tool generates synthetic images comprising a black rectangular target on a white background, i.e., exactly like the blocks you see in typical test charts (e.g., Imatest charts). These synthetic images simulate a specified point spread function, optionally adding some realistic sensor noise to create a synthetic image that is quite close to that which you would be able to capture with your actual camera. Since the point spread function controls the resulting MTF50 value of the image, we can choose to generate an image with an exact, known MTF50 value. The chart above is thus obtained by generating a large number of synthetic images at each of the MTF50 levels indicated on the x-axis. The MTF50 error is just the difference between the known MTF50 value of a given synthetic image, and the actual MTF50 value measured by MTF Mapper on the same image. By generating a number of images at each MTF50 level, each image with a pseudo-random noise component that differs slightly from the other images at the same MTF50 level, we obtain the distribution of MTF Mapper's measurement error at the given MTF50 level. With that out of the way, what can we learn from the chart?

The black bar in the centre of each red box is the median error, which stays fairly close to zero. This is good news, since it means that on average MTF Mapper measurements are unbiased.

The red box itself gives an indication of the spread of the MTF50 measurement error. The most important message here is that the absolute MTF50 measurement error increases with the nominal MTF50 level. If you have a sharp lens, the absolute measurement error (in cycles per pixel, or line pairs per mm) will be greater than that of a soft lens. In my experience, a sharp lens will have an MTF50 value of about 0.25 cycles per pixel or higher when perfectly focused.

If we divide the MTF50 error by the MTF50 level to obtain the relative error (e.g., the percentage error), we still see the same trend of increasing relative error with increasing MTF50 level.  I did not include a plot of that, but MTF Mapper's measurement error remains below 5% at real-world noise levels all the way up to an MTF50 value of 0.5 cycles per pixel. You will never obtain MTF50 values that high from a normal DSLR. For a more realistic value of about 0.3 cycles per pixel (a really, really sharp lens), MTF Mapper's relative measurement error will remain below 2% at real-world noise levels.

The bottom line: it is harder to obtain an accurate MTF50 estimate of a sharp lens than it is to do so for a soft lens. In reality, this means you have to evaluate more samples (images) for sharp lenses than for soft lenses.

What about Imatest or DxOLabs measurements?

I do not own a copy of either, so I could not test their software comprehensively using the same method. I can tell you that other freely available slanted edge implementations (e.g., Mitre) behave in exactly the same way as MTF Mapper did on the same synthetic images.

Looking a the maths behind the slanted edge method, I would expect that all implementations should behave exactly like MTF Mapper in this regard, i.e., the measurement error increases with increasing MTF50 values. This follows directly from the steeper slope we see in the MTF curve of a sharp lens, which means that the MTF50 value is more sensitive to small observation errors, such as those caused by sensor noise.

DxO uses a different method of computing sharpness, but ultimately they end up evaluating the MTF curve as well, so their method is likely to be similarly affected by increasing sensitivity to sensor noise with increasing nominal sharpness.

How to obtain your own copy of MTF Mapper

MTF Mapper is a free-as-in-beer Open Source project, currently hosted on Sourceforge.net. You can download pre-built binaries for both Windows and Ubuntu Linux, as well as the source code if you like.