Digital Halftoning: Algorithm Engineering Challenges
Summary :
Digital halftoning is a technique to convert a continuous-tone image into a binary image consisting of black and white dots. It is an important technique for printing machines and printers to output an image with few intensity levels or colors which looks similar to an input image. This paper surveys how algorithm engineering can contribute to digital halftoning or what combinatorial problems are related to digital halftoning. A common criterion on optimal digital halftoning leads to a negative result that obtaining an optimal halftoned image is NP-complete. So, there are two choices: approximation algorithm and polynomial-time algorithm with relaxed condition. Main algorithmic notions related are geometric discrepancy, matrix (or array) rounding problems, and network-flow algorithms.
- Publication
- IEICE TRANSACTIONS on Information Vol.E86-D No.2 pp.159-178
- Publication Date
- 2003/02/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- INVITED SURVEY PAPER
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Tetsuo ASANO, "Digital Halftoning: Algorithm Engineering Challenges" in IEICE TRANSACTIONS on Information,
vol. E86-D, no. 2, pp. 159-178, February 2003, doi: .
Abstract: Digital halftoning is a technique to convert a continuous-tone image into a binary image consisting of black and white dots. It is an important technique for printing machines and printers to output an image with few intensity levels or colors which looks similar to an input image. This paper surveys how algorithm engineering can contribute to digital halftoning or what combinatorial problems are related to digital halftoning. A common criterion on optimal digital halftoning leads to a negative result that obtaining an optimal halftoned image is NP-complete. So, there are two choices: approximation algorithm and polynomial-time algorithm with relaxed condition. Main algorithmic notions related are geometric discrepancy, matrix (or array) rounding problems, and network-flow algorithms.
URL: https://global.ieice.org/en_transactions/information/10.1587/e86-d_2_159/_p
Copy
@ARTICLE{e86-d_2_159,
author={Tetsuo ASANO, },
journal={IEICE TRANSACTIONS on Information},
title={Digital Halftoning: Algorithm Engineering Challenges},
year={2003},
volume={E86-D},
number={2},
pages={159-178},
abstract={Digital halftoning is a technique to convert a continuous-tone image into a binary image consisting of black and white dots. It is an important technique for printing machines and printers to output an image with few intensity levels or colors which looks similar to an input image. This paper surveys how algorithm engineering can contribute to digital halftoning or what combinatorial problems are related to digital halftoning. A common criterion on optimal digital halftoning leads to a negative result that obtaining an optimal halftoned image is NP-complete. So, there are two choices: approximation algorithm and polynomial-time algorithm with relaxed condition. Main algorithmic notions related are geometric discrepancy, matrix (or array) rounding problems, and network-flow algorithms.},
keywords={},
doi={},
ISSN={},
month={February},}
Copy
TY - JOUR
TI - Digital Halftoning: Algorithm Engineering Challenges
T2 - IEICE TRANSACTIONS on Information
SP - 159
EP - 178
AU - Tetsuo ASANO
PY - 2003
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E86-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2003
AB - Digital halftoning is a technique to convert a continuous-tone image into a binary image consisting of black and white dots. It is an important technique for printing machines and printers to output an image with few intensity levels or colors which looks similar to an input image. This paper surveys how algorithm engineering can contribute to digital halftoning or what combinatorial problems are related to digital halftoning. A common criterion on optimal digital halftoning leads to a negative result that obtaining an optimal halftoned image is NP-complete. So, there are two choices: approximation algorithm and polynomial-time algorithm with relaxed condition. Main algorithmic notions related are geometric discrepancy, matrix (or array) rounding problems, and network-flow algorithms.
ER -
English
