张量投票(Tensor voting)理论是一种经典的显著性结构特征推理理论, 最初由南加利福尼亚大学Guy等首先提出^[1].其基本思想源于心理学领域的Gestalt原理, 即:人类视觉系统趋于根据某种准则将所提取到的图像特征按照某种规律编组为更高层的结构^[2].张量投票本意在于从带有强噪声、离群点的三维点云中推理隐含的结构特征^[3].在随后的近20年中, 张量投票因其强大的显著性结构推理能力受到了国内外学者的广泛关注.经过不断的完善, 已成功应用于图像处理、点云处理、计算机视觉等多个领域^[4-5].具有代表性的研究成果有: Tang等应用张量投票实现了强噪声三维点云中采样点主曲率及其方向的鲁棒估计, 避免了传统曲率估计方法由于曲面拟合及求导造成的噪声敏感问题^[6]; Tong等将张量投票用于二维图像和三维点云数据的边界结构推理中, 实现了存在离群点、噪声、方向不连续等因素下, 三维点云曲面边界、二维人脑MRI影像的边界结构推理^[7]; 此外, Tong等还将4D张量投票用于非静态场景的对极几何参数估计^[8], 该方法采用一种非迭代推理机制求取对极几何参数, 避免了传统的基于优化的参数估计中初值敏感、局部极值效应、参数空间维数对优化过程影响等不利因素; Mordohai等将张量投票用于两幅静态图像的匹配, 解决了在带有离群点、缺失纹理信息情况下静态图像的可靠匹配问题^[9]; Kim等基于张量投票提出了一种三角网格曲面$n$维特征识别方法, 实现了三角网格曲面几何属性特征和附加属性(如颜色)特征的识别等^[10].当前, 张量投票已成为感知分组和机器学习领域的经典理论之一^[11].

尽管张量投票具有强大的结构特征推理能力, 但计算效率一直是制约该理论进一步应用于工程实际最为关键的因素之一.究其根源, 造成该算法效率低的主要原因在于长期以来传统的张量投票过程一直无法得到解析形式求解表达式, 只能依赖数值计算进行近似求解, 计算过程复杂、耗时, 利用数值计算求解时, 计算精度和计算效率之间存在矛盾^[12].近年来, 国内外学者为解决上述问题不断进行探索, 具有代表性的研究成果有: Wu等提出了一种闭式张量投票算法(Closed-form solution to tensor voting, CFTV), 该算法通过构造新的投票关系, 将积分式整理为一个新的数学表达式, 这在投票过程中就大大节省了计算时间^[12].然而, Maggiori等从理论分析到实际举证两个方面均证明了CFTV算法存在本质性的错误^[13].

为了解决传统2D张量投票计算过程复杂、耗时, 计算精度与计算效率存在矛盾的问题, 本文基于局部坐标构架, 设计了一种二维解析张量投票新机制, 推导了二维棒张量和二维球张量投票解析表达式, 应用该表达式可实现二维棒张量和二维球张量的直接、快速、精确投票, 为二维图像、二维点集的快速、鲁棒结构推理奠定基础.需特别指出的是, 本文研究方法可进一步推广至高维张量投票, 进而用于高维数据结构的精确、鲁棒推理.

1.   传统张量投票算法

利用原始张量投票(Original tensor voting, OTV)算法进行高维数据结构推理, 从本质上讲是通过邻近点之间传递(投票)张量(微分几何信息)的机制, 从大量、不可靠(含有噪声、离群点的、微分几何信息估计不准确的)推理其隐含的几何结构的一种方法.其机制类似于Hough变换, 且其应用范围更广, 可推广至$N$维.利用张量投票理论进行显著性结构推理可以描述为如下三步:张量编码、张量投票和张量分解, 如图 1所示.

图 1  传统张量投票算法流程

Fig. 1  Flow-chart of traditional tensor voting algorithm

下载: 全尺寸图片 幻灯片

