§ 46. Обработка с произвольным доступом к строке

Обработка с произвольным доступом к строке — это режим обработки изображений, при котором доступ к строкам входного изображения осуществляется не последовательно. Для эффективной работы входной файл изображения должен храниться в НМД, а выходной файл изображения может быть эквивалентным дисковым файлом. К простым программам такой обработки относятся программы, которые переставляют элементы изображения сверху донизу (возможно, непосредственно в ЗУ) или редактируют отдельные строки изображения.

Здесь мы рассмотрим некоторые виды обработки с произвольным доступом к строке, которые представляют особый интерес. Многие из них направлены на понижение уровня шумов, например в заданном искаженном изображении. Они основаны на различных допущениях относительно характеристик шума и изображения, на которое налагается шум. Различия в этих характеристиках можно использовать для подавления шумов. Желательно, чтобы при этом не увеличивалось искажение изображения. Медианным фильтром называется фильтр, который заменяет каждое значение элемента изображения медианной выборкой элементов изображения, лежащих в прямоугольной области фиксированного размера с центром в обрабатываемой точке растра. Медианный фильтр эффективен при удалении высокочастотных шумов, пиков, битовых сбоев, сбойных строк, царапин, пыли и других аномалий в изображении. Размер области должен быть достаточно малым для того, чтобы не вносилось искажение изображения, но достаточно большим для того, чтобы устраняемый дефект не доминировал над элементами изображения в этой области. Для вычисления медианы обычно используется быстрый алгоритм сортировки, относящийся к тому же типу алгоритмов, что и БПФ. В этом случае фильтр называется медианным фильтром Тьюки.

Другой полезный алгоритм, аналогичный по действию, — рамочная фильтрация нижних частот, при которой каждое значение элемента изображения заменяется средним значением но прямоугольной области фиксированных размеров. Такая фильтрация имеет ряд преимуществ по сравнению в фильтрацией на основе алгоритма БПФ. В частности, этот способ обладает большим быстродействием (его скорость сравнима со скоростью свертки с прямым нерекурсивным фильтром 2 х 2), им можно обрабатывать непосредственно 8- и

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

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

Чтобы понять суть алгоритма, прежде всего необходимо уяснить, каким образом хранятся в ЗУ компьютера данные изображения. Для вычисления (46.1) нужно организовать некоторый буфер на N слов и использовать однословную переменную Содержимое обновляется перед расчетом каждой строки выходного изображения, используется при подсчете каждого элемента строки выходного изображения.

Для строки слово в буфере можно записать в виде

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

вычитанием элемента изображения:

при Заметим, что начальные значения должны быть явным образом вычислены по формуле (46.2).

Промежуточное значение ISUM необходимо находить для каждого элемента изображения каждой выходной строки. Мы обозначаем его через к и находим по формуле

Заметим, что к выражается через к формулой

и, следовательно, формулы (46.5) и (46.3) связаны между собой. Начальное значение вычисляется для ISUM по формуле (46.4) с учетом того, что при или Остальные значения ISUM вычисляются но формуле (46.5). После того как для ISUM получено очередное значение вычисляется соответствующее ему значение

Хотя выражения (46.1) и (46.6) совершенно эквивалентны, пользуясь формулами (46.2)-(46.5), величину (46.6) можно вычислить значительно быстрее, чем по формуле (46.1).

Если координаты строки и точки растра вычисляются по модулю соответственно, вместо того, чтобы элементы изображения с координатами полагать равными нулю, то выражение (46.1) представляет собой периодическую свертку (см. § 12, 14, 15) с рамочным фильтром нижних частот.

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

это будет приблизительно в 4000 раз быстрее, чем прямая фильтрация, и в 15 раз быстрее, чем при использовании алгоритма БПФ. Это существенный выигрыш в скорости.

Проведенные сравнения верны при условии, что изображение хранится в ЗУПВ. Обычно это невыполнимо для больших изображений, а потому их приходится хранить в НМД. Преобразование Фурье больших изображений в НМД требует затрат времени на обмен с НМД (см. § 48). К тому же для записи изображения в форме вещественных чисел, а не в виде 8- или -разрядных целых чисел требуется много места в НМД. Рамочная фильтрация успешно справляется с обеими трудностями, так как в этом случае изображение обычно хранится в формате «целых чисел» (8- или -разрядных) и при вычислении строки выходного изображения за одно обращение к НМД должна считываться только одна строка изображения. Это является важным практическим преимуществом.

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

Еще одним примером обработки с произвольным доступом к строке может служить метод расширения границ, описанный в § 15. Он используется для экстраполяции искаженною изображения, представляющего собой усеченную свертку (так как оно усечено кадром записи), в изображение большего размера, являющееся периодической сверткой внутри кадра. Расширение границ производится следующим образом. Пусть данное 8-разрядное искаженное изображение имеет размеры М х N элементов, а ФРТ умещается в кадре с минимальным размером К элементов. Данное изображение помещается центрированно в кадре размерами с нулевыми значениями на границе. Затем прогоняется программа двумерной линейной интерполяции (см. § 11), которая периодически (см. § 15) заполняет значения на границе. Далее для сглаживания граничной области можно использовать итерационную процедуру, включающую рамочную фильтрацию (с уменьшающимися размерами рамки), за которой следует замена центральной области изображения данным искаженным изображением. Эта процедура превращает усеченную

свертку в периодическую свертку и обеспечивает стабильные результаты восстановления (см. относительно согласованности периодических сверток § 14).