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

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

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.