在张量编码阶段, 根据已知信息(位置、法向、曲率等)将输入数据(点云、三角网格曲面等)表示为一系列稀疏张量(由正定对称矩阵表示), 若原始数据中只有位置信息, 则其被编码为一系列单位矩阵; 在张量投票阶段, 分别进行稀疏投票和稠密投票, 两者投票机制完全相同, 其区别在于:稀疏投票是对原始数据集中存在数据点的位置进行投票, 以通过投票提高张量信息的准确性, 稠密投票是对数据集分布空间内的规则栅格点进行投票, 形成稠密张量场, 为后续的结构特征推理服务; 在张量分解阶段, 对投票后的各张量矩阵进行特征分解(在二维空间中, 分解为棒张量分量和球张量分量, 在三维空间中, 分解为棒张量分量、板张量分量和球张量分量), 获得各张量分量及其显著性, 进而根据张量显著性进行结构推理^[1].纵观整个张量投票过程, 投票阶段的精度和效率成为影响整个算法性能的关键.本文着重从投票过程入手, 研究提高张量投票算法精度和效率的方法.

图 2为二维空间中张量投票示意图.如图所示在对二维空间中的点${p}$进行特征推理时, 首先将其邻近点${p_1}, {p_2}, {p_3}$, $\cdots$编码为二阶对称张量${T_1}, {T_2}, {T_3}, \cdots$, 再将各张量矩阵分解为棒张量分量${T_{Si}}$和球张量分量${T_{Bi}}$, 张量分解过程如下:

图 2  二维张量投票示意图

Fig. 2  Illustration of tensor voting in 2D

下载: 全尺寸图片 幻灯片

若${T}$是二维空间中的二阶对称张量(非负定二阶对称矩阵), 则其可分解为

其中, ${\lambda_1}\geq{\lambda_2}\geq0$为${T}$的特征值, ${\pmb{e}_1}$和${\pmb{e}_2}$为对应的特征向量. ${T}_S=(\lambda_1-\lambda_2)\pmb{e}_1\pmb{e}_1^{\rm T}$称为$T$的棒张量分量, $\lambda_1-\lambda_2$为棒张量分量的显著性; ${T}_B=\lambda_2(\pmb{e}_1 \pmb{e}_1^{\rm{T}}+\pmb{e}_2\pmb{e}_2^{\rm{T}})$称为$T$的球张量分量, $\lambda_2$为球张量分量的显著性.

在张量投票过程中, 邻近点${p_i}$向点${p}$投出自己的选票(张量矩阵), 两种张量分量各自投票, 点${p_i}$累计来自各邻近点的棒张量投票和球张量投票, 用于推理自身的结构特征.

1.1   二维棒张量投票

下面以二维法向张量投票为例简要介绍传统棒投票过程.设如图 3所示坐标原点$o$处有一个棒张量$T=\pmb{v}\pmb{v}^{\rm{T}}$, 其中, $\pmb{v}=\left[{array}{cccc} 0\\ 1 {array}\right]$, 则该棒张量在任一点$p$处的投票为$T_{so}(p)=$ $DF$ $\times$ $\pmb{v}'\pmb{v}'^{\rm{T}}$, 其中$DF$为衰减函数, $\pmb{v}'$为用于构建棒投票张量矩阵的单位向量.由此可知, 二维空间中的棒张量投票可表示为单位向量$\pmb{v}'$的估计问题.为此, 张量投票理论提出$\pmb{v}'$应从点$p$指向连接$op$两点的密切圆弧的圆心, 因为这条圆弧能够保持曲率不变.

图 3  标准棒张量投票示意图

Fig. 3  Illustration of standard stick tensor voting

下载: 全尺寸图片 幻灯片

由图 3可求得: $\pmb{v}'=\left[{array}{cccc}-\sin(2\theta)\\ \cos(2\theta) {array}\right]$.传统棒张量投票理论定义衰减函数$DF$如下:

