---
# System prepended metadata

title: 影像處理專題 資料

---

# 影像處理專題 資料
{%hackmd nzwXYrKQTGqIftPO5fCdKA %}

<style>
    .red{
        color:#f26;
    }
    .gr{
        color:#11ff11;
    }
</style>

:::    spoiler 24.03.13
# 論文閱讀
# Nearly lossless HDR images compression by background image segmentation
=======================================================================

文章連結: https://ieeexplore.ieee.org/abstract/document/7888260

## 大概在說甚麼?
+ 論文中的Input image 為X光照片，由於他是X光所以基本上為只有灰階值的圖
+ 他將Input_im 做依照閾值(threshold) 的影像分割
+ 形成了 `Foreground` 以及`Background`
+ 依照我們對於此兩種區域 我們認為他所攜帶的影像資訊多寡分別做出處理:
    + `Foreground` 攜帶資訊較為單一重複； 較適合使用RLE算法
    + `Background` 攜帶資訊較為複雜多樣； 較適合使用LZ77算法 (或LZW)
+ 至少在此篇論文中的ROI (region of interesting) 為`Background`
#### Flow chart:
![image](https://hackmd.io/_uploads/H1k437PAT.png =80%x)

## RLE(run-length encoding) 是什麼?
### 上課有說過!
運行長度編碼，又稱行程長度編碼或變動長度編碼法，是一種與資料性質無關的無失真資料壓縮技術，基於「使用變動長度的碼來取代連續重複出現的原始資料」來實現壓縮。(By wiki)
+ 簡單來說，舉個例子`2444666668888888` 這一段編碼使用了16個單位去存取訊息
+ 但經過RLE 後他會變成 `12345678` 意思代表 "一個2 三個4 五個6 七個8" 所以這樣所需的單位就變成了 8個
+ 但如果原始訊息為 `12345678` 經過RLE後 反而會變冗長成 `1112131415161718`
+ 所以可想而之這樣的編碼適合大量重複的資訊，像是影像中的低頻部分或者是"背景"

## LZ77 是什麼?
### Buffer 向前緩衝區:
+ 當壓縮開始時，從窗口向前預載 n個單位 稱為向前緩衝區
### Slide window 滑動窗口:
+ 一段為 m單位的窗口， 存在在窗口中的資料若未編碼過， 會形成新的 字典
### Dictionary
+ 就是儲存
### 圖解
#### 壓縮
![image](https://s2.51cto.com/images/blog/202106/06/69dc5f82600a4054b698bbfab1556b13.png?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=/format,webp/resize,m_fixed,w_1184)
![image](https://s2.51cto.com/images/blog/202106/06/c492780be436fa14e1a29b3eef37fc9c.png?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=/format,webp/resize,m_fixed,w_1184)
![image](https://s2.51cto.com/images/blog/202106/06/123a0a59bc7887729df9d565d8cd5be1.png?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=/format,webp/resize,m_fixed,w_1184)
![image](https://s2.51cto.com/images/blog/202106/06/2de6fe53e7392248e7901b08d98b476d.png?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=/format,webp/resize,m_fixed,w_1184)
![image](https://s2.51cto.com/images/blog/202106/06/2de6fe53e7392248e7901b08d98b476d.png?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=/format,webp/resize,m_fixed,w_1184)
![image](https://s2.51cto.com/images/blog/202106/06/a9a9723593a6ae5986dd5f2c6d0dad8f.png?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=/format,webp/resize,m_fixed,w_1184)
![image](https://s2.51cto.com/images/blog/202106/06/9438dba073d562e6dc6923fbdf631bb5.png?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=/format,webp/resize,m_fixed,w_1184)
![image](https://s2.51cto.com/images/blog/202106/06/6972aa8604954b942dd46dc674d92b4d.png?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=/format,webp/resize,m_fixed,w_1184)

#### 解壓縮
![image](https://s2.51cto.com/images/blog/202106/06/2e5df3b4e85f5803beb7d7a6f36e3567.png?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=/format,webp/resize,m_fixed,w_1184)
![image](https://s2.51cto.com/images/blog/202106/06/c58d53452b8ecc7f8080900ec8683e97.png?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=/format,webp/resize,m_fixed,w_1184)
![image](https://s2.51cto.com/images/blog/202106/06/2489ef24dde442b9af7f3f355de3809a.png?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=/format,webp/resize,m_fixed,w_1184)
![image](https://s2.51cto.com/images/blog/202106/06/3ee46bbc6b25098972c05336c45e0902.png?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=/format,webp/resize,m_fixed,w_1184)
![image](https://s2.51cto.com/images/blog/202106/06/effab8e2fd2e4f4fa1274f7fd7c2bc8f.png?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=/format,webp/resize,m_fixed,w_1184)
![image](https://s2.51cto.com/images/blog/202106/06/3f0b77ab90694dafc376f3326f7fe0a3.png?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=/format,webp/resize,m_fixed,w_1184)
![image](https://s2.51cto.com/images/blog/202106/06/ba30bd58df8ae8748e627cc57c013fbe.png?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=/format,webp/resize,m_fixed,w_1184)
[圖解LZ77在幹嘛](https://blog.51cto.com/u_15127629/2873305)
###  比較: LZ77 and LZW(上課說的那個)
+ LZ77:它只是根据指標和長度来重構原始數據
+ LZW: 會需要有一本字典作為壓縮及解壓縮的傳輸的資料，解壓縮需要使用與壓縮時相同的字典来重建原始數據。

## Reference:
L. Chen and Z. -m. Wang, "Nearly lossless HDR images compression by background image segmentation," _2016 IEEE International Conference on Signal and Image Processing (ICSIP)_, Beijing, China, 2016, pp. 241-246, doi: 10.1109/SIPROCESS.2016.7888260.

<hr>
<br>
<br>
<br>
<br>
<br><br>
<br>
<br><br>
<br>
<br>
<br>


An Efficient Image Compression Algorithm for almost Dual-Color Image Based on K-Means Clustering, Bit-Map Generation and RLE
=======================================================================


文章連結: https://ieeexplore.ieee.org/document/5640529
### 大概在說什麼?
+ 這一篇論文的input image為只有兩種顏色的影像
+ 之後利用 K-means 算法 將影像分割成兩區
+ Bit-Map 其實就只是 將 K-means 算出來的顏色轉換成 `0` 和 `1`
+ 這樣就可以使用 RLE 去執行壓縮

### 和JPEG compression 比較壓縮率 以及展示
![image](https://hackmd.io/_uploads/BJkUhaw0T.png)
![image](https://hackmd.io/_uploads/B15A3pDAp.png =80%x)

+ 因為input image 的性質太好了 所以看起來壓縮率比起JPEG 好很多
+ 並且為Nearly lossless compression

## Reference:
A. Banerjee and A. Halder, "An efficient image compression algorithm for almost dual-color image based on k-means clustering, bit-map generation and RLE," _2010 International Conference on Computer and Communication Technology (ICCCT)_, Allahabad, India, 2010, pp. 201-205, doi: 10.1109/ICCCT.2010.5640529.

<hr>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>

A Lossless Image Compression Algorithm Based On Group Encoding
==============================================================
文章連結: https://ieeexplore.ieee.org/document/9208909

### 
+  group encoding algorithm 建立一個代表像素顏色群組重複或非重複的編碼序列。 
+  群組編碼的過程從第一個像素開始，並在同一圖像的最後一個像素結束。
+  一般來說，這是一個循環編碼過程，創建一個字節序列（1-D 數組），其中新數組的大小小於原始圖像的大小。
![image](https://hackmd.io/_uploads/HyMlvTvAT.png)

##  Reference:
V. Koval, V. Yatskiv, I. Yakymenko and D. Zahorodnia, "A Lossless Image Compression Algorithm Based On Group Encoding," _2020 10th International Conference on Advanced Computer Information Technologies (ACIT)_, Deggendorf, Germany, 2020, pp. 871-874, doi: 10.1109/ACIT49673.2020.9208909.
:::

:::spoiler 24.03.27
A Lossless Image Compression Algorithm Based On Group Encoding
==============================================================
文章連結: https://ieeexplore.ieee.org/document/9208909

## 在幹嘛??
+ 依照RLE (run-length encoding) 的概念去發想的另外一種編碼法
### 資料結構:


##  Reference:
V. Koval, V. Yatskiv, I. Yakymenko and D. Zahorodnia, "A Lossless Image Compression Algorithm Based On Group Encoding," _2020 10th International Conference on Advanced Computer Information Technologies (ACIT)_, Deggendorf, Germany, 2020, pp. 871-874, doi: 10.1109/ACIT49673.2020.9208909.
:::



:::spoiler 24.04.14
# 240414
1. 完成了 2D 轉 1D的RLE 
2. 發現了這個方法有很大的問題
用"cameraman.tif"這張照片 去壓縮發現壓縮後資料反而變成1.69倍大
但用背景相對單一的"brain_492.tif" 這張照片 去壓縮壓縮比也還是有0.689
再更極端一點使用一張Binary的圖 "circuit_bw.tif" 是有很好的壓縮比:0.118
3. 將row-oriention 換成<span style="
color:#f27">zig-zag</span>方式去讀取轉換成向量的方式 
跟想像中比起來好像並沒有必較好的樣子

**2D to 1D RLE main function**
```=
clc;
image = imread("cameraman.tif");
% imshow(image)
[row,col] = size(image);
im2arr = zeros(1,col*row);
for i = 0:row-1
    im2arr(i*col+1:1+(i+1)*col-1) = image(i+1,:);
end
fprintf("the original size of image is %d\n", length(im2arr));
rle_arr = rle(im2arr);
fprintf("the 'after compression' size of image is %d\n", length(rle_arr));
fprintf("the compression rate compr. / original is %f\n", length(rle_arr)/length(im2arr))
recover_arr = irle(rle_arr);
recover_mat = zeros(row,col);
for i = 1:256
    k = (i-1)*256;
    recover_mat(i,:) = recover_arr(k+1:k+256);
end
im_recover = mat2gray(recover_mat);
subplot(1,2,1),imshow(image); title("Oriniginal  Image")
subplot(1,2,2),imshow(im_recover); title("Recover After Compression Image")
```

**zig-zag function**
```=
function  result = zigzag_read(mat)
    [m, n] = size(mat);
    result = zeros(1, m * n);
    index = 1;
    for sum_idx = 1:(m + n - 1)
        if rem(sum_idx, 2) == 1 
            for i = max(1, sum_idx - n + 1):min(sum_idx, m)
                result(index) = mat(i, sum_idx - i + 1);
                index = index + 1;
            end
        else 
            for i = max(1, sum_idx - n + 1):min(sum_idx, m)
                result(index) = mat(sum_idx - i + 1, i);
                index = index + 1;
            end
        end
    end
end
```

**RLE**
```=
function result=rle(vector)
L=length(vector);
j=1; k=1; i=1;
while i<2*L
    comp=1;
    for j=j:L
        if j==L 
            break
        end
         if vector(j)==vector(j+1)
            comp=comp+1;
        else
            break
         end
    end
        result(k+1)=comp;
        result(k)=vector(j);
        if j==L && vector(j-1)==vector(j) 
            break
        end  
        i=i+1;
        k=k+2;
        j=j+1;
        if j==L 
            if mod(L,2)==0 
                result(k+1)=1;
                result(k)=vector(j);
            else
                result(k+1)=1;    
                result(k)=vector(j);
            end
                break
        end
end
```
Right(Original image) Left(Recover After Compression Image)
![untitled](https://hackmd.io/_uploads/rkRnohieC.jpg)

COMMAND WINDOW MESSENGE
the original size of image is 65536
the 'after compression' size of image is 110774
the compression rate compr. / original is <span style="color:red">1.690277</span>


zig-zag direction
the original size of image is 65536
the 'after compression' size of image is 115100
the compression rate compr. / original is <span style="color:red">1.756287</span>


Right(Original image) Left(Recover After Compression Image)
![image](https://hackmd.io/_uploads/ByKJR3slA.png)

COMMAND WINDOW MESSENGE
the original size of image is 307200
the 'after compression' size of image is 433458
the compression rate compr. / original is <span style="color:red">1.410996</span>



zig-zag direction

the original size of image is 73984
the 'after compression' size of image is 115074
the compression rate compr. / original is <span style="color:red">1.555390</span>


<span style="font-size:23px;color:#f25f26">Nearly monotonous background </span>
![image](https://hackmd.io/_uploads/H1ML1Toe0.png)
COMMAND WINDOW MESSENGE
the original size of image is 349920
the 'after compression' size of image is 241152
the compression rate compr. / original is <span style="color:red">0.689163</span>



zig-zag direction

the original size of image is 73984
the 'after compression' size of image is 28714
the compression rate compr. / original is <span style="color:red">0.388111</span>

<span style="font-size:23px;color:#f25f26">Binary Case </span>
![image](https://hackmd.io/_uploads/HybDZajxC.png)
COMMAND WINDOW MESSENGE
the original size of image is 76160
the 'after compression' size of image is 9006
the compression rate compr. / original is <span style="color:red">0.118251</span>

zig-zag direction

the original size of image is 73984
the 'after compression' size of image is 14458
the compression rate compr. / original is <span style="color:red">0.195421</span>


## Image Resourses: 
https://people.math.sc.edu/Burkardt/data/tif/tif.html
:::

::: spoiler 24.04.24

用Decoder 的想法去思考比較簡單
反而Encoder 的想法去想好難喔 :(
半成品@0423
```=
% ouput = struct("tag", []
%               "similar_arr", [],
%               "diff_nums", [], 
%               ......
%               ......                    )
% similar_arr = struct("similar_count", [] 
%                                 , "number" , [], "scale" , [] 
%                                   ......
%                                    ......                    )
% diff_nums = struct("number", [] , "scale","scale".............)

%%
clear;clc
img_arr = [2,2,2,2,2,  1,1,  3,2,   5,5,   4,4,9,   6,6,6,6, 1,1, 0];
similar_str = struct('N', [], 'scale', []);

% Handle the tag
if img_arr(1) == img_arr(2)
    output.tag = 1; % present start from the similar tuple
    idx = 2;
    similar_str.N = 2; %at least 2 element are the same
else
    output.tag = 0;
    idx=1;
end

sim_idx = 1;
similar_arr = [];
diff_count = 0 ;
similar_count =0;

while idx<length(img_arr)
        if img_arr(idx) == img_arr(idx+1)    
            diff_count =0; %開始相同所以diff count return zero
            idx = idx+1;
            similar_str.N = similar_str.N +1; 
            continue;
        else
            diff_count =diff_count+1;
            if diff_count==2

                fprintf("%d is simcount\n",similar_count);
                
                %Return to zero 
                similar_count=0;
                diff_count =0;
                
                fprintf("%d is the start of diffent number\n",idx);
                diff_scale = img_arr(idx);

                %push diff scale into similar array\
                similar_arr = pushArr(similar_arr,diff_scale);
            else

                similar_str.scale = img_arr(idx);
                fprintf("%d and %d are not the same\n",idx,idx+1);
                if similar_str.N>1
                    similar_count = similar_count +1;
                    similar_arr = pushArr(similar_arr,similar_str.N);
                    similar_arr = pushArr(similar_arr,similar_str.scale);
                end
                similar_str.N = 1;      
                idx = idx+1;
            end
        end
end
printArr(similar_arr);





function outputArr = pushArr(arr,element)
    idx = length(arr) +1;
    arr(idx) = element;
    outputArr = arr;
end
function printArr(arr)
    fprintf("\n");
    for i=1:length(arr)
        fprintf("%d ",arr(i));
    end
end
```
<span style="background-color:#705200">INPUT: img_arr = [2,2,2,2,2,  1,1,  3,2,   5,5,   4,4,9,   6,6,6,6, 1,1] </span>
<span style="background-color:#320070">
OUTPUT: rle_arr = [5	2	2	1	3	2	2	5	2	4	9	4	6	2	1] </span>


<span style="background-color:#006570">
    "ideal" OUTPUT: rle_arr = [<span style="color:#f27">2</span> 5	2	2	1//	<span style="color:#f27">2</span> 3	2//<span style="color:#f27">2</span>	2	5	2	4//<span style="color:#f27">1</span>	9//<span style="color:#f27">2</span>	4	6	2	1] </span>
![SmartSelect_20240420_133729_Samsung Notes](https://hackmd.io/_uploads/rkk4rRg-C.jpg)


~~暫時卡住~~ <span style="color:#f27fff;font-size:26px">成功了!</span>
## 結果:
1. "cameraman.tif" compression rate :  0.9537661 <span style="color:#f27">(1.690277)</span>
2. "balloons.tif" compression rate = 0.9121251 <span style="color:#f27">(1.410996)</span>
3. "brain_492.tif"  compression rate = 0.2031711 <span style="color:#f27">(0.68)</span>
4. "circuit.tif"  compression rate = 0.1105651 <span style="color:#22ff99">(0.118251)</span>
![cameraman](https://hackmd.io/_uploads/BkqgAGLWR.png =40%x)![balloons](https://hackmd.io/_uploads/Bk9gCM8b0.png =40%x)
![brain_492](https://hackmd.io/_uploads/B1sgCMIW0.png =40%x)![circuit_bw](https://hackmd.io/_uploads/HycxRzUZC.png =40%x)

## 分析
+ 壓縮比分析:
*worst case*: 重複兩個 接一個不重複 再重複兩個
In:$\;\;\,$ [1 1 2 3 3 4 5 5 6 7 7....] 
Out: [1// 1 2 1// 1 2// 1 2 3// 1 4 // 1 2 5 // 1 6 // 1 2 7 .... ] 
重複的case 壓縮比會變成<span style="color:#f27">1.5倍</span>
非重複的case 壓縮比會變成<span style="color:#f27">2倍</span>
所以整體的壓縮比會是 <span style="color:#f27">1.75倍</span>
和之前的2倍相比會是一個較好的改良方案
+ 優點:
若是每一個元素都不一樣，這個方法基本上大小不會變大(就多兩個元素 tag 和 diff_num)
worst case的形式會比較少見 (重複兩個 接一個不重複 再重複兩個)

+ 只要$\underline{\text{重複的數字超過3 或是有大於1組的重複數組}}$， 重複的部分就會被壓縮到
+ 只要$\underline{\text{連續不重複的數字越多， 重複的壓縮比就會趨近於1}}$ 
$$\underset{n\rightarrow ∞}{lim}\frac{n+1}{n}=1$$
:::


:::    spoiler 24.05.01
## Decoder 寫出來了!!!!!!!!
Code:
```=
%Set array
decode = [];
code = [3 3 2 5 1 7 0 4 9 4 7 6 2 2 0 3 4 2 2 7 2 2 5 4 0];
%========Magic==========
N = length(code);
code = [code code(N)+1 code(N)+1];
%======================
N = length(code);
index = 1;
de_index =1;

for i = 1:N
    % End Requirement
     if index==N
            fprintf("Read over");
            disp(decode);
            break
     end

     %Read how many same set 
    if index<N     
        sameSets = code(index); index = pp(index);
    end

    for k = 1:sameSets
        %Read how many repetition of scale 
        if index<N    
            sameNumber = code(index); index = pp(index);
        end
        for j = 1:sameNumber
            %Repeat scales and push into decode array
            if index<N    
                element = code(index); 
                decode(de_index) = element; de_index = pp(de_index);
            end
        end
         index = pp(index);

         % End Requirement
         if index==N
            fprintf("Read over")
            break
         end
    end
     % End Requirement
     if index==N
            fprintf("Read over")
            break
     end

    %Read how many different num would show
    if index<N
        diffentNum = code(index); index = pp(index);
    end
    for d = 1: diffentNum
         % End Requirement
         if index==N
                fprintf("Read over")
                break
         end
        if index<N
            element = code(index); index = pp(index);
            decode(de_index) = element; de_index = pp(de_index);
        end
    end
end
disp(decode);
```
Decoder(完成):
+ 測試(簡單陣列)
<span style="background-color:#329970; border:solid 1px; padding:2px">INPUT: code = [3 3 2 5 1 7 0 4 9 4 7 6 2 2 0 3 4 2 2 7 2 2 5 4 0]</span>
<span style="background-color:#327099; border:solid 1px; padding:2px">OUTPUT:decode=[2	2	2	1	1	1	1	1	0	0	0	0	0	0	0	9	4	7	6	0	0	4	4	4	2	7	5	5	0	0	0	0]</span>
```=
function decode = Decoder(code)
%==========================
% INPUT: Modifiled RLE code
%OUTPUT: Uncompressed original data
%==========================

N = length(code);
code = [code code(N)+1 code(N)+1];

N = length(code);
index = 1;
de_index =1;

for i = 1:N
    % End Requirement
     if index==N
            fprintf("Read over");
            disp(decode);
            break
     end

     %Read how many same set 
    if index<N     
        sameSets = code(index); index = pp(index);
    end

    for k = 1:sameSets
        %Read how many repetition of scale 
        if index<N    
            sameNumber = code(index); index = pp(index);
        end
        for j = 1:sameNumber
            %Repeat scales and push into decode array
            if index<N    
                element = code(index); 
                decode(de_index) = element; de_index = pp(de_index);
            end
        end
         index = pp(index);

         % End Requirement
         if index==N
            fprintf("Read over")
            break
         end
    end
     % End Requirement
     if index==N
            fprintf("Read over")
            break
     end

    %Read how many different num would show
    if index<N
        diffentNum = code(index); index = pp(index);
    end
    for d = 1: diffentNum
         % End Requirement
         if index==N
                fprintf("Read over")
                break
         end
        if index<N
            element = code(index); index = pp(index);
            decode(de_index) = element; de_index = pp(de_index);
        end
    end
end
```
![image](https://hackmd.io/_uploads/B1X9NlC-A.png)


## Burrows-Wheeler變換
Burrows–Wheeler Transform（簡稱BWT，也稱作塊排序壓縮）

當一個字符串用該算法轉換時，算法只改變這個字符串中字符的順序而並不改變其字符
如果原字符串有幾個出現多次的子串，那麼轉換過的字符串上就會有一些連續重複的字符
這對壓縮是很有用的。
該方法能使得基於處理字符串中連續重複字符的技術（如MTF變換和RLE）的編碼更容易被壓縮。

### Examle:

![image](https://hackmd.io/_uploads/rk2NGAIZR.png =60%x)
![image](https://hackmd.io/_uploads/ByULzAL-R.png =60%x)
![image](https://hackmd.io/_uploads/BJpvG08WC.png =60%x)
![image](https://hackmd.io/_uploads/BJR_M0LWA.png =60%x)
![image](https://hackmd.io/_uploads/rJg9z08-A.png =60%x)
![image](https://hackmd.io/_uploads/S1hhfRUZC.png =60%x)



```=
function bw_transformed = bwt(input_array)
    % Add a unique end-of-string marker
    input_array = [input_array '$'];

    % Create a matrix of all cyclic permutations
    n = length(input_array);
    cyclic_permutations = cell(1, n);
    for i = 1:n
        cyclic_permutations{i} = circshift(input_array, [0, i-1]);
    end

    % Sort the cyclic permutations
    cyclic_permutations = sort(cyclic_permutations);

    % Extract the last column
    bw_transformed = cellfun(@(x) x(end), cyclic_permutations);
end

```

![image](https://hackmd.io/_uploads/HkoPBlAZA.png)
### 問題
對於"文字"的作用比較大，舉例來說"HE" 在一篇文章中有很大的機率前面會接上"T"
組成"THE"的字串。 所以當我們按照字典序排列時，"HE"會被排到相似的地方所以我們就可以再字串尾端找到挺多的"T"。
所以對於文字的灰度的RLE計算是否有幫助，尚待研究。
### 重寫Encoder

```=
% Handle the tag
img_arr = [2 2 2 2 3 3 3 3 3 4 5 6 7 2 2 1 2 3 4 2 2 2 6 8 8 0];
if img_arr(1) == img_arr(2)
    output.tag = 1; % present start from the similar tuple
    idx = 2;
    similar_str.N = 2; %at least 2 element are the same
else
    output.tag = 0;
    idx=1;
end
sameNumber =1;
diffentNumber =1;
for i=2:length(img_arr)-1

    if img_arr(i) == img_arr(i+1)
        sameNumber = sameNumber+1;
        if diffentNumber ~= 1
            fprintf("=================\n")
        end
        diffentNumber =1;
        fprintf("%d and %d are the same N:%d\n",i,i+1,sameNumber);
    else
        sameNumber = sameNumber+1;
        if sameNumber ==diffentNumber
            fprintf("---------------------------\n");
        end
        fprintf("%d and %d are not the sameN:%d, D:%d\n",i,i+1,sameNumber,diffentNumber);
        similar_str.N = sameNumber;
        similar_str.scale = img_arr(i);
        if sameNumber ==1
            diffentNumber = diffentNumber+1;
        end
        sameNumber =0;
    end
end
```
```=
|  2 and 3 are the same N:2
|  3 and 4 are the same N:3
|- 4 and 5 are not the sameN:4, D:1

OUTPUT: 2 has 4 times

|  5 and 6 are the same N:1
|  6 and 7 are the same N:2
|  7 and 8 are the same N:3
|  8 and 9 are the same N:4
|- 9 and 10 are not the sameN:5, D:1

OUTPUT: 3 has 5 times

--------------------sameSets 2

|- 10 and 11 are not the sameN:1, D:1
|- 11 and 12 are not the sameN:1, D:2
|- 12 and 13 are not the sameN:1, D:3
|- 13 and 14 are not the sameN:1, D:4

=========diffentNumber 4

|  14 and 15 are the same N:1
|- 15 and 16 are not the sameN:2, D:1

OUTPUT: 2 has 2 times

--------------------sameSets 1

|- 16 and 17 are not the sameN:1, D:1
|- 17 and 18 are not the sameN:1, D:2
|- 18 and 19 are not the sameN:1, D:3
|- 19 and 20 are not the sameN:1, D:4

=========diffentNumber 4

|  20 and 21 are the same N:1
|  21 and 22 are the same N:2
|- 22 and 23 are not the sameN:3, D:1

OUTPUT: 2 has 3 times

--------------------sameSets 1

|- 23 and 24 are not the sameN:1, D:1

=========diffentNumber 1

|  24 and 25 are the same N:1
|- 25 and 26 are not the sameN:2, D:1

OUTPUT: 8 has 2 times

```

![image](https://hackmd.io/_uploads/HkivsIJMA.png)
![image](https://hackmd.io/_uploads/rkV-681GC.png)
:::

:::spoiler 24.05.22
## 測試Blockwise compression
+ 附加優點 : Encode最大值 <256 $\Rightarrow$ 確定可以用一個BYTE去儲存。
+ 保證壓縮率 $\leq$ 1 can apply to general cases
+ 對於壓縮率本來就低的Case 可能沒顯著效果。

```=
clear;
image = imread("mybrain.png");
    [rows, cols] = size(image);
    original_size = rows*cols;
    
    blockSize = 16;
    numBlocks = (rows / blockSize) * (cols / blockSize);
    encode = [];

    % Iterate over each 16x16 block
    for i = 1:blockSize:rows
        for j = 1:blockSize:cols
            % Extract the block
            block = image(i:i+blockSize-1, j:j+blockSize-1);
            
            % Flatten the block into a vector
            block_vector = block(:);
            
            % Perform RLE
            encoded_block = Encoder(block_vector);
            if max(size(block_vector)) < max(size(encoded_block))
                encoded_block = [ block_vector];
            end
            append_sz = max(size(encoded_block));
            for id = 1:append_sz
                encode(end+1) =  encoded_block(id);
            end
        end
    end
    comprRate = length(encode)/original_size;
```


![image](https://hackmd.io/_uploads/Sythjkj7C.png)


| <span style="color:#f28;border:solid,0.5px;padding:5px">compr_rate</span> | common RLE | improved RLE            | blockwise RLE                 |
| ---------------------------------------------------------------------------- | ---------- | ----------------------- | ----------------------------- |
| cameraman                                                                    | 1.6903     | 1.1259                  | <span class="gr">0.9772</span>       |
| bollons                                                                      | 1.3303     | 1.1031                  | <span class="gr">0.9945</span>       |
| brain                                                                        | 1.1301     | 0.7682                  | <span class="gr">0.756</span> |
| brain492                                                                     | 0.3733     | <span class="gr">0.2471</span> | 0.2522                        |
:::

# 0529
## 上禮拜測試的 Blockwise RLE encoding 
| <span style="color:#f28;border:solid,0.5px;padding:5px">compr_rate</span> | common RLE | improved RLE            | blockwise RLE                 |
| ---------------------------------------------------------------------------- | ---------- | ----------------------- | ----------------------------- |
| cameraman                                                                    | 1.6903     | 1.1259                  | <span class="gr">0.9772</span>       |
| bollons                                                                      | 1.3303     | 1.1031                  | <span class="gr">0.9945</span>       |
| brain                                                                        | 1.1301     | 0.7682                  | <span class="gr">0.756</span> |
| brain492                                                                     | 0.3733     | <span class="gr">0.2471</span> | 0.2522                        |

## 這次的加入Huffman Coding 
+ Dictionary 基本上都會是 0~255的機率編碼

| <span style="color:#f28;border:solid,0.5px;padding:5px">compr_rate</span> | RLE    | improved                       | b.w. RLE                       | RLE + Huffan |
| ------------------------------------------------------------------------- | ------ | ------------------------------ | ------------------------------ | ------------ |
| cameraman                                                                 | 1.6903 | 1.1259                         | 0.9772 | 0.955125 + Dict       |
| bollons                                                                   | 1.3303 | 1.1031                         | 0.9945 | 0.840901  + Dict     |
| brain                                                                     | 1.1301 | 0.7682                         | 0.756< |     0.707742 + Dict        |
| brain492                                                                  | 0.3733 | 0.2471 | 0.2522                         |    0.226403 + Dict        |

## 使用固定字典去免去傳輸字典的麻煩




| image\Dict | Lena     | brain492 |
| ---------- | -------- | -------- |
| cameraman  | 1.088086 | NaN      |
| bollons    | 0.896762 | 0.956010 |
| brain      | 0.746880 | 0.791327 |
| brain492   | NaN      | 0.226403 |
| Lena       | 1.004410 | NaN      |
