ETC1 optimization notes

I've been optimizing this function:

std::pair<etc1_bits, error> = ETC1Encode(pixels, options).

Which actually gives me a really fast way of accurately computing this:

error = ETC1Distance(pixelsA, pixelsB, options).

I'm seriously considering a SIMD implementation next. I wrote one for DXT1 just for fun last week.

I need this distance function to be fast in order to justify another series of bottom->up clusterization experiments, and on improving the clusterization process itself. 

ETC2 planar block only output created with etcpak

Bartosz Taudul (etcpak author) sent these ETC2 planar block only encodings in a reply to my previous post. For planar-only they look amazing!

Note: I've verified these images myself by hacking etcpak's ProcessRGB_ETC2() function to immediately "return result.first" after it calls Planar( src ); It returns all planar blocks in this case. I've verified this by generating a histogram of the used ETC1/2 modes in all the encoded blocks.

Hey GPU texture format engineers: Come on, give us more basis functions to play with! I'm starting to look more deeply at ETC2 encoded textures, and a surprising amount of blocks in some textures are using planar mode vs. the other ETC2 modes.

He also says that etcpak uses planar blocks quite often (blue indicates a planar block):

ETC2 texture compression using exclusively planar blocks

The usual explanation given for planar blocks is that they are intended for smoothly varying blocks (see my previous post on planar blocks). So it seems natural to model the block's pixels as three planes (separately R, G, and B) when trying to create a trial planar encoding.

etc2comp tries fitting several lines along the edges of the block to compute a trial plane definition, then it "twiddles" the quantized coordinates to minimize the quantization error. From what I've been told, in practice planar blocks aren't actually used that much in ETC2 compression, which seems sad to me.

I realized while looking at the planar mode's unpack function that the "offset" or "origin" component is equivalent to the DC component in the DCT. And, the H and V components are equivalent to two of the lowest frequency basis vectors (not counting DC) in the 4x4 DCT (circled in red):

So planar blocks actually support three basis vectors (including the DC component, in the upper left). So, why not try encoding each block in a test image as a ETC2-style planar block and see what the results looks like? In other words, look at using planar blocks from the perspective of transform coding.

In this experiment, I find the average block color, set the planar "O" color to that, then subtract that out from the block. I then dot (or inner product) the left-over pixel values against the H basis vector, then the V basis vector. I encode the resulting vectors into the ETC2 planar block H and V colors. I then use the same code to unpack this as I use to decode actual ETC2 planar block data. (Note because this is only a little fun experiment on Sunday night, I'm using 888 colors for O, H, and V, not 676, but I think the results should hold up in 676 with careful quantization/twiddling.)

The results are interesting. (See my newer post for much better looking planar-only encodings created by etcpak.) Remember, only planar blocks are used:

DC+H+V:

DC+H+V:

DC only:

DC+H+V:

DC only:

Rest are DC+H+V:

Visualization of random ETC2 Planar Mode blocks

For fun I've been poking around at the planar mode in ETC2. From this presentation:

Okay, they are intended for use on smoothly varying blocks. I'm intrigued by planar mode because the colors are stored at high precision (676) and there are no selectors like in the other modes. But what do planar blocks really look like though? This random planar block image, sorted by standard deviation, was pixel (box filter) upsampled by 400%:

Just the green channel:

This image was computed by poking random 8-bit bytes into an ETC2 block. If the block passed the planar ETC2 mode check it gets decoded and stored in a temporary image. After the temp image was full it gets sorted by standard deviation.

Hey - most of these random planar blocks are not actually smoothly varying! I'm unsure if this is actually useful in practice, but it's interesting.

Looking at how Planar blocks are actually unpacked, the H and V vectors are interpreted relative to the "origin" color, so they're actually signed and the unpacking code uses per-component [0,255] clamping. This is where the high frequency patterns come from.

// ro, go, bo - origin color, unpacked from 676
// rv, gv, bv and rh, gh, bh - vertical and horizontal colors, unpacked from 676
// unpack planar block's pixels - there are no selectors in this mode
for (int y = 0; y < 4; y++)
{
    for (int x = 0; x < 4; x++)
    {
        pDst->set(
            (4 * ro + x * (rh - ro) + y * (rv - ro) + 2) >> 2,
            (4 * go + x * (gh - go) + y * (gv - go) + 2) >> 2,
            (4 * bo + x * (bh - bo) + y * (bv - bo) + 2) >> 2,
            255);
        pDst++;
    }
}

ETC1 encoder performance on kodim18 at various quality/effort levels

I'm trying to get a handle on how the available ETC1 compressors perform, using their public API's, at their various quality or effort levels. This is only for a single image (kodim18 - my usual for quick tests like this).

First, here's the performance of etc2comp on kodim18, in ETC1-only mode, multithreading enabled, RGB Avg PSNR metrics, on effort levels [0,100] in increments of 5:

Efforts between roughly 40-65 seem to be the sweet spot. Effort=100 is obviously wasteful.

Here's another graph (can you tell I'm practicing my Excel graphing skills!), this time comparing the time and quality of various ETC1 (and now ETC2 - for etc2comp) compressors at different encoder quality/effort settings:

