DEVELOPMENT OF A GENERAL METHOD FOR DETECTING A SPECIFIED FAMILY OF CURVES IN A DIGITAL IMAGE

开发检测数字图像中特定曲线族的通用方法

• 批准号: 06680334
• 负责人: ASANO Tetsuo
• 金额: $ 1.41万
• 依托单位: OSAKA ELECTRO-COMMUNICATION UNIVERSITY
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for General Scientific Research (C)
• 财政年份: 1994
• 资助国家: 日本
• 起止时间: 1994 至 1995
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-06680334/
• 关键词: Computational Geometry; Pattern recognition; Algorithms; Digital lines and curves; Hough transform; 直線検出

The problem of detecting all digital line components contained in a black-white image is one of the most fundamental problems in pattern recognition. In this study we have developed efficient algorithms for detecting all of digital line components. We also developed space-efficient algorithms for detecting all of digital curve components. This is the first linear-space algorithm for the purpose for detecting curve components and in addition the first to define a family of digital curves using least possible number of parameters. More concretely, key ideas are duality transform between points and lines and efficient search in an arrangment of lines. One advantage of the proposed algorithms to be distinguished from the existing ones is that they can detect all possible line and curve components satisfying the conditions without missing one. We also analyzed the computational complexity of the problem itself and algorithms to establish the optimality of the proposed algorithms. Experimental results show the practical usefullness and effectiveness of the proposed methods.

检测黑白图像中包含的所有数字线条分量的问题是模式识别中最基本的问题之一。在这项研究中，我们开发了有效的算法来检测所有数字线路组件。我们还开发了节省空间的算法来检测所有数字曲线分量。这是第一个用于检测曲线分量的线性空间算法，也是第一个使用尽可能少的参数来定义数字曲线族的算法。更具体地说，关键思想是点和线之间的对偶变换以及线排列中的有效搜索。所提出的算法与现有算法的区别之一是它们可以检测满足条件的所有可能的直线和曲线分量而不会遗漏任何一个。我们还分析了问题本身和算法的计算复杂性，以确定所提出算法的最优性。实验结果表明了所提方法的实用性和有效性。

项目成果

浅野哲夫: "計算幾何学的手法の画像処理への応用" 画像ラボ. 29-32 (1994)

Tetsuo Asano：“计算几何方法在图像处理中的应用”图像实验室 29-32 (1994)

T. Asano, L. J. Guibas T. Tokuyama: "Walking in a Arrangement Topologically" Int. J. an Computational Geometry and Applications. 4. 123-151 (1994)

T. Asano、L. J. Guibas T. Tokuyama：“在拓扑排列中行走” Int。

N. Kanamaru, T. Nishizeki, T. Asano: "Efficient Enumeration of Grid Points in a Convex Polygon and Its Applications to Integer Programming" Int. J. an Computational Geometry and Applications. 4. 69-86 (1994)

N. Kanamaru、T. Nishizeki、T. Asano：“凸多边形中网格点的高效枚举及其在整数规划中的应用” Int。

浅野: "計算幾何学的手法の画像処理への応用" 画像ラボ. 29-32 (1994)

浅野：“计算几何方法在图像处理中的应用”图像实验室 29-32 (1994)

T.Asano,L.J.Guibas,T.Tokuyama: "Walking in an Arrangement Topologically" International J.on Computational Geometry and Applications. 4. 123-151 (1994)

T.Asano，L.J.Guibas，T.Tokuyama：“拓扑排列中的行走”国际计算几何及其应用杂志。