半色調影像回復是將輸入的半色調影像重建為灰階的影像。最近Kim 提出了
利用決策樹學習機制來作回復半色調的影像，可以得到較好的影像品質。這篇論
文提出了植基於紋理與決策樹的半色調影像回復技術。首先我們建置一棵類似於
Kim 所提出之決策樹，接著利用向量量化的方法，將附著在每個決策樹葉子上的
子影像集建立出ㄧ個碼表。碼表中每個碼對應到一個回復的灰階值。在重建灰階
影像的過程中，首先利用高斯遮罩作用於輸入的半色調影像並得到ㄧ個暫時的灰
階影像。利用半色調影像的黑白紋理，可以在紋理決策樹中找到一個對應的葉
子。接著，利用暫存灰階影像的紋理，可以在碼表中找到最近的碼並得到其對應
的重建灰階值。在兩組不同大小的訓練與測試影像中，實驗結果說明我們所提出
的演算法再第一組中能提供最佳的影像品質，另外在兩組中都達到了最佳的視覺
品質在最近所提出的四個演算法中。

Inverse halftoning (IH) is used to reconstruct the gray image from an input halftone image. Recently, Kim et al. presented an e cient decision tree learning approach to perform IH and the reconstructed gray images have the good quality under large testing and training images. This thesis presents a new IH algorithm using texture- and decision tree- (TDT) based learning approach. Our proposed TDT-based IH (TDTIH) algorithm first constructs an approximate decision tree which is modified from the previous decision tree approach. Then we partition textures of gray subimages, which are attached to each leaf of the decision tree, into some clusters. Next, using vector quantization technique, a dynamic local codebook, where each codeword stores the reconstructed gray value, is built up for each leaf. In the reconstructing process, a Gaussian lter is rst applied to the input halftone image to obtain a temporary gray image. Then, the subimages of this obtained temporary gray image and the input halftone image are used as two keys to obtain the
reconstructed value based on the TDT-based codebook. Two image sets with different sizes are used in the experiments. Firstly, under the same large training and testing images adopted from Kim et al.'s image set, experimental results demonstrate that our proposed TDTIH algorithm has the highest image quality when compared to the currently published three IH algorithms, such as the DT-based IH (DTIH) algorithm, the lookup table-based IH (LIH) algorithm and the edge-based LIH (ELIH) algorithm. Secondly, based on the training images adopted from Mese website, experimental results show the reconstructed images by using our proposed TDTIH algorithm have better visual quality when compared to the DTIH algorithm, the LIH algorithm and the ELIH algorithm.

