Digital Halftoning: Algorithm Engineering Challenges
スポンサーリンク
概要
- 論文の詳細を見る
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.
- 社団法人電子情報通信学会の論文
- 2003-02-01
著者
関連論文
- Voronoi Diagrams with Respect to Criteria on Vision Information
- Space-Efficient Algorithm for Image Rotation
- Constant-Work-Space Image Scan with a Given Angle
- Inserting Points Uniformly at Every Instance
- On Detecting Digital Line Components in a Binary Image
- Digital Curve Approximation with Length Evaluation
- Topological Walk Revisited(Special Section on Discrete Mathematics and Its Applications)
- A Linear Time Algorithm for Binary Fingerprint Image Denoising Using Distance Transform
- Digital Halftoning Algorithm Based on Random Space-Filling Curve
- Arranging Fewest Possible Probes to Detect a Hidden Object with Industrial Application
- Digital Halftoning: Algorithm Engineering Challenges
- Algorithmic Evaluation of Line Detection Problem
- Halftoning Through Optimization of Restored Images : A New Approach with Hardware Acceleration
- NP-completeness of generalized Kaboozle
- A Small-Space Algorithm for Removing Small Connected Components from a Binary Image