OpenHarmony啃論文俱樂部—細數生活中的壓縮點滴
【本期看點】
主題：《老子到此一游系列》之 老子游玩了一條河。
- 深度學習助力數據壓縮。
- 貫穿生活的無線傳感器網絡。
- SFFT的前世今生。
【技術DNA】
【智慧場景】
無線傳感器網絡(WSN)
- 說到無線傳感器網絡，大家或許會先自然將其結合自己所熟悉的三個概念進行拆分：無線——傳感器——網絡。無線與網絡這兩個概念大家已經十分熟悉了，把這兩個概念進行組合：無線 + 網絡 = 無線網絡，就是我們“賴以生存”的 WIFI。
- 再介紹傳感器，傳感器就是一種先感再傳的檢測裝置(如樓道里的聲控燈，銀行的感應門等)。“感”，是能感受到被測量的信息;“傳”，是能將感受到的信息，按一定規律變換成為電信號或其他所需形式的信息輸出;“器”，以滿足信息的傳輸、處理、存儲、顯示、記錄和控制等要求的檢測裝置。
背景
目前，我們正處于計算機進化的第三代，稱為普適計算時代。在這個時代，計算機已經開始消失在周圍的物體中，人們甚至可能不知道他們在日常生活活動中與計算機進行交互。支持廣泛存在計算的關鍵技術之一是無線傳感器網絡 (WSN)。
如何構建
無線傳感器網絡 = 傳感器節點 + 無線網絡小微控制器板傳感器
傳感器節點：三個子單元。
- 傳感單元——獲取目標事件/感興趣數據。
- 處理單元——管理采集數據。
- 通信單元——無線電收發器——節點間交換信息。
傳感器節點經過組織形成無線傳感器網絡。簡單來講，就是由諸多傳感器節點組合形成網絡，再利用無線通信技術進行信息綜合處理的一項技術。
建立WNS需解決的三大問題
1、 信息管理體系結構，多傳感器采信時的信息沖突與交互問題
多傳感器系統的運行過程中，必須不斷融合“有用數據”和“不良數據”。然而，好的和壞的數據的簡單組合總是會產生不準確的結果，因為壞數據“污染”了好數據。因此，需要不斷地使用所有可用的信息，不論是外衍或者是系統內生的，并據此在理論框架內對其建模，以此來在運行時中不斷評估和修正來自不同傳感器的觀察數據，并基于其相關性加以利用。
2、 敏感數據加密與密鑰管理
傳感器節點隨機分布，易遭受惡意gong擊。
3、 無線傳感網絡中功耗與功耗管理
傳感網絡中傳感節點由電池供電，數量龐大順序更換充電實踐中不可行。
最關鍵問題：傳感器節點上的無線電收發器是功耗的主要因素。
節能方案
占空比方案——協調定義網絡中節點之間的喚醒和睡眠計劃。
通俗點講：節點996，定時開關機，到點下班回家，關機睡覺
網絡內方案——聚合技術 + 數據壓縮——減少傳輸數據量。
*聚合技術程序。
- 不同傳感器節點——提取數據集(特征，統計信息)——路由(路由器從一個接口上收到數據包)方式組合——轉發匯聚節點。
- 基本組件：路由算法 + 數據聚合 + 數據壓縮/數據表示。
- 路由算法：聚合函數—>提取最值—>匯總數據平均值—>減少密集傳感器網絡中影響功耗的通信數據量。
- 弊端：聚合程度較高時。提取的數據中丟失大部分原始結構，只提供粗略的統計數據，沒有局部變化。
- 解決方案：數據壓縮方案——不需要密集網絡和路由算法——壓縮算法是在每個本地節點上獨立于其他節點執行的——分布式數據壓縮方法 + 本地數據壓縮方法。
*數據壓縮。
- 可滿足需求：減少計算成本和節能。
- 原因：由于無線傳感器節點上的通信單元是主要的電力消耗單元， 因此可以使用一種數據壓縮方案來減少網絡中交換的信息量，從而節省電力。比率越高數據壓縮越好，省電百分比越高。然而，當應用數據壓縮算法時，傳感器節點的處理單元需要更大的功率來運行算法。
*商用傳感器的節點約束。
商用無線傳感器節點的實際應用中，這些節點通常具有體積小、通過一組傳感器、低數據率無線電收發器和小電池來感知環境現象的能力。
*硬件約束。
- 處理約束：著名的無線傳感器節點平臺，配備了 Atmel Atme -ga128L 和 Texas Instruments MSP430 微控制器， 指令內存分別只有 128 和 48 KB。他們的處理時鐘從 4 到 8 兆赫茲不等。
- 解決途徑：在這些約束條件下，有必要為無線傳感器網絡的應用設計一種低復雜度、小編碼的壓縮算法。
傳感器精度誤差。
- 原因：硬件固有噪聲——制造時——規定工作范圍，精度。
- 問題：用戶只明確測量值在誤差范圍內，而不知道誤差的大小和相關的誤差概率。
- 結果：無損數據壓縮算法，確保信息在壓縮過程中的正確性和解壓縮過程，對于商用節點——低效。有損壓縮算法——導致信息丟失——在只允許丟失噪聲的條件下更適合——去噪技術來實現。
- 結論：在某些應用中，如果它們使用的是誤差幅度較大的傳感器，則有必要避免實現無損數據壓縮，而采用帶去噪技術的有損壓縮則更為合理。
應用實例
軍事領域的敵人跟蹤
在軍事領域，由于WSN具有密集型、隨機分布的特點，使其非常適合應用于惡劣的戰場環境。利用WSN能夠實現監測敵軍區域內的兵力和裝備、實時監視戰場狀況、定位目標、監測核gong擊或者生物化學gong擊等。
智能交通中保障安全暢通
在智能交通領域，由于WSN具有密集型、隨機分布的特點，使其非常適合應用于靈活多變的環境。利用WSN能夠實現監測區域內的車輛流量、路燈、交通設施等實時監測。
- 家庭自動化應用中的人類跟蹤。
- 醫療保健應用中的病人監測。
基于深度學習的三維點云幾何壓縮
背景
過去幾年間，人工智能得到了迅猛式發展，深度學習作為人工智能的主流技術，已經成功應用于解決各種二維視覺問題。三維層面上，由于點云表示在計算機視覺、自動駕駛、增強現實(AR)、智慧城市、虛擬現實(VR)等領域有著廣泛的應用，因此，深度學習取代如PCL、Draco等傳統方式處理點云數據，成為當今或未來的必然趨勢。點云數據在自動導航、沉浸傳播等現實生活領域發揮著重要作用，為了應對數據傳輸效率和數據存儲的嚴格要求，需要采用更高壓縮比的相關無損壓縮方案，相關學者提出了在當時2019年可能是第一個基于深度學習的點云壓縮算法。2020年起，逐漸火熱起來，而當下，相關技術已較成熟。
何為“點云”
點云就是某個三維坐標系下一些點(X, Y, Z, Nx, Ny, Nz)的集合，但是這些點并不是普通的點，它包含了豐富的信息，每一個點都會有屬于自己的X、Y、Z坐標及相對應的法向量，因為大量的離散點聚集在一起，放遠了看就像一片片云，所以便稱之為了點云。簡單來看，我們能夠掌握事物的輪廓。通過點的顏色，能夠知道點的稠密，從而得到其他屬性。
那么這些3D點是如何獲取的? 它們主要是由激光雷達等傳感器掃描得到，目的是為了更好地表達位置信息。
畫面中這些看起來像熱成像的東西就是點云數據。
點云生成
點云生成有算法和軟件兩種方式，很多是基于深度學習算法將無人機拍攝的圖像做成3D點云。
點云補全
整體來說類似于GAN和Unet編解碼網絡的感覺，其中，GAN全稱生成對抗網絡，可用于目前比較火熱的換臉等媒體場景，OMGD是相關的前沿壓縮算法。
體素
體素是體積元素(Volume Pixel)的簡稱，是數字數據于三維空間分割上的最小單位，類似于二維平面的像素。就像著名的沙盒游戲 MineCraft 一樣，世界中的很多建筑等都是由 1x1 的小方塊組成的。
同像素一樣，體素本身并不含有空間中位置的數據(即它們的坐標)，然而卻可以從它們相對于其他體素的位置來推敲。
BPP
BPP(bit per pixel) 是評判壓縮算法好壞的重要指標之一，表示每個像素占據的比特位數。從壓縮的目的來看，BPP越小越好。
表示學習
為了提高機器學習的準確率，我們就需要將輸入的信息轉換成有效的特征，這種行為被稱為表示(Representation)。表示學習(Representation Learning)就是一種可以自動地學習出有效特征的算法，并在最終提高了機器學習的性能的一種學習。使用深度學習進行三維點云幾何壓縮要做的事情也就兩項：點云表示學習以及點云數據壓縮。點云表示學習在這里起到了一個預處理的作用，把數據預處理后能夠更方便地壓縮。
點云幾何壓縮
點云是一大堆點，存儲這些點云數據會大量消耗內存，而且不利于傳輸。舉個不是特別恰當的例子，假如未來有一天你正開著無人駕駛車，開的過程中它突然無人駕駛系統突然卡了，那就一失兩命了。有人可能會說我們只要不斷的往車里堆加內存不就行了? 但是車的容量是有限的，堆加這些設備就意味著要增大車的體積或者降低其它部件的體積，而且汽車廠商更要考慮成本。
所以，為了大家都從中獲益，點云壓縮顯得尤為重要
點云壓縮一直是計算機圖形學的一個重要研究方向，包括三種類型：幾何壓縮、屬性壓縮和動態運動補償壓縮，這里研究幾何壓縮。一般而言，體素模型的體、面、邊、點的形狀分布既不規則、也不均衡，其它壓縮技術難以適應它的特點以取得高效的壓縮結果。而幾何壓縮用盡可能少的比特來反應連接信息和幾何信息，并將這些比特順序排列形成比特數據流，然后用數據壓縮方法壓縮這個比特數據流。其傳統的算法主要是PCL和Draco，新興的也就是本文關注的，是基于深度學習的稀疏點云幾何壓縮算法，它比現有的任何壓縮方法都能達到更高的壓縮比，且壓縮損耗可接受。它還提供了三種不同分辨率的輸出，適合不同的場合。但這里，還是將對PCL和Draco做一些簡單介紹：
PCL
PCL全稱Point cloud library(點云庫)，于2011年推出，屬于機器視覺類別，與獲取2D信息并處理的OpenCV類似，它是一個獨立的、大規模的、開放的跨平臺 2D/3D 圖像和點云處理項目，根據BSD許可條款發布，因此可免費用于商業和研究用途。庫中包含很多先進的算法，PCL與機器人操作系統ROS完全集成，并已在機器人領域的各種項目中使用。從0.6版本開始，PCL就已經被移植進Windows，MacOS和Linux，目前的最新版本是1.12.1，Android中也在使用，因此，PCL的應用容易移植和多方發布。另外，PCL的壓縮比可以根據實際需要進行調整。
上圖是對點云數據集進行PCL可視化操作的結果。
Draco
Draco是一個Google的開源庫，于2017年推出，用于壓/解壓縮3D幾何網格和點云，旨在改進3D圖形的存儲和傳輸。Draco專為壓縮效率和速度而設計，該代碼支持壓縮點、連接信息、紋理坐標、顏色信息、法線以及與幾何相關的任何其他通用屬性。使用Draco，3D圖形的應用程序可以顯著縮小，而不會影響視覺保真度。對用戶而言，這意味著應用程序可以更快地下載，瀏覽器中的 3D圖形可以更快地加載，VR和AR場景因此可以用一小部分帶寬傳輸并快速渲染。
Draco算法同時支持有損和無損壓縮，它提供了10種可選的壓縮級別，還可通過減少量化位以支持進一步的有損壓縮。官網Draco 3D Graphics Compression的Demo子頁面中可以在線測試3D渲染性能。
實際上，Draco最初便是由Chrome團隊設計。
Draco開源剛不久，便有網友對其進行了測試復現：
可以看到，編碼之后，點云文件大小從原本的3mb顯著減小到了110kb，但此時的文件是不能夠被正常可視化的，只能用來傳輸存儲，所以我們需要對其再進行解碼。解碼之后為431kb，其實也并沒有再大多少，但是我們注意下方的編碼前后點云圖像質量比較，發現二者從肉眼上幾乎分辨不出差別，而點云數目也沒有發生變化，都是35947 data points。
可見，Draco的編碼效率十分強悍。
基于深度學習的壓縮
學者設計了一種新的基于深度學習的稀疏點云幾何壓縮方案，能夠達到比現有的任何壓縮算法都更高的壓縮比，且壓縮損耗可接受。另外，它提供了三種不同分辨率的輸出，適應于不同場合;基于矩陣運算，支持GPU對多個模型并行壓縮，大大提高處理效率。
算法測試
ShapeNet數據集是一個稀疏的點云數據集，不常用于點云壓縮任務。但是，稀疏點云可以用來測試壓縮算法，原因是它們比密集點云更難壓縮，因此更能體現算法效率。稀疏點云用更少的點代表形狀或表面，比密集點云包含更少的冗余信息。
為了比較稀疏點云壓縮和密集點云壓縮在簡化Stanford bunny(斯坦福兔子)點云時采樣的2048和35947個點的差異，使用PCL和Draco對兩個模型壓縮，得到下圖結果。bpp指每點壓縮數據的比特數，損耗由RMS計算以減小計算量：
結果表明，稀疏點云壓縮往往比密集點云壓縮更難達到高壓縮比及低重構損失。
為了清晰顯示算法訓練過程，學者選擇了幾個模型，并在不同迭代次數下重構點云，模型細節逐漸出現：
編碼的最后一層稱為瓶頸層，瓶頸層的維數和碼字中每個浮點數所占位數是影響壓縮結果的兩個關鍵因素。
將基于深度學習使用"PointNet++、TensorFlow"等技術的壓縮算法與PCL和Draco在最終條件下進行比較，Ours-16和Ours-32分別表示用16位和32位表示單個值的方式，討論壓縮比、重構損失、計算量等一系列參數。結果表明，基于深度學習的新算法有著比Draco高10倍、甚至比PCL高110倍的壓縮比，同時保證了較小的重構損失。
但是，有優點必有缺點。PCL和Draco更快、更節省內存。原因是PCL和Draco都是基于C的，比基于Python的新算法要更高效，解決辦法可以是用C程序簡化網絡，替換TensorFlow中的更多操作，從而提高效率、減小內存負載。
總結
本文提出的基于深度學習的三維點云壓縮新方法，是第一個基于深度學習的點云幾何壓縮算法。由于其并行處理能力和較高的壓縮比，在保持可接受的損耗的情況下，顯示了巨大的潛力。實驗表明，在高壓縮比條件下，該算法的性能優于 PCL 和 Draco。該算法的關鍵是具有分層結構的自動編碼器，其性能優于目前的重建質量，特別是在局部細節上。毫無疑問，深度學習是數據壓縮未來的發展方向。
基于稀疏快速傅里葉變換(SFFT)的語音壓縮算法
SFFT的前世今生
1876 年 Bell 發明創造了電話，用聲電-電聲轉換方式實現了人類有史以來第一次的遠距離語音傳輸，開啟了現代語音信號處理的研究。
1928年奈奎斯特(Nyquist)就推導出在理想低通信道的最高碼元傳輸速率的公式。
2012 年由麻省理工學院(Massachusetts Institute of Technology，MIT)Haitham Hassanieh 等四位研究員提出的一種新的信號處理算法，稀疏快速傅里葉變換(Sparse Fast Fourier Transform，SFFT) 。該算法通過利用信號頻域的稀疏特性，以與信號長度成亞線性關系的時間復雜度和較高的概率重構出信號的完整頻譜，其效率是傳統快速傅里葉變換(Fast Fourier Transform，FFT)算法的 10～100 倍。為此，麻省理工學院專門建立了研究 SFFT 的相關網站，并發表了多篇相關論文。
應用場景
語言交流是人類最基本的能力之一，是人類長期進化形成的特有的思維和交流形式。語言是概況總結的規律性的符號系統，是創造和記錄人類文明的根本方式。
語音作為語言的聲學表現形式，是音與義的結合體，是最方便有效的信息傳遞和交換形式。語音和語言是人類思維的一種依托，它與所生存的社會、文化密切相關，擁有最大的信息含量及最高的智慧水平。
語音信號的數字化處理已成為數字化時代下通信網絡里最重要的一部分，數字語音信號的傳輸、合成、存儲、增強、識別等已經有了比較成熟的技術，語音壓縮算法在此基礎之上擁有了蓬勃發展的機會。
語音信號處理技術的應用包括工業、軍事、交通、醫學、民用等多種領域，市場上已有大量的語音相關產品，語音信號方向的科研及應用擁有極為廣闊的市場需求及應用場景。
語音信號壓縮面臨的問題
傳統的信號離散化基本依據為奈奎斯特(Nyquist)采樣定理，指出當采樣頻率 f 大于信號最高頻率的 2 倍時，采樣后的數字信號完整地保留了原信號中的信息，而在實際應用中往往需要 5～10 倍才能達到理想的效果。這給信息處理帶來了巨大壓力：其一，需要提高采樣頻率來完成超寬帶信號的信息采集，硬件要求高、設備昂貴、難于實現;其二，采樣信息龐大，需要的更多的存儲介質。
在隨著移動互聯網等的快速發展，語音業務也大幅增加，用傳統奈奎斯特采樣將會獲得龐大的采樣數據，這給信號的傳輸和存儲帶來了巨大壓力。而此時，如何有效降低傳輸和存儲所需的數據量成為了緩解硬件設備的壓力，降低時延，提高信息傳輸的整體效率的關鍵問題。
關鍵技術
MIT提出的**稀疏快速傅里葉變換(SFFT)**技術將語音信號內的冗余部分找到，并且在保持可接受失真的情況下盡可能多的將冗余部分刪除，使用較少的比特數表示原始信號。最后，利用這些較少的比特數，通過反變換算法將語音信號以高概率重構出來。
簡而言之，利用信號頻域具有稀疏性的特點，抽取有用特征點，去除無用信號， 減少信號變換過程中的運算時間和存儲單元，達到壓縮數據的效果。
理論架構
SFFT 算法大致可以分為三個步驟：
1. “分筐”
首先將長度為 N 的信號頻率系數按規律 H 投入 B 個“筐”中，即分筐：
很明顯，在分筐的過程中數據量下降了。
2. FFT降采樣
對分筐后的信號進行降采樣 FFT。
3. 重構信號
最后依據分筐時的各種參數設計出重構算法，以高概率重構出大頻率系數的位置和幅值，得到重構信號的頻譜。
根據上面的分析可以得到如下 SFFT 的理論框架框圖：
總結
- 所謂分筐即抽取有用特征點，去除無用信號。
- 降采樣，即是采樣點數減少的FFT。
- 重構，即重構出大頻率系數的位置和幅值，得到重構信號的頻譜，即還原出音頻信號。
- 我們發現分筐與降采樣的過程抽取出了有用信號，去除了無用信號，從而大幅度壓縮了數據量，從而實現了緩解硬件設備的壓力，降低時延，提高信息傳輸的整體效率的目的。
算法評估
1、 分筐效果
頻域效果分析：
時域效果分析：
可以看出頻域與時域信號明顯密集化。
2、 重構信號與原信號對比
可以看出信號高度相似，差異很小。
綜上，采用高效的 SFFT 算法對其語音信號進行壓縮處理，在接收端通過高概率重構得到原始信號的近似信號。在語音信號傳輸前通過有效的壓縮方法剪去信號內部的冗余部分，利用較少的數據量便可以完成信號的高效傳輸。
其他應用場景
醫學成像大多數的醫學圖像具有稀疏特性，將 SFFT 運用在 2D 相關振動光譜技術成像中， 降低了掃描時間、減少了截斷偽影。
頻譜感知由于對 GHz 帶寬的信號檢測會帶來超高的采樣頻率并獲得海量采樣數據，給硬件設備提出了巨大的挑戰。采用混疊同余類似方法，無需全帶采樣實現信號的頻譜計算，高效減少檢測時間和降低能耗。
GPS 導航在衛星傳輸過程中通常使用偽隨機前導碼來實現同步，存在較大的時延。基于前導碼良好的自相關性，使用 SFFT 技術加快了 GPS 的同步處理能力。
語音信號處理，埃及-日本科學技術大學的研究人員在語音信號處理中采用了基于 SFFT 算法的處理方法。
在國內，SFFT 算法還處在研究的起步階段，在水聲快速解調算法、寬帶頻譜感知、直接序列擴頻信號的捕獲、計算外輻射源雷達互模糊函數等做了一定的研究。綜上不難發現，該算法擁有廣闊的應用前景。
