基于工程圖三維重建中的預處理與信息提取技術研究

摘要：提出了基于邊界表示Brep方法的工程圖三維重建中對于二維工程圖紙進行預處理和信息提取的一系列實用算法，涉及到工程圖讀入、實體過濾、視圖分離、視圖坐標規格化以及視圖數據處理等流程。不但可以快速準確地獲得二維工程視圖中完備的幾何信息和拓撲信息，而且處理對象并不局限于標準的工程三視圖，對于工程一視圖、二視圖同樣可以處理。這些算法已經應用于一個CAD原型系統并取得了較好的效果，為后續的三維重建工作提供了良好的基礎。

關鍵詞：三維重建； 預處理； 信息提取； 視圖分離

中圖分類號：TP391文獻標志碼：A

文章編號：1001-3695(2007)04-0161-05

0引言

從二維視圖重建三維實體已經研究了近三十年，是CAD/CAM中的主要研究課題之一。目前的三維重建方法主要有自頂向下基于體素的CSG方法和自底向上基于邊界表示的Brep方法，兩種方法各有特點^[1～4]。在基于二維工程圖紙的形體重建方面，基于邊界表示的Brep方法有著先天的優勢^[5，6]。人們對該方法的研究越來越廣泛和深入，目前在某些領域已經開始得到實際應用。

工程圖預處理和信息提取是三維重建中的一項基本流程，同時也是三維重建工作的第一步，這一部分工作的好壞與否將直接影響到后期的重建工作。工程圖紙中并不是所有的信息均是三維重建所需要的，對于重建不需要的信息，如圖紙的邊框，文字標注等必須過濾掉。另外，二維圖紙的輸入是在整體坐標系下進行的，而從二維視圖到三維形體重建的基礎是視圖之間圖元投影關系。所以在三維重建之前必須對整個視圖進行視圖分離，即把圖紙中的每個圖元歸屬于一個視圖中。由于視圖投影的重疊性和積聚性以及繪圖者繪圖過程的不確定性，在投影面會有圖元重疊和相交情況的出現，對這些情況要進行適當的處理。以上這些均是工程圖預處理要完成的工作。其主要步驟包括：讀取工程圖實體元素，提取重建所需要的點、邊的信息；對工程圖進行視圖分離并對視圖坐標規格化；對視圖數據進行必要處理，將視圖中點和邊的信息存儲到相應的點集和邊集中，以便重建需要。

如何準確快速地實現視圖分離是其中的一項關鍵技術。國內外的研究者們相繼提出一些方法。傳統的視圖分離方法^[7，8]是根據角度判別法^[9](TurntotheLeftMost Rule)求出各個視圖的外部輪廓線，然后搜索位于每一輪廓內的二維實體。主要步驟為：將視圖中的曲線按照y坐標值增大的順序排列；在未分離的曲線中選擇y值最大的曲線作為跟蹤的起點，用角度判別法生成一個二維環，環中的曲線是某個視圖的邊界；收集所有位于該環內的曲線，分離出一個視圖，將這些曲線從輸入工程圖中移走；如果輸入數據中還包含其他曲線，則在其中選y值最大的曲線作為跟蹤的起點繼續分離。

雖然輪廓搜索的算法已經比較成熟，但是應用于二維轉三維的視圖分離時，通常每搜索一個視圖輪廓均需要先通過比較確定出一個起始點。當視圖的輪廓比較復雜，如包括許多邊界曲線時，運算量較大；而且如果曲線的遍歷方向選擇不正確，生成的二維環可能不是視圖的邊界環。為此，傳統方法必須生成所有經過初始邊的二維環，從中選擇最大環，這大大降低了算法的效率。

本文提出了改進的坐標軸投影分離法來實現視圖的分離。該方法避免了每一視圖外輪廓線的搜索，而且減少了每一個二維實體的比較次數，每一實體只需作兩次比較即可確定其所在的視圖。本文在此方法的基礎上進行了改進，引入了X、Y坐標鏈表，以此來判斷輸入工程圖的類型；根據不同的類型來調用相應的視圖分離方法，實現了對于各類視圖的分離。

本文在基于清華大學自主開發CAD系統——GEMS平臺下，實現了對于各類工程視圖（包括一視圖、二視圖和三視圖等）進行預處理和信息提取的一套處理流程與算法，并經過了多個實例驗證。結果表明完全能夠滿足后續的三維重建工作的需要。

1工程圖的預處理與信息提取

1.1基本性質和定義

