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

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Введение

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

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

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

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

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

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

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

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

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

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

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

1.1 Описание предметной области

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

Введение в палинологию

Палинология - это междисциплинарная наука, являющаяся частью ботаники, систематики, геологии, археологии, медицины и других отраслей, и связанна с изучением спор и пыльцевых зерен растений их рассеивания и применения. Палинология как наука возникла в 30гг. ХIX столетия. Принято считать, что термин «палинология» ввели в литературу Х.Х. Хайд и Д.А. Вильямс в своих работах в 1944 году.

Разделы палинологии:

1. Палиноморфология изучает морфологическое строение пыльцевых зёрен и спор.

2. Аэропалинология изучает состав и закономерности формирования пыльцевого дождя.

3. Мелиссопалинология (мелиттопалинология, апипалинология) изучает пыльцевые зерна медоносов.

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

5. Археологическая палинология занимается решением вопросов палеоэкологии человека в древности и средневековье.

6. Криминалистическая (судебная) палинология занимается изучением пыльцевых зерен и других палиноморфов для описания и изучения места преступления.

7. Экологическая палинология является молодой наукой, которая изучает экологию и окружающую среду планеты в прошлом и настоящем.

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

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

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

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

Оболочка пыльцевого зерна состоит из двух базовых слоев - экзины и интины (рис. 1.1).



Рисунок 1.1. Строение пыльцевого зерна

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

Экзина (см. рис. 1.1) - это внешний слой оболочки пыльцевого зерна. Благодаря основному ее компоненту - спорополленину, экзина характеризуется необычной стойкостью: в отличии от интины она не растворяется в кислотах и щелочах, выдерживает температуру до 100 градусов по Цельсию и сохраняется миллионы лет в геологических отложениях.

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

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

Далее рассмотрим этапы анализа пыльцевых зерен: сбор, обработку и распознавание.

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

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

Последний этап - распознавание (рис. 1.4). Эксперт самостоятельно определяет род и вид растения после чего вносит результаты в компьютер сам или с помощью помощника. Для определения таксономической принадлежности пыльцы и спор эксперт пользуется определителями и атласами, что занимает немало времени. На данном этапе есть возможность автоматизировать процесс распознавания.



Рисунок 1.2. Сбор пыльцевых зерен

Рисунок 1.3. Обработка и микроскопирование пыльцевых зерен

Рисунок 1.4. Распознавание пыльцевых зерен

1.2 Постановка задачи, описание бизнес-процессов и требований к системе

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

Математическая формулировка задачи распознавания следующая: пусть X -- пространство объектов (в данной случае, изображений), Y -- классы (в данном случае, вида). Дана обучающая выборка: (x1,y1) … (xm,ym), где xi принадлежит X, yi принадлежит Y и i принимает значения из интервала [1; m]. Требуется построить функцию F: X > Y (распознаватель), сопоставляющий класс Y произвольному объекту X.

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

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

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

2. Управление наборами данных (добавление, удаление, изменение, сохранение, загрузка).

3. Обучение системы.

a. Разбиение загруженных изображений на классы.

b. Предобработка изображений.

c. Обучение.

4. Распознавание:

a. Предобработка изображения пыльцевого зерна.

b. Отнесение распознаваемого изображения к одному из классов с использованием алгоритма голосования.

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

Для достижения поставленной задачи необходимо будет автоматизировать процедуру распознавания пыльцевых зерен (модель «AS-IS» см. рис. 1.5). Данный процесс выполняет эксперт в лаборатории путем микроскопического анализа предметных стекол, после чего сам, либо с помощью помощника заносит сделанные выводы в компьютер.



Рисунок 1.5. Процедура распознавания пыльцевых зерен на модели «AS-IS»

После автоматизации процедура распознавания будет включать в себя три бизнес-процесса: обучение системы, распознавание пыльцевых зерен и формирование отчета (модель «TO-BE» см. рис. 1.6 и 1.7). Не смотря на увеличение количества бизнес-процессов количество необходимых затрат значительно снижается. Причем процесс обучения системы будет выполнятся единожды.

Рисунок 1.6. Бизнес-процесс «Обучение системы» на модели «TO-BE»



Рисунок 1.7. Бизнес-процессы «Распознавание пыльцевых зерен» и «Формирование отчета» на модели «TO-BE»

изображение пользовательский распознавание программный

