Устройство ранговой фильтрации

 

Изобретение относится к специализированным устройствам вычислительной техники, выполняющим ранговую фильтрацию полутоновых изображений (поиск элемента, стоящего на определенном месте в упорядоченной последовательности из всех элементов выборки) в системах обработки изображений в реальном времени для устранения импульсных помех. Целью изобретения является упрощение устройства и увеличение быстродействия при получении результата из накопленной гистограммы. Цель достигается за счет того, что устройство состоит из P блоков (2≤P≤K, где K - разрядность фильтрации), в блоках памяти происходит накопление гистограмм не по одному значению, а в пределах определенных интервалов, из критерия ранга вычитается значение, полученное в старших каскадах, после накопления гистограммы результат получается параллельным способом во всех блоках устройства. Устройство содержит вычислительный блок 1 и (P-1) блоков 2 накопления гистограммы. 3 ил.

союз соВетских

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (si)s 6 06 F 15/353

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Диг, Г (21) 4718372/24 (22) 11.07.89 (46) 07.07.91. Бюл. М 25 (71) Специальное конструкторское бюро научного приборостроения СО АН СССР (72) В.В. Воробьев, Ю.В. Обидин и А.Н. Хегай (53) 681.32(088.8) (56) Оап1е!зоп В, Е. Getting the median faster.

Computer Grapiss and Image Processing, 1981, ч,1 7, М 1, р. 71-78.

Авторское свидетельство СССР

1Ф 1304036, кл. G 06 F 15/353, 1985. (54) УСТРОЙСТВО РАНГОВОЙ ФИЛЬТРАЦИИ (57) Изобретение относится к специализированным уСтройствам вычислительной техники, выполняющим ранговую фильтрацию полутоновых изображений (поиск элемента, стоящего на определенном месте в упорядо. Ж 1661794 А1 ченной последовательности из всех элементов выборки) в системах обработки изображений в реальном времени для устранения импульсных помех, Целью изобретения является упрощение устройства и увеличение быстродействия при получении результата из накопленной гистограммы, Цель достигается за счет того, что устройство состоит из р блоков (2 < p < К где М вЂ” разрядность фильтрации), в блоках памяти происходит накопление гистрограмм не по одному значению, а в пределах определенных интервалов, из критерИя ранга вычитается значение, полученное в старших каскадах, после накопления гистограммы результат получается параллельным способом во всех блоках устройства. Устройство содержит вычислительный блок 1 и р — 1 блоков 2 накопления гистограммы. 3 ил.

1661794

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

Цель изобретения — упрощение устройства и увеличение быстродействия при получении результата из накопленной гистограммы;

На фиг, 1 приведена структурная схема устройства; на фиг. 2 — функциональная схема вычислительного блока; на фиг, 3 — функциональная схема блока накопления гистограммы.

Устройство (фиг. 1) содержит вычислительный блок 1, р-1 блоков 2 накопления гистограммы, (2 < р < k, k — разрядность фильтрации), вход 3 данных устройства, вход 4 критерия ранга, устройства, вход 5 знака приращения устройства, вход 6 признака конца маски устройства, вход 7 управления считыванием-записью устройства, выход 8 результата устройства, Вычислительный блок 1 (фиг. 2) содержит дешифратор 9, элемент НЕ 10, группу элементов ИЛИ 11, первую группу элементов И 12, вторую группу элементов И 13, группу реверсивных счетчиков 14, мультиплексор 15, группу узлов 16 сравнения, приоритетный шифратор 17, выход 18 результата блока, вход 19 логического нуля блока 1, выход 20 блока 1..

Блок 2i накопления гистограммы (фиг. 3) содержит мультиплексор 21, дешифратор

22, группу элементов ИЛИ 23, группу блоков

24 памяти, реверсивные счетчики 25, вычислитель 26, мультиплексор 27, группу узлов

28 сравнения, приоритетный шифратор 29, вхОды 30-32 блока, выходы 33 — 35 блока.

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

