Усовершенствованный метод вычисления связанного списка кортежей смежности уровней яркости для решения задачи текстурной сегментации изображений

Размещено на http: //www. allbest. ru/

Южный федеральный университет, Ростов-на-Дону

Усовершенствованный метод вычисления связанного списка кортежей смежности уровней яркости для решения задачи текстурной сегментации изображений

Е.П. Волков

Аннотация

Объектом исследования является задача текстурной сегментации изображений. Предметом исследования является улучшение одной из составляющих частей алгоритма текстурной сегментации, а именно ускорение процесса расчёта связанного списка кортежей смежности уровней яркости. В статье представлены новый метод вычисления списка кортежей, и проведено сравнение времени выполнения программ реализующих вычисление списка кортежей смежности уровней яркости стандартным и предложенным способами.

Ключевые слова: Обработка изображений, текстура, текстурная сегментация, матрица смежности, связанный список смежности, связанный список кортежей смежности уровней яркости, оптимизация.

Введение

В настоящее время интеллектуальные алгоритмы классификации, сегментации или группирования получили большое распространение и решают разнообразный круг задач [1-5]. Одним из направлений их успешного внедрения является решение задач обработки изображений [6-8]. Типовой задачей интеллектуальной обработки изображений при помощи методов классификации является текстурный анализ. Одним из классических подходов в нём является вычисление статистических текстурных характеристик на основе матрицы смежности уровней яркости (далее GLCM) [9]. Размер данной матрицы зависит от уровней квантования изображения при предобработке. Однако при непосредственном использовании данного метода производится большое количество лишних вычислений и выделений памяти. Одним из усовершенствований данного подхода является вычисление не матрицы смежности уровней яркости, а связанного списка кортежей смежности уровней яркости (далее GLCLL) [6, 10]. В данной статье предлагается усовершенствование для процесса вычисления связанного списка кортежей смежности уровней яркости.

1. GLCLL

GLCLL содержит в себе кортежи пар квантованных уровней яркости соседних пикселей изображения. Соседи пикселя находятся по различным направлениям и удалённостям. Количество уровней яркости изображения обычно снижают от 256 уровней квантования для ускорения подсчётов и уменьшения объёма расходуемой памяти. Поскольку соседними пикселями можно считать пиксели по различным угловым направлениям и с различной дистанцией, то информация по данным вариантам вычисления статистики либо складывается (усредняется), формируя единый GLCLL, либо участвует в формировании нескольких различных GLCLL. GLCLL имеет смысл сортировать или индексировать при анализе больших областей [11].

Область применения предложенного метода

Существуют различные подходы к осуществлению сегментации изображений на основе текстурных признаков на базе GLCM/GLCLL. Краткий обзор основных подходов приведён в [12]. Одной из предпосылок данной статьи является продолжение исследований, описанных в [12], в части ускорений вычислений GLCM/GLCLL для метода выращивания текстурных сегментов.

Отличительными вычислительными особенностями метода выращивания текстурных сегментов являются многократные вычисления GLCM/GLCLL и текстурных свойств на их основе перекрывающихся областей малого размера. При классической схеме вычисления GLCM или GLCLL одни и те же соседние пикселы будут многократно анализироваться. Преодолению этого недостатка посвящена данная работа.

Описание метода

Суть предлагаемого метода заключается в предварительном однократном составлении матрицы размером с анализируемое изображение, каждый элемент которой является структурой, содержащей в себе GLCLL для соответствующего пиксела входного изображения.

В простом случае анализа соседей на расстоянии одного пиксела по четырём направлениям (0, р/4, р/2, 3р/4) для каждого элемента изображения будет сформирован связанный список из четырёх элементов. Во время вычисления GLCLL для региона интересов списки всех интересующих пикселов связываются в единый и используются для дальнейшего вычисления текстурных характеристик.

Результаты экспериментов

Для сравнения времени вычисления GLCLL стандартным способом и предложенным была написана программа на языке c++, которая для различных размеров региона интересов, различным количеством повторений, генерировала границы региона интереса изображения (далее ROI) для изображений из базы данных и вычисляла списки GLCL двумя способами. Анализ производился по четырём направлениям на расстоянии одного пиксела. Из замеряемого времени были программно исключены времена выделения и высвобождения памяти. Время вычислений измерялось при помощи стандартной «C Time Library» (заголовочный файл <time.h>) с точностью до секунд. Для проведения экспериментов использовался ПК с Windows 7.1 x64, CPU AMD Fx™-8350 Eight-Core Processor 4.00GHz, RAM 8 GB Dual-Channel (2*4GB DDR3-1600). Приложение не использовало многопоточность и средства распараллеливания выполнения кода, и было написано при помощи MSVS2012 с флагом компиляции «Optimization: Maximize Speed (/O2)».

Результаты измерений времён выполнения циклов проиллюстрированы на Рис. 1 и 2. На Рис. 1 и 2 показаны сравнения времён выполнения кода при количестве повторений 106 и 107 соответственно.

По горизонтальной оси на обоих рисунках указан размер ROI. По вертикальной - суммарное время выполнения в секундах всех повторений.

На легендах рисунков обозначения “old 10e+6” и “old 10e+7” относятся к классическому варианту подсчёта GLCLL при количестве повторений 106 и 107 соответственно, а обозначения “new 10e+6” и “new 10e+7” - к предложенному методу.

Рис. 1 Времена работы двух алгоритмов для различных размеров ROI при количестве итераций 106

Рис. 2 Времена работы двух алгоритмов для различных размеров ROI при количестве итераций 107.

Выводы

