Translate this page:
Please select your language to translate the article


You can just close the window to don't translate
Library
Your profile

Back to contents

Cybernetics and programming
Reference:

On the choice of gray levels in the problem of texture segmentation of images based on the luminance dependence matrices

Tymchuk Andrey Igorevich

graduate student, Kuban State Technological University

350080 181, kv.103, Russia, Krasnodarskii Krai oblast', g. Krasnodar, ul. Sormovskaya, 181, kv. 103

tymchuk.2017@bk.ru
Other publications by this author
 

 

DOI:

10.25136/2644-5522.2018.3.26170

Received:

02-05-2018


Published:

18-05-2018


Abstract: The object of research is the method of textural image segmentation based on the construction and use of luminance dependence matrices. The subject of the study is the influence of the number of reference gray levels used for computations on the speed and quality of image segmentation. Particular attention is paid to the process of constructing brightness dependency matrices, as well as texture attributes, which are calculated on their basis. In the article the author conclude that the choice of the size of the brightness dependence matrix (the number of gray levels) is certainly an important aspect in solving the image segmentation problem, since it directly affects the segmentation quality and program speed. The research methodology is based on the analysis of the method of textural image segmentation based on luminance dependence matrices, testing the segmentation algorithm based on this approach for various input parameters and analysis of results. The main conclusion of the study is the conclusion about the selection of the best number of gray levels in solving the segmentation problem in terms of productivity and segmentation quality. This conclusion is made on the basis of analysis of the results of the program, which implements the algorithm of image segmentation. The analysis was carried out with respect to the time spent on constructing the matrices and calculating the texture attributes, and also with respect to the value of each texture feature separately. The novelty of the study is to determine the number of reference levels relative to the speed and quality of segmentation.


Keywords:

image processing, texture, segment, texture segmentation, texture analysis, textural feature, texture characteristic, Gray Level Co-occurrence Matrix, gray level, pixel


Введение

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

Как было отмечено в [4], на сегодняшний день существует несколько подходов к описанию текстуры. Один из самых первых методов основан на построении и использовании матриц яркостной зависимости, и был предложен Робертом М. Хараликом в 1973 году [1]. Сам подход и его различные вариации до сих пор широко используются в задачах анализа изображений. Суть метода заключается в описании текстуры посредством вычисления текстурных признаков, которые также были описаны в [1]. Изначально в работе [1] было представлено 14 признаков, однако, в дальнейшем были выведены и некоторые другие, как, например, в работе [3]. В зависимости от решаемой задачи набор используемых признаков может меняться и может возникать необходимость в определении новых.

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

Для тестирования алгоритма сегментации разработан алгоритм и написана программа на языке программирования C++. В качестве текстурных признаков были выбраны четыре стандартные характеристики: энергия, контраст, энтропия и обратный момент. В качестве входных изображений использовались аэрофотоснимки. На основании результатов тестирования проведён анализ производительности и эффективности сегментации при разном количестве используемых градаций серого.

Матрицы яркостной зависимости

Один из способов описания текстуры основывается на использовании пространственного распределения и пространственной взаимозависимости значений яркости между соседними пикселями изображения. Как указывается в [4], данный способ обладает высокой точностью определения областей на изображении, однако, имеет высокую сложность вычислений.

Обозначим с помощью I матрицу со значениями яркости (уровень серого) пикселей изображения размера N×M, где N×M – размер изображения. С помощью K обозначим количество различных уровней серого в матрице I. В таком случае матрица яркостной зависимости, которую обозначим P, будет иметь размер K×K, а каждый элемент матрицы будет вычисляться по формуле [1]:

В данной формуле:

- – значение яркости пикселя изображения, расположенного в точке с координатами ;

- N и M – размеры изображения в пикселях;

- – параметры сдвига, задающие взаимное расположение пикселей на изображении;

- – уровни серого соседних пикселей.

Таким образом, элемент будет содержать число случаев взаимного расположения пикселей изображения с уровнями серого i и j. Важно отметить, что расположение соседнего пикселя вычисляется по двум параметрам: расстоянию между пикселями d и угловому направлению φ. В формуле (1) параметры d и φ отражены в виде сдвига относительно текущего пикселя с координатами . Для каждой пары значений строится своя матрица яркостной зависимости. Как правило, для сегментации изображения хватает расстояния d=1 (в пикселях). Другие значения используются при необходимости более детального анализа, что, в свою очередь, ведёт к увеличению количества матриц яркостной зависимости и возрастанию вычислительной сложности. Угловых направлений всего может быть восемь – от 0 до 315 градусов. Однако используют только первые четыре из них: . Оставшиеся четыре направления опускают, так как они будут учтены при проходе нижележащих значений матрицы I. На рисунке 1 представлен пример вычисления матрицы яркостной зависимости для изображения размером 10×10 пикселей при пяти уровнях серого и сдвиге . При этом диапазон яркости был ограничен 256 значениями, а K=5. На рисунке 2 изображены направления, относительно которых выполняется построение матриц яркостной зависимости.

Рисунок 1 – Шаги построения матрицы яркостной зависимости для пяти уровней серого на примере изображения размера 10×10 пикселей при сдвиге

