Lossy Block Reduction Filter 0

/*
Copyright (C) 2013 by Brendan G Bohannon
Email: cr88192@gmail.com
Copying: http://pastebin.com/iJxtZHm6
 */

/*
Lossy Block Reduction Filter.

Goal: Reduce the number of distinct pixel blocks such that subsequent compression of DXT output will compress better.

This is done as an image pre-filter rather than as part of the block-encoding process mostly to generalize over some of the subsequent encoding steps.

Note: May write over the edges or past the end of the image if it is not evenly divisible by the block size.

This estimates the block similarily mostly via MSE (Mean Square Error).
Tests show that this will introduce blocky artifacts with gradients.
 */

#include <bgbbtj.h>

// #define BLKSZ    8
// #define BLKSZ    2
#define BLKSZ   4
#define BLKSZ2  (BLKSZ*BLKSZ)

int *filtlbr_block_vals;
int *filtlbr_block_yval;
byte *filtlbr_block_cvals;
short *filtlbr_block_cyval;
int *filtlbr_block_cnt;
int filtlbr_n_blocks;

void BGBBTJ_FiltLBR_GetIndexBlock(int idx, byte *buf)
{
    int i, n;

    memcpy(buf, filtlbr_block_cvals+(idx*(BLKSZ2*4)), BLKSZ2*4);
}

int BGBBTJ_FiltLBR_GetIndexBlockY(int idx)
{
    return(filtlbr_block_cyval[idx]);
}

void BGBBTJ_FiltLBR_AddIndexBlock(int idx, byte *buf)
{
    int i, j, n;

    i=BGBBTJ_FiltLBR_CalcBlockY(buf);
    filtlbr_block_yval[idx]+=i;

    for(i=0; i<(BLKSZ2*4); i++)
    {
        filtlbr_block_vals[idx*(BLKSZ2*4)+i]+=buf[i];
    }
    filtlbr_block_cnt[idx]++;

    n=filtlbr_block_cnt[idx];
    j=filtlbr_block_yval[idx]/n;
    filtlbr_block_cyval[idx]=j;

    for(i=0; i<(BLKSZ2*4); i++)
    {
        j=filtlbr_block_vals[idx*(BLKSZ2*4)+i]/n;
        if(j<0)j=0;
        if(j>255)j=255;
        filtlbr_block_cvals[idx*(BLKSZ2*4)+i]=j;
    }

#if 0
    j=BGBBTJ_FiltLBR_CalcBlockY(filtlbr_block_cvals+(idx*(BLKSZ2*4)));
    filtlbr_block_cyval[idx]=j;
#endif
}

int BGBBTJ_FiltLBR_CalcBlockY(byte *buf)
{
    int i, j, k;

    k=0;
    for(i=0; i<BLKSZ2; i++)
    {
        j=buf[i*4+0]+2*buf[i*4+1]+buf[i*4+2]+(buf[i*4+3]>>1);
        k+=j;
    }
    return(k/BLKSZ2);
}

int BGBBTJ_FiltLBR_CompareBlock(byte *blka, byte *blkb)
{
    int i, j, n;

    n=0;
    for(i=0; i<(BLKSZ2*4); i++)
    {
        j=blka[i]-blkb[i];
        n+=j*j;
    }
    return(n/(BLKSZ2*4));
}

int BGBBTJ_FiltLBR_GetImageBlock(
    byte *img, int xstride, int ystride,
    byte *block)
{
    int i, j;

    for(i=0; i<BLKSZ; i++)
        for(j=0; j<BLKSZ; j++)
    {
        block[(i*BLKSZ+j)*4+0]=img[(i*ystride)+(j*xstride)+0];
        block[(i*BLKSZ+j)*4+1]=img[(i*ystride)+(j*xstride)+1];
        block[(i*BLKSZ+j)*4+2]=img[(i*ystride)+(j*xstride)+2];
        block[(i*BLKSZ+j)*4+3]=img[(i*ystride)+(j*xstride)+3];
    }
}

int BGBBTJ_FiltLBR_SetImageBlock(
    byte *img, int xstride, int ystride,
    byte *block)
{
    int i, j;

    for(i=0; i<BLKSZ; i++)
        for(j=0; j<BLKSZ; j++)
    {
        img[(i*ystride)+(j*xstride)+0]=block[(i*BLKSZ+j)*4+0];
        img[(i*ystride)+(j*xstride)+1]=block[(i*BLKSZ+j)*4+1];
        img[(i*ystride)+(j*xstride)+2]=block[(i*BLKSZ+j)*4+2];
        img[(i*ystride)+(j*xstride)+3]=block[(i*BLKSZ+j)*4+3];
    }
}

int BGBBTJ_FiltLBR_LookupMatchIndexBlock(byte *blk, int mmse)
{
    byte tblk[BLKSZ2*4];
    int bi, be;
    int i, j, yv;

    yv=BGBBTJ_FiltLBR_CalcBlockY(blk);

    bi=-1; be=mmse;
    for(i=0; i<filtlbr_n_blocks; i++)
    {
        j=BGBBTJ_FiltLBR_GetIndexBlockY(i);
        j=j-yv; j=j*j;
        if(j>be)continue;

        BGBBTJ_FiltLBR_GetIndexBlock(i, tblk);
        j=BGBBTJ_FiltLBR_CompareBlock(tblk, blk);
        if(j<be) { bi=i; be=j; }
    }

    return(bi);
}

