八角形斯坦纳树问题的文化基因算法

针对多端线网互连问题,提出以超大规模集成电路物理设计中布线阶段应用较多的斯坦纳树为切入点,采用一种基于种群的全局搜索和基于个体的局部启发式搜索相结合的文化基因算法,对八角形斯坦纳树的结构进行优化,从而进一步缩减线长. 使用Prim算法预处理取得初始种群,并重新修改了原本的文化基因的编码以及相关操作,以便可以处理八角形斯坦纳树构建这一离散问题,利用八角形结构,使其能在全局范围内,快速收敛并全局寻优. 实验结果表明,所提算法能获得较好拓扑的八角形斯坦纳树,快速得到多端线网最优或者较优的布线结果,缩减布线的线长.     

一种改进的图像骨架提取算法

针对Zhang细化算法的不足提出改进算法。首先,根据提取的骨架特点设计细化模板,将骨架进行细化并且保持骨架的连通性和满足单像素,便于后续处理;其次,利用像素找出骨架的分支点,骨架减去分支点形成多个不连通区域,根据骨架特点选择不同的阈值,去除小于该阈值的连通分支,从而去除骨架毛刺,该步骤高效地除去了多余的噪音和毛刺,优化了骨架的视觉效果。仿真实验结果表明用改进算法提取图像骨架比Zhang细化算法得到的骨架效果更好,不但能够根据阈值的选择来除掉长短不一的毛刺,且不会破坏物体结构中重要的骨架。