Аппроксимация геометрических преобразований изображений с помощью многочленов

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость новой

Детальная информация о работе

Выдержка из работы

Толкачев Данил Сергеевич
АППРОКСИМАЦИЯ ГЕОМЕТРИЧЕСКИХ ПРЕОБРАЗОВАНИЙ ИЗОБРАЖЕНИЙ С ПОМОЩЬЮ МНОГОЧЛЕНОВ
В статье предложена аппроксимация двумерных таблиц геометрического преобразования изображений с помощью многочленов. Представлен метод аппроксимации по методу наименьших квадратов. Описаны схемы вычисления значения полинома с помощью схемы Горнера и метода конечных разностей. Проверена корректность предлагаемой аппроксимации применительно к задаче коррекции геометрических искажений объектива камеры.
Адрес статьи: www. gramota. net/materials/1/2013/10/53. html
Статья опубликована в авторской редакции и отражает точку зрения автора (ов) по рассматриваемому вопросу.
Источник
Альманах современной науки и образования
Тамбов: Грамота, 2013. № 10 (77). C. 170−173. ISSN 1993−5552.
Адрес журнала: www. gramota. net/editions/lhtml
Содержание данного номера журнала: www. gramota. net/materials/1 /2013/10/
© Издательство & quot-Грамота"-
Информация о возможности публикации статей в журнале размещена на Интернет сайте издательства: www. gramota. net Вопросы, связанные с публикациями научных материалов, редакция просит направлять на адрес: almanaс@gramota. net
УДК 004.9 Технические науки
В статье предложена аппроксимация двумерных таблиц геометрического преобразования изображений с помощью многочленов. Представлен метод аппроксимации по методу наименьших квадратов. Описаны схемы вычисления значения полинома с помощью схемы Горнера и метода конечных разностей. Проверена корректность предлагаемой аппроксимации применительно к задаче коррекции геометрических искажений объектива камеры.
Ключевые слова и фразы: геометрическое преобразование изображений- коррекция геометрических искажений- дисторсия- схема Горнера- метод конечных разностей.
Толкачев Данил Сергеевич
Инженерно-технологическая академия Южного федерального университета dandur. oak@gmail. com
АППРОКСИМАЦИЯ ГЕОМЕТРИЧЕСКИХ ПРЕОБРАЗОВАНИЙ ИЗОБРАЖЕНИЙ
С ПОМОЩЬЮ МНОГОЧЛЕНОВ®
Типичной задачей в области цифровой обработки изображений является геометрическое преобразование изображений [5, с. 277], например, вращение или масштабирование. Геометрические преобразования также применяются при исправлении дисторсии (геометрических искажений) камеры [6, р. 396], построении панорамных изображений [7] и др. Геометрические преобразования определяют зависимость между точками на исходном и преобразованном изображении и чаще всего определяются в виде функций прямого или обратного отображения:
u = М (^), (1а)
^ = М-1^), (1б)
где u'-=[u'-, у] - координаты исходного изображения, а u=[u, V] - координаты преобразованного изображения. Использование функции обратного отображения (1б) предпочтительнее, так как позволяет избегать наложений и дыр, которые могут возникнуть при применении функции прямого отображения, а также облегчает задачу интерполяции [5, с. 278].
Рассмотрим задачу исправления дисторсии камеры, как наиболее часто встречающуюся на практике при использовании широкоугольной оптики. Модель искажений, вносимых объективом камеры, определяется характеристиками объектива. Например, модель искажений может быть определена тремя коэффициентами радиальных искажений, k2, kз и двумя коэффициентами тангенциальных искажений р1 и р2 следующим образом:
й = {и-иЛ! /
~ Л, г (2а)
2 ~2 ~2 г =и +у ,
и'= й{ + к1г + к2г + к3г) + 2р1й& gt- + р2(г +2м), (26)
Vі = у (1 + к1г2 + к2г4 +къг6) + 2р2 йV + рх (г2 +2у) —
и=/яи+и0,
,, (2в)
V =/& gt-'-+У0-
где [и0, у0] и [ ^] - координаты центра изображения (точка пересечения оптической оси и плоскости) и фокусные расстояния по обеим осям для выходного изображения- параметры [и0, у0] и [^, fl] определены аналогично для исходного изображения.
Вычисление выражения (2б) для одной точки требует выполнения 14 умножений при условии хранения результатов промежуточных вычислений, что является весьма затратным при обработке видео в режиме реального времени. Распространенное решение в этом случае: предварительно рассчитать значения функции обратного отображения для всех возможных точек преобразованного изображения. Для выходного изображения размера потребуются две таблицы Цу, и) и У{у, и), где и=0, 1, …, м& gt- - 1- у=0, 1, …, h — 1. Такой подход требует постоянного хранения в памяти таблицы заранее рассчитанных значений функции (1б) и, следовательно, регулярного обращения к этой области памяти, что может представлять трудности в случае реализации алгоритма исправления геометрических искажений на программируемых логических интегральных схемах (ПЛИС). Предлагается следующее решение этой проблемы.
(r) Толкачев Д. С., 2013
Рассмотрим многочлен степени п вида
Дх) = а0 + а1 х + а1×2 + … + ап-1 хп-1 + ап хп. (3)
Вычисление значений такого многочлена эффективно реализуется с помощью схемы Горнера [4, с. 284], при этом многочлен записывается в следующей форме:
Дх) = а0 + х (а1 + х (а2 + … х (а"_1 + ап х) …)). (4)
Несмотря на простоту, такой подход позволяет вычислить значение многочлена за п операций сложения и п операций умножения. Другой способ вычисления значений полинома, позволяющий обойтись исключительно операциями сложения, что во многих случаях позволяет повысить быстродействие, известен как метод конечных разностей [3, с. 668]. Для многочлена (3) рассмотрим следующие разности:
До (х) = Р (х),
Д/+1 (х) = Д,+1 (х + 1) — Д,(х), (5)
где і = 0, 1, …, п — 1. Из (5) напрямую следует, что Р (х + 1) = Д0(х + 1),
Ді+1 (х + 1) = Д-(х) — Ді+1 (х). (6)
Можно доказать, что конечная разность п-го порядка Дп (х) будет одинаковой при любых х. Полученные итерационные соотношения (6) позволяют вычислить значения многочлена в точке х+1 при известных значениях многочлена Р и разностей Д,(х) для,=0, 1, …, п в точке х. Раскрывая выражения (5), получаем следующие начальные значения разностей Д, для многочлена степени п = 5 при х = 0:
До (0) = а0,
Д1(0) = а1 + а2 + а3 + а4 + а5,
Д2(0) = 2а2 + 6а3 + 14а4 + 30а5, (7)
Д3(0) = 6а3 + 36а4 + 150а5,
Д4(0) = 24а4 + 240а5,
Д5(0) = 120а5.
Таким образом, алгоритм вычисления значений многочлена с помощью метода конечных разностей следующий:
1. Получить начальные значения разностей Д, в точке х=0 по формулам (7). Значение многочлена в этой точке Р (0)=Д0.
2. Для получения каждого следующего значения многочлена необходимо согласно формулам (6) итерационно обновить значения Д, а затем запомнить Д0 как значение многочлена.
Первый шаг алгоритма можно опустить, если в качестве входных данных использовать не коэффициенты полинома а, а предварительно рассчитанные разности Д,. Таким образом, для вычисления одного значения многочлена требуется всего п — 1 операций сложения.
Рассмотрим теперь задачу аппроксимации некоторого набора точек (хі, у), і = 0, 1, ., т с помощью многочлена заданной степени п. Подставляя хі иуі в (3), получаем следующую систему уравнений:
(8)
Первый множитель системы уравнений (8), называемый матрицей Вандермонда, обозначим как X. Векторами а=(а0, аь …, ап) и у=(у0, у, …, ут) обозначим соответственно коэффициенты полинома и аппроксимируемые значения. Таким образом, система уравнений (8) может быть представлена в краткой записи:
Xa = у.
При т& gt-п система является переопределенной и не имеет точного решения. В том случае, если требуется аппроксимировать данные, не содержащие некорректных значений (выбросов), разумно применить метод наименьших квадратов. Обозначим разность исходных и аппроксимированных значений, также называемую остатками, как e=y-Xa. При решении системы (8) по методу наименьших квадратов находятся такие коэффициенты a многочлена (3), что сумма квадратов разностей остатков e является минимальной: а = а^т^ (Р (х) — у1)2.
'- хП хГ1 •• *0 1 an У0
& lt- хГ •• *1 1 ап-1 = л
с1 & quot- Хш 1 _ a0 _ _ ym _
Сумма квадратов остатков также может быть записана в следующем виде: ?(Р (х,) — у,.)2 = ете = (у — Хя) т (у — Ха).
Дифференцируя по, а и приравнивая производную к 0 (в этом случае ошибка е е будет минимальной), получаем:
(ХтХ)а = Хту, откуда находим, а = (ХтХ) -1Хту = Х+ у,
здесь Х+ = (ХтХ) 1Хт является псевдообратной матрицей [1, с. 178], которая может быть найдена с помощью сингулярного разложения [2, с. 260].
Выше была рассмотрена аппроксимация многочленами одномерных функций, а таблицы функции обратного отображения и (ы,^) и У (и^) двумерны. Для перехода к двумерному случаю предлагается следующий
А
подход. Каждая у-я строка таблицы (пусть для определенности это будет таблица Ц) аппроксимируется многочленом степени п построчно (т.к. зачастую изображение хранится в памяти построчно):
Ц (у, и) ~ Rv (u) = г0(у) + Г (у)и + г2(у)и2 + … + гп (у)ип.
Далее по формулам, подобным (7), осуществляется переход от коэффициентов г/у), /=0,1,. ,., п многочленов к начальным значениям конечных разностей Др (у). Полученные коэффициенты Д/у) рассматриваются как функции от номера строки у. Если таблица Ц является гладкой функцией, то и разности Д (у) также будут гладкими, и следовательно, их также возможно аппроксимировать многочленом степени т:
Др (у) ~ С/(у) = С/0 + /у + Сру2 + … + Ср"ут.
Наконец, эти многочлены представляются в виде набора разностей 8/, г-0,1, …, т, полученных по формулам (7) из коэффициентов Ср. В результате исходная таблица Цу, и) размера w^h упаковывается в таблицу коэффициентов 8/ размера (т+1)*(п+1), г=0,1, …, п-р = 0,1, …, т. Аналогичным образом упаковывается таблица У (у, и).
При аппроксимации многочленами необходимо подобрать степени полиномов т и п таким образом, чтобы с одной стороны обеспечить достаточную точность аппроксимации, а с другой стороны избежать нежелательных осцилляций аппроксимирующей функции, которые могут возникнуть при ее высоких порядках (подобных феномену Рунге [Там же, с. 118]).
Распаковка двумерной таблицы разностей А/ может быть осуществлена по следующему алгоритму:
1. Принять, что номер строки у=0.
2. Копировать Др — 8/0, для/ = 0,1,., п.
3. Принять, что номер столбца и = 0.
4. Записать в выходную таблицу значение Ц (и, у) = До.
5. Если текущий элемент — последний в строке (и=^-1), перейти к 8.
6. Обновить значения Др — Др + Др + 1, для/ = 0,1, ., п — 1.
7. Обновить номер столбца и — и + 1 и перейти к 4.
8. Если текущая строка последняя (у^-1), завершить работу алгоритма.
9. Для всех/=0,1, …, п и г=0,1, …, т — 1 обновить коэффициенты 8/ - 8/ + 8/ +
10. Обновить номер строки у -- у + 1 и перейти к 3.
В качестве иллюстрации рассмотрим применение описанного способа аппроксимации таблиц Цу, и) и У (у, и) для сжатия таблиц исправления геометрических искажений. На Рисунке 1 приведено разностное изображение исходных и аппроксимированных таблиц преобразований. Темные тона соответствуют максимальной абсолютной разности, светлые — минимальной. Среднеквадратичное отклонение значений, аппроксимированных от значений исходных таблиц, составило около 0,014 пикселя, а максимальное абсолютное — около 0,08 пикселя, что значительно превосходит точность калибровки камеры (в конкретном случае порядка 0,5 пикселя).
а) б)
Рис. 1. Разностные изображения для исходных и аппроксимированных таблиц: а) для таблицы Ц (у, и) — б) для таблицы У (у, и)
На Рисунке 2 приведены примеры преобразования изображений на основе описанной схемы аппроксимации таблиц функции обратного отображения. Корректность аппроксимации можно проконтролировать по разности изображений, полученных на основе исходных и аппроксимированных таблиц (Рис. 2в). Для синтезированного изображения максимальное значение абсолютной разности составило 14 уровней из 255, для реального изображения меньше — 3 уровня из 255.
а) б) в)
Рис. 2. Применение аппроксимированных таблиц преобразования для исправления геометрических искажений объектива: а) исходное изображение- б) преобразованное изображение- в) разностное изображение.
Верхний ряд — синтезированное изображение, нижний ряд — изображение калибровочной таблицы
Таким образом, предложенная модель аппроксимации таблиц геометрического преобразования изображений позволяет без существенных погрешностей сократить объем долговременной памяти, необходимой для хранения таблиц.
Список литературы
1. Беклемишев Д. В. Дополнительные главы линейной алгебры. М.: Наука (Главная редакция физико-математической литературы), 1983. 336 с.
2. Каханер Д., Моулер К., Нэш С. Численные методы и математическое обеспечение / пер. с англ. М.: Мир, 1998. 575 с.
3. Корн Г., Корн Т. Справочник по математике (для научных работников и инженеров). М.: Наука, 1973. 832 с.
4. Левитин А. Алгоритмы: введение в разработку и анализ / пер. с англ. М.: Издательский дом «Вильямс», 2006. 576 с.
5. Яне Б. Цифровая обработка изображений. М.: Техносфера, 2007. 584 с.
6. Bradski G., Kaehler A. Learning OpenCV. Sebastopol: O’Reilly, 2008. 555 p.
7. Szeliski R. Image Alignment and Stitching: a tutorial // Foundations and Trends® in Computer Graphics and Vision. 2006. Vol. 2. № 1. P. 1−104.
APPROXIMATION OF IMAGES GEOMETRICAL TRANSFORMATIONS WITH POLYNOMIALS
Tolkachev Danil Sergeevich
Engineering-Technological Academy of Southern Federal University dandur. oak@gmail. com
In the article the approximation of the two-dimensional pictures of images geometrical transformation with polynomials is suggested. Approximation method according to the technique of least squares is introduced. The schemes of polynomial evaluation with Horner’s and finite difference methods are described. Such approximation correctness with regard to the problem of camera lens geometrical distortions correction has been tested.
Key words and phrases: images geometrical transformation- geometrical distortions correction- distortion- Horner’s method- finite difference method.

Показать Свернуть
Заполнить форму текущей работой