int BGBBTJ_FiltLBR_GetMatchIndexBlock(byte *blk, int mmse)
{
    int i;

    i=BGBBTJ_FiltLBR_LookupMatchIndexBlock(blk, mmse);
    if(i>=0)return(i);
    i=filtlbr_n_blocks++;
    BGBBTJ_FiltLBR_AddIndexBlock(i, blk);
    return(i);
}

/**
 * Filter image, where irgba and orgba give the input and output images.
 * xs and ys give the size, and qf gives the quality (low 8 bits, 0-100).
 */
BGBBTJ_API void BGBBTJ_FiltLBR_FilterImage(
    byte *orgba, byte *irgba, int xs, int ys, int qf)
{
    byte tblk[BLKSZ2*4];
    int *bidx;
    int x, y, xs2, ys2, xstr, ystr;
    int idx, idx1, mmse;

    if((qf&255)>=100)
    {
        memcpy(orgba, irgba, xs*ys*4);
        return;
    }

    printf("BGBBTJ_FiltLBR_FilterImage: Begin\n");

    xs2=(xs+BLKSZ-1)/BLKSZ;
    ys2=(ys+BLKSZ-1)/BLKSZ;

    filtlbr_block_vals=malloc(xs2*ys2*(BLKSZ2*4)*sizeof(int));
    filtlbr_block_yval=malloc(xs2*ys2*sizeof(int));
    filtlbr_block_cnt=malloc(xs2*ys2*sizeof(int));
    filtlbr_n_blocks=0;

    filtlbr_block_cvals=malloc(xs2*ys2*(BLKSZ2*4));
    filtlbr_block_cyval=malloc(xs2*ys2*sizeof(short));

    memset(filtlbr_block_vals, 0, xs2*ys2*(BLKSZ2*4)*sizeof(int));
    memset(filtlbr_block_yval, 0, xs2*ys2*sizeof(int));
    memset(filtlbr_block_cnt, 0, xs2*ys2*sizeof(int));

    bidx=malloc(xs2*ys2*sizeof(int));

    xstr=4; ystr=xs*4;
//  mmse=95-(qf&255);
//  mmse=90-(qf&255);
//  mmse=100-(qf&255);
//  mmse=256-(qf&255);

//  mmse=1.0+10.0*(pow(100.0/(qf&255), 2)-1.0);
    mmse=1.0+10.0*((100.0/(qf&255))-1.0);

    if(mmse<0)mmse=0;
    mmse=mmse*mmse;

    for(y=0; y<ys2; y++)
    {
        printf("BGBBTJ_FiltLBR_FilterImage: %d/%d %d/%d\r",
            y, ys2, filtlbr_n_blocks, y*xs2);
        for(x=0; x<xs2; x++)
        {
            BGBBTJ_FiltLBR_GetImageBlock(irgba+(y*BLKSZ*ystr)+(x*BLKSZ*xstr),
                xstr, ystr, tblk);
            idx=BGBBTJ_FiltLBR_GetMatchIndexBlock(tblk, mmse);
//          BGBBTJ_FiltLBR_AddIndexBlock(idx, tblk);
            bidx[y*xs2+x]=idx;
        }

        printf("BGBBTJ_FiltLBR_FilterImage: %d/%d %d/%d\r",
            y, ys2, filtlbr_n_blocks, y*xs2);
    }
    printf("\n");

#if 1
    for(y=0; y<ys2; y++)
    {
//      printf("BGBBTJ_FiltLBR_FilterImage: %d/%d %d/%d\r",
//          y, ys2, filtlbr_n_blocks, y*xs2);
        for(x=0; x<xs2; x++)
        {
            BGBBTJ_FiltLBR_GetImageBlock(irgba+(y*BLKSZ*ystr)+(x*BLKSZ*xstr),
                xstr, ystr, tblk);
//          idx=BGBBTJ_FiltLBR_GetMatchIndexBlock(tblk, mmse);
            idx=bidx[y*xs2+x];
            BGBBTJ_FiltLBR_AddIndexBlock(idx, tblk);
//          bidx[y*xs2+x]=idx;
        }

//      printf("BGBBTJ_FiltLBR_FilterImage: %d/%d %d/%d\r",
//          y, ys2, filtlbr_n_blocks, y*xs2);
    }
//  printf("\n");
#endif

    for(y=0; y<ys2; y++)
        for(x=0; x<xs2; x++)
    {
        idx=bidx[y*xs2+x];

#if 0
        printf("BGBBTJ_FiltLBR_FilterImage: %d/%d %d/%d\r",
            y, ys2, filtlbr_n_blocks, y*xs2);

        BGBBTJ_FiltLBR_GetImageBlock(irgba+(y*BLKSZ*ystr)+(x*BLKSZ*xstr),
            xstr, ystr, tblk);
//      idx1=BGBBTJ_FiltLBR_LookupMatchIndexBlock(tblk, mmse);
        idx1=BGBBTJ_FiltLBR_GetMatchIndexBlock(tblk, mmse);
        if(idx1>=0)idx=idx1;
#endif

        BGBBTJ_FiltLBR_GetIndexBlock(idx, tblk);
        BGBBTJ_FiltLBR_SetImageBlock(orgba+(y*BLKSZ*ystr)+(x*BLKSZ*xstr),
            xstr, ystr, tblk);
    }
//  printf("\n");

    free(bidx);
    free(filtlbr_block_vals);
    free(filtlbr_block_yval);
    free(filtlbr_block_cvals);
    free(filtlbr_block_cyval);
    free(filtlbr_block_cnt);

    printf("BGBBTJ_FiltLBR_FilterImage: Done\n");
}