基于改進(jìn)MH算法的室內(nèi)空間自動(dòng)布局

摘 要：為了生成文博展廳、城市閱讀空間、商場(chǎng)等具備公共服務(wù)職能的空間布局，提出了一種面向室內(nèi)空間的自動(dòng)布局方法。該方法首先針對(duì)多種布局的表達(dá)需求，將布局信息記錄在層次化圖結(jié)構(gòu)中；再按照?qǐng)D結(jié)構(gòu)填充適當(dāng)?shù)牟季謱?duì)象作為初始狀態(tài)；利用能量函數(shù)和移動(dòng)策略，引入改進(jìn)的MH（Metropolis-Hastings）算法進(jìn)行優(yōu)化，生成合適的布局方案。選取多種類型的應(yīng)用場(chǎng)景進(jìn)行測(cè)試，結(jié)果證明了該方法的有效性。根據(jù)公共空間設(shè)計(jì)原則，提出評(píng)價(jià)指標(biāo)比較各類方法性能。該方法在布置效率和運(yùn)算效率方面具有優(yōu)勢(shì)，可應(yīng)用于多種類型的公共空間布局設(shè)計(jì)。

關(guān)鍵詞：室內(nèi)空間布局； 布局參數(shù)化表達(dá)； 多目標(biāo)優(yōu)化； Metropolis-Hastings算法；公共空間設(shè)計(jì)

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695（2024）10-029-3087-06

doi：10.19734/j.issn.1001-3695.2024.01.0023

Automatic layout of interior space based on improved MH algorithm

Cao Lia，b， Cheng Xianga， Zhang Zhana

（a.School of Computer & Information（Artificial Intelligence College）， b. Engineering Research Center of the Ministry of Education for Safety Critical Industrial Measurement & Control Technology， Hefei University of Technology， Hefei 230009， China）

Abstract：To generate spatial layouts for spaces with public service functions such as cultural and exhibition halls， urban reading spaces， supermarkets， etc.， this paper proposed a spatial layout expression method. To address the expressive requirements of diverse spatial layouts， the method recorded layout information in a hierarchical graph structure. Subsequently， it populated the appropriate layout objects as the initial state according to the graph structure. By employing a spatial layout energy function and movement strategies，it introduced the Metropolis-Hastings algorithm for optimization， resulting in suitable layout schemes. It demonstrated the effectiveness of the method through testing across various application scenarios， validating its performance. Following principles of public space design， it proposed safety evaluation indicators to compare the performance of different methods. The results indicate that the proposed method exhibits better performance in layout efficiency and computational effectiveness， making it applicable to various types of public space layouts.

Key words：indoor scene layout; parametric expression of layout parameters; multi-objective optimization; Metropolis-Hastings algorithm; public space design

0 引言

空間布局問題是指給定布局空間和一系列布局對(duì)象，考慮如何將這些布局對(duì)象在布局空間中合理排布，并通過優(yōu)化調(diào)整使得最終的布局在某種意義上達(dá)到最優(yōu)［1］。隨著計(jì)算機(jī)信息技術(shù)的不斷發(fā)展，布局合成的應(yīng)用領(lǐng)域越來(lái)越多，在虛擬現(xiàn)實(shí)體驗(yàn)、社區(qū)規(guī)劃和管理、商業(yè)空間布局、公共空間設(shè)計(jì)等領(lǐng)域都有廣泛研究，因此研究空間布局的合成方法具有一定的實(shí)際意義。

傳統(tǒng)人工布局方式通常由用戶提出布局內(nèi)容和需求，設(shè)計(jì)師結(jié)合其專業(yè)知識(shí)設(shè)計(jì)方案供用戶參考，這種設(shè)計(jì)模式效率低下。在計(jì)算機(jī)領(lǐng)域，針對(duì)空間布局的合成已有大量研究方法，主要使用元啟發(fā)式優(yōu)化算法，如模擬退火算法［2］、粒子群算法［3］、遺傳算法［4］等，但這些方法需要復(fù)雜的規(guī)則設(shè)計(jì)，自動(dòng)化程度較低。而且，在布局對(duì)象較多的情況下會(huì)退化，通常不能在合適的時(shí)間內(nèi)找到單個(gè)有效解決方案。隨著SUNCG［5］等大型3D環(huán)境數(shù)據(jù)集的出現(xiàn)，基于學(xué)習(xí)的方法［6，7］變得流行起來(lái)。然而，現(xiàn)有方法存在三個(gè)主要的局限性：a）基于現(xiàn)有的數(shù)據(jù)集，這些數(shù)據(jù)集難以收集， 并容易導(dǎo)致架構(gòu)偏見;b）僅解決空間規(guī)劃和對(duì)象放置兩個(gè)問題之一，并且在空間規(guī)劃問題上難以處理異形輪廓，在對(duì)象放置問題上局限在單個(gè)房間內(nèi);c）這些方法大部分是針對(duì)家居布局，難以擴(kuò)展到其他空間布局的應(yīng)用。

現(xiàn)有的布局設(shè)計(jì)方法被廣泛用于家居布局設(shè)計(jì)，但如展覽布局、商場(chǎng)布局等其他公共場(chǎng)景的自動(dòng)設(shè)計(jì)卻因其獨(dú)特的挑戰(zhàn)而尚未得到充分的關(guān)注和解決。關(guān)鍵的問題之一是墻體空間的有效利用。在墻面資源有限的情況，如何創(chuàng)新性地設(shè)計(jì)墻體，以便于容納更多靠近墻面的布局對(duì)象，是需要解決的問題之一。同時(shí)，當(dāng)面對(duì)具有復(fù)雜邊界的展覽空間以及大量的布局對(duì)象時(shí)，大多數(shù)現(xiàn)有的布局生成算法往往難以產(chǎn)生合理的解決方案，導(dǎo)致空間使用效率低和視覺效果不佳。

