vn7'blog
0%

用四叉樹來對bmp與tiff實做圖像壓縮

發表於 更新於 分類於

先簡單介紹一下四叉樹QuadTree，四叉樹是一個樹狀的資料結構，經常運用在畫面處理或是2D的碰撞檢測。
從根節點root出發，當節點內達到一個條件的時候會再分裂成四個子節點。
詳細的介紹可以看Quadtree - Wikipedia
樹可能會長這樣(圖片取自wiki)

一般狀況下圖片會有RGB三原色，值是0~255，這次我設定四叉樹節點分裂的條件是區域內的RGB顏色離散程度到某個值就分裂。 `離散程度0到1，越接近0離散程度越低，mu則是區域內RGB的平均值`
接下來進入正題，要做壓縮的圖片有兩張。



把圖片讀進來後在compress這個method裡面做處理。如果有tiff檔無法讀取的狀況，請加入jai-imageio-core這個lib

1
2
3
4
5
6
7
8
9
10
11
12
13
public static BufferedImage compress(BufferedImage image, double threshold) {
    Color[][] colors = makeColorArray(image);
    int width = image.getWidth();
    int height = image.getHeight();
    QuadTree quadTree = new QuadTree(colors, new ImageMeasure(), threshold);
    BufferedImage outImage = new BufferedImage(width, height, BufferedImage.TYPE_INT_RGB);
    for (int i = 0; i < width; i++) {
        for (int j = 0; j < height; j++) {
            outImage.setRGB(i, j, quadTree.get(i, j).getRGB());
        }
    }
    return outImage;
}

threshold是設定離散程度到多少要分裂
這裡寫個一個ImageMeasure類別來對圖像讀進來的資料作運算
approximate運算區域內像素的色彩近似值
measureDetail運算區域內色彩的離散程度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public Color approximate(Color[][] data, int x, int y, int width, int height) {
    int redSum = 0;
    int greenSum = 0;
    int blueSum = 0;

    for (int i = x; i < x + width; i++) {
        for (int j = y; j < y + height; j++) {
            redSum += data[i][j].getRed();
            greenSum += data[i][j].getGreen();
            blueSum += data[i][j].getBlue();
        }
    }

    int pixelCount = width * height;

    return new Color(redSum / pixelCount, greenSum / pixelCount, blueSum / pixelCount);
}

public double measureDetail(Color[][] data, int x, int y, int width, int height) {
    int redSum = 0;
    int greenSum = 0;
    int blueSum = 0;

    for (int i = x; i < x + width; i++) {
        for (int j = y; j < y + height; j++) {
            redSum += data[i][j].getRed();
            greenSum += data[i][j].getGreen();
            blueSum += data[i][j].getBlue();
        }
    }

    double pixelCount = width * height;

    double redAvg = redSum / pixelCount;
    double greenAvg = greenSum / pixelCount;
    double blueAvg = blueSum / pixelCount;

    redSum = 0;
    greenSum = 0;
    blueSum = 0;

    for (int i = x; i < x + width; i++) {
        for (int j = y; j < y + height; j++) {
            int red = data[i][j].getRed();
            int green = data[i][j].getGreen();
            int blue = data[i][j].getBlue();

            redSum += Math.pow(red - redAvg, 2);
            greenSum += Math.pow(green - greenAvg, 2);
            blueSum += Math.pow(blue - blueAvg, 2);
        }
    }
    return redSum / (pixelCount * 255 * 255) + greenSum / (pixelCount * 255 * 255) + blueSum / (pixelCount * 255 * 255);
}

quadtree中新增節點的時候則看運算的結果來決定要不要分裂以及節點的顏色近似值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public Node(Color data[][], int x, int y, int width, int height) {
    this.x = x;
    this.y = y;
    this.width = width;
    this.height = height;
    if ((width == 1) || (height == 1) || (measure.measureDetail(data, x, y, width, height) <= threshold)) {
        value = measure.approximate(data, x, y, width, height);
    } else {
        children = new Node[4];

        children[0] = new Node(data, x, y, width / 2, height / 2);
        children[1] = new Node(data, x + width / 2, y, width - width / 2, height / 2);
        children[2] = new Node(data, x, y + height / 2, width / 2, height - height / 2);
        children[3] = new Node(data, x + width / 2, y + height / 2, width - width / 2, height - height / 2);
    }

}

這是運算之後的結果


完整程式碼在這裡
Quadtree Compression