Преобразуване на вълна: дефиниция, приложение, пример

Появата на евтини цифрови фотоапарати означава, че голяма част от жителите на планетата, независимо от тяхната възраст и пол, е придобил навика да си улови всяка стъпка и поставят своите снимки на обществен показ в социалните мрежи. Освен това, ако преди семейния фотографски архив да бъде поставен в един албум, днес той се състои от стотици снимки. За да се улесни тяхното съхранение и предаване по мрежи, тежестта на цифровото изображение трябва да бъде намалена. За тази цел се прилагат методи, базирани на различни алгоритми, включително wavelet transform. Какво е това, нашата статия ще разкаже.

Какво представлява цифровото изображение?

Визуалната информация в компютъра се представя като числа. По-просто казано, снимка, направена от цифров фотоапарат, е таблица, в която са вписани цветовите стойности на всеки от пикселите. Ако говорим за монохромно изображение, те се заменят с стойностите на яркостта от интервала [0, 1], където 0 се използва за означаване на черен цвят и 1 е бял. Останалите оттенъци се дават с частични числа, но с тях е неудобно да се работи, така че обхватът се разширява и стойностите се избират от интервала между 0 и 255. Защо от това? Това е просто! С този избор, в двоично представяне, се изисква точно 1 байт за кодиране на яркостта на всеки пиксел. Очевидно, съхраняването дори на малко изображение изисква доста памет. Например, размер на снимката от 256 x 256 пиксела ще отнема 8 kB.

Няколко думи за методите за компресиране на изображения

Разбира се, всички виждат картини с лошо качество, където има изкривявания под формата на правоъгълници от един и същи цвят, които обикновено се наричат ​​артефакти. Те възникват в резултат на така наречената загуба на компресия. Тя може значително да намали теглото на изображението, но неизбежно оказва влияние върху качеството му.

Алгоритмите за компресиране на загуби включват:

• JPEG. В момента това е един от най-популярните алгоритми. Тя се основава на прилагането на дискретна косинусна трансформация. В справедливост, трябва да се отбележи, че има варианти на JPEG, които извършват без загуба на компресия. Те включват Lossless JPEG и JPEG-LS.
• JPEG 2000. Алгоритъмът се използва на мобилни платформи и се основава на прилагането на дискретна wavelet трансформация.
• Алгоритъм за фрактална компресия. В някои случаи ви позволява да получавате изображения с отлично качество, дори при силна компресия. Въпреки това, поради проблеми с патентоването, този метод продължава да бъде екзотичен.

Без загуба, компресията се извършва посредством алгоритми:

• RLE (използва се като основен метод във форматите TIFF, BMP, TGA).
• LZW (използва се във формат GIF).
• LZ-Huffman (използва се за PNG формат).

Трансформацията на Фурие

Преди да се обърнат към уейвлет, че има смисъл да проучи свързаните с тях функции, които описват коефициентите на разширяване на първоначалната информация на елементарни компоненти, т.е.. Д. хармонични вибрации с различни честоти. С други думи, трансформацията на Фурие е уникален инструмент, който свързва дискретни и непрекъснати светове.

Това изглежда така:

Формулата за инверсия е написана, както следва:

Какво е wavelet

Зад това име се крие математическа функция, която ви позволява да анализирате различните честотни компоненти на изследваните данни. Графиката му представя вълнообразни трептения, чиято амплитуда намалява до 0, далече от произхода. В общия случай коефициентите на вълните, определени от интегралната трансформация на сигнала, представляват интерес.

Спектрограмите на Wavelet се различават от обикновените спектри на Фурие, тъй като свързват спектъра на различни характеристики на сигнала с техния времеви компонент.

Преобразуване на вълна

Този начин на преобразуване на сигнала (функция) ви позволява да го преведете от времето до представянето на времевата честота.

За да бъде възможна вълновата трансформация, трябва да бъдат изпълнени следните условия за съответната wavelet функция:

• Ако за някаква функция psi- (t) Преобразуванието на Фурие има формата

тогава трябва да бъде изпълнено следното условие:

В допълнение:

• wavelet трябва да има крайна енергия;
• тя трябва да бъде интегрируема, непрекъсната и да има компактен носител;
• Вълната трябва да бъде локализирана както по честота, така и по време (в пространството).

видове

За съответните сигнали се използва непрекъсната wavelet трансформация. Много по-голям интерес представлява неговият отделен аналог. В края на краищата може да се използва за обработка на информация в компютри. Това обаче повдига проблема, че формулите за дискретно DVP не могат да бъдат получени чрез просто вземане на проби от съответните DNP формули.

Решаването на този проблем беше открито от I. Dobesi, който успя да избере метод, който позволява конструирането на серия от такива ортогонални вълни, всяка от които се определя от ограничен брой коефициенти. По-късно бяха създадени бързи алгоритми, например алгоритъмът на Мол. Когато се използва за разлагане или за възстановяване, се изисква да се изпълни редът на cN операции, където N е дължината на пробата и c е броят на коефициентите.

Вайвелет Хар

За да компресирайте изображението, е необходимо да се намери определен модел сред данните, или дори по-добре, ако е дълга верига от нули. Това е мястото, където алгоритъмът на wavelet transforms може да дойде по-удобен. Обаче продължаваме да разглеждаме метода в ред.

Първо трябва да запомните, че снимките на яркостта на съседните пиксели, като правило, се различават с малка сума. Дори ако има области с остри, контрастни разлики в яркостта на реалните изображения, те заемат само малка част от изображението. Като пример, нека вземем добре познатото тестово изображение на Lenna в сивата скала. Ако вземем матрицата на яркостта на нейните пиксели, тогава частта от първата линия ще изглежда като поредица от номера 154, 155, 156, 157, 157, 157, 158, 156.

За да се получат нули, може да се приложи така наречения делта метод. За целта се запазва само първото число, а за останалите се вземат само разликите за всеки номер от предходния с знак "+" или ";".

Резултатът е поредицата: 154,1,1,0,0,1,2.

Недостатъкът на делта кодирането е неговото местоположение. С други думи, е невъзможно да се вземе само част от последователността и да се открият кои яркости са кодирани в нея, ако всички стойности, които пред нея не са декодирани.

За да се преодолее този недостатък, броят е разделена на двойки и всеки са половината от сумата на (об. А) и половината от разликата (об. D), т. Е. За (154,155) (156,157) (157,157) (158,156) има (154.5, 0.5), (156.5.0.5), (157.0.0), (157, -1.0). В този случай по всяко време можете да намерите стойността на двата номера в двойката.

В общия случай за дискретната wavelet трансформация на сигнала S имаме:

Този дискретен метод произтича от непрекъснатия случай на Haar wavelet трансформация и се използва широко в различни области на обработка на информация и компресия.

компресия

Както вече бе споменато, едно от приложенията на вълнов трансформ алгоритъм е метод за компресия JPEG 2000 използване Haar базата на вектора превод на два пиксела в X и Y вектор (X + Y) / 2 и (X - Y) / 2. За тази цел е достатъчно да се умножи оригиналния вектор с матрицата представена по-долу.

Ако има повече точки, вземете по-голяма матрица с диагонални матрици Н. Така оригиналният вектор, независимо от неговата дължина, се обработва по двойки.

филтри

Получените "половин суми" са средните стойности на яркост в двойките пиксели. Тоест, стойностите при преобразуване в изображение трябва да дадат копие от него, намалено с коефициент 2. В този случай половината суми осредняват яркостта, т.е. "филтрират" случайни изблици на техните стойности и играят ролята на честотни филтри.

Сега нека да разгледаме разликите. Те "разпределят" междупикселови "паузи", премахвайки постоянния компонент, т.е. "филтриране" на стойности с ниски честоти.

Дори и от горната трансформация на Haar wavelet за "манекени" става очевидно, че тя е чифт филтри, които разделят сигнала на два компонента: висока честота и ниска честота. За да се получи оригиналният сигнал, е достатъчно просто да се комбинират отново тези компоненти.

пример

Нека да компресираме фотографския портрет (тестовото изображение на Lenna). Помислете за пример за wavelet трансформация на неговата пикселна яркост матрица. Високочестотният компонент на изображението е отговорен за показването на малки детайли и за описването на шума. Що се отнася до ниската честота, тя носи информация за формата на лицето и гладките промени в яркостта.

Особеностите на човешкото възприятие на снимките са такива, че последният компонент е по-важен. Това означава, че по време на компресията определена част от данните с висока честота може да бъде отхвърлена. Освен това тя има по-малки стойности и е кодирана по-компактно.

За да увеличите съотношението на компресия, можете да приложите Haar трансформацията няколко пъти на нискочестотни данни.

Приложение към двумерни масиви

Както вече беше споменато, цифровото изображение в компютъра е представено като матрица на стойностите на интензитета на неговите пиксели. Следователно би трябвало да се интересуваме от трансформацията на двуизмерната wavelet на Haar. За да я приложите, трябва просто да извършите едномерно преобразуване за всеки ред и всяка колона на матрицата на интензитета на пикселите на изображението.

Стойности, близки до нула, могат да бъдат изхвърлени без значително увреждане на декодираната картина. Този процес е известен като квантуване. И на този етап се губи част от информацията. Между другото, броят на нулеви коефициенти може да се промени, като по този начин се коригира съотношението на компресия.

Всички описани действия водят до матрица, която съдържа голям брой 0. Тя трябва да бъде написана по линия до текстов файл и да бъде компресирана от всеки архиватор.

декодиране

Обратната трансформация към изображението се извършва съгласно следния алгоритъм:

• архивът е разопакован;
• се прилага обратната Haar трансформация;
• Декодираната матрица се преобразува в изображение.

Предимства пред JPEG

Когато разглеждате алгоритъма Съвместна група по фотографски експерти се казва, че се основава на DCT. Тази трансформация се извършва блокирано (8 х 8 пиксела). В резултат на това, ако компресията е силна, блоковата структура става забележима върху възстановеното изображение. При компресиране, използвайки wavelets, този проблем отсъства. Възможно е обаче да се появят други видове изкривявания, които приличат на вълни в близост до остри ръбове. Смята се, че такива артефакти са средно по-малко забележими от "квадратите", създадени при прилагането на JPEG алгоритъма.

Сега знаете какво са wavelets, какви са те и какви практически приложения за тях са открити при обработката и компресирането на цифрови изображения.