Assoc. Prof. Dr. Faruk BULUT

Research Title:

MIC: A Lossless Image Compression Format Based on the 11/9 Integer-Domain Surjective Mapping

with YCoCg-R Color Decorrelation, MED Spatial Prediction,

Zigzag Integer Coding, and Per-Channel Adaptive Human Entropy Coding

Authors:

Ibrahim Furkan Ince
Huseyin Kusetoğlu
Eren Yildirim
Faruk Bulut

Kodak Image set

Lena, pepper, babun, etc.

Babun, Cameraman, etc.

The JAVA codes for the proposed algorithmn can be downloaded from here for further developments:

import java.util.Arrays;

import java.util.PriorityQueue;

import java.awt.image.BufferedImage;

import javax.imageio.*;

import java.io.*;

import java.util.zip.Deflater;

double totalRawBytes = 0, totalPngBytes = 0, totalMicBytes = 0;

long totalMicEncTime = 0, totalMicDecTime = 0;

long totalPngEncTime = 0, totalPngDecTime = 0;

long totalPixels = 0;

int fileCount = 0, losslessCount = 0;

java.io.PrintStream levelLogStream = null;

int[] pixelGrid = new int[4096 * 4096], residuals = new int[4096 * 4096];

int[] symbolFreqs = new int[1048576], huffmanLens = new int[1048576];

long[] huffmanCodes = new long[1048576];

