鄭朝鑫, 董 晨, 葉 尹

(1.福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院，福建 福州 350108； 2.福建省人大常委會，福建 福州 350001； 3.網(wǎng)絡(luò)系統(tǒng)信息安全福建省高校重點實驗室，福建 福州 350108)

0 引言

目前比較流行的3D建模方式是三維激光掃描點云建模方式，文獻[1-2]展示了這種方式建?？梢赃_到極高的模型精度.微軟公司也推出Kinect，文獻[3-4]介紹Kinect技術(shù)以及利用Kinect進行3D建模的實現(xiàn)方法.另外一種比較特殊的3D建模方式是從2D圖片中進行摳圖建模，文獻[5]詳細地介紹這種建模方法的具體實現(xiàn)以及技術(shù)細節(jié).遺傳算法(genetic algorithm，GA)是將生物界中的自然選擇和種群遺傳學(xué)原理引入到算法的搜索過程中，具有強大的魯棒性以及搜索性能.文獻[6]展示如何直接利用經(jīng)典遺傳算法來解決智能事件辨識問題、傳感器數(shù)量配置優(yōu)化問題.文獻[7-9]研究遺傳算法的改進方法以及具體的實現(xiàn)步驟，并用大量的仿真實驗數(shù)據(jù)證明改進后的混合遺傳算法具備更加強大的搜索性能.文獻[10]提出一種基于遺傳算法的入侵檢測特征選擇方法，提高系統(tǒng)的檢測效率.文獻[11]通過遺傳算法中編碼技術(shù)和基因技術(shù)分析，在社交網(wǎng)站數(shù)據(jù)分析過程中發(fā)現(xiàn)不良信息和違法信息.

1 3D建模

動態(tài)3D建模技術(shù)在家居裝修中，將需要求解房間的長、寬、高, 以及用戶身高作為多維空間中的一組可能解.利用遺傳算法進行搜索計算最優(yōu)可能解，最后得到8組標定向量誤差最小的解.在本文中，需要利用陀螺儀傳感器輸出數(shù)據(jù)，實現(xiàn)測量立方體房間中心點與墻角連線的單位向量數(shù)值.這個過程中存在著設(shè)備誤差以及人工站在房間中心點對準墻角位置進行輔助標定的人為操作誤差，如圖1.歸納可得本文中的優(yōu)化問題是利用遺傳算法對陀螺儀測量數(shù)據(jù)的各種誤差進行有效性的優(yōu)化，最后計算得到現(xiàn)場房間單位比例的長寬高尺寸.3D模型本身尺寸單位是點或者說像素，與現(xiàn)實物體尺寸只是比例映射關(guān)系，所以陀螺儀簡易測量可通過遺傳算法得到房間最佳的長寬高比例信息，即可實現(xiàn)3D建模目的.

圖1 不同用戶測量同一房間產(chǎn)生的坐標系原點偏差示意圖Fig.1 Different users measure the frame origin deviation of the same room

2 遺傳算法

2.1 編碼方式

基因編碼選擇實數(shù)編碼方式.系統(tǒng)需要求解的目標有4個實數(shù)值，分別對應(yīng)房間長度、寬度、高度、用戶身高，通過遺傳算法將4個參數(shù)優(yōu)化后，就可以通過3D引擎創(chuàng)建一個3D房間模型并設(shè)置正確的攝像頭位置視野與實際房間尺寸及用戶視野一一映射，如圖2.

圖2 各視野與實際房間尺寸一一映射Fig.2 Each view is mapped to the actual room size

算法種群第i個個體的編碼定義為：Xi={w,l,h,b}，其中w為房間長度，l為房間寬度，h為房間高度，b為用戶身高.在系統(tǒng)中用戶操作進行標定的向量是8個，8個標定向量與個體信息間的關(guān)系如下式.

(1)

這樣經(jīng)過式(1)對解進行轉(zhuǎn)換后，得到的8個向量就是遺傳算法能處理的搜索空間，遺傳算法可對這8個向量進行交叉、變異等操作，并與標定向量進行適應(yīng)值匹配，如圖3.

圖3 房間墻角人工標定步驟示意圖Fig.3 Schematic diagrams of manual calibration step in room corner

2.2 交叉操作

遺傳算法的交叉方式描述如下： 第i個子代染色體的交叉概率Pc，如果滿足執(zhí)行交叉運算的條件，則雙親中的父親就選擇第i個子代染色體自身，數(shù)學(xué)表達為Xi={wi,li,hi,bi}，母親染色體則通過隨機選擇方法獲得，其數(shù)學(xué)表達式為Xj={wj,lj,hj,bj}，根據(jù)式(1)將父母的基因轉(zhuǎn)換成兩組8個向量的基因數(shù)據(jù)，在這個基礎(chǔ)上進行交叉操作.

交叉操作具體步驟為： 1) 隨機產(chǎn)生Pi∈U(0, 1), 當Pi>Pc，則這個染色體不滿足交叉概率，不進行交叉運算，跳轉(zhuǎn)到步驟8)，結(jié)束交叉操作; 2) 隨機生成1～8的隨機數(shù)，決定本次交叉的基因總數(shù)Ct; 3) 選擇父親染色體Xi，并根據(jù)式(1)計算得到父親基因數(shù)據(jù)8個向量，隨機生成1～8的隨機數(shù)i，則選擇第i個向量Vi作準備; 4) 隨機選擇母親染色體Xj，并根據(jù)式(1)計算得到母親基因數(shù)據(jù)8個向量，隨機生成1～8的隨機數(shù)j，則選擇第j個向量Vj; 5) 隨機生成步驟3)的隨機數(shù)k，選擇Vi的第k維分量浮點數(shù)，隨機生成步驟3)的隨機數(shù)m，選擇Vj的第m維分量浮點數(shù)，將Vi的k與Vj的m進行交叉賦值實現(xiàn)向量Vi和Vj的交叉操作; 6) 交叉后的基因數(shù)據(jù)映射還原成新的染色體Xi和Xj替換原來的染色體數(shù)據(jù)，局部交叉成功; 7) 將Ct數(shù)值減1，判斷Ct是否大于1，如果大于1，代表整體交叉操作尚未結(jié)束，跳轉(zhuǎn)至步驟2)重復(fù)進行; 8)Ct為0，結(jié)束交叉操作.

2.3 變異操作

變異運算，采用染色體中的一個隨機基因，用新的隨機數(shù)賦值實現(xiàn)基因變異的目的.遺傳算法變異方式描述如下： 子代第i個染色體Xi={wi,li,hi,bi}的變異概率Pm滿足變異條件，則將染色體根據(jù)式(1)解碼成基因信息得到8個向量數(shù)據(jù)，然后進行變異操作.

變異操作具體步驟為： 1) 隨機產(chǎn)生Pi∈U(0, 1), 當Pi>Pm，則此染色體不滿足變異條件，不進行變異操作運算，跳轉(zhuǎn)至步驟6)，結(jié)束變異操作; 2) 選擇變異染色體Xi，并根據(jù)式(1)計算得到8個向量的基因數(shù)據(jù); 3) 隨機產(chǎn)生ζk∈U(0, 1)，令j=(Int(ζk×8)+1) ，則j∈[1, 8]，這里Int表示取整運算.選擇第j個向量Vj; 4) 隨機生成一個符合向量取值范圍內(nèi)的浮點數(shù)更新替換向量Vj; 5) 變異后的基因數(shù)據(jù)映射還原成新的染色體Xi，更新染色體數(shù)據(jù)，完成第i個染色體的變異操作; 6) 結(jié)束變異操作.

2.4 選擇策略

遺傳算法通過選擇操作模擬實現(xiàn)種群的繁衍過程.選擇即是擇優(yōu)，因此選擇操作是基于適應(yīng)值計算結(jié)果的過濾方法，每個個體被選擇的概率Pi計算公式如下：

(2)

種群進行選擇操作具體步驟為： 1) 根據(jù)種群規(guī)模NP參數(shù)大小，設(shè)置擇優(yōu)操作的次數(shù)St=NP，初始化ids=0; 2) 準備對種群第ids個新染色體個體進行擇優(yōu)操作; 3) 隨機生成一個0～1之間的隨機數(shù)P; 4) 初始化i=0，從第i個個體Xi開始，根據(jù)式(2)計算Xi的選擇概率Pi，令P=P-Pi.判斷P是否大于0，如果P小于0，則跳轉(zhuǎn)到步驟6); 5)i=i+1，跳轉(zhuǎn)到步驟4)，繼續(xù)進行輪盤旋轉(zhuǎn)選擇; 6) 得到種群中的第i個染色體，即選中染色體Xi.將Xi賦值給新一代種群中的第ids個空值染色體; 7) ids=ids+1，判斷ids是否小于St，如果小于St，則跳轉(zhuǎn)到步驟2); 8) 選擇操作完成，新一代種群染色體賦值全部完成，結(jié)束操作.

2.5 解決房間尺寸計算問題

