连通域标记算法

第２８卷第１０期　２０１１年ｌ０月　计算机应用研究　Ａｐｐｌｉｃａｔｉｏｎ　Ｒｅｓｅａｒｃｈ　ｏｆ　Ｃｏｍｐｕｔｅｒｓ　Ｖｏ１．２８　Ｎｏ．１０　Ｏｃｔ．２０１１　

基于均值漂移一连通域标记的多目标跟踪算法木　

鲁好波，李坚强，王小民　

（深圳大学计算机与软件学院，广东深圳５１８０６０）　

摘要：提出一种基于Ｍｅａｎ　Ｓｈｉｆｔ改进算法与连通域标记的多目标跟踪算法。在多目标跟踪过程中，对目标瞬　

间丢失、目标遮挡或重叠时目标跟踪失败等情况有较好的改进。在跟踪过程中，当目标丢失时，基于改进的　

Ｍｅａｎ　Ｓｈｉｆｔ算法能自适应调整搜索窗口尺寸和方向。通过自适应扩展搜索窗口，利用连通域标记算法搜索目标　

并计算其矩特征来获得跟踪目标的重心和大小信息，并将获得的位置和尺度信息作为下一帧Ｍｅａｎ　Ｓｈｉｆｔ算法跟　

踪初始坐标和尺度，统计目标区域颜色直方图作为Ｍｅａｎ　Ｓｈｉｆｔ算法目标模型，从而解决了因目标速度过快而引起　

的目标瞬间丢失问题。最后研究结果显示，这种改进的目标跟踪算法可以有效改善多目标跟踪的性能，实现目　

标连续跟踪。　

关键词：均值漂移；多目标跟踪；连通域标记；矩特征；特征匹配　

中图分类号：ＴＰ３９１；ＴＰ２４２　文献标志码：Ａ　文章编号：１００１—３６９５（２０１１）１０—３９６３—０４　

ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１－３６９５．２０１　１．１０．１００　

Ｍｕｌｔｉ—ｏｂｊ　ｅｃｔｉｖｅ　ｔｒａｃｋｉｎｇ　ｍｅｔｈｏｄ　ｂａｓｅｄ　ｏｎ　

Ｍｅａｎ　Ｓｈｉｆｔ　ｃｏｎｎｅｃｔｅｄ　ｃｏｍｐｏｎｅｎｔ　ｌａｂｅｌｉｎｇ　

ＬＵ　Ｈａｏ—ｂｏ，ＬＩ　Ｊｉａｎ・ｑｉａｎｇ，ＷＡＮＧ　Ｘｉａｏ—ｍｉｎ　（Ｓｃｈｏｏｌ　ｏｆＣｏｍｐｕｔｅｒ＆Ｓｏｆｉｗａｍ，Ｓｈｅｎｚｈｅｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈｅｎｚｈｅｎ　Ｇｕａｎｇｄｏｎｇ　５１８０６０，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｐｏｓｅｄ　ａｌｌ　ｉｍｐｒｏｖｅｄ　Ｍｅａｎ　Ｓｈｉｆｔ　ｂａｓｅｄ　ａｌｇｏｒｉｔｈｍ　ａｎｄ　ａ　ｃｏｎｎｅｃｔｅｄ　ｃｏｍｐｏｎｅｎｔｓ　ｌａｂｅｌｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｍｕｌｔｉ－ｔａｒｇｅｔ　ｔｒａｃｋｉｎｇ，ｗｈｉｃｈ　ｈａｄ　ａ　ｇｏｏｄ　ｐｅｒｆｏｒｍａｎｃｅ　ｉｎ　ｔｈｅ　ｐｒｏｃｅｓｓ　ｏｆ　ｍｕｌｔｉ－ｔａｒｇｅｔ　ｔｒａｃｋｉｎｇ　ｔｏ　ｄｅａｌ　ｗｉｔｈ　ｔｈｅ　ｓｉｔｕａｔｉｏｎｓ　ａｓ　ｔａｒｇｅｔ　ｉｎｓｔａｎｔ　ｌｏｓｓ，ｔａｒｇｅｔ　ｏｃｃｌｕｓｉｏｎ　ａｎｄ　ｔａｒｇｅｔ　ｔｒａｃｋｉｎｇ　ｆａｉｌｕｒｅ　ｄｕｒｉｎｇ　ｔｈｅ　ｏｖｅｒｌａｐｐｉｎｇ．Ｗｈｅｎ　ｔｈｅ　ｔａｒｇｅｔ　ｗａｓ　ｍｉｓｓｉｎｇ　ｉｎ　ｔｈｅ　ｔｒａｃｋｉｎｇ，ｔｈｉｓ　ｉｍｐｒｏｖｅｄ　ｔｒａｃｋｉｎｇ　ａｌｇｏｒｉｔｈｍ－－Ｍｅａｎ　Ｓｈｉｆｔ　ｃｏｕｌｄ　ｂｅ　ｓｅｌｆ－ａｄａｐｔｅｄ　ｔｏ　ａｄｊｕｓｔ　ｔｈｅ　ｓｉｚｅ　ａｎｄ　ｄｉｒｅｃｔｉｏｎ　ｏｆ　ｓｅａｒｃｈ　ｗｉｎｄｏｗ．Ｗｈａｔ’Ｓ　ｍｏｒｅ，ｔｈｒｏｕｇｈ　ｔｈｅ　ｓｅｒｆ－ａｄａｐｔｉｖｅ　ｅｘｔｅｎｄｅｄ　ｓｅａｒｃｈ　ｗｉｎｄｏｗ，ｉｔ　ｍａｄｅ　ｕｓｅ　ｏｆ　ｃｏｎｎｅｃｔｅｄ　ｃｏｍｐｏｎｅｎｔｓ　ｌａｂｅｌｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｔｏ　ｓｅａｒｃｈ　ｔａｒ－　ｇｅｔ　ａｎｄ　ｃａｌｃｕｌａｔｅ　ｉｔｓ　ｍｏｍｅｎｔ　ｃｈａｒａｃｔｅｒ　ａｓ　ｔｏ　ａｃｑｕｉｒｅ　ｔｈｅ　ｔｒａｃｋｉｎｇ　ｔａｒｇｅｔ　ｆｏｃｕｓ　ａｎｄ　ｓｉｚｅ，ａｎｄ　ｔｈｅ　ｇｅｔｔｉｎｇ　ｔａｒｇｅｔ　ｆｏｃｕｓ　ａｎｄ　ｓｉｚｅ　ｗｉｌｌ　ｂｅ　ｔｈｅ　ｔｒａｃｋｉｎｇ　ｉｎｉｔｉａｌ　ｃｏｏｒｄｉｎａｔｅ　ａｎｄ　ｓｉｚｅ　ｏｆ　Ｍｅａｎ　Ｓｈｉｆｔ　ｉｎ　ｔｈｅ　ｎｅｘｔ　ｆｒａｍｅ．Ｃａｌｃｕｌａｔｅｄ　ｔｈｅ　ｃｏｌｏｒ　ｈｉｓｔｏｇｒａｍ　ｏｆ　ｔｈｅ　ｏｂｊｅｃｔ　ｒｅｇｉｏｎ　ａｎｄ　ｐｕｔ　ｔｈｅ　ｈｉｓｔｏｇｒａｍ　ａｓ　ｔｈｅ　ｏｂｊｅｅｔ　ｍｏｄｅ１．Ｔｈａｔ　ｃｏｕｌｄ　ｓｏｌｖｅ　ｐｒｏｂｌｅｍｓ　ａｓ　ｔａｒｇｅｔ　ｌｏｓｓ　ｒｅｓｕｌｔｅｄ　ｆｒｏｍ　ｔｈｅ　ｏｖｅｒ—ｓｐｅｅｄ　ｔａｒｇｅｔ　ｍｏｖｉｎｇ．　Ｔｈｅ　ｆｉｎａｌ　ｒｅｓｕｌｔｓ　ｅｌｉｃｉｔ　ｔｈａｔ　ｔｈｉｓ　ｋｉｎｄ　ｏｆ　ｉｍｐｒｏｖｅｄ　ｔａｒｇｅｔ　ｔｒａｃｋｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｃａｎ　ｂｅ　ｅｆｆｉｃｉｅｎｔ　ｉｎ　ａｍｅｌｉｏｒａｔｉｎｇ　ｔｈｅ　ｆｕｎｃｔｉｏｎ　ｏｆ　ｍｕｌｔｉ－　ｔａｒｇｅｔ　ｔｒａｃｋｉｎｇ　ａｎｄ　ｒｅａｌｉｚｉｎｇ　ｔａｒｇｅｔ’Ｓ　ｃｏｎｔｉｎｕｉｎｇ　ｔｒａｃｋｉｎｇ．　Ｋｅｙ　ｗｏｒｄｓ：Ｍｅａｎ　Ｓｈｉｆｔ；ｍｕｌｔｉ—ｔａｒｇｅｔ　ｔｒａｃｋｉｎｇ；ｃｏｎｎｅｃｔｅｄ　ｃｏｍｐｏｎｅｎｔ　ｌａｂｅｌ；ｔｏｒｑｕｅ；ｃｈａｒａｃｔｅｒｓ　ｍａｔｃｈ　

