6.4.Программирование медианного фильтра

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

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

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

.RSECT

pbuf: .DS 1 ;указатель на кольцевой буфер

bufO: .DS 1 ;ранг записывается в R4

buf1: .DS 1 ;ранг записывается в R5

buf2: .DS 1 ;ранг записывается в R6

buf3: .DS 1 ;ранг записывается в R7

Значения рангов (информации о старшинстве сигналов) будем нака­пливать в регистрах общего назначения. Предназначим регистр R3 для ранга входного сигнала, а регистры R4, R5, R6 и R7 для рангов сигналов, хранящихся в буфере. В начале работы программы в эти регистры заносятся нули. Для подсчета рангов пяти сигналов нужно произвести сравнение 10 пар значений (аналогично проведению турнира по круговой системе). При равенстве значений сигналов содержимое соответствующих им регистров не изменяется. При неравенстве в регистр большего сигнала добавляется 1, а из регистра меньшего сигнала вычитается 1. Определим операцию накопления ранга с двумя формальными параметрами, факти­ческие значения которых должны соответствовать номерам используемых регистров:

.CODE

RANK: .MACRO f, s

CJNE A, buf|<s-4>, ch#

SJMP ex#

ch#: JC lt#

INC R|f

DEC R|s

SJMP ex#

lt#: DEC R|f

INC R|s

ex#:

.ENDM

Перед использованием этой операции в накопитель нужно занести сиг­нал, соответствующий первому фактическому параметру. В регистровых операндах команд счета используется подстановка символа фактического параметра, что обозначено операцией конкатенации (вертикальная черта). Во втором операнде команды сравнения в результате подстановки долж­но быть записано имя ячейки буфера. Перед подстановкой приходится выполнять арифметическую операцию вычитания. Необходимость вы­числения выражения до подстановки обозначена угловыми скобками. Все метки в операции подсчета рангов локальные. При равенстве сигналов выполняется 2 команды. Если первый сигнал меньше второго, то выпол­няется 4 команды. Если первый сигнал больше второго, то выполняется 6 команд.

Запишем часть программы, осуществляющую подсчет рангов. За счет применения сложной текстовой подстановки исходный текст для подсчета рангов получился компактным и легко читаемым:

MOV А, #0

MOV R3 , А

MOV R4, А

MOV R5, А

MOV R6, А

MOV R7, А ; запись нулей в счетчики ранга

MOV A, x ; для проверки входного сигнала

RANK 3, 4

RANK 3, 5

RANK 3, 6

RANK 3, 7

MOV A, buf0 ; для проверки 0-ой ячейки буфера

RANK 4, 5

RANK 4, 6

RANK 4, 7

MOV A, buf1 ; для проверки 1-ой ячейки буфера

RANK 5, 6

RANK 6, 7

MOV A, buf2 ; для проверки 2-ой ячейки буфера

RANK 6, 7

Но главное достоинство использования сложной текстовой подстановки зак­лючается в том, что вся формальная работа по записи меток и операндов осуществляется ассемблером. Транслятор преобразует приведенные 20 строк исходного текста в 100 и переведет их в 100 машинных команд с 30 метками. Теперь по содержимому регистров нужно определить, в какой ячейке находится медиана. Если бы все сигналы были разные, то все ранги также были бы разными. Поэтому медиану можно было бы найти по регистру с нулевым содержимым. В случае совпадения значений сигналов поиск медианы несколько усложняется. Рассмотрим все варианты распределения рангов, расположенных по старшинству:

0, 0, 0, 0, 0 значения всех сигналов совпадают

+1,+1,+1,+1,-4

+2,+2,+2,-3,-3

+2,+2,+2,-2,-4

+3,+3,-2,-2,-2

+3,+3,-1,-1,-4

+3,+3, 0,-3,-3

+3,+3, 0,-2,-4

+4,-1,-1,-1,-1

