算法的复杂性（通用9篇）
算法的复杂性 篇1
1 引言
自然界和社会领域中的许多复杂系统都可被表述成由节点集通过边的连接而构成的网络, 例如现实世界中的互联网、新陈代谢网、食物链网、神经网络、通信与分布式网络、物流与供应链网络、产业集群网以及社会组织网络等[1,2]。近年来在对复杂网络的研究中发现它们存在一个共同的性质, 称为社团结构。它是指整个网络由若干个组或簇构成, 组内节点间的连接比较紧密, 而组间节点的连接比较松散[3]。发现网络中的社团结构并对其进行分析是了解整个网络结构、特征和功能的重要途径, 在自然科学、工程技术、经济管理和社会学研究领域中都有广泛的应用[3,4]。
谱平分法、分裂法、凝聚法和搜索法是近年来在该领域主要的四类研究方法[1,5], 而本文提出的算法兼具了谱平分法和分裂法的特征。谱平分法主要包括基于Laplace矩阵[6,7,8]、基于Normal矩阵[9]和基于电压谱[10]的方法。基于Laplace矩阵的谱平分法以网络的Laplace矩阵为研究对象, Laplace矩阵可表示为L=K-A, 其中K是对角矩阵, 其对角线上的各元素为对应节点的度, A是网络的邻接矩阵。求L的特征值与特征向量, 其中第二小特征值λ2所对应的特征向量是分割网络的依据, 该特征向量中正元素所对应的节点是一个社团, 负元素所对应的节点是另一个社团。如果要将一个网络分成两个以上的社团, 应对子社团多次重复该算法。该算法适合于网络可明显地分为两个社团的情况, 这种情况下不仅可得到满意的社团结构, 而且时间复杂度也比较低, 否则该算法就未必有效。基于Normal矩阵的谱平分法假设社团数目为g, 则网络的Normal矩阵N=K-1A有g-1个非常接近1的非平凡特征值, 而其他的特征值都与1有明显差距, 而在这g-1个特征值所对应的特征向量也有一个非常明显的特征结构:在这g-1个特征向量中, 同一社团内的节点相应的元素非常接近。以此为依据, 可将网络分割为g个社团。该算法适用于多个社团的情况, 时间复杂度与计算特征值和特征向量的方法和社团数目g相关。上述算法的时间复杂度均比基于电压谱算法的时间复杂度高, 而且本文算法与基于电压谱算法相关性较大, 故下面着重介绍该算法。
Wu和Huberman提出的基于电阻网络电压谱的快速谱分割法 (下文简称WH算法) :无向加权图G= (V, E, W) , V是节点集, E是边集, n是节点个数, m是边的条数, W=[wij]n×n是边的权值矩阵。假设G可以划分为两个社团G1和G2, 且已知节点A和B分别属于这两个社团, 初始时令节点A为源节点, 电压值为1, 而节点B为终节点, 电压值为0, 其它节点的电压值也为0, 即v1=1, v2=0, …, vn=0。将网络中的每条边都视为一个电阻Rij=w-1ij, 整个网络就可以看做一个电阻网络, 从而利用Kirchhoff定理求得各个节点的电压值。然后选取一个电压阈值v (0<v<1) , 若节点i的电压值vi>v, 则认为它属于源节点A所在的社团, 否则属于终节点B所在的社团。一般情况下, 利用Kirchhoff定理求各节点的电压, 算法时间复杂度为O (n3) 。Wu和Huberman进一步简化了算法, 按照式 (1) 运算, 只需迭代一定次数, 使电压谱达到一定精度, 就足够进行网络的一分为二。
社团发现的分裂方法一般是基于社会学与社会网络模型方法的。由Girvan和Newman提出的GN算法是一种典型的分裂方法, 它的基本思想是通过不断地从网络中移除介数最大的边来达到划分网络的目的[3];而Radicchi等则是利用边聚类系数代替GN算法中的边介数来作为发现社团结构的依据[11];Tsuchiura等引入了布朗微粒来衡量网络中两个节点之间的“距离”[12], Zhou基于这种距离矩阵, 引入了相异性指数来表示两个最相邻节点属于同一个社团的可能性大小[13,14];Fortunato等提出了一种利用信息中心度来划分网络的算法[15];Sales-Pardo等提出了一种自上而下划分且可以区分出不同社团特性网络的分裂算法[16]。以上算法均可得到层次结构的社团结构, 但是它们也有各自的局限, 如GN算法的边介数计算的时间复杂度较高, 又需反复计算, 总时间复杂度为O (m2n) ;Radicchi的算法则在很大程度上依赖于网络中存在的三角形的数目;基于相异性的算法需重复计算距离矩阵和相邻节点的相异性指数, 基于信息中心度的算法同样要反复计算移除每条边后造成的信息有效率减小的相对量。此外, 值得提出的是其他类型的社团发现方法如:Blondel等提出的能够探测到层次化社团结构的凝聚算法BGLL[17]、高学东等研究的基于共享最近邻的社团结构探测算法[18]、段晓东等给出的节点权重计算函数及在此基础上的多社团网络结构划分算法[19]等进一步拓展了该领域的研究。
本文在分析上述算法优缺点的基础上, 提出一种网络社团结构快速划分算法, 算法借鉴电阻网络电压谱和分裂法的思想, 在经过简单的迭代过程之后, 能够找到使网络能够一分为二的最大分割位, 经过一定数量的二分过程, 从而达到自然分割为层次社团结构的目的。
2 社团发现的快速划分算法
2.1 “扩散距离”与算法思路
针对WH算法的限制条件, 本文算法不需预先知道网络社团数目, 也不需要预先设定源节点和终节点, 而是在初始时赋给每个节点随机数;迭代过程中每一步对所有节点做加权平均运算, 即所有节点都运算公式 (1) ;然后用相邻节点差值的绝对值代表每条边的“扩散距离” (类似于WH算法中的电位差) ;在迭代过程中, 虽然网络中的所有节点的值都会逐渐趋近于某个固定数值, 但是由于网络中节点连接的疏密, 社团内部节点的数值会相对聚集在一起, 而社团之间的节点的数值则会差距相对较大, 这就是本文划分社团的基础。
WH算法是通过计算节点电压, 然后利用电位差来分割网络的, 而本文算法是利用扩散或传播的概念来划分网络的, WH算法中源节点和终节点的数值 (电压) 是固定不变的, 本文算法中所有节点的数值都在变化, 这个变化其实是不断的扩散或传播过程, 虽然最终所有节点都会趋于一致, 但是在这个过程中, 连接紧密的节点间的差异明显小于连接松散的节点间的差异, 这个节点差异其实就是上述边的“扩散距离”, 在迭代一定次数后, 网络中节点之间的“扩散距离”虽然还在变小, 但它们之间的比例关系趋于稳定 (在下文中讨论迭代次数问题) , 那么通过切断一组平均“扩散距离”最大的边, 即可二分网络得到两个社团。该组边需满足的条件是:①组中每条边连接的两个节点分别属于分割后的两个子网络, ②连接两个子网络的所有边都包含在该组中, ③该组边的“扩散距离”之和与该组边的权值之和的比值是最大的。显然, 寻找该组边是一个NP问题, 为快速求解, 可通过线性的方法得到最优解或近似最优解:将扩散后节点的值从小到大排列得到一个序列, 如果从此序列中某节点处将网络一分为二 (此节点前的所有节点属于子网络1 (包括此节点) , 此节点后的所有节点属于子网络2) , 将切断所有连接两个子网络的边, 那么依次从序列中做此假设切割, 计算所对应的每组边的“扩散距离”之和, 然后再除以每组边权值之和得到每个均值, 其中最大的均值所对应的就是“扩散距离”最大的那组边。如网络存在多个社团, 继续二分网络即可, 当满足算法终止条件时, 即完成了划分网络社团的任务。
2.2 模块度函数
所有的网络社团结构划分算法都需要一个评价准则, 来判断划分得到的社团结构的合理性和有效性。因此Newman和Girvan定义了一个用以评价网络划分满意度的指标, 称为模块度[20,21,22] (Modularity) 。模块度函数定义为
本文使用模块度函数Q来衡量社团划分的结果, 在网络逐渐分裂的过程中, Q值会逐渐增加, 当划分为kmax个社团时将达到峰值, 之后开始减少, 那么算法的终止条件就是当Q值减小时算法停止。
2.3 算法描述
本文算法是一种社团划分的分割算法, 在WH算法的基础上提出了对所有节点都运行式 (1) , 在迭代过程中, 切断平均“扩散距离”最大的组边, 达到快速分割成为社团的目的。采用模块度函数作为衡量最佳社团结构的标准, 即通过模块度函数确定最佳的社团数目。具体算法如下:
Input: 复杂网络G= (V, E, W) , 社团数目s=1, 确定“扩散距离”最大边或组所需的累计数j;
Output: 社团划分结果Pkmax;
Step1: 对每个节点赋随机数Vi=random, i=1, …, n;
Step2: 对每个节点计算:
Step5: 如果最近j次循环中的gmax不同, 转到Step2;
Step6: 将节点的值Vi从小到大排列得到一个序列, 依次从序列中每个节点处做假设分割 (将网络一分为二) , 计算所需切断的每组边的“扩散距离”之和, 然后再除以每组边权值之和得到每个均值:
Step8: 按照式 (3) 计算模块度Q, 如大于上次的模块度, 转到Step1, 如小于, 上次的模块度即为最大模块度, 其所对应的社团结构Pkmax是最佳社团结构划分, 算法终止。
2.4 时间复杂度分析
从算法描述中可以看出, Step1赋随机数的时间复杂度为O (n) ;Step2、Step3、Step4和Step6是以边为核心的运算, 时间复杂度为O (m) ;要找到平均“扩散距离”最大组边所需的循环次数, 需要所有节点的数值扩散到比较平均的程度, 这明显取决于网络的平均路径长度L;算法最终的平分次数在最差情况下是m-1, 但在一般情况下, 切断边的条数与网络节点数和边数目无关。所以算法在最差情况下的时间复杂度是O (Lm2) , 需要指出的是WH算法在二分网络时的时间复杂度应是O (Lm) , 而其在划分多社团的最差情况下与本文算法的时间复杂度是一样的, 因为计算节点电压的过程实际上也是一个扩散过程, 那么也是取决于网络的平均路径长度L的。当网络是稀疏网络时, m～n, L～m, 算法的时间复杂度是O (n3) , 比其它谱平分算法的时间复杂度低;当边数目远大于节点数时, 即m≫n时, 平均路径长度将远小于边数目, 即L≪m, 而且最终切断边的条数一般来说是远小于m的, 那么算法的时间复杂度就约等于O (m) 。可见, 本文算法在边数目远大于节点数的情况下, 比其它谱平分算法有较大的优势, 而且时间复杂度对于网络的规模是不敏感的, 而且对于社团结构较强的网络往往很快就分裂成几个独立的部分, 这样就大大减小了后续的计算量。
2.5 “扩散距离”的收敛性
本文算法的前提是“扩散距离”必须收敛于0, 即网络中所有节点均无限趋近于某个实数, 显然, 只有在满足这个前提的基础上才能计算并分割网络。算法中的基本迭代运算公式 (4) 用矩阵形式来描述:Vt+1=K-1WVt=NVt=NtV1, t=1, 2, … (7) 其中, Vt= (v1t, v2t, …, vnt) T是t-1次迭代后节点值组成的向量, N=K-1W是网络的Normal矩阵, K是对角矩阵, 其对角线上的各元素
根据随机矩阵的定义[23]:矩阵的每行的元素和等于1, 可知N是一个随机矩阵。
由于要划分的网络是连通网络 (连通网络才有化分社团的必要) , 所以矩阵N是不可约的;而对于有向网络, 矩阵是不可约的当且仅当矩阵对应的网络为强连通网络。
而且要划分的网络不应该是简单的规则网络, 那么N的循环指标应为1, 即模等于1的N的特征值的个数为1, 根据素矩阵和循环矩阵的定义, 可知N是素矩阵, 不是循环矩阵。
矩阵N是不可约的随机矩阵, 则
且由于N是非负素矩阵, 则
综上,
3 实验
本文算法是在Matlab软件平台中实现的, 实验所用网络为空手道俱乐部网络和美国大学橄榄球联盟网络, 数据来自M.E.J.Newman教授的网站。
3.1 空手道俱乐部网络
Zachary网络是社会网络分析的一个经典问题。20世纪70年代初期, Zachary用了两年的时间来观察美国一所大学中的空手道俱乐部成员间的相互社会关系, 从而构造了该网络。该俱乐部的主管与校长之间殷某些问题而产生了争执, 结果该俱乐部分裂成了两个分别以主管和校长为核心的小俱乐部。图1中的节点1和节点33分别代表了俱乐部主管和校长, 而左侧的18个节点和右侧的16个节点分别代表了分裂后的小俱乐部中的各个成员。其中节点3是有歧义的, 与两边的连接数都是5, 谱平分算法和GN算法将节点3划入左边的社团, 本文算法也将节点3划入左边的社团。Zachary网络可进一步分裂, 得到6个社团的结果如图1所示, 其中在分裂为三个社团时Q值达到最大, 即在右边社团分裂出节点5、6、7、11和17所构成的社团时Q值最大。网络的层次结构在逐步的分裂过程中很清楚地展现出来, 如图2所示, 其中左图是社团数逐渐增加时模块度Q的变化情况, 右图为划分的层次结构图, 左右图是相对应的。
3.2 美国大学橄榄球联盟网络
本文实验研究的第二个网络是美国大学橄榄球联盟, 网络中115个节点表示115支球队, 而613条边代表了613场赛事。这些球队被分成若干小组, 每个小组由8～12支球队组成, 同组内球队之间的比赛要比组间球队之间的比赛多。
应用本文算法得到的模块度最大时的社团结构如图3所示, 此时社团数为12, Q=0.54。图4是随着分裂得到的社团数目的增加, 模块度值的变化情况, 从图中可知, 在整个网络逐渐分裂的过程中模块度值不断变大, 但到了峰值 (k=12) 以后, Q值开始变小。按大学所处的地理位置 (12个地区) 划分时Q=0.48, 根据GN算法得到的社团结构与图3基本一致, 模块度也是0.54, 唯一的区别在于节点37所属的社区不同。
分别利用GN算法、FCM算法、WH算法和本文两种算法计算美国大学橄榄球联盟网络, 所得的结果如表1所示。
4 结论
分裂算法和谱平分算法是复杂网络中社团结构划分的两类重要方法。本文借鉴电压谱分割算法的思想, 提出了复杂网络社团发现的快速平分方法。算法通过分割平均“扩散距离”最大的一组边来平分网络, 同时算法以模块度函数作为评价标准得到最佳的社团结构;本文给出了算法时间复杂度的分析, 表明算法不仅对稀疏网络能够快速运算, 对非稀疏网络更能高效求解, 体现出算法具有较高的健壮性;又进一步从矩阵论和图论基础上说明了“扩散距离”是收敛的, 从而证明了算法的可行性。与已有的社团发现谱平分算法和分裂算法相比, 本文算法不需要事先给定社团数目, 时间复杂度较低, 划分社团的准确率高, 能够在结构未知的大型网络中得到高质量的社团结构。
算法的复杂性 篇2
复杂网络是 20 世纪兴起的复杂系统研究的一个分支领域，近来关于复杂网络的研究已经涉及到计算机、社会学以及经济学等各个领域。虽然复杂网络目前还没有精确的定义，但因为复杂网络子系统的各个组成部分之间都具备一定的关联性，所以从图论的观点来看，可以将复杂网络看作是一个由点集 V(G)和边集 E(G)构成的一个图 G(V，E)。多数的复杂网络都有如下特征：
(1)统计性。复杂网络的节点个数都很多，大规模性的网络行为一般都具有统计特性。
(2)稀疏性。具有 M 个节点的网络连接数目的复杂度为O(M2)，但实际上网络的连接数目通常为 O(M)。
(3)时空演化的复杂性。复杂网络会随着时间和空间的推移而进行演化，而且这种演化行为表现出一定的复杂性。
衡量复杂网络有不同的指标，分别是平均路径长度、聚类系数和连通度分布。假设复杂网络中任意两个节点的距离指的是这两个节点间最短路径所包含的向量边的数目，那么平均路径长度(average dis—tance) 就可以理解成复杂网络中所有节点的距离的平均值，它反映了复杂网络节点之间的通信链路的长短。假设复杂网络内一个节点 n 连接到其他 m 个节点存在的最大向量边为 t，而且这 m 个节点间存在的向量边为 e，那么节点 n 的聚类系数(cluster coeffi—cient)可以理解为 e 与 t 的比值。复杂网络的聚类系数是所有节点的聚类系数之和，与节点总数的比值。复杂网络中一个节点的连通度指的是和此节点相连的向量边的数目;假设从复杂网络中任意选择一个节点，连通度为 k 的概率为 P，那么函数 P(k)就是复杂网络的连通度分布。
复杂网络的安全域并不是完全独立的，而是存在一定的包含或交叉关系。
2 GABP 算法的引入
神经网络技术应用以来，在复杂性系统的研究中起着越来越重要的作用，BP 神经网络是使用最广泛的一种神经网络技术，主要包括输入层、输出层和若干隐含层。基于图论观点的复杂网络可以看作是多维节点到多维节点的映射，而这种映射关系都可以用一个三层的 BP 网络来实现。
算法的复杂性 篇3
关键词 沪深300股票指数；复杂度；kolmogorov熵；样本熵；模糊熵
中图分类号 F830 文献标识码 A
AbstractThis paper studied the high frequency data of the CSI 300 index， and examined the efficiency of complexity measures such as Kolmogorov entropy， sample entropy and fuzzy entropy in high frequency environment. By using the effective measurement， it compared the changing process and range of the complexity both before and after the subprime crisis. The results show that， compared with the Kolmogorov entropy based on the compatible method and sample entropy， fuzzy entropy is more suitable for measuring the CSI300 index's complexity， which has the lower sensitivity to the similar tolerance and the better continuity of measure value. The CSI 300 index's complexity is rising during the sample interval. However， the complexity during the crisis is far more less than the two other stages， and the complexity after the crisis is higher than that before the crisis. Compared with the developed markets and even some emerging markets， the CSI 300 index's complexity is much lower.
Key wordsthe CSI 300 index； complexity； Kolmogorov entropy； sample entropy； fuzzy entropy
1问题提出与相关文献回顾
根据混沌理论，复杂度被定义为非线性动力系统或序列的复杂性程度[1].其大动态范围、短平稳性和小数据量的特征被认为是最适于分析非线性系统的动力学特征参数，也是非线性动力系统研究的重要方面[2].沪深300股票指数是联系我国股票现货市场与股指期货市场之间的重要桥梁，金融机构往往需在日内动态调整资产头寸并关注风险管理，因此，沪深300股票指数高频数据的复杂性程度对于风险管理和交易策略实施均具有重要意义.在我国市场环境下，有效地复杂度测算方法是什么？与成熟市场和周边的新兴市场相比，我国沪深300股票指数的复杂度如何？围绕次贷危机的影响，不同时间阶段其复杂度的变化幅度与变化过程如何？既有研究尚未对上述系列重要问题做出较为全面地解答，同时学术界和实务界对采用何种方法来进行复杂度测算亦尚未达成共识.
早期文献表明，关于混沌序列复杂度的研究始于20世纪60年代.西方学者提出了各种相关测度指标与方法，但成果主要集中于工程计算领域.随着金融市场非线性动力学行为与混沌效应的存在性逐渐得到实证，关于股价波动复杂度的测算研究成为热点，但方法局限于围绕分形维数的测算，研究结论也在多重分形错觉方面存在较大争议[3，4].
近年来，学者们运用不同类型的熵模型展开了复杂度测算研究，主要包括柯尔莫哥洛夫熵（kolmogorov）、近似熵（ApEn）、样本熵（SampEn）和模糊熵（FuzzyEn）算法.kolmogorov（1965）将复杂度界定为能够产生某一（0，1）序列所需的最短程序的比特数，并形成Kolmogorov熵算法.Lempel和Ziv（1976）给出了其在计算机中实现的具体算法.对此，肖辉，吴冲锋，吴文峰，等（2002）将之应用于中国股票市场检测，计算了沪市综合指数与深市成份指数的复杂度[5].尽管该算法有着严格的数学理论基础和依据，但因需将给定时间序列转换成符号序列，使得转换方法成为该算法在股价波动复杂度测算应用时的关键.然而，均值法、极值法和遗传密码法三种主要转换方法均未考虑序列整体性质，亦不能区分弱混沌与周期序列，以及强混沌与随机序列（Abuasad， ect.， 2012）[6].综合法（He，Xu，2000）为解决上述问题，按不同时间序列分别应用均值法和极值法，但受限于需事先明确知道时间序列性质（赵波等，2014）.对此，王福来和达庆利（2007）提出了基于兼容法的Kolmogorov熵算法并应用于上证综合指数日收盘价序列复杂度测算[7]，为Kolmogorov熵算法缺陷问题的解决提供了新视角.
由于近似熵算法（Pincus，1995）采用Heaviside函数进行相似性量度，敏感于阀值和相空间维数，从而参数选取会使其计算精度带有经验性（蔡觉平，李赞，宋文涛，2003）.样本熵算法通过不计算自身匹配的统计量，对其形成了改进，但在无模板匹配的情况下可能出现ln0的无意义结果（贺少波，尹林子，阿地力·多力坤，2012）.对此，学术界相继提出了多种改进方法.肖方红，阎桂荣和韩宇航（2004）将混沌伪随机序列看成符号序列，提出符号熵算法.虽然该算法不涉及参数的选取，计算比近似熵算法更为简单，但符号熵算法需预先知道符号空间，且只针对伪随机序列，应用范围局限性较大.Chen（2011）在对样本熵（SampEn）进行改进基础上提出模糊熵（FuzzyEn）算法，并基于TDERCS系统成功检验了其有效性（贺少波，尹林子，阿地力·多力坤，2012）[8].模拟显示，基于模糊熵的复杂度测算方法可能在对参数依赖的敏感性方面更低，测度值的连续性更好，从而获得更高的测度效率（李鹏，等，2013）[9].
文章的创新之处在于：1）不仅较为全面的对比了各种基于熵算法的复杂度模型测算效率，而且进行了小样本修正，以期为沪深300股票指数复杂度测算提供可靠的实证依据与分析结论.2）围绕次贷危机的影响分阶段研究和比较了危机前、中、后期序列复杂度的变化过程与变化幅度，并与发达市场乃至周边新兴市场股指期货标的指数的复杂度相较，得到我国沪深300股票指数复杂度的演化规律与独特性质.
2代表性熵算法、有限样本修正
与测算效率评价标准
通过对相关研究成果的梳理可知，对既有测算效率形成一定改进后的代表性熵算法主要集中为基于兼容法的Kolmogorov熵、样本熵和模糊熵.重构相空间维数m、相似容限度r和序列长度N是测算过程中的共同关键变量.如模糊熵：
当时间长度足够长时，MFDFA方法计算得到的h（q）是较准确的，但在实际应用中，序列长度很难满足要求，此时有限样本会使h（q）的计算产生偏误，进而也会使关联维数以及熵计算中的相空间维数m产生偏误，因此需要对MFDFA中的有限样本效应进行修正，以提升测算和评价结果的准确性.修正方法基本思路为：利用Liu（2007）和吴栩等（2014）对马尔科夫转换多重分形模型（MSM）的解析，构造能够尽可能反映原始股指序列多重分形特征的模拟序列，该模拟序列的长度应该足够的长，从而可以消除MFDFA计算中的有限样本效应.
在测算复杂度的过程中，对模型效率的评价标准主要集中于算法本身的稳定性和结果对模型参数的依赖程度，即，算法鲁棒性，对相空间维数、相似容限度和时间序列长度的敏感性和依赖性，以及测度结果的连续性[11].由于是对我国沪深300股票指数运动的复杂度进行测算，而复杂度的标准值尚未知，不同于在某些性质既定和已知正确结果的复杂系统下对研究方法的评价，因此，通过算法鲁棒性来评价模型效率的路径尚不能行通.在熵算法模型中股指序列长度N既定，相空间维数m通过计算获得，测度值对参数的敏感性和依赖性，以及结果的连续性主要与相似容限度r密切相关[12].因此可以认为，当在相似容限度的经验取值范围内，某一算法未出现错误度量值，其测度结果趋于稳定且图像相对平滑，则该算法对相似容限度的敏感性和依赖性较低，测度效率相对较高.
3数据说明与采样频率筛选
以2005年5月9日至2013年12月31日沪深300股票指数1分钟、5分钟、10分钟、15分钟和60分钟高频数据
选择了相关研究中主要出现的若干种高频频率作为筛选对象.作为基础研究样本.数据来源为Reset数据库.虽然我国沪深300股票指数于2005年4月8日上市，但考虑到上市之初，市场各方对该指数存在熟悉过程[13]，为准确起见，在数据选取时剔除掉了2005年4月的交易数据.
直接采用股票指数而未如传统证券市场定量分析采用收益率数据 在有关证券市场的定量分析中通常使用收益率样本而不是指数本身，主要是考虑到价格序列的相关性违反以高斯假设和正态分布为基础的线性分析框架原则.，主要缘于文章的复杂性研究视角，避免收益率变量可能对系统非线性相依结构所形成的破坏.
沪深300股票指数1分钟、5分钟、10分钟、15分钟和60分钟高频数据的描述性统计结果如表1所示， 其中IF1、IF5、IF10、IF15和IF60依次对应不同采样频率.统计结果显示，各种不同采样频率的高频数据都表现出有偏和尖峰厚尾的统计特征，且明显超出了正态分布假定的范围（JarqueBera统计量显著） .因此，可以认为各序列明显具有非线性特质.
鉴于不同采样频率可能会带来不同检验结果，在进行复杂度测算之前需要进行有效采样频率甄别.由既有熵测算方法可知，相空间维数是各熵算法中的关键变量.较窄的多重分形度置信区间对应较精确的维数.因此，遵从多重分形度置信区间计算方法，以对多重分形度置信区间宽度的比较筛选有效高频采样频率，比较结果如表2所示.
根据表2结果可知：各采样频率下经有限样本效应修正后的多重分形度均仍接近于1，我国沪深300股票指数运行具有多重分形特征；置信区间宽度随采样间隔的增加而变化，其中当间隔为5分钟时宽度最窄.从而，沪深300股票指数5分钟高频数据为进行复杂度测算的有效采样频率数据.
为方便与发达市场和周边新兴市场的股指期货标的指数复杂度的对比，文章还选择了标准普尔500指数、日经225指数和韩国指数2005年5月9日至2013年12月31日的5分钟高频数据，作为第四部分对比分析中的研究数据.
4沪深300股票指数高频数据复杂度的
熵测算实证结果与分析
由于涉及了三种熵算法模型，且模型中至少涉及了三种关键参数，为了清晰起见，此处不逐一报告参数的估计结果，而是直接展示对应熵算法下的复杂度结果，及其随关键参数值改变而变化的过程，并进一步进行模型测算效率评价.
4.1关键参数值的确定
由熵算法步骤可知，重构相空间维数m、相似容限度r和序列长度N是测算过程中的关键变量，需要对其进行准确数值确定.
在上述三变量中，时间序列长度N由给定样本区间决定.经筛选，研究中的基础样本为2005年5月9日至2013年12月31日的沪深300股票指数5分钟高频数据，时间序列总长度N= 689 330.
相似容限度r属于熵算法模型中的阀值变量，其值过小会增加结果对噪声的敏感性，过大则会导致信息丢失，根据Chen（2009）的模拟建议，r的取值一般可在[0.3，0.35]中选取.
对相空间维数m的选取，相关研究通常使用经验值.由于尽管较大的m能细致重构系统的动态演化过程，但亦会陡增运算量，m取值通常为2、3、4、5和6.为了更为准确衡量指数复杂度，可以基于所提出的有限样本修正方法计算获取合理m值.依第二部分中的修正算法得到测算后的适宜m值为3
鉴于篇幅有限，小样本修正的计算步骤在此不作列示，仅给出最后结果.有兴趣的读者可与作者联系..
4.2全样本区间内的测算结果与模型测算效
率比较
基于兼容法的Kolmogorov熵算法的计算结果显示，全样本区间内我国沪深300股票指数的复杂度为1.057 1，超出了该算法复杂度值的（0，1）值域.考虑到全样本区间可能因数据存在结构突变而导致虚假统计结果，运用计算程序每次取其连续的1 000个数据在有限样本效应修正下进行分析，然后取其均值作为序列平均复杂度.结果显示，平均复杂度为1.049 9，依然超出了Kolmogorov熵算法复杂度的值域范围.说明基于兼容法的Kolmogorov熵算法并不适用于对我国沪深300股票指数复杂度的测算
其原因可能缘于该算法在序列复杂度接近于1时分辨率不高.但整体结果与分段后均值结果均超出了值域范围，已经说明该方法失效.文章并不旨在分析该方法失效的原因，因此不再对此进行深入说明..
图1（a）、（b）依次显示的是样本熵和模糊熵两种算法对复杂度的估计结果.虽然相似容限度r的经验值取范围为[0.3，0.35]，但为了更便于分析研究方法的效率，在编写程序过程中令r从0到0.5以0.001等间距变化
以0.001的间距变化趋近连续变化.，并对应计算复杂度值，以观察结果的连续性及其对参数变化的敏感程度.从图1（a）（b）中可以看出，样本熵和模糊熵算法均测出了复杂度计算结果，且计算结果整体比较接近.复杂度值均随r的增大而减小，当r取值为[0.3，0.35]时，其所估计的沪深300股票指数复杂度值相对其他区间内的复杂度值平稳，数值在0.55到0.43之间（如图1（a）和（b）中的虚线区域部分）.
相似容限度（a）样本熵算法下沪深300股票指数复杂度的估计结果
相似容限度（b）模糊熵算法下沪深300股票指数复杂度的估计结果
在测度结果的连续性与对参数的敏感性方面，样本熵测度结果在r的整个取值范围[0，0.5]内出现多个跳跃点，且在[0.3，0.35]范围内的跳跃点明显多于模糊熵（如图1（a）中的虚线区域部分），说明模糊熵算法相对于样本熵算法对相似容忍度的敏感性更低，测度值的连续性更高.有限样本效应修正后，当r取[0.3，0.35]时，模糊熵算法下的复杂度均值为0.494 9.
4.3不同时段沪深300股票指数复杂度结果
比较
为进一步刻画我国沪深300股票指数复杂度，在对测算方法评估后，本部分基于模糊熵算法，对全样本区间内不同时段复杂度进行测算比较.
从2005年5月9日至2013年12月31日的全样本区间可划分为2005年5月9日到2007年9月30日的指数高速攀升阶段，2007年10月8日到2009年3月31日的危机阶段和2009年4月1日到2013年12月31日的后危机阶段（其涵盖了我国股指期货从2010年4月16日推出并运行至今的阶段）三个阶段.各阶段复杂度值如表3所示.
虽然各阶段时间序列长度不尽相同，但由于模糊熵算法优于样本熵和Kolmogorov熵复杂度算法，且当N值在10 000左右时，模糊熵算法本身具有对时间序列长度较高的一致性，经有限样本效应修正后此种一致性效果会进一步增强.因此，分阶段后时间序列长度的不一致并不会对分阶段研究的计算结果形成显著影响.
如表3所示，各阶段复杂度测算结果表明，在危机前中国股市的集中上涨时段，指数复杂度为0.462 3；指数受危机冲击而大幅下挫阶段的复杂度为0.427 1；后危机时代的指数复杂度为0.510 2.其说明我国沪深300股票指数复杂度以后危机时代阶段为最高，受危机冲击阶段为最低.
美国次贷危机前我国股票指数运行表现为整体性快速上涨，受危机影响阶段表现为指数整体大幅下挫，两阶段股指运行均呈现出较强规律性，其市场投资者行为较单一，符合规律性序列复杂度较低的复杂度数值性质.而指数下跌阶段复杂度低于上涨阶段复杂度，则提示出沪深300股票指数在下跌阶段趋势性更强.这一点与股指波动非对称性（陈浪南，黄杰鲲，2002；陆贤伟，董大勇，纪春霞，2009；顾锋娟，金德环2013）特征一致.指数在后危机时代复杂度得到提升，说明危机冲击及相关股市政策改革后，我国沪深300股票指数运行的单一趋势性有所转化，投资者行为多样性得到补充；同时，在后危机阶段我国股指期货正式推出运行，也说明股指期货的推出对打破股票市场运行单一趋势性与修正波动时间一定程度上发挥了作用.
4.4不同市场股指期货标的指数复杂度比较
为了便于与发达市场和周边新兴市场的股指期货标的指数复杂度进行对比，此处选择了标准普尔500指数、日经225指数和韩国指数2005年5月9日至2013年12月31日的5分钟高频数据作为对比样本.基于模糊熵算法，全样本区间内发达市场和周边新兴市场的股指期货标的指数复杂度测算结果如表4所示；2009年4月1日到2013年12月1日的后危机阶段的复杂度测算结果如表5所示.
通过对比各个不同股票市场的复杂度，不难发现，无论是全样本区间还是后危机阶段，发达股票市场的复杂度均大于我国股票市场的复杂度；其中，我国沪深300股票指数复杂度以与标准普尔500指数复杂度差距为最大，与韩国指数复杂度最为接近；而在后危机阶段，我国沪深300股票指数运行的复杂度较其他国家股指期货标的指数复杂度的差距均有所减小.说明，我国沪深300股票指数相对于代表性发达市场和周边新兴市场股指期货标的指数的可预测性更明显，潜在的市场投机性更大；而随着我国股票市场相关监督和运作体系的完善以及股指期货的推出，市场逐渐成熟，可预测性有所降低，投机性正在逐渐被削减.
5结论
文章对我国沪深300股票指数高频数据复杂度测算方法及复杂度特征进行了研究.通过运用3种新兴主流熵算法以及有限样本效应的修正，研究了3种算法对沪深300股票指数复杂度测算适用性以及不同时段和不同市场对比下我国沪深300股票指数复杂度变化和差异.
主要实证结果显示： 第一，在日内高频数据环境下，与基于兼容法的kolmogorov熵和样本熵算法相比，模糊熵算法是一种更适用于研究我国沪深300股票指数的有效的复杂度测算方法.其对相似容忍度参数的敏感性更低，测度结果的连续性更好.第二，随着时间的推移，我国沪深300股票指数序列复杂度整体呈上升趋势.但危机中阶段指数序列的复杂度远小于危机前后两阶段的复杂度，后危机阶段复杂度高于危机前阶段复杂度；相较于危机中阶段，后危机阶段复杂度的上升速度较快.第三，相较于发达市场甚至周边新兴市场股指期货标的指数，我国沪深300股票指数的复杂度呈现偏低结果.
针对实证研究的政策建议如下：
第一，鉴于虽然在后危机阶段（包括股指期货的推出）我国沪深300股票指数复杂度得到了快速上升，但与其他市场股指期货标的指数运行情况相比仍然偏低.而比较公认的观点是，偏低的复杂度对应市场投资者行为多样性不足，市场运行的不可预测性较弱.因此，为了稳定沪深300股票指数运动，减少较多一致性投机行为，增加机构投资者参与数量，提高预测难度.
第二，由于多种类型机构投资者可以丰富不同环境下期货与现货指数市场的投资行为，并对市场稳定起到积极作用从而提升市场复杂度（魏宇，赖晓东，余江，2013），目前我国还需转变机构投资者投资策略，避免一致性追涨杀跌，引导机构投资者端正投资理念，发挥其在股票市场中的稳定作用.
第三，由于实证结果表明，在日内高频环境下，模糊熵算法具有更好的适用性.因此，在监测沪深300股票指数复杂度时可采用该方法进行测算，以便获得更为准确的结果.基于兼容法的kolmogorov熵算法虽然较基础性kolmogorov熵算法形成了改进，但分析结果也表明了其对我国沪深300股票指数的不适用性.虽然在研究过程中还可对其形成进一步改进，但其计算过程相较于模糊熵算法的繁琐性也是明显的.因此，如果考虑到运算成本和使用难度等问题，模糊熵算法是监测我国沪深300股票指数复杂度的不错选择.
参考文献
[1]张林，李荣钧，刘小龙. 基于小波领袖多重分形分析法的股市有效性及风险检测[J]. 中国管理科学，2014，22（6）：17-26.
[2]陈小军，李赞，白宝明，等. 一种确定混沌伪随机序列复杂度的模糊关系熵测度[J]. 物理学报，2011，60（6）：064215.
[3]魏宇，赖晓东，余江.沪深300股指期货日内避险模型及效率研究[J].管理科学学报，2013，16（3）：29-40.
[4]周炜星.上证指数高频数据的多重分形错觉[J].管理科学学报，2010，13（3） ：81-86.
[5]肖辉，吴冲锋，吴文峰，等.复杂性度量法在股票市场中的应用[J].系统工程理论与实践，2002，11（3）：190-197.
[6]A ABUASAD，M I ALSMADI. Evaluating the correlation between software defect and design couping metrics[C]//2012 International Conference on Computer Information and Telecommunication Systems（CITS）. Washington DC： IEEE Computer，2012：1-5.
[7]王福来，达庆利.Co复杂度的改进及其在证券市场中的应用[J].数学的实践与认识，2007，37（8）：20-25.
[8]贺少波，尹林子，阿地力·多力坤.模糊熵算法在混沌序列复杂度分析中的应用[J].物理学报，2012，61（13）：130507.
[9]李鹏，刘澄玉，李丽萍，等.多尺度多变量模糊熵分析[J] .物理学报，2013，62（12）：120512.
[10]J KANTELHARDT，S ZSCHIEGNER. Multifractal detrended fluctuation analysis of nonstationary time series[J]. Physica A，2004（2）：49-83.
[11]I SOROKIN. Comparing files using structural entropy[J]. Journal in Comuter Virology， 2011， 7（4）：259-265.
[12]Ruipeng LIU， T D MATTEO， L THOMAS. True and apparent scaling： The proximity of the Markovswitching multifractal model to longrange dependence[J]. Physica A： Statistical Mechanics and its Applications，2007，383（1）：35-42.
算法的复杂性 篇4
现在最为流行的无疑是双帧和三帧以及背景差分和光流算法这几种,这几种方法不是彼此之间相互独立的,而是可以相互之间进行变换和融合的。所谓的移动目标跟踪就是要创建一个以移动目标为对象的实时移动的数据模型来进行实时的跟踪计算。采用一种好的算法能够很大程度上保证最后得到的移动目标的计算跟踪结果更加精确和精准。这一算法将在以后的时间中一样被人们所热爱和研究,因为这些算法还有很大的提升空间来进行改进和创新。
1 运动目标跟踪的原理
运动目标跟踪是根据每一个移动的物体在每一个画面像素之间的序列位置来进行的移动目标的跟踪计算处理分析。那么随着社会科学技术的进步,对于这一方法出现了很多种的方法来进行移动目标的跟踪计算分析处理。那么主要的就是有下面的几种来进行我们的移动目标的跟踪计算分析结果处理。本文主要列举了几个简单具有明显特征的方法来进行移动目标跟踪信息的分析与计算处理。
1.1针对区域的跟踪
针对于某一个区域进行的移动目标的跟踪计算分析的主要中心思想是:首先把得到的捕捉的图像进行加工分割处理划分为一个个包含有有用信息的一些压缩包的模式板块,然后设定一个标准的量来进行模块的选取,在原油的图像目标中进行有用信息的收集处理。那么因为开始在进行额分割处理以后的一些小的模块中含有大量的完整的信息,所以在移动目标能够看见前,这一方法能够达到很高的精确度来进行移动目标的跟踪和计算分析。并且具有跟踪性能十分稳定等特点。但是主要缺点还是过于耗费时间,尤其是在一些较大的区域进行这种方法时,耗费的时间一般都较长。所以这一方法在进行区域性搜索时一般是运用于区域性较小的地方,或者是阴暗对比较差的区域来进行的。
1.2 针对于特征的跟踪
针对于某一个特征的跟踪计算分析处理的中心思想是:首先对于一个目标的某一个局部特点进行提取记录,然后再用计算机配对法里斯进行图像信息的对比,最后达到跟踪移动目标的目的。这一方法主要的优点就是即使被捕捉的目标某一个地方被掩盖,也能够通过局部特征法来进行跟踪分析计算,从而达到跟踪目标的目的。那么这一方法一般是和卡尔曼滤波器相互进行使用,这样能够达到最好的效果,所以这一目标一般常用的场所就是在一些较为复杂的背景下进行目标的跟踪。
1.3针对于活动轮廓的跟踪
针对于活动轮廓的目标跟踪的中心思想是:运用了曲线的封闭性能来进行的移动目标的跟踪计算和分析。主要是依靠了目标特征和数学计算来进行的曲线函数的数学运用更新,达到目标跟踪的目的。这一方法自从被发明出来以后,就被大家广泛的应用到目标搜索中去,因为它具有减少清晰敏感度的优点,并且能够在移动目标被物体所压盖以后还能够自动的进行目标对象的跟踪处理。但是这一方法主要的缺点也是受开始输入数据和噪音系数的影响较大。
1.4针对于模型的跟踪
针对于模型的跟踪方法的主要的中心思想是:首先由一定的数据库来进行目标数据的建模处理,然后再经过匹配计算达到跟踪目标的目的,并且能够自动的进行数据模型库的实时更新。从而得到较为完整的具有鲜明特点的数据结构据。但是背景差分法最大的缺点就是对于环境的要求太高,尤其是光的敏感度的干扰特别严。从而更好的确定目标的信息帧数,达到更为清晰的画面的展示。帧数之间的差分法对于背景为移动画面时的移动目标的画面捕捉是最为适合的,因为帧数差分法对于移动的物体更加的敏感,或者说这一方法只适合运用到移动的物体间。人工智能判断以及自动智能控制等多种技术学科进行相互交织的领域进行的技术研究,这一技术手段被大量的运用到了社会中各个方面其中就包含有军事领域的研究或者是航空行业以及其它的视频监控领域等,在这些研究领域中对于移动目标在复杂背景下的跟踪研究取得了很大的研究成果和重要的实际意义。尤其是对于大量运动物体的移动能够提取相关的信息输入进大脑,然后进行综合计算得到有用的信息。并且能够捕捉到有用的信息以后进行下一步移动物体的预算处理。
2 运动目标检测算法分析
从复杂的背景情况中进行移动目标图像信息的获取就是我们的移动目标跟踪技术。主要分别在于摄像机和我们的移动目标之间的动静关系的确定,其中分为两种,第一种是在背景为静态时移动目标信息的获取和第二种移动背景下移动目标信息的获取。第一种就是指我们的摄像机不产生移动,在整个的拍摄过程中保持静止的状态来进行拍摄。第二种就是我们的摄像机在拍摄时发生了平移或者是旋转等方向的移动而进行的拍摄。
2.1 背景差分法
这一方法是目前为止在进行这一移动目标信息获取方面最为人们所常用的一种方法,这一背景差分法中心思想就是在得到了一个收集了的数据背景模型以后,将现有的帧数和背景模块中的帧数进行减法运算得到一个差值,那么这一差值的结果如果大于一定的标准就可以知道这一信息为移动目标的信息,如果没有大于这一标准就可以判定这一信息为我们的背景模型中的数据。利用背景差分法能够有效的进行移动目标信息的判别,从而得到较为完整的具有鲜明特点的数据结构据。
但是背景差分法最大的确定就是对于环境的要求太高,尤其是光的敏感度的干扰特别严。那么针对于这一情况我们的技术人员最主要的方法就是创造出不同的背景模型来进行移动目标的跟踪计算,这样能够最大限度的减小因为环境因素的影响从而产生的对移动目标跟踪计算出现的失误等现象。对移动目标的跟踪计算至关重要的就是对于背景模型的创立和模式选取以及背景阴影的摒弃,将在很大程度上对整个的移动目标跟踪计算的结果造成关键性的影响。这一方法对于仪器设备的要求不是太高,能够简单的实现,除了要在固定不移动的背景下进行捕捉以外,其余的性能都很好,能够做到快速的进行移动目标信息的获取,从而能够精确的进行信息的取缔。但是这一方法最大的缺陷就是对于环境的要求很苛刻,容易受到光线强弱变化的影响,而这一影响将给整个计算带来严重的偏差。
2.2 帧间差分法
这一方法主要就死利用三三两两相互靠近的帧数在连续像素中的变化,利用时间差值来进行的时间差值分化从而进行的移动目标的信息帧数获取。这一方法对于移动的帧数具有相当强硬的适应性,但是帧数差分法主要的缺陷就是不能够提出所有的移动目标的关键性像素,从而导致最后的呈像会出现一些空洞的现象。那么针对于这一重大的缺点我们的技术人员就运用了我们的对称帧数差分法来进行缺陷的修补。
这一方法主要就是在进行获取了的图像帧数中针对于每三帧数的图像信息来进行的对称差分法的修补,对称差分法主要就是运用了从上一帧数的图像信息中进行模块的切割来进行的移动目标的帧数范围的确定,这样能够得到一个较为清晰的移动目标帧数的移动范围,从而更好的确定目标的信息帧数,达到更为清晰的画面的展示。帧数之间的差分法对于背景为移动画面时的移动目标的画面捕捉是最为适合的,因为帧数差分法对于移动的物体更加的敏感,或者说这一方法只适合运用到移动的物体间。其实,帧数间差分法捕捉的主要就是相对来说是移动的物体,从而造成了捕捉到的两个画面之间的时间值很短,所以就会不容易受到外界光照等因素的影响。这也是帧数间差分法和上一方法之间最大的区别之一,帧数间差分法具有简单有效并且不容易受到外界的影响,具有效果稳定,反应速度快等特点。
2.3光流法
这一方法能够充分的用捕捉到的图像信息来进行移动目标信息的获取。运动场能就是移动在空间力矩中的表示,那么要在一个平面上表现物体的移动就是通过平面中的阴暗对比色调来进行移动物体的展示的。最后就会使得整个的运动场在画面上进行展示,这种现象我们称之为光流现象。那么光流就是指一瞬间产生的运动力场而变现的现象,其中就有一些基本的移动物体的很多信息。那么针对于光流现象我们就采用了时间变化而变化的光速效应,因为光速流中包含有大量的信息可以进行有效的利用。在理想状态下可以进行移动目标的测量,并且可以不用其余的参照物来进行参照对比。能够做到最大限度的得到移动物体的移动信息,可以运用进行背景动态运转时对于移动目标物体的跟踪计算测量。
但是这一方法主要的缺点就是对于仪器设备的要求很高,不能够第一时间的进行分析计算处理。对称差分法主要就是运用了从上一帧数的图像信息中进行模块的切割来进行的移动目标的帧数范围的确定,这样能够得到一个较为清晰的移动目标帧数的移动范围,从而更好的确定目标的信息帧数,达到更为清晰的画面的展示。帧数之间的差分法对于背景为移动画面时的移动目标的画面捕捉是最为适合的,因为帧数差分法对于移动的物体更加的敏感,或者说这一方法只适合运用到移动的物体间。
3 结束语
跟踪目标的算法现在已经有很多种,每一种的类型和方式都是不一样的,但是这些算法无一例外都是只能够针对于某一种情况或者是多种情况来进行移动目标的跟踪计算分析处理,并不能够做到所有的环境都使用一种算法的理想状态,所以这也是以后要研究和解决的地方。现在最为流行的无疑是双帧和三帧以及背景差分和光流算法这几种,这几种方法不是彼此之间相互独立的,而是可以相互之间进行变换和融合的。所谓的移动目标跟踪就是要创建一个以移动目标为对象的实时移动的数据模型来进行实时的跟踪计算。其实,帧数间差分法捕捉的主要就是相对来说是移动的物体,从而造成了捕捉到的两个画面之间的时间值很短,所以就会不容易受到外界光照等因素的影响。这也是帧数间差分法和上一方法之间最大的区别之一,帧数间差分法具有简单有效并且不容易受到外界的影响,具有效果稳定,反应速度快等特点。采用一种好的算法能够很大程度上保证最后得到的移动目标的计算跟踪结果更加精确和精准。这一算法将在以后的时间中一样被人们所热爱和研究,因为这些算法还有很大的提升空间来进行改进和创新。
摘要：在进行背景非常复杂的情况对于移动目标进行监控并进行跟踪的算法研究已经取得了突破性的进展,那么人的眼睛对于自己所处的环境能够进行感觉和捕捉作用,尤其是对于大量运动物体的移动能够提取相关的信息输入进大脑,然后进行综合计算得到有用的信息。并且能够捕捉到有用的信息以后进行下一步移动物体的预算处理。这也是本文主要研究的对于移动目标物体在复杂背景下进行移动预测研究算法的主要目的。
关键词：移动目标,跟踪算法,算法原理
参考文献
[1]施家栋,王建中.动态场景中运动目标检测与跟踪[J].北京理工大学学报,2009(10).
[2]陆军,李凤玲,姜迈.摄像机运动下的动态目标检测与跟踪[J].哈尔滨工程大学学报,2008(8).
算法的复杂性 篇5
关键词：矩阵乘法,凝聚算法,算法复杂度,对数代价
0 引言
矩阵乘法的凝聚算法首先是由蒋昌俊和吴哲辉于1989年提出文献[1], 并于1994年做了进一步改进文献[2], 在理论上完成了各种矩阵乘法的运算。然对于该算法是否能够在计算机上有效执行, 或者其运算次数的阶数真的能够达到文献[1]、[2]中所说的O (n2) 这个问题, 文献[3]首先针对文献[1]提出了质疑, 倘若如文献[1]所言, 忽略字长因素, 非负整数矩阵乘法就可归结为一次乘法运算。而后[4]指出文献[1]中忽略了大整数运算除了运算的次数这一影响因素外还需要把大整数本身的规模也要考虑进去。并对[3]进行了校正和补充, 最终得出文献[1]的运算量不低于O (n3log2n) 。后来, 文献[5]又针对改进后的凝聚算法文献[2]进行分析, 又得出文献[2]的算法复杂度依旧不低于O (n3log2n) 。文献[4]指出文献[3]中“不同字长有不同运算量”的说法的不确切性, 确切的说, “计算机上的大整数算数是多重精度算术”, [6]字长是属于计算机的概念, 而算法范畴应该说精度。因为“当我们在描述实施算法所需比特运算次数时, 我们就在描述算法的时间复杂度计算复杂性”, [6]于是文献[4]用运算比特数去衡量凝聚算法复杂度得出其不低于O (n3log2n) 。
实际上, 衡量算法的复杂度有不同的标准, 常用的有两个, 一个是统一代价标准, 例如我们平时讨论算法复杂度时只讨论算数次数或操作次数;另一个是对数代价标准, 也就是按比特运算数来计算复杂度。两者是不同的。文献[4]和文献[5]在讨论复杂度时混淆了两种复杂度代价标准, 而文献[3]中在讨论中也忽略了移位操作的复杂度, 才得出矩阵运算只需一次乘法运算的结论。
本文将区分两种代价标准, 结合文献[3]、[4]和[5]和, 重新讨论凝聚算法复杂度。
1 时间复杂度
衡量算法的一个重要标准是算法的时间复杂度, 他是输入规模的函数。算法所消耗的时间, 即算法中每条语句执行时间总和。而每条语句执行时间, 即语句的执行次数 (即频度) x语句执行一次所需时间。
1.1 两种常用代价标准
算法转换为程序后, 每条语句执行一次所需的时间取决于机器的指令性能、速度以及编译所产生的代码质量等难以确定的因素。因此, 一般要独立于机器的软、硬件系统来分析算法的时间复杂度。我们常常以RAM为计算模型, 在RAM模型下, 所采用标准一般有两种:
1) 统一代价标准:设每条语句执行一次所需时间均是单位时间, 则一个算法的时间耗费是该算法中所有语句的频度之和。此时的算法时间复杂度记作OA (f (n) ) , A表示“算术”。
2) 对数代价标准:以位操作为一个单位, 则一个算法的时间耗费是该算法的位操作数之和。此时的算法复杂度记作OB (f (n) ) , B表示“位”。
其中, 对数代价标准考虑到计算机中实际存储字的有限大小, 尤其在涉及到算数操作时, 用对数标准更现实。例如, 两个位整数相乘, 按照统一代价标准其算法复杂度为OA (1) , 而按照对数代价标准, 已经有的最好结果是Schǒnhage-Strassen整数相乘算法文献[8]:两个n位的整数相乘, 其算法复杂度是OB (mlogmloglogm) 。
1.2 时间复杂度讨论误区
一般来说, 对于整数而言, 位操作次数是考虑算法复杂度时感兴趣的。凝聚算法涉及大量的整数运算。因此, 对于凝聚算法, 我们考虑位操作更为现实。而如果比较同一问题不同的算法的复杂度时, 我们一定要统一标准, 这样才具有可比性。否则, 比较结果不具有意义。这也就是文献[4]和[5]中讨论的误区所在。
2 凝聚算法时间复杂度
下面分别讨论按数学定义和用凝聚算法计算矩阵乘积的时间复杂度。
Cnxn=AnxnBnxn, 其中Cnxn= (cij) nxn, Anxn= (aij) nxn, Bnxn= (bij) nxn
按照数学定义中的方法计算C中的元素, i=1, 2, …n, j=1, 2, …n。在本论文中, 我们称其为一般方法。
若是按照统一代价标准的话, 一般方法计算复杂度为OA (n3) , 而凝聚算法也正如文献[1]和[2]所得结论为OA (n2) 。然而, 凝聚算法中涉及到大量整数运算, 下面就仔细讨论如何按照对数标准计算凝聚算法时间复杂度。
本文首先讨论凝聚算法和一般方法按照对数代价标准如何计算时间复杂度, 而后举例反驳文献[5]中关于凝聚算法“运算量仍高于常规算法的运算量的阶”。
2.1 准备工作
定义:如果是一个整数, 则, 为方便, 我们记l (i) =size (i)
下面讨论凝聚算法[2]按对数代价标准的时间复杂度。
注解1:除矩阵的阶统一为nxn外, 其他符号同文献[2]中改进的凝聚算法。
注解2:以下在讨论时间复杂度时, 关注的是涉及到算术运算时的对数标准复杂度。
注解3:整数乘法的复杂度记作g (m) 。若采用文献[8]中的算法, 两个m位的整数相乘, 其算法复杂度是OB (mlogmloglogm) , g (m) =mlogmloglogm即。而“整数的除法需要的时间和整数乘法需要的时间只差一个常数因子”。[7]故同样两个m位的整数相除, 其算法复杂度是g (m) 。
注解5:两个位的整数相加, 其算法复杂度是OB (m) 。在文献[2]中关于凝聚算法按统一代价标准计算复杂度中可以看出, 其中加法和乘法的次数是n2的常数倍, 而在按对数代价标准计算时, 两个m位的整数相乘一次要比相加复杂度高, 所以, 下面我们讨论时更加关注于乘法时间复杂度的讨论, 加法时间复杂度我们只是带过。
2.2 凝聚算法对数代价复杂度
下面按照对数代价标准讨论凝聚算法中每步复杂度:
1) 求a=max{aij|i∈{1…n, }, j∈{1…n}}, b=max{ bij|i∈{1…n}, j∈{1…n}}
x=nab+1
分析:该步骤除了2 (n2-1) 次比较外, 两次乘法的时间复杂度为OB (g (max (1 (n) , 1 (a) ) +g (max (1 (na) , 1 (b) ) ) ) 以及一次加法OB (max (1 (nab) , 1 (1) ) 。
2) 用Horner方法计算bk=Σnj=1bkjxj-1, k=1, 2, gn
分析:这里用Horner方法计算bk, 乘法和加法都是n-1次。该方法不影响原算法的统一代价复杂度。
该方bk法=中/nj=, 1bkjxj-1, k需=1, 要2, 两gn次的乘法运算的时间复杂度为OB (g (max (1 (xj-2) , 1 (x) ) ) +g (max (1 (bkj) , 1 (xj-1) ) ) , 其中j=2, …n, 因为j=1时没有乘法运算。故bk中乘法计算复杂度为OB (Σnj=2{g (max (1 (xj-2) , 1 (x) ) ) +g (max (1 (bkj) , l (xj-1) ) ) }) , 加法计算复杂度为。则计算所有的bk, k=1, 2, …n时, 乘法复杂度OB (Σnk=1Σnj=2{g (max (1 (xj-2) , 1 (x) ) ) +g (max (1 (bkj) , l (xj-1) ) ) }) , 加法复杂度OB (Σnk=1Σnj=2 (max (1 (Σi=2j-1bk (i-1) xi-2) , l (bkjxj-1) ) ) 。
3) 计算Ci=Σnk=1aikbk, i=1, 2, gn
分析:这里Ci需要n次乘法和n-1次加法。
计算Ci乘法计算复杂度OB (Σnj=2 g (max (1 (aik) , 1 (bk) ) ) , 加法计算复杂度OB (Σnk=2max (1 (Σk-1j=1) aijbj) , 1 (aikbk) ) ) 。则计算所有的Ci, i=1, 2, …n时, 乘法的计算复杂度是OB (Σni=1Σnj=1g (max (1 (aik) , 1 (bk) ) ) , 加法的计算复杂度是OB (Σni=1Σnk=2max (1 (Σk-1j=1aijbj) , 1 (aikbk) ) )
4) 做除法i=1, 2, …n。对, 依次求商ki1, ki2, gki (n-2) 和余数Ci1, Ci2, g Ci (n-1) , 使满足Ci=ki1 x+Ci1, 0≤Ci1< x, ki (j-1) =kij x+Cij, 0≤Cij
分析:此处, 每一步辗转相除我们都分解成两种运算:一是对商取整, 得整商;一是求模运算, 得余数。例如:ki (j-1) =kijx+Cij, 整商kij=[ki (j-1) /x], 余数Cij=mod (ki (j-1) /x) 。这和[2]中讨论的每一步辗转相除有一次除法、一次乘法和一次减法从按照统一代价标准计算复杂度的阶上没有影响。
为了统一标记, 我们记C1=ki0。
于是由Ci计算Ci1, Ci2, g Ci (n-1) , Cin的过程中, 两次除法计算复杂度是OB (2Σn-1j=1g (max (1 (ki (j-1) , 1 (x) ) ) ) =OB (Σn-1j=1g (max (1 (ki (j-1) , 1 (x) ) ) ) 。其中, kij=Cin x (n-1) -j+Ci (n-1) x (n-1) - (j+1) +g+Ci (j+1) =Σnk=j+1Cikxk-1-j。
则由Ci, i=1, 2, …n计算C=[Cij]nxn的复杂度为OB (Σni=1Σn-1j=1g (max (1 (ki (j-1) , 1 (x) ) ) ) 。
2.3 一般方法对数代价复杂度
文献[9]中用对数代价标准计算矩阵乘法复杂度时, 因为矩阵中的元素是常数而忽略了其计算对于复杂度的影响, 这是不应该的。因为, 讨论按照对数代价标准, “两个数相乘”不能像按照统一代价标准一样看作一个单位, 而是要把元素本身都考虑进去, 那么我们必然要在考虑矩阵乘积时把矩阵元素考虑在内。
按一般方法计算Cij=Σnk=1aikbkj, 每个Cij乘法复杂度为OB (gΣnk=1g (max (1 (aik) , 1 (bkj) ) ) ) , 加法复杂度为OB (Σn-1k=1max (1 (Σkh=1aihbhj) 1 (ai (k+1) bk (j-1) ) ) 。所以, 计算Cnxn时的乘法复杂度为OB (Σni=1Σnj=1Σnk=1g (max (1 (aik) , 1 (bkj) ) ) ) , 加法复杂度为OB (Σni=1Σnj=1Σn-1k=1max (1 (Σkh=1aihbhj) , 1 (ai (k+1) bk (j+1) ) ) ) 。
2.4 举例
Cnxn=AnxnBnxn, 其中Cnxn= (Cij) nxn, Anxn= (aij) nxn, Bnxn= (bij) nxn
现假设矩阵Anxn和Bnxn中元素均为n2。下面我们将分别分析该情形下一般方法和凝聚算法计算矩阵Cnxn的时间复杂度。我们只需要把值代入上面的讨论结果即可。
注意:鉴于OB (Cq nq+Cq-1nq-1+g+C0) =OB (nq) , 所以在下面计算的时候, 会利用此来简化计算。
2.4.1 一般方法计算复杂度
按照一般方法:乘法复杂度]]
OB (Σni=1Σnj=1Σnh=1g (max (1 (aih) , 1 (bij) ) ) ) ) =OB (n3g (plog2n) )
加法复杂度
2.4.2 凝聚算法计算复杂度
1) 乘法复杂度
加法复杂度OB (max (1 (nab) , 1 (1) ) =OB (p log2n) ) 。
2) 乘法复杂度
加法复杂度^
3) 乘法复杂度
加法复杂度
4) 除法复杂度
2.4.3 讨论
综上所述, 矩阵Anxn和Bnxn中元素均为时, 矩阵乘积利用一般方法计算的计算复杂度为OB (n3g (plog2n) ) 而凝聚算法复杂度OB (n2g (pnlog2n) ) 。
倘若两个位的整数相乘, 其算法复杂度是g (m) =m, 则无论是一般方法还是凝聚算法按照对数代价计算复杂度均为OB (pn3log2n)
但是倘若整数乘法采用文献[8]中的算法, 那么两个m位的整数相乘, 其算法复杂度是OB (mlog2mlog2log2m) 。则此时g (m) =mlogmloglogm, 那么此时一般算法的计算复杂度是OB (n3[plog2n]log2[plog2n]log2log2[plog2n]) , 而凝聚算法的算法复杂度为OB (n3[plog2n]log2[pnlog2n]log2log2[pnlog2n]) , 那么, 凝聚算法的复杂度比较大。
上面讨论了在矩阵Anxn和Bnxn中元素均为np这种情形下的两种算法对数代价复杂性的比较, 扩展到一般情下存在以下两个问题:
1) 矩阵中元素不全是np的形式。
2) 矩阵中元素不全相同。因为凝聚算法复杂度主要和矩阵中最大元素相关, 而一般算法的复杂度和所有元素相关。如果矩阵中元素相同, 在这种特殊情形下比较两种算法复杂性, 是否不具有说服力?
下面, 就以上两个个问题分别加以研究说明:
首先, 从形式上讲, 针对一个特定的正整数矩阵, 我们完全可以将矩阵中每个元素通过辗转相除分解成与矩阵规模相关的多项式形式。采取np是为了在计算复杂性的时候取对数容易计算, 形式可取。
再者, 从设定的元素值来讲, 矩阵可以通过一些折中拆分变换使得矩阵元素相差不大。比如元素中最小为0和最大为10 000, 那么我们可以将矩阵中元素均减去5 000, 再将矩阵分成正负整数矩阵, 此时分解的两个矩阵中最大最小之差绝不会大于5 000了。这种变换大大减小了凝聚算法中引进的向量元素大小, 同时, 一定次数的变换, 并不会改变凝聚算法的算法复杂度。此外, 对于凝聚算法而言, 我们在考虑辅助量x的取值时利用了X=nab+1, 其中a=max{aij|i∈{1...n}, j∈{1...n}}, b=max{bij|i∈{1...n}, j∈{1...n}}。我们可以改进x的计算方法, 如利用Cauchy-Schwarz不等式计算x, 使得其与所有元素相关, 方法如下:由Cauchy-Schwarz不等式可得其中i=1...n, j=1...n。令, 其中i=1…n, j=1...n, 于是有了计算的新方法, x=amaxbmax≤nab。因此, 对于一般的输入而言, 我们可以通过变换和改进x的求值来减少与我们所研究情形的差距。
总之, 由矩阵Anxn和Bnxn中元素均为np这种输入情况并扩展到一般情形的研究可以表明, 凝聚算法的对数复杂性并非远远高于其他矩阵乘积算法复杂性。
3 结论
比较算法复杂度依据不同的标准结果也不同, 讨论时必须以统一标准为前提。按照统一代价标准, 凝聚算法达到了矩阵乘积算法的复杂度下界。而依据对数代价标准, 凝聚算法如文献[4]和文献[5]所言不低于OB (n3log2n) , 然常规算法复杂度也是如此, 矩阵乘积的凝聚算法复杂度并非远远高于常规算法复杂度。
参考文献
[1]蒋昌俊, 吴哲辉.矩阵乘法的一个最佳算法[J].科学通报, 1989, 34 (4) :251-254.
[2]蒋昌俊, 吴哲辉.“矩阵乘法的一个最佳算法”一文的进一步研究[J].计算物理, 1994, 11 (2) :149-153.
[3]陈道琦, 谢友才, 应文隆.关于矩阵乘法的一个最佳算法[J].科学通报, 1990 (3) :161-162.
[4]张振祥.关于矩阵乘法的一个算法的时间复杂度[J].数学研究与评论, 1992, 12 (3) :149-153.
[5]张振祥.关于矩阵乘法的一个改进算法的时间复杂度[J].数学研究与评论, 1999, 19 (4) :716-718.
[6]D E Knuth.Semi-numerical Algorithms volume 2 (2nd edition) [M], 1981.
[7]Alfred V.Aho, John E.Hopcroft, Jeffrey D.Ullman.The design and Analysis of Computer Algorithm[M], 2007.
[8]Arnold Schǒnhage, Volker Strassen.Schnelle Multiplikation grosser Zahlen.Computing 7, 1971:281-292.
算法的复杂性 篇6
红外热成像目标的跟踪是红外告警系统、空载下视系统对低空及地面目标的监视和红外寻的制导等军事领域中的关键技术。但是,红外热成像多为背景噪声干扰大,分辨率低的图像序列,尤其远距离检测时目标成为点源,缺少细节和形状等信息,加上在拍摄过程中目标相对于背景高速运动,使得红外目标的跟踪成为技术难题。
Mean Shift算法是目标跟踪广泛应用的一种方法,它是一种以目标区域像素值的概率分布为特征,搜索与样本点分布最相近模式的非参数统计方法[1]。由于采用了统计特征,该算法对噪声有很强的鲁棒性。另外,由于它采用核函数直方图建模,对边缘阻挡、目标的旋转、变形以及背景运动都不敏感,并且具有运算速度快、实时性好等优点。但是,该算法在跟踪快速运动的红外目标时,系统将会变得不稳定,最终可能导致目标丢失。因此,必须对Mean Shift方法改进[2,3,4],使其能增强跟踪复杂背景下快速运动红外目标的准确度。
为此,本文提出了一种基于非线性边缘检测和Mean Shift方法相结合的红外目标跟踪算法。非线性边缘算法可对复杂背景下运动图像序列进行快速边缘检测[5],以获取高质量目标边缘图像;在此基础上,利用Mean Shift改进算法对目标实施准确跟踪。
1 非线性边缘检测算法
在实际应用中,所获取的红外热图像包含着大量的噪声点,这些噪声点可能影响到边缘点的检测,得到的边缘图像不尽人意,因此这里所述的边缘检测算法首先利用传统的梯度算子[6](如Sobel算子)对图像边缘点进行初选,滤除绝大部分的噪声后,再利用一种非线性算子实现高质量的图像边缘检测,得到目标边缘的二值图像。非线性边缘检测算法思想如下:
在初选的灰度图像I(x,y)中选取一个像素点s为圆心,建立两个同心圆形窗口W1(s)(半径为R1)和W2(s)(半径为R2),求出两个圆形窗口的中最大灰度值(Max1、Max2)和最小灰度值(Min1、Min2)。定义双窗口算子D(s),其表达式如下:
任取候选边缘点集Ω0中的一点(x,y),计算D(x,y)的值,所得D(x,y)的符号可能为正、零或负。如果D(x,y)=0,则该像素点是边缘点;否则,如果D(x,y)>0,并且沿水平和垂直方向的4个领域中至少有一个像素点处的D(x,y)<0,即算子D出现了符号改变,则像素点也被认为是边缘点。
若令双窗口算子中的内窗口半径R1=0,外窗口半径R2的大小由边缘轮廓的尺寸确定,则式(1)变为
可见,I(x,y)在W2(s)中的最大值和最小值确定了s邻域中最大斜率的方向,D(s)近似于沿此方向的二阶导数,因此基于双窗口算子D(s)的零交叉检测可以用于提取图像边缘,这种算子与非线性的拉普拉斯算子类似,为一种高通的非线性算子。
2 改进的Mean Shift目标跟踪算法
传统的Mean Shift跟踪算法,依赖于由目标区域得到的灰度分布和纹理特征,利用统计分布的概念描述目标,通过相似函数计算图像空间中目标中心的位移。此算法所需参数少、鲁棒性较强、能够快速的实现模式计算,具有良好的实时性。但是由于红外目标对比度低,背景亮度经常高于目标亮度,此时仅使用灰度特征的核密度估计很难实现对目标的准确跟踪。为此在Mean Shift目标跟踪方法中,作了如下改进:一方面,融合由目标区域局部标准差的核密度估计所得到的信息[7];另一方面,为了克服用单一的灰度空间里建立目标灰度的概率密度分布时,目标灰度的概率密度分布描述不稳健的缺点,提出构造级联的灰度空间作为特征空间的想发。
局部标准差图像是通过源图像中每个像素的邻域得到的,是一种非常好的描述局部图像结构频率特性的方法。根据所定义的邻域M,图像中像素点s=I(x,y)的局部标准差计算如下:
式中:I为图像函数,Xi为空间坐标,N为邻域M中的像素个数。融合了目标区域局部标准差核密度估计的Mean Shift的跟踪方法如下。
2.1 目标模型的建立
目标模型是灰度值和局部标准差的概率密度函数,并采用核密度估计,核函数选用Epanechnikov核,因为该核在连续空间中能够产生最佳的积分均方误差(MISE)[8]。两个Epanechikov核的级联形式如下:
第一个核作为特征直方图的加权因子,即以特征值为中心放置一个一维核。第二个核是通过特征的空间位置与目标质心之间的欧氏距离来确定特征的空间关系,即以目标质心为中心放置一个二维核,核的值表示空间权重。使用联合核,目标特征u的核密度估计可由下式给出:
式中:C为归一化常量,
利用核密度估计方法建立目标特征的概率密度分布,实现目标模型的描述。假设包含目标的搜索窗口中,第u个特征值的概率密度函数:
式中:x0为搜索窗口的中心像素坐标,xi为第i个像素的坐标;k(||x||2)是核函数,h表示核函数的带宽,即目标的半径;b(xi)和δ函数的作用是判断目标区域中像素xi的特征值b(xi)是否属于特征值u,C是归一化函数。
在后续的帧图像中,使用相同的核函数和半径h,以y为中心,计算可能存在的目标特征u在候选模型中出现的概率,从而获取候选目标模型,形式如下:
其中:Ck为归一化因子,h决定了候选目标尺度。也称为描述目标和候选目标的灰度直方图特征。
2.2 目标跟踪方法
假定目标在第0帧首次出现,x0表示它的中心,利用式(5)分别计算模板的灰度图像QI和局部标准差图像Qσ每一灰度级的核密度估计。直接通过最小化模板和目标之间的距离,定位目标位置y,从而在当前帧中找到目标位置。距离定义如下:
式中:ρ(y)是修改的Bhattacharya系数,它融合了图灰度和局部标准差的特征。修改的Bhattacharya系数可理解为模板与候选目标分布的相似程度,其相似函数定义如下:
式中L为灰度和局部标准差分布的灰度级数。系数越大,距离值就越小,候选目标与模板也就越相似。因此,目标跟踪成了在当前帧中从上一个目标位置的邻域内搜索目标的新位置,使得以位置y1为自变量的距离函数取得最小值。利用Taylor展开式将式(8)在上一个目标位置y0处展开,其线性近似为
其中
可见,式(10)中第一项与y1无关。因此,要使d(y)最小,应使式(10)中的第二项最大,而该项代表着当前帧中位置y1处使用K2(X)计算的核密度估计,其中ψi为它的加权值。这样就可以使用Mean Shift向量不断的迭代,寻找邻域内该核密度估计的极大值。在这个过程中,核中心从当前位置y0移向新位置y1,其可表示为
重复以上过程就可以实现对当前帧中目标的跟踪。
2.3 模板更新
在上述的跟踪方法中,模板更新根据图像序列中目标特征的帧间相关性自动完成。为了利用目标特征改变的帧间相关性,可把相似度距离的分布看作高斯分布。在每一帧都通过下面两个公式进行更新:
式中k为当前帧序号。由公式可看到,模板的更新取决于当前的距离值dk,距离的门限值由上式决定,即如果dk<µk-2σk,则更新目标模板。
3 算法步骤及流程
首先,利用非线性边缘检测算法获取红外图像序列中边缘像素点集,其结果是滤除大量噪声点后的二值图像,并将其作为后续的目标跟踪数据源。边缘检测的流程如图1所示。
然后,对边缘检测后的灰度图像进行目标跟踪。假定目标出现在初始帧为0帧,当前帧为第k帧。计算目标模板灰度QI和标准差分布Qσ,利用式(6)计算目标中心的直方图;计算第k帧的候选目标灰度PI和标准差分布Pσ,利用式(7)计算候选目标中心的直方图。目标模板与候选目标分布之间的距离用dk表示。利用改进的Mean Shift跟踪算法进行红外目标的跟踪,步骤如下:
1)利用式(5)计算检测的目标的QI和Qσ;利用式(6)计算目标中心的;
2)在第k帧图像中使用上一次的目标中心初始化当前的目标中心,计算当前的PI和Pσ;利用式(7)计算候选目标的;
3)根据式(10)、式(11)、式(12)计算迭代的Mean Shift向量;
4)计算距离dk,根据其值确定是否跳转到第2步;
5)判断距离dk,是否满足dk<µk-2σk。若满足则更新QI和Qσ;
6)利用式(13),更新µk和σk,返回到第2步。
4 实验与结果分析
1)利用真实的红外图像,验证非线性边缘检测的性能。
原始图像为以天空为背景的高速运动的飞机目标。为了分析对比检测结果,分别利用了Sobel算子和本文提出的算法进行了实验,利用MATLAB6.5进行了结果仿真。实验采用两帧原始图像,一帧原始图像包含了弱小目标的图像,另一帧包含了面目标的图像,如图2中的(a1)、(a2)所示。图2中的(b1)、(b2)为利用Sobel算子检测的结果,(c1)、(c2)为Sobel初检后,又利用双窗口算子进行检测后的结果。
由检测的结果可看出,Sobel算子虽然可以滤除大部分噪声,把目标的边缘轮廓检测出来,但在背景噪声较大或高频噪声点时,检测结果中包含噪声点,如图2(b1)中目标被检测到,但同时也检测出背景的纹理;图2(b2)中目标比较清晰,但存在大量的噪声点。经过双窗口算子后,效果较好,如图2(c1)和图2(c2)。
2)跟踪效果的实验。
以地面背景下的运动汽车为目标的红外图像序列。该实验序列长度为300帧,每帧图像的大小为128×128。目标模型的大小(核函数的半径h和)为(h,h)=(6,6),图像处理速率为10(帧/秒)。首先利用本文提出的边缘检测算法对第0帧原始图像进行目标检测,如图3所示,并用手动方式确定目标的中心位置。图4为边缘检测和Mean Shift方法相结合的跟踪处理的结果,第0帧的图像为本实验红外序列图像的第0帧,其中十字叉丝的交点为目标检测后得出目标的中心位置。可以看到,本文方法能够对红外目标实现实时的准确跟踪。
5 结论
本文提出的红外目标检测和跟踪算法,结合了非线性边缘检测和Mean Shift跟踪方法的各自优点,其中非线性边缘检测具有计算量小、速度快、检测出图像质量高等优点;在目标检测出来的基础上,利用改进的Mean Shift跟踪算法,对红外目标实时跟踪,该方法克服了传统Mean Shift跟踪方法对目标对比度低的跟踪效果不佳的现象。实验结果表明,非线性边缘检测分割出的目标边缘清晰,图像质量好;在手动确定第0帧目标的中心位置后,可以对复杂背景下的红外目标准确跟踪,并能够自动更新目标模板。
参考文献
[1]宋新,沈振康,王平,等.Mean shift在目标跟踪中的应用[J].系统工程与电子技术,2007,29(9):1405-1409.SONG Xin,SHEN Zhen-kang,WANG Pin,et al.Application of Mean shift method in target tracking[J].Systems Engineering and Electronics,2007,29(9):1405-1409.
[2]程建,杨杰.一种基于均值移位的红外目标跟踪新方法[J].红外与毫米波学报,2005,24(3):231-235.CHENG Jian,YANG Jie.Novel Infrared Object Tracking Method Based On Mean Shift[J].J.Infrared Millim.Waves,2005,24(3):231-235.
[3]杨烜,裴继红,谢维信.基于运动特征的远距离红外目标检测方法[J].电子与信息学报,2007,29(8):1829-1832.YANG Xuan,PEI Ji-hong,XIE Wei-xin.Long Range Moving Target Detection Based on Motion Analysis[J].Journal of Electronics&Information Technology,2007,29(8):1829-1832.
[4]颜佳,吴敏渊,陈淑珍,等.基于Mean Shift算法的伪装目标跟踪[J].光电工程,2009,36(2):11-15.YAN Jia,WU Min-yuan,CHEN Shu-zhen,et al.Camouflaged Target Tracking Based on Mean Shift[J].Opto-Electronic Engineering,2009,36(2):11-15.
[5]梁燕,刘文耀.一种新型非线性边缘检测算法[J].光电子.激光,2003,14(12):1332-1335.LIANG Yan,LIU Wen-yao.A New Nonlinear Algorithm for Edge Detection[J].Journal of Optoelectronics.Laser,2003,14(12):1332-1335.
[6]王苑楠.图像边缘检测方法的比较和研究[J].计算机与数字工程,2009,37(1):121-127.WANG Yuan-nan.Comparison and Research on Image Edge Detection Method[J].Computer&Digital Engineering,2009,37(1):121-127.
[7]Comaniciu D,Ramesh V,Meer P.Real-Time Tracking of Non-Rigid Objects Using Mean Shift[C]//IEEE Conference on Computer Vision and Pat tern Recognition,Hilton Head Island,SC,June13-15,2000,2:142-149.
算法的复杂性 篇7
关键词：复杂网络,相似度,演化模型,幂率分布,小世界
0 引言
现实世界中的大量系统都可以抽象为复杂网络, 如社交网络、计算机网络、新陈代谢网等等[1,2]。研究表明, 这些网络通常都具有无标度特性[1]和小世界特性[3], 社交网络通常还表现出高聚类系数和局部传递性[4]。由于真实网络数量有限, 因此建立符合真实网络演化特性的模型来模拟真实网络, 是复杂网络研究中的重要问题[1]。
1999年Barabasi和Albert首先提出了无标度网络演化模型BA模型[1], 它基于增长和偏好连接机制, 即每步增加一个新节点连接到若干已存在节点, 且新节点优先与度大的节点连接。后续很多模型在其基础上提出各种各样的改进, 如节点老化和死亡机制[4]、随机游走机制[5]、吸引因子机制[2]等等。近年来, 随着研究的深入偏好连接这一机制的内涵又有了新的理解, 在BA模型中度大的节点吸引力更强, 而在现实世界中两个相似度大的对象间更易于形成联系[4,6,7]。2012年, Fragkiskos在《Nature》上发文提出一种权衡流行度和相似度来计算节点吸引力的方法[6], 即用角度代表节点相似度, 用年龄代表节点流行度, 为网络演化模型的研究开辟了一个新思路。但上述模型并没有解决BA模型的最重要缺陷:该模型不具备小世界特性。
为此, 本文提出了一种基于相似度特性[6]和三角形结构[8,9]的复杂网络演化模型, 引入了节点相似度因素, 基于真实网络中的三角形结构, 演化机制简单, 生成的网络具有幂率分布和高聚类系数的性质。
1 演化模型及算法流程
模型中引入角度代表节点的相似度, 即为每个节点赋予[0, 360) 区间内的值作为该节点的偏好。对于边e (u, v) , 引入θe为节点u, v角度的平均值, 代表该边的平均偏好;de为节点u, v的角度差, 代表该边两端点的分歧。不妨设θu>θv, 定义函数dif (θu, θv) 为角度差, 则θe和de的计算方法如下:
该演化模型算法流程如下:
(1) 初始化网络:初始网络中有m0 (m0≥3) 个相互连接的节点, 初始边数
(2) 加入新节点:加入新节点v, 随机生成[0, 360) 内均匀分布的浮点数角度θv。
(3) 计算相似度:对于网络中的每条边ei, 计算节点v和该边的相似度si=f (θei, θv) 。
(4) 择优连接:节点v优先选择相似度高的边, 选择边ei的概率 。选出边ei后, 节点v与该边的两个端点连接。
上述步骤中相似度s=f (θe, θv) , 根据需要, 函数f可以有多种不同定义。显然, 角度差越大, 则节点的相似度越小, 所以 。给出以下两种函数形式:
(1) 幂函数形式: , 其中α>0
(2) 对数函数形式:f (θe, θv) =C-ln (dif (θe, θv) ) , 其中C为常数以保证f (θe, θv) 恒大于0。
根据网络的增长过程, 每加入一个新节点, 网络中都引入两条边, 形成一个三角形, 经过t步后形成一个具有m0+t个节点和e0+2t条边的网络。
2 演化模型分析和仿真
2.1 度分布
用P (k) 表示网络中节点度为k的概率。首先计算每条边被选中的先验概率, 设任意两条边ei和ej, 新加入节点为v。根据全概公式, 相似度si的期望 , 由于f (θi, θv) 仅和角度差有关且积分区间为0-360度, 故对于任意的θi积分式均相等。则E (si) =E (sj) , 即任意两条边被选中的先验概率相等。故度为k的节点在第t+1步被选中加边的概率为 。
设p (k, ti, t) 为ti时刻加入网络的节点在t时刻度为k的概率, 它来自上一时刻该节点度为k-1被选中加边, 或上一时刻该节点度为k未被选中。可得满足的动态演化方程如下[10]:
当k=2时, P (k-1) =0, δ (pk) =p (k, t+1, t+1) =1, 可得
由上述递推关系可得,
说明该演化模型算法生成的网络的度分布服从幂率分布, 度分布函数为: , 当网络规模足够大时, 幂指数趋近于-3。
在Network X中网络节点数N=2000和N=10000时的仿真结果如图1所示。
验证了该演化模型生成的网络服从幂率分布。
2.2 相似度
在度分布一节中已证明, 由于新节点角度分布的随机性, 使得每条边被选中的先验概率相当。所以, 该模型在不影响度分布的情况下, 使角度相近的节点以更大概率连接, 可以通过调整相似度函数s=f (θe, θv) 的形式控制聚合的程度。根据该算法随机生成具有N个节点的网络, 对于任意一条边e, 分析当新节点v与该边角度差为dif (θe, θv) =Δθ时, 边e被选中的概率p。显然在E确定时, p仅和角度差Δθ及相似度函数s的形式有关。
当N=50时的仿真结果如图2所示。从图2中可以看出, 对于等概随机选边, 即相似函数恒为常数, 新节点连接每条边的概率相等。由于相似函数s=f (θe, θv) 随角度差Δθ单调递减, 所以Δθ越大, 相似度越小, 连接概率越小。幂函数形式的斜率大, 且阶数约高斜率越大, 而对数函数形式的斜率小, 且常数越大斜率越小, 因而可以通过控制函数形式和参数来控制角度相近节点的聚合程度。
定义 为网络平均分歧, 其中 (u, v) 为网络中的边。当N=500时的仿真结果如表1所示。
从表中可以看出, 幂函数形式α=3具有最小的平均分歧, 与上述分析结论一致。
2.3 聚类系数
聚类系数表示网络中某节点的邻居节点间存在边的概率, 节点v的聚类系数定义为 , 其中kv为节点v的度, ev为其邻居节点间存在的边数。网络平均聚类系数为所有节点聚类系数的平均值
由演化算法的步骤可知, 节点度的增加只能来自与新节点连接, 节点度每增加1, 则邻居节点间的边数增长1。节点新加入网络中时度为2, 邻居节点间边数为1。故节点度为k时, 邻居节点间边数为k-1, 聚类系数 。
当网络规模趋于无穷大时, 网络平均聚类系数 , 由度分布一节已知, , 利用无穷分式计算可得:
因此, 该模型算法生成的网络有较大的聚类系数, 度为k的节点聚类系数为 , 当网络规模足够大时网络平均聚类系数趋近于常数0.7392, 而BA模型的聚类系数在网络规模增大时趋近于0。
在N=2000时网络的聚类系数分布仿真结果如图3所示。
验证了度为k的节点聚类系数 网络平均聚类系数逼近理论值0.7392。
2.4 网络平均距离
网络平均距离定义为网络中任意两个节点距离的平均值, 即 , 其中L (N) 表示节点数为N网络平均距离, lij表示节点i与节点j的距离。该模型生成的网络具有小世界特性, 网络平均距离L (N) ≤2ln (N) 。
证明:设t时刻网络节点数为N, t+1时刻加入新节点v。则t+1时刻网络平均距离L (N+1) 满足下式:
整理得:
设新节点v连接的两个端点为u1和u2, 则liv=min (liu1+1, liu2+1) 。在平均意义下, 任取两个节点i和u的距离liu可视为网络的平均距离L (N) 。
说明该演化算法生成的模型具有小世界特性, 即网络平均距离随网络节点数量增长的速率不超过其对数速率, 网络具有较小的平均距离。
从N=500至N=5000网络平均距离的仿真结果如图4所示。
验证了网络平均距离随节点数增加的增长速率为对数函数。
3 结束语
本文提出了基于相似度特性的网络演化模型算法, 对模型的度分布、相似度特性、聚类系数和平均距离等给出了详细的分析, 并通过数值仿真验证了理论推导。该演化模型生成的网络服从幂率分布, 聚类系数较大且平均距离较短, 具有小世界特性;相似度较高的节点间连接概率大, 并可以通过控制相似度函数的形式和参数调整相似节点的聚合程度。
参考文献
[1]Barabási A L, Albert R.Emergence of scaling in random networks[J].science, 1999, 286 (5439) :509-512.
[2]Holme P, Kim B J.Growing scale-free networks with tunable clustering[J].Physical Review E, 2002, 65 (2) :026107.
[3]Watts D J, Strogatz S H.Collective dynamics of‘small-world’networks[J].nature, 1998, 393 (6684) :440-442.
[4]Dorogovtsev S N, Mendes J F F.Evolution of networks with aging of sites[J].Physical Review E, 2000, 62 (2) :1842.
[5]Saramki J, Kaski K.Scale-free networks generated by random walkers[J].Physica A:Statistical Mechanics and its Applications, 2004, 341:80-86.
[6]Papadopoulos F, Kitsak M, Serrano Má, et al.Popularity versus similarity in growing networks[J].Nature, 2012, 489 (7417) :537-540.
[7]Leskovec J, Backstrom L, Kumar R, et al.Microscopic evolution of social networks[C]//Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining.ACM, 2008:462-470.
[8]裴伟东, 夏玮, 王全来, 等.多三角形结构动态复杂网络演化模型及其稳定性分析[J].计算机工程与应用, 2011, 47 (23) :41-44.
[9]Zhou T, Yan G, Wang B H.Maximal planar networks with large clustering coefficient and power-law degree distribution[J].Physical Review E, 2005, 71 (4) :046141.
算法的复杂性 篇8
随着计算机网络应用与数据挖掘技术的发展,特别是社交网络平台的盛行,复杂网络的研究变得越来越重要。不论是对于社交平台用户关系网的数据分析[1],还是对于电子商务网站消费模式制定,抑或是电信营运商的资费方式调整,借助与复杂网络方法更能挖掘出关联用户的价值信息。比如腾讯公司根据用户的好友及所在群情况,建立了圈子好友,为用户推送更多具有间接联系的好友,这便是对复杂网络的一种应用。在利用复杂网络知识分析问题之前,首先必须对复杂网络进行可视化处理,这一步骤能够更好地反映整个网络的结构。文献[2]是运用复杂网络可视化对社会网的数据分析,文献[3,4]均是对网络社交平台的数据挖掘[2,3,4],可视化处理最大的优点是便于查看网络内部结构,从而挖掘网络中隐藏的有价值信息。这是数据处理比较关键的一步。本文正是基于此背景所做研究,目的在于找到一种性能更优的网络生成方法,为大型网络数据分析提供一定的帮助。
当前复杂网络的生成方式主要有三种[5]: 随机点生成方式、随机边的生成方式和基于节点的度的生成方式。三种方式各有优劣,本文提出了基于随机游走复杂网络生成方法,网络抽样更加均匀,通过实验比较,能够更好地保持原网络结构,连通性优良。
1 基于随机游走的层次网络生成
对于复杂网络来说,研究其层次结构显得非常重要。复杂网络节点数目较多,节点之间的上行总括关系、下行隶属关系及并列关系错综复杂,而节点之间的这种关系对分析网络相邻节点属性以及整个网络的结构研究具有重要意义。这便需要采用相应的策略对复杂网络结构进行层次分析,将整个复杂网络按照一定的方式划分成不同层次的小网络,将三维空间网络结构划分成多张二维空间的网络进行探究分析,以降低复杂网络的分析难度。本文将采用随机游走算法来实现网络的层次生成。
1. 1 常见层次网络生成方法
( 1) 随机选点方法
随机选点方法,顾名思义是随机选择原始网络中的节点,并参考原始网络中所选中节点的边关系对网络进行重新构建[6]。根据原始网络节点个数确定抽样比,选择一定量的随机节点,然后组建网络。一般而言,随机选点策略的精确性较差,因为网络中的节点都是随意抽取的,在样本量大的情况下,可能较好地恢复整个网络的原貌,但是在样本容量较小的情况下,误差较大,不适合复杂网络的结构生成。
( 2) 随机选边方法
随机选边策略是对网络中的边进行随机选择,然后与选中边相连的节点选中,将选中的边与这些节点进行网络重建。在已经选中的边的相邻边中进行随机选择,该方法和随机选点方法的缺点一样,在样本容量不够大的情况下,误差较大,所以使用具有一定的局限性。
( 3) 基于节点度方法
在随机点方法的基础上衍生了一种基于节点度的选点策略[7],节点的度在一定程度上反映了该节点与相邻节点的关联关系的强弱。该策略选择度较大的节点进行网络重建,因为度越大,与之相连的节点越多,表明该节点在整个网络中的重要性越高,选择这样的节点更能够保持原来网络的真实架构,该方法具有一定的应用范围,但是要计算出所有节点的度是比较耗时的,效率低下,特别是大型复杂网络,因此该方法不适合节点多的网络生成。
考虑到三种方法的适用范围及优缺点,提出了基于随机游走的网络生成方法,很好地弥补了这三种方法的不足。
1. 2 基于随机游走的层次网络生成方法
随机游走是一种基于扩散策略的网络生成方法,基本实现原理是在整个原始网络中放置一个活跃标签[8],活跃标签的游走过程即为随机游走过程。活跃标签经过的节点即为网络重建的节点,随机游走策略在选取行走路由的时候,不是简单地根据当前节点与之相连的节点中随机选取下一个节点,而是根据节点网络属性。
随机游走策略强调下一次抽取与前一次抽取的联系,选中某一节点之后,从与之节点相连的节点中随机选取下一个节点,依次迭代重建网络。
在给定区域的随机游走算法数学模型如下所示:
考虑到网络节点个数为有限个,是具有一定的边界条件的,因此只需考虑在边界条件下活跃标签移动的概率求解即可。定义在给定边界条件Γ下,随机游走活跃标签从非标记点出发第一次到达标记点的概率可参考下式:
其中u( i,j) 在边界区域内具有二阶连续偏导数且满足拉普拉斯方程,因此该函数是典型的调和函数,该函数的边界条件为:
根据二维空间偏微分的数学关系,概率的求解过程转变为u( i,j) 的最小值求解过程。在映射图中定义联合拉普拉斯矩阵为:
Lij的值由节点vi与vj共同决定,di为节点vi的度。顶点间的关联矩阵,即图G的m×n条边的定义:
由式( 4) 得,关联矩阵由边eij和节点vk共同决定,图中所有的eij可以是任意一个指定的方向。一般称A为联合梯度算子,AT为联合散度算子。
网络边的权值用对角阵C来定义:
由于正定阵L可以分解为L = ATA。这个构造矩阵C可以理解为在向量上一个加权内积大小的度量,从这个意义上来说,通过L = ATCA,即当C = I时,L = ATA。
给定区域Ω上的积分为:
在已经固定标记点的值的前提下,求解非标记点到达标记点的概率值。式( 6) 可以改写为:
根据线性代数相关知识,由式( 7) 可得,L是半正定矩阵,所以在唯一临界点处,D[x]可以取得最小值。将映射图G的所有顶点划分为种子节点集VM( 标记点集) 和未标记点集VU两个子集,且使它们满足VM∪VU= V,VM∩VU= 0,在不失一般性的前提下,我们假定L和x中的顶点按照优先排列种子点再排列非种子点的规则来完成,于是,式( 7) 可以分解为:
其中,xB和xU分别对应种子点和非种子点的电压值,此时,拉普拉斯矩阵也被分解为:
对D[xU]求关于xU的微分可求得临界点,可得:
这是一个含未知数| VU|的线性方程系统,只有整个图是连通的,或者每个连接区域都含有一个种子点,那么式( 10) 才是满秩的。
令xsi表示非种子点vi第一次到达类别s的种子点的概率值,并定义这样一个函数来表示所有标记点的集合: Q( vj) = s,vj∈VM,其中s∈Ζ,0 < s≤K,再为所有在vj∈VM的点定义一个| VM|×1大小的矩阵:
因此,通过求解式( 12) ,就能得到单个标记点s的联合狄利克雷问题的概率值大小。而对于所有的种子点的概率值大小,需通过求解式( 13) 得到[9]。
由K - 1个线性方程求解出非标记点到K个标记点的概率值大小,由xs可以得出X有K列,且由ms可以得出M的列数,由电路原理可知,每个节点的概率和为1:
在获得每个未标记点vi到标记点的K个概率后,逐个比较它们的大小,以最大转移概率maxs( xsi) 为准则来实现下一个节点的选择。
2 实例仿真
为了验证本文算法在复杂网络层次生成运算中的性能,采用某一社交网站服务器用户数据网络作为数据来源来进行实例仿真。社交网络平台需要发展,必须借助考虑用户之间的联系,以求为用户提供更优质便捷的推送服务,这就需要对用户之间的关联性进行深入研究,复杂网络方法则正好解决了该问题。
本文以某社交网站的用户数据进行提取,然后运用随机节点、随机边、基于节点的度方法和随机游走算法生成复杂网络,并对算法运行时间及层次网络属性进行分析,验证本文算法的优越性。
将每个注册的用户作为网络中的节点,用户发送消息对话作为网络中的边。首先抽取某一时间段的用户交互数据构建网络,网络节点共有10 000个,边633 241条。
由于要对节点度选点算法进行性能对比,有必要对网络中节点的度分布和聚类系数进行求解。其中聚类系数是对网络节点与之相邻节点紧密程度的衡量。
如图1所示为原始网络节点度分布结构图,其中横轴为节点的度,纵轴为网络中节点数量,从图中可见,网络中节点的度普遍集中在1 ~ 6,度为1的节点最多,约有3 200个。
如图2所示为原始网络节点聚类系数分布图,其中横轴为节点的度,纵轴为节点的平均聚类系数,从图中可见,度为20 ~40的节点的聚类系数最高,在0. 4左右,表明度为20 ~ 40的节点与之相邻节点的紧密程度更高。
在实验中,为了便于展示整个网络,在原始网络中按一定数量抽取节点,抽取节点占原始节点比例分别为: 80% ,60% ,40% ,20% ,分别查看可得原始网络的拓扑结构图。考虑到篇幅原因,本文仅列举了抽样比例为40% 时随机游走算法生成的网络结构图,如图3所示。
在实际运算过程中,抽样比并不是越高越好,抽样比过高,系统运算量大,而且节点数目过多,对整个网络结构分析的贡献表现并不突出,相反,抽样比适中,系统运算效率高,而且能够很好地反映整个网络的层次架构,本文选择的抽样比例为40% ,满足本文分析需求。
考虑到层次生成的目的是用尽可能少的节点和边展示出网络特性,下面将对点边比例、网络连通分量个数、最大连通分量比例做仿真,因为这些参数在一定程度上反映了层次生成策略算法是否展示出原始网络特性。
从表1和表2数据可得,从网络连通程度上来看,随机节点,随机边,基于度的点策略均会因为节点抽样比下降导致网络连通性下降,随机游走则受节点抽样比的降低对网络连通性影响较小。
下面将对不同策略的网络层次生成后的节点度分布和聚类系数与原图进行对比,比较网络生成的相似性与稳定性,考虑到篇幅原因,本文仅给出了随机游走策略生成的度分布和聚类系数图,如图4和图5所示。
4种层次生成策略在生成层次网络时,基本都能保持整个网络度分布的无标度特性,同时也能保证聚类系数的各层次之间也具有一定的相似关系,但是通过与图1和图2的原始网络度分布和聚类系数比较,策略算法性能有一定的差异。其中随机游走在度分布和聚类系数上更接近于原始网络。
从以上结果分析可得,随机游走策略运用于复杂网络层次生成,网络连通性好,度分布和聚类系数与原始网络更相似,是一种较好的复杂网络层次生成方法。
3 结 语
一种复杂环境中的车牌定位算法 篇9
关键词：边缘检测,梯度方向特征,边缘点密度,车牌定位
车牌识别(License Plate Recognition,LPR)是模式识别和机器视觉应用在智能交通系统领域中的一个重要研究课题,在公共安全、交通监测和管理以及电子收费系统等方面具有重要的应用价值。车牌定位是车牌识别中的一项关键技术,其准确度直接影响着后续的字符分割和识别。
车牌定位是基于车牌区域的特征将车牌区域从车牌图像中分割出来。常见的车牌定位方法有:1)基于灰度图像纹理特征的分析方法[1]。此类方法一般先利用图像处理的手段获取车牌图像的纹理特征,并基于车牌区域纹理特征独有的特点搜寻车牌区域在整幅图像中的位置。但基于纹理特征的车牌定位方法对于噪声比较敏感,且受光照因素影响较大,需结合光照鲁棒的方法提升其准确度。2)基于数学形态学的车牌定位算法[2,3]。此类算法一般在对车牌图像进行二值化后,利用结构算子对二值化图像进行腐蚀运算和闭运算消除噪声,并形成闭合的连通区域。然后计算出每个连通区域的外接矩形框,利用车牌区域的一些特点完成车牌定位。 3)基于小波变换的车牌定位算法[4]。小波变换将输入的原始车牌图像信号分解成一系列不同分辨率、不同频率特性的子带信号,然后利用这些信号的特性完成对信号在时域和频域的局部变换。4)基于神经网络的车牌定位算法[5]。为了提高车牌定位的速度和准确度,通常情况下,基于神经网络的车牌定位算法要求车牌特征保持基本不变,如果牌照特征发生了较大的变化,那么就必须对神经网络重新训练,而对于车牌采集环境的复杂性来讲,车牌特征常常发生较大范围的变化,所以对于在不同环境中采集到的车牌图像利用神经网络进行车牌定位往往达不到满意的效果。5)基于车牌区域颜色特征的车牌定位算法[6]。该算法主要是根据车牌底色和字符颜色只有固定几种颜色搭配的特点,通过提取图像中的颜色信息结合其他算法来进行车牌定位。由于车牌图像在不同的光照条件下有一定程度的色偏,所以需要考虑对车牌图像进行颜色校正。上述车牌定位方法都有各自的优缺点,但值得指出的是,目前尚未发现性能能够全面超越其他方法的某一车牌定位算法。
本文提出了一种基于车牌图像边缘特征和梯度方向特征的车牌定位方法,其主要任务是消除干扰边缘并尽可能保留车牌区域的边缘特征。该方法提取车牌图像的垂直边缘, 然后根据边缘长度、边缘点密度及梯度方向移除干扰边缘以凸显车牌区域位置,最后将车牌区域从原图像中分割出来。
1车牌图像处理
在本方法中,输入的车牌图像首先会被转换为384×288像素的灰度图像。车牌图像背景中的树叶、建筑物、走廊和倒影等会产生大量的密集干扰边缘。此时,仅依靠边缘长度来去除干扰边缘的效果通常不够理想。相比之下,本文提出的方法能够很好地从边缘图像中消除此类干扰边缘。
1.1边缘图像获取
1)灰度变换
原始的RGB图像包含的数据量较大。为加快后续的图像处理过程,本文首先利用一个灰度变换公式将原始的彩色图像转换为灰度图像,利用加权平均的方法完成灰度转换, 表示为
2)垂直边缘提取
车牌周围的背景区域存在较多的水平边缘,且该区域中比较常见的是一些较长的边缘和随机噪声。而车牌区域的边缘较为集中,具有强烈的纹理特征。如果只提取车牌图像的垂直边缘,则会损失少量车牌区域的水平边缘信息,但大量的背景区域边缘可以被移除,从而使得车牌区域在车牌图像中进一步被凸显出来。考虑到以上事实,本文利用垂直Sobel算子对灰度图像进行边缘检测以获得垂直方向的梯度图像。尽管车牌区域的少量水平边缘信息会丢失,但这种损失是值得的。垂直Sobel算子的定义为
接下来需要找到一个合适的阈值对梯度图像进行二值化。本文通过计算图像梯度的平均绝对值并将其乘以一个调节因子作为二值化阈值。最后,对梯度图像进行水平方向的非极大值抑制[7],并利用前面得到的阈值最终获得一个单边缘图像,结果如图1所示。图1a是原始图像,图1b是经过式(1)灰度变换后的图像,图1c是利用Sobel算子提取的垂直边缘图像,从图中可以看出,车牌图像背景中纷杂的树叶、建筑物以及走廊等形成大量密集的干扰边缘被凸显出来,这些会对车牌定位造成极大的干扰。
1.2梯度方向图像获取
Gradientfaces方法[8]最初用于人脸识别领域,主要任务是在不同光照条件下获取一种光照不变量。该方法对光照变化不敏感,在不同光照条件下具有较好的鲁棒性。此外,Gradientfaces方法源于图像的梯度域。因为梯度空间中梯度信息包含有相邻像素间的关系,所以Gradientfaces方法能够找出图像中隐含的固有结构。
Gradientfaces方法的实现过程如下:
1)通过将输入图像I与高斯核函数G卷积,对输入图像I进行平滑处理。
式中:*表示卷积运算;是高斯核函数。
2)通过与x和y方向上的高斯核派生函数卷积来计算图像I的梯度值。
式中,Gx(x,y,σ ) 和Gy(x,y,σ ) 分别为x方向和y方向上的高斯核派生函数。
3)最后,利用等式(5)求得图像I的梯度方向图像。
这就是梯度方向矩阵G。车牌图像的处理结果如图2所示。
2干扰边缘移除
2.1根据边缘长度移除干扰边缘
在1.1节中获取的垂直边缘图像中存在大量过长或过短的背景边缘,它们不同于车牌区域的边缘特征。因此,本文根据边缘长度可以移除部分干扰边缘。
在本文中,M和N是与垂直边缘图像同等大小的矩阵; Tlong和Tsh ort均为边缘长度的阈值。算法描述如下:首先,从左到右从上到下扫描边缘点并将对应边缘点累计的边缘长度记录在矩阵M中;然后,从右到左从下到上扫描图像中的边缘点,并将对应边缘点累计的边缘长度记录在矩阵N中; 最后,计算M和N的和矩阵,若该矩阵中某个值大于Tlong或小于Tsh ort,则消除掉边缘图像中对应的边缘点。
这里,边缘长度是当前像素Pi,j的相关邻域像素值的累积。如图3所示,阴影网格表示当前像素的相关邻域像素。
2.2根据边缘密度移除干扰边缘
因为车牌图像的车牌区域具有高度集中的边缘信息,边缘点相对稀疏的区域可以被排除,据此可以消除边缘图像中此类区域中边缘点。
本方法利用一个以边缘点为中心的小矩形窗口(如32× 24)从左到右从上到下对经2.1节处理后的边缘图像进行扫描。如果窗口内的边缘点所占比例低于某个阈值,则将窗口中所有的边缘点全部移除。
2.3根据梯度方向移除干扰边缘
为了降低这一步骤的复杂度,本文首先对1.2节中获取的梯度方向矩阵G求取绝对值,将其中的负值取正。观察车牌特点可知,在矩阵G中,车牌区域中边缘点的梯度方向主要集中在0°,45°,90°,135°,180°左右。对于矩阵G中在指定取值范围内的值,利用2.1节的方法重新统计2.2节中得到的边缘图像中对应位置边缘点的边缘长度。值得注意的是,此次统计除了需要考虑当前像素的相关邻域像素是否为边缘点外,还要考虑邻域边缘点的梯度方向是否与当前边缘点的梯度方向相近,只有两个条件均符合时方可将两个边缘点视为在同一条边缘上。然后重新设定一个阈值Tsh ort,消除边缘长度小于Tsh ort的边缘点。处理结果如图4所示,图4a是经过2.1节的方法处理后的图像,图4b是经过2.2节方法处理后的图像,图4c是经过2.3节方法处理后的图像,可以看到,原边缘图像中大部分的干扰边缘已被移除。
3车牌检测与分割
在经过上述若干步处理后,原大部分的干扰边缘已被移除的情况下,利用一个比车牌区域稍大的全1矩阵与处理后的边缘图像做卷积运算。找出卷积结果中最大值的位置,以最大值位置的对应点为中心从原车牌图像中将车牌区域分割出来。分割出的车牌区域如图5所示。
4实验结果与分析
在仿真实验中,笔者用本文方法对来自不同拍摄环境中的301幅车牌图像进行处理。这些图像均具有较复杂的背景,且拍摄于各不相同的光照环境中,如多云、阴雨天、白天、 晚上等等。一些示例图像及它们的处理结果如图6所示。
实验结果显示,大部分车牌区域可以被成功地从车牌图像中分割出来,其定位准确率为93.7%。此外,笔者将本文方法与文献[9]和文献[10]的方法分别进行对比,三者均应用于同一实验环境中,后二者的定位准确率分别为89.7%和90.4%。结果显示文献[9]的方法在复杂背景情况下受干扰严重,会出现定位不准的现象;文献[10]的方法受光照偏色影响较大,在光照条件不理想或车牌颜色失真时效果会大打折扣;而本文方法在应对复杂背景或光照不足的情况时具有更高的定位准确度和更好的适应性。
5结论
【算法的复杂性】推荐阅读：
建筑的复杂性02-01
金融系统的复杂性05-08
高等教育的复杂性10-12
复杂性肛瘘的治疗体会论文07-11
复杂性视野中的技术08-09
业务流程的角色复杂性10-25
中药材栽培技术的复杂性分析论文01-31
从系统科学和系统复杂性的角度看中医理论07-18
【形势与政策】正确认识两岸关系和平发展的长期性和复杂性07-18
复杂的心态12-03