Colour Subsampling

[Reverend]

Aths,
I'd like to make comments on your work but to do it properly requires quite a bit of time and I'm really a bit busy at the moment.

Okay, which new patent got you scrambling?

 

[Hyp-X]

The way to do it is to compute the principal axis through the set of pixels in the block. You do that by computing the correlation matrix of the RGB values and then calculate the principal eigenvector of that matrix. That gives the direction of the axis which also passes through the average of the colours.

Once you have that, you can map all your pixels into a 1 dimensional system which makes it a lot simpler.

Sounds like how I did it for our engine.
One question though:
How do you handle the case where mapping a pixel to that axis makes the mapped pixel fall out of the [0..1] range? (That is the endpoint is not representable.)

 

[Simon F]

The way to do it is to compute the principal axis through the set of pixels in the block. You do that by computing the correlation matrix of the RGB values and then calculate the principal eigenvector of that matrix. That gives the direction of the axis which also passes through the average of the colours.

Once you have that, you can map all your pixels into a 1 dimensional system which makes it a lot simpler.

Sounds like how I did it for our engine.
One question though:
How do you handle the case where mapping a pixel to that axis makes the mapped pixel fall out of the [0..1] range? (That is the endpoint is not representable.)

Well, an indvidual pixel that maps to a point on that line which is outside the RBG colour cube doesn't really matter. What does matter is that you choose your 2 rep colours so that they do lie inside the RGB cube, which is probably going to be very likely anyway. After all, you're going to have a distribution of pixel=>1D mappings which might look like:

  . . A..    .    .   ...    .   .   ..B. . .

where the a "." represents a pixel and the "A" and "B" are representative colours. Some of the pixels are very likely to be outside of the line segment between A and B.

 

[aths]

Aths,
I'd like to make comments on your work but to do it properly requires quite a bit of time and I'm really a bit busy at the moment.

But just quickly...

Thanks to your posting, I now have a new idea of finding good S3TC reference colours:

The way to do it is to compute the principal axis through the set of pixels in the block. You do that by computing the correlation matrix of the RGB values and then calculate the principal eigenvector of that matrix. That gives the direction of the axis which also passes through the average of the colours.

Once you have that, you can map all your pixels into a 1 dimensional system which makes it a lot simpler.

Why don't map the 4x4 texels into a 1D line of 16 values in the first place? I think, the quality measurement counts the average per-texel-error, so the 2D-position the texel shouldn't matter.

 

[Rolf N]

Why don't map the 4x4 texels into a 1D line of 16 values in the first place? I think, the quality measurement counts the average per-texel-error, so the 2D-position the texel shouldn't matter.

RGB is a 3D problem. You can't immediately turn it into 1D problems because you only have one index per encoded texel.
Or did you mean something else?

 

[Simon F]

Why don't map the 4x4 texels into a 1D line of 16 values in the first place? I think, the quality measurement counts the average per-texel-error, so the 2D-position the texel shouldn't matter.

Errr... that's sort of what I'm saying. Map the 16 points onto a line but you have to choose the correct line and you get that by computing the principal axis.

It's standard practice for vector quantisation.

 

[aths]

Why don't map the 4x4 texels into a 1D line of 16 values in the first place? I think, the quality measurement counts the average per-texel-error, so the 2D-position the texel shouldn't matter.

Errr... that's sort of what I'm saying. Map the 16 points onto a line but you have to choose the correct line and you get that by computing the principal axis.

It's standard practice for vector quantisation.

I am not fluid in "mathematical english", so I don't exactly know what you mean with principal axis, neither what the eigenvector is. (Even though it sounds like a germanism.) Wikipedia's explanations are very abstract so I don't really understand them.

Why don't map the 4x4 texels into a 1D line of 16 values in the first place? I think, the quality measurement counts the average per-texel-error, so the 2D-position the texel shouldn't matter.

RGB is a 3D problem. You can't immediately turn it into 1D problems because you only have one index per encoded texel.
Or did you mean something else?

