Содержание к диссертации
Введение
1 Текстурные статистические методы анализа изображений 20
1.1 Понятие текстуры 20
1.2 Статистические признаки Харалика 21
1.3 Классификация с помощью статистических признаков 26
1.4 Классификация изображений биомедицинских препаратов 28
1.5 Использование цветовых пространств 30
1.6 Численный эксперимент 33
1.7 Результаты 34
2 Использование диффузионных моделей описания поведения сложных систем 36
2.1 Понятие диффузионной модели 36
2.2 Использование диффузионных моделей для классификации изображений 38
2.3 Модель Diffusion-limited aggregation (DLA) для плоского случая 38
2.4 Оптимизация модели DLA для плоского случая
2.4.1 Априорная оценка коэффициентов выбора 41
2.4.2 Определение точки присоединения новой частицы 42
2.4.3 Особенности реализации 43
2.4.4 Оценка вычислительной сложности з
2.4.5 Численный эксперимент 44
2.4.6 Оценка достоверности результатов
2.5 Модель DLA для поверхности 47
2.6 Оптимизация модели DLA для поверхности
2.6.1 Априорная оценка коэффициентов присоединения 48
2.6.2 Определение точки присоединения новой частицы 49
2.6.3 Оценка вычислительной сложности 50
2.6.4 Численный эксперимент 51
2.7 Результаты 51
3 Метод построения модели с использованием стационарного по токанаграфе 53
3.1 Основные определения 53
3.2 Построение стационарного потока на графе 54
3.2.1 Описание базового алгоритма 55
3.3 Модификация алгоритма построения стационарного потока на графе 56
3.4 Оценка вычислительной сложности 58
3.5 Численный эксперимент 59
3.6 Результаты 62
4 Особенности реализации комплекса программ 64
Заключение 68
Литература 69
- Классификация с помощью статистических признаков
- Численный эксперимент
- Модель Diffusion-limited aggregation (DLA) для плоского случая
- Модификация алгоритма построения стационарного потока на графе
Введение к работе
Актуальность темы исследования. Вопрос создания компьютерных алгоритмов, способных разделить множество изображений на классы в зависимости от типа иллюстрируемой ими информации (решить задачу классификации), часто возникает при решении задач из совершенно различных прикладных областей знаний, таких как анализ аэрофотографий местности, дефектоскопия материалов по изображениям, исследование фотоснимков областей звездного неба. Необходимость автоматизации в таких задачах обусловливается чрезвычайно большим числом анализируемых изображений, настолько большим, что ручной анализ их занял бы месяцы и годы. Поэтому важными качествами используемых алгоритмов должны быть как высокая точность классификации, так и высокая скорость работы. Кроме того, алгоритмы анализа и классификации изображений всегда проблемно-ориентированы.
Биология и медицина — активно развивающиеся области современной науки, в которых анализ и классификация изображений играют особую роль: фактически это единственный способ наблюдения за той или иной исследуемой в их рамках органической системой, начиная с наблюдаемой в микроскоп клетки и заканчивая изображениями органов и тканей. Точные и быстрые алгоритмы компьютерной классификации изображений по определенным признакам могут сильно облегчить задачу врача или ученого, работающего в указанных областях.
Несмотря на взрывной рост числа новых работ в исследуемой области за последние 15 лет, достаточно очевидно, что объем и разнообразие доступной для анализа информации чрезвычайно велики, и существующие методы не всегда могут дать приемлемый результат.
Актуальность темы исследования обусловлена необходимостью использования новых идей и создания на их основе алгоритмов для анализа и классификации биомедицинских изображений, что позволит исследователям получить более полное представление о процессах, происходящих в объектах естественного происхождения.
Степень разработанности темы исследования. В последнее время растет число работ, посвященных анализу и классификации биомедицинских
изображений. Наиболее часто используется морфологический анализ, текстурный анализ, фрактальный и мультифрактальный анализ, анализ c помощью нейронных сетей, многомерный анализ изображений, исследования изображений с помощью теории графов и при помощи кластерного анализа. Для повышения точности и скорости классификации применяются методы поля направлений, вейвлет-преобразования, дискриминантный и факторный анализ. Большое число различных применяемых методов обусловлено большой вариативностью исследуемых изображений. Методы классификации изображений применяются для распознавания мочекаменной болезни, заболеваний крови, исследования препаратов тканей различных органов, определения наличия герпеса, определения наличия заболеваний нервной системы и сердечных заболеваний. Для решения перечисленных задач анализируются снимки внутренних органов и тканей, образцы кристаллизированных (дегидратированных) капель биологических жидкостей, снимки микрообъектов (клетки, нервные окончания), изображения кровеносных сосудов глазного дна, рентгеновские изображения коронарных сосудов. Множество исследуемых данных расширяется еще и за счет того, что снимки объектов естественного происхождения могут отличаться большой вариабельностью форм даже в рамках одного класса.
Особое внимание уделяется вопросам исследования цветных изображений и вопросам их предварительной обработки для повышения точности работы классифицирующих алгоритмов. Кроме того, исследуются вопросы оптимизации, распараллеливания и организации вычислений с помощью графических карт с целью повышения быстродействия.
Объектом исследования являются модели, методы, алгоритмы и программные средства обработки изображений. Предметом исследования являются разработка и реализация алгоритмов решения задачи классификации изображений биомедицинских препаратов.
Исследуемое изображение при решении задачи классификации биомедицинских изображений полезно рассматривать как фазовый портрет некоторой сложной динамической системы. Математическое описание такой системы редко бывает возможным, поскольку моделирование процессов, происходящих в живых тканях требует учета огромного числа параметров и связей
между ними. Анализ фазовых портретов позволяет охарактеризовать состояние системы в определенный момент времени, а также промоделировать развитие процесса, например, достижения системой некоторого стационарного состояния.
Цифровые изображения представляются в виде решетки пикселей с заданными параметрами, поэтому их характеристики формулируются в этих терминах. Так характеристики Харалика описывают взаимное расположение пикселей различной интенсивности. Методы фрактального и мультифрак-тального анализа используют разбиение изображения на ячейки и вычисление их мер с последующим определением размерности (или набора размерностей). С точки зрения динамики фазовый портрет системы характеризует распределение траекторий по фазовому пространству в некоторый момент времени, а распределение меры характеризует частоту попадания траекторий в ячейки разбиения.
Такой подход к анализу изображений позволяет:
охарактеризовать текущее состояние процесса с помощью вычисления статистических и фрактальных характеристик;
для широкого класса диффузионных процессов реализовать модель их развития от начального состояния;
охарактеризовать стационарные состояния процесса с помощью построения стационарного потока на связанном с изображением графе.
Целью работы является разработка алгоритмов классификации изображений биомедицинских препаратов, основанных на анализе фазовых портретов динамических систем, и реализация на их основе комплекса программ.
Для достижения поставленной цели решаются следующие задачи:
исследовать влияние выбора цветовых координат в качестве начальных данных для классификации биомедицинских изображений с помощью вычисления статистических признаков Харалика второго порядка;
разработать модификацию алгоритма построения агрегатов по математической модели DLA (Diffusion Limited Aggregation) с помощью априорной оценки коэффициентов присоединения;
разработать модификацию алгоритма построения стационарного потока на графе путем построения стационарных потоков на подграфах;
- разработать комплекс программ, реализующих все перечисленные алгоритмы.
Методология и методы исследования. Методология работы основана на методах индукции и дедукции, обобщения, математического моделирования, анализа и синтеза теоретического и практического материала. При получении основных результатов работы использовались методы работы с двумерными изображениями, построения математических моделей сложных систем, компьютерного моделирования, математического анализа, теории графов, теории сложности вычислений, а также программирование на языке высокого уровня.
Достоверность и обоснованность полученных результатов опирается на проведенные доказательства, рассуждения и эксперименты.
Научная новизна диссертации заключается в том, что разработанные в ней алгоритмы классификации изображений биомедицинских препаратов предложены впервые. Использование координат цветовых пространств в качестве исходных данных для классификации с помощью статистических признаков Харалика дает более высокую точность классификации по сравнению с классическим методом. Использование модифицированных алгоритмов построения агрегатов и стационарного потока на графе позволяет значительно уменьшить временную и емкостную сложности вычислений, что позволяет получить сопоставимые с оригинальными алгоритмами результаты до 40 раз быстрее. В диссертации сформулированы и доказаны четыре теоретических утверждения, обосновывающие эффективность разработанных алгоритмов.
Теоретическая и практическая значимость работы. В рамках диссертационного исследования разработана алгоритмическая основа для комплекса программ анализа и классификации изображений биомедицинских препаратов. Предлагаемые алгоритмы дают большую точность классификации и обладают меньшей вычислительной сложностью, что делает результаты диссертации теоретически значимыми. Практическая значимость результатов диссертации заключается в реализации комплекса программ, позволяющего оценить эффективность разработанных алгоритмов классификации для каждого конкретного случая исследований.
Положения, выносимые на защиту
-
Предложен метод использования координат цветовых пространств RGB и HSV в качестве входных данных для алгоритмов анализа изображений с помощью статистических характеристик Харалика второго порядка. Полученные наборы характеристик для разных цветовых пространств позволяют выбрать наиболее подходящую пару координата-признак или комбинацию таких пар для эффективной классификации изображений.
-
Разработаны и реализованы алгоритмы эффективного построения агрегатов по модели DLA с помощью априорного анализа коэффициентов выбора как в плоском случае, так и в случае построения агрегатов на произвольной поверхности. Путем вычисления емкостной размерности и дивергенции Кульбака–Лейблера показано, что полученные с помощью модифицированного алгоритма агрегаты качественно близки к агрегатам, построенным по классической модели DLA. Дана теоретическая оценка вычислительной сложности предложенных алгоритмов. Программы для реализации классических алгоритмов запускались на компьютере с процессором Intel CoreDuo T2050 и объемом оперативной памяти 1.5GB. Время вычислений одного агрегата из 10000 частиц для плоского случая составило 37 мин. 43 сек.; время вычислений 10 агрегатов из 1000 частиц на поверхности составило 4 ч. 47 мин. 33 сек. Оптимизированные алгоритмы запускались на той же конфигурации оборудования. При этом время вычислений одного агрегата из 10000 частиц для плоского случая составило 1 мин. 8 сек.; время вычислений 10 агрегатов из 1000 частиц на поверхности составило 31 мин. 58 сек. В результате продемонстрировано уменьшение времени вычислений приблизительно в 40 раз для плоского случая и в 10 раз при моделировании на поверхности по сравнению с классическими алгоритмами.
-
Разработана и реализована модификация алгоритма Шелейховского– Брэгмана построения стационарного потока на графе путем разбиения изображения на подмножества, построения стационарного потока на каждом из подмножеств и объединения стационарных потоков в один общий поток. Приведена оценка потери точности вычислений на склеиваемых границах областей; оценено ее влияние на значение взвешенной энтропии, выступающее в качестве классифицирующего признака. Показана эффективность модифи-
цированного алгоритма для использования на многоядерных системах. Программа для реализации классического алгоритма запускалась на компьютере с процессором Intel CoreDuo T2050 и объемом оперативной памяти 1.5GB. Время вычислений составило 13 мин. 3 сек. Оптимизированный алгоритм запускался на той же конфигурации оборудования. Время вычислений составило 1 мин. 38 сек. В результате продемонстрировано уменьшение времени вычислений приблизительно в 10 раз.
4. Разработан и реализован комплекс программ для исследования и классификации изображений биомедицинских препаратов, который объединяет в себе методы статистического анализа с помощью вычисления характеристик Харалика второго порядка в координатах цветовых пространств RGB и HSV; методы имитационного моделирования структуры изображения путем построения агрегатов с помощью априорного анализа коэффициентов распределения для модели DLA; методы анализа с помощью построения стационарного потока на связанном с изображением графе.
Апробация результатов. Основные результаты диссертационной работы докладывались и обсуждались на следующих научных конференциях и семинарах:
-
Конференция “Научные исследования и их практическое применение. Современное состояние и пути развития”, 2012, Одесса;
-
LXVI и LXVII Международные конференции “Герценовские чтения”. Секция “Актуальные информационные системы и технологии моделирования”, 2013 - 2014, РПГУ им. Герцена, Санкт-Петербург;
-
“Межвузовский конкурс-конференция студентов, аспирантов и молодых ученых Северо-Запада”, 2013, СПбГПУ, Санкт-Петербург;
-
Восьмая международная конференция “Актуальные проблемы прикладной математики, информатики и механики”, 2013, ВГУ, Воронеж;
-
Семинары “Информатика и компьютерные технологии”, доклады “Алгоритм анализа изображений, основанный на построении стационарного потока на графе” и “Разработка и реализация алгоритмов классификации изображений биомедицинских препаратов”, 2014–2015, СПИИРАН, Санкт-Петербург;
-
9-th International Conference on Communications, Electromagnetics and Medical Applications (CEMA), 2014, Technical Univercity of Sofia, Sofia, Bulgaria.
Классификация с помощью статистических признаков
В ранних работах по изучению текстур изображений использовались функции автоматической корреляции [64], понятие спектра мощности [51], ограниченные марковские цепи первого и второго порядков [46], отношения различных оттенков серого. Можно выделить исследования по классификации изображений с помощью определения “крупнозернистости” текстур [88] и наличия определенных паттернов в них [53].
В 1971 году Харалик, Шанмуган и Динстейн (Haralick R. M., Shanmugan K., Dinstein I.) предложили [59, 60] некоторую общую процедуру выделения текстурных свойств блоков графических данных. Они назвали эти свойства признаками, сейчас их называют “статистическими признаками Харалика второго порядка”. Эти признаки вычисляются в предположении, что информация о текстуре изображения заключается в общем или среднем пространственном отношении одних оттенков серого, содержащихся в изображении, к другим.
Для их вычисления необходимо составить набор матриц распределения вероятностей пространственной зависимости оттенков серого для изображения и вычислить на их основе вектор из 14 основных определяющих текстурных признаков. Эти характеристики содержат в себе информацию о таких особенностях изображения, как однородность, линейные зависимости оттенков серого, контрастность, число и природа границ, сложность структуры изображения.
Рассмотрим прямоугольное черно-белое изображение размером Nx на Ny. Предположим, что число вариантов оттенков серого, используемых для посто-ения изображения, равно Ng . Пусть Lx = {1, 2,..., Nx} множество столбцов, Ly = {1,2,..., АУ - множество строк в нашем изображении; G = {1,2,..., 7VJ — множество оттенков серого. Множество Ly х Lx — это множество элементов изображения, упорядоченное в виде строк и столбцов в соответствии с их положением в изображении. Изображение / можно представить в качестве функции, которая присваивает некоторый оттенок серого из множества G каждой паре Рисунок 1.1. – Соседние пиксели. координат I : Ly х Lx — G.
Для каждого пикселя в изображении определим понятие соседа — это пиксель, отличный от рассматриваемого, координаты которого в множествах Lx и Ly отличаются не более чем на 1 от координат рассматриваемого пикселя. Таким образом, все неграничные пиксели изображения имеют по 8 соседей, они показаны на рисунке 1.1.
Разделим 8 соседних пикселей на 4 класса в зависимости от того, каким образом они граничат с рассматриваемым пикселем. В первый класс попадут соседи номер 1 и 5, во второй — номера 4 и 8, в третий — номера 3 и 7, в четвертый — номера 2 и 6. Классы соответственно можно назвать классами направлений 0, 45, 90 и 135 градусов.
Понятие соседа можно обобщить на пиксели, находящиеся на расстоянии d друг от друга. Нас будут интересовать пиксели, находящиеся друг от друга на расстоянии d = 1 и принадлежащие одному классу направлений.
Будем строить четыре матрицы относительных частот P(i,j,d,x), с кото 23 рыми два элемента изображения, первый из которых имеет значение интенсивности г, а второй — j, находящиеся на расстоянии d и принадлежащие одному из четырех соответствующих классов направлений, встречаются в изображении. Другими словами,
Обратим внимание, что матрицы симметричны P(i,j,d,a) = P(J,i,d,a). Обычно рассматривают нормализованный вариант этих матриц, для чего делят все элементы матрицы на число R всех участвующих в подсчете по данному направлению пар. Другими словами
Построенные нами 4 матрицы размера Ng х Ng используются для вычисления следующих 14 характеристик, представляющих собой функции расстояния и угла. Все они были предложены в [60] и перечислены ниже:
При вычислении статистических признаков Харалика второго порядка алгоритм построения матриц относительных частот квадратичен по времени и линеен по памяти относительно числа пикселей исследуемого изображения. Существуют оптимизации [94, 75], основанные на распараллеливании, использовании статистических оценок и вероятностном анализе, которые дают время работы O(LxLy log(LxLy)). После построения этих матриц вычисление всех признаков занимает константное время (в случае признака f14 с достаточно большой константой из-за решения неявного уравнения). Как правило, ограничиваются вычислением подмножества признаков из числа f1–f13.
Каждая из представленых характеристик может быть использована как некоторое число, сопоставляемое изображению, и эти числа (или вектора из них) могут быть кластеризованы на числовой прямой (или в соответствующем пространстве) для решения задачи классификации.
Вместе с тем для каждых конкретных наборов классифицируемых изображений нет точного способа априори определить, какая (или какие) именно признаки из перечисленных дадут разбиение на классы, соответствующее действительности. Например, в работе [60] авторы приводят некоторые рассуждения об определении значимости такого признака, как энтропия, для разделения изображений, субъективно воспринимаемых как изображения “разной сложности картинки”, но подобные рассуждения нельзя воспринимать как математически строгое обоснование. Строго говоря, нет четкой гарантии того, что изображения, которые человек по тем или иным признакам разделяет на классы, разделимы на те же (или близкие к ним) классы с помощью текстурных признаков Харалика второго порядка. Кроме того, достаточно просто понять, что некоторое пары признаков линейно или нелинейно зависимы друг от друга, и вычисление обоих признаков из пары неэффективно.
Поэтому для использования классификатора на новых изображениях необходимо предварительно проанализировать, какие именно из признаков могут быть использованы для эффективного решения задачи автоматической классификации. Это можно сделать с помощью машинного обучения классификатора на тестовых данных, предварительно разделенных на классы [48]. В дальнейшем все вычисления будем производить для первых 13 признаков, вследствие того, что они вычисляются явно, в то время как 14 признак требует решения неявного уравнения.
Практические исследования показывают, что классификация с помощью указанных признаков во многих случаях дает точные результаты. Так, в работе [60] Харалик демонстрирует работу своего алгоритма классификации для идентификации категорий трех различных видов графических данных, и точность классификации алгоритма составляет 89% для микрофотоснимков пяти категорий песчаника, 82 % для аэрофотоснимков восьми категорий земной поверхности и 83 % для спутниковых снимков семи категорий земной поверхности.
Одним из классических наборов тестовых данных для определения эффективности классифицирующего алгоритма [92] является альбом изображений Бродаца [47], представляющий собой черно-белые фотоснимки поверхностей с различной текстурой, сделанные в условиях, близким к лабораторным. Два представителя из этого набора изображены на рисунке 1.2. Для каждого из изображений, представляющих свой собственный класс, были вычислены 13 характеристик.
Численный эксперимент
Итак, большое время расчета объясняется прежде всего большим числом обрабатываемых данных: число точек велико и траектория блуждания каждой точки может быть достаточно длинной. Рассматриваемый нами алгоритм представляет собой классический пример детерминированного алгоритма, обрабатывающего большие объемы данных. Его можно ускорить за счет перехода к решению упрощенной задачи с частичной информацией. 2.4.1 Априорная оценка коэффициентов выбора
Предположим, что при бросании частицы на координатную сетку ее координаты оказались равны (x + a, y + b). Сделаем оценку того, что данная частица присоединится к точке агрегата с координатами (x, y). Если при блуждании частицы по плоскости она сделала n шагов в сторону от точки (x, y) по оси абсцисс, то, чтобы попасть в (x, y), частица должна сделать (n+a) шагов в сторону точки (x, y). Соответственно, если при блуждании частица сделала m шагов в сторону от точки (x, y) по оси ординат, то она должна сделать (m + b) шагов в сторону точки (x, y). На каждом шаге блуждания направление следующего перехода определяется равновероятно между четырьмя вариантами. Это позволяет написать следующую оценку того, что через (2n+a+2m+b) шагов координатами блуждающей точки окажутся (x, y): 4n4n+a4m4m+b Число шагов, через которые блуждающая точка попадет в (x, y), определяется значениями n и m. Классы траекторий, определяемых конкретными значениями n и m, представляют собой разбиение множества всех траекторий
При бросании частицы на плоскость вычисляют такие оценки между первоначальными ее координатами и всеми точками границы агрегата. Полученный набор чисел будем называть коэффициентами выбора присоединения. В соответствии с вычисленными коэффициентами строится функция распределения случайной величины присоединения частицы к граничным точкам агрегата (“функция численного распределения”, [66]), из области значений которой случайным образом выбирается значение. Прообраз этого значения и определяет, к какой точке агрегата присоединится частица.
Особо стоит отметить, что для каждого бросания число вычислений, необходимых для определения, к какой именно точке агрегата присоединится новая точка, не зависит от каких-либо неизвестных на момент вычисления данных (таких, как число шагов в маршруте). Кроме того, ни одна из брошенных точек не отбрасывается. При таком методе оценки практически не учитывается влияние на коэффициент выбора расположения других точек агрегата, которые могут оказывать влияние на траекторию. Кроме того, учтены также и те траектории, в которых точка при блуждании по линиям решетки попадает в точку агрегата неоднократно. Эти ограничения являются неизбежным следствием того факта, что мы отказываемся от обработки части информации для ускорения вычислений.
При реализации предлагаемого алгоритма для ограниченной области из M точек на сетке предварительно вычисляются значения коэффициентов выбора присоединения для каждой пары точек сетки. Из них составляется матрица G размера M M коэффициентов выбора переходов из одной точки в другую. Заметим, что для двух пар точек, таких, что в каждой паре суммарное покоординатное расстояние между точками равно s = a + b, значение коэффициента выбора будет одинаковым и равным 41s . Это означает, что построение матрицы G избыточно и достаточно вычислить значение коэффициента выбора для всех возможных s. Тем не менее, идея построения матрицы G позволит в дальнейшем сформулировать некий более общий подход.
Один раз предварительно вычисленные значения коэффициентов присоединения могут быть переиспользованы для вычисления нескольких агрегатов.
Пусть число ячеек в рассматриваемой области M, а число бросаемых частиц T. Тогда вычислительная сложность этапа предподсче-та предлагаемого алгоритма равна O(M), а вычислительная сложность этапа бросания частиц равна O(T2). Размер используемой памяти пропорционален 0{М) на этапе предподсчета и константен на этапе бросания частиц.
Доказательство. Предварительное вычисление априорных коэффициентов для области из М точек пропорционально максимальному возможному для этой области s. Для квадратной области максимальное значение s пропорционально у/М, в общем случае оно не превосходит М + 1, что легко видеть из оценки периметра области заданной площади. Это означает, что алгоритмическая сложность вычисления априорных коэффициентов не более чем О(М), размер используемой памяти при этом также равен 0{М).
Предположим, что для некоторой области размером из М точек предварительно вычислены априорные оценки. При бросании на плоскость каждой новой частицы для нее необходимо выбрать одну из возможных точек границы уже построенного агрегата для присоединения. При бросании точки под номером к граница агрегата не может состоять более чем из к — 1 точки. Это означает, что для бросания Т частиц алгоритмическая сложность алгоритма не будет превосходить
Модель Diffusion-limited aggregation (DLA) для плоского случая
Были реализованы алгоритмы, описанные для построения базовой модели и модели с априорной оценкой выбора коэффициентов. Примеры результатов моделирования представлены на рисунке 2.4.
В каждой серии экспериментов было проведено по 10 вычислений. Вычисления производились для параметров N = 300, Т = 1000. Время построения 1 агрегата и общее время работы алгоритмов можно оценить из таблицы 2.1.
В различных моделях агрегации, ограниченной диффузией, вычисляют размерность полученного фрактала (как правило - емкостную). Это позволяет сравнить размерность образца, полученного в процессе диффузии, и образца, полученного с помощью предложенной в этой работе модели. В статье [60], где впервые рассматривалась описанная модель, для емкостной размерности была получена оценка 1.66. Во всех рассмотренных нами оптимизациях емкостная размерность построенных агрегатов колеблется от 1.62 до 1.73.
Опираясь только лишь на значение размерности, нельзя говорить о струк 46 турной близости двух фракталов между собой. В работе [38] приведен способ построения двух различных ковров Серпинского, емкостные размерности которых между собой совпадают. Там же в качестве одного из общепринятых вариантов сравнения двух изображений фракталов между собой предложен метод вычисления дивергенции Кульбака-Лейблера.
Расхождение (дивергенция) Кульбака-Лейблера - это несимметричная мера удаленности друг от друга вероятностных распределений. Одно из сравниваемых распределений — истинное, а второе — проверяемое на похожесть с первым. Для того чтобы подсчитать его значение для двух изображений фрактальных структур, поступают следующим образом. Каждое из двух изображений разбивают на n ячеек, для каждой из которых подсчитывают отношение числа пикселей, принадлежащих агрегату, к общему числу пикселей в области. Таким образом получают меру изображения {p{}. Расхождением Кульбака-Лейблера для изображений, определяемых мерами {p} и {q}, называют величину
Для оценки похожести агрегатов, построенных с использованием алгоритма с априорной оценкой вероятности, на агрегаты, построенные обычным способом, для двух представителей каждого из классов была вычислена величина дивергенции Кульбака-Лейблера. Вычисления производились по квадратной сетке из 100 ячеек. Величина D оказалась равна 5.0806. Для сравнения была вычислена дивергенция между изображениями агрегатов, построенных по алгоритмам DLA и RLCA, она оказалась равна 74.6781.
Приведенные значения емкостной размерности и дивергенции Кульбака-Лейблера между определяющими изображения агрегатов вероятностными мерами позволяют утверждать, что построенный в результате предложенного ав 47 тором алгоритма агрегат по своим структурным особенностям близок к агрегату сопоставимой мощности, построенному по классическому алгоритму.
В работах [20, 52, 97] описаны различные реализации алгоритма DLA на нерегулярной триангуляционной сетке. Точно так же, как и в плоском случае, процесс формирования агрегата начинается с одной частицы, занимающей один из треугольников триангуляции. Другие частицы последовательно бросаются на треугольники, составляющие триангуляцию и начинают блуждать по ней. На каждом шаге частица может перейти в один из треугольников, соседних с треугольником, задающим ее текущее положение. Переходы в разных соседей неравновероятны: вероятность перехода из треугольника 1 в треугольник 2 определяется по формуле где величины a, b, c сунке 2.5. длины сторон треугольника 1, отмеченные на ри Рисунок 2.5. – Вероятности перехода между треугольниками сетки.
В качестве примера авторы [20] успешно моделируют процесс распространения вещества на модели поверхности кости. Пример полученного результата представлен на рисунке 2.6. Тем не менее, для расчетов агрегатов, составленных из большого количества частиц, как и в плоском случае, требуется значительное время работы вычислителя.
Рисунок 2.6. – Пример результата моделирования DLA на триангуляционной сетке на модели поверхности кости, представленного в работе [20].
Построим на выделенной области поверхности триангуляционную сетку. Как и в [20], треугольники в ней могут иметь разные размеры. Пусть общее число треугольников равно M.
Каждому треугольнику ставим в соответствие вершину некоторого графа G. В этом графе между вершинами i и j есть дуга тогда и только тогда, когда соответствующие им треугольники Mi и Mj имеют общую сторону. На дугах расставим веса, равные вероятности перехода из i в j согласно приведенной выше формуле.
Рассмотрим всевозможные пути на графе длины не более чем некоторое N. Для любого пути между двумя произвольными вершинами i и j вероятностью этого пути назовем произведение вероятностей (весов) всех входящих в путь дуг. Вычислим некоторый коэффициент выбора для вершин і и j, равный сумме вероятностей всевозможных путей из і в j длины не более чем N. Из всех коэффициентов выбора составим матрицу G размера М х М.
Вычисления организуем следующим образом. Изначально нам даны вероятности всех путей, состоящих ровно из одной дуги (это веса на соответствующих дугах). Будем последовательно вычислять матрицы Gk. В матрицу G\ на позицию (i, j) при наличии на графе дуги (i,j) запишем значение веса этой дуги. На каждом шаге будем из матрицы Gk составлять матрицу Gk+i следующим образом. Пусть элемент (i, j) матрицы Gk равен у. Рассмотрим все дуги на графе, начало которых — j (таких дуг не более 3, по числу возможных соседей). Пусть для некоторой из этих дуг ее конец — х. Тогда в матрицу Gk+i на позицию (і, х) добавим число, равное у, умноженному на веc дуги (j, х). Матрицей G назовем сумму всех матриц Gk, где к Є {1...N}. Несложно заметить, что матрица G содержит значения всех коэффициентов выбора для путей длины не более чем N.
Модификация алгоритма построения стационарного потока на графе
Вычисления проводились на многоядерном вычислителе с числом ядер 4. Базовый алгоритм не допускает распараллеливания, поэтому скорость его работы не зависит от числа ядер системы. Как было показано выше, модифицированный алгоритм допускает распараллеливание. Поэтому для него вычисления производились трижды. В первом эксперименте вычислениям было отдано 1 ядро машины. В втором эксперименте использовались 2 ядра. В третьем — все 4 имеющихся ядра процессора.
В результате вычислений по базовому алгоритму были получены значения центров кластеров 1,37360 и 1,34875 соответственно для первого и второго классов изображений. В результате вычислений по модифицированному алгоритму при К = 4 были получены значения центров кластеров 1,37326 и 1,34804. При К = 16 были получены значения центров кластеров 1,35829 и 1,34103.
Алгоритмы сравнивались по двум факторам — процент точности и скорость работы. Процент точности вычислялся как отношение числа верно отнесенных к классам изображений к общему их числу. Результаты вычислений представлены в таблицах 3.1 и 3.2.
В результате численного эксперимента было установлено, что при вычислениях по модифицированному алгоритму процент точности падает с 96% до 92% при K = 4 и до 76% при K = 16. При этом скорость вычислений по модифицированному алгоритму c K = 4 даже при использовании 1 ядра процессора выше в 2,4 раза, а при использовании 4 ядер выше почти в 8 раз. При К = 16 скорость работы алгоритма на 4 ядрах практически в 10 раз превосходит скорость работы базового алгоритма. Стоит отметить, что для K = 16 необ 62
Предложена модификация алгоритма построения стационарного потока на графе, применяемого для решения задачи классификации изображений. Пока 63 зано, что алгоритмическая сложность модифицированного алгоритма меньше алгоритмической сложности исходного. Другим преимуществом модифицированного алгоритма является возможность его эффективного использования на многоядерных вычислителях. Реализованы все описанные алгоритмы.
Эксперимент показывает, что модифицированный алгоритм при K = 4 можно применять для классификации исследуемых изображений практически в той же мере, что и не модифицированный. При этом процент точности в использованной выборке падает всего на 4%, что позволяет утверждать о сравнимом качестве классификации. При этом при K = 16 процент точности падает значительно. Можно предположить, что это связано с тем, что процент числа граничных точек, в которых свойство стационарности построенного потока выполняется с точностью 4 по отношению к общему числу точек (в которых условие стационарности выполняется с точностью ) возрос. На указанной выборке падение процента точности составило 20%. Это означает, что алгоритм с большими значениями K для исследуемых изображений тканей печени можно использовать только как предварительно оценивающий степень близости картинки к тому или иному классу.
Для изображений больших размеров (или большего разрешения) можно ожидать, что для задач классификации могут быть использованы и большие значения K, вследствие того, что число граничных точек растет пропорционально линейным размерам изображения, в то время как общее число точек изображения растет квадратично. Глава 4. Особенности реализации комплекса программ
Комплекс программ для решения задачи классификации изображений биомедицинских препаратов реализован на языке программирования tcl (tool command language). Для создания форм пользовательского интерфейса использована графическая библиотека tk [101].
Все использованные в исследовании алгоритмы написаны в виде отдельных подключаемых модулей кода (библиотек), что позволяет переиспользовать их для дальнейших исследований в любой комбинации.
Для классификации изображений с помощью статистических признаков Харалика второго порядка были реализованы алгоритмы построения матриц относительных частот расположения пикселей по направлениям 0, 45, 90 и 135 градусов и вычисления с их помощью 13 статистических признаков. Для анализа влияния использования цветовых координат на результаты классификации были реализованы в виде отдельного модуля grayscale, R, G, B, H, S, V фильтры для цветных изображений. В исследованиях предполагалось вычисление статистических признаков Харалика для большого числа изображений различных классов, поэтому были реализованы сценарии автоматической обработки указанных групп изображений, сохраняющие результаты в виде таблиц, пригодных для дальнейшего анализа.
Для исследования алгоритма моделирования диффузионных процессов DLA были реализованы следующие варианты этого алгоритма: классический алгоритм построения агрегата на плоскости, алгоритм построения агрегата на плос 65 кости с ограничениями числа шагов и области блужданий частиц, алгоритм моделирования DLA на плоскости с использованием априорной оценки коэффициентов выбора, классический алгоритм построения агрегата на триангуляционной решетке, алгоритм построения агрегата на триангуляционной решетке с использованием априорной оценки коэффициентов выбора. Для оценки достоверности результатов были реализованы алгоритмы подсчета емкостной размерности плоской структуры и сравнения двух изображений агрегатов с помощью вычисления дивергенции Кульбака–Лейблера между их вероятностными мерами.
Для исследования алгоритма классификации изображений с помощью построения стационарного потока на связанном с изображением графе были реализованы алгоритмы построения начального ориентированного графа, построения приоритетной очереди вершин, балансировки этой очереди и нормировки потока. Для организации многопоточных вычислений было использовано свободно распространяемое расширение языка tcl под названием tcl threads [102]. Организация параллелизма с помощью потоков с разделяемой памятью [99] позволила избежать лишних копирований данных и накладных расходов, связанных с обеспечением и синхронизацией работы нескольких процессов.
Использование языка программирования tcl обеспечило кроссплатформен-ность реализованных алгоритмов. Командные интерпретаторы этого языка доступны для операционных систем семеств GNU/Linux, Windows и OS X. Для запуска комплекса программ на каждой из этих систем требуется установка командного интерпретатора с поддержкой графики wish.
Всего написано более 3500 строк программного кода алгоритмов. При реализации для загрузки изображений использовалась свободно распространяемая библиотека purecl-bmp версии 0.4, написанная S. Havelka [100].