Устройство для выравнивания гистограмм Советский патент 1993 года по МПК G06F15/36 

элементов задержки, группу из N компараторов, причем элементы задержки первой группы соединены последовательно, введены третья группа из N элементов задержки, N компараторов, группа из N сумматоров, объединенные в N процессорных элементов, причем элементы задержки второй группы соединены последовательно, информационный вход устройства соединен с входами первых элементов задержки первой и второй группы и с первыми входами (2Ы)-ых компараторов (H1.N), выход 1-го элемента задержки второй группы соединен с вторыми входами (21-1) и 21-го компараторов, выход 21-го элемента задержки первой группы соединен с первым входом 21-го компаратора, выходы (21-1) и 21-го компараторов соединены с первым и вторым входами Нч сумматора, выход j-ro сумматора (, N-1) соединен с входом J-ro элемен- та задержки третьей группы, выход которого соединен с третьим входом 0+1)-го сумматора и j-ым выходом устройства, третий вход первого сумматора соединен с входом нулевого кода устройства, выход N-ro сумматора соединен с входом N-ro элемента задержки третьей группы, выход которого является N-ым выходом устройства, тактовые входы элементов задержки первой, второй и третьей трупп обьединены и соединены с тактовым входом устройства.

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

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

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

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

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

На фиг, 1 представлена схема заявляемого устройства; на фиг. 2 - взаимное расположение точек окрестности Qk1 длины k и Qk-21 длины (k-2), имеющих одну и ту же цен

0

5

0 5 0

5

0

5

0

5

тральную 1-ю точку и отличающихся друг от

k - 1k - 1

друга двумя точками (I-) и (I + -4.

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

элементов 2.1, 2.2...2.N 2.2N элементов

задержки, вторую группу элементов 3.1, 3.2...3.N задержки, третью группу элементов 4,1, 4.2...4.N задержки, группу компараторов 5.1, 5.2...5.N...5.2N, группу сумматоров 6.1, 6.2...6.N, объединенных в N процессорных элементов 1.1, 1.2...1.N, информационный вход 7 устройства, тактовый вход 8 устройства, выходы 9.1, 9.2...9.N устройства.

Элементы 2.1, 2,2...2.2N задержки первой группы, а также элементы 3,1, 3.2...3.N задержки второй группы соединены последовательно. Информационный вход 7 устройства соединен с входами элементов 2.1 и 3.1 задержки, а также с первыми входами компараторов 5.(2Ы)(где П)). Выход элемента 3.I задержки соединен с вторыми входами компараторов 5.(21-1) и 5.2.1. Выход элемента 2.21 задержки соединен с первым входом компаратора 5.21. Выходы компараторов 5,(21-1) и 5.2 соединены с первым и вторым входами сумматора 6.1. Выход сумматора 6.J , N-1) соединен с входом элемента 4.J задержки. Выход элемента 4.J задержки соединен с третьим входом сумматора 6.J+1 и выходом 9.J устройства. Третий вход сумматора 6.1 соединен с входом нулевого кода устройства. Выход сумматора 6.N соединен с входом элемента 4.N задержки, выход которого является выходом 9.N устройства. Тактовые входы элементов задержки 2.1...2.2N; 3.1...3.N; 4.1...4.N объединены и соединены с тактовым входом 8 устройства.

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

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

вюючаюшей в себя k точек, заменяется зна- че -тем Rk его локального ранга, yi - Rk ,

ад

(1)

г yi - результат операции СВГ в l-ой точке; Rk - локальный ранг значения xi цент-

рфьного элемента локальной окрестности Qii. ,

Qk - текущая локальная окрестность,

содержащая k точек

1 I, 1

(2)

Qk {xj}, J |-i-l;|4.

точек из множества Qk значения xj, в которьх

Ранг Rk значения xi равен количеству

:(xjeQk )

не превышает хц

Rk1

2 h(xj;xi)

X|ЈQk

где h(xj, xi) - признак результата сравнения значений xj и xi;.20

i (xj; xi) |0

если xj xi если xi xi

(4)

ir-vt xi +

f.

Qk1 - Qk-21 U xi - 2 „ „, . Учитывая (5) и (3), получим, что:

k-1

Uxi +

k-1

k-1

Rk - Rk-21 + h (xi - -; xi) + h (xi +

Формирование результатов СВГ можно осуществлять рекуррентно. Суть предлагаема го подхода заключается в следующем.

Рассмотрим локальные окрестности различной длины, центральные точки кото- рьх совпадают. Локальная окрестность Qk дллны k с центром в i-ой точке и локальная ок эестность Qk-21 длины (k-2) с центром в i-ой то же отличаются друг от друга двумя точка(см. фиг. 2). Это значит, что результат операции СВГ для окрестности Qk1 равен результату операции СВГ для окрестности Qi«-2 плюс вклад двух новых точек, т.е. результат операции СВГ можно формировать ре уррентно, переходя от локальной окрест юсти меньшей длины к локальной окрест ности большей длины. Такой подход к организации вычислений позволяет в парал- лепьно-конвейерном режиме осуществить параллельное вычисление результатов опера дни СВГ для всех локальных окрестностей, размеры которых не превышают заданный размер. Рекуррентная организация процесса вычислений позволяет свести к минимуму тр збуемый объем вычислительных затрат.

Локальные окрестности Qk и Qk-21 (см. ф| г. 2) отличаются двумя точками: xi - k-- 1 . k-1

(5)

5

10

15

где k - нечетное.

Выражение (6) описывает закон рекуррентного формирования результатов операции СВГ в 1-ой точке для локальной окрестности длины k на основе полученного ранее результата операции СВГ я i-ой точке для локальной окрестности длины (k-2) и результатов сравнения значений сигнала в Ik - 1

) точках.

ой точке и в (i - и (I

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

0

5

0

5

0

5

0

5

Rk Rk-21 + h (xi - Јyl; xi) + h (xi + 3,N

k-1

;xi)

(7)

k - нечетное. k

Rj -O

где N - заданная константа, равна половине длины локальной окрестности максимальной длины.

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

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

В начальный момент времени элементы 2.1...2.2N, 3.1...3.N, 4.1...4.N задержки обнулены.

Пусть в текущем 1-ом такте работы параллельный код значения xi текущего отсчета сигнала поступает «а вход 7 устройства. Значение xi с информационного входа 7 устройства поступает на входы элементов 2.1 и 3.1 элементов задержки и на первые входы компараторов 5.(2j-1) (,N). На первые входы компаратора 5.2J поступает значение отсчета xi-2j с выхода элемента 2.2 задержки. На вторые входы компараторов 2.(2J-1) и 2.2J поступает значение отсчета xi-j с выхода элемента 3. задержки. Значения величин h (xi; хи) и 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; xi-2) и п(хи; xi-2) с выходов ком па paторов 5.3 и 5.4. На выходе сумматора 6.2 формируется (согласно (7)) значение Rs , которое поступает на вход элемента 4.2 задержки. На выходе элемента 4.2 задержки сформировано значение Rs13, поступившее на его вход в предыдущем такте. Значение с выхода элемента 4.2 задержки поступает на вход 9.2 устройства и на третий вход сумматора 6.3. и т.д. Таким образом, в 1-ом такте работы на выходе 9.k ( ,N) формируется значение R k-M1 1 . С приходом очередного тактового .импульса в элементах .2.1. ..2.2N,3.1...3.N,4,1..AN осуществляется запись новых значений с их входов (по переднему фронту тактового импульса) и сдвиг информации (по заднему фронту тактового импульса) и начинается новый такт работы устройства. В (1+1)-ом такте работы на выходе 9.k () формируется значение R2k+i «

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

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

быстродействующих специализированных системах обработки сигналов, например в автоматизированных системах обработки изображений.

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

времени.

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

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

компараторов первой группы и с входами первых элементов задержки первой и третьей групп, выход 1-го элемента задержки второй группы подключен к первому вхо- iy 1-го компаратора второй группы, выход

1-го элемента задержки третьей группы соединен с входом (И-1)-го элемента задержки этой группы и с вторыми входами 1-х компараторов первой и второй групп, выходы 1-х компараторов первой и второй групп подключены к первому и второму входам 1-го сумматора группы, выход 1-го сумматора группы подключен к входу 1-го элемента задержки четвертой группы, выход 1-го элемента задержки четвертой группы соединен

1-м выходом устройства и с третьим входом (H-1)-rg сумматора группы, третий вход первого сумматора группы является входом начальной установки устройства, тактовый вход которого соединен с тактовыми входами элементов задержки всех групп.

ФигЛ

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