[Release] DXTn Compression Algorithm

Thanks for releasing the code and algorithm details. However you should really compare against ATI's texture compression library, which is not only fast (it's multithreaded) but has excellent quality. I made some comparison images and gathered some error metrics using Compressonator (the front-end tool for ATI_Compress) and their results had lower error rates, and also look better to my eyes. Yours does a better job of reproducing the gradients on the text in a few cases, however it also has some severe discoloration artifacts. But of course their library is not open source,so it's always great to have full implementation details for alternate approaches.

[attachment=6310:Comparisons.png]

[attachment=6311:ErrorStats.png]

Thank you for the suggestion.
I have tweaked a few things on how it decides how close colors are and my percentage of error has been decreasing. For one I used their weights for each channel instead of 0.3, 0.59, and 0.11.

I am now at 14.485, which at least beats their low-quality setting. Their high-quality setting is only at 14.055, so I am pretty close (using db(square error)).
I think the algorithm itself is sound; I just need to tweak a few things and adjust how it grades closeness of colors.
Will post more results later.


L. Spiro


[EDIT]
There is a bug in my implementation of the 3rd part. That is where the discoloration is sneaking in.
I will fix that and I believe my error will drop significantly, since nearly all of my errors are coming from the discolorazation caused there.
[/EDIT]

Fixing the bug helped, and I made a few tweaks to the first and second stages of the algorithm.
Here are my current results:
[attachment=6318:LSResults.png]
[attachment=6319:AdOrig copy5.png]

I have a few more ideas to try.


L. Spiro

That looks really nice!

Although I can see quite a large amount of very light blue discolorations instead of white, all over the place... especially noticeable on the upper text, along the bottom line. Which seems kind of interesting, because there's a lot of that same light blue, but not really any other noticeable discolorations besides that.


PS. Although admittedly, the light blue is easily perceived as white under normal circumstances... it just seems so abundant, I'm curious if there's something amiss.

One may be tempted to expect all greys, but as the DXTn compression is lossy and must represent all colors in a block using only 2 16-bit endpoint colors and 2 values interpolated between them (which are not restricted to 16-bit precision, but still limited by their 16-bit end points), not every color can be exactly reproduced.

As it turns out, you can nudge a grey color closer to another grey color by changing only one of its RGB components, and blue is the component that is least perceptible. The result is of course slight discolorization, but still a closer match to the actual grey perceptually.

If I graded the closeness between 2 colors using 0.333333 for each channel then the images above would all be fully grey.


L. Spiro

Nice read!

I would love to see MJP's updated Error Statistics after YogurtEmperor's fixes to the algorithm.

Also, have you guys tried to compute the optimal/global minimum for this problem by brute-forcing through all relevant possibilities for the compression? (minus any obvious pruning of the search space to make it feasible to brute force) Having the global minimum SNR-wise in MJP's statistics would be a nice addition, to be able to estimate how far these algorithms go from the optimal. Of course that doesn't necessarily give the best perceptual result, but having a good raw number for the lower bound is useful when estimating how far it's possible to improve.

Nice read!

I would love to see MJP's updated Error Statistics after YogurtEmperor's fixes to the algorithm.

Also, have you guys tried to compute the optimal/global minimum for this problem by brute-forcing through all relevant possibilities for the compression? (minus any obvious pruning of the search space to make it feasible to brute force) Having the global minimum SNR-wise in MJP's statistics would be a nice addition, to be able to estimate how far these algorithms go from the optimal. Of course that doesn't necessarily give the best perceptual result, but having a good raw number for the lower bound is useful when estimating how far it's possible to improve.

If you're targeting next-gen then why would you still use dxt? Why not use BC7 - it has much higher quality and most importantly you don't see the hue-shift which is so common with DXT.

-= Dave

[quote name='clb' timestamp='1323117491' post='4890820']
Nice read!

I would love to see MJP's updated Error Statistics after YogurtEmperor's fixes to the algorithm.

Also, have you guys tried to compute the optimal/global minimum for this problem by brute-forcing through all relevant possibilities for the compression? (minus any obvious pruning of the search space to make it feasible to brute force) Having the global minimum SNR-wise in MJP's statistics would be a nice addition, to be able to estimate how far these algorithms go from the optimal. Of course that doesn't necessarily give the best perceptual result, but having a good raw number for the lower bound is useful when estimating how far it's possible to improve.

