ارائه روشی برای ارزیابی کمی الگوریتم‌های کاهش رنگ تصویر با ارائه نمونه‌ای کاربردی
محورهای موضوعی : مهندسی برق و کامپیوتر
منصور فاتح
1
,
احسان‌اله کبیر
2
1 - دانشگاه صنعتی شاهرود
2 - دانشگاه تربیت مدرس
کلید واژه: کاهش رنگ, ارزیابی کمی ارزیابی کیفی C- میانگین نقشه فرش,
چکیده مقاله :
در الگوریتم‌های کاهش رنگ، نتیجه کار به صورت دیداری یا بر اساس معیارهای کیفی بررسی می‌شوند. ارزیابی بدون در نظر گرفتن معیارهای کمی، ارزیابی جامع و دقیقی نیست و سلیقه بیننده در ارزیابی بسیار تأثیرگذار است. در برخی از مقالات، نتیجه کار با معیار MSE ارزیابی می‌شود. در این معیار تفاوت میان رنگ پیکسل‌های تصویر نتیجه با تصویر اولیه به عنوان خطا در نظر گرفته می‌شود که روش مناسبی برای ارزیابی روش‌های کاهش رنگ نیست. در کاهش رنگ تصاویر، اگر یک رنگ به طور کامل با رنگی نزدیک به رنگ اصلی جایگزین شود، خطا محسوب نمی‌شود. اگر این جایگزینی‌ها برای تمام پیکسل‌های آن رنگ رخ ندهد خطایی در کاهش رنگ اتفاق افتاده است. یکی‌نبودن رنگ‌های حاصل از اعمال الگوریتم کاهش رنگ با رنگ‌های مطلوب باید در ارائه معیار ارزیابی لحاظ شود که در معیار MSE لحاظ نمی‌شود. در برخی از کاربردهای کاهش رنگ مانند کاهش رنگ در نقشه‌های فرش، رنگ مطلوب پیکسل نهایی مشخص است و ارائه رنگ نادرست خطا محسوب می‌شود. از این رو در این گونه از کاربردها، امکان ارزیابی کمی بر اساس رنگ نهایی هر پیکسل وجود دارد. با ارائه معیاری برای ارزیابی کمی، سلیقه بیننده در ارزیابی لحاظ نمی‌شود و امکان مقایسه دقیق الگوریتم‌های کاهش رنگ فراهم می‌شود. در این مقاله به ارائه معیاری کمی برای ارزیابی الگوریتم‌های کاهش رنگ پرداخته شده و در صورت مشخص‌بودن رنگ مطلوب پیکسل‌های نهایی، این معیار کارا است. برای نشان‌دادن کارایی معیار ارزیابی کمی، یکی از کاربردهای کاهش رنگ یعنی کاهش رنگ در نقشه‌های فرش بررسی شده است. چندین روش کاهش رنگ با معیار ارزیابی پیشنهادی سنجیده شده‌اند و الگوریتم [42] به دلیل تناسب با کاربرد، کمترین خطای کمی را داشته است.
In color reduction algorithms the result will be evaluated based on visual or qualitative standards. Evaluation without considering the quantitative standard wouldn't be a complete and accurate evaluation and trends of viewer are very effective on the evaluation. In some articles, the result will be evaluated with MSE. In this standard error the difference between the final images’ pixels color with first image will be considered as a failure in which is not a suitable technique for evaluating of color reduction methods. In images color reduction, if a color completely be replaced by a color closed to the original color it wouldn’t be considered as a failure. If these replacements don’t happen for all of those specific color pixels, then an error has happened in color reduction. The disintegration of the resulted colors from color reduction algorithm with desired colors should be considered in presenting the evaluation criteria since this will not be considered in MSE. In some of color reduction applications such as color reduction in the carpet cartoons, the final desired pixel color is specified and presenting the wrong color will be an error. Therefore, in such applications, the quantitative evaluation based on final color of each pixel is possible. By presenting criteria for quantitative evaluation, viewer trends wouldn't be considered in evaluation and the possibility of accurate comparison of color reduction algorithms would take place. In this article, we have presented a technique of quantitative evaluation for color reduction algorithms. When the final desired color for pixels are specified, this criteria would work out. To demonstrate the functionality of this quantitative evaluation technique, one of the applications of color reduction which is color reduction in carpet cartoons would be discussed. Several methods of color reduction would be evaluated based on proposed evaluation criteria and reference [42], had the lowest error.
[1] L. Brun and A. Tremeau, Digital Color Imaging Handbook, CRC Press, pp. 589-638, 2002.
[2] C. K. Yang and W. H. Tsai, "Color image compression using quantization, thresholding and edge detection techniques all based on the moment-preserving principle," Pattern Recognition Letters, vol. 19, no. 2, pp. 205-215, Feb. 1998.
[3] Y. Deng and B. Manjunath, "Unsupervised segmentation of color-texture regions in images and video," IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 23, no. 8, pp. 800-810, Aug. 2001.
[4] N. Sherkat, T. Allen, and S. Wong, "Use of colour for hand-filled form analysis and recognition," Pattern Analysis and Applications, vol. 8, no. 1, pp. 163-180, Oct. 2005.
[5] O. Sertel, J. Kong, U. V. Catalyurek, G. Lozanski, J. H. Saltz, and M. N. Gurcan, "Histopathological image analysis using model-based intermediate representations and color texture: follicular lymphoma grading," J. of Signal Processing Systems, vol. 55, no. 1-3, pp. 169-183, Apr. 2009.
[6] C. T. Kuo and S. C. Cheng, "Fusion of color edge detection and color quantization for color image watermarking using principal axes analysis," Pattern Recognition, vol. 40, no. 12, pp. 3691-3704, Dec. 2007.
[7] Y. Deng, B. Manjunath, C. Kenney, M. Moore, and H. Shin, "An efficient color representation for image retrieval," IEEE Trans. on Image Processing, vol. 10, no. 1, pp. 140-147, Jan. 2001.
[8] M. E. Celebi, "Improving the performance of K-means for color quantization," Image and Vision Computing, vol. 29, no. 4, pp. 260-271, Mar. 2011.
[9] A. Mojsilovic and E. Soljanin, "Color quantization and processing by fibonacci lattices," IEEE Trans. on Image Processing, vol. 10, no. 11, pp. 1712-1725, Nov. 2001.
[10] N. Papamarkos, A. E. Atsalakis, and C. P. Strouthopoulos, "Adaptive color reduction," IEEE Trans. on Systems, vol. 32, no. 1, pp. 44-56, Feb. 2002.
[11] P. Heckbert, "Color image quantization for frame buffer display," ACM SIGGRAPH Computer Graphics, vol. 16, no. 3, pp. 297-307, Jul. 1982.
[12] M. Gervautz and W. Purgathofer, "A simple method for color quantization: octree quantization," New Trends in Computer Graphics, vol. 1, pp. 219-231, Jun. 1988.
[13] S. Wan, P. Prusinkiewicz, and S. Wong, "Variance-based color image quantization for frame buffer display," Color Research and Application, vol. 15, no. 1, pp. 52-58, Feb. 1990.
[14] G. Joy and Z. Xiang, "Center-cut for color image quantization," the Visual Computer, vol. 10, no. 1, pp. 62-66, Jan. 1993.
[15] M. Orchard and C. Bouman, "Color quantization of images," IEEE Trans. on Signal Processing, vol. 39, no. 12, pp. 2677-2690, Dec. 1991.
[16] C. Y. Yang and J. C. Lin, "RWM-Cut for color image quantization," Computers and Graphics, vol. 20, no. 4, pp. 577-588, Jul. 1996.
[17] I. S. Hsieh and K. C. Fan, "An adaptive clustering algorithm for color quantization," Pattern Recognition Letters, vol. 21, no. 4, pp. 337-346, Apr. 2000.
[18] S. Cheng and C. Yang, "Fast and novel technique for color quantization using reduction of color space dimen-sionality," Pattern Recognition Letters, vol. 22, no. 8, pp. 845-856, Jun. 2001.
[19] K. Lo, Y. Chan, and M. Yu, "Colour quantization by three-dimensional frequency diffusion," Pattern Recognition Letters, vol. 24, no. 14, pp. 2325-2334, Oct. 2003.
[20] Y. Sirisathitkul, S. Auwatanamongkol, and B. Uyyanonvara, "Color image quantization using distances between adjacent colors along the color axis with highest color variance," Pattern Recognition Letters, vol. 25, no. 9, pp. 1025-1043, Jul. 2004.
[21] K. Kanjanawanishkul and B. Uyyanonvara, "Novel fast color reduction algorithm for time-constrained applications," J. of Visual Communication and Image Representation, vol. 16, no. 3, pp. 311-332, Jun. 2005.
[22] W. H. Equitz, "A new vector quantization clustering algorithm," IEEE Trans. on Acoustics, Speech, and Signal Processing, vol. 37, no. 10, pp. 1568-1575, Oct. 1989.
[23] R. Balasubramanian and J. Allebach, "A new approach to palette selection for color images," J. of Imaging Technology, vol. 17, no. 6, pp. 284-290, Jun. 1991.
[24] Z. Xiang and G. Joy, "Color image quantization by agglomerative clustering," IEEE Computer Graphics and Applications, vol. 14, no. 3, pp. 44-48, May 1994.
[25] L. Velho, J. Gomez, and M. Sobreiro, "Color image quantization by pairwise clustering," in Proc. of the 10th Brazilian Symposium on Computer Graphics and Image Processing, pp. 203-210, Oct. 1997.
[26] L. Brun and M. Mokhtari, "Two high speed color quantization algorithms," in Proc. of the 1st Int. Conf. on Color in Graphics and Image Processing, pp. 116-121, Oct. 2000.
[27] ا. ايزدی‌پور و ا. کبير، "ارائه روشی برای خواندن خودکار نقشه چاپی فرش و مقایسه آن با روش خوشه‌یابی C- میانگین،" نشریه مهندسی برق و مهندسی کامپیوتر ایران، جلد 8، شماره 1، صص. 56-48، بهار 1389.
[28] Y. L. Huang and R. F. Chang, "A fast finite-state algorithm for generating RGB palettes of color quantized images," J. of Information Science and Engineering, vol. 20, no. 4, pp. 771-782, Jul. 2004.
[29] Y. C. Hu and M. G. Lee, "K-means based color palette design scheme with the use of stable flags," J. of Electronic Imaging, vol. 16, no. 3, pp. 033003-033013, Jul. 2007.
[30] Y. C. Hu and B. H. Su, "Accelerated K-means clustering algorithm for colour image quantization," Imaging Science J., vol. 56, no. 1, pp. 29-40, Feb. 2008.
[31] Z. Xiang, "Color image quantization by minimizing the maximum intercluster distance," ACM Trans. on Graphics, vol. 16, no. 3, pp. 260-276, Jul. 1997.
[32] M. E. Celebi, "An effective color quantization method based on the competitive learning paradigm," in Proc. of the 2009 Int. Conf. on Image Processing, Computer Vision, and Pattern Recognition, vol. 2, pp. 876-880, Jul. 2009.
[33] M. E. Celebi and G. Schaefer, "Neural gas clustering for color reduction," in Proc. of the 2010 Int. Conf. on Image Processing, Computer Vision, and Pattern Recognition, pp. 429-432, Aug. 2010.
[34] D. Ozdemir and L. Akarun, "Fuzzy algorithm for color quantization of images," Pattern Recognition, vol. 35, no. 8, pp. 1785-1791, Aug. 2002.
[35] G. Schaefer and H. Zhou, "Fuzzy clustering for colour reduction in images," Telecommunication Systems, vol. 40, no. 1, pp. 17-25, Feb. 2009.
[36] Z. Bing, S. Junyi, and P. Qinke, "An adjustable algorithm for color quantization," Pattern Recognition Letters, vol. 25, no. 16, pp. 1787-1797, Dec. 2004.
[37] A. Dekker, "Kohonen neural networks for optimal colour quantization," Network: Computation in Neural Systems, vol. 5, no. 3, pp. 351-367, Jan. 1994.
[38] C. H. Chang, P. Xu, R. Xiao, and T. Srikanthan, "New adaptive color quantization method based on self-organizing maps," IEEE Trans. on Neural Networks, vol. 16, no. 1, pp. 237-249, Jan. 2005.
[39] X. D. Yue, D. Miao, L. Cao, Q. Wu, and Y. Chen, "An efficient color quantization based on generic roughness measure," Pattern Recognition, vol. 47, no. 4, pp. 1777-1789, Apr. 2014.
[40] A. Atsalakis and N. Papamarkos, "Color reduction and estimation of the number of dominant colors by using a self-growing and self-organized neural gas," Engineering Applications of Artificial Intelligence, vol. 19, no. 7, pp. 769-786, Oct. 2006.
[41] A. T. Ghanbarian, E. Kabir, and N. M. Charkari, "Color reduction based on ant colony," Pattern Recognition Letters, vol. 28, no. 12, pp. 1383-1390, Sept. 2007.
[42] م. فاتح و ا. ا. کبير، "کاهش رنگ نقشه‌هاي دستي فرش پيش از نقطه‌گذاري،" نشریه مهندسی برق و مهندسی کامپیوتر ایران، سال 12، شماره 1، صص. 41-33، بهار 1393.
[43] بوريا، www.booria.com/carpetdesigner.htm.
[44] مرکز کنترل کامپيوتر ايران، نرم‌افزار نقش‌ساز، www.centraltouch.com.
[45] م. فاتح، ا. کبير و م. نیلی احمدآبادی، "کاهش رنگ در نقشه چاپی فرش به کمک یادگیری تقویت‌شده،" نشریه مهندسی برق و مهندسی کامپیوتر ایران، سال 9، شماره 3، صص. 142-133، پاييز 1390.
[46] ا. ايزدی‌پور و ا. کبير، "شناسايی خودکار خطوط نقشه فرش،" اولين کنگره مشترک سيستم‌های فازی و هوشمند، جلد اول، صص. 618-613، مشهد مقدس، شهريور 1386.
[47] م. فاتح و ا. کبير، "خواندن خودکار نقشه‌های دستی فرش،" نشریه سيستم‌های هوشمند در مهندسی برق، جلد 3، شماره 2، صص. 30-15، تابستان 1391.
[48] موزه فرش ایران، 9/1/1396، http://carpetmuseum.ir/home.htm.
[49] Binary Splitting Color Quantization software, Accessed on 2017/3/30, https://engineering.purdue.edu/~bouman/software/color_quantization
[50] Color quantizer 0.6.5.0, Accessed on 2017/3/30, http://www.softpedia.com/progDownload/Color-quantizer-Download-206091.html
[51] Color Quantization Software, Accessed on 2017/3/30, http://www.colorpilot.com/layer.htm
