第十章 機器視覺 人工智能課程 北京大學(共19頁)

1、第十章 機器(j q)視覺教學內容：本章所研究的機器視覺是諸多傳感信息(xnx)中包含信息最豐富、最復雜和最重要的感覺之一，也是應用最為廣泛的機器感覺之一。內容包括圖象的理解與分析、視覺的知識表示與控制策略和物體形狀的分析與識別等。教學(jio xu)重點：物體邊緣距離的計算、表面方向的計算、物體形狀識別方法教學難點：圖匹配法、松弛標示法、多層匹配法等教學方法：用較為通俗的語言將機器視覺的相關知識講透徹，同時結合圖表，對不同線條的標示方法進行講解。多結合日常生活中常有的現(xiàn)象，讓學生對所學知識有更深入的認識。教學要求：重點掌握視覺信息的表達方法，包括初始簡圖、二維半簡圖和三維模型；掌握物體邊緣距

2、離和表面方向的生理學基礎及計算原理和計算方法；了解復雜形狀物體的表示和三維物體的形狀描述方法；一般了解機器視覺應用系統(tǒng)的構成、視覺系統(tǒng)的設計思想。10.1 圖象的理解與分析教學內容：對圖象進行理解和解釋是計算機視覺的研究中心，也是人工智能研究的焦點之一。教學重點：初始簡圖、二維半簡圖和三維模型教學難點：松弛算法、邊緣距離的計算教學方法：以課堂書本知識為主，采取提問，討論等方式提高學生學習的積極性，自主性和創(chuàng)造性。教學要求：重點掌握視覺信息的表達方法，包括初始簡圖、二維半簡圖和三維模型；掌握物體邊緣距離和表面方向的生理學基礎及計算原理和計算方法10.1.1 視覺信息的表達方法根據(jù)(gnj)馬氏(

3、Marr)提出的假設，視覺信息處理過程包括3個主要表達層次，即初始簡圖、二維半簡圖和三維簡圖，如圖10.1所示。圖10.1 視覺(shju)信息的表達層次1、初始(ch sh)簡圖的基本概念：亮度圖象含有兩種重要信息：圖象的亮度變化和局部幾何特征。初始簡圖是一種本原表達法，它能完全而又清楚地表示上述信息。初始簡圖所包含的信息大部分集中在與實際邊緣以及邊緣終止點有關的劇烈灰度變化上。對于每一邊緣亮度變化，在初始簡圖上都有對應的描述。這些描述包括：與邊緣有關的亮度變化率、總的亮度變化、邊緣長度、曲率和方向等。粗略地說，初始簡圖是以勾劃草圖的形式來表示圖象中的亮度變化的。 圖10.2 用初始(ch

4、sh)簡圖表示灰度變化 圖10.3 二維半簡圖舉例(j l)2、二維半簡圖的基本概念：二維半簡圖包含景物表面的信息，可以把它看做某些內在特性(txng)的混合信息。二維半簡圖清楚地表示物體表面方向的信息。物體表面法線從物體內部穿出來，使物體好象穿刺。3、三維模型的表示方法三維表達法能夠完全而又清晰地表示有關物體形狀的信息，其方法之一即為廣義柱體。廣義柱體的概念十分重要，而其表示方法又十分簡單，如圖10.4所示。圖中，柱體的橫截面沿軸線的投影不變。一個普通圓柱可看作是一個圓周沿其中心垂線移動而成；一個楔形物是一個三角形沿其中垂線移動而得的，等等。一般地說，一個廣義柱體是二維輪廓圖沿其軸線移動而成

5、的。在移動過程中，輪廓與軸線之間保持固定的角度不變。輪廓可為任何形狀，而且在移動過程中其尺寸可能是變化的，其軸線也不一定是垂線或直線，如圖10.4所示。 圖10.4 廣義(gungy)錐體 10.5 截面形狀(xngzhun)變化或軸線為曲線時的廣義柱體10.1.2邊緣距離(jl)的計算1、圖象輝亮邊緣的平均與差分產(chǎn)生噪聲邊緣問題是因為在獲得圖象時，會遇到傳感器的亮度靈敏性波動、圖象坐標信息誤差、電子噪聲、光源擾動以及無力接收大范圍變化的亮度信息等。另一個原因是圖象本身很復雜，其實際邊緣并不是陡削的，而是逐步過渡的；還可能存在相互照明效應、意外劃痕和灰塵等。一種處理噪聲邊緣的方法包括下列四個步

