УДК 004.932

ДУАЛЬНАЯ ОПТИМИЗАЦИЯ ТОНОВОЙ АППРОКСИМАЦИИ МОНОХРОМНЫХ ИЗОБРАЖЕНИЙ ПАРАЛЛЕЛЬНЫМ ЭВОЛЮЦИОННО-ГЕНЕТИЧЕСКИМ ПОИСКОМ

Р.А. Нейдорф, А.Г. Агаджанян

Аннотация


В статье рассматривается оптимизация процедуры тоновой аппроксимации полутоновых (например, в палитре серого цвета) изображений. Процедура тоновой аппроксимации подразумевает сокращение в палитре аппроксимированного изображения количества используемых тонов по сравнению с количеством тонов в палитре исходного изображения. Оптимизация этой процедуры заключается в минимизации потери качества передачи графической информации, которая оценивается суммарным или усредненным по изображению отклонением тонов координатно-идентичных пикселей аппроксимированного изображения от тонов исходного. В качестве инструмента оптимизации предлагается гибридный алгоритм, который совмещает эвристический и детерминированный алгоритмы поиска наилучшей по критерию минимизации ошибки аппроксимации структуры аппроксимирующей палитры. Эвристический алгоритм реализован на основе эволюционно-генетической парадигмы. Его задачей является поиск области тоновых структур аппроксимирующей палитры, максимально близких к оптимальной. Цель детерминированного алгоритма направленного перебора — найти ближайший к полученному предыдущим поиском результату экстремум критерия качества аппроксимации. Эвристический алгоритм, как более быстродействующий, нацелен на оперативное сокращение области поиска, а детерминированный, как более затратный, — на нахождение хотя бы локального экстремума (а, возможно, и глобального) по максимально сокращенному предыдущим алгоритмом пути. Совместная работа этих алгоритмов позволяет обеспечить процессу тоновой аппроксимации эффект оптимизации, названный в статье дуальной. Под этим термином подразумевается получение результата, при котором достигается экстремум критерия качества аппроксимации при минимизации времени его достижения. Описываемое в статье исследование посвящено повышению результативности гибридного алгоритма на эвристическом этапе, в качестве которого используется модифицированный эволюционно-генетический алгоритм. Рассматриваются перспективы разработки и оценки эффективности внедрения модели параллельного использования алгоритмов с различными параметрами настройки. Обсуждаются первичные эксперименты, а их результаты сравниваются с известным алгоритмом решения поставленной задачи.

Ключевые слова


тоновая аппроксимация; гибридизация; параллельная модель; оптимизация; адаптивная схема; эволюционно-генетический алгоритм; аппроксимирующая палитра

Полный текст:

PDF

Литература


  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.


Рудольф Анатольевич Нейдорф - д-р техн. наук, профессор, профессор кафедры программного обеспечения вычислительной техники и автоматизированных систем, Донской Государственный Технический Университет.
Область научных интересов: математическое моделирование, методы оптимизации и преобразования информации, эвристические методы исследований.
Число научных публикаций: 379.

Адрес (E-mail): rudolf.neydorf.44@mail.ru
Почтовый адрес: пл. Гагарина 1, Ростов-на-Дону, 344000
Телефон: +79034722292


Альберт Грантович Агаджанян - аспирант кафедры программного обеспечения вычислительной техники и автоматизированных систем, Донской Государственный Технический Университет.
Область научных интересов: эвристические алгоритмы, эволюционные методы оптимизации, обработка цифровых данных.
Число научных публикаций: 15.

Адрес (E-mail): foralbert92@gmail.com
Почтовый адрес: пл. Гагарина 1, Ростов-на-Дону, 344000
Телефон: +79515050716




DOI: http://dx.doi.org/10.15622/sp.60.6

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.