+4, 0, 0, 0,-4

+4,+1,+1,-3,-3

+4,+1,+1,-2,-4

+4,+2,-2,-2,-2

+4,+2,-1,-1,-4

+4,+2, 0,-3,-3

+4,+2, 0,-2,-4 значения всех сигналов различны

Анализ всех 16 вариантов показывает, что ранг с модулем не более 1 всегда соответствует медиане. Если минимальный модуль ранга равен 2, то медиане соответствует ранг с таким знаком, какой имеется еще у двух таких же значений ранга. Ранги с модулями 3 и 4 никогда не соответст­вуют медиане.

Для определения номера регистра, удовлетворяющего заданным требованиям, используется сложная текстовая подстановка с одним формальным параметром. Если в результате проверки удалось вычислить номер регистра, соответствующего медиане, то управление передается на нелокальную метку в ту часть программы, которая должна записать медиану в ячейку у:

MDN: .MACRO n

MOV R0, #|n

MOV A, R|n

JZ 1dm

JNB A.7, pls#

CPL A

SJMP chl#

pls#: DEC A

chl#: JZ 1dm

DEC A

JNZ nxt#

MOV A, R|n

JB A.7, ch2 #

INC Rl

CJNE Rl, #3, nxt#

SJMP 1dm

SJMP nxt#

ch2#: INC R2

CJNE R2, #3, nxt#

SJMP 1dm

nxt#:

.ENDM

Сначала на случай обнаружения подходящего ранга в регистр RO зано­сится номер проверяемого регистра. Затем содержимое проверяемого регистра пересылается в накопитель. В случае нулевого ранга управление передается на загрузку медианы. В противном случае вычисляется модуль ранга, уменьшенный на единицу. Если модуль ранга равен 1, то управление передается на загрузку медианы. Если он больше 2, то управление пере­дается на последнюю метку подстановки. Для рангов +2 и -2 в регистрах R1 и R2 подсчитывается количество соответствующих им сигналов. Если содержимое счетчика оказалось равным 3, управление передается на загрузку медианы. Время выполнения подстановки зависит от содержи­мого проверяемых регистров. При нулевом ранге выполняется 3 команды, а при рангах +1 и -1 — 6 и 7 команд соответственно. При рангах +3 и +4 выполняется 8 команд, а при рангах -3 и -4 выполняется 9 команд. При модуле ранга, равном 2, выполняется 14 команд.

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

MOV R1, #0 ; для подсчета количества рангов +2

MOV R2, #0 ; для подсчета количества рангов -2

MDN 3

MDN 4

MDN 5

MDN 6

MOV R0, t7 /проверка рангов завершена

Длительность поиска медианы существенно зависит от расположения выборок в массиве. В наилучшем случае, когда нулевой ранг содержится в первом проверяемом регистре, поиск займет 3 команды. Если нулевой ранг содержится в последнем проверяемом регистре, то для поиска медианы придется затратить свыше 40 команд. Наиболее длительным оказывается поиск медианы при трех совпавших сигналах, когда модуль ранга равен 2. Обратите внимание на то, как по номеру регистра вычисля­ется адрес передачи управления на команду записи медианы в ячейку у.

Idm: MOV A, R0 ; номер регистра

MOV В, #5 ; длина блока загрузки медианы

MUL АВ ; для вычисления адреса перехода

SUBB А, #15 ; смещение относительно адреса Idy

MOV DPTR, #ldy

JMP @A+DPTR

Idy: MOV у, х

SJMP Idx

MOV y, bufO

SJMP Idx

MOV y, bufl

SJMP Idx

MOV y, buf2

SJMP Idx

MOV y, buf3

В завершение программы производится запись входного сигнала в буфер:

Idx: INC pbuf

ANL pbuf, #03h

MOV A, pbuf

ADD A, #buf0

MOV R0, A

MOV @R0, x ; запись входного сигнала в буфер

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

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