Important Notes:

• To be fair to Intel's ETC1 encoder (function CompressBlocksETC1()), which is not multithreaded, I added another bar labeled "ispc_etc1 MT" which has the total CPU time divided by 20 (to roughly match the speedup I'm seeing using 40 threads in the other natively multithreaded encoders). 
• basislib is now using a variant of cluster fit (see previous posts). basislib_1 is lowest quality, basislib_3 is highest. Notice that basislib_3 is only ~2X slower than Intel's SIMD code, but basislib doesn't use any SIMD at all.
• basislib and etc2comp both use 40 threads
• etcpak's timings are currently single threaded, because I'm still using a single threaded entrypoint inside the code (BlockData::Process()). It's on my TODO to fix this. IMHO unless you need a real-time ETC1 encoder I think it trades off too much quality. However, if you need a real-time encoder and don't mind the loss in quality it's your best bet. If the author added a few optional SIMD-optimized cluster fit trials in there it would probably kick ass.

To get an idea how efficient etc2comp currently is at scanning the ETC1 search space for kodim18, let's see what effort level (and how much CPU time) etc2comp takes to approximately match two other encoder's quality levels:

• basislib Cluster Fit (64 trials out of 165): .115 secs 35.917 dB

Quality matched or exceeded first at etc2comp effort 70: 1.095 secs 35.953 dB

• Intel ISPC: 1.03 secs 35.969 dB

Quality matched or exceeded first at etc2comp effort 80: 1.83 secs 35.992 dB

perceptual: 0 etc2: 0 rec709: 1
Source filename: kodak\kodim18.png 512x768
--- basislib Quality: 4
basislib pack time: 0.115
basislib ETC image Error: Max:  56, Mean: 2.865, MSE: 16.648, RMSE: 4.080, PSNR: 35.917, SSIM: 0.965767

