Метод оценки эффективности декодирования трехмерных

ІНФОРМАЦІЙНО–КЕРУЮЧІ СИСТЕМИ НА ЗАЛІЗНИЧНОМУ ТРАНСПОРТІ
УДК 629.391
РЯБУХА Ю.Н., кандидат технических наук (ХУВС им. И. Кожедуба)
Метод оценки эффективности декодирования
структур
с
позиции
целостности
и
видеоинформационного ресурса
трехмерных
доступности
Обосновывается, что ключевыми требованиями относительно безопасности видеоинформационного
ресурса являются: уменьшение их цифрового объема, повышение степени достоверности, сокращение времени
доступа и уменьшение времени обработки. Излагается разработка метода оценки эффективности
рекуррентного трехмерного полиадического декодирования, начиная с младших элементов. Отличительной
особенностью метода оценки сложности восстановления является то, что для снижения времени обработки
восстановление элементов трехмерного полиадического числа организовывается за один проход. Проводится
сравнительная оценка относительно доступности видеоинформационного ресурса с использованием различных
технологий реконструкции трехмерных структур данных.
Ключевые слова:. трехмерное декодирование структур видеоданных, количество арифметических операций
Введение
Ключевыми
требованиями
относительно
безопасности
видеоинформационного
ресурса
являются: уменьшение их цифрового объема,
повышение степени достоверности, сокращение
времени доступа и уменьшение времени обработки
[1 – 3]. Для обеспечения выполнения указанных
требований
в
работах
[3 – 5]
предложено
реорганизовать исходные видеоданные в трехмерные
структуры с последующим хранением, обработкой и
передачей их кодового эквивалента. Здесь устраняется
структурная
избыточность,
обусловленная
одновременным учетом ограничений на динамические
диапазоны по трем направлениям. Это позволяет
увеличить
относительно
методов
двумерного
кодирования степень сжатия данных без внесения
погрешности и сократить время выборки необходимой
информации из базы данных. В тоже время для
выполнения требования относительно эффективности
реконструкции видеоинформации по категориям
целостности и доступности необходимо разработать
соответствующий метод оценки. Это составляет цель
исследований статьи.
числа (ТПЧ) по известному на данный момент
значению накопленного произведения. Тогда, если
текущий элемент является допустимым, то появляется
возможность
его
восстановления
на
основе
накопленного на данный момент произведения
оснований предыдущих допустимых элементов ТПЧ. В
таком случае процесс восстановления состоит в
следующем:
1) для перового элемента с координатами (1;1;1 )
ТСД проводится проверка на его принадлежность
трехмерному полиадическому числу. Проверочное
M
правило заданно неравенством ψ111 ≤ 2 − 1 ;
2) для j i z -го элемента ТПЧ проверочное правило
задается неравенством
z
i −1` n c
j −1 n стр n с
γ =1
k =1 γ =1
η=1 k =1 γ =1
∏ ψ jiγ ∏ ∏ ψ jkγ ∏ ∏∏ ψηkγ
(1)
z
Разработка
метода
оценки
эффективности
рекуррентного
трехмерного
полиадического
восстановления, начиная с младших элементов
Для сокращения времени доступа в условиях
сохранения
требуемого
уровня
целостности
необходимо
использовать
однопроходное
декодирование, состоящее в обеспечении возможности
восстанавливать элемент трехмерного полиадического
≤ 2 M −1 ,
где
i −1` n c
j −1 n стр n с
∏ ψ jiγ ∏ ∏ ψ jkγ ∏ ∏∏ ψηkγ
γ =1
k =1 γ =1
η =1 k =1 γ =1
накопленное произведение оснований
структурной
части
( n стр ( j − 1 ) + ( i − 1 ) )
ТСД,
ψ ηkγ
состоящей
вертикалей
по
для
из
nс
элементов в каждой и вертикали с координатами
( j; i ) , содержащей z элементов.
 Ю.Н. Рябуха, 2014
