Поиск по базе сайта:
Пояснительная записка к дипломной работе на тему icon

Пояснительная записка к дипломной работе на тему




НазваПояснительная записка к дипломной работе на тему
Сторінка6/20
Дата конвертації08.07.2013
Розмір1.67 Mb.
ТипПояснительная записка
1   2   3   4   5   6   7   8   9   ...   20
^

1.6.Описание алгоритма преобразования абсолютных параметров минюций к относительным параметрам




1.6.1.Назначение и характеристика алгоритма преобразования абсолютных параметров минюций к относительным


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

Представим структурное представление отпечатка пальцев в виде списка M, содержащего параметры специальных точек:

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

Так как необходимо оценить расстояние между каждой из пар минюций, сложность этих алгоритмов превышает o(N2), где N - количество обнаруженных минюций на изображении отпечатка пальца. В среднем количество точек на отпечатке не превышает 50, таким образом, потребуется 502 = 2500 операций, что является небольшим объемом вычислений. Тесты показывают, что современные пользовательские ЭВМ способны выполнять около операций вычисления расстояния в секунду.

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

1.6.2.Используемая информация


При реализации данного алгоритма используется массив информации, сформированный на предыдущем этапе обработки изображения отпечатка пальца в подсистеме анализа изображения. Каждый элемент массива представляет из себя структуру, содержащую все необходимые для обработки параметры минюций: координаты целого типа – 2х4 байта, угол направления 8 байт, тип точки 1 байт, поэтому общий размер массива должен быть кратен 2*4+8+1 = 17 байт.

,


где Xi, Yi – координаты минюций на растровом представлении изображения отпечатка пальцев, целые числа, величина которых ограничена размером изображения отпечатка в пикселах;

αi – направление предполагаемого продолжения гребня на отпечатке пальцев в точки типа окончание и направление слипания для точки типа раздвоение, дробное число, величина которого изменяется (–pi, +pi);

Тi – тип обнаруженной точки, битовое поле, принимает 2 значения «раздвоение» = 0 (false) и «окончание» = 1 (true);

k – количество минюций на исследуемом отпечатке.

Для обработки массивов используется двунаправленный список. Список представляет собой вектор:



В данную информационную структуру можно заносить и извлекать элементы с любой стороны.
^

1.6.3.Результаты решения


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

Каждый элемент массива содержит описание точки, расстояние до второй точки, угол между собственным направлением точки и направлением во вторую точку, Угол между собственными направлениями двух точек. В табл. 2.3 приведен формат элемента массива.

Таблица 2.3

Структура элемента массивазаписи


Поле

Формат

Описание

lij

Целое

Расстояние между i и j точками

A1ij

Дробное

Угол между собственным направлением точки i и направлением из точки i в точку j. A1ij[0, 2*M_PI)

A2i

Дробное

Угол между собственными направлениями точек i и j. A2ij[0, 2*M_PI)



^

1.6.4.Математическое описание алгоритма преобразования абсолютных параметров минюций к относительным


Обобщенное математическое описание преобразования приведено в п.2.1.4.

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


,


где i, j – минюции

dLengthij – расстояние между точками i и j

dAlpha1ij – угол между направлением точки i и направлением на точку j

dAlpha2ij – угол между направлением точки i и точки j

Alphai – угол вектора самой точки

Alphaij – угол вектора направления от точки i к точке j

На рис. 2.5 представлено расположение точки i относительно точки j со всеми полученными параметрами.


относительные параметры



Рис. 2.5

^

1.6.4.1.Алгоритм нахождения габаритных размеров и количества точек в непрерывной области


  1. Очистить список RelFing с относительными параметрами отпечатка

  2. Если список AbsFing пуст, перейти к пункту 20

  3. Для каждого элемента iterA1 списка AbsFing выполнить пункты 4 - 19

  4. Очистить список listDots с относительными параметрами точки

  5. Для каждого элемента iterA2 списка AbsFing выполнить пункты 5 - 17

  6. Если iterA2 == iterA1, перейти к пункту 5.

  7. l = |GetS(iterA1->coord, iterA2->coord)|

  8. vecAB = GetAlpha(iterA2->coord, iterA1->coord)

  9. tmpa = iterA1->alpha - vecAB;

  10. Если (tmpa < 0), переход к п. 11, иначе переход к п. 12

  11. tmpa = 2*M_PI + tmpa;

  12. a1 = |tmpa * 180.0/M_PI +0.5|

  13. tmpa = iterA2->alpha – iterA1->alpha

  14. Если (tmpa < 0) , переход к п. 15, иначе переход к п. 16

  15. tmpa = 2*M_PI + tmpa;

  16. a2 = |tmpa * 180.0/M_PI +0.5|

  17. Добавить в список listDots параметры очередной точки – l, a1, a2, перейти к п. 5.

  18. отсортировать список listDots

  19. занести относительные параметры точки listDots в список отпечатка RelFing, перейти к п. 3

  20. Конец



^

1.6.5.Требования к контрольному примеру


Контрольный пример должен содержать отпечатки более чем с одной обнаруженной минюцией.

1.6.6.Список условных обозначений


RelFing - список минюций в относительных параметрах

AbsFing - список минюций в абсолютных параметрах

listDots – относительные параметры точки

iterA1 – исследуемая точка в абсолютных параметрах

iterA2 – точка в абсолютных параметрах, относительно которой вычисляется точка iterA1

l – расстояние между точками iterA1 и iterA2

GetS – функция вычисления расстояния

|| - округление до ближайшего целого

vecAB – вектор между направлениями точки iterA1 и iterA2

GetAlpha – функция вычисления угла между векторами

tmpa

a1 = угол между направлением самой точки и направлением на другую точку

a2 = угол между направлениями точек.

1   2   3   4   5   6   7   8   9   ...   20



Схожі:




База даних захищена авторським правом ©lib.exdat.com
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації