ТеорИнфМетоды / metod_1

5.1. Ранговая фильтрация

Рассмотрим в начале выполнение ранговой фильтрации в одномерном случае. При ранговой фильтрации для i-го положения окна сканирования требуется выполнить следующие действия [16]:

Все элементы вектора X, попавшие в окно сканирования, переупорядочиваются в порядке возрастания:

2. В качестве результата y_i выбирается значение: , где R – заданный номер позиции элемента в упорядоченном списке.

Производится смещение окна сканирования на одну позицию: i=i+1

3. Повторяются пункты 1-3.

Очевидно, что если R=1, то выполняется так называемая минимальная фильтрация, поскольку всегда в качестве результата выбирается наименьший элемент в окне; если же R=M, - то за результат выбирается максимальный элемент окна.

При R=(M+1)/2 выполняется медианная или срединная фильтрация. При ранговой фильтрации при размере окна M происходит искажение фильтруемого сигнала - высокочастотные компоненты сигнала с периодом <R будут пропущены.

Поэтому для того, чтобы сигнал при фильтрации не был подвержен существенному искажению, необходимо, чтобы:

(при ). (5.1)

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

Возможны ещё два алгоритма выполнения РФ:

гистограммный алгоритм;
разрядно-срезовый алгоритм.

При гистограммном алгоритме строится гистограмма H(I), т.е. распределение числа элементов окна по уровням (т.е. по значениям):

_(5.2)

При выполнении ранговой фильтрации согласно (5.2) строится гистограмма и вычисляется её площадь (сумма значений), до тех пор, пока число элементов учтённых уровней в гистограмме не превысит значение ранга R. Последний учтённый уровень и определяет значение элемента заданного ранга. На рис.5.1. показан пример нахождения элемента заданного ранга по построенной гистограмме.

Рис.5.1. Гистограмма распределения элементов по уровням

Гистограммный алгоритм ранговой фильтрации для окна размером М х М может быть представлен в следующем виде [16,22]:

начало;

H(I):=0; для 

для цикл:

;

конец цикла по ;

для цикл:

если то выход из цикла;

иначе ;

конец цикла по ;

;

конец

Здесь - значение отсчета с номером (m,n),Q - разрядность отсчетов. Поскольку фильтрация выполняется в скользящем режиме, то при перемещении окна вдоль строки изображения достаточно модифицировать имеющуюся гистограмму предшествующего положения окна, включив в нее элементы нового столбца и исключив элементы, соответствующие "ушедшему" столбцу. Модификация гистограммы сводится к следующим операциям:

· выполнить М раз вычитание H(I) := H(I) - 1 для элементов столбца, выходящего из окна сканирования;

· выполнить М раз сложение H(I) := H(I) + 1 для элементов нового столбца полосы.

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

Разрядно-срезовый алгоритм РФ может быть интерпретирован как поиск необходимого значения по по двоичному дереву и сведен к следуещему( пусть разрядность данных – 4 бита) :

Анализируем биты старшего среза. Если “0” больше, чем R, то это значит, что элемент ранга R лежит среди отсчётов с нулевым старшим битом;
Анализируем второй срез, исключив при его рассмотрении те отсчеты x_m, для которых старший бит =1 (т.е. модифицируем второй срез). Если “0” во втором срезе больше, чем R, то это значит, что элемент заданного ранга лежит среди отсчетов со старшими битами “00”;
Анализируем третий срез, исключив при его рассмотрении те отсчеты x_m, у которых во втором модифицированном срезе бит =1, т.е. у которых старшие два бита равны “01”. Если “0” в третьем срезе больше, чем R, то это значит, что элемент заданного ранга лежит среди отсчетов со старшими битами “000”;
Анализируем четвертый срез, исключив при его рассмотрении те отсчеты x_m, у которых старшие биты равны ”001”. Если “0” в младшем срезе больше, чем R, то это значит, что элемент заданного ранга лежит среди отсчетов со старшими битами “0000”, иначе среди тех, у которых младший бит =1, т.е. x_m,=”0001”.

Заметим, что “1” в последнем младшем срезе указывает и местоположение, и число элементов заданного ранга

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

Запишем подобный алгоритм (для фиксированного положения окна) [16]:

начало:

;

для цикл:

если то,

иначе

конец цикла по ;

;

если , то

для цикл:

;

конец цикла по ;

конец цикла по

иначе

для цикл:

;

конец цикла по ;

конец цикла по

конец цикла по ;

;

конец.

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

Такая маска может быть найдена в соответствии с выражением [22]:

, (5.3)

где - q-й разрядный срез элементов окна, а символ # обозначает логическую операцию неравнозначности. Накапливаемая суммаопределяется в этом случае из соотношения:

(5.4)

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

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

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

Модифицированный четный разрядно-срезовый алгоритм ранговой фильтрации, позволяющий оптимизировать конвейерный режим вычислений с возможностью обработки срезов по столбцам, может быть записан в следующем виде [22]:

Начало :

;

цикл для :

;

цикл для

;

конец цикла по

;

если , то

;

цикл для

конец цикла по ;

иначе

цикл для

конец цикла по ;

;

конец.

Здесь Q - разрядность данных; - q-я разрядно-срезовая бинарная маска ;- q-й разрядный срез матрицы данных ;- число единичных бит в маскированном разрядном срезе- вычисленое значение q-го разряда результата;- результат ранговой фильтрации.

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

Рассмотрим примеры выполнения ранговой фильтрации по разрядно-срезовому алгоритму со сквозным маскированием.

1. Пусть MM=55; Q=4 и надо определить элемент рангаR=13 (выполняется медианная фильтрация)

0) S₀=11…1111; 1) ₁=S₀&=15; 2) ₂=S₁&;

D₀=-13; D₁=-13+15=2; D₁>0;d₁=0; D₂=-13+6=--7;

Y_i0=I_R; D₁=-13; S₁= S₀&; D₂=-7; d₂=1; D₂<0;

D₂=-7; S₂=S₁&;

3) ₃=S₂&; 4) ₄=S₃&;

D₃=-7+4=-3; D₃=-3; d₃=1; D₃<0; D₄=-3+2=-1; d₄=1;

S₃= S₂&; S₄=S₃&;

“1” в S4 показывает, где расположен I_R.

2. Пусть для того же окна надо найти элемент ранга R=18.

R=18; I_R18=10.

0) S₀=11…1111; 1) ₁=S₀&=15; 2) ₂=S₁&=4;

D₀=-18; D₁=-18+15=-3; D₁<0;d₁=1; D₂=-3+4=1;

D₁=-3; S₁= S₀&; d₂=0; D₂>0; D₂=-3;

S₂=S₁&;

3) ₃=S₂&=2; 4) ₄=S₃&=1;

D₃=-3+2=-1; D₃<0; D₃=-1; d₃=1; D₄=-1+1=0; d₄=0; D₄=0;

S₃= S₂&; S₄=S₃& ;

“1” в S4 показывает, где расположен I_R.

Содержание