Бизнес-процесс «Обучение системы» будет выполняться пользователем с помощью системы (см. табл. 1.1). Сначала пользователю необходимо загрузить обучающий набор данных изображений и разбить его по классам. После чего программа выполнит обучение и будет готова для выполнения своей основной функции - распознавание пыльцевых зерен.

Бизнес-процесс «Распознавание пыльцевых зерен» выполняется пользователем с помощью системы (см. табл. 1.2). Для выполнения распознавания пользователю необходимо загрузить изображение в программу. После чего программа выполнить обработку изображения и классификацию, по завершению этапа распознавания программа перейдет к бизнес-процессу «Формирование отчета» (см. табл. 1.3), где предоставит результаты в таблице, которые пользователь может выгрузить в Excel.

Таблица 1.1. Операции бизнес-процесса «Обучение программы»

№	Операция	Исполнитель	Входящие данные	Исходящие данные
1	Загрузка обучающего множества изображений пыльцевых зерен	Пользователь, программа	Изображения пыльцевых зерен	Сообщение об успешной загрузке изображений
2	Разбиение на классы	Пользователь, система	Название классов введенных пользователем или извлеченные из имен файлов изображений	-
3	Обучение программы	Программа	Изображения добавленные пользователем и разбитые по классам	Сообщение об успешном выполнении обучения

Таблица 1.2. Операции бизнес-процесса «Распознавание пыльцевых зерен»

№	Операция	Исполнитель	Входящие данные	Исходящие данные
1	Загрузка изображений пыльцевых зерен	Пользователь, программа	Изображения пыльцевых зерен	Сообщение об успешной загрузке изображений
2	Предобработка изображений	Программа	Изображения загруженные пользователем	-
3	Классификация	Программа	Изображения загруженные пользователем	Результаты

Таблица 1.3. Операции бизнес-процесса «Формирование отчета»

№	Операция	Исполнитель	Входящие данные	Исходящие данные
1	Формирование отчета	Программа	Результаты этапа классификации	Результаты сформированные в таблице
2	Экспорт отчета в Excel	Программа	Результаты сформированные в таблице	Отчет в Excel

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

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

2. Управление наборами данных (добавление, удаление, изменение, сохранение, загрузка).

3. Обучение программы на обучающем наборе данных:

a. Разбиение загруженных изображений на классы.

b. Предобработка изображений.

c. Обучение.

4. Распознавание:

a. Предобработка изображений.

b. Отнесение распознаваемого изображения к одному из классов с использованием алгоритма голосования.

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

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

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

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

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

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

Требования к безопасности. Требования к безопасности не предъявляются.

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

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

Интервал загрузки одного изображения не должен превышать 2 секунды. Интервал распознавания изображения (предобработки изображения и классификация) не должен превышать 10-20 секунд. Интервал обучения на 100 изображениях не должен превышать 10-15 минут.

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

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

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

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

Настоящая работа была выполнена по заказу ученых-биологов ПГНИУ. Они ведут работы по выявлению периода пыления растений-аллергенов. Это необходимо для информирования аллергиков, страдающих поллинозом и бронхиальной астмой. Вторая задача, которая решается биологами - определение качества меда. На текущий момент времени распознавание пыльцевых зерен не автоматизировано, а существующие зарубежные разработки недоступны.

1.3 Обзор наиболее значимых решений распознавания пыльцевых зерен

В данном обзоре рассмотрим работы следующих авторов:

1. Н.Е. Ханжина и Е.Б. Замятина.

2. M. Chica.

3. C. Riley.

4. F. Chung.

5. R. Rendondo и V. Marcos.

Краткий обзор наиболее значимых решений представлен в табл. 1.4.

В своей работе Н.Е. Ханжина и Е.Б. Замятина разработали систему распознавания пыльцевых зерен по фотографиям сделанных под микроскопом. Предварительная обработка изображений выполняется с помощью функций библиотеки OpenCV. Для классификации сегментированных пыльцевых зерен, используются следующие методы: метод особых точек, лингвистический метод и нейронная сеть Хэмминга, где комбинируются данные методы с помощью бэггинга. Метод особых точек используется для исключения объектов, не являющихся пыльцевыми зернами. Данная система имеет следующие результаты распознавания: доля ошибок первого рода составляет 7%, второго рода - 24%. Средняя точность распознавания около 93%. Недостатком системы является низкая скорость обработки изображений и распознавания сегментированных пыльцевых зерен. С целью улучшения производительности Н.Е. Ханжина и Е.Б. Замятина применяют возможности технологии CUDA. В среднем на обработку одного изображения требуется 20 секунд.

