СПОСОБ ОПТИМАЛЬНОГО ФОРМИРОВАНИЯ ВИЗУАЛЬНОГО ИЗОБРАЖЕНИЯ Российский патент 1995 года по МПК G06T1/20 

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

Из технического решения [1] известен способ параллельной обработки видеоинформации, в котором в кадре выбирают нечетное число пикселей: число пикселей по горизонтали (2k+1) и вертикали (2L+1), в результате чего образуется решетка прямоугольных пикселей; вычислению подвергается пиксел, находящийся в центре этой решетки (картины). Для производства вычислений требуется (2L+1)(2k+1) вычислительных блоков (процессоров).

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

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

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

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

3. Способ не гарантирует минимизации затрат на его аппаратную реализацию, т.к. число разбиений экрана на квадраты ничем не определяeтся.

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

Это достигается тем, что в способе построения визуального изображения, заключающемся в непрерывном восстановлении массива пикселей, образующих заданную последовательность кадров, с помощью однородных процессоров, число процессоров выбирают, исхoдя из условия:
kpt ≅ n ≅ , где n число процессоров,
k число кадров в 1 с;
р число пикселей в кадре,
t₀ время восстановления (обработки) одного пиксела одним процессором,
С₀ стоимость коллективно используемых компонентов схемы;
С₁ стоимость одного процессора и используемого только им оборудования.

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

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

В обоих случаях инструментом оптимизации является число процессоров n.

Время обработки одного кадра обратно пропорционально числу процессоров, но не может быть меньше времени вычисления параметра одного пиксела одним процессором. Тогда справедливо равенство:
a+ , (1) где а и b коэффициенты, определяемые как:
(a + b/n) t₀, откуда а t₀.

При n 1, 1/k pt₀, откуда следует
b + t₀ pt₀ или
b (p 1)t₀, где t₀ время обработки одного пикселя.

Учитывая, что р > > 1 и приняв а t₀ (1) можно записать в виде
t₀+ , откуда следует
n kpt₀ (2)
Так как правая часть равенства (2) содержит произведение kp, определяющее качество изображения, уменьшение величины n по отношению к условию, задаваемому (2), приведет к нарушению качества изображения, что не допустимо. Таким образом, допустимым является такое число процессоров n, для которого справедливо:
n≥ kpt_o (3)
Как отмечалось выше, время формирования одного кадра определяется выражением t . Если положить, что стоимость единицы времени прибора линейно зависит от числа используемых процеcсоров n и определяется зависимостью вида С₀+ С₁n₁, то стоимость Q формирования одного кадра устройством, содержащим n однородных процессоров, равна:
Q qt₀(C₀ + C₁n)(1 + p/n), (4) где q коэффициент пропорциональности.

Приравнивая нулю производную dQ/dn, получим точку экстремума, которая соответствует условию:
C₁- 0, откуда следует
n (5)
Так как при любых значениях n вторая производная > 0 0, значение n, определяемое (4), соответствует минимальному значению Q.

Так как увеличение числа процессоров тогда ведет к росту Q, справедливо неравенство:
n≅ (6)
Сочетание (3) и (6) приводит к уcтановлению значений нижней и верхней границ выбора оптимального числа n.

В случае, если в результате реализации неравенств число n не окажется целым, а дробным, то оно округляется до ближайшего большего целого.

Кроме того, целое число n можно получить, осуществляя формирование числа процессоров пошагово в соответствии со следующим условием:
n n1 + n2 (7) где n1 entier(N)
n2 signum(N)
N kpt
Пример реализации изобретения показан на чертеже.

Устройство, реализующее способ, содержит входной коммутатора 1; канальные коммутаторы 2, 3, 4, управляющие соответственно, ключами 2.1-2.n, 3.1-3. n, 4.1-4.n; внешнюю память 5, систему управления 6, буферную память N1: блоки 7.1.11-7.n.21; процессоры 8.1-8.n; буферную память N2; блоки 9.1.12-9.n. 22; память 10 экрана и связи, показанные на этом рисунке.

Входящие в структуру устройства выполняют стандартные функции и реализуются с использованием стандартной элементной базы, например, блоки 1, 2, 3, 4, 6 могут быть выполнены на основе сходных по функции блоков из авт.св. [1] т.е. новых средств для своего осуществления предлагаемый способ не требует.

Пошаговый алгоритм работы этого устройства осуществляется следующим образом.

