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

Спосіб безвтратного кодування та декодування зображень на основі безартефактної моделі, згідно з яким для зображення, записаного в файл растрового формату, задають розмір підмножини випадково вибраних пікселів; здійснюють генера U 1 3 39379 4 клад, двох сусідніх, формують масив помилки між - формують основну модель зображення шляосновною моделлю зображення та висхідним зохом інтерполяції амплітуд кольору на підмножині браженням та кодують цю помилку на основі коду випадково обраних пікселів; Голомба-Райса. Під час формування основної мо- формують масив даних помилки шляхом обделі використовують також методи аналізу струкчислення різниці амплітуд кольору пікселів фізичтури зображення та пошуку та формування конного зображення та пікселів основної моделі; текстної моделі зображення на основі - здійснюють архівування масиву даних поминадлишковості інформації зображення, що усклалки; днює застосування цього способу. При цьому ме- записують у файл масив даних помилки, підтоди формування контекстної моделі зображення множину випадково обраних пікселів, координати не є універсальними для різних типів зображення. випадково обраних пікселів або параметри генеЗа прототип прийнято спосіб кодування та дерації масиву випадково обраних координат піксекодування кольорових зображень без втрат, в лів. якому використовують ентропійне кодування. За Для отримання відновленого зображення здійцим способом формують основну модель зобраснюють декодування даних, кодованих ви щеопиження з амплітуд кольору поточних пікселів шлясаним чином. При цьому виконують наступні дії, хом інтерполяції амплітуд кольору попередньо аналогічні діям при кодуванні в зворотному порядоброблених пікселів при попередньому заданому ку: правилі обходу усі х пікселів у висхідному зобра- розкривають файл зображення та відновлюженні. Далі формують масив даних помилки шляють архівований масив даних помилки; хом обчислення різності між інтерпольованими - формують основну модель зображення шлязначеннями пікселів та значеннями пікселів оригіхом інтерполяції амплітуд кольору на підмножині нального зображення. Потім здійснюють перетвовипадково обраних пікселів, з використанням алрення величини помилки у бінарний вигляд та горитму інтерполяції, який тотожній застосованому здійснюють пошук безперервних серій нульових при кодуванні; значень помилки з наступним частковим їх вида- формують відновлене зображення шляхом ленням. Для ненульових значень помилки, які запідсумовування інтерпольованих амплітуд кольору лишилися, генерують код, який показує кількість з відновленими значеннями помилки. ненульових значень [заявка №WO 2006/010644, В якості додаткових дій, направлених на поопублікована 04.072007р., МПК: H04N1/417]. кращення параметрів вихідного зображення, поВідомі способи кодування та декодування зокращення параметрів «стиснення/якість» при здійбражень мають такий недолік, як залежність коесненні способу кодування та декодування, тощо фіцієнта стискання від структури зображення. Зоможуть здійснювати наступні дії. Ці дії є окремими браження растрової графіки за структурою можна випадками реалізації етапів способу кодування та умовно поділити на деякі підтипи, серед яких видідекодування та ніяким чином не обмежують переляються фотореалістичні зображення та зобраліку дій, який викладено у формулі корисної модеження лінійної графіки, які переважно складаються лі. з ліній різної товщини. Таки підтипи можуть бути Так, наприклад, формування підмножини вичорно-білими або кольоровими, тонованими, пейпадково обраних пікселів можуть здійснювати зажами тощо, тобто такими, що мають різну півтошляхом розбиття вхідного зображення на ідентичнову або лінійну структур у. Також зображення одні елементарні області з суміжними межами, заночасно може мати різні за структурою елементи. вдання єдиного правила обходу пікселів у вищеУ відомих способах кодування та декодування названих елементарних областях та вибору формування основної моделі зображення виконуєдиного піксела в кожній елементарній області з ють на основі рівномірної вибірки пікселів з вхіднокоординатою, яку обирають з попередньо генерого зображення, що збільшує залежності статистиваного масиву випадкових чисел. чного розподілення помилки від структури В якості ідентичних елементарних областей зображення. можуть використовува ти прямокутники. В основу корисної моделі поставлено задачу Додатково можуть задавати правило обходу покращення способу безвтратного кодування та пікселів у елементарних областях, яке полягає в декодування зображень, який би покращення співпослідовному переборі пікселів, що належать до відношення «стиснення/якість» для зображень, що елементарної області, в напрямку зліва направо одночасно містять різні за структурою елементи, та зверху донизу. шляхом формування основної моделі зображення В якості методу інтерполяції при формуванні на основі підмножини випадково обраних пікселів. основної моделі зображення можуть використовуПоставлена задача вирішується таким чином, вати тріангуляцію Делоне. що у способі безвтратного кодування та декодуДодатково можуть здійснювати архівування вання зображень на основі безартефактної модепідмножини випадково обраних пікселів та коорлі, згідно з яким для зображення, записанного в динат випадково обраних пікселів. файл растрового формату, за корисною моделлю: Також можуть здійснювати корекцію координат - задають розмір підмножини випадково обравипадково обраних пікселів, багаторівневе поданних пікселів; ня масиву даних значень помилки або здійснюють - здійснюють генерацію масиву випадково обнелінійне квантування при редукції помилки. раних координат пікселів; В якості параметрів генерації масиву випадко- формують підмножину випадково обраних піво обраних пікселів можуть використовувати пакселів на основі генерованого масиву координат; 5 39379 6 раметр синхронізації генератора випадкових чиВиконання випадкової вибірки за допомогою сел, наприклад, кодове слово. поділу вихідного зображення на ідентичні елеменВ якості параметрів генерації масиву випадкотарні області з суміжними межами, завдання єдиво обраних пікселів можуть використовувати посиного правила обходу пікселів у названих елеменлання на попередньо задану таблицю координат тарних областях та вибору одного піксела у кожній випадково обраних пікселів, розташовану в окреелементарній області з координатою, яку обирамому файлі на матеріальному носії даних. ють з попередньо генерованого масиву випадкоПри декодуванні зображень можуть розкривавих чисел, дозволяє гарантувати, що в кожній ти файл зображення та відновлювати архівований елементарній області буде обрано один піксел та масив даних помилки, підмножину випадково обсередня щільність пікселів з декілька елементарраних пікселів та координати випадково обраних них областей буде близька до середній щільності пікселів. пікселів по всій площині малюнка, а також спросТакож можуть здійснювати обчислення коортити вибір та запам’ятовування координат випаддинат випадково обраних пікселів за допомогою ково відібраних пікселів у файл при кодуванні та синхронізованого генератора випадкових чисел. витяг при декодуванні. У роботі [М. Dippe and E. Додатково можуть здійснювати постфільтраWold. Antialiasing through Stochastic Sampling. In цію відновленого зображення. Computer Graphics (SIGGRAPH ’85 Conference Між сукупністю суттєви х ознак способу безвтProceedings), стор.69-78, 1985] описано, що шляратного кодування та декодування зображень на хом застосування різних засобів стохастичної (виоснові безартефактної моделі, що заявляється, і падкової) дискретизації (вибірки) (розподіл Пуссотехнічним результатом, що досягається, існує нана (стор.71, Фіг. 2, 3 або розпиленої дискретизації ступний причинно-наслідковий зв’язок. (стор. 72, Фіг. 4, 5)) можна регулювати відношення При проведенні досліджень з отримання стис«сигнал/шум» та розподільчу здатність відновлененого відновленого зображення та використовуного зображення. ючи данні роботи, винахідниками з’ясовано, що Інтерполяція амплітуд кольору на підмножині формування основної моделі зображення на основипадково обраних пікселів призначена для обчиві стохастичної вибірки пікселів вхідного зобраслення величин амплітуд кольору решти пікселів, ження в поєднанні з архівуванням масиву даних які складають основну модель зображення. Викопомилки та формуванням файлу для зберігання ристання в якості алгоритму інтерполяції білінійної інформації про зображення, який містить масив інтерполяції на трикутниках (тріангуляції Делоне) даних помилки, підмножину випадково обраних дозволяє отримати розмитості дрібних деталей в пікселів, координат випадково обраних пікселів, основній моделі зображення, що виконує функцію дозволяє отримати основну модель зображення, фільтру, що згладжує. яка не містить артефактів. Під артефактом зобраБагаторівневе кодування дозволяє додатково ження мають на увазі будь-які елементи структури підвищити коефіцієнт стиснення зображення та зображення, які не присутні у вхідному зображенні, оптимізувати швидкість стискання. але присутні у відновленому зображенні, та які Уточнення координат масиву випадково відівиникають, зокрема, в силу перетворення природбраних пікселів дозволяє зменшити величини поного зображення у цифрову форму як результат милки. недотримання умов теореми відліків [теорема УітСпосіб безвтратного кодування та декодувантакера - Найквіста - Котельникова - Шеннона, ня зображень на основі безартефактної моделі джерело - R. Cook, "Stochastic Sampling in Comздійснюють наступним чином. puter Graphics" ACM Transactions on Graphics, Jan. У вхідному цифровому зображенні, яке пред1986, стор.51-72, стор.52, 53]. В свою чергу, ви щеставляє собою в загальному розумінні матрицю вказана основна модель зображення дозволяє [b(i, j)], де і - кількість пікселів у горизонтальному спростити статистичне розподілення помилки при рядку, j - кількість рядків у вхідному зображенні, формуванні масиву даних помилки та, відповідно, задають розмір підмножини випадково вибраних зменшує його залежність від структури зображенпікселів. Розмір підмножини обмежується визнаня. Таким чином, зменшується залежність коефіціченою кількістю пікселів і залежить від розмірів єнту стискання від структури зображення, що довихідного зображення та необхідною точністю відзволяє покращити параметри «стискання/якість» творення відновленого зображення при декодудля зображення, що має різні структурні елементи, ванні. наприклад, півтонові або лінійні. Далі розбивають вихідне зображення на іденВикористання при кодуванні випадкової вибіртичні елементарні області з суміжними межами. В ки пікселів шляхом завдання розміру підмножини якості елементарних областей вибирають, напривипадково обраних пікселів, генерації масиву виклад, прямокутники. Також такими областями мопадково обраних координат пікселів, формування жуть бути будь-які прямокутники з суміжними мепідмножини випадково обраних пікселів на основі жами. Задають єдине правило обходу для кожної генерованого масиву координат, дозволяє уникнуелементарної області, яке полягає в послідовному ти генерації артефактів. Метою застосування стопереборі пікселів, які розташовані усередині елехастичної вибірки пікселів для побудови основної ментарної області, в напрямку зліва направо та моделі зображення є формування такої підмножизверху донизу. Потім здійснюють генерацію коорни пікселів вихідного зображення, яка містить мідинат пікселів в кожній з елементарних областей. німум надлишковості інформації про зображення, На основі з цих координат формують масив випазгідно з вищезгаданою теоремою Уиттакера – дково обраних координат пікселів. Найквиста – Котельникова – Шеннона. 7 39379 8 В кожній з отриманих елементарних областей сивом даних помилки та таким чином отримують обирають піксел за координатами, які отримані відновлене зображення. попередньою генерацію, використовуючи для кожДля підвищення ефективності способу може ної елементарної області єдине визначене правивиконуватися багаторівневе кодування масиву ло обходу, після чого формують підмножину випаданих помилки. Для цього в масиві даних помилки дково обраних пікселів. виконують випадкову вибірку, причому її розмір Далі здійснюють інтерполяцію амплітуд кольозадають більшим ніж розмір підмножини випадкору на підмножині випадково обраних пікселів. В во обраних пікселів. На основі цієї вибірки формуякості методу інтерполяції, наприклад, використоють наступний рівень представлення значень повують інтерполяцію на основі тріангуляції Делоне. милки, тобто підмножину випадкових даних Для цього підмножина випадково обраних пікселів, помилки. З цією множиною також виконують оброяка утворює характеристичну поверхню амплітуди бку за допомогою граничного порогу або нелінійне кольору, розбивається на елементарні трикутники квантування та отримують масив даних помилки, в з суміжними сторонами. Усередині кожного з цих якому багато нульових значень та який краще піделементарних трикутників здійснюють апроксимадається кодуванню. В подальшому можливо, що цію вищевказаної характеристичної поверхні за здійснюють ще випадкову вибірку підмножину видопомогою частини площини. Коефіцієнти а, в, с падкових даних помилки та граничну обробку та рівняння, яке описує площину f(x,y)=a x+b y+c обчиквантування. Кількість таких рівнів масиву даних слюють локально для кожного трикутника шляхом помилки обирають пропорційно розмірам вихідновирішення лінійної системи. Така інтерполяція го зображення та розміру відновленого зображенодночасно має властивості фільтру, який згладжує ня. Таким чином досягають формування такої піддрібні деталі зображення. Також можливе викоримножини випадково обраних пікселів, яка містить стання таких відомих методів просторової інтермінімум надлишковості інформації пікселів. поляції, як метод найближчого сусідства, білінійну, Для подальшого підвищення ефективності кобіквадратичну, бікубічну інтерполяцію, В-сплайн дування здійснюють корекцію координат випадкоінтерполяцію, інтерполяцію Лагранжа тощо. во обраних пікселів після формування масиву даНа основі інтерпольованих пікселів та випадних помилки, наприклад, таким чином. Спочатку в ково обраних пікселів формують основну модель кожній ідентичній елементарній області обирають зображення. Далі обчислюють помилку між ампліодин піксел, відмінний від піксела, який було обратудами кольору пікселів вихідного зображення та но під час формування підмножини випадково обпікселів основної моделі зображення. раних пікселів. Попередньо задають розмір підДля мінімізації помилки здійснюють формумножини випадково обраних пікселів, яка включає вання підмножини відкорельованих випадково в себе декілька ідентичних елементарних обласобраних пікселів на основі підмножини випадково тей, та задають граничне значення помилки для обраних пікселів. такої підмножини випадково обраних пікселів. Далі З отриманих різниць формують масив даних формують підмножину випадково обраних пікселів помилки, який на наступному етапі кодування арз декількох ідентичних елементарних областей. На хівують за допомогою відомих алгоритмів архівації основі цієї підмножини здійснюють аналіз статисданих, наприклад, алгоритму Хаффмана, кодувантики значень помилки по вказаній підмножині шляня серій послідовностей (Run Length Encoding хом побудови гістограми на основі обчислення RLE) тощо. При різновидах реалізації заявленого середньоквадратичного та пікового значень помиспособу також додатково здійснюють архівацію лки та порівняння значення помилки по абсолютпідмножини випадково обраних пікселів та коорній величині з заданим граничним значенням. Далі динат випадково обраних пікселів. визначають ті елементарні області, в яких значенНа останньому етапі записують масив даних ня помилки, які перевищують задану граничну вепомилки, підмножину випадково обраних пікселів, личину, мають максимальну величину, та обиракоординати випадково обраних пікселів у файл, ють в цих областях інші піксели таким чином, що який розташовують у запам’ятовувальному призначення помилки зменшувались. Після цього застрої комп’ютера (наприклад, оперативній пам’яті писують у файл відкориговані координати пікселів комп’ютера, жорсткому диски) або іншому зата масив даних помилки, який сформовано на оспам’ятовувальному пристрої, призначеному для нові відкорегованих пікселів. Варто відмітити, що зберігання файлів. при здійснені корекції координат випадково обраДля декодування і отримання відновленого них пікселів розмір вихідного файлу залишається зображення виконують аналогічні дії в зворотній таким же, як і без здійснення корекції. Таким чипослідовності та використовують такі ж параметри, ном, корекція координат випадково обраних піксеяк і при кодуванні. Так, розкривають файл зобралів служить для звуження статистичного розподіження та розархівовують масив даних помилки, лення значень помилки, що призводить до підмножину випадково обраних пікселів, координапокращення стискання масиву даних помилки при ти випадково обраних пікселів. ЕІісля чого формуархівуванні. ють основну модель зображення шляхом інтерпоЗаявлений спосіб безвтратного кодування та ляції амплітуд кольору на підмножині випадково декодування зображень на основі безартефактної обраних пікселів. Далі виконують підсумовування моделі забезпечує покращення стискання зобрамножини інтерпольованих амплітуд кольору з мажень, які мають різнорідну структур у (півтонову, лінійну то що). 9 Комп’ютерна в ерстка А. Крижанівський 39379 Підписне 10 Тираж 28 прим. Міністерство осв іт и і науки України Держав ний департамент інтелектуальної в ласності, вул. Урицького, 45, м. Київ , МСП, 03680, Україна ДП “Український інститут промислов ої в ласності”, вул. Глазунова, 1, м. Київ – 42, 01601