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

 

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

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

Известно устройство для вычисления скользящего среднего (авт. св. СССР N 1247895, кл. G 06 F 15/36, 04.01.85), содержащее три регистра, два сумматора, накапливающий сумматор, коммутатор и блок управления, генератор тактовых импульсов, содержащий делитель частоты и триггер, причем первый информационный вход устройства соединен с входом накапливающего сумматора, выход которого соединен с входом третьего регистра, выход которого соединен с первым входом второго сумматора и выходом скользящего среднего "по столбцу" устройства, второй информационный вход устройства соединен с первым входом коммутатора, выход которого соединен с вторым входом второго сумматора, выход которого соединен с входами второго и первого регистров, выход которого соединен с вторым входом коммутатора, выход второго регистра соединен с выходом скользящего среднего "по строке" устройства, первым входом первого сумматора и вторым входом второго сумматора, выход которого является выходом скользящего среднего "по кресту" устройства, выход генератора тактовых импульсов соединен с управляющим входом второго регистра и входами триггера и делителя частоты, выход которого соединен с управляющим входом первого регистра, выход триггера соединен с управляющими входами коммутатора, первого сумматора и третьего регистра. Устройство реализует вычисление среднего значения по скользящей апертуре типа "крест".

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

Наиболее близким техническим решением к заявляемому является устройство для вычисления скользящего среднего (авт. св. СССР N 1485270, кл. G 06 F 15/36, 17.11.87), содержащее многовходовый сумматор, выход которого подключен к входу делимого блока деления и является выходом одномерной скользящей суммы устройства, m-1 сдвигающих регистров (m - число выборок), счетчик, причем выход блока деления является выходом одномерного скользящего среднего устройства, дополнительный многовходовый сумматор, дополнительный блок деления, К триггеров (К - число интервалов усреднения), К блоков памяти, К-1 коммутаторов, при этом выход j-го регистра, кроме (m-1)-го, подключен к информационному входу (j+1)-го регистра и (j+1)-входу многовходового сумматора (j = 1, 2, ..., m-2), выход (m-1)-го регистра соединен с m-входом многовходового сумматора, информационный вход первого регистра объединен с первым входом сумматора и является информационным входом устройства, единичный выход j-го триггера, кроме К-го, подключен к D-входу (j+1)-го триггера, входу разрешения записи-считывания j-го блока памяти, единичный выход К-го триггера соединен с D-входом первого триггера и входом разрешения записи-считывания К-го блока памяти, единичный выход i-го триггера (i = 2, 3, . . . , K) подключен к управляющему входу соответствующего коммутатора, первые информационные входы которых объединены и соединены с выходом первого блока памяти, тактовый вход которого объединен с тактовыми входами i блоков памяти, с тактовыми входами счетчика и регистров и является тактовым входом устройства, выход сумматора подключен к первому входу дополнительного многовходового сумматора, другие входы которого соединены соответственно с выходами коммутаторов, выход дополнительного многовходового сумматора подключен к входу делимого дополнительного блока деления и является выходом двумерной скользящей суммы устройства, вход делителя дополнительного блока деления является входом задания числа выборок двумерного среднего, а выход - выходом двумерного скользящего среднего устройства, вход делителя и выход блока деления являются соответственно входом задания числа выборок одномерного среднего и выходом одномерного скользящего среднего, вход установки в "1" К-го триггера объединен с входами установки в "0" (К-1)-го триггера и установки в "0" счетчика и является входом предустановки устройства, входы синхронизации триггеров объединены и являются входом синхронизации устройства, выход счетчика подключен к адресным входам блоков памяти, выходы которых, кроме первого, соединены с вторыми информационными входами соответствующих коммутаторов.

Устройство реализует вычисление среднего значения и суммы отсчетов по двумерной скользящей апертуре путем параллельного суммирования отсчетов текущего отрезка строки и подсчитанных ранее сумм элементов соответствующих отрезков других строк, принадлежащих текущей двумерной апертуре. Процесс суммирования соответствующих значений организован параллельно-последовательно. Для вычисления сумм соответствующих значений используются два последовательно соединенных многовходовых сумматора. Многовходовый сумматор представляет собой дерево сумматоров. Для реализации N-входового сумматора используются N-1 сумматоров для сложения двух операндов. Таким образом, для организации процесса вычисления используется 2(N-1) сумматоров для сложения двух операндов. Это приводит к большим аппаратурным затратам при вычислении скользящего среднего по скользящей апертуре больших размеров. При N = =32, например, для реализации двух 32-входовых сумматоров необходимо 62 сумматора для сложения двух операндов. Кроме того, для организации процесса вычисления необходимы запоминающие элементы (блоки памяти) общим объемом V = L ^. M (k ++ [log₂ N]) бит для хранения промежуточных сумм элементов отрезков строк (L - количество отсчетов в строке двумерного массива данных, M, N - количество отсчетов в столбце и строке двумерной скользящей апертуры, k - количество разрядов на информационном входе устройства, [ ] - ближайшее справа целое число). Таким образом, недостатком устройства являются высокие аппаратурные затраты, особенно при больших размерах скользящей апертуры. Кроме того, следует отметить следующее.

