Список основных исполнителей по Государственному контракту 14. 740. 11. 1258 от 17 июня 2011

Скачать 0.6 Mb.

Название	Список основных исполнителей по Государственному контракту 14. 740. 11. 1258 от 17 июня 2011
страница	7/8
Дата публикации	29.12.2014
Размер	0.6 Mb.
Тип	Отчет

100-bal.ru > Право > Отчет

1 2 3 4 5 6 7 8

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

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

N ― размер обрабатываемого изображения;
r ― цветовая глубина обрабатываемого изображения.

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

Кроме того, нужно отметить, что, несмотря на то, что при использовании асимптотических оценок константами пренебрегают (O(f(x)) = O(k∙f(x)), где k ― константа [5]), в таблице 5 эти константы приведены. Это связано с тем, что при работе с изображениями большого размера они имеют значение для оценки эффективности метода. Например, при визуализации набора изображений методом вывода текстурного атласа требуется сначала сформировать текстуру, а затем вывести её на экран. Это требует в два раза больше времени, чем в случае непосредственного вывода всех изображений. Двукратное превосходство в скорости выполнения одного метода над другим имеет большое значение в условиях необходимости обеспечения оперативности обработки изображений.

Таблица 5 ― Классификация методов обработки полутоновых растровых изображений по асимптотическим оценкам их вычислительной сложности и потребления памяти

Метод	Оценка сложности	Оценка памяти	Комментарий
Непосредственный вывод одного изображения	O(N)	O(1)
Визуализация одного изображения текстурированием	O(N)	O(N)	Дополнительная память используется для хранения изображения в видеопамяти
Последовательный вывод набора изображений	O(kN)	O(1)	k ― количество выводимых изображений
Визуализация набора изображения путём однократного вывода текстурного атласа	O(2kN)	O(kN)	O(kN) времени требуется на формирование текстурного атласа и столько же – на его визуализацию
Визуализация набора изображения путём вывода частей текстурного атласа	O(2kN)	O(kN)
Перемещение и масштабирование путём копирования в буфер	O(2N)	O(N)	O(N) времени требуется на масштабирование, O(N) – на копирование
Перемещение и масштабирование путём изменения текстурных координат	O(1)	O(1)

Продолжение таблицы 5

Метод	Оценка сложности	Оценка памяти	Комментарий
Представление изображения линейным массивом байтов	O(N)	O(N)	Для методов представления изображений в оперативной памяти приведена асимптотическая оценка вычислительной сложности формирования представления
Представление изображения двумерным массивом байтов	O(N)	Ω(N)
Представление изображения линейным массивом битов	O(rN)	O(N)
Представление изображения двумерным массивом битов	O(rN)	Ω(N)
Представление изображения многомасштабной пирамидой	O(N∙logN)	O(N∙logN)
Градационное преобразование	O(N)	O(1)
Видоизменение гистограммы	O(2N)	O(2^r)	O(N) времени требует построение гистограммы и O(N) – её видоизменение
Маскирование	O(N)	O(N)
Линейная пространственная фильтрация	O(c²N)	O(c²)	c ― размер ядра линейного фильтра
Сглаживающая частотная фильтрация	O(2N∙logN +N)	O(N)	Все методы частотной обработки требуют O(2N∙logN) времени на выполнение прямого и обратного преобразований Фурье, поэтому их сложность указана в виде O(2N∙logN + f(N)), где f(N) ― сложность самого метода. O(N) памяти используется для хранение Фурье-образа
Гоморофная фильтрация	O(2N∙logN +N)	O(N)
Пространственное подавление шумов	O(qN)	O(1)	q ― размер окрестности, в которой осуществляется фильтрация
Частотное подавление шумов	O(2N∙logN +N)	O(N)
Фильтрация методом минимизации среднего квадратического отклонения	O(2N∙logN +N)	O(N)
Неравномерное кодирование	O(N)	O(N)
LZW-кодирование	O(NKlogK)	O(K)	K ― размер словаря
Кодирование битовых плоскостей	O(r∙g(N))	O(rN)	g(N) ― оценка сложности алгоритма, применяемого для сжатия каждой битовой плоскости

