鞏現(xiàn)勇,武 芳

1.信息工程大學(xué)地理空間信息學(xué)院,河南鄭州 450052;2.地理信息工程國家重點(diǎn)實(shí)驗(yàn)室,陜西西安 710054

城市建筑群網(wǎng)格模式的圖論識別方法

鞏現(xiàn)勇1,2,武 芳1

1.信息工程大學(xué)地理空間信息學(xué)院,河南鄭州 450052;2.地理信息工程國家重點(diǎn)實(shí)驗(yàn)室,陜西西安 710054

建筑群空間分布模式體現(xiàn)了城市的物質(zhì)形式及其與社會經(jīng)濟(jì)功能之間的關(guān)系,反映了城市的空間結(jié)構(gòu)特征,對于制圖綜合和多尺度表達(dá)等具有重要意義。結(jié)合國內(nèi)外對該問題的研究,提出基于圖論的建筑群網(wǎng)格模式識別方法。首先分析研究網(wǎng)格模式的認(rèn)知特征和定義。然后利用Delaunay三角網(wǎng)構(gòu)建建筑群的鄰近關(guān)系,生成鄰近圖;從Gestalt視覺準(zhǔn)則出發(fā),基于三角剖分模型建立視覺距離;考慮直線模式的直線性、緊湊性等約束條件識別出交叉的多連通直線模式。最后對直線模式建立相交圖和方向關(guān)系圖,通過求解極大完全子圖、連接、相交和后期修建等圖運(yùn)算,實(shí)現(xiàn)網(wǎng)格模式的識別。試驗(yàn)表明該方法能夠識別出明顯網(wǎng)格模式,其識別結(jié)果符合人類空間認(rèn)知特點(diǎn)。

制圖綜合;建筑群;網(wǎng)格模式;模式識別;圖論

1 引 言

如何從矢量地圖中自動挖掘隱含的知識、關(guān)系或內(nèi)在模式,并指導(dǎo)地圖設(shè)計(jì)編繪和時空數(shù)據(jù)更新等,一直是困擾地圖學(xué)者的難題[1-2]?？臻g分布模式是指核心地理要素在空間分布形態(tài)上表現(xiàn)出的可以明確命名且能夠識別的形狀或排列[2],是空間數(shù)據(jù)增強(qiáng)的基本內(nèi)容之一,是多尺度、多時相時空關(guān)聯(lián)的關(guān)鍵技術(shù),對于多模式時空綜合、多尺度表達(dá)、時空數(shù)據(jù)更新、時空數(shù)據(jù)挖掘、空間推理、智能交通系統(tǒng)、區(qū)位經(jīng)濟(jì)和城市規(guī)劃等具有重要理論意義和應(yīng)用價(jià)值[1-5]。

空間模式,從所涉及的知識類別出發(fā),有兩種:一是空間(多)變量在連續(xù)或離散空間中表現(xiàn)出的分布規(guī)律性、異常性、時空趨勢和時空關(guān)聯(lián)性,屬于空間統(tǒng)計(jì)范疇,關(guān)注語義信息的內(nèi)涵;二是地理要素在鄰近地理空間中所體現(xiàn)出的組織、布局、排列以及功能上顯著的空間結(jié)構(gòu)和關(guān)系,即本文的研究范疇,稱之為地圖的空間分布模式,關(guān)注空間的外延。建筑群的空間分布是制圖綜合、多尺度表達(dá)和時空數(shù)據(jù)更新等必須考慮和保持的空間特征,其自動識別則屬于空間推理范疇,是時空數(shù)據(jù)挖掘的研究熱點(diǎn)和難點(diǎn)之一[2-5]。在小比例尺地圖上,建筑群綜合考慮空間和語義特點(diǎn),主要基于自然屬性和網(wǎng)絡(luò)要素(道路、水系等)劃分[6-7];對于中大比例尺的建筑群分布,當(dāng)前研究多集中于聚群分組,主要包括兩個過程[5,8-9]:①基于最小支撐樹的空間聚類;②基于Gestalt原則的多參數(shù)控制的后期修剪。在此基礎(chǔ)上,還有多參數(shù)控制法、區(qū)域綜合法、智能優(yōu)化法等實(shí)現(xiàn)建筑群自動聚群[10-14]。然而,這些研究只是對建筑群進(jìn)行了初步的粗略聚群,其聚群粒度大小不一,地理意義模糊,不能高效建立時空關(guān)聯(lián),不能夠滿足多尺度表達(dá)與制圖綜合等需要;而且聚群結(jié)果形態(tài)復(fù)雜、不規(guī)則,大多數(shù)不可名狀,不能精確刻畫建筑群的空間分布特征。因此有必要更進(jìn)一步探測、識別隱含于建筑群的空間模式信息。文獻(xiàn)[15]通過對上述基于圖識別方法中的鄰近圖進(jìn)行反復(fù)修剪,來實(shí)現(xiàn)直線模式的挖掘;文獻(xiàn)[16]采用直線模板匹配方法進(jìn)行直線排列結(jié)構(gòu)的識別;文獻(xiàn)[17]直接利用鄰近關(guān)系圖識別網(wǎng)格模式用于建筑物典型化。

網(wǎng)格模式是建筑群分布的典型模式之一,常見于規(guī)劃整齊的城市小區(qū)等。本文在前期研究基礎(chǔ)之上,基于圖論進(jìn)行建筑群網(wǎng)格模式識別,需要解決以下3個問題:①網(wǎng)格模式的認(rèn)知特征和定義;②識別建筑群的基本模式——直線型;③利用已有的直線模式進(jìn)行網(wǎng)格模式的識別。

