Метод формирования признаков текстурных изображений на основе марковских моделей тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Пластинин, Анатолий Игоревич

• Пластинин, Анатолий Игоревич
• кандидат технических наук
• 2011

Оглавление диссертации кандидат технических наук Пластинин, Анатолий Игоревич

Содержание

Введение

Раздел 1. Формирование признаков текстурных изображений на основе модели марковских случайных полей с использованием процедуры обучения

1.1. Определение текстурных изображений

1.2. Модель марковского случайного поля

1.2.1. Модель изображения

1.2.2. Модель марковского случайного поля

1.2.3. Анализ векторов окрестностей

1.3. Обзор существующих методов анализа текстур

1.3.1. Признаки Габора

1.3.2. Метод цветовых гистограмм

1.3.3. Автокорреляционный метод

1.3.4. Метод матрицы взаимного вероятностного распределения

1.3.5. Признаки Тамура

1.4. Постановка задачи распознавания текстурных изображений

1.5. Регрессионные признаки изображений

1.6. Объект и задачи исследований

1.6.1. Диагностические изображения клеток крови

1.6.2. Диагностические изображения в металлографии

1.7. Выводы

Раздел 2. Вычисление признаков текстурных изображений

2.1. Метод построения признаков

2.1.1. Восстановление регрессии

2.1.2. Метод простой регрессии

2.1.3. Метод гребневой регрессии

2.2. Экспериментальные исследования текстурных признаков

2.3. Модели искажений

2.3.1. Модель аддитивного стационарного гауссова шума

2.3.2. Модель импульсного шума

2.4. Исследования метода формирования признаков, основанного

на простой регрессии

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

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

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

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

2.5. Исследования метода формирования признаков, основанного

на гребневой регрессии

2.6. Исследования методов формирования признаков на тесте МеаэТех

2.7. Выводы

Раздел 3. Оценка мер сходства текстурных изображений

3.1. Сравнение текстурных изображений

3.1.1. /-дивергенция

3.1.2. Дивергенция Кульбака— Лейблера

3.1.3. Интегральные вероятностные метрики

3.2. Ядра на пространстве текстурных изображений

3.3. Формирование признаков с использованием дискриминантного анализа

3.4. Экспериментальные исследования методов основанных на мерах схожести текстур

3.4.1. Характеристики разделимости классов

3.4.2. Исследование метрики на основе дивергенции Кульба-ка—Лейблера

3.4.3. Исследование расстояния Васерштейна

3.4.4. Исследование метрики Дадли

3.4.5. Исследование ММБ метрики

3.5. Исследование признаков построенных на основе дискриминантного анализа

3.6. Исследование метрик в задаче классификации

3.6.1. Исследование метрики на основе дивергенции Кульба-ка—Лейблера

3.6.2. Исследование расстояния Васерштейна

3.6.3. Исследование метрики Дадли

3.6.4. Исследование ММБ метрики

3.7. Выводы

Раздел 4. Обнаружение локальных текстурных неоднородно-стей

4.1. Постановка задачи выделения неоднородностей

4.2. Выделение текстурных неоднородностей

4.2.1. Квантиль-функция и множество минимального объема

4.2.2. Метод обнаружения новизны

4.3. Экспериментальные исследования метода обнаружения локальных текстурных неоднородностей

4.3.1. Экспериментальные исследования метода обнаружения текстурных неоднородностей

4.3.2. Исследование качества обнаружения локальных неоднородностей натурных изображений при различных значениях параметров алгоритма

4.4. Выводы

Заключение

Литература

Приложение А. Математический аппарат. Методы

А.1. Гильбертовы пространства с воспроизводящим ядром

А.2. Методы классификации

А.2.1. Обзор методов классификации изображений

А.З. Метод опорных векторов для классификации

А.3.1. Оптимальная гиперплоскость для линейно-разделимых

образов

А.3.2. Оптимальная гиперплоскость для неразделимых образов144

А.3.3. Нелинейная разделяющая граница

А.3.4. Выбор параметров и обучение ЯУМ

А.4. Метод опорных векторов для регрессии

Приложение Б. Имитационное моделирование текстурных изображений

Б.1. Имитационное моделирование

Б. 1.1. Метод имитационного моделирования

Б. 1.2. Модифицированный метод имитационного моделирования

Б. 1.3. Имитационное моделирование изображений микроструктуры поверхности материалов с дефектами

Б.2. Экспериментальные исследования имитационного моделирования текстур

Б.2.1. Экспериментальные исследования базового метода

метода

Приложение В. Результаты исследования ММБ метрики в задаче классификации текстурных изображений

Введение диссертации (часть автореферата) на тему «Метод формирования признаков текстурных изображений на основе марковских моделей»

Введение

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

Актуальность темы

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

Для классификации текстурных изображений широко применяется модель изображения как реализации случайного поля, в частности, марковского случайного поля. Большой вклад в развитие этого направления внесли: Р. Харалик, который ввел статистический и структурный подходы к определению текстуры, а также предложил использовать признаки на основе матрицы взаимного распределения вероятности; Дж. Бесаг, Д. Геман, С. Геман, работы которых посвящены разработке методов оценки параметров модели марковских случайных полей; а также М.Хаиндл, А. Джейн, Г. Винклер, С. Ли и Г. Л. Гимельфарб.

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

однозначного подхода к выбору этого параметра.

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

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

Цель и задачи исследований

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

Для достижения этой цели в диссертации решаются следующие задачи:

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

2. исследование информативности коэффициентов регрессии, как признаков текстурных изображений.

3. Оценка мер схожести текстурных изображений и применение этих мер для классификации текстурных изображений.

4. Разработка информационной технологии выделения текстурных неоднородностей на изображениях.

5. Экспериментальные исследования разработанных методов и алгоритмов на натурных и модельных текстурных изображениях.

Методы исследований

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

Научная новизна работы

Научной новизной обладают следующие результаты:

1. Метод формирования признаков на основе вычисления коэффициентов регрессии, который использует априорные данные о типах изображений из обучающего множества. Предложены алгоритмы вычисления признаков на основе простой и гребневой регрессии. Разработана методика выбора параметров и исследования предложенных методов вычисления признаков. Полученные признаки показали улучшение вероятности верной классификации до 12% на тестах коллекции изображений МеаэТех.

2. Информационная технология обнаружения текстурных неоднородностей на основе «обнаружения новизны» по методу опорных векторов. Разработана методика выбора параметров и исследования метода выделения текстурных неоднородностей.

3. Оценка меры схожести текстурных изображений на основе дивергенции Кульбака—Лейблера и интегральных вероятностных метрик.

4. Вид функций ядер скалярного произведения текстурных изображений, основанные на мерах сходства текстурных изображений. Предложенные

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

Практическая ценность работы

заключается в разработке методов и алгоритм классификации текстурных изображений, позволяющих повысить качество классификации на 1 — 12% по сравнению с известными методами за счет вычисления признаков, использующих априорные данные. Предложенные методы и алгоритмы обработки текстурных изображений могут быть использованы в автоматизированных системах дефектоскопии материалов и анализа включений, в системах анализа био-медицинских изображений, а также в других информационных системах обработки текстурных изображений.

Реализация результатов работы

Результаты диссертации использованы при выполнении ряда госбюджетных и хоздоговорных НИР в лаборатории лазерных измерений института систем обработки изображений РАН.

Апробация работы

Основные результаты диссертации докладывались на:

• 8-ой международной конференции «Распознавание образов и анализ изображений: новые информационные технологии» (РОАИ), Россия, Йошкар-Ола, 2007;

• Всероссийской молодежной научной конференции с международным участием «IX Королевские чтения» (Самара, СГАУ, октябрь, 2007)

• 9-ой международной конференции «Распознавание образов и анализ изображений: новые информационные технологии» (РОАИ), Россия, Нижний Новгород, 2008;

• Всероссийской молодежной научной конференции с международным участием «X Королевские чтения», Самара, 2009;

• Научно-технической конференции с международным участием «Перспективные информационные технологии в научных исследованиях, проектировании и обучении», «ПИТ-2010», Самара, 2010;

• 4-ой Международной конференции по распознаванию образов и искусственному интеллекту (Pattern Recognition and Machine Intelligence, PReMI-2011).

Публикации

По теме диссертации опубликовано 12 работ, из них 6 из перечня ведущих рецензируемых научных журналов и изданий ВАК РФ.

В работах [1-4] автору принадлежит идея и численные методы оценивания признаков цветных текстурных изображений с использованием модифицированного метода Харалика. В работе [5] автору принадлежит разработка алгоритмов выделения изображений клеток крови на цифровых изображениях пробы крови. В работе [б] — предложен метод и алгоритм выделения текстурных изображений с использованием метода опорных векторов. Работы [7-12] выполнены автором единолично. В работах [7-10] предложены методы и алгоритмы формирования признаков и имитационного моделирования текстурных изображений на основе модели марковского случайного поля. В работах [11, 12] представлен ряд мер схожести текстурных изображений, а также предложено, как использовать эти меры для построения ядер на пространстве текстурных изображений.

Ниже в тексте диссертации ссылки на работы автора помечены (*).

Структура диссертации

Диссертация состоит из введения, четырех глав, заключения, списка литературы и четырех приложений. Она изложена на 164 страницах машинописного текста (без приложений), содержит 43 рисунков, 46 таблиц, список использованных источников из 122 наименований.

Краткое содержание диссертации

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

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

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

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

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

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

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

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

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

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

На защиту выносятся

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

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

3. Оценка мер схожести текстурных изображений на основе дивергенции Кульбака—Лейблера и интегральных вероятностных метрик.

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

5. Результаты экспериментальных исследований эффективности разработанных методов и алгоритмов.

Заключение диссертации по теме «Теоретические основы информатики», Пластинин, Анатолий Игоревич

Основные результаты диссертационной работы:

• Предложен общий подход к анализу текстурных изображений на основе анализа векторов окрестностей, в соответствии с Марковской моделью изображения.

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

• Предложен метод выделения текстурных неоднородностей на основе метода обнаружения новизны. Показано, что метод выделения текстурных неоднородностей на изображениях с текстурными дефектами.

• Предложен и исследован метод вычисления меры схожести текстурных изображений на основе дивергенции Кульбака—Лейблера и интегральных вероятностных метрик.

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

Заключение

В работе рассматрены задачи анализа текстурных изображений: вычисление признаков и классификация текстурных изображений, обнаружение текстурных неоднородностей.

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

Список литературы диссертационного исследования кандидат технических наук Пластинин, Анатолий Игоревич, 2011 год

Литература

1. Plastinin, A. Color textural analysis of the blood preparation images [Text] / A. Plastinin, A. Kupriyanov, N. Ilyasova // Optical Memory & Neural Networks. - 2008. - Vol. 17. - P. 201-207.

2. Пластинин, А. И. Разработка методов формирования цвето-текстурных признаков для анализа биомедицинских изображений [Текст] / А. И. Пластинин, А. В. Куприянов, Н. Ю. Ильясова // Компьютерная оптика. — 2007. - Т. 31, № 2. - С. 82-85.

3. Plastinin, A. The methods for color-textural parameters estimation of the biomedical diagnostic images [Text] / A. Plastinin, A. Kupriyanov, N. Ilyasova // PRIA-8-2007 Conf. Proc. - Vol. 1.— Yoshkar-Ola : [s. п.], 2007,-October. - P. 355-359.

4. Пластинин, А. И. Разработка методов формирования цветотекстурных признаков для анализа биомедицинских изображений [Текст] / А. И. Пластинин, А. В. Куприянов //IX Королевские чтения, тезисы докладов. — Самара : [б. и.], 2007. - С. 308.

5. The technology of leukocytes determination on blood preparation images [Text] / E. Zhulkova, N. Ilyasova, A. Kupriyanov, A. Plastinin // Optical Memory к Neural Networks. - 2008. - Vol. 17. - P. 152-156.

6. Пластинин, А. И. Обнаружение текстурных неоднородностей на микромасштабных изображениях материалов [Текст] / А. И. Пластинин, А. Г. Храмов, В. А. Сойфер // Компьютерная оптика. — 2011.— Т. 35, № 2.— С. 158-165.

7. Plastinin, A. Markov model based features for color-texture images analysis

[Text] / A. Plastinin, A. Kupriyanov // PRIA-9-2008 Conf. Proc. - Vol. 1.-Nizhni Novgorod : [s. п.], 2008. - P. 118-120.