綜上，本文提出一種新的面向室內(nèi)空間的自動(dòng)布局方法。給定輸入輪廓和布局需求列表，設(shè)計(jì)適用于多種室內(nèi)場(chǎng)景的布局模式，根據(jù)元素種類選擇合適布局模式填充于布局空間中。布局模式的空間占用與排布方式受制于一系列精細(xì)設(shè)計(jì)的約束條件，由于布局模式內(nèi)部各元素相互依存，且不同布局模式之間也相互影響，這些約束條件難以被表述為一個(gè)連續(xù)可微函數(shù)，所以無(wú)法直接得出單一的全局最優(yōu)解。這就導(dǎo)致了布局問題的求解空間呈現(xiàn)出高度復(fù)雜性，其本質(zhì)上屬于NP-hard問題，隨著問題規(guī)模的增長(zhǎng)，尋求此類問題的最優(yōu)解變得極其困難。Metropolis-Hastings算法作為一種隨機(jī)優(yōu)化算法，擅長(zhǎng)在復(fù)雜的搜索空間中進(jìn)行有效探索，通過接納次優(yōu)解的策略，增加了跳出局部最優(yōu)解并持續(xù)搜索的可能性，從而提升了找到全局最優(yōu)解的概率。為進(jìn)一步逼近全局最優(yōu)解，本文還提出了針對(duì)成本函數(shù)值的擾動(dòng)策略，以避免在復(fù)雜空間中進(jìn)行詳盡的搜索，從而降低算法耗時(shí)。本文的貢獻(xiàn)如下：

a）提出了一種圖驅(qū)動(dòng)的MH布局優(yōu)化算法（graph-driven metropolis-hastings，GD-MH），可應(yīng)用于商場(chǎng)貨架布局、展覽布局或其他虛擬場(chǎng)景布局。

b）提出了針對(duì)室內(nèi)布局的層次化圖結(jié)構(gòu)（scene graph，SG）結(jié)構(gòu)，記錄布局元素信息及其關(guān)系；設(shè)計(jì)了室內(nèi)場(chǎng)景布局模板和能量函數(shù)，幫助布局優(yōu)化過程快速收斂；設(shè)計(jì)了墻生成策略，滿足布局對(duì)象對(duì)墻段的占用需求。

c）將GD-MH布局優(yōu)化方法運(yùn)用到多種場(chǎng)景并與模擬退火算法以及混合整數(shù)二次規(guī)劃進(jìn)行對(duì)比，相關(guān)的性能分析證明了本文方法的有效性。

1 相關(guān)工作

1.1 虛擬場(chǎng)景布局合成

隨著虛擬現(xiàn)實(shí)技術(shù)的飛速發(fā)展，虛擬場(chǎng)景布局合成已成為研究熱點(diǎn)。純細(xì)分方法［8，9］遞歸地分割輸入空間，直到有足夠多的元素或大小達(dá)到閾值，自上而下生成不同布局類型。然而，這種方法完全控制生成過程，無(wú)法預(yù)設(shè)元素位置。Yang等人［10］使用基于語(yǔ)義的方法，通過設(shè)計(jì)一組劃分規(guī)則，使用合適的矩形來(lái)劃分不規(guī)則空間，實(shí)現(xiàn)空間規(guī)劃。Pérez-Martínez等人［11］使用遺傳算法生成地塊，然后使用地塊和建筑物比率以及變異性標(biāo)準(zhǔn)在其上分配建筑物，生成虛擬場(chǎng)景。隨著數(shù)據(jù)集的逐漸完善，數(shù)據(jù)驅(qū)動(dòng)的方法逐漸流行。例如，Yin等人［12］使用房間屬性作為圖節(jié)點(diǎn)，房間連接作為圖邊，使用圖注意力網(wǎng)絡(luò)來(lái)預(yù)測(cè)平面圖的拓?fù)浣Y(jié)構(gòu)。Hartmann等人［13］使用二進(jìn)制像素圖像來(lái)訓(xùn)練GAN模型，用于生成街道網(wǎng)絡(luò)。然而，這些方法只關(guān)注一種布局類型的生成，難以運(yùn)用到不同類型的布局。

1.2 布局結(jié)構(gòu)化表示

目前布局結(jié)構(gòu)化表示主要集中在制定和優(yōu)化居住場(chǎng)景。Ikehata等人［14］使用樹型表示室內(nèi)場(chǎng)景，節(jié)點(diǎn)對(duì)應(yīng)于房間、墻和對(duì)象等結(jié)構(gòu)元素?；旌险麛?shù)二次規(guī)劃［15］對(duì)空間的類別、位置和邊界編碼設(shè)置約束，由粗到細(xì)地生成空間規(guī)劃圖。另一種方法考慮布局空間的鄰接關(guān)系和尺寸約束［16，17］，利用圖論和優(yōu)化技術(shù)構(gòu)建平面圖?；旌霞s束規(guī)劃的遺傳優(yōu)化方法［18］將空間網(wǎng)格化，再結(jié)合劃分空間功能合并網(wǎng)格獲得規(guī)劃圖。一些研究還使用層次化方法表示村落布局［19］。上述方法強(qiáng)調(diào)了區(qū)域或?qū)ο箝g的功能關(guān)系，關(guān)注對(duì)象之間的相互關(guān)系，并需要仔細(xì)地約束設(shè)置。然而，在一些場(chǎng)景中，對(duì)象之間的關(guān)系并非首要考慮因素。例如，展柜通常按照對(duì)齊方式擺放，貨架通常彼此相鄰，桌子和椅子通常組成套裝擺放。因此，更傾向于將最小單位定位為對(duì)象組，評(píng)估一組物體在場(chǎng)景中的整體表現(xiàn)。本文的布局移動(dòng)方式是模式驅(qū)動(dòng)的，遵循室內(nèi)布局設(shè)計(jì)的規(guī)則。

