基于距离预测的快速自适应运动估计算法

Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　２００７，４３（３０）８３　基于距离预测的快速自适应运动估计算法　谭琳　２，李丽娟１　ＴＡＮ　Ｌｉｎ　一，ＬＩ　Ｌｉ－ｊｕａｎ　１．湖南大学计算机与通信学院，长沙４１００８３　２，中南林业科技大学，长沙４１０００４　１．Ｓｃｈｏｏｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　ａｎｄ　Ｃｏｍｍｕｎｉｃａｔｉｏｎ，Ｈｕｎａｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｓｈａ　４１００８３，Ｃｈｉｎａ　２．Ｃｅｎｔｒａｌ　Ｓｏｕｔｈ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｆｏｒｅｓｔｒｙ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｓｈａ　４　１０００４，Ｃｈｉｎａ　ＴＡＮ　Ｌｉｎ，ＬＩ　Ｌｉ－ｊｕａｎ．Ｆａｓｔ　ａｄａｐｔｉｖｅ　ｍｏｔｉｏｎ　ｅｓｔｉｍａｔｉｏｎ　ｂａｓｅｄ　ｏｎ　ｄｉｓｔａｎｃｅ　ｐｒｅｄｉｃｔｉｏｎ．Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ，２００７，４３（３０）：８３－８４．　Ａｂｓｔｒａｃｔ：Ｓｉｎｃｅ　ｍｏｓｔ　ｏｆ　ｔｈｅ　ｅｘｉｓｔｉｎｇ　ｆａｓｔ　ｍｏｔｉｏｎ　ｓｅａｒｃｈ　ａｌｇｏｒｉｔｈｍ　ｓｅｌｄｏｍ　ｅｘａｍｉｎｅ　ａｌｌ　ｐｏｓｓｉｂｌｅ　ｃａｎｄｉｄａｔｅｓ　ｗｉｔｈｉｎ　ａ　ｓｅａｒｃｈ　ａｒｅａ，　ｔｈｅｙ　ｍａｙ　ｆａｉｌ　ｔｏ　ｆｉｎｄ　ｔｈｅ　ｏｐｔｉｍｕｍ　ｐｏｉｎｔ　ｆｏｒ　ｓｅｑｕｅｎｃｅｓ　ｈａｖｉｎｇ　ｆａｓｔ　ａｎｄ／ｏｒ　ｒａｎｄｏｍ　ｍｏｔｉｏｎｓ．Ｔｏ　ａｌｌｅｖｉａｔｅ　ｔｈｉｓ　ｐｒｏｂｌｅｍ，ｐｒｏｐｏｓｅｓ　ａ　ｍｅａｓｕｒｅ　ｅｓｔｉｍａｔｉｎｇ　ｔｈｅ　ｄｉｓｔａｎｃｅ　ｂｅｔｗｅｅｎ　ｔｈｅ　ｃｕｒｒｅｎｔ　ｓｅａｒｃｈ　ｐｏｉｎｔ　ａｎｄ　ｔｈｅ　ｏｐｔｉｍａｌ　ｐｏｉｎｔ，ｗｈｉｃｈ　ｃｏｍｂｉｎｅｓ　ｗｉｔｈ　ｈｉｅｒａｒｃｈｉｃａｌ　ｓｅａｒｃｈｅｓ．Ｔｈｅ　ｐｒｏｐｏｓｅｄ　ａｌｇｏｒｉｔｈｍ　ｉｍｐｒｏｖｅｓ　ｓｅａｒｃｈ　ｓｐｅｅｄ　ｏｆ　ｓｅｑｕｅｎｃｅｓ　ｗｉｔｈ　ｆａｓｔ　ａｎｄ／ｏｒ　ｒａｎｄｏｍ　ｍｏｔｉｏｎｓ　ａｓ　ｗｅｌｌ　ａｓ　ＰＳＮＲ　ｐｅｒｆｏｒｍａｎｃｅ．　Ｋｅｙ　ｗｏｒｄｓ：ｆａｓｔ　ｍｏｔｉｏｎ　ｅｓ【ｉｍａ【ｉｏｎ；ｄｉｓ【ａｎｃｅ　ｐｒｅｄｉｃｔｉｏｎ；ｈｉｅｒａｒｃｈｉｃａｌ　ｓｅａｒｃｈ；ｒａｎｄｏｍ　ｍｏｔｉｏｎ　ｖｅｃｔｏｒ　摘要：已有的快速搜索算法中，绝大多数都不检查搜索区中所有候选项，所以，当视频序列中有快速或随机运动时，这些算法常　导致搜索陷入局部最优。为了解决这一问题，提出了一种估算当前搜索点和最佳点之间的距离的度量方法，在此基础上提出了一　种新的自适应的阂值方案，并结合层次搜索技术，既有效提高了具有快速或随机运动的视频的运动估计的搜索速度，也保证了算　法较好的ＰＳＮＲ性能。　关键词：快速运动估计；距离预测；分层搜索；随机ＭＶ　文章编号：１００２—８３３１（２００７）３０—００８３—０２　文献标识码：Ａ　中图分类号：ＴＰ３０１．６　１引言　的方案，并阐述了一个基于该估算距离提出的终止搜索的自适　在视频编码技术中，已推出了许多基于块匹配（ＢＭＡ）的快　应阈值技术，在此基础上设计随机ＭＶ搜索方案，最后是该运　速运动估计算法，如ＴＳＳ、ＢＢＧＤＳ、ＤＳ、ＨＥＸＢＳ、ＣＤＳ、ＭＶＦＡＳＴ　动估计算法的描述。　和ＰＭＶＦＡＳＴ等。在快速搜索算法中，搜索模式的形状、大小及　２．１距离估算方案　初始搜索中心的选择等因素对搜索速度及ＰＳＮＲ性能均有很　为了简化距离估算，先做如下假设：假设为一维运动；假设　大影响，所以，各种搜索算法均针对影响搜索性能的因素对算　在前一帧和当前帧之问只有平移运动；假设一个块内所有的像　法进行优化，此外，ＭＶＦＡＳＴ及ＰＭＶＦＡＳＴ还通过引入阈值技　素都进行相同的运动；假设前一帧的像素能通过对当前块的像　术以提早终止搜索来减少计算量。然而，绝大多数快速搜索算　素进行线性插值得以重构。　法都不检查搜索区的所有候选项，所以，当视频序列中有快速　图ｌ显示了当前块的像素Ｃ（　）在前一帧的匹配像素位置　或随机运动时，以上算法常导致搜索陷入局部最优，它们的　Ｐ（ｉ￣ｍ—ｄ），ｍ和ｄ分别代表整像素ＭＶ和亚像素ＭＶ。所以（ｍ—　ＰＳＮＲ性能比ＦＳＢＭＡ或分层方法的ＰＳＮＲ性能要低，后者是通　ｄ）是当前块的真实的ＭＶ，相应的实心点代表前一帧中精确匹　过牺牲搜索速度来检查整个搜索区。　配的点。从图１可以得到下列关系式：　本文提出的基于距离预测的快速自适应运动估计算法　ｐ（　＋，ｎ）＝ｃ（　）（１－ｄ）＋ｃ（ｉ＋１）ｄ，ｉ∈ｂｌｏｃｋ　（１）　（ＦＡＢＤＰ），通过在当前搜索点与最佳点之间定义一个距离，并　在整像素运动估计中，ＭＶ的最小绝对值误差和ＳＡＤ值计　结合层次搜索技术，根据估算的距离自动选择相应的搜索策略　或是中断搜索，比已有的基于梯度下降搜索算法更适合于那些　具有快速或随机运动的视频序列。　２　ＦＡＢＤＰ算法　在本章，先介绍一个用于估算搜索点和最佳点之间的距离　图１　当前块的像素在前一帧的匹配位置　金项Ｈ：湖南省自然科学基金（ｔｈｅ　Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｆｏｕｎｄａｔｉｏｎ　ｏｆ　Ｈｕｎａｎ　Ｐｒｏｖｉｎｃｅ　ｏｆ　Ｃｈｉｎａ　ｕｎｄｅｒ　Ｇｒａｎｔ　Ｎｏ．０５ＪＪ４０００６）。　作者简介：谭琳（１９７０一），女，副教授，主研方向：视频压缩技术、数据库技术；李丽娟，教授。　维普资讯 http://www.cqvip.com ８４　２００７．４３（３０）　Ｃｏｍｐｕ￣ｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　基于以上思想，判断是否随机运动的过程如下：　（１）计算随机运动的阈值ｓＡＤ　，此处，ＳＡＤｍ．ｘ＝ＭＡＸ　（２）　（ｓＡＤ　ｌ，ｓＡＤ　２，ｓＡＤ肺帕，ｓＡ　），ｓＡＤ　ｌ，ｓＡＤ　２和ｓＡ　分　算方法如下：　ＳＡＤ（ｍ）＝∑Ｉｐ（ｉ＋ｍ）一ｃ（　）Ｉ　ｉＥｂｌｏｃｋ　由式（１）和式（２），得到：　别代表当前块的左、上和右上邻块的最小ＳＡＤ值，ｓＡ　是前一　帧中相同位置的块的最小ＳＡＤ值。　（３）　ＳＡＤ（ｍ）＝ｄ∑　＋１）－ｃ（　）　令ＳＡＤＮＰ＝∑Ｉｃ（ｉ＋１）－ｃ（ｉ）ｌ，即为相邻像素间的绝对值　误差和，则，距离估算为：　（２）￣ｌＪ用小菱形搜索模式计算得到运动矢量，再由此运动　矢量计算得到当前块的ＳＡＤ值（记为ｓＡＤ　）。　（３）若ｓＡＤ　ｓＡＤ　，可认为存在随机运动。　２．３．２随机ＭＶ搜索　为了高效地执行随机运动矢量搜索，采用了分层搜索方　ｄ：—ＳＡＤ（ｍ）　（４）　ＳＡＤＮＰ　案。图像的第０层是原图，第１层采用了子采样　（ｉ√）　＾（４ｉ，　应该注意的是：只有当前搜索点和最佳ＭＶ之间的距离小　４ｊ），故在该层，搜索区缩小为原图的１／１６。　于１个像素时式（４）才有效。然而，如果假定ＳＡＤ值从最佳ＭＶ　随机ＭＶ搜索的步骤为：先在第１层基于ＦＳＢＭＡ获得具　处开始单调递增，则当估算的距离ｄ大于１时，此时ｄ虽然并　有最小ＳＡＤ的第１层最佳点；再将第１层最佳点作为第０层　没有实际的数量上的含义，但仍然可由ｄ得知，当前搜索点与　的初始搜索中心，然后，在初始中心的周围采用ＳＤＳＰ进行局　最佳点的距离大于１个像素。　部搜索，以找到随机ＭＶ；如果由随机ＭＶ搜索得到的最小　因视频编码中的运动估计是在二维空间进行，以上的推理　ＡＳＤ比ｓＡＤ　小，相应的ＭＶ将是当前块的最终ＭＶ。　应扩展到二维情况。在二维空间，当前搜索点和最佳点之间的　因为新的初始搜索中心是通过检测第１层的所有搜索点　距离表达为（　，　），水平ＳＡＤＮＰ和垂直ＳＡＤＮＰ计算方法如下：　才得到的，它应该接近全局最小，所以，在第０层通过ＳＤＳＰ搜　索就够了。　ＳＡＤＮＰｘ＝　Ｉｃ（ｉ＋１√）＿ｃ（ｉ√）Ｉ　（ｉＪ）Ｅｂｌｏｃｋ　因为只有当ｓＡｐ　比ｓＡＤ　大才在简化的图像中执行　（５）　随机ＭＶ搜索，而大多数情况下ｓＡＤ　比ｓＡＤ　小，这种求　ＳＡＤＮＰｒ＝　Ｉｃ（ｉ　１）－ｃ（ｉｊ）ｌ　精的过程很少执行；且简化的图像只是原始图像的１／１６，所以　Ｃｉｏ＇）Ｅｂｌｏｃｋ　此处，ｃ（　）表示当前块的—个像素，则距离的每—个分量　随机ＭＶ搜索的计算量与总的计算量相比并不突出。　可分别预测如下：　２．４　ＦＡＢＤＰ算法描述　ＦＡＢＤＰ算法是基于以上的距离估算方案，自适应阈值技　Ⅱ　＝—ＳＡＤＮＰ—！　．Ⅱ　—。　ｘ　ＳＡＤＮＰｒ———　！　　（６）０　　术和随机ＭＶ搜索技术，并结合了ＰＭＶＦＡＳＴ的阈值技术而提　此处，（ｍ，ｎ）代表当前搜索点。按照式（６），若　或　为０，　出的。其具体算法描述如下：　ＳＡＤ（ｍ，ｎ）也应为０。然而，即使　或　为０，或当前搜索点的　先利用当前块的左、上和右上块的ＭＶ预测ＭＶ　，如果　或Ｙ分量与最佳点的相应分量匹配，如果当前搜索点的Ｙ或　Ｍｖ　处的ＳＡＤ比　１小，搜索终止；否则，将检测（０，０）点、　分量与最佳点不匹配，ＳＡＤ（ｍ，ｎ）也可能不为０。所以，预测的　左、上和右上块的ＳＡＤ，且将最小ＳＡＤ的点作为Ｍｖ　。如果　或　可能比实际的距离要大。　ＭＶ　的ＳＡＤ比　小，ＭＶ　就被当作最终的ＭＶ，搜索终止。　２．２自适应阈值技术　否则，将利用式（６）来预测Ｍ‰和ＭＶ～之间的距离（　，　在．ＰＭＶＦＡＳＴ中提出了一种自适应的阈值技术，即当前块　）。如果　和　都小于１，２像素，搜索终止。如果只有　或　的阈值由三个相邻块（左，上和右上块）的最小ＳＡＤ值共同决　小于１／２像素，就沿Ｙ或　方向进行一维搜索，直到找到该分　定，从而使之能有效地终止—个有快速运动或随机运动的序列　量才终止搜索。只有当　和　均大于１，２像素，才利用分层搜　的搜索。然而，应该注意到，阈值只考虑到了相邻块的ＳＡＤ值，　索和　ＳＤＳＰ进行随机ＭＶ搜索。　而没有考虑当前块自己的特征，如果当前块与其相邻块的特征　不同，不适当的阈值可能引起ＰＳＮＲ退化或限制其加速性能。　３实验结果　为了解决这一问题，基于前一小节的估算距离提出了一种　本文的实验采用了Ｊ、，Ｔ的ＪＭ８．１作为实验平台，采用了　新的自适应的阈值方案。在该方案中，该位置的　和　由式　Ｃａｒｐｈｏｎｅ（ＣＰ）和Ｆｏｒｅｍａｎ（ＦＭ）两个视频序列的ＣＩＦ格式，　（５）和式（６）预测。那么，如果　或　小于１，２像素，认为当前　Ｆｏｏｔｂａｌｌ（ＦＢ）和Ｔａｂｌｅ　Ｔｅｎｎｉｓ（Ｔｒ）两个视频序列的ＳＩＦ格式，　搜索点的　或Ｙ分量与有整数精确度的最佳点的　或Ｙ分量　Ｆｏｒｅｍａｎ和Ｔａｂｌｅ　ｔｅｎｎｉｓ两个视频序列的ＱＣＩＦ格式（１７６ｘ１４４）。　相同，则不再沿　或Ｙ方向搜索。所以，如果　和　均小于１／２　每个视频序列包含１００帧，帧率为３０　Ｈｚ。实验中，块大小设为　像素，搜索终止，当前搜索点成为最后的整像素ＭＶ。然而，如　１６ｘ１６，搜索范围设为＋１５，ｎ和　分别设为５１２和７６８。　、果只有　或　小于１，２像素，就沿Ｙ或　方向进行一维搜索，　表１中给出了各种运动估计算法的平均ＰＳＮＲ性能比较，　直到找到该分量才终止搜索。如果　和　均大于１，２个像素，　表２给出了各种算法每一块中平均搜索点数（包括了阈值过程　基于搜索范围进行下—步搜索。　和随机ＭＶ搜索在内的所有计算）的比较。ＦＡＢＤＰ算法中使用　２－３基于分层搜索的随机ＭＶ搜索　的Ｉ圜值　１和　是在搜索速度和ＰＳＮＲ之间进行平衡而设置　２．３．１随机运动的判断　的，通过调整阈值，该算法可以通过牺牲ＰＳＮＲ性能达到更高　因为相邻块总是高度相关，预期中当前块的ＳＡＤ值会与其　的加速比，或者通过降低加速比提高其ＰＳＮＲ性能。该结果表　相邻块的ＳＡＤ值相似，如果差异较大，则可认为存在随饥运动。　明，在对照的搜索算法中，ＦＡＢＤＰ算法需要的平均搜索点数最　（下转１６６页）　维普资讯 http://www.cqvip.com １６６　２００７，４３（３０）　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　ｆｅｒｅｎｃｅ　２００３，Ｈｙａｔｔ　Ｒｅｇｅｎｃｙ　Ｃｒｙｓｔａｌ　Ｃｉｔｙ，Ａｒｌｉｎｇｔｏｎ，ＶＡ，ＵＳＡ，　２０ｏ３．　的基础上，以适当降低所采集的虹膜图像质量为代价，实现采　集失败率和注册失败率的大幅降低；然后在虹膜识别的决策层　引入对应脸像特征模板的相似度，以补充因为虹膜图像质量的　降低而损失的生物特征信息；最后利用数据融合的方法，根据　虹膜特征模板的汉明距和脸像特征模板的相似度的实际分布　特性，建立各自的隶属度函数，在识别的决策层，提出了一种基　【７】Ｚａｄｅｈ　Ｌ　Ａ．Ｆｕｚｚｙ　ｓｅｔｓ［Ｊ］．Ｉｎｆｏｒｍａｔｉｏｎ　ａｎｄ　Ｃｏｎｔｒｏｌｓ，１９６５，８：３３８－３５３．　【８】Ｚａｄｅｈ　Ｌ　Ａ．Ｆｕｚｚｙ　ｓｅｔｓ　ａｓ　ａ　ｂａｓｉｓ　ｆｏｒ　ａ　ｔｈｅｏｒｙ　ｏｆ　ｐｏｓｓｉｂｉｌｉｔｙ【ＪＪ．　Ｆｕｚｚｙ　Ｓｅｔｓ　ａｎｄ　Ｓｙｓｔｅｍｓ，１９７８，１：３－２８．　【９】Ｐａｏ　Ｙ　Ｈ．Ａｄａｐｔｉｖｅ　ｐａｔｔｅｒｎ　ｒｅｃｏｇｎｉｔｉｏｎ　ａｎｄ　ｎｅｕｒａｌ　ｎｅｔｗｏｒｋｓ［Ｍ］．ＩＳ．１．】：　Ａｄｄｉｓｏｎ－Ｗｅｓｌｅｙ　Ｐｕｂｌｉｓｈｉｎｇ　Ｃｏｍｐａｎｙ　Ｉｎｃ，１９８９．　于隶属度函数的塔式分层融合决策识别的算法。实验结果表　【ｌ０】Ｖａｌｅｔ　Ｌ，Ｍａｕｒｉｓ　Ｇ，Ｂｏｌｏｎ　Ｐ．Ａ　ｓｔａｔｉｓｔｉｃａｌ　ｏｖｅｒｖｉｅｗ　ｏｆ　ｒｅｃｅｎｔ　ｌｉｔｅｒａ—　明，这种方法能够有效地提升识别算法的性能，使得在大幅降　ｔｕｒｅ　ｉｎ　ｉｎｆｏｒｍａｔｉｏｎ　ｆｕｓｉｏｎ【ＪＪ．ＩＥＥＥ　ＡＥＳＳ　Ｓｙｓｔｅｍ　Ｍａｇａｚｉｎｅ，２００１：　低虹膜的采集失败率和注册失败率的同时，识别算法的整体性　７一ｌ４．　能依然能够保持目前虹膜识别技术的高准确率。　【１１】Ｄｕｂｏｉｓ　Ｄ，Ｐｒａｄｅ　Ｈ．Ｆｕｚｚｙ　ａｎｄ　ｓｙｓｔｅｍｓ：ｔｈｅｏｒｙ　ａｎｄ　ａｐｐｌｉｃａｔｉｏｎｓ［Ｍ］．　（收稿日期：２００７年２月）　Ｎｅｗ　Ｙｏｒｋ：Ａｃａｄｅｍｉｃ　Ｐｒｅｓｓ，１９８０．　【１２】Ｋａｎｄｅｌ　Ａ．Ｆｕｚｚｙ　ｔｅｃｈｎｉｑｕｅｓ　ｉｎ　ｐａｔｔｅｒｎ　ｒｅｃｏｇｎｉｔｉｏｎ【Ｍ】．Ｎｅｗ　Ｙｏｒｋ：　参考文献：　Ｗｉｌｌｅｙ　Ｉｎｔｅｒｓｃｉｅｎｃｅ，１９８２．　【１】Ｄｕｎｃａｎ　Ｃａｍｐｂｅｌ１．Ｔｈｅ　ｉｍｐｏｒｔａｎｃｅ　ｏｆ　ｂｉｏｍｅｔｉｒｃｓ　ｉｎ　ｔｈｅ　Ｕ．Ｓ．ｇｏｖｅｒｎ－　【１３】Ｋａｎｄｅｌ　Ａ．Ｆｕｚｚｙ　ｍａｔｈｅｍａｔｉｃａｌ　ｔｅｃｈｎｉｑｕｅｓ　ｗｉｔｈ　ａｐｐｌｉｃａｔｉｏｎｓ【Ｍ】．　Ｒｅａｄｉｎｇ，ＭＡ：Ａｄｄｉｓｏｎ－Ｗｅｓｌｅｙ，１９８６．　ｍｅｎｔ’ｓ　ｒｅｓｐｏｎｓｅ　ｔｏ　９１　１［Ｃ］／／Ｐｍｃｅｅｄｉｎｇ　ｏｆ　Ｂｉｏｍｅｔｉｒｃｓ　Ｃｏｎｓｏｒｔｉｕｍ　Ｃｏｎ—　ｆｅｒｅｎｃｅ　２００５，Ｈｙａｔｔ　Ｒｅｇｅｎｃｙ　Ｃｒｙｓｔａｌ　Ｃｉｔｙ，Ａｒｌｉｎｇｔｏｎ，ＶＡ，ＵＳＡ，２００５．　【１４】Ｍａｎｄａｎｉ　Ｅ　Ｈ，Ｇａｉｎｅｓ　Ｂ　Ｒ．Ｆｕｚｚｙ　ｒｅａｓｏｎｉｎｇ　ａｎｄ　ｉｔｓ　ａｐｐｌｉｃａｔｉｏｎｓ［Ｍ］．　Ｎｅｗ　Ｙｏｒｋ：Ａｃａｄｅｍｉｃ　Ｐｒｅｓｓ，１９８１．　【２】Ｈｉｇｇｉｎｓ　Ｐ　Ｔ．Ａｎ　ｉｎｔｒｏｄｕｃｔｉｏｎ　ｏｆ　ｂｉｏｍｅｔｉｒｃｓ【Ｃ］ＨＰｒｏｃｅｅｄｉｎｇｓ　ｏｆ　Ｂｉｏ—　【１５】Ｚｉｍｍｅｒｍａｎ　Ｈ　Ｊ．Ｆｕｚｚｙ　ｓｅｔ　ｔｈｅｏｒｙ　ａｎｄ　ｉｔｓ　ａｐｐｌｉｃａｔｉｏｎｓ［Ｍ］．Ｈｉｎｇ—　ｍｅｔｉｒｃｓ　Ｃｏｎｓｏｒｔｉｕｍ　Ｃｏｎｆｅｒｅｎｃｅ　２００５，Ｈｙａｔｔ　Ｒｅｇｅｎｃｙ　Ｃｒｙｓｔｌａ　Ｃｉｔｙ，　ｈａｍ，ＭＡ：Ｋｌｕｗｅｒ　Ｎｉｊｈｏｆｆ，１９８４．　Ａｒｌｉｎｇｔｏｎ，ＶＡ，ＵＳＡ，２００５．　【１６】Ｖｉｏｌａ　Ｐ，Ｊｏｈｎ　Ｍ．Ｒｏｂｕｓｔ　ｒｅａｌ—ｔｉｍｅ　ｏｂｊｅｃｔ　ｄｅｔｅｃｔｉｏｎ［Ｃ］／／Ｓｅｃｏｎｄ　Ｉｎ—　【３】Ｊａｉｎ　Ａ　Ｋ，Ｐａｎｋａｎｔｉ　Ｓ，Ｐｒａｂｈａｋａｒ　Ｓ，ｅｔ　ａ１．Ｂｉｏｍｅｔｉｒｃｓ：ａ　ｇｒａｎｄ　ｃｈａｌ—　ｔｅｒｎａｔｉｏｎａｌ　Ｗｏｒｋｓｈｏｐ　ｏｎ　Ｓｔａｔｉｓｔｉｃａｌ　ａｎｄ　Ｃｏｍｐｕｔａｔｉｏｎａｌ　Ｔｈｅｏｒｉｅｓ　ｏｆ　ｌｅｎｇｅ［Ｃ￣／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｐａｔｔｅｒｎ　Ｒｅｃｏｇ—　Ｖｉｓｉｏｎ—ｍｏｄｅｌｉｎｇ，Ｌｅａｒｎｉｎｇ，Ｃｏｍｐｕｔｅｒ　ａｎｄ　Ｓａｍｐｌｉｎｇ，２００１，７（１３）：　ｎｉｔｉｏｎ，Ｃａｍｂｒｉｄｇｅ，ＵＫ，Ａｕｇ　２００４．　ｌ－２５．　【４】Ｙｅ　Ｘｕｅ－ｙｉ．Ｉｉｒｓ　ａｎｄ　ｆａｃｅ　ｂａｓｅｄ　ｍｕｌｔｉ．ｂｉｏｍｅｔｒｉｃｓ　ｉｄｅｎｔｉｉｆｃａｔｉｏｎ　ａｎｄ　【１７】Ｄａｕｇｍａｎ　Ｊ．Ｉｒｉｓ　ｒｅｃｏｇｎｉｔｉｏｎ　ｂｏｒｄｅｒ　ｃｒｏｓｓｉｎｇ　ｓｙｓｔｅｍ　ｉｎ　ｔｈｅ　ＵＡＥ［Ｊ］．　ｆｕｓｉｏｎ　ａｌｇｏｒｉｔｈｍ［ＤＪ．Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ　ｏｆ　Ｃｈｉｎａ，　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ａｉｒｐｏｒｔ　Ｒｅｖｉｅｗ，２００４（２）．　２００６．　【１　８】Ｄａｕｇｍａｎ　Ｊ．Ｂｉｏｍｅｔｒｉｃ　ｐｅｒｓｏｎａｌ　ｉｄｅｎｔｉｉｆｃａｔｉｏｎ　ｓｙｓｔｅｍ　ｂａｓｅｄ　ｏｎ　ｉｉｒｓ　【５】Ｄａｕｇｎｍｎ　Ｊ．Ｈｏｗ　ｉｉｒｓ　ｒｅｃｏｇｎｉｔｉｏｎ　ｗｏｒｋｓ　．ＩＥＥＥ　Ｔｒｎａｓａｃｔｉｏｎｓ　ｏｎ　Ｃｉｒ—　ａｎａｌｙｓｉｓ，５２９１５６０［Ｐ】，１９９４．　ｃｕｉｔｓ　ａｎｄ　Ｓｙｓｔｅｍｓ　ｆｏｒ　Ｖｉｄｅｏ　Ｔｅｃｈｎｏｌｏｇｙ，２００４，１４（１）．　【１９】Ｄａｕｇｍａｎ　Ｊ．Ｈｉｇｈ　ｃｏｎｆｉｄｅｎｃｅ　ｖｉｓｕａｌ　ｒｅｃｏｇｎｉｔｉｏｎ　ｏｆ　ｐｅｒｓｏｎｓ　ｂｙ　ａ　【６】Ｍａｈｌｍｅｉｓｔｅｒ　Ｕ．Ｃｏｕｎｔｅｒｍｅａｓｕｒｅ　ｐｅｒｆｏｒｍａｎｃｅ　ｅｖａｌｕａｔｉｏｎ　ｆｏｒ　ｉｉｒｓ　ｔｅｓｔ　ｏｆ　ｓｔａｔｉｓｔｉｃａｌ　ｉｎｄｅｐｅｎｄｅｎｃｅ【ＪＪ．ＩＥＥＥ　Ｔｒａｎｓ　Ｐａｔｔｅｒｎ　Ａｎａｌｙｓｉｓ　ｒｅｃｏｇｎｉｔｉｏｎ　ｓｙｓｔｅｍｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　Ｂｉｏｍｅｔｉｒｃｓ　Ｃｏｎｓｏｒｔｉｕｍ　Ｃｏｎ—　ａｎｄ　Ｍａｃｈｉｎｅ　Ｉｎｔｅｌｌｉｇｅｎｃｅ，１９９３，１５：１１４８～１１６１．　（上接８４页）　之间的距离的方法，提出了一种判断是否存在随机运动的方　表１各种算法ＰＳＮＲ性能比较　法，还提出了一种只有在存在快速或随机ＭＶ时才执行的分层　搜索方案。虽然由此会增加一些额外的计算量，但因为快速或　随机ＭＶ在视频序列中并不常见，并且，正确地估计距离也提　高了终止搜索的性能，从而也提高了整个搜索速度，所以，这额　外增加的用于分层搜索的计算量可不予考虑。实验结果表明，　新的算法比已有的基于ＧＤＳ算法速度更快，并提供了更好的　ＰＳＮＲ性能，特别是当视频序列中存在快速或随机ＭＶ时。　表２各种算法每一块中平均搜索点数比较　（收稿日期：２００７年３月）　参考文献：　【ｌ】Ｌｅｅ　Ｙｕｎ－ｇｕ，Ｒａ　Ｊ　Ｂ．Ｆａｓｔ　ｍｏｔｉｏｎ　ｅｓｔｉｍａｔｉｏｎ　ｒｏｂｕｓｔ　ｔｏ　ｒａｎｄｏｍ　ｎｏ—　ｔｉｏｎｓ　ｂａｓｅｄ　ｏｎ　ａ　ｄｉｓｔａｎｃｅ　ｐｒｅｄｉｃｔｉｏｎ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓ　Ｃｉｒｃｕｉｔｓ　Ｓｙｓｔ　Ｖｉｄｅｏ　Ｔｅｃｈｎｏｌ，２００６，１６（７）：８６９—８７５．　，　【２】Ａｈｍａｄ　Ｉ，Ｚｈｅｎｇ　Ｗｅｉ－ｇｕｏ，Ｌｕｏ　Ｊｉａｎ－ｃｏｎｇ，ｅｔ　ａ１．Ａ　ｆｓａｔ　ａｄａｐｔｉｖｅ　Ｉｎ０．－　ｔｉｏｎ　ｅｓｔｉｍａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ【ＪＪ．ＩＥＥＥ　Ｔｒａｎｓ　Ｃｉｒｃｕｉｔｓ　Ｓｙｓｔ　Ｖｉｄｅｏ　Ｔｅｃｈ—　少，且其总体ＰＳＮＲ性能最好。更重要的是，ＦＡＢＤＰ算法较好　ｎｏｌ，２００６，１６（３）：４２０－４３８．　地提高了Ｔａｂｌｅ　Ｔｅｎｎｉｓ和Ｆｏｏｔｂａｌｌ视频序列的ＰＳＮＲ性能，这　【３】向友君，郭宝龙．一种快速多分辨率运动估计算法　．中国图象图形　是因为其高效的随机ＭＶ搜索。　学报，２０ｏ３（特刊）：５３０—５３３．　【４】喜超，姜昱明．一种用于Ｈ．２６４的快速运动估计算法　．计算机工程　与应用，２００６，４２（１７’）：１５７—１５９．　４结束语　【５】Ｊｏｉｎｔ　Ｖｉｄｅｏ　Ｔｅａｍ（ＪＶＴ）Ｔｅｓｔ　Ｍｏｄｅｌ，ＪＭ８．１【ＥＢ／ＯＬ］．［２００６一ｌｌ】．ｈｔｔｐ：／／　本文提出了一种在搜索过程中估计当前搜索点和最佳点　ｂｓ．ｈｈｉ．ｄｅ／一ｓｕｅｈｒｉｎｇ／ｔｍｌ／ｄｏｗｎｌｏａｄ／．