8. Пластинин, А. И. Модель марковского случайного поля в задачах синтеза и анализа текстурных изображений [Текст] / А. И. Пластинин, А. В. Куприянов // Вестник Самарского государственного аэрокосмического университета имени академика С. П. Королева. — 2008. — Т. 15, № 2. — С. 252-258.

9. Пластинин, А. И. Разработка методов формирования признаков цветных текстурных изображений [Текст] / А. И. Пластинин, А. В. Куприянов // X Королёвские чтения, тезисы докладов. — Самара : [б. и.], 2009. — С. 318.

10. Пластинин, А. И. Построение текстурных признаков на основе регрессионных моделей [Текст] / А. И. Пластинин // ПИТ-2010. — Самара : [б. и.], 2010. - С. 795-799.

11. Plastinin, A. Regression models for texture image analysis [Text] / Ana-toliy Plastinin // PReMI 2011, LNCS 6744. - Springer-Verlag Berlin Heidelberg : [s. п.], 2011.- P. 136-141.

12. Пластинин, А. И. Применение интегральных вероятностных метрик для анализа текстурных изображений [Текст] / А. И. Пластинин // Вестник Самарского государственного аэрокосмического университета имени академика С. П. Королева. - 2011. - Т. 26, № 2. - С. 242-250.

13. Handbook of Texture Analysis [Text] / Ed. by Majid Mirmehdi, Xianghua Xie, Jasjit Suri.— [S. 1.] : Imperial College Press, 2008. — December. — ISBN: 978-1-84816-115-3.

14. Petrou, M. Image Processing: Dealing with Texture [Text] / Maria Petrou, Pedro García-Sevilla. - [S. 1.] : John Wiley к Sons, 2006,- ISBN: 0-470-02628-6.

15. Pietikâinen, M. Texture analysis in machine vision [Text] / M. Pietikâinen. Series in machine perception and artificial intelligence. — [S. 1.] : World Scientific, 2000. - ISBN: 9789810243739.

16. Haralick, R. M. Statistical and structural approaches to texture [Text] / R. M. Haralick // Proceedings of the IEEE.- 1979,- Vol. 67, no. 5.— P. 786-804.— URL: http://ieeexplore.ieee.org/xpls/abs_all.jsp? arnumber=1455597.

17. Haindl, M. Texture synthesis [Text] / M. Haindl // CWI Quarterly. - 1991.-Vol. 4. — P. 305-331.

18. Bennis, C. 2-d macroscopic texture synthesis [Text] / C. Bennis, A. Gagalow-icz // Computer Graphics Forum. - 1989. - Vol. 8. - P. 291-300.

19. Francos, J. M. A unified structural-stochastic model for texture analysis and synthesis [Text] / J. M. Francos, A. Z. Meiri // Proceedings 5th International Conference on Pattern Recognition, Washington, 1988.— [S. 1. : s. n.], 1988. — P. 41-46.

20. D'Astous, F. Texture discrimination based on detailed measures of the power spectrum [Text] / F. D'Astous, M.E. Jernigan // 7ICPR. - Vol. 84. - P. 83-86.

21. Pavlidis, T. Segmentation by texture using correlation [Text] / T. Pavlidis, P.C. Chen // ICPR80. — [S. 1. : s. n.], 1980. - P. 551-553.

22. Gagalowicz, A. Sequential synthesis of natural textures [Text] / André Gaga-lowicz, Song De Ma // Computer Vision, Graphics, and Image Processing. — 1985. - Vol. 30, no. 3. - P. 289-315.

23. Li, S. Z. Markov Random Field Modeling in Image Analysis [Text] /

Stan Z. Li. — 3rd edition.— [S. 1.] : Springer Publishing Company, Incorporated, 2009. - ISBN: 9781848002784.

24. Winkler, G. Image Analysis, Random Fields and Markov Chain Monte Carlo Methods: A Mathematical Introduction (Stochastic Modelling and Applied Probability) [Text] / Gerhard Winkler. — Secaucus, NJ, USA : Springer-Verlag New York, Inc., 2006. - ISBN: 3540442138.

25. Dubes, R. C. Random field models in image analysis [Text] / R. C. Dubes, A. K. Jain // Journal of Applied Statistics.— 1989.— Vol. 16, no. 2,— P. 131-164.

26. Ahuja, N. Mosaic models for textures [Text] / N. Ahuja, A. Rosenfeld // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 1981. — Vol. PA MI 3. - P. 1-10.

27. Haralick, R. M. Textural features for image classification [Text] / R. M. Har-alick, Dinstein, K. Shanmugam // IEEE Transactions on Systems, Man, and Cybernetics. - 1973. - November. - Vol. SMC-3. - P. 610-621.

28. Julesz, B. Textons, the elements of texture perception, and their interactions' [Text] / B. Julesz // Nature. - 1981. - Vol. 290. - P. 91-97.

29. Paget, R. Texture synthesis via a noncausal nonparametric multiscale markov random field [Text] / R. Paget, D. Longstaff // IEEE Transactions on Image Processing. - 1998. - Vol. 7. - P. 925-931.

30. Park, M. Fast content-based image retrieval using quasi-gabor filter and reduction of image feature dimension [Text] / Mira Park, Jesse S. Jin, Laurence S. Wilson // SSIAI '02: Proceedings of the Fifth IEEE Southwest Symposium on Image Analysis and Interpretation. — Washington, DC, USA : IEEE Computer Society, 2002. - P. 178.

31. Gabor filtering of complex hue/saturation images for color texture classification [Text] / Christoph Palm, Daniel Keysers, Thomas M. Lehmann, Klaus Spitzer // International Conference on Computer Vision, Pattern Recognition, and Image Processing. — Atlantic City, NJ : [s. п.], 2000. — February. - P. 45-49.

32. Siggelkow, S. Feature Histograms for Content-Based Image Retrieval [Text] : Ph. D. thesis / S. Siggelkow ; Albert-Ludwigs-Universität Freiburg, Fakultät für Angewandte Wissenschaften, Germany. — [S. 1. : s. п.], 2002. — dec.

33. Pratt, W. К. Digital Image Processing [Text] / William K. Pratt. — 4 edition. — [S. 1.] : Wiley-Interscience, 2007. - February. - ISBN: 0471767778.

34. Tamura, H. Textural features corresponding to visual perception [Text] /