1.3 家居場(chǎng)景布局

室內(nèi)場(chǎng)景布局領(lǐng)域研究主要集中在家居場(chǎng)景布局，其根據(jù)方法可以分為兩類：a）基于約束的方法。如Yu等人［20］提取各種家具對(duì)象的層次和空間關(guān)系， 總結(jié)出一系列約束并將其編碼到成本函數(shù)中， 通過模擬退火算法來(lái)優(yōu)化。Merrell等人［21］提出了一個(gè)交互式的家具布局系統(tǒng)，使用硬件加速的蒙特卡羅采樣器對(duì)密度函數(shù)進(jìn)行快速采樣來(lái)生成布局建議。Bao等人［22］使用一組硬約束和軟約束，制定了約束優(yōu)化以表征良好的建筑布局。然而，這類方法在較大規(guī)模場(chǎng)景布局設(shè)計(jì)中會(huì)退化，通常不能在有效時(shí)間得到合理解。b）基于學(xué)習(xí)的方法。如Wang等人［23］提出了第一個(gè)基于卷積網(wǎng)絡(luò)的系統(tǒng)，用于從零開始合成室內(nèi)場(chǎng)景。Wang等人［24］提出了PlanIT，將室內(nèi)場(chǎng)景合成任務(wù)分規(guī)劃階段和實(shí)例化階段兩步實(shí)現(xiàn)。Ritchie等人［25］通過使用單獨(dú)的神經(jīng)網(wǎng)絡(luò)模塊預(yù)測(cè)對(duì)象的類別、位置、方向和大小，將對(duì)象迭代地插入到場(chǎng)景中，以完成室內(nèi)場(chǎng)景的合成。但這類方法只能處理簡(jiǎn)單布局輪廓下的少量家具擺放問題。

2 布局結(jié)構(gòu)表示

2.1 問題描述

如圖1所示，本文方法輸入一個(gè)劃分好功能區(qū)的布局輪廓和布局元素組信息，輸出一個(gè)符合要求的布局平面圖。

根據(jù)布局類型、元素組的數(shù)量和尺寸，使用基于利用率的填充方法，選擇合適的布局模式將元素組填充在布局空間中，進(jìn)行初始化。如圖2所示，本文總結(jié)了五種不同的布局模式，用于派生出不同的布局結(jié)果，例如鏈?zhǔn)浇Y(jié)構(gòu)常用于會(huì)議室座位、圖書館書架等具有平行功能的物品。

本文使用SG結(jié)構(gòu)存儲(chǔ)布局元素信息及其關(guān)系，通過修改SG結(jié)構(gòu)中的參數(shù)信息完成場(chǎng)景初始化。再使用能量函數(shù)來(lái)指導(dǎo)布局的調(diào)整，例如，重疊約束防止布局元素的重疊擺放。基于能量函數(shù)值，執(zhí)行合理的移動(dòng)策略，并使用Metropolis-Hastings算法進(jìn)行采樣，生成期望布局。2.2 布局模式

參考室內(nèi)設(shè)計(jì)規(guī)范［26～28］總結(jié)了五種不同的布局模式，用于派生出不同的布局結(jié)果。

圖2（a）所示為鏈?zhǔn)浇Y(jié)構(gòu)，表示為Tchain={c，（n1，n2，…，nM），（rw1，rw2，…，rwM），（rh1，rh2，…，rhM）}。其中，c為模板中心位置坐標(biāo)，ni為第i層對(duì)象數(shù)量，rwi為第i層橫向間距，rhi為第i層縱向間距。鏈?zhǔn)浇Y(jié)構(gòu)是最常見的布局結(jié)構(gòu)，用于具有平行功能的布局元素組。圖2（b） 所示為散射式結(jié)構(gòu)Tradiation，表示為Tradiation={c，（n1，n2，…，nM），（r1，r2，…，rM）}。其中，ni為第i層對(duì)象數(shù)量，ri為第i層正多邊形半徑長(zhǎng)度。當(dāng)n1=1，r1=0時(shí)，布局對(duì)象擺放在模板中心位置。散射式結(jié)構(gòu)適合擺放在寬闊的區(qū)域，具有突出中心元素的功能和對(duì)稱美觀的優(yōu)點(diǎn)，常用于展廳展柜的擺放。圖2（c）所示為環(huán)式結(jié)構(gòu)Tcirculation，其表示形式與環(huán)式結(jié)構(gòu)相同，這種擺放方式空間利用率較高，一般用于商場(chǎng)的環(huán)形貨架。圖2（d）所示為扇形結(jié)構(gòu)Tfan，表示為Tfan={c，θ，（n1，n2，…，nM），（r1，r2，…，rM）}，其中，θ為扇區(qū)角度，ni為第i層對(duì)象數(shù)量，ri為第i層扇區(qū)半徑。扇形結(jié)構(gòu)常用于會(huì)議室座位擺放或其他曲形面的擺放需求。圖2（e） 所示為混合式結(jié)構(gòu)，由兩個(gè)鏈?zhǔn)浇Y(jié)構(gòu)和散射式結(jié)構(gòu)的組合，表示為Tmixture={T1，T2，…，TM}，其中，Ti表示任意一種模式。

2.3 SG結(jié)構(gòu)

圖3（a）顯示了一個(gè)空間布局的SG結(jié)構(gòu)。布局定義為SG={V，E}，其中V = {Vi}表示功能區(qū)的集合。邊集合E = {ei}表示功能區(qū)的連通性。Vi的子節(jié)點(diǎn)是布局對(duì)象組Si，記錄了需求列表中每個(gè)布局對(duì)象的基本信息。圖3（b）顯示了每個(gè)功能區(qū)的細(xì)節(jié)，記錄為Vi={P，W，S}。其中，P={pi}表示子空間端點(diǎn)集合，W={wi}記錄子空間墻壁信息，S={Si}表示子空間內(nèi)的布局對(duì)象組，每個(gè)組按照對(duì)應(yīng)的模式布局。圖3（c）顯示了布局對(duì)象組的基本信息。每個(gè)布局對(duì)象組Si={Ti，Bi}，其中Ti為布局模式，Bi為對(duì)象組。Ti取-1表示布局元素是獨(dú)立個(gè)體。每個(gè)布局對(duì)象均用最大矩形包圍盒表示，表示為Bi={tagi，ci，wi， hi，θi}，其中tagi為該對(duì)象所在模板的相對(duì)位置編號(hào)，ci為布局對(duì)象中心坐標(biāo)，wi和hi為布局對(duì)象的尺寸，θi為旋轉(zhuǎn)角度。

3 算法設(shè)計(jì)

3.1 初始化布局

將布局對(duì)象組分配給各個(gè)功能區(qū)，本文使用基于利用率的填充方法遍歷每個(gè)功能區(qū)。方法流程為：

a）計(jì)算參考基準(zhǔn)空間利用率Ua和墻壁利用率Uw。據(jù)此設(shè)置利用率范圍為［Ui-κi，Ui+κi］。其中，κi為小超參數(shù)。

b）預(yù)分配一組布局對(duì)象Si到功能區(qū)Vi。更新空間利用率Ua和墻利用率Uw。

c）若Ua或Uw超出范圍，拒絕此次分配，繼續(xù)考察下一組布局對(duì)象，否則，接受此次分配。分配完成，遍歷下一個(gè)功能區(qū)。

方法流程中，Ua=∑s∈SA（s）Ar，Uw=∑s∈SL（s）Lr。其中，A（·）是面積運(yùn)算符，L（·）是墻占用長(zhǎng)度運(yùn)算符，Ar和Lr分別是輸入輪廓的總面積和輸入輪廓的長(zhǎng)度。分配完成后，根據(jù)SG結(jié)構(gòu)中記錄的功能區(qū)和組的信息初始化的布局，將布局對(duì)象組模板隨機(jī)擺放在功能區(qū)內(nèi)，靠墻的對(duì)象沿墻擺放。擺放過程中，避免布局對(duì)象發(fā)生重疊。

3.2 能量函數(shù)

將布局信息存在層次化圖結(jié)構(gòu)（scene graph，SG）后，需要?jiǎng)?chuàng)建一個(gè)有效的布局方式SG=arg minS∑Vi∈VEr（S），其中，Er是下述各能量項(xiàng)的加權(quán)和，通過最小化該能量函數(shù)來(lái)確定最佳布局方案。

a）空間需求。組內(nèi)對(duì)象周圍需要有開闊的空間。組之間以及組和墻之間也需要保持間距作為行走的通道。式（1） 所示為空間約束Es的能量函數(shù)。

Es=∑φ（ε-2εσ（α（Si）+α（Mi）+α（Wi）））（1）

其中：α（Si）是組內(nèi)對(duì)象之間的空間重疊面積；α（Mi）組之間的重疊面積；α（Wi）是墻與組之間的空間重疊面積；β（S）是總空間需求面積；ε為常量取1.5；σ（x）是sigmoid函數(shù)；φ（x）表示為

φ（x）=1x+x2+τ2（2）

其中：τ是一個(gè)小增量取0.05。

b）填充度需求。大部分室內(nèi)場(chǎng)景的布局要求充分利用空間，例如展覽中需要均勻擺放展項(xiàng)使得展區(qū)各個(gè)部分都有內(nèi)容。商場(chǎng)中要充分利用昂貴的空間擺放貨架等。式（3）為填充度約束Eu的能量函數(shù)。

Eu=∑Vi∈Vφ（1-δminδVi）（3）

其中：δmin是功能區(qū)Vi空間利用率最小閾值;δVi是實(shí)際空間利用率。一組布局對(duì)象占用空間面積由其占地面積和其空間需求之和確定。

c）可達(dá)性需求。輸入輪廓中各功能區(qū)之間有連接關(guān)系，可達(dá)性要求相連的功能區(qū)之間可達(dá)，相鄰區(qū)域必須共享一個(gè)足夠?qū)挼耐ǖ?。式?）為可達(dá)性約束Ea的能量函數(shù)。

Ea=∑Vi，Vj∈Vγ（eρ（dmin-dij）-1）（4）