2 建筑群網(wǎng)格模式的認(rèn)知特征

熟悉和有意義的事物容易成為知覺對象。根據(jù)心理學(xué)的信息論度量方法,典型的、有意義的空間結(jié)構(gòu)特征是(視覺)信息最集中的地方。結(jié)構(gòu)特征識別是人類對空間信息進(jìn)行感知、識別和推理的過程,是地圖句法學(xué)的重要研究內(nèi)容。建筑群的空間分布具有豐富的幾何結(jié)構(gòu)模式,具有整體感、秩序感、均衡感、空間感。人類對建筑群模式的視覺思維認(rèn)知具有選擇性、注視性和結(jié)構(gòu)聯(lián)想性。研究人類對建筑群模式的空間認(rèn)知規(guī)律,可以有效指導(dǎo)算法設(shè)計(jì),為計(jì)算機(jī)進(jìn)行建筑群模式的自動識別提供理論依據(jù)和技術(shù)支持。

網(wǎng)格模式是建筑群的典型模式之一,其拓?fù)涓兄P(guān)系具有層次性:如圖1(a)中,從宏觀上看,網(wǎng)格模式由一組近似平行分布的直線排列建筑群與另一組近似平行的直線排列建筑群,以近似正交的方式相交構(gòu)成;從微觀上看,網(wǎng)格模式由一組尺寸、形狀等相似的建筑物構(gòu)成,而建筑物之間的空間分布滿足特定的排列方式——直線排列。本文采用自下而上的思想,首先通過建筑群的相似特性(形狀、方向和距離)及特定排列規(guī)律(直線分布)識別直線模式,然后基于直線模式的特定組合(正交關(guān)系)實(shí)現(xiàn)網(wǎng)格模式的識別。

直線模式的正確識別是網(wǎng)格模式識別的前提和保障。直線是視知覺拓?fù)淅碚摰幕疽?是指點(diǎn)在空間內(nèi)沿相同或相反方向運(yùn)動的軌跡。建筑群直線模式是城市建筑群在宏觀層次上表現(xiàn)出來的一種有規(guī)律的空間分布、配置。在中、大比例尺地圖上,建筑物表現(xiàn)為幾何形態(tài)上的多邊形,具有方向、形狀等幾何特征,即本文下述的單個建筑物自身的局部變量。由此,根據(jù)單個建筑的局部方向和一個建筑群模式的全局方向兩者之間的關(guān)系,建筑群直線模式有廣義(松弛約束,linear line)和狹義(嚴(yán)格約束,straight line)之分。大量認(rèn)知研究和試驗(yàn)表明,對于建筑群,狹義的直線模式應(yīng)滿足兩方面:①模式群內(nèi)部的各個建筑的局部方向一致,且模式的全局方向與各建筑物的主方向近似相同(如圖1(b))或正交(如圖1(c));②模式內(nèi)各建筑物在形狀、大小和方向等方面“相似”。狹義直線模式是視知覺認(rèn)知的直接結(jié)果,其分布形態(tài)最容易受人類視知覺的感知和捕獲。廣義的直線模式是指模式群內(nèi)建筑的局部方向不一致而其質(zhì)心大致呈直線分布(如圖1(d)),或者雖然局部方向一致但與群模式的全局方向呈“斜直線”分布(如圖1(e))。由廣義直線模式相交構(gòu)成的空間群分布在視知覺拓?fù)鋵哟紊喜荒茌^好地滿足嚴(yán)格意義上的網(wǎng)格模式的定義(如圖1(f))。

圖1 網(wǎng)格模式的認(rèn)知特征Fig.1 Cognitive characteristics of grid pattern

3 多連通直線模式信息提取方法和步驟

模式應(yīng)從幾何、拓?fù)洹h(huán)境上下文和文化差異等方面保證其易讀性、簡潔性和可分辨性。直線模式是最簡潔、最直接的模式,是網(wǎng)格模式識別的基礎(chǔ)。其影響因素至少有:模式與背景、鄰近性、相似性、方向性、連通性、連續(xù)性、完整和閉合性、同趨勢性和簡潔性等。其中,模式與背景是視覺選擇性的結(jié)果,主要解決模式存在的意義和價(jià)值,是模式識別的動機(jī);連通性可以用鄰近性代替(兩目標(biāo)距離為0);連續(xù)性、完整和閉合性可以由鄰近性、相似性與方向性得到;同趨勢性在靜態(tài)地圖中不存在;構(gòu)型的簡潔性為已知因素,即需要識別的感興趣的建筑群分布模式。因此在建筑群模式識別時,只考慮鄰近性、相似性和方向性[10,18]。文獻(xiàn)[8,10,18—19]深入研究了用于建筑群自動聚群的Gestalt原則,都從不同方面驗(yàn)證了利用距離、大小、方向三者的組合能夠表達(dá)鄰近性、相似性和方向性等三者的主要矛盾,并通過不同類型的數(shù)據(jù)驗(yàn)證了其可行性和有效性。

因此,考慮到人作為認(rèn)知主體在感知、識別和推理直線模式時主要參考其直線性、緊湊性和相似性等組織規(guī)律,此處結(jié)合數(shù)學(xué)方法和幾何模型,以建筑物的大小、方向和距離等3個基本參數(shù)建立認(rèn)知意義上的直線模式結(jié)構(gòu)化參數(shù)(表1),用以描述模式的形態(tài)和結(jié)構(gòu)規(guī)則,從而作為約束條件進(jìn)行直線模式的提取。

