本发明公开了一种基于启发式的蚁群航迹恢复方法，每一个航迹对应一个蚁群，每一个蚁群赋予一个颜色身份信息，所有蚂蚁都从航迹的起始位置开始觅食行为，受到启发式函数和信息素强度的影响进行决策；蚂蚁决策包括蚂蚁正向决策和蚂蚁反向决策，觅食过程结束时，该蚂蚁对其信息素场进行一次全局更新，迭代次数增加，蚂蚁受到信息素的影响趋向于选择成本更低的路径，信息素场不断增强，最终对每一个蚁群的信息素场进行归一化处理，利用形态学运算提取出不同颜色的轨迹信息素场映射到原始航迹空间，联合时序信息，获得航迹重新关联部分的信息并提取完整的细胞谱系树。本发明能修复由于细胞运动过快、漏检测、细胞黏连和分裂检测丢失等导致的航迹碎片。
1.一种基于启发式的蚁群航迹恢复的细胞跟踪方法，其特征在于：每一个航迹对应一个蚁群，每一个蚁群赋予一个颜色身份信息，蚁群中的所有蚂蚁都从航迹的起始位置开始觅食行为，蚂蚁受到启发式函数和信息素强度的影响进行决策；
蚂蚁决策包括蚂蚁正向决策、蚂蚁反向决策，在蚂蚁决策过程中，包括普通细胞迁移和细胞分裂事件；
蚂蚁正向决策，所有蚁群同时开始进入觅食工作状态，首先蚂蚁以时间序列正序移动，当一只蚂蚁抵达某一航迹的结束位置，同时在后三帧内没有其他候选航迹时进入蚂蚁反向决策；
蚂蚁反向决策，该蚂蚁再以时间序列逆序反向决策移动，直到该蚂蚁抵达某一航迹片段的起始位置并且前三帧内无候选航迹时，此时此次觅食过程结束，该蚂蚁对其信息素场进行一次全局更新；当一个蚁群中的所有蚂蚁都完成一次觅食，该蚁群结束工作状态；
全局信息素更新，当所有蚁群都结束工作状态，根据当前迭代的总成本再对所有信息素场进行一次全局更新；
信息素场的提取和航迹的重新关联，随着迭代次数的增加，蚂蚁受到信息素的影响更加趋向于选择成本更低的路径，信息素场不断增强，最终对每一个蚁群的信息素场进行归一化处理，再利用形态学运算提取出不同颜色的轨迹信息素场，将提取到的轨迹信息素场空间反映射到原始航迹空间，联合时序信息，获得航迹重新关联部分的信息，最终提取出完整的细胞谱系树。
2.根据权利要求1所述的基于启发式的蚁群航迹恢复的细胞跟踪方法，其特征在于成本函数为：将原有连续航迹上的两个相邻帧细胞状态之间的成本设置为一个常数，此常数取值为 ；设在某一图像序列中共有 个断裂航迹， 表示在航迹碎片 上第帧的第 个细胞位置， ， 表示在航迹碎片 上第 帧的第 个细胞位置， ，其中 是一个小于等于3的正整数，和 分别表示航迹索引，并且 ；那么，在不同的航迹碎片之间的两个细胞状态之间的成本表示为其中， 是一个在 范围内的常数， 表示细胞位置 和细胞位
置 之间的距离成本， 表示细胞位置 和细胞位置 之
其中， 表示细胞位置 和细胞位置 之间的距离，H和W分别表示输入细胞图像的高和宽；面积成本 定义为
其中， 表示细胞位置 的面积估计， 表示细胞位置 的面积估
3.根据权利要求1所述的基于启发式的蚁群航迹恢复的细胞跟踪方法，其特征在于，蚂蚁正向决策：当蚁群以时间序列正序移动时，设蚁群中的任意一只蚂蚁a位于第 帧某一细胞位置 上，则蚂蚁正向决策过程实现如下描述：步骤1：初始化：首先设置在细胞位置 的蚂蚁a的初始搜索范围 ，获取所有航迹上每一帧细胞的位置信息和形态学信息，包括细胞面积、形状；
步骤2：蚁群中的每一只蚂蚁以最大帧间位移为约束条件选择下一步要移动到的细胞位置，以时间序列正序移动；以最大帧间位移为约束条件先确定 帧的候选细胞集，定义符号 表示集合里元素的数目，根据 的值，即候选细胞的数量分为以下三种情况：（1）：若 ，即在 帧的候选细胞集 中有且仅有一个细胞，则蚂蚁直接移动到这一候选细胞；
（2）：若 ，即在 帧的候选细胞集 的数量大于等于2，则候选细胞集 中的所有细胞两两之间分别要进行相似度计算，来判断是否有分裂事件发生；设和 分别为第 帧的两个不同的细胞位置，且 ，则相似度标准定义为
其中， 是一个在 范围内的常数，且 表示面积相似度，
其中， 表示细胞的面积估计， 表示细胞间的距离， 表示细胞轮廓估计的长轴长度， 表示细胞估计轮廓的短轴长度；
若候选细胞集 中细胞位置 和细胞位置 的相似度值大于某一给定
阈值 ，则认为蚂蚁在当前时刻即将发生分裂事件，该蚂蚁复制成两只蚂蚁分别移动到细胞位置 和细胞位置 ，且 ；若候选细胞集中无任意两细胞的相似度大于某一给定阈值 ，则认为是普通的细胞迁移，蚂蚁根据概率选择移动到下一细胞位置，蚂蚁a从 出发，在候选细胞集 中选择细胞位置 的概率为其中， 和 分别表示信息素和启发式因子的相对重要性系数， 表示路径 上的轨迹信息素量， 表示路径 上的启发式信
（3）： ，即在 帧的候选细胞集 中没有候选细胞，则将蚂蚁搜索范围扩大到下一帧，即 ，若此时 ，则重新进行步骤2；若 ，即蚂蚁a在接下来三帧内均未找到候选细胞，则该蚂蚁正向决策过程结束，开始进入蚂蚁反向决策；
步骤3：当蚂蚁按照步骤2完成一次决策并移动到下一个细胞位置后，则在经过的轨迹上释放一定量的信息素：其中， 表示信息素挥发系数， 表示一定量的信息素值。
4.根据权利要求1所述的基于启发式的蚁群航迹恢复的细胞跟踪方法，其特征在于，蚂蚁反向决策：当蚁群以时间序列逆序反向移动时，此时对应反向细胞运动过程，设蚁群中的任意一只蚂蚁a位于第 帧某一细胞位置 上，则蚂蚁反向决策过程实现如下描述：步骤1：首先设置在细胞位置 的蚂蚁a的初始搜索范围 ；
步骤2：蚁群中的每一只蚂蚁以最大帧间位移为约束条件选择下一步要移动到的细胞位置，以时间序列逆序移动；以最大帧间位移为约束条件先确定 帧的候选细胞集，根据 的值，即候选细胞的数量分情况进行：（1）：若 ，则将候选细胞依次与蚂蚁当前所在细胞位置和当前时刻中满足最大帧间位移约束条件的其他细胞位置分别进行相似度判断，设 为 帧的一个候选细胞位置， 为第 帧的另一个细胞位置，且 ，若相似度值大于某一给定阈值，则蚂蚁a当前所在细胞位置为 时刻 分裂的
细胞之一，则蚂蚁a移动到 ；若无相似度值大于某一给定阈值或当前时刻无其他细胞与候选细胞之间满足最大帧间位移约束条件，则蚂蚁根据概率选择移动到下一细胞位置，蚂蚁a从 出发，在候选细胞集 中选择细胞位置 的概率为其中， 和 分别表示信息素和启发式因子的相对重要性系数， 表示路径上的轨迹信息素量， 表示路径 上的启发式信息，为两细胞状态之间成本的倒数： ；
（2）：若 ，即在 帧的候选细胞集 中没有候选细胞，则将蚂蚁搜索范围扩大到前一帧，即 ，若此时 ，则重新进行步骤2；若 ，即蚂蚁a在前三帧内均未找到候选细胞，该蚂蚁停止决策，蚂蚁此次觅食过程结束；
步骤3：当蚂蚁按照步骤2完成一次决策并移动到下一个细胞位置后，则在经过的轨迹上释放一定量的信息素：其中， 表示信息素挥发系数， 表示一定量的信息素值。
5.根据权利要求1所述的基于启发式的蚁群航迹恢复的细胞跟踪方法，其特征在于，全局信息素更新：当一只蚂蚁a完成一次觅食过程后，要根据该蚂蚁轨迹的成本值进行一次信息素更新：其中， 表示信息素残留系数， 为一个常量， 表示蚂蚁a的移动轨迹， 表示 的成本值；由于定义的蚁群觅食行为具有随机性，有的蚂蚁会回到其出发位置，而有的蚂蚁不会，于是根据蚂蚁是否回到其出发位置，设置不同程度的信息素更新：回到出发位置的蚂蚁信息素更新时 的值比未回到出发位置的蚂蚁信息素更新时 的值要大，这意味着回到巢穴的蚂蚁的信息素更新程度比未回到巢穴的蚂蚁的信息素更新程度要高；
当所有蚁群中的蚂蚁都完成一次觅食过程，即所有蚁群都终止工作状态，此时当前迭代过程结束，所有蚁群的轨迹信息素场要根据本次迭代的总成本值再进行一次全局信息素更新：其中， 为一个常量， 表示本次迭代中第 个蚁群中第a只蚂蚁的移动轨迹， 表示本次迭代中第 个蚁群中第a只蚂蚁移动轨迹的成本值， 表示本次迭代中所有蚁群中所有蚂蚁移动轨迹的总成本值，m表示蚁群的个数，n表示一个蚁群中蚂蚁的个数。
6.根据权利要求1所述的基于启发式的蚁群航迹恢复的细胞跟踪方法，其特征在于，信息素场的提取和航迹的重新关联，随着迭代次数的增加，蚂蚁受到信息素的影响更加趋向于选择成本更低的路径，信息素场不断得到增强，直到达到最大迭代次数，提取带有身份信息的信息素场，将信息素场空间映射入原始航迹空间，获得航迹恢复信息：步骤1：为了获得更加清晰的轨迹信息素场，对每个蚁群的信息素场进行阈值处理：其中， 为信息素提取阈值， 表示第 个蚁群对应的信息素场中像素 的信息素强度；
步骤2：分别对 个经过阈值处理的轨迹信息素场进行形态学处理，提取出 个带有不同身份信息的轨迹信息素场，随后进入步骤3；
步骤3：将不同颜色的轨迹信息素场进行轨迹融合处理，设两个不同的轨迹信息素场分别为 和 ，其中 和 分别代表两种不同的颜色，若 ，即包含 ，则将轨迹信息素场 删除；经过轨迹融合处理后，将剩余的带有身份信息的轨迹信息素场叠加到同一个轨迹信息素场空间 ，设此时 中共有 种不同颜色的轨迹信息素场，分别用 表示， ， 表示轨迹信息素场的颜色，即身份信息；
步骤4：将带有身份信息的轨迹信息素场空间 映射到原始航迹空间 ，两空间坐标位置一一对应，关联映射关系为 ，即将轨迹信息素场每一个轨迹点投影至原始航迹空间 中对应的坐标位置，设轨迹信息素场空间 中的轨迹信息素场 经过关联映射 投影至 中的连续轨迹为 ， 为原始航迹空间 中 个航迹碎片中的索引为 的航迹碎片， ，若
经过关联映射至原始航迹空间 中的轨迹 包含多条航迹碎片时，则此多条航迹碎片得到恢复，联合时序信息完成原始航迹碎片间的重新关联，即可得到可靠的细胞谱系树；每一个细胞都拥有特殊的标签，这个标签由细胞第一次出现新生的帧数和细胞在新生的那一帧所有新生细胞中的索引值构成，设一个细胞的标签为 ，其中表示细胞第一次出现的帧数， 表示这一细胞在第 帧中所有新生细胞中的索引值，当细胞发生普通迁移时标签不变，当细胞发生分裂时对应的两个子细胞的标签将分别变为，其中 表示发生分裂事件的帧数，表示分裂的子细胞在第 帧所有新生细胞中的索引值；所以重新关联后的每一条细胞航迹都对应一个特殊的细胞标签。
基于启发式的蚁群航迹恢复方法
技术领域
[0001] 本发明涉及细胞行为分析领域，尤其涉及一种基于启发式的蚁群航迹恢复方法。
背景技术
[0002] 细胞行为分析对于人类疾病诊断和生物医学研究十分重要，为了更加直观和定量地对细胞行为进行科学评估，延时显微视频通常被用于自动记录细胞形态和动态的变化。在一帧显微图像中，往往有数以百计的细胞经历着迁移、变形、分裂和死亡，这些复杂行为为研究人员人工跟踪每一个细胞并记录其谱系带来了很大的困难，因此细胞的自动跟踪方法引起了广泛的关注。
[0003] 目前，细胞自动跟踪方法主要集中于逐帧关联方法，这类方法在连续的图像序列中可以实现较高的跟踪精度，但由于噪声或分割错误等误差的存在，这类方法仍然会出现一些问题。比如，当出现假阴性分割（即漏检）时，可能会导致跟踪丢失。为了解决这些问题，研究人员提出了全局时空数据关联方法，其中最著名的有多假设跟踪（MHT）和联合概率数据关联滤波器（JPDAF）。多假设跟踪方法通过时空信息寻找全局最优解，联合概率数据关联是一种面向目标的贪婪算法。但是，这类方法没有考虑细胞分裂情况，因此得到的细胞谱系树仍然是不完整的。同时，为了降低计算复杂度，将可靠的航迹碎片进一步进行关联的方法相继被提出，有人利用动态规划来获得航迹之间的最小路径来完成航迹与航迹之间的关联，有人将树结构的全局航迹碎片的关联表示为一个极大后验（MAP）问题，然后通过线性规划来求解。
发明内容
[0004] 本发明为了解决由于细胞运动过快、漏检测、细胞黏连、分裂、检测丢失等导致的航迹断裂的恢复问题，提出了一种基于启发式的蚁群航迹恢复方法。
[0005] 本发明公开了一种基于启发式的蚁群航迹恢复方法，每一个航迹对应一个蚁群，每一个蚁群赋予一个颜色身份信息，蚁群中的所有蚂蚁都从航迹的起始位置开始觅食行为，蚂蚁受到启发式函数和信息素强度的影响进行决策；
[0006] 蚂蚁决策包括蚂蚁正向决策、反向决策，在蚂蚁决策过程中，包括普通细胞迁移和细胞分裂事件；
[0007] 蚂蚁正向决策，所有蚁群同时开始进入觅食工作状态，首先蚂蚁以时间序列正序移动，当一只蚂蚁抵达某一航迹的结束位置，同时在后三帧内没有其他候选航迹时进入蚂蚁反向决策；
[0008] 蚂蚁反向决策，该蚂蚁再以时间序列逆序反向决策移动，直到该蚂蚁抵达某一航迹片段的起始位置并且前三帧内无候选航迹时，此时此次觅食过程结束，该蚂蚁对其信息素场进行一次全局更新；当一个蚁群中的所有蚂蚁都完成一次觅食，该蚁群结束工作状态；
[0009] 全局信息素更新，当所有蚁群都结束工作状态，根据当前迭代的总成本再对所有信息素场进行一次全局更新；
[0010] 信息素场的提取和航迹的重新关联，随着迭代次数的增加，蚂蚁受到信息素的影响更加趋向于选择成本更低的路径，信息素场不断增强，最终对每一个蚁群的信息素场进行归一化处理，再利用形态学运算提取出不同颜色的轨迹信息素场，将提取到的轨迹信息素场空间反映射到原始航迹空间，联合时序信息，获得航迹重新关联部分的信息，最终提取出完整的细胞谱系树。
[0011] 更进一步，成本函数为：将原有连续航迹上的两个相邻帧细胞状态之间的成本设置为一个非常小的常数，在本发明中此常数取值为 ；假设在某一图像序列中共有个断裂航迹， 表示在航迹碎片 上第 帧的第 个细胞位置， 表示在航迹碎片 上第 帧的第 个细胞位置，其中 是一个小于等于3的正整数，和
分别表示航迹索引，并且 ；那么，在不同的航迹碎片之间的两个细胞状态之间的成本表示为
[0012]
[0013] 其中， 是一个在 范围内的常数， 表示细胞位置 和细胞位
[0014] 置 之间的距离成本， 表示细胞位置 和细胞位置 之间的面积成本；
[0015] 距离成本 定义为
[0016]
[0017] 其中， 表示细胞位置 和细胞位置 之间的距离， 和 分别表示输入细胞图像的高和宽；面积成本 定义为
[0018]
[0019] 其中， 表示细胞位置 的面积估计， 表示细胞位置 的面积估计， 表示两细胞面积交集， 表示两细胞面积求和。
[0020] 更进一步，蚂蚁正向决策：当蚁群以时间序列正序移动时，假定蚁群中的任意一只蚂蚁 位于第 帧某一细胞位置 上，则蚁群正向决策过程实现如下描述：
[0021] 步骤1：初始化：首先设置在细胞位置 的蚂蚁 的初始搜索范围 ，获取所有航迹上每一帧细胞的位置信息和形态学信息，包括细胞面积、形状；
[0022] 步骤2：蚁群中的每一只蚂蚁以最大帧间位移为约束条件选择下一步要移动到的细胞位置，以时间序列正序移动；以最大帧间位移为约束条件先确定 帧的候选细胞集，定义符号 表示集合里元素的数目，根据 的值，即候选细胞的数量分为以下三种情况：
[0023] （1）：若 ，即在 帧的候选细胞集 中有且仅有一个细胞，则蚂蚁直接移动到这一候选细胞；
[0024] （2）：若 ，即在 帧的候选细胞集 的数量大于等于2，则候选细胞集 中的所有细胞两两之间分别要进行相似度计算，来判断是否有分裂事件发生；设和 分别为第 帧的两个不同的细胞位置，且 ，
则相似度标准定义为
[0025]
[0026] 其中， 是一个在 范围内的常数，且 表示面积相似度，表示距离相似度， 表示形状相似度，分别定义为
[0027]
[0028]
[0029]
[0030] 其中， 表示细胞的面积估计， 表示细胞间的距离， 表示细胞轮廓估计的长轴长度， 表示细胞估计轮廓的短轴长度；
[0031] 若候选细胞集 中细胞位置 和细胞位置 的相似度值大于某一给定阈值 ，则认为蚂蚁在当前时刻即将发生分裂事件，该蚂蚁复制成两只蚂蚁分别移动到细胞位置 和细胞位置 ，且 ；若候选细胞集中无任意两细
胞的相似度大于某一给定阈值 ，则认为是普通的细胞迁移，蚂蚁根据概率选择移动到下一细胞位置，蚂蚁 出发，在候选细胞集 中选择细胞位置 的概率为
[0032]
[0033] 其中， 和 分别表示信息素和启发式因子的相对重要性系数， 表示路径 上的轨迹信息素量， 表示路径 上的启发式信息，为两细胞状态之间成本的倒数： ；
[0034] （3）： ，即在 帧的候选细胞集 中没有候选细胞，则将蚂蚁搜索范围扩大到下一帧，即 ，若此时 ，则重新进行步骤2；若 ，即蚂蚁
在接下来三帧内均未找到候选细胞，则该蚂蚁正向移动过程结束，开始进入反向决策；
[0035] 步骤3：当蚂蚁按照步骤2完成一次决策并移动到下一个细胞位置后，则在经过的轨迹 上释放一定量的信息素：
[0036]
[0037] 其中， 表示信息素挥发系数， 表示一定量的信息素值。
[0038] 更进一步，蚂蚁反向决策：当蚁群以时间序列逆序反向移动时，此时对应反向细胞运动过程，假定蚁群中的任意一只蚂蚁 位于第 帧某一细胞位置 上，则蚁群决策过程实现如下描述：
[0039] 步骤1：首先设置在细胞位置 的蚂蚁 的初始搜索范围 ；
[0040] 步骤2：蚁群中的每一只蚂蚁以最大帧间位移为约束条件选择下一步要移动到的细胞位置，以时间序列逆序移动；以最大帧间位移为约束条件先确定 帧的候选细胞集，根据 的值，即候选细胞的数量分情况进行：
[0041] （1）：若 ，则将候选细胞依次与蚂蚁当前所在细胞位置和当前时刻中满足最大帧间位移约束条件的其他细胞位置分别进行相似度判断，设 为 帧的一个候选细胞位置， 为第 帧的另一个细胞位置，且 ，若相似度值大于某一给定阈值，则蚂蚁 当前所在细胞位置为 时刻 分
裂的细胞之一，则蚂蚁 移动到 ；若无相似度值大于某一给定阈值或当前时刻无其他细胞与候选细胞之间满足最大帧间位移约束条件，则蚂蚁根据概率选择移动到下一细胞位置，蚂蚁 从 出发，在候选细胞集 中选择细胞位置 的概率为
[0042]
[0043] 其中，和 分别表示信息素和启发式因子的相对重要性系数， 表示路径上的轨迹信息素量， 表示路径 上的启发式信息，为两细胞状态之间成本的倒数： ；
[0044] （2）：若 ，即在 帧的候选细胞集 中没有候选细胞，则将蚂蚁搜索范围扩大到前一帧，即 ，若此时 ，则重新进行步骤2；若 ，即蚂
蚁 在前三帧内均未找到候选细胞，该蚂蚁停止决策，蚂蚁此次觅食过程结束；
[0045] 步骤3：当蚂蚁按照步骤2完成一次决策并移动到下一个细胞位置后，则在经过的轨迹 上释放一定量的信息素：
[0046]
[0047] 其中， 表示信息素挥发系数， 表示一定量的信息素值。
[0048] 更进一步，全局信息素更新：
[0049] 当一只蚂蚁 如上述完成一次觅食过程后，要根据该蚂蚁轨迹的成本值进行一次信息素更新：
[0050]
[0051]
[0052] 其中， 表示信息素残留系数， 为一个常量， 表示蚂蚁 的移动轨迹， 表示 的成本值；由于定义的蚁群觅食行为具有随机性，有的蚂蚁会回到其出发位置，而有的蚂蚁不会，于是根据蚂蚁是否回到其出发位置，设置不同程度的信息素更新：回到出发位置的蚂蚁信息素更新时 的值比未回到出发位置的蚂蚁信息素更新时 的值要大，这意味着回到巢穴的蚂蚁的信息素更新程度比未回到巢穴的蚂蚁的信息素更新程度要高；
[0053] 当所有蚁群中的蚂蚁都完成一次觅食过程，即所有蚁群都终止工作状态，此时当前迭代过程结束，所有蚁群的轨迹信息素场要根据本次迭代的总成本值再进行一次全局信息素更新：
[0054]
[0055]
[0056] 其中， 为一个常量， 表示本次迭代中第 个蚁群中第 只蚂蚁的移动轨迹，表示本次迭代中第 个蚁群中第 只蚂蚁移动轨迹的成本值， 表示本次迭代中所有蚁群中所有蚂蚁移动轨迹的总成本值， 表示蚁群的个数， 表示一个蚁群中蚂蚁的个数。
[0057] 更进一步，信息素场的提取和航迹的重新关联，随着迭代次数的增加，蚂蚁受到信息素的影响更加趋向于选择成本更低的路径，信息素场不断得到增强，直到达到最大迭代次数，这时需要提取带有身份信息的信息素场，将信息素场空间映射入原始航迹空间，获得航迹恢复信息：
[0058] 步骤1：为了获得更加清晰的轨迹信息素场，对每个蚁群的信息素场进行阈值处理：
[0059]
[0060] 其中， 为信息素提取阈值， 表示第 个蚁群对应的信息素场中像素 的信息素强度；
[0061] 步骤2：分别对 个经过阈值处理的轨迹信息素场进行形态学处理，提取出 个带有不同身份信息的轨迹信息素场，随后进入步骤3；
[0062] 步骤3：将不同颜色的轨迹信息素场进行轨迹融合处理，设两个不同的轨迹信息素场分别为 和 ，其中 和 分别代表两种不同的颜色，若 ，即包含 ，则将轨迹信息素场 删除；经过轨迹融合处理后，将剩余的带有身
份信息的轨迹信息素场叠加到同一个轨迹信息素场空间 ，设此时 中共有 种不同颜色的轨迹信息素场，分别用 表示， 表示轨迹信息素场的颜
色，即身份信息；
[0063] 步骤4：将带有身份信息的轨迹信息素场空间 映射到原始航迹空间 ，两空间坐标位置一一对应，关联映射关系为 ，即将轨迹信息素场每一个轨迹点投影至原始航迹空间 中对应的坐标位置，设轨迹信息素场空间 中的轨迹信息素场 经过关联映射 投影至 中的连续轨迹为 ， 为原始航迹空间中 个航迹碎片中的索引为 的航迹碎片，若
[0064]
[0065] 即 中的轨迹信息素场 经过关联映射至原始航迹空间 中的轨迹包含多条航迹碎片时，则此多条航迹碎片得到恢复，联合时序信息完成原始航迹碎片间的重新关联，即可得到可靠的细胞谱系树；每一个细胞都拥有特殊的标签，这个标签由细胞第一次出现新生的帧数和细胞在新生的那一帧所有新生细胞中的索引值构成，假设一个细胞的标签为 ，其中 表示细胞第一次出现的帧数， 表示这一细胞在第 帧中所有新生细胞中的索引值，当细胞发生普通迁移时标签不变，当细胞发生分裂时对应的两个子细胞的标签将分别变为 ，其中 表
示发生分裂事件的帧数， 表示分裂的子细胞在第 帧所有新生细胞中的索引值；所以重新关联后的每一条细胞航迹都对应一个特殊的细胞标签。
[0066] 本发明的有益效果是所提出的方法能较好地修复由于细胞运动过快、漏检测、细胞黏连和分裂检测丢失等导致的航迹碎片，重建完整可靠的细胞谱系树。
附图说明
[0067] 图1为本发明方法流程图；
[0068] 图2为多细胞跟踪序列（第一行为序列1，第二行为序列2）图示；
[0069] 图3为序列1航迹恢复结果（a）航迹恢复前（b）航迹恢复后图示；
[0070] 图4为序列1航迹恢复结果（细胞谱系树）（a）航迹恢复前（b）航迹恢复后图示；
[0071] 图5为序列1航迹恢复结果（细胞位置曲线）（a）航迹恢复前（b）航迹恢复后图示；
[0072] 图6为序列2航迹恢复结果（a）航迹恢复前（b）航迹恢复后图示；
[0073] 图7为序列2航迹恢复结果（细胞谱系树）（a）航迹恢复前（b）航迹恢复后图示；
[0074] 图8为序列2航迹恢复结果（细胞位置曲线）（a）航迹恢复前（b）航迹恢复后图示。
具体实施方式
[0075] 下面结合本发明实例中的附图，对本发明实例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明的实施例，本领域技术人员在没有做创造性劳动前提下所获得的所有其他实施例，都属于本发明的保护范围。
[0076] 下面将结合附图对本发明实例作进一步地详细描述。
[0077] 本发明公开了一种基于启发式的蚁群航迹恢复方法，针对多目标跟踪中可能出现的航迹碎片，以最大帧间位移为约束条件，通过将发生于航迹片段之间的成本函数最小化来完成航迹碎片间的重新关联。本发明中，规定每一个航迹对应一个蚁群，每一个蚁群赋予一个特殊的身份信息（颜色），蚁群中的所有蚂蚁都从航迹的起始位置开始觅食行为，蚂蚁受到启发式函数和信息素强度的影响进行决策。在蚂蚁决策过程中，考虑两个不同事件：普通细胞迁移和细胞分裂。所有蚁群同时开始进入工作状态（觅食），首先蚂蚁以时间序列正序移动，当一只蚂蚁抵达某一航迹的结束位置，同时在后三帧内没有其他候选航迹时，该蚂蚁再以时间序列逆序反向决策移动，直到该蚂蚁抵达某一航迹片段的起始位置并且前三帧内无候选航迹时，此时此次觅食过程结束，该蚂蚁对其信息素场进行一次全局更新。当一个蚁群中的所有蚂蚁都完成一次觅食，该蚁群结束工作状态。当所有蚁群都结束工作状态，根据当前迭代的总成本再对所有信息素场进行一次全局更新。随着迭代次数的增加，蚂蚁受到信息素的影响更加趋向于选择成本更低的路径，信息素场不断增强，最终对每一个蚁群的信息素场进行归一化处理，再利用形态学运算提取出不同颜色的轨迹信息素场，将提取到的轨迹信息素场空间反映射到原始航迹空间，联合时序信息，获得航迹重新关联部分的信息，最终提取出完整的细胞谱系树。实验结果说明，本发明所提出的方法能较好地修复由于细胞运动过快、漏检测、细胞黏连和分裂检测丢失等导致的航迹碎片，重建完整可靠的细胞谱系树。
[0078] 主要术语与定义
[0079] 蚁群：表示一个由多个蚂蚁所构成的集合，其中每个蚂蚁的决策行为是随机的，且行为简单，但蚂蚁个体间相互协作，可共同完成某个复杂任务。
[0080] 蚁群觅食行为：同一蚁群中的蚂蚁从其巢穴出发，通过随机决策行为各自寻找食物源，当其中一只蚂蚁找到食物源，它会携带部分食物回到巢穴，并在经过的路径上释放一定量的信息素，信息素会随着时间的推移以一定程度挥发，这种信息素会影响其它蚂蚁的决策使其趋向于选择信息素浓度较强的路径寻找食物，一旦找到食物源也会携带部分食物回巢并释放信息素，蚂蚁数量很多，它们通过不同的路径觅食回巢，最终长度最短的路径上的信息素会越来越浓，形成一条最优化的路径。实施例
[0081] 成本函数定义：
[0082] 在本发明中，我们将原有连续航迹上的两个相邻帧细胞状态之间的成本设置为一个非常小的常数。假设在某一图像序列中共有 个断裂航迹， 表示在航迹碎片上第 帧的第 个细胞位置， 表示在航迹碎片 上第 帧的第 个细胞位置，其中 是一个小于等于3的正整数， 和 分别表示航迹索引，并且。那么，在不同的航迹碎片之间的两个细胞状态之间的成本表示为
[0083]
[0084] 其中， 是一个在 范围内的常数， 表示细胞位置 和细胞位置 之间的距离成本， 表示细胞位置 和细胞位置 之间的面积
成本。
[0085] 距离成本 定义为
[0086]
[0087] 其中， 表示细胞位置 和细胞位置 之间的距离， 和 分别表示输入细胞图像的高和宽。面积成本 定义为
[0088]
[0089] 其中， 表示细胞位置 的面积估计， 表示细胞位置 的面积估计， 表示两细胞面积交集，表示两细胞面积求和。
[0090] 蚂蚁决策
[0091] 首先进行蚁群初始化及各蚁群信息素场初始化，在本发明中，原始航迹和蚁群之间具有一一对应关系，即在每一个航迹碎片的初始细胞位置上分别放置一个蚁群，每一个蚁群对应一种特殊的身份信息（颜色），迭代开始时，所有蚁群同时进入工作状态（觅食），首先所有蚁群都以时间序列正序移动，进行正向决策：
[0092] 蚂蚁正向决策：当蚁群以时间序列正序移动时，假定蚁群中的任意一只蚂蚁 位于第 帧某一细胞位置 上，则蚁群正向决策过程实现如下描述：
[0093] 步骤1：初始化：首先设置在细胞位置 的蚂蚁 的初始搜索范围 ，获取所有航迹上每一帧细胞的位置信息和形态学信息，包括细胞面积、形状等。
[0094] 步骤2：蚁群中的每一只蚂蚁以最大帧间位移为约束条件选择下一步要移动到的细胞位置，以时间序列正序移动。以最大帧间位移为约束条件先确定 帧的候选细胞集，定义符号 表示集合里元素的数目，根据 的值，即候选细胞的数量分为以下三种情况：
[0095] （1）：若 ，即在 帧的候选细胞集 中有且仅有一个细胞，则蚂蚁直接移动到这一候选细胞；
[0096] （2）：若 ，即在 帧的候选细胞集 的数量大于等于2，则候选细胞集 中的所有细胞两两之间分别要进行相似度计算，来判断是否有分裂事件发生。设和 分别为第 帧的两个不同的细胞位置，且 ，则相似度
标准定义为
[0097]
[0098] 其中， 是一个在 范围内的常数，且 ， 表示面积相似度，表示距离相似度， 表示形状相似度，分别定义为
[0099]
[0100]
[0101]
[0102] 其中， 表示细胞的面积估计， 表示细胞间的距离， 表示细胞轮廓估计的长轴长度， 表示细胞估计轮廓的短轴长度。
[0103] 若候选细胞集 中细胞位置 和细胞位置 的相似度值大于某一给定阈值 ，则认为蚂蚁在当前时刻即将发生分裂事件，该蚂蚁复制成两只蚂蚁分别移动到细胞位置 和细胞位置 ，且 ；若候选细胞集中无任意两细胞的相似度大于某一给定阈值 ，则认为是普通的细胞迁移，蚂蚁根据概率选择移动到下一细胞位置，蚂蚁 从 出发，在候选细胞集 中选择细胞位置 的概率为
[0104]
[0105] 其中，和 分别表示信息素和启发式因子的相对重要性系数， 表示路径上的轨迹信息素量， 表示路径 上的启发式信息，为两细胞状态之间成本的倒数： 。
[0106] （3）： ，即在 帧的候选细胞集 中没有候选细胞，则将蚂蚁搜索范围扩大到下一帧，即 ，若此时 ，则重新进行步骤2。若 ，即蚂蚁 在接下来三帧内均未找到候选细胞，则该蚂蚁正向移动过程结束，开始进入反向决策。
[0107] 步骤3：当蚂蚁按照步骤2完成一次决策并移动到下一个细胞位置后，则在经过的轨迹 上释放一定量的信息素：
[0108]
[0109] 其中，表示信息素挥发系数， 表示一定量的信息素值。
[0110] 蚂蚁反向决策：当蚁群以时间序列逆序反向移动时，此时对应反向细胞运动过程，假定蚁群中的任意一只蚂蚁 位于第 帧某一细胞位置 上，则蚁群决策过程实现如下描述：
[0111] 步骤1：首先设置在细胞位置 的蚂蚁 的初始搜索范围 。
[0112] 步骤2：蚁群中的每一只蚂蚁以最大帧间位移为约束条件选择下一步要移动到的细胞位置，以时间序列逆序移动。以最大帧间位移为约束条件先确定 帧的候选细胞集，根据 的值，即候选细胞的数量分情况进行：
[0113] （1）：若 ，则将候选细胞依次与蚂蚁当前所在细胞位置和当前时刻中满足最大帧间位移约束条件的其他细胞位置分别进行相似度判断，设 为 帧的一个候选细胞位置， 为第 帧的另一个细胞位置，且 ，若相似度值大于某一给定阈值，则蚂蚁 当前所在细胞位置为 时刻 分裂的
细胞之一，则蚂蚁 移动到 ；若无相似度值大于某一给定阈值或当前时刻无其他细胞与候选细胞之间满足最大帧间位移约束条件，则蚂蚁根据概率选择移动到下一细胞位置，蚂蚁 从 出发，在候选细胞集 中选择细胞位置 的概率为
[0114]
[0115] （2）：若 ，即在 帧的候选细胞集 中没有候选细胞，则将蚂蚁搜索范围扩大到前一帧，即 ，若此时 ，则重新进行步骤2。若 ，即蚂蚁 在前三帧内均未找到候选细胞，该蚂蚁停止决策，蚂蚁此次觅食过程结束。
[0116] 步骤3：当蚂蚁按照步骤2完成一次决策并移动到下一个细胞位置后，则在经过的轨迹 上释放一定量的信息素：
[0117]
[0118] 其中，表示信息素挥发系数， 表示一定量的信息素值。
[0119] 全局信息素更新
[0120] 当一只蚂蚁 如上述完成一次觅食过程后，要根据该蚂蚁轨迹的成本值进行一次信息素更新：
[0121]
[0122]
[0123] 其中， 表示信息素残留系数，为一个常量， 表示蚂蚁 的移动轨迹， 表示的成本值；由于本发明中所定义的蚁群觅食行为具有随机性，有的蚂蚁会回到其出发位置（巢穴），而有的蚂蚁不会，于是根据蚂蚁是否回到其出发位置，设置不同程度的信息素更新：回到出发位置的蚂蚁信息素更新时 的值比未回到出发位置的蚂蚁信息素更新时 的值要大，这意味着回到巢穴的蚂蚁的信息素更新程度比未回到巢穴的蚂蚁的信息素更新程度要高。
[0124] 当所有蚁群中的蚂蚁都完成一次觅食过程，即所有蚁群都终止工作状态，此时当前迭代过程结束，所有蚁群的轨迹信息素场要根据本次迭代的总成本值再进行一次全局信息素更新：
[0125]
[0126]
[0127] 其中， 为一个常量， 表示本次迭代中第 个蚁群中第 只蚂蚁的移动轨迹，表示本次迭代中第 个蚁群中第 只蚂蚁移动轨迹的成本值， 表示本次迭代中所有蚁群中所有蚂蚁移动轨迹的总成本值， 表示蚁群的个数，表示一个蚁群中蚂蚁的个数。
[0128] 信息素场的提取和航迹的重新关联
[0129] 随着迭代次数的增加，蚂蚁受到信息素的影响更加趋向于选择成本更低的路径，信息素场不断得到增强，直到达到最大迭代次数，这时需要提取带有身份信息的信息素场，将信息素场空间映射入原始航迹空间，获得航迹恢复信息：
[0130] 步骤1：为了获得更加清晰的轨迹信息素场，对每个蚁群的信息素场进行阈值处理：
[0131]
[0132] 其中， 为信息素提取阈值， 表示第 个蚁群对应的信息素场中像素 的信息素强度。
[0133] 步骤2：分别对 个经过阈值处理的轨迹信息素场进行形态学处理，提取出 个带有不同身份信息（颜色）的轨迹信息素场，随后进入步骤3。
[0134] 步骤3：将不同颜色的轨迹信息素场进行轨迹融合处理，设两个不同的轨迹信息素场分别为 和 ，其中 和 分别代表两种不同的颜色，若 ，即包含 ，则将轨迹信息素场 删除；经过轨迹融合处理后，将剩余的带有身
份信息的轨迹信息素场叠加到同一个轨迹信息素场空间 ，设此时 中共有 种不同颜色的轨迹信息素场，分别用 表示， 表示轨迹信息素场的颜色，即
身份信息。
[0135] 步骤4：将带有身份信息的轨迹信息素场空间 映射到原始航迹空间 ，两空间坐标位置一一对应，关联映射关系为 ，即将轨迹信息素场每一个轨迹点投影至原始航迹空间 中对应的坐标位置，设轨迹信息素场空间 中的轨迹信息素场 经过关联映射 投影至 中的连续轨迹为 ， 为原始航迹空间中 个航迹碎片中的索引为 的航迹碎片，若
[0136]
[0137] 即 中的轨迹信息素场 经过关联映射至原始航迹空间 中的轨迹 包含多条航迹碎片时，则此多条航迹碎片可以得到恢复，联合时序信息完成原始航迹碎片间的重新关联，即可得到可靠的细胞谱系树。在本发明中，每一个细胞都拥有特殊的标签，这个标签由细胞第一次出现新生的帧数和细胞在新生的那一帧中所有新生细胞中的索引值构成，假设一个细胞的标签为 ，其中 表示细胞第一次出现的帧数， 表示这一细胞在第 帧中所有新生细胞中的索引值，当细胞发生普通迁移时标签不变，当细胞发生分裂时对应的两个子细胞的标签将分别变为 ，其中 表示发生分裂事件的帧数， 表示分裂的子细胞在第 帧所有新生细胞中的索引值。所以重新关联后的每一条细胞航迹都对应一个特殊的细胞标签。
[0138] 验证
[0139]
[0140] 表1 航迹恢复性能
[0141] 评价指标：
[0142] （完全航迹）：
[0143]
[0144] 其中， 表示完全重构的参考航迹数量， 表示所有计算航迹数量， 表示所有参考航迹数量（即真实航迹数量）。当一个参考航迹所有航迹节点都能分配到一个计算航迹的估计值时，称之为完全重构的参考航迹。
[0145] ：
[0146] 对于两个带标签的细胞状态集 和，其中 分别表示两状态集的细胞数量， 表示两状态集的
细胞状态， 表示两状态集的细胞标签。如果 ，则
距离为
[0147]
[0148] 其中， 代表两标签状态的截距并且 ， 表示两标签状态的基距， 表示取自元素 的长度为 的
集合， 表示一个范围为 的值。如果 ，则 ，且当
时 。基距 为
[0149]
[0150] 其中为 基距参数， 表示位置误差且 ， 表示标签误差，定义为
[0151]
[0152] 其中 ，如果 ， 则变为一个不带标签的指标，即 距离。如果 ，则对 的惩罚最明显。
[0153] 以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明披露的技术范围内，可轻易想到的变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应该以权利要求书的保护范围为准。