其中：dmin是通道寬度最小閾值；dij是相鄰功能區(qū)通道寬度；ρ（·）為ReLU函數(shù)；γ為0-1參數(shù)，γ=1表示功能區(qū)相鄰。

d）比例約束。為了避免一組占用過大空間，壓縮其他布局對(duì)象的空間，需要控制布局對(duì)象組的面積占比。式（5）為比例約束Ep的能量函數(shù)。

Ep=∑iφ（1-ρ（μi-μimax）μimax）（5）

其中：μi是組內(nèi)編號(hào)相鄰對(duì)象的距離;μimax為距離參數(shù)最大閾值;μimax=ιSi+ιSj+Z，ιSi和ιSj為單個(gè)布局對(duì)象的空間需求寬度，Z為常數(shù)，Z越小對(duì)組的面積占比約束越強(qiáng)；ρ（·）為ReLU函數(shù)。

對(duì)能量函數(shù)進(jìn)行加權(quán)形成如式（6）的成本函數(shù)：

Er（S）=ω0Es+ω1Eu+ω2Ea+ω3Ep（6）

其中：ωi為正權(quán)重，實(shí)驗(yàn)中參數(shù)的取值為ω0=ω1=ω2=ω3=1.0。

3.3 GD-MH算法

使用圖驅(qū)動(dòng)的MH布局優(yōu)化算法對(duì)空間布局優(yōu)化，算法輸入是初始化布局SG，輸出是優(yōu)化后布局SG，步驟如下：

a）計(jì)算當(dāng)前布局目標(biāo)函數(shù)f（SGi）。

b）進(jìn)行一次布局調(diào)整，若有元素出界或重疊，返回步驟a）。否則，計(jì)算新的目標(biāo)函數(shù)f（SGi+1）。

c）計(jì)算接受概率，p=min{1，f（SGi+1）f（SGi）}，生成0-1范圍內(nèi)隨機(jī)數(shù)rand。

d）若p<rand，拒絕本次移動(dòng)；否則，接受本次移動(dòng)。

e）迭代次數(shù)i=i+1。若i=1 000，結(jié)束；否則，返回步驟a）。

其中，函數(shù)f（SG）=e-λEr（S），λ為常數(shù)取0.1。為了有效地探索布局空間，布局調(diào)整必須包含細(xì)微調(diào)整布局的局部調(diào)整和顯著改變布局的模式改變。具體調(diào)整策略如下：

a）擴(kuò)大/縮小模板。擴(kuò)大模板的操作適用于Es和Eu較大的情況。若Ep占比較大，則縮小空間占比最大的組，通過修改模板的距離參數(shù)對(duì)組內(nèi)間距進(jìn)行調(diào)整，調(diào)整距離為均勻分布下的隨機(jī)值與max（I－iI，0.5）乘積，其中I為迭代次數(shù)最大閾值。

b）平移/旋轉(zhuǎn)模板。若組之間空間有重疊或組和墻段空間有重疊，則隨機(jī)地進(jìn)行平移或旋轉(zhuǎn)操作。旋轉(zhuǎn)操作需要保證組包圍盒的一邊與最近的墻段平行。

c）延長(zhǎng)/縮短墻段。部分場(chǎng)景對(duì)墻的需求較大，若功能區(qū)墻長(zhǎng)度小于所需長(zhǎng)度，則生成墻段。若Ea較大，則刪除墻段以留出通道。根據(jù)文獻(xiàn)［29］，布局對(duì)象對(duì)墻的需求長(zhǎng)度公式為100×（M+1）+∑ili，其中M為靠墻的布局對(duì)象數(shù)量，li為單個(gè)布局對(duì)象的占用展線的長(zhǎng)度，公式中的單位是cm。

本文的墻段生成策略如圖4（a）所示，如果功能區(qū)輪廓有多條邊可以生成墻，則優(yōu)先考慮SG結(jié)構(gòu)中拓?fù)漤樞虿幌噜彽墓δ軈^(qū)的公共邊。如圖4（b）所示，如果公共邊是相鄰區(qū)域之間的唯一通路，則應(yīng)預(yù)留行走間隙，生成墻段位置為線段AB。

d）更改模式。若無(wú)論如何調(diào)整模式的參數(shù)都無(wú)法滿足約束，則改變不適合的模式樣式。例如，將現(xiàn)有的環(huán)形圖案改變?yōu)樾碌逆準(zhǔn)浇Y(jié)構(gòu)，從而顯著改變能量函數(shù)值。

4 實(shí)驗(yàn)結(jié)果與評(píng)估

4.1 實(shí)驗(yàn)結(jié)果

本文實(shí)驗(yàn)使用的硬件配置為CPU Xeon W-2235 3.80 GHz，內(nèi)存64 GB，顯卡GeForce RTX3060 12 GB。圖5為本文方法應(yīng)用到展廳布局的例子，圖5（a）顯示了相同需求列表和輸入輪廓的布局結(jié)果。圖5（b）展示了相同輸入輪廓但不同需求列表的布局結(jié)果?；谛枨罅斜砗洼斎胼喞慕M合生成不同的布局，顯示了本文方法的普適性。表1展示了本文方法的性能，生成布局的平均時(shí)間為38.54 s。