性質1(空間點的投影特性)設空間點P(x，y，z)在主視圖投影面上的投影為(xf，zf)，在俯視圖投影面上的投影為(xt， yt)，在側視圖投影面上的投影為(ys，zs)，則有：xf=xt=x，yt=ys=y，zf=zs=z。性質2(對應原理)若主視圖、俯視圖、側視圖三個視圖中的二維點(xf，zf)，(xt，yt)和(ys，zs)滿足xf=xt，yt=ys，zf=zs，那么它們對應于三維空間中的唯一點(x，y，z)。

為了敘述方便，特作如下定義：

定義1圖元：亦可稱為實體，是指視圖中所有可見的圖形元素。例如直線、圓、圓弧、尺寸標注以及文字等。

定義2特征點：反映一個圖元位置特征的點。例如直線的端點，圓、圓弧的圓心，文本的插入點等。

定義3隱含點：從圖形數據文件中無法直接得到其信息的點。例如圖元之間的交點或切點等。

1.2工程圖預處理的實現流程

二維工程圖紙通常是以dxf/dwg文件存儲的。這些文件所記錄的圖形信息是以圖元形式保存的，而基于邊界表示的Brep重建方法主要是依賴于視圖中二維點和二維邊信息來生成三維點、邊、面的。因此，工程圖預處理的主要任務就是將輸入的二維工程圖中的二維點、二維邊的相關信息提取出來，以便后面的三維重建過程來調用這些數據進行重建，同時過濾掉圖紙邊框、文字標注等無關信息。也就是說，對于輸入的包含大量冗余信息的工程圖紙，經過處理后，輸出的是一張“干凈”的工程圖，里面所有的信息均是三維重建工作所需要的。

主要的實現流程（圖1）如下所示：

（1）工程視圖的讀入。包括工程一視圖、工程二視圖以及工程三視圖的dwg、dxf工程文件。其中對于二視圖主要考慮兩種情況，即含有主視圖和側視圖的二視圖和含有主視圖和俯視圖的二視圖。

（2）過濾工程圖實體。從工程圖中刪除圖紙邊框、尺寸標注以及文字等與重建無關的信息，保留直線、圓弧、圓、橢圓等有用的圖元信息。

（3）工程視圖分離。由于輸入的工程視圖是位于同一坐標系中的無序數據，而無序的輸入數據不利于形體的三維重建。需要對輸入數據進行視圖分離，建立每一視圖所對應的二維頂點表和二維邊表。這里采用了改進的坐標軸分離法實現了視圖的分離。

（4）坐標規格化。按照“長對正、高平齊、寬相等”的視圖間的投影規律，需要確定每個視圖的基準點（主視圖為右下角點，側視圖為左下角點，俯視圖為右上角點），并以此為基準進行坐標轉換，為每個視圖建立自己的視圖坐標系。

（5）視圖數據處理。這里主要考慮相交和重疊情況。

（6）將預處理后的工程圖數據保存到后續三維重建所需要的二維節點數組（二維點集）和鏈接數組（二維邊集）中。

1.3視圖分離

用繪圖軟件繪制的圖形，如果不同視圖采用不同的圖層來表示，其dxf文件實體段中含有層信息。這樣可以很容易得到圖元所屬視圖的信息。對于在同一圖層中畫出的投影三視圖或是掃描識別得到的數據文件，不可能從中得到圖元所屬視圖的信息。為了解決這個問題，投影視圖的分割算法可以很方便地將三個視圖分離出來。

標準的實體投影三視圖如圖2所示，對視圖進行分割的算法是基于這樣的性質，即每一視圖均是連續的、封閉的圖元組合，任何經過視圖的直線必然與該視圖中的圖元相交或重合。

通常的分割線確定方法^[10]是，首先設定兩條分別平行于設備坐標系坐標軸的輔助直線。平行于X軸的直線經過正、側視圖且與X軸指向一致；平行于Y軸的直線經過正、俯視圖與Y軸指向一致。然后在程序的運行過程中，平行于X軸的直線lx不斷向下移動，平行于Y軸的直線ly不斷向右移動，直到兩條直線位于三視圖之間，將視圖徹底分開為止。如果分割線的初始位置確定不當，分割線的平移過程必將花費大量的時間來進行比較和判斷，這就大大降低了算法效率。