表1 直線模式結(jié)構(gòu)化參數(shù)Tab.1 Structural parameters for linear pattern

在結(jié)構(gòu)化參數(shù)中,局部和全局方向差異對模式的直線構(gòu)型至關(guān)重要。其中,局部方向差異僅能保證相鄰兩建筑物的方向差異滿足直線模式要求,而全局方向差異在整體上使得整個直線模式的局部方向差異的方差滿足直線特征,從而避免僅由局部方向差異約束而引起的圓弧形或蛇形排列的出現(xiàn),如圖2(a)、(b)。

圖2 圓弧形和蛇形排列Fig.2 Arc-like and snake-like alignment

文獻(xiàn)[15—16]識別出的直線模式具有單連通性,只能滿足某個方向的直線模式的識別,不允許模式的相交。這不符合人類“橫看成嶺側(cè)成峰”的認(rèn)知心理,亦不能支持網(wǎng)格模式識別。一個建筑物參與多個直線模式時會產(chǎn)生直線模式的相交現(xiàn)象。為允許不同方向相互交叉的直線模式的存在,本文通過以下方法和步驟進(jìn)行提取:

(1)空間鄰近關(guān)系捕捉。對建筑物多邊形沿線加密,并建立Delaunay三角網(wǎng),如圖3(a)。刪除建筑物內(nèi)部及其凹部的三角元,如圖3(b)。對剩余的通視域三角元建立骨架線,實(shí)現(xiàn)建筑群剖分,如圖3(c)。用圖表達(dá)鄰近關(guān)系,圖的節(jié)點(diǎn)表示建筑物的質(zhì)心,圖的邊表明兩個建筑物被其之間的通視域三角元直接相連,如圖3(d)。此步驟保證了Gestalt原則中的鄰近性。

(2)異質(zhì)性修剪。設(shè)置面積比、正對投影長度的閾值δArea和δface;遍歷鄰近圖的所有邊,若被其連接的兩個建筑物正對投影長度小于δface(圖3 (e)虛線),或者面積比小于δArea(圖3(f)虛線),則刪除該邊。其中,利用面積比修剪保證Gestalt原則中的大小相似性,利用正對投影長度修剪保證直線模式的方向性。

(3)構(gòu)建視覺距離加權(quán)圖。對于圖3(c),定義兩個建筑物間的視覺距離為

(4)直線模式提取。經(jīng)過每個節(jié)點(diǎn)的直線模式的數(shù)目不可能大于其連通度。記連接點(diǎn)v的連通度為Degree(v),其被訪問的次數(shù)為Visited-Count(v),設(shè)方向和視覺距離容差分別為δorient和δdis,則直線模式的提取算法如下:

步驟1選擇一個建筑物作為種子起點(diǎn)v0。

步驟2訪問與v0相接的點(diǎn)vi,如果Visited-Count(vi)＝Degree(vi),則結(jié)束當(dāng)前模式鏈;否者,判斷Degree(vi):

步驟2-1 Degree(vi)＝1,若滿足直線條件,則此連接點(diǎn)為直線模式的一部分,加入當(dāng)前模式鏈表;否則結(jié)束當(dāng)前模式鏈提取。重新選擇種子起點(diǎn),goto步驟2。Visited Count(vi)加1。

步驟2-2 Degree(vi)＞1,若存在滿足直線條件的邊,則加入當(dāng)前模式鏈表;否則,以此節(jié)點(diǎn)為種子起點(diǎn),新建模式鏈表,goto步驟2。Visited-Count(vi)加1。

步驟3如果鄰近圖所有節(jié)點(diǎn)均滿足Visited-Count(vi)＝Degree(vi),整個圖層的直線模式提取過程結(jié)束。

注:直線條件是指邊內(nèi)側(cè)夾角與當(dāng)前模式鏈表建筑群全局方向差異的百分比在δorient以內(nèi),視覺距離差異與當(dāng)前模式鏈表建筑群視覺距離的平均值的百分比在δdis以內(nèi)。

圖3 直線模式提取過程Fig.3 Process of linear pattern extraction

以上步驟可初步識別出多連通直線模式,如圖3(g)。其優(yōu)點(diǎn)在于:①識別過程僅涉及距離、大小和方向等參數(shù),參數(shù)意義明確,易于理解;②利用節(jié)點(diǎn)的連通度控制對鄰近圖的多次掃描,實(shí)現(xiàn)了所有可能方向的直線模式的提取,保證其完備性,且為網(wǎng)格模式識別提供支持;③對同質(zhì)性修剪之后的鄰近圖進(jìn)行視覺距離加權(quán),降低算法的時間復(fù)雜度。其中,降低算法的時間復(fù)雜度主要體現(xiàn)在步驟2與步驟3的執(zhí)行順序上。相較于現(xiàn)有文獻(xiàn)[8,15]計(jì)算每個邊的視覺距離而言,本文先進(jìn)行同質(zhì)性修剪,則只需要對鄰近圖中滿足面積比和正對投影長度比的邊進(jìn)行視覺距離的計(jì)算。算法運(yùn)行減少的復(fù)雜度等于同質(zhì)性修剪掉的邊的數(shù)目。例如對于圖3,本文方法減少了10條邊(圖3(e)修剪掉8條、圖3(f)修剪掉2條)的視覺距離的計(jì)算代價(jià)。

4 基于圖論的網(wǎng)格模式識別