其中, $s = \theta l/\sin \theta $为op两点间弧长, $k = 2\sin \theta /l$为密切圆弧的曲率, $\sigma$为控制投票衰减速度的尺度因子, c为用于权衡距离和曲率的控制参数.式(2)定义的主旨在于通过两点间的距离以及两点连线与$\pmb{v}$的关系控制不同投票位置和投票方向上张量投票的强度.由式(2)直接得到的衰减函数特性如图 4(a) 所示.为防止对投票点附近的点进行投票时发生混乱, 利用阈值对$\theta$的范围进行限制, 即仅取$\theta\leq\pi/4$范围内的衰减函数, 其他情况下衰减函数置0, 限定后的衰减函数特性如图 4(b) 所示.

图 4  传统张量投票中的衰减函数特性

Fig. 4  Demonstration of decay function in traditional tensor voting

下载: 全尺寸图片 幻灯片

为了计算二维平面中任意点${p}_i$处的棒张量(方向$\pmb{v}_i$可能为任意方向)向其邻近点$p_j$的棒张量投票, 需要以点$p_i$为原点, $\pmb{v}_i$方向为${y}'$轴建立局部坐标系, 如图 5所示.

图 5  任意两点间棒张量投票坐标变换示意图

Fig. 5  Illustration of stick voting coordinate transformation between any two points

下载: 全尺寸图片 幻灯片

设用于对齐坐标系$oxy$与$ox'y'$的变换矩阵为$R$, 局部坐标系$ox'y'$中估计$p_j$的方向向量为$\pmb{v}_j$, 则在全局坐标系中由$\pmb{v}_i$估计得到的$\pmb{v}_j'$为

因此, 可得点$p_i$对点$p_j$的棒张量投票$T_S$为

1.2   二维球张量投票

在传统张量投票理论中, 将二维球张量投票表示为投票点处所有方向的棒张量投票的积分.如图 6所示, 点$p_i$对点$p_j$进行球张量投票时, 取平面内点$p_i$处任意单位向量$\pmb{v}_\theta$, 应用棒张量投票方法, 估计$p_j$接收到的方向向量$\pmb{v}_\theta'$, 再改变$\theta$并把所有产生的棒投票结果累加起来即为点$p_i$对$p_j$的球张量投票.该过程可表示为

图 6  由棒张量投票求取球张量投票

Fig. 6  Ball tensor induced by stick tensor

下载: 全尺寸图片 幻灯片

式(5)即为传统张量投票中二维球张量投票计算公式.然而, 由于任意方向棒张量投票和积分表达式中均引入了用于坐标系对齐的变换矩阵$R_\theta$, 使得球张量投票解析表达式的求取变得异常困难, 在传统的张量投票算法中只能采用数值积分逼近模拟积分, 即:以一定间隔对$\theta$在$0\sim2\pi$区间内进行等间隔采样, 再将计算所得的各棒张量投票矩阵进行累加, 以近似表示真实的二维球张量投票矩阵.通过分析不难发现, 这样的处理存在如下不足.

1)在进行投票过程中需要频繁的坐标对齐操作, 这在很大程度上降低了算法的效率, 因此在实际应用中往往事先计算出标准的棒张量场, 再通过棒张量场的旋转和累加构成球张量场, 在实际投票过程中再通过类似查表的机制尽可能提高张量投票过程的计算效率.

2)虽然采用张量场进行投票在一定程度上提高了算法的效率, 但由于其采用的是一种类似查表的方式进行投票, 因此其仅适用于采样点分布十分规律的数据(如二维图像等采样点坐标为整数的数据), 不适用于采样点随机分布的数据处理;

3)由于传统算法采用数值积分代替连续积分, 其积分步长必然成为制约投票效率和投票精度的关键因素, 即:积分步长越大则投票效率越高, 同时投票精度越差; 反之, 则投票效率越差, 同时投票精度越高.这意味着利用传统的张量投票算法必然造成算法效率和算法精度之间的矛盾.

为此, 本文针对二维空间中张量投票问题, 以传统张量投票基本思想为基础, 设计了一种新的张量投票机制, 并以此为基础求得了棒张量投票和球张量投票的解析表达式, 利用该解析表达式可实现张量投票矩阵的直接求解, 不仅有效简化了张量投票过程, 有效避免了球张量投票过程中引入的数值积分运算, 提高了算法的效率; 还有效克服了算法效率与算法精度之间的矛盾.

2.   二维解析张量投票