Время срабатывания N-входового древовидного сумматора определяется из выражения t^N_сум = t_c^{2 .} [log² N], где t^N_сум - продолжительность такта работы N-входового сумматора; N - количество входов многовходового сумматора; t_c² - продолжительность работы сумматора для сложения двух операндов; [ ] - ближайшее справа целое число.

Такт работы устройства определяется суммарным временем срабатывания регистра и двух многовходовых сумматоров: t = t_R + 2t^N_сум = t_R + 2t_c^{2 .} [log² N].

Например, при N = 32, имеют t = t_R + 2t_c^{2 .} log₂ 32 = t_R + 10t_c².

Принимая t_R = 40 нс и t_c² = 40 нс, имеют t = 40 + 400 = 440 нс.

Такое низкое быстродействие не позволяет обрабатывать, например, телевизионные изображения в реальном масштабе времени. Таким образом, недостатком устройства является низкое быстродействие.

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

Целью изобретения является сокращение аппаратурных затрат.

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

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

Сопоставительный анализ с другими техническими решениями показывает, что сумматоры, накапливающие сумматоры и вычитатели широко известны (см., например, Зельдин Е.А. Цифровые интегральные микросхемы в информационно-измерительной аппаратуре. - Л.: Энергоатомиздат, Ленинградское отделение, 1986). Блок деления может быть реализован как умножитель, на один вход которого подается величина, обратная делителю. Умножители широко известны (см. Титце У., Шенк К. Полупроводниковая схемотехника: Справочное руководство. М.: Мир, 1983). Блок элементов задержки может быть реализован как параллельное соединение сдвиговых регистров соответствующей длины, тактовые входы которых объединены и соединены с тактовым входом блока элементов задержки. Реализация сдвиговых регистров на основе интегральных микросхем широко известна (см. Титце У., Шенк К. Полупроводниковая схемотехника: Справочное руководство. М.: Мир, 1983).

Однако введение известных блоков в указанной связи между ними и с остальными элементами схемы позволяет сократить объем аппаратурных затрат и повысить быстродействие устройства. Это позволяет сделать вывод о соответствии предлагаемого решения критерию "существенные отличия".

На фиг. 1 представлена схема заявляемого устройства; на фиг. 2 показано взаимное расположение элементов текущей апертуры b_ij и предшествующей апертуры b_ij-1 и текущего отсчета x_ij изображения.

Устройство содержит блоки 1 и 2 элементов задержки, вычитатели 3 и 4, сумматор 5, накапливающий сумматор 6, блоки 7 и 8 деления, информационный вход 9 устройства, тактовый вход 10 устройства, вход 11 задания числа выборки одномерного массива, вход 12 задания числа выборок двумерного массива, выход 13 одномерного скользящего среднего, выход 14 одномерной скользящей суммы устройства, выход 15 двумерного скользящего среднего устройства, выход 16 двумерной скользящей суммы устройства.

Информационный вход 9 устройства соединен с входом уменьшаемого вычитателя 3 и входом блока 1 элементов задержки. Выход блока 1 элементов задержки соединен с входом вычитаемого вычитателя 3. Выход вычитателя 3 соединен с первым входом сумматора 5. Выход сумматора 5 соединен с входом блока 2 элементов задержки. Третий выход блока 2 элементов задержки соединен с вторым входом сумматора 5, выходом 14 одномерной скользящей суммы устройства и входом делимого блока 7 деления. Выход блока 7 деления является выходом 13 одномерного скользящего среднего устройства. Первый и второй выходы блока 2 элементов задержки соединены соответственно с входами уменьшаемого и вычитаемого вычитателя 4. Выход вычитателя 4 соединен с входом накапливающего сумматора 6. Выход накапливающего сумматора 6 соединен с выходом 16 двумерной скользящей суммы устройства и входом делимого блока 8 деления. Выход блока 8 деления является выходом 15 двумерного скользящего среднего устройства. Вход 11 задания числа выборок одномерного массива соединен с входом делителя блока 7 деления. Вход 12 задания числа выборок двумерного массива соединен с входом делителя блока 8 деления. Тактовые входы блоков 1 и 2 элементов задержки, накапливающего сумматора 6 и блоков 7 и 8 деления объединены и соединены с тактовым входом 10 устройства.

Блок 1 элементов задержки имеет длину L^.M, блок 2 элементов задержки имеет длину L, причем на его первом, втором и третьем выходах осуществляется задержка элементов на 1, N+1 и L тактов работы соответственно M и N - количество отсчетов в столбце и строке скользящей апертуры, L - количество отсчетов в строке изображения).

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

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

Текущая апертура b_ij и предшествующая апертура b_i,j-1 (см. фиг. 2) отличаются друг от друга двумя столбиками a_i,j-N и a_ij по М отсчетов в каждом. Учитывая это, можно записать MEAN(b_ij) = MEAN(b_i,j-1) + MEAN(a_ij) - - MEAN(a_i,j-N), (1) где МEAN(b_i,j-1) - сумма значений отсчетов апертуры b_i,j-1;
MEAN(a_i,j-N) - сумма значений отсчетов столбца a_i,j-N.
В свою очередь, столбики a_ij и a_i-1,j отличаются друг от друга двумя отсчетами x_i-M,j и x_ij. Учитывая это, можно записать
MEAN(a_ij) = MEAN(a_i-1,j) + x_ij - x_i-M,j, (2) где MEAN(a_ij) - сумма значений отсчетов столбика a_ij отсчетов высотой М;
x_ij - значение отсчета (i,j) изображения.

Подставив уравнение (2) в выражение (1), получают
MEAN(b_ij) = MEAN(b_i,j-1) + MEAN(a_i-1,j) + x_ij- - x_i-M,j - MEAN(a_ij-M).

(3)
Выражение (3) описывает порядок рекуррентного формирования значения суммы значений отсчетов текущей апертуры b_ij. При этом
x_αβ = 0;
MEAN(b_αβ) = 0;
MEAN(a_αβ) = 0, если α≅ 0 или β≅ 0. (4)
Локальные средние значения и по одномерной и двумерной апертурам формируются путем деления сумм a_ij и b_ij на соответствующее количество отсчетов в апертурах:
= a_ij;
= b_ij.

В начальный момент времени блоки 1 и 2 элементов задержки и накапливающий сумматор 6 обнулены.

Пусть в текущем k-м такте работы устройства код текущего отсчета x_ij с информационного входа 9 устройства поступает на вход уменьшаемого вычитателя 3 и вход блока 1 элементов задержки длины M^.L (где М - количество отсчетов в столбце скользящей апертуры, L - количество отсчетов в строке изображения). Код задержанного на М^.L тактов работы отсчета x_i-M,j с выхода блока 1 элементов задержки поступает yа первый вход вычитателя 3. Значение величины x_ij - x_i-M,j с выхода вычитателя 3 поступает на первый вход сумматора 5. Значение величины MEAN(a_i-1,j) с третьего выхода блока 2 элементов задержки длиной L поступает на выход 14 скользящей суммы устройства, на вход делимого блока 7 деления и второй вход сумматора 5. На выходе сумматора 5 формируется значение величины MEAN(a_ij) = MEAN(a_i-1,j) + x_ij - x_i-M,j (согласно (2)), поступает на вход блока 2 элементов задержки. Значение величины М с входа 11 задания числа выборок одномерного массива поступает на вход делителя блока 7 деления. Значение текущего скользящего среднего значения с выхода блока 7 деления поступает на выход 13 одномерного скользящего среднего устройства. Блок 2 элементов задержки длины L (L - количество отсчетов в строке изображения) предназначен для хранения промежуточных результатов - сумм MEAN(a_ik)(k=) отсчетов соответствующих столбиков. Значения величин MEAN(a_i,j-1) и MEAN(a_i,j-N-1) с второго и третьего выходов блока 2 элементов задержки поступают на входы уменьшаемого и вычитаемого вычитателя 4. Значение величины MEAN(a_i,j-1) - MEAN(a_i,j-N-1) поступает на вход накапливающего сумматора 6, в котором формируется значение MEAN(b_i,j-1) = =MEAN(b_i,j-2) + MEAN(a_i,j-1) - MEAN(a_i,j-N-1). Значение величины MEAN(b_i,j-2) с выхода накапливающего сумматора 6 поступает на выход 16 двумерной скользящей суммы устройства и на вход делимого блока 8 деления. На вход делителя блока 8 поступает значение величины M^.N с входа 12 задания числа выборок двумерного массива. Значение величины текущего скользящего среднего поступает на выход 15 двумерного скользящего среднего устройства.

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

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

