本論文中提出兩種改良式之數位半色調技術與一種改良式之數位多色調技術以供硬體輸出設備之使用。數位半色調技術主要功能是將連續色階影像轉換至有限色階影像，並且以有限色階表現連續色階之結果。由於色階數量的降低，將會造成轉換影像有所失真，因此如何降低此失真情況以產生良好的影像品質，為數位半色調技術的研究目標之一。此外，現今影像解析度越來越高，人們對於印表機處理速度之要求，數位半色調技術必須快速地轉換影像以供硬體輸出設備之使用，因此數位半色調技術的處理效能也將納入評估的項目。
本論文前半部分基於提高影像品質與處理效能提出兩種數位半色調技術。有鑑於統計式查表法之高效率處理之特性，本論文提出的第一個方法為多查詢表之查表法。統計式查表法雖然在點分佈上能有接近直接二元搜尋法的特性，不過透由自相關評估工具就可發現其差異，在本方法中數個查詢表將依不同特徵分類並適應不同的影像內容以提供更佳的點分佈特性。在實驗結果中驗證此方法與直接二元搜尋在點分佈上具有高相似性。第二個方法為相依於影像內容之點擴散法，其中點擴散法具有平行處理之特性，但週期性圖樣帶來的負面效應，造成影像品質的降低，因此本方法提出有效抵抗週期性圖樣之改良式之點擴散法藉此提升影像品質，並且同時保有點擴散法的平行處理之特性。在實驗結果中驗證此方法在具平行處理特性之方法中能提供最佳的影像品質，並且在影像結果中不具週期性圖樣。
本論文後半部分以提升影像品質為主要目標，提出一種改良式之數位多色調技術，該技術為數位半色調技術之延伸技術，其特色為具有較多的輸出色階以降低轉換時的失真情況。雖然數位多色調技術能夠提供更高的影像品質，但是帶狀效應會造成負面的影響，因此本論文提出色調替代之錯誤擴散法以抵抗帶狀效應。在實驗結果中驗證此方法為一個有效率的演算法，並能提供高影像品質多色調影像，實驗結果可看出帶狀效應明顯被消除，影像品質遠較前人所提方法來得好。

In this thesis, three techniques, including two improved digital halftoning algorithms and one digital multitoning algorithm, are proposed to convert images for output devices. Digital halftoning is a technique for converting continuous-tone images into limited-tone images. The distortion between an original image and the converted image is inevitable, since the number of the corresponding output levels is less than the continuous-tone. Thus, the main object of the halftoning is to reduce the distortion induced from this transformation. Nowadays, the processing performance of the halftoning has become a critical issue as the image resolution is increasing. Another key element of this thesis is to effectively boost the processing efficiency.
The first proposed method is the Multiple Look-Up Table (MLUT) which is based on the look-up table halftoning, and is an effective technique for yielding satfactory image quality. According to the experiment results, the dot distribution generated by the proposed method can approximate to the well-known direct binary search halftoning which can achieve the best image quality so far, and thus it can be a very competitive candidate in coping printing industry. The second proposed method is the Content-Dependent Dot Diffusion (CDDD) which is based on Dot Diffusion (DD). The proposed CDDD can provide better image quality and a near aperiodic characteristic simultaneously comparing to the former parallel methods.
The multitoning is a technique which extends the halftoning by adopting more than two quantification levels for reducing the distortion between an original image and the converted image. Yet, the banding effect disturbs the visual perception, and thus degrades the image quality. To improve the image quality by removing the banding effect, the third method termed Tone-Replacement Error Diffusion multitoning (M-TRED), is proposed. According to the experimental results, the proposed method can provide excellent tone-similarity and dot-distribution simultaneously comparing to the former banding-free methods in the literature.

