9.1. Ранговая фильтрация
Рассмотрим в начале выполнение ранговой фильтрации в одномерном случае. При ранговой фильтрации для i-го положения окна сканирования требуется выполнить следующие действия [16]:
Все элементы вектора X, попавшие в окно сканирования, переупорядочиваются в порядке возрастания:
2. В качестве результата yi выбирается значение: , где R – заданный номер позиции элемента в упорядоченном списке.
Производится смещение окна сканирования на одну позицию: i=i+1
3. Повторяются пункты 1-3.
Очевидно, что если R=1, то выполняется так называемая минимальная фильтрация, поскольку всегда в качестве результата выбирается наименьший элемент в окне; если же R=M, - то за результат выбирается максимальный элемент окна.
При R=(M+1)/2 выполняется медианная или срединная фильтрация. При ранговой фильтрации при размере окна M происходит искажение фильтруемого сигнала - высокочастотные компоненты сигнала с периодом <R будут пропущены.
Поэтому для того, чтобы сигнал при фильтрации не был подвержен существенному искажению, необходимо, чтобы:
(при ). (9.1)
Если размер окна относительно невелик, то ранговую фильтрацию можно выполнить посредством упорядочения, т.е. сортировки элементов окна. Однако при больших размерах окна и жестких ограничениях на время фильтрации сортировку следует выполнять только при наличии специальных аппаратных средств - сортирующих сетей [13].
Возможны ещё два алгоритма выполнения РФ:
гистограммный алгоритм;
разрядно-срезовый алгоритм.
При гистограммном алгоритме строится гистограмма H(I), т.е. распределение числа элементов окна по уровням (т.е. по значениям):
(9.2)
При выполнении ранговой фильтрации согласно (9.2) строится гистограмма и вычисляется её площадь (сумма значений), до тех пор, пока число элементов учтённых уровней в гистограмме не превысит значение ранга R. Последний учтённый уровень и определяет значение элемента заданного ранга. На рис.9.1. показан пример нахождения элемента заданного ранга по построенной гистограмме.
Рис. 9.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 лежит среди отсчётов с нулевым старшим битом;
Анализируем второй срез, исключив при его рассмотрении те отсчеты xm, для которых старший бит =1 (т.е. модифицируем второй срез). Если “0” во втором срезе больше, чем R, то это значит, что элемент заданного ранга лежит среди отсчетов со старшими битами “00”;
Анализируем третий срез, исключив при его рассмотрении те отсчеты xm, у которых во втором модифицированном срезе бит =1, т.е. у которых старшие два бита равны “01”. Если “0” в третьем срезе больше, чем R, то это значит, что элемент заданного ранга лежит среди отсчетов со старшими битами “000”;
Анализируем четвертый срез, исключив при его рассмотрении те отсчеты xm, у которых старшие биты равны ”001”. Если “0” в младшем срезе больше, чем R, то это значит, что элемент заданного ранга лежит среди отсчетов со старшими битами “0000”, иначе среди тех, у которых младший бит =1, т.е. xm,=”0001”.
Заметим, что “1” в последнем младшем срезе указывает и местоположение, и число элементов заданного ранга
Подобный алгоритм получил название разрядно-срезового алгоритма со сквозным маскированием. Очевидно, что отдельно взятый разрядный срез не позволяет определить искомый элемент . Для этого необходимо дополнительно иметь результаты анализа на предыдущих итерациях поиска. Поэтому в разрядно - срезовом алгоритме требуется, чтобы при переходе к анализу текущего разрядного среза были известны все элементы, исключенные из поиска на предыдущих этапах, т.е. требуется задание срезовой маски. В результате обработки текущего разрядного среза определяется очередной разряд результатаи маска, содержащая всю информацию об исключенных элементах списка на q -ом этапе поиска.
Запишем подобный алгоритм (для фиксированного положения окна) [16]:
начало:
;
для цикл:
для цикл:
для цикл:
если то,
иначе
конец цикла по ;
конец цикла по ;
;
если , то
для цикл:
для цикл:
для цикл:
;
конец цикла по ;
конец цикла по ;
конец цикла по
иначе
для цикл:
для цикл:
для цикл:
;
конец цикла по ;
конец цикла по ;
конец цикла по
конец цикла по ;
;
конец.
Недостатком алгоритма со сквозным маскированием является необходимость после анализа текущего среза модифицировать все последующие, что резко увеличивает объем вычислений и практически не позволяет распараллелить вычисления по срезам. Указанный недостаток преодолевается путем ввода маски, воздействующей только на один последующий срез и не изменяющей другие разрядные срезы.
Такая маска может быть найдена в соответствии с выражением [22]:
, (5.3)
где - q-й разрядный срез элементов окна, а символ # обозначает логическую операцию неравнозначности. Накапливаемая суммаопределяется в этом случае из соотношения:
(5.4)
Такой подход и является основой алгоритма с последовательным маскированием. Таким образом, для обработки последующего разрядного среза необходимо сформировать маскуи передать предыдущий разрядный срез.
Возможны три варианта процедуры разрядно-срезовой ранговой фильтрации: четный, нечетный и четно-нечетный алгоритмы. На каждой q-й итерации четного алгоритма анализируются элементы q-го разрядного среза, имеющие четные значения, т.е. элементы, q-ый разряд которых равен нулю. Для нечетного алгоритма на q-й итерации учитываются те элементы, соответствующий q-й разряд которых равен единице, а в четно-нечетном алгоритме на различных итерациях могут учитываться как четные, так и нечетные элементы .
В разрядно-срезовых алгоритмах каждый разрядный срез должен быть представлен как битовая строка длиной М2 бит, что при размере окна более чем 5 х 5 превышает разрядность большинства существующих операционных элементов. Поэтому в разрядно-срезовых алгоритмах следует предусмотреть возможность обработки разрядных срезов по фрагментам (например по столбцам). В этом случае обрабатывается вектор длиной лишь М бит.
Модифицированный четный разрядно-срезовый алгоритм ранговой фильтрации, позволяющий оптимизировать конвейерный режим вычислений с возможностью обработки срезов по столбцам, может быть записан в следующем виде [22]:
Начало :
;
цикл для :
;
;
цикл для
;
конец цикла по
;
если , то
;
цикл для
конец цикла по ;
иначе
цикл для
конец цикла по ;
конец цикла по ;
;
конец.
Здесь Q - разрядность данных; - q-я разрядно-срезовая бинарная маска ;- q-й разрядный срез матрицы данных ;- число единичных бит в маскированном разрядном срезе- вычисленое значение q-го разряда результата;- результат ранговой фильтрации.
Следует отметить, что при использовании подобного алгоритма может быть определена не только величина элемента заданного ранга R, но и его местоположение в окне. Информация о местоположении элемента содержится в бинарной маске, сформированной на последней итерации алгоритма. Положение единичного бита (или единичных бит) определяет положение элементов заданного ранга R в окне сканирования.
Рассмотрим примеры выполнения ранговой фильтрации по разрядно-срезовому алгоритму со сквозным маскированием.
1. Пусть 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.
2. Пусть для того же окна надо найти элемент ранга 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.
Yandex.RTB R-A-252273-3
- Цифровая обработка сигналов
- Санкт-Петербург
- Содержание
- 7.2. Вейвлеты 106
- Введение
- 1. Основные понятия цифровой обработки сигналов
- Понятие о первичной и вторичной обработке сигналов
- Основные требования к системам цос
- 2. Понятие сигналов. Виды сигналов
- 2.1. Виды сигналов
- 2.2. Энергия и мощность сигнала
- 2.3. Представление периодических сигналов в частотной области
- 2.4. Представление в частотной области непериодических сигналов
- Введение в теорию ортогональных преобразований
- 2.4.2. Интегральное преобразование Фурье
- 2.5. Свойства преобразования Фурье
- 2.5.1. Фурье-анализ неинтегрируемых сигналов
- 2.6. Интегральное преобразование Хартли
- 2.7. Случайные сигналы
- 2.7.1.Модели случайных процессов
- 2.7.2. Вероятностные характеристики случайного процесса Функциональные характеристики.
- Числовые характеристики
- Примеры случайных процессов с различными законами распределения
- 3. Корреляционный анализ сигналов
- 3.1. Корреляционная функция (кф):
- 3.2. Взаимная корреляционная функция
- 3.3. Взаимный спектр сигналов
- 3.4. Корреляционные функции случайных процессов
- 3.4.1. Стационарные и эргодические случайные процессы
- 3.5. Спектральные характеристики случайных процессов
- 3.5.1. Теорема Винера-Хинчина
- 3.6. Комплексная огибающая сигнала
- 4. Переход от аналоговых сигналов к цифровым
- 4.1. Дискретизация сигналов
- 4.1.1. Влияние формы дискретизирующих импульсов
- 4.1.2. Теорема Котельникова
- 4.1.3. Дискретизация при использовании квадратурных сигналов
- 4.1.4. Определение шага временной дискретизации при восстановлении сигнала полиномами 0-го порядка
- 4.1.5. Определение шага дискретизации при заданной автокорреляционной функции
- Изменение частоты дискретизации. При решение различных задач обработки сигналов достаточно часто требуется изменение частоты дискретизации сигнала.
- 4.2. Квантование непрерывных сигналов по уровню
- 5. Основные типы дискретных алгоритмов цифровой обработки сигналов
- 5.1. Линейные и нелинейные преобразования
- 5.2. Характеристики линейных систем
- 5.4. Апериодическая свертка и корреляция
- 5.5. Двумерная апериодическая свертка и корреляция
- 5.6 Нерекурсивные и рекурсивные фильтры
- 5.7. Метод синхронного или когерентного накопления
- 5.8. Адаптивные фильтры.
- 5.8.1. Фильтр Винера-Хопфа.
- 5.10. Фильтр Калмана.
- 6. Дискретные ортогональные преобразования
- Задачи цос, решаемые методами дискретных ортогональных преобразований
- 6.1. Дискретное преобразование Фурье
- 6.2. Дискретное преобразование Хартли
- 6.3. Двумерные дискретные преобразования Фурье и Хартли
- 6.4. Ортогональные преобразования в диадных базисах
- 6.5. Дискретное косинусное преобразование
- 6.6. Оконное преобразование Фурье
- 6.7. Выполнение фильтрации в частотной области
- Виды фильтров
- 7. Вейвлет преобразования или разложение по всплескам
- 7.1. Понятие о Wavelet-преобразованиях. Преобразование Хаара
- 7.2. Вейвлеты
- 7.2.1. Непрерывные вейвлет преобразования
- 7.2.2. Частотный подход к вейвлет преобразованиям
- 7.2.3. Вейвлет-ряды дискретного времени
- 7.2.4. Дискретное вейвлет-преобразование
- 7.2.4.1. Условия полного восстановления сигнала
- 7.2.5. Пакеты вейвлетов (алгоритм одиночного дерева)
- 7.2.6. Целочисленное вейвлет-преобразование
- Целочисленное вычисление вейвлет–преобразование (2,2). Это преобразование эквивалентно вейвлет-преобразованию Хаара, использующему следующие фильтры декомпозиции:
- Целочисленное вычисление вейвлет-преобразования (2,6). Данное преобразование эквивалентно использованию следующих фильтров анализа:
- Целочисленное вычисление вейвлет –преобразования (5,3). Такое преобразование также является разновидностью биортогонального преобразования и использует следующую пару фильтров:
- 7.3. Применение вейвлет-преобразований для сжатия изображения
- 8. Быстрые алгоритмы ортогональных преобразований
- 8.1. Вычислительная сложность дпф и способы её сокращения
- 8.2. Запись алгоритма бпф в векторно-матричной форме
- 8.3. Представление алгоритма бпф в виде рекурсивных соотношений
- 8.4. Алгоритмы бпф с прореживанием по времени и по частоте
- 8.6. Вычислительная сложность алгоритмов бпф
- 8.7. Выполнение бпф для случаев
- 8.8. Быстрое преобразование Хартли
- 8.9. Быстрое преобразование Адамара
- 8.10. Выбор метода вычисления свертки / корреляции
- 9. Алгоритмы нелинейной обработки сигналов
- 9.1. Ранговая фильтрация
- 9.2. Взвешенная ранговая фильтрация
- 9.3. Скользящая эквализация гистограмм
- 9.4. Преобразование гистограмм распределения
- Контрольные вопросы и задания. Разделы 1-3.
- Раздел 4
- Разделы 5 и 6
- Раздел 5
- Раздел 8
- Раздел 9
- Кафедра вычислительной техники