一种基于FQFD_FLL_PLL的混合载波跟踪算法
混合群智能优化算法研究及应用
混合群智能优化算法研究及应用 优化问题广泛地存在于科学研究和工程实践中。群智能优化算法是优化算法中最新的一个分支,也是最热门的发展方向。群智能优化算法是通过模拟自然界中生物间相互合作、共享信息等群体行为而建立起来的随机搜索算法,相较于经典优化算法具有结构简单、易于实现等优点。不同的群智能优化算法是模拟不同生物行为形成的,所以它们各具特点和适用场景。然而,单一的群智能优化算法均有其局限性,如搜索精度不够高、收敛速度慢、性能受参数影响较大和容易陷入局部最优等。将不同群智能优化算法有机结合,设计混合群智能优化算法是一种提高算法性能的有效方法,具有重要的研究意义。本文的主要研究内容及创新点包括以下几个方面:(1)针对单目标数值优 化问题提出了一种基于跟随蜂搜索的自适应粒子群算法(Follower Bee Search Based Adapitve Particle Swarm Optimization,F-APSO)。首先在经典粒子群算法粒子飞行轨迹分析的基础上提出了一种自适 应的粒子群算法(Adapitve Particle Swarm Optimization,APSO), 提高了算法在求解单峰问题时的性能。然后提出了一种针对自适应粒子群算法的稳定性分析方法,基于该方法对APSO进行了稳定性分析,给出了能够保证算法稳定的参数取值条件。接着通过引入人工蜂群算法中的跟随蜂搜索,提高了算法的开拓性,并将APSO的稳定性条件拓展到了 F-APSO中。仿真实验表明F-APSO在求解单目标数值优化问题时在解的质量和时间消耗上都具有良好表现。将F-APSO用于解决矿山生产排程优化问题,与原有生产方案相比优化后的方案在不同铁
二值图像连通域标记算法与代码
二值图像连通域标记算法与代码 这里列举二值图像连通域标记算法包括直接扫描标记算法和二值图像连通域标记快速算法 一、直接扫描标记算法把连续区域作同一个标记，常见的四邻域标记算法和八邻域标记算法。 1、四邻域标记算法： 1）判断此点四邻域中的最左，最上有没有点，如果都没有点，则表示一个新的区域的开始。 2）如果此点四邻域中的最左有点，最上没有点，则标记此点为最左点的值；如果此点四邻域中的最左没有点，最上有点，则标记此点为最上点的值。 3）如果此点四邻域中的最左有点，最上都有点，则标记此点为这两个中的最小的标记点，并修改大标记为小标记。 2、八邻域标记算法： 1）判断此点八邻域中的最左，左上，最上，上右点的情况。如果都没有点，则表示一个新的区域的开始。 2）如果此点八邻域中的最左有点，上右都有点，则标记此点为这两个中的最小的标记点，并修改大标记为小标记。 3）如果此点八邻域中的左上有点，上右都有点，则标记此点为这两个中的最小的标记点，并修改大标记为小标记。 4）否则按照最左，左上，最上，上右的顺序，标记此点为四个中的一个。代码实现： #include #include
基于FPGA的二值图像连通域标记快速算法实现
基于FPGA的二值图像连通域标记快速算法实现 摘要：在图像自动目标识别和跟踪过程中，首先对图像目标进行阈值分割提取，得到的二值图像通常包含多个连通区域，系统利用图像目标的形状特性对可疑高威胁的飞行目标进行自动识别。因此，需要对各连通区域块进行分别检测判断，本文采用改进的适合FPGA实现的快速标记算法对各连通域进行检测提取。 关键词：FPGA，二值图像连通域，快速标记算法，可编程逻辑 贺明 1 引言 在图像自动目标识别和跟踪过程中，首先对图像目标进行阈值分割提取，得到的二值图像通常包含多个连通区域，系统利用图像目标的形状特性对可疑高威胁的飞行目标进行自动识别。因此，需要对各连通区域块进行分别检测判断，本文采用改进的适合FPGA实现的快速标记算法对各连通域进行检测提取。 实现二值图像连通体检测通常采用的方法有下几种[1] [2] [3]：区域生长法：首先对图像进行逐行(列)扫描，每遇到一个未标记的“1”像素点，就分配其一个未使用过的标号，然后对其领域进行检测，如有未标记过的“1”像素，则赋予相同的标号。反复进行这一操作．直到不存在应该传播标号的“1”像素。然后继续图像行(列)扫描，如检测判未标记的“1”像素则赋予其新的标号，并进行与以上相同的处理。整个图像扫描结束，算法也就终止。这种方法可准确地检测出各种类型的连通体．但处理时间也较长．因为要逐一检测每一“1”像素的邻域，且出现“1”像素的重复扫描。跟踪算法：二值图像中每个取值为“1”的像素被标记一个与其坐标相关的标号，如由n，m串构成的数。热后，扫描标记后的图像，并将每十像素的标号改为其邻域内的最小标号。反复执行这个过程，直到不需要作标记更改为止。用这种方法处理小而凸的目标时，收敛速度较慢。 本文以适合FPGA实现为目的，提出一种具有计算规则性的快速二值图像连通域标记算法。与传统的二值图像标记算法相比，该算法具有运算简单性、规则性和可扩展性的特点，适合以FPGA实现。选用在100MHz工作时钟下，处理384×288像素的红外图像能够达到400帧／秒以上的标记速度，足够满足实时目标识别系统的要求。处理速度可以满足大部分实时目标识别系统的要求。该算法同样可以软件编程方式应用于嵌入式DSP系统中。 2 算法描述 首先，在进行标记算法以前，利用硬件开辟独立的图像标记缓存和连通关系数组，接着在视频流的采集传输过程中，以流水线的方式按照视频传输顺序对图像进行逐行像素扫描，然后对每个像素的邻域分别按照逆时针方向和水平方向进行连通性检测和等价标记关系合并，检测出的结果对标记等价数组和标记缓存进行更新，在一帧图像采集传输结束后，得到图像的
关于mean shift视频目标跟踪算法的设计与实现-----中期报告
河北工业大学城市学院本科毕业设计（论文）中期报告 毕业设计（论文）题目：基于Mean-Shift的视频目标跟踪算法的设计与实现 专业(方向)：网络工程 学生信息：学号：088302 姓名：坎启娇班级：网络C081班 指导教师信息：教师号：02019 姓名：侯向丹职称：副教授 报告提交日期：2012年4月30号 1.前言 1.1选题的背景 运动目标的检测与跟踪是应用视觉领域[1]的一个重要的课题。目标跟踪涉及到图像处理、模式识别、人工智能以及自适应控制多领域问题的综合解决,其中对于复杂背景(或环境)下的图像处理一直是视觉信息处理和理解的难点。在实际应用中，复杂的现场环境以及跟踪应用的实时性要求，对算法都提出了更高的要求。因此，研究复杂背景下运动目标的检测和跟踪的课题有重要意义。本文的研究目的是建立一个视频图像监控系统，根据目标的运动方向，系统将目标锁定在视野中。目标跟踪是在一段视频序列中寻找与指定目标最相似的部分，是计算机视觉的一个重要研究内容。它在视频监控、人机界面、增强现实、基于目标的视频压缩等众多领域中有着广泛的应用。 1.2运动目标跟踪算法 1.2.1常见的运动目标跟踪算法 目前视频目标跟踪方法[2]大体上可以分为基于区域匹配的目标跟踪、基于轮廓的匹配跟踪、基于特征的匹配跟踪、基于模型的跟踪,以及基于运动特性的跟踪。下面详细介绍这五类算法。 (1)基于区域匹配跟踪 区域匹配跟踪的基本思想是:预先通过人为的方法或图像分割的方法得到包含目标的模板，然后在后续的视频序列中运用相关匹配准则进行目标的匹配跟踪。决定区域匹配跟踪效果好坏最主要的因素就是匹配度量和搜索算法的选取。最常用的相关准则是平方和准则法(SSD),颜色法、形状法等。 优点:提取了较完整的目标模板，因此相对其它跟踪算法能得到更多的图像信息，当目标未被遮挡时跟踪精度高且稳定，因而广泛应用于小目标的跟踪或对比度比较差的目标跟
mean shift及其改进算法图像跟踪原理和应用
mean shift及其改进算法图像跟踪原理和应用Mean Shift 简介 Mean Shift 这个概念最早是由Fukunaga等人[1]于1975年在一篇关于概率密度梯度函数的估计中提出来的,其最初含义正如其名,就是偏移的均值向量,在这里Mean Shift是一个名词,它指代的是一个向量,但随着Mean Shift理论的发展,Mean Shift的含义也发生了变化,如果我们说Mean Shift算法,一般是指一个迭代的步骤,即先算出当前点的偏移均值,移动该点到其偏移均值,然后以此为新的起始点,继续移动,直到满足一定的条件结束. 然而在以后的很长一段时间内Mean Shift并没有引起人们的注意,直到20年以后,也就是1995年,另外一篇关于Mean Shift的重要文献才发表.在这篇重要的文献中,Yizong Cheng对基本的Mean Shift算法在以下两个方面做了推广,首先Yizong Cheng定义了一族核函数,使得随着样本与被偏移点的距离不同,其偏移量对均值偏移向量的贡献也不同,其次Yizong Cheng还设定了一个权重系数,使得不同的样本点重要性不一样,这大大扩大了Mean Shift的适用范围.另外Yizong Cheng 指出了Mean Shift可能应用的领域,并给出了具体的例子. Comaniciu等人把Mean Shift成功的运用的特征空间的分析,在图
像平滑和图像分割中Mean Shift 都得到了很好的应用. Comaniciu 等在文章中证明了,Mean Shift 算法在满足一定条件下,一定可以收敛到最近的一个概率密度函数的稳态点,因此Mean Shift 算法可以用来检测概率密度函数中存在的模态. Comaniciu 等人还把非刚体的跟踪问题近似为一个Mean Shift 最优化问题,使得跟踪可以实时的进行. 在后面的几节,本文将详细的说明Mean Shift 的基本思想及其扩展,其背后的物理含义,以及算法步骤,并给出理论证明.最后本文还将给出Mean Shift 在聚类,图像平滑,图像分割,物体实时跟踪这几个方面的具体应用. Mean Shift 的基本思想及其扩展 基本Mean Shift 给定d 维空间d R 中的n 个样本点i x ,i=1,…,n,在x 点的Mean Shift 向量的基本形式定义为: ()()1 i h h i x S M x x x k ∈≡ -∑ (1) 其中,h S 是一个半径为h 的高维球区域,满足以下关系的y 点的集合, ()() (){ } 2:T h S x y y x y x h ≡--≤ (2) k 表示在这n 个样本点i x 中,有k 个点落入h S 区域中.
近两年跟踪速度较快的算法
近两年跟踪速度较快的算法小结 近两年跟踪速度较快的算法有CN [1]，KCF [2]，STC [3]，ODFS [4]等等，均足以满足现实场景中实时跟踪的应用。 各算法执行速度： 各算法的主要思想： CN 跟踪器是CSK [5]跟踪器的改进算法。它联合颜色特征（ColorName ）和灰度特征来描述目标，在文献[1]作者通过大量的实验证明了Color Name 在视觉跟踪中的卓越性能，并且对ColorName 进行了PCA 降维，去除了ColorName 中的冗余信息，使得对目标的外观描述更加精确和鲁棒。在分类器的训练中，在CSK 算法的代价函数的基础上引入一个固定的权值β，使得分类器的训练和更新更加准确和鲁棒。CN 跟踪器对很多复杂的视频序列都有很好的跟踪结果，比如：光照变化，遮挡，非刚性形变，运动模糊，平面内旋转，出平面旋转和背景杂乱。CN 跟踪器也有不足的地方，比如：尺度变化，快速运动，出视角和低分辨率，等视频的跟踪效果不佳。 KCF 跟踪器是原CSK 跟踪器的作者对CSK 跟踪器的完善，这里简单介绍一下CSK 跟踪器的主要思想。CSK 跟踪器最大亮点就是提出了利用循环移位的方法进行稠密采样并结合FFT 快速的进行分类器的训练。稠密采样的采样方式能提取目标的所有信息，这对目标的跟踪至关重要。虽然CSK 的速度很快，但是CSK 只是简单的使用了灰度特征，对目标的外观描述能力显然不足。对此作者改进了CSK 提出了KCF ，从原来的单通道灰度特征换成了多通道Hog 特征。KCF 算法通过核函数对多通道的Hog 特征进行了融合，使得训练所得的分类器对待检测目标的解释力更强。KCF 跟踪器对光照变化，遮挡，非刚性形变，运动模糊，背景杂乱和旋转等视频均能跟踪良好，但对尺度变化，快速运动，刚性形变等视频跟踪效果不佳。 STC 跟踪器是一个简单快速而且鲁棒的算法，它利用稠密的空时场景模型来进行跟踪。在贝叶斯框架下，它利用目标和目标局部的稠密信息的空时关系来建模。置信图在被计算时考虑了上一帧目标的位置的先验信息，这有效的减轻了目标位置的模糊。STC 跟踪器使用了最简单的灰度特征，但是灰度并不能很好对外观进行描述。这里可以改进为其他比较好的特征（Colorname 或者Hog ），但是就会遇到多通道特征融合的问题。一般的Tracking-by-Detection 跟踪算法基本都不能实现尺度的变化，而STC 跟踪器就提出了一种有效的尺度变化方案，也是文章[3]中最大的亮点。这里简单介绍一下，通过连续两帧的目标最 佳位置t x *处的置信值()t m x *的比值来计算当前帧中目标的估计尺度 ()()()12' 1t t t s m x m x ** -=，为了不引入噪声和避免过度敏感的自适应引入连续n 帧的平均估 计尺度'1 1n t t i i s s n -==∑，最后通过滤波获得最终的目标估计尺度()11t t t s s s λλ+=-+。STC
S T A P L E 目 标 跟 踪 算 法
计算机视觉中，究竟有哪些好用的目标跟踪算法（下） 在介绍SRDCF之前，先来分析下相关滤波有什么缺点。总体来说，相关滤波类方法对快速变形和快速运动情况的跟踪效果不好。 快速变形主要因为CF是模板类方法。容易跟丢这个比较好理解，前面分析了相关滤波是模板类方法，如果目标快速变形，那基于HOG的梯度模板肯定就跟不上了，如果快速变色，那基于CN的颜色模板肯定也就跟不上了。这个还和模型更新策略与更新速度有关，固定学习率的线性加权更新，如果学习率太大，部分或短暂遮挡和任何检测不准确，模型就会学习到背景信息，积累到一定程度模型跟着背景私奔了，一去不复返。如果学习率太小，目标已经变形了而模板还是那个模板，就会变得不认识目标。(举个例子，多年不见的同学，你很可能就认不出了，而经常见面的同学，即使变化很大你也认识，因为常见的同学在你大脑里面的模型在持续更新，而多年不见就是很久不更新) 快速运动主要是边界效应(Boundary Effets)，而且边界效应产生的错误样本会造成分类器判别力不够强，下面分训练阶段和检测阶段分别讨论。 训练阶段，合成样本降低了判别能力。如果不加余弦窗，那么移位样本是长这样的： 除了那个最原始样本，其他样本都是“合成”的，100*100的图像块，只有1-10000的样本是真实的，这样的样本集根本不能拿来训练。如果加了余弦窗，由于图像边缘像素值都是0，循环移位过程中只要目标保持完
整那这个样本就是合理的，只有目标中心接近边缘时，目标跨越边界的那些样本是错误的，这样虽不真实但合理的样本数量增加到了大约2-3(padding= 1)，即使这样仍然有1-3(3000-10000)的样本是不合理的，这些样本会降低分类器的判别能力。再者，加余弦窗也不是“免费的”，余弦窗将图像块的边缘区域像素全部变成0，大量过滤掉分类器本来非常需要学习的背景信息，原本训练时判别器能看到的背景信息就非常有限，我们还加了个余弦窗挡住了背景，这样进一步降低了分类器的判别力(是不是上帝在我前遮住了帘。不是上帝，是余弦窗)。 检测阶段，相关滤波对快速运动的目标检测比较乏力。相关滤波训练的图像块和检测的图像块大小必须是一样的，这就是说你训练了一个100*100的滤波器，那你也只能检测100*100的区域，如果打算通过加更大的padding来扩展检测区域，那样除了扩展了复杂度，并不会有什么好处。目标运动可能是目标自身移动，或摄像机移动，按照目标在检测区域的位置分四种情况来看： 1、如果目标在中心附近，检测准确且成功。 2、如果目标移动到了边界附近但还没有出边界，加了余弦窗以后，部分目标像素会被过滤掉，这时候就没法保证这里的响应是全局最大的，而且，这时候的检测样本和训练过程中的那些不合理样本很像，所以很可能会失败。 3、如果目标的一部分已经移出了这个区域，而我们还要加余弦窗，很可能就过滤掉了仅存的目标像素，检测失败。 4、如果整个目标已经位移出了这个区域，那肯定就检测失败了。
第7章 边沿检测与提取,轮廓跟踪
第7章边沿检测与提取，轮廓跟踪 我们在第三章介绍平滑与锐化时引入了模板操作，今天还要用到它。 7.1边沿检测 我们给出一个模板和一幅图象。不难发现原图中左边暗，右边亮，中间存在着一条明显的边界。进行模板操作后的结果如下： 。 可以看出，第3、4列比其他列的灰度值高很多，人眼观察时，就能发现一条很明显的亮边，其它区域都很暗，这样就起到了边沿检测的作用。 为什么会这样呢？仔细看看那个模板就明白了，它的意思是将右邻点的灰度值减左邻点的灰度值作为该点的灰度值。在灰度相近的区域内，这么做的结果使得该点的灰度值接近于0；而在边界附近，灰度值有明显的跳变，这么做的结果使得该点的灰度值很大，这样就出现了上面的结果。 这种模板就是一种边沿检测器，它在数学上的涵义是一种基于梯度的滤波器，又称边沿算子，你没有必要知道梯度的确切涵义，只要有这个概念就可以了。梯度是有方向的，和边沿的方向总是正交(垂直)的，例如，对于上面那幅图象的转置图象，边是水平方向的，我们可以用 梯度是垂直方向的模板检测它的边沿。 例如，一个梯度为45度方向模板，可以检测出135度方向的边沿。 1.Sobel算子
在边沿检测中，常用的一种模板是Sobel算子。Sobel算子有两个，一个是检测水平边沿的 ；另一个是检测垂直平边沿的。与和 相比，Sobel算子对于象素的位置的影响做了加权，因此效果更好。 Sobel算子另一种形式是各向同性Sobel(Isotropic Sobel)算子，也有两个，一个是检测水平边 沿的，另一个是检测垂直平边沿的。各向同性Sobel 算子和普通Sobel算子相比，它的位置加权系数更为准确，在检测不同方向的边沿时梯度的幅度一致。 下面的几幅图中，图7.1为原图；图7.2为普通Sobel算子处理后的结果图；图7.3为各向同性Sobel算子处理后的结果图。可以看出Sobel算子确实把图象中的边沿提取了出来。 图7.1原图 图7.2普通Sobel算子处理后的结果图
组合优化近似搜索算法中的超启发式发展趋势
文章编号:100622475(2004)0620007205 收稿日期:2003206230 作者简介:李菊芳(19782),女,河南林州人,国防科技大学人文与管理学院博士研究生,研究方向:系统管理与综合集成技术,智能优化算法;谭跃进(19582),男,湖南长沙人,教授,博士生导师,研究方向:系统管理与综合集成技术。 组合优化近似搜索算法中的超启发式发展趋势 李菊芳,谭跃进 (国防科技大学人文与管理学院系统工程研究所,湖南长沙 410073) 摘要:对组合优化中近似搜索算法采用的超启发式策略进行了总结和分类,并着重从强化和变化两个概念出发分析了不同超启发式的优缺点,探讨了其发展趋势,目的是为开发博采众长的混合近似搜索算法提供参考和指导。关键词:近似搜索算法;超启发式;强化;变化;混合算法中图分类号:TP301.6 文献标识码:A U ptrend on Metaheuristics in Approxim ate Search Algorithms for Combinatori al Optimization LI Ju 2fang ,T AN Y ue 2jin (Institute of Management Science ,National University of Defense T echnology ,Changsha 410073,China ) Abstract :This paper classifies and summarizes the metaheuristics in approximate search alg orithms for combinatorial optimization ,and em phasizes analyzing s ome strengths and weaknesses of different approaches from tw o concepts as intensification and diversification.The purpose is to find the uptrend and provide s ome references and guidance for developing hybrid alg orithms combining strengths of different mataheuristics. K ey w ords :approximate search alg orithm ;metaheuristic ;intensification ;diversification ;hybrid alg orithm 0 引 言 组合优化问题的求解算法可以分为两大类:一类 是精确算法,这类算法将对解空间进行完整搜索,可以保证找到小规模问题的最优解;另一类是近似算法,这类算法放弃了对解空间搜索的完整性,因此不能保证最终解的全局最优性。由于组合优化问题中大量存在着NP 2Hard 问题,因此精确搜索算法在问题规模较大时往往无法实现。而近似算法尽管不能证明解的最优性,但很多情况下却能够以合理的计算代价找出较好的近优解,因而逐渐被理论研究和实践应用所广泛关注。 组合优化问题的近似求解技术中,较常用、较有代表性的是邻域搜索(neighborhood search )算法,这类算法从某初始解出发,利用一些规则指导搜索过程反复对当前解的邻域进行搜索并替换当前解,最终逐步实现向最优解移动。基本局部搜索(basic local search )算法或称爬山法(hill climbing )可以看作是最简单的邻域搜索算法,它采用一种迭代式改进的简单 思想,以贪婪的方式在当前解的近邻中进行搜索,每步移动只接受比当前解更好的解。基本局部搜索的最大缺点在于其往往很快就会到达局部极值并终止整个搜索过程,从而放弃对解空间中其它区域的搜索,所找到的局部极值解则往往离全局最优解还有很大距离。针对这个缺点,许多改进的邻域搜索算法在基本局部搜索算法的基础上,采用了一些更好的规则和方法来指导搜索过程摆脱局部极值,实现在整个解空间中对优良解的探索,如模拟退火、禁忌搜索、遗传算法等等,它们所使用的用于指导搜索的规则和方法又被称为超启发式(metaheuristics )。目前对超启发式尚没有统一的标准定义,从字面理解,英文中heuristic (译为启发式)的意思是探索性过程或方法,而前缀meta 是超出、在一个更高层次的意思,算法中采用超启发式的目的是要在一个更高的层次对解空间进行探索。 总的说来,超启发式一般具有如下基本属性[2]:(1)它是一种指导搜索过程的策略;(2)其目标是高效地探索解空间来寻找最优(次优)解;(3)构造超启发 计算机与现代化 2004年第6期 J IS UAN J I Y U XI ANDAIH UA 总第106期
轮廓特征和拓扑关系的图像检索方法
９０２００８，４４（５）Ｃｏｍｐｕｔｅｒ－ＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用 一种基于轮廓特征和拓扑关系的图像检索方法 曾接贤，毕东格 ＺＥＮＧＪｉｅ－ｘｉａｎ，ＢＩＤｏｎｇ－ｇｅ 南昌航空大学无损检测技术教育部重点实验室，南昌３３００６３ ＫｅｙＬａｂｏｒａｔｏｒｙｏｆＮｏｎｄｅｓｔｒｕｃｔｉｖｅＴｅｓｔ，ＭｉｎｉｓｔｒｙｏｆＥｄｕｃａｔｉｏｎ，ＮａｎｃｈａｎｇＨａｎｇｋｏｎｇＵｎｉｖｅｒｓｉｔｙ，Ｎａｎｃｈａｎｇ３３００６３，Ｃｈｉｎａ Ｅ－ｍａｉｌ：ｚｅｎｇｊｘ５８＠１６３．ｃｏｍ ＺＥＮＧＪｉｅ－ｘｉａｎ，ＢＩＤｏｎｇ－ｇｅ．Ｉｍａｇｅｒｅｔｒｉｅｖａｌｍｅｔｈｏｄｂａｓｅｄｏｎｃｏｎｔｏｕｒｃｈａｒａｃｔｅｒａｎｄｓｐａｔｉａｌｔｏｐｏｌｏｇｙ．ＣｏｍｐｕｔｅｒＥｎｇｉ－ｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ，２００８。４４（５）：９０－９２． Ａｂｓｔｒａｃｔ：ＡｎｅｗｍｅｔｈｏｄｆｏｒＣＢＩＲｂａｓｅｄｏｎｓｈａｐｅＦｏｕｒｉｅｒｄｅｓｃｒｉｐｔｏｒｉｓｐｒｅｓｅｎｔｅｄ．Ｔｈｅｆｉｒｓｔｓｔｅｐｏｆｔｈｉｓｍｅｔｈｏｄｉｓｐｒｅ－ｐｒｏｃｅｓｓｉｎｇｔｈｅｉｍａｇｅ，ｔｈｅｎｃａｒｒｙｉｎｇｔｈｅｉｍａｇｅｓｅｇｍｅｎｔａｔｉｏｎｂａｓｅｄｏｎｔｏｐｏｌｏｇｙｒｅｌａｔｉｏｎｓｈｉｐ，ａｎｄｔｈｅｎｕｓｅｃｏｎｔｏｕｒｔｒａｃｋｉｎｇｍｅｔｈｏｄｔｏｏｂｔａｉｎｔｈｅｃｏｎｔｏｕｒｆｅａｔｕｒｅｗｈｉｃｈｌａｔｅｒｄｅｓｃｒｉｂｅｄｂｙＦｏｕｒｉｅｒｄｅｓｃｒｉｐｔｏｒｕｓｉｎｇＦＦＴ，ａｔｌａｓｔ，ｕｓｉｎｇｂｌｏｃｋｄｉｓｔａｎｃｅｔｏｍｅａｓｕｒｅｔｈｅｓｉｍｉｌａｒｉｔｙｂｅｔｗｅｅｎｔｈｅｏｒｉｇｉｎａｌｐｉｃｔｕｒｅａｎｄｔａｒｇｅｔｐｉｃｔｕｒｅ．Ｉｎｏｒｄｅｒｔｏｖｅｒｉｆｙｔｈｅｅｆｆｅｃｔｉｖｅｎｅｓｓｏｆｔｈｅｍｅｔｈｏｄ，ｗｅｅｘｐｅｒｉｍｅｎｔｅｄｕｎｄｅｒＭＡＴＬＡＢａｎｄＶＣ＋＋ｅｎｖｉｒｏｎｍｅｎｔ．Ｂｙｓｅｖｅｒａｌｅｘｐｅｒｉｍｅｎｔｓ，ｔｈｅｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｉｓｍｅｔｈｏｄｉｓｅｆｆｅｃｔｉｖｅａｎｄａｌｓｏｂｙａｌｇｏｒｉｔｈｍａｎａｌｙｓｉｓ，ｗｅｃｏｎｃｌｕｄｅｔｈａｔｔｈｅｍｅｔｈｏｄｉｓｒａｔｉｏｎａｌｆｏｒｉｍａｇｅｒｅｔｒｉｅｖａｌ． Ｋｅｙｗｏｒｄｓ：ｓｈａｐｅｄｅｓｃｒｉｂｉｎｇ；Ｆｏｕｒｉｅｒｄｅｓｃｒｉｐｔｏｒ；ｓｐａｔｉａｌｔｏｐｏｌｏｇｙ；ｃｏｍｐａｒａｂｉｌｉｔｙ 摘要：提出了一种利用轮廓特征和拓扑关系的图像检索方法。首先对图像进行预处理，然后根据空间拓扑关系进行区域分割，再对各个区域进行轮廓跟踪，并用傅立叶描述子对所提取区域的轮廓进行描述，最后用街区距离进行相似度的判定。为了验证该算法的有效性，在ＭＡＴＬ＾．Ｂ和ＶＣ＋＋环境下进行了实验，通过实验结果和算法分析，证明了该方法的合理性和有效性。 关键词：形状描述；傅立叶描述子；空间拓扑关系；相似度 文章编号：１００２—８３３１（２００８）０５—００９０—０３文献标识码：Ａ中图分类号：ＴＰ３９１．３ １引言 在计算机视觉中，形状特征属于图像的中间层特征。形状特征作为刻画图像中物体和区域特点的重要特征，是描述高层视觉特征（如目标、对象等）的重要手段，而目标、对象对获取图像语义尤为重要。利用形状特征进行检索可提高检索的准确性和效率ｆｌ】。但是基于形状特征的图像检索，主要存在有四个问题：一是图像分割算法还不能做到自适应；二是形状描述子难于提取［２１。三是特征空间的相似性与人视觉系统感受到的相似性也有差别，四是由于视点的变化可能会产生各种失真。所以，基于形状的图像检索还缺乏比较完善的数学模型，目标变形时检索结果也不可靠；另外，要全面描述形状对计算和存储都有较高的要求。 基于空间关系的查询，其主要优点是能比较完整地表达图像各部分的信息，并能比较方便地无示例或用自然语言查询。空间位置关系的特征还可加强对图像内容的描述区分能力ｔ３］。空间关系是图像内部目标的重要特征１３１，但是如果单独用空间关系描述物体的特征就显得模糊，常常很难用一个确定的表达式描述清楚，它们常由一组互相联系又有矛盾的条件所限定，每个条件在具体情况下得到不同程度的满足。常用的空间关系一般包括朝向关系和拓扑关系，它们都可以通过自然语言来描述。由于空间关系的模糊性，根据空间关系来确定检索对象的相似性是一个复杂的工作。 物体的形状及其空间关系既是图像中的核心内容，也是人们识别图像、分类图像的重要依据。但是目前基于形状和空间关系的图像检索还仅处于研究二值商标图像。在文献【１］提出了．利用小波分解技术的形状和空间关系的图像检索方法，但是小波分解的多分辨率和小波分解的方向性，使得该描述子不具有旋转和尺度变换的不变性。如果检索的图像内容包括运动的物体，则不能得到好的检索结果。 鉴于此，提出了一种基于轮廓特征和拓扑关系的图像检索方法。首先利用空间拓扑关系进行图像分割；然后提取区域轮廓特征，并用傅立叶描述子进行描述；最后再把该描述子应用于基于形状的图像检索中。通过实验验证了该算法的有效性和合理性。 基金项目：国家自然科学基金（ｔｈｅＮａｔｉｏｎａｌ‘ＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＣｈｉｎａｕｎｄｅｒＧｒａｎｔＮｏ．６０６７５０２２）；江西省自然科学基金（ｔｈｅＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＪｉａｎｇｘｉＰｒｏｖｉｎｃｅｏｆＣｈｉｎａｕｎｄｅｒＧｒａｎｔＮｏ．０３１１０１９）；江西省教育厅资助科研课题（ｔｈｅＲｅｓｅａｒｃｈＰｍｊｅｃｔｏｆＤｅ一 ● ｐａｒｔｍｅｎｔ ｏｆＥｄｕｃａｔｉｏｎｏｆＪｉａｎｇｘｉＰｒｏｖｉｎｃｅ）。 作者简介：曾接贤（１９５８一），男，教授，主要从事工程图学、计算机图形学和计算机视觉等方面的研究；毕东格（１９８１一），女，硕士研究生，主要研究方向为计算机视觉与图像处理。 收稿日期：２００７－０６—２７修回１３期：２００７—０９—０７
轮廓跟踪
轮廓跟踪 (2009-05-25 15:10:14) 转载▼ 标签： 杂谈 在识别图象中的目标时，往往需要对目标边缘作跟踪处理，也叫轮廓跟踪。顾名思义，轮廓跟踪就是通过顺序找出边缘点来跟踪边界的。若图象是二值图象或图象中不同区域具有不同的象素值，但每个区域内的象素值是相同的，则如下算法可完成基于4连通或8连通区域的轮廓跟踪。 步骤1：首先按从上到下，从左到右的顺序扫描图象，寻找没有标记跟踪结束记号的第一个边界起始点A0，A0是具有最小行和列值的边界点。定义一个扫描方向变量dir,该变量用于记录上一步中沿着前一个边界点到当前边界点的移动方向，其初始化取值为（1）对4连通区域取dir=3； （2）对8连通区域取dir=7； 步骤2：按逆时针方向搜索当前象素的3*3邻域，其起始搜索方向设定如下： （1）对4连通区域取（dir+3）mod 4； （2）对8连通区域，若dir为奇数取（dir+7）mod 8；若dir为偶数去（dir+6）mod 8； 在3*3邻域中搜索到的第一个与当前像素值相同的像素便为新的边界点An,同时更新变量dir为新的方向值。 步骤3：如果An等于第二个边界点A1且前一个边界点An-1等于第一个边界点A0，则停止搜索，结束跟踪，否则重复步骤2继续搜索。 步骤4：由边界点A0、A1、A2、……、An-2构成的边界便为要跟踪的边界。 上述算法是图象轮廓跟踪最基本的算法，它只能跟踪目标图象的内边界（边界包含在目标点集内），另外，它也无法处理图象的孔和洞 轮廓跟踪问题 [m,n]=size(yy); U=zeros(m,n); for i=1:m for j=1:n if yy(i,j)==255 U(i,j)=yy(i,j); break; end; end; end; figure,imshow(U); [m,n]=size(yy); V=zeros(m,n);
二值图像连通域标记快速算法实现
二值图像连通域标记快速算法实现 算法描述 首先，在进行标记算法以前，利用硬件开辟独立的图像标记缓存和连通关系数组，接着在视频流的采集传输过程中，以流水线的方式按照视频传输顺序对图像进行逐行像素扫描，然后对每个像素的邻域分别按照逆时针方向和水平方向进行连通性检测和等价标记关系合并，检测出的结果对标记等价数组和标记缓存进行更新，在一帧图像采集传输结束后，得到图像的初步标记结果以及初步标记之间的连通关系，最后，根据标号对连通关系数组从小到大的传递过程进行标号的归并，利用归并后的连通关系数组对图像标记缓存中的标号进行替换，替换后的图像为最终标记结果，并且连通域按照扫描顺序被赋予唯一的连续自然数。 图 1 标记算法流程 本文快速二值图像连通域标记算法分为三个环节： 1.图像初步标记：为每个像素赋予临时标记，并且将临时标记的等价关系记录在等价表中 2.整理等价表：这一环节分为两个步骤： （1）将具有等价关系的临时标记全部等价为其中的最小值； （2）对连通区域以自然数顺序重新编号，得到临时标记与最终标记之间的等价关系。 3.图像代换：对图像进行逐像素代换，将临时标记代换为最终标记．经过3个环节处理后，算法输出标记后的图像，图像中连通域按照由上到下，由左至右出现的顺序被标以连续的自然数。 1 图像初始标记 标记算法符号约定：算法在逆时钟方向检测连通域时用w1，w2表示连续两行的图像数据，在紧接着的顺时钟方向连通域检测时用k0，k表示连续两行经过
逆时钟方向标记后的图像数据。其在工作窗口的位置在图2、3中分别说明；对初始逆时针方向临时标记用Z表示。Z初始标记值为1。 二值图像连通域标记算法采用8连通判断准则，通过缩小标记范围剔除了图像的边界效应。为了简化标记处理过程，使标记处理在硬件对一帧图像传输操作时间内结束，标记处理利用中间数据缓存分为连续的两种类型，其中类型1用于直接图像序列传输，硬件发起图像序列传输时，类型1采用逆时钟顺序连通域检测，对2×3工作窗口中的二值像素进行初始标记。类型2对经过类型1初始标记过的图像数据再进行水平方向的连通域检测和归并，然后把标记结果存入图像存储区。 图像初始标记类型1： 步骤1读取像素w1（2）、w1（1）、w1（0）、w0（2）、w0（1），以及相应的二值像素值。 步骤2读取像素w0（1），按照逆时针方向依次与w1（0）、w1（1）、w1（2）、w0（2）比较，若w0（1）= w1（0），则k0（1）=k（2）；若w0（1）= w1（1），则k0（1）=k（1）；若w0（1）= w1（2），则k0（1）=k（0）；若w0（1）= w0（2），则k0（1）=k0（0）；否则（即w0（1）≠（w1（2）、w1（1）、w1（0）、w0（2）），k0（1）= Z；Z ++。 步骤3写入等价关系表，以Z为地址将Z写入等价关系数组。 图 2 逆时钟方向初始标记的工作窗 图像初始标记类型2： 步骤1判断经过逆时针方向标记后，如果w0（1）= w0（2）= 1，而标记灰度k0（1）≠k0（0），则进行下一步骤。 步骤2 假设k0（1）> k0（0），判断lab（k0（1））=k0（1）或者lab（k0（1））=k0（0），则lab（k0（1））=k0（0），否则对标记数组进行追踪置换。跳转至步骤3。 步骤3 假设k0（1）< k0（0），判断lab（k0（0））=k0（0）或者lab（k0（0））=k0（1），则lab（k0（0））=k0（1），否则对标记数组进行追踪置换。 追踪置换方法：步骤2的追踪置换令t= lab（k0（0））；若lab（t）≠t，则
实验6,运动目标跟踪算法与实现
对图像进行阈值分析，并进行二值化处理 确定目标在像素平面上 结束 通过以形心位置为中 含目标的矩形框一． 实验名称：运动目标跟踪算法设计与实现 二． 实验目的 1. 熟悉各种图像预处理方法，如直方图处理、图像去噪声、图像增强与复原、图像变换等，了解这些方法在图像分析与识别、目标检测及跟踪等各种应用中所起的作用。 2. 熟悉基本的图像分割原理。 3. 能够利用MATLAB 工具完整实现从图像预处理、图像分割、特征提取与分析及各种实际应用的完整流程。 4. 该实验为一个综合设计及应用的实验，目的是要求学生综合利用学到的光电图像处理知识，解决图像识别、目标检测及目标定位与跟踪问题。进一步深入理解光电图像处理的重要性，提高学生利用光电图像处理基本理论、方法等解决实际问题及提高分析问题的能力。 三． 实验原理及步骤 1. 序列图像中的运动目标形心跟踪 (1) 序列图像的读取与显示 本实验提供了200 帧的图像序列，为BMP 文件，文件名后缀的序号按场景出现的先后顺序排列。 (2) 图像分割 首先，对图像进行必要的阈值分析。根据实际情况自行确定合适的阈值后，再对图像进行二值化处理。 (3) 形心计算 在分割的单帧图像上，计算图像中目标区的形心坐标（Xc ，Yc ），确定目标在像素平面上的位置坐标。 (4) 形心跟踪 ①MATLAB 确定跟踪波门：即以形心位置为中心，在图像中包含目标的区域添加一个合适的矩形框（如取32×16 pixels ，32×32 pixels ，64×32 pixels 等）， ②实时跟踪：循环读取序列图像，对每帧图像均计算目标区的形心坐标，连
续绘制包含目标区域的波门（即矩形框）。实现对200 帧序列图像中运动目标的实时稳定跟踪。 2. 序列图像中的运动目标相关跟踪 实验原理及步骤如下： (1) 序列图像的读取与显示 同实验内容1，序列图像数据另选。 (2) 参考模板制作 在起始帧图像中，手动选取包含目标的矩形区域（根据目标尺寸，确定模板尺寸）。另（缓）存为预制图像模板数据。 (3) 模板匹配 ①确定搜索区域大小：在当前帧目标区域扩大适当范围作为下一帧图像的搜索区域。 ②确定匹配准则：MSE 、MAD 、NCC 或MPC 等（选其一种），进行搜索区域的匹配度（相似度）计算，画出搜索区域内的相似度3D 曲面图（画连续2 帧之间的搜索过程的结果即可），确定最佳的匹配位置。视频数据若为彩色图像，可先进行灰度化处理，然后用像素灰度值进行计算。 ③实时跟踪：重复步骤①-②，实现序列图像中的目标的连续稳定跟踪。 四． 实验结果及分析 1. 序列图像中的运动目标形心跟踪 通过对形心的定位，可以实现更好的目标跟踪 制作参考模版，确定搜索区域大小确定匹配准则和 最佳的匹配位置结束
基于连通域算法的区域测量
第8卷 第9期 2008年5月1671-1819(2008)9-2492-03 科 学 技 术 与 工 程 S c i e n c e T e c h n o l o g ya n d E n g i n e e r i n g V o l .8 N o .9 M a y 2008 2008 S c i .T e c h .E n g n g . 基于连通域算法的区域测量 李仪芳 刘景琳 (广东技术师范学院电子与信息学院,广州510665) 摘 要 基于数字图像处理的原理,提出用八连通域算法对有多个连通区域的二值图像进行面积测量。通过逐行逐列地扫描图像,按照一定的规则标记连通区域,得到对象的个数,同时统计每个区域所含的像素,通过标尺转换可以得出区域的面积。结果表明,该算法能有效地提取八连通区域,可用于计算显微图像颗粒物的面积和粒径。关键词 区域标记 像素测量 八连通域算法中图法分类号 T P 391.77; 文献标识码 A 2008年1月21日收到 广东省第二批产业技术研究研发计划 项目(2007B 010200041)资助 第一作者简介:李仪芳(1983—),女,广东三水人,广东技术师范学院助教,硕士,研究方向:图像处理和光电技术。E -m a i l :a n g e l i -n a 2008@y a h o o .c o m .c n 二值图像中连通域的提取是图像处理和分析中的一个重要处理过程,可以用于显微图像的对象识别和测量,红外图像的目标定位等领域。灰度图像经过阈值分割后常包括多个连通的区域,需要将连通区域搜索标记出来以便测量。但常见算法是关于四连通区域的研究,其中文献[1,2]中描述或采用的是区域标号法,但文献[1]中描述的算法在实现时并不能达到预定的结果。而且区域生长法计算复杂度过高;像素标记法和行程标记法必须全部扫描完图像才能得到连通域,随着图像幅度和连通域个数的增加,计算复杂度增长。现提出用八连通域算法 [3] ,它不仅能在对图像一次扫描中标记连 通域即计算对象的个数,而且可实现边扫描边提取像素,即累计每个连通域所含像素的个数。 1 区域标记 算法实现逐行逐列扫描,对图像内每个连通的黑色区域进行标记操作,求得对象的数目。图1为6×12图像点阵,图中有三个连通区域,即三个对 象,分别用1,2,3标号。设前景点灰度取1,背景点取值为0。在算法中,定义了多个数组N (i ),其中i 代表连通区域的标号,∑N (i )表示区域内部包含的像素个数。如第1个区域,∑N (1)=7;对第2个区域,∑N (2)=6。下面以标记区域1为例,说明标记的具体算法。 图1 八连通域算法说明图 ① 初始化N (i )=0,i =0。② 从左到右,从上到下逐行扫描图像;如果没有遇到“1”,则继续扫描。若遇到“1”,如(1,1),则依次判断该像素点的
(完整版)视频目标检测与跟踪算法综述
视频目标检测与跟踪算法综述 1、引言 运动目标的检测与跟踪是机器视觉领域的核心课题之一，目前被广泛应用在 视频编码、智能交通、监控、图像检测等众多领域中。本文针对视频监控图像的运动目标检测与跟踪方法，分析了近些年来国内外的研究工作及最新进展。 2、视频监控图像的运动目标检测方法 运动目标检测的目的是把运动目标从背景图像中分割出来。运动目标的有效分割对于目标分类、跟踪和行为理解等后期处理非常重要。目前运动目标检测算法的难点主要体现在背景的复杂性和目标的复杂性两方面。背景的复杂性主要体现在背景中一些噪声对目标的干扰，目标的复杂性主要体现在目标的运动性、突变性以及所提取目标的非单一性等等。所有这些特点使得运动目标的检测成为一项相当困难的事情。目前常用的运动目标检测算法主要有光流法、帧差法、背景相减法，其中背景减除法是目前最常用的方法。 2.1 帧差法 帧差法主要是利用视频序列中连续两帧间的变化来检测静态场景下的运动目标，假设(,)k f x y 和(1)(,)k f x y +分别为图像序列中的第k 帧和第k+1帧中象素点(x ，y)的象素值,则这两帧图像的差值图像就如公式2-1 所示： 1(1)(,)(,)k k k Diff f x y f x y ++=- (2-1) 2-1式中差值不为0的图像区域代表了由运动目标的运动所经过的区域（背景象素值不变），又因为相邻视频帧间时间间隔很小，目标位置变化也很小，所以运动目标的运动所经过的区域也就代表了当前帧中运动目标所在的区域。利用此原理便可以提取出目标。下图给出了帧差法的基本流程：1、首先利用2-1 式得到第k 帧和第k+1帧的差值图像1k Diff +；2、对所得到的差值图像1k Diff +二值化（如式子2-2 示）得到Qk+1；3、为消除微小噪声的干扰，使得到的运动目标更准确，对1k Q +进行必要的滤波和去噪处理，后处理结果为1k M +。 111255,,(,)0,,(,)k k k if Diff x y T Q if Diff x y T +++>?=?≤? （T 为阈值） （2-2）