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):

Example code: 4x4 Haar transform on ETC1 selectors

Someone asked me for the code that implements the selector frequency domain filtering experiment I did on one of my previous posts. Here you go. The linear algebra and utility code is all very similar to crunch's. The Haar stuff was copied straight from wikipedia.

If you understand how coefficient quantization works in JPEG, then this example should be pretty easy to follow. Let me know if you have any questions or want to see the 8x8 version, but it's basically the same thing with larger matrices (and the selectors within 2x2 ETC1 blocks).

Notes:
gpu_image: A compressed GPU texture (in this case, ETC1). image_u8: A 32bpp ARGB raster image. etc_block: A simple helper class to get/set ETC1/2 selectors, subblock colors, codework table indices, etc.
static void selector_haar_transform_test(const gpu_image &g)
{
image_u8 g_unpacked;
g.unpack_image(g_unpacked);

image_utils::write_to_file("g_orig.png", g_unpacked);

gpu_image g_temp(g);

#define sqrt2 (1.4142135623730951f)

matrix44F haar_matrix(
.5f * 1, .5f * 1, .5f * 1, .5f * 1,
.5f * 1, .5f * 1, .5f * -1, .5f * -1,
.5f * sqrt2, .5f * -sqrt2, 0, 0,
0, 0, .5f * sqrt2, .5f * -sqrt2);

matrix44F inv_haar_matrix(haar_matrix.get_transposed());

for (uint block_y = 0; block_y < g_temp.get_blocks_y(); block_y++)
{
for (uint block_x = 0; block_x < g_temp.get_blocks_x(); block_x++)
{
etc_block &blk = g_temp.get_element_of_type<etc_block>(block_x, block_y);

matrix44F s;
for (uint y = 0; y < 4; y++)
for (uint x = 0; x < 4; x++)
s(x, y) = (float)blk.get_selector(x, y) + .5f;

matrix44F h(haar_matrix * s * inv_haar_matrix);

for (uint i = 0; i < 4; i++)
{
for (uint j = 0; j < 4; j++)
{
float q = h(i, j);

const float scale = 4.0f;
int iq = math::float_to_int_nearest(q * scale);

int quant = (i+j+1);

if (quant < 1)
quant = 1;

iq /= quant;

iq *= quant;

h(i, j) = iq / scale;
}
}

matrix44F ih(inv_haar_matrix * h * haar_matrix);

for (uint y = 0; y < 4; y++)
for (uint x = 0; x < 4; x++)
//blk.set_selector(x, y, math::clamp<int>((int)ih(x, y) + .5f, 0, 3));
blk.set_selector(x, y, math::clamp<int>((int)ih(x, y), 0, 3));
}
}

write_etc1_vis_images(g_temp, "g_temp_");

g_temp.unpack_image(g_unpacked);

image_utils::write_to_file("g.png", g_unpacked);
exit(0);
}

libsquish's DXT1 "Cluster Fit" method applied to ETC1

(This post is probably of interest to like a dozen people in the world, so it's kinda hairy.)

libsquish (a popular DXT encoding library) internally uses a total ordering based method to find high-quality DXT endpoints. This method can also be applied to ETC1 encoding, using the equations in rg_etc1's optimizer's remarks to solve for optimal subblock colors given each possible selector distribution in the total ordering and the current best intensity index and subblock color.

I don't actually compute the total ordering, I instead iterate over all selector distributions present in the total ordering because the actual per-pixel selector values don't matter to the solver. So basically, the new optimizer first tries the subblock's average color, then it computes and tries a series of "correction" factors (relative to the subblock's average color), which depend on the current intensity table index and the current best subblock color found so far (to account for clamping). A hash table is also used to prevent the optimizer from evaluating a trial solution more than once.

Single threaded results:

perceptual: 0 etc2: 0 rec709: 1
Source filename: kodak\kodim03.png 768x512

--- basislib Quality: 4
basislib time: 5.644
basislib ETC image Error: Max:  70, Mean: 1.952, MSE: 8.220, RMSE: 2.867, PSNR: 38.982, SSIM: 0.964853

--- etc2comp effort: 100
etc2comp time: 75.792851
etc2comp Error: Max:  75, Mean: 1.925, MSE: 8.009, RMSE: 2.830, PSNR: 39.095, SSIM: 0.965339

--- etcpak time: 0.006
etcpak Error: Max:  80, Mean: 2.492, MSE: 12.757, RMSE: 3.572, PSNR: 37.073, SSIM: 0.944697

--- ispc_etc time: 1.021655
ispc_etc1 Error: Max:  75, Mean: 1.965, MSE: 8.280, RMSE: 2.877, PSNR: 38.951, SSIM: 0.963916



After enabling multithreading (40 threads) in those encoders that support it:

J:\dev\basislib1\bin>texexp kodak\kodim03.png
perceptual: 0 etc2: 0 rec709: 1
Source filename: kodak\kodim03.png 768x512

--- basislib Quality: 4
basislib pack time: 0.266
basislib ETC image Error: Max:  70, Mean: 1.952, MSE: 8.220, RMSE: 2.867, PSNR: 38.982, SSIM: 0.964853

--- etc2comp effort: 100
etc2comp time: 3.608819
etc2comp Error: Max:  75, Mean: 1.925, MSE: 8.009, RMSE: 2.830, PSNR: 39.095, SSIM: 0.965339

--- etcpak time: 0.006
etcpak Error: Max:  80, Mean: 2.492, MSE: 12.757, RMSE: 3.572, PSNR: 37.073, SSIM: 0.944697

--- ispc_etc time: 1.054324

ispc_etc1 Error: Max:  75, Mean: 1.965, MSE: 8.280, RMSE: 2.877, PSNR: 38.951, SSIM: 0.963916

Intel is doing some kind of amazing SIMD dark magic in there. The ETC1 cluster fit method is around 10-27x faster than rg_etc1 (which uses my previous method, a hybrid of a 3D neighborhood search with iterative base color refinement) and etc2comp (effort 100) in ETC1 mode. RGB Avg. PSNR is usually within ~.1 dB of Intel.

I'm so tempted to update rg_etc1 with this algorithm, if only I had the time.

Update 10/1: Okay, I computed a histogram of the "winning" subblock average color correction factors applied over a few hundred test textures. I then selected the top 64 correction factors (out of 165), and don't bother trying the rest. Here's a graph showing the usage histogram of the selector distributions across all the test textures, sorted by frequency (the most successfully selector distributions are to the right).

