• <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麻豆专区| 咕卡用的链子| 18禁动态无遮挡网站| 日韩一区二区视频免费看| 国产伦理片在线播放av一区| 亚洲av中文av极速乱| 久久久精品国产亚洲av高清涩受| 人人妻人人添人人爽欧美一区卜| 超碰成人久久| 国产免费又黄又爽又色| 久久99一区二区三区| 国产成人91sexporn| www.精华液| 久久 成人 亚洲| 青春草国产在线视频| 午夜福利乱码中文字幕| 黄频高清免费视频| 亚洲精品乱久久久久久| 亚洲四区av| 日韩 亚洲 欧美在线| 高清欧美精品videossex| 欧美 日韩 精品 国产| 亚洲第一青青草原| 电影成人av| 日本wwww免费看| 黄色怎么调成土黄色| 777久久人妻少妇嫩草av网站| 韩国精品一区二区三区| 黑丝袜美女国产一区| 亚洲精品久久久久久婷婷小说| 可以免费在线观看a视频的电影网站 | 亚洲精品美女久久av网站| 国产熟女欧美一区二区| 男女边摸边吃奶| 最新中文字幕久久久久| 国产成人精品婷婷| 国产伦理片在线播放av一区| 亚洲欧美色中文字幕在线| 十八禁网站网址无遮挡| 国产精品一区二区在线观看99| 亚洲精品一二三| 叶爱在线成人免费视频播放| 波多野结衣一区麻豆| 久久久久精品久久久久真实原创| 亚洲综合色网址| 啦啦啦中文免费视频观看日本| 亚洲欧洲日产国产| 久久久精品94久久精品| av天堂久久9| 亚洲国产欧美网| 久久久久国产精品人妻一区二区| 97人妻天天添夜夜摸| 老汉色∧v一级毛片| 亚洲国产欧美在线一区| 哪个播放器可以免费观看大片| av片东京热男人的天堂| 久久午夜综合久久蜜桃| 天天躁日日躁夜夜躁夜夜| 黄色视频在线播放观看不卡| 国产深夜福利视频在线观看| 日韩一区二区视频免费看| 亚洲精华国产精华液的使用体验| 国产一区二区三区综合在线观看| 美女脱内裤让男人舔精品视频| 国产福利在线免费观看视频| 精品国产乱码久久久久久小说| 亚洲精品国产一区二区精华液| 国产成人av激情在线播放| av女优亚洲男人天堂| 自线自在国产av| 黄片小视频在线播放| 精品国产一区二区三区久久久樱花| 久久狼人影院| 国产精品久久久久久精品古装| av卡一久久| 老司机亚洲免费影院| 日韩一区二区三区影片| 极品少妇高潮喷水抽搐| 欧美激情 高清一区二区三区| 夫妻性生交免费视频一级片| 男人操女人黄网站| 国产片内射在线| 99九九在线精品视频| 亚洲精品日本国产第一区| 日韩一区二区三区影片| 亚洲成人手机| 国产精品免费视频内射| 飞空精品影院首页| 一级爰片在线观看| 日韩熟女老妇一区二区性免费视频| 国产伦理片在线播放av一区| 久久毛片免费看一区二区三区| 国产日韩欧美亚洲二区| 90打野战视频偷拍视频| 国产熟女午夜一区二区三区| 精品午夜福利在线看| 搡女人真爽免费视频火全软件| 99热网站在线观看| 激情五月婷婷亚洲| 国产免费一区二区三区四区乱码| 国产精品久久久久久精品电影小说| 热re99久久精品国产66热6| 欧美av亚洲av综合av国产av | 国产一区亚洲一区在线观看| 国产人伦9x9x在线观看 | 国产人伦9x9x在线观看 | 色哟哟·www| 精品一区在线观看国产| 欧美人与性动交α欧美软件| 男人舔女人的私密视频| 99久久人妻综合| 人妻 亚洲 视频| 成人毛片60女人毛片免费| 日本vs欧美在线观看视频| 校园人妻丝袜中文字幕| www日本在线高清视频| 亚洲国产成人一精品久久久| 午夜福利一区二区在线看| 岛国毛片在线播放| 免费观看在线日韩| 婷婷色综合www| 99久国产av精品国产电影| 三级国产精品片| 久久国产精品男人的天堂亚洲| 国产探花极品一区二区| 欧美精品一区二区大全| 午夜av观看不卡| 国产亚洲午夜精品一区二区久久| xxxhd国产人妻xxx| 久久精品夜色国产| 国产精品久久久av美女十八| 黄色配什么色好看| 美女大奶头黄色视频| 亚洲伊人久久精品综合| 亚洲 欧美一区二区三区| 国产精品免费视频内射| 精品视频人人做人人爽| 狠狠婷婷综合久久久久久88av| 成人毛片a级毛片在线播放| 十分钟在线观看高清视频www| 精品卡一卡二卡四卡免费| 久久久精品区二区三区| 亚洲视频免费观看视频| 欧美最新免费一区二区三区| 亚洲av中文av极速乱| 1024视频免费在线观看| 欧美另类一区| av不卡在线播放| 久久精品国产鲁丝片午夜精品| 午夜免费观看性视频| 一级毛片黄色毛片免费观看视频| 一区二区三区精品91| 免费久久久久久久精品成人欧美视频| 亚洲色图综合在线观看| 亚洲av综合色区一区| 亚洲精品一二三| 伊人亚洲综合成人网| 成人国语在线视频| 一级毛片我不卡| 国产精品久久久久久精品古装| 成年女人在线观看亚洲视频| 熟女电影av网| 国产麻豆69| 91精品国产国语对白视频| 国产精品国产三级国产专区5o| 亚洲美女搞黄在线观看| 亚洲视频免费观看视频| 亚洲一区二区三区欧美精品| 国产精品 欧美亚洲| 啦啦啦视频在线资源免费观看| 国产乱来视频区| 亚洲人成网站在线观看播放| 免费观看在线日韩| 欧美另类一区| videos熟女内射| 老鸭窝网址在线观看| 看免费av毛片| 国产一区有黄有色的免费视频| 美女大奶头黄色视频| 观看美女的网站| 高清在线视频一区二区三区| 制服诱惑二区| 久久国内精品自在自线图片| 欧美精品高潮呻吟av久久| 亚洲精品视频女| 亚洲色图综合在线观看| 热99久久久久精品小说推荐| 精品国产乱码久久久久久小说| 日韩免费高清中文字幕av| 少妇被粗大的猛进出69影院| 少妇人妻久久综合中文| 啦啦啦啦在线视频资源| 肉色欧美久久久久久久蜜桃| 日本爱情动作片www.在线观看| 午夜精品国产一区二区电影| a级毛片在线看网站| 啦啦啦中文免费视频观看日本| 香蕉精品网在线| 精品国产露脸久久av麻豆| www.熟女人妻精品国产| 免费黄网站久久成人精品| 美女脱内裤让男人舔精品视频| 国产男女内射视频| 日日啪夜夜爽| 99香蕉大伊视频| 日本欧美国产在线视频| 捣出白浆h1v1| 一级毛片电影观看| 一个人免费看片子| 亚洲一区二区三区欧美精品| 亚洲av电影在线观看一区二区三区| 欧美日韩av久久| 欧美精品高潮呻吟av久久| av不卡在线播放| 久久国产精品男人的天堂亚洲| 久久久久久久久免费视频了| a级毛片黄视频| 午夜福利,免费看| 69精品国产乱码久久久| 天堂8中文在线网| 欧美 日韩 精品 国产| 久久国产精品大桥未久av| 一级毛片 在线播放| 国产 精品1| 人妻一区二区av| 99香蕉大伊视频| 日本欧美国产在线视频| 亚洲三级黄色毛片| 汤姆久久久久久久影院中文字幕| 狠狠婷婷综合久久久久久88av| 免费观看在线日韩| 一本—道久久a久久精品蜜桃钙片| 一本久久精品| 久久国产精品男人的天堂亚洲| 久久人妻熟女aⅴ| 亚洲内射少妇av| 精品少妇久久久久久888优播| 飞空精品影院首页| 亚洲国产精品一区二区三区在线| 熟女少妇亚洲综合色aaa.| 99热全是精品| 久久久久久久亚洲中文字幕| 久久国产精品大桥未久av| 一本—道久久a久久精品蜜桃钙片| 精品卡一卡二卡四卡免费| 免费黄频网站在线观看国产| 亚洲第一区二区三区不卡| 亚洲av成人精品一二三区| 嫩草影院入口| 午夜福利视频在线观看免费| 在线看a的网站| 久久久国产一区二区| 午夜激情av网站| 亚洲视频免费观看视频| 两性夫妻黄色片| 在线观看免费高清a一片| 三上悠亚av全集在线观看| 久久女婷五月综合色啪小说| 桃花免费在线播放| 亚洲国产精品成人久久小说| 久久毛片免费看一区二区三区| 日韩人妻精品一区2区三区| 久久影院123| 免费黄频网站在线观看国产| 亚洲伊人久久精品综合| 久久人人97超碰香蕉20202| 麻豆av在线久日| 国语对白做爰xxxⅹ性视频网站| 国产成人午夜福利电影在线观看| 大码成人一级视频| 国产日韩欧美亚洲二区| 亚洲国产av新网站| 中文字幕亚洲精品专区| 亚洲美女黄色视频免费看| 美女国产高潮福利片在线看| 亚洲欧美精品自产自拍| 少妇猛男粗大的猛烈进出视频| 欧美变态另类bdsm刘玥| 爱豆传媒免费全集在线观看| 久久久久久久国产电影| 婷婷色综合大香蕉| 天堂俺去俺来也www色官网| 大话2 男鬼变身卡| 99久国产av精品国产电影| 欧美激情极品国产一区二区三区| 一本色道久久久久久精品综合| 在线观看www视频免费| 亚洲一码二码三码区别大吗| 最近手机中文字幕大全| 精品酒店卫生间| 国产精品一区二区在线不卡| 精品人妻在线不人妻| 成人国语在线视频| 丝袜喷水一区| 性少妇av在线| 高清在线视频一区二区三区| 日韩一卡2卡3卡4卡2021年| 久热久热在线精品观看| 街头女战士在线观看网站| 亚洲国产精品成人久久小说| 成人毛片60女人毛片免费| 啦啦啦中文免费视频观看日本| 精品人妻在线不人妻| 女人精品久久久久毛片| 国产在线一区二区三区精| av福利片在线| 飞空精品影院首页| 观看av在线不卡| 少妇熟女欧美另类| 交换朋友夫妻互换小说| 丝袜脚勾引网站| 欧美xxⅹ黑人| 色婷婷久久久亚洲欧美| 制服丝袜香蕉在线| 亚洲精品日本国产第一区| 国产av码专区亚洲av| 国产免费视频播放在线视频| 成人免费观看视频高清| 色视频在线一区二区三区| 国产又色又爽无遮挡免| 丰满乱子伦码专区| 成年动漫av网址| 一本色道久久久久久精品综合| 建设人人有责人人尽责人人享有的| 天堂中文最新版在线下载| 色播在线永久视频| 久久女婷五月综合色啪小说| 精品国产国语对白av| 日韩熟女老妇一区二区性免费视频| 欧美精品国产亚洲| 久久久久久久亚洲中文字幕| 女人精品久久久久毛片| 一个人免费看片子| 久久久久国产一级毛片高清牌| 丝袜在线中文字幕| 波多野结衣一区麻豆| 国产亚洲一区二区精品| 男人操女人黄网站| 纯流量卡能插随身wifi吗| 一区二区三区精品91| 秋霞在线观看毛片| 亚洲av日韩在线播放| 亚洲国产最新在线播放| 最近中文字幕2019免费版| 美女福利国产在线| 亚洲经典国产精华液单| 青春草亚洲视频在线观看| 婷婷成人精品国产| 一区在线观看完整版| 韩国高清视频一区二区三区| 国产精品一国产av| 国产精品蜜桃在线观看| 黄频高清免费视频| 成年人午夜在线观看视频| 亚洲第一区二区三区不卡| 精品国产国语对白av| 老司机影院毛片| 精品国产国语对白av| 久久久久久久久久人人人人人人| 国产成人av激情在线播放| 宅男免费午夜| 黑人欧美特级aaaaaa片| 99国产精品免费福利视频| 国产日韩一区二区三区精品不卡| 人妻 亚洲 视频| 男女边吃奶边做爰视频| 美女中出高潮动态图| 亚洲av福利一区| 亚洲欧美色中文字幕在线| 精品久久蜜臀av无| 日韩电影二区| 欧美少妇被猛烈插入视频| h视频一区二区三区| 2018国产大陆天天弄谢| 久久久精品免费免费高清| 丰满乱子伦码专区| 午夜福利,免费看| 人人澡人人妻人| 国产伦理片在线播放av一区| 最近中文字幕高清免费大全6| 国产精品不卡视频一区二区| 久久久精品94久久精品| 一区二区日韩欧美中文字幕| 精品一区在线观看国产| 热99久久久久精品小说推荐| 我的亚洲天堂| 国产一区二区激情短视频 | 久久午夜福利片| 岛国毛片在线播放| 国产高清国产精品国产三级| 深夜精品福利| 日韩成人av中文字幕在线观看| 久久av网站| 美女xxoo啪啪120秒动态图| 欧美成人午夜免费资源| 亚洲精品乱久久久久久| 精品人妻在线不人妻| 国产人伦9x9x在线观看 | 一区二区三区四区激情视频| 人人妻人人澡人人爽人人夜夜| 久久久久久久久免费视频了| 成年人免费黄色播放视频| 免费观看无遮挡的男女| 香蕉丝袜av| 2021少妇久久久久久久久久久| 亚洲成人av在线免费| 午夜91福利影院| 叶爱在线成人免费视频播放| 亚洲国产精品成人久久小说| 久久99精品国语久久久| 久久精品久久久久久久性| 久久精品亚洲av国产电影网| 飞空精品影院首页| 久久久久久伊人网av| 午夜精品国产一区二区电影| 十分钟在线观看高清视频www| 国产亚洲av片在线观看秒播厂| 亚洲国产av新网站| 精品一区二区三卡| 伦理电影免费视频| 亚洲在久久综合| 在线观看美女被高潮喷水网站| 国产成人一区二区在线| 久久人人爽av亚洲精品天堂| 日韩熟女老妇一区二区性免费视频| 久久99热这里只频精品6学生| 亚洲精品美女久久久久99蜜臀 | 国产一区亚洲一区在线观看| 精品视频人人做人人爽| 黑人欧美特级aaaaaa片| 90打野战视频偷拍视频| 亚洲精品日本国产第一区| 大陆偷拍与自拍| 久久韩国三级中文字幕| 美女脱内裤让男人舔精品视频| 一本久久精品| 亚洲一码二码三码区别大吗| 欧美亚洲日本最大视频资源| 你懂的网址亚洲精品在线观看| 丝袜美足系列| 国产精品.久久久| 91精品国产国语对白视频| 国产熟女欧美一区二区| 色婷婷久久久亚洲欧美| 只有这里有精品99| 18禁动态无遮挡网站| 桃花免费在线播放| av视频免费观看在线观看| 色视频在线一区二区三区| 久久久久久久久久久免费av| 午夜福利影视在线免费观看| 成人毛片a级毛片在线播放| 曰老女人黄片| 91国产中文字幕| 伊人久久大香线蕉亚洲五| 桃花免费在线播放| 国产午夜精品一二区理论片| 观看美女的网站| 老司机影院毛片| 亚洲国产色片| 日本色播在线视频| 日韩制服丝袜自拍偷拍| 在线观看三级黄色| 少妇的逼水好多| 日本爱情动作片www.在线观看| 精品少妇黑人巨大在线播放| 久久国产亚洲av麻豆专区| 免费女性裸体啪啪无遮挡网站| 欧美日韩国产mv在线观看视频| 在线天堂最新版资源| 久久久久精品性色| 欧美人与性动交α欧美精品济南到 | 另类精品久久| 极品人妻少妇av视频| 久久精品熟女亚洲av麻豆精品| 91久久精品国产一区二区三区| 一本一本久久a久久精品综合妖精 国产伦在线观看视频一区 | 国产xxxxx性猛交| 丰满乱子伦码专区| 成人免费观看视频高清| 亚洲国产精品成人久久小说| 日本色播在线视频| 女人高潮潮喷娇喘18禁视频| 国产精品三级大全| 国产一区二区激情短视频 | 久久久久国产网址| 亚洲精品av麻豆狂野| 国产有黄有色有爽视频| 国产日韩欧美视频二区| 精品一区二区免费观看| av在线老鸭窝| 亚洲精品国产色婷婷电影| 成年人免费黄色播放视频| 2021少妇久久久久久久久久久| 国产成人精品久久二区二区91 | 99久久人妻综合| 国产精品亚洲av一区麻豆 | 一级,二级,三级黄色视频| 女人被躁到高潮嗷嗷叫费观| 各种免费的搞黄视频| 熟女av电影| 国产免费一区二区三区四区乱码| 午夜福利网站1000一区二区三区| 韩国高清视频一区二区三区| 国产97色在线日韩免费| 亚洲,欧美精品.| 大片免费播放器 马上看| 老鸭窝网址在线观看| 在线亚洲精品国产二区图片欧美| 国产国语露脸激情在线看| 久久国产精品男人的天堂亚洲| 国产人伦9x9x在线观看 | 99久久综合免费| 永久免费av网站大全| 久热久热在线精品观看| 中文精品一卡2卡3卡4更新| 巨乳人妻的诱惑在线观看| 我的亚洲天堂| 国产免费福利视频在线观看| 啦啦啦啦在线视频资源| 美女国产视频在线观看| 亚洲精品久久成人aⅴ小说| 日本av手机在线免费观看| 国产精品一区二区在线观看99| 超碰成人久久| 一区在线观看完整版| 巨乳人妻的诱惑在线观看| 天美传媒精品一区二区| 最近最新中文字幕大全免费视频 | a 毛片基地| 观看av在线不卡| 精品一区二区三卡| 啦啦啦视频在线资源免费观看| 90打野战视频偷拍视频| 亚洲欧美一区二区三区国产| 国产欧美日韩综合在线一区二区| 亚洲少妇的诱惑av| 欧美少妇被猛烈插入视频| 亚洲av电影在线进入| 最近2019中文字幕mv第一页| 国产欧美日韩综合在线一区二区| 日韩视频在线欧美| 黑人欧美特级aaaaaa片| 寂寞人妻少妇视频99o| 人妻系列 视频| 亚洲美女视频黄频| kizo精华| 久久韩国三级中文字幕| 美女大奶头黄色视频| 韩国精品一区二区三区| 国产精品一区二区在线不卡| 欧美激情高清一区二区三区 | 日韩一区二区视频免费看| 日本爱情动作片www.在线观看| av.在线天堂| 国产精品一二三区在线看| 国产麻豆69| a级片在线免费高清观看视频| 久久韩国三级中文字幕| 一级片免费观看大全| www.自偷自拍.com| 中国国产av一级| 精品少妇黑人巨大在线播放| 热99国产精品久久久久久7| 男人操女人黄网站| 精品一品国产午夜福利视频| 国产成人免费无遮挡视频| 边亲边吃奶的免费视频| 精品国产超薄肉色丝袜足j| 在线观看三级黄色| 日韩熟女老妇一区二区性免费视频| 欧美日韩av久久| 日韩一卡2卡3卡4卡2021年| 国产毛片在线视频| 久久久久网色| 2022亚洲国产成人精品| 亚洲图色成人| 国产亚洲欧美精品永久| 亚洲经典国产精华液单| 少妇人妻精品综合一区二区| 国产成人91sexporn| 欧美老熟妇乱子伦牲交| www日本在线高清视频| 成人国产麻豆网| 少妇被粗大的猛进出69影院| 人妻人人澡人人爽人人| 欧美人与性动交α欧美精品济南到 | 肉色欧美久久久久久久蜜桃| 晚上一个人看的免费电影| 2018国产大陆天天弄谢| 老司机影院毛片| 亚洲精品中文字幕在线视频| 久久久国产一区二区| 欧美最新免费一区二区三区| 亚洲欧美日韩另类电影网站| 久久久久视频综合| 性高湖久久久久久久久免费观看| 最近的中文字幕免费完整| 少妇人妻 视频| 宅男免费午夜| 男人爽女人下面视频在线观看| 99热国产这里只有精品6| 亚洲人成网站在线观看播放| 国产1区2区3区精品| 亚洲av中文av极速乱| videos熟女内射| 校园人妻丝袜中文字幕| 纵有疾风起免费观看全集完整版| 欧美日韩亚洲高清精品| av天堂久久9| 永久免费av网站大全| 男女午夜视频在线观看| 午夜免费鲁丝| 视频在线观看一区二区三区|