s1091521 Homework #5

s1091521 1122 Homework #5

1122 Digital Image Processing Assignment #5

學號：1091521

姓名：林哲慶

主題：Run-Length Based Image Compression 影像壓縮練習

專案目標：

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

開發平台：

        Windows 11, Python 3.9.10, OpenCV-Python 4.9.0, gcc/g++ 11.2.0, Visual Studio Code

專案結果：

        本次作業使用霍夫曼編碼（Huffman Coding）進行圖片壓縮，並與PNG無失真圖片壓縮進行比較。實作霍夫曼編碼壓縮時，套用兩種不同的方式進行檔案壓縮，分別為以1byte做Huffman Coding與3bytes做Huffman Coding，以下簡稱HC1以及HC3。各壓縮方式結果比較如下：

專案說明：

        該專案使用C++實作Huffman Coding，PNG則是使用Python與OpenCV用讀寫檔的方式實現。

        第一部分先說明Python和OpenCV將bmp轉成PNG的作法，將bmp讀入，並使用imwrite將檔案轉為PNG寫檔，在該函數中可以增加參數使得圖片變得更小，使用更高的壓縮率寫檔，但同時也會使用更多的運算時間。

        第二部分則是使用C++實作出Huffman Coding並用於壓縮bmp檔案。一開始以1byte作為單位做壓縮，發現壓縮效果不錯，但仍與PNG差一大截。為了獲得更高的壓縮率，除了觀察到作業所提供的bmp多數由重複的顏色與色塊組成，在較具有規律的檔案，能有更好的壓縮率。此時決定以3bytes為單位進行Huffman Coding，用RGB三種顏色數值進行編碼。改良進行前，需要先了解bmp檔案本身的結構，否則無法知道其RGB的放置方式，就好比網路協定的封包都具有特定格式。

        bmp檔案本身也有header，一般情況下具有24位元深度時，共佔54bytes，也就是說在進行Huffman Coding前，先將header與後方的顏色data進行分離，並將header完全保留，最後將顏色data進行編碼並壓縮。雖然Huffman Coding建立的tree檔案會比以1byte為單位進行編碼的tree大得多，但對於壓縮較大的檔案，其提升的壓縮率和省下的空間可以彌補tree過大的不足之處。

        第二部分不只壓縮檔案，也必須將檔案還原，所以會使用到壓縮過後的檔案以及該次壓縮時所產生的Huffman tree檔案，後者會用於解碼壓縮檔，並還原出原檔，達成無失真壓縮。