Таблица 1.4. Сравнение аналогов

Название (имя разработчика/ов)	Используемые методы	Средняя точность	Особенности
Н.Е. Ханжина, Е.Б. Замятина	Метод особых точек, Лингвистический метод, Нейронная сеть Хэмминга	93%	Используется комбинированный подход - бэггинг, в котором метод особых точек используется для исключения объектов, которые не являются пыльцевыми зернами. Для оптимизации используются технологии CUDA.
M. Chica	K-NN	94%	Используется методология цветовых свойств пчелиной пыльцы.
С. Riley	K-NN, Support Vector Machine, Pseudo-linear discriminant analysis, Pseudo-quadratic discriminant analysis, Decision tree	95,4% и 93,8%	Система выполняет оцифровку изображений пыльцевых зерен из-под микроскопа и их классификацию. Наилучшие результаты были получены при использовании K-NN метода.
F. Chung	Weighted Neighbor Distance, Neural Network, Decision Tree, Random Forest	97%	На стадии предобработки изображений и сегментации пыльцевых зерен используется теория многофокальной обработки изображений. Точность в 97% была достигнута с помощью метода Random Forest.
R. Randondo, V. Marcos	Fischer, Support Vector Machine и Random Forest	99%	На этапе обработки был использован новый признак при сегментации пыльцевых зерен «novel contour-inner», который повысил точность на 50%.

M. Chica в своей работе представляет полную методологию аутентификации пыльцевых зерен медоносов от фальсифицируемых образцов, где экспериментально показывает, что предложенная методология будет иметь среднюю точность в 94%. Разрабатываемая система будет способна быстро отклонить фальсифицируемые образцы с недорогих аппаратных средств без необходимости их отправки в лабораторию на экспертизу. Данная методология основана на цветовых свойствах пыльцевых зерен медоносов и использовании одно-классового классификатора (K-NN). Метод ближайших соседей (K-NN) она выбирает, основываясь на своих предыдущих работах. Однако прототип программы еще полностью не реализован.

C. Riley в своем исследовании представляет полуавтоматическую систему, которая выполняет оцифровку изображений пыльцевых зерен из-под микроскопа и их классификацию для построения вероятностной модели гео-исторического расположения для судебно-медицинских экспертиз. C. Riley достиг точности в 95,4% и 93,8% для двух различных морфологически сходных наборов данных пыльцевых зерен. Данная система использует мульти-классификатор из нескольких методов: метод ближайших соседей (K-NN), метод опорных векторов (SVM), линейный дискриминантный анализ (Pseudo-linear discriminant analysis), квадратичный дискриминантный анализ (Pseudo-quadratic discriminant analysis) и дерево принятия решения (Decision tree). Данный мульти-классификатор выбирает результат с наименьшей ошибкой. Наилучшие результаты были получены при использовании K-NN метода.

F. Chung разработал свою систему для распознавания изображений пыльцевых зерен. На стадии предобработки изображений и сегментации пыльцевых зерен он предлагает использовать теорию многофокальной обработки изображений, которая основана на анализе резкости изображения наблюдаемого объекта. Далее на этапе классификации аналогично работе C. Riley он использует мульти-классификатор, состоящий из метода ближайших соседей (K-NN), нейронной сети, дерева принятия решений (Decision tree) и метод «случайный лес» (Random Forest). Где самая высокая точность в 97% была достигнута с помощью метода Random Forest.

И в заключении рассмотрим работу в области распознавания пыльцевых зерен R. Rendondo и V. Marcos. Они в своей работе использовали следующие классификаторы метод Фишера (Fischer), метод опорных векторов (SVM) и Random Forest, кроме того на этапе обработки изображения они предложили новый признак сегментации пыльцевых зерен, который назвали признак новой внутренне-контурной (novel contour-inner) сегментации зерен. Данный признак повысил точность распознавания на 50%. В своей работе они смогли достичь наибольшей точности 99%.

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

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

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

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

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

Обоснована необходимость создания системы и приведен обзор наиболее значимых аналогов систем распознавания пыльцевых зерен таких авторов как Н.Е. Ханжина и Е.Б. Замятина, M. Chica., C. Riley, F. Chung, R. Rendondo и V. Marcos.

2. Формализация описания решения задачи и проектирование системы

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

2.1 Предобработка изображений

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

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

Операция сглаживания (иначе размытия) - довольно популярный метод обработки изображений от шума. Для устранения шума на изображении методом сглаживания будем использовать Гауссово сглаживание. Гауссово сглаживание представляет собой фильтр «размывающий» изображение, который использует функцию Гаусса для вычисления преобразвоания, которые применяется к каждому пикселю изображения. Уравнение гауссовой функции в двумерном измерении выглядит следующим образом:

(1)

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

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

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

Для решения данной задачи будет применяться бинаризация методом Отсу (Otsu). Алгоритм Отсу пытается найти пороговое значение (t), которое минимизирует взвешенную дисперсию внутри класса, заданную соотношением:

(2)

где:

(3)

(4)

(5)

Он фактически находит значение t, которое находится между двумя пиками, так что отклонения от обоих классов минимальны. Все значения выше порога t становятся равны 1, в данном случае 255 (насыщенный) и все значения пикселей, которые меньше порога t -- 0 (ненасыщенный).

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

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

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

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

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

2.2 Распознавание изображений

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

Итак, далее более подробно рассмотрим отбор характеристик и алгоритм классификации объектов (пыльцевых зерен).

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

Для классификации пыльцевых зерен были отобраны 12 признаков (табл. 2.1).

Хотя данные 12 признаков были выбраны после полного изучения литературы, зачастую имеются неуместные особенности и бесполезная информация, которые ухудшают производительность моделей как в скорости, из-за высокой размерности, так и в точности из-за ненужной информации. Выбор признаков имеет цель выбора наименьшего возможного подмножество признаков P необходимых для описания проблемы с начальным набором N признаков, где P =< N. Другими словами, выбор признаков может быть определен как процесс поиска для удаления неуместных и/или избыточных признаков для получения более простой системы классификации. В некоторых задачах отбор признаков необходим не только для более высокой производительности, но и для более точной классификации.

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

Таблица 2.1. Признаки пыльцевых зерен

№	Название признака	Пояснение	Формула вычисления
1	Area (A)	Область	Количество пикселей, представляющих область пыльцевых зерен
2	Perimeter (P)	Периметр	Количество пикселей, которые образуют границу пыльцевых зерен.
3	Compactness (C)	Компактность
4	Diameter (D)	Диаметр	Наибольшее расстояние между любыми двумя точками границы
5	Rmax	Максимальный радиус	Максимальное расстояние между центром зерна пыльцы и любой точкой на ее границе
6	Rmin	Минимальный радиус	Минимальное расстояние между центром зерна пыльцы и любой точкой на ее границе
7	Rd	Дисперсия радиуса	Изменчивость расстояний между центром и всех граничных точек пыльцевых зерен
8	R(среднее)	Средний радиус	Среднее расстояние между центром зерна и всеми точками границы зерна пыльцы
9	Rmax/Rmin	Отношение между Rmax и Rmin	Соотношение между максимальным и минимальным расстоянием граничных точек зерна и центра
10	Rmax/R(среднее)	Отношение между Rmax и R(среднее)	Соотношение между максимальным и средним расстоянием граничных точек зерна и центра
11	Rmin/R(среднее)	Отношение между Rmin и R(среднее)	Соотношение между минимальным и средним расстоянием граничных точек зерна и центра
12	Eccentricity (E)	Эксцентриситет

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

Пусть множество объектов w подразделено на классы U[i], i=1..m, и для описания объектов используются признаки x[j], j=1..N. Все объекты одном и тем же набором признаков. Каждый из признаков может принимать значения из различных множеств (алфавитов), например:

1. 0,1, где 0 - признак не выражен; 1 -выражен;

2. 0,1,X, где X - информация о признаке отсутствует;

3. 0,1,..,c - степень выраженности признака имеет различные градации;

4. [a, b] - признак принимает значение из числового отрезка;

5. f[i](x1,..,xn) - задана условная плотность распределения значений признаков.

Априорная (исходная) информация формируется в виде таблицы, содержащей значения признаков x1,..xn всех объектов, принадлежащих различным классам.

Под распознаваемым объектом будем понимать вектор признаков, компонентами которого являются конкретные значения:

w' = b[1], b[2],.. b[N]. (6)

