Library/src/main/java/org/example/FractalCompressor.java - master - Dixix404/Image_Compression

Library/src/main/java/org/example/FractalCompressor.java
342 строки11 KB
Dixix404
Algorithm Fractal
16 дек 2025, 00:56
16 дек 2025, 00:562b757a5
package org.example;

import java.io.*;
import java.util.Arrays;

/**
 * Быстрый фрактальный компрессор с 8 трансформациями.
 */
public class FractalCompressor implements Compressor {

    private static final byte[] MAGIC = {'F','R','C','1'};
    private static final int RANGE = 4;
    private static final int DOMAIN = 8;
    private static final int STEP = 8;
    private static final int ITERS = 10;

    @Override
    public String getName() {
        return "fractal";
    }

    @Override
    public void compress(String inputBmpPath, String outputPath) throws IOException {
        byte[] bmp = readFile(inputBmpPath);
        try (FileOutputStream fos = new FileOutputStream(outputPath)) {
            compressCore(bmp, fos);
        }
    }

    @Override
    public void decompress(String inputPath, String outputBmpPath) throws IOException {
        byte[] compressed = readFile(inputPath);
        try (FileOutputStream fos = new FileOutputStream(outputBmpPath)) {
            decompressCore(compressed, fos);
        }
    }

    private void compressCore(byte[] bmp, OutputStream out) throws IOException {
        int offset = readIntLE(bmp, 10);
        int w = readIntLE(bmp, 18);
        int h = Math.abs(readIntLE(bmp, 22));
        boolean bottomUp = readIntLE(bmp, 22) > 0;

        if (w % RANGE != 0 || h % RANGE != 0) {
            throw new IOException("Размеры должны делиться на " + RANGE);
        }

        int stride = ((w * 3 + 3) / 4) * 4;
        byte[] img = readTopDown(bmp, offset, w, h, stride, bottomUp);

        out.write(Arrays.copyOfRange(bmp, 0, offset));
        out.write(MAGIC);
        out.write(RANGE);
        out.write(ITERS);
        writeUShort(out, STEP);
        writeInt(out, w);
        writeInt(out, h);

        int bx = w / RANGE;
        int by = h / RANGE;
        writeInt(out, bx * by);

        int n = RANGE * RANGE;
        int[] rB = new int[n], rG = new int[n], rR = new int[n];
        int[] dB = new int[n], dG = new int[n], dR = new int[n];
        int[] tB = new int[n], tG = new int[n], tR = new int[n];

        for (int y = 0; y < by; y++) {
            for (int x = 0; x < bx; x++) {
                fillRange(img, w, x * RANGE, y * RANGE, rB, rG, rR);
                Best best = findBest(img, w, h, rB, rG, rR, dB, dG, dR, tB, tG, tR);

                writeUShort(out, best.dx);
                writeUShort(out, best.dy);
                out.write(best.tr);
                writeShort(out, best.sB);
                writeUShort(out, best.oB);
                writeShort(out, best.sG);
                writeUShort(out, best.oG);
                writeShort(out, best.sR);
                writeUShort(out, best.oR);
            }
        }
    }

    private void decompressCore(byte[] data, OutputStream out) throws IOException {
        int offset = readIntLE(data, 10);
        int w = readIntLE(data, 18);
        int h = Math.abs(readIntLE(data, 22));
        boolean bottomUp = readIntLE(data, 22) > 0;

        out.write(Arrays.copyOfRange(data, 0, offset));

        int p = offset + 4; // skip MAGIC
        int range = data[p++] & 0xFF;
        int iters = data[p++] & 0xFF;
        p += 2; // skip STEP
        int width = readIntLE(data, p); p += 4;
        int height = readIntLE(data, p); p += 4;
        int count = readIntLE(data, p); p += 4;

        Map[] maps = new Map[count];
        for (int i = 0; i < count; i++) {
            maps[i] = new Map(
                    readUShort(data, p), readUShort(data, p+2), data[p+4] & 0xFF,
                    readShort(data, p+5), readUShort(data, p+7),
                    readShort(data, p+9), readUShort(data, p+11),
                    readShort(data, p+13), readUShort(data, p+15)
            );
            p += 17;
        }

        byte[] cur = new byte[w * h * 3];
        Arrays.fill(cur, (byte) 128);
        byte[] nxt = new byte[cur.length];

        int bx = w / range;
        int n = range * range;
        int[] dB = new int[n], dG = new int[n], dR = new int[n];
        int[] tB = new int[n], tG = new int[n], tR = new int[n];

        for (int iter = 0; iter < iters; iter++) {
            for (int i = 0; i < count; i++) {
                int rx = (i % bx) * range;
                int ry = (i / bx) * range;
                applyMap(cur, nxt, w, range, maps[i], rx, ry, dB, dG, dR, tB, tG, tR);
            }
            byte[] tmp = cur; cur = nxt; nxt = tmp;
        }

        int stride = ((w * 3 + 3) / 4) * 4;
        out.write(writePixels(cur, w, h, stride, bottomUp));
    }

