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

Реферат: Спосіб стиснення зображень з урахуванням методу двоознакового структурного кодування, що містить етапи дискретно-косинусного перетворення та квантування. Введено етап формування матриці знаків та введено стиснення методом двоознакового структурного кодування, за яким слідує етап стиснення значень кодів-номерів з використанням методу RLE. UA 75932 U (12) UA 75932 U UA 75932 U 5 10 15 20 25 30 35 40 45 50 55 60 Запропонована корисна модель належить до галузі телекомунікаційних технологій і може бути використана для підвищення ступеня стиснення інформаційного потоку даних без внесення спотворень у відновлювану інформаційну структуру при вирішенні задач кодування джерела в системах обробки інформації. Відомий спосіб стиснення зображень без втрат [1], згідно з яким кодування значень пікселів зображення здійснюється відповідно до такого алгоритму: визначаються значення декількох сусідів поточного піксела; дані значення розглядаються як контекст цього піксела; контекст використовується для прогнозування піксела і для вибору розподілу вірогідності; вибраний розподіл застосовується для кодування помилки прогнозу за допомогою спеціального коду Голомба. Однак суттєвим недоліком цього методу є досить низький ступінь стиснення. Усереднене значення коефіцієнта стиснення, що досягається при компресії 24-бітних зображень, сягає 2. Відомий також метод стиснення зображень, вибраний як прототип, що є близьким за технічним рішенням до запропонованого [2]. Відповідно до відомого способу процес стиснення зображень відбувається у декілька етапів: 1) Виконується попередня обробка зображення, що приводить його до зручного для подальшого кодування вигляду. На даному етапі зображення з формату представлення моделлю RGB переводиться у формат колірність/світимість (YUV). Зображення розбивається на крупні пікселі. Укрупнення пікселів проводиться у співвідношенні 2:1 по горизонталі і вертикалі або в пропорціях 2:1 по горизонталі і 1:1 по вертикалі. Пікселі компонентів YUV збираються в блоки 8×8, що називаються одиницями даних. Якщо число рядків або стовпців зображення не кратно 8, то нижній рядок і правий стовпець повторюються необхідну кількість разів. 2) Застосовується дискретне косинус-перетворення (ДК11) до кожної одиниці даних, внаслідок чого формуються блоки 8×8 частот одиниць даних. Вони містять середнє значення в одиниць даних і поправки для високих частот. 3) Застосовується квантування - етап, на якому відбувається основна втрата інформації за рахунок округлення несуттєвих, високочастотних коефіцієнтів ДКП. 4) Всі 64 квантованих частотних коефіцієнта кожної одиниці даних, зчитані у порядку, що визначається зигзаґ-скануванням, кодуються з за допомогою комбінації методу RLE та методу Хаффмена. Декодер JPEG здійснює зворотні дії. Описаний спосіб має наступні суттєві недоліки: при підвищенні ступеня стиснення з'являються суттєві спотворення (втрати) у відновленій інформаційній структурі, проявляється ефект Гіббса - ореоли по межах різких переходів кольорів; водночас в режимі без втрати якості зображення ступінь стиснення є досить обмеженим і сягає 1,4; використання методу Хаффмена для кодування трансформованих інформаційних одиниць приводить до підвищення складності апаратно-програмної реалізації у зв'язку з необхідністю синхронізації нерівномірних кодових комбінацій на межах оброблюваних фрагментів. В основу корисної моделі поставлені такі задачі: 1) Сформувати спосіб стиснення зображень, який би не вносив спотворення у відновлену інформаційну структуру. 2) Забезпечити досягнення більшого у порівнянні з існуючими методами без втрат ступеня стиснення. 3) Побудувати технологію кодування, яка вимагатиме меншої кількості операцій у порівнянні з методом Хаффмена. Поставлені задачі вирішуються наступним чином: 1) На етапі попередньої обробки не використовують перехід до представлення зображення моделлю колірність/світимість. Також на даному етапі не використовують процедуру укрупнення пікселів, яка є першопричиною появи артефактів у відновлюваному зображенні. 2) Комбінація кодування методом RLE та методом Хаффмена замінена на стиснення методом двоознакового структурного кодування [3] (ДСК). На даному етапі проводять перехід від десяткових значень пікселів до побітового представлення структури зображення, що дозволяє врахувати структурні закономірності за сукупністю певних структурних ознак і сформувати згідно з їх значень коди-номери двійкових послідовностей, які входять до складу трансформованого зображення. 3) Враховують можливість додаткового стиснення значень кодів-номерів з використанням методу RLE. 1 UA 75932 U 5 10 15 20 25 Використання попередніх процедур трансформації - ДКП та квантування - забезпечує досягнення найбільш сприятливих умов для подальшого стиснення даних за рахунок обнуління більшості значень у сегментах 88 трансформованого зображення. Це в комбінації із застосуванням на подальшому етапі кодування методу ДСК та стисненням значень кодів номерів методом RLE дозволяє досягти значень коефіцієнта стиснення в межах від 4,79 до 5,52 в залежності від типу вихідного зображення. Кодування методом ДСК не вносить додаткових спотворень до відновлюваного зображення, оскільки декодер ДСК абсолютно однозначно відновлює вихідні двійкові послідовності, що з урахуванням відмови від процедури укрупнення пікселів дозволяє уникнути втрат у відновленому зображенні. Визначено, що метод послідовного двоознакового декодування двійкових даних у структурному просторі забезпечує скорочення кількості операцій у порівнянні з методом Хаффмена у середньому на 80 % [3]. На фіг. 1 наведена схема способу стиснення зображень. Описання етапів схеми: 1. Кольорове зображення необхідно перетворити у формат представлення для моделі RGB. Пікселі кожної компоненти формують в блоки 8×8, що називаються сегментами зображення. Якщо число рядків або стовпців вихідного зображення не кратно 8, то верхній рядок і правий крайній стовпець, повторюють потрібну кількість разів. Операції по стисненню проводитимуться з чергуванням колірних компонент: спочатку перший ряд сегментів червоної компоненти, потім перший ряд сегментів зеленої та синьої компонент, далі другий ряд сегментів червоної компоненти, і так далі. Даний етап можна назвати "підготовчим" до загальної процедури стиснення. 2. До кожного сегменту зображення застосовують ДКП. В результаті трансформації матриці зображення на базі ДКП отримують блоки 8×8 частот одиниць даних. Дану процедуру проводять задля збільшення кількості нульових значень в трансформованій матриці. Оскільки пікселі корельовано по двох напрямках, при стисненні використовують двовимірне ДКП, що задають формулою: Gf  30 35 40 1 2n СiC j 7 7   pxy cos( x 0y 0 (2y  1) j (2x  1)i ) cos( ), 16 16  1 , f  0;  Cf   2  1 f  0. , де Тут pxy - числові значення пікселів зображення, що містяться в сегментах розмірністю n x n (в даному випадку n=8). Значення і тa j змінюються в межах від 0 до n-1. Практично значення перетвореного вмісту сегментів 8×8 пікселів обчислюються як добуток Т матриць СРС , де Р - початковий сегмент пікселів 8×8, а матриця С визначається формулами:  1 , i  0;   Cij   8  1 cos( (2 j  1)i ), i  0.  2 16  T С - транспонована матриця С. 3. Кожен з 64 елементів частот одиниць даних ділять на число - коефіцієнт квантування і округляють до цілої частини. На даному етапі відбувається необоротна втрата інформації. Оскільки на даному етапі квантовані сегменти містять від'ємні значення, доцільно сформувати матриці знаків за правилом: 0,  c k.  0; Sk,   1,  c k.  0. Тут Sk, - (k; ) -й матриці знаків, що надає інформацію про знак компоненти c k. . 45 k  1, q ;   1, q , де q ; qc - кількість рядків та стовбців растру зображення відповідно. 4. На цьому етапі застосовують базовий метод стиснення даних - ДСК. Кожен сегмент далі кодують за допомогою методу ДСК. Перш ніж перейти до описання даної ітерації, з'ясовують структуру представлення початкових даних. Початкове зображення розбивають на одиниці даних у вигляді сегментів розмірністю 8×8. Кожне з числових значень представляють у вигляді 8-бітового двійкового числа (тобто кожним сегментом є паралелепіпед, довжина якого становить 8 біт, а ширина і висота дорівнюють розмірності сегмента 8×8). Кожен сегмент 2 UA 75932 U 5 10 15 20 25 30 35 40 складається ніби з восьми шарів. До складу кожного шару входить по 8 стовпців розмірністю 8 біт. На фіг. 2,а зображено принцип просторової структуризації матриці RGB, що містить числові значення колірних компонентів. Ці компоненти формують уявлення про тестове зображення моделлю RGB на прикладі Сегмента1,8 із наведенням змісту кожного з шарів (фіг. 2,б). Завданням даного етапу є формування кода-номера методом ДСК для кожного із стовпців на базі виявлення структурної надмірності з урахуванням структурних ознак сегменту зображення. Таким чином для сегменту формують 8 кодів-номерів для кожного з восьми стовпців восьми шарів зображення. У результаті здійснення даного кроку, кодером формують масив значень кодів-номерів для зображення, а також таблиці параметрів структурних ознак ДСК, що містять значення векторів обмежень на позиції з допустимою появою одиниць і числа серій одиниць в кожній з допустимих зон, які необхідні декодеру для подальшого однозначного декодування даних. 5. На цьому етапі застосовують кодування послідовностей кодів-номерів методом RLE з метою збільшення ступеня стиснення початкового зображення. Цей прийом є досить доцільним, якщо врахувати те, що в результаті попереднього кроку буде сформована велика кількість нульових кодів-номерів. Сканування кодів-номерів будуть проводити для кожного сегменту почергово. Принцип кодування методом RLE полягає її такому: ненульові елементи надходитимуть без змін, а послідовності нулів - кодуються стандартно двома числами, перше з яких - 0 - прапор (позначає початок послідовності нулів), другий - розмір довжини даної послідовності. Також на даному етапі за таким же принципом проводять кодування таблиці, що містить значення числа серій одиниць в кожній з допустимих зон двійкових послідовностей (ДКП), для яких сформовано код-номер та матриці знаків. Сформований спосіб стиснення зображень дозволяє підвищити значення коефіцієнта стиснення kсm в порівняні з відомими методами в 1,3-4,2 разу для більш широких класів джерел повідомлень, що проілюстровано за допомогою діаграми на Фіг. 3. Джерела інформації: 1. Селомон Д. Стиснення даних, зображень і звуку. - М.: Техносфера, 2006.-386 с. 2. Ватолин В.И., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. - М.: ДИАЛОГ - МИФИ, 2002.-384 с. 3. Юдін O.K. Методи структурного кодування даних в автоматизованих системах управління. - К.:НАУ, 2007.-458с. ФОРМУЛА КОРИСНОЇ МОДЕЛІ Спосіб стиснення зображень з урахуванням методу двоознакового структурного кодування, що містить етапи дискретно-косинусного перетворення та квантування, який відрізняється тим, що введено етап формування матриці знаків та введено стиснення методом двоознакового структурного кодування, за яким слідує етап стиснення значень кодів-номерів з використанням методу RLE. 3 UA 75932 U Комп’ютерна верстка І. Мироненко Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 4