--- etc2comp effort: 0
etc2comp time: 0.051663
etc2comp Error: Max:  64, Mean: 3.186, MSE: 21.123, RMSE: 4.596, PSNR: 34.883, SSIM: 0.958817
--- etc2comp effort: 5
etc2comp time: 0.083509
etc2comp Error: Max:  64, Mean: 3.129, MSE: 19.658, RMSE: 4.434, PSNR: 35.196, SSIM: 0.959313
--- etc2comp effort: 10
etc2comp time: 0.106361
etc2comp Error: Max:  64, Mean: 3.092, MSE: 19.052, RMSE: 4.365, PSNR: 35.331, SSIM: 0.959794
--- etc2comp effort: 15
etc2comp time: 0.133278
etc2comp Error: Max:  64, Mean: 3.063, MSE: 18.661, RMSE: 4.320, PSNR: 35.421, SSIM: 0.960250
--- etc2comp effort: 20
etc2comp time: 0.193460
etc2comp Error: Max:  64, Mean: 3.042, MSE: 18.416, RMSE: 4.291, PSNR: 35.479, SSIM: 0.960595
--- etc2comp effort: 25
etc2comp time: 0.162790
etc2comp Error: Max:  64, Mean: 3.027, MSE: 18.256, RMSE: 4.273, PSNR: 35.517, SSIM: 0.960869
--- etc2comp effort: 30
etc2comp time: 0.182370
etc2comp Error: Max:  64, Mean: 3.012, MSE: 18.108, RMSE: 4.255, PSNR: 35.552, SSIM: 0.961207
--- etc2comp effort: 35
etc2comp time: 0.196609
etc2comp Error: Max:  64, Mean: 2.998, MSE: 17.980, RMSE: 4.240, PSNR: 35.583, SSIM: 0.961578
--- etc2comp effort: 40
etc2comp time: 0.217227
etc2comp Error: Max:  64, Mean: 2.987, MSE: 17.888, RMSE: 4.229, PSNR: 35.605, SSIM: 0.961854
--- etc2comp effort: 45
etc2comp time: 0.248881
etc2comp Error: Max:  64, Mean: 2.970, MSE: 17.771, RMSE: 4.216, PSNR: 35.634, SSIM: 0.962461
--- etc2comp effort: 50
etc2comp time: 0.361306
etc2comp Error: Max:  59, Mean: 2.916, MSE: 17.175, RMSE: 4.144, PSNR: 35.782, SSIM: 0.963669
--- etc2comp effort: 55
etc2comp time: 0.379762
etc2comp Error: Max:  59, Mean: 2.902, MSE: 17.091, RMSE: 4.134, PSNR: 35.803, SSIM: 0.964149
--- etc2comp effort: 60
etc2comp time: 0.522357
etc2comp Error: Max:  59, Mean: 2.882, MSE: 16.840, RMSE: 4.104, PSNR: 35.867, SSIM: 0.964800
--- etc2comp effort: 65
etc2comp time: 0.560707
etc2comp Error: Max:  59, Mean: 2.878, MSE: 16.818, RMSE: 4.101, PSNR: 35.873, SSIM: 0.964974
--- etc2comp effort: 70
etc2comp time: 1.095014
etc2comp Error: Max:  59, Mean: 2.857, MSE: 16.512, RMSE: 4.063, PSNR: 35.953, SSIM: 0.965366
--- etc2comp effort: 75
etc2comp time: 1.166479
etc2comp Error: Max:  59, Mean: 2.852, MSE: 16.490, RMSE: 4.061, PSNR: 35.959, SSIM: 0.965534
--- etc2comp effort: 80
etc2comp time: 1.829960
etc2comp Error: Max:  59, Mean: 2.842, MSE: 16.362, RMSE: 4.045, PSNR: 35.992, SSIM: 0.965769
--- etc2comp effort: 85
etc2comp time: 1.904691
etc2comp Error: Max:  59, Mean: 2.836, MSE: 16.329, RMSE: 4.041, PSNR: 36.001, SSIM: 0.966037
--- etc2comp effort: 90
etc2comp time: 2.709250
etc2comp Error: Max:  59, Mean: 2.829, MSE: 16.255, RMSE: 4.032, PSNR: 36.021, SSIM: 0.966277
--- etc2comp effort: 95
etc2comp time: 2.802099
etc2comp Error: Max:  59, Mean: 2.827, MSE: 16.251, RMSE: 4.031, PSNR: 36.022, SSIM: 0.966315
--- etc2comp effort: 100
etc2comp time: 3.619217
etc2comp Error: Max:  59, Mean: 2.825, MSE: 16.216, RMSE: 4.027, PSNR: 36.031, SSIM: 0.966349

--- etcpak time: 0.006
etcpak Error: Max:  90, Mean: 3.464, MSE: 25.640, RMSE: 5.064, PSNR: 34.042, SSIM: 0.950396

--- ispc_etc time: 1.033881
ispc_etc1 Error: Max:  56, Mean: 2.866, MSE: 16.450, RMSE: 4.056, PSNR: 35.969, SSIM: 0.965412


ETC2 enabled:

