Помощь студентам в учебе
О РАЗБИЕНИИ ЦИФРОВЫХ ИЗОБРАЖЕНИЙ НА КЛАССЫ МЕТОДАМИ К - MEANS, FOREL И С ПОМОЩЬЮ КЛАССИФИКАТОРА БАЙЕСА
|
Реферат 2
Введение 4
1 Модель данных 9
1.1 Проверка распределения дескрипторов 10
1.2 Дескрипторы изображений 11
1.2.1 Усреднённые значения по каналам RGB 11
1.2.2 Усреднённое преобразование Фурье - спектра 12
1.2.3 Моменты Хью 14
1.2.4 Гистограммы 16
1.3 Проверка на нормальность дескрипторов 17
2 Методы кластеризации 22
2.1 Метод Forel 23
2.2 Метод k - means 24
2.3 Классификатор Байеса 24
2.3.1 Многомерная нормальная плотность распределения 27
2.3.2 Разделяющие функции для нормального случая 28
3 Сравнительный анализ 30
3.1 Обучающая выборка (подсолнухи и мотоциклы) 30
3.2 Тестовая выборка (подсолнухи и мотоциклы) 34
3.3 Обучающая выборка (гвоздики и мотоциклы) 39
3.4 Тестовая выборка (гвоздики и мотоциклы) 42
4 Сравнительный анализ методов Forel и k - means для стандартизированных 48 данных
Заключение 51
Список использованной литературы 53
Приложение А 56
Приложение Б 56
Приложение В 57
Приложение Г 57
Приложение Д
Введение 4
1 Модель данных 9
1.1 Проверка распределения дескрипторов 10
1.2 Дескрипторы изображений 11
1.2.1 Усреднённые значения по каналам RGB 11
1.2.2 Усреднённое преобразование Фурье - спектра 12
1.2.3 Моменты Хью 14
1.2.4 Гистограммы 16
1.3 Проверка на нормальность дескрипторов 17
2 Методы кластеризации 22
2.1 Метод Forel 23
2.2 Метод k - means 24
2.3 Классификатор Байеса 24
2.3.1 Многомерная нормальная плотность распределения 27
2.3.2 Разделяющие функции для нормального случая 28
3 Сравнительный анализ 30
3.1 Обучающая выборка (подсолнухи и мотоциклы) 30
3.2 Тестовая выборка (подсолнухи и мотоциклы) 34
3.3 Обучающая выборка (гвоздики и мотоциклы) 39
3.4 Тестовая выборка (гвоздики и мотоциклы) 42
4 Сравнительный анализ методов Forel и k - means для стандартизированных 48 данных
Заключение 51
Список использованной литературы 53
Приложение А 56
Приложение Б 56
Приложение В 57
Приложение Г 57
Приложение Д
Активное развитие компьютерной техники и технологий привели к стремительному росту количества цифровых изображений. Источниками таких изображений являются цифровые фотоаппараты, видеокамеры, видеорегистраторы, камеры видеонаблюдения, мобильные телефоны, сканеры и т.д. Появились различные архивы, содержащие миллионы фотографий [1]. То есть возникает проблема структурирования архивов, их упорядочивание, описание отдельных изображений и классов “близких” в каком - либо смысле изображений. Таким образом, актуальными и практически значимыми являются задачи:
♦ Выявления минимальных наборов признаков, адекватно описывающих изображения;
* Создание алгоритмов классификации и их сравнения.
В настоящее время в этом направлении проводятся исследования. В данной работе будут рассмотрены некоторые из них.
В работе [2] в качестве основной проблемы в машинном зрении выделяют нахождение соответствий на изображениях. Методы поиска таких соответствий базируется на процессе распознания, задачей, которой является вычисление признаков объектов по их изображениям. Процесс тесно связанный с распознаванием — идентификация объектов. Суть идентификации заключается в объединении всей полученной информации от процесса распознавания в единое целое с целью классифицировать объект .
Любое цифровое изображение можно представить в виде множества числовых признаков, заданных в пространстве. Размерность этого пространства определяется числом пикселов изображения. Однако классификация объектов (изображений) в таком пространстве невозможна. В работе [3] указано по какой причине это практически невозможно сделать.
1. Представление изображения является избыточным, признаки оказываются сильно зависимыми.
2. Обучение многопараметрических классификаторов для большой размерности признаков требует значительных ресурсов (временных, объема обучающей выборки и т.д.), причем качество таких классификаторов при реальном применении может не удовлетворять заданным требованиям.
3. Поиск изображения в больших базах данных с использованием большого числа признаков потребует неоправданно больших вычислительных ресурсов. При преобразовании изображения в другое пространство без снижения его размерности (например, путем спектрального преобразования) эти проблемы сохраняются.
Таким образом, одной из важных и сложных задач является задача построения эффективных систем распознавания. В работе [4] рассматривается задача выбора рабочего словаря признаков, составленного из наиболее информативных признаков. Успешное решение этой задачи обеспечивает как снижение размерности вектора признаков, подлежащих анализу, так и повышение эффективности системы распознавания в целом [4]. В [5] признаками объекта (дескрипторы) называют его качественные и количественные характеристики. Дескриптором называется набор параметров, описывающих характеристики изображения, например, такие как цвет, текстуру и т.д. [2].
В [2] объект описывается некоторыми дескрипторами, называемыми авторами глобальными и локальными. Под глобальными признаками подразумеваются вектора признаков, полученные при анализе всего изображения в целом (например, цвет, текстура). Поиск по глобальным дескрипторам применяется при решении задачи поиска по запросу - образцу тех изображений, которые визуально и семантически похожи. Под локальными признаками подразумевается вектора признаков, которые описывают не все изображение в целом, а какие - то его небольшие части. Также в работе [5] признаки объектов на цифровых изображениях разделены на первичные и вторичные. Первичные признаки — это такие признаки, которые вычисляются с помощью цифрового изображения. Вторичные вычисляются на базе первичных.
Методы поиска по локальным дескрипторам применяются в основном для решения задач поиска нечетких дубликатов и поиска заданного фрагмента на изображениях коллекции [2]. В работе [6] рассматриваются нечеткие дубликаты. Два изображения, которые могут быть переведены друг в друга путем элементарных преобразований, таких как поворот, сдвиг, изменение угла обзора, изменение разрешения, изменение масштаба, изменение освещения, называются нечеткими дубликатами. Примерами нечетких дубликатов являются снимки, сделанные с различных ракурсов, при различном освещении, в различные моменты времени, при помощи различных регистрирующих устройств. Заметим, что нечеткими дубликатами являются в том числе отредактированные изображения.
Для поиска таких нечетких дубликатов в [6] был предложен метод, основанный на выявлении и сопоставлении точечных особенностей изображений. В [2] точечной особенностью называется точка изображения, структура окрестности которой ковариантная заданным преобразованиям изображения. Для нахождения этих особенностей 5
разрабатываются различные методы - детекторы. Результатом методов - детекторов является множество особых точек, для которых строиться математическое описание. Для этих особых точек рассчитываются дескрипторы, описывающие структуру окрестности точечной особенности. Дескрипторы строятся на основании информации об интенсивности, цвете и текстуре особой точки. Также особыми точками могут являться углы, ребра или даже контур объекта.
Рассмотрим различные виды дескрипторов, которые представлены в работе [5].
Геометрические признаки
Геометрические признаки вычисляются локально. К геометрическим признакам можно отнести: особые точки объекта, границу объекта, форму объекта, размеры объекта.
Приведем пример таких признаков.
♦ Особыми точками для отрезка являются две его конечные вершины.
♦ Размерными признаками являются количество пикселей объекта, его длина, ширина.
В работе [7] описаны методы определения геометрических параметров и анализа пространственного положения объектов.
Яркостные признаки
Яркостные признаки описывают изменения локальной энергии изображения, то есть перепады в яркостях пикселей, составляющих изображение. К яркостным признакам можно отнести: экстремумы, частотные признаки, гистограммные признаки, моменты.
Поясним эти признаки.
♦ Экстремум объекта — максимальное или минимальное значение пикселя.
♦ Частотные признаки используются для обнаружения краев, границ, угловых щель.
♦ К гистограммным признакам относят среднее значение, стандартное отклонение, искажение.
В работе [8] предлагается использовать цветовые признаки. Для этого строится цветовая гистограмма, учитывающая пространственное расположение цветов, и вычисляются цветовые моменты. Для оценки подобия двух изображений сравниваются параметры распределения их цветов: математическое ожидание по каждому из цветовых каналов и попарные ковариации распределений каналов.
В работе [9] рассматривается возможность цветовой модели HIS (Hue, Saturation, Intensity). HSI — это цилиндрическое представление цветовой модели RGB, состоящее из компонент: цветовой тон, насыщенность и интенсивность. Автор также предлагает использовать модель HLD (Hue Layout Descriptor).
Текстурные признаки
Текстура есть повторение текселей. Тексель содержит несколько пикселей, расположение которых периодичное, квазипериодчное или случайное. Текстурными признаками являются: угловой момент второго порядка, контраст, корреляция, сумма дисперсий, сумма энтропии, энтропия.
В работе [7] приведен обзор текстурных признаков. Дано краткое описание каждого признака. Рассмотрена проблема выбора информативных признаков.
Бинарные признаки
Бинарные признаки могут иметь только два значения. При сравнении двух бинарных признаков можно сделать единственный вывод о совпадении или несовпадении значений признаков.
Комбинированные признаки
Комбинированные признаки — это комбинация текстурных, геометрических и яркостных признаков.
В работе [10] предлагается дескрипторы условно разделить на следующие категории:
1. Дескрипторы на основе вероятностных распределений. Для этой категории дескрипторов фрагмент изображения используется для построения оценки некоторого распределения вероятностей.
2. Дескрипторы на основе спектрального и спектрально - частотного представления. Дескрипторы этого класса формируются как функции отсчётов спектрального или спектрально - частотного разложения анализируемого фрагмента изображения .
3. Дифференциальные дескрипторы. Дескрипторы этой категории рассчитываются как функции частных производных функции яркости анализируемого изображения .
4. Дескрипторы, конструируемые на основе дифференциальных и вероятностных свойств локальной окрестности наблюдаемого изображения. Спецификой дескриптора является наличие априори заданного (или заранее определённого по обучающему множеству изображений) вероятностного распределения поля градиента, характеризующего модель анализируемого изображения и/или решаемую задачу.
Также на данный момент актуальны задачи поиска трёхмерных моделей. Данная задача является одной из самых сложных в области компьютерного зрения, поскольку для ее решения требуется эффективный и робастный алгоритм сравнения трёхмерных полигональных моделей произвольной формы. Один из подходов к этому основан на глобальных дескрипторах поверхности, содержащих информацию о форме всей поверхности модели в сжатом и ёмком виде. В статье [11] представлены новые глобальные дескрипторы поверхности, названные интегральными спиновыми изображениями. Также предложен специальный метод нормализации трёхмерной модели для вычисления интегрального спинового изображения. В статье показано, что новый метод сравнения моделей с использованием интегральных спиновых изображений обеспечивает адекватную меру похожести формы моделей и может успешно применяться в системах поиска трёхмерных моделей.
♦ Выявления минимальных наборов признаков, адекватно описывающих изображения;
* Создание алгоритмов классификации и их сравнения.
В настоящее время в этом направлении проводятся исследования. В данной работе будут рассмотрены некоторые из них.
В работе [2] в качестве основной проблемы в машинном зрении выделяют нахождение соответствий на изображениях. Методы поиска таких соответствий базируется на процессе распознания, задачей, которой является вычисление признаков объектов по их изображениям. Процесс тесно связанный с распознаванием — идентификация объектов. Суть идентификации заключается в объединении всей полученной информации от процесса распознавания в единое целое с целью классифицировать объект .
Любое цифровое изображение можно представить в виде множества числовых признаков, заданных в пространстве. Размерность этого пространства определяется числом пикселов изображения. Однако классификация объектов (изображений) в таком пространстве невозможна. В работе [3] указано по какой причине это практически невозможно сделать.
1. Представление изображения является избыточным, признаки оказываются сильно зависимыми.
2. Обучение многопараметрических классификаторов для большой размерности признаков требует значительных ресурсов (временных, объема обучающей выборки и т.д.), причем качество таких классификаторов при реальном применении может не удовлетворять заданным требованиям.
3. Поиск изображения в больших базах данных с использованием большого числа признаков потребует неоправданно больших вычислительных ресурсов. При преобразовании изображения в другое пространство без снижения его размерности (например, путем спектрального преобразования) эти проблемы сохраняются.
Таким образом, одной из важных и сложных задач является задача построения эффективных систем распознавания. В работе [4] рассматривается задача выбора рабочего словаря признаков, составленного из наиболее информативных признаков. Успешное решение этой задачи обеспечивает как снижение размерности вектора признаков, подлежащих анализу, так и повышение эффективности системы распознавания в целом [4]. В [5] признаками объекта (дескрипторы) называют его качественные и количественные характеристики. Дескриптором называется набор параметров, описывающих характеристики изображения, например, такие как цвет, текстуру и т.д. [2].
В [2] объект описывается некоторыми дескрипторами, называемыми авторами глобальными и локальными. Под глобальными признаками подразумеваются вектора признаков, полученные при анализе всего изображения в целом (например, цвет, текстура). Поиск по глобальным дескрипторам применяется при решении задачи поиска по запросу - образцу тех изображений, которые визуально и семантически похожи. Под локальными признаками подразумевается вектора признаков, которые описывают не все изображение в целом, а какие - то его небольшие части. Также в работе [5] признаки объектов на цифровых изображениях разделены на первичные и вторичные. Первичные признаки — это такие признаки, которые вычисляются с помощью цифрового изображения. Вторичные вычисляются на базе первичных.
Методы поиска по локальным дескрипторам применяются в основном для решения задач поиска нечетких дубликатов и поиска заданного фрагмента на изображениях коллекции [2]. В работе [6] рассматриваются нечеткие дубликаты. Два изображения, которые могут быть переведены друг в друга путем элементарных преобразований, таких как поворот, сдвиг, изменение угла обзора, изменение разрешения, изменение масштаба, изменение освещения, называются нечеткими дубликатами. Примерами нечетких дубликатов являются снимки, сделанные с различных ракурсов, при различном освещении, в различные моменты времени, при помощи различных регистрирующих устройств. Заметим, что нечеткими дубликатами являются в том числе отредактированные изображения.
Для поиска таких нечетких дубликатов в [6] был предложен метод, основанный на выявлении и сопоставлении точечных особенностей изображений. В [2] точечной особенностью называется точка изображения, структура окрестности которой ковариантная заданным преобразованиям изображения. Для нахождения этих особенностей 5
разрабатываются различные методы - детекторы. Результатом методов - детекторов является множество особых точек, для которых строиться математическое описание. Для этих особых точек рассчитываются дескрипторы, описывающие структуру окрестности точечной особенности. Дескрипторы строятся на основании информации об интенсивности, цвете и текстуре особой точки. Также особыми точками могут являться углы, ребра или даже контур объекта.
Рассмотрим различные виды дескрипторов, которые представлены в работе [5].
Геометрические признаки
Геометрические признаки вычисляются локально. К геометрическим признакам можно отнести: особые точки объекта, границу объекта, форму объекта, размеры объекта.
Приведем пример таких признаков.
♦ Особыми точками для отрезка являются две его конечные вершины.
♦ Размерными признаками являются количество пикселей объекта, его длина, ширина.
В работе [7] описаны методы определения геометрических параметров и анализа пространственного положения объектов.
Яркостные признаки
Яркостные признаки описывают изменения локальной энергии изображения, то есть перепады в яркостях пикселей, составляющих изображение. К яркостным признакам можно отнести: экстремумы, частотные признаки, гистограммные признаки, моменты.
Поясним эти признаки.
♦ Экстремум объекта — максимальное или минимальное значение пикселя.
♦ Частотные признаки используются для обнаружения краев, границ, угловых щель.
♦ К гистограммным признакам относят среднее значение, стандартное отклонение, искажение.
В работе [8] предлагается использовать цветовые признаки. Для этого строится цветовая гистограмма, учитывающая пространственное расположение цветов, и вычисляются цветовые моменты. Для оценки подобия двух изображений сравниваются параметры распределения их цветов: математическое ожидание по каждому из цветовых каналов и попарные ковариации распределений каналов.
В работе [9] рассматривается возможность цветовой модели HIS (Hue, Saturation, Intensity). HSI — это цилиндрическое представление цветовой модели RGB, состоящее из компонент: цветовой тон, насыщенность и интенсивность. Автор также предлагает использовать модель HLD (Hue Layout Descriptor).
Текстурные признаки
Текстура есть повторение текселей. Тексель содержит несколько пикселей, расположение которых периодичное, квазипериодчное или случайное. Текстурными признаками являются: угловой момент второго порядка, контраст, корреляция, сумма дисперсий, сумма энтропии, энтропия.
В работе [7] приведен обзор текстурных признаков. Дано краткое описание каждого признака. Рассмотрена проблема выбора информативных признаков.
Бинарные признаки
Бинарные признаки могут иметь только два значения. При сравнении двух бинарных признаков можно сделать единственный вывод о совпадении или несовпадении значений признаков.
Комбинированные признаки
Комбинированные признаки — это комбинация текстурных, геометрических и яркостных признаков.
В работе [10] предлагается дескрипторы условно разделить на следующие категории:
1. Дескрипторы на основе вероятностных распределений. Для этой категории дескрипторов фрагмент изображения используется для построения оценки некоторого распределения вероятностей.
2. Дескрипторы на основе спектрального и спектрально - частотного представления. Дескрипторы этого класса формируются как функции отсчётов спектрального или спектрально - частотного разложения анализируемого фрагмента изображения .
3. Дифференциальные дескрипторы. Дескрипторы этой категории рассчитываются как функции частных производных функции яркости анализируемого изображения .
4. Дескрипторы, конструируемые на основе дифференциальных и вероятностных свойств локальной окрестности наблюдаемого изображения. Спецификой дескриптора является наличие априори заданного (или заранее определённого по обучающему множеству изображений) вероятностного распределения поля градиента, характеризующего модель анализируемого изображения и/или решаемую задачу.
Также на данный момент актуальны задачи поиска трёхмерных моделей. Данная задача является одной из самых сложных в области компьютерного зрения, поскольку для ее решения требуется эффективный и робастный алгоритм сравнения трёхмерных полигональных моделей произвольной формы. Один из подходов к этому основан на глобальных дескрипторах поверхности, содержащих информацию о форме всей поверхности модели в сжатом и ёмком виде. В статье [11] представлены новые глобальные дескрипторы поверхности, названные интегральными спиновыми изображениями. Также предложен специальный метод нормализации трёхмерной модели для вычисления интегрального спинового изображения. В статье показано, что новый метод сравнения моделей с использованием интегральных спиновых изображений обеспечивает адекватную меру похожести формы моделей и может успешно применяться в системах поиска трёхмерных моделей.
1. В данной работе рассмотрены дескрипторы: усредненные значения яркости по красному, зеленому и синему каналам (модель RGB) с учетом или без учета ряда светлых и темных уровней яркости; усредненные значения преобразования Фурье - спектра по тем же каналам; гистограммы; моменты Хью. Изучалось распределение этих признаков по коллекциям изображений. Показано, что тестовые и обучающие выборки по рассмотренным коллекциям, кроме тестовой коллекции мотоциклов, в основном имеют нормальное распределение. Признаки для тестовой коллекции мотоциклов имеют нормальное распределение при сужении диапазона яркости. Для моментов Хью было показано, что практически все моменты за исключением первого имеют нормальное распределение.
2. Сравнивались результаты кластеризации коллекций изображений методами Forel и k - means. В том случае, если цвета изображений близки, то результаты классификации при использовании дескрипторов: усредненные значения яркости по красному, зеленому и синему каналам (модель RGB) без учета ряда светлых и темных уровней яркости и усредненные значения преобразования Фурье - спектра по тем же каналам, то уровень ошибки больше, чем ошибка для коллекций, где цвета изображений различаются по средним значениям яркости. Это можно объяснить тем, что добавление к коллекции объектов, не совпадающих по основному цвету, приводит к большему различию средних значений.
3. Уровень ошибки для классификатора Байеса по парам коллекций составляет 0%. Дополнение коллекции нестандартными изображениями привело к ошибке равной 7%. Это можно объяснить тем, что число пикселей фона изображения превосходит числа пикселей самого объекта. Из этого можно сделать вывод о необходимости предварительной обработки изображения или привлечения других дескрипторов.
4. Результаты исследований опубликованы в сборниках статей: молодежная научная конференция «Все грани математики и механики» [17]; восьмая Сибирская конференция по параллельным и высокопроизводительным вычислениям [20], и в сборнике трудов конференции ВМНК "Все грани математики и механики". Из них две зарегистрированы в базе РИНЦ.
5. Программы и результаты планируется использовать в качестве учебно-методических материалов в курсе <<Математическое моделирование>>, который читается на механико-математическом факультете для направления подготовки “Математика и компьютерные науки”.
2. Сравнивались результаты кластеризации коллекций изображений методами Forel и k - means. В том случае, если цвета изображений близки, то результаты классификации при использовании дескрипторов: усредненные значения яркости по красному, зеленому и синему каналам (модель RGB) без учета ряда светлых и темных уровней яркости и усредненные значения преобразования Фурье - спектра по тем же каналам, то уровень ошибки больше, чем ошибка для коллекций, где цвета изображений различаются по средним значениям яркости. Это можно объяснить тем, что добавление к коллекции объектов, не совпадающих по основному цвету, приводит к большему различию средних значений.
3. Уровень ошибки для классификатора Байеса по парам коллекций составляет 0%. Дополнение коллекции нестандартными изображениями привело к ошибке равной 7%. Это можно объяснить тем, что число пикселей фона изображения превосходит числа пикселей самого объекта. Из этого можно сделать вывод о необходимости предварительной обработки изображения или привлечения других дескрипторов.
4. Результаты исследований опубликованы в сборниках статей: молодежная научная конференция «Все грани математики и механики» [17]; восьмая Сибирская конференция по параллельным и высокопроизводительным вычислениям [20], и в сборнике трудов конференции ВМНК "Все грани математики и механики". Из них две зарегистрированы в базе РИНЦ.
5. Программы и результаты планируется использовать в качестве учебно-методических материалов в курсе <<Математическое моделирование>>, который читается на механико-математическом факультете для направления подготовки “Математика и компьютерные науки”.