為驗(yàn)證每個(gè)能量項(xiàng)對(duì)布局結(jié)果的影響，按照順序逐一對(duì)權(quán)重系數(shù)ωi進(jìn)行歸零處理，而在每次單獨(dú)實(shí)驗(yàn)中，其余權(quán)重系數(shù)均保持不變。實(shí)驗(yàn)結(jié)果如圖6所示，從中明顯可見，每一項(xiàng)能量項(xiàng)對(duì)于整體布局優(yōu)化都具有不可替代的重要性。其中，合理的展覽布局如圖6（e）所示；圖6（a）未考慮空間約束Es，發(fā)生了布局對(duì)象之間重疊；圖6（b）未考慮填充度約束Eu，導(dǎo)致空間利用率過?。粓D6（c）未考慮可達(dá)性約束Ea，一組展項(xiàng)阻礙了通道；圖6（d）未考慮比例約束Ep，一組展項(xiàng)占用過大空間，壓縮了其他布局對(duì)象的空間。

4.2 定量評(píng)估

為了評(píng)估本文GD-MH布局優(yōu)化方法的有效性，本文實(shí)現(xiàn)了文獻(xiàn)［21］的成本函數(shù)進(jìn)行對(duì)比，應(yīng)用模擬退火算法進(jìn)行布局優(yōu)化，模擬退火參數(shù)初始溫度T設(shè)為1 000 ℃，下降率α為0.99。算法輸入是初始化布局SG，輸出是優(yōu)化后布局SG，具體步驟如下：

a）計(jì)算當(dāng)前布局成本Er0；b）若溫度T大于最小閾值，隨機(jī)進(jìn)行一次移動(dòng)生成新布局，否則結(jié)束；c）計(jì)算新布局成本Ernew，計(jì)算差值ΔEr=Ernew-Er0，生成0～1的隨機(jī)數(shù)rand；d）若ΔEr>0&&e（-ΔEr/T）>rand，拒絕本次移動(dòng)，否則接受本次移動(dòng)，Er0=Ernew，更新溫度T=α·T，返回步驟b）。

本文實(shí)現(xiàn)了文獻(xiàn)［15］的約束，并使用其層次化框架的改進(jìn)版本優(yōu)化布局，設(shè)置最大迭代次數(shù)為1 000。由于本文布局對(duì)象具有預(yù)定義的尺寸和數(shù)量，故選擇預(yù)先分割好的布局輪廓作為初始配置，細(xì)分區(qū)塊的數(shù)量等于功能區(qū)中布局對(duì)象組的數(shù)量，各個(gè)細(xì)分區(qū)塊在不斷的迭代過程中逐步優(yōu)化形成一組匹配的布局對(duì)象。具體步驟如下：

a）對(duì)每個(gè)分塊進(jìn)行隨機(jī)劃分，使得分塊數(shù)量等于布局對(duì)象組內(nèi)成員個(gè)數(shù)。

b）計(jì)算當(dāng)前布局成本Er0。

c）隨機(jī)進(jìn)行以下兩個(gè)布局?jǐn)_動(dòng)：移動(dòng)同一組的小分塊；調(diào)整小分塊的間隙以適應(yīng)布局對(duì)象尺寸。

d）若新布局違反線性約束集，拒絕本次擾動(dòng)，返回步驟c），計(jì)算新布局成本Ernew，若Ernew>Er0，拒絕本次擾動(dòng)。

e）若當(dāng)前迭代次數(shù)i小于最大迭代次數(shù)，返回步驟b）。

設(shè)計(jì)美觀性指標(biāo)、均勻性指標(biāo)和流通性指標(biāo)用于定量評(píng)估真實(shí)設(shè)計(jì)、文獻(xiàn)［15，21］和本文方法的結(jié)果。

a）美觀性。美觀性指標(biāo)度量界面元素的對(duì)齊與組合程度［30］，其表達(dá)式如式（7）所示。

Maesthetic=3nvap+nhap+n（7）

其中：nvap為豎直方向?qū)R對(duì)象數(shù)量；nhap為水平方向?qū)R對(duì)象數(shù)量；n為布局對(duì)象總數(shù)量。

b）均勻性。各子區(qū)域?qū)ο髴?yīng)均勻分布在各個(gè)子區(qū)域。式（8）為均勻性指標(biāo)。

Muniformity=∑v∈V（|Uva-Ua|+|Uvw-Uw|）NV（8）

其中：NV表示功能區(qū)的數(shù)量；Uva是功能區(qū)空間利用率；Uvw是功能區(qū)墻利用率；Ua為基準(zhǔn)空間利用率；Uw為基準(zhǔn)墻壁利用率。

c）流通性。流通性指標(biāo)衡量間隔距離的合理性，式（9）為流通性指標(biāo)。

Mcirculation=∑si，sj∈Sρ（ML-MLsi，sj）（9）

其中：MLsi，sj代表任意兩個(gè)展品之間的距離;ML是一個(gè)人移動(dòng)所需的寬度;ρ（·）為ReLU函數(shù)。

表2給出了三類場(chǎng)景的平均度量值和耗時(shí)的比較。本文方法所有度量指標(biāo)和耗時(shí)優(yōu)于人工設(shè)計(jì)布局和文獻(xiàn)［21］，并且所有度量指標(biāo)都優(yōu)于文獻(xiàn)［15］。如圖7所示，將三種方法以及人工數(shù)據(jù)分別應(yīng)用在展廳、商場(chǎng)和家居場(chǎng)景布局。其中，人工數(shù)據(jù)是提供輸入需求和區(qū)域劃分結(jié)果，由三名計(jì)算機(jī)專業(yè)志愿者設(shè)計(jì)得出?？梢钥闯觯渌椒ㄓ忻黠@的不足之處：a）觀測(cè)區(qū)域重疊;b）長(zhǎng)寬比過大;c）觀測(cè)區(qū)域重疊;d）布局對(duì)象重疊;e）不平行;f）布局對(duì)象重疊;g）觀測(cè)區(qū)域重疊;h）阻礙通行;i）空間分布不均勻。在處理對(duì)墻需求較大的布局場(chǎng)景如展覽布局時(shí)，由于缺乏有效的墻生成策略，其他方法容易導(dǎo)致布局對(duì)象之間的重疊或觀測(cè)區(qū)域的沖突，從而降低了布局的實(shí)用性和觀賞性。