If you're targeting next-gen then why would you still use dxt? Why not use BC7 - it has much higher quality and most importantly you don't see the hue-shift which is so common with DXT.

-= Dave

[/quote]

DXT1 is still half the size compared to BC7 though if the quality is good enough for a given texture, or you could use the space savings to compensate with larger textures.

But yeah, it would be interesting to see what the mathematically optimal would be like, although it seems to me like it's pretty much as close as it gets in that picture. Perceptually, however might be more difficult... but as far as I can tell, no one seems to have been able to really provide a solid way to estimate perceptual quality. I saw some very high-tech NASA JPEG-encoder that boasted significantly lowered error values (it even allowed you to enter intended viewing distance, pixel density, etc), but to me the perceptual quality still ended up just noticably worse than the standard JPEG library implementation, despite the error values indicating otherwise.

DXT1 is still half the size compared to BC7 though if the quality is good enough for a given texture, or you could use the space savings to compensate with larger textures.

But yeah, it would be interesting to see what the mathematically optimal would be like, although it seems to me like it's pretty much as close as it gets in that picture. Perceptually, however might be more difficult... but as far as I can tell, no one seems to have been able to really provide a solid way to estimate perceptual quality. I saw some very high-tech NASA JPEG-encoder that boasted significantly lowered error values (it even allowed you to enter intended viewing distance, pixel density, etc), but to me the perceptual quality still ended up just noticably worse than the standard JPEG library implementation, despite the error values indicating otherwise.

http://pdiff.sourceforge.net/


The above describes a technique they used on Shrek 2 for comparing if two images are perceptually equivalent.

Also, there are some good test images out there used to that are pretty standard for image comparisons when you are doing compression if you just read some of the literature.

Here are my latest results. One of these is ATI and one of these is mine. I will let you try to see if one looks better than the other. Rather than making a poll I will just accept your input in replies.
[attachment=6354:Ad43.png][attachment=6355:Ad46.png]

Please try not to cheat by doing an image compare of the text region or the face region.

I will post the results later after I have updated my blog and eaten lunch etc.
Note that the images have been scaled down in this post. You will have to click them.


L. Spiro

Here are my latest results. One of these is ATI and one of these is mine. I will let you try to see if one looks better than the other. Rather than making a poll I will just accept your input in replies.
[attachment=6354:Ad43.png][attachment=6355:Ad46.png]

Please try not to cheat by doing an image compare of the text region or the face region.

I will post the results later after I have updated my blog and eaten lunch etc.
Note that the images have been scaled down in this post. You will have to click them.


L. Spiro

Having looked at a reasonable distance;

I would have to say I think #2 looks visually/aesthetically better than #1.
But #1 seems to have a sharper picture quality (but it's hard to tell whether it's compression noise/artifacts or not).

#1 has "pretty severe" discoloration on the shoulder, and has an overall much more sharper/grainy feel... if I were to put my thoughts into a sentence, I would say that if one just views them separately without trying to determine the quality or compare them I would say that; #1 has visible artifacts from compression, as if it has sacrificed color to improve sharpness... #2 is smoother and although it may not perfectly represent the final image, I can't point to anything that looks "wrong", colors look really great.

It's also pretty borderline, but #2 seems to slightly out-perform #1 when it comes to text, #1 has slightly more jagged edges and has a slight light blue tint and discoloration in certain areas . But it's really borderline, and varies a bit depending on where one looks. But my personal opinion would be that visually/aesthetically #2 is slightly ahead of #1 when it comes to text.

EDIT: Looking at the lower left logo, I would say that #1 seems to more faithfully reproduce the original image, better highlights and slightly sharper features, but there seem to be some strange discolorations in certain blocks. #2 again looks the best, it does have a flatter appearance but there is nothing visibly wrong with it. So, I'd say it depends on what you prefer. Although I would perhaps call this in slightly in favor of #1 for having a more vibrant look.

EDIT: (look really up close) Looking at the transition from green to the girls hair, #1 messes up completely there. #2 can't really do much about it, but it hides it really well perceptually, I didn't actually notice it at first. Adjacent blocks also seem a lot more coherent in #2, where as quite a lot of blocks in #1 can be completely discolored compared to the blocks next to it in #1.


