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




Скачать 297.16 Kb.
НазваниеКобзарь А. И. Прикладная математическая статистика. Для инженеров и научных работников
страница2/5
Дата20.09.2012
Размер297.16 Kb.
ТипДокументы
1   2   3   4   5

Милов А.Н.

ГУП НПЦ «ЭЛВИС»


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

Одним из существенных факторов при выборе того или иного способа масштабирования производительности является эффективная площадь на кристалле. С этой точки зрения наиболее перспективными способами масштабирования производительности являются параллелизм на уровне инструкций ILP (Instruction Level Parallelism) и SIMD (Single Instruction – Multiple Data) [1], которые при минимальном увеличении площади кристалла обеспечивают высокие результаты масштабирования производительности. Однако такие способы заключают в себе серьезные недостатки.

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

Поэтому ряд исследователей (см. например [2,3]) предлагают различные методики для оптимизации алгоритмов, основывающиеся, как правило, на минимизации программных ветвлений алгоритма, зависящих от исходных данных, и модификации математических критериев при обработке данных.

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

Одной из разновидностей проблемы является задача получения по исходному двумерному сигналу, представляющему собой сетку высот, аппроксимированной с заданной точностью триангулированной поверхности. В работе [4] показан способ, а в [2] приведены оптимизированные алгоритмы преобразования Хаара, позволяющие осуществлять многомасштабный анализ исходного изображения в том числе и с использованием SIMD. Однако преобразование Хаара обладает рядом известных недостатков [4].

Интересный подход продемонстрирован в [5]. В его основу положен геометрический критерий анализа. Согласно методу [5], поверхность, определяемая треугольниками ABE и BCE, может быть аппроксимирована треугольником ACE в том случае, если величина отклонения не превосходит некоторого порога: (1).

Процесс «реберного» слияния соседних треугольников продолжается рекурсивно до тех пор, пока величина отклонения не превзойдёт порога ошибки.


Рис. 1. Участок исходного сигнала сетки высот.





Рис. 2. Два варианта триангуляции исходной сетки высот.


Однако такие подходы оказываются достаточно сложными в реализации – сепаративный характер анализа нивелирует потенциальные возможности масштабирования с помощью ILP и SIMD.

Предлагается методика, включающая модификацию математического критерия многомасштабного анализа с целью адаптации вычислений к ILP и SIMD.

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

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

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

Для принятия решения о допустимости аппроксимации фрагмента исходной сетки (рис. 2) предлагается использовать следующий подход. Во-первых, необходимо учесть отклонения точек B,D,H,F от каркаса плоскости, заданного угловыми точками A,C,I,G (рис. 1). При этом для устранения избыточных программных ветвлений по исходным данным на промежуточных этапах многомасштабного анализа целесообразно иметь одно значение ошибки, учитывающее отклонения всех четырех точек, поскольку ограниченность всех четырех отклонений является необходимым условием для аппроксимации и последующего рекурсивного анализа (рис. 2). Можно рассматривать сумму квадратов отклонений и сравнивать ее с квадратом максимальной ошибки: (2).

Во-вторых, необходимо также учесть погрешность, вносимую в аппроксимированную модель отклонением точки E. Для этого достаточно рассмотреть два дополнительных отклонения по диагоналям – и . Если хотя бы одно из отклонений меньше допустимой ошибки , то выбирается вариант триангуляции (рис. 2), в котором этому отклонению соответствует общая линия треугольников (первый вариант соответствует отклонению , второй – отклонению ).

Несмотря на кажущуюся сложность математического вычисления критерия (2) по сравнению с (1), при вычислении степени может быть эффективно использован принцип ILP (операция может выполняться параллельно со сложением операндов).

Предлагаемая методика служит в качестве инструмента для более эффективной реализации алгоритмов в устройствах, поддерживающих масштабирование производительности по принципам ILP и SIMD, на промежуточных стадиях многомасштабного анализа изображения. Результаты аппроксимации исходного двумерного сигнала с помощью критерия (2) представлены на Рис. 3.