2.1   二维解析棒张量投票

出于一般性考虑, 以二维空间中任意两点$p_i$到$p_j$的棒张量投票为例进行研究, 如图 7所示.

图 7  二维解析棒张量投票示意图

Fig. 7  Illustration of stick voting analytical solution in 2D

下载: 全尺寸图片 幻灯片

图 7中棒张量由点$p_i$投向点$p_j$. $\pmb{v}_i$为$p_i$处棒张量矩阵对应的单位方向向量, 即$p_i$棒张量矩阵$T=\pmb{v}_i\pmb{v}_i^{\rm{T}}$, $\pmb{v}_j$为$p_j$处接收到张量矩阵对应的单位方向向量. $\pmb{v}_i$与$\pmb{v}_j$共同指向连接两点密切圆弧的中心, $\rho$为连接两点密切圆弧的曲率半径. l为两点间的距离. $\pmb{r}$为$p_i$指向$p_j$的单位向量.由张量投票理论可知, 棒张量投票的过程可分解为单位方向向量$\pmb{v}_j$的估计和衰减函数$DF(\cdot)$的计算两个相对独立的过程.为此, 先考虑单位方向向量$\pmb{v}_j$的估计问题.由图 7可知, $\pmb{v}_j$可通过向量计算直接求取, 由于$\pmb{v}_i$, $\pmb{v}_j$与$\pmb{r}$均为单位向量, 故该计算过程可表示如下:

由于$l=2\rho \pmb{v}_i^{\rm{T}}\pmb{r}$, 代入式(6), 可得$\rho {\pmb v}_j=\rho \pmb{v}_i-2\rho {\pmb r}{\pmb r}^{\rm{T}}\pmb{v}_i$, 即

其中, $I$为$2\times2$阶单位矩阵.

由于在构造棒张量投票矩阵过程中要求$\pmb{v}_j$为单位向量, 求取向量$\pmb{v}_j$的模, 如下式所示:

由于$\pmb{r}$和$\pmb{v}_i$均为单位向量, 即: $\pmb{r}^{\rm{T}}\pmb{r}=\pmb{v}_i^{\rm{T}}\pmb{v}_i=1$, 可得

即$\pmb{v}_j$是满足二维棒张量投票要求的单位向量.

为便于二维球张量解析表达式的求解, 本文采用文献[11]中定义的衰减函数, 如下式所示:

其中, $c_{ij}={\rm e}^{(-l^2/\sigma^2)}$, $l=\|{p_j-p_i}\|$为两点间的距离, $\sigma$为投票控制强度的尺度参数.

为此, 二维平面中点$p_i$对点$p_j$的棒张量投票为

其中, $R=\mathit{I}-2\pmb{r}\pmb{r}^{\rm{T}}$, $\pmb{r}={(p_j-p_i)}/{\|{p_j-p_i}\|}$.

式(11)为本文提出的二维解析棒张量投票表达式.可以看出, 该表达式的求取是在深入研究张量投票理论基本思想的基础上, 利用向量计算, 推导过程中摒弃了传统棒张量投票过程中坐标系对齐的过程, 直接从全局坐标系下求取接收向量, 整个过程更加清晰, 计算过程也更为简洁, 应用该式可直接计算平面中任意两点间的棒张量投票.在棒张量投票过程中, 选用了新的衰减函数, 该衰减函数不仅具有原衰减函数类似的性质, 而且更加便于计算.尤为关键的是, 该衰减函数的应用使得二维球张量投票的解析求解成为可能.

2.2   二维解析球张量投票

根据传统二维球张量投票理论, 二维平面中的球张量投票可表示为投票点处所有方向的棒张量投票的积分.考虑图 6中点$p_i$对点$p_j$进行球张量投票, 取平面内点$p_i$处任意单位向量$\pmb{v}_\theta$, 应用本文提出的二维解析棒张量投票方法对点$p_j$进行棒张量投票, 估计$p_j$接收到的方向向量$\pmb{v}_\theta'$, 再改变$\theta$并把所有产生的棒投票结果累加起来即为点$p_i$对$p_j$的球张量投票.由于本文所设计的二维解析棒张量投票中投票公式仅与点$p_i$和点$p_j$的相对位置及$p_i$处的方向向量$\pmb{v}_\theta$有关, 与参考坐标系无关.可以通过定义一个方向可控的单位向量$\pmb{v}_\theta$, 使其满足当控制参数$\theta$从$0\sim2\pi$变化时, 向量$\pmb{v}_\theta$绕投票点$p_i$转动一周.基于此思想, $\pmb{v}_\theta$可构造如下:

因此, 二维解析球张量投票的过程可表示为

由于$R=\mathit{I}-2\pmb{r}\pmb{r}^{\rm{T}}$, 与积分变量$\theta$无关, 将式(10)和式(12)代入式(13), 可求得

式中, $c_{ij}$, $I$以及$\pmb{r}$的定义与二维解析棒张量投票中相同.

式(14)为本文提出的二维解析球张量投票表达式.可以看出, 该表达式的求取是在深入研究张量投票理论基本思想的基础上, 充分利用二维解析棒张量投票公式与坐标系无关的特性, 定义了一个方向可控的单位向量, 通过向量旋转和连续积分直接求取二维解析球张量投票表达式, 应用该表达式可直接计算平面中任意两点间的球张量投票.

2.3   任意二阶对称张量的二维解析张量投票

在实际二维张量投票中, 待投票的张量往往包含棒张量分量和球张量分量, 如式(1)所示.基于式(11)和式(14)给出待投票张量包含两种张量分量情况下的张量投票表达式.

设二维平面中任意点$p$处的二阶对称张量为$T=\left[{array}{ccc} a & b \\ b& c {array} \right]$, $\mathit{a}\geq0$且$\mathit{ac}\geq{\mathit{b}^2}$, ${\lambda_1}\geq{\lambda_2}\geq0$为$T$的特征值, $\pmb{e}_1$, $\pmb{e}_2$为对应的特征向量.考虑点$p$向邻近点$q$进行张量投票, 根据式(11), 棒张量分量$T_S=(\lambda_1-\lambda_2)\pmb{e}_1\pmb{e}_1^{\rm{T}}$产生的张量投票为

根据式(14), 球张量分量$T_B=\lambda_2(\pmb{e}_1\pmb{e}_1^{\rm{T}}+\pmb{e}_2\pmb{e}_2^{\rm{T}})$产生的张量投票为

则位于点$p$的张量$T$投向点$q$的张量$T'$为

其中, $H=\lambda_1H_1+\lambda_2(\frac{3\pi}{4}I-\frac{\pi}{2}\pmb{r}\pmb{r}^{\rm{T}}-H_1)$, $H_1=(1-(\pmb{r}^{\rm{T}}\pmb{e}_1)^2)\pmb{e}_1\pmb{e}_1^{\rm{T}}$. $c_{ij}$, $I$以及$\pmb{r}$的定义与第2.1节和第2.2节中的定义相同.

需要特别指出的是, 文献[12]也对解析张量投票问题进行了研究, 并给出了张量投票的闭式表达式(Closed-form solution to tensor voting), 但随后的研究证明了文献[12]的研究方法和研究结果均是错误的, 主要表现在如下两个方面^[13]:

1)推导板张量和球张量投票公式过程中以${N}_\theta$为积分变量, 意义不明确, 且推导过程自相矛盾;

2)应用该方法求得的张量投票矩阵为非对称矩阵, 导致各特征向量非正交, 与张量投票的基本思想相悖.

在本文研究过程中, 以张量投票基本理论为基础, 借鉴文献[12]中的衰减函数构造思路, 重新设计和推导了二维解析棒张量和球张量投票公式, 在二维解析球张量投票公式推导过程中以控制参数为积分变量, 具有明确的物理意义.

应用本文方法对文献[13]中给出的算例进行计算.设待投票张量$T_1= \left[{array}{ccc} 1/2 & 0 \\ 0& 1 {array} \right]$, 投票方向为${\pi}/{4}$, 即: $\pmb{r}$ $=$ $[\sqrt{2}/2\quad\sqrt{2}/2]^{\rm{T}}$, 应用文献[12]中方法得到的投票矩阵为

