---
title: 'CS362 Assignment #6'
disqus: hackmd
---

Run-Length Based Image Compression 練習
===

## 目錄

[TOC]

## 作業說明
附件中為三張利用將晶片高度以色彩視覺化後的圖片。
請設計一個基於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](https://zh.wikipedia.org/zh-tw/BMP)
- [ZigZag](https://www.uoanbar.edu.iq/eStoreImages/Bank/6137.pdf)
###### tags: `CS362` `s1081050` `HW6`