void setup() {

size(100, 100); pixelDensity(1); noLoop();

String[] dirs = {"mic", "png_level9"};

for (String d : dirs) { File f = new File(sketchPath(d)); if (!f.exists()) f.mkdir(); }

File dataFolder = new File(dataPath(""));

String[] allFiles = dataFolder.list();

if (allFiles == null) { println("Error: data folder not found!"); return; }

String logPath = sketchPath("results_level9.txt");

try {

levelLogStream = new java.io.PrintStream(

new java.io.FileOutputStream(logPath, false), true, "UTF-8");

} catch (Exception e) {

println("Failed to open log file: " + e.getMessage());

}

String h1 = "\n=== PNG COMPRESSION LEVEL 9 ===\n" + "=".repeat(215);

String h2 = String.format("%-15s | %-20s | %-14s | %-14s | %-18s | %-25s | %-20s",

"IDENTIFIER", "FILE SIZE (Bytes)", "BITRATE (BPP)", "COMP.RATIO(CR)", "SPACE SAVING(SS%)", "SPEED vs PNG (%)", "GAIN (vs PNG)");

String h3 = String.format("%-15s | %-9s %-10s | %-6s %-7s | %-6s %-7s | %-8s %-9s | %-12s %-12s | %-8s %-9s",

"File Name", "PNG", "MIC", "PNG", "MIC", "PNG", "MIC", "PNG", "MIC", "ENC", "DEC", "Factor", "Saving");

String h4 = "-".repeat(215);

logPrint(h1); println(h1);

logPrint(h2); println(h2);

logPrint(h3); println(h3);

logPrint(h4); println(h4);

for (String fileName : allFiles) {

if (fileName.toLowerCase().matches(".*\\.(png|bmp|jpg|jpeg|tga|gif|tif|tiff)$")) {

benchmarkImage(fileName);

fileCount++;

}

if (fileCount > 0) printExecutiveSummary();

if (levelLogStream != null) { levelLogStream.flush(); levelLogStream.close(); }

println(">>> Done. Log: " + logPath);

}

void logPrint(String s) {

if (levelLogStream != null) levelLogStream.println(s);

}

PImage loadImageSafe(String fullPath) {

try {

java.io.File file = new java.io.File(fullPath);

BufferedImage bi = ImageIO.read(file);

if (bi == null) return null;

BufferedImage normalizedImg = new BufferedImage(bi.getWidth(), bi.getHeight(), BufferedImage.TYPE_INT_ARGB);

java.awt.Graphics2D g2 = normalizedImg.createGraphics();

g2.drawImage(bi, 0, 0, null);

g2.dispose();

PImage out = createImage(normalizedImg.getWidth(), normalizedImg.getHeight(), ARGB);

normalizedImg.getRGB(0, 0, normalizedImg.getWidth(), normalizedImg.getHeight(), out.pixels, 0, normalizedImg.getWidth());

out.updatePixels();

return out;

} catch (Exception e) {

println("Yükleme hatası (" + fullPath + "): " + e.getMessage());

return null;

}

int detectChannels(String fullPath) {

try {

BufferedImage bi = ImageIO.read(new java.io.File(fullPath));

if (bi == null) return 3;

int numBands = bi.getRaster().getNumBands();

if (numBands == 1) return 1;

if (numBands == 2) return 4;

if (numBands == 4) return 4;

return 3;

} catch (Exception e) {

return 3;

}

boolean isGreyscale(PImage img) {

for (int p : img.pixels) {

int r = (p >> 16) & 255, g = (p >> 8) & 255, b = p & 255;

if (r != g || r != b) return false;

}

return true;

}

void benchmarkImage(String fileName) {

String srcPath = dataPath(fileName);

boolean srcIsPng = fileName.toLowerCase().endsWith(".png");

PImage img = loadImageSafe(srcPath);

if (img == null) { println("SKIP (unreadable): " + fileName); return; }

img.loadPixels();

int w = img.width, h = img.height;

long pCount = (long) w * h;

int srcChannels = detectChannels(srcPath);

String pPath = sketchPath("png_level9/" + (srcIsPng ? fileName : fileName + ".png"));

byte[] pngBytesForStats;

long tPngEncNano = 0, tPngDecNano = 0;

if (srcIsPng) {

pngBytesForStats = loadBytes(srcPath);

saveBytes(pPath, pngBytesForStats);

long _t = System.nanoTime();

getPngLevel9Bytes(img, srcChannels);

tPngEncNano = System.nanoTime() - _t;

_t = System.nanoTime();

try {

ImageIO.read(new ByteArrayInputStream(pngBytesForStats));

} catch (Exception e) {}

tPngDecNano = System.nanoTime() - _t;

} else {

long _t = System.nanoTime();

pngBytesForStats = getPngLevel9Bytes(img, srcChannels);

tPngEncNano = System.nanoTime() - _t;

saveBytes(pPath, pngBytesForStats);

_t = System.nanoTime();

try {

ImageIO.read(new ByteArrayInputStream(pngBytesForStats));

} catch (Exception e) {}

tPngDecNano = System.nanoTime() - _t;

}

long pSize = pngBytesForStats.length;

String mPath = sketchPath("mic/" + fileName + ".mic");

long tMicEncNano = System.nanoTime();

byte[] mBytes = micEncode(img, (srcChannels == 4));

tMicEncNano = System.nanoTime() - tMicEncNano;

saveBytes(mPath, mBytes);

long tMicDecNano = System.nanoTime();

PImage mDecImg = micDecode(mBytes);

tMicDecNano = System.nanoTime() - tMicDecNano;

long mSize = mBytes.length;

PImage referencePng = loadImageSafe(pPath);

totalPngEncTime += tPngEncNano;

totalPngDecTime += tPngDecNano;

totalMicEncTime += tMicEncNano;

totalMicDecTime += tMicDecNano;

totalMicBytes += mSize;

totalPngBytes += pSize;

totalRawBytes += (pCount * srcChannels);

double mse = calculateMSE(referencePng, mDecImg);

if (mse < 0.0001) losslessCount++;

String encSpeed = (tMicEncNano < tPngEncNano) ?

String.format("%%%4.1f Fast", (1.0 - (double) tMicEncNano / tPngEncNano) * 100) :

String.format("%%%4.1f Slow", ((double) tMicEncNano / tPngEncNano - 1.0) * 100);

String decSpeed = (tMicDecNano < tPngDecNano) ?

String.format("%%%4.1f Fast", (1.0 - (double) tMicDecNano / tPngDecNano) * 100) :

String.format("%%%4.1f Slow", ((double) tMicDecNano / tPngDecNano - 1.0) * 100);

String line = String.format("%-15s | %-9d %-10d | %-6.2f %-7.2f | %-6.2f %-7.2f | %%%-7.1f %%%-8.1f | %-12s %-12s | %-7.2fx %%%-8.1f %s",

fileName, pSize, mSize, (pSize * 8.0) / (pCount * srcChannels), (mSize * 8.0) / (pCount * srcChannels),

(double)(pCount * srcChannels) / pSize, (double)(pCount * srcChannels) / mSize,

(1.0 - pSize / (double)(pCount * srcChannels)) * 100, (1.0 - mSize / (double)(pCount * srcChannels)) * 100,

encSpeed, decSpeed, (double) pSize / mSize, (1.0 - (double) mSize / pSize) * 100, (mse < 0.0001 ? "OK" : "LOSS"));

println(line);

logPrint(line);

}

byte[] getPngLevel9Bytes(PImage img, int channels) {

try {

int w = img.width, h = img.height;

int colorType = (channels == 1) ? 0 : (channels == 4) ? 6 : 2;

ByteArrayOutputStream baos = new ByteArrayOutputStream();

baos.write(new byte[]{(byte)137, 80, 78, 71, 13, 10, 26, 10});

ByteArrayOutputStream ihdr = new ByteArrayOutputStream();

DataOutputStream dos = new DataOutputStream(ihdr);

dos.writeInt(w); dos.writeInt(h);

dos.writeByte(8); dos.writeByte(colorType); dos.writeByte(0); dos.writeByte(0); dos.writeByte(0);

writePngChunk(baos, "IHDR", ihdr.toByteArray());

ByteArrayOutputStream idatRaw = new ByteArrayOutputStream();

for (int y = 0; y < h; y++) {

idatRaw.write(0);

for (int x = 0; x < w; x++) {

int p = img.pixels[y * w + x];

if (channels == 1) idatRaw.write((p >> 16) & 255);

else {

idatRaw.write((p >> 16) & 255); idatRaw.write((p >> 8) & 255); idatRaw.write(p & 255);

if (channels == 4) idatRaw.write((p >> 24) & 255);

}

Deflater def = new Deflater(9);

def.setInput(idatRaw.toByteArray());

def.finish();

byte[] buf = new byte[1024];

ByteArrayOutputStream comp = new ByteArrayOutputStream();

while (!def.finished()) { int count = def.deflate(buf); comp.write(buf, 0, count); }

def.end();

writePngChunk(baos, "IDAT", comp.toByteArray());

writePngChunk(baos, "IEND", new byte[0]);

return baos.toByteArray();

} catch (Exception e) { return new byte[0]; }

}

void printExecutiveSummary() {

double avgBppP = (totalPngBytes * 8.0) / totalRawBytes;

double avgBppM = (totalMicBytes * 8.0) / totalRawBytes;

double globalCRP = totalRawBytes / totalPngBytes;

double globalCRM = totalRawBytes / totalMicBytes;

double globalSSP = (1.0 - totalPngBytes / totalRawBytes) * 100.0;

double globalSSM = (1.0 - totalMicBytes / totalRawBytes) * 100.0;

String[] lines = {

"-".repeat(215),

"\n" + "=".repeat(100),

"COMPREHENSIVE PERFORMANCE EVALUATION (MIC vs. PNG Level 9)",

"=".repeat(100),

"I. STORAGE EFFICIENCY VS. UNCOMPRESSED RAW DATA",

String.format(" %-35s | %-20s | %-20s", "METRIC", "PNG (Standard)", "MIC (Proposed)"),

" " + "-".repeat(85),

String.format(" %-35s | %-20.4f | %-20.4f", "Avg. Bitrate (BPP)", avgBppP, avgBppM),

String.format(" %-35s | %-20.3fx | %-20.3fx", "Compression Ratio (CR)", globalCRP, globalCRM),

String.format(" %-35s | %%%-19.2f | %%%-19.2f", "Space Saving (SS%)", globalSSP, globalSSM),

" " + "-".repeat(85),

"\nII. COMPARATIVE ADVANTAGE (MIC vs. PNG)",

String.format(" %-45s: %1.3fx SMALLER", "MIC COMPRESSION FACTOR OVER PNG", (double) totalPngBytes / totalMicBytes),

String.format(" %-45s: %%%.2f REDUCTION", "NET STORAGE SAVING OVER PNG", (1.0 - totalMicBytes / totalPngBytes) * 100.0),

"\nIII. COMPUTATIONAL PERFORMANCE",

(totalPngEncTime > 0) ?

String.format(" %-35s | %-20.2f | %-20.2f", "Avg. Encoding Time (ms)", (totalPngEncTime/1e6)/fileCount, (totalMicEncTime/1e6)/fileCount) :

String.format(" %-35s | %-20s | %-20.2f", "Avg. Encoding Time (ms)", "N/A (source=PNG)", (totalMicEncTime/1e6)/fileCount),

(totalPngDecTime > 0) ?

String.format(" %-35s | %-20.2f | %-20.2f", "Avg. Decoding Time (ms)", (totalPngDecTime/1e6)/fileCount, (totalMicDecTime/1e6)/fileCount) :

String.format(" %-35s | %-20s | %-20.2f", "Avg. Decoding Time (ms)", "N/A (source=PNG)", (totalMicDecTime/1e6)/fileCount),

(totalPngEncTime > 0) ?

String.format(" %-35s | %-17.2f MB/s | %-17.2f MB/s", "System Throughput",

(totalRawBytes / 1048576.0) / (totalPngEncTime / 1.0e9),

(totalRawBytes / 1048576.0) / (totalMicEncTime / 1.0e9)) :

String.format(" %-35s | %-20s | %-17.2f MB/s", "System Throughput",

"N/A (source=PNG)", (totalRawBytes / 1048576.0) / (totalMicEncTime / 1.0e9)),

"\nIV. DATA INTEGRITY",

String.format(" %-45s: %d/%d (100%% Lossless)", "Bit-for-Bit Validation", losslessCount, fileCount),

"=".repeat(100)

};

for (String l : lines) { println(l); logPrint(l); }

}

void writePngChunk(OutputStream os, String type, byte[] data) throws IOException {

DataOutputStream dos = new DataOutputStream(os);

dos.writeInt(data.length);

byte[] typeBytes = type.getBytes();

dos.write(typeBytes);

dos.write(data);

java.util.zip.CRC32 crc = new java.util.zip.CRC32();

crc.update(typeBytes);

crc.update(data);

dos.writeInt((int) crc.getValue());

}

byte[] micEncode(PImage img, boolean alpha) {

int w = img.width, h = img.height;

boolean grey = isGreyscale(img);

FastWriter fw = new FastWriter(w * h * 4 + 4096);

fw.writeInt(w, 16);

fw.writeInt(h, 16);

fw.writeBit(alpha ? 1 : 0);

fw.writeBit(grey ? 1 : 0);

if (grey) {

encodeChannel_Grey(fw, img, w, h);

if (alpha) encodeChannel_Alpha(fw, img, w, h);

} else {

for (int k = 0; k < 3; k++) {

encodeChannel_RGB(fw, img, w, h, k, alpha);

}

if (alpha) encodeChannel_Alpha(fw, img, w, h);

}

return fw.terminate();

}

void encodeChannel_Grey(FastWriter fw, PImage img, int w, int h) {

Arrays.fill(symbolFreqs, 0);

for (int y = 0, idx = 0; y < h; y++) {

for (int x = 0; x < w; x++, idx++) {

int p = img.pixels[idx];

int val = (p >> 16) & 255;

pixelGrid[idx] = val;

int a = (x > 0) ? pixelGrid[idx-1] : 0;

int b = (y > 0) ? pixelGrid[idx-w] : 0;

int c = (x > 0 && y > 0) ? pixelGrid[idx-w-1] : 0;

int pred = (c >= Math.max(a, b)) ? Math.min(a, b) : (c <= Math.min(a, b)) ? Math.max(a, b) : a + b - c;

int d = val - pred;

d = (d >= 0 ? (d << 1) : ((-d << 1) - 1));

int q = d / 11, r_ = d % 11; if (r_ < 0) r_ += 11;

d = (r_ == 3 || r_ == 8) ? -(d + 1) : q * 9 + ((r_ > 8) ? r_ - 2 : (r_ > 3 ? r_ - 1 : r_));

residuals[idx] = d;

int sIdx = d + 524288;

if (sIdx >= 0 && sIdx < 1048576) symbolFreqs[sIdx]++;

}

buildH(symbolFreqs);

int dc = 0; for (int f : symbolFreqs) if (f > 0) dc++;

fw.writeInt(dc, 12);

for (int i = 0; i < 1048576; i++) if (symbolFreqs[i] > 0) {

int v = i - 524288; fw.writeBit(v < 0 ? 1 : 0); fw.writeInt(Math.abs(v), 18);

fw.writeInt(huffmanLens[i], 6); fw.writeLong(huffmanCodes[i], huffmanLens[i]);

}

for (int i = 0; i < w * h; i++) {

int dI = residuals[i] + 524288;

fw.writeLong(huffmanCodes[dI], huffmanLens[dI]);

}

void encodeChannel_Alpha(FastWriter fw, PImage img, int w, int h) {

Arrays.fill(symbolFreqs, 0);

for (int y = 0, idx = 0; y < h; y++) {

for (int x = 0; x < w; x++, idx++) {

int val = (img.pixels[idx] >> 24) & 255;

pixelGrid[idx] = val;

int a = (x > 0) ? pixelGrid[idx-1] : 0;

int b = (y > 0) ? pixelGrid[idx-w] : 0;

int c = (x > 0 && y > 0) ? pixelGrid[idx-w-1] : 0;

int pred = (c >= Math.max(a, b)) ? Math.min(a, b) : (c <= Math.min(a, b)) ? Math.max(a, b) : a + b - c;

int d = val - pred;

d = (d >= 0 ? (d << 1) : ((-d << 1) - 1));

int q = d / 11, r_ = d % 11; if (r_ < 0) r_ += 11;

d = (r_ == 3 || r_ == 8) ? -(d + 1) : q * 9 + ((r_ > 8) ? r_ - 2 : (r_ > 3 ? r_ - 1 : r_));

residuals[idx] = d;

int sIdx = d + 524288;

if (sIdx >= 0 && sIdx < 1048576) symbolFreqs[sIdx]++;

}

buildH(symbolFreqs);

int dc = 0; for (int f : symbolFreqs) if (f > 0) dc++;

fw.writeInt(dc, 12);

for (int i = 0; i < 1048576; i++) if (symbolFreqs[i] > 0) {

int v = i - 524288; fw.writeBit(v < 0 ? 1 : 0); fw.writeInt(Math.abs(v), 18);

fw.writeInt(huffmanLens[i], 6); fw.writeLong(huffmanCodes[i], huffmanLens[i]);

}

for (int i = 0; i < w * h; i++) {

int dI = residuals[i] + 524288;

fw.writeLong(huffmanCodes[dI], huffmanLens[dI]);

}

void encodeChannel_RGB(FastWriter fw, PImage img, int w, int h, int k, boolean alpha) {

Arrays.fill(symbolFreqs, 0);

for (int y = 0, idx = 0; y < h; y++) {

for (int x = 0; x < w; x++, idx++) {

int p = img.pixels[idx], val;

int r=(p>>16)&255, g=(p>>8)&255, b=p&255;

int co=r-b, tmp=b+(co>>1), cg=g-tmp;

val = (k==0) ? tmp+(cg>>1) : (k==1 ? co : cg);

pixelGrid[idx] = val;

int a=(x>0)?pixelGrid[idx-1]:0, b_v=(y>0)?pixelGrid[idx-w]:0, c=(x>0&&y>0)?pixelGrid[idx-w-1]:0;

int pred = (c>=Math.max(a,b_v))?Math.min(a,b_v):(c<=Math.min(a,b_v)?Math.max(a,b_v):a+b_v-c);

int d = val - pred;

d = (d>=0?(d<<1):((-d<<1)-1));

int q=d/11, r_=d%11; if(r_<0)r_+=11;

d=(r_==3||r_==8)?-(d+1):q*9+((r_>8)?r_-2:(r_>3?r_-1:r_));

residuals[idx] = d;

int sIdx = d + 524288;

if (sIdx >= 0 && sIdx < 1048576) symbolFreqs[sIdx]++;

}

buildH(symbolFreqs);

int dc=0; for(int f:symbolFreqs) if(f>0) dc++;

fw.writeInt(dc, 12);

for (int i=0; i<1048576; i++) if (symbolFreqs[i]>0) {

int v=i-524288; fw.writeBit(v<0?1:0); fw.writeInt(Math.abs(v), 18);

fw.writeInt(huffmanLens[i],6); fw.writeLong(huffmanCodes[i],huffmanLens[i]);

}

for (int i=0; i<w*h; i++) {

int dI = residuals[i] + 524288;

fw.writeLong(huffmanCodes[dI], huffmanLens[dI]);

}

PImage micDecode(byte[] data) {

BitReader br = new BitReader(data);

int w = br.readInt(16), h = br.readInt(16);

boolean alpha = br.readBit() == 1;

boolean grey = br.readBit() == 1;

PImage out = createImage(w, h, ARGB);

out.loadPixels();

if (grey) {

int[] luma = decodeChannel_Grey(br, w, h);

int[] aData = alpha ? decodeChannel_Grey(br, w, h) : null;

for (int i = 0; i < w * h; i++) {

int lum = constrain(luma[i], 0, 255), a = alpha ? constrain(aData[i], 0, 255) : 255;

out.pixels[i] = (a << 24) | (lum << 16) | (lum << 8) | lum;

}

} else {

int[][] gF = new int[3][w * h];

for (int k = 0; k < 3; k++) decodeChannel_RGB_Decode(br, w, h, gF[k]);

int[] aData = alpha ? decodeChannel_Grey(br, w, h) : null;

for (int i = 0; i < w * h; i++) {

int lum=gF[0][i], co=gF[1][i], cg=gF[2][i], a = alpha ? constrain(aData[i], 0, 255) : 255;

int t=lum-(cg>>1), g=cg+t, b=t-(co>>1), r=co+b;

out.pixels[i] = (a<<24)|(constrain(r,0,255)<<16)|(constrain(g,0,255)<<8)|constrain(b,0,255);

}

out.updatePixels(); return out;

}

int[] decodeChannel_Grey(BitReader br, int w, int h) {

int ds = br.readInt(12);

HNode root = new HNode(-1, 0);

for (int i = 0; i < ds; i++) {

int s = br.readBit(), v = br.readInt(18), fv = (s == 1 ? -v : v), ln = br.readInt(6);

HNode curr = root;

for (int j = 0; j < ln; j++) {

if (br.readBit() == 0) { if (curr.l == null) curr.l = new HNode(-1, 0); curr = curr.l; }

else { if (curr.r == null) curr.r = new HNode(-1, 0); curr = curr.r; }

}

curr.id = fv;

}

int[] result = new int[w * h];

for (int i = 0; i < w * h; i++) {

HNode curr = root;

while (curr.id == -1) curr = (br.readBit() == 0) ? curr.l : curr.r;

int x = i % w, y = i / w, a = (x>0)?result[i-1]:0, b = (y>0)?result[i-w]:0, c = (x>0&&y>0)?result[i-w-1]:0;

int pred = (c>=Math.max(a,b))?Math.min(a,b):(c<=Math.min(a,b)?Math.max(a,b):a+b-c);

int iv = (curr.id < 0) ? -(curr.id+1) : (curr.id/9*11+((curr.id%9>=7)?curr.id%9+2:(curr.id%9>=3?curr.id%9+1:curr.id%9)));

result[i] = (((iv & 1) == 0) ? (iv >> 1) : -((iv+1) >> 1)) + pred;

}

return result;

}

void decodeChannel_RGB_Decode(BitReader br, int w, int h, int[] out) {

int ds = br.readInt(12);

HNode root = new HNode(-1, 0);

for (int i = 0; i < ds; i++) {

int s = br.readBit(), v = br.readInt(18), fv = (s == 1 ? -v : v), ln = br.readInt(6);

HNode curr = root;

for (int j = 0; j < ln; j++) {

if (br.readBit() == 0) { if (curr.l == null) curr.l = new HNode(-1, 0); curr = curr.l; }

else { if (curr.r == null) curr.r = new HNode(-1, 0); curr = curr.r; }

}

curr.id = fv;

}

for (int i = 0; i < w * h; i++) {

HNode curr = root;

while (curr.id == -1) curr = (br.readBit() == 0) ? curr.l : curr.r;

int x = i % w, y = i / w, a = (x>0)?out[i-1]:0, b = (y>0)?out[i-w]:0, c = (x>0&&y>0)?out[i-w-1]:0;

int pred = (c>=Math.max(a,b))?Math.min(a,b):(c<=Math.min(a,b)?Math.max(a,b):a+b-c);

int iv = (curr.id < 0) ? -(curr.id+1) : (curr.id/9*11+((curr.id%9>=7)?curr.id%9+2:(curr.id%9>=3?curr.id%9+1:curr.id%9)));

out[i] = (((iv & 1) == 0) ? (iv >> 1) : -((iv+1) >> 1)) + pred;

}

void buildH(int[] f) {

PriorityQueue<HNode> pq = new PriorityQueue<HNode>();

for (int i=0; i<1048576; i++) if (f[i]>0) pq.add(new HNode(i,f[i]));

if (pq.isEmpty()) return;

if (pq.size()==1) { int id=pq.poll().id; huffmanLens[id]=1; huffmanCodes[id]=0; return; }

while (pq.size()>1) {

HNode l=pq.poll(), r=pq.poll();

HNode p=new HNode(-1, l.freq+r.freq); p.l=l; p.r=r; pq.add(p);

}

Arrays.fill(huffmanLens, 0); walk(pq.poll(), 0, 0);

}

void walk(HNode n, long c, int l) {

if (n.id!=-1) { huffmanLens[n.id]=l; huffmanCodes[n.id]=c; }

else { walk(n.l, c<<1, l+1); walk(n.r, (c<<1)|1, l+1); }

}

class FastWriter {

byte[] b; int p=0; long buf=0; int c=0;

FastWriter(int s) { b=new byte[s]; }

void writeBit(int bit) { buf=(buf<<1)|(bit&1); c++; if(c==8){b[p++]=(byte)buf; c=0; buf=0;} }

void writeInt(int v, int bits) { for(int i=bits-1;i>=0;i--) writeBit(v>>i); }

void writeLong(long v, int bits) { for(int i=bits-1;i>=0;i--) writeBit((int)(v>>i)); }

byte[] terminate() { if(c>0) b[p++]=(byte)(buf<<(8-c)); return Arrays.copyOf(b,p); }

}

class BitReader {

byte[] d; int ptr=0; BitReader(byte[] data) { d=data; }

int readBit() { if((ptr>>3)>=d.length) return 0; int v=(d[ptr>>3]>>(7-(ptr&7)))&1; ptr++; return v; }

int readInt(int b) { int v=0; for(int i=0;i<b;i++) v=(v<<1)|readBit(); return v; }

}

class HNode implements Comparable<HNode> {

int id, freq; HNode l, r; HNode(int i, int f) { id=i; freq=f; }

public int compareTo(HNode o) { return freq-o.freq; }

}

double calculateMSE(PImage i1, PImage i2) {

double m=0;

for (int i=0; i<i1.pixels.length; i++) {

int p1=i1.pixels[i], p2=i2.pixels[i];

int r=((p1>>16)&255)-((p2>>16)&255), g=((p1>>8)&255)-((p2>>8)&255), b=(p1&255)-(p2&255), a=((p1>>24)&255)-((p2>>24)&255);

m+=(r*r+g*g+b*b+a*a);

}

return m/(i1.pixels.length * 4.0);

}