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