Thursday, November 6, 2008

Fractal compression. Comparision of two blocks.

Here I want to write implementation of function which gets minimum distance between two blocks. Every block has N (block_size * block_size) elements. In my case block_size = 8. And every element of block is byte. So the function gets two such blocks and find minimum distance between them using different values for Factor (F) an Shift(S) of one block. Here some mathematical equations for solving this problem.



Comments for the code:
  • Block - is a class of one block (8x8 bytes) element.
  • _data - array of elements of this block (b)
  • bl - array of elements of bl block (a)
  • diri - is a Sum(ai*bi)
  • d - is a Sum(ai)
  • r - is a Sum(bi)
  • d2 - is a Sum(ai*ai)
  • r2 - is a Sum(bi*bi)

[C++ code] :

BlockDistance Block::Distance( Block *bl )
{
BlockDistance bd;
int diri = std::inner_product(_data, _data + block_size * block_size, &((*bl)[0]), 0);
int d=getR(), r=bl->getR(), d2 = getR2(), r2 = bl->getR2();
int N = block_size*block_size;
if (N*d2-d*d != 0.0)
bd.Factor = (double)(N*diri-d*r)/(double)(N*d2-d*d);
else bd.Factor = 0.0;
bd.Shift = (r-bd.Factor*d)/(double)N;
double ddd = d2 + (bd.Factor * bd.Factor * r2) + N * (bd.Shift * bd.Shift) - 2 * (bd.Factor * diri) - 2* (d * bd.Shift) + 2 * (bd.Factor * bd.Shift * r);
bd.Distance = ddd / N;
return bd;
}

This method also used the following functions. Them calculates Sum(ai) and Sum(ai*ai) and saves calculated value into some cache variable, because these values are used many times.

[C++ code]:

inline int getR()
{
if (!(_calculated_flags & 1))
{
_r = std::accumulate(_data, _data + block_size * block_size, 0);
_calculated_flags ^= 1;
}
return _r;
}
inline int getR2()
{
if (!(_calculated_flags & 2))
{
_r2 = std::inner_product(_data, _data + block_size * block_size, _data, 0);
_calculated_flags ^= 2;
}
return _r2;
}

Fractal compression. Introduction.

I have no time to introduce you to fractal compression. So I just give you a link to wikipedia.

http://en.wikipedia.org/wiki/Fractal_compression

In my following posts I want to show implementation of some functions used by fractal compressor and decompressor.