4.3 定性評(píng)估

由于部分布局場(chǎng)景如展覽布局、商場(chǎng)布局等，領(lǐng)域特異性較強(qiáng)，并且不同類型布局在設(shè)計(jì)需求與評(píng)價(jià)標(biāo)準(zhǔn)上存在著顯著差異，普適性的量化方法難以統(tǒng)一評(píng)判布局方案的質(zhì)量。本文參照室內(nèi)空間規(guī)劃和平面建筑設(shè)計(jì)領(lǐng)域的即有研究成果，對(duì)相關(guān)文獻(xiàn)進(jìn)行定性比較。具體劃分為數(shù)據(jù)支撐、布局輪廓復(fù)雜性、分區(qū)域優(yōu)化、模板驅(qū)動(dòng)優(yōu)化以及墻體結(jié)構(gòu)生成五個(gè)方面，如表3所示，其中T表示方法中使用了對(duì)應(yīng)策略，F(xiàn)表示方法中不涉及對(duì)應(yīng)策略。文獻(xiàn)［23，25］使用基于深度學(xué)習(xí)的室內(nèi)空間布局生成方法，文獻(xiàn)［20，21］使用基于約束優(yōu)化的室內(nèi)空間布局生成方法。這些方法均為單個(gè)房間內(nèi)的室內(nèi)空間布局優(yōu)化，未涉及多個(gè)功能區(qū)和模板驅(qū)動(dòng)的優(yōu)化，而且，僅考慮面積較小的規(guī)則房間內(nèi)的少量家具布置，優(yōu)化目標(biāo)較少。文獻(xiàn)［15］采用了一種分層框架以實(shí)現(xiàn)從粗糙到精細(xì)的布局生成過程。然而，該方法在處理細(xì)化室內(nèi)場(chǎng)景布局時(shí)，容易導(dǎo)致觀測(cè)區(qū)域的重疊，這一現(xiàn)象限制了其在精確布局設(shè)計(jì)中的應(yīng)用效果。本文采用了基于模板的分區(qū)域優(yōu)化策略，有效縮減了解空間范圍，從而保證在有限的時(shí)間內(nèi)獲得合理的解決方案。通過引入基于功能區(qū)輪廓的墻生成策略，本文在處理墻需求較高的場(chǎng)景時(shí)展現(xiàn)出一定的優(yōu)勢(shì)。

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

布局問題是商業(yè)和文化領(lǐng)域的一個(gè)重要部分，一個(gè)設(shè)計(jì)良好的方法將有助于用戶展示他們的想法。本文提出了一種圖驅(qū)動(dòng)的自動(dòng)布局生成方法，可以用于展覽布局、商場(chǎng)布或類似的應(yīng)用。該方法使用層次化圖結(jié)構(gòu)（SG），記錄布局元素信息及其關(guān)系，并利用設(shè)計(jì)好的布局模板來(lái)填充合適的項(xiàng)目，引入Metropolis-Hastings算法對(duì)布局進(jìn)行優(yōu)化，生成合適的布局。選取多種類型的布局進(jìn)行實(shí)驗(yàn)，生成的結(jié)果證明了該方法的有效性。然而，所提方法具有局限性，在輸入階段需要較多的參數(shù)設(shè)置。未來(lái)，將使用所提方法來(lái)生成更多的數(shù)據(jù)，并繼續(xù)使用深度學(xué)習(xí)算法來(lái)探索布局生成。

參考文獻(xiàn)：

［1］Wu Wenming， Fu Xiaoming， Tang Rui， et al. Data-driven interior plan generation for residential building

s［J］. ACM Trans on Graphics， 2019， 38（6）： article No.234.

［2］Asl A D， Wong K Y. Solving unequal-area dynamic facility layout problems based on slicing tree representation and simulated annealing［J］. AIP Conference Proceedings， 2015， 1660（1）： 1660-1661.

［3］謝美華， 李艷武， 葛棚丹. 自適應(yīng)混合粒子群算法求解置換流水車間調(diào)度問題［J］. 計(jì)算機(jī)應(yīng)用研究， 2023， 40（11）： 3241-3246，3253. （Xie Meihua， Li Yanwu， Ge Pengdan. Solving the job shop scheduling problem with adaptive hybrid particle swarm algorithm［J］. Application Research of Computers， 2023， 40（11）： 3241-3246，3253.）［4］劉思宇， 李鐵克， 王柏琳， 等. 混合流水車間插單重調(diào)度的超啟發(fā)式遺傳算法［J］. 計(jì)算機(jī)應(yīng)用研究， 2023， 40（9）： 2609-2615. （Liu Siyu， Li Tieke， Wang Bailin， et al. Hyper-heuristic genetic algorithm for hybrid flow shop with rush orders insertion rescheduling problem［J］. Application Research of Computers， 2023， 40（9）： 2609-2615.）

