一種直線立體匹配方法
2023-04-29 08:55:31
專利名稱：一種直線立體匹配方法
技術領域：
本發明屬於攝影測量和圖像處理技術領域，特別是涉及一種直線匹配方法。
背景技術：
立體匹配是攝影測量和圖像處理領域長期研究的一個基本問題，它的目的是獲取目標場景的三維信息，方法是匹配從兩個不同視點圖像中提取出來的特徵集。直線是立體匹配應用的一種重要特徵，國內外很多學者致力於基於直線的立體匹配問題。
目前，直線立體匹配是一個公認的難題，主要體現在以下兩個方面第一，由於場景遮擋、圖像噪聲以及直線提取過程中的不確定性等問題的影響，造成從不同圖像中提取的同名直線特徵的屬性出現差異，不易準確生成直線特徵匹配對假設；第二，匹配過程中沒有嚴格的去模糊約束機制，從而難於區分真實匹配對假設和虛假匹配對假設。為了得到可靠的匹配結果，絕大多數已有匹配算法將直線立體匹配問題轉化為一個優化求解問題，為得到全局一致的匹配結果，普遍應用唯一性約束，即限定直線特徵之間的對應關係只能是「一配一」的。事實上，直線特徵之間還可能存在「一配多」甚至「多配多」等複雜對應關係，其產生的原因主要是遮擋和特徵不確定性，體現在以下三個方面第一，提取過程中一條直線特徵被分割成多段；第二，一條三維直線在某個觀測視角中的投影被遮擋而斷裂成多段；第三，一組互連的空三維直線共面且該平面通過其中一個相機的攝影中心，則這組三維直線在一幅圖像中的投影共線並連接成一條直線特徵，而在另一幅圖像中的投影則由多條直線特徵組成。
當前，對於包含複雜對應關係的直線立體匹配問題有兩種解決思路第一，基於特徵整體變換的方法。假定一幅圖像或模型中的一組直線與另一幅圖像或模型中的一組直線間存在參數一致的幾何變換，搜索整體變換誤差最小情況下的直線特徵間對應關係作為匹配結果。這類方法通常應用於二維圖像配準或基於模型的二維/三維目標識別、姿態參數求解等，而對求解基於立體像對的匹配問題則很難適用；第二，對直線進行編組的方法。應用較多的是斷裂直線編組和感知編組方法。斷裂直線編組是在單幅圖像中將共線的臨近直線編為一組，然後以編組為單位參與匹配。該方法可以部分解決斷裂直線造成的複雜匹配問題，但對於直線特徵提取不完整性嚴重的情況仍然難以得到滿意的匹配結果；感知編組是依據拓撲關係將同一幅圖像中形成特定的幾何形狀的直線特徵編為一組，這種思路的優點是編組之間的匹配有更多的屬性信息可用於消除模糊性，且可以在一定程度上補充因直線提取過程造成的直線特徵不完整部分。這兩種編組方法的缺點在於分別在不同圖像內對直線進行編組，由於投影變換和遮擋等問題，編組結果由一幅圖像到另一幅圖像可能是變化的，難以保證編組過程的穩定，並且，它們除對少數斷裂直線的兼容外，並不能完全解決所有「一配多」和「多配多」的對應性問題，尤其是包含多條非共線直線的複雜對應性問題。
發明內容
本發明的目的是提供一種直線立體匹配方法，能夠對直線立體匹配中的遮擋問題和特徵不確定性問題進行建模，對實現對直線間「一配一」、「一配多」或「多配多」在內的各種對應關係的求解。
本發明方法對該問題進行求解的工作流程是利用提取的直線特徵從統計意義上恢復對應的投影直線→由恢復的投影直線生成所有直線特徵編組→選取最可靠的直線特徵編組作為匹配問題的解。
本發明的技術方案是，一種直線立體匹配方法，具體包括下述步驟 已知從不同視角獲取的同一場景的兩幅圖像，分別記為左圖像I1和右圖像I2，它們的成像參數已知；對圖像I1和I2進行邊緣檢測的結果分別為圖像E1和E2，圖像E1和E2中每個邊緣點的灰度梯度相位已知；從左圖像I1中提取的直線特徵的集合為其中，任意一個直線特徵l1i的端點分別為s1，1i(x1，1i，y1，1i)和s1，2i(x1，2i，y1，2i)，在l1i上每隔3個像素長度取一個點，將這些點在I1中的灰度梯度相位平均值記為θ1i；從右圖像I2中提取的直線特徵的集合為其中，任意一個直線特徵l2i的端點為s2，1i(x2，1i，y2，1i)和s2，2i(x2，2i，y2，2i)，在l2i上每隔3個像素長度取一個點，將這些點在I2中的灰度梯度相位平均值記為θ2i。
第一步，利用直線特徵集合恢復投影直線段 本發明將針對直線特徵提取不完整以及提取斷裂這兩類不確定性問題，依據圖像E1和E2中滿足指定搜索範圍的邊緣點，估計每個提取的直線特徵對應的投影直線段的端點，求解端點位置參數的概率密度函數，從而在統計意義上恢復投影直線段。
對於任意一個直線特徵γ＝1或γ＝2，由它的兩個已知端點計算的中點坐標記為(xγ，0i，yγ，0i)，長度記為dγi，經過它的直線記為lγi。由lγi恢復的投影直線段記為
它的兩個端點
和
到
的距離分別記為
和
由
恢復
的過程等效為求解
和
的概率密度函數的過程。與
的任意一個端點相關的距離參數
的概率密度函數求解步驟如下 第1步，搜索用於估計投影直線段端點的有效邊緣點
的有效邊緣點是指在指定搜索範圍內用於估計
的端點
位置的邊緣點。
搜索有效邊緣點的方法包括確定搜索範圍和在該範圍內選擇有效邊緣點兩個過程。有效邊緣點的搜索範圍包括空間搜索範圍和灰度梯度相位搜索範圍，由3個門限值來確定 Th表示
的有效邊緣點到直線lγi的距離最大值，最優取值為3個像素； Tτ表示
的兩個相鄰的有效邊緣點在直線lγi上的投影間距離的最大值，最優取值為3個像素，它和Th共同確定空間搜索範圍； Tθ指定
的有效邊緣點的灰度梯度相位搜索範圍為[θγi-Tθ，θγi+Tθ]，最優取值為
弧度。
將lγi的端點sγ，qi視為
的第0個有效邊緣點，記為(x(0)，y(0))，它在直線lγi上的投影記為(xp(0)，yp(0)，此時，且 搜索有效邊緣點的方法由以下兩個步驟組成，它們被循環執行，從搜索第1個有效邊緣點開始，直到確定的搜索範圍內不再有邊緣點被找到。
第1)步，確定端點
的有效邊緣點的搜索範圍 當k＝1時，第k個有效邊緣點的空間搜索範圍R(1)表示為以下四個點(u1(1)，v1(1))、(u2(1)，v2(1))、(u3(1)v3(1))和(u4(1)，v4(1))順次連接而成的矩形 其中，
的第k個有效邊緣點的灰度梯度相位搜索範圍為 當k＞1時，第k個有效邊緣點的搜索範圍由R(k)和Ω(k)表示，確定方法為 計算投影點(xp(k-1)，yp(k-1))到(xp(k-2)，yp(k-2))的距離，記為τ(k-1)，第k個有效邊緣點的空間搜索範圍R(k)由四個點(u1(k)，v1(k))、(u2(k)，v2(k))、(u3(k)，v3(k))和(u4(k)，v4(k))順次連接而成 其中，λu、λv和m的取值與k＝1時相同； 第k個有效邊緣點的灰度梯度相位搜索範圍為Ω(k)＝Ω(1)。
第2)步，在搜索範圍內選擇有效邊緣點 當k＞0時，將同時落在R(k)和Ω(k)範圍內的邊緣點的集合記為Ak。選取Ak中在直線lγi上的投影到點(xp(0)，yp(0))距離最小的邊緣點作為第k個有效邊緣點(x(k)，y(k))，它在直線lγi上的投影記為(xp(k)，yp(k))。
第2步，計算與端點相關的距離參數的概率密度函數 假定得到
的n個有效邊緣點，計算與
相關的距離參數
概率密度函數。
如果0≤n≤3，
的概率密度函數為 ρ的最優取值為0.25； 如果n＞3，
的概率密度函數計算方法由以下步驟組成 第1)步，計算
的函數
其中，nt表示
的有效邊緣點中在直線lγi上的投影到點(xγ，0i，yγ，0i)距離小於
的數目，h(k)是(x(k)，y(k))到直線lγi的距離，當γ＝1時，θ(k)表示E1中的邊緣點(x(k)，y(k))的灰度梯度相位，當γ＝2時，θ(k)表示E2中的邊緣點(x(k)，y(k))的灰度梯度相位。
第2)步，計算
的近似導數
其中，Δt的最優取值為3個像素。
第3)步，計算參數η1 其中，η0的最優取值為0.25， 第4)步，計算
的概率密度函數 第一步恢復得到的所有投影直線段的集合記為和每條投影直線段的端點都是以概率密度函數的形式從統計意義上描述的。
第二步，對恢復投影直線段進行特徵編組 通過生成一個投影直線段匹配關係圖求解，生成的無向圖記為G，方法包括下述步驟 第1步，生成投影直線段匹配關係圖的節點 計算
中任意一條投影直線段
與
中任意一條投影直線段
的對應關係測度；如果這個測度大於一個指定的門限，則判定它們是匹配的，並由
和
生成G的一個節點，節點屬性等於這個測度。
記生成的所有節點集合V＝{vα|α＝1，2，…，M}，任意一個節點vα的屬性記為μα。
第2步，判定投影直線段匹配關係圖中任意兩個節點間的連接關係 任取集合V中的兩個元素vα和vβ，假定與它們相對應的投影直線段匹配對分別為
和
判定它們之間連接關係的方法包括下述步驟 第1)步，計算vα和vβ的相容關係測度 任意兩個節點的相容性取決於它們對應的投影直線段匹配對包含在任意一幅圖像中的兩條投影直線段的相容性。計算投影直線段
和
的相容關係測度
以及
和
的相容關係測度
如果且則判定vα和vβ是相容的，計算節點vα和vβ的相容關係測度為否則，直接判定節點vα和vβ在圖G中不可連接，並返回判定其它節點間的連接關係。
第2)步，判定節點vα和vβ是否為直接可組合關係，計算組合關係測度 如果i＝a或j＝b，判定節點vα和vβ是直接可組合的，其組合關係測度為Fc(vα，vβ)＝1，進入第4)步； 如果i≠a且j≠b，計算
和
屬於同一條真實投影直線段的概率
以及
和
屬於同一條真實投影直線段的概率
如果或則判定節點vα和vβ是直接可組合的，且組合關係測度為進入第4)步；否則，進入第3)步。
第3)步，判定節點vα和vβ是否為間接可組合關係，計算組合關係測度 以集合V中的元素為節點，建立一個新的無向圖g，如果任意兩個節點是直接可組合的，則將它們在g中連接起來，連接邊權重等於第2)步計算的組合關係測度。如果圖G中節點vα和vβ在圖g中對應的節點之間存在至少一條路徑，則判定它們是間接可組合的，組合關係測度為其中，m表示不含環的路徑數，Dist(b)等於第b條不含環的路徑上所有連接邊權重的最小值；否則，直接判定它們在圖G中不可連接，並返回判定其它節點間的連接關係。
第4)步，計算節點vα和vβ之間的連接邊權重 將投影直線段匹配關係圖G中的節點vα和vβ進行連接，計算連接邊權重為 W(vα，vβ)＝Fu(vα，vβ)·Fc(vα，vβ) 當α＝β時，指定W(vα，vβ)＝0。
第3步，生成直線特徵編組並計算可靠性測度 計算圖G的所有極大團，記為Q＝{cw|w＝1，2，…，NQ}，任意一個極大團cw是集合V的子集。利用每個極大團生成一個直線特徵編組，計算該直線特徵編組的可靠性測度為 第三步，選取最可靠的直線特徵編組，確定提取的直線特徵間的匹配關係 按照下述方法生成直線特徵編組關係圖GF利用每個生成的直線特徵編組生成圖GF的一個節點，節點屬性等於相對應的直線特徵編組的可靠性測度，如果任意兩個直線特徵編組中不包含相同的投影直線段，則在圖GF中連接它們對應的節點。
計算圖GF的所有極大團，其中，每個極大團的能量等於該極大團中包含的所有節點的屬性值之和，選取能量最大的極大團包含的直線特徵編組作為最可靠的直線特徵編組。
在每個直線特徵編組中，投影直線段之間的匹配關係是確定的，並且，這些恢復的投影直線段與提取的直線特徵是一一對應的，從而，提取的直線特徵間匹配關係也是確定的，結合已知的成像參數，依據攝影測量理論可以求解匹配的直線特徵對應的三維直線段。
本發明的有益效果是 本發明利用直線特徵恢復投影直線段並構造投影直線段特徵編組的方法，能夠建立起直線特徵間包括「一配一」、「一配多」和「多配多」在內的各種對應關係；本發明第一步中通過搜索有效邊緣點估計投影直線端點的方法，可以提高投影直線段端點估計的可靠性，並能夠定量描述估計結果的可靠性；本發明第二步中對恢復投影直線段進行特徵編組時，採用了圖論中求解極大團的方法，將複雜的特徵編組過程轉化為一個經典的數學問題來求解，利於實現；本發明第二步中生成投影直線段匹配關係圖的節點和判定節點間連接關係的方法，以投影直線段端點估計的可靠性為基礎，計算了節點對應的投影直線段匹配對的匹配可能性以及同一幅圖像中的兩條投影直線段間的相容關係測度和組合關係測度，可以方便和準確地計算每個直線特徵編組的可靠性，提高匹配結果的正確性。
圖1是本發明所述的直線立體匹配方法流程示意圖； 圖2是本發明第一步所述的恢復投影直線段示意圖； 圖3是本發明第二步的第1步所述的計算
中任意一條投影直線段
與
中任意一條投影直線段
的對應關係測度的示意圖； 圖4是本發明第二步的第2步所述的計算投影直線段
和
的相容關係測度
的示意圖； 圖5是本發明第二步的第2步所述的計算
和
屬於同一條真實投影直線段的概率
的示意圖。
具體實施例方式 下面結合附圖對本發明作進一步解釋。
圖1是本發明所述的直線立體匹配方法流程示意圖本發明技術方案的輸入是已知成像參數的立體圖像對、立體圖像的邊緣檢測結果以及由立體圖像提取的直線特徵，技術方案的輸出是在左右圖像提取的直線特徵之間建立起來的匹配關係。其中，第一步是利用直線特徵集合恢復投影直線段，包括第1步，搜索用於估計投影直線段端點的有效邊緣點，第2步，計算與端點相關的距離參數的概率密度函數；第二步是對恢復投影直線段進行特徵編組，包括第1步，生成投影直線段匹配關係圖的節點，第2步，判定投影直線段匹配關係圖中任意兩個節點間的連接關係，第3步，生成直線特徵編組並計算可靠性測度；第三步，選取最可靠的直線特徵編組，確定提取的直線特徵間的匹配關係。
圖2是本發明方法第一步所述的利用提取的直線特徵恢復投影直線段的方法示意圖lγi是任意一條由圖像中提取的直線特徵，sγ，1i和sγ，2i是它的端點，(xγ，0i，yγ，0i)是它的中點，
和
由lγi恢復的投影直線段的端點，
和
分別是端點
和
到點(xγ，0i，yγ，0i)的距離，R(1)、R(2)和R(3)是在計算
的概率密度函數時確定的第1、2和3個有效邊緣點的空間搜索範圍，它們中的點表示確定的有效邊緣點，圖中圓圈內給出了搜索有效邊緣點的局部放大效果示意圖。
圖3是本發明第二步的第1步所述的計算
中任意一條投影直線段
與
中任意一條投影直線段
的對應關係測度的示意圖I1和I2是左右圖像，它們中的兩條實線表示用於恢復
和
的直線特徵l1i和l2j，為了提高對於部分遮擋問題的適應性，對應關係測度的計算只依據直線特徵l1i和l2j的相對應部分，R1i表示I1中經過l1i的端點的核線與I1的邊界圍成的陰影區域，T1i表示由l1i的端點在I2中確定的核線與I2的邊界圍成的陰影區域，R2j表示由l2j的端點在I1中確定的核線與I1的邊界圍成的陰影區域，T2j表示I2中經過l2j的端點的核線與I2的邊界圍成的陰影區域，D1表示l1i位於內的長度，D2表示l2j位於內的長度，w是設定的矩形圖像塊的寬度，最優取值為5個像素，r＝D2/D1，IL1i和IR1i表示以D1為長、w為寬並且以l1i位於的部分為公共長邊的兩塊矩形圖像區域，IL2j和IR2j表示以D2為長、(w·r)為寬並且以l2j位於的部分為公共長邊的兩塊矩形圖像區域，IL2ji和IR2ji表示對IL2j和IR2j進行插值計算後得到兩塊與IL1i和IR1i尺寸相同的圖像區域，插值方法可採用最近鄰插值、雙線性插值或三線性插值。
如果D1與l1i的長度d1i之比小於0.2，或者D2與l2j的長度d2j之比小於0.2，則指定對應關係測度否則，判定
和
滿足核線約束，對區域IL1i與IL2ji、IR1i與IR2ji分別進行歸一化互相關運算，得到兩個歸一化灰度互相關係數
和
選擇
和
中較大的一個作為
和
的對應關係測度。
圖4是本發明第二步的第2步所述的計算投影直線段
和
的相容關係測度
的示意圖e1是圖像I1的核點，經過它的虛線表示核線，
和
是兩條恢復的投影直線段，
和
上的實線部分分別表示用於恢復它們的直線特徵l1i和l1α，s1，1i和s1，2i是l1i的端點，s1，1α和s1，2α是l1α的端點，(x1，0i，y1，0i)和(x1，0α，y1，0α)分別表示l1i和l1α的中點，如果經過s1，1i或s1，2i的核線與l1α所在直線的交點位於s1，1α和s1，2α之間，或者經過s1，1α或s1，2α的核線與l1i所在直線的交點位於s1，1i和s1，2i之間，則
和
的相容關係測度為否則，選擇l1i和l1α的位於經過點(x1，0i，y1，0i)和(x1，0α，y1，0α)的兩條核線之間的端點，假定它們是s1，1i和s1，1α，Ji是經過
的核線與L1i的延長線的交點，q1i是Ji與(x1，0i，y1，0i)之間的距離，Jα是經過s1，1i的核線與l1α的延長線的交點，q1α是Jα與(x1，0α，y1，0α)之間的距離，計算
和
的相容關係測度為 其中，q1i可表示成
的函數，q1α可由s1，1i計算得到，d1i和d1α分別表示提取的直線特徵l1i和l1α的長度。
圖5是本發明第二步的第2步所述的計算
和
屬於同一條真實投影直線段的概率
的示意圖
和
是兩條恢復的投影直線段，
和
上的實線部分分別表示用於恢復它們的直線特徵l1i和l1α，選擇
和
的相互靠近的端點，假定它們是
和
和
可以合併的概率的計算方法包括以下步驟 第1)步，判定
和
是否共線 如果下面的不等式組不成立，則判定
和
不共線，
和
可以合併的概率計算過程結束；否則，判定它們共線，進入第2)步。
其中， ε的最優取值是π/20。
(x1，1i，y1，1i)和(x1，2i，y1，2i)分別表示s1，1i和s1，2i的坐標；(x1，1α，y1，1α)和(x1，2α，y1，2α)分別表示s1，1α和s1，2α坐標。
第2)步，計算
和
可以合併的概率 計算
和
可以合併的概率為 其中，S表示點(x1，0i，y1，0i)和(x1，0α，y1，0α)之間的距離。
下面詳細說明本發明中的其它有關細節。
第一點，極大團求解方法 本發明中涉及的所有無向圖的極大團求解算法均採用一種快速的極大團求解算法，具體參見Tomita E，Tanaka A，Takahashia H.The worst-case timecomplexity for generating all maximal cliques and computational experiments.Theoretical Computer Science，2006，36328-42。
第二點，離散積分求解方法 本發明方案中涉及的一元和二元積分運算全部採用牛頓-柯特斯內差求積公式，具體參見丁麗娟和程杞元著《數值計算方法》，北京北京理工大學出版社，2005年，第168-174頁。
權利要求
1.一種直線立體匹配方法，其特徵在於，包括下述步驟
已知從不同視角獲取的同一場景的兩幅圖像，分別記為左圖像I1和右圖像I2，它們的成像參數已知；對圖像I1和I2進行邊緣檢測的結果分別為圖像E1和E2，圖像E1和E2中每個邊緣點的灰度梯度相位已知；從左圖像I1中提取的直線特徵的集合為其中，任意一個線特徵l1i的端點分別為s1，1i(x1，1i，y1，1i)和s1，2i(x1，2i，y1，2i)，在l1i上每隔3個像素長度取一個點，將這些點在I1中的灰度梯度相位平均值記為θ1i；從右圖像I2中提取的直線特徵的集合為其中，任意一個直線特徵l2i的端點為s2，1i(x2，1i，y2，1i)和s2，2i(x2，2i，y2，2i)，在l2i上每隔3個像素長度取一個點，將這些點在I2中的灰度梯度相位平均值記為θ2i；
第一步，利用直線特徵集合恢復投影直線段
對於任意一個直線特徵γ＝1或γ＝2，由它的兩個已知端點計算的中點坐標記為(xγ，0i，yγ，0i)，長度記為dγi，經過它的直線記為lγi；由lγi恢復的投影直線段記為
它的兩個端點
和
到(xγ，0i，yγ，0i)的距離分別記為
和
由lγi恢復
的過程等效為求解
和
的概率密度函數的過程；與
的任意一個端點相關的距離參數
的概率密度函數求解步驟如下
第1步，搜索用於估計投影直線段端點的有效邊緣點
的有效邊緣點是指在指定搜索範圍內用於估計
的端點
位置的邊緣點；
有效邊緣點的搜索範圍包括空間搜索範圍和灰度梯度相位搜索範圍，由3個門限值來確定
Th表示
的有效邊緣點到直線lγi的距離最大值；
Tτ表示
的兩個相鄰的有效邊緣點在直線lγi上的投影間距離的最大值；
Tθ指定
的有效邊緣點的灰度梯度相位搜索範圍為[θγi-Tθ，θγi+Tθ]；
將lγi的端點sγ，qi視為
的第0個有效邊緣點，記為(x(0)，y(0))，它在直線lγi上的投影記為(xp(0)，yp(0))，此時，且
搜索有效邊緣點的方法由確定端點的有效邊緣點的搜索範圍和在搜索範圍內選擇有效邊緣點兩個步驟組成，它們被循環執行，直到確定的搜索範圍內不再有邊緣點被找到；
第2步，計算與端點相關的距離參數的概率密度函數
假定得到
的n個有效邊緣點，計算與
相關的距離參數
概率密度函數
第一步恢復得到的所有投影直線段的集合記為和
第二步，對恢復投影直線段進行特徵編組
通過生成一個投影直線段匹配關係圖求解，生成的無向圖記為G，方法包括下述步驟
第1步，生成投影直線段匹配關係圖的節點
計算
中任意一條投影直線段
與
中任意一條投影直線段
的對應關係測度；如果這個測度大於一個指定的門限，則判定它們是匹配的，並由
和
生成G的一個節點，節點屬性等於這個測度；
記生成的所有節點集合V＝{vα|α＝1，2，…，M}，任意一個節點vα的屬性記為μα；
第2步，判定投影直線段匹配關係圖中任意兩個節點間的連接關係
任取集合V中的兩個元素vα和vβ，假定與它們相對應的投影直線段匹配對分別為
和
判定它們之間連接關係並計算連接邊權重W(vα，vβ)；
第3步，生成直線特徵編組並計算可靠性測度
計算圖G的所有極大團，記為Q＝{cw|w＝1，2，…，NQ}，任意一個極大團cw是集合V的子集；利用每個極大團生成一個直線特徵編組，計算該直線特徵編組的可靠性測度為
第三步，選取最可靠的直線特徵編組，確定提取的直線特徵間的匹配關係
按照下述方法生成直線特徵編組關係圖GF利用每個生成的直線特徵編組生成圖GF的一個節點，節點屬性等於相對應的直線特徵編組的可靠性測度，如果任意兩個直線特徵編組中不包含相同的投影直線段，則在圖GF中連接它們對應的節點；
計算圖GF的所有極大團，其中，每個極大團的能量等於該極大團中包含的所有節點的屬性值之和，選取能量最大的極大團包含的直線特徵編組作為最可靠的直線特徵編組；
在每個直線特徵編組中，投影直線段之間的匹配關係是確定的，並且，這些恢復的投影直線段與提取的直線特徵是一一對應的，從而，提取的直線特徵間匹配關係也是確定的，結合已知的成像參數，依據攝影測量理論可以求解匹配的直線特徵對應的三維直線段。
2.根據權利要求1所述的直線立體匹配方法，其特徵在於，搜索有效邊緣點的方法是；
第1)步，確定端點
的有效邊緣點的搜索範圍
當k＝1時，第k個有效邊緣點的空間搜索範圍R(1)表示為以下四個點(u1(1)，v1(1))、(u2(1)，v2(1))、(u3(1)，v3(1))和(u4(1)，v4(1))順次連接而成的矩形
其中，
的第k個有效邊緣點的灰度梯度相位搜索範圍為
當k＞1時，第k個有效邊緣點的搜索範圍由R(k)和Ω(k)表示，確定方法為
計算投影點(xp(k-1)，yp(k-1))到(xp(k-2)，yp(k-2)的距離，記為τ(k-1)，第k個有效邊緣點的空間搜索範圍R(k)由四個點(u1(k)，v1(k))、(u2(k)，v2(k))、(u3(k)，v3(k))和(u4(k)，v4(k))順次連接而成
其中，λu、λv和m的取值與k＝1時相同；
第k個有效邊緣點的灰度梯度相位搜索範圍為Ω(k)＝Ω(1)；
第2)步，在搜索範圍內選擇有效邊緣點
當k＞0時，將同時落在R(k)和Ω(k)範圍內的邊緣點的集合記為Ak；選取Ak中在直線lγi上的投影到點(xp(0)，yp(0))距離最小的邊緣點作為第k個有效邊緣點(x(k)，y(k))，它在直線lγi上的投影記為(xp(k)，yp(k))。
3.根據權利要求2所述的直線立體匹配方法，其特徵在於，計算與
相關的距離參數
的概率密度函數，方法是；
如果0≤n≤3，
的概率密度函數為
ρ的最優取值為0.25；
如果n＞3，
的概率密度函數計算方法由以下步驟組成
第1)步，計算
的函數
其中，nt表示
的有效邊緣點中在直線lγi上的投影到點(xγ，0i，yγ，0i)距離小於
的數目，h(k)是(x(k)，y(k))到直線lγi的距離，當γ＝1時，θ(k)表示E1中的邊緣點(x(k)，y(k))的灰度梯度相位，當γ＝2時，θ(k)表示E2中的邊緣點(x(k)，y(k))的灰度梯度相位；
第2)步，計算
的近似導數
其中，Δt的最優取值為3個像素；
第3)步，計算參數η1
其中，η0的最優取值為0.25，
第4)步，計算
的概率密度函數
4.根據權利要求3所述的直線立體匹配方法，其特徵在於，判定集合V中的任意兩個元素vα和vβ之間連接關係並計算連接邊權重W(vα，vβ)的方法包括下述步驟
第1)步，計算vα和vβ的相容關係測度
計算投影直線段
和
的相容關係測度
以及
和
的相容關係測度
如果且則判定vα和vβ是相容的，計算節點vα和vβ的相容關係測度為否則，直接判定節點vα和vβ在圖G中不可連接，並返回判定其它節點間的連接關係；
第2)步，判定節點vα和vβ是否為直接可組合關係，計算組合關係測度
如果i＝a或j＝b，判定節點vα和vβ是直接可組合的，其組合關係測度為Fc(vα，vβ)＝1，進入第4)步；
如果i≠a且j≠b，計算
和
屬於同一條真實投影直線段的概率
以及
和
屬於同一條真實投影直線段的概率
如果或則判定節點vα和vβ是直接可組合的，且組合關係測度為進入第4)步；否則，進入第3)步；
第3)步，判定節點vα和vβ是否為間接可組合關係，計算組合關係測度
以集合V中的元素為節點，建立一個新的無向圖g，如果任意兩個節點是直接可組合的，則將它們在g中連接起來，連接邊權重等於第2)步計算的組合關係測度；如果圖G中節點vα和vβ在圖g中對應的節點之間存在至少一條路徑，則判定它們是間接可組合的，組合關係測度為其中，m表示不含環的路徑數，Dist(b)等於第b條不含環的路徑上所有連接邊權重的最小值；否則，直接判定它們在圖G中不可連接，並返回判定其它節點間的連接關係；
第4)步，計算節點vα和vβ之間的連接邊權重
將投影直線段匹配關係圖G中的節點vα和vβ進行連接，計算連接邊權重為
W(vα，vβ)＝Fu(vα，vβ)·Fc(vα，vβ)
當α＝β時，指定W(vα，vβ)＝0。
全文摘要
本發明提供一種直線立體匹配方法，能夠對直線立體匹配中的遮擋問題和特徵不確定性問題進行建模，對實現對直線間「一配一」、「一配多」或「多配多」在內的各種對應關係的求解。本發明方法對該問題進行求解的工作流程是利用提取的直線特徵從統計意義上恢復對應的投影直線→由恢復的投影直線生成所有直線特徵編組→選取最可靠的直線特徵編組作為匹配問題的解。本發明通過搜索有效邊緣點估計投影直線端點的方法，可以提高投影直線段端點估計的可靠性；對恢復投影直線段進行特徵編組，採用了圖論中求解極大團的方法，利於實現；計算每個直線特徵編組的可靠性，提高了匹配結果的正確性。
文檔編號G06T7/00GK101635052SQ20091004419
公開日2010年1月27日 申請日期2009年8月26日 優先權日2009年8月26日
發明者文貢堅, 王繼陽, 回丙偉 申請人:中國人民解放軍國防科學技術大學