Рисунок 2 – Четыре направления смежности, используемых для построения матриц яркостной зависимости

Как правило, полученную матрицу яркостной зависимости P приводят к нормализованной матрице , каждый элемент которой вычисляется согласно формуле [7]:

В данной формуле:

- – элемент матрицы P, содержащий количество случаев соседнего расположения пикселей с уровнями серого i и j;

- S – сумма всех элементов матрицы P.

После преобразования матрицы P в матрицу с помощью формулы (2) все элементы матрицы будут иметь значения в интервале от нуля до единицы. При этом элемент будет отражать вероятность соседнего расположения пикселей с уровнями серого i и j на изображении [7].

Текстурные признаки

Очевидно, что матрица яркостной зависимости будет содержать уникальную для каждой текстуры информацию. Таким образом, на основании данной матрицы можно вычислить ряд характеристик (признаков), которые позволят описать текстуру. В работе [1] говорится о 28 характеристиках, и приводятся формулы для вычисления 14 из них.

Текстурные признаки отражают различные аспекты текстуры, однако, большинство признаков взаимосвязаны между собой [5]. По результатам работы [5] было выбрано несколько независимых признаков: контраст, обратный момент, сумма квадратов, корреляция и энтропия. При этом два из них (контраст и обратный момент) были признаны наиболее эффективными для использования в задаче классификации изображений [5].

В данной работе исследование выполнялось относительно наиболее используемых текстурных признаков, к которым относят: энергию, контраст, энтропию и обратный момент. Далее приведено описание и назначение используемых признаков:

1) Энергия (признак также известен как равномерность, равномерность энергии и второй угловой момент) – представляет собой сумму квадратов элементов матрицы яркостной зависимости. Значение энергии располагается в интервале. Данный текстурный признак отражает однородность распределения уровней серого на изображении и грубость текстуры. Однородная текстура будет содержать лишь несколько уровней серого. Соответственно, в матрице P будет несколько ненулевых элементов, имеющих большие значения, что даст высокое значение энергии. Признак рассчитывается по формуле [6]:

2) Контраст (признак также известен как дисперсия и инерция) –представляет собой меру расхождения в интенсивности между соседними пикселями текстуры. Значение признака располагается в интервале . Контраст отражает резкость текстуры и глубину борозд на ней. Более глубокие борозды на текстуре будут связаны с высокой контрастностью и большей резкостью; напротив, низкая контрастность связана с менее глубокими бороздами и размытостью текстуры. Соответственно, высокое количество пар пикселей с высокой разницей в оттенках серого будет давать высокое значение контраста. Признак рассчитывается по формуле [6]:

3) Энтропия – отражает неравномерность (хаотичность) и сложность текстуры изображения. Неоднородные текстуры будут иметь низкое значение признака энтропии, в то время как однородные текстуры – высокое. Признак рассчитывается по формуле [6]:

4) Обратный момент (признак также известен как однородность) – представляет собой меру близости распределения элементов матрицы яркостной зависимости к диагонали этой же матрицы. Значение признака располагается в интервале . Обратный момент отражает однородность текстуры и учитывает её локальные изменения. Высокое значение признака означает отсутствие локальных изменений текстур и говорит об однородном распределении уровней серого. Соответственно, высокое значение обратного момента характерно для однородных текстур. Признак рассчитывается по формуле [11]:

Результаты

Для выбора количества уровней серого при построении матриц яркостной зависимости была написана программа на языке программирования C++, реализующая алгоритм сегментирования входного изображения на основе текстурных признаков. В качестве признаков были выбраны четыре стандартные характеристики, подробно описанные ранее: энергия, контраст, энтропия и обратный момент. Размер скользящего окна при анализе результатов не учитывался и имел постоянное значение, равное пяти пикселям. Количество уровней серого (размер матрицы яркостной зависимости) рассматривалось относительно времени, затрачиваемого на построение матриц и вычисление признаков, а также относительно значения каждого текстурного признака в отдельности.

Анализ производительности выполнялся при сегментировании изображения, имеющего размер 1200×798 в пикселях. Все вычисления проводились на основе процессора Intel Core i3. Рассматривались различные размеры матрицы яркостной зависимости - от 4 до 128 уровней серого. Результаты оценки времени вычислений (в секундах) приведены в таблице 1.

Тип оценки

K = 4

K = 8

K = 16

K = 32

K = 64

K = 128

0.000003

0.000009

0.000038

0.000119

0.000425

0.001802

0.109

0.336

1.354

4.323

16.99

64.41

0.007

0.010

0.021

0.061

0.227

0.869

0.008

0.012

0.035

0.114

0.440

1.713

0.025

0.059

0.082

0.110

0.247

0.877

0.008

0.016

0.046

0.156

0.609

2.399

Т

0.138

0.337

1.357

4.441

17.12

67.11

Таблица 1 – Время вычислений в секундах для различных типов оценок относительно размера матрицы яркостной зависимости

В данной таблице:

- – среднее время построения матрицы яркостной зависимости для одного прохода окна;

- – общее время построения всех матриц яркостной зависимости для входного изображения;