Устройство содержит несколько каскадов счетчиков. В первом каскаде весь диапазон допустимых значений данных разбивается на N равных зон. Каскад содержит М-1 счетчиков для подсчета количества поступающих в устройство данных. Первый счетчик считает только те значения, которые попадают в первую зону, второй считает значения, относящиеся к двум первым зонам, третий накапливает количество эле

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

10 сколько раз во входной последовательности встречались значения меньшие, чем границы зон. Поскольку значение Х соответствует рангу в том случае, если в последовательности имеется r — 1 меньших или

15 равных ему значений (по определению ранга), то, следовательно, номер счетчика, содержащего первое превышающее ранг число, однозначно определяет зону, в которой следует искать Х, 20 Для уточнения значения Хг каждая зона разделяется на N участков во втором каскаде. Счетчики второго каскада работают в процессе загрузки параллельно со счетчиками первого каскада. Распределение участ25 ков диапазона между счетчиками одной эоны аналогично распределению в первом каскаде, т.е. первый счетчик считает количество значений в первом участке диапазона, второй в первом и втором, третий — в пер30 вом, втором и третьем и т.д. Счетчики накапливают количество элементов, значения которых лежат в пределах, ограниченных снизу началом зоны, а сверху — концом своего участка в этой зоне. Такое разделение

35 диапазона значений между счетчиками второго каскада может потребовать одновременно изменять содержимое не более чем у

N — 1 счетчиков одной зоны, которые должны быть реализованы аппаратно. Содержимое

40 всех счетчиков второго каскада сохраняется в N-1 блоках памяти (в первом блоке первый счетчик, во втором второй и т.д,). Номер зоны, к которой относится обрабатываемое значение, определяет при этом ячейку памя45 ти в каждом иэ блоков. Счетчики первой эоны лежат в первых ячейках блоков, счетчики второй зоны во вторых, третьей — в третьих и т.д.

В третьем каскаде каждый из участков

50 второго каскада разбивается еще íà N равных частей. Работа третьего каскада не отличается от работы второго. Отличие третьего каскада от второго заключается только в емкости каждого из N — 1 блоков

55 памяти, которая равна полному числу участков (N *N). Разбиение всего диапазона значений продолжается до тех пор, пока не будет обеспечена необходимая точность вычисления значения Хг, соответствующего рангу. Для минимизации аппаратуры и

1661794

30

50 удобства работы с двоичными значениями необходимо количество зон (участков, частей) выбирать крайным 2, В частности, для

N=4 два старших разряда числа будут определять номер зоны, следующие: два — номер участка в зоне, еще два — часть участка и т.д.

На втором этапе работы устройства, при определении значения Хг, соответствующего заданному рангу, производится одновременное сравнение содержимого счетчиков первого каскада с величиной ранга. Если k первых счетчиков содержит число элементов, меньшее чем ранг, à (k+1)-й счетчик— большее или равное рангу, это указывает, что Хг находится в зоне k+1, а код этой зоны определяет значение старших разрядов результата.

Далее производится анализ счетчиков второго каскада для выбранной зоны k+1.

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

В отличие от процесса накопления данных, когда счетчики всех каскадов работают параллельно, процесс извлечения результата — последовательный. Время поиска Хг определяется задержками в каскадах и их числом ..

Рассмотрим работу устройства по схеме при конкретной реализации для k = В и а1же аз= аЗ= аа= 2.

При накоплении гистограммы в первом счетчике 14 вычислительного блока 1 подсчитывается число элементов, имеющих коды Π— 63, во втором — коды Π— 127, в третьем --коды Π— 191. Блоки памяти блока 2 имеют по четыре ячейки. В первом блоке 24 памяти подсчитывается число элементов, имеющих коды р1+ Л1, во втором — рг+ Л1, в третьем — рз+ Л1 (р1= Π— 15, рг= Π— 31, рз= 0-47, рз= 0-47, Л1= 0,64, 128, 192. Блоки памяти блока 2 имеют по 16 ячеек. В первом блоке 24 памяти блока 2 подсчитывается число элементов, имеющих коды г1+ dq, во втором г2+ Йд, в третьем гз+ Л1 (г1= 0 — 3; г2= 0-7; гз=Π— 11; Q =16; )=0,15). Блоки памяти блока 2з имеют по 64 ячейки. В первом блоке 24 блока 2з накапливается число элементов с кодами de, во втором— цг+ Лз, в третьем — уз+ do(gz= 0,1; дзсж

= 0,12;Лд = 4ь i=0,63), Таким образом, весь диапазон входного сигнала, составляющий

