Описание процесса работы над проектом
ДЕТЕКТОР ЛИСТЬЕВ
Новосибирск 2016
Аннотация
В рамках данного проекта реализован программный продукт «Детек- тор листьев», который позволит с легкостью определить принадлежность листа к тому или иному дереву по его изображению. В тексте описана тео- рия, необходимая для понимания работы проекта. «Детектор листьев» напи- сан на языке Matlab, наличие которого необходимо для запуска программы.
Содержание
Введение............................................................................................... 4
1 Описание процесса работы над проектом...................................... 5
1.1 Теоретическая часть........................................................................ 5
1.1.1 Биологическая часть................................................................... 5
1.1.2 Математическая теория.............................................................. 6
1.1.3 Matlab, основные функции......................................................... 7
1.2 Ход работы...................................................................................... 9
1.2.1 Реализация дерева вариантов.................................................... 9
1.2.2 Работа с изображением.............................................................. 9
1.2.3 Разработка алгоритмов............................................................ 11
1.2.4 Разработка программы............................................................ 13
1.2.5 База данных.............................................................................. 13
1.3 Анализ хода работы...................................................................... 14
2 Анализ полученного проекта......................................................... 15
2.1 Характеристики полученного проекта......................................... 15
2.2 Сопоставление целей и полученного продукта............................ 15
2.3 Конструктивные особенности проекта......................................... 15
2.4 Новизна.......................................................................................... 15
2.5 Практическая применимость........................................................ 16
3 Перспективы развития проекта..................................................... 17
Приложение 1.................................................................................... 18
ВВЕДЕНИЕ
Еще пару веков назад определение названия дерева было жизненно не- обходимой задачей для каждого человека. Ребенок должен был уметь отли- чить куст с ядовитой ягодой от куста со съедобной. Плотник или столяр дол- жен был понимать, какое дерево он срубит и какой предмет мебели или сам дом можно изготовить из этого дерева. В современном мире человеку, живу- щему в городских условиях, эти навыки уже не нужны, поэтому немногие могут быстро определить название стоящего перед ними дерева или куста.
Для реализации проекта необходимо поставить цель, которая опреде- ляет результат проекта, и задачи, которые позволяют достичь эту цель.
Целью проекта является создание программного продукта на языке Matlab, который позволит определить принадлежность листа к какому-либо растению по его изображению.
Задачи, поставленные для выполнения проекта:
1) Изучить строение листьев различных растений и выявить их отличи- тельные признаки;
2) Разработать алгоритм, который позволит компьютеру различать эти от- личительные признаки;
3) Создать базу, в которой содержатся характеристики каждого листа;
4) Написать разработанные алгоритмы на языке Matlab и соединить их в единую программу, которая в итоге и позволит определить растение по изображению его листа.
ОПИСАНИЕ ПРОЦЕССА РАБОТЫ НАД ПРОЕКТОМ
Теоретическая часть
Биологическая часть
С биологической точки зрения листья делятся на простые и сложные (ри- сунок 1). Простые листья имеют единую листовую пластину, а сложные – разделенную.
 |
Рисунок 1 – Классификация листьев
В дальнейшем при реализации проекта учитывались только простые листья. Также каждый лист имеет такие параметры как (рисунок 2):
1) Его длина и ширина (для программы было использовано отношение длины к ширине);
2) Величина угла при вершине;
3) Наличие/отсутствие зубчиков (край листа может быть гладким или с зубчиками, как на рисунке 2);
4) Количество крайних точек (крайние точки определяют наличие выпук- лого участка на листе с острым углом).
 |
Рисунок 2 – Параметры листа
Математическая теория
В данном проекте при анализе программой изображения листа используется принцип математических деревьев.
Дерево выбора — средство поддержки принятия решений, использующееся в статистике и анализе данных для прогнозных моделей. Структура де- рева представляет собой «листья» и «ветки». На ребрах («ветках») дерева решения записаны атрибуты, от которых зависит целевая функция, в «листьях» записаны значения целевой функции, а в остальных узлах — атрибуты, по которым различаются случаи. Подобные деревья решений широко используются в интеллектуальном анализе данных. Цель состоит в том, чтобы создать модель, которая предсказывает значение целевой переменной на основе нескольких переменных на входе. Также необходимой теорией для успешной реализации проекта являются тригонометрические функции и обратные им. В прямоугольном треугольнике ABC для угла α (рисунок 3) определено:
 |
