計算機視覺三維測量與建模 課件 第5、6章 雙目立體視覺、點云濾波與分割

第五章計算機視覺三維測量與建模雙目立體視覺南京航空航天大學(xué)研究生教育教學(xué)改革專項（優(yōu)質(zhì)教學(xué)資源建設(shè)）項目資助01標(biāo)準(zhǔn)形式的雙目系統(tǒng)】9如果已知一對攝影機的內(nèi)參數(shù)，就可以通過畸變校正算法，去除影像的幾何畸變影響。然后利用對極幾何關(guān)系，對兩幅影像進行極線校正，得到標(biāo)準(zhǔn)形式的二視圖關(guān)系，即極線方向與影像的行掃描線方向平行。接下來就能夠用立體匹配算法進行密集像素匹配，標(biāo)準(zhǔn)立體匹配流程圖如圖5.1所示。標(biāo)準(zhǔn)形式的雙目系統(tǒng)02匹配基礎(chǔ)給定兩幅影像，本章分別約定為參考影像（左影像）工和目標(biāo)影像（右影像），立體匹配的目標(biāo)是找到工，中的像素在中的同名點對應(yīng)。極線校正的一種簡單表示方法是將兩個像空間坐標(biāo)系旋轉(zhuǎn)，使它們的光軸平行，且垂直于光心連線，如圖5.3所示。極線校正之后，兩幅影像上的視差只發(fā)生在x方向上，在y方向上沒有視差。由此將兩幅影像的同名點匹配搜索過程從二維像空間縮減到了一維空間上，從而提高匹配的準(zhǔn)確性和計算速度。匹配基礎(chǔ)常用的立體影像極線校正的方法是采用的Bouguet算法，該算法已經(jīng)被集成到OpenCV庫中，可以方便地調(diào)用它來完成二視圖的極線校正。Bouguet算法是將求解出來的旋轉(zhuǎn)矩陣R分解成左、右攝像機各旋轉(zhuǎn)一半的旋轉(zhuǎn)矩陣。分解的原則是使得左、右影像重投影造成的畸變最小，左、右視圖的共同面積最大，主要步驟如下。將右影像平面相對于左影像平面的旋轉(zhuǎn)矩陣分解成兩個矩陣民和R，叫作左、右攝像機的合成旋轉(zhuǎn)矩陣。匹配基礎(chǔ)將左、右攝像機各旋轉(zhuǎn)一半，使得左、右攝像機的光軸平行。此時左、右攝像機的成像面平行，但是基線與像平面不平行。構(gòu)造變換矩陣Rrect使得基線與像平面平行。構(gòu)造的方法是通過右攝像機相對于左攝像機的偏移矩陣t來完成的。匹配基礎(chǔ)通過合成旋轉(zhuǎn)矩陣與變換矩陣相乘獲得左、右攝像機的整體旋轉(zhuǎn)矩陣。左、右攝像機坐標(biāo)系乘以各自的整體旋轉(zhuǎn)矩陣就可使得左、右攝像機的主光軸平行，且像平面與基線平行。通過上述的兩個整體旋轉(zhuǎn)矩陣，就能夠得到理想的平行配置的雙目立體影像。校正后根據(jù)需要對影像進行裁剪，需重新選擇一個影像中心和影像邊緣，從而讓左、右疊加部分最大。匹配基礎(chǔ)通常影像數(shù)據(jù)在采集時刻會存在高頻噪聲的影晌，通過一個高斯卷積可以明顯改善噪聲的影響。因此在匹配之前進行匹配預(yù)處理十分必要。設(shè)一幀二維影像為f0(x,y)，預(yù)處理過程就是為獲得新的影像匹配基礎(chǔ)視差圖（DisparityMap）和深度圖（DepthMap）是在立體匹配基礎(chǔ)上得到的一組反眏空間二維和三維對應(yīng)關(guān)系的二維圖像。如圖5.6所示，影像上像素位置的視差值對應(yīng)著空間結(jié)構(gòu)到成像光心連線（沿垂直于像平面的方向）的距離，即深度（Depih）。在極線校正后的影像上，每個目標(biāo)像素點對應(yīng)深度的計算公式為匹配基礎(chǔ)03傳統(tǒng)立體匹配算法】9BM算法首先構(gòu)造一個小窗口，類似于卷積核。窗口的大小可以為3×3~21×21，通常情況下窗口的寬度是奇數(shù)確定窗口大小后，以待匹配的像素為中心，用窗口框選參考影像的區(qū)域內(nèi)的所有像素點，同樣用相同窗口框選目標(biāo)影像并選出像素點。用兩個窗口范圍內(nèi)的對應(yīng)像素計算匹配代價函數(shù)。傳統(tǒng)立體匹配算法對于紋理缺三的影像區(qū)域，極易出現(xiàn)誤匹配或無法匹配的情況。01但是，該類以窗口匹配為基礎(chǔ)的算法存在以下不足：02對由光照條件的變化所引起的紋理畸變較為敏感。03對攝像機的位置和姿態(tài)變化及場景深度變化所引起的紋理畸變比較敏感。傳統(tǒng)立體匹配算法在紋理重復(fù)的區(qū)域中，可能會出現(xiàn)多個相關(guān)的峰值，這會導(dǎo)致誤匹配的產(chǎn)生。04但是，該類以窗口匹配為基礎(chǔ)的算法存在以下不足：05對遮擋情況沒有很好的處理機制。傳統(tǒng)立體匹配算法匹配算法都需要對像素進行匹配代價函數(shù)設(shè)計，不同的代價函數(shù)會對應(yīng)形成不同的匹配代價度量。在眾多匹配代價度量的算法中，圍繞方差和相關(guān)性展開設(shè)計較為普遍。方差匹配的直觀理解就是兩幅影像的“距離”，也就是它們之間差別大小的量化概念；相關(guān)性則以模板與檢測影像各個像素值相乘后得到的相關(guān)度為基礎(chǔ)。傳統(tǒng)立體匹配算法傳統(tǒng)立體匹配算法代價聚合的目的是讓代價度量的值可以較為精確地反映像素之間的相關(guān)性，單純的代價匹配計算只考志單一路徑以及局部區(qū)共的相關(guān)性。同時，在視差不連續(xù)的區(qū)域與紋理偏弱或重復(fù)紋理的區(qū)域，代價值很有可能無法反映左、右像素點的相關(guān)性，最直接的表現(xiàn)就是自動匹配的同名像點的代價并不是視差搜索范團內(nèi)最優(yōu)的值。傳統(tǒng)立體匹配算法01唯一性檢測傳統(tǒng)立體匹配算法02左右一致性檢測傳統(tǒng)立體匹配算法連通域檢測八點算法最小化的誤差是一個代數(shù)錯誤，然而理想的最小化目標(biāo)函數(shù)是一個幾何意義上的標(biāo)量?？梢圆扇〉恼`差測量是點與外極線之間的距離D(m，l)。假設(shè)每個特征點上的噪聲都是獨立的零均值高斯，所有點的標(biāo)準(zhǔn)差都相同，則以下形式的最小化會產(chǎn)生最大似然解。03傳統(tǒng)立體匹配算法】9動態(tài)規(guī)劃（DynamicPrograrnming，DP）算法應(yīng)用在立體匹配中，是一種比較高效的全局匹配優(yōu)化算法，整體精度相對可革。20世紀(jì)50年代初美國數(shù)學(xué)家R.E.Bellman等人在研究多階段決策過程（MultistepDecisionProcess）的優(yōu)化問題時，提出了著名的最優(yōu)性原理。同時，Bellman把多階段過程轉(zhuǎn)化為一系列單階段問題，利用各階段之間的關(guān)系逐個求解，創(chuàng)立了解決多階段決策問題的優(yōu)化方法——動態(tài)規(guī)劃法。傳統(tǒng)立體匹配算法傳統(tǒng)立體匹配算法04圖割優(yōu)化匹配算法圖割優(yōu)化匹配法圖割優(yōu)化匹配法】9圖割優(yōu)化匹配法】9圖割優(yōu)化匹配法本節(jié)介紹一種簡單線性迭代聚類（SimpleLinearIterativeClustering,SLIC）算法來進行超像索分割操作，它是在區(qū)均值聚類分割（K-means）算法的基礎(chǔ)上進行的優(yōu)化算法。下面介紹算法的具體實施步驟。進行分割中心初始化，利用規(guī)則化的格網(wǎng)將影像像素區(qū)間進行原始劃分，格網(wǎng)的尺寸根據(jù)

計算獲得。采樣中心初始化在各個格網(wǎng)的中心，然后在3x3的格網(wǎng)鄰域區(qū)間內(nèi)移動尋找影像梯度變化最小的位置，這樣做可以避免分割中心落在梯度大的邊緣位置。圖割優(yōu)化匹配法對每個像素找到其所屬的初始分割區(qū)間。每個像素僅與最鄰近的聚類中心聯(lián)系在一起，每個聚類中心聯(lián)系的像素范圍為2S×2S，僅當(dāng)像素落在一個聚類中心的覆蓋區(qū)域內(nèi)時才與該中心進行分析。

迭代更新直至殘差收斂。SLIC分割算法是一種改化的K-Means分類方法，它具有以下兩大特點：（1）通過約束與超像素尺才成正比的搜索空間大小，優(yōu)化過程的距離測度計算涉及的像素被大大減少，因此計算復(fù)雜度是與像素個數(shù)N成正比的線性復(fù)雜度O(N)；（2）加權(quán)相似性測度西數(shù)是一個包含顏色和位置屬性的函數(shù)，它可以控制超像素分割后的各像素塊的尺度和緊湊度。圖割優(yōu)化匹配法圖割優(yōu)化匹配法Middlebury發(fā)布的第二版本測試數(shù)據(jù)包括tsukuba、venus、teddy三組立體影像，三組圖像的最大視差的取值范圍分別為16像素、32像素、64像素，所以具有較好的代表性，圖5.16列出了三組影像的標(biāo)準(zhǔn)數(shù)據(jù)集圖像（上）以及對應(yīng)的真實視差圖（下）。圖割優(yōu)化匹配法05結(jié)構(gòu)光三維掃描如圖5.18所示，空間變化的二維結(jié)構(gòu)照射由特殊投影儀或由空問光調(diào)制器控制的光源產(chǎn)生。一個任意目標(biāo)的三維表面被結(jié)構(gòu)光投射圖案所照射，該例的結(jié)構(gòu)光的模式圖案是空問變化的。成像傳感器獲取目標(biāo)在結(jié)構(gòu)光照射下的表面影像。改變?nèi)S曲面的幾何形狀，成像傳感器捕獲的影像也會發(fā)生相應(yīng)的變化。結(jié)構(gòu)光三維掃描結(jié)構(gòu)光三維掃描使用連續(xù)變化的結(jié)構(gòu)光圖案的技術(shù)。01進一步可以將單點拍攝技術(shù)分為三大類：02使用一維編碼方案的技術(shù)（條帶索引)。03使用二維編碼方案（網(wǎng)格索引）的技術(shù)。結(jié)構(gòu)光三維掃描二進制編碼使用黑白條帶形成一系列投影圖案，使得每個點都有唯一的二進制代碼，該代碼不同于其他任何不同點的代碼。結(jié)構(gòu)光三維掃描相移法是一種著名的三維表面成像的條帶投影方法，它投射一組正弦圖家到物體表面（圖5.23），在相鄰光平面之間插值，每幅影像的像素獲得亞像素級別的條帶值。投影三個相移正弦模式，三個投影條帶圖的每個像素(x,y)的強度都可以描述為：結(jié)構(gòu)光三維掃描相移技術(shù)主要存在的問題是相位展開方法只提供相對展開，而不能求解絕對相位。如果兩個表面的不連續(xù)性大于2元，則基于相位展開的任何方法都無法正確地展開這兩個互相關(guān)聯(lián)的表面之間的關(guān)系。這些通常被稱為“整周期模糊度”的問題，可以通過結(jié)合使用灰度碼投影技術(shù)和相移技術(shù)來解決。結(jié)構(gòu)光三維掃描12光度立體法它從同一視點拍攝，通過改變光照射的方向，使用目標(biāo)表面的影像序列來估計局部表面方向。它通過使用多幅影像解決了傳統(tǒng)的SFS方法中的不適定問題。彩虹三維攝像機圖5.28展示了利用彩虹帶模式的三維攝像機的基本概念，前提假設(shè)是場景不會改變投影儀打出的光顏色。相比于必須從一對立體影像中提取相應(yīng)特征以計算深度值的傳統(tǒng)立體視覺，彩虹三維攝像機可將空間變化的波長照射投影到物體表面。結(jié)構(gòu)光三維掃描34偽隨機二進制陣列一種網(wǎng)格索引的方法，是在網(wǎng)格位置上使用的隨二進制陣列（Pseudo-Random

BinaryArray,PRBA），產(chǎn)生點或其他圖案標(biāo)記，使任何子窗口的編碼圖案是唯一的。DeBruiin編碼DeBruijn編碼是應(yīng)用了DeBruijn序列的結(jié)構(gòu)光編碼方法。n個字母m階的序列是一個長度為n的圓形字符串，其中長度為m的各子串出現(xiàn)一次。結(jié)構(gòu)光三維掃描】9結(jié)構(gòu)光三維掃描06立體視覺標(biāo)定】9攝像機標(biāo)定過程建立了二維影像上的像素與物體點所在的三維空間中的攝影關(guān)系，并且考慮了鏡頭的喂變失真。在大多數(shù)應(yīng)用中，標(biāo)定技術(shù)可以使用簡化的攝像機模型和一組內(nèi)參數(shù)來表示這個關(guān)系。有幾種方法和相應(yīng)的工具箱可用，這些過程需要不同角度拍攝的照片和已知的標(biāo)定對象的尺度信息。平面棋盤格是一種常用的標(biāo)定對象，因為它的制作非常簡單，可以用標(biāo)準(zhǔn)的打印機打印出來，并且有很容易被檢測到的明顯的角點。具體的原理和實現(xiàn)可以參見第2章中的技術(shù)方法。立體視覺標(biāo)定02投影儀的強度標(biāo)定此逆模型使得將二維影像上的像素與三維空間中的直線坐標(biāo)的關(guān)聯(lián)問題變得困難。尋找方法建立這種關(guān)聯(lián)對應(yīng)關(guān)系，就可以使用攝像機標(biāo)定算法對投影儀進行標(biāo)定。為了提高對比度，投影儀的強度曲線通常隨著伽馬變換而改變。當(dāng)在三維成像系統(tǒng)中作為主動光源使用時，標(biāo)定的目標(biāo)是恢復(fù)照射強度的線性度。投影儀的幾何標(biāo)定立體視覺標(biāo)定式中，d是視差的標(biāo)準(zhǔn)偏差。該方程表明，深度不確定度隨深度呈二次暴增長。因此，標(biāo)注雙目立體視覺系統(tǒng)通常只能在有限的距離范圍內(nèi)工作。如果目標(biāo)距離較大，則深度估計變得更不確定。立體視覺標(biāo)定07應(yīng)用舉例實驗數(shù)據(jù)。算法實現(xiàn)。精度評定。010203這些設(shè)各設(shè)施直接驗證了月球車對地外星體探測的能力，為定量地分析各類算法精度和效率提供了可靠的支持與保障。應(yīng)用舉例08小結(jié)雙目立體視覺技術(shù)涵蓋了前面章節(jié)的許多基礎(chǔ)知識，包括對極幾何、攝像機標(biāo)定、特征提取與匹配的理論。雙目立體視覺無論是設(shè)備搭建還是程序開發(fā)實現(xiàn)，都是比較容易入手的。小結(jié)感謝觀看第六章計算機視覺三維測量與建模點云濾波與分割南京航空航天大學(xué)研究生教育教學(xué)改革專項（優(yōu)質(zhì)教學(xué)資源建設(shè)）項目資助01采樣點云特性】9隨著數(shù)據(jù)采集設(shè)備的不斷更新發(fā)展，三維點云的獲取變得越米越便捷，采集數(shù)據(jù)的設(shè)備包括數(shù)碼攝像機、結(jié)構(gòu)光掃描儀、LiDAR掃描儀以及彩色深度（RGBD）攝像機等，然而數(shù)據(jù)獲取方式的差異也使采樣點云具有不同的屬性，同時包括各種潛在的數(shù)據(jù)缺陷，是表面重建工作需要面臨的重要挑戰(zhàn)。接下來概括描達采樣點云通常存在的一些典型問題，如圖6.1所示，以一個點云片段的截面為例。采樣點云特性嗓音（Noise）點云噪聲通常是指數(shù)據(jù)點隨機分布在靠近真實表面位置的情況典型的噪聲受以下因素的影響：傳感器的系統(tǒng)性問題、觀測目標(biāo)的材料散射特性、深度值測量質(zhì)量、傳感器與目標(biāo)之間的距離等。0102外點（Outliers）外點也叫作異常值或者野值，它是指遠商真實表面的采樣點。小點的產(chǎn)生通常是由于在數(shù)據(jù)采集的過程中出現(xiàn)了結(jié)構(gòu)性的錯誤。主要表現(xiàn)為隨機地分布生真實表面周團的離散點，通常這部分點的密度低于正常采樣數(shù)據(jù)的密度。外點也可以是戲群存在的，比如以較高密度點集群存在于遠離真實表面的位置。03采樣缺失（Missing）采樣缺失是由于在掃描過程中傳感器的采樣范圍有限、目標(biāo)具有高吸收特性、目標(biāo)形狀遮擋等因素造成的。這使得部分目標(biāo)表面沒有采樣數(shù)據(jù)，主采樣密度為零的區(qū)域。采樣點云特性密度不均（UnevenDensity）對目標(biāo)物表面進行掃描采樣時，點云在對應(yīng)物體表面約密度分布被理解為采樣密度。三維掃描產(chǎn)生的點云通常會具有采樣密度不均勻的特點，這可能是由于采樣目標(biāo)與掃描儀的距離變化、掃描儀攝影方向變換、采樣目標(biāo)的自身形態(tài)特征等因素引起的。0405配準(zhǔn)錯位（Misalignment）有時數(shù)據(jù)采集不是一次性完成的，而是利用多角度或者多頻次的采樣拼接得到整個目標(biāo)場景的點云數(shù)據(jù)的。采樣點云特性采樣點云特性】9從程序?qū)崿F(xiàn)的角度出發(fā)，將待估計距離直接用平方項進行比較，避免開平方運算的消耗,可大大提高算法效率。幾乎所有的ANN方法都基于對全空間的劃分，迅速找到查詢點所在的子空間,并將查詢點與子空間內(nèi)的數(shù)據(jù)點進行比較計算。對于具體的應(yīng)用而言,鄰域查詢還被分為兩種類型的查詢,即:找到離查詢點p，最近的k個點，不考慮這些點的分布范圍；找到距p，小于半徑r的至多k個點,此時查詢結(jié)果的個數(shù)可能小于k個。采樣點云特性在這些結(jié)構(gòu)當(dāng)中，八叉樹和KD樹是三維點云數(shù)據(jù)組織中應(yīng)用最為廣泛的兩種。八叉樹數(shù)據(jù)結(jié)構(gòu)是由二維空間的四叉樹數(shù)據(jù)結(jié)構(gòu)推廣到三維空間而形成的，它是種樹形結(jié)構(gòu)，在空間分解上具有很強的優(yōu)勢。采樣點云特性KD樹是一種用于組織＆維空間中離散數(shù)據(jù)點的數(shù)據(jù)結(jié)構(gòu)，它是一種二叉搜索樹，在最鄰近搜索上具有非常高的效率。采樣點云特性02點云濾波增強】96.1節(jié)所述的建模算法對掃描點云的采樣密度、表面法向量和噪聲分布等特性都有一定的要求，雖然許多隱式建模算法都可以容忍一定程度的點云密度的稀疏分布和法向量的方向翻轉(zhuǎn)錯誤的情況，但當(dāng)存在大面積連續(xù)的法向量估計錯誤時，表面重建結(jié)果會有顯著的缺陷。因此，準(zhǔn)確的法向量估計以及優(yōu)化的點云空間結(jié)構(gòu)，對于表面建模工作具有十分重要的意義。在本節(jié)中，將介紹與點云結(jié)構(gòu)增強相結(jié)合的法向量估計優(yōu)化算法,可以提高離散點云數(shù)據(jù)質(zhì)量。點云濾波增強點云的法向量信息對于采樣點云的平面擬合、特征提取、表面分割、表面建模以及信息提取等研究來說有極其重要的作用。光滑表面在每一點上的法向量都有唯一的定義，即垂直于該點的空間切面的方向，在一個給定的點上切面空間的直觀表示是一個局部表面近似。表面法向量可以是有向的，其中每個法向量始終指向表面的內(nèi)側(cè)或外側(cè)；法向量估計的結(jié)果也可能是無向的，即具體指向不確定。有向的法向量為重建算法提供了非常有用的線索，然而如果與點云相關(guān)的某些信息是不存在的，那么要得到一個方向明確的法向量是非常困難的。點云濾波增強主成分分析算法確定法向量的指向點云濾波增強最小生成樹(MST)算法使用Kruskal算法生成MST的方法可以稱為“加邊法”，初始最小生成樹的邊數(shù)為0，每迭代一次就選擇一條滿足條件的最小代價邊，加入最小生成樹的邊集合里。具體步驟如下：（1）把圖中的所有邊按代價從小到大排序；（2）把圖中的n個頂點視為獨立的由n棵樹組成的森林；（3）按權(quán)值從小到大選擇邊，所選的邊連接的兩個頂點應(yīng)屬于兩棵不同的樹，則成為最小生成樹的一條邊，并將這兩棵樹合并為一棵樹；（4）重復(fù)上一步，直到所有頂點都在一棵樹內(nèi)或者有1-1條邊為止。點云濾波增強一點的局部歐氏坐標(biāo)系點云濾波增強01基于統(tǒng)計學(xué)的方法一種簡單的基于統(tǒng)計學(xué)方法的原理是假設(shè)點云里的所有點到其鄰域點的平均距離值的概率服從高斯分布，其形狀由均值和標(biāo)準(zhǔn)差決定。在算法處理時，首先將輸入點云數(shù)據(jù)中的每一個點到其鄰近點的距離分布情況進行計算，得到各點到它所有鄰近點的平均距離。然后，將平均距離在標(biāo)準(zhǔn)差范園之外的點定義為離群點，進而將這些離群點從點云中刪除。02基于表面重采樣的方法經(jīng)典的表面重采樣方法從計算機圖形研究領(lǐng)域被推廣到了三維點云處理領(lǐng)域?；诒砻嬷夭蓸拥姆椒▽Ⅻc投影到估計的局部曲面。點云濾波增強03基于深度學(xué)習(xí)的方法它通過將點斑投影到一個基于學(xué)習(xí)得到的局部框架下，并在有監(jiān)咨的環(huán)境中使用卷積神經(jīng)網(wǎng)絡(luò)(ConvolutionalNeuralNetwork,CNN)將點斑移動到曲面上來，達到去噪的效果。另一種方法使用PCPNet將噪聲點云投影映射到一個千凈的點云曲面。此外，也有學(xué)者以人造目標(biāo)為對象，研究用基于深度學(xué)習(xí)的方法提取邊特征，然后在保持邊特征的前提下對點云進行重采樣。點云濾波增強異常值（Outliers）檢測在許多領(lǐng)域都被應(yīng)用，比如統(tǒng)計分析、機器學(xué)習(xí)、模式識別和數(shù)據(jù)壓縮等。采樣點云數(shù)據(jù)通常具有不同的點密度，此外測量誤差會引起稀疏的異常值和退化的結(jié)果。點云濾波增強主成分分析（PrincipalComponentAnalysis,PCA）算法是典型的協(xié)方差矩陣估計算法，它對觀測噪聲十分飯感，當(dāng)噪聲強烈或有異常點存在時，所計算的結(jié)果會存在嚴(yán)重誤差。因此，下面提出了基于局部優(yōu)化投影采樣算法的點云增強算法來滅小噪聲和異常點給法向量估計帶來的不利影響。點云濾波增強】9點云濾波增強03點云超體素分割】9點云分割的目的是將點云集合中的點分割成具有感知意義的符合目標(biāo)邊界劃分性質(zhì)的若干區(qū)域子集。在同一個區(qū)域中的點應(yīng)該擁有相同的性質(zhì)。該技術(shù)在機器視覺中有很多應(yīng)用，例如，智能交通、現(xiàn)代測繪和自動導(dǎo)航。超體素（SuperVoxel）是一種集合,超體素聚類分割的目的不是完整地分割出某種特定目標(biāo),而是對點云實施一種過分割（OverSegmentation）。點云超體素分割】9依據(jù)馬爾可夫隨機場或條件隨機場條件，基于圖的算法將點云內(nèi)部的上下文關(guān)系與對象級的類別先驗知識合并在一起，近些年來獲得了廣泛的研究應(yīng)用。雖然這些技術(shù)的使用取得了顯著的進展，但有一個缺點，即在這些圖上進行推理的計算成本通常會隨肴圖的節(jié)點數(shù)量的增加而急劇增大。這意味著求解以每個點為一個節(jié)點的圖變得非常困難，這限制了算法在需要實時分割的應(yīng)用中的使用。點云超體素分割超體素分割可以提供超體素過分割形式的節(jié)點，代替原始的點，減少了進行推理時必須考慮的節(jié)點數(shù)量，從而減小了后續(xù)處理算法的計算成本?；诔w素的后續(xù)分割或建模算法必須考慮重構(gòu)數(shù)量，并且信息損失最小。點云超體素分割分割方法利用了觀測數(shù)據(jù)點之間的三維幾何關(guān)系，有時也包含附加的投影顏色或深度信息，分段區(qū)域內(nèi)必須具有空間連接性的約束。點云的體素類型包含規(guī)則格網(wǎng)化的體素，這類體素可以認為是一種對空間規(guī)則劃分的具有等尺寸的立方體。另一類體素是不規(guī)則的過分割形式的體素，在本節(jié)討論的超體素指的就是不規(guī)則的過分割超體素。點云超體素分割】9首先考慮相似性度量，通常它是以法向量、曲率和離散度等屬性信息構(gòu)成的特征空間中的特征向量來進行計算的，當(dāng)點云數(shù)據(jù)的附加信息中具有影像紋理亮度時，亮度參數(shù)也被包含到點的特征向量中。下一步對所有點進行聚類判斷，不同于傳統(tǒng)的后均值聚類算法對將每個點與所有聚類中心做判斷，本算法中的原始點只與3倍搜索半徑內(nèi)的種子點做相似性判斷。之后的運算與化均值聚類相似，利用相似性度量和距離度量判別聚類關(guān)系，并迭代更新聚類中心的位置，直到察類結(jié)果收斂。點云超體素分割構(gòu)建鄰接關(guān)系圖。構(gòu)建鄰接關(guān)系圖是VCCS的一個關(guān)鍵步驟，這一步能夠確保各個超體素不會跨越在空間中不相連的對象的邊界。在體素云化的三維空間中，有3種相鄰的形式，分別是6相鄰、18相鄰和26相鄰，它們分別共享一個面或邊，以及面、邊或頂點。0102選擇種子點。點云超體素分割設(shè)計特征空間和度量函數(shù)。0304基于約束的迭代聚類。05更新聚類中心，再選代直至收斂。點云超體素分割點云超體素分割04目標(biāo)級別分割】9點云分割是將擁有相似特征的同質(zhì)點劃分為獨立的區(qū)域，這些分割的區(qū)域具有語義層面同屬的意義。分割結(jié)果將有助于從多個方面分析一個場景，例如，定位識別物體和場景事件理解。良好的三維點云分割算法應(yīng)當(dāng)具有以下三條性質(zhì)。第一，算法要能夠使用幾種不同種類的特征，例如，樹與車這兩種目標(biāo)物有者不同的特征。當(dāng)特征的數(shù)量變多時，分割算法要能夠?qū)W會如何自動地調(diào)整它們；第二，針對那些在采樣稀疏區(qū)域的點，分割算法需要能夠根據(jù)應(yīng)用領(lǐng)域的先驗信息推斷點的類別；第三，良好的分割算法需要適用于數(shù)據(jù)采集時使用的不同類型的傳感器，因為不同的傳感器會產(chǎn)生不同質(zhì)量的數(shù)據(jù)。目標(biāo)級別分割人類可以輕松地從三維空間中感知物體的形狀、大小和類別性質(zhì)。然而,計算機自動從三維點云中分割物體是一項困難的任務(wù)。點云數(shù)據(jù)通常是充滿噪聲的和無序的?；谟跋衿ヅ浜腿S重建獲得的三維點云，由于有標(biāo)定參數(shù)的誤差和同名像素匹配的誤差，因此會存在比較明顯的表面噪聲;而用三維掃描儀獲取的三維數(shù)據(jù)，由于具有不同的線速率和角速率，因此點的采樣密度一般也是不均勻的。目標(biāo)級別分割另外，表面形狀可以是擁有尖銳特征的任意形狀并且在數(shù)據(jù)中也沒有統(tǒng)計學(xué)分布規(guī)律。受觀測條件的限制，有時候前景和背景混雜在一起,還有遮擋造成的數(shù)據(jù)缺失，這些問題都為點云目標(biāo)自動分割帶來了很大的困難。目標(biāo)級別分割01基于邊緣的目標(biāo)分割目標(biāo)的邊緣描繪了物體的形狀特征?；谶吘壍哪繕?biāo)分割方法探測點云中的多個域的邊界來得到分割點云?；趨^(qū)域特性的目標(biāo)分割方法利用應(yīng)用領(lǐng)域的先驗信息，合并那些有相似性質(zhì)的鄰近點，獲取獨立的區(qū)域?；趨^(qū)域特性的目標(biāo)分割方法比基于邊緣的目標(biāo)分割方法更加準(zhǔn)確，但是它有過分割和分割不足的問題，在確定區(qū)域邊界時也不夠準(zhǔn)確。基于區(qū)域特性的目標(biāo)分割方法可分為兩類：種子區(qū)域方法（自底向上）和非種子區(qū)域方法（自頂向下)。0203基于區(qū)域特性的目標(biāo)分割基于特征空間聚類的方法基于特征空間聚類的方法是基于點云的獨立特征，使用模式識別中的聚類算法對點云