由工程圖的性質可知，三視工程圖中所有實體在兩個坐標軸上投影的并集分別為兩條相互分離的線段。根據這一性質，本文提出了基于坐標軸投影分離法。該方法的基本思想是：將工程圖中的每一實體向X和Y軸投影，分別求出它們在X軸上投影的并集——線段AB和CD以及在Y軸上投影的并集——線段EF和GH(圖3) 。然后在y=(yG+yF)/2做一條水平線lx， 在x=(xB+xC)/2處做一條豎直線ly。lx和ly將平面分成P1、P2、P3和P4四個部分。根據三視圖的性質可知，主視圖、左視圖和俯視圖分別位于區域P1、P2和P3內。利用這一特性，只需判斷工程圖的每一實體位于哪一區域就可以分離三視圖。

與前面的方法相比，基于坐標軸投影分離法不但省去了大量的平移比較過程，而且減少了每一個二維實體的比較次數，每一實體只需作兩次比較即可確定其所在的視圖。

該方法是針對標準三視圖設計的。而在工程實踐中往往存在著大量僅含有一個視圖或者兩個視圖的工程圖紙。為了使該方法能夠處理非標準三視圖的情況，本文在其基礎上作了進一步的改進：在實體向坐標軸投影的同時，引入了Xlist、Ylist坐標鏈表因子。其鏈表數據結構如下：

double length; //該鏈表的長度說明了輸入工程圖的類型

這樣，在進行視圖分割時，首先判斷坐標鏈因子值；然后根據該因子值按對應的方法來生成分割線。主要有以下幾種情況：

(1)X->length=Y->length=1

說明在X、Y軸上的投影線段均為一段，即輸入為一視圖。對于這種情況，一般只考慮主視圖，找到視圖中實體元素最小包圍矩形的左下頂點和右上頂點，分別過這兩點做水平線和豎直線作為視圖分割線。

(2)X->length=2，Y->length=1

說明在X軸上投影線段為兩段，Y軸上投影線段為一段，即輸入為包含主視和側視的二視圖。對于這種情況，利用坐標分離法，只需判斷X軸上的投影關系，確定水平分割線。

(3)X->length=1，Y->length=2

說明在X軸上投影線段為一段，Y軸上投影線段為兩段，即輸入為包含主視和俯視的二視圖。對于這種情況，利用坐標分離法，只需判斷Y軸上的投影關系，確定豎直分割線。

(4)X->length=Y->length=2

說明輸入工程圖為標準三視圖。直接參照前面的坐標軸投影分離方法來處理。

舉例說明，假設讀入的工程圖只含有主視圖和俯視圖。將視圖中實體在X軸和Y軸做投影。在X軸方向上，由于兩視圖中實體元素的X坐標區間一致，兩視圖在X坐標軸投影重合，只會出現一段投影；在Y軸方向上，由于兩視圖中實體元素的Y坐標處于不同區間內，在Y軸上的投影線段就是兩段。通過對坐標軸上投影線段數目的判斷，置Xlist的值域為1，Ylist的值域為2，然后將坐標鏈因子的值與上述情況進行比較。結果滿足第二種情況，于是調用對應的算法來處理。

當分割線將視圖分開時，各視圖上的圖元相對于分割線的位置關系如表1所示。可通過該表判斷得出各圖元所屬的視圖。

1.4視圖坐標規格化

在實際工程應用中，所有視圖圖形均是在一個統一坐標系中描述的，各視圖的坐標與空間投影坐標之間并無明確的對應關系。本文以三視圖為例，各視圖圖形的幾何數據是孤立的、無聯系的。在重建過程中，需首先將圖所示的原始繪圖坐標轉換成各自的投影坐標形式，作為后續重建的基礎。將所有圖形和尺寸分割成單個視圖區域，如主視圖區域、俯視圖區域、左視圖區域和AA剖視圖區域等。這些視圖是零件在某個方向的投影，反映了零件在空間X、Y、Z坐標中的兩或三個值。例如主視圖反映了空間X和Z方向的值，斜向視圖反映了空間三個坐標的值。然后根據視圖所代表的空間坐標值，建立相應的變換公式，將繪圖坐標映射到相應的空間投影坐標上。

1.4.1坐標變換

為了建立如圖4所示的視圖間的空間投影坐標關系，需在各視圖所在的xy平面上選擇一個合適的點(X0，Y0)作為空間投影坐標系原點的對應點，稱其為投影原點。在確定投影原點的問題上，可以有許多選擇方案。這里以坐標軸投影分離法中的視圖分割線的交點O(X0，Y0)作為投影原點。過投影原點設置兩條分別與x和y軸平行的直線，并按下圖5所示的空間投影坐標系在平面上的對應關系來設置空間坐標軸XYZ。當空間投影坐標原點在視圖平面上的對應原點確定之后，應按畫法幾何學和工程制圖習慣，將各視圖在統一坐標系下的二維坐標轉換成空間坐標。為此，設置三個不同的坐標系，用以進行由原始二維圖形信息到空間投影坐標系的轉換。這三個坐標系分別是繪圖坐標系(xyz)、視圖坐標系(uvw)和空間投影坐標系(XYZ)。三者之間的關系如圖4所示。