第15卷第2期2005年4月 江苏大学学报(医学版)JournalofJiangsuUniversity(medicine) Vo.l15No.2Apr.2005 一种易于实现的适于细胞图像连通区域的标记算法喻 杰,许化溪(江苏大学医学技术学院,江苏镇江212001)[摘 要] 目的:为了实现简化细胞图像连通区域标记算法,本研究结合当前的应用情况提出了一种基于递归技术并适合于细胞图像目标区域的标记算法,探讨了其应用于白细胞计数的可能性。方法:常规瑞氏染色光镜下人工计数白细胞;应用计算机和CCD相机采集血涂片细胞图像,细胞标记递归算法进行细胞图像处理并计数白细胞。结果:此算法只需要一次扫描就可完成标记过程,因此算法的实现比经典的像素标记算法大大简化。应用该算法对19份血涂片样本进行标记,取得了较为满意的效果。本文还对区域标记时应注意的问题进行了讨论。结论:本研究应用递归过程建立的细胞图像连通区域的标记算法,适于在尚不发达地区实现白细胞计数的计算机化,也为应用计算机进行医学形态学研究提供了思路。[关键词] 细胞图像;图像分割;连通区域[中图分类号] R446 [文献标识码] A [文章编号] 1671-7783(2005)02-0152-03AnAchievableAlgorithmSuitabletoCellImageConnectedAreaYUJie,XUHua-xi,WANGSheng-jun(SchoolofMedicalTechnology,JiangsuUniversity,ZhenjiangJiangsu212001,China)[Abstract] Objective:Inordertosimpletherealizationofconnectedcomponentlabelingalgorithm,aconnectedcomponentlabelingalgorithmbasedonrecursionispresentedinthisstudy,itmaybeusefulforwhitebloodcell(WBC)coun.tMethods:puterandCCDcamerawereappliedtotakethepictureofbloodcellsfrombloodsmearandthecellimagewastreatedusingthealgorithmofcelllabelingrecursion.Results:Thisalgorithmcancompletethelabelingwithonlyonetimeofscanning,sotherealizationofthealgorithmwasmoresimplerthanthatoftheclassicpixellabeling.Applyingthisalgorithminlabelingnineteensamplesofbloodcellflakeobtainedsa-tisfyingeffec.tConclusion:ThealgorithmissuitableforcomputerizingWBCcountinalessdevelopedarea,italsohelptobringaboutcomputerapplicationonmedicalmorphologicstudies.[Keywords] Cellimage;Imagesegmentation;Connectedarea 生物医学研究有一个显著的特点)))海量信息,现代众多的医学研究都需要借助计算机,这是因为计算机有着高速,准确的信息处理能力。随着传感技术、模式识别技术的发展,计算机已被广泛应用在生物医学领域进行信息处理。其中细胞分类记数就是一个经典的应用实例,同时细胞分类记数也是一项重要的辅助诊断技术。就计算机来讲,记数就是一个对细胞图像目标区域进行标记的过程,当前比较流行的区域标记(将图像上不同的连通区域用不同的数值表示,而同一个目标区域所有的象素点用一个值表示)算法有象素点标记算法和游程连通性算法。本文以经过处理得到的二值图像为基础,主要对象素点标记算法进行了研究。分析了该标记算法在处理算法实现、可读性方面的不足,提出了基于递归技术的简化标记算法,并在血细胞计数中予以验证,以期为临床检验工作提供方便。1 材料与方法111 材 料外周血涂片,高倍显微镜,视频相机,图像采集[基金项目]国家自然科学基金资助项目(30471627);江苏省/333工程0资助项目[作者简介]喻 杰(1979-),男,硕士研究生;许化溪(联系人),教授,博士生导师,E-mai:lxuhx@卡,计算机。112 方 法11211 血涂片显微镜记数 常规采血制成涂片,用Wright染色,显微镜观察与计数。11212 采集彩色细胞图像 将制备好的的血涂片置光镜下,调好焦距,然后连接彩色CCD相机进行原始图像采集,图像模拟信号经过图像采集卡转换成数字信号并存入计算机。11213 细胞标记处理 彩色图→灰度图→二值图→标记细胞标记递归算法:①首先按从左到右,从上到下以TV光栅的方式从图像的左上角开始扫描。直到发现一个没有标记的1象素点。②对此1象素点赋予一个新的标记NewFlag。③按图1的编号次序的对此1象素(阴影)点的8个邻点进行扫描,如果遇到没有标记的1象素点就把它标记为new-Flag(它也就是②中的NewFlag)。此时又要按上述次序扫描8个邻点中的1象素的8个邻点,如遇到没有标记的1象素,又将它标记为NewFlag。次过程是一个递归,在邻点中遇到没有标记的1象素点,递推一层,直到没有标记的1象素点被耗尽,才开始层层返回。④递归结束,继续扫描没有标记的1象素点,然后执行②、③两个步骤。⑤反复执行上述过程直至光栅扫描到图像的右下角。

