s1081050 作業6

Run-Length Based Image Compression 練習

目錄

• Run-Length Based Image Compression 練習
  • 目錄
  • 作業說明
  • 開發環境
  • 實作方式
  • 程式碼說明
  • 編譯與執行
    • 編譯
    • 執行程式
    • 比對結果
    • 壓縮率計算
  • 參考資料

作業說明

附件中為三張利用將晶片高度以色彩視覺化後的圖片。
請設計一個基於Run-Length 的壓縮法方，對圖檔作無失真壓縮後儲存成新檔案。
部落格上應敘述你的壓縮方法，提供壓縮檔之格式，並計算三張圖的平均壓縮率。

Table1	Image 1	Image 2	Image 3
預覽

開發環境

$ uname -srvmio
Linux 5.15.90.1-microsoft-standard-WSL2 #1 SMP Fri Jan 27 02:56:13 UTC 2023 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04.1) 11.3.0

實作方式

1. 讀入檔案
2. 因為三個檔案的標頭相同因此可以移除54 byte內容
3. 透過zigzag重排資料
4. 透過run-length進行壓縮
5. 反向解壓縮解碼
6. 用diff比較結果

程式碼說明

標頭檔

#include <iostream>
#include <string>
#include <vector>
#include <fstream>

編譯器指令

// Disable alignment for struct (讓編譯器不要自動對齊)
#pragma pack(1)

Namespace & Prototype 宣告

using namespace std;
vector<char> zigZagEncode(const std::vector<char>& input);
vector<char> zigZagDecode(const std::vector<char>& input);

BMP Header定義

struct BMPHeader 
{
    char signature[2] = {0x42, 0x4d};
    uint32_t fileSize = 14665254;
    uint32_t reserved = 0;
    uint32_t dataOffset = 54;
    uint32_t headerSize = 40;
    int32_t width = 2420;
    int32_t height = 2020;
    uint16_t planes = 1;
    uint16_t bitDepth = 24;
    uint32_t compression = 0;
    uint32_t imageSize = 0;
    int32_t xPixelsPerMeter = 0;
    int32_t yPixelsPerMeter = 0;
    uint32_t colorsUsed = 0;
    uint32_t colorsImportant = 0;
} bmpHeader;

主程式

int main(int argc, char* argv[] )
{
    for(auto i = 1; i < argc; i++)
    {
        // Open file
        fstream infile;
        infile.open(argv[i], ios::binary | ios::in);
        if(!infile)
        {
            cout << "Cannot open file: "<< argv[i] << endl;
            continue;
        }

        // Read file
        int dataSize = bmpHeader.fileSize - bmpHeader.dataOffset;        
        vector<char> pixelData(dataSize);
        infile.seekg(bmpHeader.dataOffset, std::ios::beg);
        for(int j = 0; j < dataSize; j++)
        {
            infile.read(&pixelData[j], sizeof(char));
        }
        infile.close();

        // ZigZag encoding
        cout << "encoding...\n";
        pixelData = zigZagEncode(pixelData);
        cout << "size: " << pixelData.size() << endl;
        // Run-length Compress
        cout << "compressing...\n";
        vector<char> outputData;
        int count = 1;
        for(int j = 0; j < pixelData.size(); j++)
        {
            char temp = pixelData[j];
            if(temp == pixelData[j+1] && count <= 255)
            {   
                count++;
            }
            else
            {
                outputData.push_back(temp);
                outputData.push_back(count);
                count = 1;
            }
        }
        cout << "size: " << outputData.size() << endl;
        // Write output binary file
        fstream outfile;
        string outFileName = "output_" + string(argv[i]) + ".bin";
        outfile.open(outFileName, ios::binary | ios::out);
        outfile.write(&(outputData[0]), outputData.size());
        outfile.close();

        // Read output binary file
        cout << "Loading bin file...\n";
        fstream infile2;
        infile2.open(outFileName, ios::binary | ios::in);
        if(!infile2)
        {
            cout << "Cannot open file: "<< outFileName << endl;
            continue;
        }

        // Get file size
        infile2.seekg(0, ios::end);
        int dataSize2 = infile2.tellg();
        infile2.seekg(0, ios::beg);
        cout << "size: " << dataSize2 << endl;
        cout << "Uncompressing...\n";
        // Read file
        vector<char> inputData2(dataSize2);
        infile2.seekg(0, std::ios::beg);
        for(int j = 0; j < dataSize2; j++)
        {
            infile2.read(&inputData2[j], sizeof(char));
        }
        infile2.close();

        vector<char> pixelData2(pixelData.size());
        int j = 0, index = 0 ;
        while(j < inputData2.size())
        {
            char temp = inputData2[j++];
            int count = (uint)inputData2[j++];
            for(int k =0; k < count; k++)
                pixelData2[index++] = temp;
        }
        cout << "size: " << pixelData2.size() << endl;
        pixelData2 = zigZagDecode(pixelData2);
        fstream outfile2;
        string outFileName2 = "output_rev_" + string(argv[i]);
        outfile2.open(outFileName2, ios::binary | ios::out);
        outfile2.write(reinterpret_cast<char*>(&bmpHeader), sizeof(bmpHeader));
        outfile2.write(&(pixelData2[0]), pixelData2.size());
        outfile2.close();
    }
    return 0;
}

ZigZag Encode & Decode

vector<char> zigZagEncode(const std::vector<char>& input) 
{
    vector<char> output;
    int numColumns = 16;
    int numRows = input.size() / numColumns;
    int i = 0, j = 0;
    bool up = true;
    while (i < numRows && j < numColumns) 
    {
        output.push_back(input[i * numColumns + j]);
        if (up) 
        {
            if (i == 0)
            {
                up = false;
                j++;
            }
            else if (j == numColumns - 1) 
            {
                up = false;
                i++;
            }
            else 
            {
                i--;
                j++;
            }
        } 
        else 
        {
            if (j == 0)
            {
                up = true;
                i++;
            }
            else if (i == numRows - 1) 
            {
                up = true;
                j++;
            } 
            else 
            {
                i++;
                j--;
            }
        }
    }
    return output;
}

vector<char> zigZagDecode(const std::vector<char>& input) 
{
    vector<char> output(input.size());
    int numColumns = 16;
    int numRows = input.size() / numColumns;
    int i = 0, j = 0;
    bool up = true;
    int index = 0;
    while (index < input.size()) 
    {
        output[i * numColumns + j] = input[index];
        if (up) {
            if (i == 0) 
            {
                up = false;
                j++;
            }
            else if (j == numColumns - 1) 
            {
                up = false;
                i++;
            }
            else 
            {
                i--;
                j++;
            }
        }
        else 
        {
            if (j == 0)
            {
                up = true;
                i++;
            }
            else if (i == numRows - 1) 
            {
                up = true;
                j++;
            }
            else 
            {
                i++;
                j--;
            }
        }
        index++;
    }
    return output;
}

編譯與執行

編譯

g++ image_compress.cpp

執行程式

 ./a.out img1.bmp img2.bmp img3.bmp

比對結果

diff img1.bmp output_rev_img1.bmp
diff img2.bmp output_rev_img2.bmp
diff img3.bmp output_rev_img3.bmp

壓縮檔案(output_rev_xxxx.bmp)還原後和原始檔案大小一致

透過diff比對內容結果一致

壓縮率計算

Table2	Image 1	Image 2	Image 3
原始圖片
原始大小	14665254	14665254	14665254
壓縮大小	6928092	8319702	6917278
壓縮率	211.68%	176.27%	212.01%

平均壓縮率:(14665254*3)/(6928092+8319702+6917278) * 100% = 198.49%

參考資料

• BMP Header
• ZigZag