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

          Рассмотрим вначале выполнение ранговой фильтрации в одномерном случае. При ранговой фильтрации для i-го положения окна сканирования требуется  выполнить следующие действия:
1.	Все элементы вектора X, попавшие в окно сканирования, переупорядочиваются в порядке возрастания: 

2.	В качестве результата yi выбирается значение: , где R -  номер заданный позицией элемента в упорядоченном ряду элементов вектора X.
3.	Производится смещение окна сканирования на одну позицию: i=i+1
4.	Повторяются  пункты с 1-3.

Если R=1, то выполняется так называемая минимальная фильтрация; а если R=M, - то максимальная.

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

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

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

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

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

Пример

	

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

	Гистограммный алгоритм  ранговой  фильтрации  для  окна размером М х М может быть представлен в следующем виде :
начало;
H(I):=0;       для  
	для  цикл:
		для  цикл:
			;
		конец цикла по ;
	конец цикла по ;                                                              (А.12.1)
	
	для  цикл:
		если  то выход из цикла;
		иначе ;
	конец цикла по ;
	;
конец
	Здесь - значение отсчета с номером (m,n),   - разрядность отсчетов. Поскольку фильтрация выполняется в скользящем режиме, то при перемещении окна вдоль строки изображения  достаточно  модифицировать  имеющуюся гистограмму предшествующего положения окна,  включив в нее  элементы  нового столбца и  исключив  элементы,  соответствующие   "ушедшему" столбцу. Модификация гистограммы сводится к следующим операциям:
	выполнить М раз вычитание H(I) := H(I) - 1  для  элементов  столбца,  выходящего из окна сканирования;
	выполнить М раз сложение H(I) := H(I) + 1 для элементов  нового столбца полосы.
	Очевидно, что такой подход позволяет значительно сократить время формирования гистограммы.  Дальнейшее  сокращение времени  фильтрации  может  быть достигнуто путем сокращения времени поиска элемента заданного ранга.  Для этого оказывается удобным строить не одну,  а  гистограмм,  причем  строится только по старшему разряду,  - по двум старшим разрядам  и  так далее,  до ,  которая строится по всем разрядам элементов окна. В результате поиск по  организуется  как поиск по  - уровневому бинарному дереву.  Поиск результата начинается с первой гистограммы ,  по  которой определяется старший разряд. Анализ каждой следующей гистограммы уточняет очередной младший разряд результата,  в  результате  за   циклов будет определен -разрядный результат фильтрации .
  
	Разрядно-срезовый алгоритм РФ может быть интерпретирован как  поиск необходимого значения по по двоичному дереву:

Пусть M=15; q=4

q1	0	0	0	0	0	1	1	0	0	0	0	0	0	0	1	3 старший срез	
q2	0	0	0	0	1	0	1	0	0	0	1	0	0	0	1	2 второй срез	
q3	0	0	1	0	0	1	0	1	1	1	0	0	0	1	0	1 третий срез	
q4	0	1	0	0	0	1	0	0	0	0	0	1	0	1	0	0 младший срез	
	0	1	2	0	4	11	2	2	2	2	4	1	0	3	12		
	xm	

R1=5

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

В нашем случае .

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

Подобный алгоритм получил название разрядно-срезового алгоритма со сквозным маскированием .

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

начало:
	;
	для  цикл:
		
		для  цикл:                                    (А.12.2)
			для  цикл:
				если  то ,
				иначе 
			конец цикла по ;
		конец цикла по ;
		;
		если , то

				для  цикл:
					для  цикл:
						для  цикл:
						;
						конец цикла по ;
					конец цикла по ;
				конец цикла по 

		иначе 

				для  цикл:
					для  цикл:
						для  цикл:
						;
						конец цикла по ;
					конец цикла по ;
				конец цикла по 
			
	конец цикла по ;
	;
конец.

	Недостатком алгоритма со сквозным маскированием является  необходимость после анализа текущего среза модифицировать все последующие, что резко увеличивает объем вычислений и практически не позволяет распараллелить вычисления по срезам.  Указанный недостаток преодолевается путем ввода маски, воздействующей только на один последующий срез и не изменяющей другие разрядные срезы.
	Такая маска может быть найдена в соответствии с выражением: 
