1. Hämta bilden från extern källa.
Detta är vad jag har gjort tidigare.
2. Komprimera bilden.
Bilden behöver komprimeras ca 10 ggr!
För att lära mig lite mer om praktisk implementation av bildkomprimering så skrev jag en egen komprimeringsalgoritm som bygger på en typ II/III 2D DCT (2-Dimensional Discrete Cosine Transform). För att den ska gå att köra på en långsam mikrodator så implementerade jag hela inverstransformen i fixed-point. Det som krävs av processorn utöver plats för den komprimerade bilden är ca 1kB RAM.
Komprimeringen går till så här:
1. Dela upp bilden i 8x8-pixel block.
2. Konvertera RGB-delblocken till YUV-delblock. Eftersom ögat är mer känsligt för själva formen än för färgerna så kan man lägga betydligt mer bandbredd på luminans-komponenten (Y) än på Chrominans-komponenterna (U, V).
3. Gör en 2D DCT på varje block på bilden. Sedan kan de höga frekvenserna kastas bort. Det är detta som sparar en massa data. Vi ser inte höra frekvenser i bilder lika bra som låga frekvenser och ofta är de höga frekvenserna endast brus.
För att återställa bilden görs samma sak baklänges.
De transformerade koefficienterna skalas sedan ner för att få plats i 8-bitars variabler. För att det ska gå snabbt så är alla cosinusdelar i transförmen förberäknade och sparade i tabeller.
Här är java-programmet jag har gjort för att testa metoden (jobbar fortfarande på optimeringar, detta är bara vad jag skrev ihop igår kväll):
Kod: Markera allt
/*
* Fixed point cosine coefficients for inverse-transform.
*/
public static int cos_t[][] = {
{ 127, 125, 117, 106, 90, 71, 49, 25 },
{ 127, 106, 49, -25, -90, -125, -117, -71 },
{ 127, 71, -49, -125, -90, 25, 117, 105 },
{ 127, 25, -117, -71, 90, 106, -49, -125 },
{ 127, -25, -117, 71, 90, -106, -49, 125 },
{ 127, -71, -49, 125, -90, -25, 117, -106 },
{ 127, -106, 49, 25, -90, 125, -117, 71 },
{ 127, -125, 117, -106, 90, -71, 49, -25 },
};
/*
* Floating point cosine coefficients for transform
*/
public static double cos_t_d[][] = {
{ 1, 0.980785280403230, 0.923879532511287, 0.831469612302545, 0.707106781186548, 0.555570233019602, 0.382683432365090, 0.195090322016128 },
{ 1, 0.831469612302545, 0.382683432365090, -0.195090322016128, -0.707106781186547, -0.980785280403230, -0.923879532511287, -0.555570233019602 },
{ 1, 0.555570233019602, -0.382683432365090, -0.980785280403230, -0.707106781186547, 0.195090322016128, 0.923879532511287, 0.831469612302546 },
{ 1, 0.195090322016128, -0.923879532511287, -0.555570233019602, 0.707106781186548, 0.831469612302546, -0.382683432365090, -0.980785280403231 },
{ 1, -0.195090322016128, -0.923879532511287, 0.555570233019602, 0.707106781186548, -0.831469612302545, -0.382683432365091, 0.980785280403230 },
{ 1, -0.555570233019602, -0.382683432365090, 0.980785280403230, -0.707106781186547, -0.195090322016128, 0.923879532511287, -0.831469612302545 },
{ 1, -0.831469612302545, 0.382683432365090, 0.195090322016128, -0.707106781186547, 0.980785280403231, -0.923879532511286, 0.555570233019602 },
{ 1, -0.980785280403230, 0.923879532511287, -0.831469612302545, 0.707106781186548, -0.555570233019602, 0.382683432365090, -0.195090322016129 },
};
/*
* Fixed point scaling table for inverse transform
*/
public static int sc_t[] = { 64516, 91239, 129032 };
// public static int sc_t[] = { 65536, 65536, 131072 };
/*
* Floating point scaling table for transform
*/
public static double sc_t_d[] = { 4, 5.656854249492381, 8 };
/*
* Scaling of transform coefficients. 16 makes them fit into 8 bits.
*/
public static int div = 16;
/**
* Get a 2D DCT (Discrete cosine transform) from an 8x8 block
* in the spatial domain. This method uses floating-point
* operations.
* @param block
* The 8x8 block to transform.
* @param len
* The number of coefficients to store in each dimension.
* @return
* A vector with the block in the frequency domain. The length
* will be len*len.
*/
public static void getDCTBlock(int block[], int len, int out[]) {
double aa[] = new double[len * len];
for (int i = 0; i < aa.length; i++) {
aa[i] = 0;
}
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
for (int k = 0; k < 8; k++) {
for (int l = 0; l < 8; l++) {
aa[i * len + j] += (double)block[k * 8 + l] * cos_t_d[k][i] * cos_t_d[l][j];
}
}
int sc_ind = 0;
if (i == 0) {
sc_ind++;
}
if (j == 0) {
sc_ind++;
}
aa[i * len + j] /= (sc_t_d[sc_ind] * (double)div);
}
}
for (int i = 0; i < aa.length; i++) {
out[i] = (int)aa[i];
}
}
/**
* Get a IDCT (Inverse Discrete Cosine Transform) 8x8 block from
* a block in the frequency domain. This method uses only
* fixed point operations.
* @param block_in
* The block in the frequency domain. Length should be a power of 2.
* @return
* A 8x8 block in the spatial domain.
*/
public static void getIDCTBlock(int block_in[], int block_out[]) {
int len = (int) Math.sqrt(block_in.length);
for (int i = 0; i < block_out.length; i++) {
block_out[i] = 0;
}
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
for (int k = 0; k < len; k++) {
for (int l = 0; l < len; l++) {
int sc_ind = 0;
if (k == 0) {
sc_ind++;
}
if (l == 0) {
sc_ind++;
}
block_out[i * 8 + j] += (block_in[k * len + l] * cos_t[i][k] * cos_t[j][l] * div) / sc_t[sc_ind];
}
}
}
}
}
/**
* Compress an image with the DCT (Discrete Cosine Transform).
* @param img
* The image to compress.
* @param y
* The number of Y (luma) coefficients to store in each dimension.
* @param u
* The number of U (Chrominance) coefficients to store in each dimension.
* Can usually be a lower number than the luma coefficients.
* @param v
* The number of V (Chrominance) coefficients to store in each dimension.
* Can usually be a lower number than the luma coefficients.
* @return
* A vector with the compressed image.
*/
public static int[] getDCTImage(BufferedImage img, int y, int u, int v) {
int w = img.getWidth();
int h = img.getHeight();
int[] aa = new int[y * y * ((w / 8) * (h / 8)) + u * u
* ((w / 8) * (h / 8)) + v * v * ((w / 8) * (h / 8))];
int block_y[] = new int[8 * 8];
int block_u[] = new int[8 * 8];
int block_v[] = new int[8 * 8];
int y_c[] = new int[y*y];
int u_c[] = new int[u*u];
int v_c[] = new int[v*v];
int rgb, r, g, b;
int pos = 0;
for (int i = 0; i < w; i += 8) {
for (int j = 0; j < h; j += 8) {
for (int k = 0; k < 8; k++) {
for (int l = 0; l < 8; l++) {
rgb = img.getRGB(i + k, j + l);
r = (rgb & 0xFF0000) >>> 16;
g = (rgb & 0x00FF00) >>> 8;
b = rgb & 0x0000FF;
block_y[k * 8 + l] = (299 * r + 587 * g + 114 * b) / 1000;
block_u[k * 8 + l] = (-147 * r - 289 * g + 436 * b) / 1000;
block_v[k * 8 + l] = (615 * r - 515 * g - 100 * b) / 1000;
// block_y[k * 8 + l] = r;
// block_u[k * 8 + l] = g;
// block_v[k * 8 + l] = b;
}
}
getDCTBlock(block_y, y, y_c);
getDCTBlock(block_u, u, u_c);
getDCTBlock(block_v, v, v_c);
for (int k = 0; k < y_c.length; k++) {
aa[pos + k] = y_c[k];
}
pos += y_c.length;
for (int k = 0; k < u_c.length; k++) {
aa[pos + k] = u_c[k];
}
pos += u_c.length;
for (int k = 0; k < v_c.length; k++) {
aa[pos + k] = v_c[k];
}
pos += v_c.length;
}
}
return aa;
}
/**
* De-compress an image compressed with the DCT (Discrete Cosine Transform).
* @param dct
* The compressed image.
* @param w
* The width of the image.
* @param h
* The height of the image.
* @param y
* The number of Y (luma) coefficients stored in each dimension.
* @param u
* The number of U (Chrominance) coefficients stored in each dimension.
* @param v
* The number of V (Chrominance) coefficients stored in each dimension.
* @return
*/
public static BufferedImage getIDCTImage(int dct[], int w, int h, int y,
int u, int v) {
BufferedImage img = new BufferedImage(w, h, BufferedImage.TYPE_INT_RGB);
int y_c[] = new int[y * y];
int u_c[] = new int[u * u];
int v_c[] = new int[v * v];
int block_y[] = new int[8*8];
int block_u[] = new int[8*8];
int block_v[] = new int[8*8];
int r, g, b;
int pos = 0;
for (int i = 0; i < w; i += 8) {
for (int j = 0; j < h; j += 8) {
for (int k = 0; k < y_c.length; k++) {
y_c[k] = dct[pos + k];
}
pos += y_c.length;
for (int k = 0; k < u_c.length; k++) {
u_c[k] = dct[pos + k];
}
pos += u_c.length;
for (int k = 0; k < v_c.length; k++) {
v_c[k] = dct[pos + k];
}
pos += v_c.length;
getIDCTBlock(y_c, block_y);
getIDCTBlock(u_c, block_u);
getIDCTBlock(v_c, block_v);
for (int k = 0; k < 8; k++) {
for (int l = 0; l < 8; l++) {
r = (1000*block_y[8*k+l] + 1140 * block_v[8*k+l]) / 1000;
g = (1000*block_y[8*k+l] - 395*block_u[8*k+l] - 581*block_v[8*k+l]) / 1000;
b = (1000*block_y[8*k+l] + 2032 * block_u[8*k+l]) / 1000;
// r = block_y[8*k+l];
// g = block_u[8*k+l];
// b = block_v[8*k+l];
if (r < 0) {
r = 0;
}
if (r > 255) {
r = 255;
}
if (g < 0) {
g = 0;
}
if (g > 255) {
g = 255;
}
if (b < 0) {
b = 0;
}
if (b > 255) {
b = 255;
}
img.setRGB(i + k, j + l, (r << 16) + (g << 8) + b);
}
}
}
}
return img;
}
Bilden ovan (Lena, http://www.ecogito.net/articles/lena.html) är komprimerad så att endast 9% informationen av originalbilden används. Alltså över 10 gånger komprimering! Man kan se block-artefakten och zoomar man in ser man att färgera har mycket lägre upplösning än luminansen.
Nästa steg blir att implementera inverstransformen på en mikrodator. Inga konstiga funktioner används i återskapningen och allt är fixed-point, så det borde inte vara något problem.
