胡海霞，李 鋼

(1. 宜春學(xué)院 物理科學(xué)與工程技術(shù)學(xué)院;2. 宜春學(xué)院 數(shù)學(xué)與計算機科學(xué)學(xué)院，江西 宜春 336000)

笛卡爾積屬于集合論的范疇，［1］設(shè)A、B 為任意集合，以A 的成員為第一元素，B 的成員為第二元素構(gòu)造序偶，由所有這樣的序偶組成的集合稱為A 與B 的笛卡爾積。笛卡爾積在密碼學(xué)［1］、數(shù)據(jù)庫數(shù)據(jù)質(zhì)量［2］、視覺運動分析［3］等方面都有廣泛應(yīng)用。比如在密碼學(xué)中，根據(jù)笛卡兒積的結(jié)構(gòu)特點，從工程應(yīng)用的角度構(gòu)造出基于笛卡爾積的各階欺騙概率相等的最優(yōu)Cartesian 認證碼。［1］在數(shù)據(jù)庫數(shù)據(jù)質(zhì)量方面，利用笛卡爾積運算進行數(shù)據(jù)庫數(shù)據(jù)質(zhì)量的分析。［2］視覺運動分析中常常利用序列圖像中的直線特征，匹配出序列圖像中對應(yīng)的直線特征，從而進行運動分析估計及三維重建。

但是直線的匹配一直是個難點，［4］傳統(tǒng)的直線編組匹配算法［3］使用了笛卡爾積運算，但是這種方法存在計算量巨大、計算復(fù)雜的問題。因此，本文提出一種改進的直線匹配算法，該算法采用分步笛卡爾積運算、逐步過濾的方法，以解決傳統(tǒng)的直線編組匹配算法中的計算量巨大問題。

1 分步笛卡爾積運算

一般地，直線編組匹配算法中需要兩幅圖像，一幅模板圖像，一幅待匹配圖像，分別提取出兩副圖像的直線特征，數(shù)量分別為M、N 條，直線特征組成的有序集合分別記為IA= {a1，a2，…，aM}(1 ≤i ≤M)，IB= {b1，b2，…，bN}(1 ≤i ≤N)，其中ai、bj分別表示兩幅圖像中的第i、j 條線段。匹配算法的目標是在待匹配圖像中找到一個有序的特征線段組，組中的線段能與模板圖像IA中的特征線段一一對應(yīng)匹配。直線編組匹配算法的步驟如下圖1 所示。

圖1 直線編組匹配算法的步驟

S1:根據(jù)文獻［5］定義好的線段對幾何二元關(guān)系表達式(2)和(3)，分別在模板圖像和待匹配圖像中計算線段對(am，an)和線段對(bs，bt)的二元關(guān)系值。

S2:根據(jù)模板圖像中的線段對(am，an)和待匹配圖像中的線段對(bs，bt)的二元關(guān)系值，采用文獻［5］中的公式(10)計算線段對的粗匹配相似度SL(am，an，bs，bt)。

S3:用閾值Th1過濾SL，得到SL≥Th1的所有四元組(am，an，bs，bt)。根據(jù)四元組生成每條模板特征線段ai(1≤i≤M)的候選線段集合Ui，方法如下:

(1)找出m =i 的所有四元組(ai，an，bs，bt)，再在(ai，an，bs，bt)中，針對n =j(1≤j ≤M，j ≠i)分別找出四元組(ai，aj，bs，bt)，此時，將(ai，aj，bs，bt)中對應(yīng)的所有s 組成集合Vij。

(2)找出n = i 的所有四元組(am，ai，bs，bt)，再在(am，ai，bs，bt)中，針對m = j(1 ≤j ≤M，j ≠i)分別找出四元組(aj，ai，bs，bt)，此時，將(aj，ai，bs，bt)中對應(yīng)的所有t 組成集合V'ij。

(3)將Vij和V'ij中的數(shù)據(jù)求交集，即Ui=

S4:利用所有的候選線段集合Ui(1 ≤i ≤M)，采用分步笛卡爾積運算，再用閾值Th2逐步過濾，最后生成模板特征的候選匹配線段組。生成過程示意圖如下圖2 所示:

