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.