该矩阵为非对称矩阵, 证明了文献[12]中给出的张量投票方法是错误的.

应用本文方法重新计算, 过程如下:首先, 对$T$进行张量分解: $T=\lambda_1\pmb{e}_1\pmb{e}_1^{\rm{T}}+\lambda_2\pmb{e}_2\pmb{e}_2^{\rm{T}}$, 可得$\lambda_1=1$, $\lambda_2=1/2$, $\pmb{e}_1=$ $[0\quad1]^{\rm{T}}$, $\pmb{e}_2=[1\quad0]^{\rm{T}}$, 故棒张量分量为

球张量分量为

其次, 将上述参数代入式(11)和式(14), 求得接收到的棒张量投票为

接收到的球张量投票为

因此, 最终接收到的张量投票为$T'=T_S'+T_B'$.由于$T_S'$和$T_B'$均为非负定对称矩阵, 因此$T'$必然为非负定对称矩阵.实质上, 不难证明, 只要投票矩阵$T$为非负定对称矩阵, 则接收到的张量矩阵$T'$必为非负定对称矩阵.

此处仅初步验证了本文方法张量投票矩阵非负定对称性, 下面分别从投票强度仿真分析, 棒张量投票域和球张量投票域仿真分析和应用实验三个方面验证本文方法的性能.

3.   实验研究

3.1   投票强度分析实验

在张量投票理论中, 投票强度是指接收到的张量投票矩阵的强度, 往往通过衰减函数体现.在传统的张量投票理论中, 衰减函数的定义如式(2)所示.由式(2)可见, 该函数值两点之间的距离$l$及夹角$\theta$有关.当$\theta$一定时, $l$越大, 衰减函数值越小, 投票点对受票点的影响也越小; 当$l$一定时, $\theta$越小, 衰减函数值越小, 投票点对受票点的影响也越小.

本文采用的衰减函数特性如图 8所示, 其中图 8(a) 为利用二维图像体现的衰减函数幅度特性, 图 8(b) 为利用三维图形体现的衰减函数幅度特性.图 8(a) 中, 横、纵坐标表示受票点坐标, 亮度信息代表投票强度, 图 8(b) 中横、纵坐标表示受票点坐标, 高度信息代表投票强度.由图 8中可以看出, 投票强度的大小与角度$\theta$和距离$l$有关, 且当$\theta$一定时, $l$越大, 衰减函数值越小, 投票点对受票点的影响越小; 当$l$一定时, $\theta$越小, 衰减越大投票强度越小, 投票点对受票点的影响越小, 且该衰减函数在投票点附近没有出现幅度特性紊乱, 因此可以不用角度阈值加以限定.由于该衰减函数与传统张量投票算法中实际使用的衰减函数具有相似的衰减特性, 其可直接应用于解析张量投票.

图 8  本文采用的衰减函数特性

Fig. 8  Demonstration of adopted decay function

下载: 全尺寸图片 幻灯片

3.2   投票域验证实验

张量投票域(Tensor voting fields)是张量投票过程中投票点附近所有位置接收到的张量投票方向和强度的直观表示, 已成为验证张量投票正确性最为直观、有效的手段之一.为此, 本文对待投票张量为棒张量和球张量的情况下投票点附近的张量投票域进行仿真实验, 以验证本文提出的二维解析棒张量和球张量投票方法的正确性.首先, 为了验证本文提出的二维解析棒张量投票方法的正确性, 设定坐标为$[0\quad0]^{\rm{T}}$的${\mathit{o}}$点处有一棒张量$T_1$ $=$ $\left[{array}{ccc} 0 & 0 \\ 0 & 1 {array} \right]$, 分别应用传统张量投票算法和本文方法计算$\mathit{o}$点附近的投票域, 结果如图 9所示.由图 9可见, 利用本文方法求取的投票域, 其分布范围较传统张量投票算法求取的投票域分布范围广, 这是因为在传统张量投票算法的衰减函数设计中, 为了避免投票点附近衰减函数特性混乱而人为限定了所有$\theta>\pi/4$范围的衰减函数全部置0.本文采用的衰减函数, 由于不存在投票点附近幅度混乱的问题, 因而可以不用对$\theta$进行强制限定.实质上, 通过观察投票域局部放大图可以发现, 利用两种方法得到的棒张量投票域中各点接收到的张量均具有相同的主方向(由图中箭头的方向体现)和相似的强度衰减特性(由图中线段的长短体现).因此, 该棒张量投票域符合Gestalt原理, 即符合张量投票理论的基本思想.