Рисунок 3 – Прямоугольный треугольник ABC
Matlab, основные функции
В коде использовались следующие функции:
· if: оператор «если». Если значение параметра «выражение» соот- ветствует значению «истинно», то выполняется оператор, иначе он пропускается программой.
if <выражение>
<операторы> end
· for: оператор цикла. Позволяет проще и нагляднее реализовывать цикл, в котором требуется перебирать значение счетчика в заданном диапазоне значений и с заданным шагом изменения. Если шаг изменения не задан, то он автоматически равен единице.
for <счетчик> = <начальное значение>:<конечное значение>
<операторы цикла>
end
· imread: функции чтения изображений, представленных в форматах bmp, png, gif, jpeg, tif.
Picturename = imread(‘filename’);
· imshow: функции вывода изображений.
imshow(Picturename);
· imresize: функция, которая создает новое изображение, изменяя размеры исходного изображения любого типа (в представленной программе использовался автоматический подбор новой ширины изображения).
Newimage = imresize(Oldimage [hight Nan]);
· axis on: автоматическая вставка осей координат.
axis on;
· round: функция возвращает значения, округленные до ближайшего целого.
Y = round(X)
· atand: возвращает арктангенс (для действительных чисел возвращает значения в диапазоне от –π/2 до π/2).
Y = atand(X);
· im2bw: функция создает бинарное изображение, используя отсечение по порогу яркости. Пикселы результирующего бинарного изображения принимают значения 0 (черный цвет), если яркость соответствующих пикселов исходного изображения меньше порога threshold, и значения 1 (белый цвет), если яркость соответствующих пикселов исходного изображения больше либо равна threshold. Порог threshold должен задаваться в диапазоне [0, 1]. Result = im2bw(Picture, threshold);
Ход работы
1.2.1 Реализация дерева вариантов
При анализе выявленных параметров было составлено дерево вариантов (рисунок 4), которое позволяет не проверять у каждого листа по 4 параметра, а делать это только с индивидуальными отличительными признаками.
 |