- – общее время, которое было затрачено на вычисление текстурного признака «энергия» на основе формулы (3) для всех построенных матриц яркостной зависимости;

- – общее время, которое было затрачено на вычисление текстурного признака «контраст» на основе формулы (4) для всех построенных матриц яркостной зависимости;

- – общее время, которое было затрачено на вычисление текстурного признака «энтропия» на основе формулы (5) для всех построенных матриц яркостной зависимости;

- – общее время, которое было затрачено на вычисление текстурного признака «обратный момент» на основе формулы (6) для всех построенных матриц яркостной зависимости;

- Т – общее время, которое было затрачено на все вычисления.

На основании данных таблицы 1 подтверждается факт о том, что увеличение количества используемых уровней серого ведёт к значительному увеличению времени, которое потребуется для построения матриц яркостной зависимости и вычисления текстурных признаков. Стоит отметить, что время вычисления признаков «энергии» и «энтропии» не так сильно зависит от размера матрицы, как признаки «контраста» и «обратного момента». Относительно временной оценки наилучшее количество уровней серого находится в интервале от 4 до 32.

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

С точки зрения визуальной оценки качества сегментирования наилучший размер матрицы яркостной зависимости равен 32. Пример входного изображения представлен на рисунке 3, а примеры его сегментации на основе значений текстурных признаков (каждый сегмент раскрашивается в зависимости от значения признака) для 32 уровней серого – на рисунке 4.

Признак

K = 4

K = 8

K = 16

K = 32

K = 64

K = 128

Энергия

0.28027

0.06841

0.01535

0.00341

0.00067

0.00016

Контраст

0.318

1.167

4.997

22.34

117.1

694.5

Энтропия

2.152

4.245

6.394

8.561

10.85

12.87

Обратный момент

0.845

0.652

0.430

0.245

0.119

0.051

Таблица 2 – Значения текстурных признаков относительно размера матрицы яркостной зависимости

Рисунок 3 – Пример входного изображения для тестирования сегментации

Рисунок 4 – Примеры сегментации изображения на основе значений текстурных признаков (контраст, энергия, энтропия и обратный момент)

Заключение

Выбор размера матрицы яркостной зависимости (количество уровней серого), безусловно, является важным аспектом при решении задачи сегментирования изображения, так как он напрямую влияет на качество сегментации и скорость работы программы. В рамках данной статьи было установлено, что с точки зрения производительности и визуальной эффективности сегментации наилучшим решением будет использование 32 уровней серого. При этом стоит отметить, что при оценке не учитывалось численное значение качества классификации сегментов и влияние размера скользящего окна на скорость и результаты сегментации. Данные факторы планируется учесть в будущих работах.

References
1. Haralick R. M., Shanmugan K., Dinstein I. Textural Features for Image Classification // IEEE Trans. Systems, Man and Cybernetics. 1973, vol. 3, no. 6, pp. 610-621.
2. Haralick R. M. Statistical and Structural Approaches to Texture //Proceedings of the IEEE. 1979, vol. 67, no. 5, pp. 786-804.
3. Sebastian V. B., Unnikrishnan A., Balakrishnan K. Grey Level Co-occurrence Matrices: Generalisation and Some New Features // International Journal of Computer Science, Engineering and Information Technology. 2012, vol. 2, no. 2, pp. 151-157.
4. Tymchuk, A. I. Analiz aktual'nykh metodov segmentatsii tekstur na aerofotosnimkakh // Avtomatizirovannye informatsionnye i elektroenergeticheskie sistemy: Materialy V Mezhdunarodnoi nauchno-prakticheskoi konferentsii (7–8 dekabrya 2017 goda).
5. Ulaby F. T., Kouyate F., Brisco B. Textural Information in SAR Images // IEEE Trans. Geoscience and Remote Sensing. 1986, vol. GE-24, no. 2, pp. 235-245.
6. Zhao Q., Shi CZ., Luo LP., Role of the texture features of images in the diagnosis of solitary pulmonary nodules in different sizes // Chinese Journal of Cancer Research. 2014, vol. 26, no. 4, pp. 451-458.
7. Kovaleva, I. L. Teksturnye priznaki izobrazhenii // Minsk: Izd-vo BNTU, 2010. – 24 c.
8. Albregtsen F. Statistical Texture Measures Computed from Gray Level Coocurrence Matrices // Image Processing Laboratory, Department of Informatics, University of Oslo. 2008, 14 p.
9. Gray-Level Co-occurrence Matrices (GLCMs): [Elektronnyi resurs]. – Rezhim dostupa: http://www.code.ucsd.edu/pcosman/glcm.pdf. – (Data obrashcheniya: 18.03.2018).
10. Properties of gray-level co-occurrence matrix: [Elektronnyi resurs]. – Rezhim dostupa: https://www.mathworks.com/help/images/ref/graycoprops.html. – (Data obrashcheniya: 21.03.2018).
11. Calculating texture measures from the GLCM: [Elektronnyi resurs]. – Rezhim dostupa: http://www.ucalgary.ca/mhallbey/measures. – (Data obrashcheniya: 19.03.2018).