Оцінка ефективності нового статистичного ієрархічного агломеративного алгоритму кластеризації для розпізнавання регіонів зображень
The new hierarchical aglomerative algorithm for cluster (region) recognition of images is considered. The analysis of the processing speed of the suggested algorithm and most widespread k-means algorithm is proposed. The evaluations of image clusterization quality are introduced.
Saved in:
| Date: | 2019 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2019
|
| Online Access: | https://journal.iasa.kpi.ua/article/view/171322 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | System research and information technologies |
| Download file: |  |
Institution
System research and information technologies| _version_ | 1867334365254516736 |
|---|---|
| author | Bashkov, E. A. Vovk, O. L. |
| author_facet | Bashkov, E. A. Vovk, O. L. |
| author_institution_txt_mv | [
{
"author": "E. A. Bashkov",
"institution": null
},
{
"author": "O. L. Vovk",
"institution": null
}
] |
| author_sort | Bashkov, E. A. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2019-06-24T12:52:05Z |
| description | The new hierarchical aglomerative algorithm for cluster (region) recognition of images is considered. The analysis of the processing speed of the suggested algorithm and most widespread k-means algorithm is proposed. The evaluations of image clusterization quality are introduced. |
| first_indexed | 2025-07-17T10:25:13Z |
| format | Article |
| fulltext |
© Е.А. Башков, О.Л. Вовк, 2005
Системні дослідження та інформаційні технології, 2005, № 2 117
TIДC
НОВІ МЕТОДИ В СИСТЕМНОМУ АНАЛІЗІ,
ІНФОРМАТИЦІ ТА ТЕОРІЇ ПРИЙНЯТТЯ РІШЕНЬ
УДК 681.3
ОЦЕНКА ЭФФЕКТИВНОСТИ НОВОГО СТАТИСТИЧЕСКОГО
ИЕРАРХИЧЕСКОГО АГЛОМЕРАТИВНОГО АЛГОРИТМА
КЛАСТЕРИЗАЦИИ ДЛЯ РАСПОЗНАВАНИЯ РЕГИОНОВ
ИЗОБРАЖЕНИЙ
Е. А. БАШКОВ, О. Л. ВОВК
Рассматривается новый иерархический агломеративный алгоритм выделения
кластеров (регионов) изображений. Приводится анализ быстродействия пред-
лагаемого алгоритма в сравнении с наиболее распространенным алгоритмом k-
means кластеризации. Вводятся оценки качества кластеризации изображений.
ВВЕДЕНИЕ
На современном уровне развития технических средств повышается интерес
к нетрадиционным сферам внедрения компьютерных технологий. К их чис-
лу относятся и сферы использования методов распознавания объектов изо-
бражений. Задачи выделения таких объектов (задачи кластеризации) наибо-
лее часто решаются при контекстном поиске в электронных базах данных и
при содержательной классификации изображений (медицинская диагности-
ка, удаленное наблюдение, анализ документов) [1, 2].
Цель данной статьи – оценить эффективность нового статистического
алгоритма кластеризации путем введения различных оценок затрат процес-
сорного времени и качества кластеризации.
В соответствии с поставленной целью в предлагаемой работе решаются
следующие основные задачи:
• рассматривается общая постановка задачи кластеризации;
• предлагается новый алгоритм кластеризации, являющийся модифи-
кацией статистического иерархического агломеративного алгоритма распо-
знавания однородных областей;
• вводится теоретическая оценка нового алгоритма по критерию за-
трат процессорного времени (рассматривается роль сегментации при кла-
стеризации изображений);
• проводится экспериментальный анализ качества кластеризации
авторского алгоритма по критериям быстродействия и качества.
Е.А. Башков, О.Л. Вовк
ISSN 1681–6048 System Research & Information Technologies, 2005, № 2 118
1. ПОСТАНОВКА ЗАДАЧИ КЛАСТЕРИЗАЦИИ
Кластеризация [3] — общее название множества вычислительных процедур,
используемых при создании классификации объектов, в результате которых
образуются «кластеры» (регионы) — группы похожих по различным харак-
теристикам объектов. Кластерный метод [3] — многомерная статистическая
процедура, выполняющая сбор данных, содержащих информацию о харак-
теристиках объектов, и затем упорядочивающая объекты в сравнительно
однородные группы.
Исходные данные для процедуры кластеризации [4]: набор объектов,
каждый из которых задается вектором своих характеристик. Существует два
основных формата представления входных данных процедуры кластериза-
ции [2, 5] — матрица шаблонов и матрица близости.
В ходе процедуры кластеризации происходит объединение «подобных»
объектов в отдельные классы. Результат кластеризации — набор классов,
содержащих однородные объекты [3, 4].
В задаче выделения объектов изображения задан набор пикселей, каж-
дый из которых определяется тремя цветовыми компонентами в одном из
цветовых пространств. С помощью процедуры кластеризации выделяются
группы пикселей, имеющие наиболее близкие цветовые компоненты, т.е.
происходит распознавание изображений (рис. 1).
2. ОСНОВНЫЕ СТАТИСТИЧЕСКИЕ МЕТОДЫ КЛАСТЕРИЗАЦИИ
В соответствии с работами [3, 4] все разработанные кластерные методы ста-
тистики образуют шесть основных групп:
1. Иерархические агломеративные методы. В начале процедуры
кластеризации каждый объект представляет собой отдельный кластер, затем
происходит объединение наиболее «близких» кластеров. Процесс объедине-
ния продолжается до тех пор, пока не будет удовлетворено условие оконча-
ния кластеризации.
2. Иерархические дивизимные методы являются логической проти-
воположностью методов предыдущей группы. При инициализации процесса
кластеризации все объекты принадлежат одному классу, а затем этот все-
объемлющий кластер делится на последовательно уменьшающиеся части.
3. Итеративные методы группировки. Предварительно все данные
разбиваются на некоторое количество кластеров, для которых вычисляются
центры тяжести. Каждый объект помещается в кластер с ближайшим
Исходное
изображение
Изображение,
разбитое на два
кластера
Исходное
изображение
Изображение,
разбитое на три
кластера
Рис. 1. Примеры кластеризации изображений
Оценка эффективности нового статистического иерархического агломеративного алгоритма …
Системні дослідження та інформаційні технології, 2005, № 2 119
центром тяжести. Вычисляются новые центры тяжести. Эта процедура про-
должается до тех пор, пока не перестанут меняться кластеры.
4. Методы поиска модальных значений плотности. Рассматривается
кластер как область пространства с высокой плотностью точек по сравнению
с окружающими областями. В ходе кластеризации происходит поиск скоп-
лений данных, которые и представляют собой области высокой плотности.
5. Факторные методы основываются на формировании корреляцион-
ной матрицы сходств между объектами, по которой определяются факторы,
и объекты распределяются по кластерам в зависимости от их факторных
нагрузок.
6. Методы сгущений. Уникальность их состоит в том, что они позво-
ляют создавать перекрывающиеся кластеры. Основываются на вычислении
матрицы сходства между объектами и определении оптимального значения
статистического критерия, называемого специалистами «функцией сцепле-
ния». Затем объекты перемещаются до тех пор, пока функция не достигнет
оптимального значения.
Рассмотренные группы методов соответствуют разным подходам к соз-
данию кластеров. Применение различных методов к одним и тем же данным
может привести к существенно различным результатам [3]. Поэтому особое
внимание необходимо уделить выбору метода кластеризации для каждой
конкретной задачи разделения объектов на однородные группы.
При решении проблемы кластеризации изображений заданный набор
точек рассматривается как многомерная совокупность признаков объектов,
согласно которым требуется рассортировать эти объекты по классам. С уче-
том исходных данных не все приведенные выше группы методов примени-
мы к корректному решению задачи выделения объектов изображений.
Например, методы поиска модальных значений трудно применимы к
кластеризации изображений, так как они основаны на объединении класте-
ров по некоторому заданному правилу, которое необходимо изменять при
анализе каждого нового изображения.
Факторные методы предполагают, что объекты распределяются по кла-
стерам в зависимости от факторных нагрузок. В случае обработки изобра-
жений в качестве факторов выступают три цветовые компоненты. Согласно
факторному методу по отдельным кластерам объекты распределяются с вы-
сокой нагрузкой по каждой из трех компонент. Однако алгоритмы этой
группы не учитывают ситуацию, когда высокая нагрузка присутствует по не-
скольким компонентам (при анализе изображений — это обычный случай).
Основное достоинство методов сгущения — возможность создания пе-
рекрывающихся кластеров — является основным недостатком при класте-
ризации изображений. При выделении объектов изображений ставится тре-
бование однозначности, а, следовательно, один объект не может быть
членом нескольких кластеров.
Таким образом, для выделения регионов изображений наиболее приме-
нимы иерархические и итеративные методы. Именно эти две группы мето-
дов рассматриваются как основные в работах [2, 5].
Иерархические методы представляют собой процедуры создания по-
следовательности вложенных разбиений, исходя из данных матрицы близо-
сти [2]. Формально любой иерархический метод кластеризации состоит из
следующих шагов [5]:
Е.А. Башков, О.Л. Вовк
ISSN 1681–6048 System Research & Information Technologies, 2005, № 2 120
1. Расчет матрицы близости между всеми парами шаблонов. Изначаль-
но каждый объект — отдельный кластер.
2. Нахождение минимума в матрице близости и объединение кластеров
с минимальным расстоянием. Обновление строк и столбцов матрицы, соот-
ветствующих объединенным кластерам.
3. Если все объекты принадлежат одному кластеру, то конец работы
метода. Иначе на шаг 2.
В результате работы таких методов все объекты классификации будут
принадлежать одному кластеру. Поэтому для получения значимых разбие-
ний необходимо рассматривать различные срезы построенной иерархии [2].
По способу формирования кластеров иерархические методы подразде-
ляются на методы одиночной и методы полной связи [5]. При одиночной
связи в один кластер объединяются объекты с минимальным расстоянием, а
при полной — в разные кластеры разносятся объекты с максимальным рас-
стоянием.
Основная идея итеративных методов (методов разбиения) [5] — нахо-
ждение единственного разделения шаблонов по кластерам вместо иерархии,
полученной согласно иерархическим технологиям. Реализация методов раз-
биения предполагает выполнение таких шагов [2, 5]:
1. Выбор начального распределения объектов по кластерам. Расчет
центров тяжести полученных кластеров.
2. Перегруппировка объектов кластеров (отнесение каждого объекта к
кластеру с минимальным расстоянием до центра).
Однако такая технология имеет существенные ограничения [5]: при
разных стартовых условиях такие методы выдают различные результаты,
нет методики выбора количества кластеров.
Наиболее используемый метод данной группы — метод k-means кла-
стеризации [1, 5–7], который при решении задачи выделения объектов изо-
бражений состоит из следующих основных этапов:
1. Произвольное разбиение на некоторое заданное количество класте-
ров (обычно изначально количество кластеров равно двум).
2. Вычисление центров тяжести полученных кластеров.
3. Анализ каждого объекта каждого кластера. Перераспределение в
кластер с минимальным расстоянием до центра.
4. После перераспределения — пересчет центров тяжести кластеров.
5. Этапы 3, 4 повторяются до тех пор, пока все точки не будут нахо-
диться в «ближайшем» кластере.
6. Если не удовлетворен критерий окончания кластеризации, то увели-
чивается количество кластеров, повторяются шаги 1 – 5.
Необходимо отметить, что в работах [6, 7] показано, что для выделения
наиболее информативных областей изображений при их кластеризации ко-
личество кластеров необходимо ограничивать шестнадцатью.
3. НОВЫЙ СТАТИСТИЧЕСКИЙ АГЛОМЕРАТИВНЫЙ АЛГОРИТМ (НСАА)
ДЛЯ КЛАСТЕРИЗАЦИИ ИЗОБРАЖЕНИЙ
3.1. Описание НСАА
В основе предлагаемого алгоритма — битовая маска связей и рангов цвето-
вых компонентов центров кластеров. Так как любое цветовое пространство
Оценка эффективности нового статистического иерархического агломеративного алгоритма …
Системні дослідження та інформаційні технології, 2005, № 2 121
трехмерно [8], то разработанная маска отражает взаимосвязи и ранги трех
цветовых характеристик. Она содержит 18 бит, причем 9 младших бит ха-
рактеризуют взаимосвязи цветовых составляющих, а старшие 9 —уровни
(ранги) каждого из анализируемых компонентов в отдельности.
При формировании младших бит маски каждая пара компонентов ана-
лизируется на наличие связей типа меньше, больше и равно.
Старшие биты маски описывают уровни каждой из трех характеристик
(вводится три основных уровня — низкий, средний и высокий). Для этого
весь интервал изменения каждой из цветовых составляющих ],[ hl xx делит-
ся на три равных промежутка ],(],,[],,[ hl xGHGHGLGLx , соответствую-
щих приведенным уровням.
В табл. 1 приведены правила формирования младших и старших бит
маски для пространства цветов RGB.
Кроме того, предлагается «размывать» границы как отношений, так и
уровней с помощью введения некоторой погрешности маски ε . Т.е. в от-
ношении между компонентами 1X и 2X присутствует связь, например,
« > », если удовлетворяется условие 21 XX > . Кроме того, предполагается,
что если выполняется условие )( 21 ε+< XX , то между 1X и 2X существу-
ет и связь « = ». Аналогичны рассуждения и для отношения «< ».
Пример анализа рангов цветовых характеристик.
Пусть 11 xX = , тогда:
• если )(1 ε+≤ GLx , то 1X имеет низкий уровень;
• если )(1 ε−≥ GHx , то 1X имеет высокий уровень;
• если )(1 ε−> GLx или )(1 ε+< GLx , то 1X имеет средний уровень.
В табл. 2 приведены примеры масок для конкретных числовых значе-
ний. Предполагается, что значения компонентов GR, , B принадлежат ин-
тервалу ]1,0[ ; 1,0=ε ; 33,0=GL ; 67,0=GH .
Т а б л и ц а 1 . Маска связей и рангов компонентов пространства RGB
Старшие биты Младшие биты
Ком-
по-
нент
Предел
изменения
компонента
Ранг Маска
Ком-
по-
ненты
Связь цвето-
вых
характери-
стик
Маска
]...[ GLxl низкий 0 0 0 0 0 0 0 0 1 R и G GR > 0 0 0 0 0 0 0 0 1
]...( GHGL средний 0 0 0 0 0 0 0 1 0 GR = 0 0 0 0 0 0 0 1 0 B
]...( hxGH высокий 0 0 0 0 0 0 1 0 0 GR < 0 0 0 0 0 0 1 0 0
]...[ GLxl низкий 0 0 0 0 0 1 0 0 0 R и B BR > 0 0 0 0 0 1 0 0 0
]...( GHGL средний 0 0 0 0 1 0 0 0 0 BR = 0 0 0 0 1 0 0 0 0 G
]...( hxGH высокий 0 0 0 1 0 0 0 0 0 BR < 0 0 0 1 0 0 0 0 0
]...[ GLxl низкий 0 0 1 0 0 0 0 0 0 G и B BG > 0 0 1 0 0 0 0 0 0
]...( GHGL средний 0 1 0 0 0 0 0 0 0 BG = 0 1 0 0 0 0 0 0 0 R
]...( hxGH высокий 1 0 0 0 0 0 0 0 0 BG < 1 0 0 0 0 0 0 0 0
Е.А. Башков, О.Л. Вовк
ISSN 1681–6048 System Research & Information Technologies, 2005, № 2 122
Т а б л и ц а 2 . Примеры битовых масок
Числовые значе-
ния центров
кластеров
Маска
Биты R G B
17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
0,5 0,5 0,5 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0
0,7 0,1 0,3 1 1 0 0 0 1 0 1 1 1 0 0 0 0 1 0 0 1
0,2 0,8 1 0 0 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0
0,3 0,35 0,9 0 1 1 0 1 1 1 0 0 1 0 0 1 0 0 1 1 0
0,35 0,6 0,3 0 1 1 1 1 0 0 1 1 0 0 1 0 1 1 1 0 0
Разработанный иерархический алгоритм состоит из трех основных этапов.
1. Полная связь. Предполагается, что изначально каждый пиксель
изображения представляет собой отдельный кластер. Происходит разнесе-
ние точек изображения в кластеры с одинаковыми битовыми масками. Т.е.
для каждого пикселя изображения формируется маска взаимосвязей и ран-
гов, затем пиксели с одинаковыми масками разносятся в разные кластеры.
2. Одиночная связь. Для полученных на предыдущем этапе кластеров
строится матрица близости (расстояний) между кластерами. В качестве рас-
стояния используется среднее евклидово расстояние между всеми парами
точек, входящих в кластеры с рассчитываемыми между ними расстояниями.
В полученной матрице происходит поиск наиболее «близких» кластеров
(т.е. кластеров с минимальным расстоянием). Они объединяются, образуя
новые кластеры, для которых производится перерасчет центров. Причем i -й
и j -й кластеры считаются «близкими» только в том случае, если расстояние
от i -го кластера к j-му минимально в i -й строке матрицы близости, и рас-
стояние от j -го кластера к i -му минимально в j -й строке матрицы близо-
сти. Из матрицы расстояний удаляются строки и столбцы, соответствующие
объединенным кластерам, и добавляется строка и столбец, соответствующие
полученному кластеру. Данный этап повторяется до тех пор, пока количест-
во кластеров не достигнет шестнадцати (данный числовой параметр взят из
работ [6, 7] и проверен экспериментально).
3. Окончание. Данный этап разработан как критерий окончания кла-
стеризации. Он аналогичен предыдущему с некоторым ограничением. Объ-
единение кластеров с минимальным расстоянием матрицы близости произ-
водится только при выполнении условия «близости» масок. В противном
случае процесс кластеризации заканчивается. Обозначим маски кластеров,
претендующих на объединение, 1M и 2M . Тогда основные стадии анализа
выполнения условия “близости” масок сформулируем так:
• расчет результирующей маски объединения 211 & MMM = ;
• установка начального значения количества эквивалентных бит 0=bK ;
• анализ всех соответствующих триад масок rM , 1M и 2M в отдель-
ности:
если ( ) ( ) ( )((( ( &4&1&&4&&&2&2&!&&7& 22121 MMMMMM r
))))1&& 1M ,
то 1+= bb KK ;
Оценка эффективности нового статистического иерархического агломеративного алгоритма …
Системні дослідження та інформаційні технології, 2005, № 2 123
• переход к следующей триаде масок: 3>>= rr MM , 311 >>= MM и
322 >>= MM ;
• возвращение к анализу следующей триады масок;
• анализ полученного числа эквивалентных битов:
если ( 5≥bK ), то условие «близости» масок выполняется, иначе — не
выполняется.
Т.е. при анализе триад масок количество эквивалентных бит инкремен-
тируется, если конъюнкция масок кластеров содержит хотя бы одну едини-
цу ( )7&rM , причем пара триад рассматриваемых масок не должна быть
двух следующих типов ( ) ( )((( ( &4&1&&4&&&2&2&! 22121 MMMMM
))))1&& 1M :
1) (1 1 0) и (0 1 1);
2) (0 1 1) и (1 1 0).
3.2. Визуальные результаты кластеризации
На рис.2 показаны результаты выделения значимых областей изображений с
помощью авторского алгоритма. В качестве тестируемых изображений вы-
браны 24-битовые изображения размером 512х512 пикселей: baboon.tiff —
энтропия 17,74; lena.tiff — энтропия 16,84.
На рис.3 приведены результаты кластеризации тех же изображений с по-
мощью противоположной (итеративной) технологии. Как пример итеративной
Исходное
изображение
Изображение,
разбитое на пять кла-
стеров, процессорное
время 997614 мс
Изображение,
разбитое на три кла-
стера, процессорное
время 825652 мс
Исходное
изображение
Рис. 3. Примеры распознавания изображений с помощью алгоритма k-means
Исходное
изображение
Изображение,
разбитое на четыре
кластера, процессор-
ное время 6890 мс
Изображение,
разбитое на три кла-
стера, процессорное
время 5625 мс
Исходное
изображение
Рис. 2. Примеры распознавания изображений с помощью алгоритма НСАА
Е.А. Башков, О.Л. Вовк
ISSN 1681–6048 System Research & Information Technologies, 2005, № 2 124
группы методов кластеризации выбран алгоритм k-means, модификация ко-
торого для выделения объектов изображений подробно описана в работах [6,7].
3.3. Анализ затрат оперативной памяти
При обработке изображений начальное количество кластеров будет ,whk =
где h — высота изображения; w — ширина изображения в пикселях.
Тогда для хранения матрицы близости с элементами заданного типа
требуемый объем оперативной памяти в байтах можно вычислить по фор-
муле
bkV 2
ОП = , (1)
где b — количество байт, необходимое для хранения одного элемента за-
данного типа.
Самый очевидный способ минимизации этого объема — хранение не
всей матрицы, а нижней (верхней) треугольной ее части без диагонали, что
возможно в силу симметричности матрицы. Необходимое количество байт
оперативной памяти можно представить как
.
22
2
ОП
bkbkV −= (2)
3.4. Анализ скорости кластеризации
Рассмотрим теоретическое обоснование эффективности разработанного ме-
тода по сравнению с алгоритмом k-means кластеризации [6, 7].
Пусть для заданного изображения размером hw× оптимальное коли-
чество кластеров согласно критерию окончания кластеризации — n. Оценим
количество итераций, необходимое каждому из сравниваемых алгоритмов
для достижения этого количества групп однородных элементов.
Рассмотрим применение алгоритма k -means [6, 7] для распознавания
объектов изображений. Задачу вычисления максимального количества ите-
раций, которое будет затрачено на выделение n объектов изображения,
можно свести к комбинаторной задаче размещений. Следовательно, макси-
мальное количество итераций будет
.
)!(
)!(
2
means ∑
=
− −
=
n
i
k ihw
hwI (3)
Используя обозначения, введенные выше, максимальное число итера-
ций для разработанного НСАА можно вычислить по формуле
.НСАА nhwI −= (4)
Необходимо отметить, что в формуле (4) произведена теоретическая
оценка количества итераций предлагаемого алгоритма, полученная из пред-
положения, что на первом этапе иерархического алгоритма (этапе полной
связи) маски всех кластеров были различны, т.е. не было первоначального
разнесения точек в кластеры с одинаковыми масками и, следовательно, ко-
личество кластеров изначально не уменьшалось. Такая стратегия оценки
выбрана для предупреждения спора о природе первого этапа алгоритма.
Оценка эффективности нового статистического иерархического агломеративного алгоритма …
Системні дослідження та інформаційні технології, 2005, № 2 125
Предполагается, что этап полной связи алгоритма может быть отнесен как к
предварительной сегментации (выделению однородных областей — умень-
шению количества первоначальных цветов изображений [6, 7, 9]), так и к
предлагаемому алгоритму распознавания изображений непосредственно.
При разработке алгоритма авторы склонялись ко второму варианту, так как
на этапе полной связи использовали одну из особенностей иерархической
стратегии кластеризации.
Практическое тестирование НСАА, проводимое на ПЭВМ Intel Celeron
2700 на коллекции из 1000 картинок, показало превосходство разработанно-
го алгоритма над наиболее распространенным алгоритмом кластеризации k-
means по критерию затрат процессорного времени (рис. 4, кривая алгоритма
НСАА практически совпадает с осью абсцисс). Так как значения затрат про-
цессорного времени несоизмеримы для сравниваемых алгоритмов (при та-
ких шкалах осей показатели быстродействия НСАА не видны), то рекомен-
дуется анализировать быстродействие НСАА по рис. 5. Анализируемые 24-
битовые картинки были упорядочены по возрастанию энтропии (меры ин-
формативности изображений [8]). Показатели энтропии для тестируемых
изображений приведены на оси абсцисс. Неравномерность нанесения значений
по оси абсцисс связана с неравным количеством изображений различных
показателей энтропии в экспериментальной базе данных (большинство изо-
бражений имеют энтропию в пределах от 14 до 15). Количество пикселей
тестируемых изображений от 98304 (384× 256) до 262144 (512× 512) пиксе-
лей.
Для чистоты эксперимента сравнение затрат процессорного времени
проведено также для алгоритма k-means с изначальным разбиением по тех-
нологии этапа полной связи разработанного иерархического алгоритма НСАА
с помощью битовой маски (результаты тестирования приведены на рис. 5).
0
200000
400000
600000
800000
1000000
11
,5
7
12
,2
8
12
,5
3
12
,8
7
13
,0
6
13
,1
7
13
,3
9
13
,6
7
13
,9
6
14
,0
9
14
,1
8
14
,3
9
14
,5
6
14
,6
1
14
,7
3
14
,9
3
15
,0
2
15
,1
1
15
,3
6
16
,5
7
Энтропия
За
тр
ат
ы
п
ро
це
сс
ор
но
го
вр
ем
ен
и
м
с
Рис. 4. Сравнение показателей затрат процессорного времени НСАА (1) и k-means
(2) алгоритмов
1 2
За
тр
ат
ы
п
ро
це
сс
ор
но
го
вр
ем
ен
и,
м
с
0
1000
2000
3000
4000
5000
6000
7000
11
,5
7
12
,2
8
12
,5
3
12
,8
7
13
,0
6
13
,1
7
13
,3
9
13
,6
7
13
,9
6
14
,0
9
14
,1
8
14
,3
9
14
,5
6
14
,6
1
14
,7
3
14
,9
3
15
,0
2
15
,1
1
15
,3
6
16
,5
7
Энтропия
За
тр
ат
ы
п
ро
це
сс
ор
но
го
вр
ем
ен
и
м
с 1 2
Рис. 5. Сравнение показателей затрат процессорного времени НСАА (1) и усовер-
шенствованного k-means (2) алгоритмов
За
тр
ат
ы
п
ро
це
сс
ор
но
го
вр
ем
ен
и,
м
с
Е.А. Башков, О.Л. Вовк
ISSN 1681–6048 System Research & Information Technologies, 2005, № 2 126
Анализ полученных результатов экспериментов показывает значимость
введенной авторами битовой маски связей и рангов, при использовании ко-
торой алгоритм k-means получает ускорение в несколько сотен раз и превос-
ходит даже разработанный алгоритм (НСАА). Введение битовой маски как
этапа алгоритма k-means визуально практически не изменяет качество
кластеризации. То же можно заметить и для критериев качества, описанных
ниже.
Отметим, что всевозможные «скачки» на рис. 4 и 5 связаны с различ-
ным числом выделяемых кластеров (ведь увеличение количества кластеров
на единицу приводит к увеличению количества итераций в алгоритме k-
means в среднем в два раза) и различными размерами анализируемых изоб-
ражений.
3.5. Роль предварительной сегментации изображений
Под предварительной сегментацией будем понимать дискретизацию (кван-
тование) цветов изображения для уменьшения исходного числа кластеризи-
руемых цветов (кластеров) и, соответственно, ускорения процедуры выде-
ления значимых объектов изображений. Как отмечалось выше,
предварительной сегментацией условно можно считать и первый этап
НСАА.
Реальные изображения наряду с полезной информацией содержат раз-
личные помехи. Источниками помех являются собственные шумы фотопри-
емных устройств, зернистость фотоматериалов, шумы каналов связи [8].
Предварительная сегментация уместна только в том случае, если ее введе-
ние не ухудшает качество кластеризации (т.е. помехи изображений не по-
дчеркиваются, а сглаживаются).
Большинство методов сегментации основано на специфических свойст-
вах различных цветовых пространств (LUV, YUV, LAB, HSL) [2, 10, 11]. Та-
кие методы выделяют наиболее значимые цвета изображений, которые для
низкоэнтропийных изображений и являются результирующими значимыми
кластерами, а для изображений с высокой энтропией предполагают реализа-
цию процедуры кластеризации со значительно уменьшенным исходным на-
бором кластеров. Например, в основе YUV (сегментации [11]) лежит после-
довательное применение к палитре исходных цветов изображения 2D
алгоритма k-means для характеристик U и V цветового пространства и 1D
алгоритма k-means для характеристики Y (рис. 6).
Изображение, разбитое
на три кластера, процес-
сорное время 126132 мс
Изображение, разбитое на
пять кластеров, процес-
сорное время 178307 мс
Рис. 6. Пример предварительной YUV-сегментации
Оценка эффективности нового статистического иерархического агломеративного алгоритма …
Системні дослідження та інформаційні технології, 2005, № 2 127
При простейшей предварительной сегментации [6, 7] исходное изобра-
жение разбивается на блоки заданного размера (в предлагаемых работах —
блоки 44× пикселя). Цветовые характеристики всех пикселей полученных
блоков принимаются равными средним цветовым характеристикам блоков
(рис. 7).
Анализируя результаты примеров кластеризации с предварительной
сегментацией, необходимо заметить, что наряду со значительным ускорени-
ем процесса кластеризации, получаемом при сегментации на блоки, эта ме-
тодика проигрывает по критерию качества. Таким образом, выбор техноло-
гии сегментации необходимо осуществлять, исходя из требований к
качеству и доступных вычислительных мощностей. В нашей работе предла-
гаемый алгоритм не дополняется ни одним из видов сегментирования.
4. КРИТЕРИИ ОЦЕНКИ КАЧЕСТВА КЛАСТЕРИЗАЦИИ ИЗОБРАЖЕНИЙ
4.1 Функционал качества разбиения Колмогорова
Предлагается подход оценки качества разбиения изображений на кластеры,
основанный на схеме, предложенной А.Н. Колмогоровым и описанной в ра-
боте [12]. Эта схема основана на понятии меры концентрации )(SZ точек,
соответствующей разбиению S , и средней меры внутриклассового рассея-
ния )(SI , характеризующей то же разбиение S .
Мера концентрации точек кластеров в данной схеме
∑
=
=
k
i
in
n
SZ
1
21)( , (5)
где k — число различных кластеров в разбиении S ; n — общее число эле-
ментов во всех кластерах; in — число элементов в кластере iS .
Заметим, что предложенная мера концентрации имеет минимальное
значение, равное
n
1 , при разбиении исследуемого множества на n одното-
чечных кластеров, и максимальное значение, равное 1, при объединении
всех объектов в один кластер.
Средняя мера внутриклассового рассеяния определяется
Изображение, разбитое
на три кластера, процес-
сорное время 1813 мс
Изображение, разбитое на
четыре кластера, процессор-
ное время 5500 мс
Рис. 7. Пример кластеризации с предварительным разбиением на блоки 44×
Е.А. Башков, О.Л. Вовк
ISSN 1681–6048 System Research & Information Technologies, 2005, № 2 128
∑ ∑
= ∈
=
n
i iXSlX
li
i
XXd
Xn
SI
1 )(
),(
)(
11)(
υ
, (6)
где )( iXυ — число элементов в кластере, содержащем точку iX ;
),( li XXd — расстояние между точками iX и lX .
Определим функционал качества Колмогорова для распознавания
образов изображений: качество разбиения изображения на кластеры
выше у того из сравниваемых алгоритмов, для которого выражение =)(SK
)(1
)(
))()(/1(
1
SI
SZ
SISZ +=+= имеет максимальное значение, т.е. при
максимальном количестве точек кластера разброс значений цветовых харак-
теристик является минимальным.
4.2. «Удаленность» кластеров друг от друга
При удовлетворении требований полноты и точности кластеризации резуль-
тирующие кластеры должны не только иметь минимальный разброс цвето-
вых характеристик (согласно критерию, описанному выше), но и быть мак-
симально «удаленными» по отношению друг к другу.
В соответствии с [13] «удаленность» кластеров друг от друга можно
измерять величиной
∑
−
=−
=
1
11
1 k
i
id
k
f , (7)
где k — количество кластеров, полученное в результате разбиения; id —
расстояние между центрами кластеров.
Согласно этому критерию более эффективным является тот алгоритм
кластеризации, для которого числовое значение f будет наибольшим.
4.3. Учет значимости неиспользуемых характеристик
Критерием является результат проведения теста значимости, с помощью
которого анализируются кластеры по признакам, не применявшимся при
получении кластерного решения [3].
Для решения проблемы кластеризации изображений этот критерий
предлагается переформулировать следующим образом.
Определить различия R в кластерных решениях, найденные одним и
тем же алгоритмом кластеризации, но с использованием различных цвето-
вых характеристик. Т.е. необходимо сравнить решения, полученные каждым
из исследуемых методов для различных цветовых пространств. Тот алго-
ритм, для которого данное различие минимально, и является более устойчи-
вым к смене цветовых координат. Таким образом, показатель качества со-
гласно этому критерию выше у алгоритмов с максимальным значением
величины
R
1 .
В качестве анализируемых цветовых пространств выбраны пространст-
ва RGB и HSL [8, 14].
4.4. Сравнительный анализ качества алгоритмов кластеризации
Исследования качества алгоритмов кластеризации k-means и НСАА прово-
дилось на базе данных картинок, описанных в подпункте 3.4. Результаты
тестирования по критериям, рассмотренным выше, приведены на рис. 8–10.
Оценка эффективности нового статистического иерархического агломеративного алгоритма …
Системні дослідження та інформаційні технології, 2005, № 2 129
Полученные практические результаты тестирования рассматриваемых
алгоритмов показывают, что в абсолютном большинстве случаев лучшими
являются показатели эффективности НСАА. Основными предпосыл-
ками получения таких числовых значений предлагаемых критериев можно
считать:
• отсутствие в алгоритме k-means учета вклада каждой из анализируе-
мых характеристик (в методе НСАА эта задача решается введением маски
связей и рангов цветовых компонентов);
• окончание процесса кластеризации в методе k-means по критериям,
не связанным с данными конкретного рассматриваемого изображения в от-
личие от разработанного алгоритма [6, 7].
0
0,5
1
1,5
2
11
,5
7
12
,2
8
12
,5
3
12
,8
7
13
,0
6
13
,1
7
13
,3
9
13
,6
7
13
,9
6
14
,0
9
14
,1
8
14
,3
9
14
,5
6
14
,6
1
14
,7
3
14
,9
3
15
,0
2
15
,1
1
15
,3
6
16
,5
7
Энтропия
K(
S)
=Z
(S
)/(
1+
I(S
))
1
2
Рис. 8. Показатели функционалов качества разбиения Колмогорова: 1 — НСАА;
2 — k-means
0
0,5
1
1,5
2
2,5
3
3,5
4
11
,5
7
12
,2
1
12
,4
5
12
,6
1
12
,8
8
13
,0
6
13
,1
2
13
,2
3
13
,4
4
13
,7
1
13
,9
6
14
,0
7
14
,1
2
14
,2
3
14
,4
7
14
,5
6
14
,6
1
14
,7
0
14
,8
1
14
,9
4
15
,0
2
15
,1
1
15
,2
1
15
,4
3
16
,5
7
Энтропия
f=
Su
m
(d
i)/
(k
-1
) 1 2
Рис. 9. Показатели «удаленности» кластеров друг от друга: 1 — НСАА; 2 —
k-means
0
2
4
6
8
10
12
14
11
,5
7
12
,2
1
12
,4
5
12
,6
1
12
,8
8
13
,0
6
13
,1
2
13
,2
3
13
,4
4
13
,7
1
13
,9
6
14
,0
7
14
,1
2
14
,2
3
14
,4
7
14
,5
6
14
,6
1
14
,7
0
14
,8
1
14
,9
4
15
,0
2
15
,1
1
15
,2
1
15
,4
3
16
,5
7
Энтропия
1/
R
1 2
Рис. 10. Показатели критерия учета значимости неиспользуемых характеристик:
1 — НСАА; 2 — k-means
Е.А. Башков, О.Л. Вовк
ISSN 1681–6048 System Research & Information Technologies, 2005, № 2 130
ВЫВОДЫ
Предложен эффективный алгоритм кластеризации изображений НСАА.
В основе нового метода кластеризации — статистический иерархический
агломеративный метод. Для выделения объектов изображений проведена
существенная модификация алгоритма, базирующаяся на введении маски
взаимосвязей и рангов отдельных цветовых компонентов изображений, не-
обходимой для учета значения каждого из этих компонентов.
В работе проведено многостороннее тестирование НСАА. Среди кри-
териев тестирования: быстродействие, критерий функционалов качества
разбиения Колмогорова, «удаленности» кластеров друг от друга и учета
значимости неиспользуемых цветовых характеристик. В ходе практического
тестирования НСАА и алгоритмов k-means более высокие показатели каче-
ства и быстродействия были получены для разработанного алгоритма. Для
подтверждения практических результатов приведено теоретическое обосно-
вание эффективности НСАА по предлагаемым критериям.
ЛИТЕРАТУРА
1. An Efficient k-Means Clustering Algorithm: Analysis and Implementation /
T. Kanungo, D. Mount, N. Netanyahu et al. // IEEE Transactions on Pattern
Analysis and Machine Intelligence. — July 2002. — 24, № 7. — P. 881–892.
2. Chen C.H., Pau L.F., Wang P.S.P. The Handbook of Pattern Recognition and Com-
puter Vision (2nd Edition). — World Scientific Publishing Co. — 1998. —
1004 p.
3. Ким Д.О., Мьюллер Ч.У., Клекка У.Р. Факторный, дискриминантный и кластер-
ный анализ. – М.: Финансы и статистика, 1989. — 215 с.
4. Классификация и кластер / Под ред. Д. В. Райзина — М.: Мир, 1980. — 393 с.
5. Jain A.K., Murty M.N., Flynn P.J. Data Clustering: A Review // ACM Computing
Surveys. — 1999. — 31, № 3. — P. 264–323.
6. Wang J.Z., Du Y. Scalable Integrated Region-based Image Retrieval using IRM and
Statistical Clustering // Proc. ACM and IEEE Joint Conference on Digital Librar-
ies. — Roanoke, VA, ACM, June 2001. — Р. 268–277.
7. Wang J.Z., Li J., Wiederhold G. SIMPLIcity: Semantics-Sensitive Integrated Match-
ing for Picture Libraries // IEEE Transactions on Pattern Analysis and Machine
Intelligence. — 2001. — 23, № 9. — P. 947–963.
8. Прэтт У. Цифровая обработка изображений. – Кн. 1. — М.: Мир, 1982. ––
312 с.
9. Путятин Е.П. Нормализация и распознавание изображений. http: // sum-
school.sumdu.edu.ua / i s-02 / rus / lectures / pytyatin / pytyatin.htm.
10. Comaniciu D., Merr P. Robust Analysis of Feature Spaces: Color Image Segmenta-
tion // Proc. Of CVPR’97. — P. 750–755.
11. Lucchese L., Mitra S.K. Unsupervised Segmentation of Color Images Based on
k-means Clustering in the Chromaticity Plane // Proc. of IEEE Workshop on
Content-based Access of Images and Video Libraries (CBAIVL'99). — Fort
Collins, CO. — 1999. — P. 74–78.
12. Айвазян С. А., Мхитарян В.С. Прикладная статистика и основы эконометрики:
Учебник для вузов. — М.: ЮНИТИ, 1998. — 1022 с.
13. Загоруйко Н.Г. Методы распознавания и их применение. — М.: Сов. радио,
1972. — 206 с.
14. Руководство по работе с цветом компании X-Rite. http://www.Realcolor.ru.
Поступила 28.08.2003
|
| id | journaliasakpiua-article-171322 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2025-07-17T10:25:13Z |
| publishDate | 2019 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/6c/78e96f3012d968c6453692014f67b16c.pdf |
| spelling | journaliasakpiua-article-1713222019-06-24T12:52:05Z Effectiveness evaluation of new statistical hierarchical aglomerative clusterization algorithm for recognition of images regions Оценка еффективности нового статистического иерархического агломеративного алгоритма кластеризации для распознавания регионов изображений Оцінка ефективності нового статистичного ієрархічного агломеративного алгоритму кластеризації для розпізнавання регіонів зображень Bashkov, E. A. Vovk, O. L. The new hierarchical aglomerative algorithm for cluster (region) recognition of images is considered. The analysis of the processing speed of the suggested algorithm and most widespread k-means algorithm is proposed. The evaluations of image clusterization quality are introduced. Рассматривается новый иерархический агломеративный алгоритм выделения кластеров (регионов) изображений. Приводится анализ быстродействия предлагаемого алгоритма в сравнении с наиболее распространенным алгоритмом k-means кластеризации. Вводятся оценки качества кластеризации изображений. Розглядається новий ієрархічний агломеративний алгоритм виділення кластерів (регіонів) зображень. Надається аналіз швидкодії пропонованого алгоритму у порівнянні з найбільш поширеним алгоритмом k-means кластеризації. Вводяться оцінки якості кластеризації зображень. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2019-06-24 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/171322 System research and information technologies; No. 2 (2005); 117-130 Системные исследования и информационные технологии; № 2 (2005); 117-130 Системні дослідження та інформаційні технології; № 2 (2005); 117-130 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/171322/170986 Copyright (c) 2021 System research and information technologies |
| spellingShingle | Bashkov, E. A. Vovk, O. L. Оцінка ефективності нового статистичного ієрархічного агломеративного алгоритму кластеризації для розпізнавання регіонів зображень |
| title | Оцінка ефективності нового статистичного ієрархічного агломеративного алгоритму кластеризації для розпізнавання регіонів зображень |
| title_alt | Effectiveness evaluation of new statistical hierarchical aglomerative clusterization algorithm for recognition of images regions Оценка еффективности нового статистического иерархического агломеративного алгоритма кластеризации для распознавания регионов изображений |
| title_full | Оцінка ефективності нового статистичного ієрархічного агломеративного алгоритму кластеризації для розпізнавання регіонів зображень |
| title_fullStr | Оцінка ефективності нового статистичного ієрархічного агломеративного алгоритму кластеризації для розпізнавання регіонів зображень |
| title_full_unstemmed | Оцінка ефективності нового статистичного ієрархічного агломеративного алгоритму кластеризації для розпізнавання регіонів зображень |
| title_short | Оцінка ефективності нового статистичного ієрархічного агломеративного алгоритму кластеризації для розпізнавання регіонів зображень |
| title_sort | оцінка ефективності нового статистичного ієрархічного агломеративного алгоритму кластеризації для розпізнавання регіонів зображень |
| url | https://journal.iasa.kpi.ua/article/view/171322 |
| work_keys_str_mv | AT bashkovea effectivenessevaluationofnewstatisticalhierarchicalaglomerativeclusterizationalgorithmforrecognitionofimagesregions AT vovkol effectivenessevaluationofnewstatisticalhierarchicalaglomerativeclusterizationalgorithmforrecognitionofimagesregions AT bashkovea ocenkaeffektivnostinovogostatističeskogoierarhičeskogoaglomerativnogoalgoritmaklasterizaciidlâraspoznavaniâregionovizobraženij AT vovkol ocenkaeffektivnostinovogostatističeskogoierarhičeskogoaglomerativnogoalgoritmaklasterizaciidlâraspoznavaniâregionovizobraženij AT bashkovea ocínkaefektivnostínovogostatističnogoíêrarhíčnogoaglomerativnogoalgoritmuklasterizacíídlârozpíznavannâregíonívzobraženʹ AT vovkol ocínkaefektivnostínovogostatističnogoíêrarhíčnogoaglomerativnogoalgoritmuklasterizacíídlârozpíznavannâregíonívzobraženʹ |