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

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

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» (заголовочный файл) с точностью до секунд. Для проведения экспериментов использовался ПК с Windows 7.1×64, 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.