Предложенный метод ускоренного вычисления GLCLL увеличивает скорость подсчёта от 3 до 5 раз для размера ROI от 50х50 до 125х125 пикселов при многократном подсчёте связанных списков смежности градаций серого. Подобные условия наблюдаются в методе выращивания текстурных сегментов [12], а следовательно разработанное улучшение применим для указанного метода и должно оказать положительный эффект на производительность алгоритма. Результаты данного исследования будут использованы для развития алгоритма текстурной сегментации изображений, предложенном в [12].

Исследование выполнено при финансовой поддержке гранта Российского фонда фундаментальных исследований (проект № 16-07-00336) в Южном федеральном университете.

Литература

1. Крашенинников А.М., Гданский Н.И., Рысин М.Л. Построение сложных классификаторов для объектов в многомерных пространствах // Инженерный вестник Дона, 2013, №2 URL: ivdon.ru/magazine/archive/n2y2013/1611/.

2. Воронин В.В., Адигамов К.А., Петренко С.С., Сизякин Р.А. Критерии и способы оценки качества смешивания сыпучих материалов // Инженерный вестник Дона, 2012, №4 URL: ivdon.ru/magazine/archive/n4p2y2012/1400/.

3. Родзин С.И. Гибридные интеллектуальные системы на основе алгоритмов эволюционного программирования // Новости искусственного интеллекта. 2000. №3. С. 159.

4. Курейчик В. М. Курейчик В. В. Гладков Л. А. Родзин С. И.. Основы теории эволюционных вычислений: научная монография. - Ростов-на-Дону: Изд-во ЮФУ, 2010, 222 c.

5. Курейчик В.М., Родзин С.И. Эволюционные вычисления: генетическое и эволюционное программирование // Новости искусственного интеллекта. 2003. № 5. С. 13.

6. Mohammed E. Shokr. Evaluation of second-order texture parameters for sea ice classification from radar images / Journal of geophysical research, Vol. 96, No. C6, pp. 10,625-10,640, June 15, 1991.

7. David Anthony Clausi. Texture segmentation of SAR sea ice imagery / Thesis requirement for the degree of Doctor of Philosophy in Systems Design Engineering to the University of Waterloo. Ontario, Canada, 1996, 175 p.

8. Д.В. Явна. Компьютерное моделирование зрительных механизмов группирования, избирательных к пространственным модуляциям контраста материалов // Инженерный вестник Дона, 2009, №4 URL: ivdon.ru/ru/magazine/archive/n4y2013/2009.

9. Robert M. Haralick, K. Shanmugam, and Its'hak Dinstein, "Textural Features for Image Classification", IEEE Transactions on Systems, Man, and Cybernetics, 1973, SMC-3 (6): pp. 610-621.

10. Clausi, D.A., and Jernigan, M.E. A fast method to determine cooccurrence texture features. IEEE Transactions on Geoscience and Remote Sensing, Vol. 36, No. 1, pp. 298-300, 1998.

11. David A. Clausi, Yongping Zhao. Rapid extraction of image texture byco-occurrence using a hybrid data structure / Computers & Geosciences 28, 2002, pp.763-774

12. Е.П. Волков. «Реализация многоагентного подхода при построении текстурного сегментатора изображений». Журнал "Информатика, вычислительная техника и инженерное образование" №3(18), 2014, URL: digital-mag.tti.sfedu.ru/lib/17/4-3(17)2014.pdf.

References

1. Krasheninnikov A.M., Gdanskij N.I., Rysin M.L. Inћenernyj vestnik Dona (Rus), 2013, №2 URL: ivdon.ru/magazine/archive/n2y2013/1611/.

2. Voronin V.V., Adigamov K.A., Petrenko S.S., Sizjakin R.A. Inћenernyj vestnik Dona (Rus), 2012, №4 URL: ivdon.ru/magazine/archive/n4p2y2012/1400/.

3. Rodzin S.I. Novosti iskusstvennogo intellekta. 2000. №3. P. 159.

4. Kurejchik V. M. Kurejchik V. V. Gladkov L. A. Rodzin S. I.. Osnovy teorii jevoljucionnyh vychislenij: nauchnaja monografija [Fundamentals of evolutionary computation theory: scientific monograph]. Rostov-na-Donu: Izd-vo JuFU, 2010, 222 p.

5. Kurejchik V.M., Rodzin S.I. Novosti iskusstvennogo intellekta. 2003. № 5. p. 13.

6. Mohammed E. Shokr. Journal of geophysical research, Vol. 96, No. C6, pp. 10,625-10,640, June 15, 1991.

7. David Anthony Clausi. Thesis requirement for the degree of Doctor of Philosophy in Systems Design Engineering to the University of Waterloo. Ontario, Canada, 1996, 175 p.

8. D.V. Javna. Inћenernyj vestnik Dona (Rus), 2009, №4 URL: ivdon.ru/ru/magazine/archive/n4y2013/2009.

9. Robert M. Haralick, K. Shanmugam, and Its'hak Dinstein, "Textural Features for Image Classification", IEEE Transactions on Systems, Man, and Cybernetics, 1973, SMC-3 (6): pp. 610-621.

10. Clausi, D.A., and Jernigan, M.E. IEEE Transactions on Geoscience and Remote Sensing, Vol. 36, No. 1, pp. 298-300, 1998.

11. David A. Clausi, Yongping Zhao. Computers & Geosciences 28, 2002, pp.763-774

12. Y.P. Volkov. Zhurnal "Informatika, vychislitel'naja tehnika i inzhenernoe obrazovanie" №3(18), URL: digital-mag.tti.sfedu.ru/lib/17/4-3(17)2014.pdf.

Размещено на Аllbеst.ru