H. Tamura, T. Mori, T. Yamawaki // SMC.- 1978.-June.- Vol. 8.— P. 460-473.

35. Ту, Д. Принципы распознавания образов [Текст] / Дж. Ту, Р. Гонсалес. — Москва : Мир, 1978.

36. Vapnik, V. N. Statistical Learning Theory [Text] / Vladimir N. Vapnik. — [S.

I.] : Wiley-Interscience, 1998. - September. - ISBN: 0471030031.

37. Вапник, В. Восстановление зависимостей по эмпирическим данным [Текст] / В.Н. Вапник, — Москва : Наука. Главная редакция физико-математической литературы, 1979.

38. Wei, L.-Y. Deterministic texture analysis and synthesis using tree structure vector quantization [Text] / Li-Yi Wei // Proceedings of the XII Brazilian Symposium on Computer Graphics and Image Processing. — SIBGRAPI '99. — Washington, DC, USA : IEEE Computer Society, 1999. - P. 207-214.

39. Ashikhmin, M. Synthesizing natural textures [Text] / M. Ashikhmin // The proceedings of 2001 ACM Symposium on Interactive 3D Graphics, Research Triangle Park, NorthCarolina, March, 2001. - [S. 1. : s. п.], 2001. - P. 217-226.

40. Kern, W. PDQ Hematology [Text] / W. Kern. - [S. 1.] : B.C. Decker, 2002.

41. Theml, H. Color Atlas of Hematology, 2nd revised ed [Text] / H. Theml.— [S. 1.] : Thieme, 2004.

42. Osowski, S. Support vector machine for recognition of white blood cells of leukaemia [Text] / S. Osowski, T. Markiewicz // Kernel methods in bioengineering, signal and image processing. — [S. 1.] : IGI Global, 2007.

43. Engler, O. Introduction to texture analysis: macrotexture, microtexture, and orientation mapping [Text] / O. Engler, V. Randle. — [S. 1.] : CRC Press, 2009. - ISBN: 9781420063653.

44. Smith, M. Surface Inspection techniques: Using the Integration of Innovative Machine Vision and Graphical Modelling Techniques [Text] / M.L. Smith. — [S. 1.] : Wiley, 2001.

45. Сканирующая электронная микроскопия и рентгеноспектральный микроанализ в примерах практического применения [Текст] / М. М. Криштал, И. С. Ясников, В. И. Филатов [и др.]. - М. : Техносфера, 2009. 206 с.

46. Haindl, М. Texture defect detection [Text] / Michal Haindl, Jiri Grim, Stanislav Mikes // Computer Analysis of Images and Patterns / Ed. by Walter Kropatsch, Martin Kampel, Allan Hanbury. — [S. 1.] : Springer Berlin / Heidelberg, 2007. — Vol. 4673 of Lecture Notes in Computer Science. — P. 987-994,- URL: http://dx.doi.org/10.1007/978-3-540-74272-2_ 122.

47. Sobral, J. L. Optimised filters for texture defect detection [Text] / J. L. Sobral // IEEE International Conference on Image Processing. — [S. 1. : s. п.], 2005. — P. 565-568.

48. Iivarinen, J. Surface defect detection with histogram-based texture features [Text] / Jukka Iivarinen // Proceedings of SPIE 4197,- [S. 1. : s. п.], 2000,-P. 140-145.

49. Chetverikov, D. Textures and structural defects [Text] / Dmitry Chetverikov, Krisztian Gede // Computer Analysis of Images and Patterns / Ed. by Gerald Sommer, Kostas Daniilidis, Josef Pauli. — [S. 1.] : Springer Berlin / Heidelberg, 1997. — Vol. 1296 of Lecture Notes in Computer Science. — P. 167-174. — URL: http: //dx. doi . org/10.1007/3-540-63460-6_114.

50. Деммель, Д. Вычислительная линейная алгебра. Теория и приложения [Текст] / Дж. Деммель. — Москва : Мир, 2001.

51. Golub, G. Matrix Computations, 3rd ed. [Text] / G.H. Golub, C.F. van Loan. — [S. 1.] : The Johns Hopkins University Press, 1996.

52. Haykin, S. Neural Networks: A Comprehensive Foundation [Text] / Simon Haykin. — 2nd edition. — Upper Saddle River, NJ, USA : Prentice Hall PTR, 1998.- ISBN: 0132733501.

53. Hastie, T. The elements of statistical learning: data mining, inference and prediction [Text] / Trevor Hastie, Robert Tibshirani, Jerome Friedman. — 2 edition. — [S. 1.] : Springer, 2009. — URL: http://www-stat.stanford.edu/ ~tibs/ElemStatLearn/.

54. Scholkopf, B. A generalized representer theorem [Text] / Bernhard Scholkopf, Ralf Herbrich, Alex J. Smola // Proceedings of the 14th Annual Conference on Computational Learning Theory and and 5th European Conference on

Computational Learning Theory. - COLT 'Ol/EuroCOLT '01. - London, UK : Springer-Verlag, 2001. - P. 416-426.

55. Scholkopf, B. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond [Text] / Bernhard Scholkopf, Alexander J. Smola. — Cambridge, MA, USA : MIT Press, 2001.- ISBN: 0262194759.

56. Engel, Y. The kernel recursive least squares algorithm [Text] / Yaakov Engel, Shie Mannor, Ron Meir // IEEE Transactions on Signal Processing. — 2003. — Vol. 52. - P. 2275-2285.

57. Texturing and Modeling: A Procedural Approach [Text] / David S. Ebert, F. Kenton Musgrave, Darwyn Peachey [et al.]. — 3rd edition. — San Francisco, CA, USA : Morgan Kaufmann Publishers Inc., 2002,- ISBN: 1558608486.

58. Huang, T. S. Two-Dimensional Digital Signal Processing II: Transforms and Median Filters [Text] / Thomas S. Huang. — Secaucus, NJ, USA : Springer-Verlag New York, Inc., 1981. - ISBN: 0387103597.

59. Ohanian, P. Performance evaluation for four classes of textural features [Text] / P.P. Ohanian, R.C. Dubes // Pattern recognition. - 1992. - Vol. 25, no. 8.— P. 819-833.

60. Smith, G. Meastex image texture database and test suite [Text] / G. Smith // URL: http://www.cssip.uq.edu.au/meastex/meastex.html,— 1997.