遺傳算法首先設(shè)置一定數(shù)量的種群，種群中的每個個體對應(yīng)問題的一個可能解.需要求解的參數(shù)數(shù)量N即為解的維度，算法具體實現(xiàn)過程描述為： 存在一個N維空間，其中有M個個體組成的種群.個體i的表達方式為Xi={X1,X2, …,XN}，采用隨機賦值方式初始化種群，而后經(jīng)過選擇遺傳、交叉、變異操作，迭代得到新一代的規(guī)模為M的種群.

將標定的8個向量Vi和可能解的8個向量Vxi都單位化之后，就具備在相同尺度下進行比較的條件，下一步驟為計算8對向量的向量差，并求向量差的長度值，最后求出適應(yīng)值，計算公式如下：

(3)

(4)

式(4)是計算適應(yīng)值的函數(shù)，其中DO的物理意義是可能解代表的房間墻角單位向量與實際房間墻角單位向量的偏差值.式(4)的前半段代表對8個DO偏差值進行累計，作為綜合的偏差，偏差越大，數(shù)值就越小.偏差越小，數(shù)值就越接近1，即100%.后半段中，DO越小，代表兩個單位向量偏差越小，可能解代表的墻角的空間位置與實際房間墻角位置越靠近，1-DO的值也就越接近1, DO越大，1-DO的值就越小.式(5)的計算結(jié)果代表可能解與現(xiàn)實房間相似度，理論最大值為1，代表可能解100%與現(xiàn)實房間匹配.

遺傳算法實現(xiàn)具體步驟描述為： 1) 根據(jù)設(shè)計好的初始種群數(shù)量和遺傳代數(shù)設(shè)定參數(shù)，并對種群中每個染色體數(shù)據(jù)結(jié)構(gòu)用隨機數(shù)進行初始化賦值，產(chǎn)生初始種群; 2) 執(zhí)行循環(huán)體操作，對種群每個染色體Xi={wi,li,hi,bi}，根據(jù)式(1)計算得到8個向量，然后以8個向量為參數(shù)進行適值函數(shù)運算，適應(yīng)值函數(shù)按照式(3)和式(4)計算可得.依此求得每個個體生存適應(yīng)值fitness，并且保存記錄具有最佳適應(yīng)值的個體染色體信息; 3) 根據(jù)每個染色體個體的生存適應(yīng)值執(zhí)行選擇策略，適應(yīng)值越大則染色體被選擇的概率Pi根據(jù)式(2)計算得到的數(shù)值越大，能獲得的遺傳生存幾率越大，以此選擇出下一代種群; 4) 對新一代的種群執(zhí)行交叉運算操作; 5) 對新一代的種群執(zhí)行變異運算操作.讓種群的個體在選擇、交叉及變異算子作用下不斷向更好的適應(yīng)能力方向進化; 6) 判定算法停止條件，如果循環(huán)次數(shù)達到預(yù)定的遺傳代數(shù)NG，則退出循環(huán)操作，跳轉(zhuǎn)至步驟7).如果不滿足算法停止條件，則跳轉(zhuǎn)至步驟2); 7) 所記錄下來的最佳適應(yīng)值就是最優(yōu)解組合，可通過最佳染色體信息解算出房間的8個墻角頂點空間位置，結(jié)束算法.

3 改進遺傳算法

由于遺傳算法每次發(fā)生種群迭代時，主要的操作是擇優(yōu)，以保證新一代的種群比上一代更優(yōu)，這是遺傳算法的優(yōu)勢，同樣也導(dǎo)致容易陷入局部最優(yōu).遺傳算法設(shè)置跳出局部最優(yōu)的操作是交叉和變異.在本文中，一種有目的性的嘗試突破當前最優(yōu)適應(yīng)值的改進的擇優(yōu)操作方式被提出.有意識的突破最優(yōu)的擇優(yōu)方式可參考粒子群算法的優(yōu)化過程，當粒子群中有最優(yōu)個體時，其他個體的迭代更新方式是有目的的優(yōu)化.當遺傳算法的種群擇優(yōu)就能提高種群的最佳適應(yīng)值時，擇優(yōu)操作相比經(jīng)典遺傳算法得到改進.

3.1 實現(xiàn)步驟