圖論是研究事物相互關(guān)系的抽象代數(shù)。網(wǎng)格模式由相互近似正交的直線模式構(gòu)成。本文在直線模式識別的基礎(chǔ)上,根據(jù)網(wǎng)格模式的認(rèn)知特點(diǎn),通過圖論算法識別 “垂直交錯”的直線模式,從而提取網(wǎng)格模式。圖論關(guān)鍵定義如下。

定義1:在圖G＝〈V,E〉中,若從節(jié)點(diǎn)vi出發(fā),沿一些邊經(jīng)過一些節(jié)點(diǎn)vp1、vp2、…、vpm,到達(dá)節(jié)點(diǎn)vj,則稱節(jié)點(diǎn)序列(vp1,vp2,…,vpm)為從節(jié)點(diǎn)vi到節(jié)點(diǎn)vj的路徑(path)。

定義2:在無向圖中,若從節(jié)點(diǎn)vi到節(jié)點(diǎn)vj有路徑,則稱節(jié)點(diǎn)vi與vj是連通的(connected)。

定義3:如果圖中任意一對節(jié)點(diǎn)都是連通的,則稱此圖是連通圖(connected graph)。

定義4:非連通圖的極大連通子圖叫作連通分量(connected component)。

定義5:Intersection運(yùn)算,是指兩個或多個圖的交集,只有兩個或多個圖中均存在的邊才會保留到Intersection運(yùn)算結(jié)果中。即:對于圖G1＝〈V1, E1〉和圖G2＝〈V2,E2〉,所有ei∈E1且ei∈E2,則圖GIntersection＝{〈vi,ei〉|ei∈E1且ei∈E2}稱為G1與G2的Intersection運(yùn)算的結(jié)果。

定義6:Jion運(yùn)算,是指在圖G1＝〈V1,E1〉和圖G2＝〈V2,E2〉中,對于所有?vp∈V1且所有?vq∈V2,連接vp,vq所組成邊ei＝〈vp,vq〉作為Join運(yùn)算結(jié)果圖的邊。即圖GJoin＝{〈vi, ei〉|ei＝〈vp,vq〉,?vp∈V1且?vq∈V2}稱為G1與G2的Join運(yùn)算的結(jié)果。

由第2節(jié)網(wǎng)格模式認(rèn)知的層次性特點(diǎn)可知,組成網(wǎng)格模式的直線模式之間需要滿足以下3點(diǎn):①每組直線模式近似平行;②兩組直線模式近似正交;③兩組直線模式具有連接關(guān)系(相交或相接)。對應(yīng)于以上3點(diǎn)要求,利用圖論識別網(wǎng)格模式的基本思想是:①根據(jù)方向關(guān)系圖計(jì)算近似平行的直線模式組;②選取近似正交的所有直線模式組進(jìn)行Join運(yùn)算,得到所有可能的網(wǎng)格模式;③將之與直線模式的連接圖進(jìn)行Intersection運(yùn)算,保留那些具有連接關(guān)系的直線模式組,剔除那些不相交和不相接的直線模式組。通過以上3步可獲得初始的網(wǎng)格模式,對其進(jìn)行后期修剪得出建筑群的網(wǎng)格模式。以圖4(a)為例,網(wǎng)格模式提取算法的流程如下:

(1)根據(jù)第2節(jié)算法提取建筑群的多連通直線模式。建立直線模式的連接圖G＝〈V,E〉。圖的節(jié)點(diǎn)V代表直線模式,節(jié)點(diǎn)之間的連接E表示兩個直線模式相交或者相接。如圖4(a)中,直線模式{1,2,3}與{4,5,6}相交,{8,9,10,11}與{12,13}相交。則此建筑群的連接圖如圖4(b)所示。該步驟能夠保證組成網(wǎng)格的直線模式組均相交或者相接。例如{7}與{1,2,3}雖然存在正交關(guān)系,但由于不存在連接關(guān)系,因此不能構(gòu)成網(wǎng)格,將在下文步驟(5)中被排除。

(2)建立建筑群直線模式的方向關(guān)系圖ORG＝〈OV,OE〉,圖的節(jié)點(diǎn)OV代表直線模式,節(jié)點(diǎn)之間的連接OE表示兩相連的直線模式具有近似相同的方向(平行或者共線),兩者可以不相交或者不相接。如圖4(c)中,直線模式組{1,2,3}、{4,5,6,7}、{8,9,10,11}、{12,13}分別具有近似相同的方向。該步驟提取了所有可能形成網(wǎng)格的直線模式。

(3)提取方向關(guān)系圖ORG的連通分量ORG_ CC。如果ORG只有一個連通分量,則說明要么不存在網(wǎng)格模式,要么方向閾值設(shè)置過大,應(yīng)考慮重新設(shè)置。這是因?yàn)槿糁挥幸粋€連通分量,則所有直線模式的角度都近似相同,從而導(dǎo)致無法構(gòu)成網(wǎng)格。閾值設(shè)置為10°時,從圖4(c)中提取得到4個方向連通子圖A、B、C和D,見圖4(c)中虛線橢圓框。該步驟的作用是提取近似平行的直線模式組。

(4)方向關(guān)系圖分組。對方向關(guān)系圖ORG的每個連通分量ORG_CC,求解其極大完全子圖ORG_CC_max。完全子圖是指每個節(jié)點(diǎn)都與其他所有節(jié)點(diǎn)相連的一種滿秩圖。該步驟可以剔除某些孤立直線模式,將直線模式強(qiáng)制分為特定組,每個組內(nèi)的直線模式方向相似(平行或者共線)。圖4(c)中的子圖A、B、C、D均已是極大完全子圖。

(5)初始網(wǎng)格模式信息提取。計(jì)算步驟(4)中每個極大完全子圖ORG_CC_max的平均方向,利用閾值控制選取方向近似正交的兩個極大完全子圖進(jìn)行Join連接運(yùn)算,其結(jié)果與連接圖G進(jìn)行Intersection相交運(yùn)算。其中Join連接運(yùn)算的目的是保留所有具有正交關(guān)系的直線模式,如圖4(d)中所示的{1,2,3}與{4,5,6,7},{8,9,10, 11}與{12,13}分別近似正交;而Intersection運(yùn)算是為了剔除那些不相交或者不相接的直線模式,如圖4(d)中虛線所示的{7}由于與{1,2,3}既不相交也不相接,因此在此運(yùn)算下被剔除。經(jīng)過以上兩個圖運(yùn)算,剩下來的節(jié)點(diǎn)滿足相連且正交,如圖4(d)中的實(shí)線所示。由此便得到了初始的網(wǎng)絡(luò)InitG,如圖4(e)。

(6)網(wǎng)絡(luò)模式提取。計(jì)算Init G的連通分量,每一個連通分量即為一個網(wǎng)格模式。如圖4(e)中計(jì)算的兩個網(wǎng)格模式的連通分量分別為GA＝{1,2,3,4,5,6}和GB＝{8,9,10,11,12,13}。

(7)網(wǎng)絡(luò)模式后期處理。步驟(6)提取的網(wǎng)格模式可能會存在“毛刺”或者“尾巴”等不合理之處。剔除此類不合理建筑物的處理方法是:將直線模式在線的節(jié)點(diǎn)處打斷成弧段,循環(huán)刪除連通度小于2的建筑節(jié)點(diǎn)。如圖4(f)中斜線填充的建筑物均從GA和GB中被剔除。由此得到網(wǎng)格模式的最終結(jié)果如圖4(f)所示。

圖4 網(wǎng)格模式識別過程Fig.4 Process of grid pattern recognition

本文算法進(jìn)行網(wǎng)格模式識別主要具有以下優(yōu)點(diǎn):①采用“分解—組合”的思想,按照其認(rèn)知特點(diǎn)的層次性,將網(wǎng)格模式這一復(fù)雜的非線性認(rèn)知概念分解為直線模式這一線性認(rèn)知概念的正交組合,認(rèn)知意義更加簡潔;②網(wǎng)格模式提取過程僅涉及方向這一類參數(shù),參數(shù)的地理含義明確,便于調(diào)整;③在直線模式基礎(chǔ)之上進(jìn)行網(wǎng)格模式的識別,充分利用了連續(xù)多尺度的數(shù)據(jù)。對于地圖綜合和多尺度表達(dá)等問題,地理信息的處理順序是由大比例尺向小比例尺逐級級聯(lián)漸進(jìn)進(jìn)行的,例如由1∶1000綜合生成1∶5000數(shù)據(jù),再由1∶5000綜合生成1∶10 000數(shù)據(jù)。因此,地理信息聚集的粒度由小到大。直線模式是一組建筑物,而網(wǎng)格模式則是一組直線模式,“建筑物—直線模式—網(wǎng)格模式”是空間域粒度由小變大的層次關(guān)系,亦即對應(yīng)不同比例尺的地圖。由直線模式提取識別網(wǎng)格模式,充分利用了上一比例尺的直線模式信息。

5 試驗(yàn)與討論

5.1 試 驗(yàn)

為檢驗(yàn)上述識別方法的有效性,本文基于Arc Engine設(shè)計(jì)實(shí)現(xiàn)了以上算法,并融入課題組試驗(yàn)平臺GxGIS。為更好體現(xiàn)本文算法的合理性和適用性,試驗(yàn)分為兩組,采用兩組不同空間分布特點(diǎn)的數(shù)據(jù)進(jìn)行測試。試驗(yàn)中直線模式提取的5種參數(shù)的范圍均為[0,1],參數(shù)設(shè)置的指導(dǎo)思想是:面積比閾值和正對投影長度的閾值越大(經(jīng)驗(yàn)取值[0.6,1]),局部方向差異、全局方向差異和視覺距離容差越小(經(jīng)驗(yàn)取值[0,0.4]),模式的直線性越強(qiáng)。網(wǎng)格模式提取過程中,方向關(guān)系圖計(jì)算連通分量的方向閾值經(jīng)驗(yàn)范圍為[0°,10°],近似正交是指角度在[80°,100°]內(nèi)。

試驗(yàn)數(shù)據(jù)1為某城市1∶10 000地圖上的部分建筑群,試驗(yàn)區(qū)域包含18個小區(qū),162個建筑物,如圖5(a)。該試驗(yàn)區(qū)域建筑群方向分布多數(shù)相近,但一階鄰域內(nèi)要素的形狀有不同程度的變化;建筑群密集,但不均勻。不同方向、不同大小的建筑物交錯相鄰分布,存在一定的空間異質(zhì)性,整體分布上沒有全局平穩(wěn)的特征,但在某些方向上較為平穩(wěn),因此在視知覺上呈現(xiàn)出明顯的直線模式,網(wǎng)格模式分布現(xiàn)象并不太直觀和明顯。參考前人經(jīng)驗(yàn)[4,15],經(jīng)過反復(fù)測試,參數(shù)設(shè)置如表2。識別出的多連通直線模式如圖5(b),提取的網(wǎng)格模式如圖5(c)。