0 — 255, разбивается на четыре части в первом каскаде и во втором, третьем, четвертом каскадах, каждая часть предыдущего каскада разбивается еще на четыре части, что дает возможность анализировать 256 градаций входного сигнала.

Сказанное можно записать в виде:

Я< = n (<) — содержимое серио<о

)=о счетчика 14;

Р7

$г =, п (I) — содержимое второго (=о счетчика 14;

191

$з =,), и (I) — содержимое третьего

)=о счетчика 14.

Содержимое блоков 24 памяти блока 2 равно

54М <6 64<<49< 64<<447

5,(<) е 2 д(1), б (<6) + < (Ц, Э (К) n(r>,o<: 0,>.

l-64« . I=64<6 j64g

Содержимое блоков 24 памяти блока 22 равно

<6Я4 3 <6(34 16Р 4<< < (p) «+ n(i) < В,д () -K «(z) > 5",((о) -," «(г), (р-О .

? ° 16(3 L le Z ° (6(

Содержание блоков 24 памяти блока 2з равно

$1 (у) =и (4у); $2 (y) =n (4y)

+ п(4у+1);

$з " (у) = n (4у)+ п (4y+ 1)+ и (4у+2)

Рассмотрим числовой пример. Пусть размерность маски равна 4х4=16 и на вход устройства поступает некоторая последовательность из 16-ти элементов, например 5, 8, 20, 40, 130, 131, 140, 150, 180, 18 ., 182, 183, 201, 205, 205, .240 (они расположены в порядке возрастания, хотя поступают в произвольном порядке) и г= 6. Тогда искомый элемент Хг=131. Для блока 1 имеет S1=4;

$2=4; $з=12; $2 < r < $з . На выходе 18 результата блока 1 код "2". На входы узлов сравнения с вычитателя поступает код

r- Sz=2; S1 =3; $2 =4; $з =4; r — $2 < S1, поэтому на выходе приоритетного шифратора блока 2 код О. На входы узлов сравнения

1661794 блока 2z поступает код r — Sz — 0=2, Я1"= 2; .

Я2"=2; Яз"=2, r— - Я2-0 S>", поэтому на выходе приоритетного шифратора блока 22 код О. На входы узлов сравнения блока 2з поступает код r— - Sz-Π— 0=2; S>" =0; Яг" =-0;

Яз" =1; r — Sr=2 > Яз ", поэтому на выходе приоритетного шифратора блока 2з код 3.

Окончательный результат, поступающий на выход 8, равен 203в=1311о, Формула изобретения

Устройство ранговой фильтрации, содержащее вычислительный блок и блок накопления гистрограммы, причем вычислительный блок содержит дешифратор, группу реверсивных счетчиков, мультиплексор, группу узлов сравнения, две группы элементов И, группу элементов ИЛИ, приоритетный шифратор и элемент НЕ, при этом g> старших разрядов информационного входа устройства подключены к входам дешифратора вычислительного блока, i-й выход которого подключен к i-My входу j-го элемента Ит1И, группы (i=2,2 — 1, j=i,2 " — 1), первый выход дешифратора подключен к первому входу i-ro элемента ИЛИ группы, первым входам первых элементов И первой и второй группы, выход 1-ro элемента ИЛИ группы подключен к первым входам i-х элементов И первой и второй групп, вторые входы элементов И первой группы соединены с входом элемента НЕ и с входом знака приращения устройства, выход элемента

НЕ подключен к вторым входам элементов

И второй группы, выходы S-x (S=1,2 " — 1) элементов И первой и второй групп подключены соответственно к суммирующему и вычитающему входам S-го реверсивного счетчика группы, выход которого подключен к S-му информационному входу мультиплексора и первому входу S-го узла сравнения группы, выход "Больше" которого подключен к S-му входу приоритетного шифратора, выход которого подключен к управляющему входу мультиплексора, выход мультиплексора вычислительного блока является первым управляющим выходом вычислительного блока, вторые входы узлов сравнения группы подключены к входу критерия ранга устройства, а блок накопления гистограммы содержит первый мультиплексор, дешифратор, группу блоков памяти, группу элементов ИЛИ и первый реверсивный счетчик, причем первый информационный вход первого мультиплексора подключен к старшим разрядам информационного входа устройства, управляющий вход первого мультиплексора соединен с первыми входами элементов ИЛИ группы и с входом признака конца маски устройства, входы дешифратора соединены с информационным входом устройства, и-й выход дешифрэторэ (п=1. 2 т-1. sz — число входов дешифратора, равное числу разрядов результата) подключен к второму входу и-го элемента ИЛИ группы, выход которого подключен к входу разрешения обращения и-го блока памяти группы, выход первого мультиплексора подключен к адресным входам блоков памяти группы, входы управления считыванием-записью которых соединены с входом управления считыванием-записью устройства, информационный выход первого реверсивного счетчика подключен к информационному входу первого блока памяти группы, вход задания направления счета первого реверсивного счетчика соединен с входом знака приращения устройства, выход приоритетного шифратора вычислительного блока является выходом результата вычислительного блока и соединен с вторым информационным входом первого мультиплексора блока накопления гистограммы, о т л и ч а ю щ е е с я тем, что, 25 с целью упрощения устройства и увеличения быстродействия при получении результата из накопленной гистограммы, в него введены р — 2 блоков накопления гистограммы (2 р К k — разрядность фильтрации, р — полное число блоков устройства), причем информационный вход устройства соединен с информационным входом t-ro блока накопления гистограммы (t=2,ð — 1), первый управляющий вход которого соединен с входом признака конца маски устройства, второй управляющий вход t-ro блока накопления гистограммы соединен с входом управления считыванием -записью устройства, третий управляющий вход t-го блока

40 накопления гистограммы соединен с входом знака приращения устройства, четвертый и пятый управляющие входы.с-го блока накопления гистограммы соединены с первым и вторым управляющим выходами (t 1)го блока накопления гистрограммы, вход результата t-го блока накопления гистограммы соединен с выходом результата (t-1)го блока накопления гистограммы, в g-й

50 блок накопления гистограммы (g=1, р-1) введены 2 -2 реверсивных счетчиков (а — число разрядов результата, определяемых

g-м блоком накопления гистограммы), вычитатель„второй мультиплексор, группа 2 (— 1

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

ИЛИ группы, Х-й выходдешифратора соеди1661794 нен с (Х+1г-м входом Y-го элемента ИЛИ группы (X=112 — 1; Y=X+1. 2 в — 1), ннформационный выход I-го реверсивного счетчика (1=2, 2 9-1) соединен с информационным входом I-го блока памяти группы, выход Z-го

5 блока памяти группы (2=1, 2 (-1) соединен с информационным входом Z-m реверсивного счетчика, с Z-м информационным входом второго мультиплексора и первым входом 2-ro узла сравнения группы, выход пбольше" которого соединен с Z-м входом приоритетного шифратора, выход которого соединен с управляющим входом второго мультиплексора, выход приоритетного шифратора и вход результата g-го блока накопления гистограммы является выходом результата g-го блока накопления гистограммы, выход мультиплексора вычислительного бло-ка и вход критерия ранга устройства соедине- 2р ны соответственно с первым и вторым входами вычитателя первого блока накопления гистограммы, второй управляющий вход

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

1661794

Составитель M. Логачева

Редактор А. Козориз Техред М.Моргентал Корректор Н, Король

Заказ 2126 Тираж 412 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5

Производственно-издател ьский комбинат "Патент", г. Ужгород, ул. Гагарина, 101