I know that my approach with independend R, G and B min and max value is quite suboptimal because it searches the start- and end points seperately instead of considering the whole colour in the first place. I still don't understand the trick how to correctly incorporate the combined RGB colour vector. I think in the end it is the (weightet) averaged line of the 3 seperate lines (for R, G and B).

 

[Simon F]

I am not fluid in "mathematical english", so I don't exactly know what you mean with principal axis,

Imagine a LOT of pixel values are plotted in an a RGB cube. They would form a cloud of points. The principal axis is the line going through the 'longest' part of the cloud in a "best fit" sence.

neither what the eigenvector is. (Even though it sounds like a germanism.) Wikipedia's explanations are very abstract so I don't really understand them.

I would think it was probably Gauss or someone like that who invented it.

A simple definition: if you have a matrix M, then all of its eigenvectors, e.g. Ei, and associated scalar eigenvalue, lambda_i satisfy:

M.Ei =  lambda_i * Ei

i.e. Multiplying the Matrix by the eigenvector looks like you are just scaling it by its eigenvalue.

The principal eigenvector is the one with the largest magnitude eigenvalue.

Anyway, these are really useful mathematical tools to understand if you are going to get involved in image compression.

 

[aths]

I am not fluid in "mathematical english", so I don't exactly know what you mean with principal axis,

Imagine a LOT of pixel values are plotted in an a RGB cube. They would form a cloud of points. The principal axis is the line going through the 'longest' part of the cloud in a "best fit" sence.

So it is a kind of a regression curve?

It looks like that axis must fulfill to have the lowest differences (as orthogonal vectors on that line to each rgb value). May be that line also goes through the average value of all vector components.

While computable, it does not look that easy to get the principal axis, but I don't investigated possibilities yet, to simplify the formula. (The 1d linear regression with Gauss' method is quite easy, if one knows, how to simplify.)

neither what the eigenvector is. (Even though it sounds like a germanism.) Wikipedia's explanations are very abstract so I don't really understand them.

I would think it was probably Gauss or someone like that who invented it.

A simple definition: if you have a matrix M, then all of its eigenvectors, e.g. Ei, and associated scalar eigenvalue, lambda_i satisfy:

M.Ei =  lambda_i * Ei

i.e. Multiplying the Matrix by the eigenvector looks like you are just scaling it by its eigenvalue.

The principal eigenvector is the one with the largest magnitude eigenvalue.

Anyway, these are really useful mathematical tools to understand if you are going to get involved in image compression.

The eigenvalue is a "cell" of the matrix? Does eigenvalues and -vectors have anything to do with the determinant? Either I just don't got what you trying to explain because I cannot see the deeper sense of your formula, or this is an application of matrices I never heard of until your posting. As far as I understand, that eigen-stuff is a tool to calculate the principal axis in an efficient way.

We used the matrix mainly to get the determinant, to transform (only scale and translate iirc) or to solve equations.

May be I find a book with an explanation. That whole topic looks interesting.

 

[Simon F]

Imagine a LOT of pixel values are plotted in an a RGB cube. They would form a cloud of points. The principal axis is the line going through the 'longest' part of the cloud in a "best fit" sence.

So it is a kind of a regression curve?

I guess it is the line of best fit in N dimensional space. For example, when I wrote the VQ compressor for Dreamcast, I was computing the axis in 16 dimensional space. Luckily for you, you are probably only working in 3D RGB or YUV.

While computable, it does not look that easy to get the principal axis, but I don't investigated possibilities yet, to simplify the formula.

Simplify the formula? It's quite straightforward. Compute the Covariance matrix, i.e. you need to compute covariances of the R,G,B etc terms of each pixel. (HMMM I just looked at that link again, and it's not the best explanation)

Once you have that matrix, you need to compute the principal eigenvector.

