|
СодержаниеВведение. 5rnМатематическая теория 8rnПонятие эйлеровой характеристики. 8rnЭйлерова характеристика одномерного изображения. 8rnЭйлерова характеристика двумерных изображений 9rnТопологические свойства и понятия. 10rnХарактеристический набор коэффициентов изображений, построенных на основе прямоугольной решетки 12rnАналоги топологических понятий для изображений. 12rnАналоги топологических операций для изображений. 13rnПостроение характеристического набора коэффициентов 15rnТеорема об эйлеровой характеристике для прямоугольной решетки. 16rnХарактеристический набор коэффициентов черно-белого изображения и некоторые его свойства 17rnРасстояния и другие меры близости на множестве черно-белых цифровых изображений. 22rnРазличение и идентификация подписей………………………………………………...25rnРазличение и идентификация подписей на сравнительном анализе отдельных коэффициентов характеристических наборов………………………………..……………25rnАлгоритм поиска допустимых отклонений коэффициентов…….………………………29rnШкала допустимых отклонений коэффициентов…………………………...…………….30rnРазличение и идентификация на основе расстояний между векторами характеристических наборов……………………………………………………………….39rnСторонние эксперименты.………………………………………………………………….40rnЗаключение…………………………………………………………………………………..42rnСписок литературы………………………………………………………………………….43rnПрограммный код проекта………………………………………………………………….44ВведениеКрупнейший математик XVIII века Леонард Эйлер (1707-1783) родился в швейцарском городе Базеле. С двадцатилетнего возраста он жил в Петербурге, в Берлине, потом снова в Петербурге. Эйлер сыграл выдающуюся роль в развитии математики, механики, физики и техники.rnВ 1758 г. Л. Эйлер опубликовал в \\\"Записках Петербургской академии наук\\\" доказательство формулы.rnДля двумерных изображений формула эйлеровой характеристики имеет вид:rn = В-Р+Г,rnДля одномерных изображений формула эйлеровой характеристики имеет вид:rn= В-Р.rnЭта формула связывает число вершин В, число ребер Р, и число граней Г.rnЕсли задано какое-то множество то, как бы мы ни разбивали его на части (грани, ребра, вершины), определенным образом \\\"примыкающие\\\" друг к другу, сумма В-Р+Г, называемая эйлеровой характеристикой, сохраняет постоянное значение.rnЭйлерова характеристика это число, которое ставится в соответствие фигуре и не изменится при топологических деформациях.rnФормула Эйлера имеет огромное значение в геометрии. Эта формула породила новое направление в математике – топологию. Эйлерова характеристика не зависит ни от длин рёбер, ни от площадей граней, а так же не меняется при увеличении их числа.rn rnтопологически эквивалентныrnrnтопологически эквивалентныrnrnВ данной дипломной работе исследуются расстояния и другие меры близости на множестве цифровых черно-белых изображений зависящие от характеристического набора коэффициентов, полученных благодаря неизменности значения эйлеровой характеристики, анализируются и сами характеристические наборы изображений построенные на основе прямоугольной решетки, а также большая база подписей на предмет их численного различения и определения возможности идентификации человека по его подписи.rnЗадача данной работы состоит в следующем:rn• построение функций для вычисления эйлеровой характеристики rn• изучение характеристического набора коэффициентов черно-белых цифровых изображений rn• получение необходимых условий того, чтобы набор неотрицательных целых чисел являлся характеристическим набором некоторого черно-белого цифрового изображения, rn• построение подхода к численному различению изображений rn• программная реализация алгоритма различения и идентификации подписей на основе определения расстояний и других мер близости для изображений, построенных на прямоугольной решеткеrnВ дальнейшем под цифровым изображением, построенным на основе прямоугольной решетки, понимается изображение, для которого аналогами пикселей являются прямоугольные элементы некоторой прямоугольной решетки, через аij будем обозначать как сам этот элемент, так и значение его цветности. Изображение можно представить в виде матрицы A=(аij) размера m*n, у которой элементы могут принимать значения либо 0, либо 1, т. е черно либо белое изображение.rn rn Фрагментом Si размера 2*2 будем называть фрагменты вида:rnПри вычислении возникает вопрос: связно ли множество такого типа: rnrnrnСуществует такая функция F, для подсчета эйлеровой характеристики изображения, построенного на основе прямоугольной решетки, где:rn ,rnSi – фрагменты вида: S0 S1 S2 S3 S4 S5rn …rnи так далее всевозможные комбинации из черных и белых пикселов. Фрагменты задаются подматрицей из 4 элементов матрицы А:rnai j ai j+1rnai+1 j ai+1 j+1.rnСуществует 16 различных фрагментов такого вида. Набор неотрицательных целых чисел, являющихся количеством фрагментов каждого типа, будем называть характеристическим набором коэффициентов изображения А, построенных по системе фрагментов размера 2х2. Таким образом, вычислив функцию F на всевозможных фрагментах данного изображения, можно вычислить эйлерову характеристику изображения.rnВ работе используется построение аналогов расстояний на основе понятия характеристического набора коэффициентов черно-белого изображения. rn rn rn rnПредлагаемые подходы позволяют не только решать задачи различения изображений (а подпись у нас будет рассматриваться как черно-белое изображение), но также дают возможность численно оценить меру их сходства.rnТакже в работе описываются свойства характеристических наборов коэффициентов черно-белых изображений, построенных на прямоугольной решетке, выводятся необходимые условия того, чтобы наборы из 16 неотрицательных целых чисел являлись характеристическими наборами коэффициентов для черно-белых цифровых изображений, построенных на основе прямоугольной решетки. Решается задача численного различения и идентификации 300 подписей. При сравнении характеристических наборов подписей использовалось два метода. Первый способ – новая разработка, основанная на поэлементном анализе характеристического набора. Мной был сформирован алгоритм, который позволяет получить шкалу допустимых погрешностей по каждому из коэффициентов для существующей базы подписей. Способ позволяет определять поддельная или истинная вводится подпись. Второй способ – определение расстояний между изображениями, то есть работа с характеристическим набором как с единым целым. Позволяет идентифицировать личность по подписи, если ранее он был занесен в базу.ЗаключениеРаспознавание почерка всегда будет трудоемкой задачей. До получения значимого с коммерческой точки зрения результата в этой области проходят годы - годы исследований, годы разработки и годы воплощения теории в программу, которая могла бы осуществлять хотя бы малую часть наглядной операции - преобразование начерченных человеком кривых в буквы и цифры. Например, международный холдинг Paragon Software Group работает над этим с 1996 года.rnСложно утверждать, что сделан программный продукт, готовый к выходу на рынок. Но можно дальше разрабатывать этот проект, вносить дополнительные параметры и получить что-то конкурентоспособное для дальнейшей реализации на рынке. Отрицательная сторона проекта в том, что человек может свести подпись с образца, подложив его на экран. Следовательно, если буду далее развивать этот продукт, надо будет поработать с четвертым измерением – временем и ввести такой параметр как скорость.rnНе исключено, что если число подписей будет увеличиваться, то в какой-то момент для некоторых образцов может стереться грань между оригиналом и подделкой. Эта программа рассчитана на сравнительно небольшие клиентские базы размером до 3000 человек.rnВ создающихся программах по графологии и криптографии используется масса параметров, огромные матрицы, эллиптические кривые. Главным результатом диплома является получение отличного результата по различению и распознаванию подписей на основе небольших матриц (2500 элементов) и вектора из 15 координат. Эти параметры являются достаточными для реализации поставленной задачи.rnВыполненные задачи:rn• изучен характеристий набор коэффициентов черно-белых цифровых изображений rn• получены необходимые условий того, чтобы набор неотрицательных целых чисел являлся характеристическим набором некоторого черно-белого цифрового изображения rn• построен подхода к численному различению подписей изображений rn• программная реализация алгоритма различения и идентификации подписей на основе определения расстояний и других мер близости для изображений, построенных на прямоугольной решетке.Литература1 Парфенов П.Г. Назарычев С.Л. Об одном подходе к различению элементов из больших совокупностей традиционных систем символов // Моделирование и анализ информационных систем. – Т.13, № 1. – Ярославль 2006. – С.52-54.rn2 Назарычев С.Л. Характеристический набор коэффициентов черно-белого цифрового изображения и его применение к различению алфавитно-цифровых символов // Магистерская диссертация. – Ярославль 2006. – 86 с.rn3 Шашкин Ю.А. Эйлерова характеристика. – М.: Наука, 1984. – 96 с.rn // Популярные лекции по математике.rn4 Прэтт У. Цифровая обработка изображений. Кн.2. М.: Мир, 1982.rn5 Курант Р., Роббинс Г. Что такое математика? под ред. А.Н.Колмогорова. rn пер. с англ. – 3-е изд. испр. и доп. – М.: МЦНМО, 2001. – 564 с.rn6 Розенфельд Ф. Распознавание и обработка изображений с помощью вычислительных машин. М.: Мир, 1972.rn7 Парфенов П.Г. Об эйлеровой характеристике изображения //Архитектура и программное обеспечение вычислительных систем. – Ярославль, 1992. – С.76-79.rn8 Парфенов П.Г. Многочлены на изображениях, вычисляющих эйлерову характеристику // Моделирование и анализ информационных систем.– Т.8, № 2.-rn Ярославль, 2001. – С.3-7.rn9 Парфенов П.Г. Завьялова Л.М. Об эйлеровой характеристике изображений, построенных на основе гексагональной и треугольной решеток //Моделирование и анализ информационных систем. – Вып.2– Ярославль,1994. – С.84-91.rn10 Парфенов П.Г. Завьялова Л.М. Об одном классе аддитивных функций на изображениях // Моделирование и анализ информационных систем. – Вып.3. – Ярославль, 1996. – С.40-45.rn11 Парфенов П.Г. Завьялова Л.М. Об одном подходе к распознаванию изображения букв // Моделирование и анализ информационных систем. – Вып.4. – Ярославль, 1997. – С.40-45rn12 Парфенов П.Г. Некоторые числовые характеристики изображений, инвариантные относительно сдвигов и поворотов // Моделирование и анализ информационных систем. – № 5. – Ярославль 1998. – С.58-61.rn13 Парфенов П.Г. Каплий И.А. Куликов О.С. Расстояния и другие меры близости на множестве черно-белых цифровых изображений. // Моделирование и анализ информационных систем. – Т.12, № 1. – Ярославль 2007. – С.52-54.rn14 Парфенов П.Г. О некоторых свойствах характеристического набора коэффициентов черно-белого цифрового изображения // Моделирование и анализ информационных систем. – Т.12, № 1. – Ярославль 2005. – С.52-54.rnАрхангельский А.Я. Программирование С++ Builder 6 – М.: Бином, 2003 – 1151с.
|
|
