🔒 Locked

DXTn Compressor

Started by Haroogan Mar 31, 2011 at 5:56 PM 16 replies 6.2k views

Original Post

Mar 31, 2011 at 5:56 PM

Hey folks, I've written my own DXT1 and DXT5 compressor for personal needs. To be more specific I need it because I'm programming with JOGL (Java OpenGL bindings) and I wanted to make my application completely independent from 3rd party tools like ATI Compressonator. The problem I face is noticeable quality loss. Well it is noticeable only in some cases - long gradient fields. I think I won't be able to explain it without images. Please have a look at the following two images. The first one is png - but it was derived from my own DXT1 compression. The second one is also png - but it was derived from DXT1 compression product of ATI Compressonator. PNG's should not confuse you - I've converted both dds's to png's just to let you inspect them.

Ok, on the first image I have marked areas, which do not satisfy me. As you can see (and compare) - after my DXT1 compression there is like "stair" effect where it is long gradient field, i. e. where it is implied that color should change smoothly in some area. ATI Compressonator somehow produces the same smooth area, so quality loss on ATI Compressonator products is almost unnoticeable. Mine also produces good results and all I need is to fix this problem with "stair" effect on long gradient fields.

I know why this happens - or at least here is my idea: this is because of color degradation from 8-8-8 to 5-6-5. I'm sure that this is the reason, because if you make simple color depth conversion (I mean without any compression - just a simple color depth conversion) from 8-8-8 image to 5-6-5 image you will see the same "stair" effect on long gradient fields, due to the color degradation. Therefore, to prevent this effect maybe I need something like dithering, or maybe something else? If dithering would help, could you please explain how to implement dithering, since I don't have a complete understanding of its purpose.

If anyone of you has ever done similar things or at least knows a good source of information on it - that would be great! Thank you.

kdmiller3

Mar 31, 2011 at 7:41 PM

Error diffusion is a good way to do this, and Floyd-Steinberg is the most common algorithm. There are plenty of other options, though.

davidleonardcook

Mar 31, 2011 at 7:54 PM

In DXT1 compression, it is only the "anchors" in a block which are quantized to 5:6:5, not the pixels. Your compressed image should have much less quantization than a 5:6:5 image.

Pixel values are interpolated between the anchors with weights of n/3, for n = 0,1,2,3. So in a loose sense, you have 1-2 more bits of precision than 5:6:5, or in other words you're between 6:7:6 and 7:8:7. This is still not enough to eliminate quantization artifacts on gradients, but it's getting closer to uncompressed 8-bit. I would isolate a band in your image and measure the exact pixel difference from one side to the other in the R or B channels. It should be on the order of 2-4, not up near 8. You might also try some open source compressors, like Squish, for comparison. If the results look good, you can examine what they do.

You're right that dithering is sometimes used to mask compression effects. It's hard to tell from the screenshots whether this is happening, since the source image looks a bit dithered to begin with. Dithering involves intentionally introducing a noise pattern into the image. You can look here http://en.wikipedia.org/wiki/Floyd%E2%80%93Steinberg_dithering for one example, although I'm not sure it's applicable to your situation.

Lastly, make sure you are using gamma properly. The right thing to do is first acquire the source image in gamma (sRGB) space and then compress, not the other way around.

Haroogan

Mar 31, 2011 at 8:29 PM

In DXT1 compression, it is only the "anchors" in a block which are quantized to 5:6:5, not the pixels. Your compressed image should have much less quantization than a 5:6:5 image.

Pixel values are interpolated between the anchors with weights of n/3, for n = 0,1,2,3. So in a loose sense, you have 1-2 more bits of precision than 5:6:5, or in other words you're between 6:7:6 and 7:8:7. This is still not enough to eliminate quantization artifacts on gradients, but it's getting closer to uncompressed 8-bit. I would isolate a band in your image and measure the exact pixel difference from one side to the other in the R or B channels. It should be on the order of 2-4, not up near 8. You might also try some open source compressors, like Squish, for comparison. If the results look good, you can examine what they do.

You're right that dithering is sometimes used to mask compression effects. It's hard to tell from the screenshots whether this is happening, since the source image looks a bit dithered to begin with. Dithering involves intentionally introducing a noise pattern into the image. You can look here http://en.wikipedia....nberg_dithering for one example, although I'm not sure it's applicable to your situation.

Lastly, make sure you are using gamma properly. The right thing to do is first acquire the source image in gamma (sRGB) space and then compress, not the other way around.

I didn't understand your case about 6-7-6 and 7-8-7. It seems like you are trying to say like "5-6-5 in DXT1 is almost like 8-8-8 so the problem is not in color truncation" - did I catch it right? Moreover I have already said (in the very first post) that this can happen only because of 5-6-5 truncation. Why? Because if we forget about compression right now and just make simple image conversion from 8-8-8 to 5-6-5 we shall see absolutely the same "stair" artifacts on gradient areas - and that's logical. The pseudo-code for truncation is:


 x5 = x8 >> 3; // for r and b
 x6 = x8 >> 2; //for g

So, to my mind, these "stair" artifacts are not produced by compression itself. These artifacts are just a product of color degradation from 8-8-8 scheme to 5-6-5 scheme using the above pseudo-code. And this is why the first thing I thought about - was dithering...

To compare results of my compression and ATI compressonator one - I have compared MSE between original and compression product:
DXT1:
ATI - 5.40
Me - 7.91
DXT5:
ATI - 3.37
Me - 4.98

I don't know whether these results are good or bad, but I know one thing - for this test on ATI compressonator I have used best-quality settings - so I think that ATI compressonator used principal component analysis (PCA) to compute color0 and color1 - which is slow enough. In contrast, mine compressor used much more lightweight and faster approach to compute color0 and color1 - but visually the results are the same (not taking stair effect into consideration). Therefore, I suppose that 7.91 - 5.40 = 3.51 difference between my compression product and compression product of ATI compressonator is not that critical and appears to be unnoticeable. Thats why all I want to do - is to eliminate stair effect...

davidleonardcook

Mar 31, 2011 at 10:01 PM

I didn't understand your case about 6-7-6 and 7-8-7. It seems like you are trying to say like "5-6-5 in DXT1 is almost like 8-8-8 so the problem is not in color truncation" - did I catch it right? Moreover I have already said (in the very first post) that this can happen only because of 5-6-5 truncation. Why? Because if we forget about compression right now and just make simple image conversion from 8-8-8 to 5-6-5 we shall see absolutely the same "stair" artifacts on gradient areas - and that's logical. The pseudo-code for truncation is:

x5 = x8 >> 3; // for r and b x6 = x8 >> 2; //for g

Haroogan

Mar 31, 2011 at 10:20 PM

[quote name='Haroogan' timestamp='1301603365' post='4792747']
I didn't understand your case about 6-7-6 and 7-8-7. It seems like you are trying to say like "5-6-5 in DXT1 is almost like 8-8-8 so the problem is not in color truncation" - did I catch it right? Moreover I have already said (in the very first post) that this can happen only because of 5-6-5 truncation. Why? Because if we forget about compression right now and just make simple image conversion from 8-8-8 to 5-6-5 we shall see absolutely the same "stair" artifacts on gradient areas - and that's logical. The pseudo-code for truncation is:

x5 = x8 >> 3; // for r and b x6 = x8 >> 2; //for g

Yes, you rephrased my point correctly.

Your argument is that DXT1 compression involves first truncating to 5:6:5, and then doing some additional lossy operation. That's not the case. The input pixels are not truncated to 5:6:5. Each 4x4 DXT1 block can represent 4 colors. Two of these colors are 5:6:5 colors. The other two are 8:8:8 colors which are interpolated between the first two.

I should qualify this by saying "on some hardware". I have heard that on older NVidia parts, such as the PS3 RSX, DXT1 pixels are only expanded to 5:6:5 upon fetch, and then your point is correct. However, that won't affect your screenshots, which I presume are generated by compressing and then decompressing in software (?).
[/quote]

Yep the input pixels are not truncated, you find min and max in 8-8-8 format, but when you are writing DXT1 block you make truncation of these min and max to 5-6-5 anyway. Interpolation between min and max is done when they are still 8-8-8 and moreover I have my own powerful classes, which drive color operations (sum, sub, mul, div, calculating distance and etc. while treating colors as vectors) and these classes work with float colors internally (0.0f - 1.0f), therefore all calculations connected with interpolation and calculation of "combinator" (those 32 bits, which say how to combine colors on decompression) are done in floats.

These "screenshots" are actually real images, they were generated by the following steps:

1. Source image with bottles (png) was compressed by ATI compressonator to DXT1 and also compressed by my compressor to DXT1 too
2. Products of compression (my dds file and ATI compressonator dds file) were decompressed by my decompressor and written as png files again - and these are the images you see in the first post

davidleonardcook

Mar 31, 2011 at 10:48 PM

So imagine you have a smooth horizontal gradient from 0,..,255, 8-bit, with the value increasing by 1 per pixel as you move to the right. If you were to quantize this to 5:6:5, you'd see exactly 32 distinct values in the red channel. On the other hand, if you compress this as DXT1, the number of distinct values in the red channel will be around 94. That's because you'll have the 32 5-bit values, plus two interpolated values between every neighboring pair.

That's what I mean by 6-7 bit precision. The green channel will have 7-8 bit precision. This is admittedly less than 8:8:8, but I'm not sure it's bad enough to account for the banding you are seeing.

davidleonardcook

Mar 31, 2011 at 10:51 PM

Here's another question. How are you computing "color0 and color1" for each block? A common approach is to choose color0 to be the min of R, G, B over the block, and color 1 to be the max. This will produce banding in blocks where the variance is mainly in the chroma directions (in color, not in luminance).

Haroogan

Mar 31, 2011 at 11:11 PM

Here's another question. How are you computing "color0 and color1" for each block? A common approach is to choose color0 to be the min of R, G, B over the block, and color 1 to be the max. This will produce banding in blocks where the variance is mainly in the chroma directions (in color, not in luminance).

Actually the common approach is to choose color0 to be max and color1 to be min - to be able to add 2 interpolations. If you make color0 - min and color1 - max - you will be able to add only 1 interpolation: (color0 + color1) / 2... That's why I always make color0 - max and color1 - min, the same goes about alphas in DXT5.

Returning to banding, how would you comment the fact I've provided 2 times already - that if you convert any 8-8-8 image to 5-6-5 image you will see the same banding. And forget about compression while thinking of this. Anyway you can try that by yourself (still I believe that you understand that it's true - because it is obvious color truncation). This fact proves my thoughts - that banding is derived from 8-8-8 to 5-6-5 truncation. Because, in any case, when any decompressor (the hardware one or the software one - it doesn't matter since decompression algorithm is uniform) will be rebuilding 4x4 block from 64-bit of DXT1 chunk it will operate with those 5-6-5 color0 and color1... Yes, of course, first of all, it may convert them into floats and calculate interpolated colors in floats already, but that doesn't matter anyway - because these floats were derived from 16-bit colors (5-6-5 color0 and color1) and therefore these floats only have 65536 discrete float values available, in contrast to floats, which were, for instance, derived from 8-8-8 colors - and therefore have 16777216 discrete float values available...

So imagine you have a smooth horizontal gradient from 0,..,255, 8-bit, with the value increasing by 1 per pixel as you move to the right. If you were to quantize this to 5:6:5, you'd see exactly 32 distinct values in the red channel. On the other hand, if you compress this as DXT1, the number of distinct values in the red channel will be around 94. That's because you'll have the 32 5-bit values, plus two interpolated values between every neighboring pair.

That's what I mean by 6-7 bit precision. The green channel will have 7-8 bit precision. This is admittedly less than 8:8:8, but I'm not sure it's bad enough to account for the banding you are seeing.
[/quote]

Wow-wow - not so fast! I'm 100% sure this is wrong assumption - 16-bit color depth is unchanged and can't be changed in this world in any case! These 2 interpolated values, which you have generated from min and max will be decompressed in 16-bit format anyway (as I've already said above) and these 2 interpolated values do not increase "overall color depth of 4x4 block" (I believe you've tried to imply this), these 2 values have another physical purpose - we need them to make those 16 colors in 4x4 block look more distinctly. So what we have is: 4 colors of 5-6-5 depth to represent 16 colors of 8-8-8 depth. And again, no 6-7-6 or 7-8-7 (lol, sorry I didn't mean to be rude but that really looks ridiculous, recall the information theory - according to it, this magical color-depth increasing from interpolation between 2 colors of 5-6-5 to 7-8-7 is just impossible since you just don't have enough information - those precision bits are lost forever during the compression stage! The only thing that you get from interpolated values - are just 2 more 5-6-5 colors to make your 4x4 block look not that poor and flat...) just 4 colors of 5-6-5 scheme - the obvious color TRUNCATION

davidleonardcook

Apr 1, 2011 at 12:16 AM

These 2 interpolated values, which you have generated from min and max will be decompressed in 16-bit format anyway (as I've already said above).

This is not true, at least for recent GPUs. They decompress like this:

1) Take the 5:6:5 color0 and color1 values. Expand them (by repeated fraction expansion) to at least 8:8:8.
2) Interpolate between the endpoints using lerp factors of 1/3 and 2/3 (approximately), keeping at least 8:8:8 precision.

You can verify this by rendering your DXT1 to a decompressed texture and checking pixel values. You will see pixels which are not 5:6:5.

[color=#1C2837][size=2][color=#000000]

Actually the common approach is to choose color0 to be max and color1 to be min - to be able to add 2 interpolations. If you make color0 - min and color1 - max - you will be able to add only 1 interpolation: (color0 + color1) / 2... That's why I always make color0 - max and color1 - min, the same goes about alphas in DXT5.
[color=#1C2837][size=2][color=#000000]

[color=#1C2837][size=2][color=#000000]

[color=#1C2837][size=2][color=#000000]

Yes, you're right about the ordering being important. But the point I'm trying to make is that max RGB and min RGB are sometimes a bad choice for color0 and color1. To take an extreme example, suppose you have a DXT1 block where all the pixels are either pure red or pure green. For that block, min RGB will be (0,0,0), which is black, while max RGB will be (255,255,0), which is yellow. So your compression will change both the red pixels and the green pixels into yellow pixels.
[color=#1C2837][size=2][color=#000000]

A better choice in this case would be color0 = red and color1 = green (or the other way around). The high quality compressors like ATIs will probably make this choice, while the simple compressors will not. It's possible that's what going on in your test case. Do you ever see the banding in grayscale test images?

Haroogan

Apr 1, 2011 at 10:04 AM

[quote name='Haroogan' timestamp='1301613083' post='4792795']
These 2 interpolated values, which you have generated from min and max will be decompressed in 16-bit format anyway (as I've already said above).

Actually the common approach is to choose color0 to be max and color1 to be min - to be able to add 2 interpolations. If you make color0 - min and color1 - max - you will be able to add only 1 interpolation: (color0 + color1) / 2... That's why I always make color0 - max and color1 - min, the same goes about alphas in DXT5.
[color="#1c2837"][color="#000000"]

[/quote]

First of all, you still haven't commented this:

Returning to banding, how would you comment the fact I've provided 2 times already - that if you convert any 8-8-8 image to 5-6-5 image you will see the same banding. And forget about compression while thinking of this.
[/quote]

Secondly, you say that on recent GPUs they convert to 8:8:8 - ok, but the algorithm is:

r8 = (r5 << 3) | (r5 >> 2);
g8 = (g6 << 2) | (g6 >> 4);
b8 = (b5 << 3) | (b5 >> 2);

And this conversion from 5-6-5 back to 8-8-8 still doesn't blow away color truncation effect, because after such conversion you will still have maximum 65536 discrete values but in 8-8-8 format. It happens because the source of your conversion is is 16-bit format and during the conversion to 24-bit format you are able to extract only 65536 different values and no more...

If GPUs provide some magic during the conversion, i. e. they use more complicated algorithm of conversion (I'm really hesitating that it is true) - then cool, but in any case, let's forget about GPU and talk only about images.

[color="#1c2837"][color="#000000"]Yes, you're right about the ordering being important. But the point I'm trying to make is that max RGB and min RGB are sometimes a bad choice for color0 and color1. To take an extreme example, suppose you have a DXT1 block where all the pixels are either pure red or pure green. For that block, min RGB will be (0,0,0), which is black, while max RGB will be (255,255,0), which is yellow. So your compression will change both the red pixels and the green pixels into yellow pixels.
[color="#1c2837"]
A better choice in this case would be color0 = red and color1 = green (or the other way around). The high quality compressors like ATIs will probably make this choice, while the simple compressors will not. It's possible that's what going on in your test case. Do you ever see the banding in grayscale test images?
[/quote]

Wrong, I've just checked this case on both - my compressor and ATI's one. I've made a simple 4x4 image in Paint program , which had 2 distinct colors - red and green, and after the compression both mine and ATI's compressor didn't distort anything - there were red and green as intended...

To conclude, for now, as you can see mate - everything I say appears to be true - the only reason of banding is truncation and the only solution seems to be dithering.

Edit: I've just tried to compress image with bottles by ATI compressonator but not with "Normal" option (it's best quality as they say), but with "Fast" option (they say that it is "slightly lower quality than normal") - and I got absolutely the same banding in the same areas of product image! So you see no magic here, just with "Fast" they skip dithering stage - I'm almost sure...

rarelam

Apr 1, 2011 at 11:33 AM

I think you have missed the point about the interpolation of the values. When the min/max color values stored in 565 format are used, they are converted to 888.
They do not increase in precision at all, but the 2 interpolated values you generate will have increased precision over these values.

For instance lets say in the red channel:
min = 1
max = 2
Covert to 8 bit from 5 bit (this is quite a simple conversion, usually you would pad out the data so you can represent 0-31 as 0-255)
min <<= 3
max <<= 3
We now have
min = 8
max = 16
interpolating between these values we get our 4 values as
color0 8
color1 10.667
color2 13.333
color3 16

Note: that color1 & color2 now have values we cant represent with 8 bits of precision

Clamp these to discrete values, however now we have values inbetween just 5bits of precision in our final red channel. So it is not true to say that the gradients are constrained just by the 565 encoding. From looking at your images it looks like your method of encoding the blocks is a niave min/max color implementation which would cause this kind of artifact.

Haroogan

Apr 1, 2011 at 12:28 PM

I think you have missed the point about the interpolation of the values. When the min/max color values stored in 565 format are used, they are converted to 888.
They do not increase in precision at all, but the 2 interpolated values you generate will have increased precision over these values.

For instance lets say in the red channel:
min = 1
max = 2
Covert to 8 bit from 5 bit (this is quite a simple conversion, usually you would pad out the data so you can represent 0-31 as 0-255)
min <<= 3
max <<= 3
We now have
min = 8
max = 16
interpolating between these values we get our 4 values as
color0 8
color1 10.667
color2 13.333
color3 16

Note: that color1 & color2 now have values we cant represent with 8 bits of precision

Clamp these to discrete values, however now we have values inbetween just 5bits of precision in our final red channel. So it is not true to say that the gradients are constrained just by the 565 encoding. From looking at your images it looks like your method of encoding the blocks is a niave min/max color implementation which would cause this kind of artifact.

What could you offer except min/max approach? There is nothing wrong with min/max approach, because you need min and max anyway to make interpolations, how would you fight with banding without dithering?

Krypt0n

Apr 1, 2011 at 1:58 PM

What could you offer except min/max approach? There is nothing wrong with min/max approach, because you need min and max anyway to make interpolations, how would you fight with banding without dithering?

I doubt anyone is using the min-max rgb approach, it leads to horrible results in a lot of cases. simply converting to YCoCg for min-max can improve the situation already, but usually, the best results with an acceptable time consumption is achived by calculating the mean axis. imagin rgb to be xyz, those 16 pixels are actually points in that volume, now you seek the axis in this space that minimizes the (squared) distances sum to all points.

it's also useful to always evaluate the 4 and 3 value versions, sometimes just 3 values can still lead to less error.

some realtime compressors I saw try to permutate the min-max rgb values, it's a simple way to increase the quality in a lot of cases like

[quote name='davidleonardcook']suppose you have a DXT1 block where all the pixels are either pure red or pure green[/quote]

I saw also some early compressors (that didn't use the mean axis) that try to vary the two end points by +-1 for each channel to compensate errors due to rounding when converting from 8:8:8 to 5:6:5 (it's not done by round to nearest, as you affect 3 values by that, not just one, and both ends of the LUT affect 2 colors, so it's really not simply round to nearest).

there is an article on the nvidia page of compression on gpu, there is also one on intels page of how it's done in quake enemy territory for megatextures.

rarelam

Apr 1, 2011 at 2:07 PM

The basic idea think of your rgb values as a 3d position. In a 4x4 block of pixels if you plot all the 16 values in a 3d space, you want to create a line that best fits all of these points. By taking the min/max of of all the values an using that you line will encompass the full data range, but unless all the points are close to this line, you interpolated points will be a very poor representation of the actual original data.

You basically want to minimise the standard deviation of your data set for calculating the min/max. Remove points with very large deviation from the mean. Then find 2 points that minimise the deviation for the min/max. You will loose some fine detail this way, but it is controllable based on your tolerence with which you remove points for determining min/max points of the DXT block.

Haroogan

Apr 1, 2011 at 2:29 PM

Guys you are trying to explain so trivial things (16 points in space, mean axis and etc.) - like if I was a noob in this question... I know about PCA approach and I know how it works. Also I haven't yet presented the way how I calculate min and max - it seems like you think that I'm simply doing a stupid sorting of colors and choose max and min - lol, no, of course I don't! If I would do like that the results would be horrible and not even close to what you've seen in the first post. My quality is very good and very close to ATI compressonator one. Here is my algorithm - so it will make clear for you how I calculate min and max:


 protected static class ColorExtremum
 {
 public int minRGB565;
 public int maxRGB565;
 
 
 public ColorExtremum(int rgb565A, int rgb565B)
 {
 init(rgb565A > rgb565B ? rgb565B
 : rgb565A, rgb565A > rgb565B ? rgb565A
 : rgb565B);
 }
 
 
 private void init(int minRGB565, int maxRGB565)
 {
 this.minRGB565 = minRGB565;
 this.maxRGB565 = maxRGB565;
 }
 }
 
 public static ColorExtremum colorExtremum(RGBABlock rgbaBlock)
 {
 RGB rgbA = null;
 RGB rgbB = null;
 
 float maxSquareDist = -Float.MAX_VALUE;
 
 for(int i = 0; i < rgbaBlock.capacity() - 1; ++i)
 {
 for(int j = i + 1; j < rgbaBlock.capacity(); ++j)
 {
 float squareDist = RGB.squareDist(rgbaBlock.out(i), rgbaBlock.out(j));
 
 if(squareDist > maxSquareDist)
 {
 maxSquareDist = squareDist;
 
 rgbA = rgbaBlock.out(i);
 rgbB = rgbaBlock.out(j);
 }
 }
 }
 
 return new ColorExtremum(RGB565.rgb565(rgbA), RGB565.rgb565(rgbB));
 }

This produces almost the same result as PCA approach, but works RATHER faster. There is absolutely no need in PCA. I can't get why you are trying to say that banding on long gradient fields depends min and max, huh? Yes it does, but not in my case, since my approach and PCA one are almost the same and overall quality of my compression product proves it. Banding - is an obvious color truncation derivative.

davidleonardcook

Apr 1, 2011 at 3:46 PM

[color=#1C2837][size=2]First of all, you still haven't commented this:

[color=#2B3730][size=2]Quote

[size=2][size=2]Returning to banding, how would you comment the fact I've provided 2 times already - that if you convert any 8-8-8 image to 5-6-5 image you will see the same banding. And forget about compression while thinking of this.

The fact that you're seeing the same banding as 5-6-5 is odd. In practice, DXT compressors, even naive ones, do not have as much banding as 5-6-5. So I worry you may be quantizing somewhere that you do not need to.

Hey, do you have the original uncompressed source image available somewhere? I have a couple of DXT compressors that I can run it through for comparison, including ones which use the simple min RGB - max RGB approach. Maybe that will shed some light on it.

I'm about to leave on vacation though, so it might take me a while. I'm sure someone else on this thread would try it out in the meantime.

Haroogan

Apr 1, 2011 at 5:25 PM

[quote name='Haroogan' timestamp='1301668192' post='4793078']
[color="#1c2837"]First of all, you still haven't commented this:

[color="#2b3730"]Quote

Returning to banding, how would you comment the fact I've provided 2 times already - that if you convert any 8-8-8 image to 5-6-5 image you will see the same banding. And forget about compression while thinking of this.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.