,	         (12.2)
где - q-й разрядный срез элементов окна, а символ # обозначает  логическую операцию неравнозначности.  Накапливаемая сумма  определяется в этом случае из соотношения:
	(12.3)
	Такой подход  и  является основой алгоритма с последовательным маскированием. Таким образом, для обработки последующего разрядного среза  необходимо сформировать маску  и передать предыдущий разрядный срез .
Очевидно, что  отдельно  взятый  разрядный срез не позволяет определить искомый элемент . Для этого  необходимо  дополнительно иметь результаты анализа на предыдущих итерациях поиска.  Поэтому в разрядно-срезовом алгоритме требуется,  чтобы  при  переходе  к анализу  текущего  разрядного  среза  были известны все элементы, исключенные из поиска на предыдущих этапах,  т.е. требуется задание  срезовой  маски.  В результате обработки текущего разрядного среза определяется очередной разряд результата  и маска, содержащая  всю  информацию  об  исключенных элементах списка на q -ом этапе поиска.
	Возможны три варианта такой процедуры ранговой  фильтрации: четный,  нечетный и четно-нечетный алгоритмы. На каждой q-й итерации четного алгоритма анализируются элементы  q-го  разрядного среза, имеющие четные значения, т.е. элементы, q-ый разряд которых равен нулю. Для нечетного алгоритма на q-й итерации учитываются те элементы,  соответствующий q-й разряд которых равен единице,  а в четно-нечетном алгоритме на различных итерациях могут учитываться как четные, так и нечетные элементы .
	В разрядно-срезовых алгоритмах каждый разрядный срез должен быть представлен как битовая строка длиной М2 бит, что при размере окна > 5 Х 5 превышает разрядность большинства существующих операционных элементов. Поэтому в разрядно-срезовых алгоритмах следует предусмотреть возможность обработки разрядных срезов по фрагментам (например по столбцам). В этом случае обрабатывается вектор длиной лишь М бит.
	Модифицированный четный  разрядно-срезовый  алгоритм ранговой фильтрации, позволяющий оптимизировать конвейерный режим вычислений с возможностью обработки срезов по столбцам, может быть записан в следующем виде :

Начало :
	;
	цикл для :
		;
		;
		цикл для 
			;
		конец цикла по                                                 (А.12.3)
		;
	если , то 
			;
			цикл для 
			
			конец цикла по ;
		иначе 
			цикл для 
			
			конец цикла по ;

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

	Здесь  - разрядность данных;  - q-я разрядно-срезовая бинарная маска ; - q-й разрядный срез матрицы данных  ; - число единичных бит в маскированном разрядном срезе - вычисленое значение q-го разряда результата; - результат ранговой фильтрации.
	Следует отметить,  что при использовании  подобного  алгоритма может быть определена не только величина элемента заданного ранга R,  но и его местоположение в окне.  Информация о  местоположении элемента  содержится  в бинарной маске ,  сформированной на последней итерации алгоритма. Положение единичного бита (или единичных  бит)  определяет  положение элементов заданного ранга R в окне сканирования.
	Рассмотрим пример выполнения ранговой фильтрации по разрядно-срезовому алгоритму со сквозным маскированием.
	Пусть MM=55; Q=4 и надо определить элемент ранга.

R=13 (медиана)
          
0) S0=11...1111;			1) 1=S0&=15;			2) 2=S1&;
    D0=-13;			     D1=-13+15=2; D1>0;d1=0;		     D2=-13+6=--7;
    Yi0=IR;			     D1=-13; S1= S0&;			     D2=-7; d2=1; D2<0;
    D2=-7; S2=S1&;
                     
3) 3=S2&;						4) 4=S3&;
     D3=-7+4=-3; D3=-3; d3=1; D3<0;			     D4=-3+2=-1; d4=1;
     S3= S2&;						     S4=S3&;

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

Тот же пример, но R=18.
R=18; IR18=10.

0) S0=11...1111;		1) 1=S0&=15;			2) 2=S1&=4;
    D0=-18;		     D1=-18+15=-3; D1<0;d1=1;		     D2=-3+4=1;
			     D1=-3; S1= S0&;			     d2=0; D2>0; D2=-3;
     S2=S1&;
                                     
3) 3=S2&=2;					4) 4=S3&=1;
     D3=-3+2=-1; D3<0; D3=-1; d3=1;			     D4=-1+1=0; d4=0; D4=0;
     S3= S2&;						     S4=S3&;

“1” в S4 показывает, где расположен IR.
Ранговая, и в частности, медианная фильтрация весьма эффективны при решении задач фильтрации (подавления) импульсных помех