Bug ID: JDK-4990624 REGRESSION: Image pipeline heuristics for choosing transform code are too strict

Type: Bug
Component: client-libs
Sub-Component: 2d
Affected Version: 5.0

Priority: P3
Status: Resolved
Resolution: Fixed
OS: generic
CPU: generic

Submitted: 2004-02-07
Updated: 2004-02-20
Resolved: 2004-02-20

Other
5.0 b40Fixed

Recently a fix was integrated for bug 4916948 which causes the
image rendering pipeline to invoke the image transformation code
when there is a chance that the sub-pixel positioning of the pixels
might make them subject to interpolation or to slight changes in
the sampling of the sources pixels.

Unfortunately the new decisions are incredibly strict and basically
reject any transform that does not map an image to exact pixel
boundaries with no leeway for any sub-pixel positioning.  This very
strict cutoff is not realistic for a couple of reasons:

	- Often transforms are the result of a number of
	  smaller operations which result in scale or
	  translation components that are very slightly
	  off from exact integer numbers even though
	  the intent is to end on a whole number.

	- Even if the transform numbers are off by a tiny
	  amount, these very tiny sub-pixel variations
	  may not result in changes to either the pixel
	  sampling of the original image or in the
	  blending of adjacent pixel values for interpolated
	  image transforms since most image operations are
	  performed in a discrete 8-bit per color component
	  mathematical space.  If the sub-pixel positioning
	  is not off by more than 1 out of an 8-bit number
	  then the results of the interpolation calculation
	  will be identical anyway.

The test case for bug 4989837 demonstrates one problem that can
arise when what should be a simple copy operation is instead
implemented using a full image transformation operation.  A
more widely observable result will be the poorer performance
of many operations that used to map to a simple image copy but
which now go through the much slower image transformation,
even if the quality problems seen in 4989837 are not visible
to the user in those cases.  Such performance losses could
be a serious regression for users who require fast image
operations.

CONVERTED DATA BugTraq+ Release Management Values COMMIT TO FIX: tiger-beta2 FIXED IN: tiger-beta2 INTEGRATED IN: tiger-b40 tiger-beta2

14-06-2004

SUGGESTED FIX Change the tests that verify that a transform results in either an integer scale or an integer pixel-for-pixel copy to use a larger cutoff for pixel precision. Instead of requiring: roundedIntegerCoordinate == floatCoordinate use a formula more like: Math.abs(roundedCoord - floatCoord) <= smallEpsilon where a smallEpsilon of 1.0/256.0 might be reasonable for detecting interpolation variations on 8-bit images and some other value might work well for detecting whether the source pixel sampling math will choose different source pixels for nearest neighbor mode.

11-06-2004

EVALUATION The code in the suggested fix section is easy enough to add to the Image pipeline, but we need to think a little more about the exact epsilon that can rule out visible changes in the interpolation or pixel sampling equations. ###@###.### 2004-02-06 Attempts to calculate a lower bound for the sub-pixel error allowed in positioning in deciding between a simpler integer-based operation or a more expensive floating point based full image scale yielded the following analysis: [Note that all of the decisions we are referring to below are made in the final stages of the image pipeline when the mapping to actual device pixels is known. Thus small deviations from integer coordinates represent distances of only a tiny fraction of a pixel and are not subject to being zoomed up by any scaling further along in the pipeline.] For interpolated scaling operations, the amount by which you can move an image before it changes the resulting blended pixels is really a factor of how much precision would be used in blending the pixels. The current implementation of the 2D API really only supports a max of 8-bits per component so the components would only exhibit changes in their values at 256 different sub-pixel locations. This would suggest that changes of less than 1/256th of a pixel would not have any impact at all on most pixels and the pixels that might change under such a small change of the scaling parameters would only change by 1 value out of 256. This isn't the strictest upper bound on the worst impact of a minor change in the transform values, but it gives a nice ballpark estimate that would suggest that rounding values that were within 1/256th or maybe 1/512th of a pixel to an integer coordinate (in device space) would not cause very noticeable deviations from the "true" answer. For uninterpolated scaling operations (when the NEAREST_NEIGHBOR mode is specified) we have a slightly more complicated story because the pixels do not subtly change their value as the transform for the image is perturbed by tiny sub-pixel values. Instead, many of the pixels will change their color from one source pixel value to another as the sampling equations scan along and encounter pixel boundaries. If the source image has adjacent pixels with a lot of contrast in their colors, then those sudden changes of value could represent striking changes in the visual result. The worst case example occurs when an even sized image is scaled into an odd destination size. For example, if the source image is 2 pixels wide and the destination area it is scaled into is 3 pixels wide then the first column of pixels in the destination maps to the first 2/3rds of the first pixel in the source image and the center of that column maps to the sub-pixel location that is 1/3rd of the way across that pixel - so all of those pixels will be taken from the first column of the source with a fairly generous margin for error of 1/3rd of a pixel. It is the middle column of that 3-pixel wide region that causes the problem. It maps to the region that spans the border between the columns of source pixels and includes the centermost 1/3 of both columns of pixels. The center of that middle column of dest pixels then maps exactly onto the boundary between the two columns of source pixels. This means that the decision of which pixel to use for the destination depends on whether > or >= logic is used in the inner loop of the implementation (i.e. some implementations may choose the first column and others the second in this case). Worse yet, it means that perturbing the sampling parameters (i.e. the transform) by even the smallest delta could cause the algorithm to change its mind about those pixels that map onto that boundary and affect the outcome of the operation. If we knew which way the underlying implementation biased its pixel sampling decisions (i.e. preferring the first or the second pixel when the sampling coordinate falls exactly on the boundary) then we could allow some deviation in one direction, but not the other, but we don't know this detail for many hardware implemenations. This would suggest then that for operations with even source and odd destination sizes we should not allow any deviation from exact integer coordinates before deciding to use a reduced integer-scale or pixel copying algorithm. The analysis of odd sized scaling operations can produce a formula for the closest that a pixel sampling equation comes to landing on the boundary between 2 source pixels (I did a loose version of such analysis that showed that 1/(2d) is a good estimate for this value when the destination size is d), but this formula is kind of moot given that even-source-sized operations do not theoretically allow any error at all. So, if we wish to try to calculate a cutoff value based on the type of operation we are performing (interpolation mode and specific source and destination sizes) we end up with a number of different values or formulas to use and we still have one case which would suggest that no error at all be allowed. Perhaps it would be far simpler to simply pick a very small constant epsilon that represents a reasonable balance between "theoretically possibly causing some visible anomalies" and "belligerently not allowing any amount of roundoff error in the calculation of image transforms". The value should be small enough to represent a sub-pixel precisiion error that most would decide was "not worth worrying about". The question would then be how small an error would be small enough that developers would not take issue with the quality, but not so small that roundoff errors frequently tickle it. I'd like to choose a value as small as ".00001" (1 hundred thousandth of a pixel), but the test case as submitted would not pass with such a cutoff implemented. Inquiring with the original submitter, it looks like the values they were encountering in their calculated transforms in practice had roundoff errors on the order of .0000001 to .0001 which span a range around that cutoff. I looked at the code in question and found a few sources of roundoff error that could be improved such that the transforms would end up with values that were much closer to integers, but in the meantime it may be necessary to use a cutoff as high as .0001 (1 ten thousandth of a pixel in device space). I might add that some image scaling algorithms might use 16-bit fractional arithmetic to sample the source image pixels which would impose an error of around that much precision in any case so a cutoff of around .0001 is only a few bits larger than the per-pixel error introduced by some software scaling algorithms. ###@###.### 2004-02-10

10-02-2004