图 9  棒张量T₁形成的投票域

Fig. 9  Voting filed generated by stick tensor T₁

下载: 全尺寸图片 幻灯片

为验证本文提出的二维解析棒张量投票方法的自对齐功能, 设定坐标为$[0\quad0]^{\rm{T}}$的$o$点处的待投票棒张量为$T_2$ $=$ $\left[{array}{ccc} 1/2 &-1/2 \\-1/2 & 1/2 {array} \right]$, 由本文方法和原张量投票方法计算所得的棒张量投票域如图 10所示.显然, 本算例中, 待投票张量的主方向向量为$[-1/\sqrt{2}\quad1/\sqrt{2}]^{\rm{T}}$, 为此, 利用传统张量投票算法计算该棒张量的投票域时, 需经过``坐标变换--标准投票域计算--坐标反变换''的复杂过程, 而利用本文提出的二维解析棒张量投票公式计算时, 可直接求取该投票域.由图 10可见, 采用两种方法计算的投票域在主方向和强度衰减特性方面均是一致的.

图 10  棒张量T₂形成的投票域

Fig. 10  Voting filed generated by stick tensor T₂

下载: 全尺寸图片 幻灯片

为了验证本文提出的二维解析球张量投票方法的正确性, 设定坐标为$[0\quad0]^{\rm{T}}$的$\mathit{o}$点处有一球张量$\mathit{T}_3=\left[{array}{ccc} 1 & 0 \\ 0& 1 {array} \right]$, 由传统张量投票方法和本文方法计算所得投票域如图 11所示.

图 11  球张量T₃形成的投票域

Fig. 11  Voting filed generated by ball tensor T₃

下载: 全尺寸图片 幻灯片

从图 11可以看出, 二维球张量投票域中, 采用两种方法求取的各点处接收到的张量矩阵主方向相同, 且采用本文方法求取的各张量的强度分布更加均匀.根据传统张量投票理论, 二维球张量投票域中各处接收到的张量矩阵, 其主方向应垂直于投票点与受票点的连线, 且其强度随两点间的距离按高斯函数衰减.显然, 应用本文方法求取的二维球张量投票域与理论结果更相近.而传统的张量投票方法虽然主方向与理论投票方向一致, 但张量投票的强度存在误差, 这是因为在传统的球张量投票计算中采用数值积分代替了连续积分, 数值积分过程中参数$\theta$的步长影响了球张量投票的精度(本仿真实验中取$\Delta\theta=\pi/16$).当然, 通过减小$\Delta\theta$可以提高球张量投票的精度, 但是同时也会造成算法效率的下降.因此, 应用传统张量投票算法进行球张量投票时, 投票精度与投票速度相互矛盾, 而利用本文提出的二维解析张量投票可以同时兼顾投票精度和投票速度.

3.3   投票效率实验

为了检验本文提出的二维解析张量投票方法的效率, 以Inter Corei5、1.7 GHz CPU、4 GB内存的PC机为硬件处理平台, 在Matlab环境下进行实验研究.

相对于张量编码和张量分解而言, 张量投票过程是影响整个算法效率的核心, 为此, 本文仅对传统张量投票算法和本文提出的张量投票方法投票所需的时间进行统计, 统计结果见表 1 (在实验过程中两种投票方法参数设置完全相同).

表 1  算法运行时间比较

Table 1  Running time comparison between the methods

投票	棒投票时间(ms)		球投票时间(ms)
点数	传统方法	本文方法	传统方法	本文方法
4 225	9.123	3.775	222.619	1.549
6 241	11.820	6.137	292.801	2.273
16 641	36.184	13.621	979.026	7.407