So, I would say that I think #2 looks best... but it seems #1 has slightly sharper features.
I would also like to add that, looking at both pictures at 100% from a reasonably normal distance without flipping between them, the difference is minor... however the sharper details aren't really visible either, meaning... #1 looks as good as #2 at best, but #2 is perhaps slightly ahead still. But when you move closer to the screen or view them enlarged, then #2 definitely looks better in my opinion due to there being no visible compression artificats and the text being slightly less jaggy.

So my final verdict would be: #2 looks slightly better... most of the time. (Although it should be said that #1 appears to more faithfully reproduce the source image in high-contrast areas, at the expense of visible artifacts.)

Personally I would like to see more real-world examples to see how it really compares (it seems as if #1 could perform significantly better for regular textures than it does here). I can't imagine text and high-detail down-scaled art being the most common usage for DXT compression.


What it seems like to me; #1 favors colors based on some "flawed" average error metric (there are certain blocks that have really rather unreasonable discolorations), while #2 more strictly tries to reproduce the original colors. I admittedly have little to no knowledge in this area though.

Much to my disdain, after updating my blog and proof-reading it, I spotted an error in the 3rd stage again. A simple misnaming of 3 variables. It was also the direct cause of the over-blocky artifacts spotted by Syranide (notice the improvements to her shoulder, forehead, and inside the O of NOW).

I had a job interview (I was—for the first time ever—asked to tell a joke. After telling a hilarious one involving Superman, Superwoman, and The Invisible Man, I was hired on-the-spot) and could not post any results until now.


What you have basically noticed is that each of our routines excel in some areas more than the other.
Here I will show the original, mine (fixed), and ATI’s.

[attachment=6361:AdOrig.png][attachment=6363:Ad50.png][attachment=6362:Ad46.png]

I feel that my routine excels at contrast, while ATI is statistically more faithful to the original colors. While that is good mathematically, perceptually that can cause unpleasant results.
Notice the green bar on top. The area to the far right contains blocks that include 1 line of greens, 1 line of whites, and 2 lines in the hair.
This is one of those cases that is simply impossible for DXTn to encode faithfully.
In the ATI image, the green is distorted in order to make room for the other colors it needs in the hair.
Mine has less-detailed hair in favor of a more faithful reproduction of the green area. If I had to choose, I would probably pick this version, because everyone can spot the distortion in the green, but many will fail to notice the drop in detail in the hair.

Both of our routines generate similar artifacts inside the H in FIGHT, however my I has none.

In the logo, my previous post had some artifacts in the L in SOUL.
By fixing my copy/paste error this has gone away and my new L is much more accurate than the ATI L.


For the most part, now that my block-causing bug has been removed, the two DXT1 images shown here look virtually identical.


I think I am satisfied with these results and can discontinue my research.
My results are not mathematically as accurate as ATI’s (mind you I am only off by about 0.3%) but I don’t believe that math is the best way to go.
If I had added dithering, my amount of error would go up mathematically, but perceptually I would be even closer to the real image.
[attachment=6364:Happy.png]

This shows how much damage can be done by trusting only the numbers.


L. Spiro

There are definitely significant improvements to your new texture! (text is definitely overall equal or slighty ahead of ATI it seems)

However, I feel that there are still some strange discolorations that doesn't really seem to have any really logic behind them.

Here's a picture of some of the things I mean (order in the picture is: original, ATI, yours):
#1 It seems to have become pink for no reason at all (also there's an exaggerated protusion to the left, but that is reasonable)
#2 Why is there a green line in the block here?
#3 This block is way too green for some reason
#4 Again green blocks when green is the least visible color in the source
#5 Not an issue really, just highlighting that ATI seems to favor keeping the green tint throughout, while yours only puts it in this block (I'm not claiming that ATI's looks better though)




I also definitely agree with your assertion about not blindly trusting numbers when it comes to perception.

Great work!

PS. Congratulations to your new job too!

Thank you.

#1: Notice how the ATI routine has some heavier artifacts here, along the left side of the D. My routine was probably trying to avoid those, and the result was a decrease in one channel.
#2, #3, #4, #5: It could be an indication of another bug, but it may have simply been the result of my having chosen to give only the green channel a larger range on the 3rd stage. I suspect that the extended search range on the green and these green artifacts is not a coincidence.


L. Spiro