61. Ali, S. M. A General Class of Coefficients of Divergence of One Distribution from Another [Text] / S. M. Ali, S. D. Silvey // Journal of the Royal Statistical Society. Series B (Methodological). - 1966. - Vol. 28, no. 1. - P. 131-142. -URL: http: //www. jstor. org/stable/2984279.

62. Reid, M. D. Information, divergence and risk for binary experiments [Text] / Mark D. Reid, Robert C. Williamson // Journal of Machine Learning Research. - 2011. - March. - Vol. 12. - R 731-817.

63. Wang, Q. A nearest-neighbor approach to estimating divergence between continuous random vectors [Text] / Q. Wang, S. Kulkarni, S. Verdu // IEEE Int. Symp. Information Theory. — Seattle, USA : [s. n.], 2006.

64. Muller, A. Integral probability metrics and their generating classes of functions [Text] / A Muller // Advances in Applied Probability. — [S. 1. : s. n.], 1997. — P. 429-443.

65. Rachev, S. T. Probability Metrics and the Stability of Stochastic Models [Text] / S. T. Rachev. Wiley Classics Library Edition. — Chichester, New York : John Wiley & Sons, 1991.

66. Zolotarev, V. M. Probability metrics [Text] / V. M. Zolotarev // Theory of Probability and its Applications. - 1984. - Vol. 38, no. 2. - P. 278-302.

67. Dudley, R. Probabilities and metrics [Text] / R.M. Dudley. — [S. 1.] : Aarhus universitet, Matematisk institut, 1976.

68. Non-parametric estimation of integral probability metrics [Text] / B.K. Sripe-rumbudur, K. Fukumizu, A. Gretton [et al.] // Information Theory Proceedings (ISIT), 2010 IEEE International Symposium on / IEEE. - [S. 1. : s. n.].-P. 1428-1432.

69. Moreno, P. J. A Kullback-Leibler divergence based kernel for SVM classification in multimedia applications [Text] / Pedro J. Moreno, Purdy Ho, Nuno Vasconcelos // NIPS / Ed. by Sebastian Thrun, Lawrence K. Saul, Bernhard Schölkopf [et al.]. - [S. 1.] : MIT Press, 2003.

70. Fuglede, B. Jensen-Shannon divergence and Hilbert space embedding [Text] / B. Fuglede, F. Tops0e // IEEE International Symposium on Information Theory. - [S. 1. : s. n.], 2004. - P. 31-36.

71. Haasdonk, B. Learning with distance substitution kernels [Text] / Bernard Haasdonk, Claus Bahlmann // Pattern Recognition / Ed. by Carl Edward Rasmussen, Heinrich H. Bulthoff, Bernhard Scholkopf, Martin A. Giese. — [S. 1.] : Springer Berlin / Heidelberg, 2004. — Vol. 3175 of Lecture Notes in Computer Science. - P. 220-227.

72. Pekalska, E. A generalized kernel approach to dissimilarity-based classification [Text] / Elzbieta Pekalska, Pavel Paclik, Robert P. W. Duin // J. Mach. Learn. Res. - 2002. - March. - Vol. 2. - P. 175-211.

73. Haasdonk, B. Feature space interpretation of svms with indefinite kernels [Text] / Bernard Haasdonk // IEEE Trans. Pattern Anal. Mach. Intell.— 2005. - April. - Vol. 27. - P. 482-492.

74. Abe, S. Support Vector Machines for Pattern Classification [Text] / Shi-geo Abe. — 2nd edition. — [S. 1.] : Springer Publishing Company, Incorporated, 2010. - ISBN: 1849960976, 9781849960977.

75. Fisher discriminant analysis with kernels [Text] / S. Mika, G. Ratsch, J. Weston [et al.] // Neural Networks for Signal Processing IX: Proceedings of the 1999 IEEE Signal Processing Society Workshop (Cat. No.98TH8468). - [S. 1.] : IEEE, 1999,- P. 41-48,- URL: http://dx.doi.org/10.1109/NNSP.1999. 788121.

76. Fukunaga, K. Introduction to statistical pattern recognition (2nd ed.) [Text] / Keinosuke Fukunaga. — San Diego, CA, USA : Academic Press Professional, Inc., 1990,- ISBN: 0-12-269851-7.

77. Estimating the support of a high-dimensional distribution [Text] / Bernhard Schölkopf, John C. Piatt, John C. Shawe-Taylor [et al.] // Neural Corn-put. - 2001.-July. - Vol. 13.-P. 1443-1471,-URL: http://portal.acm. org/citation.cfm?id=1119748.1119749.

78. Markou, M. Novelty detection: a review-part 1: statistical approaches [Text] / Markos Markou, Sameer Singh // Signal Processing. — 2003. — Vol. 83, no. 12. — P. 2481 - 2497.— URL: http://www.sciencedirect.com/science/ article/B6V18-49HMF2J-3/2/c31ee7bc4b3aabf21044a0el78c4305f.

79. Markou, M. Novelty detection: a review-part 2:: neural network based approaches [Text] / Markos Markou, Sameer Singh // Signal Processing.- 2003,- Vol. 83, no. 12,- P. 2499 - 2521,- URL: http://www.sciencedirect.com/science/article/B6V18-49HMF2J-2/ 2/291a58d8baa505709fIca3a86ad8316b.

80. Einmahl, J. H. J. Generalized Quantile Process [Text] / J. H. J. Einmahl, D. M. Mason // Ann. Stat. - 1992. - June. - Vol. 20. - P. 1062-1078.

81. Nolan, D. The excess mass ellipsoids [Text] / D. Nolan // Journal of Multivariate Analysis. - 1991. - Vol. 39. - P. 348-371.

82. Tsybakov, A. B. On nonparametric estimation of density level sets [Text] / A. B. Tsybakov // The Annals of Statistics.- 1997,- Vol. 25, no. 3.-P. 948-969.

83. Polonik, W. Concentration and goodness-of-fit in higher dimensions: Asymptotically distribution-free methods [Text] / W. Polonik // The Annals of Statistics. - 1999. - Vol. 27. - P. 1210-1229.

84. Brodatz, P. Textures: A Photographic Album for Artists and Designers [Text] / P. Brodatz. - [S. 1.] : New York, 1966.

85. Aronszajn, N. Theory of reproducing kernels [Text] / N. Aronszajn // Transactions of the American Mathematical Society. — 1950. — Vol. 68.

86. Berg, C. Harmonic Analysis on Semigroups [Text] / C. Berg, J. P. R. Christensen, P. Ressel. — Berlin : Springer, 1984.

87. Benyamini, Y. Geometric nonlinear functional analysis [Text] / Y. Benyamini, J. Lindenstrauss. - [S. 1.] : AMS, 2000. - ISBN: 0821808354.

88. Chapelle, O. Support vector machines for histogram-based image classification [Text] / O. Chapelle, P. Haffner, V. N. Vapnik // Neural Networks, IEEE Transactions on. - 1999,- Vol. 10, no. 5,- P. 1055-1064,- URL: http: //dx.doi.org/10.1109/72.788646.

89. Вапник, В. Теория распознавания образов (статистические проблемы обучения) [Текст] / В.Н. Вапник, А.Я. Червоненкис. — Москва : Наука. Главная редакция физико-математической литературы, 1974.

90. Vapnik, Vladimir. The Nature of Statistical Learning Theory (Information Science and Statistics) [Text] / Vapnik, Vladimir. — 2nd edition. — [S. 1.] : Springer, 1999. - November. - ISBN: 0387987800.

91. Aizerman, A. Theoretical foundations of the potential function method in pattern recognition learning [Text] / A. Aizerman, E. M. Braverman, L. I. Ro-zoner // Automation and Remote Control. - 1964. - Vol. 25. - P. 821-837.

92. Platt, J. C. Fast training of support vector machines using sequential minimal optimization [Text] / John C. Piatt // Advances in kernel methods. — Cambridge, MA, USA : MIT Press, 1999,- P. 185-208. - ISBN: 0-262-19416-3,-URL: http: //portal. acm. org/citation. cfm?id=299094.299105.

93. A practical guide to support vector classification [Text] : Rep. / Department of Computer Science, National Taiwan University ; Executor: Chih-Wei Hsu, Chih-Chung Chang, Chih-Jen Lin : 2003.— URL: http://www.csie.ntu. edu.tw/~cjlin/papers.html.

94. Wei, L.-Y. Fast texture synthesis using tree-structured vector quantization [Text] / Li-Yi Wei, Marc Levoy // Proceedings of the 27th annual conference on Computer graphics and interactive techniques. — SIGGRAPH '00. — New York, NY, USA : ACM Press/Addison-Wesley Publishing Co., 2000. - P. 479-488. -URL: http: //dx. doi . org/10.1145/344779 .345009.

95. Ruderman, D. L. Statistics of cone responses to natural images: Implications for visual coding [Text] / Daniel L. Ruderman, Thomas W. Cronin, Chuan-Chin Chiao // Journal of the Optical Society of America A. — 1998. — Vol. 15. - P. 2036-2045.

Приложение А Математический аппарат. Методы.

А.1. Гильбертовы пространства с воспроизводящим ядром

Ниже представлены основные положения о гильбертовых пространствах с воспроизводящим ядром [85, 86]. Мы будем рассматривать класс функций (ядер) к, которые соответствуют скалярному произведению в некотором пространстве !К согласно отображению Ф:

Будем рассматривать только действительнозначимые ядра к: X х X —У М.

Определение А. 1.1 (Положительно определенное ядро). Пусть X непустое множество. Будем называть функцию к: X х X —> Ж. положительно определенным ядром, если

для любых т Е Х\,..., хт Е X и любых ... ,ст Е М.

Определение А. 1.2 (Отрицательно определенное ядро). Пусть X непустое множество. Будем называть функцию к: X х X —> К. отрицательно определенным ядром, если

Ф-.Х-+Ж

то есть

к(х,х') = (Ф(ж),Ф(х/)).

т

т

для любых т > 2, ... ,хт Е X и любых ... ,ст Е К, таких что

Т2.1« = о-

Далее, всякий раз, когда будет использоваться термин ядро, подразумевается положительно определенное ядро (если не оговорено обратное).

Следующие теоремы показывают связь между отрицательно-определенными и положительно-определенными ядрами.

Теорема А.1.1. Пусть X непустое множество и^: Хх1-у1 является ядром. Тогда ф является отрицательно определенным тогда и только тогда, когда ехр(—£-г/>) является положительно определенным ядром для любого Ь > 0.

Теорема А.1.2. Пусть ф: ХхХ —> М является отрицательно определенным ядром, которое удовлетворяет условию ф(х, х) > 0, тогда фа при 0 < а < 1 и + ф) также являются отрицательно определенными.

Теорема А.1.3. Пусть ф: X х X —)• М+ является ядром, тогда ф является отрицательно определенным тогда и только тогда, когда {Ь + ф)~1 при £ > 0 является положительно определенным.

Доказательство теорем А.1.1, А.1.2 и А.1.3 может быть найдено в [86] в главе 3.

Теорема А.1.4. Пусть (X,¡л) метрическое пространство, где ¡л: X х X —»• — метрика. Тогда ¡л2 является отрицательно определенным ядром, тогда и только тогда когда существует Гильбертово пространство Ж и отображение Ф: X —>• Ж, такое что

[л{х,х') = ||Ф(я) -Ф(я')||, Ух, у Е X.

Доказательство. Доказательство следует из факта /л(х, х) — 0 (из аксиом метрики), и применением теоремы 8.5 из [87]. □

Предположим что к действительное положительно определенное ядро, и X непустое множество. Определим отображение из X в пространство функций отображающих X в Ж, Мх = {/: X М}:

Ф: X ->• Е*

х х)

Здесь Ф(ж) обозначает функцию, которая ставит в соответствие значение к(х,х') для х' Е X, т.е. Ф(а?)(-) = к(-,х).

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

Для того чтобы построить пространство связанное с Ф необходимо выполнить следующее:

1. определить векторное пространство над образом отображения Ф;

2. определить скалярное произведение;

3. доказать что скалярное произведение удовлетворяет условию:

к(х, х') = (Ф(ж),Ф(У))

Покажем, как получить предгильбертово пространство, содержащие все образы Ф. Сперва, определим векторное пространство. Возьмем линейную комбинацию вида:

то г=1

где т Е М, а^ Е М Х\,..., хт Е X. Скалярное произведение между / и другой функцией

то' ¿=1

определяется как

т т' г=1 ¿=1

Отметим, что выражение не зависит от конкретного разложения функций / и д.

т'

</,£) = Е^Ж)