Рисунок 4 – Дерево вариантов
Работа с изображением
Для различения параметров листа не нужно цветное изображение, поэтому прежде чем запускать разработанные алгоритмы на изображении листа, необходимо перевести его в черно-белую картинку (рисунок 5) и записать результат в матрицу, где 0 – черный цвет, а 1 - белый.
Чтобы получить изображение, как на Рисунке 5, программа выполняет с изображением следующие функции:
1) Кластеризация (Приложение 1, пункт 1).
Кластеризация — это задача разбиения множества объектов на группы, называемые кластерами. Внутри каждой группы должны оказаться «похожие» объекты, а объекты разных группы должны быть как можно более отличны.
Программа выполняет бинарную кластеризацию изображения по границе яркости 0,775.
Рисунок 5 – Преобразование изображения, кластеризация
2) Размер изображения (Приложение 1, пункт 2).
Программа выставляет высоту изображения 2000 пикселей и автоматически подбирает ширину с сохранением пропорций изначального изображения.
3) Чистка изображения (Приложение 1, пункт 3).
При кластеризации на изображении могут остаться белые пятна на площади самого листа или черные точки на белом фоне. Для того, чтобы от них избавиться, программа построчно проверяет для каждого пикселя цвет его соседей через 10 пикселей влево и вправо. Если хотя бы один из соседей такого же цвета, что и проверяемый пиксель, то его цвет не меняется, в противном случае цвет пикселя меняется на противоположный.
Аналогичный алгоритм повторяется для соседей на расстоянии 5 и 3 пикселя для увеличения точности и исключения вероятности незакрашивания неправильных пикселей. Затем этот алгоритм повторяется по столбцам.
Таким образом белые пиксели на белом фоне заменяются на черные и наоборот.
4) Отсечение черенка (Приложение 1, пункт 4).
От середины изображения вниз построчно проводится следующий алгоритм: Для каждого черного пикселя проверяется цвет его соседей через 1/30 от ширины изображения. Если оба соседних пикселя белого цвета, то проверяемый закрашивается белым.
Таким образом, от листа убирается черенок.
Разработка алгоритмов
Для проверки каждого параметра необходимо было разработать алгоритм, который впоследствии будет реализован в программе на языке Matlab.
1) Отношение длины к ширине.
Для нахождения длины использован алгоритм, который проверяет каждую строчку на наличие черного пикселя сверху вниз. Как только программа встречает первый черный пиксель, она запускает счетчик и проверяет каждую последующую строчку. Пока в строчке есть черные пиксели, счетчик увеличивается. Таким образом, в счетчике сохраняется длина листа.
Аналогичным образом находится ширина листа (программа проверяет по столбцам). Для нахождения отношения длины к ширине, нужно поделить первое на второе.
2) Количество крайних точек.
Крайние точки определяют наличие выпуклого участка на листе. Для их подсчета программа проверяет левый край листа, затем умножает количество получившихся точек на два, предполагая симметричность листовой пластины.
Пиксель является крайним, если у квадрата 61*61, где она центральная, количество черных пикселей на периметре меньше 58.
3) Угол при вершине.
Программа берет вершину листа (самый первый черный пиксель при по- строчной проверке изображения), опускается вертикально вниз на 1/8 от всей
длины листа (), смотрит строчку основания до краев листа, тем самым полу- чая основания и . Строится два прямоугольных прямоугольника (рисунок
6), у которых находятся углы при вершинах через их тангенсы. Складывается сумма двух углов и получатся величина угла при вершине.
Рисунок 6 – Угол при вершине
Искомый угол: γ = α + β = arctg(a / c) + arctg(b / c)
4) Наличие/отсутствие зубчиков.
Для определения зубчика программы проверяет картинку по столбцам. Если в столбце есть 1, 2, 3 или 4 черных пикселя, у которых сверху и снизу хотя бы по три белых пикселя (рисунок 7), то данный участок называется зубчиком.
Рисунок 7 – Зубчики
Разработка программы
По разработанным алгоритмам были написаны части кода, которые впо- следствии соединены в итоговую программу.
1) Отношение длины к ширине (Приложение 1, пункт 5);
2) Угол при вершине (Приложение 1, пункт 7);
3) Наличие/отсутствие зубчиков (Приложение 1, пункт 8);
4) Количество крайних точек (Приложение 1, пункт 6);
5) Проверка изображения и вывод результата (Приложение 1, пункт 9).
База данных
На данный момент детектор листьев имеет начальную базу данных (таб- лица 1.1) из 11 листьев, которая составлена на основе различных вариантов изображений листьев дерева каждого вида. При обработке изображения про- грамма получала различные параметры листа, затем на основе полученных данных были составлены числовые диапазоны для каждого параметра.
Таблица 1.1 – База данных
| Название дерева | Отношение длины к ширине | Угол при вершине | Количество крайних точек | Наличие зубчиков |
| Ива | 0.51 – 0.7 | — | — | — |
| Гинко | 4.41– 6.5 | — | — | — |
| Лавр | 2 – 3.1 | — | — | — |
| Осина | 0.8 – 1.2 | 95 – 135 | — | |
| Клен | 0.8 – 0.99 | 30 - 75 | — | — |
| Дуб | 1.2 – 1.8 | 75 - 120 | — | — |
| Вишня | 1.8 – 1.9 | 36 - 104 | >16 | — |
| Яблоня | 1.6 – 1.9 | 40 - 104 | 1 - 14 | — |
| Липа | 1 – 1.2 | 56 - 101 | <10 | да |
| Береза | 1.1 – 1.4 | 30 - 55 | <105 | да |
| Сирень | 1.1 – 1.4 | 35 - 70 | <40 | нет |
Анализ хода работы
В ходе работы над проектом возникали сложности с реализацией алгорит- мов в коде, из-за отсутствия опыта работы с языком Matlab. Но подобные за- труднения не повлияли на результат и работоспособность программмы.
АНАЛИЗ ПОЛУЧЕННОГО ПРОЕКТА
Новизна
Новизна проекта заключается в том, что большинство существующих об- щедоступных аналогов программы основывается на алгоритме сравнения изображений с шаблоном. А ныне реализованный проект определяет назва- ние дерева по параметрам имеющегося листа.
Практическая применимость
Программа «Детектор листьев» может использоваться среди людей для обеспечения безопасности на прогулке или в походе от ядовитых растений.
Еще одной возможной областью применения программы является образо- вание. Она может полезна для проведения практических работ по биологии для средних или младших классов.
Программа может найти свое применение среди любителей собирать раз- личные растения для изготовления натуральных лекарств или отваров.
ПРИЛОЖЕНИЕ 1
ДЕТЕКТОР ЛИСТЬЕВ
Новосибирск 2016
Аннотация
В рамках данного проекта реализован программный продукт «Детек- тор листьев», который позволит с легкостью определить принадлежность листа к тому или иному дереву по его изображению. В тексте описана тео- рия, необходимая для понимания работы проекта. «Детектор листьев» напи- сан на языке Matlab, наличие которого необходимо для запуска программы.
Содержание
Введение............................................................................................... 4
1 Описание процесса работы над проектом...................................... 5
1.1 Теоретическая часть........................................................................ 5
1.1.1 Биологическая часть................................................................... 5
1.1.2 Математическая теория.............................................................. 6
1.1.3 Matlab, основные функции......................................................... 7
1.2 Ход работы...................................................................................... 9
1.2.1 Реализация дерева вариантов.................................................... 9
1.2.2 Работа с изображением.............................................................. 9
1.2.3 Разработка алгоритмов............................................................ 11
1.2.4 Разработка программы............................................................ 13
1.2.5 База данных.............................................................................. 13
1.3 Анализ хода работы...................................................................... 14
2 Анализ полученного проекта......................................................... 15
2.1 Характеристики полученного проекта......................................... 15
2.2 Сопоставление целей и полученного продукта............................ 15
2.3 Конструктивные особенности проекта......................................... 15
2.4 Новизна.......................................................................................... 15
2.5 Практическая применимость........................................................ 16
3 Перспективы развития проекта..................................................... 17
Приложение 1.................................................................................... 18
ВВЕДЕНИЕ
Еще пару веков назад определение названия дерева было жизненно не- обходимой задачей для каждого человека. Ребенок должен был уметь отли- чить куст с ядовитой ягодой от куста со съедобной. Плотник или столяр дол- жен был понимать, какое дерево он срубит и какой предмет мебели или сам дом можно изготовить из этого дерева. В современном мире человеку, живу- щему в городских условиях, эти навыки уже не нужны, поэтому немногие могут быстро определить название стоящего перед ними дерева или куста.
Для реализации проекта необходимо поставить цель, которая опреде- ляет результат проекта, и задачи, которые позволяют достичь эту цель.
Целью проекта является создание программного продукта на языке Matlab, который позволит определить принадлежность листа к какому-либо растению по его изображению.
Задачи, поставленные для выполнения проекта:
1) Изучить строение листьев различных растений и выявить их отличи- тельные признаки;
2) Разработать алгоритм, который позволит компьютеру различать эти от- личительные признаки;
3) Создать базу, в которой содержатся характеристики каждого листа;
4) Написать разработанные алгоритмы на языке Matlab и соединить их в единую программу, которая в итоге и позволит определить растение по изображению его листа.
ОПИСАНИЕ ПРОЦЕССА РАБОТЫ НАД ПРОЕКТОМ
Теоретическая часть
Биологическая часть
С биологической точки зрения листья делятся на простые и сложные (ри- сунок 1). Простые листья имеют единую листовую пластину, а сложные – разделенную.
| |
Рисунок 1 – Классификация листьев
В дальнейшем при реализации проекта учитывались только простые листья. Также каждый лист имеет такие параметры как (рисунок 2):
1) Его длина и ширина (для программы было использовано отношение длины к ширине);
2) Величина угла при вершине;
3) Наличие/отсутствие зубчиков (край листа может быть гладким или с зубчиками, как на рисунке 2);
4) Количество крайних точек (крайние точки определяют наличие выпук- лого участка на листе с острым углом).
| |
Рисунок 2 – Параметры листа
Математическая теория
В данном проекте при анализе программой изображения листа используется принцип математических деревьев.
Дерево выбора — средство поддержки принятия решений, использующееся в статистике и анализе данных для прогнозных моделей. Структура де- рева представляет собой «листья» и «ветки». На ребрах («ветках») дерева решения записаны атрибуты, от которых зависит целевая функция, в «листьях» записаны значения целевой функции, а в остальных узлах — атрибуты, по которым различаются случаи. Подобные деревья решений широко используются в интеллектуальном анализе данных. Цель состоит в том, чтобы создать модель, которая предсказывает значение целевой переменной на основе нескольких переменных на входе. Также необходимой теорией для успешной реализации проекта являются тригонометрические функции и обратные им. В прямоугольном треугольнике ABC для угла α (рисунок 3) определено:
| |
Рисунок 3 – Прямоугольный треугольник ABC
Matlab, основные функции
В коде использовались следующие функции:
· if: оператор «если». Если значение параметра «выражение» соот- ветствует значению «истинно», то выполняется оператор, иначе он пропускается программой.
if <выражение>
<операторы> end
· for: оператор цикла. Позволяет проще и нагляднее реализовывать цикл, в котором требуется перебирать значение счетчика в заданном диапазоне значений и с заданным шагом изменения. Если шаг изменения не задан, то он автоматически равен единице.
for <счетчик> = <начальное значение>:<конечное значение>
<операторы цикла>
end
· imread: функции чтения изображений, представленных в форматах bmp, png, gif, jpeg, tif.
Picturename = imread(‘filename’);
· imshow: функции вывода изображений.
imshow(Picturename);
· imresize: функция, которая создает новое изображение, изменяя размеры исходного изображения любого типа (в представленной программе использовался автоматический подбор новой ширины изображения).
Newimage = imresize(Oldimage [hight Nan]);
· axis on: автоматическая вставка осей координат.
axis on;
· round: функция возвращает значения, округленные до ближайшего целого.
Y = round(X)
· atand: возвращает арктангенс (для действительных чисел возвращает значения в диапазоне от –π/2 до π/2).
Y = atand(X);
· im2bw: функция создает бинарное изображение, используя отсечение по порогу яркости. Пикселы результирующего бинарного изображения принимают значения 0 (черный цвет), если яркость соответствующих пикселов исходного изображения меньше порога threshold, и значения 1 (белый цвет), если яркость соответствующих пикселов исходного изображения больше либо равна threshold. Порог threshold должен задаваться в диапазоне [0, 1]. Result = im2bw(Picture, threshold);
Ход работы
1.2.1 Реализация дерева вариантов
При анализе выявленных параметров было составлено дерево вариантов (рисунок 4), которое позволяет не проверять у каждого листа по 4 параметра, а делать это только с индивидуальными отличительными признаками.
| |
Рисунок 4 – Дерево вариантов
Работа с изображением
Для различения параметров листа не нужно цветное изображение, поэтому прежде чем запускать разработанные алгоритмы на изображении листа, необходимо перевести его в черно-белую картинку (рисунок 5) и записать результат в матрицу, где 0 – черный цвет, а 1 - белый.
Чтобы получить изображение, как на Рисунке 5, программа выполняет с изображением следующие функции:
1) Кластеризация (Приложение 1, пункт 1).
Кластеризация — это задача разбиения множества объектов на группы, называемые кластерами. Внутри каждой группы должны оказаться «похожие» объекты, а объекты разных группы должны быть как можно более отличны.
Программа выполняет бинарную кластеризацию изображения по границе яркости 0,775.
Рисунок 5 – Преобразование изображения, кластеризация
2) Размер изображения (Приложение 1, пункт 2).
Программа выставляет высоту изображения 2000 пикселей и автоматически подбирает ширину с сохранением пропорций изначального изображения.
3) Чистка изображения (Приложение 1, пункт 3).
При кластеризации на изображении могут остаться белые пятна на площади самого листа или черные точки на белом фоне. Для того, чтобы от них избавиться, программа построчно проверяет для каждого пикселя цвет его соседей через 10 пикселей влево и вправо. Если хотя бы один из соседей такого же цвета, что и проверяемый пиксель, то его цвет не меняется, в противном случае цвет пикселя меняется на противоположный.
Аналогичный алгоритм повторяется для соседей на расстоянии 5 и 3 пикселя для увеличения точности и исключения вероятности незакрашивания неправильных пикселей. Затем этот алгоритм повторяется по столбцам.
Таким образом белые пиксели на белом фоне заменяются на черные и наоборот.
4) Отсечение черенка (Приложение 1, пункт 4).
От середины изображения вниз построчно проводится следующий алгоритм: Для каждого черного пикселя проверяется цвет его соседей через 1/30 от ширины изображения. Если оба соседних пикселя белого цвета, то проверяемый закрашивается белым.
Таким образом, от листа убирается черенок.
Разработка алгоритмов
Для проверки каждого параметра необходимо было разработать алгоритм, который впоследствии будет реализован в программе на языке Matlab.
1) Отношение длины к ширине.
Для нахождения длины использован алгоритм, который проверяет каждую строчку на наличие черного пикселя сверху вниз. Как только программа встречает первый черный пиксель, она запускает счетчик и проверяет каждую последующую строчку. Пока в строчке есть черные пиксели, счетчик увеличивается. Таким образом, в счетчике сохраняется длина листа.
Аналогичным образом находится ширина листа (программа проверяет по столбцам). Для нахождения отношения длины к ширине, нужно поделить первое на второе.
2) Количество крайних точек.
Крайние точки определяют наличие выпуклого участка на листе. Для их подсчета программа проверяет левый край листа, затем умножает количество получившихся точек на два, предполагая симметричность листовой пластины.
Пиксель является крайним, если у квадрата 61*61, где она центральная, количество черных пикселей на периметре меньше 58.
3) Угол при вершине.
Программа берет вершину листа (самый первый черный пиксель при по- строчной проверке изображения), опускается вертикально вниз на 1/8 от всей
длины листа (), смотрит строчку основания до краев листа, тем самым полу- чая основания и . Строится два прямоугольных прямоугольника (рисунок
6), у которых находятся углы при вершинах через их тангенсы. Складывается сумма двух углов и получатся величина угла при вершине.
Рисунок 6 – Угол при вершине
Искомый угол: γ = α + β = arctg(a / c) + arctg(b / c)
4) Наличие/отсутствие зубчиков.
Для определения зубчика программы проверяет картинку по столбцам. Если в столбце есть 1, 2, 3 или 4 черных пикселя, у которых сверху и снизу хотя бы по три белых пикселя (рисунок 7), то данный участок называется зубчиком.
Рисунок 7 – Зубчики
Разработка программы
По разработанным алгоритмам были написаны части кода, которые впо- следствии соединены в итоговую программу.
1) Отношение длины к ширине (Приложение 1, пункт 5);
2) Угол при вершине (Приложение 1, пункт 7);
3) Наличие/отсутствие зубчиков (Приложение 1, пункт 8);
4) Количество крайних точек (Приложение 1, пункт 6);
5) Проверка изображения и вывод результата (Приложение 1, пункт 9).
База данных
На данный момент детектор листьев имеет начальную базу данных (таб- лица 1.1) из 11 листьев, которая составлена на основе различных вариантов изображений листьев дерева каждого вида. При обработке изображения про- грамма получала различные параметры листа, затем на основе полученных данных были составлены числовые диапазоны для каждого параметра.
Таблица 1.1 – База данных
| Название дерева | Отношение длины к ширине | Угол при вершине | Количество крайних точек | Наличие зубчиков |
| Ива | 0.51 – 0.7 | — | — | — |
| Гинко | 4.41– 6.5 | — | — | — |
| Лавр | 2 – 3.1 | — | — | — |
| Осина | 0.8 – 1.2 | 95 – 135 | — | |
| Клен | 0.8 – 0.99 | 30 - 75 | — | — |
| Дуб | 1.2 – 1.8 | 75 - 120 | — | — |
| Вишня | 1.8 – 1.9 | 36 - 104 | >16 | — |
| Яблоня | 1.6 – 1.9 | 40 - 104 | 1 - 14 | — |
| Липа | 1 – 1.2 | 56 - 101 | <10 | да |
| Береза | 1.1 – 1.4 | 30 - 55 | <105 | да |
| Сирень | 1.1 – 1.4 | 35 - 70 | <40 | нет |
Анализ хода работы
В ходе работы над проектом возникали сложности с реализацией алгорит- мов в коде, из-за отсутствия опыта работы с языком Matlab. Но подобные за- труднения не повлияли на результат и работоспособность программмы.
АНАЛИЗ ПОЛУЧЕННОГО ПРОЕКТА