@techreport{oai:kanazawa-u.repo.nii.ac.jp:00055713,
 month = {Mar},
 note = {本研究では,濃淡画像を白黒の2値で出力するための技術であるハーフトーニングを組み合わせ最適化問題として定式化するとともに,その本質的な計算複雑度の解析を行った.この種の技法は,ファクシミリやレーザプリンタのように黒点しか出力できない出力装置で濃淡画像を扱う際に不可欠であり,実用的な側面から様々な方法が提案されてきた.本研究では,出力の2値画像を評価するのに合理的と思われる数学的基準を設定して,その基準の下で最適な解を求める問題の本質的な計算複雑度を解析した.その結果,妥当な仮定の下では効率よく解くアルゴリズムは存在しないという結論を得ることができた.この結果は理論計算機科学の国際会議でも発表し,高い評価を得た.また,本研究では理論と応用の融合を目指すために,従来から提案されている手法を詳しく調査し,かつそれらの手法をプログラムの形に実現することによって提案手法との比較を行った.さらに,この問題が計算幾何学におけるディスクレパンシーの問題と密接に関連していることを発見し,最悪の場合の性能を保証することができるアルゴリズムを開発した.これとは全く別の方向の手法としてグラフ理論において長年研究されてきたネットワークフローの技術が応用できることを発見し,巨大なネットワーク問題を解くことにより緩和した基準の下では最適な解を多項式時間で求めることができることを証明し,実際にプログラミングをして計算機実験を行った., 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., 研究課題/領域番号:10680344, 研究期間(年度):1998 - 2000, 出典：「濃淡画像のハーフトーニングの最適化問題としての定式化と計算複雑度解析」研究成果報告書　課題番号10680344
（KAKEN：科学研究費助成事業データベース（国立情報学研究所）） 
（https://kaken.nii.ac.jp/ja/report/KAKENHI-PROJECT-10680344/106803442000kenkyu_seika_hokoku_gaiyo/）を加工して作成, 金沢大学 / 北陸先端科学技術大学院大学},
 title = {濃淡画像のハーフトーニングの最適化問題としての定式化と計算複雑度解析},
 year = {2002}
}