Оцінка ефективності методу динамічного стиску відеозображень для найбільш розповсюджених розподілів яскравості та кольорів
У роботі розглянуто метод стиску інформації про зображення, що заснований на запам'ятовуванні лише значення старшого розряду рівня квантування для яскравості (кольору). Приведено критерій можливості використання даного методу для великих зображень, тобто доведено, що при щільності розподілу ймо...
Збережено в:
| Опубліковано в: : | Штучний інтелект |
|---|---|
| Дата: | 2017 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Інститут проблем штучного інтелекту МОН України та НАН України
2017
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/162339 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Оцінка ефективності методу динамічного стиску відеозображень для найбільш розповсюджених розподілів яскравості та кольорів / В.А. Бородін // Штучний інтелект. — 2017. — № 3-4. — С. 55-60. — Бібліогр.: 8 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859614662157402112 |
|---|---|
| author | Бородін, В.А. |
| author_facet | Бородін, В.А. |
| citation_txt | Оцінка ефективності методу динамічного стиску відеозображень для найбільш розповсюджених розподілів яскравості та кольорів / В.А. Бородін // Штучний інтелект. — 2017. — № 3-4. — С. 55-60. — Бібліогр.: 8 назв. — укр. |
| collection | DSpace DC |
| container_title | Штучний інтелект |
| description | У роботі розглянуто метод стиску інформації про зображення, що заснований на запам'ятовуванні лише значення старшого розряду рівня квантування для яскравості (кольору). Приведено критерій можливості використання даного методу для великих зображень, тобто доведено, що при щільності розподілу ймовірності вхідного параметра, що спадає швидше за o(x³), метод є достатньо ефективним. Ця ефективність кількісно оцінена.
In this paper the method for compressing images based on the coding only first digit representing brightness (color), is considered. The criterion for effectiveness of this method is deduced. It is proved, that for frequency distribution lower than o(x³) the method is effective and quality of this effectiveness is estimated.
|
| first_indexed | 2025-11-28T17:39:20Z |
| format | Article |
| fulltext |
ISSN 1561-5359. Штучний інтелект, 2017, № 3-4
© В.А. Бородін 55
УДК 681.327.5
В.А. Бородін
Київський національний університет імені Тараса Шевченка, Україна
вул. Володимирська, 64/13, м. Київ, 01601
ОЦІНКА ЕФЕКТИВНОСТІ МЕТОДУ ДИНАМІЧНОГО
СТИСКУ ВІДЕОЗОБРАЖЕНЬ ДЛЯ НАЙБІЛЬШ
РОЗПОВСЮДЖЕНИХ РОЗПОДІЛІВ
ЯСКРАВОСТІ ТА КОЛЬОРІВ
V.A. Borodin
Taras Shevchenko Kyiv National University, Ukraine
64/13, Volodymyrska str., Kyiv, 01601
THE ESTIMATION OF EFFECTIVENESS FOR THE
DYNAMICAL COMPRESSION METHODS FOR THE MOST
POPULAR BRIGHTNESS AND COLOR DISTRIBUTIONS
У роботі розглянуто метод стиску інформації про зображення, що заснований на
запам'ятовуванні лише значення старшого розряду рівня квантування для яскравості (кольору).
Приведено критерій можливості використання даного методу для великих зображень, тобто доведено,
що при щільності розподілу ймовірності вхідного параметра, що спадає швидше за )( 3xo , метод є
достатньо ефективним. Ця ефективність кількісно оцінена.
Ключові слова: стиск зображень, розподіли яскравості, динамічний метод стиску.
In this paper the method for compressing images based on the coding only first digit representing
brightness (color), is considered. The criterion for effectiveness of this method is deduced. It is proved, that for
frequency distribution lower than )( 3xo the method is effective and quality of this effectiveness is estimated.
Keywords: image compression, brightness distributions, dynamical compression methods.
Вступ
У комплексах реального часу, що здійснюють введення відеоінформації з
одночасною її обробкою, зокрема у системах спостереження, існує задача швидкого і
повного запам'ятовування одержуваних зображень для правильного функціонування
комплексу. Ця задача вимагає для свого вирішення великих обчислювальних
ресурсів, оскільки кожне зображення, а тим більше, серія зображень, що надходять з
частотою, необхідною для відтворення реального часу, є великим масивом
інформації [1],[2],[3].
З одного боку, ці масиви вимагають великого обсягу пам'яті для
запам'ятовування зображень. З іншого боку, велика кількість інформації вимагає
значних часових ресурсів на обробку і виконання задач комплексу (наприклад,
виявлення і фіксування проникнень у системах охорони) [4],[5].
Відомі методи кодування відеозображень і зображень полягають у компресії
даних з втратою, або без втрати, на основі різних алгоритмів стиску (MPEG, JPEG,
GIF і ін.), які дозволяють зберігати інформацію у більш стислому виді, але значно
сповільнюють роботу системи при обробці, оскільки кожен з цих методів вимагає
значних ресурсів пам'яті і часу для розпакування зі свого формату у формат,
придатний для обробки або адекватного відтворення на екрані [3],[6]. Особливо
важливою ця проблема стає при відображенні та розпізнаванні зображень з
великими динамічними роздільними межами [7], [8], які використовують великі
масиви зображень.
ISSN 1561-5359. Штучний інтелект, 2017, № 3-4
56 © В.А. Бородін
Тому існує задача такої організації збереження, обробки і представлення
відеоінформації, щоб зображення зберігалися у стислому вигляді, однак не вимагало
спеціальних трудомістких алгоритмів для свого розпакування й обробки.
Постановка проблеми
У роботі [3] пропонувався метод кодування відео- і числових послідовностей за
допомогою кодування послідовностей яскравостей, у якому запам'ятовується не вся
інформація, а лише перший значущий розряд у двійковому записі числа, що
відповідає даному значенню яскравості.
При такому підході можливі декілька варіантів кодування стиску. У даній роботі
досліджується метод кодування інформації [3], у якому замість повного числа, що
відповідає яскравості даної точки, запам'ятовується тільки рівень квантування, тобто
величина першого значущого розряду. При такому підході замість запам'ятовування
числа B , що відповідає яскравості, запам'ятовується число ][log 2 B . Відзначимо, що в
цьому випадку число буде зберігатися з помилкою
][log22
B
B .
Очевидно, що не для всіх можливих варіантів зображень, що потребують стиску,
даний метод може бути ефективним, тобто незважаючи на неминучі при такому
методі втрати якості зображення, воно зберігалося у достатній для подальшого
розпізнання якості та при цьому обсяг зображення, що зберігається, був менший, ніж
обсяг початкового зображення. Таким чином, постає задача знаходження критерію,
якому повинно відповідати зображення, щоб умова ефективності виконувалася. У
даній роботі критерій ефективності оцінюється для розподілів зображення та робиться
оцінка на ефективність цього кодування залежно від розподілу.
Аналіз останніх досліджень і публікацій
Оцінкам ефективності різноманітних методів стиску зображень, зокрема для
методів подібних до динамічного методу кодування яскравості, присвячено досить
багато статей: серед відносно недавніх можна відзначити статті [7],[8]. Однак, в
більшості з подобних робіт оцінюється коефіцієнт стиску зображень при такому
підході, в той час як в даній роботі ставиться обернена задача визначення критеріїв,
яким повинен задовольняти розподіл характеристик зображення для того щоб сам метод
стиску був ефективним, тобто коефіцієнт стиску був більшим за одиницю. Автором
даної роботи не було знайдено критеріїв оцінки методів стиску для динамічного методу
кодування, що вказував би на критерій, який можна застосувати до розподілів
яскравості, та визначав би при яких параметрах розподілу забезпечувався б високий
коефіцієнт стиску при незначній втраті інформації про зображення.
Оцінка ресурсів при використанні динамічного розподілу для загального
типу розподілу
Визначимо помилку при збереженні всієї послідовності значень яскравостей
при використанні даного кодування.
Очевидно, що для того щоб застосування методу було коректним, необхідно,
щоб зі збільшенням значень яскравості кількість таких значень спадала, тобто
функція розподілу спадала.
Розглянемо перший варіант такого кодування, при якому в пам'ять записується
тільки старший значущий розряд у значенні яскравості.
У цьому випадку помилка, що виникає при кодуванні числа x буде
дорівнювати
][log22
x
xx . Очевидно, її значення буде належати інтервалу [0,x/2].
Якщо прийняти, що на цьому інтервалі її значення буде розподілено
рівномірно, то математичне очікування помилки буде
42
2/0 xx
xM
.
ISSN 1561-5359. Штучний інтелект, 2017, № 3-4
© В.А. Бородін 57
Таким чином, на всьому інтервалі розподіл помилки буде визначатися за
формулою
0
)(
4
1
dxxxfxM .
Зокрема, для експоненціального розподілу
4
1
xM , а для розподілу Гауса
22
xM .
Отже, при такому варіанті кодування інформації неминучі помилки порядку
чверті математичного очікування самих величин.
Дисперсія помилки буде обчислюватися за формулою
0
2][log
4
1
)()2( 2 DxdxxfxxM
x
для монотонно спадного розподілу.
Тому, більш прийнятний другий варіант, у якому для збереження інформації
старший розряд ще й збільшується на коефіцієнт 1,5, тобто пороги зміщаються в 1,5 рази.
Тоді помилка буде визначатися за формулою
1][log223
x
xx , значення якої
лежить на інтервалі [-x/4,x/4].
Математичне очікування помилки буде 0xM за умови, що на зазначеному
інтервалі її значення буде розподілено рівномірно.
Отже, у цьому випадку, математичне очікування закодованої інформації буде
дорівнювати математичному очікуванню первісної інформації.
Дисперсія помилки при використанні такого кодування буде обчислюватись за формулою
0 0
21][log1][log
0
2
0
21][log
)()2(9)()2(6)()()23( 222 dxxfdxxfxdxxfxdxxfxxM
xxx
Зокрема, для експоненціального розподілу одержуємо
0 0
21][log1][log
0
2
0
21][log
)2(9)2(6)23( 222 dxedxexdxexdxexxM xxxxxxx
З огляду на те, що xxx 222 log][log1log , одержуємо, нерівності
2
1
xM і
2
17
xM .
А для нормального розподілу одержуємо
0
2/21][log 2
2
2
1
)23( dxexxM xx
.
Визначимо, за яких умов на функцію розподілу дисперсія помилки
використання зазначеного методу кодування буде сходитися і, тим самим,
визначимо умови застосовності методу.
Як було вже відмічено, для використання методу необхідно, щоб функція )(xf
розподілу монотонно спадала.
Відзначимо, що в цьому випадку )()()( bfxfaf при bxa .
Тоді
0
12
12
121
0
12
12
21
0
21][log
11
2 )12()23()()23()()23(
k
kk
k
kx
k
k
k
k
dxfxdxxfxdxxfxxM
ISSN 1561-5359. Штучний інтелект, 2017, № 3-4
58 © В.А. Бородін
0
31311
1
0
12
12
211
3
)232()232(
)12()23()12(
1
k
kkkk
k
k
kk fdxxf
k
k
0
123 )12(2
k
kk f .
З іншого боку, аналогічно одержимо нерівність
0
23 )12(2
k
kk fxM .
Перший ряд сходиться згідно з ознаками збіжності Д’Аламбера, якщо
1)12(2 123
kkk fq .
Отже, 1)12(8 1/1 kkf , тобто kkf 31 2)12( .
Другий ряд сходиться, якщо 1)12(2 23
kkk fq .
Отже, 1)12(8 /1 kkf , тобто kkf 32)12( .
Звідси, з огляду на монотонність функції розподілу, одержуємо, що функція
розподілу повинна задовольняти співвідношенню )()( 3 xoxf при x . Отже,
зокрема, нормальний та експоненціальні розподіли є ефективними для даного типу стиску.
У випадку послідовної обробки двовимірна функція яскравості В(X,Y), що описує
плоске зображення, перетвориться в одновимірну )](),([)( tYtXBtB за допомогою
його розгортки, де послідовно рядок за рядком аналізуються елементи зображення. При
цьому траєкторія розгортки або автоматично визначається сприйманим зображенням
або визначена раз і назавжди заздалегідь (примусове розгорнення).
Таким чином, розподіл яскравості та будь-яких інших параметрів для
двовимірного зображення можна звести до одновимірного розподілу. Таким чином,
дані оцінки годяться і для двовимірного зображення, незважаючи на
«одновимірність» проведених оцінок.
Оцінимо вигоду використання запропонованого методу в порівнянні з простим
запам'ятовуванням величин яскравості (кольорів).
У загальному випадку кількість необхідних при такому підході ресурсів пам'яті
(інформації) для збереження (введення) інформації про зображення з максимальною
яскравістю A і кількістю одиниць екрану (точок зображення) XYV для розподілу
ймовірності яскравості )(xF і щільності ймовірності яскравості )(xf буде
обчислюватися по формулі
V
dxxf
V
A
x
0
2 ))((log
при простому запам'ятовуванні параметрів, і
A
dxxf
V
A
x
0
22 ))((loglog при запропонованому методі, що забезпечує високу відносну
ефективність при V . Дійсно, зокрема для експоненціального розподілу
коефіцієнт стиску буде приблизно дорівнювати 2ln , а для нормального розподілу –
у більш ніж 2ln рази.
Висновки
Розглянуто метод динамічного стиску інформації відеозображення, що
використовує можливість запам'ятовування лише значення старшого розряду рівня
квантування для яскравості (кольору). Приведено критерій можливості використання
даного методу для великих зображень, тобто доведено, що при щільності розподілу
ISSN 1561-5359. Штучний інтелект, 2017, № 3-4
© В.А. Бородін 59
ймовірності вхідного параметра, що спадає швидше за )( 3xo ( де x наш параметр),
дисперсія помилки буде сходитися й оцінена його ефективність. Таким чином,
оцінюваний у роботі метод може бути застосований для стиску зображень у системі
побудови баз даних відеозображень.
Література
1. Гонсалес Р. Цифрова обробка зображень / Р. Гонсалес, Р. Вудс; [пер. з англ. під ред. П.А. Чочіа]. –
М.: Техносфера, 2006. – 1070 с.
2. Мартинес Ф. Синтез изображений: Принципы, аппаратное и программное обеспечение./ - М.:
Радио и связь, 1990 – 192 с.
3. Бутаков Е.А., Островский В.И., Фадеев И.Л. Обработка изображений на ЭВМ. – М.: Радио и
связь, 1987. – 240 с.
4. Боюн В.П. Динамическая теория информации. Основы и приложения. //ИК НАНУ, Киев, 2001.-326 с.
5. Арпс Р.Б. Сжатие двухуровневых изображений: Пер. с англ.- К.: УкрНИИНТИ, 1981.- 85 с.
6. Бородин В.А. Методы и средства представления и анализа динамической обстановки для
геоинформационных комплексов оперативного взаимодействия. Дис… к-та техн. наук:
05.13.06/Институт кибернетики НАН Украины – К., 2005.- 171 с.
7. Ballé J., Laparra V., Simoncelli E.P. End-to-end Optimized Image Compression // International
Conference on Learning Representations ICLR 2017 conference paper [Електронний ресурс]. – Режим
доступу: https://openreview.net/forum?id=rJxdQ3jeg¬eId=rJxdQ3jeg
8. Mantiuk R.K., Myszkowski K., Seid H.-P. High Dynamic Range Imaging [Електронний ресурс] //
Preprint of the article to be published in Wiley Encyclopedia of Electrical and Electronics Engineering. –
Режим доступу: https://www.cl.cam.ac.uk/~rkm38/pdfs/mantiuk15hdri.pdf
Literatura
1. Honsales R. Tsyfrova obrobka zobrazhen / R. Honsales, R. Vuds; [per. z anhl. pid red. P.A. Chochia]. –
M.: Tekhnosfera, 2006. – 1070 s
2. Martines F. Sintez izobrazheniy: Prinzypyi, apparatnoe i programmnoe obespechenie / - M.: Radio i
svyz’, 1990 – 192 s.
3. Butakov E.A., Ostrovskiy V.I., Fadeev I.L. Obrabotka izobrazheniy na EVM. – M.: Radio i svyaz, 1987. – 240 s.
4. Boyun V.P. Dinamicheskaya teoriya informatsii. Osnovyi i prilozheniya. //IK NANU, Kiev, 2001.-326 s.
5. Arps R.B. Szhatie dvuhurovnevyih izobrazheniy: Per. s angl.- K.: UkrNIINTI, 1981.- 85 s.
6. Borodin V.A. Metodyi i sredstva predstavleniya i analiza dinamicheskoy obstanovki dlya
geoinformatsionnyih kompleksov operativnogo vzaimodeystviya. Dis… k-ta tehn. nauk: 05.13.06/Institut
kibernetiki NAN Ukrainyi – K., 2005.- 171 s.
7. Ballé J., Laparra V., Simoncelli E.P. End-to-end Optimized Image Compression // International
Conference on Learning Representations ICLR 2017 conference paper [Elektronnyi resurs]. – Rezhym
dostupu: https://openreview.net/forum?id=rJxdQ3jeg¬eId=rJxdQ3jeg
8. Mantiuk R.K., Myszkowski K., Seid H.-P. High Dynamic Range Imaging [Elektronnyi resurs] // Preprint
of the article to be published in Wiley Encyclopedia of Electrical and Electronics Engineering. – Rezhym
dostupu: https://www.cl.cam.ac.uk/~rkm38/pdfs/mantiuk15hdri.pdf
RESUME
V.A. Borodin
The estimation of effectiveness for the dynamical compression methods for the
most popular brightness and color distributions
Despite the huge amount of research for compression of images and video sequences
methods, the problem is still actual and developments of the new approaches for
compression methods are continuously appearing. Also the theoretical estimations for the
researched methods are needed to be developed.
In this paper the method for compressing images based on the coding only first digit
representing brightness (color) is considered. This approach is used in some of the most
popular image and video compression methods. However, this method is not lossless and
the criterion for efficiency or possibility to use it correctly is required. In the article the
javascript:void(0)
https://openreview.net/forum?id=rJxdQ3jeg¬eId=rJxdQ3jeg
ISSN 1561-5359. Штучний інтелект, 2017, № 3-4
60 © В.А. Бородін
criterion for possibility of this method correctness is evaluated. The estimation of criterion
is based on the assumption that the distribution of the colors or brightness of the picture or
video sequence can be set by some function that is representing frequency distribution. For
this distribution the loss rate for the researched method is evaluated and compared with
compression rate.
It is proved that for a frequency distribution lower than )( 3xo the method is
effective and the quality of this effectiveness is estimated. Therefore, the researched
method can be effectively used for the most popular type of the distribution.
Надійшла до редакції 29.09.2017
|
| id | nasplib_isofts_kiev_ua-123456789-162339 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Ukrainian |
| last_indexed | 2025-11-28T17:39:20Z |
| publishDate | 2017 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Бородін, В.А. 2020-01-06T20:53:02Z 2020-01-06T20:53:02Z 2017 Оцінка ефективності методу динамічного стиску відеозображень для найбільш розповсюджених розподілів яскравості та кольорів / В.А. Бородін // Штучний інтелект. — 2017. — № 3-4. — С. 55-60. — Бібліогр.: 8 назв. — укр. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/162339 681.327.5 У роботі розглянуто метод стиску інформації про зображення, що заснований на запам'ятовуванні лише значення старшого розряду рівня квантування для яскравості (кольору). Приведено критерій можливості використання даного методу для великих зображень, тобто доведено, що при щільності розподілу ймовірності вхідного параметра, що спадає швидше за o(x³), метод є достатньо ефективним. Ця ефективність кількісно оцінена. In this paper the method for compressing images based on the coding only first digit representing brightness (color), is considered. The criterion for effectiveness of this method is deduced. It is proved, that for frequency distribution lower than o(x³) the method is effective and quality of this effectiveness is estimated. uk Інститут проблем штучного інтелекту МОН України та НАН України Штучний інтелект Системи розпізнавання і сприйняття образів Оцінка ефективності методу динамічного стиску відеозображень для найбільш розповсюджених розподілів яскравості та кольорів The estimation of effectiveness for the dynamical compression methods for the most popular brightness and color distributions Article published earlier |
| spellingShingle | Оцінка ефективності методу динамічного стиску відеозображень для найбільш розповсюджених розподілів яскравості та кольорів Бородін, В.А. Системи розпізнавання і сприйняття образів |
| title | Оцінка ефективності методу динамічного стиску відеозображень для найбільш розповсюджених розподілів яскравості та кольорів |
| title_alt | The estimation of effectiveness for the dynamical compression methods for the most popular brightness and color distributions |
| title_full | Оцінка ефективності методу динамічного стиску відеозображень для найбільш розповсюджених розподілів яскравості та кольорів |
| title_fullStr | Оцінка ефективності методу динамічного стиску відеозображень для найбільш розповсюджених розподілів яскравості та кольорів |
| title_full_unstemmed | Оцінка ефективності методу динамічного стиску відеозображень для найбільш розповсюджених розподілів яскравості та кольорів |
| title_short | Оцінка ефективності методу динамічного стиску відеозображень для найбільш розповсюджених розподілів яскравості та кольорів |
| title_sort | оцінка ефективності методу динамічного стиску відеозображень для найбільш розповсюджених розподілів яскравості та кольорів |
| topic | Системи розпізнавання і сприйняття образів |
| topic_facet | Системи розпізнавання і сприйняття образів |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/162339 |
| work_keys_str_mv | AT borodínva ocínkaefektivnostímetodudinamíčnogostiskuvídeozobraženʹdlânaibílʹšrozpovsûdženihrozpodílívâskravostítakolʹorív AT borodínva theestimationofeffectivenessforthedynamicalcompressionmethodsforthemostpopularbrightnessandcolordistributions |