圖2 生成候選匹配線段組的過程

(1)分步笛卡爾積運算:首先設(shè)G1= U1，然后將G1與U2做笛卡爾積運算得到G'2，用閾值Th2對G'2進行過濾得到G2，再G2與U3做笛卡爾積運算得到G'3，用閾值Th2對G'3進行過濾得到G3，依此類推，最后得到候選線段組集合GM。

(2)逐步過濾的方法:以G'k→過濾Gk(1 ＜i≤k)為例，設(shè)G'k= {(c1，c2，…，ck)}(ci∈IB)，表明ai與ci是對應(yīng)匹配的。首先計算G'k中每個元素(c1，c2，…，ck)的相似度Sk(S1=0 )，表達式為Sk= Sk－1+(SL(ai，ak，ci，ck)+SL(ai，ak，ci，ck))。再用閾值Th2過濾出Sk/(k(k－1))≥Th2的元素而得到Gk。

S6:選取GM中匹配相似度SG最大的元素作為最后的匹配線段組。

2 分布笛卡爾積運算的核心代碼

由于直線匹配算法的代碼量很大，在此僅列出S3 和S4 兩部分的核心代碼。

S3 的核心代碼:

%過濾出SL≥Th1的四元組(am，an，bs，bt)

tmp=find(SL(:，5)＞=Th1);

%SL= {(am，an，bs，bt，SL(am，an，bs，bt))}

SL_Filter=SL(tmp(:)，:);

%生成每條模板特征線段的候選線段集合U

U=cell(1，M);%定義U

for i=1:M

U{i}=1:N;%初始化

3 實驗

實驗平臺為Matlab 2011b。實驗采用一組真實的衛(wèi)星圖像，如圖3 所示。圖3(a)為模板圖像，圖3(c)為待匹配圖像;圖3(b)模板線特征圖，線特征均為6 條;圖3(d)為待匹配線特征圖，線特征分別為51 條;圖3(e)為實驗所得線段組匹配結(jié)果圖像。

圖3 實驗圖像

實驗所取的兩個閾值分別為Th1= 0.85 和Th2= 0.9 ，實驗中得到的相關(guān)數(shù)據(jù)如下表1 所示。比較表中“本文方法所得線段組數(shù)量”和“直接笛卡爾積所得候選線段組數(shù)量”兩項數(shù)據(jù)，表明本文算法大大減少了候選線段組數(shù)量，極大地提高了直線匹配的效率。

表1 實驗中得到的相關(guān)數(shù)據(jù)

4 結(jié)論

本文研究了笛卡爾積運算在圖像間直線特征匹配中的應(yīng)用，針對運用傳統(tǒng)的直線編組匹配方法中采用直接笛卡爾積運算存在的計算量巨大、計算復(fù)雜等問題，提出了一種改進的算法，該算法詳細介紹了采用分步笛卡爾積、逐步過濾的過程，并列出了Matlab 環(huán)境下的主要核心程序代碼。實驗表明本文所提算法大大減少了候選線段集數(shù)量，并驗證了整個直線特征匹配的高效性和有效性。

［1］劉金龍，許宗澤. 笛卡爾積與認證碼［J］. 電子與信息學(xué)報，2008，30(6):1441－1444.

［2］陳衛(wèi)東，張維明. 笛卡爾積運算對數(shù)據(jù)庫數(shù)據(jù)質(zhì)量的傳遞影響［J］. 計算機科學(xué)，2008，35(6):210－213.

［3］HP Sang，KM Lee，UL Sang.A line feature matching technique based on an eigenvector approach［J］.Computer Vision ＆ Image Understanding，2000，77(3):263－283.

［4］ Schmid C，Zisserman A.Automatic line matching across views［J］.IEEE Computer Vision and Pattern Recognition，1997，17(19):666－671.

［5］胡海霞，李鋼. 幾何特性二元關(guān)系的直線匹配［J］. 中國圖象圖形學(xué)報，2014，19(9):1338－1348.