    private Best findBest(byte[] img, int w, int h, int[] rB, int[] rG, int[] rR,
                          int[] dB, int[] dG, int[] dR, int[] tB, int[] tG, int[] tR) {
        Best best = new Best();
        best.err = Double.MAX_VALUE;

        for (int dy = 0; dy <= h - DOMAIN; dy += STEP) {
            for (int dx = 0; dx <= w - DOMAIN; dx += STEP) {
                downsample(img, w, dx, dy, dB, dG, dR);

                for (int tr = 0; tr < 8; tr++) {
                    transform(dB, tB, tr);
                    transform(dG, tG, tr);
                    transform(dR, tR, tr);

                    Aff aB = fit(tB, rB);
                    Aff aG = fit(tG, rG);
                    Aff aR = fit(tR, rR);

                    double err = aB.err + aG.err + aR.err;
                    if (err < best.err) {
                        best.err = err;
                        best.dx = dx; best.dy = dy; best.tr = tr;
                        best.sB = aB.s; best.oB = aB.o;
                        best.sG = aG.s; best.oG = aG.o;
                        best.sR = aR.s; best.oR = aR.o;
                        if (err == 0) return best;
                    }
                }
            }
        }
        return best;
    }

    private void applyMap(byte[] cur, byte[] nxt, int w, int r, Map m, int rx, int ry,
                          int[] dB, int[] dG, int[] dR, int[] tB, int[] tG, int[] tR) {
        downsample(cur, w, m.dx, m.dy, dB, dG, dR);
        transform(dB, tB, m.tr);
        transform(dG, tG, m.tr);
        transform(dR, tR, m.tr);

        for (int y = 0; y < r; y++) {
            for (int x = 0; x < r; x++) {
                int i = y * r + x;
                int b = clamp(((m.sB * tB[i]) + m.oB) >> 8);
                int g = clamp(((m.sG * tG[i]) + m.oG) >> 8);
                int rr = clamp(((m.sR * tR[i]) + m.oR) >> 8);

                int idx = ((ry + y) * w + (rx + x)) * 3;
                nxt[idx] = (byte) b;
                nxt[idx+1] = (byte) g;
                nxt[idx+2] = (byte) rr;
            }
        }
    }

    private Aff fit(int[] d, int[] r) {
        int n = d.length;
        double md = 0, mr = 0;
        for (int i = 0; i < n; i++) { md += d[i]; mr += r[i]; }
        md /= n; mr /= n;

        double vd = 0, cv = 0;
        for (int i = 0; i < n; i++) {
            double xd = d[i] - md, yr = r[i] - mr;
            vd += xd * xd;
            cv += xd * yr;
        }

        double s = (vd < 1e-9) ? 0 : Math.max(-1, Math.min(1, cv / vd));
        double o = Math.max(0, Math.min(255, mr - s * md));

        double err = 0;
        for (int i = 0; i < n; i++) {
            double e = r[i] - (s * d[i] + o);
            err += e * e;
        }

        return new Aff((short) Math.round(s * 256), (int) Math.round(o * 256), err);
    }

    private void fillRange(byte[] img, int w, int rx, int ry, int[] rB, int[] rG, int[] rR) {
        int k = 0;
        for (int y = 0; y < RANGE; y++) {
            for (int x = 0; x < RANGE; x++) {
                int idx = ((ry+y)*w + (rx+x))*3;
                rB[k] = img[idx] & 0xFF;
                rG[k] = img[idx+1] & 0xFF;
                rR[k] = img[idx+2] & 0xFF;
                k++;
            }
        }
    }