This works well in my testing, for another 2.25 - 5x speedup (depending on the # of factors you choose to apply):

J:\dev\basislib1\bin>texexp  kodak\kodim03.png
perceptual: 0 etc2: 0 rec709: 1
Source filename: kodak\kodim03.png 768x512

--- basislib Quality: 4
basislib pack time: 0.118
basislib ETC image Error: Max:  70, Mean: 1.960, MSE: 8.276, RMSE: 2.877, PSNR: 38.953, SSIM: 0.964881

--- etc2comp effort: 100
etc2comp time: 3.621138
etc2comp Error: Max:  75, Mean: 1.925, MSE: 8.009, RMSE: 2.830, PSNR: 39.095, SSIM: 0.965339

--- etcpak time: 0.006
etcpak Error: Max:  80, Mean: 2.492, MSE: 12.757, RMSE: 3.572, PSNR: 37.073, SSIM: 0.944697

--- ispc_etc time: 1.038211
ispc_etc1 Error: Max:  75, Mean: 1.965, MSE: 8.280, RMSE: 2.877, PSNR: 38.951, SSIM: 0.963916

How It Works

rg_etc1 tries refining the current best subblock color found so far as it scans "around" the ETC1 444 or 555 color 3D lattice surrounding the subblock's average color. This refinement approach takes as input the current set of 2-bit selectors, the current best intensity table index, and the current best subblock color (only to account for clamping). Given this information, you can compute a RGB "correction" factor which is subtracted from the subblock's average color to compute a potentially better (lower error) subblock color.

Here's the basic math, from the comments:

// Now we have the input block, the avg. color of the input pixels, a set of trial selector indices, and the block color+intensity index.
// Now, for each component, attempt to refine the current solution by solving a simple linear equation. For example, for 4 pixels:
// The goal is:
// pixel0 - (block_color+inten_table[selector0]) + pixel1 - (block_color+inten_table[selector1]) + pixel2 - (block_color+inten_table[selector2]) + pixel3 - (block_color+inten_table[selector3]) = 0
// Rearranging this:
// (pixel0 + pixel1 + pixel2 + pixel3) - (block_color+inten_table[selector0]) - (block_color+inten_table[selector1]) - (block_color+inten_table[selector2]) - (block_color+inten_table[selector3]) = 0
// (pixel0 + pixel1 + pixel2 + pixel3) - block_color - inten_table[selector0] - block_color-inten_table[selector1] - block_color-inten_table[selector2] - block_color-inten_table[selector3] = 0
// (pixel0 + pixel1 + pixel2 + pixel3) - 4*block_color - inten_table[selector0] - inten_table[selector1] - inten_table[selector2] - inten_table[selector3] = 0
// (pixel0 + pixel1 + pixel2 + pixel3) - 4*block_color - (inten_table[selector0] + inten_table[selector1] + inten_table[selector2] + inten_table[selector3]) = 0
// (pixel0 + pixel1 + pixel2 + pixel3)/4 - block_color - (inten_table[selector0] + inten_table[selector1] + inten_table[selector2] + inten_table[selector3])/4 = 0
// block_color = (pixel0 + pixel1 + pixel2 + pixel3)/4 - (inten_table[selector0] + inten_table[selector1] + inten_table[selector2] + inten_table[selector3])/4
// So what this means:
// optimal_block_color = avg_input - avg_inten_delta
// So the optimal block color can be computed by taking the average block color and subtracting the current average of the intensity delta.
// Unfortunately, optimal_block_color must then be quantized to 555 or 444 so it's not always possible to improve matters using this formula.
// Also, the above formula is for unclamped intensity deltas. The actual implementation takes into account clamping.

To implement cluster fit for ETC1, you can iterate over the total ordering of all the selectors for each of the 8 subblock pixels, much like squish does in DXT1. However, doing this is unnecessary, because all that ultimately matters in the refinement equation is the computed avg_inten_delta, which just depends on the selector distribution (and not what each pixel's selector actually is).

Here's my current optimizer's compute() function. It first tries the subblock's average color (at coordinates m_br, m_bg, m_bb), to establish a baseline (minimally useful) solution, then it iterates over the precomputed (and sorted) selector distribution table and attempts applying (usually) a few dozen or so avg. color "correction" factors from this table. The table is sorted, so the entries with the highest probability of applying the best correction appear first (as mentioned above).

Note that evaluate_solution() uses a hash table to avoid trying the same solution more than once. The sorted table of total ordering selector distributions is at the bottom of this post.

// total_perms_to_try: 1-64 seems good enough (out of 165)
void etc1_optimizer::compute_internal_cluster_fit_fast(uint total_perms_to_try)
{
    if ((!m_best_solution.m_valid) || ((m_br != m_best_solution.m_coords.m_unscaled_color.r) || (m_bg != m_best_solution.m_coords.m_unscaled_color.g) || (m_bb != m_best_solution.m_coords.m_unscaled_color.b)))
    {
        evaluate_solution(etc1_solution_coordinates(m_br, m_bg, m_bb, 0, m_pParams->m_use_color4), m_trial_solution, &m_best_solution);
    }

    if ((m_best_solution.m_error == 0) || (!m_best_solution.m_valid))
        return;
            
    for (uint i = 0; i < total_perms_to_try; i++)
    {
        int delta_sum_r = 0, delta_sum_g = 0, delta_sum_b = 0;

        const int *pInten_table = g_etc1_inten_tables[m_best_solution.m_coords.m_inten_table];
        const color_quad_u8 base_color(m_best_solution.m_coords.get_scaled_color());

        const uint8 *pNum_selectors = g_cluster_fit_order_tab[i].m_v;

        for (uint q = 0; q < 4; q++)
        {
            const int yd_temp = pInten_table[q];

            delta_sum_r += pNum_selectors[q] * (math::clamp<int>(base_color.r + yd_temp, 0, 255) - base_color.r);
            delta_sum_g += pNum_selectors[q] * (math::clamp<int>(base_color.g + yd_temp, 0, 255) - base_color.g);
            delta_sum_b += pNum_selectors[q] * (math::clamp<int>(base_color.b + yd_temp, 0, 255) - base_color.b);
        }

        if ((!delta_sum_r) && (!delta_sum_g) && (!delta_sum_b))
            continue;

        const float avg_delta_r_f = static_cast<float>(delta_sum_r) / 8;
        const float avg_delta_g_f = static_cast<float>(delta_sum_g) / 8;
        const float avg_delta_b_f = static_cast<float>(delta_sum_b) / 8;

        const int br1 = math::clamp<int>(static_cast<uint>((m_avg_color[0] - avg_delta_r_f) * m_limit / 255.0f + .5f), 0, m_limit);
        const int bg1 = math::clamp<int>(static_cast<uint>((m_avg_color[1] - avg_delta_g_f) * m_limit / 255.0f + .5f), 0, m_limit);
        const int bb1 = math::clamp<int>(static_cast<uint>((m_avg_color[2] - avg_delta_b_f) * m_limit / 255.0f + .5f), 0, m_limit);

#if BASISLIB_DEBUG_ETC_ENCODER_DEEPER
        printf("Second refinement trial %u, avg_delta %f %f %f\n", refinement_trial, avg_delta_r_f, avg_delta_g_f, avg_delta_b_f);
#endif

        evaluate_solution(etc1_solution_coordinates(br1, bg1, bb1, 0, m_pParams->m_use_color4), m_trial_solution, &m_best_solution);

        if (m_best_solution.m_error == 0)
            break;
    }
}

const uint BASISLIB_CLUSTER_FIT_ORDER_TABLE_SIZE = 165;

static const struct { uint8 m_v[4]; } g_cluster_fit_order_tab[BASISLIB_CLUSTER_FIT_ORDER_TABLE_SIZE] =
{
    { 0, 0, 0, 8 }, { 0, 5, 2, 1 }, { 0, 6, 1, 1 }, { 0, 7, 0, 1 }, { 0, 7, 1, 0 },
    { 0, 0, 8, 0 }, { 0, 0, 3, 5 }, { 0, 1, 7, 0 }, { 0, 0, 4, 4 }, { 0, 0, 2, 6 },
    { 0, 0, 7, 1 }, { 0, 0, 1, 7 }, { 0, 0, 5, 3 }, { 1, 6, 0, 1 }, { 0, 0, 6, 2 },
    { 0, 2, 6, 0 }, { 2, 4, 2, 0 }, { 0, 3, 5, 0 }, { 3, 3, 1, 1 }, { 4, 2, 0, 2 },
    { 1, 5, 2, 0 }, { 0, 5, 3, 0 }, { 0, 6, 2, 0 }, { 2, 4, 1, 1 }, { 5, 1, 0, 2 },
    { 6, 1, 1, 0 }, { 3, 3, 0, 2 }, { 6, 0, 0, 2 }, { 0, 8, 0, 0 }, { 6, 1, 0, 1 },
    { 0, 1, 6, 1 }, { 1, 6, 1, 0 }, { 4, 1, 3, 0 }, { 0, 2, 5, 1 }, { 5, 0, 3, 0 },
    { 5, 3, 0, 0 }, { 0, 1, 5, 2 }, { 0, 3, 4, 1 }, { 2, 5, 1, 0 }, { 1, 7, 0, 0 },
    { 0, 1, 4, 3 }, { 6, 0, 2, 0 }, { 0, 4, 4, 0 }, { 2, 6, 0, 0 }, { 0, 2, 4, 2 },
    { 0, 5, 1, 2 }, { 0, 6, 0, 2 }, { 3, 5, 0, 0 }, { 0, 4, 3, 1 }, { 3, 4, 1, 0 },
    { 4, 3, 1, 0 }, { 1, 5, 0, 2 }, { 0, 3, 3, 2 }, { 1, 4, 1, 2 }, { 0, 4, 2, 2 },
    { 2, 3, 3, 0 }, { 4, 4, 0, 0 }, { 1, 2, 4, 1 }, { 0, 5, 0, 3 }, { 0, 1, 3, 4 },
    { 1, 5, 1, 1 }, { 1, 4, 2, 1 }, { 1, 3, 2, 2 }, { 5, 2, 1, 0 }, { 1, 3, 3, 1 },
    { 0, 1, 2, 5 }, { 1, 1, 5, 1 }, { 0, 3, 2, 3 }, { 2, 5, 0, 1 }, { 3, 2, 2, 1 },
    { 2, 3, 0, 3 }, { 1, 4, 3, 0 }, { 2, 2, 1, 3 }, { 6, 2, 0, 0 }, { 1, 0, 6, 1 },
    { 3, 3, 2, 0 }, { 7, 1, 0, 0 }, { 3, 1, 4, 0 }, { 0, 2, 3, 3 }, { 0, 4, 1, 3 },
    { 0, 4, 0, 4 }, { 0, 1, 0, 7 }, { 2, 0, 5, 1 }, { 2, 0, 4, 2 }, { 3, 0, 2, 3 },
    { 2, 2, 4, 0 }, { 2, 2, 3, 1 }, { 4, 0, 3, 1 }, { 3, 2, 3, 0 }, { 2, 3, 2, 1 },
    { 1, 3, 4, 0 }, { 7, 0, 1, 0 }, { 3, 0, 4, 1 }, { 1, 0, 5, 2 }, { 8, 0, 0, 0 },
    { 3, 0, 1, 4 }, { 4, 1, 1, 2 }, { 4, 0, 2, 2 }, { 1, 2, 5, 0 }, { 4, 2, 1, 1 },
    { 3, 4, 0, 1 }, { 2, 0, 3, 3 }, { 5, 0, 1, 2 }, { 5, 0, 0, 3 }, { 2, 4, 0, 2 },
    { 2, 1, 4, 1 }, { 4, 0, 1, 3 }, { 2, 1, 5, 0 }, { 4, 2, 2, 0 }, { 4, 0, 4, 0 },
    { 1, 0, 4, 3 }, { 1, 4, 0, 3 }, { 3, 0, 3, 2 }, { 4, 3, 0, 1 }, { 0, 1, 1, 6 },
    { 1, 3, 1, 3 }, { 0, 2, 2, 4 }, { 2, 0, 2, 4 }, { 5, 1, 1, 1 }, { 3, 0, 5, 0 },
    { 2, 3, 1, 2 }, { 3, 0, 0, 5 }, { 0, 3, 1, 4 }, { 5, 0, 2, 1 }, { 2, 1, 3, 2 },
    { 2, 0, 6, 0 }, { 3, 1, 3, 1 }, { 5, 1, 2, 0 }, { 1, 0, 3, 4 }, { 1, 1, 6, 0 },
    { 4, 0, 0, 4 }, { 2, 0, 1, 5 }, { 0, 3, 0, 5 }, { 1, 3, 0, 4 }, { 4, 1, 2, 1 },
    { 1, 2, 3, 2 }, { 3, 1, 0, 4 }, { 5, 2, 0, 1 }, { 1, 2, 2, 3 }, { 3, 2, 1, 2 },
    { 2, 2, 2, 2 }, { 6, 0, 1, 1 }, { 1, 2, 1, 4 }, { 1, 1, 4, 2 }, { 3, 2, 0, 3 },
    { 1, 2, 0, 5 }, { 1, 0, 7, 0 }, { 3, 1, 2, 2 }, { 1, 0, 2, 5 }, { 2, 0, 0, 6 },
    { 2, 1, 1, 4 }, { 2, 2, 0, 4 }, { 1, 1, 3, 3 }, { 7, 0, 0, 1 }, { 1, 0, 0, 7 },
    { 2, 1, 2, 3 }, { 4, 1, 0, 3 }, { 3, 1, 1, 3 }, { 1, 1, 2, 4 }, { 2, 1, 0, 5 },
    { 1, 0, 1, 6 }, { 0, 2, 1, 5 }, { 0, 2, 0, 6 }, { 1, 1, 1, 5 }, { 1, 1, 0, 6 } 
};