perceptual: 0 etc2: 1 rec709: 1
Source filename: kodak\kodim18.png 512x768
--- basislib Quality: 1
basislib pack time: 0.036
basislib ETC image Error: Max:  73, Mean: 3.168, MSE: 20.910, RMSE: 4.573, PSNR: 34.927, SSIM: 0.959441
--- basislib Quality: 2
basislib pack time: 0.054
basislib ETC image Error: Max:  56, Mean: 2.945, MSE: 17.772, RMSE: 4.216, PSNR: 35.634, SSIM: 0.964359
--- basislib Quality: 3
basislib pack time: 0.107
basislib ETC image Error: Max:  56, Mean: 2.865, MSE: 16.648, RMSE: 4.080, PSNR: 35.917, SSIM: 0.965767
--- etc2comp effort: 0
etc2comp time: 0.086306
etc2comp Error: Max:  64, Mean: 3.158, MSE: 20.810, RMSE: 4.562, PSNR: 34.948, SSIM: 0.959069
--- etc2comp effort: 5
etc2comp time: 0.179816
etc2comp Error: Max:  59, Mean: 3.087, MSE: 19.044, RMSE: 4.364, PSNR: 35.333, SSIM: 0.959701
--- etc2comp effort: 10
etc2comp time: 0.247190
etc2comp Error: Max:  59, Mean: 3.046, MSE: 18.396, RMSE: 4.289, PSNR: 35.484, SSIM: 0.960256
--- etc2comp effort: 15
etc2comp time: 0.287620
etc2comp Error: Max:  59, Mean: 3.013, MSE: 17.977, RMSE: 4.240, PSNR: 35.584, SSIM: 0.960751
--- etc2comp effort: 20
etc2comp time: 0.339065
etc2comp Error: Max:  59, Mean: 2.990, MSE: 17.709, RMSE: 4.208, PSNR: 35.649, SSIM: 0.961162
--- etc2comp effort: 25
etc2comp time: 0.383907
etc2comp Error: Max:  59, Mean: 2.971, MSE: 17.515, RMSE: 4.185, PSNR: 35.697, SSIM: 0.961507
--- etc2comp effort: 30
etc2comp time: 0.432019
etc2comp Error: Max:  59, Mean: 2.954, MSE: 17.352, RMSE: 4.166, PSNR: 35.737, SSIM: 0.961876
--- etc2comp effort: 35
etc2comp time: 0.480186
etc2comp Error: Max:  59, Mean: 2.938, MSE: 17.210, RMSE: 4.149, PSNR: 35.773, SSIM: 0.962279
--- etc2comp effort: 40
etc2comp time: 0.516155
etc2comp Error: Max:  59, Mean: 2.925, MSE: 17.107, RMSE: 4.136, PSNR: 35.799, SSIM: 0.962590
--- etc2comp effort: 45
etc2comp time: 0.565827
etc2comp Error: Max:  59, Mean: 2.911, MSE: 17.009, RMSE: 4.124, PSNR: 35.824, SSIM: 0.963044
--- etc2comp effort: 50
etc2comp time: 1.124057
etc2comp Error: Max:  59, Mean: 2.892, MSE: 16.852, RMSE: 4.105, PSNR: 35.864, SSIM: 0.963703
--- etc2comp effort: 55
etc2comp time: 1.192462
etc2comp Error: Max:  59, Mean: 2.880, MSE: 16.772, RMSE: 4.095, PSNR: 35.885, SSIM: 0.964164
--- etc2comp effort: 60
etc2comp time: 1.713074
etc2comp Error: Max:  59, Mean: 2.851, MSE: 16.424, RMSE: 4.053, PSNR: 35.976, SSIM: 0.964913
--- etc2comp effort: 65
etc2comp time: 1.828673
etc2comp Error: Max:  59, Mean: 2.846, MSE: 16.398, RMSE: 4.049, PSNR: 35.983, SSIM: 0.965099
--- etc2comp effort: 70
etc2comp time: 2.461853
etc2comp Error: Max:  59, Mean: 2.836, MSE: 16.274, RMSE: 4.034, PSNR: 36.016, SSIM: 0.965358
--- etc2comp effort: 75
etc2comp time: 2.608303
etc2comp Error: Max:  59, Mean: 2.831, MSE: 16.247, RMSE: 4.031, PSNR: 36.023, SSIM: 0.965534
--- etc2comp effort: 80
etc2comp time: 3.383624
etc2comp Error: Max:  59, Mean: 2.820, MSE: 16.156, RMSE: 4.019, PSNR: 36.047, SSIM: 0.965855
--- etc2comp effort: 85
etc2comp time: 3.719689
etc2comp Error: Max:  59, Mean: 2.814, MSE: 16.125, RMSE: 4.016, PSNR: 36.056, SSIM: 0.966079
--- etc2comp effort: 90
etc2comp time: 4.675509
etc2comp Error: Max:  59, Mean: 2.808, MSE: 16.072, RMSE: 4.009, PSNR: 36.070, SSIM: 0.966264
--- etc2comp effort: 95
etc2comp time: 4.619700
etc2comp Error: Max:  59, Mean: 2.806, MSE: 16.068, RMSE: 4.008, PSNR: 36.071, SSIM: 0.966293
--- etc2comp effort: 100
etc2comp time: 4.771136
etc2comp Error: Max:  59, Mean: 2.805, MSE: 16.064, RMSE: 4.008, PSNR: 36.072, SSIM: 0.966309
--- etcpak time: 0.045
etcpak Error: Max:  90, Mean: 3.458, MSE: 25.593, RMSE: 5.059, PSNR: 34.050, SSIM: 0.950551
ispc_etc time: 1.034064
ispc_etc1 Error: Max:  56, Mean: 2.866, MSE: 16.450, RMSE: 4.056, PSNR: 35.969, SSIM: 0.965412

