Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Стиск зображень з використанням дискретних косинусних перетворень.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Електронні обчислювальні машини
Інформація про роботу
Рік:
2003
Тип роботи:
Методичні вказівки до виконання розрахунково-графічної роботи
Предмет:
Проектування комп’ютерних засобів цифрової обробки сигналів та зображень
Частина тексту файла (без зображень, графіків і формул):
Міністерство Освіти і Науки України
Національний Університет “Львівська Політехніка”
Кафедра ЕОМ
Стиск зображень з використанням дискретних косинусних перетворень
Методичні вказівки до розрахунково-графічної роботи (частина 1) з курсу “Проектування комп’ютерних засобів цифрової обробки сигналів та зображень” для студентів спеціальностей
7.091501 і 8.091501 "Комп'ютерні системи та мережі"
7.091503 і 8.091503 “Спеціалізовані комп'ютерні системи“
Затверджено на засіданні кафедри ”Електронних обчислювальних машин” Протокол № 9 від 17 квітня 2003 року
Львів – 2003
Стиск зображень з використанням дискретних косинусних перетворень :
Методичні вказівки до розрахунково-графічної роботи (частина 1) з курсу “Проектування комп’ютерних засобів цифрової обробки сигналів та зображень” для студентів спеціальностей 7.091501 і 8.091501 "Комп'ютерні системи та мережі", 7.091503 і 8.091503 “Спеціалізовані комп'ютерні системи“ / Укладачі: Є. Ваврук, Р. Попович – Львів: Національний університет “Львівська політехніка”, 2003, 11 с.
Укладачі: Є. Ваврук, к.т.н., ст.викл.
Р. Попович, к.т.н., доцент
Відповідальний за випуск: Мельник А. О., професор, завідувач кафедри
Рецензенти: Пуйда В.Я., к. т. н, доцент
Троценко В.В., к. т. н, доцент
Мета роботи
Опрацювати та випробувати в середовищі MATLAB 6.0 програму, яка реалізує етапи стиску зображень з використанням дискретного косинусного перетворення.
Теоретичне підґрунтя
Безвтратні методи стиску (кодування Хафмена, LZW, довжин серій) не забезпечують потрібного у багатьох випадках степеня стиску зображень. Необхідно застосовувати методи стиску з втратою інформації. Один з таких підходів використовується у форматах стиску зображень JPEG.
Стиск даних у форматі JPEG (Joint Photographic Experts Group), який дозволяє стискати окремі (незмінні, still picture) зображення, можна умовно розбити на три етапи:
1-й етап - перетворення та субдискретизація кольорової інформації.
2-й етап – поблочні дискретні косинусні перетворення.
3-й етап – квантування та кодування значень дискретного косинусного перетворення.
Перший етап - це перетворення та субдискретизація кольорової інформації. Він полягає в наступному.
Кожна точка зображення, представлена 3 байтами в системі RGB, переводиться в систему YUV (яскравість, кольорова насиченість, кольоровий тон) згідно виразів:
Y=27/256*R+150/256*G+29/256*B
U=131/256*R-110/256*G-21/256*B+128
V= -44/256*R-87/256*G+131/256*B+128
або в матричному вигляді
EMBED Equation.3
Перетворення з системи YUV в систему RGB виконується за формулами:
R=Y+1.37*(U_128)
G=Y-0.698*(U-128)-0.336*(V-128)
B=Y+1.73*(V-128)
або в матричному вигляді
EMBED Equation.3
Далі значення компоненти Y залишаються без зміни, а число значень компонент U і V зменшується (так звана субдискретизація; компоненти U і V можна загрубити без суттєвої втрати якості зображення). Можливі різні варіанти субдискретизації: просте викидання частини з сусідніх точок чи заміна значень сусідніх точок зображення на їх середні. При цьому можливі кілька варіантів об'єднання точок: дві по горизонталі, дві по вертикалі, квадрат з чотирьох сусідніх точок. Найчастіше використовується наступний варіант: число точок зменшується вдвоє, причому значення точок обчислюються згідно з виразом
y(n)=1/4*x(n-2)+1/2*x(n-1)+1/4*x(n).
При цьому блок 8Х16 значень компоненти U або V перетворюється в блок 8Х8 значень.
При відтворенні інформації для покращення якості проміжні точки рекомендується отримувати не простим повторенням, а шляхом інтерполяції між сусідніми точками. Найчастіше використовується наступний спосіб: при відтворенні зображення блок 8Х8 точок реконструюється в блок 8Х16 точок за формулою
x(n)=[y(2n)+y(2n-1)]/2.
Якщо використовується описаний варіант субдискретизації, то досягається стиск зображення в 1,5 раза. Дійсно 1 байт компоненти яскравості залишається без змін, а кожні 2 байти компонент U і V заміняються на 1 байт. Отже, замість 6 байт на кожних 2 точки зображення тепер припадає 4 байта. Якщо використовується варіант об'єднання чотирьох сусідніх точок, то досягається стиск зображення в 2 рази. Адже 1 байт компоненти яскравості залишається без змін, а кожні 4 байти компонент U і V заміняються на 1 байт. Тобто, замість 12 байт на кожних 4 точки зображення тепер припадає 6 байт.
Мінімальний фрагмент інформації (MCU) для обробки – це блок початкового RGB зображення розміру 8Х16 елементів. У результаті обробки такого фрагменту на першому етапі отримуємо чотири блоки розміру 8Х8: два блоки розміру 8Х8 для компоненти яскравості Y та по одному блоку розміру 8Х8 для компонент U і V. Це ілюструється наступним рисунком.
EMBED Word.Picture.8
Другий етап має в своїй основі дискретне косинусне перетворення (ДКП).
Кожна з компонент Y,U,V зображення на цьому етапі розглядається як окреме монохромне (однокольорове) зображення і її стиск проводиться окремо.
Зображення розбивається на блоки 8Х8 елементів. До кожного блоку P застосовується двовимірне ДКП
PДКП=APAT,
де А - матриця двовимірного ДКП;
PДКП - матриця значень ДКП фрагменту зображення.
Пряме ДКП задається наступним виразом
а обернене ДКП задається формулою
де EMBED Equation.3 для i=0 та c(i)=1 для i=1,2,…,7.
Двовимірне ДКП має ту властивість, що воно зосереджує найбільші значення у верхньому лівому куті матриці перетворення. Типовий розподіл ДКП коефіцієнтів показано в наступній матриці:
EMBED Equation.3
Ці значення треба взяти більш точно, а решта значень ДКП можна суттєво загрубити. Це і є основою стиску зображень у форматі JPEG. Дії, які реалізують описану ідею, відбуваються на наступному третьому етапі.
На третьому етапі виконуються квантування та кодування значень дискретного косинусного перетворення.
Спочатку виконується квантування значень ДКП. Для цього формується матриця Q дільників з елементами q(i,j)=1+(1+i+j)r,i,j=0,1,…,7; r- параметр, який впливає на якість зображення, що отримуємо при відтворенні. Для компонент Y рекомендується брати r=2, а для компонент U,V значення r може бути більшим. q(i,j) це не що інше як крок квантування, який залежно від позиції змінюється. При русі від верхнього лівого кута до правого нижнього кута крок квантування збільшується, тобто виконується грубіше квантування.
При r=2 матриця дільників має вигляд
EMBED Equation.3
Значення x(i,j) матриці PДКП діляться на відповідні значення q(i,j) матриці дільників і заокруглються до найближчого цілого. Процес квантування описується наступним виразом:
Q(x(i,j),i,j)=round(x(i,j)/q(i,j)).
Приклад, як виглядає матриця ДКП після квантування значень, наведено нижче:
EMBED Equation.3
До коефіцієнтів ДКП, які знаходяться на першому місці (DC коефіцієнти), застосовується дельта імпульсно-кодова модуляція:
DC(-1)=0; del(0)=0; del(n)=DC(n)-DC(n-1)
До коефіцієнтів, які знаходяться на місцях крім першого (AC коефіцієнти), застосовується описане нижче кодування.
Останнім кроком є застосування до елементів отриманої матриці кодування Хафмена разом з кодуванням довжин серій для послідовностей нулів. Вважається, що поява нульового елемента у даній матриці є найбільш імовірною, а із збільшенням абсолютної величини елемента ймовірність його появи зменшується. Один з варіантів таблиці кодування виглядає наступним чином.
Таблиця кодування може фіксуватися перед початком обробки або бути адаптивною, тобто мінятися з використанням статистики появи даних у попередніх блоках.
Кодування матриці квантованих елементів ДКП проводиться по шляху, показаному послідовними номерами (так званий зигзаг або змійка; у напрямку збільшення значень елементів матриці дільників).
EMBED Equation.3
Результатом кодування є послідовність кодових слів коду Хафмена. Відомо, що ніякі два слова в цьому коді не мають однакового початку, тобто слова в послідовності можуть іти підряд без маркерів розділення.
Певні маркери мають бути лише для того, щоб вказати, де починається послідовність кодових слів, отриманих при обробці блоку 8Х8 елементів.
Замість застосування коду Хафмена стандарт допускає також використання безвтратних арифметичних кодів.
При відтворенні зображення виконуються наступні дії, зворотні до дій при стиску:
- декодування Хафмена;
- деквантування (множення на відповідні значення елементів матриці дільників);
- обернені двовимірні ДКП блоків 8Х8 елементів;
- обернена кольорова субдискретизація (відтворення проміжних точок для компонент U,V шляхом інтерполяції між сусідніми точками);
-перехід від системи YUV до системи RGB.
Етапи стиску та відтворення даних при використанні формату JPEG показані на рисунку.
YUV
Субдискре-
тизація
Прямі
ДКП
Кванту-вання
Коду-
вання
Стиснуті дані JPEG
Обернені ДКП
Декван-тування
Декоду-вання
RGB
Обернена субдискре-тизація
Відтво-рення кольорів
Степінь стиску в форматі JPEG - від 16:1 до 25:1 без помітної втрати якості.
Зразок програми на мові сценаріїв MATLAB 6.0
Далі наведено зразок програми на мові сценаріїв MATLAB 6.0, яка реалізує описані вище етапи 1-3 стиску зображень.
clear all;
imshow source.tif;
im_rgb=imread('source.tif');
info='Started JPEG compression'
% RGB to YUV
info='RGB to YUV...'
a_rgb=double(im_rgb(1:400,1:496,1:3));
a_y=round(77/256*a_rgb(1:400,1:496,1)+150/256*a_rgb(1:400,1:496,2)+29/256*a_rgb(1:400,1:496,3));
a_u=round(131/256*a_rgb(1:400,1:496,1)-110/256*a_rgb(1:400,1:496,2)-21/256*a_rgb(1:400,1:496,3)+128);
a_v=round(-44/256*a_rgb(1:400,1:496,1)-87/256*a_rgb(1:400,1:496,2)+131/256*a_rgb(1:400,1:496,3)+128);
%info='finished'
% downsampling
info='downsampling U,V...'
a_u_ds(1:400,1)=a_u(1:400,1);
a_v_ds(1:400,1)=a_v(1:400,1);
for j=1:400
for i=2:248
a_u_ds(j,i)=round(a_u(j,2*i-2)/4+a_u(j,2*i-1)/2+a_u(j,2*i)/4);
a_v_ds(j,i)=round(a_v(j,2*i-2)/4+a_v(j,2*i-1)/2+a_v(j,2*i)/4);
end;
end;
clear a_u a_v
%info='finished'
%dct
info='2-D Discrete Cosine Transform ...'
y_dct=blkproc(a_y,[8,8],'dct2');
u_dct=blkproc(a_u_ds,[8,8],'dct2');
v_dct=blkproc(a_v_ds,[8,8],'dct2');
clear a_u_ds a_v_ds
%info='finished'
%quantization
info='quantization ...'
r=3;
for i=1:8
for j=1:8
kvant(i,j)=1+(i+j-1)*r;
end;
end;
for j=1:50
for i=1:62
y_kv(8*j-7:8*j,8*i-7:8*i)=round(y_dct(8*j-7:8*j,8*i-7:8*i)./kvant);
end;
end;
for j=1:50
for i=1:31
u_kv(8*j-7:8*j,8*i-7:8*i)=round(u_dct(8*j-7:8*j,8*i-7:8*i)./kvant);
v_kv(8*j-7:8*j,8*i-7:8*i)=round(v_dct(8*j-7:8*j,8*i-7:8*i)./kvant);
end;
end;
clear fuctions;
clear y_dct u_dct v_dct;
%info='finished'
%Differencial pulse-code modulation (DPCM) coding and runlength coding
info='Zigzag Ordering Y ...'
for j=1:50
for i=1:62
y_mas((j-1)*62+i,1:64)=zigzag(y_kv(8*j-7:8*j,8*i-7:8*i));
end;
end;
info='Zigzag Ordering U,V ...'
for j=1:50
for i=1:31
u_mas((j-1)*31+i,1:64)=zigzag(u_kv(8*j-7:8*j,8*i-7:8*i));
v_mas((j-1)*31+i,1:64)=zigzag(v_kv(8*j-7:8*j,8*i-7:8*i));
end;
end;
clear fuctions;
info='Coding Y (DPCM & RunLength) ...'
x_y=0;midle=[];
for i=1:3100
y_cod=[midle y_mas(i,1)-x_y runcode(y_mas(i,2:64))];
x_y=y_mas(i,1);
midle=y_cod;
end;
clear functions;
info='Coding U,V (DPCM & RunLength)'
x_u=0;x_v=0;midle_u=[];midle_v=[];
for i=1:1550
u_cod=[midle_u u_mas(i,1)-x_u runcode(u_mas(i,2:64))];
x_u=u_mas(i,1);
midle_u=u_cod;
v_cod=[midle_v v_mas(i,1)-x_v runcode(v_mas(i,2:64))];
x_v=v_mas(i,1);
midle_v=v_cod;
end;
clear y_kv u_kv v_kv;
clear functions;
info='Huffman coding Y ...'
m_y=0;
for i=1:length(y_cod)
m_y=m_y+huffman(y_cod(i));
end;
clear functions;
info='Huffman coding U,V ...'
m_u=0;
for i=1:length(u_cod)
m_u=m_u+huffman(u_cod(i));
end;
clear functions;
m_v=0;
for i=1:length(v_cod)
m_v=m_v+huffman(v_cod(i));
end;
clear functions;
%info='finished coding'
info='Finished JPEG Compression'
m=size(im_rgb);
compression_ratio=8*m(1)*m(2)*m(3)/(m_y+m_u+m_v);
%clear m m_y m_u m_v
compression_ratio
imshow source.tif;
%clear all;
function [res]=zigzag(x)
res=[x(1,1) x(1,2) x(2,1) x(3,1) x(2,2) x(1,3) x(1,4) x(2,3) x(3,2) x(4,1) x(5,1) x(4,2) x(3,3) x(2,4) x(1,5) x(1,6) x(2,5) x(3,4) x(4,3) x(5,2) x(6,1) x(7,1) x(6,2) x(5,3) x(4,4) x(3,5) x(2,6) x(1,7) x(1,8) x(2,7) x(3,6) x(4,5) x(5,4) x(6,3) x(7,2) x(8,1) x(8,2) x(7,3) x(6,4) x(5,5) x(4,6) x(3,7) x(2,8) x(3,8) x(4,7) x(5,6) x(6,5) x(7,4) x(8,3) x(8,4) x(7,5) x(6,6) x(5,7) x(4,8) x(5,8) x(6,7) x(7,6) x(8,5) x(8,6) x(7,7) x(6,8) x(7,8) x(8,7) x(8,8)];
function [res]=runcode(vect)
n=0;res=[];
for i=1:63
if vect(i)==0
n=n+1;
else
res=[res n vect(i)];
n=0;
end;
end;
res=[res 0 0];
function kod=huffman(elem)
switch elem
case 0, kod=1; % kode word=1
case 1, kod=4; % kode word=0100
case -1, kod=4; % kode word=0101
case 2, kod=4; % kode word=0110
case -2, kod=4; % kode word=0111
case 3, kod=5; % kode word=00100
case -3, kod=5; % kode word=00101
case 4, kod=5; % kode word=00110
case -4, kod=5; % kode word=00111
case 5, kod=7; % kode word=0001000
case -5, kod=7; % kode word=0001001
case 6, kod=7; % kode word=0001010
case -6, kod=7; % kode word=0001011
case 7, kod=7; % kode word=0001100
case -7, kod=7; % kode word=0001101
case 8, kod=7; % kode word=0001110
case -8, kod=7; % kode word=0001111
otherwise kod=13; % kode word=00001+elem(8 bits)
end;
Типове зображення, яке обробляємо – файл зображення з розширенням tiff.
Зміст звіту до розрахунково-графічної роботи
1.Мета роботи.
2. Основні теоретичні відомості.
3. Блок-схема алгоритму стиску.
4. Результат виконання індивідуального завдання
а) скоректована програма на мові сценаріїв MATLAB 6.0, яка реалізує етапи стиску зображень з використанням дискретного косинусного перетворення;
б) потік бітів, які є результатом опрацювання заданого викладачем зображення;
в) оцінка степеня стиску зображення.
5. Висновок.
ЛІТЕРАТУРА
Бабак В.П., Хандецький А.І., Шрюфер Е. Обробка сигналів: підручник для вузів., К., Либідь, 1996.- 390с.
Бондарев В.Н., Трестер Г., Чернега В.С. Цифровая обработка сигналов: методы и средства. - Харьков: Конус, 2001 (підручник для вузів).
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора