Устройство для выравнивания гистограмм

 

Изобретение относится к вычислительной технике и может быть использовано для статистической обработки информации. Цель изобретения - расширение функциональных возможностей за счет обработки скользящих апертур различной длины. Устройство содержит группы элементов задержки , группу сумматоров и группы компараторов. 2 ил. сл С Параллельное формирование результатов операции СВГ по скользящим апертурам различной длины (от трех до N включительно) возможно за счет рекуррентного формирования результата СВГ для апертуры больших размеров на основе полученного ранее результата СВГ для апертуры меньших размеров. Поставленная цель достигается тем, что в устройство для локального выравнивания гистограмм, содержащее первую группу из 2N элементов задержки, вторую группу из N 00 OJ -ч СА) ю о 00

союз советских социАлистических

РеспуБлик (я)з G 06 F 15/36 пдтентное"

НИЕ ИЗОБРЕТЕНИЯ

К, ПАТЕНТУ (2 ) 4927895/24 (2 ) 16,04.91 (4 ) 30.08.93. Бюл. М 32 (71) Научно-исследовательский институт тел визионной техники "Электрон" (7 ) С.А. Елманов (7 ) С.А, Елманов (5 ) 1. Авторское свидетельство СССР

М 1312614, кл. 6 06 F 15/36. 1986.

2. Очин Е.Ф. Вычислительные системы о работки изображений.-Л.: Энергоатом здат. Ленингр. отд-ние, 1989, с. 104-105, р с. 5.3. Структура полусистолического про- ц ссора локальной эквализации гистогр м, 3. Ярославский Л.П. Цифровая обработка сигналов в оптике и голографии: Введен е в цифровую оптику. — М.: Радио и связь, 19887, с. 229-238.

4. Справочник по устройствам цифрово обработки информации — К.: Техника, 19 8.

5. Титце У. и Шенк К. Полупроводникова схемотехника: Справочное руководство, П р. с нем,-М.: Мир, с. 354 — 355, рис. 20.16.

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

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

„„5lJ 1837326 АЗ (54) УСТРОЙСТВО ДЛЯ ВЫРАВНИВАНИЯ

ГИСТОГРАММ (57) Изобретение относится к вычислительной технике и может быть использовано для статистической обработки информации.

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

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

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

2N элементов задержки, вторую группу из N

1837326 элементов задержки, группу из N компараторов, причем элементы задержки первой группы соединены последовательно, введены третья группа из N элементов задержки, N компараторов, группа из N сумматоров, объединенные в и процессорных элементов, причем элементы задержки второй группы соединены последовательно, информационный вход устройства соединен с входами первых элементов задержки первой и второй группы и с первыми входами (2i-1)-ых компараторов (I-1,N), выход I-го элемента задержки второй группы соединен с вторыми входами (21-1) и 21-го компараторов, выход 2i-ro элемента задержки первой группы соединен с первым входом

2i-ro компаратора, выходы (2i-1) и 2I-ro компараторов соединены с первым и вторым входами i-ro сумматора, выход j-го сумматора ()=1, N-1) соединен с входом J-ro элемента задержки третьей группы, выход которого соединен с третьим входом (j+1)-ro сумматора и J-ым выходом устройства, третий вход первого сумматора соединен с входом нулевого кода устройства, выход N-ro сумматора соединен с входом N-го элемента задержки третьей группы, выход которого является N-ым выходом устройства, тактовые входы элементов задержки первой, второй и третьей групп объединены и соединены с тактовым вхОдом устройства.

Сопоставительный анализ с прототипом показывает, что заявляемое устройство отличается наличием новых блоков: N компараторов, N сумматоров, группы из N эле. ментов задержки, а также из связи между собой и с остальными элементами схемы.

Таким образом, заявляемое устройство соответствует критерию "новизна".

Сопоставительный анализ с другими техническими решениями показывает, что компараторы и сумматоры широко известны (4).

Элемент задержки на один такт работы можно реализовать, как параллельный регистр на MS-триггерах, которые также широко известны (5). Однако введение известных элементов B указанной связи позволяет расширить функциональные возможности устройства за счет параллельного рекуррентного формирования результатов операции CBI по скользящим апертурам различной длины.

Это позволяет сделать вывод о соответствии предлагаемого решения критерию

"Существенные отличия".

На фиг, 1 представлена схема заявляемого устройства; на фиг. 2 — взаимное расположение точек окрестности Ок длины k u

Qa-г длины (k-2), имеющих одну и ту же центральную I-e точку и отличающихся друг от друга двумя точками (I ) и (I + ).

2 2

Устройство содержит первую группу

5 элементов 2.1, 2.2...2,N,..., 2.2N элементов задержки, вторую группу элементов 3.1, 3.2...3М задержки, третью группу элементов 4.1, 4.2...4.Nзадержки,,группу компараторов 5.1, 5.2...5.N,..5.2N, группу

10 сумматоров 6.1, 6,2...6.N, объединенных в N процессорных элементов 1 1, 1.2...1.N, информационный вход 7 устройства, тактовый вход 8 устройства, выходы 9.1, 9.2...9.N устройства.

15 Элементы 2.1, 2.2...2.2N задержки первой группы, а также элементы 3,1, 3.2„.3,N задержки второй группы соединены последовательно. Информационный вход 7 устройства соединен с входами элементов 2.1

20 и 3.1 задержки, а также с первыми входами компарато ров 5.(2I-1) (где I-Г,Й). Выход элемента З.i задержки соединен с вторыми входами компараторов 5.(2I-1) и 5.2I. Выход элемента 2.2! задержки соединен с первым

25 входом компаратора 5.2I. Выходы компараторов 5.(2I-1) и 5.2i соединены с первым и вторым входами сумматора 6Л. Выход сумматора 6.j 0-1, N-1) соединен с входом элемента 4.J задержки. Выход элемента 4.J

3О задержки соединен с третьим входом сумматора 6.j+1 и выходом 9.J устройства. Третий вход сумматора 6.1 соединен с входом нулевого кода устройства. В ыход сумматора

6.N соединен с входом элемента 4,N задер35 жки, выход которого является выходом 9.N устройства. Тактовые входы элементов задержки 2.1...2.2N; 3.1...3 N; 4.1...4 N объединены и соединены с тактовым входом 8 устройства.

4О Перед изложением описания принципов работы устройства целесообразно отметить следующее.

Операция скользящего выравнивания гистограммы (СВГ) широко используется

45 при обработке структурных сигналов, например телевизионных изображений с целью повышения их детальности (локальных контрастог)(3). Операция СВГ позволяет нелинейНо подавить низкочастотную и

50 усилить высокочастотную составляющие сигнала. При обработке иэображений возникает необходимостьгизменения размеров скользящей локальной окрестности (апертуры), по элементам которой идет формирова55 ние значений результата СВГ, т,е. необходимо параллельное формирование результатов операции CBI для локальных окрестностей различных размеров. При операции СВГ значение х в центральной точке текущей локальной окрестности Оь, 1837326 в че гд

20 то

Rk= „ h(xi, x!) хфС!!

l (3),, 1, eCJIN xi х!

10, если х! > х! (4) 25

55 ючаю!! ей в себя k точек, заменяется знаием Rk его локального ранга, у!=М, (1) у! — результат операции CB Г в l-ой точке;

Rk — локальный ранг значения х! цент-! ьного элемента локальной окрестности

О! — текущая локальная окрестность, ! ержащая k точек.

0к =(х!), J= i —; i+ (2)

2 2

Ранг Rk значения х! равен количеству ек иэ множества Qk значения х!, в кото-! х (х б0 ) не превышает xi, гд h(xi, х!) — признак результата сравнения зн чений х! и х!, Формирование результатов СВГ можно ос ществлять рекуррентно. Суть предлагаем го подхода заключается в следующем.

Рассмотрим локальные окрестности рамичной длины, центральные точки котор х совпадают. Локальная окрестность О! дл ны k с центром в i-ой точке и локальная ок естность О!:-2 длины(И-2) с центром в 1-ой ! то ке отличаются друг от друга двумя точкам (см. фиг. 2). Это значит, что результат операции СВГ для окрестности Qk равен ! ре ультату операции СВГ для окрестности

Q 2плюс вклад двух новых точек,,т.е. резу ьтат операции СВГ можно формировать р уррентно, переходя от локальной окрест ости меньшей длины к локальной окрест ости большей длины. Такой подход к о ганизации вычислений позволяет в паралле ьно-конвейерном режиме осуществить и аллельное вычисление результатов опера ии СВГ для всех локальных окрестностей, равмеры которых не превышают заданный ер. Рекуррентная организация процесса слений позволяет свести к минимуму уемый объем вычислительных затрат.

Локальные окрестности Qk u Qk-a (см.

2) отличаются двумя точками. x!

k — 1 и xI+

k — 1 k — 1

Qk 0k-2 0 x! — — 0 х! +

2 2 (5)

Учитывая (5) и (3), получим, что:

k — 1 k — 1, Rk! = Rk-ð + h (x! —, x!) + h (x! +; х!), 2 2 (6) где k — нечетное.

Выражение (6) описывает закон рекуррентного формирования результатов операции СВГ в i-ой точке для локальной окрестности длины k на основе полученного ранее результата операции СВГ в i oé точке для локальной окрестности длины (k-2) и результатов сравнения значений сигнала à Ik — 1 k — 1 ой точке и s (i — †) и (! + ) точках.

2 . 2

Рекуррентное формирование результатов

СВГ позволяет с минимальными вычислительными затратами для каждой 1-ой точки сигнала определить результат операции

СВГ для всех локальных окрестностей, длина которых не превышает заданную

Rk = Rk-2 + h (x! — —, х!) + h (x! +; x!)

k — 1, k — 1.

2 2

k — нечетное. к= З,М Р)

В! =0 где М вЂ” заданная константа, равна половине длины локальной окрестности максимальной длины.

Предложенное устройство реализует параллельное рекуррентное вычисление результатов операции СВГ по всем локальным окрестностям, размеры которых не превышает заданный.

Устройство работает следующим обра30 зом.

В начальный момент времени элементы

2 1...2,2N, ЗЛ...Ç.N, 4.1...4.N задержки обнулены.

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

Значение х! с информационного входа 7 устройства поступает на входы элементов 2.1 и 3.1 элементов задержки и на первые входы компараторов 5.(2J-1) (J-1,N). На первые входы компаратора 5.2J поступает значение отсчета х!-2) с выхода элемента 2.2) задержки.

На вторые входы компараторов 2.(2J-1) и 2.2J поступает значение отсчета х!-! с выхода элемента З.j задержки. Значения величин h (x!, xI-1) и h (xI-2, xI-1) с выходов компараторов 5.1 и 5,2 поступают на первый и второй входы сумматора 6.1, на третий вход которого поступает нулевое значение с входа нулевого кода устройства.

На выходе сумматора 6.1 формируется (согласно (7)) значение Вз, которое поступает на вход элемента 4.1 задержки. На выходе элемента 4.2 задержки сформировано значение Яз, поступившее на его вход в предыдущем такте. Значение Вз с выхода элемента 4.1 задержки поступает на выход

9;1 устройства и третий вход сумматора 6,2, на вторые входы которого поступают значения h(xi, хы) и h(x!.4; xI-2) с выходов компара1837326 8

10 времени.

20

30 компараторов первой группы и с входами

35 Ио элемента задержки третьей группы сое: динен с входом {1+1)-го элемента задержки

40 мента задержки четвертой группы соединен

45 I-м выходом устройства и с третьим входом ((+1-го сумматора группы, третий вход пвр50 торов 5.3 и 5.4. На выходе сумматора 6.2 формируется (согласно (7)) значение Rs 2, которое поступает на вход элемента 4.2 задержки. На выходе элемента 4.2 задержки сформировано значение Ив з, поступившее 5 на его вход в предыдущем такте, Значение

Rs с выхода элемента 4.2 задержки. поступает на вход 9.2 устройства и на третий вход сумматора 6.3. и Y.ä. Таким образом, в 1-ом такте работы на выходе.9.к (К-I,N) формируется значение Rg>+t " . С приходом очередного тактового.,импульса в элементах

2 1...2.2N, 3.1...3.N, 4,1...4Я осуществляется запись новых значений.с их входов.(по переднему фронту тактового импульса) и сдвиг информации (по заднему фронту. тактового импульса) и начинается новый такт работы устройства. В (I+1)-ом такте работы на выходе 9.k {k=1,É) формируется значение Rgb+I, Устройство работает в параллельноконвейерном режиме (вычисления в ПЗ

1.1...1.N проводятся параллельно и результаты, полученные в текущем такте в предшествующем ПЭ, используются в последующем такте в следующем ПЗ) и в каждом такте работы на выходе 9 k устройства будет формироваться значение результата операции СВ Г по скользящей окрестности размерами (2k+1) для соответствующей точки.

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

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

Формула изобретения

Устройство для выравнивания гистограмм, содержащее три группы элементов задержки и первую группу компараторов, причем выход I-ro элемента задержки первой группы (где 1=1, N)-соединен с входом

I-ro элемента задержки второй группы, выход 1-го элемента задержки второй группы подключен к входу(!+1)-го элемента задержкипервойгруппы, отличающееся тем, что, с целью расширения функциональных возможностей 38 счет обработки скольэящих апертур различной длины, в него введены четвертая группа элементов задержки, вторая группа компараторов и группа сумматоров, причем информационный вход устройства соединен с первыми входами первых элементов задержки первой и третьей групп, выход I-го элемента задержки второй группы подключен к первому вхо.".ду I-ro компаратора второй группы, выход этой:группы и с вторыми входами 1-х компараторов первой и второй групп, выходы 1-х компараторов первой и второй групп подключены:к первому и второму входам I-го сумматора группы, выход i-го сумматора группы подключен к входу i-го элемента звдержки. четвертой группы, выход i-го элевого сумматора группы является входом начальной установки устройства, тактовый вход которого соединен с тактовыми входами элементов задержки всех групп, 1837326

У,2 с

Составитель С.Елманов

Реда тор М.Кузнецова Техред М,Моргентал Корректор M.Ïåòðîâà

Зака 2867 Тираж Подписное

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

113035, Москва, Ж-35, Раушская наб., 4/5 Производственно-издательский комбинат "Патент", r. Ужгород, ул. Гагарина, 101