• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

    基于八叉樹(shù)與KD樹(shù)索引的點(diǎn)云配準(zhǔn)方法

    2017-07-01 19:15:24王育堅(jiān)廉騰飛吳明明
    測(cè)繪工程 2017年8期
    關(guān)鍵詞:八叉樹(shù)立方體結(jié)點(diǎn)

    王育堅(jiān),廉騰飛,吳明明,高 倩

    (北京聯(lián)合大學(xué) 信息學(xué)院,北京 100101)

    基于八叉樹(shù)與KD樹(shù)索引的點(diǎn)云配準(zhǔn)方法

    王育堅(jiān),廉騰飛,吳明明,高 倩

    (北京聯(lián)合大學(xué) 信息學(xué)院,北京 100101)

    針對(duì)點(diǎn)云配準(zhǔn)算法中KD樹(shù)多維查詢效率較低的問(wèn)題,提出一種基于八叉樹(shù)和KD樹(shù)多層索引結(jié)構(gòu)的點(diǎn)云配準(zhǔn)方法。首先為模型點(diǎn)云數(shù)據(jù)建立八叉樹(shù)全局索引,然后在八叉樹(shù)葉子結(jié)點(diǎn)構(gòu)建局部數(shù)據(jù)的KD樹(shù)索引。對(duì)傳統(tǒng)的ICP點(diǎn)云配準(zhǔn)算法進(jìn)行改進(jìn),通過(guò)葉子結(jié)點(diǎn)的全局索引值快速定位局部點(diǎn)云數(shù)據(jù)塊,利用局部KD樹(shù)索引加快最近點(diǎn)的搜索,計(jì)算最近點(diǎn)時(shí)利用歐氏距離閾值、點(diǎn)對(duì)距離差值和法向量閾值剔除部分噪聲點(diǎn)。實(shí)驗(yàn)表明,改進(jìn)算法提高了點(diǎn)云配準(zhǔn)的效率和精度。

    點(diǎn)云配準(zhǔn);八叉樹(shù);KD樹(shù);ICP算法

    三維重建在計(jì)算機(jī)視覺(jué)、虛擬現(xiàn)實(shí)、3D打印和逆向工程等方面有著廣泛的應(yīng)用,點(diǎn)云數(shù)據(jù)配準(zhǔn)方法的優(yōu)劣直接影響三維重建的效果。利用三維掃描儀多次掃描物體表面,得到不同視角下的三維點(diǎn)云數(shù)據(jù),將掃描得到的多片點(diǎn)云數(shù)據(jù)進(jìn)行配準(zhǔn),即可得到完整的模型[1]。點(diǎn)云配準(zhǔn)包括粗配準(zhǔn)和精配準(zhǔn),粗配準(zhǔn)的目的是為精配準(zhǔn)提供良好的初值,縮小相鄰點(diǎn)云之間的旋轉(zhuǎn)誤差和平移誤差。精配準(zhǔn)的目的是找到最合適的旋轉(zhuǎn)矩陣和平移矩陣,使得相鄰點(diǎn)云配準(zhǔn)的誤差最小。

    目前應(yīng)用最廣泛的點(diǎn)云配準(zhǔn)算法是迭代最近點(diǎn)(Iterative Closest Point,ICP)算法[2]及其改進(jìn)算法。ICP算法作為一種基于純粹幾何模型的配準(zhǔn)方法,人們提出了多種改進(jìn)方案[3],改進(jìn)的基本思路主要體現(xiàn)在點(diǎn)云數(shù)據(jù)模型設(shè)計(jì)和最近點(diǎn)搜索策略兩個(gè)方面[4-5]。例如,在點(diǎn)云數(shù)據(jù)模型設(shè)計(jì)方面,利用Delaunay三角剖分[6]、KD樹(shù)[7]等對(duì)ICP算法進(jìn)行改進(jìn)。在實(shí)際應(yīng)用過(guò)程中,對(duì)于數(shù)據(jù)量很大的點(diǎn)云數(shù)據(jù),ICP算法配準(zhǔn)耗時(shí)較長(zhǎng),影響了算法效率。本文基于八叉樹(shù)和KD 樹(shù)的多層索引結(jié)構(gòu),提出一種點(diǎn)云精配準(zhǔn)的改進(jìn)方法。

    1 點(diǎn)云數(shù)據(jù)結(jié)構(gòu)

    1.1 八叉樹(shù)結(jié)構(gòu)和KD樹(shù)結(jié)構(gòu)

    八叉樹(shù)結(jié)構(gòu)是一種規(guī)則的數(shù)據(jù)結(jié)構(gòu),利用樹(shù)形結(jié)構(gòu)對(duì)模型進(jìn)行遞歸,按X,Y,Z3個(gè)不同方向,將所要表示的三維空間實(shí)體分割成8個(gè)大小相等的子立方體。然后根據(jù)每個(gè)子立方體中所含的目標(biāo)來(lái)決定是否對(duì)子立方體繼續(xù)進(jìn)行8等分的劃分,一直劃分到每個(gè)子立方體被一個(gè)目標(biāo)所充滿,或沒(méi)有目標(biāo),或其大小已成為預(yù)先規(guī)定的體素為止。八叉樹(shù)分解是將三維空間實(shí)體逐級(jí)分解,最終形成八叉樹(shù)體素表示的結(jié)構(gòu)。八叉樹(shù)的主要優(yōu)點(diǎn)是可以方便地實(shí)現(xiàn)物體的并、交、差等集合運(yùn)算,適用于不同形狀物體的建模。

    KD樹(shù)是一種把二叉查找樹(shù)推廣到多維數(shù)據(jù)的結(jié)構(gòu),實(shí)現(xiàn)多維空間數(shù)據(jù)的組織和存儲(chǔ)。KD樹(shù)利用超平面把一個(gè)空間劃分成多個(gè)不相交的子空間,每一層都將所包含的空間分成兩個(gè)子空間,頂層結(jié)點(diǎn)按一維劃分,下一層結(jié)點(diǎn)按另一維劃分,KD樹(shù)所有維的屬性在層間循環(huán)。任何一個(gè)非葉子結(jié)點(diǎn)的左右子樹(shù)也是KD樹(shù),若結(jié)點(diǎn)的左子樹(shù)不為空,則左子樹(shù)上所有結(jié)點(diǎn)第d維的值均小于根結(jié)點(diǎn)第d維的值;若結(jié)點(diǎn)的右子樹(shù)不為空,則右子樹(shù)上所有結(jié)點(diǎn)第d維的值均大于等于根結(jié)點(diǎn)第d維的值。

    KD樹(shù)每一個(gè)結(jié)點(diǎn)劃分結(jié)束的條件是結(jié)點(diǎn)中只包含一個(gè)數(shù)據(jù)或少于設(shè)定的上限為止。KD樹(shù)可以用來(lái)建立多維空間數(shù)據(jù)集或數(shù)據(jù)塊的索引。利用KD樹(shù)進(jìn)行數(shù)據(jù)查詢時(shí),每一步結(jié)點(diǎn)的條件判斷只要比較其中的一個(gè)維。通過(guò)交替比較不同維的屬性值,可以快速查找某個(gè)數(shù)據(jù)點(diǎn)的鄰域,不需要知道數(shù)據(jù)之間的任何拓?fù)潢P(guān)系。

    1.2 多層索引結(jié)構(gòu)設(shè)計(jì)

    KD樹(shù)通過(guò)左右孩子指針建立數(shù)據(jù)關(guān)系,索引指針數(shù)據(jù)占據(jù)了大量的內(nèi)存空間。KD樹(shù)采用一分為二的分割方式,由于點(diǎn)云數(shù)據(jù)量巨大,使得樹(shù)的深度很大,增加了數(shù)據(jù)查找的時(shí)間,但影響KD樹(shù)搜索效率的主要因素是回溯[8]。八叉樹(shù)結(jié)構(gòu)規(guī)則統(tǒng)一,樹(shù)的深度大大降低,對(duì)于精確數(shù)據(jù)點(diǎn)查找,其性能較高[9]。但八叉樹(shù)的動(dòng)態(tài)性較差,在數(shù)據(jù)點(diǎn)集分布不均勻的情況下,樹(shù)的平衡性不好。

    考慮到八叉樹(shù)數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)特點(diǎn)和KD樹(shù)搜索有效性,提出一種八叉樹(shù)與KD樹(shù)相結(jié)合的多層索引結(jié)構(gòu)。設(shè)待配準(zhǔn)點(diǎn)云為P,模型點(diǎn)云為Q?;谀P忘c(diǎn)云Q建立多層索引結(jié)構(gòu),在上層采用八叉樹(shù)結(jié)構(gòu)存儲(chǔ)和管理全局的點(diǎn)云數(shù)據(jù),在下層利用KD樹(shù)組織和存儲(chǔ)局部的點(diǎn)云數(shù)據(jù),每個(gè)局部KD樹(shù)索引的信息都保存在八叉樹(shù)末端關(guān)聯(lián)的葉結(jié)點(diǎn)中。全局八叉樹(shù)和局部KD樹(shù)的多層索引結(jié)構(gòu)如圖1所示,其中的虛線框內(nèi)表示八叉樹(shù)葉結(jié)點(diǎn)與KD樹(shù)的對(duì)應(yīng)關(guān)系。

    圖1 多層索引結(jié)構(gòu)

    根據(jù)這種多層索引結(jié)構(gòu),首先自上而下采用八叉樹(shù)結(jié)構(gòu)對(duì)模型點(diǎn)云進(jìn)行空間分割。根據(jù)模型點(diǎn)云的最小和最大坐標(biāo),得到一個(gè)包圍整個(gè)模型的立方體,該立方體作為八叉樹(shù)的根結(jié)點(diǎn)。將該立方體分解成8個(gè)子立方體,作為8個(gè)孩子結(jié)點(diǎn)。根據(jù)配準(zhǔn)精度要求確定八叉樹(shù)的分割參數(shù),得到每個(gè)葉子結(jié)點(diǎn)點(diǎn)云所包含最大的點(diǎn)數(shù)。當(dāng)葉子結(jié)點(diǎn)內(nèi)的點(diǎn)云數(shù)目小于最大點(diǎn)數(shù)時(shí),結(jié)束八叉樹(shù)的分解,不必像傳統(tǒng)八叉樹(shù)那樣直到結(jié)點(diǎn)只有一個(gè)數(shù)據(jù)點(diǎn)或有限的數(shù)據(jù)點(diǎn)時(shí)才結(jié)束分解。

    當(dāng)利用八叉樹(shù)分割點(diǎn)云模型生成葉子結(jié)點(diǎn)后,在八叉樹(shù)非空的葉子結(jié)點(diǎn)設(shè)置指針值,指向關(guān)聯(lián)的KD樹(shù)。KD樹(shù)將八叉樹(shù)葉子結(jié)點(diǎn)中的點(diǎn)云數(shù)據(jù)一分為二,劃分為兩個(gè)子空間,然后再對(duì)每一個(gè)子空間進(jìn)一步進(jìn)行遞歸劃分,最后得到一棵完整的KD樹(shù),即所有含有點(diǎn)云數(shù)據(jù)的葉子結(jié)點(diǎn)都建立關(guān)聯(lián)的KD樹(shù)。創(chuàng)建KD樹(shù)采用一種改進(jìn)的方法,即先對(duì)3個(gè)軸都進(jìn)行采樣[7],然后選擇合適的軸進(jìn)行劃分,以保證每次劃分都能找到近似最優(yōu)的分割位置。

    全局八叉樹(shù)是第一層索引,局部KD樹(shù)是建立在八叉樹(shù)葉子結(jié)點(diǎn)之下的第二層索引。通過(guò)分割參數(shù)設(shè)定八叉樹(shù)葉子結(jié)點(diǎn)的數(shù)據(jù)量,如果設(shè)置的分割參數(shù)很大,則葉子結(jié)點(diǎn)關(guān)聯(lián)的局部點(diǎn)云數(shù)據(jù)很多,KD樹(shù)的深度較大,會(huì)降低KD樹(shù)的搜索效率;反之,如果將結(jié)點(diǎn)劃得很細(xì),雖然KD樹(shù)的深度降低,但增加了邊界數(shù)據(jù)點(diǎn)的數(shù)量,勢(shì)必影響配對(duì)的精度。因此,生成八叉樹(shù)時(shí)要綜合考慮模型的空間形狀、點(diǎn)元數(shù)據(jù)規(guī)模和配準(zhǔn)精度的要求,通過(guò)實(shí)驗(yàn)分析得出接近于最佳搜索的分割參數(shù)。

    與傳統(tǒng)的KD樹(shù)相比,多層索引結(jié)構(gòu)需要額外的空間存儲(chǔ)八叉樹(shù),但由于八叉樹(shù)沒(méi)有分割到只有一個(gè)數(shù)據(jù)點(diǎn)才結(jié)束,八叉樹(shù)的深度是可以控制的,需要的附加空間并不大。并且,結(jié)點(diǎn)之間的層次關(guān)系可以根據(jù)結(jié)點(diǎn)編碼得到,配準(zhǔn)時(shí)定位八叉樹(shù)的葉子結(jié)點(diǎn)并不需要回溯,因此,八叉樹(shù)每個(gè)結(jié)點(diǎn)可以不存儲(chǔ)其父結(jié)點(diǎn)的指針,減少了模型的存儲(chǔ)空間。

    多層索引結(jié)構(gòu)的八叉樹(shù)結(jié)點(diǎn)用一個(gè)屬性值表示葉子結(jié)點(diǎn)與KD樹(shù)的關(guān)聯(lián),若八叉樹(shù)葉子結(jié)點(diǎn)的屬性值為“KD”,表示該葉子結(jié)點(diǎn)鏈接一個(gè)局部的KD樹(shù)。通過(guò)葉子結(jié)點(diǎn)與其對(duì)應(yīng)KD樹(shù)的根結(jié)點(diǎn)的關(guān)聯(lián),形成局部KD樹(shù)索引。搜索時(shí)根據(jù)待配準(zhǔn)點(diǎn)的坐標(biāo)和子立方體空間屬性值快速完成最近點(diǎn)的自適應(yīng)定位,最近點(diǎn)的搜索局限于數(shù)據(jù)點(diǎn)所在八叉樹(shù)葉子結(jié)點(diǎn)的包圍盒內(nèi),避免了回溯八叉樹(shù)。

    將索引代價(jià)較小的八叉樹(shù)與KD樹(shù)相關(guān)聯(lián),利用空間分塊策略設(shè)計(jì)多層索引,這種索引結(jié)構(gòu)在保證滿足配準(zhǔn)精度的前提下,能夠大大優(yōu)化最近點(diǎn)的搜索性能。建立全局八叉樹(shù)和局部KD樹(shù)多層索引結(jié)構(gòu)的算法如下:

    1)根據(jù)模型點(diǎn)云Q的大小選取一個(gè)包圍盒立方體,將該立方體作為八叉樹(shù)的根結(jié)點(diǎn)。

    2)若當(dāng)前結(jié)點(diǎn)包含的數(shù)據(jù)點(diǎn)數(shù)大于規(guī)定的點(diǎn)數(shù),采用深度優(yōu)先策略對(duì)該結(jié)點(diǎn)進(jìn)行八叉樹(shù)遞歸分解,將立方體分解成8個(gè)子立方體。

    3)若當(dāng)前結(jié)點(diǎn)包含的點(diǎn)數(shù)小于或等于規(guī)定的點(diǎn)數(shù),停止分解,該結(jié)點(diǎn)為八叉樹(shù)的葉子結(jié)點(diǎn),生成結(jié)點(diǎn)數(shù)據(jù)域,設(shè)置結(jié)點(diǎn)的“KD”屬性值。

    4)針對(duì)八叉樹(shù)葉子結(jié)點(diǎn)包含的局部點(diǎn)云數(shù)據(jù)創(chuàng)建KD樹(shù)。根據(jù)3個(gè)軸的采樣選擇劃分的坐標(biāo)軸,將八叉樹(shù)葉結(jié)點(diǎn)的點(diǎn)云數(shù)據(jù)一分為二,劃分為兩個(gè)平面;再對(duì)每個(gè)平面進(jìn)一步遞歸劃分,直到生成KD樹(shù)的每一個(gè)結(jié)點(diǎn)。生成KD樹(shù)后,建立八叉樹(shù)葉子結(jié)點(diǎn)與KD樹(shù)的索引。

    5)將當(dāng)前指針指向八叉樹(shù)的下一個(gè)結(jié)點(diǎn),重復(fù)步驟2),直到處理完所有八叉樹(shù)結(jié)點(diǎn)。

    2 改進(jìn)的點(diǎn)云配準(zhǔn)算法

    2.1 ICP算法的最近點(diǎn)搜索

    ICP算法根據(jù)一定的準(zhǔn)則確立對(duì)應(yīng)點(diǎn)集P與Q,通過(guò)最小二乘法迭代計(jì)算最優(yōu)的坐標(biāo)變換,即旋轉(zhuǎn)矩陣和平移矢量,將一個(gè)坐標(biāo)系下的點(diǎn)數(shù)據(jù)變換到另一個(gè)坐標(biāo)系,并使得誤差函數(shù)最小。點(diǎn)云配準(zhǔn)可以看作是求解變換矩陣的過(guò)程,決定ICP算法坐標(biāo)變換的關(guān)鍵在于能否在模型點(diǎn)云Q中準(zhǔn)確、快速地找到P中待配準(zhǔn)點(diǎn)的最近點(diǎn)。因此,影響ICP算法效率和精度的主要因素是最近點(diǎn)的搜索方法[10]。

    研究者基于最近點(diǎn)搜索提出多種ICP的改進(jìn)方法。文獻(xiàn)[11]提出基于重疊區(qū)域的近似KD樹(shù),在搜索重疊區(qū)域的子結(jié)點(diǎn)時(shí)不回溯,提高了搜索效率和精度。文獻(xiàn)[12]基于點(diǎn)云單應(yīng)性假設(shè)提出一種采用點(diǎn)和面對(duì)應(yīng)的ICP改進(jìn)算法,利用單應(yīng)性剔除其余點(diǎn)對(duì),算法具有較好的穩(wěn)健性和收斂性。文獻(xiàn)[13]在K近鄰搜索中使用OKDT正交搜索樹(shù),利用主成分分析方法計(jì)算點(diǎn)集方差最大的正交軸方向,按照優(yōu)化KD樹(shù)劃分方法劃分子樹(shù),當(dāng)點(diǎn)云數(shù)據(jù)量很大時(shí)該方法具有較好的搜索性能。此外,文獻(xiàn)[14]根據(jù)模型點(diǎn)集的各維方差按坐標(biāo)軸排序,能夠快速搜索最近點(diǎn)搜索范圍的邊界。文獻(xiàn)[15]采用點(diǎn)云歐氏距離閾值和方向矢量夾角閾值去噪。文獻(xiàn)[16]提出曲率約束與對(duì)應(yīng)點(diǎn)距離約束相結(jié)合的自適應(yīng)噪點(diǎn)剔除策略。文獻(xiàn)[5]首先采用中心重合法實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)的粗配準(zhǔn),然后利用KD樹(shù)快速搜索最近點(diǎn)對(duì),完成點(diǎn)云數(shù)據(jù)的精配準(zhǔn)。上述算法都在不同情況下提高了搜索的效率或精度。

    2.2 基于KD樹(shù)最近鄰搜索算法的改進(jìn)

    通常情況下,計(jì)算P中每個(gè)點(diǎn)p的最近點(diǎn),需要計(jì)算p與Q中所有點(diǎn)的歐氏距離。局部KD樹(shù)是針對(duì)八叉樹(shù)葉子結(jié)點(diǎn)的點(diǎn)云數(shù)據(jù)塊建立的,通過(guò)模型點(diǎn)云的八叉樹(shù)和KD樹(shù)多層索引可以快速定位p的最近點(diǎn)所在的數(shù)據(jù)塊,可以避免搜索所有點(diǎn)。最近點(diǎn)的搜索過(guò)程分為兩步:第一步搜索全局索引層,通過(guò)搜索模型點(diǎn)云八叉樹(shù),定位最近點(diǎn)所在的點(diǎn)云數(shù)據(jù)塊,即找到包含最近點(diǎn)的八叉樹(shù)葉子結(jié)點(diǎn);第二步,根據(jù)八叉樹(shù)葉子結(jié)點(diǎn)中存儲(chǔ)的信息找到對(duì)應(yīng)的KD樹(shù)根結(jié)點(diǎn),即存儲(chǔ)局部數(shù)據(jù)塊的KD樹(shù),然后在局部點(diǎn)云數(shù)據(jù)塊中搜索最近鄰域點(diǎn)。

    影響KD樹(shù)最近鄰搜索效率的主要因素是回溯,八叉樹(shù)結(jié)點(diǎn)存儲(chǔ)了相關(guān)的數(shù)據(jù)信息,不需要回溯就可以定位包含最近鄰域點(diǎn)的局部點(diǎn)云塊。八叉樹(shù)中的每一個(gè)結(jié)點(diǎn)都對(duì)應(yīng)一個(gè)空間包圍盒,根據(jù)待配準(zhǔn)點(diǎn)坐標(biāo)pi(xi,yi,zi)與包圍盒的空間位置和大小,確定需要繼續(xù)搜索的八叉樹(shù)葉子結(jié)點(diǎn)。設(shè)最近鄰域點(diǎn)qj(xj,yj,zj)所在子立方體的空間索引值為(a,b,c),與子立方體對(duì)應(yīng)的結(jié)點(diǎn)的八進(jìn)制編碼為q=qn-1…qj…q1q0,qj(j=0, 1, … ,n-1 )表示葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑。根據(jù)式(1)可以得到八叉樹(shù)中最近鄰域點(diǎn)所在子立方體的全局索引值。

    (1)

    在局部KD樹(shù)搜索最近鄰域點(diǎn)時(shí),對(duì)于位于分割子體邊界上的點(diǎn),搜索的結(jié)果有可能是錯(cuò)誤的,可以將邊界點(diǎn)作為噪聲點(diǎn)處理,由于點(diǎn)云數(shù)據(jù)量巨大,這樣處理提高了配準(zhǔn)速度,而對(duì)精度沒(méi)有太大的影響。研究表明,如果允許有少量錯(cuò)誤的搜索結(jié)果,KD樹(shù)的搜索效率會(huì)得到很大的提高[10]。

    改進(jìn)算法利用歐氏距離閾值剔除噪聲點(diǎn)[15]。通過(guò)模型點(diǎn)云八叉樹(shù)葉子結(jié)點(diǎn)關(guān)聯(lián)的KD樹(shù),搜索與點(diǎn)pi歐式距離最近的3個(gè)點(diǎn)s1,s2和s3;若pi與s1,s2,s3構(gòu)成的平面的距離超出閾值E,則剔除該對(duì)應(yīng)點(diǎn);否則,以這3個(gè)點(diǎn)中距離pi最近的點(diǎn)sj作為對(duì)應(yīng)點(diǎn)。閾值為E=c*d,其中c為控制系數(shù),d為點(diǎn)云中相鄰點(diǎn)間的平均距離。此外,邊界噪聲點(diǎn)也有可能形成多個(gè)對(duì)應(yīng)點(diǎn)對(duì),可以比較兩組對(duì)應(yīng)點(diǎn)對(duì)p1和q1,p2和q2,若出現(xiàn)式(2)情況,即它們之間的差超過(guò)F,則視為噪聲點(diǎn),也予以剔除。

    |dist(p1-p2)-dist(q1-q2)|≥F.

    (2)

    利用歐氏距離閾值雖然剔除了大量的噪聲點(diǎn),但對(duì)應(yīng)點(diǎn)對(duì)仍然存在噪聲點(diǎn)??紤]到待配準(zhǔn)點(diǎn)云和模型點(diǎn)云雖然處于不同的坐標(biāo)系,但其空間拓?fù)潢P(guān)系應(yīng)該一致,點(diǎn)云之間除了有平移量,還有旋轉(zhuǎn)量。因此,對(duì)匹配點(diǎn)對(duì)的法向量夾角設(shè)置一個(gè)閾值,以進(jìn)一步剔除錯(cuò)誤的點(diǎn)對(duì)。

    (3)

    應(yīng)用最小二乘法,可以得到以下3*3矩陣A。

    (4)

    可以證明,A的最小特征值對(duì)應(yīng)的特征向量即可作為法向量ni的近似值。

    通過(guò)以上方法得到兩個(gè)對(duì)應(yīng)點(diǎn)集中各點(diǎn)的法向量。對(duì)于任意對(duì)應(yīng)點(diǎn)對(duì)pi和qj,它們的法向量分別為ni和nj。兩者的法向量差別越大,夾角的余弦值越小,即ni·nj就越小。因此,根據(jù)式(5)對(duì)向量夾角余弦設(shè)置閾值,即將法向量的乘積小于G的點(diǎn)對(duì)視為噪聲點(diǎn),予以剔除。

    ni·nj≥G.

    (5)

    2.3 算法步驟

    改進(jìn)的點(diǎn)云配準(zhǔn)算法的主要步驟如下:

    1)針對(duì)模型點(diǎn)云Q建立八叉樹(shù)與KD樹(shù)多層索引結(jié)構(gòu)。

    2)迭代初始化:選擇初始目標(biāo)點(diǎn)集P0=P,設(shè)定最大迭代次數(shù)Kmax,給定法向閾值V。

    3)根據(jù)待配準(zhǔn)點(diǎn)云Pk中的每個(gè)點(diǎn)pi的坐標(biāo)pi(xi,yi,zi)和八叉樹(shù)子立方體包圍盒的空間位置及大小(x,y,z,l),在八叉樹(shù)中定位最近點(diǎn)qi所在的葉子結(jié)點(diǎn)。

    4)通過(guò)八叉樹(shù)的葉子結(jié)點(diǎn)找到包含局部點(diǎn)云的KD樹(shù),基于KD樹(shù)搜尋數(shù)據(jù)點(diǎn)集Pk中每一個(gè)點(diǎn)pi的最近點(diǎn),得到對(duì)應(yīng)點(diǎn)集Qk。

    5)利用歐氏距離閾值和點(diǎn)對(duì)距離差值剔除部分噪聲點(diǎn)。

    6)根據(jù)法向量閾值剔除錯(cuò)誤的匹配點(diǎn)對(duì)。

    7)利用四元數(shù)法對(duì)式(6)進(jìn)行最小化,求出旋轉(zhuǎn)矩陣Rk和平移矢量Tk。

    (6)

    8)根據(jù)旋轉(zhuǎn)矩陣Rk和平移矢量Tk得到新的數(shù)據(jù)點(diǎn)集:Pk+1=RkPk+Tk。

    9)R=RkR,T=RkT+Tk,重復(fù)進(jìn)行步驟3)~8),直至前一次最近點(diǎn)之間的距離與后一次最近點(diǎn)之間的距離滿足條件:dk-dk+1

    10)利用變換矩陣參數(shù)R和T將初始目標(biāo)點(diǎn)云數(shù)據(jù)變換到參考點(diǎn)云所在的坐標(biāo)系,完成點(diǎn)云數(shù)據(jù)的配準(zhǔn)。

    設(shè)模型點(diǎn)云Q有N個(gè)數(shù)據(jù)點(diǎn),待配準(zhǔn)點(diǎn)云P有M個(gè)數(shù)據(jù)點(diǎn),模型點(diǎn)集中數(shù)據(jù)點(diǎn)的總數(shù)N與八叉樹(shù)一個(gè)葉子結(jié)點(diǎn)包含的數(shù)據(jù)點(diǎn)之比為K(分割參數(shù)),模型點(diǎn)云八叉樹(shù)深度為h??梢运愠?,八叉樹(shù)每個(gè)葉子結(jié)點(diǎn)包含的點(diǎn)數(shù)為N/K,葉子結(jié)點(diǎn)數(shù)為K,將八叉樹(shù)簡(jiǎn)化為滿八叉樹(shù)處理,可以計(jì)算出八叉樹(shù)深度為

    h≥|log8K|+1.

    (7)

    對(duì)于有M個(gè)數(shù)據(jù)點(diǎn)的待配準(zhǔn)點(diǎn)云P,對(duì)應(yīng)八叉樹(shù)的搜索時(shí)間為O(Mlog8K);在局部模型點(diǎn)云塊KD樹(shù)中搜索最近點(diǎn),時(shí)間為O(Mlog2(N/K))。因此,搜索最近鄰的總時(shí)間為

    O(Mlog8K+O(Mlog2(N/K)).

    (8)

    研究表明[14],在實(shí)例隨機(jī)分布的情況下,KD樹(shù)最近鄰的深度優(yōu)先搜索的時(shí)間為O(Mlog2N),在最差回溯情況下的時(shí)間為O(3MN2/3)。因此,在保證配準(zhǔn)精度的前提下,選擇合適的K值,滿足式(9)就能保證改進(jìn)后的算法優(yōu)于隨機(jī)條件下的傳統(tǒng)KD樹(shù)最近鄰搜索算法。

    Mlog8K+Mlog2N/K

    (9)

    即:

    log8K

    (10)

    顯然很容易滿足上述算式,分割參數(shù)K越大,即點(diǎn)云模型分割越細(xì),時(shí)間效率越高,當(dāng)然,前提是需要保證配準(zhǔn)的精度。

    3 實(shí)驗(yàn)與分析

    為了驗(yàn)證改進(jìn)算法的正確性和有效性,分別選擇了三組點(diǎn)云模型進(jìn)行配準(zhǔn)實(shí)驗(yàn)。實(shí)驗(yàn)的系統(tǒng)環(huán)境為內(nèi)存4G、Window7操作系統(tǒng),軟件為MATLAB R2014a。第一組實(shí)驗(yàn)選擇經(jīng)典的Bunny模型,圖2(a)為配準(zhǔn)前的點(diǎn)云(灰色部分表示模型點(diǎn)云,黑色部分表示待配準(zhǔn)點(diǎn)云),待配準(zhǔn)點(diǎn)云包含10 753個(gè)點(diǎn)。圖2(b)為傳統(tǒng)ICP算法的配準(zhǔn)結(jié)果,平均配準(zhǔn)時(shí)間為26.588 s。圖2(c)為本文改進(jìn)算法的配準(zhǔn)結(jié)果,平均配準(zhǔn)時(shí)間為9.695 s。實(shí)驗(yàn)結(jié)果顯示,采用本文提出的改進(jìn)算法,配準(zhǔn)速度大大提高,同時(shí)配準(zhǔn)精度得到改善。

    圖2 Bunny模型配準(zhǔn)

    第2組實(shí)驗(yàn)采用David 3D三維掃描儀,從兩個(gè)不同角度分別對(duì)一個(gè)瓶子模型進(jìn)行掃描,對(duì)獲得的兩個(gè)點(diǎn)云模型先粗配準(zhǔn)再精配準(zhǔn)。圖3(a)為精配準(zhǔn)前的點(diǎn)云,待配準(zhǔn)點(diǎn)云包含2 473個(gè)點(diǎn)。圖3(b)為傳統(tǒng)ICP算法的配準(zhǔn)結(jié)果,平均配準(zhǔn)時(shí)間為3.785 s。圖3(c)為本文改進(jìn)算法的配準(zhǔn)結(jié)果,平均配準(zhǔn)時(shí)間為2.327s。第3組實(shí)驗(yàn)采用Cat模型,圖4(a)為配準(zhǔn)前的點(diǎn)云,待配準(zhǔn)點(diǎn)云包含21 530個(gè)點(diǎn)。圖4(b)為傳統(tǒng)ICP算法的配準(zhǔn)結(jié)果,平均配準(zhǔn)時(shí)間為87. 829 s。圖4(c)為本文改進(jìn)算法的配準(zhǔn)結(jié)果,平均配準(zhǔn)時(shí)間為22.451 s。

    對(duì)于不同規(guī)模的點(diǎn)云模型分別采用傳統(tǒng)ICP算法、文獻(xiàn)[15]提出的算法和本文提出的改進(jìn)算法進(jìn)行配準(zhǔn),不同規(guī)模點(diǎn)云情況下3種算法的配準(zhǔn)時(shí)間如表1所示,3種算法的配準(zhǔn)精度如表2所示。可以看出,本文首先利用八叉樹(shù)對(duì)空間進(jìn)行分割,建立局部KD樹(shù)索引,有效減少最近鄰搜索時(shí)間,使算法的效率有較大的提高,并且在精度上有較好的改善。在數(shù)據(jù)量非常大的海量點(diǎn)云情況下,降低配準(zhǔn)時(shí)間的效果更加明顯。

    圖3 杯子模型配準(zhǔn)

    圖4 Cat模型配準(zhǔn)

    表1 不同數(shù)據(jù)規(guī)模點(diǎn)云配準(zhǔn)的時(shí)間比較

    表2 不同數(shù)據(jù)規(guī)模點(diǎn)云配準(zhǔn)的精度比較

    為了分析分割參數(shù)K對(duì)最近鄰搜索效率和配準(zhǔn)精度的影響,分別采用有5 456、10 753、21 530個(gè)點(diǎn)的點(diǎn)云模型進(jìn)行實(shí)驗(yàn)。圖5所示是不同分割參數(shù)K對(duì)最近鄰搜索時(shí)間的影響,圖6所示是不同分割參數(shù)K對(duì)配準(zhǔn)精度的影響。顯然,K越大,搜索效率越高,但誤差越大。對(duì)于不同形狀的三維點(diǎn)云模型,通過(guò)反復(fù)實(shí)驗(yàn)和分析,可以得到接近于最佳效率和精度的分割參數(shù)K值。

    圖5 分割參數(shù)K對(duì)搜索時(shí)間的影響

    圖6 分割參數(shù)K對(duì)配準(zhǔn)精度的影響

    4 結(jié)束語(yǔ)

    本文對(duì)ICP及其改進(jìn)的點(diǎn)云配準(zhǔn)算法進(jìn)行深入研究,針對(duì)大規(guī)模點(diǎn)云數(shù)據(jù)配準(zhǔn)KD樹(shù)查詢效率較低的問(wèn)題,提出一種基于八叉樹(shù)與KD樹(shù)索引的點(diǎn)云精配準(zhǔn)方法。利用八叉樹(shù)空間結(jié)構(gòu)特點(diǎn)和KD樹(shù)搜索特性,采用歐氏距離閾值、點(diǎn)對(duì)距離差值和法向量閾值剔除錯(cuò)誤點(diǎn)對(duì)。將索引代價(jià)較小的全局八叉樹(shù)與高效的局部KD樹(shù)相關(guān)聯(lián),在保證滿足配準(zhǔn)精度的前提下,能夠不同程度提高配準(zhǔn)算法的時(shí)間效率,特別適合于較大規(guī)模的點(diǎn)云模型的配準(zhǔn)。通過(guò)算法分析和實(shí)驗(yàn)可以看到,在實(shí)際應(yīng)用中,設(shè)置合適的模型點(diǎn)云分割參數(shù),是影響改進(jìn)算法配準(zhǔn)效率和精度的關(guān)鍵。

    [1] XIE J, HSU Y F, FERIS R S, et al. Fine registration of 3D point clouds fusing structural and photometric information using an RGB-D camera[J]. Journal of Visual Communication & Image Representation, 2015, 32:194-204.

    [2] BESL P J, MCKAY N D. A method for registration of 3-d shapes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(2): 239-256.

    [3] 劉豐華. 復(fù)雜模型三維點(diǎn)云自動(dòng)配準(zhǔn)技術(shù)的研究[D]. 天津:天津大學(xué),2013.

    [4] LIU Z X,AN J,JING Y. A simple and robust feature point matching algorithm based on restricted spatial order constraints for aerial image registration[J]. IEEE Transactions on Geoscience and Remote Sensing, 2012, 50(2): 514-527.

    [5] 劉江,張旭,朱繼文. 一種基于K-D樹(shù)優(yōu)化的ICP三維點(diǎn)云配準(zhǔn)方法[J]. 測(cè)繪工程, 2016, 25(6): 15-18.

    [6] MULCHRONE K F. Application of delaunay triangulation to the near_est neighbor method of strain analysis[J]. Journal of Structural Geology, 2003, 25(5): 689-702.

    [7] 何婧,吳躍,楊帆,等. 基于KD樹(shù)和R樹(shù)的多維云數(shù)據(jù)索引[J]. 計(jì)算機(jī)應(yīng)用,2014,34(11):3218-3221.

    [8] 楊建思. 一種四叉樹(shù)與KD樹(shù)結(jié)合的海量機(jī)載LiDAR數(shù)據(jù)組織管理方法[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版),2014,39(8): 918-922.

    [9] WANG Yujian, TAN Shaowei, DONG Weiwei, et al. Research on 3D modeling method based on hybrid octree structure[J]. The Open Electrical & Electronic Engineering Journal, 2014, 8: 323-329.

    [10] ARYA S, MOUNT D M, NETANYAHU N S, et al. An optimal algorithm for approximate nearest neighbor searching fixed dimensions[J]. Journal of the ACM, 1998, 45(6): 891-923.

    [11] 鄭明玲, 許柯, 劉衡竹, 等. 基于重疊區(qū)域的高性能近似KD樹(shù)算法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2015, 27(6): 1053-1059.

    [12] 韋盛斌, 王少卿, 周常河, 等. 用于三維重建的點(diǎn)云單應(yīng)性迭代最近點(diǎn)配準(zhǔn)算法[J]. 光學(xué)學(xué)報(bào), 2015, 35(5): 31-37.

    [13] LIAW Y C, LEOU M L, WU C M. Fast exact k nearest neighbors search using an orthogonal search tree[J]. Pattern Recognition, 2010, 43(6): 2351-2358.

    [14] 祝繼華, 尹俊, 邗汶鋅, 等. 面向低維點(diǎn)集配準(zhǔn)的高效最近鄰搜索法[J]. 模式識(shí)別與人工智能, 2014, 27(12): 1071-1077.

    [15] 鐘瑩, 張蒙. 基于改進(jìn)ICP算法的點(diǎn)云自動(dòng)配準(zhǔn)技術(shù)[J]. 控制工程, 2014, 21(1):37-40.

    [16] 李聰波,肖衛(wèi)洪,杜彥斌,等. 基于改進(jìn)ICP算法的損傷零部件精確配準(zhǔn)方法[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2016, 22(4):1021-1028.

    [責(zé)任編輯:張德福]

    Point cloud registration based on octree and KD-tree index

    WANG Yujian, LIAN Tengfei,WU Mingming,GAO Qian

    (School of Information, Beijing Union University, Beijing 100101, China)

    A multilayer index structure based on octree and KD tree is reported for low query efficiency problems in multi-dimensional queries of KD tree. First, the octree global index for model point cloud is established. Then, the local data KD-tree indexes are built in the octree leave nodes. To improve the traditional Iterative Closest Point algorithm, the local point cloud data is quickly located based on the global index of leave nodes. Using the local KD tree indexes, the searching speed of closest point is sped up. Part of the noise points are removed by the euclidean distance threshold, the difference of interval of point pair and the normals threshold. Experimental result indicates that the proposed method can improve the efficiency and accuracy of registration.

    point cloud registration; octree; KD-tree; ICP algorithm

    2016-12-20

    國(guó)家自然科學(xué)基金資助項(xiàng)目(61271369)

    王育堅(jiān)(1963-),男,教授.

    廉騰飛(1991-),女,碩士研究生.

    著錄:王育堅(jiān),廉騰飛,吳明明,等.基于八叉樹(shù)與KD樹(shù)索引的點(diǎn)云配準(zhǔn)方法[J].測(cè)繪工程,2017,26(8):35-40.

    10.19349/j.cnki.issn1006-7949.2017.08.008

    TP391

    A

    1006-7949(2017)08-0035-06

    猜你喜歡
    八叉樹(shù)立方體結(jié)點(diǎn)
    疊出一個(gè)立方體
    三維十字鏈表八叉樹(shù)的高效檢索實(shí)現(xiàn)
    Ladyzhenskaya流體力學(xué)方程組的確定模與確定結(jié)點(diǎn)個(gè)數(shù)估計(jì)
    圖形前線
    立方體星交會(huì)對(duì)接和空間飛行演示
    太空探索(2016年9期)2016-07-12 09:59:53
    折紙
    基于Raspberry PI為結(jié)點(diǎn)的天氣云測(cè)量網(wǎng)絡(luò)實(shí)現(xiàn)
    散亂點(diǎn)云線性八叉樹(shù)結(jié)構(gòu)在GPU中的實(shí)現(xiàn)
    基于密集型區(qū)域的八叉樹(shù)劃分算法
    科技傳播(2012年2期)2012-06-13 10:03:26
    一種基于GPU實(shí)現(xiàn)的自適應(yīng)八叉樹(shù)紋理繪畫算法
    如何舔出高潮| 欧美激情在线99| 久久久精品欧美日韩精品| 国产精品久久久久久av不卡| 久久国内精品自在自线图片| 成人性生交大片免费视频hd| 嫩草影院入口| 卡戴珊不雅视频在线播放| 亚洲五月天丁香| 日韩欧美精品免费久久| 亚洲最大成人手机在线| 日本欧美国产在线视频| 久久国内精品自在自线图片| 人妻少妇偷人精品九色| 亚洲成人久久爱视频| 51国产日韩欧美| 麻豆乱淫一区二区| 成人亚洲精品av一区二区| 亚洲天堂国产精品一区在线| 国产精品野战在线观看| 日韩欧美在线乱码| 女的被弄到高潮叫床怎么办| 欧美xxxx性猛交bbbb| 99热这里只有是精品在线观看| 久久精品久久久久久久性| 国产69精品久久久久777片| 成人鲁丝片一二三区免费| 国产一级毛片在线| 午夜福利成人在线免费观看| 欧美高清性xxxxhd video| 国产精品久久久久久久久免| 秋霞在线观看毛片| 色5月婷婷丁香| 男人舔奶头视频| 国产一区二区亚洲精品在线观看| 国产麻豆成人av免费视频| 成人综合一区亚洲| 亚洲欧美精品自产自拍| 99在线人妻在线中文字幕| 亚洲四区av| 久久人妻av系列| 欧美日韩综合久久久久久| 日本wwww免费看| 国产免费视频播放在线视频 | 国产69精品久久久久777片| 国产精品人妻久久久久久| 日韩欧美 国产精品| 亚洲国产欧洲综合997久久,| 水蜜桃什么品种好| 啦啦啦韩国在线观看视频| av.在线天堂| 亚州av有码| 午夜免费激情av| 国产 一区 欧美 日韩| 美女脱内裤让男人舔精品视频| 日韩精品有码人妻一区| 国语对白做爰xxxⅹ性视频网站| 别揉我奶头 嗯啊视频| 三级经典国产精品| 日韩欧美三级三区| 日本一二三区视频观看| 久久这里有精品视频免费| ponron亚洲| 色哟哟·www| 国产人妻一区二区三区在| 一级毛片aaaaaa免费看小| 1000部很黄的大片| 国产精品精品国产色婷婷| 三级国产精品片| 亚洲无线观看免费| 国产一区二区三区av在线| 我要搜黄色片| 女的被弄到高潮叫床怎么办| 中文亚洲av片在线观看爽| 亚洲一级一片aⅴ在线观看| 性色avwww在线观看| av在线老鸭窝| 身体一侧抽搐| 久久久久久国产a免费观看| 热99re8久久精品国产| 亚洲精华国产精华液的使用体验| 婷婷色麻豆天堂久久 | 三级经典国产精品| 国产亚洲91精品色在线| 国产视频内射| 看免费成人av毛片| 亚州av有码| 亚洲国产色片| 国产成人午夜福利电影在线观看| 哪个播放器可以免费观看大片| 69人妻影院| 免费黄网站久久成人精品| 一个人看的www免费观看视频| 免费av毛片视频| 亚洲综合精品二区| 精品国内亚洲2022精品成人| 久久99精品国语久久久| 久久99热这里只频精品6学生 | 22中文网久久字幕| 免费av毛片视频| 三级男女做爰猛烈吃奶摸视频| 18禁在线无遮挡免费观看视频| 岛国在线免费视频观看| 亚洲精品影视一区二区三区av| 三级国产精品片| 中文字幕制服av| 一本久久精品| 寂寞人妻少妇视频99o| 亚洲av二区三区四区| 身体一侧抽搐| 男女下面进入的视频免费午夜| 99在线人妻在线中文字幕| 狠狠狠狠99中文字幕| 2021少妇久久久久久久久久久| 国产单亲对白刺激| 在线播放国产精品三级| 免费av观看视频| 国产精品1区2区在线观看.| 男女啪啪激烈高潮av片| 亚洲伊人久久精品综合 | 亚洲综合精品二区| 国产麻豆成人av免费视频| 日韩在线高清观看一区二区三区| 搡女人真爽免费视频火全软件| 午夜免费激情av| 99热精品在线国产| 精华霜和精华液先用哪个| 天天躁日日操中文字幕| 看片在线看免费视频| 亚洲成人精品中文字幕电影| 97热精品久久久久久| 夜夜爽夜夜爽视频| 哪个播放器可以免费观看大片| 18禁在线无遮挡免费观看视频| 国产成人a区在线观看| 国产爱豆传媒在线观看| 亚洲欧美日韩卡通动漫| 欧美一级a爱片免费观看看| 亚洲激情五月婷婷啪啪| 一级二级三级毛片免费看| 成人二区视频| .国产精品久久| 欧美精品国产亚洲| 免费看日本二区| 国产黄片美女视频| 久久精品影院6| 国产片特级美女逼逼视频| 日韩在线高清观看一区二区三区| 精品一区二区免费观看| 久久精品国产亚洲网站| 亚洲中文字幕日韩| 狂野欧美激情性xxxx在线观看| 晚上一个人看的免费电影| 精品不卡国产一区二区三区| 国产一区二区在线av高清观看| 超碰97精品在线观看| 看十八女毛片水多多多| 成人特级av手机在线观看| 国产v大片淫在线免费观看| 小说图片视频综合网站| 欧美一区二区亚洲| 亚洲在线自拍视频| 91av网一区二区| 午夜老司机福利剧场| 99热精品在线国产| 亚洲欧美成人综合另类久久久 | 婷婷色麻豆天堂久久 | 91久久精品电影网| 天天躁日日操中文字幕| 中文资源天堂在线| 久久亚洲精品不卡| 简卡轻食公司| 亚洲最大成人中文| 亚洲精品乱久久久久久| 少妇熟女欧美另类| 熟女电影av网| 听说在线观看完整版免费高清| 蜜桃久久精品国产亚洲av| 亚洲av日韩在线播放| 听说在线观看完整版免费高清| 国产久久久一区二区三区| 国产女主播在线喷水免费视频网站 | 日日啪夜夜撸| 亚洲精品国产av成人精品| 中文字幕av在线有码专区| 26uuu在线亚洲综合色| 久久久色成人| 免费看光身美女| 久久久久久伊人网av| 国产精品久久久久久精品电影小说 | 亚洲美女视频黄频| 亚洲欧美日韩高清专用| 国产精品国产高清国产av| 最近最新中文字幕免费大全7| 狂野欧美白嫩少妇大欣赏| 少妇高潮的动态图| 国产一区二区在线av高清观看| 嘟嘟电影网在线观看| 欧美日韩一区二区视频在线观看视频在线 | 中国美白少妇内射xxxbb| 国产精品久久久久久精品电影| 亚洲欧美一区二区三区国产| 成人亚洲欧美一区二区av| a级毛片免费高清观看在线播放| 欧美成人免费av一区二区三区| 夜夜看夜夜爽夜夜摸| 一级二级三级毛片免费看| 中文字幕人妻熟人妻熟丝袜美| 午夜日本视频在线| 精品欧美国产一区二区三| 国产免费男女视频| 久久久久久大精品| 国产高清三级在线| 哪个播放器可以免费观看大片| 亚洲四区av| 国产探花极品一区二区| 亚洲av成人av| 日本三级黄在线观看| 日韩精品青青久久久久久| 亚洲婷婷狠狠爱综合网| 日韩国内少妇激情av| 天堂√8在线中文| 国产一级毛片在线| 2022亚洲国产成人精品| 在线免费十八禁| 欧美不卡视频在线免费观看| 欧美一区二区亚洲| 天堂av国产一区二区熟女人妻| 搡女人真爽免费视频火全软件| 51国产日韩欧美| 在线观看66精品国产| 国产一区二区亚洲精品在线观看| 久久久久久久亚洲中文字幕| 日韩制服骚丝袜av| 久久精品国产99精品国产亚洲性色| 大话2 男鬼变身卡| 最后的刺客免费高清国语| 国产亚洲精品av在线| 亚洲一级一片aⅴ在线观看| 久久久国产成人精品二区| 麻豆久久精品国产亚洲av| 亚洲欧美日韩卡通动漫| 亚洲,欧美,日韩| 97超视频在线观看视频| 成人无遮挡网站| 色尼玛亚洲综合影院| 青春草视频在线免费观看| 日韩强制内射视频| 日韩成人av中文字幕在线观看| 国内精品宾馆在线| 国产又黄又爽又无遮挡在线| 午夜福利在线观看免费完整高清在| 日韩欧美三级三区| 熟女人妻精品中文字幕| 亚洲人成网站在线观看播放| 只有这里有精品99| 69人妻影院| 内地一区二区视频在线| 99视频精品全部免费 在线| 国产精品人妻久久久影院| 精品人妻熟女av久视频| kizo精华| 黄片无遮挡物在线观看| 男女视频在线观看网站免费| 夜夜爽夜夜爽视频| 亚州av有码| 成人亚洲精品av一区二区| 日韩精品青青久久久久久| 免费观看的影片在线观看| 国内精品一区二区在线观看| 美女xxoo啪啪120秒动态图| 精品久久久噜噜| 国内揄拍国产精品人妻在线| 国产精品蜜桃在线观看| 日日啪夜夜撸| 午夜爱爱视频在线播放| 国产一级毛片七仙女欲春2| 日日摸夜夜添夜夜爱| 欧美变态另类bdsm刘玥| 久久久久久久久久黄片| 精品久久久久久久久久久久久| 国产三级在线视频| 国产乱来视频区| 亚洲av日韩在线播放| 国产精品久久视频播放| 国产白丝娇喘喷水9色精品| 嫩草影院精品99| 夜夜爽夜夜爽视频| 久久久久久伊人网av| 亚洲欧美精品综合久久99| 汤姆久久久久久久影院中文字幕 | a级毛色黄片| 亚洲欧美精品自产自拍| 2021少妇久久久久久久久久久| 三级经典国产精品| 少妇猛男粗大的猛烈进出视频 | 成人一区二区视频在线观看| 97超视频在线观看视频| 99久久人妻综合| av国产免费在线观看| 秋霞在线观看毛片| 日韩一本色道免费dvd| 午夜福利视频1000在线观看| 夜夜看夜夜爽夜夜摸| 毛片一级片免费看久久久久| 国产白丝娇喘喷水9色精品| 综合色丁香网| 在线播放无遮挡| 床上黄色一级片| 国产色爽女视频免费观看| 国产精品av视频在线免费观看| 色视频www国产| 日韩人妻高清精品专区| 51国产日韩欧美| 麻豆久久精品国产亚洲av| 午夜免费激情av| 波野结衣二区三区在线| 午夜福利在线观看吧| 亚洲最大成人中文| 日日摸夜夜添夜夜爱| 精品少妇黑人巨大在线播放 | 亚洲成色77777| 校园人妻丝袜中文字幕| 尾随美女入室| 中文字幕熟女人妻在线| 赤兔流量卡办理| 国产男人的电影天堂91| 国产色婷婷99| 日韩三级伦理在线观看| 尤物成人国产欧美一区二区三区| 亚洲怡红院男人天堂| 中文字幕亚洲精品专区| 国产一区二区在线观看日韩| 成人亚洲精品av一区二区| 成人三级黄色视频| 亚洲精品456在线播放app| 亚洲精品,欧美精品| 99热全是精品| 国产三级中文精品| 少妇熟女欧美另类| 欧美日本亚洲视频在线播放| 桃色一区二区三区在线观看| 人人妻人人澡欧美一区二区| 啦啦啦啦在线视频资源| 97人妻精品一区二区三区麻豆| 啦啦啦啦在线视频资源| 亚洲成人中文字幕在线播放| 中文字幕制服av| 精品久久久久久久久亚洲| 久久精品国产99精品国产亚洲性色| 亚洲精品,欧美精品| 麻豆乱淫一区二区| av播播在线观看一区| 国产精品一二三区在线看| 亚洲激情五月婷婷啪啪| a级毛色黄片| 欧美又色又爽又黄视频| 亚洲一区高清亚洲精品| 久久国产乱子免费精品| 精品久久久久久成人av| 久久久成人免费电影| 国产精品永久免费网站| www.色视频.com| 久久久久久久久久久丰满| 国产伦精品一区二区三区视频9| 亚洲久久久久久中文字幕| 久久久久精品久久久久真实原创| 内地一区二区视频在线| 美女国产视频在线观看| 建设人人有责人人尽责人人享有的 | 欧美成人免费av一区二区三区| 尾随美女入室| 久久人人爽人人爽人人片va| 中文字幕亚洲精品专区| av在线亚洲专区| 一级毛片电影观看 | av在线蜜桃| 青春草亚洲视频在线观看| 成人美女网站在线观看视频| 久久精品人妻少妇| 成人无遮挡网站| 欧美人与善性xxx| 亚洲最大成人av| 国产成人a区在线观看| 97人妻精品一区二区三区麻豆| 麻豆乱淫一区二区| 精品熟女少妇av免费看| 亚洲精品影视一区二区三区av| 人人妻人人看人人澡| av又黄又爽大尺度在线免费看 | 亚洲国产日韩欧美精品在线观看| 久久精品夜夜夜夜夜久久蜜豆| 在线免费十八禁| 成人高潮视频无遮挡免费网站| 天堂√8在线中文| 蜜桃久久精品国产亚洲av| 国产三级中文精品| 美女cb高潮喷水在线观看| 久久精品国产亚洲av涩爱| 九色成人免费人妻av| 直男gayav资源| 国产一区二区三区av在线| 国产精品久久久久久精品电影小说 | 人妻制服诱惑在线中文字幕| 国产精品日韩av在线免费观看| 在线播放国产精品三级| 亚洲国产高清在线一区二区三| 黑人高潮一二区| 国产色爽女视频免费观看| 亚洲av成人av| 亚洲精华国产精华液的使用体验| 免费观看性生交大片5| 看黄色毛片网站| 欧美精品国产亚洲| 成人无遮挡网站| 91精品伊人久久大香线蕉| 婷婷色av中文字幕| 亚洲第一区二区三区不卡| 69av精品久久久久久| 中文字幕av在线有码专区| 日本wwww免费看| 欧美成人免费av一区二区三区| 国产三级在线视频| 水蜜桃什么品种好| 亚洲第一区二区三区不卡| 有码 亚洲区| 天堂影院成人在线观看| 搡女人真爽免费视频火全软件| 水蜜桃什么品种好| 欧美三级亚洲精品| av视频在线观看入口| 黄色日韩在线| 美女cb高潮喷水在线观看| 成人毛片a级毛片在线播放| 精品无人区乱码1区二区| 日韩欧美精品v在线| 午夜福利成人在线免费观看| 在线免费观看的www视频| 黄色欧美视频在线观看| 成人漫画全彩无遮挡| 伊人久久精品亚洲午夜| 精品久久久久久久末码| 成人毛片60女人毛片免费| 精品无人区乱码1区二区| 97人妻精品一区二区三区麻豆| 别揉我奶头 嗯啊视频| 美女黄网站色视频| 午夜免费男女啪啪视频观看| 国产高清有码在线观看视频| 精品不卡国产一区二区三区| 国产人妻一区二区三区在| 汤姆久久久久久久影院中文字幕 | 性插视频无遮挡在线免费观看| 久久精品91蜜桃| 51国产日韩欧美| 国产 一区精品| 亚洲图色成人| 亚洲熟妇中文字幕五十中出| 日韩欧美在线乱码| 少妇猛男粗大的猛烈进出视频 | 欧美最新免费一区二区三区| av女优亚洲男人天堂| 国模一区二区三区四区视频| 我要看日韩黄色一级片| 国产一区有黄有色的免费视频 | 久久久久免费精品人妻一区二区| 中文字幕熟女人妻在线| 美女被艹到高潮喷水动态| 一级毛片电影观看 | av在线观看视频网站免费| 久久久久九九精品影院| www.av在线官网国产| 男女国产视频网站| 小蜜桃在线观看免费完整版高清| 91久久精品国产一区二区三区| 午夜免费男女啪啪视频观看| 男女国产视频网站| 国产精品不卡视频一区二区| 成人特级av手机在线观看| 亚洲丝袜综合中文字幕| 又粗又硬又长又爽又黄的视频| 丝袜喷水一区| 色吧在线观看| 国产成人a区在线观看| 国产av不卡久久| 国产又黄又爽又无遮挡在线| 日本色播在线视频| 免费看av在线观看网站| 久久久午夜欧美精品| 好男人在线观看高清免费视频| 国产高清不卡午夜福利| 国产精品久久视频播放| 国产精品1区2区在线观看.| av卡一久久| 国产白丝娇喘喷水9色精品| 狠狠狠狠99中文字幕| 国产伦理片在线播放av一区| 舔av片在线| 中文字幕av在线有码专区| 91在线精品国自产拍蜜月| 在线观看66精品国产| av女优亚洲男人天堂| 人人妻人人澡欧美一区二区| 国产在视频线在精品| 一级毛片电影观看 | 中文精品一卡2卡3卡4更新| 国产伦一二天堂av在线观看| 久久午夜福利片| 久久精品人妻少妇| 别揉我奶头 嗯啊视频| 男女边吃奶边做爰视频| 女人久久www免费人成看片 | 国产一区二区在线观看日韩| 国产探花在线观看一区二区| 岛国在线免费视频观看| 成人毛片60女人毛片免费| 蜜桃亚洲精品一区二区三区| 亚洲国产欧洲综合997久久,| 日本熟妇午夜| 1024手机看黄色片| 精华霜和精华液先用哪个| 国产免费又黄又爽又色| 一夜夜www| 免费观看在线日韩| 又爽又黄无遮挡网站| 亚洲精品乱久久久久久| 熟妇人妻久久中文字幕3abv| 国产精品熟女久久久久浪| 91av网一区二区| 国产免费又黄又爽又色| 最近中文字幕高清免费大全6| 天堂中文最新版在线下载 | 日本爱情动作片www.在线观看| 全区人妻精品视频| 久久精品久久久久久久性| 免费不卡的大黄色大毛片视频在线观看 | 欧美激情国产日韩精品一区| 久久国内精品自在自线图片| 国产 一区精品| 国产色婷婷99| 69av精品久久久久久| 久久久久久九九精品二区国产| 国产91av在线免费观看| 国产一区二区亚洲精品在线观看| 亚洲av二区三区四区| 午夜激情福利司机影院| 国产成人免费观看mmmm| 国产伦在线观看视频一区| 大香蕉97超碰在线| 哪个播放器可以免费观看大片| 欧美97在线视频| 一二三四中文在线观看免费高清| ponron亚洲| 久久精品国产亚洲av天美| 男女国产视频网站| 美女脱内裤让男人舔精品视频| 久久精品国产亚洲网站| 日韩欧美三级三区| 天天一区二区日本电影三级| 99久国产av精品国产电影| 精华霜和精华液先用哪个| 欧美潮喷喷水| 精品久久久久久久末码| 2021天堂中文幕一二区在线观| av在线老鸭窝| 成人午夜高清在线视频| 国产成人精品久久久久久| 成人亚洲精品av一区二区| 97在线视频观看| 欧美区成人在线视频| 国产黄色视频一区二区在线观看 | 麻豆精品久久久久久蜜桃| 亚洲国产精品合色在线| 26uuu在线亚洲综合色| 一卡2卡三卡四卡精品乱码亚洲| 婷婷六月久久综合丁香| 别揉我奶头 嗯啊视频| 一本—道久久a久久精品蜜桃钙片 精品乱码久久久久久99久播 | 成人午夜精彩视频在线观看| 免费大片18禁| 三级经典国产精品| 国产亚洲av嫩草精品影院| 国产爱豆传媒在线观看| 久久99热6这里只有精品| 久久精品国产自在天天线| 精品久久久久久久久久久久久| 精品午夜福利在线看| 国产精品伦人一区二区| 色噜噜av男人的天堂激情| 老师上课跳d突然被开到最大视频| 亚洲av福利一区| kizo精华| 99国产精品一区二区蜜桃av| 精品不卡国产一区二区三区| 麻豆成人午夜福利视频| 日产精品乱码卡一卡2卡三| 免费看日本二区| www.色视频.com| 日韩一区二区视频免费看| 观看美女的网站| 国产高清不卡午夜福利| 热99re8久久精品国产| 美女黄网站色视频| 黄色一级大片看看| 日韩一区二区三区影片| 亚洲av福利一区| 在线观看66精品国产| 国产一级毛片在线| a级毛片免费高清观看在线播放| 夜夜看夜夜爽夜夜摸| 欧美另类亚洲清纯唯美| 成人漫画全彩无遮挡| 欧美精品一区二区大全| 中文在线观看免费www的网站| 久久精品久久精品一区二区三区|