Спосіб відновлення бітових зображень на основі нерівновагового позиційного декодування

Реферат: Спосіб відновлення бітових зображень на основі нерівновагового позиційного декодування містить етапи переходу до кольорнорізнісного подання зображень, дискретно-косинусного перетворення. Замість етапу арифметичного декодування довжин двійкових серій використано спосіб нерівновагового позиційного декодування бітових площин на основі розрахунку довжин двійкових серій та обчислення значення коду для нерівновагого позиційного числа. UA 75936 U (54) СПОСІБ ВІДНОВЛЕННЯ БІТОВИХ ЗОБРАЖЕНЬ НА ОСНОВІ НЕРІВНОВАГОВОГО ПОЗИЦІЙНОГО ДЕКОДУВАННЯ UA 75936 U UA 75936 U 5 10 15 20 Запропонована корисна модель може бути використана в сучасних інформаційнокомунікаційних системах та мережах. На сучасному етапі технологія стиску та відновлення зображень на основі їхнього трансформування реалізована в таких форматах як JPEG, JPEG-LS, JPEG2000. Існуючі технології компресії та декомпресії не забезпечують необхідного рівня обсягів компактного представлення та відновлення зображень. Тому постає актуальна задача підвищення ступеня стиску зображень з регульованою втратою їх якості в інформаційних системах та мережах реального часу. Розробку даного способу пропонується проводити на базі подальшого розвитку технології стиску формату JPEG, що обумовлено тим, що ступені стиску для методів з регульованою втратою якості найбільш близькі до необхідних значень та забезпечують найбільші ступені стиску в реальному часі. Спосіб відновлення бітових зображень на основі нерівновагового позиційного декодування, розроблений на основі корисної моделі, може бути використаний для реконструкції зображення з погрішністю, яка не перевершує погрішність, сформовану на етапі компресії, при заданій кількості службових даних і мінімізації кількості операцій на обробку. Задачею даного способу є відновлення бітових зображень із заданою якістю їхньої реконструкції. Технічний результат, який може бути отриманий при створенні даної корисної моделі полягає в забезпеченні репродукції зображень із заданою вірогідністю при: мінімізації впливу помилок, внесених на етапі стиску, тобто величина показника погрішності після відновлення зображення не перевищує величину показника погрішності для етапу компактного подання; використанні службових даних, які безпосередньо формуються на етапі стиску, що дає можливість досягти виграш за ступенем стиску в середньому 25 % для режиму обробки без  25 30   втрати якості ren  60 дБ ; 15 % - для режиму обробки із втратою якості ren  30 дБ . Впровадження даної корисної моделі підвищить ефективність функціонування інформаційно-комунікаційних систем та мереж на основі забезпечення заданого часу обміну оперативною інформацією і її якістю. Основне завдання, що вирішують в процесі відновлення відеоданих в сучасних інформаційних системах, пов'язано із забезпеченням одержання зображень із заданою вірогідністю при виконанні наступних умов: 1) мінімізують вплив помилок, внесених на етапі стиску, тобто величина показника похибки ren  30 дБ після відновлення зображення не повинна перевищувати величину показника    похибки com для етапу компактного подання: ren  com (1.1) 35 40 45 50 55 де  com ,ren - пікове значення відношення сигнал/шум відповідно на етапі стиску й відновлення відеоданих; 2) використати тільки ті службові дані, які безпосередньо формуються на етапі стиску; 3) мінімізувати кількість арифметичних операцій і в першу чергу кількість операцій множення й операцій ділення. Зрозуміло, що дані умови є взаємозалежними. Тому їх необхідно розглядати в контексті конкретної технології компресії зображень, а саме: технології компактного подання трансформованих зображень на основі нерівновагового позиційного кодування. Метод нерівновагового позиційного кодування інтегрований у технологію стиску трансформованих зображень, базовий варіант реалізації якої служить для побудови стандартів класу JPEG. Відмінності від відомих методів декодування полягають у тому, що бітові площини трансформанти представляють на основі локальнорівномірних нерівновагих позиційних чисел, побудованих на основі довжин двійкових серій. Це дозволяє: визначити кількість і границі кодів, затрачених на стисле подання бітових площин, без використання додаткових службових даних і без виконання умови префіксності, а також виникає можливість відновлювати трансформанти без внесення погрішностей. Задача вирішується тим, що, згідно з корисною моделлю, замість етапу арифметичного декодування довжин двійкових серій використано спосіб нерівновагового позиційного декодування бітових площин з на основі розрахунком довжин двійкових серій та обчислення значення коду для нерівновагового позиційного числа. Звідси, структурно-функціональна схема технологічного процесу відтворення зображень буде включати такі базові етапи (креслення): 1 UA 75936 U 1. Відновлення компонент трансформант дискретного косинусного перетворення. На даному етапі забезпечують одержання компонент c  трансформант С дискретного косинусного k перетворення (dct): c,1 1 c,2 1 C  c ,1 k c  ,2 k c ,1 c ,2 q q 5  c, 1  c,qc 1   c  ,   c  , q , k k   c ,  c ,qc q q q  qc  1 QQc / q qc , , де c  - компонента, розміщена в трансформанті на перетинанні k -й рядка й  -го стовпця; k QQc / q qc  - кількість трансформант розміром q  qc , що формується для зображення та містить Q  Qc елементів. У відповідності із умовою (1.1) на даному етапі обробки виключають похибки, тобто: det  0 , (1.2) 10 де  det - середньоквадратичний показник похибки між значеннями компонент на вході етапу кодування й значеннями компонентів на виході етапу декодування. Це пояснюється тим, що припустима кількість психовізуальної надмірності усувається на етапі квантизації компонент. 2. Якщо в процесі компресії проводилася квантизація, то значеннями величин c  k являються округлені значення квантизованих компонент. Якщо буде потреба у проведенні 15  деквантизації. У результаті чого виходять компоненти c k , їх значення мають динамічний діапазон, близький до вихідного. Деквантизацію задають наступним співвідношенням:  c k  c  qk;  , (1.3) k     20 де q k;  - k;  -й елемент матриці квантизації. У разі використання процесів квантизації при обробці компонент відбувається внесення похибки. Тому, в загальному випадку виконують нерівність:  c k  c k , (1-4) де 25 c k k;   -я компонента вихідної трансформанти дискретного косинусного перетворення. У свою чергу, якщо виконується умова (1.4), то:  tr  0 , (1.5)  де  tr - середньоквадратичний показник похибки відновлених значень компонент c k щодо вихідних c k . Процес відновлення значень компонент завершують після визначення їхнього знака. Якщо  інформацію про знак компонента c k представити величиною sk , : 30 0,  c k,  0; (1.6) sk,   , 1  c k,  0,  то остаточне c ks  значення k;   -й компоненти буде дорівнювати:   c  ,  sk,  0;  (1.7) c ks    k   c k  ,  sk ,   1 ,  Для виконання умови (1.1) забезпечують виконання наступної умови: str   tr , (1.8) 2 UA 75936 U  де  str - середньоквадратичний показник похибки відновлених значень компонент c ks   5 щодо вихідних c k з урахуванням додавання знака sk , . Виконання умови (1.8) обумовлює необхідність відтворення інформації без похибок про значення компонент трансформант. 3. Організовують виконання зворотного двовимірного двох етапного дискретного косинусного перетворення. На цьому етапі здійснюється реституція кольорововідмінного подання зображення 10 Y  yi j  U   i j  V  vi j  i  1 Q , j  1 Qc . , u , , , , Двопрохідну реалізацію зворотного двовимірного dct задають наступними співвідношеннями: 1) на першому проході виконують одновимірне зворотне дискретне косинусне перетворення стовпців трансформанти Ck,   . Формують проміжний масив Hi, j  FiCk,  i, j , (1.9) де Hi, j : Hi, j - проміжний масив розмірності q  qc , Fk  - вектор дискретних значень базисних функцій dct: 15 1   i  1;  q  (1.10) Fi   2q  1i ,  i  2, q . 2  cos   q 2q  З урахуванням співвідношення (1.10) вираз (1.9) прийме вигляд: H1 j  , Hi, j  де 20 1 q q  C i 1 k ,  i, j ; (1.11) 2q  1i 2 q k,   Ci, j cos 2q , i  2, q q i 1   Ci,kj,  - елемент масиву Ck,   , розташований на перетинанні і -го рядка й j -го стовпця трансформанти; 2) другий прохід пов'язаний з виконанням одномірного зворотного dct для рядків проміжного масиву H i, j :   Xi, j  Hi, jFT  j , (1.12)  де Xi, j - масив відеоданих після етапу зворотного dct, що належить однієї із площин кольоровідмінної моделі зображення, 25     Xi, j  xij ;FT j - транспонований вектор дискретних значень базисних функцій dct. У разі виконання умови (1.5) між вихідним x ij і відновленим виконується нерівність:  xij значеннями відеоданих  xij  xij , (1.13) 30 яка, у свою чергу, приводить до того, що: ren  0 , (1.14) де  ren - середньоквадратичний показник похибки відновлених значень відеоданих щодо вихідних x ij . Після репродукції окремих масивів відеоданих кольоровідмінного подання зображення. Y  y i j , U  ui j , V  v i j   35     4. Організовують одержання колірних площин  xij елементів формують площини R  i j  G   i j  B   i j  i  1 Q , j  1 Qc . r , g , b , , , Для того, щоб величина  ren не збільшувалася, відновлення вихідного подання зображення потрібно проводити на основі наступних формул: 3 UA 75936 U rij  uij  gij; gij  yij  uij  v ij  / 4; (1.15) bij  v ij  gij, де rij, gij, bij - елементи, розташовані на (і;j)-й позиції відповідно до колірної площини R, G, і В. 5 10 15 Таким чином, на основі співвідношень (1.3), (1.7), (1.9)-(1.12) і (1.15) здійснюють реалізацію базових технологічних функцій по відновленню зображення. Розглянутий базовий процес відновлення висуває вимоги щодо реалізації технології декодування кодових конструкцій стислого подання, що полягає в: забезпеченні відновлення квантизованих компонент трансформант без внесення похибки; використанні службових даних, формованих у процесі кодування; одержанні інформації про знаки компонент трансформант. Для одержання трансформант dct розроблено метод відновлення бітових площин трансформант на основі нерівновагового позиційного декодування (НРПД). Основі етапи НРПД: 1. Визначають кількість  кодових слів, затрачених на стисле подання масиву M довжин двійкових серій. Оскільки при формуванні кодових слів використовують локально-рівномірний принцип розподілу двійкових розрядів, то для одержання величини  : 1) обчислюють границі між кодовими словами; 2) одержують границі W E останнього кодового слова, що входять до складу стислого    подання масиву довжини двійкових серій (ДДС). За умови технології кодування, значення кодів E j обчислюють для стовпців масиву ДДС. 20 Кількість двійкових елементів, що дорівнює qbp q qc , є відомим як на передавальній, так і на приймальній сторонах. Звідси сума всіх елементів масиву ДДС дорівнює s  1 s  i, j  i,  qbp qqc (1.16) i 1 j 1 i 1 де i, j - значення (i;j) -й довжини двійкової серії, зменшене на 1; стовпці, 25 s - кількість елементів в j-м j    1 ; s  - кількість елементів в  -м стовпці масиву ДДС. Одне кодове слово формують для одного стовпця масиву довжин двійкових серій. Отже, після декодування коду E j відновлюють стовпець масиву M , елементи якого:  s  , j  s , , j j;    i, j містять   інформацію про кількість відновлених qj елементів бітового подання трансформанти (БПТ): 30  s   i, j,  j  ;  (1.17) q j   si 1    ,  j  .  i 1 i,  Усього після декодування  кодів, де j   , буде відновлено q  двійкових елементів БПТ:   s   i, j,  j  ;   j 1 i 1 (1.18) q   q j    s  j 1   ,  j  .  j 1 i 1 i,  Тоді кількість q  , невідновлених елементів БПТ, на момент декодування θ-го коду обчислюють за формулою: 4 UA 75936 U  s  qbp q qc    i, j ,  j  ;   j 1 i 1 (1.19) q  qbp q qc  q    s qbp q qc    i, ,  j  .  j 1 i 1  Оскільки величина q  залежить від кількості декодованих кодів нерівновагового 5 позиційного числа (НРПЧ), то співвідношення (1.19) використовують як умову закінчення процесу репродукції бітового подання поточної трансформанти. Зрозуміло, якщо виконується умова: q   0 , (1.20)  то декодований код є останнім для поточного масиву ДДС, а   0 . Визначають границі між кодовими словами. Оскільки за умовами процесу кодування в кодових словах утримують інформація про значення коду E j НРПЧ, то довжина W Ej кодових   10 слів обчислюють за формулою (1.42): W Ej   [og 2 ( fi  1)]  1 j  1  , (1.21) , , s i 1 де fi - основа і-го елемента НРПЧ; s - кількості елементів, для яких формується код E j . В межах обробки одного БПТ довжина кодових слів є рівномірною, тобто: W Ej    W Ej    W E . (1.22)    15       Тому для визначення кількості розрядів W Ej потрібна інформація про: основи елементів НРПЧ; кількість fi , i  1, s s елементів, для яких формується код E j . Відповідно до методу кодування, інформація про основи елементів НРПЧ є службовою й утримується в кодових конструкціях стислого подання зображення. Величину s обчислюють за наступною формулою: 20 s  W /([ og 2q qc ]  1) , де q qc - кількість елементів у бітових площинах (БП); W - задане значення обмежень на довжину кодових слів. Оскільки величина W заздалегідь задана, а величини q  й q c 25 визначають відповідно як кількість рядків і стовпців у трансформанті, то всі необхідні відомості для одержання величини s є відомими. Після визначення довжини кодових слів здійснюють перехід на наступний етап процесу нерівновагового позиційного декодування. 2. Проводять відновлення стовпців масиву ДДС. За умови методу кодування, елементи стовпців масиву M представляють як елементи нерівновагового позиційного числа. Тому  відновлення елементів масиву довжин двійкових серій проводять по формулах: 30 i, j  [ де Ej Pi ][ Ej ]f , i  1 s; j  1  , (1.23) , ,  i fiPi Pi - ваговий коефіцієнт елементів і -й рядка масиву M : Pi  s  f  . (1-24)    i 1 Аналіз (1.23), (1.24) вказує на те, що для одержання елементів i, j необхідно знати інформацію про значення коду E j й основ елементів НРПЧ. 35 Оскільки відома довжина кодового слова, то значення величини E j також буде відомим. Початок w jmin  (перший двійковий розряд) кодового слова W Ej  в кодовій структурі стислого подання з урахуванням співвідношення (1.21) обчислюють за формулою: min  . (1.25)  wj  ( j  1)([og2 (f1P1  1)]  1)  1 5 UA 75936 U Після декодування всіх кодів 1,1 1,2  Ej, j  1  будують масив M : , 1, 1 1,  M  s  ,1 s  ,2  s  , 1 s  , .   s,1 s  ,2  s, 1 5 На основі елементів масиву M формують масив ДДС із вихідним динамічним діапазоном  за формулою:  i, j  i, j  1, (1.26) де  i, j - (і;j) -й елемент масиву M , що містить ДДС із вихідним динамічним діапазоном. На базі отриманого масиву M організують побудову бітового подання трансформанти. 10 3. Відновлення бітового подання трансформанти на основі: відомих розмірів q qc бітових площин; заданого, за умови методу кодування, напрямку обходу БП. Бітове подання трансформанти формують по бітових площинах, починаючи зі старших БП. У свою чергу, як напрямок утворення БПТ обрано діагональний напрямок. Для діагонального утворення БПТ значення координат (k, ) визначають за наступною схемою: k  1, тобто розглядають діагоналі першої половини БПТ, коли   qc . Координата верхнього елемента діагоналі   1 й    , та інші елементи діагоналі обчислюють за - для 15 формулою (   1   1),   1  , а   ,1 ; ; , - для другої половини БПТ, коли   qc , a діагоналі  k k  1 q , координата верхнього елемента ,   qc , та інші елементи діагоналі обчислюють за формулою й (   1   1),   1 q , a   qc ,  . ; , Схема визначення значень елементів БПТ задають наступною системою виразів: 20        ; dk, k /     dk, k /    1,   k,    1 (1.27)        ,  dk, k /     dk, k /    1,   k,  1  де k /  - кількість двійкових елементів k -го рядка  -тої бітової площини, що передують початку  -ϊ двійкової серії (тобто кількість двійкових елементів двійкових серіях);    ф 1    k ,ф , що містяться у  Фk/ Фk /  - кількість двійкових серій сформованих для k -го рядка  -ϊ бітової площини, які передують  -й серії;  Ф k  1    ф 1 25  1  k,ф   k,Ф    q - кількість двійкових елементів у рядку k  бітової площини; Ф k  - кількість двійкових серій, утворених для k -го рядка  -ϊ бітової  площини, 1    Фk  . Бітове подання трансформант забезпечує відновлення інформації про значення компонентів c  , після чого технологічна обробка переходить на етап реконструкції вихідного динамічного k 30 35 діапазону компонент трансформант дискретного косинусного перетворення. За аналогією із процесом відновлення БПТ, здійснюється одержання двійкових матриць знаків компонент трансформант, інформація про які використовують на етапі остаточного формування значень компонент трансформант dct. Джерела інформації: 1. Чернега B.C. Сжатие информации в компьютерных сетях / B.C. Чернега - Севастополь: Изд-во СевГТУ, 1997.-214 с. 2. Ватолин В.И. Алгоритмы сжатия изображений. / В.И. Ватолин - М.: МГУ, 1999.-76 с. 6 UA 75936 U 3. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. /В.И. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин -М.: ДИАЛОГ - МИФИ, 2002.-384 с. 4. Селомон Д. Стиснення даних, зображень і звуку. - Μ.: Техносфера, 2006.-386 с. 5 ФОРМУЛА КОРИСНОЇ МОДЕЛІ 10 Спосіб відновлення бітових зображень на основі нерівновагового позиційного декодування, що містить етапи переходу до кольорнорізнісного подання зображень, дискретно-косинусного перетворення, який відрізняється тим, що замість етапу арифметичного декодування довжин двійкових серій використано спосіб нерівновагового позиційного декодування бітових площин на основі розрахунку довжин двійкових серій та обчислення значення коду для нерівновагового позиційного числа. 15 Комп’ютерна верстка Г. Паяльніков Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 7