¿=1

т г=1

Также очевидно, что (•,•) симметрично, т.е. (/,д) = (д, /). Более того оно положительно определено, т. к. из положительной определенности к следует, что для любой функции / справедливо:

т

(/, /) = а^к(хг, х^> О г,3 =1

Последнее выражение также показывает, что (•, •) само по себе является положительно определенным ядром, заданным на пространстве функций введенном выше.

Также следует отметить, что для всех функций выполнено воспроизводящее свойство:

/> = /(*) (А.З)

в частности

(к(-,х),к(-,х')) = к(х,х') (А.4)

Поэтому такие ядра также называются воспроизводящими.

Также видно, что |/(ж)|2 = |(/с(-, ж),/)| < к(х, х)- (/,/), откуда из (/,/> = О следует / = 0. Из перечисленных выше свойств следует, что (/, /) = 0 является скалярным произведением.

Из приведенных выше рассуждений видно, что любое положительно определенное ядро, может рассматриваться как скалярное произведение в другом пространстве, воспроизводящее свойство ядра может быть представлено как: (Ф(ж), = к(х,х'). Т.о. предгильбертово пространство, построен-

ное таким образом, является одним из возможных признаковых пространств, ассоциированных с ядром.

Выше, мы сперва определили функцию ядра и затем построили пространство, связанное с ядром. Однако можно сделать обратное. Пусть задано отображение Ф из X в пространство со скалярным произведением, в таком случае мы получим положительно определенное ядро: к(х,х') = (Ф(ж), Ф(ж')).

Пусть дано предгильбертово пространство функций (А.1) со скалярным произведением (А.2). Чтобы получить гильбертово пространство необходимо пополнить его по номере, соответствующей скалярному произведению: ||/|| = л/(/, /), т. е. необходимо добавить предельные точки последовательностей, которые сходятся по этой норме.

Исходя из свойств (А.З) и (А.4) такое пространство обычно называют гильбертовым пространством со скалярным произведением.

Определение А. 1.3 (Гильбертово пространство с воспроизводящим ядром (ЯКН8)). Пусть X непустое множество и "К гильбертово пространство функций f: X Ж. Тогда Л называется гильбертовым пространством с воспроизводящим ядром, оснащенным скалярным произведением (•, •) (и нормой ||/|| = у/(/, /}), если существует функция к : ХхХ —>■ К. обладающая следующими свойствами:

1. к обладает воспроизводящим свойством

(/, ад> =/Сг)у/е Я

2. к покрывает "К, т. е. *Н = 8рап{^(гг, -)|х Е X} где X обозначает замыкание множества X.

Следует отметить, что 1ЖН8 полностью определятся функцией к. Рассмотрим несколько ядер для X С К:

• Полиномиальное ядро

к(х,х') = {х,х')й (А.5)

• Гауссовское ядро

к(х, х') = ехр(-7||ж - х'\\2), 7 > 0 (А.6)

• Сигмоидальное ядро

к(х, х') = х') + 0), к > 0, $ < 0 (А.7)

Следует отметить, что сигмоидальное ядро (А.7) не является положительно определенным.

А.2. Методы классификации

А.2.1. Обзор методов классификации изображений

Классификация по К ближайшим соседям

Алгоритм классификации по К ближайшим соседям является одним из простейших среди методов машинного обучения. Суть метода заключается в том, что имеется некоторый набор объектов, принадлежность которых к одному из классов известна. Затем выбираются к ближайших объектов заданного образа. После чего подсчитывается число объектов каждого класса. Пусть к\, . .., км — число объектов, принадлежащих соответственно классам С2, ■ ■ ■, См- Тогда решающее правило будет иметь вид: кг = тах{А;1,..., км} х Е С^.

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

Линейные классификаторы

Наиболее простым видом классификатора является линейный классификатор, т. е. классификатор, который использует линейную дискриминантную функцию. Классификатор имеет вид:

Задача синтеза классификатора состоит в том, чтобы по заданному обучаю-

Это выражение представляет собой линейную разделяющую функцию в функциональном пространстве, где г переменных И{(х) заменяют п переменных х в исходном пространстве.

Следует отметить, что любой классификатор для двух классов, можно использовать в задаче классификации большего числа классов М. Для этого строятся М(М — 1)/2 классификаторов д^(х) = которые

попарно разделяют заданные классы, причем д^(х) = —д^{х). Тогда вектор х будет отнесен к г-му классу, если дц(х) > 0,..., дгм{х) > 0.

Существует несколько методов построения линейных классификаторов, такие как методы стохастической аппроксимации (процедура Робинсона-Монро), персептрон Розенблата (в случае линейной разделимости) и т.д. Однако

щему множеству определить вектор и>т и порог Ь.

Обобщенная линейная разделяющая функция имеет вид:

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

А.З. Метод опорных векторов для классификации

Этот метод хорошо себя зарекомендовал во многих прикладных задачах, например, распознавании изображений, см. в частности [88].

А.3.1. Оптимальная гиперплоскость для линейно-разделимых образов

Классификатор SVM, основан на идее построения оптимальной разделяющей гиперплоскости, которая была предложена Вапником и Червоненкисом [37, 89].

Пусть задано линейное пространство со скалярным произведением IX, и множество векторов образов xi,..., хт Е IX. Любая гипперплоскость может быть представлена в виде

{х £%\{w,x) +b = 0},w еХ,ЬеМ.

Здесь w — это вектор ортогональный гиперплоскости. Разделяющая гиперплоскость называется оптимальной, если расстояние от нее до ближайшей точки обучающего набора данных максимально.

На рисунке А.1 показан пример расположения оптимальной гиперплоскости в двумерном пространстве признаков.

Рассмотрим множество примеров: (х\,yi),..., (хт, ym),Xi ElX, Е {±1}. Также предполагается, что множество содержит хотя бы один положительный и один отрицательный элемент Необходимо построить функцию

fw,b(x) = sgn{{w,x) + b)

иитх + Ь = +1

Рис. А.1. Расположение оптимальной гиперплоскости для линейно разделимых образов

которая удовлетворяет условию = У%- Такая гиперплоскость суще-

ствует в случае линейно разделимых образов (неразделимый случай будет рассмотрен ниже). Для канонической гиперплоскости будет выполнено: Уг^х^и) + Ь) > 1.

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

Тогда для определения оптимальной гиперплоскости необходимо решить следующую задачу условной минимизации:

(х, ъи) + Ь > 0 для <1{ = +1

(ж, ш) + Ь < 0 для ¿1 = —1

1

2

(А.8)

—»■ тт

Уг ((Х4,ги) + Ь) > 1

(А.9)

Это прямая задача оптимизации.

Однако эту задачу решают в терминах двойственной задачи, которая получается применением теоремы Куна—Таккера.

т ^ т т

W(a) = агада^Жг, Xj) max (А.10)

г=1 i=1 j=1

при следующих ограничениях:

гп

У^ «¿2/» = О

г=1

«г > О

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

Решающая функция может быть представлена в виде:

f{x) = Sgn Xi) + fej . (А.11)

Вектора Xi, для которых в решении оц > 0 называются опорными векторами, для таких векторов выполнено yi((xi,w) + b) = 1, т.е. они лежат непосредственно на границе класса.

По оптимальным значениям оц можно вычислить оптимальное значение порога b:

т

Ь = Уг -^2yiOti{Xi,Xj)

г=1

для всех точек с щ > 0, т.е. опорных векторов.

А.3.2. Оптимальная гиперплоскость для неразделимых образов

Рассмотрим случай неразделимых классов [90]. При таком наборе данных обучения невозможно построить разделяющую гиперплоскость, полностью исключающую ошибки классификации. Тем не менее, возможно построить оптимальную гиперплоскость, которая минимизирует вероятность таких ошибок

на множестве обучающих примеров. Для того что бы допустить возможность нарушения условия (А.9) вводятся ослабляющие переменные

6 > О- (А.12)

в результате получим ослабленные условия (соответствующие (А.9))

yi({xi,w) + b) >1-6 (А.13)

Для того что бы исключить возможность тривиального решения, когда все переменные ^ принимают большие значения, необходимо штрафовать их в целевой функции (А.8). Таким образом, получим следующую задачу (так называемый C-SV классификатор):

1 С т

t(w) = -INI2 + — УЧ» min (А. 14)

v ' 2 й 11 m^ weKfiem v '

i=1

при условиях (А. 12) и (А. 13). Здесь С > 0 — задаваемый пользователем параметр.

Так же как в линейно разделимом случае, решение может быть записано

как:

т

W — агУгХг- (А. 15)

г=1

Коэффициенты щ могут быть получены решением следующей задачи квадратичного программирования:

т ^ т т

W(a) = ai - 2 S S агазУгУзк(хи xi) (А-16)

i=1 i= 1 j—1

при следующих ограничениях:

О < а{ < — (А.17)

т

J2aiVi = 0 (А. 18)

i= 1

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

А.3.3. Нелинейная разделяющая граница

Метод построения оптимальной гиперплоскости можно использовать в случае нелинейной разделимости классов [90]. Следует отметить, что единственное предположение об исходном пространстве образов, которое использовалось в предыдущем разделе, это требование наличия скалярного произведения. Тем более нет никакой необходимости считать вектора х^ принадлежащими исходному пространству признаков. Т.е. можно считать, что ж^Хи существует отображение Ф: X —> "К. Следовательно решение (А. 10) требует вычисления (Ф(ж), Ф(ж')).

Исходя из представленного в разделе А.1 способа представления ядра скалярного произведения, мы можем эффективно вычислять скалярное произведение, как (Ф(ж), Ф(а/)} = к{х,х!). Следовательно решающая функция может записана как

Впервые переход к ядру был описан в [91].

На рисунке А.2 представлена архитектура машины опорных векторов.

А.3.4. Выбор параметров и обучение SVM

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

В работе реализован алгоритм SMO (Sequential Minimal Optimization) [92]. Данный алгоритм разбивает исходную задачу КП большой размерности

(А.19)

У

Рис. А.2. Архитектура БУМ

на последовательность небольших задач КП. Эти небольшие задачи решаются аналитически, что не требует таких временных затрат, какие требуются на численное решение задачи КП.

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

проверка позволяет избежать проблемы переобучения классификатора.

Перекрестная проверка методом ./^-разбиений состоит из следующих этапов:

1. разделение обучающего множества на К подмножеств одинакового размера;

2. последовательно каждое подмножество проверяется классификатором, обученным на оставшихся К — 1 подмножествах.

3. усреднение результатов.

Для поиска оптимальных параметров, необходимо для каждой пары (С, 7) оценить значение перекрестной проверки. Одним из самых простых подходов к решению задачи поиска оптимальных параметров является Спс1-поиск, который заключается в последовательном переборе возможных пар значений. Исследования показывают [93], что на практике хорошие результаты дают следующие последовательности значений: С = 2~5, 2~3,... , 215 и 7 = 2~15,2~13,..., 23. На рисунке А.З показан пример значений при Спс1-поис-ке.

А.4. Метод опорных векторов для регрессии

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

В этом случае используется так называемая е-нечувствительная функция потерь

Iу - f(x)\£ = тах{0, |у - ¡(х)\ - е}, (А.20)

О 4967361 0 5664757 06401153 0 711S55 0 7836946

Рис. А.З. Grid-поиск

которая не штрафует ошибки меньше некоторого заданного априори порога £ > 0.

Метод опорных векторов для регрессии с такой функцией потерь далее будем обозначать как c-SVR (Support Vector Regression). Будем искать функцию вида:

f(x) = (ик х) + 6, w, х £ Ь G М

по заданному множеству {х\, г/])...., {хтп. ут) Е х Е. Для решения этой задачи будем минимизировать следующий функционал риска:

+ С ■ Rlmp[f] (А.21)

где

т г=I

оценка б-иечувствителыюй ошибки, и С константа, которая определяет соотношение между штрафом сложности решения ||и>||2 и эмпирическим риском.

Минимизация (А.21) эквивалентна следующей задаче условной минимизации:

1 ^ т

= + min , (А.23)

г=1

при условии

((ги,Хг) + Ь) - г/г < е + Сг

-((«;, жг)+Ь) <б + е* 6>0

Откуда двойственная задача имеет вид:

^ т mm

-- min (А.24)

г,,7=1 г=1 г=1

при условии

т

~ ai ) = 0

г=1

С

0 < oij, ск?* < — т