［5］Song Shuran， Yu F， Zeng A， et al. Semantic scene completion from a single depth image［C］//Proc of IEEE Conference on Computer Vision and Pattern Recognition. Piscataway， NJ： IEEE Press， 2017： 1746-1754.

［6］Para W， Guerrero P， Kelly T， et al. Generative layout modeling using constraint graphs［C］//Proc of IEEE Conference on Computer Vision. Piscataway， NJ： IEEE Press， 2021： 6690-6700.

［7］徐義春， 萬(wàn)書振， 董方敏. 帶平衡約束矩形布局優(yōu)化問題的深度強(qiáng)化學(xué)習(xí)算法［J］. 計(jì)算機(jī)應(yīng)用研究， 2022， 39（1）： 146-150. （Xu Yichun， Wan Shuzhen， Dong Fangmin. Deep reinforcement learning algorithm for rectangle layout optimization with equilibrium constraint［J］. Application Research of Computers， 2022， 39（1）： 146-150.）

［8］Morgan F， O’Sullivan D. Using binary space partitioning to generate urban spatial patterns［C］//Proc of the 11th International Conference on Computers in Urban Planning and Urban Management. Berlin： Springer， 2009： 1-16.

［9］Marson F， Musse S R. Automatic real-time generation of floor plans based on squarified treemaps algorithm［J］. International Journal of Computer Games Technology， 2010， 2： 1-10.

［10］Yang Yongliang， Wang Jun， Vouga E， et al. Urban pattern： layout design by hierarchical domain splitting［J］. ACM Trans on Graphics， 2013， 32（6）： article No.181.

［11］Pérez-Martínez I， Martinez-Rojas M， Soto-Hidalgo J M. A preliminary approach to allocate categories of buildings into lands based on generative design［C］//Proc of IEEE International Conference on Fuzzy Systems. Piscataway， NJ： IEEE Press， 2020 ： 1-6.

［12］Yin Yu， Hutchcroft W， Khosravan N， et al. Generating topological structure of floorplans from room attributes［C］//Proc of International Confe-rence on Multimedia Retrieval. New York： ACM Press， 2022： 295-303.

［13］Hartmann S， Weinmann M， Wessel R， et al. StreetGAN： towards road network synthesis with generative adversarial networks［C］//Proc of the 25th International Conference in Central Europe on Computer Graphics， Visualization and Computer Visionin. 2017：133-142.

［14］Ikehata S， Yang Hang， Furukawa Y. Structured indoor modeling［C］//Proc of IEEE International Conference on Computer Vision. Piscataway， NJ： IEEE Press， 2015： 1323-1331.

［15］Wu Wenming， Fan Lubin， Liu Ligang， et al. MIQP-based layout design for building interiors［J］. Computer Graphics Forum， 2018， 37（2）： 511-521.

［16］Wang Xiaoyu， Zhang Kang. Generating layout designs from high-level specifications［J］. Automation in Construction， 2020， 119： 103288.

［17］Shekhawat K， Upasani N， Bisht S， et al. A tool for computer-generated dimensioned floorplans based on given adjacencies［J］. Automation in Construction， 2021， 127： 103718.

［18］Laignel G， Pozin N， Geffrier X， et al. Floor plan generation through a mixed constraint programming-genetic optimization approach［J］. Automation in Construction， 2021， 123： 103491.

［19］Teh Y W， Jordan M I. Hierarchical Bayesian nonparametric models with applications［J］. Bayesian Nonparametrics， 2010， 1： 158-207.

［20］Yu L F， Yeung S K， Tang C K， et al. Make it home： automatic optimization of furniture arrangement［J］. ACM Trans on Graphics， 2011， 30（4）： article No.86.

［21］Merrell P， Schkufza E， Li Z， et al. Interactive furniture layout using interior design guidelines［J］. ACM Trans on Graphics， 2011， 30（4）： article No.87.

［22］Bao Fan， Yan Dongming， Mitra N J， et al. Generating and exploring good building layouts［J］. ACM Trans on Graphics， 2013， 32（4）： article No.122.

［23］Wang Kai， Savva M， Chang A X， et al. Deep convolutional priors for indoor scene synthesis［J］. ACM Trans on Graphics， 2018， 37（4）： article No.70.

［24］Wang Kai， Lin Yu’an， Weissmann B， et al. Planit： planning and instantiating indoor scenes with relation graph and spatial prior networks［J］. ACM Trans on Graphics， 2019， 38（4）： article No.132.

［25］Ritchie D， Wang Kai， Lin Yu’an. Fast and flexible indoor scene synthesis via deep convolutional generative models［C］//Proc of IEEE/CVF Conference on Computer Vision and Pattern Recognition. Piscataway， NJ： IEEE Press， 2019： 6175-6183.

［26］Washington D C. Shopping center development handbook［M］.［S.l.］： Intellectual Property Publishing House and China Water & Power Press， 1999.

［27］Narazaki Y. Shop design［M］.［S.l.］：Ltd and Science Press， 1985.

［28］Zhang Shaokui， Liu Jiahong， Li Yike， et al. Automatic generation of commercial scenes［C］//Proc of the 31st ACM International Confe-rence on Multimedia. New York： ACM Press， 2023： 1137-1147.

［29］George A. The curator’s handbook： museums， commercial galleries， independent spaces［M］.［S.l.］：Thames & Hudson， 2015.

［30］Ngo D C L， Teo L S， Byrne J G. Modelling interface aesthetics［J］. Information Sciences， 2003， 152： 25-46.