More ETC1 cluster fit data

Ignore the SSIM stats, this is a corpus test image with random 4x4 blocks chosen from many other images.

This was on a 20 core Xeon workstation, with multithreading enabled in basislib and etc2comp (40 threads each). The API I'm using in etcpak is not threaded (it's already sorta ridiculously fast), and Intel is not multithreaded either. (As far as I can tell from breakpointing inside it.) etcpak and Intel make heavy use of SIMD operations, while etc2comp and basislib do not.

Cluster fit (new algorithm):

J:\dev\basislib1\bin>texexp test_0.tga
perceptual: 0 etc2: 0 rec709: 1
Source filename: test_0.tga 4096x4096
--- basislib Quality: 4
basislib pack time: 4.211
basislib ETC image Error: Max: 255, Mean: 3.277, MSE: 40.847, RMSE: 6.391, PSNR: 32.019, SSIM: 0.999618

--- etc2comp effort: 100
etc2comp time: 154.562167
etc2comp Error: Max: 255, Mean: 3.286, MSE: 42.777, RMSE: 6.540, PSNR: 31.819, SSIM: 0.999612

--- etcpak time: 0.258
etcpak Error: Max: 255, Mean: 4.282, MSE: 69.927, RMSE: 8.362, PSNR: 29.684, SSIM: 0.998407

--- ispc_etc time: 43.694160
ispc_etc1 Error: Max: 255, Mean: 3.249, MSE: 39.912, RMSE: 6.318, PSNR: 32.120, SSIM: 0.999655

Previous algorithm (rg_etc1's lattice scan+refinement):

J:\dev\basislib1\bin>texexp test_0.tga
perceptual: 0 etc2: 0 rec709: 1
Source filename: test_0.tga 4096x4096

--- basislib Quality: 4
basislib pack time: 240.638
basislib ETC image Error: Max: 255, Mean: 3.203, MSE: 39.336, RMSE: 6.272, PSNR: 32.183, SSIM: 0.999680

--- etc2comp effort: 100
etc2comp time: 151.739932
etc2comp Error: Max: 255, Mean: 3.286, MSE: 42.777, RMSE: 6.540, PSNR: 31.819, SSIM: 0.999612

--- etcpak time: 0.243
etcpak Error: Max: 255, Mean: 4.282, MSE: 69.927, RMSE: 8.362, PSNR: 29.684, SSIM: 0.998407

--- ispc_etc time: 46.807596
ispc_etc1 Error: Max: 255, Mean: 3.249, MSE: 39.912, RMSE: 6.318, PSNR: 32.120, SSIM: 0.999655

ETC1 block flip estimation

ETC1's block includes a "flip" bit, which describes how the subblocks are oriented in each block. When this bit is set the two subblocks are oriented horizontally in a 4x4 pixel block like this:

ABCD

EFGH

IJKL

MNOP

Otherwise they're oriented vertically like this:

AB CD

EF GH

IJ KL

MN OP

(In BC7 terminology, ETC1 supports 1 or 2 subsets per block, with 1 or 2 partitions.)

Anyhow, a high quality encoder typically tries both subblock orientations and chooses the one which results in the lowest overall error. Interestingly, it's possible to predict with a reasonable degree of certainty which subblock orientation is best. The advantage to this method is obvious: higher encoding throughput, with (hopefully) only a small loss in quality.

The method used by etc2comp computes each possible subblock's average color, then it sums the squared "gray distance" from each pixel to each subblock's average color. (To compute gray distance from color A vs. B, it projects A onto the grayscale line going through B, then it computes the squared RGB distance from A to this projected point.) etc2comp then chooses the flip orientation with the lowest overall gray distance to try first.

Success rates on a handful of images, with RGB avg. PSNR and SSIM stats (using accurate vs. estimated flips):

kodim01: 68% (35.904 vs. 35.607, .975236 vs. .973744)
kodim03: 65% (39.949 vs. 38.801, .964774 vs. .963467)
kodim18: 69% (35.917 vs. 35.661, .965767 vs. .964385)
kodim20: 63% (38.849 vs. 38.589, .975558 vs. .974669)

ETC1 block flip bit visualizations on kodim03:

Image:

basislib best flips:

Flip estimates, using etc2comp's gray line estimate algorithm:

etc2comp's flips (in ETC1 mode):

etcpak's flips (in ETC1 mode):