Iterative adaptation algorithms in multicriteria tasks

Full Text

Введение

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

Подобного вида задачи чаще всего решаются с помощью сверточных нейронных сетей – YOLO, Fast R-CNN, MobileNet-SSD [1–5]. К сожалению, обучение сверточных нейронных сетей занимает большое количество времени и является ресурсозатратным.

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

В данной работе рассматривается применение каскадного классификатора Хаара и каскадного классификатора LBP (Local Binary Patterns), основанного на применении локальных бинарных шаблонов, для решения задачи определения допустимого места измерения толщины комплекса интима-медиа артериальной стенки сонной артерии.

Постановка задачи

Задача распознавания изображений базируется на задаче идентификации объекта или определения его свойств по его изображению.

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

Рассмотрим постановку многокритериальной задачи принятия решения.

Определение корректного критерия для задачи принятия решения является главным фактором выбора альтернативы из множества возможных альтернатив.

Предположим, что мы имеем некоторое множество оценок O. В то же время мы имеем некоторую оценку C, принимающую значение на этом множестве и являющуюся оценочной функцией. Значение оценочной функции будет приниматься как «наилучшее решение» в зависимости от смысла выбранного критерия. В этом случае, если $A=\left\{a_1\mathrm{,...,}{a}_n\right\}$ представляет собой множество решений, тогда $C:A\to O$.

В случае, когда необходимо принять решение на основе двух альтернатив a_i и a_k необходимо выразить отношение предпочтения, при котором одна альтернатива будет предпочтительнее. Подобное предпочтение так же можно выразить через значение оценочной функции $C\left(a_j\right)$_, где $a_j$ является предпочтительной альтернативой.

Приведенная выше постановка отражает принятие решения на основе одного критерия. Однако достаточно сложно найти задачу, при рассмотрении которой принятие решения базируется на одном критерии. Адаптируем постановку задачи для многокритериального случая.

Допустим, существует множество критериев $C_1\mathrm{,...,}{C}_m$, где $m>1$. Тогда $C_i:A\to O_i$, где O_i множество значений функции C_i.

На основании представленной постановки задачи многокритериального принятия решения можно сделать вывод, что задачи подобного вида определяются множеством возможных решений A, множеством критериев C и отношениями предпочтения на множестве A [6].

Итеративные адаптационные алгоритмы

Особенностью определения места для измерения на ультразвуковом снимке является относительно небольшие размеры поисковой области – порядка нескольких пикселей. Данный момент значительно усложняет поставленную задачу детектирования, ведь помимо небольшого размера искомой области, ультразвуковое исследование (УЗ) снимка представляет собой набор повторяющихся признаков, которые комбинируется в различных положениях. Таким образом, необходимо учитывать динамическую составляющую для решения задачи и подбирать алгоритм, который может адаптироваться в процессе распознавания, для достижения наилучших результатов детектирования и уменьшения процента ошибочных распознаваний.

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

Бустинг (англ. boosting – улучшение) – это мета-алгоритм машинного обучения. Основная идея бустинга заключается в комбинировании слабых функций, которые получаются в результате итеративного процесса, на каждом шаге которого модель обучается с использованием данных об ошибках предыдущих шагов. Классификатором является сильный обучающий алгоритм, который хорошо коррелирует с правильной классификацией [7].

Одним из примеров использования бустинга является метод Виолы-Джонса, который строит сильный обучающий алгоритм на основе признаков Хаара. Признаки Хаара – это прямоугольные особенности, подобные вейвлетам Хаара, каждый из которых является двоичной маской, т.е. черно-белым изображением [8; 9].

Метод Виолы-Джонса заключается в следующем: окно установленного размера движется по изображению, и рассчитывается признак Хаара для каждой области, над которым проходит окно. Для того, чтобы определить наличие или отсутствие предмета, рассчитывается разность между значением признака и обучаемым порогом. Однако из-за того, что признаки Хаара мало подходят для классификации или обучения, необходимо использовать большое число признаков, чтобы описать объект с достаточной точностью. Именно поэтому в методе Виолы-Джонса признаки Хаара организованы в каскадный классификатор [10].

Классификатор, построенный на признаках Хаара, может использоваться в режиме реального времени, т.к. признаки Хаара могут вычисляться за постоянное время при использовании интегрального представления изображения. Высокая скорость является доминирующим преимуществом использования данного подхода в сравнении с аналогичными алгоритмами.

LBP представляет собой определенный вид признака, который может быть использован для классификации в компьютерном зрении. Это эффективный оператор, преобразующий каждый пиксель изображения в двоичное число, которое зависит от интенсивности соседних пикселей изображения [9].

Алгоритм adaptive boosting (адаптивного усиления) лежит в основе формирования каскада классификаторов, или сокращенно AdaBoost (мета-алгоритм, предложенный Йоавом Фройндом и Робертом Шапиро) [9]. Этот алгоритм менее подвержен переобучению по сравнению с другими алгоритмами машинного обучения и может использоваться в сочетании с несколькими алгоритмами классификации для повышения их эффективности. Однако AdaBoost чувствителен к шуму в данных и случайным выбросам.

Построение линейной комбинации классификаторов

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

Рассмотрим алгоритм построения каскадного классификатора:

1. Определяем количество этапов обучения, количество отрицательных примеров и количество положительных примеров. Производим инициализацию весов.
2. Производим нормализацию весов обучающих примеров.
3. Минимизируем ошибку для каждого слабого классификатора путем поиска параметров для признаков Хаара.
4. Производим поиск классификатора с наименьшей ошибкой.
5. Для каждого обучающего примера корректируем веса на основе проведенных расчетов. Возвращаемся к пункту 2.

