Aaiming the problem of shape analysis, we proposed a linear programming model based method to segment shapes into several meaningful areas called convex parts. In the past, the segmentation of shapes focused on the shortest path based method or other heuristic based method. In our work, we firstly divided shapes into several pieces by using Reeb Graph method in different directions. Then, the cost of each candidate cut and the concavity of each part were calculated, which constructed the linear programming function of the system. By solve the linear programming problem, we can easily find the optimal cuts and parts of the shape, which also can find physical meanings for them. This method can be used for medical image analysis and other shape analysis problems.%研究图形解构和分割的问题.针对复杂图形具有较为复杂的几何特性,无法简单的进行具有物理意义的切分的难点,提出了一种利用线性规划方法并使用若干约束条件的分割方法,能有效地将复杂图形切割成若干具有物理意义的小块.首先,利用Reeb Graph将图形在不同的方向上分解成若干小块,然后通过对小块之间的凹凸程度的描述以及切割线合适程度的描述,建立线性规划方程.通过对线性方程求最优解,最终判断待定切割线中的最优分割方案.仿真结果表明,提出的改进方法能够有效地对图像进行分割,图像边缘分割明显,不会出现若干物理意义不明显的分割小块,特别适合应用在复杂图像分割领域.
展开▼
