Study on the Rectangle Detection of the Layout Knowledge Graph and Heuristic Search Algorithm for the Weighted Circle Packing
Candidate Zhou AiMin Supervisor Prof. Li Ziqiang College Institute of Information Engineering Program Computer Technology Degree Master of Engineering University Xiangtan University Date April， 2014 摘 要 容器装填问题是将若干装填物互不冲突地放进一个容器中，要求容器的利用 率最优且满足给定的约束。该问题的应用背景包括：建筑设计、服装行业、电子 工业、航空航天、交通运输、机械制造、城市规划等诸多领域。装填方案的好坏 直接影响着它们的生产效率、经济效益和系统的安全性等性能指标。 容器装填问题是众多的装填问题当中最典型的一类，基于知识的求解方法是 目前研究的热点。本文讨论布局知识的获取与基于知识的带性能约束装填问题的 求解方法。它具体包括：(i) 以印刷电路板的设计为背景讨论圆形容器加权圆集 装填问题；(ii) 以卫星舱布局问题为背景讨论圆容器布局知识图的矩形检测问 题。对于(i)，由于其 NP-hard 属性，难以在多项式时间内求解。许多学者基于该 问题的模型提出了各自的求解算法，它包括：启发式算法、免疫算法、人机交互、 演化算法，如遗传算法、蚁群算法和文化算法及粒子群算法等、混合算法等。目 前的研究热点是基于知识的求解算法。对于(ii)，目前的检测方法包括：基于线 段检测的方法，窗口 Hough 变换方法和链码检测方法。但如何利用矩形的特征 有效而快速检测出矩形，特别是残缺矩形，仍然需要进一步研究。本文在国家自 然科学基金项目、湖南省教育厅重点科学研究项目的资助下，分别对上述问题(i) 和(ii)进行了许多探索，并取得了一些研究成果。 其创新点如下： (1) 针对布局知识解参数计算问题，本文提出一种布局知识解的多个矩形检 测方法。它先随机采样两个图像点，并在以此两点间的线段为直径的圆周上搜索 第 3 个图像点来确定侯选矩形，然后快速的确认该候选矩形是否为真矩形。在随 机获取两个图像点时，通过缩小样本大小（剔除孤立、半连续噪声）减少无效采 样；在确定矩形时，利用矩形的特征确定它的另外两个顶点，并给出了确认侯选 矩形为真矩形的方法，该方法快速有效能够减少大量的无效计算。数值实验结果 表明：本文提出的算法能快速检测多矩形，对带残缺边和对角的矩形检测也非常 有效。 (2) 针对启发算法搜索效率问题，本文提出一种加权圆集装填的知识启发式 搜索算法。它以权矩阵各行和的绝对值作为第一次赌轮选择待布圆的启发信息， 以当前放置的圆所在的行的行向量的绝对值作为下一次赌轮选择待布圆的启发 信息；放置圆时采用在前一次放置的圆的外围逆时方向排列放置当前待布圆。实 验数据表明本文启发式搜。索算法的有效性。 关键字：广义 Hough。变换; 多矩形检测; 圆集 Packing；启发式算法； I Abstract The container packing problems refer to place a number of objectives into a container
