# 影像處理專題 資料
{%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:

## 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
+ 就是儲存
### 圖解
#### 壓縮








#### 解壓縮







[圖解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 比較壓縮率 以及展示


+ 因為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 數組),其中新數組的大小小於原始圖像的大小。

## 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)

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)

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>

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>

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>

~~暫時卡住~~ <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>


## 分析
+ 壓縮比分析:
*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
```

## Burrows-Wheeler變換
Burrows–Wheeler Transform(簡稱BWT,也稱作塊排序壓縮)
當一個字符串用該算法轉換時,算法只改變這個字符串中字符的順序而並不改變其字符
如果原字符串有幾個出現多次的子串,那麼轉換過的字符串上就會有一些連續重複的字符
這對壓縮是很有用的。
該方法能使得基於處理字符串中連續重複字符的技術(如MTF變換和RLE)的編碼更容易被壓縮。
### Examle:






```=
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
```

### 問題
對於"文字"的作用比較大,舉例來說"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
```


:::
:::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;
```

| <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 |