空間投影坐標系是用來構造和描述重建目標的坐標系。其中繪圖坐標系與用于描述輸入圖形的二維坐標系相重合。這樣，原始輸入圖形就可以直接在繪圖坐標系下描述，只是坐標值z=0。而視圖坐標系則在繪圖坐標系與空間投影坐標系之間起橋梁作用。每個視圖均可以定義自己的視圖坐標系，又可以與其他視圖共享一個視圖坐標系，使各視圖坐標系的原點與空間投影坐標系原點重合。這樣僅通過坐標旋轉變換就可以完成從視圖坐標系到空間投影坐標系的轉換。實際上，視圖圖形在繪圖坐標系和視圖坐標系下仍是以二維(x，y)或(u，v)的形式描述，坐標軸z和w只是為了在坐標旋轉變換時矩陣運算的方便。

在圖4中，各個視圖坐標系的原點與投影原點(x0，y0)重合，并且坐標軸u、v分別與繪圖坐標系的x、y軸平行，同時約定坐標軸w在視圖坐標系中按右手法則一直指向紙外。當投影原點(x0，y0)的位置確定后，視圖坐標(u，v，w)可直接由繪圖坐標(x，y，z)變換后得到。變換矩陣A表示如下：

相應各視圖的轉換矩陣分別為

其中，a、b分別為投影原點O(x0，y0)的坐標值，下標v、h、w分別代表主視圖、俯視圖和左視圖。

由于視圖坐標系與空間投影坐標系的原點重合，兩坐標系之間的對應關系如圖4所示。實現由視圖坐標(u，v，w)到空間投影坐標(X，Y，Z)的轉換可通過坐標旋轉變換來完成。兩坐標系之間的轉換關系用轉換矩陣B表示如下：

相應各視圖坐標的轉換矩陣分別為

經過以上的推導與轉換，最后可得到由繪圖坐標到空間投影坐標的轉換矩陣——轉換算子。通過轉換算子，每個視圖的二維點坐標都可與空間點之間建立相應的投影約束關系。由式(1)和(2)得到轉換的矩陣形式：

令轉換算子

各視圖對應的轉換算子分別為

有了這三個變換矩陣，各視圖間的對應關系也就明確了，為以后的三維重建工作奠定了基礎。

1.4.2算法實現

(1)確定工程圖中視圖數目。如果只有一個視圖，則按主視圖的情況來處理；如果有兩個視圖，主要考慮主側視圖和主俯視圖的情形。

(2)確定每個視圖的最小包圍矩形的范圍。

(3)確定每個視圖中的基準點（即新的坐標原點）。對于主視圖，以最小包圍矩形的右下頂點為基準；對于俯視圖，以最小包圍矩形的右上頂點為基準；對于側視圖，則以最小包圍矩形的左下頂點為基準，如圖5所示。

(4)以選定的基準點為基準，對相應視圖中二維點和二維邊的坐標信息進行變換，為每個視圖建立自己的視圖坐標系。

(5)按“長對正、高平齊、寬相等”的視圖間的投影規律，將視圖坐標轉換為對應的空間投影坐標。

(6)直到所有二維點和邊坐標更新完畢。將結果保存到視圖的點集合邊集中。

1.5視圖數據的預處理

由于視圖投影的重疊性和積聚性以及繪圖者繪圖過程的不確定性，直接從工程視圖上獲得原始數據的幾何信息和拓撲信息均是不完備的，不足以恢復立體上的所有頂點和邊。需要對視圖中的數據進行預處理，以便獲得比較完備的幾何信息和拓撲信息。主要考慮圖元之間重疊和相交的情況。

1.5.1重疊處理

基于上面提到的原因，視圖在投影面上進行投影時，有時不同的邊會產生重疊。因此，必須對那些在三視圖上因投影而重疊在一起的邊進行分解與重構，才能獲得視圖比較完備的數據信息。本文將視圖上因投影而重疊在一起的邊稱為重疊邊。重疊處理也就是指對重疊邊的分解與重構處理。

