欢迎来到知嘟嘟! 联系电话:13336804447 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13336804447
知嘟嘟经纪人
收藏
专利号: 2022102368332
申请人: 南京邮电大学
专利类型:发明专利
专利状态:已下证
专利领域: 计算;推算;计数
更新日期:2026-11-16
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种求解图像分割问题的基于邻域分解的迭代局部搜索方法,其特征在于:所述方法包含如下步骤:步骤1,输入待分割图像,图像划分个数K和扰动参数kmin、kmax、kstep,进行预处理生成带权无向图G,随机生成初始可行解S0;

步骤2,执行局部搜索,使用基于邻域分解的局部搜索算法对于初始可行解进行局部搜索,从而得到当前解Sc;

步骤2中,局部搜索算法使用增量计算,具体包括如下步骤:

构建图G的拉普拉斯矩阵LM和每个类的二进制量Xl;图的拉普拉斯矩阵LM涉及到图G的度矩阵DM和邻接矩阵AM;图G的度矩阵DM是一个对角矩阵,对角元素就是原图中每个点的度,即DM[i][i]=si,点vi的度si即是该点发出的边权重之和,表示为:wij为点vi和点vj之间的边权重;邻接矩阵AM[i][j]=wij;图G的拉普拉斯矩阵LM=DM-AM;

每个类的二进制量Xl=(X1l,X2l,…Xnl),其中:

Xil表示节点i是否属于类Cl:若Xil为1,则表示节点i是属于类Cl;否则表示不属于;

每当对于当前解进行单点移动的邻域动作生成一个邻居解时,对于类Cm发生切割边变换的数量为:公式中∑i∈mLM[i][j]Xim为类Cm与点vj之间的原切割边数的相反数,而sj+∑i∈mLM[i][j]Xim为单点移动后点vj与其他类的切割边数,两项相加则为点vj移动前切割边数与移动后切割边数之差;为正数表示改进后切割边数增加的数量,反之若为负数,则表示切割边数减少的数量;

对于类Cn发生切割边变换的数量为:

公式中sj+∑i∈nLM[i][j]Xin为类Cn中的点vj与其他类的切割边数,而∑i∈nLM[i][j]Xin为单点移动后类Cn与点vj之间的切割边数的相反数,两项相加的值若为正数,则表示切割边数减少的数量,反之则表示切割边数增加的数量;

根据上述的增量计算得出切割边的变换数,从而得出该邻居解是否优于当前解,实现快速审核;

步骤3,进入扰动阶段,对当前解进行扰动强度为k的扰动,从而生成扰动解Sp;

步骤4,进入局部搜索阶段,使用步骤2的算法对于扰动解执行局部搜索,从而产生新的局部最优解Si;

步骤5,进入解的更新阶段,若改进解Si优于当前解Sc,则将改进解Si替换当前解Sc,否则当前解Sc不变;

步骤6,判断是否满足终止条件,若满足终止条件则转至步骤7,否则转至步骤3;

步骤7,满足终止条件,输出当前最优解Sb,流程停止。

2.根据权利要求1所述的一种求解图像分割问题的基于邻域分解的迭代局部搜索方法,其特征在于:步骤1所述的初始可行解随机生成方法为:首先,根据有权无向图G构造邻接表;接着,随机选择K个不同的节点作为初始点;然后,通过邻接表所包含的信息对于初始选择的K个顶点从相邻点依次拓展直至所有节点分配完成;最终,将有权无向图G分割为K类,即{C1,C2,…,CK}。

3.根据权利要求1所述的一种求解图像分割问题的基于邻域分解的迭代局部搜索方法,其特征在于:步骤2中,进入局部搜索,使用基于邻域分解的局部搜索算法对于初始可行解进行改进生成当前解,其中基于邻域分解的局部搜索算法主要框架为邻域下降算法与邻域的分解。

4.根据权利要求3所述的一种求解图像分割问题的基于邻域分解的迭代局部搜索方法,其特征在于:邻域下降算法中,将一个解s的邻域定义为由某一种动作M对其进行变换所得解的集合,即:其中s为当前解,s'为对解s进行变换后的解,M为变换的动作,符号表示在解s上进行变换动作M;邻域下降算法使用单点移动邻域N1(s):其中,s表示当前解;表示一个单点移动动作,即一个顶点v从类Ci移动到类Cj;邻域下降算法主要步骤为:首先,对于当前解进行邻域动作产生邻居解;接着比较当前解与邻居解的优劣,若一旦找到某一邻居解优于当前解,则使用邻居解替换当前解并更新邻居解进行搜索;否则继续进行邻域动作,搜索邻居解,直至整个邻域搜索完成且没有改进,获得局部最优解。

5.根据权利要求3所述的一种求解图像分割问题的基于邻域分解的迭代局部搜索方法,其特征在于:邻域的分解中,邻域N1(s)划分为K×(K-1)个互不相交的邻域块B1[i][j](s);B1[i][j](s)表示将类Ci中的点依次放入类Cj中的这一动作的集合,表示为:

0-1状态矩阵记录各个邻域块的状态信息,其中每个0-1变量对应一个邻域块,即M1[i][j]对应邻域块B1[i][j](s),M1[i][j]表示邻域块B1[i][j](s)是否发生更新。若邻域块B1[i][j](s)发生更新,则将M1[i][j]置为1,否则将其置为0;而且,状态矩阵在初始化时,对角元素均设置为0,其余元素设为1;

通过实时更新状态矩阵里元素的值来记录哪些邻域块还未搜索,哪些邻域块已经搜索完成;若搜索完整个邻域块B1[i][j]后,发现一个更优的邻居解,则根据首次改进的搜索策略,立即使更优的邻居解替换当前解,并将B1[i][j]邻域块所对应的状态矩阵M1[i][j元素置1;而邻域块B1[i][j]所对应发生改变的是类Ci和类Cj,从而需将状态矩阵中涉及到类Ci和类Cj有关的元素值全部置1,即矩阵M1[i][t]、M1[t][i]、M1[t][j]和M1[j][t]均置为1,1≤t≤K。

6.根据权利要求1所述的一种求解图像分割问题的基于邻域分解的迭代局部搜索方法,其特征在于:步骤2中,基于邻域分解的局部搜索算法步骤为:步骤2.1,输入解存于当前解;

步骤2.2,初始化状态矩阵;

步骤2.3,从当前邻域动作N1(s)所对应的状态矩阵M1开始,依次搜索元素值为1的邻域块;若出现改进解,则转到步骤2.4;否则继续搜索下一个邻域块直到整个邻域搜索完成转到步骤2.5;

步骤2.4,使用改进解替换当前解,更新状态矩阵,并转到步骤2.3;

步骤2.5,基于邻域分解的变邻域搜索算法停止,输出当前解为局部最优解。

7.根据权利要求1所述的一种求解图像分割问题的基于邻域分解的迭代局部搜索方法,其特征在于:步骤3,进入扰动阶段,对当前解进行扰动强度为k的随机扰动,即进行k次的随机单点移动操作。

8.根据权利要求1所述的一种求解图像分割问题的基于邻域分解的迭代局部搜索方法,其特征在于:步骤5,进入更新阶段,若改进解优于当前解,则使用改进解替换当前解,并将扰动强度k=kmin,kmin为扰动强度最小值;否则,扰动强度k=k+kstep,kstep为递增的扰动强度;其中,若扰动强度k大于扰动强度最大值kmax,则重置扰动强度k=kmin。

9.根据权利要求1所述的一种求解图像分割问题的基于邻域分解的迭代局部搜索方法,其特征在于:步骤6中,终止条件设置为最大迭代次数或者是最大计算时间。