Продолжение таблицы 5

Метод	Оценка сложности	Оценка памяти	Комментарий
Кодирование без потерь с предсказанием	O(N)	O(1)
Трансформационное кодирование	O(N +t(N))	O(N)	t(N) ― оценка сложности алгоритма трансформации
Предсказательное кодирование с потерями	O(N)	O(1)
Выделение границ	O(N)	O(N)
Заполнение областей	O(N)	O(N)
Выделение связных компонент	O(N)	O(N)
Построение выпуклой оболочки	O(N)	O(N)
Утончение и утолщение	O(N)	O(N)
Эрозия	O(N)	O(N)
Дилатация	O(N)	O(N)

Таким образом, большинство рассматриваемых методов обработки полутоновых растровых изображений имеют линейную относительно размера изображения вычислительную сложность. Так как снизить данную асимптотическую оценку принципиально невозможно, то достичь оперативности выполнения соответствующих операций можно только за счёт создания эффективных реализаций. В связи с этим, стоит отметить, что частью методов, имеющих сложность O(N∙logN), является прямое и обратное преобразования Фурье, для которых существуют библиотеки их выполнения на графическом ускорителе [14]. Следовательно, скорость реализации таких методов должна быть достаточно высокой за счёт использования эффективных аппаратных средств.

1 2 3 4 5 6 7 8

Похожие:

	Список основных исполнителей по Государственному контракту 14. 740. 11. 1258 от 17 июня 2011 Государственному контракту 14. 740. 11. 1258 от 17 июня 2011 на выполнение поисковых научно-исследовательских работ для государственных...		Список основных исполнителей по Государственному контракту 14. 740. 11. 1258 от 17 июня 2011 Государственному контракту 14. 740. 11. 1258 от 17 июня 2011 на выполнение поисковых научно-исследовательских работ для государственных...
	Отчет о выполненной работе по Государственному контракту №14. 741.... Государственное образовательное учреждение высшего профессионального образования "Российский экономический университет им. Г. В....		Отчет о научно-исследовательской работе по Государственному контракту... Этап второй: «Выбор направлений исследований и этап предварительных исследований по мембранным коллоидным системам»
	Отчет по Дополнительному соглашению №2 к Государственному контракту... «Разработка проекта скиово бассейна реки Нарва и рек бассейна Псковско-Чудского озера» (С-10-01)		Отчет о научно-исследовательской работе, выполняемой по государственному... «Разработка алгоритмов для биоинформационного анализа комплексных метаболических и молекулярно-генетических сетей»
	Отчет о научно-исследовательской работе по государственному контракту... Русский язык и культура речи: учебно-методический комплекс для студентов очной формы обучения / сост. И. А. Крым; Кузбасский институт...		Отчет о выполнении 4 этапа Государственного контракта №14. 740. 11.... О выполнении 4 этапа Государственного контракта №14. 740. 11. 1071 от 24. 05. 2011 г
	Отчет по Дополнительному соглашению №4 от 27 февраля 2010 г к Государственному...		Отчетные материалы по гос контракту №02. 740. 11. 0072 в рамках федеральной... Учебно-методический комплекс по дисциплине «Биохимия молока и мяса» составлен на основе
	Отчет по Государственному контракту № «Разработка концепции создания интеллектуальной транспортной системы на автомобильных дорогах федерального значения»		Отчет по Государственному контракту на выполнение работ для государственных нужд Организационно-техническое обеспечение работы российской экспозиции на осенней технической ярмарке
	Отчет по государственному контракту от 04. 06. 2012 №1102-01-41/06-12... ...		Реферат отчета по государственному контракту от 20. 04. 2007 г. №8-07-Эко... Фгун екатеринбургский медицинский научный центр профилактики и охраны здоровья рабочих
	Список исполнителей Содержание деятельности и результаты Мероприятия №10 «Москва – город грамотных людей»		Список исполнителей Федеральное государственное бюджетное учреждение науки институт программных систем им. А. К. Айламазяна

Школьные материалы