唐 堂，徐光輝，劉銘哲
（中國人民解放軍陸軍工程大學(xué)，江蘇 南京 210001）
0 引言
點(diǎn)云是三維空間中一組離散坐標(biāo)點(diǎn)的集合，其中每個(gè)點(diǎn)除包含自身所在空間位置的三維坐標(biāo)信息外，通常還包含顏色、激光反射強(qiáng)度等屬性信息。點(diǎn)云數(shù)據(jù)的獲取方式可分為直接和間接兩種[1]，直接方式通常采用距離傳感器如激光雷達(dá)、深度相機(jī)等，通過主動(dòng)發(fā)射電磁波并接收回波，獲取相應(yīng)反射點(diǎn)的坐標(biāo)，從而獲得場景內(nèi)物體的幾何信息，結(jié)合圖像采集設(shè)備可以獲取對應(yīng)的顏色等屬性信息；間接方式則是通過計(jì)算或者采樣從其他形式的數(shù)據(jù)中獲取點(diǎn)云，比如雙目相機(jī)結(jié)合運(yùn)動(dòng)信息進(jìn)行三維重建等。其中激光雷達(dá)因?yàn)榫哂胁杉杆佟Ⅻc(diǎn)云密集、精確度高的特點(diǎn)[2]，成為目前最常用的點(diǎn)云采集設(shè)備。
點(diǎn)云數(shù)據(jù)信息量豐富，三維場景表現(xiàn)能力出色，在場景建模、虛擬現(xiàn)實(shí)、環(huán)境測繪、自動(dòng)駕駛等領(lǐng)域應(yīng)用廣泛，前景廣闊。但是，作為一種高維度的信息，密集的點(diǎn)云不可避免地存在著數(shù)據(jù)量龐大的問題。以Velodyne HDL-64S2 型激光雷達(dá)為例，當(dāng)其以10Hz 的頻率采集數(shù)據(jù)時(shí)，連續(xù)運(yùn)行一小時(shí)將產(chǎn)生超過100GB 的數(shù)據(jù)[3]。雖然快速發(fā)展的通信及存儲(chǔ)技術(shù)在一定程度上緩解了點(diǎn)云數(shù)據(jù)量龐大帶來的挑戰(zhàn)，但是在一些分布式、低成本、實(shí)時(shí)性要求高的場景下，龐大的數(shù)據(jù)量仍然是制約點(diǎn)云應(yīng)用和發(fā)展的瓶頸。因此，研究如何壓縮點(diǎn)云數(shù)據(jù)，對其在更多場景下的應(yīng)用具有重要意義。
點(diǎn)云壓縮算法跟點(diǎn)云獲取方式及其對應(yīng)場景密切相關(guān)。針對激光雷達(dá)點(diǎn)云，運(yùn)動(dòng)圖像專家組（Moving Pictures Experts Group，MPEG）最先公布的點(diǎn)云壓縮方案L-PCC[4]中使用的是基于八叉樹的幾何編碼。通過八叉樹將目標(biāo)區(qū)域迭代劃分為精細(xì)立方體，以樹的形式遍歷訪問目標(biāo)立方體所在空間，從而實(shí)現(xiàn)空間編碼。而在之后公布的G-PCC 方案中[5]，引入了一種一維遍歷的預(yù)測幾何編碼方法，其基本思想是利用點(diǎn)云中點(diǎn)與點(diǎn)基于幾何距離的領(lǐng)域關(guān)系，構(gòu)建一種預(yù)測樹，樹中每個(gè)節(jié)點(diǎn)的位置信息都可以從其父節(jié)點(diǎn)或其祖父節(jié)點(diǎn)推斷出來，編碼預(yù)測節(jié)點(diǎn)和其相關(guān)聯(lián)的實(shí)際點(diǎn)的殘差，從而降低點(diǎn)云幾何信息的冗余。Tu 等人結(jié)合激光雷達(dá)旋轉(zhuǎn)掃描獲取點(diǎn)云的特點(diǎn)，將激光雷達(dá)原始數(shù)據(jù)轉(zhuǎn)化為距離圖，對距離圖序列使用JPEG 進(jìn)行壓縮，從而間接實(shí)現(xiàn)了點(diǎn)云的壓縮。此外，結(jié)合場景語義信息來進(jìn)行點(diǎn)云數(shù)據(jù)壓縮也取得了不錯(cuò)的效果[6]。不同于以上算法，F(xiàn)eng 等人[7]利用了單幀點(diǎn)云中含有大量近似平面以及相鄰點(diǎn)云幀中存在大量重復(fù)場景的特點(diǎn)，通過平面擬合的方式實(shí)現(xiàn)了點(diǎn)云數(shù)據(jù)的實(shí)時(shí)壓縮，該方法在算法復(fù)雜度、壓縮率、場景應(yīng)用精度上的綜合表現(xiàn)更為優(yōu)異。
本文在Feng 等人的基礎(chǔ)上提出了使用預(yù)測殘差處理未擬合點(diǎn)距離的方案，解決了其在復(fù)雜場景平面信息少或是平面擬合精度要求高導(dǎo)致的非擬合點(diǎn)過多，占據(jù)大量編碼空間的問題，能夠在同等誤差精度條件下，取得比原算法更好的壓縮效果。
1 編解碼框架介紹
本文設(shè)計(jì)的基于平面擬合及殘差預(yù)測的編解碼框架如圖1 所示，它由編碼端和解碼端兩部分構(gòu)成。編碼端首先將三維點(diǎn)云降維轉(zhuǎn)換為二維距離圖，轉(zhuǎn)換方法是根據(jù)點(diǎn)云中點(diǎn)的坐標(biāo)位置，計(jì)算其相對于原點(diǎn)的旋轉(zhuǎn)角、俯仰角以及直線距離，根據(jù)激光雷達(dá)角度分辨率對旋轉(zhuǎn)角和俯仰角進(jìn)行量化，量化值分別作為二維距離圖中像素位置的列索引和行索引，直線距離則作為該像素的像素值，如此點(diǎn)云中的每個(gè)點(diǎn)便可以投射到二維距離圖中的某個(gè)像素上。降維轉(zhuǎn)換可以將無序的點(diǎn)云轉(zhuǎn)換為有序的二維圖，同時(shí)可以最大限度地保留點(diǎn)云中點(diǎn)的相關(guān)性，為后續(xù)的平面擬合及殘差預(yù)測奠定基礎(chǔ)。此過程中生成的二維占位圖與距離圖具有同等尺寸，像素值用單個(gè)比特1 或0 編碼，指示距離圖對應(yīng)的像素上是否存在點(diǎn)云投射點(diǎn)，用于解碼過程。在二維圖的基礎(chǔ)上，以固定數(shù)量的像素拼接的像素塊為單位，進(jìn)行平面擬合，由可以擬合的像素提取得到相應(yīng)的平面參數(shù)，不能擬合的像素則進(jìn)行預(yù)測編碼，得到相應(yīng)的預(yù)測值、殘差值和孤立值。擬合的過程中產(chǎn)生相關(guān)的索引值用來區(qū)分可擬合像素塊、可預(yù)測像素塊及孤立像素塊。最后對平面參數(shù)、索引、預(yù)測、殘差、孤立值及占位圖進(jìn)行熵編碼，產(chǎn)生可以保存或傳輸?shù)亩M(jìn)制碼流。解碼端解碼提取相應(yīng)數(shù)據(jù)，根據(jù)相關(guān)參數(shù)及索引對空白距離圖進(jìn)行像素值填充，最后進(jìn)行升維轉(zhuǎn)換，恢復(fù)得到原始點(diǎn)云數(shù)據(jù)。編解碼過程中數(shù)據(jù)形式轉(zhuǎn)換如圖2 所示。
圖1 平面擬合及殘差預(yù)測編解碼框架
圖2 編解碼過程數(shù)據(jù)形式轉(zhuǎn)換
2 平面擬合及殘差預(yù)測
2.1 平面擬合
平面擬合的基本思想是使用空間平面去擬合空間中孤立的點(diǎn)，當(dāng)空間中某一區(qū)域的點(diǎn)共面時(shí)，就可以用該擬合平面去間接表示所有位于該平面上的點(diǎn)，從而實(shí)現(xiàn)減少保存的數(shù)據(jù)量的目的。常用的車載激光雷達(dá)采集數(shù)據(jù)示例如圖3 所示：位于移動(dòng)載具上的激光雷達(dá)發(fā)出短脈沖激光束，當(dāng)激光束照射到目標(biāo)物體上時(shí)，會(huì)被部分反射回來，激光雷達(dá)接收到反射回來的激光脈沖信號，并測量信號的時(shí)間差以計(jì)算距離。利用多次測量可以獲取目標(biāo)物體在三維空間中的坐標(biāo)。實(shí)際場景中存在大量共面的點(diǎn)，比如平整的墻壁、汽車部分表面以及平坦的路面，即使有些宏觀上看起來并不規(guī)則的物體，也可以用一系列微小的平面去近似拼接表示�；谶@一特征，激光雷達(dá)采集到的點(diǎn)云中實(shí)際存在大量共面的點(diǎn)，因此可以使用平面擬合來降低點(diǎn)云的信息 冗余。
圖3 激光雷達(dá)采集數(shù)據(jù)示例及點(diǎn)云局部放大
使用空間平面去擬合空間中共面的點(diǎn)，其實(shí)就是根據(jù)給定的點(diǎn)確定一組平面參數(shù)，使得所有目標(biāo)點(diǎn)距離該平面的距離都在允許的誤差范圍內(nèi)。為此，可以使用最小二乘法得到相應(yīng)的平面參數(shù)。其基本思想是通過最小化誤差的平方和來尋找數(shù)據(jù)的最佳匹配函數(shù)。假設(shè)有n個(gè)待擬合的三維坐標(biāo)點(diǎn)(xi,yi,zi)，i=1,2,3,…,n。當(dāng)平面不過原點(diǎn)時(shí)，平面方程可以表示為：
對于平面擬合來說，誤差最小就是將待擬合的點(diǎn)帶入式（1）后，等式右邊取值盡可能接近0，因此可以得到以下目標(biāo)函數(shù)：
為使式（2）最小，需要對a,b,c分別求偏導(dǎo)數(shù)，使得：
具體編碼是在降維轉(zhuǎn)換后形成的二維距離圖的基礎(chǔ)上進(jìn)行的。將二維距離圖按照固定個(gè)數(shù)的像素點(diǎn)進(jìn)行分塊，因?yàn)榻稻S操作的過程保留了相鄰位置點(diǎn)的領(lǐng)域關(guān)系，因此同一塊內(nèi)的像素點(diǎn)所對應(yīng)的點(diǎn)云中點(diǎn)的分布也具有領(lǐng)域關(guān)系。對塊內(nèi)的像素點(diǎn)使用上述方法進(jìn)行平面擬合，得到一個(gè)擬合平面，之后判斷該塊內(nèi)的所有像素點(diǎn)到擬合平面的歐式距離是否小于某一設(shè)定閾值。當(dāng)所有點(diǎn)的誤差都在閾值范圍內(nèi)時(shí)，即認(rèn)為該像素塊可以被平面擬合，平面的參數(shù)隨即確定，通過保存該擬合平面的參數(shù)來替代保存該像素塊內(nèi)的像素點(diǎn)，因?yàn)橹恍枰４? 個(gè)參數(shù)，而像素塊內(nèi)的像素點(diǎn)的數(shù)量是超過3 的，所以能夠?qū)崿F(xiàn)減少數(shù)據(jù)量的目的。當(dāng)像素塊內(nèi)存在點(diǎn)到擬合平面的距離超過閾值時(shí)，則說明無法擬合出滿足要求的平面，認(rèn)為該像素塊內(nèi)的像素不在同一平面內(nèi)，需要進(jìn)行殘差預(yù)測或者獨(dú)立編碼。
在解碼端，當(dāng)解碼的像素塊被平面擬合編碼時(shí)，根據(jù)激光雷達(dá)采集點(diǎn)云的原理，只需要知道激光的入射角度、擬合平面參數(shù)以及該位置是否存在投射點(diǎn)，即可恢復(fù)出該點(diǎn)的空間坐標(biāo)位置。激光的入射角度已經(jīng)被編碼在二維距離圖的橫縱坐標(biāo)索引里，對應(yīng)的像素點(diǎn)是否被點(diǎn)云投射可以根據(jù)二維占位圖獲取。
2.2 殘差預(yù)測
平面擬合主要利用的是點(diǎn)云中存在共面的點(diǎn)這一特點(diǎn)，通過平面來替代該面上的一個(gè)個(gè)孤立的點(diǎn)，從而降低信息冗余。當(dāng)場景比較簡潔、規(guī)整時(shí)，比如城市道路、橋梁隧道環(huán)境下，激光雷達(dá)采集到的點(diǎn)云存在大量共面的點(diǎn)，平面擬合壓縮效果顯著。但是當(dāng)場景信息復(fù)雜時(shí)，比如灌木林立的郊區(qū)道路環(huán)境，點(diǎn)云中不共面的點(diǎn)較多，需要被單獨(dú)編碼，壓縮性能降低。圖4 展示了激光雷達(dá)采集數(shù)據(jù)的兩種不同場景：場景1 是隧道環(huán)境，存在較多平面目標(biāo)物；場景2是郊區(qū)道路環(huán)境，雖然存在平整的路面，但是道路兩邊有茂密的樹木，幾乎無法用平面進(jìn)行擬合。
圖4 激光雷達(dá)采集數(shù)據(jù)場景
對兩種場景下采集的激光雷達(dá)數(shù)據(jù)使用相同的參數(shù)進(jìn)行平面擬合壓縮處理，表1 統(tǒng)計(jì)了兩種場景點(diǎn)云壓縮相關(guān)數(shù)據(jù)。
表1 兩種場景平面擬合壓縮數(shù)據(jù)統(tǒng)計(jì)
從表1 可以看出，在相同壓縮參數(shù)下，不同場景采集到的點(diǎn)云中，不能被平面擬合的點(diǎn)數(shù)存在較大差異，并且非擬合點(diǎn)的占比對壓縮效果有較大影響。因此，如果能夠?qū)Ψ菙M合點(diǎn)進(jìn)行一定的處理，而不是直接保存其距離值，將會(huì)提升點(diǎn)云壓縮的效果。
對于降維轉(zhuǎn)換后的二維距離圖來說，像素點(diǎn)上的距離值實(shí)際上是激光雷達(dá)到場景地物反射點(diǎn)的距離，同一場景地物的多個(gè)反射點(diǎn)到激光雷達(dá)的距離應(yīng)該是相近的，而二維距離圖保存了空間中反射點(diǎn)之間的領(lǐng)域關(guān)系，因此二維距離圖上相近區(qū)域的幾個(gè)像素值即使不能被平面擬合，也應(yīng)該存在一定的近似關(guān)系。對場景2 采集到的激光雷達(dá)點(diǎn)云進(jìn)行降維轉(zhuǎn)換后，對其中不能被平面擬合的像素塊進(jìn)行抽樣，共抽樣5 次，每次抽取連續(xù)的10 個(gè)非擬合像素塊，統(tǒng)計(jì)抽取的像素塊內(nèi)所含的像素值分布情況，如圖5 所示。
圖5 非平面點(diǎn)連續(xù)區(qū)域像素值分布統(tǒng)計(jì)
從圖5 可以看出，非擬合點(diǎn)雖然不能被平面擬合，但是像素值的分布較為集中。殘差預(yù)測編碼正是利用此特點(diǎn)，對非擬合點(diǎn)進(jìn)行處理，從而減少信息冗余。
殘差預(yù)測同樣是以像素塊為單位，對每個(gè)像素塊內(nèi)的像素值進(jìn)行操作。在降維轉(zhuǎn)換、平面擬合編碼的基礎(chǔ)上，針對不能被平面擬合的像素塊，首先判斷該像素塊內(nèi)的像素值是否可以被預(yù)測編碼，即像素值分布是否集中在一個(gè)預(yù)先設(shè)定的較小閾值范圍內(nèi)，如果像素值分布滿足條件，則以其中最小的值作為該像素塊所有像素的預(yù)測值，塊內(nèi)其余像素值與該預(yù)測值相減作為殘差值保留；如果像素值分布不滿足條件，即該塊內(nèi)的像素值差異過大，則無法進(jìn)行預(yù)測編碼，需要將其作為孤立像素塊，單獨(dú)進(jìn)行編碼。之后對下一個(gè)不能擬合像素塊進(jìn)行預(yù)測編碼的判斷，該像素塊的判斷需要參考前一個(gè)像素塊的編碼情況，如果前一個(gè)像素塊是可以被預(yù)測編碼的，則首先判斷當(dāng)前像素塊是否也在前一個(gè)像素塊預(yù)測編碼的范圍內(nèi)，如果是，則利用前一個(gè)像素塊的預(yù)測值進(jìn)行殘差預(yù)測編碼，如果不在前一個(gè)像素塊的預(yù)測范圍內(nèi)，則判斷當(dāng)前像素塊是否能夠被獨(dú)立預(yù)測編碼，如果可以，則重新確定預(yù)測值并在此基礎(chǔ)上計(jì)算殘差，如果不行，則作為孤立像素塊單獨(dú)編碼。經(jīng)過預(yù)測編碼后，所有非平面編碼的像素值均可由孤立值、預(yù)測值和殘差值所確定。
判斷是否可以預(yù)測編碼的閾值對預(yù)測編碼效果有著顯著影響，當(dāng)閾值設(shè)置較大時(shí)，可被預(yù)測編碼的像素塊數(shù)量就會(huì)增多，預(yù)測范圍廣，編碼效果好，但是受到編碼殘差比特?cái)?shù)的影響，量化誤差會(huì)增大，最終會(huì)增加點(diǎn)云的信息損失。因此在實(shí)際使用中，預(yù)測判別閾值通常根據(jù)壓縮需求和點(diǎn)云失真情況來確定。
為了直觀地看到殘差預(yù)測的處理效果，選取4種不同場景采集到的單幀點(diǎn)云數(shù)據(jù)，分別使用平面擬合和平面擬合加殘差預(yù)測進(jìn)行壓縮，統(tǒng)計(jì)兩種壓縮方法中的非擬合點(diǎn)數(shù)據(jù)量，結(jié)果如表2 所示。
表2 殘差預(yù)測處理前后非擬合點(diǎn)數(shù)據(jù)量統(tǒng)計(jì)
從表2 可以看出，經(jīng)過殘差預(yù)測處理后，非擬合點(diǎn)的數(shù)據(jù)量顯著減少，殘差預(yù)測能夠在原平面擬合算法的基礎(chǔ)上帶來壓縮性能的提升。
3 壓縮性能分析
3.1 實(shí)驗(yàn)環(huán)境和評價(jià)指標(biāo)
實(shí)驗(yàn)在Windows 10 系統(tǒng)上完成，電腦配置是Intel Core i5-11300H @ 3.10 GHz，16 GB 運(yùn)行內(nèi)存。實(shí)驗(yàn)采用KITTI 數(shù)據(jù)集，該數(shù)據(jù)集包含數(shù)百個(gè)行駛場景的錄制視頻序列、激光雷達(dá)數(shù)據(jù)和圖像數(shù)據(jù)，被廣泛用于自動(dòng)駕駛和計(jì)算機(jī)視覺領(lǐng)域。其中的激光雷達(dá)數(shù)據(jù)主要是通過搭載的Velodyne HDL-64E 傳感器采集，該傳感器擁有64 個(gè)激光發(fā)射器和接收器，每秒鐘可以生成高達(dá)100萬個(gè)測量點(diǎn)，配合旋轉(zhuǎn)支架，可以在水平平面上捕捉高密度的3D 點(diǎn)云信息。
使用編碼每個(gè)點(diǎn)所用的比特?cái)?shù)（bpp）表示點(diǎn)云壓縮程度，其計(jì)算公式為：
式中：Size(P)表示點(diǎn)云的數(shù)據(jù)量，單位為bit；N(P)表示點(diǎn)云中點(diǎn)的總數(shù)。例如：原始點(diǎn)云編碼每個(gè)點(diǎn)的坐標(biāo)需要使用96 bit 數(shù)據(jù)，則原始點(diǎn)云的bpp就是96，壓縮后的點(diǎn)云bpp則是以壓縮包的數(shù)據(jù)量除以原始點(diǎn)云中點(diǎn)的個(gè)數(shù)得到，因此bpp越小表示壓縮后的數(shù)據(jù)量越小，壓縮程度越大。
因?yàn)槭怯袚p壓縮，所以還需要評估壓縮后信息的損失情況。本文使用兩種方法對信息損失進(jìn)行量化評估。第一種方法是對稱最近鄰均方根誤差，該指標(biāo)是直接比較解壓重建后的點(diǎn)云與原始點(diǎn)云的位置差異，通過計(jì)算所有點(diǎn)的位置偏移均值來量化壓縮導(dǎo)致的點(diǎn)云幾何失真[8]。具體的計(jì)算方法為：對于原始點(diǎn)云P中的每一個(gè)點(diǎn)p，通過最近鄰算法在解壓重建的點(diǎn)云Q中找到其對應(yīng)的點(diǎn)q，P相對于Q的誤差為：
除了比較原始點(diǎn)云和重建點(diǎn)云之間的幾何誤差，本文還從點(diǎn)云應(yīng)用的角度對信息損失進(jìn)行評估。位姿估計(jì)是點(diǎn)云的一種常見應(yīng)用，它是指從傳感器數(shù)據(jù)中估計(jì)物體或相機(jī)相對于參考坐標(biāo)系的位置和方向信息，在計(jì)算機(jī)視覺、機(jī)器人及自動(dòng)駕駛等領(lǐng)域使用廣泛。本文使用激光雷達(dá)里程計(jì)建圖（Lidar Odometry and Mapping，LOAM）算法[9]，基于同一段序列，對經(jīng)過不同程度壓縮解壓后的點(diǎn)云進(jìn)行位姿估計(jì)，通過比較位姿估計(jì)的誤差來衡量壓縮算法對點(diǎn)云應(yīng)用造成的影響。
3.2 實(shí)驗(yàn)結(jié)果與分析
本次實(shí)驗(yàn)與基于平面擬合、八叉樹[10]及JPEG[3]的點(diǎn)云壓縮方法進(jìn)行對比。針對直接信息損失比較，使用KITTI 數(shù)據(jù)集中不同場景共10 幀激光雷達(dá)點(diǎn)云作為壓縮處理對象。圖6 是本文算法與其他3 種算法在不同壓縮程度下，幾何信息損失的情況。從圖中可以看出，隨著壓縮程度加大，4 種算法都表現(xiàn)出了信息損失增加的情況；在同等誤差條件下，本文提出算法的bpp最小，表明壓縮性能最好。
圖6 不同點(diǎn)云壓縮方法失真情況比較
針對位姿估計(jì)應(yīng)用評價(jià)，使用KITTI 數(shù)據(jù)集中一段30 秒內(nèi)連續(xù)采集的激光雷達(dá)點(diǎn)云序列作為壓縮處理對象。采用不同的壓縮算法對該序列進(jìn)行不同程度的壓縮解壓后，使用a-loam 算法進(jìn)行位姿估計(jì)，結(jié)果如圖7 所示。從圖中可以看出，在同等位姿估計(jì)誤差情況下，本文提出的算法能將該段序列點(diǎn)云數(shù)據(jù)量壓縮至最小。
圖7 不同壓縮算法位姿估計(jì)精度比較
4 結(jié)語
本文針對激光雷達(dá)點(diǎn)云壓縮，在平面擬合算法的基礎(chǔ)上，對非平面擬合點(diǎn)進(jìn)行殘差預(yù)測處理，有效改善了高擬合精度和復(fù)雜場景下平面擬合壓縮性能下降的情況。從直接信息損失和應(yīng)用精度兩個(gè)方面比較了不同壓縮率情況下，壓縮導(dǎo)致的點(diǎn)云失真情況。結(jié)果表明，本文算法較八叉樹壓縮和基于JPEG 的壓縮有較大提升，優(yōu)于之前的基于平面擬合的壓縮算法。