6、驟：(1)從圖象建立平均亮度陣列。(2)從平均亮度陣列產(chǎn)生平均一階差分陣列。(3)從一次平均差分陣列建立二次平均差分陣列。(4)據(jù)所得陣列，記下峰點、陡變斜率和過零點，以尋求邊緣(binyun)信號的集合。2、靈長目動物(dngw)視網(wǎng)膜特性 圖10.6 靈長目動物(dngw)視網(wǎng)膜輸入輸出特性實驗 圖10.7 視網(wǎng)膜實驗特性與墨西哥草帽形濾波結果的比較 墨西哥草帽形濾波器與一些了解靈長目動物早期視覺的實驗相一致。關鍵實驗如圖10.6所示。被試動物注視各種從白色背景前移過的色質(stimuli)。這些色質包括一條窄的黑帶、一條寬的黑帶以及一個單白黑邊緣。記錄探針測定各種神經(jīng)反應。把此神經(jīng)反應與

7、據(jù)墨西哥形草帽濾波器作出的預計進行比較。圖10.7給出比較結果。在圖10.7中，(a)表示3個自左向右移動的色質的亮度分布曲線；(b) 表示以適當寬度的墨西哥草帽形濾波器對所給出的亮度分布進行濾波的結果；(c)為所謂X神經(jīng)節(jié)細胞上記錄的實驗(shyn)數(shù)據(jù)。比較圖10.7(b)和(c)可見，兩者極其相似。這表明靈長目動物的視網(wǎng)確實進行了某些與墨西哥草帽形濾波器十分相似的處理工作。如果對墨西哥草帽形濾波器稍加修改，就能夠改善相似性，如圖10.7(d)所示。比較(bjio)結果得到的高度相似性，使我們有足夠的根據(jù)作出下列假設：(1)靈長目動物視膜所進行的濾波處理功能在運算上是與由墨西哥草帽形點擴散

8、(kusn)函數(shù)所進行的濾波相似。(2)存在有兩種視膜細胞，一種用于傳輸濾波圖象的正向部分，另一種傳遞濾波圖象的負向部分。(3)對于每種細胞，墨西哥草帽形濾波器是通過激發(fā)與禁止這兩種操作的組合來實現(xiàn)的。這個濾波器等價于兩個以二維高斯濾波器濾波所得圖象的差。 3、物體距離的測定圖10.8表示兩眼立體視覺中的相對位置關系。圖中，P點為一物體。兩個透鏡的軸線是平行的。f為兩透鏡與圖象平面的距離，即為其焦距。b為兩透鏡軸線在基線上的距離，即為兩眼的距離。l和r分別為P點與左、右透鏡軸的距離。和分別為左右圖象與其相應透鏡軸線的距離。從兩相似三角形，可求得觀察者雙眼至物體的距離： 由于雙眼距離(jl)b為

9、已知，焦距f也是確定的，因此，一個物體與雙眼的距離和(+)成反比。(+)為該點的一幅(y f)圖象點位置相對于另一幅圖象點位置的位移，稱為視差(disparity)。立體視覺的實際問題(wnt)就是據(jù)左右兩圖象找到相應的物體，以便能夠測量視差。已有許多不同的立體視覺系統(tǒng)能在不同程度上成功地尋找出相應的物體。10.1.3 表面方法的計算1、反射圖體現(xiàn)光照約束把從所有可能位置觀察到的亮度都相同的表面定義為朗伯表面(Lambertian Surface)，它的亮度只由光源的方向決定。這一關系遵循下列公式：E=cosi。式中，E為被觀察亮度；為表面反射率(對于特定的表面材料，為一常數(shù))；i為入射角。2

10、、表面方向的確定上面我們研究了利用表面方向預測表面的亮度。下面研究從感測到的亮度來計算表面各方向參數(shù)f和g。由f和g來確定表面方向，初看起來似乎是不可能的。因為一小塊表面只能確定切面FG上的一條曲線，而不是單一的點。但是，事實上這樣做卻是可能的，因為大部分表面是平滑的，在不同深度和方向上只出現(xiàn)有少數(shù)不連續(xù)的情況。因此，可以利用下面兩個約束：(1)亮度。由f和g所確定的表面(biomin)方向應與表面亮度所要求的表面方向無多大不同。(2)表面(biomin)平滑度。一點的表面方向應與鄰近各點的表面方向無多大變化。對于每個點，計算的f和g值應兼顧上述兩個約束計算所得的值。據(jù)亮度要求特定點的f和g值

11、應落在等亮度線上，而據(jù)表面(biomin)平滑度則要求f和g值接近相鄰點f和g的平均值。3、松弛算法(1)對所有非邊界點，令f=0和g=0。對所有邊界點，令f和g規(guī)定一個長度為2的垂直于邊界的矢量。稱輸入陣列為當前陣列。(2)進行下列步驟(直到所有的值變化得足夠慢為止)：(a)對當前陣列中的每個點：i)如果是個邊界點，則不做任何事；ii)如果是個非邊界點，那么用松弛公式計算新的f和g值。(b)把所得新陣列稱為當前陣列。10.2 積木世界的景物分析教學內容：可見的景物的傳感器編碼，檢測器搜索圖象主要成分（如線段、簡單曲線和角度等）的處理，利用知識推斷有關景物的三維特征信息。教學重點：無斷裂和陰影

12、時三面頂點的標示方法，有斷裂和陰影時線條圖的分析。教學難點：無斷裂和陰影時三面頂點的標示方法。教學方法：以課堂教育為主，通過多種途徑開發(fā)學生的學習熱情，結合實踐。教學要求：基本了解積木世界景物的線條標示方法，掌握無斷裂和陰影時三面頂點的標示方法和有斷裂和陰影時線條圖的分析。10.2.1積木世界(shji)景物的線條標示方法圖10.9 幾種(j zhn)典型的線條圖積木世界視覺研究的主要目標是理解從一堆玩具積木的圖象得到對于景物的描述。所謂描述就是把出現(xiàn)在圖象中的大量的線條聚集成代表景物中各個積木的線條組。研究積木世界景物時，輸入的圖象可以是積木景物的照片、電視攝影圖象或是線條圖。如果是屬于(s

13、hy)前二種，那么第一步就是從圖象得到線條圖。這屬于馬氏初始簡圖的范圍，但沒有那樣復雜，只是用了邊緣檢測算子。在以下的討論中，我們都假設已經(jīng)得到了積木世界的線條圖的情況。積木世界景物分析的研究對象比較狹窄，并且是有意地進行了簡化，但仍不失為合適的計算機視覺研究的初步目標。在這個領域中的研究已經(jīng)取得了一些有實用意義的成果。積木世界可以推廣為類似工業(yè)零件的多面體，而理解簡單的三維工程圖是建立有視覺的工業(yè)機器人裝配系統(tǒng)的第一步。10.2.2 無斷裂和陰影時三面頂點的標示方法1、線條和接點的分類先研究無斷裂的三面頂點，并且設想合適的光照條件，避免了所有的陰影。在這樣的環(huán)境下，圖中的所有線條代表了各種天

14、然產(chǎn)生的邊緣。這些(zhxi)線條的簡單分類如下。2、標志三面接點(ji din)的方法為了對圍繞接點的線條的標示方式進行分類，需要從每個可能的方向來觀察每種實際可能的三面頂點。但這樣做會遇到可供選擇的方向過多的困難，為此把除了一般的觀察位置(wi zhi)以外的方向都排除在外，以減少可能出現(xiàn)的情況。假設在這一節(jié)的其余部分僅討論只包含三面頂點的線條圖。任何三面頂點的3個面規(guī)定了3個相交的平面，這3個相交的平面把空間分成8個間隔。很明顯，某個形成一個頂角的物體就占有上述8個間隔(或八分體)中的一個或幾個。接點標志所說明的是物體如何占有八分體?？梢酝ㄟ^以下兩個步驟來構成完整的包含所有連接可能性的字

15、典：先考慮所有的以物體來充滿這8個八分體的方式；然后，從未被充滿的八分體觀察所得到的頂點。10.2.3 有斷裂和陰影時線條圖的分析改善線條描述可使約束的數(shù)目增加，從而提高分析的速度。要進一步研究是否有別的方法對線條的解釋作進一步的分類。在介紹具體方法以前，有一個問題需要注意，即隨著線標志集合的擴展，實際接點標志的集合將顯著增加。將會有幾千種合法的接點標志，而不是只有18種。因此不可能建立一個合法接點標志表和企圖讓摸擬計算機利用這個表格來做些什么。以下介紹兩種對線條解釋作進一步分類的方法：1.對凹面標志進一步分類并引入斷裂線標志考慮到物體經(jīng)常放在一起。所以，凹面標志可以分成3類，這3類表示有關物

16、體的數(shù)目和認出哪個物體是在前面的。設一條凹面邊緣表示兩個物體接觸在一起的地方。然后想象把這兩個物體稍為拉開一點。這樣，這個凹面邊緣就成為邊界，其上標志指向兩個可能方向中的一個。這兩種可能性以一個由原來的負號標志和一個新的箭頭標志組成的合成標志來表示。如果有3個物體相接觸，同樣可利用一個合成標志表示如果物體稍為離開一些時可以看到什么。斷裂線也可以類似地處理：每一根斷裂線被標以1個c和1個箭頭，表示這兩個有關的物體如何配合在一起。2.用光照條件增加標志(biozh)數(shù)量和嚴格約束另一種改善線條描述的方法是結合(jih)單光源的光照條件。概括起來，線條解釋的每一次改進都促使一次線條標志的大擴展。開始

17、時只考慮(kol)基本的線條、邊界線、內部的凹面線和凸面線。這些初始的線條種類擴展到包括陰影線。凹面線又分成四類以反映接觸在一起的物體個數(shù)，以及這些物體間如何相互遮擋。這引入了斷裂線并以和凹面線相類似的方式分成2類。最后，線條的信息和照明信息相結合。從最后這次擴展產(chǎn)生50種線條標志。思考：合法的標志數(shù)目相對于不合法的標志數(shù)如何增加。10.3 視覺的知識表示與控制策略教學內容：研究在人工智能其它領域中發(fā)展起來的知識表達方法，主要是語義網(wǎng)絡在視覺領域中的應用。教學重點：語義網(wǎng)絡，位置網(wǎng)絡教學難點：位置網(wǎng)絡教學方法：以課堂教育為主，通過多種途徑開發(fā)學生的學習熱情，例如：課堂練習，思考，討論及提問等，

18、并結合實踐，加深對課堂知識的理解。教學要求：了解語義網(wǎng)絡及位置網(wǎng)絡，一般了解視覺系統(tǒng)的控制策略。10.3.1 視覺信息的語義網(wǎng)絡表示著重介紹語義網(wǎng)絡，它具有如下特點：(1)可作為一種很方便地存取模擬知識的表達方法以及命題邏輯的知識表達的數(shù)據(jù)結構。(2)可作為一種反映(fnyng)在有關領域中事物之間相互關系的模擬結構。(3)可用作一種具有(jyu)特殊的推理規(guī)則的命題邏輯表達法。習題(xt)：試用語義網(wǎng)絡表示以下景物：“在道路57(road57)與河流3(river3)交叉處的橋梁位于建筑物30(building30)附近。”10.3.2 位置網(wǎng)絡表示在一般的應用場合中，景物中所期望的特征的相

19、對位置都已表示在網(wǎng)絡中，這樣網(wǎng)絡就把圖象的所期望的結構模型化了。物體之間幾何關系的基本運算有以下4種：(1)方向性運算(左、反射、北、上、下等)：以相對于其他點集的位置和方向來規(guī)定點集。(2)區(qū)域運算(靠近于、在四邊形內、在圓周內等等)：建立一個和其他點集無方向關系的點集。(3)集合運算：完成并、交以及求差等集合運算。(4)謂詞運算：對區(qū)域進行的謂詞運算可通過測量某些數(shù)據(jù)的特征來刪除某些點集。10.3.3 視覺系統(tǒng)的控制策略視覺控制策略支配著通過各表達層次的信息流和活動，哪個觸發(fā)機構在處理?是像視網(wǎng)膜上色塊一般的低級輸入呢，還是一種高層期望，對于這兩種極端作不同的強調是一個基本控制問題，這兩個

20、極端表征如下：(1)圖象數(shù)據(jù)的驅動。這里控制的進行過程是從建立廣義圖象到已分割圖象結構，最后為描述，這也叫由底向上控制(bottomup control)。(2)內部模型驅動(q dn)。知識庫內的高層模型產(chǎn)生對輸入的幾何、分割的或廣義圖象的期望或預測，圖象理解是這種預測的驗證，這也稱為自頂向下控制(topdown control)。(3)非層次控制。這個術語似乎由麥卡洛克(McCulloch)提出來的，他使用這個術語描述腦神經(jīng)反應連通性所蘊涵的反應的本質，其思想是在任何給定時刻使用能夠完成(wn chng)最終任務的辦法，提供最多幫助的專家。10.4 物體形狀的分析(fnx)與識別教學內容：

