[发明专利]基于朱刘法和蚁群法的群体图像编码结构生成方法

摘要

本发明公开了一种基于朱刘法和蚁群法的群体图像编码结构生成方法。解决了现有多数方法不能保证用户即时访问以及HAP方法编码效率提升不高的问题。实现步骤为：构造群体图像相互关系的有权有向图；使用朱刘方法得到最小生成树；判断最小生成树是否满足深度限制；若满足，则输出该最小生成树，还原成图像，构成群体图像编码结构；若不满足深度限制，采用适宜蚁群法的规则添加新边，使用最大最小蚁群法对最小生成树进行深度限制，输出深度受限的最小生成树，还原成图像，构成群体图像编码结构。本发明生成的深度受限最小生成树权值小，编码效率高，且能保证用户即时访问。可应用于云中图像压缩、个人相册压缩等领域。

主权项

1.一种基于朱刘法和蚁群法的群体图像编码结构生成方法，其特征在于，包括有如下步骤：/n(1)构造群体图像相互关系的有权有向图：将群体图像抽象为有权有向图，即将群体图像中每个图像抽象为节点，并根据图像的相关性表征为两两节点之间的距离，相关性越大，距离越短，得到满足各个节点之间相互关系的有权有向图G(V,E)，其中，V为节点集合，E为有向边集合；/n(2)初始化：给定最大深度限制d_max，用于限制最终树形图的深度；给定节点个数N的大小为节点集合V中节点的个数，实现对有权有向图G(V,E)的初始化；/n(3)在有权有向图G(V,E)中使用朱刘方法得到最小生成树T：/n(3a)对有权有向图G(V,E)进行预处理，得到预处理后的有权有向图G₁(V,E)：虚拟一个根节点r，将该根节点r与其他所有节点的距离定义为有权有向图G(V,E)中所有边的权值之和；对于任意两个节点v_i和v_j，若从节点v_i到节点v_j有多条边，则只保留其中最短的一条；/n(3b)寻找所有节点的最短入边，构成最短入边集合P，节点v的最短入边的起点用π(v)来表示；/n(3c)判断最短入边集合P＝{＜π(v),v＞}是否构成环，其中，节点v∈V且v≠r，若不构成任何环，得到最小生成树T，跳转至步骤(4)；否则，执行步骤(3d)；/n(3d)对构成环的有权有向图进行缩环处理，并返回步骤(3b)；/n(4)判断最小生成树的深度dep(T)是否大于最大深度限制d_max，若是，则执行步骤(5)；否则，则该最小生成树T即为深度受限的最小生成树，执行步骤(7)；/n(5)采用适宜蚁群法的规则对最小生成树T添加新边＜v_i,v_j＞，得到添加新边＜v_i,v_j＞后的有权有向图G₂(V,E)，添加规则是节点v_i的深度dep(v_i)小于节点v_j的深度dep(v_j)且dep(v_j)＞d_max；/n(6)在添加新边＜v_i,v_j＞后的有权有向图G₂(V,E)使用最大最小蚁群法对最小生成树进行深度限制：/n(6a)初始化最大最小蚂蚁法参数：给定蚂蚁个数为m，设置最大迭代次数F，置全局最优解的初始权值为无穷大，已迭代次数iter为0；/n(6b)构造用于存放蚂蚁通过的节点和边的禁忌表Tabu_k,k代表任意一只蚂蚁，k＝1,2,…,m，并初始化为空；/n(6c)将当前节点集C中所有节点添加到所有蚂蚁的禁忌表Tabu_k中，其中C＝{v|dep(v)＜d_max}，k＝1,2,…,m，置本次迭代最优解的初始权值为无穷大；/n(6d)取第k只蚂蚁，计算其深度限制最小生成树T_k(V,E)；/n(6e)计算当前蚂蚁k深度限制最小生成树T_k(V,E)的权值Q_k，清空该蚂蚁对应的禁忌表Tabu_k；/n(6f)判断全部蚂蚁是否找到当次深度限制最小生成树T_k(V,E)，若是，执行步骤(6g)，否则，返回步骤(6d)；/n(6g)从所有蚂蚁的权值(Q₁，Q₂，…Q_k，…，Q_m)中选取最优蚂蚁的权值Q_best，判断其权值Q_best的权值是否小于本次迭代的最优解，若是，则更新当前迭代最优解；再判断权值Q_best的权值是否小于全局最优解，若是，更新全局最优解；/n(6h)计算最大信息素τ_max和最小信息素τ_min；/n(6i)更新路径信息素τ_ij(t+1)，其中t表示当前时刻；/n(6j)迭代次数iter加1，判断迭代次数是否达到最大迭代次数F，若是，全局最优解即为对应的深度限制的最小生成树，否则，返回步骤(6c)；/n(7)输出深度受限的最小生成树，并将节点还原为图像，构成群体图像伪视频序列编码结构。/n