В начальный момент времени блоки 1 и 2 элементов задержки и накапливающий сумматор 6 обнулены и на протяжении первых тактов работы осуществляется формирование промежуточных результатов согласно выражениям (1)-(3) с учетом начальных условий (4) для последующего рекуррентного вычисления соответствующих значений согласно выражениям (1)-(3).

Предлагаемое устройство работает в конвейерном режиме. Такт работы конвейера определяется временем срабатывания наиболее медленного звена конвейера. Такт работы предлагаемого устройства равен суммарному времени сдвига информации в элементе задержки и срабатывания сумматора и вычитателя:
= t_сд+t_c+t_в , где - время такта работы устройства;
t_cд - время сдвига информации в блоке элементов задержки;
t_c - время срабатывания сумматора;
t_в - время срабатывания вычитателя.

Принимая t_сд = 40 нс, t_c = 40 нс, t_в = 50 нс, имеют
= 40+40+50 нс = 130 нс .

Такт работы конвейера не превышает 130 нс. Быстродействие заявляемого устройства выше быстродействия прототипа в t/ = 440 нс/130 нс ≈ 3,4 раза.

Высокое быстродействие позволяет использовать заявляемое устройство в быстродействующих специализированных устройствах обработки различного рода сигналов, в частности для обработки телевизионных изображений в реальном масштабе времени. Рекуррентная организация процесса вычислений позволяет также существенно снизить аппаратурные затраты. Введение двух вычитателей и накапливающего сумматора позволяет вывести из устройства M+N-3 сумматоров (М и N - количество отсчетов в столбце и строке скользящей апертуры), М триггеров и счетчик. Объем блоков 1 и 2 элементов задержки, необходимый для запоминания промежуточных результатов вычислений, определяется выражением
= M·L·k+L·(k+[log₂M·N]) бит, где - общий объем блоков элементов задержки в битах;
М и N - количество отсчетов в строке и столбце скользящей апертуры;
L - количество отсчетов в строке изображения;
k - количество разрядов на информационном входе устройства.

Принимая М = N = 32, L = 512 и k = 8, имеют
= 32·32·8+512·(8+log₂(32·32) = 8192+9216 = 17408 бит.

Необходимый объем запоминающих элементов (блоков памяти) в устройстве-прототипе равен
V = 512^.32^.(8+log₂ 32) - 16024^.13 = 208312 бит.

Необходимый объем запоминающих элементов для хранения промежуточных результатов вычислений в заявляемом устройстве меньше, чем в устройстве-прототипе в V/ = 208312/17408 ≈ 12 раз.

В общем случае
ΔV = V- = L·M·(k+log₂N)-[M·L·k+L·(k+log₂M·N)] =→
→= L·M·log₂N-L·(k+log₂M+log₂N)=L·(M·log₂N-k-log₂M-log₂N,
где Δ V - величина в битах, показывающая насколько необходимый объем запоминающих элементов в заявляемом устройстве меньше, чем в устройстве-прототипе.

Таким образом, заявляемое устройство наряду с более высоким быстродействием отличается также существенно меньшим уровнем аппаратурных затрат.

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

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

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СКОЛЬЗЯЩЕГО СРЕДНЕГО ЗНАЧЕНИЯ, содержащее сумматор, два блока вычитания, первый блок деления и два блока элементов задержки, причем информационный вход первого блока элементов задержки является информационным входом устройства, тактовый вход которого соединен с тактовыми входами первого блока деления и первого и второго блоков элементов задержки, выход первого блока элементов задержки соединен с входом вычитаемого первого блока вычитания, выход которого подключен к первому входу сумматора, первый выход второго блока элементов задержки соединен с входом вычитаемого второго блока вычитания, выход первого делителя является выходом одномерного скользящего среднего устройства, входом задания числа выборок одномерного массива которого является вход делителя первого блока деления, отличающееся тем, что, с целью упрощения, в него введены второй блок деления и накапливающий сумматор, тактовые входы которых соединены с тактовым входом устройства, информационный вход которого подключен к входу уменьшаемого первого блока вычитания, выход сумматора соединен с информационным входом второго блока элементов задержки, второй выход которого является выходом одномерной скользящей суммы устройства и соединен с входом делимого первого блока деления и с вторым входом сумматора, третий выход второго блока элементов задержки подключен к входу уменьшаемого второго блока вычитания, выход которого соединен с информационным входом накапливающего сумматора, выход которого является выходом двумерной скользящей суммы устройства и соединен с входом делимого второго блока деления, входом делителя и выходом которого являются соответственно вход задания числа выборок двумерного массива и выход двумерного скользящего среднего устройства.

РИСУНКИ

Рисунок 1, Рисунок 2