Алгоритмы заполнения пропусков в графических объектах

Информационные системы и технологии

данных в миниатюре. Преимуществами витрин данных являются:

- простота и малая стоимость реализации;

- высокая производительность за счет физического разделения регистрирующих и аналитических систем, выделения загрузки и трансформации данных в отдельный процесс, оптимизированной структурой хранения данных под анализ;

- поддержка истории;

- возможность добавления метаданных.

Построение полноценного корпоративного хранилища данных обычно выполняется в трехуровневой архитектуре [2].

На первом уровне расположены разнообразные источники данных: внутренние регистрирующие системы, справочные системы, внешние источники.

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

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

Третий уровень представляет собой набор предметно-ориентированных витрин данных, источником информации для которых является центральное хранилище данных и с которыми работает большинство конечных пользователей.

Библиографические ссылки

1. Спирли Э. Корпоративные хранилища данных. Планирование, разработка, реализация. М. : Вильямс, 2001.

2. Аналитические системы для бизнеса [Электронный ресурс]. URL: http://www.bipartner.ru/ (дата обращения: 18.09.2012).

М. A. Lapteva, K. M. Boldyrev Siberian State Aerospace University named after academician M. F. Reshetnev, Russia, Krasnoyarsk

THE VAULT DATA: THE MAIN ARCHITECTURES AND PRINCIPLES OF THE BUILDING

Main architectures of vault data and some general principles of their building are considered. Main advantages and defects of virtual vault data and two-level architecture of data are chosen.

© Лаптева М. А., Болдырев К. М., 2012

УДК 519.688

И. Б. Ларионов

Омский государственный университет имени Ф. М. Достоевского, Россия, Омск

АЛГОРИТМЫ ЗАПОЛНЕНИЯ ПРОПУСКОВ В ГРАФИЧЕСКИХ ОБЪЕКТАХ

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

Надежность современных накопителей достаточно высока. Но всегда есть вероятность того, что какие-либо файлы будут испорчены или произойдет изменение данных, которое не заметно для внутренних алгоритмов контроля целостности носителей или для алгоритмов хеширования. Подобные изменения иногда приводят к достаточно сильному изменению данных (например, мультимедийных) в связи с тем, что современные алгоритмы сжатия с потерями неустойчивы к повреждениям.

Для заполнения пропусков в графических объектах широкое применение нашли методы бикубических сплайнов, многомерных линейных многообразий и самоорганизующихся карт Кохонена.

Интерполяция бикубическими сплайнами хорошо зарекомендовала себя при заполнении получаемых

пропусков, возникающих при изменении размеров изображений [1]. Многомерные линейные многообразия [2] и самоорганизующиеся карты [3] используются при заполнении пропусков в табличных данных [2]. В данной работе указанные методы применялись для заполнения пропусков в графических объектах с последующим сравнением качества такого заполнения.

Эффективность работы рассмотренных методов оценивалась по результатам двух компьютерных экспериментов по распознаванию лиц и распознаванию текста. Каждый из этих методов приводит к повышению процента верно распознанных лиц. Однако наиболее эффективным с этой точки зрения является метод с использованием карт Кохонена, наименее эффективным - приближение с помощью линейных многообразий, а с учетом времени выполнения наи-

Решетневскце чтения

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

Таким образом, наилучшие результаты были получены с помощью самоорганизующихся карт Кохо-нена, однако этот метод обладает наибольшим временем работы и может использоваться только в режиме сохранения изображений с последующей обработкой при отсутствии жестких ограничений по времени. Метод многомерных линейных многообразий дает визуально хорошие результаты, но также обладает не очень высоким быстродействием, вследствие чего его применение в режиме реального времени вызывает серьезные трудности. Интерполяция двумерными сплайнами больших порядков обладает достаточным быстродействием в режиме реального времени, дает

хорошие показатели по используемым метрикам, при этом заполнение пропущенных областей визуально легко различимо.

Библиографические ссылки

1. Ларионов И. Б. Алгоритмы предварительной обработки графических объектов со статическими пропусками в системах технического зрения : авто-реф. дис. ... канд. техн. наук. Уфа, 2011.

2. Россиев А. А. Итерационное моделирование данных с пробелами многообразиями малой размерности, автореф. дис. ... канд. физ.-мат. наук. Красноярск, 2000.

3. Kohonen T. Self-Organizing Maps. Berlin ; Heidelberg : Springer, 1997.

I. B. Larionov

Omsk State University named after F. M. Dostoevsky, Russia, Tomsk GAP-FILLING ALGORITHMS FOR GRAPHIC OBJECTS

Gap-filling algorithms using bi-cubic splines, multidimensional manifolds and self-organizing maps are described.

© Ларионов И. Б., 2012

УДК 004.021

А. С. Лисица

Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева, Россия, Красноярск

ИСПОЛЬЗОВАНИЕ МОДИФИЦИРОВАННОГО АЛГОРИТМА А* В ЗАДАЧЕ УПРАВЛЕНИЯ МАНИПУЛЯТОРОМ

Рассмотрена модификация алгоритма А * для планирования пути манипуляционного робота в среде с запрещенными конфигурациями и несколькими целевыми точками.

При управлении манипуляционным роботом типичной является следующая задача: манипуляцион-ный робот должен выдвинуться из стартовой конфигурации и, двигаясь в среде с препятствиями за конечное число шагов, обеспечить захват объекта в какой-либо разрешенной конфигурации [1]. Таким образом, возникает задача планирования пути из стартовой точки в одну из множества целевых, при этом путь не должен налегать на запрещенные точки. Для решения этой задачи требуется подобрать алгоритм, отвечающий следующим критериям:

- алгоритм должен быть применим к «-мерному конфигурационному пространству;

- он должен за конечное число шагов находить путь от стартовой точки к хотя бы одной целевой;

- исполнение алгоритма должно осуществляться за приемлемое время.

В [2] рассмотрен алгоритм А* для планирования пути в одну целевую точку в среде без препятствий.

В модифицированном алгоритме А* запрещенные конфигурации предстают совокупностью запрещенных точек, а различные конфигурации, удовлетворяющие условию захвата объекта (объект может быть захвачен в различных конфигурациях), - совокупностью целевых точек.

Алгоритм работает с «-мерным пространством и за конечное число шагов находит путь от стартовой точки до целевой либо обнаруживает, что такого пути не существует.

Модифицированный алгоритм А* применяет эвристическую функцию для оценки расстояния до целевой точки, которая в то же время не должна переоценивать расстояние между двумя точками.

В качестве такого расстояния мы будем рассматривать расстояние Чебышева между точками А и В, которое вычисляется как г(А, В) = тт(Ах - Вх\, \АУ — Ву\), так как именно оно показывает количество шагов по вертикали, горизонтали или диагонали, необходи-