試驗(yàn)數(shù)據(jù)2為德國南部某城市地圖上的部分建筑群,數(shù)據(jù)源自O(shè)penStreet Map,比例尺為1∶3000。試驗(yàn)區(qū)域包含12個小區(qū),168個建筑物,如圖6(a)。該試驗(yàn)區(qū)域建筑群方向分布近似相近,一階鄰域內(nèi)要素的形狀變化較小,建筑群密集且均勻?？臻g同質(zhì)性較好,異質(zhì)性表現(xiàn)不明顯,整體上分布平穩(wěn),劇烈抖動現(xiàn)象較少。在視知覺上呈現(xiàn)出明顯的直線模式和網(wǎng)格模式等分布現(xiàn)象。經(jīng)過反復(fù)測試,參數(shù)設(shè)置如表2,識別出的多連通直線模式如圖6(b),提取的網(wǎng)格模式如圖6(c)。

表2 參數(shù)設(shè)置Tab.2 Advisable parameter setting

圖5 網(wǎng)格模式識別試驗(yàn)結(jié)果Fig.5 Experiment results of grid pattern recognition

圖6 網(wǎng)格模式識別試驗(yàn)結(jié)果Fig.6 Experiment results of grid pattern recognition

5.2 討 論

5.2.1 跨街區(qū)形成模式

由于沒有考慮道路、水系等其他具有網(wǎng)絡(luò)特征的要素的空間分割和限制,單圖層的建筑群模式識別允許跨街區(qū)組成直線或者網(wǎng)格模式,如圖5(b)、(c)與圖6(b)、(c)。城市空間的形態(tài)劃分,一方面是應(yīng)用多尺度表達(dá)的層次劃分方法,需要從地理尺度、影像分辨率、地圖載負(fù)量限制等方面考慮其合理性和適用性[20-21];另一方面需要兼顧建筑群的空間分布和形態(tài)等自然地理特征。為此, AGENT項(xiàng)目組利用多圖層協(xié)同輔助的方法,提出了基于區(qū)域劃分的思想,對水系、道路、境界等進(jìn)行關(guān)聯(lián),形成拓?fù)渚W(wǎng)絡(luò),將待綜合區(qū)域進(jìn)行形態(tài)劃分[6]。本文試驗(yàn)中以城市主干路網(wǎng)形成的街區(qū)為參考網(wǎng)絡(luò)要素,其劃分結(jié)果如圖5(d)、圖6(d)。

5.2.2 閾 值

首先,對于不同類型的模式,閾值由模式的特征決定,例如直線模式的直線性、緊密性,網(wǎng)格模式的垂直相交關(guān)系等。其次,對于同一種模式,不同的數(shù)據(jù)由于空間分布狀況不同,可能需要對閾值進(jìn)行微調(diào),但必須符合模式的視覺特征約束。因此對于不同的數(shù)據(jù),閾值不會發(fā)生太大的變化。例如5.1節(jié)兩組不同的試驗(yàn)數(shù)據(jù),雖然其參數(shù)閾值設(shè)置是不同的,但變化并不大(表2)。如圖7中,若僅考慮正對投影長度比而忽略其他因素對多連通直線模式的影響,圖7(a)、(b)、(c)分別為正對投影長度比閾值取0.95、0.85、0.8的試驗(yàn)結(jié)果。對比圖7發(fā)現(xiàn),隨著正對投影長度比閾值的放寬,直線模式的曲率越大,即由嚴(yán)格約束的狹義直線向松弛約束的廣義直線過度。最后,對于退化現(xiàn)象比較嚴(yán)重的直線模式,參數(shù)閾值因?qū)δＪ叫螒B(tài)的關(guān)注點(diǎn)不同而不同。例如只關(guān)注建筑群質(zhì)心位于同一條直線,不考慮形狀、方向等因素影響的退化直線模式。如圖8中橢圓框出的4個建筑物的主方向分別為121.68°、120.54°、10.31°和13.5°,當(dāng)方向閾值放寬至0.08時,由于橢圓框中的要素的質(zhì)心排列與其下方的直線模式為近似直線,因而被納入成為直線模式的一部分。

圖7 正對面積比影響Fig.7 Facing ratio effect

圖8 直線退化現(xiàn)象Fig.8 Degeneration of line pattern

5.2.3 形狀信息

建筑群分布模式對建筑群的形狀有很強(qiáng)的依賴性?；诖蠖鄶?shù)建筑物的規(guī)則性考慮,本文將建筑物抽象為其最小面積外接矩形,用于描述其方向和正對投影長度,在一定程度上造成了形狀信息的損失。如何用定量化模型描述形狀一直是GIS必須面對的難題[22]。對于少數(shù)的矩形度較小的非規(guī)則建筑物影響較大,其分布模式的退化現(xiàn)象較嚴(yán)重,可以放寬對形狀參數(shù)(如面積比和正對投影長度比)的限制,如圖8中示例。

5.2.4 方向的度量

不同的方向度量方法也可能會對識別結(jié)果產(chǎn)生影響。文獻(xiàn)[23]對現(xiàn)有的各種度量方法進(jìn)行了深入剖析,并對較典型的Longest edge、Weighted Bisector、Smallest MBR、Wall average和Statistical weighting等5種方法進(jìn)行了詳細(xì)的對比,認(rèn)為Smallest MBR方法最優(yōu),被研究和認(rèn)同的范圍較廣[23]。即本文采用的最小面積外接矩形方法。對于方向度量方法的影響:首先,每種度量方法計(jì)算的方向肯定是唯一的、不變的;其次,建筑群模式識別的方向約束為兩個建筑物之間的相對方向。因此,只要選定某種方向度量方法,則在模式識別過程中,方向容差的閾值δorient是可以固定的。但由于不同的度量方法計(jì)算所得的建筑物的方向可能不同,因此會影響識別結(jié)果。

