• <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热这里只频精品6学生| 在线观看www视频免费| 欧美精品一区二区大全| 一个人看视频在线观看www免费| 国产高清国产精品国产三级| 少妇人妻 视频| 国产精品一区二区在线观看99| 在线播放无遮挡| 久久精品国产亚洲av天美| 中文字幕免费在线视频6| 欧美 日韩 精品 国产| 亚洲精品日本国产第一区| 国产乱来视频区| 99久久精品一区二区三区| 免费观看在线日韩| 国产一区二区在线观看av| 成人漫画全彩无遮挡| 少妇丰满av| 国产成人91sexporn| 久久青草综合色| 国产精品一区www在线观看| 亚洲av成人精品一区久久| 国产成人精品在线电影| 最黄视频免费看| 国产日韩一区二区三区精品不卡 | 免费日韩欧美在线观看| 又黄又爽又刺激的免费视频.| 免费高清在线观看日韩| 十分钟在线观看高清视频www| 一二三四中文在线观看免费高清| 内地一区二区视频在线| 日韩熟女老妇一区二区性免费视频| 如日韩欧美国产精品一区二区三区 | 国产成人精品无人区| av免费在线看不卡| 能在线免费看毛片的网站| 中文字幕免费在线视频6| 国产一区二区三区综合在线观看 | 美女xxoo啪啪120秒动态图| 51国产日韩欧美| 日韩电影二区| 高清黄色对白视频在线免费看| 亚洲精品色激情综合| 午夜老司机福利剧场| 高清在线视频一区二区三区| 高清午夜精品一区二区三区| av又黄又爽大尺度在线免费看| 国产免费视频播放在线视频| 乱码一卡2卡4卡精品| 亚洲成色77777| 日韩伦理黄色片| av国产精品久久久久影院| 另类精品久久| 岛国毛片在线播放| 亚洲伊人久久精品综合| 人妻人人澡人人爽人人| 免费人成在线观看视频色| 99re6热这里在线精品视频| 国产有黄有色有爽视频| 26uuu在线亚洲综合色| 亚洲精品乱久久久久久| 简卡轻食公司| 男女无遮挡免费网站观看| 国产免费一级a男人的天堂| 五月玫瑰六月丁香| 中文字幕精品免费在线观看视频 | 欧美激情国产日韩精品一区| 在线免费观看不下载黄p国产| 高清欧美精品videossex| 丝袜脚勾引网站| 成年av动漫网址| 成人综合一区亚洲| 国产伦理片在线播放av一区| 天堂中文最新版在线下载| 日本av免费视频播放| 亚洲av福利一区| 国精品久久久久久国模美| 中文乱码字字幕精品一区二区三区| 亚洲精品中文字幕在线视频| 免费黄频网站在线观看国产| 日韩电影二区| av又黄又爽大尺度在线免费看| 欧美国产精品一级二级三级| 高清欧美精品videossex| 中文字幕免费在线视频6| 亚洲不卡免费看| 亚洲欧美成人精品一区二区| 久久99一区二区三区| 亚洲成人av在线免费| 天堂俺去俺来也www色官网| 高清毛片免费看| 亚洲精品一二三| av有码第一页| 成年女人在线观看亚洲视频| 国产成人午夜福利电影在线观看| av在线老鸭窝| 麻豆成人av视频| 久久精品人人爽人人爽视色| 欧美老熟妇乱子伦牲交| 免费看不卡的av| 99九九线精品视频在线观看视频| 有码 亚洲区| 亚洲精品色激情综合| 九色成人免费人妻av| 色视频在线一区二区三区| av国产久精品久网站免费入址| 国产精品久久久久久精品电影小说| 欧美丝袜亚洲另类| videos熟女内射| 国产精品人妻久久久久久| 日韩av在线免费看完整版不卡| 亚洲欧洲日产国产| 999精品在线视频| 国产欧美亚洲国产| 成人国语在线视频| 在线免费观看不下载黄p国产| 国产毛片在线视频| 精品久久久久久电影网| 午夜激情av网站| 丝袜喷水一区| 久久国产精品男人的天堂亚洲 | 97超碰精品成人国产| 国产欧美日韩一区二区三区在线 | 亚洲精品久久久久久婷婷小说| 欧美日本中文国产一区发布| 亚洲国产成人一精品久久久| 日本欧美视频一区| 亚洲精品美女久久av网站| 中文字幕人妻丝袜制服| 日韩成人av中文字幕在线观看| 青青草视频在线视频观看| 亚洲高清免费不卡视频| 夫妻性生交免费视频一级片| 人人妻人人爽人人添夜夜欢视频| 精品人妻一区二区三区麻豆| 成人国产av品久久久| 少妇精品久久久久久久| 欧美人与善性xxx| 婷婷色麻豆天堂久久| 亚洲国产欧美在线一区| 亚洲成人手机| 亚洲av不卡在线观看| 麻豆成人av视频| 国产有黄有色有爽视频| 国产一区二区三区av在线| 各种免费的搞黄视频| 五月玫瑰六月丁香| 一级毛片电影观看| 精品少妇内射三级| 99久久综合免费| 9色porny在线观看| 久久ye,这里只有精品| 国产精品久久久久久av不卡| av在线播放精品| 成人18禁高潮啪啪吃奶动态图 | 韩国av在线不卡| 国产日韩欧美亚洲二区| 久久久久久久久久成人| 亚洲精品视频女| 国产男女内射视频| 好男人视频免费观看在线| 老熟女久久久| 久久久午夜欧美精品| 国产av国产精品国产| 涩涩av久久男人的天堂| 国产精品一国产av| 亚洲精品日本国产第一区| 人人妻人人爽人人添夜夜欢视频| 一本色道久久久久久精品综合| 狂野欧美白嫩少妇大欣赏| 九草在线视频观看| 精品久久国产蜜桃| 丝瓜视频免费看黄片| 寂寞人妻少妇视频99o| 成人漫画全彩无遮挡| 九九爱精品视频在线观看| 大话2 男鬼变身卡| 中文字幕av电影在线播放| 久久久国产欧美日韩av| 街头女战士在线观看网站| 一区二区三区免费毛片| 人妻 亚洲 视频| 69精品国产乱码久久久| 精品人妻熟女av久视频| 人人妻人人澡人人爽人人夜夜| 啦啦啦在线观看免费高清www| 日韩一区二区三区影片| 欧美xxⅹ黑人| 综合色丁香网| 久热这里只有精品99| 男人操女人黄网站| 久久久久精品性色| 最近中文字幕2019免费版| 亚洲欧洲日产国产| 日本91视频免费播放| 日产精品乱码卡一卡2卡三| 91精品伊人久久大香线蕉| 成人综合一区亚洲| 少妇人妻久久综合中文| 久久久精品区二区三区| 我的老师免费观看完整版| 天堂8中文在线网| 中文字幕人妻熟人妻熟丝袜美| 国产精品 国内视频| 国产成人免费无遮挡视频| 午夜免费观看性视频| 最黄视频免费看| 亚洲国产精品成人久久小说| 欧美日本中文国产一区发布| 激情五月婷婷亚洲| 一级爰片在线观看| 欧美人与性动交α欧美精品济南到 | 国产精品久久久久久久电影| 国产黄片视频在线免费观看| 国产精品国产av在线观看| 日本vs欧美在线观看视频| 亚洲精品成人av观看孕妇| 久久精品人人爽人人爽视色| 视频中文字幕在线观看| 秋霞伦理黄片| 日韩大片免费观看网站| 特大巨黑吊av在线直播| 大香蕉久久成人网| 久久久久精品性色| 免费观看在线日韩| 大片免费播放器 马上看| 成人午夜精彩视频在线观看| 国产欧美日韩综合在线一区二区| 麻豆乱淫一区二区| 欧美精品人与动牲交sv欧美| av电影中文网址| 国产精品99久久久久久久久| 多毛熟女@视频| 亚洲精品一区蜜桃| 69精品国产乱码久久久| 久久人人爽人人片av| 久久久久久久久久人人人人人人| 国产欧美另类精品又又久久亚洲欧美| 久久精品国产a三级三级三级| 日本黄大片高清| 狂野欧美激情性xxxx在线观看| 国产无遮挡羞羞视频在线观看| 久久国产亚洲av麻豆专区| 久久久国产欧美日韩av| 亚洲情色 制服丝袜| 日韩强制内射视频| 黄色视频在线播放观看不卡| 嘟嘟电影网在线观看| 亚洲精品一区蜜桃| 亚洲人成77777在线视频| 观看av在线不卡| 久久久久视频综合| 日本欧美国产在线视频| 免费少妇av软件| 久久久午夜欧美精品| av一本久久久久| 午夜激情福利司机影院| 成人综合一区亚洲| 日韩人妻高清精品专区| 久久久久久伊人网av| 91精品伊人久久大香线蕉| h视频一区二区三区| 亚洲美女黄色视频免费看| 国产日韩一区二区三区精品不卡 | 国产伦理片在线播放av一区| 精品国产一区二区久久| 中文乱码字字幕精品一区二区三区| 精品久久久噜噜| 免费观看av网站的网址| 少妇人妻 视频| 国产精品熟女久久久久浪| 夜夜爽夜夜爽视频| 亚洲熟女精品中文字幕| 天堂8中文在线网| 中文字幕人妻熟人妻熟丝袜美| 高清午夜精品一区二区三区| 大码成人一级视频| 国产乱来视频区| 亚洲在久久综合| 最黄视频免费看| 毛片一级片免费看久久久久| 乱人伦中国视频| 波野结衣二区三区在线| 在线观看三级黄色| av女优亚洲男人天堂| 国产日韩欧美亚洲二区| 免费看光身美女| 欧美亚洲 丝袜 人妻 在线| 亚洲av男天堂| 亚洲av免费高清在线观看| 亚洲丝袜综合中文字幕| 亚洲精品乱码久久久久久按摩| 一级二级三级毛片免费看| 成人二区视频| 国产白丝娇喘喷水9色精品| 一区在线观看完整版| 啦啦啦在线观看免费高清www| 欧美少妇被猛烈插入视频| 制服人妻中文乱码| 热re99久久精品国产66热6| 国产免费现黄频在线看| 我的女老师完整版在线观看| 亚洲精品日本国产第一区| 亚洲高清免费不卡视频| 啦啦啦视频在线资源免费观看| 狂野欧美白嫩少妇大欣赏| 人妻少妇偷人精品九色| 中文乱码字字幕精品一区二区三区| 精品久久久噜噜| 纵有疾风起免费观看全集完整版| 一级a做视频免费观看| 香蕉精品网在线| 精品人妻熟女毛片av久久网站| av网站免费在线观看视频| 校园人妻丝袜中文字幕| 午夜福利影视在线免费观看| 国产精品人妻久久久久久| 亚洲精品乱码久久久久久按摩| 亚洲情色 制服丝袜| 韩国av在线不卡| 亚洲经典国产精华液单| 免费观看a级毛片全部| 精品卡一卡二卡四卡免费| 久久婷婷青草| 伊人亚洲综合成人网| 国产日韩一区二区三区精品不卡 | 亚洲av在线观看美女高潮| 国产白丝娇喘喷水9色精品| 日本wwww免费看| 观看美女的网站| 丁香六月天网| 成人毛片60女人毛片免费| 天堂8中文在线网| 纯流量卡能插随身wifi吗| 伦理电影大哥的女人| 免费观看a级毛片全部| 晚上一个人看的免费电影| 最近手机中文字幕大全| 青春草视频在线免费观看| 中文天堂在线官网| 久久影院123| 国产精品久久久久久精品电影小说| 国产亚洲av片在线观看秒播厂| 黑丝袜美女国产一区| 青春草亚洲视频在线观看| 18禁观看日本| 边亲边吃奶的免费视频| 天堂8中文在线网| 亚洲国产毛片av蜜桃av| 亚洲av国产av综合av卡| 午夜免费鲁丝| 国产爽快片一区二区三区| 久久99一区二区三区| 免费大片18禁| 国产成人精品一,二区| 日本与韩国留学比较| 一区二区三区免费毛片| 日韩电影二区| 国产熟女午夜一区二区三区 | 成年av动漫网址| 国产av精品麻豆| 国产成人精品婷婷| 国产69精品久久久久777片| 欧美最新免费一区二区三区| 亚洲av福利一区| 丝袜在线中文字幕| 一级毛片黄色毛片免费观看视频| 久久久精品94久久精品| 欧美 日韩 精品 国产| 精品人妻偷拍中文字幕| 国产亚洲精品久久久com| 色5月婷婷丁香| 国产一区二区在线观看日韩| 国语对白做爰xxxⅹ性视频网站| 丁香六月天网| 午夜av观看不卡| 国产亚洲精品久久久com| 人人妻人人爽人人添夜夜欢视频| 日本vs欧美在线观看视频| 少妇 在线观看| 人人妻人人澡人人爽人人夜夜| 多毛熟女@视频| 十八禁高潮呻吟视频| 亚洲人成77777在线视频| 一边亲一边摸免费视频| 在线免费观看不下载黄p国产| 九草在线视频观看| 日本vs欧美在线观看视频| 校园人妻丝袜中文字幕| 精品人妻一区二区三区麻豆| 亚洲一区二区三区欧美精品| 少妇猛男粗大的猛烈进出视频| 韩国高清视频一区二区三区| 亚洲欧美成人精品一区二区| 搡女人真爽免费视频火全软件| 欧美日韩视频高清一区二区三区二| 老熟女久久久| 大香蕉久久成人网| 九色亚洲精品在线播放| 国产熟女欧美一区二区| 国产黄片视频在线免费观看| 午夜视频国产福利| 日韩欧美精品免费久久| 国产成人午夜福利电影在线观看| 爱豆传媒免费全集在线观看| 国产爽快片一区二区三区| 欧美日韩视频精品一区| 午夜激情福利司机影院| 亚洲精品aⅴ在线观看| 我要看黄色一级片免费的| 国产成人一区二区在线| 亚洲伊人久久精品综合| 国产精品久久久久久精品古装| 中文字幕人妻丝袜制服| 天堂8中文在线网| 两个人免费观看高清视频| 亚洲色图 男人天堂 中文字幕 | 十八禁网站网址无遮挡| 午夜日本视频在线| 夜夜骑夜夜射夜夜干| 亚洲精品美女久久av网站| 自拍欧美九色日韩亚洲蝌蚪91| 91精品国产九色| 女人久久www免费人成看片| 九色成人免费人妻av| 如何舔出高潮| 免费高清在线观看日韩| 91久久精品国产一区二区三区| 国产欧美日韩一区二区三区在线 | av卡一久久| 一区二区日韩欧美中文字幕 | 国产一区二区在线观看日韩| av不卡在线播放| 大香蕉久久网| 美女xxoo啪啪120秒动态图| 99久久精品一区二区三区| 我的女老师完整版在线观看| 欧美 日韩 精品 国产| 久久99蜜桃精品久久| 曰老女人黄片| .国产精品久久| 又粗又硬又长又爽又黄的视频| 欧美亚洲日本最大视频资源| 免费高清在线观看日韩| 国产日韩一区二区三区精品不卡 | 蜜臀久久99精品久久宅男| 精品人妻熟女av久视频| 熟女电影av网| 久久 成人 亚洲| 日本午夜av视频| 美女xxoo啪啪120秒动态图| 少妇精品久久久久久久| 色吧在线观看| 99热全是精品| 亚洲国产精品一区二区三区在线| 啦啦啦视频在线资源免费观看| 国产成人一区二区在线| 中国美白少妇内射xxxbb| 亚洲精品日韩av片在线观看| 国内精品宾馆在线| 国产成人freesex在线| 国产男人的电影天堂91| 国产精品国产三级国产专区5o| 交换朋友夫妻互换小说| 亚洲人与动物交配视频| 国产一区二区在线观看日韩| 久久久久久久亚洲中文字幕| 制服人妻中文乱码| 国产免费现黄频在线看| 在线 av 中文字幕| 只有这里有精品99| 伊人久久国产一区二区| 一本—道久久a久久精品蜜桃钙片| 亚洲丝袜综合中文字幕| 日本av手机在线免费观看| 亚洲经典国产精华液单| 丝袜脚勾引网站| 国产精品无大码| 熟妇人妻不卡中文字幕| 大片电影免费在线观看免费| 99国产精品免费福利视频| av卡一久久| 午夜福利网站1000一区二区三区| 国产精品国产三级国产专区5o| 日韩精品有码人妻一区| 精品久久久噜噜| 一级二级三级毛片免费看| 亚洲成色77777| 亚洲国产色片| 亚洲精品日韩av片在线观看| tube8黄色片| 日韩强制内射视频| 国产精品一区二区在线观看99| 在线 av 中文字幕| 亚洲精品日韩av片在线观看| 国产精品麻豆人妻色哟哟久久| 成人影院久久| 老司机影院毛片| 亚洲国产色片| 69精品国产乱码久久久| 免费少妇av软件| 免费大片18禁| 你懂的网址亚洲精品在线观看| 亚洲五月色婷婷综合| 又大又黄又爽视频免费| 免费少妇av软件| 免费大片18禁| 狠狠婷婷综合久久久久久88av| 亚洲精品成人av观看孕妇| 国产成人一区二区三区免费视频网站| 在线观看免费视频网站a站| 精品国内亚洲2022精品成人 | 久久99一区二区三区| 久久久久久免费高清国产稀缺| 精品久久久久久电影网| 他把我摸到了高潮在线观看 | 亚洲国产精品一区二区三区在线| 亚洲精品在线美女| 国产成人欧美在线观看 | 成年人黄色毛片网站| 亚洲美女黄片视频| 国产一区二区 视频在线| 99精国产麻豆久久婷婷| 午夜两性在线视频| 女人精品久久久久毛片| 亚洲,欧美精品.| 99久久99久久久精品蜜桃| 欧美精品人与动牲交sv欧美| 男人舔女人的私密视频| 免费久久久久久久精品成人欧美视频| 大香蕉久久网| 国产精品一区二区精品视频观看| 最黄视频免费看| 国产精品香港三级国产av潘金莲| xxxhd国产人妻xxx| 大型av网站在线播放| 女人被躁到高潮嗷嗷叫费观| 亚洲avbb在线观看| 国产亚洲欧美在线一区二区| 国产精品98久久久久久宅男小说| 国产成人一区二区三区免费视频网站| 欧美变态另类bdsm刘玥| netflix在线观看网站| 18在线观看网站| 男女午夜视频在线观看| 久久人人爽av亚洲精品天堂| 亚洲九九香蕉| 超碰97精品在线观看| 久久久久国产一级毛片高清牌| 99re6热这里在线精品视频| 久久精品亚洲熟妇少妇任你| 欧美人与性动交α欧美精品济南到| 久久国产精品男人的天堂亚洲| 久久青草综合色| 国产成人精品无人区| 三上悠亚av全集在线观看| 国产精品免费大片| 久久久国产精品麻豆| 一级黄色大片毛片| 无人区码免费观看不卡 | 啦啦啦在线免费观看视频4| 欧美精品一区二区大全| 黑人巨大精品欧美一区二区蜜桃| av天堂久久9| 91av网站免费观看| 老汉色∧v一级毛片| 欧美一级毛片孕妇| 国产一区二区三区综合在线观看| www日本在线高清视频| av福利片在线| 国产免费av片在线观看野外av| 黑人操中国人逼视频| 免费人妻精品一区二区三区视频| 精品亚洲成国产av| 精品少妇久久久久久888优播| 亚洲七黄色美女视频| 在线亚洲精品国产二区图片欧美| 一级毛片电影观看| 久久中文字幕一级| 美女视频免费永久观看网站| 欧美中文综合在线视频| 日韩视频一区二区在线观看| 精品一区二区三区视频在线观看免费 | 亚洲少妇的诱惑av| 久久影院123| 男女免费视频国产| 亚洲国产成人一精品久久久| 国产亚洲午夜精品一区二区久久| 欧美激情极品国产一区二区三区| 侵犯人妻中文字幕一二三四区| 成人国产av品久久久| 正在播放国产对白刺激| 国产av精品麻豆| 老汉色∧v一级毛片| √禁漫天堂资源中文www| 久久久国产精品麻豆| 黄网站色视频无遮挡免费观看| 一本—道久久a久久精品蜜桃钙片| 国产一区二区三区综合在线观看| 亚洲精品一卡2卡三卡4卡5卡| 女人精品久久久久毛片| 欧美日本中文国产一区发布| 在线观看66精品国产| 桃花免费在线播放| 亚洲成av片中文字幕在线观看| 黄色视频在线播放观看不卡| 99热网站在线观看| 男女床上黄色一级片免费看| 一边摸一边抽搐一进一出视频| aaaaa片日本免费| 精品少妇黑人巨大在线播放| 国产精品免费视频内射| 可以免费在线观看a视频的电影网站| 国产一区二区激情短视频| 亚洲成人免费电影在线观看|