Устройство для вычисления скользящего среднего

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано в устройствах, осуществляклцих весовую обработку цифровой информации, представленной в виде массивов чисел (например, при обработке изображений). Целью изобретения является повышение быстродействия 30 устройства для вычисления скользящего среднего. Деть достигается путем параллельной обработки элементов исходного массива несколькими окнами. При этом параллельно вычисляются несколько значений скользящего среднего с учетом весовых функций. Устройство содержит блок 1 памяти массива, счетчик 2 номера базовой строки массива, счетчик 8 номера столбца маски, блок 9 умножения , накапливающий сумматор 10, делитель 11, регистр 12 делителя, блок 13 элементов И, регистр 14 числа столбцов маски, блок 15 умножения , сумматор 16, триггер 17, элементы И 18-23, элемент НЕ 24, элемент ИЛИ-НЕ 25, блок 26 элементов И, элемент ИЛИ 27, синхронизатор 28, выход Конец работы 29 и тактовый вход 30 устройства. 1 ил. (Л

СОЮЗ СОВЕТСКИХ

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

РЕСПУБЛИК (19> (1И 1

А1 (51)5 С 06 F 15/36

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

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

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

ПО ИЗОБРЕТЕНИЯМ И OTHPbfTHflM

ПРИ ГКНТ СССР

1 (21) 4457391/24 (22) 16,05,88 (46) 15.04 ° 91. Бюл. Р-" 14 (72) С.В. Семенов и R.Ð. Ахметьянов (53) 681.3(088„8) (56) Авторское свидетельство СССР

Р 1247895, кл. С 06 F 15/36, 1985.

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

1 - 1410058, кл. С 06 F 15/36, 1986. (54) УСТРОЙСТВО ДЛЯ ВНЧИСЛЕНИЯ СКОЛЪВЯЦЕГО СРЕДНЕГО (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано в устройствах, осуществляющих весовую обработку цифровой информации, представленной в виде массивов чисел (например, при обработке изображений). 1 елью изобретения является повышение быстродействия

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

8 номера столбца маски, блок 9 умножения, накапливающий сумматор 10, делитель 11, регистр 12 делителя, блок 13 элементов И, регистр 14 числа столбцов маски, блок 15 умножения, сумматор 16, триггер 17, элементы И 18-23, элемент НЕ 24, элемент

ИЛИ-HF, 25, блок 26 элементов И, элемент ИЛИ 27, синхронизатор 28, выход

"Конец работы" 29 и тактовый вход 30 устройства. 1 ил. С:

1642478

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

Целью изобретения является повышение быстродействия устройства для вычисления скользящего среднего по— средством параллельного вычисления по нескольким окнам нескольких значений скользящего среднего с учетом весовых функций„

На чертеже представлена функциональная схема устройства для вычисления скользящего среднего.

Устройство содержит блок 1 памяти (массива размером m x n), счетчик (по модулю m — k + 1 номера базовой строки массива) 2, счетчик (по модулю и номера столбца) 3, счетчик (по мо — 25 дулю к номера текущей строки 4), сумматор (адреса чтения) 5, блок б хранения маски, счетчик (по модулю k номера строки маски) 7, счетчик (по модулю 1 номера столбца маски) 8, блок 9 умножения (на весовой коэффициент), накапливающий сумматор 10, делитель 11, регистр (делителя) 12, блок 13 элементов И, регистр (числа столбцов маски) 14, блок 15 умноже — 35 ния, сумматор 16, триггер (разрешения записи) 17, элементы И 18-23, элемент

НГ 24, 1-входовой элемент ИЛИ-НГ 25, бпок 26 элементов И, элемент ИЛИ 27, синхронизатор 28, выход "Конец рябо- 40 ты" 29 устройства и тактовый вход

30 устройства,, Элементы 6-20 образуют 1-й узел вычисления среднего, а элементы 1416 — схему адресации блока хранения 45 маски в i-м узле вычисления среднего, Устройство работает следующим образом, В исходном состоянии блок 1 содержит массив размером т строк на и столбцов, Лля определенности будет считать

m = n = 2, где i — целое число, Тогда содержимое блока 1 расположено, начиная с ячейки с адресом О, построчно, причем начало второй строки изображения расположено в ячейке с адре— сом 2, начало третьей строки — в 1 ячейке с адресом 2 и т,д,. Содержимое счетчиков 2-4 равно О, На управляющий вход блока 26 элементов И подан разрешающий сигнал, который сформирован на 1-входовом элементе ИЛИ-НЕ

?5 и соответствует отсутствию сигналов переполнения счетчиков 8„ В сумматор 5 на информационные входы подается содержимое счетчиков 2 и 4. Число младших разрядов адреса блока 1 памяти, подключаемых к счетчику 3, соответствует степени числа 2« Это чис" ло определяет количество столбцов массива„ В блоки б узлов вычисления среднего записаны коды элементов маски размером k r 1,, Иаска представляет собой окно, которым сканируется исходный массив„

Сканирование производится путем лов очередного наложения 1 окон-масок на массив со сдвигом вдоль строки друг относительно друга,. Просмотр массива осуществляется в пределах

k строк изображения по столбцам„

Счетчики 7 и триггеры 17 в исходном состоянии обнулены, а счетчики 8, начиная с второго узла вычисления среднего, установлены в состоянии

1 — h +1, где h — номер узла (h

2,...,1) . Счетчик 8 первого узла обнулен. В регистры 14 записан код числа, соответствующего числу столбцов в маске, накапливающий сумматор

10 обнулен, а в регистр 12 записан код числя, на которое должна быть р lçlIåëåíà в дальнейшем сумма взвешенных элементов массива внутри маски„

Это число определяется размерами маски и значениями его элементов„ Элементы маски могут быть отрицательными,, Управление Аункционированием устройства осуществляется с помощью синхрониз".тора 28. По тактовым импульсам, поступающим на тактовый вход 30, осуществляется выдача управляющих импульсов (УИ) в устройство, Ио первому тактовому импульсу осуществляется выдача первого управляющего импульса 1УИ (второй выход синхронизатора), который через элемент

ИЛИ 27 поступает на управляющий вход сумматора 5, в котором осуществляется вычисление кода номера строки массива путем сложения номеров базовой строки из счетчика 2 и текущей строки из счетчика 4. Кроме того, 1 УИ поступает на управляющий вход

16 блока 15 умножения, в котором осуществляется перемножение числа столбцов в маске, код которого хранится в регистре 14, с номером строки маски, код которого хранится в счетчике 7, с целью вычисления смещения адреса элемента маски в блоке 6 в соответствии с номером требуемой

42478 устройства таким триггером является триггер 17 второго узла вычисления среднего, во втором цикле — триггер третьего узла вычисления среднего и т.д. Кроме того, установка в 1" триггера 17 приводит к выдаче сигнала запрета на управляюгтий вход блока

26 элементов И через элемент ИЛИ-НЕ

25 о

30 строки маски.

По второму тактовому импульсу выдается 2УИ (9-й выход синхронизатора), по которому сумматором 16 формируются адреса элементов маски в узлах вычисления среднего.

По третьему тактовому импульсу выдается 3 УИ (5-й выход синхронизатора)„ который поступает в блоки 1 и 6 на входы разрешения чтения. В результате с выходов блоков 1 и 6 передаются значения элемента массива и элементов маски в блоки 9 узлов вычисления среднего.

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

По пятому тактовому импульсу выдается 5 УИ (3-й выход синхронизатора), который поступает на управляющий вход накапливающего сумматора

10. В сумматоре происходит накопле| ние результатов умножения в блоке 9. !

Кроме этого, 5 УИ поступает на вход счетчиков 4 и 7, увеличивая их содержимое на 1.

По шестому тактовому импульсу выдается 6 УИ, (7-й выход синхронизатора), который поступает на счетный вход счетчика 7. В том случае, если произошло его переполнение, и:-»пульс переполнения проходит на вход счетчика-8, увеличивая его содержимое на 1„ Переполнение счетчиков 7 и 4 происходит одновременно. В случае, если этого не происходит, последуюг»ие тактовые импульсы в цикле работы устройства не производят никаких действий, так как триггеры не изменяют своего состояния ° Если при увеличении содержимого счетчика 8 на в одном из узлов вычисления среднего произошло переполнение этого счетчика, сигнал с его выхода установит в "1" триггер 17 соответствуюгтего узла. В первом цикле работы

25 и сигнала. разрешения прохождения

8 УИ через элемент И 21, а также команды записи в блок 1 через элемент И 22.

По седьмому тактовому импульсу выдается ? УИ (10-й выход синхронизатора), которьпт через элемент И 19 по разрешающему сигналу триггера 17 соответству»сцего узла вычисления среднего выдает управляющий сигнал в делитель 11. В этом блоке содержимое накапливающего сумматора 10 делится на содержимое регистра 12 и„следовательно, вычисляется текуг»ее значение скользягтего среднего по данной маске, По восьмому тактовому импульсу выдается 8 УИ (1-й выход синхронизатора), которьп» через элемент И 20 по разрешающему сигналу триггера сбрасывает содержимое накапливающего сумматора 10 соответствующего узла вычисления среднего и открывает блок

13 элементов И, через которьпi на. вход блока 1 подается код вычисленного по 7 УИ скользяг»его среднего.

Кроме этого, 8 УИ через элементы

И 21 и элемент ИЛИ 27 поступает на управляющий вход сумматора 5, котоpbD» передает на адресньпт вход блокЫ

1 номер строки для записи полученного

B узле вычисления среднего значения.

По девятому тактовому импульсу вырабатывается 9 УИ (б-й выход синхронизатора), который через элемент

И 22 поступает на вход записи в блок

1. По этой команде в блок 1 записывается значение скользящего среднего, вычисленное в узле вычисления среднего по 7 УИ, По десятому тактовому импульсу вырабатывается !0 УИ (4-й выход синхронизатора), которьп» сбрасывает в

"0" соответствующий триггер 17 узла вычисления среднего и увеличивает содержимое счетчика 3 на 1. Если переполнения счетчика 3 не произошло, то цикл работы устройства повторяетоя. Если произошло переполнение счетчика 3, выдается счетньп» импульс в

1642478 счетчик 2, увеличивая его содержимое на "1". Если переполнения счетчика

2 не произошло, то цикл работы устройc Ira повтОряетоя. Если произошло переполнение счетчика 2, то по выходу

"Конец работы" 29 выдается сигнал об окончании работы устройства. Это означает, что в блоке 1 памяти хранится матрица значений скользящего среднего, причем первые 1-1 столбцов и последние k-1 строк не должны использоваться для дальнейшей работы.

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

Устройство для вычисления скользящего среднего, содержащее блок памяти, элемент ИЛИ, три элемента И, первый счетчик, синхронизатор, первый gg выход которого подключен к первому входу первого элемента И, о т л и— ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены элемент ИЛИ-НЕ, два счетчи- 25 ка, сумматор, блок элементов И, узлы вычисления среднего, каждый из которых содержит два счетчика, три элемента И, триггер, два регистра, два блока умножения, сумматор, накапли- 30 вающий сумматор, блок хранения маски, делитель и блок элементов И, выход первого элемента И подключен к первому входу первого элемента

ИЛИ к ВторОму вхОду которОГО подключен второй выход синхронизатора, выход первого элемента ИЛИ подключен к тактовому входу сумматора, входы первого и второго слагаемых которого .подключены соответственно к выходу первого счетчика и выходу блока элементов И, разрядные входы сумматора подключены к старшим разрядам адресного входа блока памяти, первый вход блока элементов И соединен с выходом 4 второго счетчика, счетньпr вход которого соединен с третьим выходом синхронизатора, выход переполнения второго счетчика соединен с первым входом второго элемента И, второй вход которого подключен к четвертому выходу синхронизатора, выход второго элемента И соединен со счетным входом третьего счетчика, разрядные выходы которого подключены к младшим разрядам адресного входа блока IIGMIITH> выход переполнения третьего счетчика подключен к счетному входу первого счетчика, выход гереполнения которого является выходом "Конец работы" устройства, вход разрешения чтения блока памяти подключен к пятому выходу синхронизатора, вход разрешения записи блока памяти подключен к выходу третьего элемента И, первый вход которого подключен к шестому выходу синхронизатора, второй вход третьего элемента И соединен с вторым входом первого элемента И, управляющим входом блока элементов И и подключен к выходу элемента ИЛИ-НЕ, каждый из входов которого объединен с первыми входами первого и второго элементов

И соответствующего узла вычисления среднего и подключен к прямому вьжоду триггера одноименного узла вычисления среднего, в каждом узле вычисления среднего инверсный вход триггера подключен к четвертому выходу синхронизатора, а прямой — к выходу переполнения первого счетчика этого узла вычисления среднего, счетный вход первого счетчика данного узла вычисления среднего подключен к выходу третьего элемента И этого узла вычисления среднего, первый вход которого подключен к седьмому выходу синхронизатора в каждом узле вычисления среднего, а второй вход подключен к выходу переполнения второго счетчика этого узла вычисления среднего, в каждом узле вычисления среднего счетньпr вход второго счетчика подключен к третьему выходу синхронизатора, выход второго счетчика подключен к входу первого сомножителя

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

1643478

Составитель С. Ионкин рсдактор A. Лежнина Техред С.Мигунова Корректор Н.Король

Заказ 1148 Тираж 414 Подписное

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

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

Производственно †издательск комбинат "Патент", г.ужгород, ул. Гагарина,101 ния среднего, в каждом узле вычисления среднего вход разрешения чтения подключен к пятому выходу синхронизатора, информационный выход блока хранения маски каждого узла вычисления среднего подключен к входу первого сомножителя второго блока умножения данного узла вычисления среднего, вход второго сомножителя которого подключен к информационному выходу блока памяти, тактовый вход второго блока умножения каждого узла вычисления среднего подключен к девятому выходу синхронизатора, выход второго блока умножения подключен к информационному входу накапливающего сумматора своего узла вычисления среднего, вход синхронизации которого в каждом узле вычисления среднего подключен к третьему 0 выходу синхронизатора, вход установки нуля накапливающего сумматора объединен с управляющим входом блока элементов.И своего узла вычисления среднего и подключен к выходу первого 25 элемента И .этого узла вычисления среднего, второй вход первого элемента И в каждом узле вычисления среднего подключен к первому выходу синхронизатора, выход накапливающего сумматора подключен к входу делимого блока деления данного узла, вход делителя блока деления подключен к выходу второго регистра этого узла вычисления среднего; тактовый вход блока деления подключен к выходу второго элемента И своего узла вычисления среднего, второй вход которого в каждом узле вычисления среднего подключен к десятому выходу синхронизатора, выход блока деления подключен к входу блока элементов И данного узла вычисления среднего, выходы блоков элементов И всех узлов вычисления среднего через схему NOHTAEHOF

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