ПРИБОРЫ И ТЕХНИКА ЭКСПЕРИМЕНТА, 2014, № 6, с. 41-44
ПРИМЕНЕНИЕ ВЫЧИСЛИТЕЛЬНОМ ТЕХНИКИ В ЭКСПЕРИМЕНТЕ
УДК 621.391.837:681.3
РЕАЛИЗАЦИЯ МЕДИАННЫХ ФИЛЬТРОВ ИЗОБРАЖЕНИИ НА МИКРОСХЕМАХ ПРОГРАММИРУЕМОЙ ЛОГИКИ © 2014 г. А. Х. Мурсаев, М. Н. Гречухин
С.-Петербургский государственный электротехнический университет "ЛЭТИ" им. В.И. Ульянова (Ленина)
Россия, 197376, С.-Петербург, ул. Профессора Попова, 5 E-mail:sashamursaev@yandex.ru Поступила в редакцию 16.11.2013 г. После доработки 19.02.2014 г.
Представлена структура двумерного медианного фильтра, ориентированная на реализацию в микросхемах программируемой логики и обеспечивающая сверхбыстрое определение медианы данных в двумерном окне за счет параллельного исполнения операций сравнения и упорядочения. Данный подход обеспечивает экономичную реализацию, пригоден для фильтрации как неподвижных, так и подвижных изображений и позволяет расширить область применения медианной фильтрации.
БО1: 10.7868/8003281621406010Х
ВВЕДЕНИЕ
Цифровая обработка сигналов и изображений относится к весьма трудоемким и в то же время широко распространенным задачам. Традиционные подходы, основанные на использовании процессорных архитектур общего назначения (т.е. ориентированных на последовательное исполнение команд по программе), во многих случаях оказываются недостаточно эффективными, и часто требуется переход к структурной организации вычислений [1]. В настоящее время развитие технологии больших интегральных схем позволяет реализовать в их составе весьма сложные проблемно-ориентированные блоки для решения конкретных задач обработки данных. При этом особенно эффективно в условиях частой смены алгоритмов и параметров обработки, характерных для систем предварительной обработки данных, использование программируемых логических интегральных схем (п.л.и.с.).
Медианная фильтрация — это один из популярных методов предварительной обработки одномерных и двумерных сигналов. Последние обычно сопоставляются с изображениями. Обработка медианным фильтром двумерного массива эффективно устраняет короткие всплески, включая импульсные помехи в канале передачи, без существенного искажения данных в зонах, в которых всплески отсутствуют. Суть метода состоит в том, что в выбранной окрестности (называемой окном наблюдения или просто окном) ищется медиана совокупности отсчетов в текущем окне, т.е. значение, большее половины отсчетов в этом окне [2]. Медианное значение и выбирается как выходной сигнал фильтра, соответствующий центральной точке окна.
Общим для большинства алгоритмов медианной фильтрации является упорядочение совокупности данных текущего окна. Тогда центральный элемент этой упорядоченной последовательности и является медианой. Для двумерных сигналов используют разные формы окон: крестообразную, Х-образную и ряд других [3]. Но надо отметить, что прямоугольное окно обеспечивает более высокое качество фильтрации, а упрощенные окна используются как компромисс качества и затрат.
В данной статье показано, что при прямоугольном окне возможны вполне приемлемые объемы оборудования и высокая производительность, и ниже именно такой вариант обсуждается. Последовательность медианных значений соседних, смещенных на один отсчет окон представляет собой выходную отфильтрованную последовательность.
Для поиска медианы наиболее часто используются различные алгоритмы упорядочения данных в массиве отсчетов. Традиционные методы упорядочения массивов, основанные на последовательном сравнении и перестановке элементов, являются весьма трудоемкими [4]. В работе [5] предложен рекуррентный подход к процедуре упорядочения в последовательности окон, когда упорядоченная последовательность для следующего окна получается незначительной модификацией последовательности, полученной для предыдущего окна. Это значительно сокращает объем преобразований. Однако предложенный алгоритм ориентирован на реализацию в последовательной форме в "обычном" программируемом процессоре, и неэффективен для интерпретации аппаратными средствами. В работе [6] этот подход интерпретирован для структурной (аппа-
Ш-
т + /т
п + Ш
X X •••X X •••X X X X ••• X X •••Х X
X X ••• X X •••X X X X •••X X •••Х X
X X •••X X •••Х X
Окно (Ш, п)
+
Окно (Ш, п + 1)
Рис. 1. Формирование упорядоченного массива для смежного правого окна^ "—" — удаляемые элементы, "х" — сохраняемые элементы, "+" — вставляемые элементы^
ратурно-ориентированной) реализации, но рассмотрена лишь одномерная фильтрация^ В настоящей работе подход расширен на двумерный случай, в том числе на подвижные изображения^
ОБРАБОТКА СТАТИЧЕСКИХ ИЗОБРАЖЕНИЙ
Пусть преобразуемые данные хранятся в двух-координатной памяти размером (тт + 1) х (пт + 1), где тт — максимальный индекс столбца, пт — максимальный индекс строка
Теперь т е {0 : тт} — индекс строки; п е {0 : пт} — индекс столбца^ Здесь и далее в круглых скобках записывается арифметическое выражение, в фигурных — диапазон значений {минимум : максимум}, а в квадратных — либо один индекс для строки, столбца или положения элемента в упорядоченном массиве, либо пара индексов для определения положения значения отсчета в памяти (первый индекс — номер строки)
Окном назовем блок данных размером (ш + 1) х х (Ш + 1), причем у е {0 : ]т} — относительный номер строки "внутри окна", а I е {0 : т} — относительный номер столбца^ Позиция любого окна задается парой индексов его левого верхнего эле-мета Соответственно любой элемент [т, п] внутри окна имеет абсолютный индекс [т +/, п + /]•
После обработки любого окна совокупность отсчетов этого окна будет скопирована в одно-
мерный упорядоченный массив (УМ) размером, равным числу элементов в окне^ Для определенности положим, что данные в УМ упорядочены по возрастанию от меньшего индекса к большему, слева—направо • Слоем назовем совокупность окон с одинаковым индексом верхней строки Окна в слое перекрываются (каждое смещено на одну позицию вправо от предыдущего) Аналогично перекрываются слои Тогда перемещение в слое, т^ построение УМ для окна с индексом [т, п + 1], исходя из результатов построения окна с индексом [т, п], сводится к следующему:
1) удаление из УМ всех элементов, соответствующих левому столбцу окна [т, п], т^ по одному элементу, совпадающему с элементом блока памяти [/, п], / = т — т + /т;
2) вставка в УМ всех элементов памяти из столбца [п + ш + 1] из диапазона индексов {т : т +/m}.
Изменение содержания УМ при таком подходе иллюстрирует рис 1.
Операция удаления сводится к следующему:
1) поиск в УМ элемента, равного удаляемому (так как в окне может быть несколько равных элементов, удаляется только первый из найденных равных элементов);
2) переписывание всех элементов УМ, стоящих справа от найденного, в соседние левые позиции
Операция вставки предполагает:
1) путем просмотра УМ слева—направо и сравнения вставляемого значения с элементами УМ поиск элемента, имеющего большее или равное вставляемому значение^
2) переписывание всех элементов, стоящих справа от найденного, в соседние правые позиции;
3) запись на освободившееся место значения, соответствующего вставляемому элементу
Обработка окон в слое выполняется последовательно для всех окон, начиная от крайнего левого, до последнего справа, после чего переходят к следующему (т: = т + 1) слою — и так до последнего нижнего слоя^ Переход на очередной слой может быть выполнен подобно просмотру слева-направо за счет удаления из копии упорядоченного массива для нулевого окна предыдущего слоя элементов его верхней строки и добавления элементов строки снизу
Однако выгоднее оказывается полная инициализация УМ для начального окна каждого слоя, включая самый верхний, нулевой Сначала все элементы УМ сбрасываются в ноль, а затем выполняется его заполнение отсчетами начального окна слоя^ При этом в произвольном порядке все отсчеты текущего окна последовательно передаются на блок упорядочения БУ, где сравниваются со всеми элементами УМ. Просмотром со стороны больших номеров УМ (справа-налево) ищется первый элемент УМ, содержимое которого меньше или равно значению входного отсчета^
п
РЕАЛИЗАЦИЯ МЕДИАННЫХ ФИЛЬТРОВ ИЗОБРАЖЕНИЙ
43
Этот элемент и все стоящие слева от него переписываются в соседние левые позиции, а входное значение записывается в эту позицию.
Структура устройства приведена на рис. 2. Ядром БУ является массив упорядоченных данных УМ. Каждый элемент этого массива OrA(r), где r е {0 : к}, а к = (im +1) х (jm + 1) -1, поступает на одну из схем сравнения, на вторые входы которых приходит значение анализируемого отсчета (input data) Совокупность выходов схем сравнения (больше — не больше) составляет вектор результатов сравнения CV (Comparation Vector).
Модификация УМ выполняется модулем сдвига, логика которого соответствует приведенным правилам и основана на содержании CVи текущей исполняемой операции, задаваемой сигналом Op (operation) — удаление или вставка. Программа VHDL, описывающая модуль сдвига, исполняющий операции удаления и вставки, приведена в [6].
Управление выборкой данных из памяти и задание выполняемых при этом операций осуществляются блоком сканирования и генерации инструкций (БСГИ). Модуль БСГИ представляет собой синхронный цифровой автомат. Он может находиться в двух состояниях: waiting и working.
Waiting — ожидание появления сигнала, означающего, что память заполнена и можно выполнить обработку. Получив сигнал Start, автомат переходит в следующее состояние — working.
Working — состояние, в котором автомат находится до завершения обработки всех окон фильтруемого массива. По каждому тактовому импульсу на блок памяти поступает адрес строки ai и столбца aj очередного анализируемого элемента, а на блок упорядочения — код операции (Op), выполняемой на текущем шаге. В этом режиме исполняются три вложенных цикла. Внешний цикл соответствует обработке слоя. В очередном по иерархии цикле происходит перебор окон одного слоя, а в самом нижнем цикле перебираются элементы первой колонки предыдущего и последней колонки следующего окна и выполняются операции удаления и вставки соответствующих элементов УМ.
Все сравнения и сдвиги при
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.