Интерактивное построение панорамных снимков с помощью портативных компьютеров

Пропонується ефективний алгоритмічний комплекс для побудови панорамних знімків. Його швидкодія достатня для використання на більшості сучасних кишенькових комп’ютерів. Така швидкодія досягається завдяки поєднанню різних алгоритмів на низці етапів. На основі алгоритмічного комплексу розроблено програ...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Veröffentlicht in:	Проблемы управления и информатики
Datum:	2013
Hauptverfasser:	Гаращенко, Ф.Г., Кобзарь, А.Ю.
Format:	Artikel
Sprache:	Russisch
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2013
Schlagworte:	Методы обработки информации
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/207681
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Интерактивное построение панорамных снимков с помощью портативных компьютеров / Ф.Г. Гаращенко, А.Ю. Кобзарь // Проблемы управления и информатики. — 2013. — № 6. — С. 90-102. — Бібліогр.: 10 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1860082833408655360
author	Гаращенко, Ф.Г. Кобзарь, А.Ю.
author_facet	Гаращенко, Ф.Г. Кобзарь, А.Ю.
citation_txt	Интерактивное построение панорамных снимков с помощью портативных компьютеров / Ф.Г. Гаращенко, А.Ю. Кобзарь // Проблемы управления и информатики. — 2013. — № 6. — С. 90-102. — Бібліогр.: 10 назв. — рос.
collection	DSpace DC
container_title	Проблемы управления и информатики
description	Пропонується ефективний алгоритмічний комплекс для побудови панорамних знімків. Його швидкодія достатня для використання на більшості сучасних кишенькових комп’ютерів. Така швидкодія досягається завдяки поєднанню різних алгоритмів на низці етапів. На основі алгоритмічного комплексу розроблено програмне забезпечення, яке демонструє ефективність запропонованих розробок. An efficient algorithmic complex for constructing panoramic images is proposed. It has sufficiently high performance to be used on the majority of modern portable devices. High performance has been achieved via combining chosen algorithms on different stages of image processing. A software based on this algorithmic complex, which demonstrates the potency of the submitted research, has been developed.
first_indexed	2025-12-07T17:18:17Z
format	Article
fulltext	© Ф.Г. ГАРАЩЕНКО, А.Ю. КОБЗАРЬ, 2013 90 ISSN 0572-2691 УДК 004.932.2:519.688 Ф.Г. Гаращенко, А.Ю. Кобзарь ИНТЕРАКТИВНОЕ ПОСТРОЕНИЕ ПАНОРАМНЫХ СНИМКОВ С ПОМОЩЬЮ ПОРТАТИВНЫХ КОМПЬЮТЕРОВ Введение. В сфере информационных технологий новшества появляются на стыке двух направлений развития. С одной стороны, увеличивается производитель- ность аппаратного обеспечения, с другой — возрастает эффективность алгоритмов. Методы автоматического построения панорамных снимков известны достаточно давно. Одним из первых появился программный пакет Panorama Tools. Затем про- цесс был автоматизирован с помощью алгоритма SIFT [1], который был воплощен в программе Kolor Autopano. Но скорость работы алгоритмов не позволяла со- здать приложение для маломощных портативных устройств (таких как, мобиль- ные телефоны, фотоаппараты и др.), которое бы выполняло построение панорам в режиме реального времени. Здесь предлагается эффективный алгоритмический комплекс создания панорамных снимков, осуществляемый на большинстве со- временных устройствах такого класса. В рамках проблемы можно выделить три подзадачи: поиск позиции изобра- жения в базе, ее пополнение и проецирование снимков на поверхность. Первая из них используется для отображения снятых изображений на экране видоискателя и как этап алгоритма пополнения. Важным требованием к ней есть быстродей- ствие, поскольку от скорости работы зависит удобство процесса съемки. Вторая содержит основные расчеты, которые должны быть наиболее точными. Использу- ется она при каждом новом снимке. Последняя подзадача является наиболее вычис- лительно трудоемкой, поскольку в ней необходимо обработать все точки изображе- ний; ее можно запускать в фоновом режиме или на отдельном компьютере. Схема алгоритма пополнения такая же, как в SIFT [1] и SURF [2]. Она харак- теризуется многоэтапностью. На каждом из этапов готовятся входные данные для следующего. Рассматриваются такие этапы: 1. Выделение ключевых точек. 2. Описание выделенных точек. 3. Построение пар ключевых точек на базе их описаний. 4. Фильтрация найденных пар. 5. Поиск взаимной ориентации камер. Здесь предлагается описание всех этапов, реализовав которые получают про- граммный комплекс, позволяющий быстро и качественно строить панорамные снимки. Метод сопоставления изображений приведен в [3], где автор предлагает точ- ки искать с помощью оператора Харриса, а среди всех восьмерок точек (по четы- ре из каждого изображения) найти наилучшую, на базе яркостей точек. Такой подход работает неоправданно долго, причем является неустойчивым к изменени- ям освещенности и цветового баланса. В работе [4] вместе с точками используют- ся линии, что усложняет модель. В ней предполагается, что положение камеры изменяется незначительно. Это упрощает процесс поиска соответствий, которые фильтруются алгоритмом RANSAC. Самое полное описание алгоритма построе- ния панорам предлагается в [5]. Сначала для поиска пар точек используется SIFT, затем с помощью методов Левенберга–Марквардта и RANSAC находятся взаим- Международный научно-технический журнал «Проблемы управления и информатики», 2013, № 6 91 ные расположения изображений. Окончательная прорисовка при проектировании выполняется с помощью многополосного смешивания [6] после предварительной линейной коррекции по цветам. Выделение ключевых точек. Алгоритм выделения точек должен удовле- творять таким требованиям как: достаточное количество стабильных точек на вы- ходе, устойчивость к шумам и поворотам, высокая скорость работы и равномер- ное распределение точек по площади изображения. Отметим, что нет необходи- мости делать алгоритм устойчивым к масштабированию, поскольку для всех снимков используется одна и та же камера с фиксированным углом обзора и, как следствие, известным масштабом. Для эффективной работы следующих этапов нужна фиксированная плотность точек по изображению. Меньшее их количество на некотором фрагменте не даст возможности корректной работы, а большее — неоправданно увеличит время работы всего алгоритма. Проанализировав извест- ные алгоритмы, можно сделать вывод, что большинство из них не подходит по тем или иным причинам, в частности, из-за скорости работы и неравномерности распределения найденных точек. Для решения задачи предлагается алгоритм, который основан на операторе выделения границ Кэнни [7]. Вычисляются векторы градиентов для каждой точки изображения, удовлетворяющие условиям:           .))()(( , , 22 4343 22 22 11 22 yxyyyxxx yyxxyx yyxxyx ggggggggk gggggg gggggg Здесь ),( yx gg — градиент в проверяемой точке; ),( 11 yx gg и ),( 22 yx gg — гра- диенты в соседних точках по и против направления градиента );,( yx gg ),( 33 yx gg и ),( 44 yx gg — градиенты в соседних точках, которые берутся в направлении перпендикулярном к );,( yx gg k — пороговое значение, на практике принимается равным 2/3. Первые два неравенства требуют, чтобы модуль гради- ента в проверяемой точке имел локальный максимум в своем направлении. В от- личие от оператора Кэнни здесь условие сформулировано в терминах проекции на прямую градиента для меньшего влияния шумов. Последнее условие отбрасывает случайные точки, которые находятся не на границе. Для отбрасывания несущественных границ найденные точки подвергаются фильтрации. Среди них выбираются только те, для которых выполняется неравенство ,)( Tgggg Nn nyynxx   где ),( yx gg — градиент в проверяемой точке; ),( nynx gg — градиент в точке из окрестности; N — множество близлежащих граничных точек, на практике это точки из окружности радиуса 5 точек; T — пороговое значение фильтрации, при- нимается равным 100. Установив границы, получаем большое количество точек. Их можно умень- шить, определив функцию и в качестве искомых точек рассматривать ее локаль- ные экстремумы. Экспериментально было получено, что функция    Nn nxynyx ggggpP )()( дает достаточно стабильный результат выделения ключевых точек (рис. 1). 92 ISSN 0572-2691 Полученное множество точек сор- тируется в порядке увеличения модуля градиента, чтобы на следующих этапах наиболее информативные точки обра- батывались в первую очередь. Проанализировав алгоритм, мож- но увидеть, что он удовлетворяет всем выше описанным требованиям. Высокая скорость работы достигается за счет значительного уменьшения количества обрабатываемых точек на первом этапе, а также размеров обра- батываемого изображения (на практике до 320240 точек). Для большей устой- чивости к шумам можно предварительно размыть снимок, но это сильно снизит скорость работы. Описание ключевых точек. Чтобы объединить точки различных изображе- ний в пары, для каждой из них строят стабильный вектор признаков. Основой для этого этапа есть подход, описанный в [1]. Его идея состоит в использовании ин- формации о границах, расположенных в окрестности точки. Чтобы построить устойчивый к повороту вектор признаков точки, определя- ют базовую ориентацию относительно которой формируются признаки. Для этого строят гистограмму ориентаций градиентов соседних точек из некоторой рас- сматриваемой окрестности (на практике берется круг радиуса 5 точек, а гисто- грамма — из 32 элементов). Вклад каждой точки равен длине вектора градиента и пропорционально делится между двумя соседними элементами гистограммы. Среди них находится глобальный максимум M и все локальные максимумы, пре- вышающие 0,8M. Все найденные направления уточняются как максимум квадрат- ного трехчлена, на основании соседних элементов гистограммы: . 224 NP PN HHH HH DD    Здесь NP HHH ,, — значения предыдущего, текущего и следующего элементов гистограммы; D — направление. Для каждого из направлений строится отдель- ный вектор признаков. На следующих этапах каждый такой вектор признаков вместе с точкой рассматривается как отдельный элемент. Учитывая ориентации, возле клю- чевой точки выбираем некоторое коли- чество центров (здесь используется 12, а в [1] — 16). В их окрестностях также строим гистограммы ориентаций (и в предложенной схеме, и в [1] использу- ется по 8 элементов). Полученные зна- чения элементов гистограмм для всех выбранных центров (рис. 2) образуют искомый вектор признаков. Для компенсации искривлений проектирования точки изображения к краю уплотняются по следующему закону: Рис. 1 Ориентация Гистограмма ориентаций Центры Градиенты Гистограммы возле центров Рис. 2 Международный научно-технический журнал «Проблемы управления и информатики», 2013, № 6 93 . 2 tg1 2         xSx Здесь x — позиция точки на изображении в пределах от 1 до 1;  — угол обзора камеры; xS — масштаб в точке по абсциссе. Аналогично находят масштаб по ординате yS . Независимость от уровня экспозиции обеспечивается использованием гради- ентов. Для достижения устойчивости к изменению контрастности, вектор призна- ков нормируется. Он будет устойчив к небольшому изменению положения точки и найденной ориентации за счет расстояния между центрами при построении ги- стограмм. Таким образом, получаем вектор признаков из элементов одинаковой раз- мерности. Их можно сравнивать, используя эвклидову норму. Построение пар ключевых точек. Цель этого этапа — предложить эффек- тивный алгоритм для поиска близких (в евклидовой метрике) точек многомерного (размерность порядка ста) пространства. В качестве координат принимаем эле- менты вектора признаков. Количество всех точек может достигать нескольких десятков тысяч, что де- лает полный перебор очень трудоемкой операцией. С использованием идеи хеширования значительно ускорится процесс поиска. Многоуровневая хеш-таблица строиться для точек одного или нескольких изоб- ражений из базы, а точки нового изображения поочередно ищутся в ней. В каче- стве хеш-функции целесообразно использовать поочередно координатные пря- мые. Хеширование влечет за собой проблему неравномерности распределения то- чек, что замедляет работу алгоритма. Положительным свойством подхода есть возможность добавлять новые элементы без полной перестройки таблицы. Дальнейшим развитием идеи является KD-дерево. На его ветвях пространство делится так, чтобы в каждую из частей попадало равное количество точек. В качестве разделителя выбирается гиперплоскость, перпендикулярная к той коор- динатной оси, на которой крайние проекции точек наиболее отдалены друг от дру- га. Таким образом, глубина дерева всегда будет равна .log2 N Но при этом теряется возможность пополнения дерева без полной перестройки. Рассматривая работу про- граммы в целом, приходим к выводу, что модификация дерева требуется лишь при добавлении изображения в базу, что происходит очень редко. Это позволяет каж- дый раз осуществлять перестройку без заметной потери производительности. Первым шагом поиска в KD-дереве (рис. 3) наилучшей пары для точки A яв- ляется спуск от корня к соответствующему листу. Получив там одну точку B ее можно считать первым кандидатом, но никак не конечным результатом, так как в другом листе может быть точка, ко- торая лежит ближе к A. Поэтому нужно перебрать все ветви дерева, в которых может находится точка ,B  расположенная ближе к A чем B. Ес- ли в процессе такого перебора была найдена некоторая лучшая точка ,B  то она заменяет B, и дальнейший по- иск значительно сокращается. На этом основан алгоритм, предложен- ный в [8], в котором сортируются все проверяемые ветви по возрастанию расстояния к A. Окончательный результат Второе приближение — B Запрос — A Первое приближение — B Рис. 3 94 ISSN 0572-2691 При некоторых «неудобных» данных поиск длится достаточно долго. Во из- бежание неоправданной задержки количество проверок при поиске ограничивает- ся (на практике проводится до 200 проверок). На этом этапе можно отбросить некоторые ложно определенные пары. В [1] было отмечено, если отношение расстояния от A к ближайшей точке в базе к рас- стоянию от A ко второй ближайшей превышает 0,8, то с большóй вероятностью пара является ложной. Следовательно, такие пары в дальнейшем не рассматрива- ются. Отметим, что одна и та же точка из различных изображений присутствует в дереве несколько раз, поэтому вторую следует искать только среди простран- ственно-удаленных точек (в трехмерном глобальном пространстве), чтобы не встретить копию первой. Геометрическая модель. Положение любого твердого тела, в том числе ка- меры, в пространстве полностью определяется смещением и тремя углами Эйле- ра. Но в случае панорамной съемки камера, точнее центр проекции изображений, остается на том же месте, изменяются только углы. Таким образом, положение камеры однозначно определяется этими углами. Преобразование точки из локальной системы координат камеры в глобаль- ную осуществляется по формулам ),()()(),,(,),,(                   zxy loc loc loc RRRR z y x R z y x , cos0sin 010 sin0cos )(, cossin0 sincos0 001 )(                      yx RR . 100 0cossin 0sincos )(           zR Здесь , ,  — углы поворота камеры. Все системы координат выбираются правыми (рис. 4). Вектор гравитации в глобальных координатах (а) направлен вдоль оси ординат. В локальной системе координат изображения (б) ось аппликат направлена от центра проекции к части пространства, которая снимается, и центр проекции имеет координаты (0, 0, 0). Все снятые изображения рассматриваются как прямоугольники, касающиеся еди- ничной сферы, в которых нормаль из точки касания проходит через начало коор- динат (см. рис. 4). Размеры прямоугольника определяются углом обзора, который считается из- вестным. Точка касания принимается за середину изображения. Такие конкрети- зации позволяют построить алгоритм, который работает значительно быстрее. X Y Z Z X Y Направление гравитации Изображение Точка касания Единичная сфера Центр проекции (0, 0, 1) а б Рис. 4 Международный научно-технический журнал «Проблемы управления и информатики», 2013, № 6 95 Фильтрация с помощью датчика ускорения. На предыдущем этапе алго- ритма образовалось множество пар точек. Большинство из них найдены правиль- но, но есть и те, которые были построены по ошибке или же их точки принадле- жат движущимся объектам. Такие пары вносят погрешность в поиск взаимной ориентации, поэтому их нужно исключить. Для проверки очередной пары будем совмещать изображения, которым при- надлежат ее точки, и сравнивать пиксели изображений на перекрытии. Под сов- мещением будем понимать поиск взаимного положения изображений на основе того, что координаты точек выбранной пары и вектора гравитации совпадают в глобальном пространстве. Для удобства введем функцию         .0если,arctg ,0если,arctg ),(angle x x y x x y xy Положение первого изображения известно. Тогда положение второго нахо- дят, исходя из положения первого: ),,(angle1 II zy ),cossin,(angle 111  III zyx ,),,)(()(),,( T 11 T GGGxyGGG zyxRRzyx  ),,(angle 22 2 WWW zxy  ),,(angle),,(angle 22 GGWW yxzx  ),()()()()( 11222  xyzxy RRRRRR где R — положение второго изображения в виде матрицы поворота; ),,( GGG zyx и ),,( III zyx — вектор гравитации и положение точки в системе координат второ- го изображения; ),,( WWW zyx — координаты точки в глобальном пространстве. Исходя из положений изображений, сравнивают элементы их перекрытия (рис. 5). Для начала равномерно выбираем пикселы перекрытия (на практике по- рядка 100) из первого изображения, далее проектируем их положение на второе. Получаем пары яркостей соответствующих точек. Чтобы рассчитать расстояние между элементами пар, нужно компенсировать изменение экспозиции камеры и ба- ланса белого. Проанализировав работу соответствующих алгоритмов, приходим к выводу, что компенсацию можно рассматривать как квадратичное преобразова- ние. Используя метод наименьших квадратов, находим неизвестные коэффициен- ты и применяем полученную ком- пенсацию. Для устойчивости этой схемы вместо элемента второго изображения рассматриваем интер- вал яркостей пикселов в его окрест- ности. Ошибкой для такого пере- крытия считаем среднее расстояние от элемента первого изображения до соответствующего интервала из второго. Некоторые из образован- ных пар могут быть ложно опреде- Направление гравитации Совмещенные точки пары Пикселы перекрытия Первое изображение Второе изображение Рис. 5 96 ISSN 0572-2691 ленными, поэтому учитываются только 80 % с наименьшим расстоянием. В каче- стве яркостей поочередно рассматриваются цветовые компоненты: красная, зеле- ная и синяя; результирующая ошибка рассчитывается как среднее значение. Отметим, что большинство правильно определенных пар имеют ошибку, меньшую чем 5. Таким образом, в качестве критерия для фильтрации предлагает- ся отбрасывать пары с ошибкой, превышающей 5. Отметим, что даже одну пару точек, прошедшую этот тест, можно использовать для отображения результата быстрого поиска. Фильтрация на основании геометрических свойств. С увеличением коли- чества найденных пар вероятность ошибки сильно увеличивается. В этом случае используется дополнительная фильтрация на базе геометрических особенностей взаимного расположения точек [9]. Будем рассматривать по две пары точек: ),( 11 ba и ),,( 22 ba где ,1a 2a — точки первого изображения, а ,1b 2b — второго. Если они определены правиль- но, то выполняется неравенство .),(),( 2121  bbaa Здесь  — пороговое значение ошибки определения позиций точек; ),(  — угол между векторами от центра проекции к этим точкам. Пары, которые удовлетво- ряют этому неравенству, будем называть совместимыми. Для поиска взаимного положения изображений выделяем множество попарно совместимых пар. Рассмотрим случай, когда одна из пар определена неправильно. Тогда значе- ние ошибки сильно варьируется в пределах размера изображений. На рис. 6 пока- заны варианты ошибок совместимости (изображение № 1 (а), изображение № 2: правильно найденные пары, всегда  21 dd (б); неправильно найденные па- ры, когда  21 dd (в) и  21 dd (г)). В большинстве случаев она больше порогового значения, но в некоторых случаях такие пары все-таки совместимые. Вероятность такого события обозначим как ).),(),(()( 2121  bbaaP Большая эффективность достигается за счет выбора ε так, чтобы )( было близ- ким к нулю (на практике ε 1°). d1 d2 а б d2 d2 в г Рис. 6 Международный научно-технический журнал «Проблемы управления и информатики», 2013, № 6 97 Для каждой пары точек считаем количество несовместимых с ней. Правильно определенные пары будут несовместимы с )(1  частью ложных пар, а ложные — с )(1  частью всех пар. Таким образом, правильные пары будут совместимы со значительно большим количеством пар. Отбрасываем ложные пары, начиная из самых несовместимых пар. Вместе с удалением будем пересчитывать совместимости всех оставшихся пар. В конце получим множество попарно совместимых пар. Поиск взаимной ориентации камер. В случае двух или более пар нужно найти позицию изображения, учитывая все эти пары. Обычно для решения такой задачи используют градиентные методы, которые минимизируют ошибку, варьируя углы наклона камеры в пространстве [5]. Для улучшения быстродействия и сходи- мости предлагается использовать модифицированный метод оптимизации [9]. Пусть )),(),,,(( 22111 iiiii yxzyx — пары точек, принадлежащие глобальному пространству и изображению, положение которого определяется. Задача состоит в поиске таких углов ,  и , которые минимизирую общую погрешность: .min 1,, )1,,( ),,(),,( ,,22 T22 T111             i ii ii iii yx yx Rzyx Начальное приближение значений углов ),,( 000  находится по схеме из первого метода фильтрации. В итера- ционной схеме (рис. 7) произ- водится уточнение углов  и , поскольку значение  можно аналитически рассчитать по первым двум углам и парам соответствий. Пусть k и k — значения углов на k-й ите- рации. Определяем проекции точек ),,( 111 iii zyx на плоскость изображения: ,),,)(0,,()ˆ,ˆ,ˆ( T1111T111 iiikkiii zyxRzyx   . ˆ ˆ , ˆ ˆ )~,~( 1 1 1 1 11          i i i i ii z y z x yx В результате преобразования получим пары )),(),~,~(( 2211 iiii yxyx в плоскости изоб- ражения. Находим преобразование плоскости, состоящее из сдвига, поворота и масштабирования, которое наилучшим образом переводит ),( 22 ii yx в ),~,~( 11 ii yx т.е. минимизирует сумму: .min))~cossin()~sincos(( ,,, 21 0 2221 0 22 00    i syx iiiiii yysysxxxsysx Задачу решают методом наименьших квадратов относительно параметров ,0x ,0y coss и .sin s Найденное преобразование применяется к центру изображе- ния (0, 0, 1), в результате получается точка ).1,,( 00 yx Теперь переведем ее в глобальную систему координат и рассчитаем новые значения углов поворота: Ключевые точки и середина изображения Ключевые точки в пространстве Оптимизация положения в плоскости Проекция полученного центра Единичная сфера Плоскость изображения Новая плоскость изображения Центр проекции Рис. 7 98 ISSN 0572-2691 ,)1,,)(0,,(),,( T 00 T yxRzyx kk  ).,(angle),,(angle 1 22 1 zxzxy kk   Хотя найденное преобразование в плоскости является оптимальным, оно не являет- ся таковым в пространстве, поскольку при изменении углов  и  изменяется сама плоскость изображения. Итерационный процесс позволяет за несколько шагов до- статочно точно найти значение углов и, следовательно, положение плоскости, оп- тимальное значение на которой также является оптимальным в пространстве. Угол  рассчитывается на последней итерации: ),cos,sin(angle  ss а зна- чение 22 )cos()sin(  sss используется для дополнительной проверки кор- ректности найденного преобразования. Структура базы изображений. Как указывалось выше, алгоритмический комплекс состоит из трех частей. Здесь будем рассматривать первые две, а имен- но поиск положения и пополнение базы. Поиск необходим в основном для опре- деления положения изображения из видоискателя камеры относительно изобра- жений из базы. В этой подзадаче самое важное требование — максимальная ско- рость выполнения при фиксированной, достаточно небольшой, точности. Для комфортной работы с программой необходимо обеспечить не менее 15 кадров в секунду, или до 67 мс на один поиск. Пополнение базы изображений происхо- дит гораздо реже и длится несколько секунд, обеспечивая высокую точность. Полная сферическая панорама содержит около 50–70 изображений, для каждого из которых нужно один раз использовать пополнение. База изображений состоит из двух уровней. На первом находится список KD-деревьев для поиска позиции изображения в пространстве, а на втором — граф, вершинами которого есть изображения, а ребрами — относительные поло- жения соединенных изображений и коэффициенты коррекции цветовых компо- нент. При каждом новом снимке к графу присоединяется вершина и все возмож- ные ребра, исходящие из нее. Построение ребер осуществляется на основании ключевых точек из перекрытия изображений. Для поиска находят и описывают точки входного изображения. Затем, ис- пользуя деревья из базы, формируют пары точек, первая из которых принадлежит какому-то уже снятому изображению, а вторая — обрабатываемому. Найденные пары фильтруются в два этапа, и по оставшимся определяют углы Эйлера. Если в результате второй фильтрации осталось недостаточно пар для поиска углов, то можно использовать пары, полученные после первой фильтрации. Если и после первой фильтрации недостаточно пар для поиска углов итеративным методом, то находим углы, используя направление гравитации. Алгоритм завершается ошиб- кой только в том случае, если после первой фильтрации не осталось точек. В ре- альных условиях такая схема позволяет «цепляться» за точки даже при перекры- тии до 10–20%, а метод, используемый в [10], требует от 30 до 70 % перекрытия. Скорость и точность поиска увеличивают, применяя датчик ускорения, который показывает направление гравитации в системе координат устройства. Зная коор- динаты направленного вниз вектора, можно найти углы  и  и по ним определить значение ординаты в глобальной системе координат для каждой из ключевых то- чек. Такая информация позволяет разбить точки базы на полосы и искать соответ- ствие только в дереве из нужной полосы. Первый шаг при пополнении — поиск, параметры которого подбираются не для увеличения быстродействия, а для повышения устойчивости и точности. Определенные углы позволяют значительно сократить перебор при дальнейшем связывании изображений. По их значениям определяют изображения из базы, с которыми новое изображение может образовать соединения. Для каждого потен- Международный научно-технический журнал «Проблемы управления и информатики», 2013, № 6 99 циального соединения выполняют построение пар, все такие пары фильтруют на основании геометрических свойств и по оставшимся находят положение нового изображения относительно рассматриваемого соседа. Когда все возможные отно- шения построены, изображение становится элементом базы. Чтобы подготовить ее к последующим запросам и пополнениям, нужно добавить ключевые точки но- вого изображения в деревья, распределить ошибку на все связи в полученном графе и пересчитать коэффициенты яркостей для всех цветовых компонент. Проецирование изображений панорамы. Все описанные выше средства предназначены в конечном итоге для получения позиций снимков и коэффициен- тов коррекции яркостей. Если на экран вывести изображения, используя лишь эти данные, то будут сильно заметны участки соприкосновения отдельных снимков. Эффект возникает из-за ошибок, которые есть следствием некоторых явлений, в частности: смещения центра проекции, шумов и увеличенного размера точки при обработке. Для устранения этой проблемы используются различные схемы смешивания. Самая простая из них — линейная комбинация соседних изображений. Согласно этому методу точки в некоторой окрестности границ изображений получают вследствие их линейной комбинации. При большой области смешивания такой подход дает заметные погрешности на высокочастотных элементах изображений, поскольку ошибка взаимного расположения изображений превышает амплитуду некоторых деталей, например листьев. Вместе с тем при малой области смешива- ния будут заметны скачки яркости на однородных (низкочастотных) участках, вы- званные виньетированием. Иными словами, для высоких частот нужно смешива- ние малых окрестностей, а для низких — больших. В [6] предлагается алгоритм, который исправляет ситуацию. Его основная идея состоит в разбиении изображений на частотные полосы, которые потом линейно смешиваются в различной степени (рис. 8). Разбиение происходит с использовани- ем гауссиана. Самая низкочастотная часть изображения фактически является силь- но размытым оригинальным изображением. Следующая полоса — разность между менее размытым и предыдущим изображением. Самая высокочастотная полоса — разница между немного размытым изображением и оригиналом. Получив для каждого изображения разложение в полосы частот, смешиваем одинаковые поло- сы всех изображений. Величина области смешивания зависит от частот: чем они больше — тем меньше область и наоборот. Это позволяет избежать ранее описан- ных проблем. Для получения результата, суммируем все найденные частотные полосы. Такой подход используется в работах [5, 10]. При объединении изображений происходит проектирование, его можно вы- полнять на плоскость, сферу и цилиндр. Проектирование на куб является проек- тированием на 6 плоскостей. Отметим существование двух стратегий прорисовки. Первая предполагает поочередную прорисовку каждого из слоев. Такой подход требует многократного обращения к изображениям в разное время. Для его осуществления необходимо хранение всех изображений в памяти в раскодированном виде или их декодиро- вание при каждом обращении. Вариант с хранением требует большой объем па- мяти, а вариант с декодированием — много времени. Поэтому в предложенном алгоритме используется иная стратегия, заключающаяся в последовательной об- работке каждого из изображений. Для начала по расположению камер определяют степени вкладов изображений в суммарный результат. Это выполняют для каж- дой из частот. Потом изображения обрабатывают на каждой частоте. По этой ин- формации определяют окончательный процентный вклад, на основании которого добавляют очередной пиксел. Данный алгоритм требует достаточно большой объем памяти, но ее потребность уменьшается из-за блочной прорисовки. Также эта идея используется для распараллеливания на многопроцессорных системах. 100 ISSN 0572-2691 … … Рис. 8 Значительную часть вычислений занимает процедура размытия, особенно при больших размерах ядра свертки. Ускоряется она за счет использования уменьшенных копий, размер которых выбирают так, чтобы не были заметны кон- туры пикселов изображения после размытия. Международный научно-технический журнал «Проблемы управления и информатики», 2013, № 6 101 Программная реализация. Во время построения алгоритмического ком- плекса (на рис. 9 — снимок экрана) все этапы проверялись на реальных данных. Была написана программа для мобильного телефона, которая позволяет без труда строить панорамные снимки. Рис. 9 Ключевой особенностью алгоритмического комплекса есть скорость работы. Так на процессоре Exynos 4 Quad 4412 с тактовой частотой 1,4 ГГц среднее время поиска составляло 150 мс. Для ускорения можно не использовать без необходи- мости первую методику фильтрации, что уменьшит время работы до 50 мс. Кроме того, практически все используемые алгоритмы позволяют проводить параллель- ные вычисления, задействовав возможности современных многоядерных про- цессоров. Для компенсации задержек используется гироскоп. Особенностью устройства есть то, что оно может достаточно быстро (200 раз в секунду) и точно определять угловую скорость, но имеет свойство накапливать ошибку. Компенси- руется она при каждом поиске предложенным алгоритмом. Это позволяет снизить требования к скорости работы поиска и увеличить его качественные показатели. Для добавления одного снимка программе требуется до 3 с, из которых 1 с идет на декодирование изображения из камеры. Таким образом, на построение круговой панорамы из 15 изображений требуется приблизительно 1 мин. Процедура прорисовки на телефоне занимает значительное время (для пол- ной панорамы из 5 МП изображений — порядка 1–2 ч), но она без проблем запус- кается параллельно, что в несколько раз сокращает время ее выполнения. Полно- размерную прорисовку можно перенести на компьютер, а на телефоне строить только панораму с малым количеством точек. Дальнейшая работа по улучшению программы будет касаться устранения эффектов прорисовки движущихся объектов, как полупрозрачных «призраков» и нестыковок на границах. «Призраки» возникают из-за выбранного механизма объединения изображений. Для их устранения нужно использовать дополнитель- ные средства поиска движущихся объектов. Ошибки на границах появляются из- за изменения центра проекции во время съемки. Они частично устраняются не- значительным искривлением изображений. Все описанные выше дополнения должны выполнятся непосредственно до или во время проецирования, что не по- влияет на процесс съемки. Заключение. В работе предложен эффективный алгоритмический комплекс для построения панорамных снимков с помощью маломощных портативных устройств. Подробно описаны все этапы его функционирования. По скоростным характеристикам реализация данного подхода обеспечивает комфортную работу без существенных задержек. Предложенные идеи подходят и для других задач, 102 ISSN 0572-2691 связанных с обработкой изображений, в частности для пространственного восста- новления. В перспективе планируется устранить все замеченные ошибки, про- должать увеличивать скорость и точность описанного метода. Результатом рабо- ты стал программный комплекс, который используется для интерактивного по- строения панорамных снимков на современных мобильных телефонах. Ф.Г. Гаращенко, А.Ю. Кобзар ІНТЕРАКТИВНА ПОБУДОВА ПАНОРАМНИХ ЗНІМКІВ ЗА ДОПОМОГОЮ ПОРТАТИВНИХ КОМП’ЮТЕРІВ Пропонується ефективний алгоритмічний комплекс для побудови панорамних знімків. Його швидкодія достатня для використання на більшості сучасних кишенькових комп’ютерів. Така швидкодія досягається завдяки поєднанню різних алгоритмів на низці етапів. На основі алгоритмічного комплексу розроб- лено програмне забезпечення, яке демонструє ефективність запропонованих розробок. F.G. Garashchenko, A.Yu. Kobzar INTERACTIVE CONSTRUCTION OF PANORAMIC IMAGES ON PORTABLE DEVICES An efficient algorithmic complex for constructing panoramic images is proposed. It has sufficiently high performance to be used on the majority of modern portable de- vices. High performance has been achieved via combining chosen algorithms on dif- ferent stages of image processing. A software based on this algorithmic complex, which demonstrates the potency of the submitted research, has been developed. 1. Lowe D. Distinctive image features from scale-invariant keypoints // Intern. J. Computer Vi- sion. — 2004. — 60, iss. 2. — P. 91–110. 2. Bay H., Ess A., Tuytelaars T., Gool L. SURF: Speeded up robust features // Computer Vision and Image Understanding (CVIU). — 2008. — 110, N 3. — P. 346–359. 3. Zoghlami I., Faugeras O., Deriche R. Using geometric corners to build a 2D mosaic from a set of images // Intern. Conf. on Computer Vision and Pattern Recognition, June 1997, Puerto Rico: proceedings. — 1997. — P. 420–425. 4. McLauchlan P., Jaenicke A. Image mosaicing using sequential bundle adjustment // British Ma- chine Vision Conf., Sept. 11–14, 2000, Bristol, UK: proceedings. — 2000. — 20. — P. 751–759. 5. Brown M., Lowe D. Automatic panoramic image stitching using invariant features // Intern. J. Computer Vision. — 2007. — 74, iss. 1. — P. 59–73. 6. Burt P., Adelson E. A multiresolution spline with application to image mosaics // ACM Transac- tions on Graphics. — 1983. — 2, iss. 4. — P. 217–236. 7. Canny J. A computational approach to edge detection // IEEE Trans. Pattern Analysis and Ma- chine Intelligence. — 1986. — PAMI–8, iss. 6. — P. 679–698. 8. Beis J., Lowe D. Shape indexing using approximate nearest-neighbour search in highdimensional spaces // Conf. on Computer Vision and Pattern Recognition, June 17–19, 1997, San Juan, Puerto Rico: proceedings. — P. 1000–1006. 9. Кобзар А.Ю. Структура бази зображень для побудови панорамних знімків // Вісн. Київ. нац. ун-ту імені Тараса Шевченка. Сер. Фіз.-мат. наук. — 2012. — № 4. — С. 128–131. 10. Верченко А.П., Кобзар А.Ю. Про один алгоритм побудови панорамних знімків // Там же. — 2011. — № 3. — С. 109–114. Получено 29.05.2013
id	nasplib_isofts_kiev_ua-123456789-207681
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	0572-2691
language	Russian
last_indexed	2025-12-07T17:18:17Z
publishDate	2013
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
record_format	dspace
spelling	Гаращенко, Ф.Г. Кобзарь, А.Ю. 2025-10-11T15:15:22Z 2013 Интерактивное построение панорамных снимков с помощью портативных компьютеров / Ф.Г. Гаращенко, А.Ю. Кобзарь // Проблемы управления и информатики. — 2013. — № 6. — С. 90-102. — Бібліогр.: 10 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207681 004.932.2:519.688 10.1615/JAutomatInfScien.v45.i12.30 Пропонується ефективний алгоритмічний комплекс для побудови панорамних знімків. Його швидкодія достатня для використання на більшості сучасних кишенькових комп’ютерів. Така швидкодія досягається завдяки поєднанню різних алгоритмів на низці етапів. На основі алгоритмічного комплексу розроблено програмне забезпечення, яке демонструє ефективність запропонованих розробок. An efficient algorithmic complex for constructing panoramic images is proposed. It has sufficiently high performance to be used on the majority of modern portable devices. High performance has been achieved via combining chosen algorithms on different stages of image processing. A software based on this algorithmic complex, which demonstrates the potency of the submitted research, has been developed. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Методы обработки информации Интерактивное построение панорамных снимков с помощью портативных компьютеров Інтерактивна побудова панорамних знімків за допомогою портативних комп’ютерів Interactive construction of panoramic images on portable devices Article published earlier
spellingShingle	Интерактивное построение панорамных снимков с помощью портативных компьютеров Гаращенко, Ф.Г. Кобзарь, А.Ю. Методы обработки информации
title	Интерактивное построение панорамных снимков с помощью портативных компьютеров
title_alt	Інтерактивна побудова панорамних знімків за допомогою портативних комп’ютерів Interactive construction of panoramic images on portable devices
title_full	Интерактивное построение панорамных снимков с помощью портативных компьютеров
title_fullStr	Интерактивное построение панорамных снимков с помощью портативных компьютеров
title_full_unstemmed	Интерактивное построение панорамных снимков с помощью портативных компьютеров
title_short	Интерактивное построение панорамных снимков с помощью портативных компьютеров
title_sort	интерактивное построение панорамных снимков с помощью портативных компьютеров
topic	Методы обработки информации
topic_facet	Методы обработки информации
url	https://nasplib.isofts.kiev.ua/handle/123456789/207681
work_keys_str_mv	AT garaŝenkofg interaktivnoepostroeniepanoramnyhsnimkovspomoŝʹûportativnyhkompʹûterov AT kobzarʹaû interaktivnoepostroeniepanoramnyhsnimkovspomoŝʹûportativnyhkompʹûterov AT garaŝenkofg ínteraktivnapobudovapanoramnihznímkívzadopomogoûportativnihkompûterív AT kobzarʹaû ínteraktivnapobudovapanoramnihznímkívzadopomogoûportativnihkompûterív AT garaŝenkofg interactiveconstructionofpanoramicimagesonportabledevices AT kobzarʹaû interactiveconstructionofpanoramicimagesonportabledevices

Интерактивное построение панорамных снимков с помощью портативных компьютеров

Institution

Ähnliche Einträge