Now, there are complex ways (e.g. Jacobi's method) to get all the eigenvectors/values but I'll let you in on a little hint that Konstantine Iourcha (one of the inventors of S3TC/DXTC) gave me. You only need the principal eigenvector which you can get by repeatedly squaring the covariance matrix (with rescaling to stop over/underflow) to get a candidate vector. Do a google search - there's sure to be source code for this procedure.

The eigenvalue is a "cell" of the matrix?

I don't know that term.

Does eigenvalues and -vectors have anything to do with the determinant?

Errr.... I'd imagine that the product of all the eigenvalues probably equals the determinant, but I don't know for certain. I don't think it's really relevant here.

Either I just don't got what you trying to explain because I cannot see the deeper sense of your formula, or this is an application of matrices I never heard of until your posting. As far as I understand, that eigen-stuff is a tool to calculate the principal axis in an efficient way.
We used the matrix mainly to get the determinant, to transform (only scale and translate iirc) or to solve equations.

May be I find a book with an explanation. That whole topic looks interesting.

Well, it is interesting to me now because I'm involved in computer graphics. I just wish I'd been more attentive in the lectures at Uni (which were 2 years before the graphics bug bit me)

 

[Simon F]

Aths,
Getting back to your original posting, your experiments reminded me of Strom and Akenine-Mollers' Packman texture compression method.

 

[Mate Kovacs]

The eigenvalue is a "cell" of the matrix?

I don't know that term.

He meant "element", I think. In that case the answer is no.

 

[squarewithin]

Anyway, these are really useful mathematical tools to understand if you are going to get involved in image compression.

Or, pretty much anything. Numerical analysis is an entire field of solutions looking for problems.

 

[aths]

The eigenvalue is a "cell" of the matrix?

I don't know that term.

He meant "element", I think. In that case the answer is no.

Yes, I meant element.

Anyway, these are really useful mathematical tools to understand if you are going to get involved in image compression.

Or, pretty much anything. Numerical analysis is an entire field of solutions looking for problems.

I read some articles about the eigenvalueproblem now, but I still don't got the main idea. Also I find it confusing to read this is a method to seperate significant parameters from the others.

Simon, do you use the eigenvalues for a principal components analysis (I use that word yet without to fully know what it is) or for a "full" solution?

 

[aths]

Aths,
Getting back to your original posting, your experiments reminded me of Strom and Akenine-Mollers' Packman texture compression method.

While I also thought about modify the average tile color, that Strom and Akenine-Mollers' approach is different in some ways I thought about. Interesting, though. I took some minutes to understand how it should work. It is a clever concept to aviod a second reference colour at all.

It also should work for 4x4 tiles, leading to a bitrate of 3 bpp. That would destroy my proposition one cannot significantly go under 4 bpps. – with higher errors, though.

 

[Hyp-X]

Ok it turns out I didn't know what eigenvectors are (I still don't quite get it.)

I simply chose the component with the largest variance and the two associated covariances and used that as the direction vector of the line.
(I used the means as the starting point.)

It looks good - I'm wondering how far this is from the right solution...

 

[Dio]

Eigenvectors are the best quality way to find the axis (but there are faster methods that provide nearly equivalent quality).

 

[Simon F]

Ok it turns out I didn't know what eigenvectors are (I still don't quite get it.)

I simply chose the component with the largest variance and the two associated covariances and used that as the direction vector of the line.
(I used the means as the starting point.)

Well, you are virtually all the way there. You've got your covariance matrix:

[ RR   RG   RB ]
[ RG   GG  GB ]
[ RB   GB  BB  ]

Instead of just choosing the row/column that contains the largest diagonal value, you get the principal eigenvector (assuming there actually is one that's the largest. I mean, you won't get far if all your colours are completely uniformly distributed! )

If e is your principal eigenvector and L the eigenvalue, then we know that M.e = L.e, and since L is the largest eigenvalue, if you keep on squaring the matrix (and "rescaling" to stop over/underflow) the whole matrix will converge to the principal vector.
For most image data, it doesn't take many iterations to converge. (If it doesn't, then your data is possibly not really suited to S3TC anyway ).