    private void downsample(byte[] img, int w, int dx, int dy, int[] dB, int[] dG, int[] dR) {
        int k = 0;
        for (int y = 0; y < RANGE; y++) {
            for (int x = 0; x < RANGE; x++) {
                int sx = dx + x*2, sy = dy + y*2;
                int sB = 0, sG = 0, sR = 0;
                for (int yy = 0; yy < 2; yy++) {
                    for (int xx = 0; xx < 2; xx++) {
                        int i = ((sy+yy)*w + (sx+xx))*3;
                        sB += img[i] & 0xFF;
                        sG += img[i+1] & 0xFF;
                        sR += img[i+2] & 0xFF;
                    }
                }
                dB[k] = sB >> 2;
                dG[k] = sG >> 2;
                dR[k] = sR >> 2;
                k++;
            }
        }
    }

    private void transform(int[] src, int[] dst, int t) {
        for (int y = 0; y < RANGE; y++) {
            for (int x = 0; x < RANGE; x++) {
                int sx, sy;
                switch (t) {
                    case 1: sx=y; sy=RANGE-1-x; break;
                    case 2: sx=RANGE-1-x; sy=RANGE-1-y; break;
                    case 3: sx=RANGE-1-y; sy=x; break;
                    case 4: sx=x; sy=RANGE-1-y; break;
                    case 5: sx=RANGE-1-x; sy=y; break;
                    case 6: sx=y; sy=x; break;
                    case 7: sx=RANGE-1-y; sy=RANGE-1-x; break;
                    default: sx=x; sy=y;
                }
                dst[y*RANGE+x] = src[sy*RANGE+sx];
            }
        }
    }

    private byte[] readTopDown(byte[] bmp, int off, int w, int h, int stride, boolean bu) {
        byte[] out = new byte[w*h*3];
        for (int y = 0; y < h; y++) {
            int sr = bu ? (h-1-y) : y;
            System.arraycopy(bmp, off+sr*stride, out, y*w*3, w*3);
        }
        return out;
    }

    private byte[] writePixels(byte[] td, int w, int h, int stride, boolean bu) {
        byte[] pix = new byte[stride*h];
        for (int y = 0; y < h; y++) {
            int dr = bu ? (h-1-y) : y;
            System.arraycopy(td, y*w*3, pix, dr*stride, w*3);
        }
        return pix;
    }

    private byte[] readFile(String path) throws IOException {
        try (FileInputStream fis = new FileInputStream(path)) {
            return fis.readAllBytes();
        }
    }

    private int clamp(int v) { return Math.max(0, Math.min(255, v)); }

    private int readIntLE(byte[] a, int o) {
        return (a[o]&0xFF) | ((a[o+1]&0xFF)<<8) | ((a[o+2]&0xFF)<<16) | ((a[o+3]&0xFF)<<24);
    }

    private short readShort(byte[] a, int o) {
        return (short)((a[o]&0xFF) | ((a[o+1]&0xFF)<<8));
    }

    private int readUShort(byte[] a, int o) {
        return (a[o]&0xFF) | ((a[o+1]&0xFF)<<8);
    }

    private void writeInt(OutputStream o, int v) throws IOException {
        o.write(v); o.write(v>>8); o.write(v>>16); o.write(v>>24);
    }

    private void writeShort(OutputStream o, short v) throws IOException {
        o.write(v); o.write(v>>8);
    }

    private void writeUShort(OutputStream o, int v) throws IOException {
        o.write(v); o.write(v>>8);
    }

    private static class Best {
        int dx, dy, tr;
        short sB, sG, sR;
        int oB, oG, oR;
        double err;
    }

    private static class Map {
        final int dx, dy, tr;
        final short sB, sG, sR;
        final int oB, oG, oR;
        Map(int dx, int dy, int tr, short sB, int oB, short sG, int oG, short sR, int oR) {
            this.dx=dx; this.dy=dy; this.tr=tr;
            this.sB=sB; this.oB=oB; this.sG=sG; this.oG=oG; this.sR=sR; this.oR=oR;
        }
    }

    private static class Aff {
        final short s;
        final int o;
        final double err;
        Aff(short s, int o, double err) { this.s=s; this.o=o; this.err=err; }
    }
}