Суть данного метода заключается в том, что он оперирует не отдельными признаками, а различными сочетаниями признаков (ансамблями признаков).

Сочетания признаков иначе называют систему опорных множеств метода голосования.

Так как не всегда известно наиболее информативные сочетания признаков, входящих в опорные множества, то степень похожести объектов вычисляется сопоставлением всех возможных (или каких-то определенных) опорных множеств признаков, входящих в описание объекта.

Рассмотрим полный набор признаков X=x1,x2,..,xn и выделим систему опорных множеств признаков S1,S2,..,SL.

В качестве системы опорных множеств чаще всего рассматривают:

1. Либо все подмножества множества признаков фиксированной длины k, где k принимает значения из множества 2,..,N-1.

2. Либо вообще все подмножества множества признаков.

Рассмотрим процедуру вычисления оценок по подмножеству S1. Вычисление оценок для остальных подмножеств выполняется аналогично.

В таблице выделяются столбцы, соответствующие признакам, входящим в S1. Проверяется близость строки S1w~' со строками S1w~[1], ..., S1w~[r[1]], соответствующим объектам класса U1.

Число строк этого класса, близких по выбранному критерию классифицируемой строке S1w~', обозначается через Г[S1](w',U1) - оценка строки w' для класса U1 по опорному множеству S1. Аналогично вычисляются оценки для остальных классов Г[S1](w',U2),..., Г[S1](w', Um) по опорному множеству S1.

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

Г[S2](w',U1), ..., Г[S2](w',Um), ..., Г[SL](w',U1), ..., Г[SL](w',Um). (7)

На основании анализа данной системы оценок принимается решение либо об отнесении объекта к одному из классов U[i], i=1..m, либо об отказе от его распознавания.

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

1. Объект может быть отнесен к классу, которому соответствует максимальная оценка.

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

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

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

1. Вычисление оценок по опорным множествам для каждого объекта из таблицы.

2. Затем эти оценки используются для вычисление суммарных оценок для каждого из классов U[i].

3. Применение решающего правила для классификации объекта.

Решающее правило выбирает класс объекта с максимальной оценкой.

2.3 Проектирование системы

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

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

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

2. Обучение системы на обучающем наборе.

3. Распознавание пыльцевых зерен.

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

На основе требований определим актеров и прецеденты и построим диаграмму прецедентов (рис. 2.1).

Рисунок 2.1. Диаграмма прецедентов

Для двух основных сценариев использования системы (обучения и распознавания) спроектируем диаграммы деятельности (см. рис. 2.2 и 2.3).

Рисунок 2.2. Диаграмма деятельности для обучения системы



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

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

Рисунок 2.4. Диаграмма классов

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



Рисунок 2.5. Архитектура системы

Пользовательский интерфейс главным образом будет состоять из двух вкладок: обучение (см. рис. 2.6) и распознавание (см. рис. 2.7). На вкладке обучение пользователь сможет обучить систему. На данной вкладке доступны следующие элементы:

1. Загруженные изображения. В данной части экрана приложения будут отображаться загруженные пользователем изображения.

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

3. Очистить. Удаляет загруженные пользователем изображения.

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

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

6. Обучение. Выполняет обучение системы.

7. Экспорт в Excel. Загружает таблицу признаков в Excel.

8. Загрузить данные. Загружает данные в таблицу из файла.

На вкладке распознавание пользователь сможет начать распознавание изображений. На данной вкладке аналогичные элементы, как и на вкладке обучение: загруженные изображения, загрузка, очистить, предобработка и экспорт в Excel.

Также на данной вкладке находятся:

1. Распознавание. Выполняет распознавание загруженных изображений.

2. Таблица результаты. В данной таблице отображаются результаты распознавания.

Рисунок 2.6. Спроектированные интерфейс вкладка «Обучение»



Рисунок 2.7. Спроектированные интерфейс вкладка «Распознавание»

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

Был описан подробный алгоритм процесса предобработки изображений, включающий в себя:

1. Устранение шумовых помех на изображении методом Гауссова сглаживания.

2. Бинаризация изображения с помощью порогового преобразования методом Отсу.

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

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

Описан алгоритм классификации методом голосования.

Спроектирована архитектура системы:

1. Диаграмма классов.

2. Диаграммы прецедентов.

А также спроектирован пользовательский интерфейс.

3. Реализация программной системы

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

3.1 Используемые инструменты, методы и данные

Для обучающего и тестируемого наборов данных изображений пыльцевых зерен использовался набор данных из исследований Chudyk. Данный набор данных состоит из 5 видов пыльцевых зерен (Alder, Birch, Hazel, Mugwort, и Sweet Grass) каждый из которых содержит в себе по 120 фотографий образцов. Всего данный набор содержит 600 изображений пыльцевых зерен.

Сама разработка содержит два основных этапа: предобработку изображений и классификацию изображений. На протяжении всего исследования при разработке прототипа приложения использовался объектно-ориентированный язык C# и среда разработки MS Visual Studio 2017 (IDE).

Для предобработки изображений использовалась самая популярная подключаемая библиотека компьютерного зрения OpenCV с открытым исходным кодом. Так как данная программная система разрабатывается на C#, то для интеграции OpenCV в среду разработки была использована EmguCV 3.0. Emgu CV - это кроссплатформенная "обёртка" (wrapper) для .NET библиотеки обработки изображений OpenCV от компании Intel, эта библиотека часто используется в системах машинного зрения. Данная библиотека включает более 1000 функций и алгоритмов, с помощью нее было реализовано: устранение шумовых помех на изображении, бинаризация изображения и сегментация выделенных пыльцевых зерен с целью отнесения образа к тому или иному классу.

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

3.2 Процесс реализации системы

В данной части описываются основные этапы реализации системы:

1. Предобработка изображений.

a. Устранение шумовых помех.

b. Пороговое преобразование.

c. Сегментация контура пыльцевого зерна.

2. Вычисление значений признаков.

3. Классификация методом голосования.

Для задачи устранения шумовых помех будем использовать метод Гауссова сглаживания. Для начала необходимо конвертировать изображения из вида RGB в Gray. Далее для устранения шума на изображении в EmguCV можно использовать вызов метода SmoothGaussian, которая применяется к текущему изображению и принимает на вход размер Гауссова ядра, в нашем случае равном трем. На рис. 3.1 и 3.2 можно увидеть результат бинаризации изображений без применения фильтра Гаусса и с его применением.

Для выполнения порогового преобразования будем использовать метод CvInvoke.Threshold. Эта функция используется для получения двоичного изображения из изображения в градация серого. В качестве типа порогового преобразования будем использовать ThresholdType.Otsu. А в качестве двух пиков значений 0 и 255. Пример применения порогового преобразования методом Отсу представлен на рис. 3.1. Для сегментации пыльцевых зерен сначала планировалось использовать изображение, обработанное алгоритмом Канни. Но данный алгоритм обрабатывал лишь 60-70% изображений верно. У части изображений границы контуров детектировались неверно, точнее основной контур часто не имел целостность и обрывался. Из-за чего было принято решения использовать следующий алгоритм действий. Вызывалась функция CvInvoke.FindContours, которая принимает на вход двоичное изображение, где границы переходов пикселей бинаризованного изображения от 0 к 1 рассматриваются как грани. Используя найденные грани, функция формирует вектор контуров. Для аппроксимации используется метод, который сжимает горизонтальные, вертикальные и диагональные сегменты, оставляя только их угловые точки. Все найденные контуры записываются в массив VectorOfVectorOfPoint. Для дальнейшей сегментации применяется алгоритм, формирующий из всех найденных векторов контуров вектор контура, который будет является хорошим кандидатом на роль контура зерна:

1. Сначала оценивается область (площадь) каждого отдельного контура и выбирается самая большая из них.

2. Найденный контур обрисовывается красным на исходном изображении, тем самым найденное зерно выделяется красной рамкой.

3. Алгоритм возвращает вектор координат найденного контура (для дальнейшей возможности вычисления значений признаков пыльцевого зерна).

Результаты сегментации пыльцевых зерен представлены на рис. 3.3.

Рисунок 3.1. Бинаризация с устранением шумовых помех



Рисунок 3.2. Бинаризация без устранения шумовых помех

Рисунок 3.3. Результаты выполнения предобработки изображений

Для вычисления значений признаков контуров использовались формулы (табл. 2.1) и возможности EmguCV описанные ниже.

Для нахождения области контура используется вызов функции CvInvoke.ContourArea.

Для нахождения периметра - CvInvoke.ArcLength.

В качестве нахождения центра зерна используется нахождение центроида из моментов контура CvInvoke.Moments (M00, M01, M10). Нахождение центроида необходимо для вычисления значений радиусов.

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

Эксцентриситет вычисляется из моментов контура: M02, M20 и M11.

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

Классификация пыльцевых зерен выполняется с помощью алгоритма голосования.

В качестве значений признаков пыльцевых зерен используются вычисленные значения контуров. Каждый из признаков может принимать различные значения. Некоторые из признаков принимают только целые значения, другие вещественные. Априорная(исходная) информация хранится в двумерном массиве для обучающей выборки (masForTrainigDataset). Информация о распознаваемых объектах также хранится в двумерном массиве для распознавания (masForRecognitionDataset). Алгоритм распознавания сравнивает описание распознаваемого объекта с описаниями всех объектов, содержащихся в массиве априорной информации, и записывает вычисленные оценки (голоса) в массив оценок (masVoting). Далее алгоритм анализирует массив оценок, и применяет решающее правило с целью отнесения объекта к одному из классов.

3.3 Тестирование системы

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

Все тесты проводились на одном наборе данных из 600 изображений.

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

Таблица 3.1. Результаты тестирования обучения

Класс	Количество изображений	Количество правильно обработанных изображений	Средняя доля правильно обработанных изображений	Время (мс)
Alder	120	120	100%	2060
Birch	120	120	100%	1919
Hazel	120	120	100%	1981
Mugwort	120	120	100%	2032
Sweet Grass	120	120	100%	1902
All	600	600	100%	35491

Рисунок 3.4. Предобработка изображений

По итогам тестирования: контуры изображений абсолютно для всех пыльцевых зерен обрабатываются верно ни смотря на шум, размытие, грязь, мелкие частицы и др.; название класса зерна извлекается из имени файла - верно; вычисление значений признаков и их масштабирование корректно для всех зерен; все данные полученные в ходе обучения сохраняются верно. Время обучения на 120 изображениях в среднем варьируется от 1.9 до 2 секунд. Для выборки из 600 изображений ~35 секунд.

Распознавание. В распознавание входят следующие операции: предобработка изображений, вычисление значений признаков, масштабирование значений признаков, подсчет и оценка голосов. Оценка времени затрачиваемое на распознавание пыльцевых зерен представлена в табл. 3.2. Результаты оценки качества работы распознавания подробно рассмотрены в пункте 3.4 (см. табл. 3.3). Пример распознавания представлен на рис. 3.5-3.7. На рисунках видно, что на изображениях пыльцевых зерен, представленных для распознавания контуры зерен, детектируются верно и класс каждого зерна из представленных образцов распознан верно.

Таблица 3.2. Результаты оценки времени, затрачиваемого на распознавание

Класс	Количество изображений, n1	Время, t1 (мс)	Количество изображений, n2	Время, t2 (мс)
Alder	1	135	10	1031
Birch	1	123	10	1025
Hazel	1	138	10	1100
Mugwort	1	121	10	1002
Sweet Grass	1	123	10	1019



Рисунок 3.5. Предобработка зерен для распознавания класса Alder

Рисунок 3.6. Предобработка зерен для распознавания класса Sweet Grass

Рисунок 3.7. Результат распознавания для 4 пыльцевых зерен

3.4 Анализ результатов и оценка качества работы метода голосования

Оценка производительности - это экспериментальная оценка, которая измеряет способность метода классификации принимать верные решения, то есть вычисляет вероятность верной классификации.

Основными характеристиками качества классификации являются уровни ошибок первого и второго рода (error rates).

Ошибка первого рода - это "ложный пропуск" (false negative), когда интересующее нас событие ошибочно не обнаруживается.

Ошибка второго рода - "ложное обнаружение" (false positive), когда при отсутствии события ошибочно выносится решение о его присутствии.

Пусть количество объектов в тестовом наборе равно N, из них Np - кол-во «положительных» объектов, а Nn - кол-во объектов «отрицательных», где N=Nр+Nn. Пусть количество ложных пропусков FN, а ложных обнаружений FP, тогда несложно подсчитать количество верных пропусков и верных обнаружений (True Positives, True Negatives):

TP = Np - FN, (8)

TN = Nn - FP. (9)

С помощью этих величин рассчитываются нормированные уровни ошибок первого и второго рода (nFN, nFP), а также долю верно распознаваемых пропусков (nTN)) и обнаружений (nTP):

nFN=FN / Np * 100%, (10)

nFP = FP / Nn * 100%, (11)

...