Formulating Digital Halftoning of Continuous-tone Images As Optimization Problem with Analysis of its Computational Complexity

将连续色调图像的数字半色调表述为优化问题并分析其计算复杂度

• 批准号: 10680344
• 负责人: ASANO Tetsuo
• 金额: $ 1.86万
• 依托单位: Japan Advance Institute of Science and Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 1998
• 资助国家: 日本
• 起止时间: 1998 至 2000
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-10680344/
• 关键词: Algorithm; Optimization problem; Halftoning; Network flow; Computer experiments; ディジタルハーフトーニング; 組合せ最適化; 近似解法; 計算複雑度; グラフ理論; コンピュータ・グラフィックス; コンピュータ グラフィックス

In this study we have formulated the problem of digital halftoning to convert a continuous-tone image into a binary image as a combinatorial problem and analyzed it inherent computational complexity under some reasonable mathematical criterion. We obtained a conclusion that there is no efficient algorithm for solving the problem. This result is presented in an international conference with high evaluation. To merge theory and practice we have investigated traditional studies and coded most of them for comparison with our new algorithm. We also found that this problem is closely related to the problem of discrepancy and developed an algorithm with its performance guaranteed. We also found a new algorithm for finding an optimal solution under somewhat relaxed criterion based on a network flow algorithm and made experiments on many image data. The results are quite promising.

本文将数字半调将连续色调图像转换为二值图像的问题表述为一个组合问题，并在合理的数学准则下分析了其固有的计算复杂度。我们得到了一个结论，没有有效的算法来解决这个问题。这一成果已在国际会议上发表，并受到高度评价。为了将理论与实践结合起来，我们调查了传统的研究，并对其中的大部分进行了编码，以便与我们的新算法进行比较。我们还发现该问题与差异问题密切相关，并开发了一种保证其性能的算法。在网络流算法的基础上，提出了一种新的算法，在某种程度上放宽准则下求最优解，并在大量图像数据上进行了实验。结果很有希望。

项目成果

T.Asano,N.Kato,K.Kawashima: "A New Approximation Algorithm for Capacitated Vehicle Routing Problem on a Tree"Journal of Combinatorial Optimization. (採録決定).

T.Asano、N.Kato、K.Kawashima：“树上的容量车辆路径问题的新近似算法”组合优化杂志（已接受）。

浅野,河村.: "ディジタル直線検出問題の計算量に関するアルゴリズム論的考察"電子情報通信学会論文誌. J83-D-I. 80-89 (2000)

Asano, Kawamura.：“数字线路检测问题的计算复杂性的算法考虑”，电子、信息和通信工程师学会汇刊 J83-D-I 80-89 (2000)。

T.Asano, S,Kimura, and S.Shimazu: "Contour Representation of an Image with Applications (in Japanese)"Trans.of IPS of Japan. 39, 12. 3242-3251 (1998)

T.Asano、S、Kimura 和 S.Shimazu：“图像的轮廓表示及其应用程序（日语）”Trans.of 日本 IPS。

浅野,木村,嶋津: "画像の等高線表現とその応用"情報処理学会論文誌. 39. 3242-3251 (1998)

Asano、Kimura、Shimazu：“图像轮廓表示及其应用”日本信息处理学会汇刊 39. 3242-3251 (1998)。

T.Asano: "Effective Use of Geometric Information for Clustering and Related Topics"IEICE Trans.on Fundamentals. Vol.E83-D, No.3. 418-427 (2000)

T.Asano：“有效利用几何信息进行聚类和相关主题”IEICE Trans.on 基础知识。