• <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ù)紋理繪畫算法
    亚洲欧美成人精品一区二区| 亚洲成人av在线免费| 日本-黄色视频高清免费观看| 最后的刺客免费高清国语| 欧美人与善性xxx| 欧美成人午夜免费资源| 建设人人有责人人尽责人人享有的 | 亚洲av福利一区| 天堂8中文在线网| 国产精品一区二区在线观看99| 最近的中文字幕免费完整| 91精品国产国语对白视频| 搡女人真爽免费视频火全软件| 全区人妻精品视频| 国产精品.久久久| 在线精品无人区一区二区三 | 国产精品免费大片| 国产精品人妻久久久影院| 国产成人91sexporn| 少妇人妻 视频| 日韩伦理黄色片| 日本与韩国留学比较| 亚洲精品日韩在线中文字幕| 国产高潮美女av| 少妇高潮的动态图| 岛国毛片在线播放| 婷婷色综合www| 亚洲成人中文字幕在线播放| 岛国毛片在线播放| 国产欧美日韩一区二区三区在线 | 性色avwww在线观看| 又大又黄又爽视频免费| 永久网站在线| 国产色爽女视频免费观看| 男人狂女人下面高潮的视频| 国语对白做爰xxxⅹ性视频网站| 久久久久久久精品精品| 在线观看国产h片| 亚洲人成网站在线观看播放| 久久久久精品性色| 免费av中文字幕在线| 观看av在线不卡| 欧美日韩综合久久久久久| 国产精品秋霞免费鲁丝片| 草草在线视频免费看| 午夜福利在线在线| 九草在线视频观看| 亚洲人成网站高清观看| 啦啦啦啦在线视频资源| 99久久精品国产国产毛片| 观看美女的网站| 亚洲av福利一区| 国产精品av视频在线免费观看| 99热这里只有是精品50| 亚洲av不卡在线观看| av天堂中文字幕网| 人妻系列 视频| 一级毛片我不卡| 99久久综合免费| 日日摸夜夜添夜夜爱| 欧美zozozo另类| 国产精品一区二区在线不卡| 自拍欧美九色日韩亚洲蝌蚪91 | 超碰av人人做人人爽久久| 国产伦在线观看视频一区| videossex国产| 少妇的逼好多水| 国产高清三级在线| 亚洲欧美日韩另类电影网站 | 亚洲欧洲日产国产| 精品国产露脸久久av麻豆| 伦理电影大哥的女人| 国产高清不卡午夜福利| 性高湖久久久久久久久免费观看| 欧美人与善性xxx| 美女中出高潮动态图| 国产日韩欧美在线精品| 国产日韩欧美在线精品| h视频一区二区三区| 国产色婷婷99| 国产精品99久久99久久久不卡 | 国产大屁股一区二区在线视频| 久久青草综合色| 亚洲av国产av综合av卡| 亚洲成色77777| 亚洲av不卡在线观看| 久久99热这里只频精品6学生| 欧美一区二区亚洲| 国产精品一及| 成人黄色视频免费在线看| 日本与韩国留学比较| 国产精品福利在线免费观看| 国产亚洲5aaaaa淫片| 久久国产乱子免费精品| av播播在线观看一区| 亚洲精品日韩av片在线观看| 99热国产这里只有精品6| 亚洲精品亚洲一区二区| 免费观看av网站的网址| 欧美日韩一区二区视频在线观看视频在线| 午夜免费观看性视频| 水蜜桃什么品种好| 国产精品免费大片| 亚洲精品色激情综合| 国产亚洲5aaaaa淫片| 成人毛片60女人毛片免费| 亚洲av二区三区四区| 尾随美女入室| 男女无遮挡免费网站观看| 一级av片app| 成年人午夜在线观看视频| 国模一区二区三区四区视频| 卡戴珊不雅视频在线播放| 亚洲av成人精品一二三区| 日本色播在线视频| 免费人妻精品一区二区三区视频| 国产精品无大码| 男女下面进入的视频免费午夜| 国产精品国产三级国产av玫瑰| 国产国拍精品亚洲av在线观看| 舔av片在线| 国模一区二区三区四区视频| 大香蕉97超碰在线| 午夜免费鲁丝| 777米奇影视久久| 久久99热这里只有精品18| 精品一区二区免费观看| 又大又黄又爽视频免费| 日本vs欧美在线观看视频 | 青春草视频在线免费观看| 国产午夜精品一二区理论片| 国产av一区二区精品久久 | 久久热精品热| 亚洲欧美精品专区久久| 91久久精品电影网| 久久99精品国语久久久| 亚洲av.av天堂| 青春草亚洲视频在线观看| 国产高清有码在线观看视频| 热99国产精品久久久久久7| 一级黄片播放器| 嘟嘟电影网在线观看| 涩涩av久久男人的天堂| 午夜免费男女啪啪视频观看| 18禁裸乳无遮挡免费网站照片| 亚洲国产色片| 日韩三级伦理在线观看| 日韩伦理黄色片| 国产精品三级大全| 97热精品久久久久久| 国产精品欧美亚洲77777| 欧美一区二区亚洲| 亚洲综合精品二区| 一级黄片播放器| 免费黄网站久久成人精品| 黄色欧美视频在线观看| 99re6热这里在线精品视频| 美女脱内裤让男人舔精品视频| 两个人的视频大全免费| 少妇人妻一区二区三区视频| 亚洲一区二区三区欧美精品| 国产精品成人在线| 高清午夜精品一区二区三区| 色5月婷婷丁香| 女人久久www免费人成看片| 国产久久久一区二区三区| 久久久久精品性色| 水蜜桃什么品种好| 97精品久久久久久久久久精品| 欧美精品亚洲一区二区| 三级国产精品片| 观看免费一级毛片| 国产又色又爽无遮挡免| av网站免费在线观看视频| 国产国拍精品亚洲av在线观看| 永久网站在线| 欧美精品一区二区免费开放| 亚洲欧美日韩卡通动漫| 蜜桃久久精品国产亚洲av| 久久久欧美国产精品| 国产精品久久久久久久电影| 久久精品久久久久久噜噜老黄| 亚洲高清免费不卡视频| 极品少妇高潮喷水抽搐| 久久久久久久久久人人人人人人| 国产成人免费观看mmmm| 美女国产视频在线观看| 精品少妇久久久久久888优播| 成人无遮挡网站| 干丝袜人妻中文字幕| 国产91av在线免费观看| 久久久精品94久久精品| 毛片一级片免费看久久久久| 最近手机中文字幕大全| 嘟嘟电影网在线观看| 久久国产精品男人的天堂亚洲 | 人妻 亚洲 视频| 老女人水多毛片| 黄色欧美视频在线观看| 国产欧美亚洲国产| 久久女婷五月综合色啪小说| 九草在线视频观看| 高清午夜精品一区二区三区| 三级国产精品欧美在线观看| 国产成人精品久久久久久| 国产乱人视频| 中文天堂在线官网| 精品久久久久久久久亚洲| 亚洲av男天堂| 亚洲精品久久午夜乱码| av女优亚洲男人天堂| 尤物成人国产欧美一区二区三区| 国产一区二区三区综合在线观看 | 国产精品一区二区在线观看99| av天堂中文字幕网| 免费高清在线观看视频在线观看| av在线观看视频网站免费| 亚洲成人中文字幕在线播放| 观看av在线不卡| 日韩中文字幕视频在线看片 | 乱码一卡2卡4卡精品| 内射极品少妇av片p| av在线蜜桃| 成人黄色视频免费在线看| av在线观看视频网站免费| 99久久中文字幕三级久久日本| 深爱激情五月婷婷| 亚洲av免费高清在线观看| 蜜桃亚洲精品一区二区三区| 新久久久久国产一级毛片| 色5月婷婷丁香| 在线看a的网站| 久久精品国产自在天天线| 免费人妻精品一区二区三区视频| 色吧在线观看| 亚洲aⅴ乱码一区二区在线播放| 水蜜桃什么品种好| 建设人人有责人人尽责人人享有的 | 日本与韩国留学比较| 久久精品国产自在天天线| 国产亚洲5aaaaa淫片| 国产精品秋霞免费鲁丝片| 久久国产乱子免费精品| 亚洲精品,欧美精品| 深夜a级毛片| 亚洲精品乱码久久久久久按摩| a级一级毛片免费在线观看| 国产 一区 欧美 日韩| 极品少妇高潮喷水抽搐| 日韩视频在线欧美| 在线观看人妻少妇| 99国产精品免费福利视频| 黄色欧美视频在线观看| 中文字幕人妻熟人妻熟丝袜美| .国产精品久久| 国产亚洲欧美精品永久| 在线 av 中文字幕| 欧美变态另类bdsm刘玥| 久久久久久久久久久免费av| 亚洲国产av新网站| 大片免费播放器 马上看| 男人狂女人下面高潮的视频| 欧美激情极品国产一区二区三区 | 精品熟女少妇av免费看| 午夜福利高清视频| 亚州av有码| 五月天丁香电影| 99热这里只有是精品在线观看| 18+在线观看网站| 国产av精品麻豆| 日本wwww免费看| 啦啦啦中文免费视频观看日本| 国产精品一二三区在线看| 在线观看免费视频网站a站| 国产成人精品福利久久| 久久久亚洲精品成人影院| 色5月婷婷丁香| 99re6热这里在线精品视频| 国产一区二区三区av在线| 一级毛片久久久久久久久女| 久久久久国产精品人妻一区二区| 大又大粗又爽又黄少妇毛片口| 欧美三级亚洲精品| 丰满人妻一区二区三区视频av| av国产久精品久网站免费入址| 日日啪夜夜爽| 日韩成人伦理影院| 亚洲天堂av无毛| 欧美bdsm另类| 青青草视频在线视频观看| 亚洲色图综合在线观看| 18禁裸乳无遮挡免费网站照片| 亚洲av免费高清在线观看| 妹子高潮喷水视频| 蜜桃久久精品国产亚洲av| 成人综合一区亚洲| 国产精品国产av在线观看| 网址你懂的国产日韩在线| 欧美区成人在线视频| 免费人妻精品一区二区三区视频| 国产精品一区二区在线不卡| 最近的中文字幕免费完整| 99热这里只有是精品50| 日本-黄色视频高清免费观看| www.色视频.com| 国产高清有码在线观看视频| 热re99久久精品国产66热6| 亚洲精华国产精华液的使用体验| 成人毛片a级毛片在线播放| 国产男人的电影天堂91| 大香蕉97超碰在线| 亚洲三级黄色毛片| 国产精品一区二区性色av| 国产精品人妻久久久影院| 热99国产精品久久久久久7| 久久久久久久亚洲中文字幕| av.在线天堂| 久久久成人免费电影| 国产淫片久久久久久久久| 久久国产精品男人的天堂亚洲 | freevideosex欧美| av在线播放精品| 一级爰片在线观看| 国产女主播在线喷水免费视频网站| 日本猛色少妇xxxxx猛交久久| 国内精品宾馆在线| 久久精品国产鲁丝片午夜精品| 久久精品熟女亚洲av麻豆精品| 九九在线视频观看精品| 精品久久久久久久久亚洲| 婷婷色综合www| 新久久久久国产一级毛片| av福利片在线观看| 国内揄拍国产精品人妻在线| 综合色丁香网| 亚洲精品成人av观看孕妇| 久久久a久久爽久久v久久| 不卡视频在线观看欧美| 国产爱豆传媒在线观看| xxx大片免费视频| 国产免费一区二区三区四区乱码| 中文字幕亚洲精品专区| 欧美+日韩+精品| 国产精品福利在线免费观看| 国产亚洲最大av| 欧美成人一区二区免费高清观看| 久久久久久久久久久丰满| av天堂中文字幕网| 日韩不卡一区二区三区视频在线| 男男h啪啪无遮挡| 国产日韩欧美在线精品| 国产成人精品久久久久久| 欧美精品国产亚洲| 国产精品一区www在线观看| 久久亚洲国产成人精品v| 久久国产精品大桥未久av | 欧美人与善性xxx| 日本色播在线视频| 十分钟在线观看高清视频www | 赤兔流量卡办理| 亚洲精品日韩av片在线观看| 亚洲成人手机| 免费黄网站久久成人精品| 精品国产露脸久久av麻豆| 国产男人的电影天堂91| 日韩免费高清中文字幕av| 97在线人人人人妻| 岛国毛片在线播放| 日本vs欧美在线观看视频 | 欧美zozozo另类| 亚洲精品第二区| 熟妇人妻不卡中文字幕| 九九在线视频观看精品| 国产精品免费大片| 国产成人aa在线观看| 91精品一卡2卡3卡4卡| 亚洲欧美精品专区久久| 色视频在线一区二区三区| 日本一二三区视频观看| 国产精品麻豆人妻色哟哟久久| av在线蜜桃| 精品一区在线观看国产| 久久久久国产精品人妻一区二区| 久久久精品免费免费高清| 我的老师免费观看完整版| 我要看日韩黄色一级片| 久久久久久久国产电影| 久久人妻熟女aⅴ| 精品久久国产蜜桃| 亚洲精品中文字幕在线视频 | 青春草亚洲视频在线观看| 中文字幕亚洲精品专区| 国产精品久久久久久久电影| 少妇的逼好多水| 亚洲av综合色区一区| 网址你懂的国产日韩在线| 97超视频在线观看视频| 国产淫片久久久久久久久| 尾随美女入室| 国产伦精品一区二区三区视频9| 免费观看无遮挡的男女| 国产一区有黄有色的免费视频| 亚洲第一区二区三区不卡| 99热国产这里只有精品6| 国产高清国产精品国产三级 | 欧美激情极品国产一区二区三区 | h日本视频在线播放| 汤姆久久久久久久影院中文字幕| 色哟哟·www| 免费观看的影片在线观看| 国产 一区 欧美 日韩| 黄色一级大片看看| 日韩制服骚丝袜av| 能在线免费看毛片的网站| 亚洲国产毛片av蜜桃av| 三级国产精品欧美在线观看| 人人妻人人添人人爽欧美一区卜 | 国产毛片在线视频| 一区二区av电影网| 精品人妻熟女av久视频| 精品少妇黑人巨大在线播放| xxx大片免费视频| 黄色视频在线播放观看不卡| 亚洲精华国产精华液的使用体验| 最新中文字幕久久久久| 久久久久网色| 人妻制服诱惑在线中文字幕| 97超视频在线观看视频| 国产69精品久久久久777片| 欧美区成人在线视频| 男女国产视频网站| 少妇的逼好多水| 亚洲av综合色区一区| 你懂的网址亚洲精品在线观看| 九色成人免费人妻av| 啦啦啦啦在线视频资源| 老师上课跳d突然被开到最大视频| 特大巨黑吊av在线直播| 亚洲成色77777| 日韩av免费高清视频| 免费黄色在线免费观看| 日韩欧美一区视频在线观看 | 国产精品99久久久久久久久| 国产男女超爽视频在线观看| 大码成人一级视频| 少妇人妻精品综合一区二区| 日韩成人伦理影院| 99热国产这里只有精品6| 午夜福利影视在线免费观看| 色5月婷婷丁香| 97超视频在线观看视频| 晚上一个人看的免费电影| 在线看a的网站| 天堂8中文在线网| 国产爽快片一区二区三区| 大陆偷拍与自拍| 91久久精品国产一区二区三区| 女的被弄到高潮叫床怎么办| 国产免费福利视频在线观看| 天美传媒精品一区二区| 亚洲精品一区蜜桃| 汤姆久久久久久久影院中文字幕| 国产高清国产精品国产三级 | 亚洲国产毛片av蜜桃av| 午夜福利网站1000一区二区三区| 国产精品精品国产色婷婷| 久久精品国产鲁丝片午夜精品| 亚洲熟女精品中文字幕| 亚洲精品色激情综合| 久久久久久久国产电影| 人妻夜夜爽99麻豆av| 多毛熟女@视频| 亚洲图色成人| 日本黄大片高清| 一级毛片久久久久久久久女| 老女人水多毛片| 黄片无遮挡物在线观看| 欧美xxxx黑人xx丫x性爽| 在线播放无遮挡| 国产男人的电影天堂91| 男人狂女人下面高潮的视频| 亚洲精品一二三| 日韩一本色道免费dvd| 久久精品久久精品一区二区三区| 干丝袜人妻中文字幕| 插逼视频在线观看| 亚洲av男天堂| 美女福利国产在线 | 久久精品熟女亚洲av麻豆精品| 只有这里有精品99| 青春草亚洲视频在线观看| 久久精品久久久久久久性| 91精品一卡2卡3卡4卡| 国产精品国产三级专区第一集| av卡一久久| 亚洲人成网站高清观看| 亚洲欧美精品专区久久| 亚洲精品国产av成人精品| 91狼人影院| 男女下面进入的视频免费午夜| 中文乱码字字幕精品一区二区三区| 日本黄色日本黄色录像| 五月玫瑰六月丁香| 久热久热在线精品观看| 亚洲精品自拍成人| 亚洲人与动物交配视频| 国产成人精品久久久久久| 日韩大片免费观看网站| 一区在线观看完整版| 51国产日韩欧美| 肉色欧美久久久久久久蜜桃| 最后的刺客免费高清国语| 免费av不卡在线播放| 国产高清有码在线观看视频| 中文字幕久久专区| 哪个播放器可以免费观看大片| 少妇熟女欧美另类| 永久免费av网站大全| 在线观看免费高清a一片| 伊人久久精品亚洲午夜| 日韩强制内射视频| 免费少妇av软件| 国产欧美另类精品又又久久亚洲欧美| 日韩 亚洲 欧美在线| 国产美女午夜福利| 99精国产麻豆久久婷婷| 午夜老司机福利剧场| 成人高潮视频无遮挡免费网站| 偷拍熟女少妇极品色| 99久久精品一区二区三区| 中国国产av一级| www.av在线官网国产| 国模一区二区三区四区视频| 午夜福利在线观看免费完整高清在| 国产亚洲精品久久久com| 亚洲精品aⅴ在线观看| 国产人妻一区二区三区在| 永久网站在线| 国产精品久久久久久av不卡| 五月开心婷婷网| 啦啦啦视频在线资源免费观看| 女性生殖器流出的白浆| 最近中文字幕高清免费大全6| 久久鲁丝午夜福利片| 偷拍熟女少妇极品色| 一级毛片aaaaaa免费看小| 国产精品免费大片| 中文字幕久久专区| 麻豆国产97在线/欧美| av专区在线播放| 伦理电影免费视频| 中国美白少妇内射xxxbb| 国产综合精华液| 十八禁网站网址无遮挡 | 亚州av有码| 99热这里只有是精品50| 精品午夜福利在线看| 亚洲三级黄色毛片| 日本猛色少妇xxxxx猛交久久| 久久久精品免费免费高清| 黑人猛操日本美女一级片| 18+在线观看网站| 久久综合国产亚洲精品| 日韩国内少妇激情av| 国精品久久久久久国模美| 成人免费观看视频高清| 99久久综合免费| 亚洲经典国产精华液单| 国语对白做爰xxxⅹ性视频网站| 插逼视频在线观看| 99久国产av精品国产电影| 欧美精品人与动牲交sv欧美| 久久99热6这里只有精品| 国产黄频视频在线观看| 麻豆精品久久久久久蜜桃| 深夜a级毛片| 亚洲av不卡在线观看| 日韩伦理黄色片| 免费黄网站久久成人精品| 成人国产麻豆网| 欧美极品一区二区三区四区| 亚洲欧洲国产日韩| 久久久久久久亚洲中文字幕| av又黄又爽大尺度在线免费看| 日本欧美视频一区| 色哟哟·www| 男女无遮挡免费网站观看| 精品久久久久久久久av| 黄色欧美视频在线观看| 黑人猛操日本美女一级片| 欧美老熟妇乱子伦牲交| 国产精品三级大全| 久久毛片免费看一区二区三区| 成人18禁高潮啪啪吃奶动态图 | 亚洲电影在线观看av| 高清欧美精品videossex| 我的老师免费观看完整版| 日本爱情动作片www.在线观看| 欧美激情极品国产一区二区三区 | 18禁裸乳无遮挡免费网站照片| 在线看a的网站| 国产成人aa在线观看| av网站免费在线观看视频| 成年免费大片在线观看| 少妇被粗大猛烈的视频| 国产爽快片一区二区三区| 99热网站在线观看| 男女无遮挡免费网站观看| 国产亚洲最大av| 内射极品少妇av片p| 美女内射精品一级片tv| 国产av精品麻豆| 久久久久网色| 亚洲欧美精品专区久久| 干丝袜人妻中文字幕|