Распознавание изображений логотипов компаний
Представлено действие алгоритма, который показывает хорошие результаты на сложных многокомпонентных логотипах, которые могут иметь сложные градиенты. Преимуществом данного алгоритма является линейное по количеству точек изображения время работы.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 19.01.2018 |
| Размер файла | 693,0 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
РАСПОЗНАВАНИЕ ИЗОБРАЖЕНИЙ ЛОГОТИПОВ КОМПАНИЙ
М.С. Пихенько (pikhenko@gmail.com)
Московский Физико-Технический Институт (Государственный университет), Москва
Представлен алгоритм распознавания, дающий хорошие результаты на многокомпонентных логотипах и обладающий малым временем работы.
В данной работе представлен алгоритм распознавания логотипов компаний, дающий хорошие результаты на определенном классе логотипов.
Постановка задачи. Есть серое изображение логотипа компании - . Есть множество изображений логотипов компаний - .Нужно определить какому из изображений множества соответствует изображение.
Данная задача возникла из задачи классификации отсканированных документов, но имеет интерес и в других областях, так как большое количество изображение обладают свойствами логотипов - могут состоять из одноцветных областей, часто имеют ровные границы, плавные градиенты.
В данной работе представлен алгоритм, который показывает хорошие результаты на сложных многокомпонентных логотипах, которые могут иметь сложные градиенты. Преимуществом данного алгоритма является линейное по количеству точек изображения время работы.
В настоящее время существует довольно много статей по данной тематике, практически во всех используется черно-белое изображение логотипа, в отличие от серого, рассматриваемого в данной работе. Использование серого изображения позволяет использовать больше информации о логотипе. Использование же бинаризованного изображения может породить различные труднопреодолимые трудности. Так, если изображение было неравномерно засвечено, то некоторые части логотипа могут отсутствовать на черно-белом изображении.
В настоящее время существует довольно много алгоритмов, позволяющих классифицировать логотипы с небольшим количеством составных частей, например[Neumannetal.], [Doermannetal., 1993],однако не существует алгоритмов, которые покрывают все множество существующих логотипов.
Последовательность действий алгоритма
1. Первичное выделение границ логотипа.
2. Бинаризация
3. Выращивание областей
4. Выделение скелета
5. Соединение разрывов и удаление шума
6. Выделение связных компонент
7. Генерация гипотез
8. Проверка гипотез и выбор лучшей.
Первичное выделение границ логотипа
Первичное выделение границ логотипа осуществляется с помощью особого градиентного оператора. Пусть дано серое изображение . Будем использовать градиентный оператор G следующего вида:
, где
распознавание изображение логотип алгоритм
Причем окрестность O имеет одинаковую форму для всех точек изображения I. Точки изображения, не входящие в область определения, считаем равными 0. Типичный размер окрестности - 3x3, 4x4, 5x5.
Бинаризация. Бинаризация осуществляется по методу Ниблэка ([Гонсалес и др.,2005]). Этот метод является локальным адаптивным и позволяет достичь большой скорости обработки изображения. Идея данного метода состоит в подборе порога яркости B на основании значения стандартного отклонения в локальной окрестности. Порог яркости в точке (x, y) рассчитывается так:
,
среднее значение яркости.
стандартное отклонение яркости.
Здесь #O(x, y) - количество точек в окрестности O точки (x, y).
Выращивание областей
В алгоритме выращивания областей используется 2 изображения: исходное, над которым проводилась бинаризация, и бинаризованное.
В качестве центров роста областей выступает бинаризованное изображение.
На первом этапе в белый цвет красятся все точки, удовлетворяющие следующему условию:
1) У точки есть белый сосед на бинаризованном изображении.
2) Разность яркостей точки и ее белого соседа меньше заданной константы.
Алгоритм продолжается рекурсивно до тех пор, пока будут добавляться новые точки.
Этот алгоритм параметрический и допускает различные модификации. Например, константа может зависеть от номера итерации и от яркости.
Алгоритм выделения скелета области
Данный алгоритм является итерационным алгоритмом с локальным окном. Впервые он предложен в статье [Zhangetal., 1984].
Ниже представлена блок-схема алгоритма.
Соединение разрывов и удаление шума
Полученное изображение может содержать разрывы линий, которые препятствуют эффективному выделению связанных компонент логотипа. Поэтому производится соединение разрывов. Для этой цели можно использовать различные алгоритмы, например алгоритм Хафа, который позволяет замыкать прямолинейные отрезки, дуги окружностей и др. Как показала практика, для данной задачи более применим алгоритм, описанный далее.
1. Выделяются все границы - каждая в свою отдельную связную компоненту.
2. Для каждой связной компоненты находятся конечные точки - их считаем разрывами. Если площадь связной компоненты меньше порога - это шум, удаляем.
3. Для каждой такой точки определяем ближайшую, обладающую таким же свойством. Соединяем их, если отрезок не пересекает уже существующие линии.
Данные этапы проделываются несколько раз. Затем опять находятся все точки разрыва и соединяются со своими ближайшими соседями из другой связной компоненты, таким образом, практически не остается точек разрыва.
Рис. 1. Выделенные связные компоненты
Выделение связных компонент
Для выделения связных компонент использовался алгоритм последовательного сканирования ([Вежневец, 2003]). Этот алгоритм позволяет за 2 прохода изображения выделить связные компоненты.
Ниже представлены шаги применения алгоритма (слева направо, сверху вниз).
Сопоставление связных компонент эталона и тестового образца
Каждую связную компоненту опишем вектором из 7 компонент, которые есть логарифмы инвариантных моментов. В качестве решающего правила выберем такое:
.
Здесь N=7 - количество компонент, вектор тестового образца; вектор эталона; вектор допустимых отклонений, б порог, выбираются опытным путем.
Составим двудольный граф . Здесь - множество связанных компонент эталона, - множество связанных компонент проверяемого логотипа, - множество ребер изв, причем ребро из вершины в вершину проводится только в случае, если вершины удовлетворяют условию(1.1).
Из этого графа нужно выбрать паросочетание, которое:
1. Дает экстремум некой функции, которая отвечает взаимному расположению связанных компонент друг относительно друга.
2. Имеет как можно большую мощность.
Проверка всех паросочетаний - задача,NP-трудная, поэтому поступим иначе.
- множество гипотез, каждая гипотеза состоит в предположении, что мы правильно определили сопоставление двух пар вершин. Каждая гипотеза - это уже паросочетание мощности 2 (по количеству ребер). Достроим его до максимально возможного с учетом сопоставления других вершин.
Рис. 2. Достраивание паросочетания
Каждую из оставшихся вершин первой доли опишем вектором из 4 величин:
1. Расстояние до первой вершины b.
2. Расстояние до второй вершины a.
3. Угол.
4. Знак векторного произведения выделенных на рисунке векторов.
Таким же образом опишем соединенные с этой вершиной вершины второй доли, только расстояния будут домножены на коэффициент масштабирования, который можно вычислить из определения гипотезы следующим образом:
Здесь d - расстояние между вершинами второй доли, - площади связных компонент первой и второй вершин из второй доли. Штрихованные величины - аналогично нештрихованным, только в первой доле. Если все 3 коэффициента не лежат в одной небольшой окрестности, то отбраковываем такую гипотезу.
Если эти вектора удовлетворяют следующему условию, то добавляем соответствующее ребро между долями, и рассматриваем следующую вершину. Условие:
1) компоненты 1. и 2. отличаются не более чем на заданную относительную погрешность;
2) компоненты 3. отличаются не более чем на заданную абсолютную погрешность
3) Компоненты 4. совпадают.
Среди всех гипотез выберем одну, которой соответствует паросочетание с максимальным количеством ребер, - это количество и будет числом отождествленных компонент.
Рис. 3. Пример работы алгоритма.
Практические результаты. Алгоритм работает только на определенном классе логотипов G, а именно: многокомпонентные логотипы с не очень резкими градиентами. Вероятность того, что логотип будет отождествлен с эталоном, есть:
Здесь I - множество логотипов, отождествимых с эталоном.
вероятность отождествить логотип с эталоном, если он принадлежит G. Аналогично вероятность отождествить, если логотип не принадлежит G:
Здесь r - допустимое минимальное число отождествленных связных компонент, при которых логотип считается тождественным эталону.
Был проведен эксперимент и получены значения , . Тестовые выборки были 1404 и 10000 элементов соответственно. Видно, что вторым слагаемым можно пренебречь.
Заключение. В статье описан алгоритм распознавания логотипов, который показывает хорошие результаты на многокомпонентных логотипах без большого количества резких градиентов. К преимуществам можно отнести большую скорость работы (все этапы алгоритма делаются за линейное по количеству точек логотипа время, а этап перебора гипотез, ввиду ограничения максимального их количества, за O(1).). К недостаткам можно отнести неприменимость данного алгоритма к простым малокомпонентным логотипам.
Список литературы
1. [Вежневец, 2003]Вежневец А. Выделение связных областей в цветных и полутоновых изображениях. Компьютерная графика и мультимедиа. Выпуск №1(5)/2003. http://cgm.computergraphics.ru/content/view/53.
2. [Гонсалес и др., 2005] Гонсалес Р., Вудс Р. Цифровая обработка изображений. Москва: Техносфера, 2005.
3. [Гонсалес и др., 2006] Гонсалес Р., Вудс Р. Цифровая обработка изображений в среде MATLAB. Москва: Техносфера, 2006.
4. [Яне, 2007]ЯнеБ. Цифровая обработка изображений. Москва: Техносфера, 2007.
5. [Doermann et al., 1993] David S. Doermann et al. "Logo Recognition Using Geometric Invariants" 1993.
6. [Neumannet al.]NeumannJ., Samet H. and Soffer A. "Integration of Local and Global Shape Analysis for Logo Classification".
7. [Zhanget al., 1984] ZhangT. Y., SuenC. Y.A Fast Parallel Algorithm for Thinning Digital Patterns.CommunicationsoftheACM.March 1984, Volume 27, Number 3.
Размещено на Allbest.ru
...Подобные документы
Этапы разработки системы реального времени для распознавания лиц на статическом изображении в условиях сложных сцен. Основные понятия алгоритма AdaBoost. Использование примитивов Хаара для описания свойств изображений. Среда разработки "Borland Delphi".
курсовая работа [6,8 M], добавлен 06.01.2011Методы предобработки изображений текстовых символов. Статистические распределения точек. Интегральные преобразования и структурный анализ. Реализация алгоритма распознавания букв. Анализ алгоритмов оптического распознавания символов. Сравнение с эталоном.
курсовая работа [2,1 M], добавлен 20.09.2014Описание принципа работы генетического алгоритма, проверка его работы на функции согласно варианту на основе готовой программы. Основные параметры генетического алгоритма, его структура и содержание. Способы реализации алгоритма и его компонентов.
лабораторная работа [20,2 K], добавлен 03.12.2014Постановка задачи и ее математическая модель. Блок-схема алгоритма обработки массивов координат точек. Тестирование алгоритма сортировки. Используемые глобальные и локальные переменные. Листинг программы на языке Си. Анализ результатов. Пример работы.
курсовая работа [1,8 M], добавлен 08.11.2012Разработка алгоритма, который может выполнить расчет определения координат точек кинематической схемы и выполнить анимацию (визуальное отображение перемещений объектов) кинематической схемы с использованием пакета MathCad. Расчет кинематической схемы.
курсовая работа [1,1 M], добавлен 10.07.2012Сравнение результатов работы генетического алгоритма по решению "несимметричной незамкнутой задачи коммивояжера" с результатами работы алгоритма динамического программирования по параметрам - время работы, точность результата и объем используемой памяти.
курсовая работа [65,3 K], добавлен 16.04.2014Проблема улучшения качества отпечатков пальца с целью повышения эффективности работы алгоритмов биометрической аутентификации. Обзор алгоритмов обработки изображений отпечатков пальцев. Анализ алгоритма, основанного на использовании преобразования Габора.
дипломная работа [4,5 M], добавлен 16.07.2014Основные свойства алгоритма. Формальный и неформальный исполнитель алгоритма, система его команд. Способы записи алгоритма. Словесное описание, построчная запись, опорный конспект. Характеристики алгоритмического языка. Выполнение алгоритма компьютером.
презентация [2,0 M], добавлен 04.04.2014Разработка алгоритма и реализация интеллектуальной информационной системы, позволяющей оценить время в неделю, необходимое для осуществления функций технической поддержки администратора с необходимым уровнем надежности работы локальной сети.
курсовая работа [37,4 K], добавлен 01.12.2009Особенности использования алгоритма Кнута-Морриса-Пратта для определения того, является ли слово A подсловом слова B. Заполнение массива pos согласно алгоритму Бойера-Мура. Сущность алгоритма Рабина как быстрого способа вычисления значения функций.
реферат [21,0 K], добавлен 30.10.2009Состав и принцип работы аппаратуры. Выбор параметров корреляционного анализа и Фурье-анализа. Разработка и применение алгоритма корреляционного анализа. Реализация алгоритма Фурье-анализа на языке С++ и алгоритма корреляционного анализа на языке С#.
дипломная работа [4,6 M], добавлен 30.11.2016Принцип работы алгоритма бинарного поиска в массиве. Способы исследования алгоритма "прямое включение". Формулы зависимости числа сравнений от элементов в массиве. Графики среднего числа сравнений и перемещений практических и теоретических измерений.
курсовая работа [646,1 K], добавлен 07.01.2014Основные характеристики сканеров. Разрешение по X и У. Глубина цвета, максимальная оптическая плотность, тип источника света. Листопротяжный, ручной, планшетный сканер, принцип действия. Распознавание текстов и изображений: точность, причины ошибок.
контрольная работа [27,2 K], добавлен 29.09.2013Разработка программы шифрования данных с использованием алгоритма DES. Структура алгоритма, режимы его работы. Электронный шифровальный блокнот. Цепочка цифровых блокнотов. Цифровая и внешняя обратная связь. Структура окна: функции основных кнопок.
лабораторная работа [830,3 K], добавлен 28.04.2014Общие требования к изображению отрезка с помощью цифрового дифференциального анализатора. Сравнительный анализ обычного и несимметричного алгоритмов и алгоритма Брезенхема для генерации векторов (соединения двух точек изображения отрезком прямой).
презентация [65,3 K], добавлен 14.08.2013Обучение нейронных сетей как мощного метода моделирования, позволяющего воспроизводить сложные зависимости. Реализация алгоритма обратного распространения ошибки на примере аппроксимации функции. Анализ алгоритма обратного распространения ошибки.
реферат [654,2 K], добавлен 09.06.2014Постановка задачи нелинейного программирования. Определение стационарных точек и их типа. Построение линий уровней, трехмерного графика целевой функции и ограничения. Графическое и аналитическое решение задачи. Руководство пользователя и схема алгоритма.
курсовая работа [2,5 M], добавлен 17.12.2012Растровая графика, составление графических изображений из отдельных точек (пикселей). Растровые графические редакторы. Векторная графика - построение изображения из простых объектов. Достоинства, недостатки и применение растровой и векторной графики.
презентация [7,8 K], добавлен 06.01.2014Изучение понятия и свойств алгоритма. Определение сущности технологии Robson. Исполнитель, а также блок-схема алгоритма или его графическое представление, в котором он изображается в виде последовательности связанных между собой функциональных блоков.
реферат [155,9 K], добавлен 19.10.2013Обратная трассировка лучей: ограничения при реализации, достоинства и недостатки. Математические и физические предпосылки алгоритма, блок-схема. Выбор языка программирования. Зависимость времени генерации от глубины рекурсии, количества источников.
курсовая работа [503,0 K], добавлен 27.05.2013