После того, как приведенный выше алгоритм выполнит заданное количество этапов обучения, будет сформирован итоговый классификатор.

В данной работе исследуются следующие алгоритмы бустинга:

• Discrete AdaBoost – ранняя версия AdaBoost рассматривала композицию из алгоритмов $h\in H$, которые возвращают лишь значения из $Y=\left\{-\mathrm{1,}+1\right\}$;
• Real AdaBoost – обобщен на случай, когда $h\in H$ возвращают вероятность принадлежности классу $\left\{+1\right\}$;
• LogitBoost – композиция бинарных классификаторов строится с использованием идеи логистической регрессии;
• Gentle AdaBoost – отличается от Real AdaBoost вычислением отклика слабого классификатора [11].

Обработка результатов экспериментальных исследований

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

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

Сложность оценки качества обучения каскадов и детектирования заключается в том, что выбор зоны для оптимального определения интима-медиа артериальной стенки сонной артерии является относительно субъективным мнением специалиста, который обрабатывает результаты УЗИ. Существует ряд особенностей для выбора оптимальной зоны: четкий кадр, участок артерии должен быть прямой, без разрывов.

Коэффициент качества детектирования – это отношение количества неверных классификаций к общему количеству изображений.

$C=\frac{P_{пром}}{P_{общ}}$, (5)

где P_пром – количество неверных классификаций, P_общ – общее количество изображений.

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

Рассмотрим параметры обучения каскадных классификаторов:

• тип бустинга;
• коэффициент, определяющий качество обучения;
• уровень ложной тревоги;
• количество этапов обучения.

Настраиваемыми параметрами являются количество соседей, минимальный размер.

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

Минимальный размер – размер прямоугольника, являющийся допустимым местом для измерения комплекса интима-медиа.

Таким образом, выведена стратегия исследования качества детектирования для каждого каскадного классификатора:

• исследование качества детектирования в зависимости от количества этапов обучения при количестве соседей от 1 до 4, для определения оптимального числа этапов обучения на основании минимальной частоты ошибок;
• исследование качества детектирования в зависимости от типа бустинга при оптимальном числе этапов обучения;
• исследование качества детектирования в зависимости от коэффициента, определяющего качество обучения при оптимальном числе этапов обучения;
• исследование качества детектирования в зависимости от уровня ложной тревоги при оптимальном числе этапов обучения;

На рисунке 1 представлена диаграмма сравнения эффективности использования типов бустинга применительно к каскадным классификаторам Хаара и LBP. Как видно из диаграммы, доля неправильно распознанных объектов при использовании каскадного классификатора Хаара значительно ниже с типом бустинга Gentle. Однако, аналогичное значение доли неправильно распознанных объектов показал и каскадный классификатор LBP с типом бустинга LogitBoost.

 

Рисунок 1 Сравнительная диаграмма эффективности использования типов бустинга

 

На рисунке 2 представлена диаграмма сравнения результатов тестирования каскадных классификаторов Хаара и LBP при разных значениях коэффициентов, определяющих качество обучения. Согласно диаграмме, значение доли неправильно распознанных объектов при использовании каскадного классификатора Хаара меньше, чем при использовании каскадного классификатора LBP. На данной обучающей выборке значения коэффициентов обучения не влияют на долю неправильно распознанных объектов при решении задачи детектирования допустимых участков измерения толщины комплекса интима-медиа артериальной стенки сонной артерии.

 

Рисунок 2 Сравнительная диаграмма эффективности использования разных значений коэффициентов обучения

 

На рисунке 3 представлена диаграмма сравнения результатов тестирования каскадных классификаторов Хаара и LBP при разных уровнях ложной тревоги. Как видно из диаграммы, доля неправильно распознанных объектов при использовании каскадного классификатора Хаара, в среднем, ниже, чем при использовании каскадного классификатора LBP.

 

Рисунок 3 Сравнительная диаграмма использования разных уровней ложной тревоги

 

На рисунке 4 представлены зависимости доли неправильно распознанных объектов каскадного классификатора LBP и Хаара от числа этапов обучения. Для каскадного классификатора LBP 13 является оптимальным значением числа этапов обучения, поскольку при числе этапов более 14 классификатор начинает переучиваться. Так же рисунок 4 показывает, что для каскадного классификатора Хаара минимальная доля неправильно распознанных объектов достигается при использовании 18 этапов обучения.

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

 

Рисунок 4 График зависимости доли неправильно распознанный объектов от количества этапов обучения

 

Заключение

Произведен сравнительный анализ значений доли неправильно распознанных объектов при помощи каскадного классификатора Хаара и каскадного классификатора LBP.

По результатам проведенного исследования для получения наилучших результатов детектирования описанной предметной области при помощи каскадного классификатора Хаара и каскадного классификатора LBP необходимо проводить обучение, используя следующие значения параметров:

• при использовании каскадного классификатора Хаара – уровень ложной тревоги 0,5, тип бустинга GAB (Gentle AdaBoost), коэффициент, отвечающий за качество обучения, 0,999;
• при использовании каскадного классификатора LBP – уровень ложной тревоги 0,5, тип бустинга LB (LogitBoost), коэффициент, отвечающий за качество обучения, 0,999.

About the authors

Irina S. Belger

Samara National Research University

Author for correspondence.
Email: irina.belger@mail.ru

PhD Student of Information Systems and Technologies Department

Russian Federation, Samara

Olga P. Soldatova

Samara National Research University

Email: op-soldatova@yandex.ru

Associated Professor of Information Systems and Technologies Department

Russian Federation, Samara

References

Supplementary files