21、多面體化為對非多面體景物的描述問題，并以這些描述為基礎，對物體形狀進行分析與識別。教學重點：討論非多面物體的分析，并特別集中于形狀分析。教學難點：松弛標示法、多層匹配法。教學方法：課堂講解教學要求：了解物體形狀分析與識別的基本概念10.4.1 復雜形狀物體的表示一個好的形狀表示能夠由物體的部分視圖來識別物體，而且物體形狀的小變化只引起形狀描述的小變化。物體各部分的連接表示應當是很方便的，它能夠比較兩個物體的差別和相似性，而不僅是進行簡單的分類。如果把復雜物體表示為被分割的比較簡單的部分以及這些部分間的相互關系，那么上述要求就比較容易得到滿足。對形狀的識別(shbi)是由兩個相關描述的匹配獲得的

22、。一個物體的部分視圖所產(chǎn)生的描述圖是完整的物體描述子圖，并能適當匹配過程的需要。1、曲線形狀(xngzhun)的描述與量度曲線描述對于(duy)一些特別物體(如字母符號)和三維景物(如某地區(qū)照片上的道路)分析是很重要的。此外，三維物體的形狀描述也往往被簡化為“輪廓”線條結構。（1）曲線的存儲方法。依次采用曲線上各點的坐標序列來表示線條是最容易的描述方法。如果只要存儲曲線的起點坐標和依次各點的坐標增量，那么就能夠顯著節(jié)省計算機內存。（2）曲線的近似描述。曲線的緊密和結構描述可以采用近似方法。一種方法是把曲線展開為正交級數(shù)；另一種是把曲線分段為一些比較簡單的曲線。線性分割分段近似是最常見的，而樣條

23、函數(shù)（對多項式分段，在各連接點規(guī)定連續(xù)條件）具有普遍意義。（3）曲線形狀分析量度法。把一些與某曲線的分析近似法有關的系數(shù)用來表示該曲線形狀的特征。不同形狀的曲線具有不同的系數(shù)。不過，隨著比例尺、旋轉和遮斷情況的不同，這些系數(shù)可能變化很大。因此，這種分析量度法只適用于曲線數(shù)目較少及預期變化較小的情況。2、面積形狀的描述與量度采用圖形內部不在邊界上的點來描述圖形，比較健全，因為比較小的面積變化能引起大得多的邊界變化。（1）簡單形狀的量度。由平面圖形的面積和周邊來粗略量度其形狀面積(周長)2是個與圖形尺寸、位置和方向無關的量度不變式。把一個圖形的最小約束矩形定義為一個完全包圍該圖形的矩形，而且此矩形

24、不會被任何其它的這類矩形所包圍，見圖10.10。一種改進的對圖形形狀的近似量度是由它的凸緣進行的。把凸緣定義為包圍已知圖形的最小凸出圖形。原圖形則由凸緣形狀及圖中凹面或凹陷的數(shù)目和形狀來描述，見圖10.11。圖10.10最小約束(yush)矩形 圖10.11圖形(txng)的凸緣與凹陷（2）面積分析量度法。如同曲線描述一樣，借助于某些基本函數(shù)(如二維傅里葉級數(shù))對圖形展開或近似而得到的系數(shù)，可用于對圖形形狀進行分析量度。對于一些基本函數(shù)，有可能組合(zh)這些系數(shù)以獲得一個對比例尺、位置和方向的不變式。10.4.2 三維物體的形狀描述三維物體的形狀可由物體的外表面或這些外表面所包絡的容體來描述