65
ІКСЗТ, 2014 №4
ІНФОРМАЦІЙНО–КЕРУЮЧІ СИСТЕМИ НА ЗАЛІЗНИЧНОМУ ТРАНСПОРТІ
Соответственно восстановление элемента
a ji z
ψ j, i, z −1 ω j, i, z −1 ,
проводится по формулам:
произведению
a ji z = [ N(ν) / ω ji z ] − [ N(ν) /(ψ ji z ω ji z ) ] ψ ji z ;
U j, i , z −1 вычисляется по формуле
(2)
z −1
i −1` n c
j −1 n стр n с
γ =1
k =1 γ =1
η =1 k =1 γ =1
где
ω ji z
равный
ψ ηkγ
- весовой коэффициент элемента
накопленному
произведению
a ji z ,
оснований
для структурной части ТСД, состоящей из
( n стр ( j −1 ) + ( i − 1 ) )
в каждой
вертикалей по
и вертикали
с
nс
элементов
координатами
В тоже время недостатком восстановления является то,
что необходимо на каждом шаге восстановления
выполнять две операции деления и округления.
Однако, из анализа выражений (2) и (3) вытекает, что
существует возможность уменьшить количество
операций деления за счет организации рекуррентного
восстановления. Для этого в выражении (2) введем
U j, i , z −1
и
U j, i, z ,
равные
соответственно:
(ν )
U j, i, z−1 = [ N
Анализ
U j, i , z −1 зависит
( j, i, z − 1)-м шаге
U j, i , z −1
( j i z )-м
U 1,1, 0 = N
U 1,1,1 = [ N
(ν )
формулы
что
известных
на
обработки. Поэтому величина
N (ν )
являются на
шаге восстановления известными. Значит,
a ji z
требуется выполнить
допустимость на основе неравенства (1); вычислить по
U j, i, z ;
формуле (4) значение величины
значение произведения
между
величинами
Суммарное
U j, i , z ψ ji z
U j, i , z −1
количество
и
найти
и разности
U j, i , z ψ ji z .
µ d( rν )
операций
для
4
рекуррентного восстановления в направлении, начиная
с младших элементов, rν элементов ТПЧ по формулам
(1), (4) и (5) равно:
µ d( rν )
4
=
2 rν
(оп. умножения) + rν (оп. деления) +
+ rν (оп. округления) + rν (оп. вычитания) +
+ rν (оп. сравнения),
(6)
отводится соответственно на: rν операций умножения
(4)
для определения весового коэффициента
rν
rν
(5)
операций деления и округления для вычисления
величин
величины
66
ψ ji z ω ji z ;
операций сравнения для проверки неравенства (1);
U j, i, z ; rν
операций умножения для
произведения
U j, i , z ψ ji z ;
операций вычитания величины
ψ 111 ] =[ U 1,1,1 ψ 111 ] .
показывает,
величин,
и значение кода
вычисления
(ν )
от
для получения элемента
Согласно выражениям (4) формула (2) примет вид
a ji z = U j, i, z−1 − U j, i, z ψ ji z ;
последней
где перечисленное в формуле (6) количество операций
/ ω ji z ] ;
U ji z = [ N ( ν ) / ( ψ j i z ω ji z ) ] .
величина
( j; i ) , следующие действия: проверить элемент a
j i z на
содержащей ( z −1) элементов.
Из анализа выражений (2) и (3) видно, что
восстановление
элементов
трехмерного
полиадического числа проводится за один проход: по
мере того, как добавляется очередной элемент
(удовлетворяющий неравенству (1)), сразу проводится
его восстановление. Для выполнения соотношения (2)
на каждом шаге восстановления требуется хранить в
(ν )
памяти только три значения: N
, ω j, i , z и ψ j i z .
обозначения
то
равен
U j, i, z−1 = [ N(ν) / ω ji z ] =[ N(ν) / ψ j, i, z−1 ω j, i, z −1 ] .
ω ji z = ∏ ψ jiγ ∏ ∏ ψ jkγ ∏ ∏∏ ψ ηkγ ,
(3)
ω j, i, z
Поскольку весовой коэффициент
U j, i , z ψ ji z
rν
от
U j, i , z −1 .
ІКСЗТ, 2014 №4
ІНФОРМАЦІЙНО–КЕРУЮЧІ СИСТЕМИ НА ЗАЛІЗНИЧНОМУ ТРАНСПОРТІ
Значит,
предложенное
рекуррентное
восстановление позволяет сократить в два раза
количество операций деления и округления. Но при
этом для такого варианта восстановления на каждом
j i z -м шаге необходимо хранить в памяти значения
четырех величин:
ψ ji z ,
т.е.
на
предыдущем
величина
N (ν ) , U j, i , z −1 , ψ ji z ω ji z
и
одно
в
случае.
значение
Таким
больше,
чем
значением
обработки. Остаточное значение кода образуется
путем рекуррентного деления величины
значение основания элемента ТПЧ, т.е.
(ν)
(ν )
на первом шаге N 111 = [ N
/ 1] ;
на втором шаге
U j, i , z −1
и
(ν )
(ν )
= [ N j, i, z −1
n стр n c
/ ψ j, i, z −1 ] = a ji z +
nc
k`
(ν )
N ji z = [ N j, i , z −1 / ψ j, i , z −1 ] = [ N ( ν ) / ψ j, i , z −1 ω j, i , z −1 ] .
N (ν )
(7)
С учетом формирования кода для полиадического
(ν)
числа с младших элементов, величина N j i z будет
являются прямо пропорциональными. Значит, их
можно заменить одной величиной. В качестве такого
параметра предлагается использовать остаточное
(ν)
(ν )
значение N j i z исходного кода N
на j i z - шаге
(ν )
N ji z
равна
γ −1
nc
∑ a ji γ ∏ ψ ji φ +
γ = z +1
γ −1
φ= z
n стб n стр n c
∑ ∑ a jk γ ∏ ψ ji φ ∏ ∏ ψ jβφ + ∑ ∑ ∑ a η k γ ×
+
k =i +1 γ =1
φ= z
n стр ` n c
nc
× ∏ ψ ji φ
φ= z
η = j+1 k =1 γ =1
β =i +1 φ =1
η
γ −1
k
∏ ∏ ψ jβφ ∏ ∏ ∏ ψαβφ .
β =i +1 φ =1
(8)
α = j+1 β =1 φ =1
Кроме того, с учетом формул (4) и (7) получим
(ν )
U j, i, z−1 = N ji z . Выразим теперь величину U ji z
Согласно выражению (8) остаточное значение кода
(ν)
N ji z на каждом шаге декодирования можно разбить
на две составляющие. Первая составляющая содержит
элемент
a ji z ,
U
×
(ν )
ji z = [ N ji z
через
а вторая – содержит сомножитель,
кратный значению основания
+
(ν )
N 112 = [ N 111 / ψ 111 ] ;
на j i z - шаге
является
U j, i , z −1 . В тоже время анализ выражения
(4), показывает, что величины
(ν)
N ( ν ) на
j i z -го элемента ψ ji z .
/ ψ ji z ] = a j, i, z +1 +
n стр n c
nc
k =i +1 γ =1
φ = z +1
(ν)
N ji z
k`
nc
γ −1
∑ a ji γ ∏ ψ j i φ +
γ = z+2
γ −1
φ = z +1
n стб n стр n c
∑ ∑ a jk γ ∏ ψ ji φ ∏ ∏ ψ jβφ + ∑ ∑ ∑ a η k γ ×
nc
n стр ` n c
η= j+1 k =1 γ =1
β =i +1 φ =1
η
k
γ −1
∏ ψ ji φ ∏ ∏ ψ jβφ ∏ ∏ ∏ ψαβφ .
φ = z +1
β =i +1 φ =1
(9)
α = j+1 β =1 φ =1
67
ІКСЗТ, 2014 №4
ІНФОРМАЦІЙНО–КЕРУЮЧІ СИСТЕМИ НА ЗАЛІЗНИЧНОМУ ТРАНСПОРТІ
Сравнив выражения (4) и (9), получим, что
[ N ( ν ) /(ψ ji z ω ji z ) ] = [
[ N ( ν ) ω ji z ]
ψ ji z
(ν )
] =[
N ji z
] =[
ψ ji z
U j, i, z −1
ψ ji z
].
В этом случае выражение (2) примет вид
a ji z =[ N(ν) / ω ji z ] −[ N(ν) / ψ ji z ω ji z ] ψ ji z = U j, i, z −1 −[ U j, i, z −1 / ψ ji z ] ψ ji z ;
(10)
U ji z = [ U j, i, z −1 ψ ji z ] .
Анализ полученного выражения показывает, что
a ji z
выполнить такое же количество операций как на
основе выражения (5), но требуется хранить три
U j, i , z −1 , ψ ji z
и
ψ ji z ω ji z ,
с размерами
т.е. на
элементов
трехмерной
структуры
данных равно:
µ (max)
= 2 n стб n стр n с (оп. умножения) +
d
4
+
n стб n стр n с
(оп. деления) +
+
n стб n стр n с
(оп. округления) +
+
n стб n стр n с
(оп. вычитания) +
+
n стб n стр n с
(оп. сравнения).
Для случая
n стб = n стр = n с = n
(11)
от
U мп .
n
для
U мп = 10
(max)
µ (max)
, td
d4
4
−10
и
Td(max)
4
(м.о./с), полученная на
основе соотношений (12) – (14), приведена
соответственно в табл. 1 и 2. Откуда видно, что
суммарное
время
восстановления
трехмерной
структуры данных для рекуррентного восстановления
в направлении, начиная с младших элементов (при
трех
параметрах)
снижается
относительно
рекуррентной обработки в направлении, начиная со
старших элементов в среднем в 1,37 раз. Такой
выигрыш по времени восстановления достигается в
результате сокращения в 2 раза количества операций
умножения.
Таблица 1
(max)
(max)
Зависимость µ d 4
и td
от n
4
Типы операций
Размер
ТСД
(12)
n=4
t (max)
d
на восстановление
4
трехмерной структуры данных находятся по формуле
t (max)
= 7,8 n 3
d4
(14)
4
Зависимость величин
максимальное
µ(max)
= n 3 ( 2,6 + 2,7 +1+1,5 ) = 7,8 n 3 .
d
Временные затраты
кадра изображения
Zстр × Zстб равно
4
количество
операций
для
рекуррентного
восстановления в направлении, начиная с младших
элементов с четырьмя параметрами равно
4
4
Td(max) = Zстр × Zстб t (max)
n3 .
d
одну величину меньше.
На основе выражения (6) максимальное суммарное
(max)
количество операций µ d
на восстановление
4
n стб n стр n с
Td(max)
64
166,4 172,8
сравнения,
1,5
величины
Время восстановления
необходимо
деления,
2,7
элемента
умножения,
1,33
восстановления
вычитания,
1
для
Суммарное время
на восстановление,
t (max)
, сек
d1
96
4,9 ×10 −8
n = 8 512 1331 1382 768
n = 16 4096 10649 11059 6144
3,9 ×10 −7
3,2 ×10−6
(13)
68
ІКСЗТ, 2014 №4
ІНФОРМАЦІЙНО–КЕРУЮЧІ СИСТЕМИ НА ЗАЛІЗНИЧНОМУ ТРАНСПОРТІ
Таблица 2
(max)
Зависимость Td
от размера кадра и объема ТСД
4
1.
Объем
ТСД
Td(max) , сек
2.
64
8 ×10 −4
512
7,9 ×10−4
64
4,6 ×10 −3
512
4,5 ×10
−3
64
2,6 ×10 −2
512
2,66 ×10 −2
Размер кадра
1024×1024
3000× 2000
7000× 5000
4
Основной
недостаток
поэлементного
рекуррентного восстановления в направлении, начиная
с младших элементов (при трех параметрах) состоит в
том что: восстановление текущего
элемента
проводится только после восстановления предыдущего
элемента и проверки текущего элемента на
допустимость. В этом случае перед выполнением
выражения (11) требуется вычислить текущее значение
накопленного произведения оснований и сравнить его
с максимально возможным значением для заданной
длины машинного слова, т.е. требуется выполнить
одну операцию умножения и сравнения.
Выводы
1. Разработан метод оценки эффективности
рекуррентного
трехмерного
полиадического
декодирования, начиная с младших элементов.
Отличительной
особенностью
метода
оценки
сложности восстановления является то, что для
снижения
времени
обработки
восстановление
элементов трехмерного полиадического числа (ТПЧ)
организовывается за один проход. На каждом шаге
восстановления требуется хранить в памяти только три
значения:
U j, i , z −1 ,
ψ ji z
и
ψ ji z ω ji z .
Предложенное
рекуррентное
восстановление
позволяет дополнительно сократить в два раза
количество операций деления и округления.
2. Суммарное время восстановления трехмерной
структуры данных для рекуррентного восстановления,
начиная
с
младших
элементов,
снижается
относительно рекуррентной обработки, начиная со
старших элементов в среднем в 1,37 раз. Такой
выигрыш по времени восстановления достигается в
результате сокращения в 2 раза количества операций
умножения.
3.
4.
5.
Литература
Гонсалес Р. Цифровая обработка изображений /
Р. Гонсалес, Р. Вудс. – М.: Техносфера, 2005. –
1072 с.
Беляев Е.А. Сжатие видеоинформации на основе
трехмерного дискретного псевдо-косинусного
преобразования для энергоффективных систем
видеонаблюдения / Е.А. Беляев, Т.М. Сухов,
Н.Н. Шостацкий // Компьютерная оптика, том 34,
2, С. 260 – 272, 2010.
B. Furht, Ken Gustafson, Hesong Huang and Oge
Marques, An Adaptive Three-Dimensional DCT
Compression Based on Motion Analysis //
Proceedings of the 2003 ACM symposium on Applied
computing, 2003.
Barannik V.V. Method of the 3-D Image Processing /
V.V. Barannik, S.V. Karpenko // Modern problems of
Radio
Engineering,
Telecommunications
and
Computer Science. Proceedings of the International
Conference TCSET’2008, Lviv-Slavsko, Ukraine,
February 20 – 24, 2008. – P. 115 – 117.
Баранник В.В.
Трехмерное
полиадическое
кодирование в направлении, начиная с младших
элементов / В.В.Баранник, Ю.Н. Рябуха // Сучасна
спеціальна техніка. – 2013. - №3. – С. 15 – 20.
Рябуха
Ю.М.
Метод
оцінки
ефективності
декодування тривимірних структур з позиції
цілісності і доступності ресурсу відеоінформації.
Обґрунтовується, що ключовими вимогами щодо
безпеки ресурсу відеоінформації є: зменшення їх
цифрового об'єму, підвищення міри достовірності,
скорочення часу доступу і зменшення часу обробки.
Висловлюється розробка методу оцінки ефективності
рекурентного тривимірного поліадичного декодування,
починаючи з молодших елементів. Відмітною
особливістю методу оцінки складності відновлення є
те, що для зниження часу обробки відновлення
елементів
тривимірного
поліадичного
числа
організовується за один прохід. Проводиться
порівняльна оцінка щодо доступності ресурсу
відеоінформації з використанням різних технологій
реконструкції тривимірних структур даних.
Ключові слова: тривимірне декодування структур
відеоданих, кількість арифметичних операцій.
–––––––––––––––––––––––––––––––––––
69
ІКСЗТ, 2014 №4
ІНФОРМАЦІЙНО–КЕРУЮЧІ СИСТЕМИ НА ЗАЛІЗНИЧНОМУ ТРАНСПОРТІ
Ryabuha Yu.N. Method of estimation of threedimensional structures efficiency decoding from the
position of integrity and availability of video
information resource. It has been grounded that key
requirements concerning the safety of video information
resource are: contraction of their digital volume, increase
of reliability degree, reduction of access time and
contraction of processing time. The development of the
method of recurrent three-dimensional polyadical decoding
efficiency estimation beginning with least significant
elements is stated. The distinctive feature of the recovery
complexity estimation method is that to decrease the
processing time, the recovery of elements of threedimensional polyadical number is organized in a single
pass. A comparative estimation concerning the availability
of video information resource with the use of different
technologies of three-dimensional data structures
reconstruction is conducted.
Key words. Three-dimensional decoding of video
information structures, the amount of arithmetic
operations.
Рецензент д.т.н., профессор Безрук В.М. (ХНУРЭ)
Поступила 31.03.2014г.
70
ІКСЗТ, 2014 №4