[1] N. Ahamed, T. Natarjan, K. R. Rao, "Discrete cosine transform," IEEE Trans.
Comput., vol. 23, pp. 90-93, 1974.
[2] J. P. Allebach, "Reconstruction of continuous-tone from halftone by projections onto convex sets," in Proc. Int. Conf. Advances Commun. Control Systems, Baton Rouge, LA, Oct. 19-21, 1988, pp. 469-478.
[3] M. Analoui and J. P. Allebach, "New results on reconstruction of continuous-tone from halftone," in Proc. Int. Conf. Acoustics, Speech, Signal Processing, San Fraan-cisco, CA, Mar. 23-26, 1992, pp. 313-316.
[4] J. Canny, "A computational approach to edge detection," in IEEE Trans. Pattern Anal. and Machine Intelligence, pp. 679-698, Nov. 1986.
[5] P. C. Chang, C. S. Yu, and T. H. Lee, "Hybrid LMS-MMS inverse halftoning technique," IEEE Trans. Image Processing, vol. 10, pp. 95-103, Jan. 2001.
[6] K. L. Chung and S. T. Wu, "Inverse halftoning algorithm using edge-based lookup table approach," IEEE Trans. Image Processing, vol. 14, pp. 1583-1589, Oct. 2005.
[7] N. Damera-Venkata, T. D. Kite, and B. L. Evans, "Fast blind inverse halftoning," in Proc. IEEE Int. Conf. Image Processing, vol. 2, Oct. 1998, pp. 64-68.
[8] W. H. Equitz, "A new vector quantization clustering algorithm," IEEE Trans. Acous-tics, Speech, and Signal Processing, vol. 37, pp. 1568-1575, Oct. 1989.
[9] Z. Fan, "Retrieval of gray image from digital halftones," in Proc. Int. Symp. Circuits Systems, May 1992, pp. 2477-2480.
[10] S. Hein and A. Zakhor, "Halftone to continuous-tone conversion of error-diffusion coded images," IEEE Trans. Image Processing, vol. 4, pp. 208-216, Feb. 1995.
[11] T. D. Kite, N. Damera-Venkata, B. L. Evans and A. C. Bovik, "A fast, high-quality inverse halftoning algorithm for error diffused halftones," in Proc. IEEE Trans. Image Processing, vol. 9, pp. 1583-1592, Sept. 2000.
[12] H. Y. Kim and R. de Queiroz, "Inverse halftoning by decision tree learning," in Proc. IEEE Int. Conf. Image Processing, vol. 2, Sept. 2003, pp. 913-916.
[13] Z. C. Lai and J. Y. Yen, "Inverse error-diffusion using classified vector quantization," IEEE Trans. Image Processing, vol. 7, pp. 1753-1758, Dec. 1998.
[14] Z. C. Lai and J. Y. Yen, "Inverse halftoning of color image using classified vector quantization," Journal of Visual Commun. and Image Representation, vol. 9, pp. 223-233. Sep. 1998.
[15] J. Luo, R. L. de Queiroz and Z. Fan "Universal descreening technique via wavelet analysis," Proc. IS&T/SPIE Symp. on Electronic Imaging: Science and Technology, Color Imaging, San Jose, CA, SPIE, vol. 3018, pp. 18-29, Feb. 1997.
[16] J. Luo, R. L. de Queiroz and Z. Fan "A robust technique for image descreening based on the wavelet transform," IEEE Trans. Signal Processing, vol. 46, pp. 1179-1185, Apr. 1998.
[17] Y. Linde, A. Buzo, R. M. Gray, "An algorithm for vector quantizer design," IEEE Trans. Commun., vol. 28, pp. 1645-1651, Jan. 1980.
[18] M. Me se and P. P. Vaidyanathan, "Look up table (LUT) method for inverse halfton-ing," IEEE Trans. Image Processing, vol. 10, pp. 1566-1578, Oct. 2001.
[19] M. Me se and P. P. Vaidyanathan, "Tree-structured method for LUT inverse halfton-ing and for image halftoning," IEEE Trans. Image Processing, vol. 11, pp. 644-655, Sept. 2002.
[20] S. Mitra and T. Acharya, Data Mining. John Wiley & Sons Press, NY, 2003.
[21] T. M. Mitchell, Machine Learning, WCB/McGraw-Hill, NY, 1997.
[22] K. R. Rao and P. Yip, "Discrete Cosine Transform-Algorithms, Advantages, Applications, Academic Press." NY. 1990.
[23] J. R. Quinlan, "Induction of decision trees," Machine Learning, vol. 1, pp. 81-106, 1986.
[24] M. Y. Shen and C.-C. J. Kuo, "A robust nonlinear ltering approach to inverse halftoning," J. Visual Commun. and Image Representation, vol. 12, pp. 84-95, Mar. 2001.
[25] R. L. Stevenson, "Inverse halftoning via MAP estimation," IEEE Trans. Image Processing, vol. 6, pp. 574-583, Apr. 1997.
[26] R. A. Ulichney, Digial Halftoning. MIT Press, MA 1987.
[27] P.W. Wong, "Inverse halftoning and kernel estimation for error di usion," IEEE Trans. Image Processing, vol. 4, pp. 486-498, Apr. 1995.
[28] Z. Xiong, M. T. Orchard, and K. Ramchandran, "Inverse halftoning using wavelets," IEEE Trans. Image Processing, vol. 8, pp. 1479-1482, Oct. 1999.