5.2.5 進(jìn)一步分析和評估結(jié)果的可靠性

視覺認(rèn)知易受人類的個體差異性和主觀性的影響,如環(huán)境、性別、年齡、教育背景和生長環(huán)境等。如圖9中,由于箭頭指向的噪聲建筑物的缺失或存在,對建筑群網(wǎng)格模式的認(rèn)知造成了一定的影響,不同的認(rèn)知主體可能會產(chǎn)生不同的認(rèn)知結(jié)果。目前,尚無定量的方法來客觀評價(jià)基于視知覺空間認(rèn)知的聚群結(jié)果的可靠性,這一直是該領(lǐng)域和心理學(xué)界的一個難題。國內(nèi)外仍都是通過人眼觀察或者與人工標(biāo)繪的結(jié)果進(jìn)行對比,從而評價(jià)聚群結(jié)果的可靠性,如文獻(xiàn)[2,4—14]。根據(jù)認(rèn)知心理學(xué)試驗(yàn)方法的要求,本文通過問卷調(diào)查的方式評價(jià)結(jié)果的可靠性。調(diào)查對象為4名制圖生產(chǎn)單位工程師、3名助理工程師、1名地圖專業(yè)講師、42名地圖專業(yè)學(xué)生。通過不同區(qū)域數(shù)據(jù)測試的調(diào)查結(jié)果表明,本文方法的可信度在67%以上。

圖9 網(wǎng)格模式的認(rèn)知影響Fig.9 Cognitive effects of grid pattern

6 結(jié) 論

由于矢量數(shù)據(jù)的離散性和稀疏性等,對其進(jìn)行空間知識挖掘一直是一個難題。本文首先分析了網(wǎng)格模式的認(rèn)知特點(diǎn),界定了直線模式和網(wǎng)格模式的定義。通過參數(shù)判別法挖掘隱含于建筑群中的多連通直線模式,利用結(jié)構(gòu)化參數(shù)直接對鄰近圖進(jìn)行反復(fù)修剪,一定程度上克服了現(xiàn)有方法的不足,所提取出的直線模式允許相交現(xiàn)象,更加符合人類空間認(rèn)知特點(diǎn),亦為建筑群網(wǎng)格模式識別提供了支撐。依據(jù)網(wǎng)格模式垂直相交的特點(diǎn),通過圖論算法,對已識別出的多連通直線模式進(jìn)行圖操作,進(jìn)而識別網(wǎng)格模式,識別結(jié)果基本能夠符合人類認(rèn)知。需要進(jìn)一步研究的問題主要包括:①視知覺拓?fù)淅碚搶δＪ阶R別的指導(dǎo)意義及其參數(shù)化表示;②模式的結(jié)構(gòu)化參數(shù)的各種閾值等需要經(jīng)過反復(fù)試驗(yàn)確定;③空間對象的形狀定量描述模型。

[1] WU Fang,QIAN Haizhong,DENG Hongyan,et al.Intelligent Spatial Information Processing for Automated Map Generalization[M].Beijing:Science Press,2008: 292-305.(武芳,錢海忠,鄧紅艷,等.面向地圖自動綜合的空間信息智能處理[M].北京:科學(xué)出版社,2008: 292-305.)

[2] STEINIGER S.Enabling Pattern-ware Automated Map Generalization[D].Zurich:Zurich University,2007.

[3] RUIZ J J,ARIZA F J,URENA M A,et al.Digital Map Conflation:a Review of the Process and a Proposal for Classification[J].International Journal of Geographical Information Science,2011,25(9):1439-1466.

[4] QI Hhuabin.Detection and Generalization of Changes in Settlements for Automated Digital Map Updating[D].Hong Kong:The Hong Kong Polytechnic University,2009.

[5] LI Zhilin,YAN Haowen,AI Tinghua,et al.Automated Building Generalization Based on Urban Morphology and Gestalt Theory[J].International Journal of Geographical Information Science,2004,18(5):514-534.

[6] UNI-ED,IGN.Strategic Algorithms Using Organisations [R].Unizh:ESPRIT/LTR,2001.

[7] WU Fang,QIAN Haizhong,DENG Hongyan,et al.Quality Evaluation Model for Automated Map Generalization[M].Beijing:Science Press,2009:11-64.(武芳,錢海忠,鄧紅艷,等.地圖自動綜合質(zhì)量評估模型[M].北京:科學(xué)出版社,2009:11-64.)

[8] AI Tinghua,GUO Renzhong.Polygon Cluster Pattern Mining Based on Gestalt Principles.[J].Acta Geodaetica et Cartographica Sinica,2007,36(3):302-308.(艾廷華,郭仁忠.基于格式塔識別原則挖掘空間分布模式[J].測繪學(xué)報(bào),2007,36(3):302-308.)

[9] ZHAO Binbin,DENG Min,LI Guangqiang,et al.A New Hierarchical Spatial Index Based on Urban Morphology.[J].Acta Geodaetica et Cartographica Sinica,2010,39 (4):435-440.(趙彬彬,鄧敏,李光強(qiáng),等.基于城市形態(tài)學(xué)原理的面狀地物層次索引方法[J].測繪學(xué)報(bào),2010,39 (4):435-440.)

