胡海霞，李 钢

(1. 宜春学院 物理科学与工程技术学院;2. 宜春学院 数学与计算机科学学院，江西 宜春 336000)

笛卡尔积属于集合论的范畴，［1］设A、B 为任意集合，以A 的成员为第一元素，B 的成员为第二元素构造序偶，由所有这样的序偶组成的集合称为A 与B 的笛卡尔积。笛卡尔积在密码学［1］、数据库数据质量［2］、视觉运动分析［3］等方面都有广泛应用。比如在密码学中，根据笛卡儿积的结构特点，从工程应用的角度构造出基于笛卡尔积的各阶欺骗概率相等的最优Cartesian 认证码。［1］在数据库数据质量方面，利用笛卡尔积运算进行数据库数据质量的分析。［2］视觉运动分析中常常利用序列图像中的直线特征，匹配出序列图像中对应的直线特征，从而进行运动分析估计及三维重建。

但是直线的匹配一直是个难点，［4］传统的直线编组匹配算法［3］使用了笛卡尔积运算，但是这种方法存在计算量巨大、计算复杂的问题。因此，本文提出一种改进的直线匹配算法，该算法采用分步笛卡尔积运算、逐步过滤的方法，以解决传统的直线编组匹配算法中的计算量巨大问题。

1 分步笛卡尔积运算

一般地，直线编组匹配算法中需要两幅图像，一幅模板图像，一幅待匹配图像，分别提取出两副图像的直线特征，数量分别为M、N 条，直线特征组成的有序集合分别记为IA= {a1，a2，…，aM}(1 ≤i ≤M)，IB= {b1，b2，…，bN}(1 ≤i ≤N)，其中ai、bj分别表示两幅图像中的第i、j 条线段。匹配算法的目标是在待匹配图像中找到一个有序的特征线段组，组中的线段能与模板图像IA中的特征线段一一对应匹配。……