改進遺傳算法種群進行遺傳時，大部分的步驟及其描述都是相同的，其中遺傳操作的核心思想做了修改，從普通的擇優(yōu)遺傳操作改進為有意識的突破最優(yōu)的擇優(yōu)方式.具體步驟為： 1) 根據(jù)種群規(guī)模NP參數(shù)大小，設(shè)置擇優(yōu)操作的次數(shù)St=NP，初始化ids=0; 2) 準備對種群第ids個新染色體個體進行擇優(yōu)操作; 3) 隨機生成一個0～1之間的隨機數(shù)P; 4) 初始化i=0，從第i個個體Xi開始，根據(jù)式(2)計算Xi的選擇概率Pi，令P=P-Pi.判斷P是否大于0，如果P小于0，則跳轉(zhuǎn)到步驟6); 5)i=i+1，跳轉(zhuǎn)到步驟4)，繼續(xù)進行輪盤選擇; 6) 得到種群中的第i個染色體，即選中染色體Xi.利用粒子群算法中的公式對染色體的四維參數(shù)的所有方向進行預(yù)處理，計算所有方向的最佳適應(yīng)值，有目的地留取最佳適應(yīng)值數(shù)值最大的方向作為新染色體Xk, 令Xi=Xk; 7) 將有意識的嘗試突破最優(yōu)適應(yīng)值的方式得到的新染色體賦值給新一代種群的第ids個空值染色體; 8) ids=ids+1，判斷ids是否小于St，如果小于St，則跳轉(zhuǎn)到步驟2); 9) 改進的擇優(yōu)操作完成，新一代種群染色體賦值全部完成，結(jié)束操作.

3.2 性能分析

對改進遺傳算法和經(jīng)典遺傳算法的搜索結(jié)果進行橫向?qū)Ρ?測試平臺分別運行兩種算法，令種群規(guī)模NP=800，交叉概率Pc=0.7，變異概率Pm=0.02，遺傳代數(shù)NG=500.兩種算法采用的參數(shù)完全相同，初始化時的目標解也標定為相同目標解，測試結(jié)果如表1所示.

表1 遺傳算法及其改進算法性能實驗

測試結(jié)果： 經(jīng)典遺傳算法得到的最佳適應(yīng)值，不如改進的遺傳算法.改進算法搜索得到的最優(yōu)解比遺傳算法更加逼近目標解.結(jié)果表明改進算法確實表現(xiàn)出更優(yōu)的搜索性能.

從改進遺傳算法的某個染色體角度比較.令種群規(guī)模NP=800，交叉概率Pc=0.7，變異概率Pm=0.02，遺傳代數(shù)NG=500，目標解為{0.559 718, 0.204 419, 0.803 074, 0.209 286}，測試結(jié)果如表2所示.

表2 改進遺傳算法隨機染色體個體迭代過程

從第一次和第二次迭代數(shù)據(jù)看出，改進遺傳算法有強大的全局搜索能力，兩次迭代后，個體快速向目標解靠近.第三次迭代中的第一維數(shù)據(jù)出現(xiàn)嚴重偏移目標解的現(xiàn)象，表明改進遺傳算法的交叉或者變異機制觸發(fā)了操作，這種操作也保證種群多樣性.第四次迭代時，染色體更新信息來自適應(yīng)值更高的上一代染色體.第67次迭代中的第四維信息、第239次迭代出現(xiàn)在第一維的信息，都是屬于變異操作的影響.

4 實驗結(jié)果與分析

使用遺傳算法對6組不同長度、寬度、高度的房間以及不同身高的用戶做動態(tài)3D建模優(yōu)化實驗，如表3所示.表中的偏差率代表計算出來的房間尺寸與現(xiàn)實房間尺寸的偏差大小，偏差率大小與算法計算出來的身高成正比.當算法隨機產(chǎn)生的可能解中的身高越接近用戶的真實身高時，算法計算得到的房間尺寸就無限接近真實房間尺寸.偏差率的大小不影響裝修預(yù)覽效果，預(yù)覽匹配數(shù)值代表3D模型中對應(yīng)的墻角空間位置與現(xiàn)實房間的墻角空間位置的匹配百分比.從實驗數(shù)據(jù)知，預(yù)覽匹配率平均在99%左右，說明該3D動態(tài)實時建模方法具有不錯的精確匹配率.

表3 不同房間的遺傳算法優(yōu)化結(jié)果比較

5 結(jié)語

未來還可以研究提高改進遺傳算法的運行效率方法，縮短算法運行消耗時間.可研究更好的適應(yīng)值表達函數(shù)，使得適應(yīng)值能更精確地表達虛擬房間與現(xiàn)實房間的相似度.目前只是針對立方體的房間進行測量并建模，在這個基礎(chǔ)上以后還能對測量方法進行擴展，可增加支持不規(guī)則房間的形狀及尺寸的測量建模，對室內(nèi)窗口、門口、墻垛、梁等信息采集和處理，具有比較好的現(xiàn)實適應(yīng)性，能在更多場合中使用，經(jīng)過擴展的應(yīng)用將有更好的發(fā)展前景.