重疊邊的分解：析出長線段(包括線段、圓、橢圓、圓弧及橢圓弧)所覆蓋的全部子線段及其特征點，并追加到相應的邊集和點集中。

重疊邊的重構：將完全重合或部分重合的線段以及若干共線且連續的子線段(包括圓弧及橢圓弧)合并為長線段，并將該線段及其特征點追加到相應的邊集和點集中。

重疊邊分解與重構的目的是生成三視圖上全部二維線段，避免了在后續處理和特征識別重建過程中產生干擾信息。

1.5.2相交處理

因為圖元之間的位置關系，它們在投影面上的投影，有時會出現相交(或相切)的情況。而這些交點或切點的信息是不能直接從圖形數據文件得到的，將其稱為隱含點。缺少這些隱含點數據，就無法獲得視圖完備的幾何信息和拓撲信息，這就會給后面重建過程中生成線框的搜索帶來困難。

隱含點數據的產生主要是因為圖元間的位置關系從圖形數據文件中無法直接得到。例如，兩圓的切點無法從數據文件中讀到。隱含點數據可以通過對投影視圖中各圖元間的位置關系進行分析來得到。對于圖元間位置關系，本文主要考慮圖6所示的幾種情況。大體可以歸結為三類進行研究^[10]：線段相交、線段與圓(弧)相交或相切、圓(弧)與圓(弧)相交或相切。

本文采用圖元求交算法處理圖元數據文件， 求出圖元間的公共點， 用求出的點數據充實已有的點表， 并合并點表中點數據相等的節點。步驟如下：

（1）指針position1指向圖元表頭，讀圖元數據。

（2）指針position2指向position1所指的下一個元素。

（3）讀position2所指圖元數據，進行兩圖元位置關系的判斷和計算。將計算出的隱含點和其關聯的圖元組成點數據，加入到點表中。

（4）position2指向下一元素；轉（3），直至圖元表末尾。

（5）position1指向下一元素，讀圖元數據；轉（2），直至圖元表倒數第二個數據。

（6）指針position3指向點表頭，讀點的坐標值。

（7）指針position4指向position3所指的下一個元素，讀點的坐標值。

（8）比較position3和position4所指點的坐標值。若相等，則合并兩節點數據。

（9）position4指針移向下一元素，讀該點的坐標值；轉（8），直至position4移至表尾。

（10）position3移向下一元素，讀該點的坐標值；轉（7），直至點表的倒數第二個元素。

處理完點數據后，再填寫圖元表各節點中的點指針數組數據。程序執行如下：

（11）d_position指針指向圖元表頭，d_position指針指向點表頭。

（12）讀點數據中圖元指針數組數據并與d_position比較。若相同，則向圖元節點中的點指針數組中加入該點指針。

（13）移動d_position到下一元素；轉（12），直至d_position移向表尾。

（14）移動d_position到下一元素，將d_position指向點表頭；轉（12），直至d_position移向表尾。

2應用實例

課題在清華大學國家CAD研究中心開發的GEMS系統下利用Visual C++設計開發了基于工程圖三維重建的原型系統。在其中較好地實現了預處理模塊和重建模塊的功能，并進行了大量的實例驗證。結果表明，本文的實現方案是合理的、高效的，達到了預期效果，如圖7～14所示。

在重建系統的預處理模塊中，系統采用了改進的坐標軸投影視圖分離方法。與前面提到的傳統方法相比，不但減少了每一個二維實體的比較次數；而且由于引入了坐標鏈因子，能夠處理不多于三個視圖的各類工程圖紙，處理的范圍和效率均比傳統方法有了很大提高。

3結束語

基于工程圖三維重建的第一步就是要對輸入的工程圖進行預處理和信息提取。用傳統的方法在處理過程中需要大量的比較判斷和復雜的幾何操作，不但需要很長的處理時間，而且很難對各類輸入工程視圖作統一的處理。本文提出的基于邊界表示方法的工程圖三維重建中對于二維工程圖紙進行預處理和信息提取的一系列方法，從開始的工程圖輸入到最后的二維點、邊幾何拓撲信息的輸出，涉及了預處理的整個流程。不但可以在較短的處理時間內獲得二維視圖中完備的幾何信息和拓撲信息，而且并不局限于標準的工程三視圖，對于工程一視圖、二視圖同樣可以處理。通過在實際系統中的應用，完全可以滿足后續重建工作的需要。

由于工程圖紙十分復雜，對于復雜圖紙和含有剖視圖或者更多其他輔助視圖的預處理的研究工作還有待進一步的深入探討。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。