Рис. 3. Фрагмент исходного изображения Lenna 512x512 (слева) и триангулированное градиентное поле 1898 треугольников (справа).

Литература

  1. Flynn M. Some Computer Organisations and Their Effectiveness // IEEE Trans. Computers. 1972. V.21. N 9. P.948-960

  2. Милов А.Н., «Оптимизированные алгоритмы преобразований Хаара для отечественной платформы DSP «Elcore» и их применение в задачах графической обработки данных» // Вычислительные методы и программирование. – 2007. – т. 8 № 2. С. 34-39

  3. K. Vostryakov, A. Voloboy. Antialiasing algorithm for a SSE 4-ray ray tracing // In Proceedings of International Conference on Computer Graphics and Vision «Graphicon-2007»

  4. Переберин А.В., дисс. канд. физ.-мат. наук «Многомасштабные методы синтеза и анализа изображений», ИПМ им. Келдыша, Москва, 2002 г.

  5. P. Lindstrom, D. Koller, W. Ribarsky, L. Hodges, N. Faust, G. Turner, Real-Time, Continuous Level of Detail Rendering of Height Fields, Georgia Institute of Technology, 2003.



1   2   3   4   5

Похожие:

Кобзарь А. И. Прикладная математическая статистика. Для инженеров и научных работников iconУчебное пособие Издательство
Учебное пособие предназначено для бакалавров направления 230700 «Прикладная информатика» по дисциплине «Теория вероятностей и математическая...
Кобзарь А. И. Прикладная математическая статистика. Для инженеров и научных работников iconПрограмма вступительного экзамена по специальности научных работников 01. 01. 05 «Теория вероятности и математическая статистика»
Аксиомы теории вероятностей. Вероятность и ее свойства. Распределение, функция распределения, плотность распределения. Их свойства....
Кобзарь А. И. Прикладная математическая статистика. Для инженеров и научных работников iconПрограмма по дисциплине «Теория вероятностей и математическая статистика»
«Теория вероятностей и математическая статистика» разработана в соответствии с Государственным стандартом образования РФ (ЕН. Общие...
Кобзарь А. И. Прикладная математическая статистика. Для инженеров и научных работников iconПрограмма дисциплины человеческое развитие для направления 080100. 62 «Экономика» подготовки бакалавров Автор: Е. Н. Кобзарь ()
«Экономика» по специализации «Прикладная экономика». Студенты, приступающие к изучению курса, должны иметь базовые знания в области...
Кобзарь А. И. Прикладная математическая статистика. Для инженеров и научных работников iconПрограмма дисциплины "Теория вероятностей и математическая статистика для менеджеров "
...
Кобзарь А. И. Прикладная математическая статистика. Для инженеров и научных работников iconТехнические науки
Анализ данных. Статистические и вычислительные методы для научных работников и инженеров
Кобзарь А. И. Прикладная математическая статистика. Для инженеров и научных работников iconПрограмма дисциплины теория вероятностей и математическая статистика Цикл ен. Ф. Специальность : 013800 Радиофизика и электроника
Рабочая программа дисциплины "Теория вероятностей и математическая статистика" предназначена для студентов 2 курса
Кобзарь А. И. Прикладная математическая статистика. Для инженеров и научных работников iconТочные науки: математика, физика, химия
Анализ данных. Статистические и вычислительные методы для научных работников и инженеров
Кобзарь А. И. Прикладная математическая статистика. Для инженеров и научных работников iconАннотация рабочей программы
Теория вероятностей и математическая статистика» является вариативной частью Профессионального цикла дисциплин подготовки студентов...
Кобзарь А. И. Прикладная математическая статистика. Для инженеров и научных работников iconМетодические рекомендации к практическим занятиям и самостоятельной работе по дисциплине «Прикладная математическая статистика»
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница