Дуальная оптимизация тоновой аппроксимации монохромных изображений параллельным эволюционно-генетическим поиском
Ключевые слова:
тоновая аппроксимация, гибридизация, параллельная модель, оптимизация, адаптивная схема, эволюционно-генетический алгоритм, аппроксимирующая палитраАннотация
В статье рассматривается оптимизация процедуры тоновой аппроксимации полутоновых (например, в палитре серого цвета) изображений. Процедура тоновой аппроксимации подразумевает сокращение в палитре аппроксимированного изображения количества используемых тонов по сравнению с количеством тонов в палитре исходного изображения. Оптимизация этой процедуры заключается в минимизации потери качества передачи графической информации, которая оценивается суммарным или усредненным по изображению отклонением тонов координатно-идентичных пикселей аппроксимированного изображения от тонов исходного. В качестве инструмента оптимизации предлагается гибридный алгоритм, который совмещает эвристический и детерминированный алгоритмы поиска наилучшей по критерию минимизации ошибки аппроксимации структуры аппроксимирующей палитры. Эвристический алгоритм реализован на основе эволюционно-генетической парадигмы. Его задачей является поиск области тоновых структур аппроксимирующей палитры, максимально близких к оптимальной. Цель детерминированного алгоритма направленного перебора — найти ближайший к полученному предыдущим поиском результату экстремум критерия качества аппроксимации. Эвристический алгоритм, как более быстродействующий, нацелен на оперативное сокращение области поиска, а детерминированный, как более затратный, — на нахождение хотя бы локального экстремума (а, возможно, и глобального) по максимально сокращенному предыдущим алгоритмом пути. Совместная работа этих алгоритмов позволяет обеспечить процессу тоновой аппроксимации эффект оптимизации, названный в статье дуальной. Под этим термином подразумевается получение результата, при котором достигается экстремум критерия качества аппроксимации при минимизации времени его достижения. Описываемое в статье исследование посвящено повышению результативности гибридного алгоритма на эвристическом этапе, в качестве которого используется модифицированный эволюционно-генетический алгоритм. Рассматриваются перспективы разработки и оценки эффективности внедрения модели параллельного использования алгоритмов с различными параметрами настройки. Обсуждаются первичные эксперименты, а их результаты сравниваются с известным алгоритмом решения поставленной задачи.Литература
1. Brun L., Tremeau A. Digital Color Imaging Handbook // The Electrical Engineering and Applied Signal Processing Series. NYC: CRC Press. 2003. 764 p.
2. Shapiro L., Stockman G. Computer Vision // Prentice Hall PTR. 2001. 609 p.
3. Emre C. Improving the Performance of K-Means for Color Quantization. // Image and Vision Computing. vol. 29. 2011. pp. 260-271.
4. Burger W., Burge M. Color Quantization // Digital Image Processing. Texts in Comuter Science. London: Springer. 2016. pp. 329-339.
5. Yue X.D., Miao D.Q., Cao L.B., Wu Q., Y.F. Chen An efficient color quantization based on generic roughness measure // Pattern Recognition: vol. 47. 2014. pp. 1777-1789.
6. Kanan C., Cottrell G. Color-to-Grayscale: Does the Method Matter in Image Recognition? // PLoS One. vol. 7. 2012. URL: https://doi.org/10.1371/journal.pone.0029740 (дата обращения: 02.07.2018).
7. Визильтер Ю.В., Вишняков Б.В., Выголов О.В., Горбацевич В.С., Князь В.А. Технологии ителлектуальной обработки информации для задач навигации и управления беспилотными летательными аппаратами // Труды СПИИРАН. 2016. Вып. 45. С. 26-44.
8. Padmavathi K., Thangadurai K. Implementation of RGB and Grayscale Images in Plant Leaves Disease Detection – Comparative Study // Indian Journal of Science and Technology. vol 9. 2016. pp. 1-6.
9. Hu Y.-C., Chen W.-L., LO C.-C., Chuang J.-C. Improved vector quantization scheme for grayscale image compression // Opto-Electronics Review. vol. 20. 2012. pp. 187-193.
10. Ramirez E., Jimenez O., Perez A., Pogrebnyak O. Grayscale Image Segmentation Based on Associative Memories // Computations in Systems. vol. 15. 2011. pp. 149-162.
11. Харинов М.В. Обобщение трех подходов к оптимальной сегментации цифрового изображения // Труды СПИИРАН. 2013. Вып. 25. С. 294-316.
12. Kharinov M. Reclassification formula that provides to surpass K-means method // Computer Vision and Pattern Recognition. 2012. URL: https://arxiv.org/ftp/arxiv/papers/1209/1209.6204.pdf (дата обращения: 02.07.2018).
13. Деревянкина А.А. Автоматизация исследования изображений методом s-аппроксимации // Математические методы в технике и технологиях (ММТТ) - сб. тр. ХХIII Междунар. науч. конф.: в 12 т. Т. 6. Секции 6,7/ под общ. ред. В.С. Балакирева.- Саратов: СГТУ. 2010. – С. 37-43.
14. Patel T., Srivastava R., Hierarchical visual cryptography for grayscale image // Online International Conference on Green Engineering and Technologies (IC-GET). 2016. pp. 1-4.
15. Zhang S., Wu Y., Bao Y., Bai J. Watermarking Algorithm for Bas-Relief Based on Depth Grayscale Image // International Conference on Computing Intelligence and Information System (CIIS). 2017. pp. 294-297.
16. Paul Heckbert Color image quantization for frame buffer display // SIGGRAPH ’82 Proceedings of the 9th annual conference on Computer graphics and interactive techniques. Boston, Massachusetts, USA: ACM. 1982. pp. 297-307.
17. Neydorf R.A., Aghajanyan A.G., Vucinic D. Monochrome Multitone Image Approximation on Lowered Dimension Palette with Sub-optimization Method based on Genetic Algorithm // Springer, Improved Performance of Materials. Springer International Publishing: 2018. pp. 144-154.
18. Neydorf R.A., Aghajanyan A.G., Vucinic D. Monochrome multitone image approximation with low-dimensional palette // IEEE East-West Design & Test Symposium (EWDTS). 2016.
19. Нейдорф Р.А., Агаджанян А.Г. Исследование аспектов возможного применения субоптимальной тоновой аппроксимации изображений в задачах технического зрения средств автономной навигации // Известия ЮФУ, Технические науки. Таганрог: Изд-во ТТИ ЮФУ. №1-2 (186-187). 2017. С. 133-145.
20. Нейдорф Р.А., Агаджанян А.Г., Нейдорф А.Р. Оптимизация результатов аппроксимации растровых изображений и оценка их экстремальности // Математические Методы в Технике и Технологиях. Саратов: СГТУ и. Ю.А. Гагарина. Том 1. 2017. с. 19-26.
21. Neydorf R.A., Aghajanyan A.G., Vucinic D. A high-speed hybrid algorithm of monochrome multitone images approximation // IEEE East-West Design & Test Symposium (EWDTS). 2017.
22. Neydorf R.A., Aghajanyan A.G., Vucinic D. Improved Bi-optimal Hybrid Approximation Algorithm for Monochrome Multitone Image Processing // ADVCOMP 2017, The Eleventh International Conference on Advanced Engineering Computing and Applications in Sciences. IARIA. 2017. pp. 20-25.
23. Sean Luke Essentials of Metaheuristics // Lulu. 2013. URL: https://cs.gmu.edu/~sean/book/metaheuristics/Essentials.pdf (дата обращения: 17.03.2018).
24. Mitchell M. An Introduction to Genetic Algorithms // London: Fifth printing, 1999.
25. Eiselt H.A., Sandblom C-L. Heuristic Algorithms // In: Integer Programming and Network Models. Springer, Berlin, Heidelberg: 2000. pp. 229-258.
26. Cook S.A. An overciew of computational complexity // Communication of the ACM. 1983. vol. 26. no. 6. pp. 401-408.
27. Deb K., Pratap A. A fast and elitist multiobjective genetic algorithm: NSGA-II // IEEE Transactions on Evolutionary Computation. 2002. vol. 6. pp. 182-197.
28. Deb. K., Himanshu J., An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems With Box Constraints // IEEE Transactions on Evolutionary Computation. 2014. vol. 18. pp. 577-601
29. Sun J.Q., Schütze O. A hybrid evolutionary algorithm and cell mapping method for multi-objective optimization problems // 2017 IEEE Symposium Series on Computational Intelligence (SSCI). 2017. pp. 1-9.
30. Fogel D.B. An introduction to simulated evolutionary optimization // IEEE Transactions on Neural Networks. 1994. vol. 5. pp. 3-14.
31. Roeva O. Genetic Algorithm and Firefly Algorithm Hybrid Schemes for Cultivation Processes Modelling // Transactions on Computational Collective Intelligence XVII. Springer, Berlin, Heidelberg: 2014. vol. 8790. pp. 196-211.
32. Neumüller C., Wagner S. Parameter Meta-optimization of Metaheuristic Optimization Algorithms // International Conference on Computer Aided Systems Theory. Springer, Berlin, Heidelberg: 2012. vol. 6927. pp. 367-374.
33. Chekanin V.A., Chekanin A.V. Design of Library of Metaheuristic Algorithms for Solving the Problems of Discrete Optimization // Advances in Mechanical Engineering. Springer, Cham: 2018. pp. 25-32.
34. Podorozhniak A., Lubchenko N., Balenko O., Zhuikov D. Neural network approach for multispectral image processing // Advanced Trends in Radioelecrtronics, Telecommunications and Computer Engineering (TCSET). Ukraine, Lviv-Slavyansk: 2018. pp. 978-981.
35. Grishkin V., Lakushkin O., Stepanenko N. Biofouling detection based on image processing technique // 2017 Computer Science and Information Technologies (CSIT). 2017. pp. 158-161.
36. Gillette A., Wilson C., George A. Efficient and autonomous processing and classification of images on small spacecraft // 2017 IEEE National Aerospace and Electronics Conference (NAECON). 2017. pp. 135-141.
37. Nikam P.A. Sawant S.D. Circuit board defect detection using image processing and microcontroller // 2017 International Conference on Intelligent Computing and Control Systems (ICICCS). 2017. pp. 1096-1098.
38. Schütze O. Hernandez V. The hypervolume based directed search method for multi-objective optimization problems // Journal of Heuristics. Springer US: 2016. vol. 22. pp. 273-300.
39. L.J. Eshelman The CHC adaptive search algorithm: how to safe search when engaging in non traditional genetic recombination, In Foundations of Genetic Algorithms. 1991. pp. 265-283.
40. Агаджанян А.Г. Анализ влияния вероятностных параметров настройки эволюционно-генетического алгоритма на результативность оптимизационной аппроксимации изображений // Техника и технологии: курс на инновации: сборник материалов международной научно-практической конференции. Иркутск: «Научное партнерство Апекс». 2017. C. 49-57.
2. Shapiro L., Stockman G. Computer Vision // Prentice Hall PTR. 2001. 609 p.
3. Emre C. Improving the Performance of K-Means for Color Quantization. // Image and Vision Computing. vol. 29. 2011. pp. 260-271.
4. Burger W., Burge M. Color Quantization // Digital Image Processing. Texts in Comuter Science. London: Springer. 2016. pp. 329-339.
5. Yue X.D., Miao D.Q., Cao L.B., Wu Q., Y.F. Chen An efficient color quantization based on generic roughness measure // Pattern Recognition: vol. 47. 2014. pp. 1777-1789.
6. Kanan C., Cottrell G. Color-to-Grayscale: Does the Method Matter in Image Recognition? // PLoS One. vol. 7. 2012. URL: https://doi.org/10.1371/journal.pone.0029740 (дата обращения: 02.07.2018).
7. Визильтер Ю.В., Вишняков Б.В., Выголов О.В., Горбацевич В.С., Князь В.А. Технологии ителлектуальной обработки информации для задач навигации и управления беспилотными летательными аппаратами // Труды СПИИРАН. 2016. Вып. 45. С. 26-44.
8. Padmavathi K., Thangadurai K. Implementation of RGB and Grayscale Images in Plant Leaves Disease Detection – Comparative Study // Indian Journal of Science and Technology. vol 9. 2016. pp. 1-6.
9. Hu Y.-C., Chen W.-L., LO C.-C., Chuang J.-C. Improved vector quantization scheme for grayscale image compression // Opto-Electronics Review. vol. 20. 2012. pp. 187-193.
10. Ramirez E., Jimenez O., Perez A., Pogrebnyak O. Grayscale Image Segmentation Based on Associative Memories // Computations in Systems. vol. 15. 2011. pp. 149-162.
11. Харинов М.В. Обобщение трех подходов к оптимальной сегментации цифрового изображения // Труды СПИИРАН. 2013. Вып. 25. С. 294-316.
12. Kharinov M. Reclassification formula that provides to surpass K-means method // Computer Vision and Pattern Recognition. 2012. URL: https://arxiv.org/ftp/arxiv/papers/1209/1209.6204.pdf (дата обращения: 02.07.2018).
13. Деревянкина А.А. Автоматизация исследования изображений методом s-аппроксимации // Математические методы в технике и технологиях (ММТТ) - сб. тр. ХХIII Междунар. науч. конф.: в 12 т. Т. 6. Секции 6,7/ под общ. ред. В.С. Балакирева.- Саратов: СГТУ. 2010. – С. 37-43.
14. Patel T., Srivastava R., Hierarchical visual cryptography for grayscale image // Online International Conference on Green Engineering and Technologies (IC-GET). 2016. pp. 1-4.
15. Zhang S., Wu Y., Bao Y., Bai J. Watermarking Algorithm for Bas-Relief Based on Depth Grayscale Image // International Conference on Computing Intelligence and Information System (CIIS). 2017. pp. 294-297.
16. Paul Heckbert Color image quantization for frame buffer display // SIGGRAPH ’82 Proceedings of the 9th annual conference on Computer graphics and interactive techniques. Boston, Massachusetts, USA: ACM. 1982. pp. 297-307.
17. Neydorf R.A., Aghajanyan A.G., Vucinic D. Monochrome Multitone Image Approximation on Lowered Dimension Palette with Sub-optimization Method based on Genetic Algorithm // Springer, Improved Performance of Materials. Springer International Publishing: 2018. pp. 144-154.
18. Neydorf R.A., Aghajanyan A.G., Vucinic D. Monochrome multitone image approximation with low-dimensional palette // IEEE East-West Design & Test Symposium (EWDTS). 2016.
19. Нейдорф Р.А., Агаджанян А.Г. Исследование аспектов возможного применения субоптимальной тоновой аппроксимации изображений в задачах технического зрения средств автономной навигации // Известия ЮФУ, Технические науки. Таганрог: Изд-во ТТИ ЮФУ. №1-2 (186-187). 2017. С. 133-145.
20. Нейдорф Р.А., Агаджанян А.Г., Нейдорф А.Р. Оптимизация результатов аппроксимации растровых изображений и оценка их экстремальности // Математические Методы в Технике и Технологиях. Саратов: СГТУ и. Ю.А. Гагарина. Том 1. 2017. с. 19-26.
21. Neydorf R.A., Aghajanyan A.G., Vucinic D. A high-speed hybrid algorithm of monochrome multitone images approximation // IEEE East-West Design & Test Symposium (EWDTS). 2017.
22. Neydorf R.A., Aghajanyan A.G., Vucinic D. Improved Bi-optimal Hybrid Approximation Algorithm for Monochrome Multitone Image Processing // ADVCOMP 2017, The Eleventh International Conference on Advanced Engineering Computing and Applications in Sciences. IARIA. 2017. pp. 20-25.
23. Sean Luke Essentials of Metaheuristics // Lulu. 2013. URL: https://cs.gmu.edu/~sean/book/metaheuristics/Essentials.pdf (дата обращения: 17.03.2018).
24. Mitchell M. An Introduction to Genetic Algorithms // London: Fifth printing, 1999.
25. Eiselt H.A., Sandblom C-L. Heuristic Algorithms // In: Integer Programming and Network Models. Springer, Berlin, Heidelberg: 2000. pp. 229-258.
26. Cook S.A. An overciew of computational complexity // Communication of the ACM. 1983. vol. 26. no. 6. pp. 401-408.
27. Deb K., Pratap A. A fast and elitist multiobjective genetic algorithm: NSGA-II // IEEE Transactions on Evolutionary Computation. 2002. vol. 6. pp. 182-197.
28. Deb. K., Himanshu J., An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems With Box Constraints // IEEE Transactions on Evolutionary Computation. 2014. vol. 18. pp. 577-601
29. Sun J.Q., Schütze O. A hybrid evolutionary algorithm and cell mapping method for multi-objective optimization problems // 2017 IEEE Symposium Series on Computational Intelligence (SSCI). 2017. pp. 1-9.
30. Fogel D.B. An introduction to simulated evolutionary optimization // IEEE Transactions on Neural Networks. 1994. vol. 5. pp. 3-14.
31. Roeva O. Genetic Algorithm and Firefly Algorithm Hybrid Schemes for Cultivation Processes Modelling // Transactions on Computational Collective Intelligence XVII. Springer, Berlin, Heidelberg: 2014. vol. 8790. pp. 196-211.
32. Neumüller C., Wagner S. Parameter Meta-optimization of Metaheuristic Optimization Algorithms // International Conference on Computer Aided Systems Theory. Springer, Berlin, Heidelberg: 2012. vol. 6927. pp. 367-374.
33. Chekanin V.A., Chekanin A.V. Design of Library of Metaheuristic Algorithms for Solving the Problems of Discrete Optimization // Advances in Mechanical Engineering. Springer, Cham: 2018. pp. 25-32.
34. Podorozhniak A., Lubchenko N., Balenko O., Zhuikov D. Neural network approach for multispectral image processing // Advanced Trends in Radioelecrtronics, Telecommunications and Computer Engineering (TCSET). Ukraine, Lviv-Slavyansk: 2018. pp. 978-981.
35. Grishkin V., Lakushkin O., Stepanenko N. Biofouling detection based on image processing technique // 2017 Computer Science and Information Technologies (CSIT). 2017. pp. 158-161.
36. Gillette A., Wilson C., George A. Efficient and autonomous processing and classification of images on small spacecraft // 2017 IEEE National Aerospace and Electronics Conference (NAECON). 2017. pp. 135-141.
37. Nikam P.A. Sawant S.D. Circuit board defect detection using image processing and microcontroller // 2017 International Conference on Intelligent Computing and Control Systems (ICICCS). 2017. pp. 1096-1098.
38. Schütze O. Hernandez V. The hypervolume based directed search method for multi-objective optimization problems // Journal of Heuristics. Springer US: 2016. vol. 22. pp. 273-300.
39. L.J. Eshelman The CHC adaptive search algorithm: how to safe search when engaging in non traditional genetic recombination, In Foundations of Genetic Algorithms. 1991. pp. 265-283.
40. Агаджанян А.Г. Анализ влияния вероятностных параметров настройки эволюционно-генетического алгоритма на результативность оптимизационной аппроксимации изображений // Техника и технологии: курс на инновации: сборник материалов международной научно-практической конференции. Иркутск: «Научное партнерство Апекс». 2017. C. 49-57.
Опубликован
2018-10-01
Как цитировать
Нейдорф, Р. А., & Агаджанян, А. Г. (2018). Дуальная оптимизация тоновой аппроксимации монохромных изображений параллельным эволюционно-генетическим поиском. Труды СПИИРАН, 5(60), 156-188. https://doi.org/10.15622/sp.60.6
Раздел
Искусственный интеллект, инженерия данных и знаний
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями:
Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале.
Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале.
Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).