下载: 导出CSV 

| 显示表格

观察表 1可以发现, 本文方法二维棒张量投票效率是传统二维棒量投票算法的1.8倍以上, 本文提出的二维球张量投票效率是传统二维球量投票算法的120倍以上.表明本文算法不仅具有更好的计算精度, 而且其计算速度明显优于传统的二维张量投票算法.

实质上, 由于本文算法在进行球张量投票时是直接计算的, 无需循环迭代, 设本文算法单次球张量投票的时间复杂度为${\rm O}(1)$, 则传统投票算法球投票时需要在$(0, 2\pi)$内进行叠加循环, 其等效时间复杂度为${\rm O}(\mathit{n})$, 其中, $\mathit{n}$为由棒张量计算球张量时循环叠加的次数.由于传统张量投票中还涉及到局部坐标系求取和坐标系对齐等计算, 因此, 本文算法的实际运行效率尚高于理论运行效率.

为了进一步对比两种算法的时间复杂度, 对10组样本数据(张量投票点数分别为: 121, 441, 961, 1 681, 2 601, 3 721, 5 041, 6561, 8 281和10 201)进行棒张量投票和球张量投票, 并统计其运行时间, 结果如图 12和图 13所示.

图 12  二维棒张量投票运行时间对比实验结果

Fig. 12  Running time comparison between 2D stick tensor voting method

下载: 全尺寸图片 幻灯片

图 13  二维球张量投票运行时间对比实验结果

Fig. 13  Running time comparison between 2D ball tensor voting method

下载: 全尺寸图片 幻灯片

观察图 12和图 13, 本文提出的张量投票算法的效率明显优于传统的张量投票算法.

3.4   应用研究

利用张量投票算法进行显著性结构推理, 是张量投票理论的出发点和落脚点.为此, 本文对常用于验证张量投票算法显著性结构推理能力的3个二维点集(Banana, Sweet-potato和Apple三个点集)进行显著性结构推理实验(采用与文献[3]相同的结构推理方法), 实验结果如图 14所示.对比两种算法的结构推理结果可以发现, 利用本文算法推理得到的结构特征曲线更为完整也更为光滑, 表明本文提出的二维解析张量投票算法可用于二维点集的显著性结构推理.

图 14  两种张量投票算法结构推理效果

Fig. 14  Results inferred by OTV and the proposed method

下载: 全尺寸图片 幻灯片

进一步, 将本文方法用于二维灰度图像边缘结构特征推理, 采用文献[14]的张量编码方法对灰度图像进行张量编码, 采用本文方法进行张量投票, 继而应用文献[3]中的特征提取方法进行边缘提取.将本文实验结果与Sobel算子、Log算子、Canny算子等传统的图像边缘提取方法及传统张量投票结构推理结果进行比较, 结果如图 15所示.实验结果表明, 对实验中选定的灰度图像传统方法中Canny算子法具有更好的图像边缘提取能力.张量投票用于灰度图像边缘提取较Canny算子法具有更好的结构特征推理能力.传统的张量投票和本文提出的二维解析张量投票都能实现灰度图像的结构特征提取, 两者相比本文方法提取的边缘特征更光顺、速度更快.

图 15  本文算法用于灰度图像结构推理

Fig. 15  Utilization of the proposed method in structure inference of gray scale image

下载: 全尺寸图片 幻灯片

4.   结语

本文提出了一种二维解析张量投票算法, 求解了二维解析棒张量投票和球张量投票解析表达式, 解决了长期困扰张量投票理论无法进行解析求解, 利用数值近似计算过程复杂、算法效率低、算法精度与算法效率存在矛盾的难题.仿真分析和对比实验结果表明, 利用本文算法得到的棒张量投票域、球张量投票域与传统张量投票算法得到的结果一致, 验证了本文方法的正确性; 本文方法的投票精度和投票效率均显著优于传统张量投票算法.需要特别指出的是, 本文研究方法可以进一步推广至三维乃至$\mathit{N}$维张量投票.