python中连通域算法

Python 中连通域算法

连通域可以简单理解为一个图像中相邻的像素点相连形成的一块区域。在图像处理中，我们常常需要对这些连通的区域进行一些操作，比如找到其中的特征、选择某个区域进行分析或对整个区域进行一些操作。在 Python 中，我们可以使用一些算法来找到图像中的连通域并进行相应的操作。

接下来，我将逐步介绍 Python 中连通域的概念、如何找到连通域、如何在连通域上进行特定操作的方法。

1. 连通域的概念

在图像处理中，连通域是一个由相邻的像素点构成的区域。在二值图像中，像素点的值通常只有两个，例如黑色和白色，被称为“0”和“1”。连通域的数量和形状通常与图像中的目标有关。例如，在一张图片中，我们可能需要找到所有联通的数字或字母，或者只需要找到图像中最大或最小的连通区域。

2. 连通域的查找算法

在 Python 中，我们可以使用不同的算法来查找连通域。其中，最常用的两种算法是DFS（深度优先搜索）和BFS（广度优先搜索）。在这里，我们将重点介绍 DFS 算法。

DFS 算法是一种非常适合连通域查找的算法。它的基本思路是从图像中的某个像素点开始，沿着该点所在的连通域递归地访问所有相邻的未访问过的像素点。通过递归，我们可以遍历整个连通域，并找到所有的像素点。

为了演示 DFS 算法，我们先创建一个简单的二值图像。以下代码创建一个

10x10 的方形图像，其中心区域是黑色的（0），外围是白色的（1）。

import numpy as np

import matplotlib.pyplot as plt

image = np.ones((10, 10), dtype=np.uint8) # 创建一个10x10的白色方形图像

image[3:7, 3:7] = 0 # 将图像中心区域切换为黑色

plt.imshow(image, cmap=plt.cm.gray) # 绘制图像

图像连通域的概念

图像连通域是指图像中一组相邻的像素点，它们具有相同的属性或特征，且通过相邻像素之间的连接关系形成一个连通区域。每个像素点可以看作是一个图像中一个最小的连通域，而多个连通域的集合则构成了整个图像。

图像连通域的概念对于图像处理和分析非常重要，可以用于目标检测、图像分割、特征提取等领域。在实际应用中，常常需要识别和提取图像中的不同连通域，以便进一步进行后续处理。

在图像中，连通域可以是任意形状的区域，这取决于图像中像素点之间的连接关系。而像素点之间的连接关系通常是通过像素点的空间位置和像素值的相似度来定义的。

在图像处理中，常常使用的连接关系有4邻接和8邻接。4邻接表示一个像素点的上、下、左、右四个邻域像素，而8邻接则表示上、下、左、右以及对角线的八个邻域像素。这两种邻接方式可根据具体应用需求选择。

连通域分析的基本原理是通过扫描整个图像，从每一个像素点开始，查找满足连接条件的相邻像素点，并将它们组成一个连通域。常使用的算法有基于种子点的扫描算法和基于区域增长算法。

基于种子点的扫描算法从图像中选择一个种子点开始，通过不断扩展种子点的相邻像素，并标记已访问过的像素点，以便于后续处理。该算法适用于具有清晰边界和简单连通域形状的图像。

基于区域增长的算法则通过像素值的相似性来判断像素点是否属于同一个连通域。该算法从一个种子点开始，逐步增长满足相似性条件的像素点，直到达到预设的停止条件。该算法适用于具有复杂连通域形状和灰度值变化较大的图像。

除了基本的连通域分析算法，还有一些改进和扩展的算法可以应用于特定的图像处理任务。例如，基于区域的分割算法、基于轮廓的形状分析算法等。这些算法利用图像连通域的特性进行目标检测、分类和识别等任务。

总的来说，图像连通域是指图像中一组相邻的像素点，通过连接关系形成的连通区域。连通域分析是图像处理和分析中常用的技术，可用于目标检测、图像分割、特征提取等领域。不同的连通域分析算法可以根据具体应用需求选择，以实现对图像中连通域的识别和提取。