[1] USC-SIPI database: http://sipi.usc.edu/database
[2] P. Hamill, “Line printer modification for better grey level pictures,” Computer Graphics and Image Proc., vol. 6, pp. 485-491, 1977.
[3] K. Knowlton and L. Harmon, “Computer-produced greyscales,” Computer Graphics and Image Proc., vol. 1, pp.1-20, 1972.
[4] B. Perry and M. L. Mendelsohn, “Picture generation with a standard line printer,” Comm. Of the ACM, 7(5), pp. 311-313, 1964.
[5] J. Jarvis and C. Roberts, “A new technique for displaying continuous tone images on a bilevel display,” IEEE Trans. Communication, 24(8), pp. 891-898, Aug. 1976.
[6] R. Ulichney, Digital halftoning. Cambridge, MA: MIT Press, 1987.
[7] R. Ulichney, “The void-and-cluster method for dither array generation,” Proc. SPIE 1913, pp. 223-343, 1993.
[8] R. W. Floyd and L. Steinberg, “An adaptive algorithm for spatial gray scale,” in proc. SID 75 Digest. Society for information Display, pp. 36-37, 1975.
[9] J. F. Jarvis, C. N. Judice, and W. H. Ninke, “A survey of techniques for the display of continuous-tone pictures on bilevel displays,” Comp. Graph. Image Proc., 5(1), pp. 13-40, 1976.
[10] P. Stucki, “MECCA-A multiple-error correcting computation algorithm for bilevel image hardcopy reproduction,” Res. Rep. RZ1060, IBM Res. Lab., Zurich, Switzerland, 1981.
[11] J. N. Shiau and Z. Fan, “A set of easily implementable coefficients in error diffusion with reduced worm artifacts,” SPIE, 2658: 222-225, 1996.
[12] P. Li and J. P. Allebach, “Block interlaced pinwheel error diffusion,” JEI, 14(2), Apr-Jun. 2005.
[13] V. Ostromoukhov, “A simple and efficient error diffusion algorithm,” Computer Graphics (Proceedings of SIGGRAPH 2001), pp. 567-572, 2001.
[14] B. Zhou and X, Fang, “Imporving mid-tone quality of variable-coefficient error diffusion using threshold modulation,” ACM Trans. Graphics, vol. 22, pp. 437-444, 2003.
[15] D. E. Knuth, “Digital halftones by dot diffusion,” ACM Trans. Graph., 6(4), Oct. 1987.
[16] M. Mese and P. P. Vaidyanathan, “Optimized halftoning using dot diffusion and methods for inverse halftoning,” IEEE Trans. Image Processing, 9(4), pp. 691-709, Apr. 2000.
[17] J. M. Guo and Y. F. Liu, “Improved dot diffusion by diffused matrix and class matrix co-optimization,” IEEE Trans. Image Processing, 18(8), August 2009.
[18] S. Lippens and W. Philips, “Green-noise halftoning with dot diffusion,” in Proc. SPIE/IS&T - The International Society for Optical Engineering, vol. 6497, no. 64970V, 2007.
[19] M. Analoui and J. P. Allebach, “Model based halftoning using direct binary search,” Proc. SPIE, vol. 1666, pp. 96-108, 1992.
[20] J. P. Allebach, “FM screen design using DBS algorithm,” in Proc. ICIP, vol. 1, Lausanne, Switzerland, pp. 549-552, 1996.
[21] M. A. Seldowitz, J. P. Allebach, and D. W. Sweeney, “Synthesis of digital holograms by direct binary search,” Appl. Opt., 26(14), pp. 2788-2798, July 1987.
[22] D. J. Lieberman and J. P. Allebach, “Efficient model based halftoning using direct binary search,” IEEE ICIP, pp. 775-778, 1997.
[23] D. J. Lieberman and J. P. Allebach, “A dual interpretation for direct binary search and its implications for tone reproduction and texture quality,” IEEE Trans. Image Processing, 9(11), pp. 1950-1963, 2000.
[24] S. H. Kim and J. P. Allebach, “Impact of HVS models on model-based halftoning,” IEEE Trans. Image Processing, 11(3), pp. 258-269, 2002.
[25] M. Mese and P. P. Vaidyanathan, “Look up talbe (LUT) method for image halftoning,” in Proc. ICIP vol. 3, pp. 993-996, 2000.
[26] D. Kacker and J. P. Allebach, “Aperiodic micro screen design using DBS and training,” in Proc. SPIE – The International Society for Optical Engineering, vol. 3300, pp. 386-397, 1998.
[27] “Multilevel image printing device,” U.S. Patent 4 434 431, Feb. 28, 1984.
[28] “Ink-jet printing method and apparatus,” U.S. Patent 6 942 310, Sep. 13, 2005.
[29] Q. Yu, K. J. Parker, K. Spaulding, and R. Miller, “Digital multitoning with overmodulation for smooth texture transition,” J. Electron. Imag., 8(3), pp. 311–321, Jul. 1999.
[30] B. W. Kolpatzik and C. A. Bouman, ‘‘Optimized error diffusion for image display,’’ J. Electron. Imaging 1, pp. 277–292, 1992.
[31] S. Sugiura and T. Matika, ‘‘An improved multilevel error diffusion method,’’ J. Imaging Sci. Technol. 39, pp. 495–501,.
[32] Q. Yu and K. Spaulding, ‘‘Combining error diffusion, dithering and over-modulation for smooth multilevel printing,’’ in Color Imaging: Device-Independent Color, Color Hardcopy, and Graphic Arts V, R. Eschbach and G. G. Marcu, eds., Proc. SPIE 3963, pp. 446–457, 2000
[33] F. Faheem, D. L. Lau, and G. R. Arce, ‘‘Multilevel halftoning using bilevel quantizers,’’ in Proceedings of IS&T’s 2001 Processing Images, Image Quality, Capturing Images, Systems (PICS) Conference (Society for Imaging Science and Technology, Springfield, Va., 2001), pp. 51–54.
[34] G. Lin and J. P. Allebach, “Multilevel screen design using direct binary search,” in Proc. SPIE Conf. Ser., Dec. 2001, vol. 4663, pp. 264–277.
[35] I. Katsavounidis and C. –C. J. Kuo, “A multiscale error diffusion technique for digital halftoning,” IEEE Trans. Image Process., vol. 6, no. 3, pp. 483-490, Mar. 1997.
[36] G. Sarailidis and I. Katsavounidis, “A multiscale Error Diffusion Technique for Digital Multitoning,” IEEE Trans. Image Processing, vol. 21, no. 5, May 2012.
[37] J. B. Rodriguez, G. R. Arce, and D. L. Lau, “Blue-noise multitone dithering,” IEEE Trans. Image Process., vol. 17, no. 8, pp. 1368–1382, Aug. 2008.
[38] M. Liu, “Fingerprint classification based on Adaboost learning from singularity features,” Pattern Recognition, 43(3), pp. 1062-1070, March 2010.
[39] Q. Zhang, H. Yan, “Fingerprint classification based on extraction and analysis of singularities and pseudo ridges,” Pattern Recognition, 37(11), pp. 233-2243, November 2004.
[40] W. J, Yang, K. L. Chung, and H. Y. M. Liao, “Quality-efficient demosaicing for digital time delay and integration images using edge-sensing scheme in color difference domain,” Journal of Visual Communication and Image Representation, 23(5), pp. 729-741, July 2012.
[41] K. L. Chung, W. J, Yang and W. M. Tan, “Efficient edge-preserving algorithm for color contrast enhancement with application to color image segmentation,” Journal of Visual Communication and Image Representation, 19(5), pp. 299-310, July 2008.
[42] X. Li and M. T. Orchard, “Novel Sequential Error-Concealment Techniques Using Orientation Adaptive Interpolation,” IEEE Trans. Circuts and Systems for Video Technology, 12(10), October 2002.
[43] X. Li and M. T. Orchard, “New Edge-Directed Interpolation,” IEEE Trans. Image Processing, 10(10), October 2001.
[44] A. Rao, “T Taxonomy for Texture Description and Identification,” New York, NY: Springer-Verlag, 1990.
[45] L. Hong, Y. Wan, and A. Jain, “Fingerprint image enhancement: algorithm and performance evaluation,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 20, no. 8, pp. 777-789, Aug. 1998.
[46] R. C. Gonzalez and R. E. Woods, Digital Image Processing, 2nd ed., Reading, MA: Addison-Wesley, 1992.
[47] P. Viola and M. J. Jones, "Robust real-time object detection," Second International Workshop on Statistical and Computational Theories of Vision, July 2001.
[48] G. Shakhnarovich, P. A. Viola, and B. Moghaddam, "A unified learning framework for real time face detection and classification," Fifth IEEE International Conference on Automatic Face and Gesture Recognition, pp.14-21, May 2002.
[49] 張斐章、張麗秋，類神經網路，東華書局，台北，第78-88頁(2005)。
[50] B. Widrow and M. E. Hoff, “Adaptive switch circuits,” IRE Western Electric Shhow and Convention Recode, part 4, pp. 96-104, 1960.
[51] P. C. Chang, C. S. Yu and T. H. Lee, “Hybrid LMS-MMSE inverse halftoning technique,” IEEE Trans. On Image Processing, vol. 10, no. 1, pp. 95-103, Jan. 2001.
[52] 李世炳、鄒忠毅，「簡介導引模擬退火法及其應用」，中央研究院物理研究所務理雙月刊，第二十四卷，第二期，第307-319頁(2002)。
[53] S. Kirkpatrick et al., “Optimization by simulated annealing,” Science 220, pp. 671-680, 1983.
[54] J. H. Holland, Adaptation in Natural and Artificial Systems. University of Michigan Press: Ann Arbor, MI, 1975.
[55] M. Mitchell, An introduction to genetic algorithm, Cambridge, MA: MIT Press, 1996.
[56] Q. Huynh-Thu and M. Ghanbari, "Scope of validity of PSNR in image/video quality assessment," Electronics Letters, 44(13), pp. 800–801, 2008.
[57] R. Nasanen, “Visibility of halftone dot textures,” IEEE Trans. Syst. Man, Cybern, SMC-14(6), pp.920-924, Dec. 1984.
[58] F. W. Cambell, R. H. S. Carpenter, and J. Z. Levinson, “Visibility of aperiodic patterns compared with that of sinusoidal gratings,” J. Physiol., 204(2), pp. 283-298, 1969.
[59] J. L. Mannos and D. J. Sakrison, “The effects of a visual fidelity criterion on the encoding of images,” IEEE Trans. Information Theory, IT-20(4), July 1974.
[60] S. Daly, “Subroutine for generation of a two dimensional human visual contrast sensitivity function,” Eastman Kodak, Tech. Rep. 233203y, 1987.
[61] D. L. Lau and R. Ulichney, “blue-noise halftoning for hexagonal grids,” IEEE Trans. Image Process., vol. 15, no. 5, pp. 1270-1284, May 2006.
[62] Testing image set: http://msp.ee.ntust.edu.tw/public%20file/JYChang/TestingImage Set.rar
[63] J. Sullivan, L. Ray, and R. R. Miller, “Design of minimum visual modulation halftone patterns,” IEEE Trans. Syst., Man, Cybern., vol. 21, no. 1, pp. 33-38, Jan. 1991.
[64] P. Li and J. P. Allebach, "Look up Table based halftoning Algorithm", IEEE Trans. Image Processing, vol. 9, no. 9, Sept. 2000.
[65] NTUST-MSP-T database: http://msp.ee.ntust.edu.tw/public%20file/JYChang/TestIma geSet.rar
[66] G. Lin and J. P. Allebach, “Multilevel screen design using direct binary search,” in Proc. SPIE Conf. Ser., Dec. 2001, vol. 4663, pp. 264–277.