Шаг 1. Параметру j (номер кадра) присваивается значение, равное единице.

Шаг 2. Если j 2entier(j/2), т.е. если j четно, то перейти к шагу 4, если же j нечетно то к шагу 3.

Шаг 3. Параметру d присвоить значение, равное нулю, и перейти к шагу 5.

Шаг 4. d 1.

Шаг 5. Система управления устанавливает все коммутаторы следующим образом:
5.1. Коммутатор (1) разрешает чтение информации из внешней памяти и запись ее в буферную память N1, причем в те блоки, которые имеют номера i(2-d)1, где i 1,2.n. Запись в блоки с номерами i(d+1)1, i1, 2,n, запрещена.

5.2. Коммутатор 2 с помощью ключей 2i разрешает чтение информации из блоков буферной памяти N1 с номерами i(d+1)1, i 1,2,3,n, причем информация из i(d+1)1-го блока поступает в i-й процессор и, одновременно, запрещает чтение из блоков с номерами i(2-d)1, i 1,2,n.

5.3. Коммутатор 3 с помощью ключей 3.i разрешает запись информации в блоки буферной памяти N2 с номерами i(2-d)2, i 1,2,n, поступающeй из i-го процессора, и одновременно запрещает запись в блоки буферной памяти N2 с номерами i(d+1)2, i 1,2,n.

5.4. Коммутатор 4 с помощью ключей 4.i разрешает чтение информации из блоков буферной памяти N2 с номерами i(d+1)2, i 1,2,n и пересылку ее в соответствующие ячейки памяти экрана и, одновременно запрещает чтение из блоков буферной памяти N2 c номерами i(2-d)2.

Шаг 6. По открытым коммутаторами 1-4 каналам:
а) информация о j-ом кадре считывается блоком "система управления" из блока "внешняя память" и распределяется между блоками буферной памяти N1 c номерами i(2-d)1, i 1,2,n.

б) информация, содеpжавшаяся в блоке буферной памяти N1 c номером i(d+1)1, i 1,2,n, поступает в i-ый процессор (i 1,2,n) и после обработки записывается в блок буферной памяти N2 номером i (2-d)2;
в) информация, содержащаяcя в блоке i(d+1)2, i 1,2,n, переписывается в соответствующие ячейки памяти 10 экрана, формируя таким образом информацию для отображения (j-1)-го кадра.

Шаг 7. Величина j увеличивается на единицу.

Шаг 8. Если j превосходит максимальное допустимое значение, то перейти к шагу 9, в противном случае к шагу 2.

Шаг 9. Конец алгоритма.

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

Изобретение относится к вычислительной технике и предназначено для цифрового оптимального синтеза и воспроизведения изображения, звукового сопровождения и других восприятий с возможностью записи на носитель или вывода на экран. Способ заключается в непрерывном восстановлении массива пикселей, образующих заданную последовательность кадров, с помощью однородных процессоров, число n которых выбирается в соответствии с выражением: где k число кадров в 1 с, p - число пикселей в кадре, t₀ время восстановления (обработки) одного пиксела одним процессором, C₀ стоимость коллективно используемых компонентов схемы, C₁ стоимость одного процессора и используемого только им оборудования. Способ позволяет повысить быстродействие и минимизировать стоимость аппаратных затрат при его реализации. Приведен пример реализации способа устройством, построенном на принципе распараллеливания входной информации при обработке пикселей, включающим в себя внешнюю память, устройство управления, входной коммутатор, канальные коммутаторы с ключами, две буферные памяти, однородные процессоры, память экрана. 1 з.п. ф-лы, 1 ил.

1. СПОСОБ ОПТИМАЛЬНОГО ФОРМИРОВАНИЯ ВИЗУАЛЬНОГО ИЗОБРАЖЕНИЯ путем непрерывного восстановления массива пикселей, образующего заданную последовательность кадров, с помощью однородных процессоров, отличающийся тем, что число однородных процессоров выбирают из условия

где n число однородных процессоров;
k число кадров в секунду;
p число пикселей в кадре;
t₀ время восстановления одного пикселя одним процессором;
C_o стоимость коллективного использования компонентов;
C_i стоимость одного процессора и используемого им оборудования. 2. Способ по п. 1, отличающийся тем, что определение числа однородных процессоров осуществляют в соответствии с условием
n=n₁+n₂,
где n₁=entier(N),
n₂=signum(N),