Try   HackMD

Enhance DCT (discrete cosine transform) kernel function, RV32IM (w/ Fixed-point Arithmetic)

Contirbuted by < Brian Cheng >

Motivation

In this project I want to implement DCT into RV32IM.I chose the project jpeg-encoder from Michael Schier's github.

Introduction

The Discrete Cosine Transform (DCT) stands as a fundamental mathematical transformation extensively employed in the realms of signal processing and data compression applications. Its pivotal application lies in the domain of jpeg standard image compression, where it serves as a cornerstone for efficiently representing image data.

Given the limitations of the human visual system, particularly its reduced sensitivity to high-frequency signals, the DCT is instrumental in capturing and representing essential image features while minimizing the impact of components that might be less perceptible to the human eye. This attribute contributes significantly to the effectiveness of image compression algorithms, as it allows for the removal or quantization of high-frequency components without significantly compromising the perceived visual quality of the compressed image. Therefore, the integration of the DCT in JPEG compression plays a crucial role in achieving a balance between compression efficiency and perceptual quality.

This transform is applied to an 8x8 block of image data. The indices (x, y) in the formula represent the spatial frequencies, and (i, j) represent the pixel coordinates within the block.

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

The result of applying the 2D-DCT to an 8x8 block leads to coefficients that represent different frequency components. The position (i, j) in the resulting image corresponds to the spatial location of these coefficients. This is often visualized in a plot like the one you provided:

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

Each position (i, j) in the resulting image corresponds to a specific frequency component, and the brightness or color intensity at that position indicates the magnitude of the corresponding DCT coefficient.

Attemptation

From Discrete Cosine Transform (DCT) of Images and Image Compression we learn

F(p,q)=Tf(x,y)T
f(x,y)=TF(p,q)T

when the block is
MM

T(u,v)=1Mcos[(2x+1)uπ2M]cos[(2y+1)vπ2M],0u,vM1

At this time I want to implement formula above to complete my dct function.
I found that matlab have the function to generate

T Matrix.

B=zeros([8,8]);
D=dctmtx(size(B,1));

And the result is

D=[0.35360.35360.35360.35360.35360.35360.35360.35360.49040.41570.27780.09750.09750.27780.41570.49040.46190.19130.19130.46190.46190.19130.19130.46190.41570.09750.49040.27780.27780.49040.09750.41570.35360.35360.35360.35360.35360.35360.35360.35360.27780.49040.09750.41570.41570.09750.49040.27780.19130.46190.46190.19130.19130.46190.46190.19130.09750.27780.41570.49040.49040.41570.27780.0975]

But if I want to implement this function into my code I should write my own function, and as below:

T=zeros([8,8]);
for X=1:8
    x=X-1;
    for Y=1:8
        y=Y-1;
        if(x==0)
            T(X,Y)=1/(sqrt(8));
        else
            T(X,Y)=sqrt(2/8)*cos((pi*(2*y+1)*x)/(16));
        end
    end
end

And the result is

T=[0.35360.35360.35360.35360.35360.35360.35360.35360.49040.41570.27780.09750.09750.27780.41570.49040.46190.19130.19130.46190.46190.19130.19130.46190.41570.09750.49040.27780.27780.49040.09750.41570.35360.35360.35360.35360.35360.35360.35360.35360.27780.49040.09750.41570.41570.09750.49040.27780.19130.46190.46190.19130.19130.46190.46190.19130.09750.27780.41570.49040.49040.41570.27780.0975]

We can see the

D=T, so the logic for the function I wrote is correct.

Work

  1. tranfer integer to fixed-point architecture
  2. matrix transpose
  3. matrix binary multiplier

Implement

  • C code

The following C code is The follow

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <assert.h>
#include <sys/time.h>

double cos_lookup[8][8];
void init_dct_lookup()
{
	int i, j;
	for (i=0; i<8; i++)
		for (j=0; j<8; j++)
		{
			cos_lookup[i][j] = cos( (2*i+1)*j*M_PI/16 );
			assert( -1<=cos_lookup[i][j] && cos_lookup[i][j]<=1 );
		}
}

inline void dct_block(int gap, int in[], double out[])
{
	int x_f, y_f; // frequency domain coordinates
	int x_t, y_t; // time domain coordinates

	double inner_lookup[8][8];
	for (x_t=0; x_t<8; x_t++)
		for (y_f=0; y_f<8; y_f++)
		{
			inner_lookup[x_t][y_f] = 0;
			for (y_t=0; y_t<8; y_t++)
				inner_lookup[x_t][y_f] += ( in[y_t*gap+x_t] - 128 ) * cos_lookup[y_t][y_f];

		}

	// freq(x_f,y_f) = ...
	double freq;
	for (y_f=0; y_f<8; y_f++)
		for (x_f=0; x_f<8; x_f++)
		{
			freq = 0;
			for(x_t=0; x_t<8; x_t++)
				freq += inner_lookup[x_t][y_f] * cos_lookup[x_t][x_f];

			if (x_f == 0)
				freq *= M_SQRT1_2;
			if (y_f == 0)
				freq *= M_SQRT1_2;
			freq /= 4;

			out[y_f*8+x_f] = freq;
		}
}

  • RISC-V