s1081050 作業6
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
$ 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
實作方式
- 讀入檔案
- 因為三個檔案的標頭相同因此可以移除54 byte內容
- 透過zigzag重排資料
- 透過run-length進行壓縮
- 反向解壓縮解碼
- 用diff比較結果
程式碼說明
標頭檔
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
編譯器指令
// Disable alignment for struct (讓編譯器不要自動對齊)
#pragma pack(1)
// 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);
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;
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;
}
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;
}
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
g++ image_compress.cpp
執行程式
 ./a.out img1.bmp img2.bmp img3.bmp
 ./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
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%
 
 
 
留言
張貼留言