25、（可把洞孔描述為負容積）。三維物體描述特別困難之處在于，三維表面或容積需要二維圖象來推斷，尤其是對不可見表面的推斷。下面我們將著重分析由二維圖象進行容積描述問題。1、物體形狀的廣義錐體表示可用廣義柱體(有時稱為廣義錐體)來表示物體的形狀。由于單一的廣義錐體能夠描述任意容積，因此，復雜的形狀能夠自然地分割為若干個比較簡單的廣義錐體來描述。圖10.13所示的螺絲起子可由4個廣義錐體來描述。其中，一個對應于螺絲刀片，為一變化的矩形截面；另一個對應于螺絲刀桿，具有圓截面；還有2個廣義錐體在手把上。簡化廣義錐體的準則應是其橫截面的形狀、尺寸或軸線方向不發(fā)生陡削變化。圖10.13螺絲起子的廣義錐體(zhu

26、 t)表示2、廣義錐體(zhu t)描述的計算廣義錐體表示(biosh)不是變換表示，對于同一輸入可能有許多可供選擇的描述。需要從中選擇一種或多種最好的描述。（1）擬合表面數(shù)據(jù)。已知可見表面的三維位置以及對軸線和橫截面形狀的約束，就能擬合出最佳廣義錐體。對于已知形狀的橫截面，可能求得一個簡單的迭代解答?？紤]一個正圓柱體。起初，該圓柱體的軸線方向和橫截面都是未知的。任選一個方向之后，就能夠對可見表面擬合出橢圓橫斷面。通過這些橫截面矩心的某軸線，并不需要與該軸線垂直。接著，能夠作出垂直于該軸的橫截面。重復此過程，直至只觀察到很小的橫截面變化為止。對于正圓柱體和正圓錐體，這個過程收斂得很快。對于任意

27、形狀的物體，其收斂情況是不確定的，這時，要采用這種擬合技術，需要假設橫截面由橢圓所近似。（2）采用物體邊界。二維錐面能夠由物體的邊界來計算。如果二維輪廓是三維物體的投影，那么被計算的錐面就是所求的三維錐體的投影。10.4.3 物體形狀識別方法物體或者由幾個物體組成的構件，可由比較它們的描述及存儲在計算機內的模型描述來識別。這些模型可能由下列方法獲取：存儲預先遇到的物體的機器描述，直接學習視圖數(shù)據(jù)序列，或者只是由操作人員提供。如果物體的描述是一張?zhí)匦郧鍐危刺匦允噶?，那么能夠采用一般的?shù)學模式識別技術來識別。對于結構性描述，需要采用比較復雜的匹配技術。此外，不要求用大量的內存把一個描述與每一個存

28、儲模型進行匹配試驗，沒有完全匹配而要選擇一個合適的子集，就需要進行檢索。1、圖匹配(ppi)法(Graph matching)結構性描述可視為圖或網(wǎng)絡。我們對評價兩幅圖的相似性感興趣。下面介紹一些(yxi)有關相似性的量度。令某幅圖G：N，P，R定義(dngy)為由結點集合N(表示物體的部件)、這些結合特性的集合P以及結點(節(jié)點)間關系的集合R組成的。已知兩幅圖G：N，P，R和G：N，P，R，如果當且僅當P(n)與P(n)對某一給定的相似性量度相似(即節(jié)點n的特性與節(jié)點n的特性相似)時，就說形成一對配對(assignment)(n,n)。如果有兩對配對(n1，n1)和(n2，n2)，對于R中的

29、r和R中的r的所有關系使得r(n1，n1)=r（n2，n2）成立，那么就說這兩對配對是兼容的。其中，我們假設關系是二元的。如果兩幅圖G和G的節(jié)點具有一對一的配對，使得所有配對相互兼容，那么就稱這兩幅圖是同構的(isomorphic)。其中，如果(n,n)為一配對，那么仍然要求P(n)=P(n)。如果G的子圖與G的子圖同構，那么就稱圖G與G為亞同構的(subisomorphic)。2、松弛標示法(Relaxation labeling)把標示問題定義為一個標示集合與一個節(jié)點(或單元)集合的配對，使得標示配對與給定約束相一致。這種標示法有許多應用，而且包含了圖匹配問題。這時，標示是其它圖的節(jié)點。令

30、N為被標示節(jié)點的集合，L為可標示的集合。對于每個ni，想要指定一個標示集合Li，使得Li為L的一個子集，而且這些標示與給定約束相容。對于不含糊的情況，每個集合Li只包含一個元。最簡單的約束是一元的，限制標示只可能賦予某個確定的節(jié)點，而不考慮網(wǎng)絡中的其它節(jié)點。二元約束規(guī)定一對節(jié)點的標示之間的關系。對于節(jié)點ni的一個標示集合Li，可能與節(jié)點nj的一個標示集合Lj相容，如果Li的每個標示至少與Lj的一個標示相容的話。這種相容性稱為弧相容性(arc consistency)。一般說來，約束是n元的，而且弧相容性可能并不導致全局相容性(global consistency)。圖10.44給出一個例子，其一元約束為：要對每個節(jié)點標示為紅色或綠色，而且要求相鄰點為不同的顏色。每當對一個