[10] YAN Haowen,WEIBEL R,YANG Bisheng.A Multiparameter Approach to Automated Building Grouping and Generalization[J].Geoinformatica,2008,12(1):73-89.

[11] BASARANER M,SELCUK M.A Structure Recognition Technique in Contextual Generalization of Buildings and Built-up Areas[J].The Cartographic Journal,2008,45 (4):274-285.

[12] ALLOUCHE M K,MOULIN B.Amalgamation in Cartographic Generalization Using Kohonen’s Feature Sets[J].International Journal of Geographical Information Science, 2005,19(8-9):899-914.

[13] SESTER M.Optimization Approaches for Generalization and Data Abstraction[J].International Journal of Geographical Information Science,2005,19(8):871-897.[14] REGN A ULD N.Contextual Building Typification in Automated Map Generalization[J].Algorithmica,2001, 30(2):312-333.

[15] ZHANG Xiang,AI Tinghua,STOTER J,et al.Building Pattern Recognition in Topographic Data:Examples on Collinear and Curvilinear Alignments[J].GeoInformatica, 2013,17(1):1-33.

[16] RAINSFORD D,MACKNESS W.Template Matching in Support of Generalization of Rural Buildings[C]∥Proceedings of the 10th International Symposium on Spatial Data Handling.Berlin:Springer,2002:137-151.

[17] ANDERS K H.Grid Typification[C]∥Proceedings of the 12th International Symposium on Spatial Data Handling.Berlin:Springer,2006:633-642.

[18] Y AN Haowen,YING Shen,LI Lin.An Approach for Automated Building Grouping and Generalization Considering Multiple Parameters[J].Geomatics and Information Science of Wuhan University,2008,33(1):51-54.(閆浩文,應(yīng)申,李霖.多因子影響的地圖居民地自動聚群與綜合研究[J].武漢大學(xué)學(xué)報(bào):信息科學(xué)版,2008,33(1):51-54.)

[19] AI Tinghua,OOSTEROM P.GAP-tree Extensions Based on Skeletons[C]∥Proceedings of the Advances in Spatial Data Handling.Berlin:Springer-Verlag,2002:501-514.

[20] GOODCHILD M F.Scale in GIS:A Review[J].Geomorphology,2011,130(1-2):5-9.

[21] BREWER C A,BUTTENFIELD B P.Mastering Map Scale: Balancing Workloads Using Display and Geometry Change in Multi-scale Mapping[J].Geoinformatica,2010,14(2): 221-239.

[22] LI Wenwen,GOODCHILD M F,CHURCH R.An Efficient Measure of Compactness for Two-dimensional Shapes and Its Application in Regionalization Problems[J].International Journal of Geographical Information Science,2013, 27(6):1227-1250.

[23] DUCHENE C,BARD S,BARILLOT X,et al.Quantitative and Qualitative Description of Building Orientation[C]∥Proceedings of the Fifth Workshop on Progress in Automated Map Generalization.Paris:ICA,2003.

(責(zé)任編輯:宋啟凡)

The Graph Theory Approach to Grid Pattern Recognition in Urban Building Groups

GONG Xianyong1,2,WU Fang1
1.Institute of Geospatial Information,Information Engineering University,Zhengzhou 450052,China;2.State Key Laboratory of Geo-information Engineering,Xi’an 710054,China

Map patterns in building groups embody the relationship of the material form of cities and their social-economic function,and reflect the city’s spatial structure,which have great importance in cartographic generalization and multi-scale representation.On the basis of related research home and abroad,a graph theory approach is proposed to recognize the grid pattern in building groups.Firstly the cognitive characteristics and definitions of grid pattern are analyzed.Then neighborhood relationship is captured by proximity graph with the help of Delaunay triangulation,and visual distance model is established considering the Gestalt principles.Multi-connected linear pattern is recognized with constrains such as linear arrangement and compactness.Finally the line pattern intersection graph and similar orientation graph are formed.The candidate grid patterns are extracted through graph operation such as finding maximal complete sub-graph,join,intersection and post-processing.Experiments show that this approach is effective,feasible and practicable for obvious grid pattern recognition with the agreement of human spatial cognitive characteristics.

cartographic generalization;building groups;grid pattern;pattern recognition;graph theory

GONG Xianyong(1988—),male,PhD candidate,majors in pattern recognition,automated cartographic generalization and spatio-temporal data analysis.

WU Fang

P208

A

1001-1595(2014)09-0960-09

國家自然科學(xué)基金(41171354;41101362;41171305;41471386);地理信息工程國家重點(diǎn)實(shí)驗(yàn)室開放研究基金(SKLGIE2013-M-4-6)

2013-06-05

鞏現(xiàn)勇(1988—),男,博士生,研究方向?yàn)槟Ｊ阶R別、自動制圖綜合和時空數(shù)據(jù)分析。

E-mail:gongxygis＠whu.edu.cn

武芳

E-mail:wufang_630＠126.com

GONG Xianyong,WU Fang.The Graph Theory Approach to Grid Pattern Recognition in Urban Building Groups[J].Acta Geodaetica et Cartographica Sinica,2014,43(9):960-968.(鞏現(xiàn)勇,武芳.城市建筑群網(wǎng)格模式的圖論識別方法[J].測繪學(xué)報(bào),2014,43 (9):960-968.)

10.13485/j.cnki.11-2089.2014.0125

修回日期:2014-03-05