Пользователь
0,1
рейтинг
10 февраля 2013 в 19:51

Разработка → Вейвлет-сжатие «на пальцах» tutorial

Введение





Вейвлеты сейчас на слуху. Даже неискушённые в математике люди наверняка слышали, что с их помощью удаётся сжимать изображения и видео сохраняя приемлемое качество. Но что же такое вейвлет? Википедия отвечает на этот вопрос целым ворохом формул за которыми не так-то легко увидеть суть.

Попробуем на простых примерах разобраться, откуда же вообще берутся вейвлеты и как их можно использовать при сжатии. Предполагается, что читатель знаком с основами линейной алгебры, не боится слов вектор и матрица, а также умеет их перемножать.



Сжатие изображений



Упрощённо, изображение представляют собой таблицу, в ячейках которой хранятся цвета каждого пикселя. Если мы работаем с чёрно-белым (или, точнее, серым) изображением, то вместо цвета в ячейки помещают значения яркости из отрезка [0, 1]. При этом 0 соответствует чёрному цвету, 1 — белому. Но с дробями работать неудобно, поэтому часто значения яркости берут целыми из диапазона от 0 до 255. Тогда каждое значение будет занимать ровно 1 байт.

Даже небольшие изображения требуют много памяти для хранения. Так, если мы кодируем яркость каждого пикселя одним байтом, то изображение одного кадра формата FullHD (1920×1080) займёт почти два мегабайта. Представьте, сколько памяти потребуется для хранения полуторачасового фильма!

Поэтому изображения стремятся сжать. То есть закодировать таким образом, чтобы памяти для хранения требовалось меньше. А во время просмотра мы декодируем записанные в память данные и получаем исходный кадр. Но это лишь в идеале.

Существует много алгоритмов сжатия данных. О их количестве можно судить по форматам, поддерживаемым современными архиваторами: ZIP, 7Z, RAR, ACE, GZIP, HA, BZ2 и так далее. Неудивительно, что благодаря активной работе учёных и программистов в настоящее время степень сжатия данных вплотную подошла к теоретическому пределу.

Плохая новость в том, что для изображения этот теоретический предел не так уж и велик. Попробуйте сохранить фотографию (особенно с большим количеством мелких деталей) в формате PNG — размер получившегося файла может вас расстроить.

Это происходит из-за того, что в изображениях из реального мира (фотографиях, например) значения яркости редко бывают одинаковыми даже у соседних пикселей. Всегда есть мельчайшие колебания, которые неуловимы человеческим глазом, но которые алгоритм сжатия честно пытается учесть.

Алгоритмы сжатия «любят», когда в данных есть закономерность. Лучше всего сжимаются длинные последовательности нулей (закономерность тут очевидна). В самом деле, вместо того, чтобы записывать в память 100 нулей, можно записать просто число 100 (конечно, с пометкой, что это именно количество нулей). Декодирующая программа «поймёт», что имелись в виду нули и воспроизведёт их.

Однако если в нашей последовательности в середине вдруг окажется единица, то одним числом 100 ограничится не удастся.

Но зачем кодировать абсолютно все детали? Ведь когда мы смотрим на фотографию, нам важен общий рисунок, а незначительные колебания яркости мы и не заметим. А значит, при кодировании мы можем немного изменить изображение так, чтобы оно хорошо кодировалось. При этом степень сжатия сразу вырастет. Правда, декодированное изображение будет незначительно отличаться от исходного, но кто заметит?

Преобразование Хаара



Итак, наша цель — преобразовать изображение так, чтобы оно хорошо сжималось классическими алгоритмами. Подумаем, как нужно изменить его, чтобы получить длинные цепочки нулей.

У «реальных» изображений, таких как фотографии, есть одна особенность — яркость соседних пикселей обычно отличается на небольшую величину. В самом деле, в мире редко можно увидеть резкие, контрастные перепады яркости. А если они и есть, то занимают лишь малую часть изображения.

Рассмотрим фрагмент первой строки яркостей из известного изображения «Lenna» (на рисунке).

154,  155,  156,  157,  157,  157,  158,  156


Видно, что соседние числа очень близки. Чтобы получить желаемые нули или хотя бы что-то близкое к ним, можно закодировать отдельно первое число, а потом рассматривать лишь отличия каждого числа от предыдущего.

Получаем:

154, 1, 1, 1, 0, 0, 1, -2.


Уже лучше! Такой метод в самом деле используется и называется дельта-кодированием. Но у него есть серьёзные недостаток — он нелокальный. То есть нельзя взять кусочек последовательности и узнать, какие именно яркости в нём закодированы без декодирования всех значений перед этим кусочком.

Попробуем поступить иначе. Не будем пытаться сразу получить хорошую последовательность, попробуем улучшить её хотя бы немного.

Для этого разобьём все числа на пары и найдём полусуммы и полуразности значений в каждой из них.

(154,  155),  (156,  157),  (157,  157),  (158,  156)

(154.5,  0.5),  (156.5,  0.5),  (157,  0.0),  (157,  -1.0)


Почему именно полусуммы и полуразности? А всё очень просто! Полусумма — это среднее значение яркости пары пикселей. А полуразность несёт в себе информацию об отличиях между значениями в паре. Очевидно, зная полусумму a и полуразность d можно найти и сами значения:
первое значение в паре = a — d,
второе значение в паре = a + d.

Это преобразование было предложено в 1909 году Альфредом Хааром и носит его имя.

А где же сжатие?



Полученные числа можно перегруппировать по принципу «мухи отдельно, котлеты отдельно», разделив полусуммы и полуразности:

154.5, 156.5, 157, 157; 0.5, 0.5, 0.0, -1.0.


Числа во второй половине последовательности как правило будут небольшими (то, что они не целые, пусть пока не смущает). Почему так?

Как мы уже выяснили раньше, в реальных изображениях соседние пиксели редко отличаются друг от друга значительно. Если значение одного велико, то и другого велико. В таких случаях говорят, что соседние пиксели коррелированы.

В самом деле, рассмотрим первые 2000 пар соседних пикселей и каждую пару представим на графике точкой.



Все точки выстраиваются вдоль одной прямой линии. И так практически во всех реальных изображениях. Верхний левый и нижний правый углы изображения практически всегда пусты.

А теперь рассмотрим график, точками в котором будут полусуммы и полуразности.



Видно, что полуразности находятся в гораздо более узком диапазоне значений. А это значит, что на них можно потратить меньше одного байта. Какое-никакое, а сжатие.

Применим математику!



Попробуем записать математические выражения, описывающие преобразование Хаара.

Итак, у нас была пара пикселей (вектор) , а мы хотим получить пару .

Такое преобразование описывается матрицей .

В самом деле , что нам и требовалось.

Внимательный читатель наверняка заметил, что рисунки из точек на двух последних графиках одинаковы. Разница лишь в повороте на угол в 45°.

В математике повороты и растяжения называются аффинными преобразованиями и описываются как раз при помощи умножения матрицы на вектор. Что мы и получили выше. То есть, преобразование Хаара — это просто поворот точек таким образом, чтобы их можно было удобно и компактно закодировать.

Правда, тут есть один нюанс. При аффинных преобразованиях может меняться площадь фигуры. Не то, чтобы это было плохо, но как-то неаккуратненько. Как известно, коэффициент изменения площади равен определителю матрицы. Посмотрим, каков он для преобразования Хаара.



Для того, чтобы определитель стал равен единице достаточно умножить каждый элемент матрицы на . На угол поворота (а значит, и на «сжимающую способность» преобразования) это не повлияет.

Получаем в итоге матрицу



А как декодировать?



Как известно, если у матрицы определитель не равен нулю, то для неё существует обратная матрица, «отменяющая» её действие. Если мы найдём обратную матрицу для H, то декодирование будет заключаться просто в умножении векторов с полусуммами и полуразностями на неё.



Вообще говоря, поиск обратной матрицы — не такая простая задача. Но, может, удастся как-то эту задачу упростить?

Рассмотрим поближе нашу матрицу. Она состоит из двух вектор-строк: и . Назовём их v1 и v2.

Они обладают интересными свойствами.

Во-первых, их длины равны 1, то есть . Здесь буква T означает транспонирование. Умножение вектор-строки на транспонированный вектор-строку — это скалярное произведение.

Во-вторых, они ортогональны, то есть .

Матрица, строки которой обладают указанными свойствами называется ортогональной. Чрезвычайно важным свойством таких матриц является то, что обратную матрицу для них можно получить простым транспонированием.



В справедливости этого выражения можно убедиться умножив H обратную матрицу. На диагонали мы получим скалярные произведения вектор-строк на самих себя, то есть 1. А вне диагоналей — скалярные произведения вектор-строк друг на друга, то есть 0. В итоге произведение будет равно единичной матрице.

Мы любим ортогональные матрицы!

Увеличиваем число точек



Всё сказанное хорошо работает для двух точек. Но что делать, если точек больше?

В этом случае тоже можно описать преобразование матрицей, но большей по размеру. Диагональ этой матрицы будет состоять из матриц H, таким образом в векторе исходных значений будут выбираться пары, к которым независимо будет применяться преобразование Хаара.



То есть. исходный вектор просто обрабатывается независимо по парам.

Фильтры



Итак, когда мы знаем, как выполнять преобразование Хаара, попробуем разобраться с тем, что же оно нам даёт.

Полученные «полусуммы» (из-за того, что делим не на 2, приходится использовать кавычки) — это, как мы уже выяснили, средние значения в парах пикселей. То есть, фактически, значения полусумм — это уменьшенная копия исходного изображения! Уменьшенная потому, что полусумм в два раза меньше, чем исходных пикселей.

Но что такое разности?

Полусуммы усредняют значения яркостей, то есть «отфильтровывают» случайные всплески значений. Можно считать, что это некоторый частотный фильтр.

Аналогично, разности «выделяют» среди значений межпиксельные «всплески» и устраняют константную составляющую. То есть, они «отфильтровывают» низкие частоты.

Таким образом, преобразование Хаара — это пара фильтров, разделяющих сигнал на низкочастотную и высокочастотную составляющие. Чтобы получить исходный сигнал, нужно просто снова объединить эти составляющие.

Что нам это даёт? Пусть у нас есть фотография-портрет. Низкочастотная составляющая несёт в себе информацию об общей форме лица, о плавных перепадах яркости. Высокочастотная — это шум и мелкие детали.

Обычно, когда мы смотрим на портрет, нас больше интересует низкочастотная составляющая, а значит при сжатии часть высокочастотных данных можно отбросить. Тем более, что, как мы выяснили, она обычно имеет меньшие значения, а значит более компактно кодируется.

Степень сжатия можно увеличить, применяя преобразование Хаара многократно. В самом деле, высокочастотная составляющая — это всего лишь половина от всего набора чисел. Но что мешает применить нашу процедуру ещё раз к низкочастотным данным? После повторного применения, высокачастотная информация будет занимать уже 75%.

Хоть мы пока и говорили об одномерных цепочках чисел, этот подход хорошо применим и для двумерных данных. Чтобы выполнить двумерное преобразование Хаара (или аналогичное ему), нужно лишь выполнить его для каждой строки и для каждого столбца.

После многократного применения к, например, фотографии замка Лихтенштейн, получим следующий рисунок.



Черные области соответствуют низкой яркости, то есть значениям, близким к нулю. Как показывает практика, если значение достаточно мало, то его можно округлить или вообще обнулить без особого ущерба для декодированного рисунка.

Этот процесс называется квантованием. И именно на этом этапе происходит потеря части информации. (К слову, такой же подход используется в JPEG, только там вместо преобразования Хаара используется дискретное косинус-преобразование.) Меняя число обнуляемых коэффициентов, можно регулировать степень сжатия!

Конечно, если обнулить слишком много, то искажения станут видны на глаз. Во всём нужна мера!

После всех этих действий у нас останется матрица, содержащая много нулей. Её можно записать построчно в файл и сжать каким-то архиватором. Например, тем же 7Z. Результат будет неплох.

Декодирование производится в обратном порядке: распаковывем архив, применяем обратное преобразование Хаара и записываем декодированную картинку в файл. Вуаля!

Где эффективно преобразование Хаара?



Когда преобразование Хаара будет давать наилучший результат? Очевидно, когда мы получим много нулей, то есть, когда изображение содержит длинные участки одинаковых значений яркости. Тогда все разности обнулятся. Это может быть, например, рентгеновский снимок, отсканированный документ.

Говорят, что преобразование Хаара устраняет константную составляющую (она же — момент нулевого порядка), то есть переводит константы в нули.

Но всё же в реальных фотографиях областей с одинаковой яркостью не так много. Попробуем усоврешенствовать преобразование, чтобы оно обнуляло ещё и линейную составляющую. Иными словами, если значения яркости будут увеличивать линейно, то они тоже обнулятся.

Эту задачу и более сложные (устранение моментов более высоких порядков) решила Ингрид Добеши — один из создателей теории вейвлетов.

Преобразование Добеши



Для нашего усовершенствованного преобразования уже будет мало двух точек. Поэтому будем брать по четыре значения, смещаясь каждый раз на два.

То есть, если исходная последовательность — 1, 2, 3, 4, 5, 6,…, N-1, N, то будем брать четвёрки (1, 2, 3, 4), (3, 4, 5, 6) и т. д. Последняя четвёрка «кусает последовательность за хвост»: (N-1, N, 1, 2).

Точно так же попробуем построить два фильтра: высокочастотный и низкочастотный. Каждую четвёрку будем заменять на два числа. Так как четвёрки перекрываются, то количество значений после преобразования не изменится.

Для того, чтобы было удобно считать обратную матрицу потребуем также ортогональности преобразования. Тогда поиск обратной матрицы сведётся к транспонированию

Пусть значения яркостей в четвёрке равны x, y, z, t. Тогда первый фильтр запишем в виде



Четыре коэффициента, образующих вектор-строку матрицы преобразования, пока нам неизвестны.

Чтобы вектор-строка коэффициентов второго фильтра был ортогонален первому, возьмём те же коэффициенты но переставим их и поменяем знаки:



Матрица преобразования будет иметь вид.



Требование ортогональности выполняется для первой и второй строк автоматически. Потребуем, чтобы строки 1 и 3 тоже были ортогональны:



Векторы должны иметь единичную длину (иначе определитель будет не единичным):



Преобразование должно обнулять цепочку одинаковых значений (например, (1, 1, 1, 1)):



Преобразование должно обнулять цепочку линейно растущих значений (например, (1, 2, 3, 4)):



Кстати, если обнуляется эта четвёрка, то будут обнуляться и любые другие линейно растущие или линейно убывающие. В этом легко убедиться, записав соответствующее уравнение и разделив все коэффициенты на первый множитель.

Получили 4 уравнения, связывающие коэффициенты. Решая их, получаем:



Подставив их в матрицу, получаем искомое преобразования. После его применения к фотографиям получим больше нулей и малых коэффициентов, что позволит сжать изображение сильнее.

Другая приятная особенность — артефакты после квантования будут не так заметны.

Это преобразование получило название вейвлета D4 (читателю предлагается самостоятельно разгадать тайну этого буквенно-цифрового названия).

Другие вейвлеты



Мы, конечно, можем не остановиться на этом, и потребовать устранения параболической составляющей (момент 2-го порядка) и так далее. В результате получим вейвлеты D6, D8 и другие.

Чтобы не считать всё вручную, коэффициенты можно посмотреть в википедии.

Добеши открыла весьма интересный способ получения коэффициентов этих преобразований, но увы, это уже выходит за рамки нашей статьи.

Домашнее задание



Чтобы окончательно разобраться с основами, предлагаю написать на вашем любимом языке программу, которая открывает изображение, выполняет преобразование Хаара (или даже D4), квантует результат, а потом сохраняет результат в файл. Попробуйте сжать этот файл своим любимым архиватором. Хорошо сжимается?

Попробуйте выполнить обратное преобразование. Как вы объясните характер артефактов на изображении?

Заключение


Итак, мы кратко рассмотрели основные идеи дискретного вейвлет-преобразования.

Конечно, в этой статье не были рассмотрены очень многие интересные математические детали и практические применения вейвлет-преобразований. Но нельзя объять необъятное. Да и многое сложно объяснить не повышая градус матана. Надеюсь, что и написанное оказалось кому-то полезным.

Спасибо за внимание!

Продолжение: Вейвлет-сжатие «на пальцах»: практика.

Литература


Есть много довольно неплохих книжек, которые дают более глубокое представление о вейвлетах. Начать рекомендую со следующих:
  1. Уэлстид С. Фракталы и вейвлеты для сжатия изображений в действии. — М.: Триумф, 2003.
  2. Штарк Г.-Г. Применение вейвлетов для ЦОС. — М.: Техносфера, 2007.
masai @masai
карма
83,5
рейтинг 0,1
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (56)

  • +3
    Можно пару вопросов, а то у меня в голове не уложилось до конца:

    1. В случае использования преобразования Хоара, если отбрасывается вся высокочастотная составляющая, то чем это приобразование лучше обычного подобия blur фильтра, или просто говоря, сжатия, которое уменьшает разрешение по X в 2 раза? Или я пропустил, и часть высокочастотной составляющей остает?

    2. Ну и хотелось бы немного больше акцента, на то, чем оно принципиально отличается от преобразования Фурье, и как частного случая — cosine transform? Ведь cosine transform это тоже по сути, разлжение картинки на различные частотные составляющие, с последующим откидыванием наиболее высоких частот, и квантованием тех, которые оставлены. При этом «частот» используется куда больше — матрица 8x8. Расскажите, чем описанные вами алгоритмы лучше, пожалуйста. (Сам я не сильно глубоко знаком с этой темой).
    • 0
      Говоря про cosine transform — я забыл сказать, что имею в виду, как оно используется в JPEG, а не вообще.
    • +8
      1. Если отбросить все высокие частоты — то ничем. Будет просто размытие. Поэтому отбрасывают не всё, а, например, только значения, которые меньше по модулю некоторого порога. А те, что остаются, округляют до пары значащих цифр.

      2. Кстати, преобразование Хаара — это почти то же самое, что и FFT по двум точкам. Там тоже полусумма и полуразность.

      В самом деле, это очень близкие вещи в дискретном случае. DCT — это тоже, в общем-то, фильтр, но имеющий несколько полос. Если делаем DCT по 8 точкам, то получаем отфильтрованные значения из 8 диапазонов.

      У DWT два диапазона — высокие частоты и низкие. Высокочастотный диапазон снова можно поделить на высокие и низкие. И ещё тут есть особенность — мы сами так конструируем фильтры, чтобы энергия сигнала концентрировалась в высокочастотной области, то есть чтобы было проще потом квантовать. Но из-за этого функции, которые используются при разложении, выглядят весьма «несинусоидально».

      Вообще, сложно рассказать об отличиях кратко. Тут целую статью можно написать. :)
      • 0
        Ясно, спасибо за развернутый ответ, вроде более-менее уловил суть :)
    • +3
      чем оно принципиально отличается от преобразования Фурье, и как частного случая — cosine transform?

      В преобразовании Фурье, в самой теории, базисом является 2-pi периодическая функция и в процессе — интегрирование на всем R, а в вейвлетах есть «всплекс», и который быстро угасает, и им можно пренебречь. Этот инструмент(прежде всего математический) дает возможность использовать его как раз там, где сигнал представляет собой не периодический бесконечный сигнал, а типичный разовый кусок данных — кадр картинки, и не нужно накладывать всякие костыли типа оконных преобразований Фурье.
    • 0
      Ваш второй вопрос хороший, но почему-то в ответ на него начинают бормотать что-то про частотные диапазоны (что в принципе верно, но совершенно никак не следует из изложенного в заметке научно-популярного материала).

      Простой ответ состоит в том, что при использовании преобразования Фурье (в одной из форм) приходится фиксировать размер окна и в результате учитываются зависимости между яркостями пикселов только на одном фиксированном масштабе. При использовании же вейвлет размер окна сам собой оказывается переменным — в тех местах, где яркость меняется медленно, используется широкое окно, а там, где быстро — узкое.

      В принципе слова про различия в строении полосового фильтра — о том же, но требуют некоторого чутья в области Фурье анализа, при отсутствии которого получаются утверждения про «костыли» преобразования Фурье. А на самом деле Фурье-анализ с переменным окном обладает большинством свойств вейвлет (а те, которыми он не обладает, в этой заметке и не обсуждались) и известно как вейвлета Морле (которая, впрочем, не является вейвлетой в смысле дискретного вейвлетного преобразования).
      • +1
        Согласен.

        Из материала заметки ответ на вопрос о различиях вообще никак не выудить, на самом деле. Потому я и ответил на комментарий кратко.

        Что дискретное преобразование Фурье, что дискретное вейвлет-преобразование — оба они являются линейными преобразованиями. Я в статье просто показал, как можно построить линейное преобразование, обладающее интересующими свойствами, и сказал, что результат называется вейвлет-преобразованием. На самом деле этого уже достаточно для элементарного применения на практике. Для более-менее предметного разговора о различиях нужно вводить понятие компактного носителя, рассматривать свёртки и т. д.

        Цель же статьи, как Вы абсолютно верно заметили, была научно-популярная. Я хотел показать, что вейвлеты не возникли на пустом месте, а могут быть представлены как обобщение решения весьма конкретной практической задачи. Правда, каюсь, до конца я объяснения не довёл, побоявшись что обилие математики отпугнёт читателей.

        Такой вот дисклеймер. :)
        • 0
          Да все нормально. Ваш стиль мне напомнил популярные (более-менее) статьи Гильберта Стренга (Gilbert Strang), он тоже любит начинать с линейной алгебры. А мое объяснение про окно переменной ширины все-таки ближе к выбранному Вами уровню изложения (ИМХО).
  • 0
    Очень прикольно, но мало =) больше математики.
    • 0
      Промазал. Ответ ниже.
  • +14
    О! Когда начал было много планов. И проиллюстрировать написанное, и рассказать про биортогональные вейвлеты, и примеры кода привести. Но уж очень много всего получается. Рассказать несложно, а оформить…

    Надеюсь, напишу ещё статью, но уже ориентированную на программирование.
    • 0
      И ещё одну на математику :)
  • 0
    Есть какие-нибудь готовые утилиты, чтобы попробовать как оно жмет?
    • 0
      Поглядите в сторону JPEG 2000, там вместо DCT применяют вейвлеты.
    • +2
      На хабре была статья, описывающая алгоритм сжатия на основе вейвлетов. Там и текст программы приводится. Правда, использовались не вейвлеты Добеши, а биортогональные вейвлеты и лифтинг-схема, про которые я не рассказывал.

      Из алгоритмов сжатия изображений вейвлеты используют, к примеру, DjVu (точнее, IW44) и JPEG2000. В видеокодеке Dirac тоже вейвлеты внутри. Но там всё сложнее устроено, конечно.

      А утилит, которые используют вейвлеты Добеши в чистом виде я не припомню. Но если на неделе будет свободное время, напишу как изложенный материал использовать на практике.
  • +5
    Помню на конференции по компьютерной графике в МГУ в 1998 году вейвлетам предрекалось большое будущее в разных областях. Сейчас же говорится о сжатии изображений и в качестве примера приводится не самый популярный формат, у которого кажется еще и проблемы с лицензиями. Можно упомянуть формат DjVu, который так же использует вейвлеты, но в целом за 14 лет какого-то видимого скачка не произошло. А может применяется не так явно?

    Кстати вейвлет сжатие изображений оказалось панацеей для хранения рентгеновских и МРТ снимков. Объемы то в хороших клиниках «там» накапливаются приличные.

    А вообще большое спасибо — тему надо продолжать, только через популяризацию можно привлечь на сторону добра :)
    • 0
      Ну, вейвлеты в самом деле широко используются при анализе и обработке сигналов. В аудиоредакторах есть вейвлет-спектрограммы, в графических редакторах — вейвлет-фильтры, в графических и видеокодеках применяются. Хотя, конечно, это не решение всех проблем.

      Но так всегда. Придумают что, потом начинается ажиотаж, а через некоторое время всё стихает. Вспомните хотя бы нейронные сети!
      • +1
        Ну, скажем, к нейронным сетям ажиотаж интерес сначала схлынул, когда стало понятно, что сходу конфетки не выйдет. А сейчас интерес к ним снова появился.
  • +1
    Спасибо, здорово! Люблю статьи где объяется от самых примитивов. Хотя мне кажется, можно было бы ещё немного углубиться.
  • 0
    — неплохая книжка также у Чуи «Введение в вейвлеты».
    — другим примером применения является способность передавать графику с заданной степенью точности (пример с Леной уж слишком хрестоматиен)
    — интересно также приложение вейвлет-анализа к функциональным разложениям.
    — Демьянович — лучший.
    • 0
      ваш никнейм и любовь к алгоритмам так и просит спросить Ruptor вы или нет?
      • 0
        жаль, но не знаю, о ком идет речь
        • 0
          все дело в этом
          • 0
            ну надо же :)… и все же, что такое Ruptor?
    • 0
      Мне книжка Чуи как раз показалась худшей из доступых. Общая теория там описана очень отрывочно и однобоко, а сплайн-вейвлетам, которым в основном посвящены работы автора, отведено слишком много места. В качестве вводного учебника книжка Блаттера выглядит привлекательнее.
  • +4
    Тестировали новые компьютеры. Фурье- и вейвлет преобразования идут на ура. Квейк тоже не тормозит.
  • +5
    Вейвлеты не вытеснили другие алгоритмы сжатия графических изображений, но заняли разные ниши, о которых писали в комментариях. Добавлю в копилку свою историю.

    Году в 99-ом я с помощью вейвлетов запаковывал данные с высотами земной поверхности, представленными в виде двумерного массива DEM. Огромные и по нынешним временам объемы приходилось ужимать в 30-60 раз, чтобы они поместились на CD-диск или, в виде участков достаточной площади, в GPS приемник. При этом нужно было обеспечить приемлемую точность — все-таки данные предназначены для навигации. Платформа накладывала серьезные ограничения на применение арифметики с плавающей точкой, поэтому рассматривался особый класс вейвлет-преобразований с целыми коэффициентами — в отличие от рассмотренных в статье. В общем, без вейвлетов было бы трудно обойтись.

    Любопытно, что в некоторых случаях проблема быстродействия остается актуальной и сегодня. Например, в марсианских миссиях NASA, столь активно обсуждаемых на Хабре, используется ICER — аналог JPEG 2000, построенный тоже на вейвлетах, но реализующийся на целочисленной арифметике.
  • +4
    Вейвлеты хорошо жмут картинку. Есть очень быстрые преобразования например 5/3 вейвлеты, используют только целые числа сложения и сдвиги. Они могут использоваться для сжатия без потерь, что и применяется в медицине. Так же очень хорошо происходит декорреляция изображения в bayer формате без всяких цветовых преобразований. Вот приме реального когда одномерного преобразования,
    <code>
    /**	\brief One step 1D 5/3 discrete wavelet transform.
            \param in	The input data array.
            \param out 	The output data array.
    	\param w 	The length.
    */
    static inline void dwt_53_1d(int16 *in, int16 *out, const uint32 w)
    {
    	int wt = w - 2, i, j;
    	int16 *l, *h;
    	l = out; h = &out[(w>>1) + (w&1)];
    	h[0] = in[1] - ((in[0] + in[2])>>1);
    	l[0] = in[0] + (h[0]>>1);
    	for(i=2,j=1; i < wt; i+=2,j++){
    		h[j] = in[i+1] - ((in[i] + in[i+2])>>1);
    		l[j] = in[i] + ((h[j-1] + h[j])>>2);
    	}
    	if(w&1){
    		l[j] = in[i] + (h[j-1]>>1);
    	} else{
    		h[j] = in[i+1] - in[i];
    		l[j] = in[i] + ((h[j-1] + h[j])>>2);
    	}
    }
    </code>
    

    двумерное это просто комбинация одномерно по горизонтали и вертикали. Теперь ложка дегтя, вейвлеты совершенно не пригодны для сжатия межкадровых разностей изображений, т.е видеопоследовательностей, по этому и не получили широкого распространения.
    • 0
      Теперь ложка дегтя, вейвлеты совершенно не пригодны для сжатия межкадровых разностей изображений, т.е видеопоследовательностей, по этому и не получили широкого распространения.

      Но при сжатии видео их всё же удаётся использовать. Например, они применяются в кодеках Dirac и Tarkin.
      • 0
        Не разбирался с Dirac и Tarkin, скорей всего они жмут вейвлетом только I фрейм, потому как бессмысленно жать ими P или B фреймы. Нет ни однго промышленного вайвлет видео кодера. Dirac тоже уже загнулся, BBC поигралось и вовремя остановилось.
        • 0
          Насчет промышленных вейвлет-кодеков — это ИМХО как с realtime-рейтрейсингом: вроде и теоретическая база проработана, и алгоритмическая, и картинка получается — залюбуешься! Но вот вычислительные ресурсы (массово доступные) — увы, пока массово недоступны. Но лет так через 5, когда наконец-то наступит технологическая сингулярность
          • +1
            Есть интересная и довольно оптимстичная статья по видеокодированию вейвлетами (Wavelet-based video compression: A glimpse of the future?) Здесь описаны основные проблемы вейвлетов и как с ними можно боротья.
            Основная прблема 3D сжатие сжатия видео — это найти трактории движения каждой точки во времени и по
            этим траекторияю уже провети вейвлет преобразование. Но если вы сможите найти эти трактории, то вам не нужны будт вейвлеты, вы и так великолепно сожмете видео. В дальнейшем в сжатие видео можно продвинутся только векторизацией изображения и ослеживанием изменений всех векторов или объектов. Опять же, каждый нормальный кодек должен и меть «железную» реализацию. Самое принципиальное отличие DWT от DCT — это то что DWT работает со всем изображением, а не с квадратиками 8x8 или 4x4. И чтобы сделать 2d вайвлет преобразование нужно хранить все изображение в памаяти, что занчительнео усложнчет хардверную реализацию, я уже не говорю о 3d преобразованиях.
    • 0
      Ну почему же не пригодны? Очень даже пригодны. Принцип Wavelet-кодеков для видео, типа Dirac, насколько я знаю, грубо говоря, в «расширении» идеи Wavelet-сжатия 2D-изображения в третье измерение — т.е. время. Т.е. получается «декорреляция в трех измерениях». В случае видео это дает очень и очень эффективное кодирование «межкадровой разности». Но требования к вычислительным ресурсам при этом, естественно, существенно возрастают.
  • +1
    Её [матрицу изображения] можно записать построчно в файл и сжать каким-то архиватором.

    Используемые архиваторы обычно работают с одномерным массивом (сигналом), игнорируя двумерную природу данных. В степени сжатия можно ещё немного выиграть, выбирая особый порядок записи байтов перед архивацией. Например, записывать не строки, а блоки изображения по очереди. Под блоком подразумевается изображение, что получаемое на одном шаге преобразования — они хорошо различимы на картинке с замком из статьи. Блоки, представляющие разности соседних элементов по горизонтали (первый такой блок на картинке справа сверху) можно записывать по столбцам, чтобы прообразы соседних элементов были ближе на исходном изображении. Это легко понять, рассмотрев вертикальную стену башни. А правый нижний блок — записывать змейкой по диагонали.

    При этом если записывать вначале низкочастотные блоки (в левом верхнем углу на картинке), то можно получить возможность прогрессивной, т. е. работающей по мере поступления данных, распаковки.
    • 0
      Да, Вы правы. На вход энтропийного кодера подают именно одномерный поток данных. Хотя там есть и свои особенности, конечно. Про запись по строчкам я намеренно написал упрощённо, а то пришлось бы лезть в дебри. Впрочем, Вы продемонстрировали, что можно и кратко всё изложить.

      Описанный Вами способ применим, если изображение вообще делится на блоки. Так поступают в том же JPEG для ускорения расчётов. В случае с вейвлетами можно подвергнуть преобразованию хоть всё изображение сразу.

      Ещё можно заметить, что самая важная информация содержится в старших битах коэффициентов и единицы концентрируются именно в них, поэтому можно переупорядочить биты, передавая сначала старшие, а потом младшие. Этот подход используется в алгоритме SPIHT.
  • НЛО прилетело и опубликовало эту надпись здесь
    • 0
      Да, эту тему активно начали развивать ещё в конце восьмидесятых. И тогда же предложили использовать для сжатия графики, если не ошибаюсь.

      С тормознутостью тоже боролись как могли. Приблизительно в конце 90-х был разработан формат PGF, в котором был сделан упор на производительность.
    • 0
      а я по дурости тогда в это поверил и курсовую по сжатию делал в 2000м.
      • НЛО прилетело и опубликовало эту надпись здесь
        • 0
          без особых. хуже джипегов
  • +2
    Это преобразование получило название вейвлета D4 (читателю предлагается самостоятельно разгадать тайну этого буквенно-цифрового названия).
    Ну, прежде всего приходит на ум, что буква D происходит от фамилии Добеши, а цифра 4 — от того, что вейвлет имеет дело с четвёрками.

    Если ещё немного подумать, то отыскивается более глубокая игра слов: фамилия Добеши оканчивается на «ши», что созвучно произношению японского иероглифа «四», означающего четвёрку. (На другом таком же созвучии с четвёркою основано популярное восточное суеверие, известное как тетрафобия.)
  • +2
    Громадное спасибо Вам за статью.
  • +2
    Блин, ну почему всегда используется для демонстрации обрезанная Lenna? Есть же полная версия, и глаз она радует больше…
    • +1
      Сейчас — по традиции, дабы иллюстрировать работу алгоритмов на всегда одном и том же изображении.
      А изначально — из-за технических ограничений сканера, которым пользовались исследователи.
      en.wikipedia.org/wiki/Lenna
      • +1
        Вопрос был риторический. Но спасибо за ответ :-)
    • 0
      Изначально использование Лены было неким эпатажем, поскольку многие понимали, из чего вырезана картинка. А потом наиболее смелые авторы стали использовать аналогичным образом вырезанные участки из гораздо более откровенных фотографий, благо сейчас не проблема найти оригинал. Но пруфлинк не приведу, потерял среди кучи статей.
      • +1
        По «официальной» версии — не было эпатажем. Что нашлось в комнате у исследователей, то и отсканировали. Подобно ютскому чайнику — исследователь во время чаепития обдумывал тело для иллюстрации своих алгоритмов, да так и оцифровал заварочный чайник со своего стола.

        Лена — не первый и далеко не единственный пример использования эротических фотографий для иллюстрации научных и околонаучных статей: каждому автору хочется, чтобы его статья «задевала глубинные струны в душах читателей», даже на Хабре регулярно попадаются иллюстрации с соблазнительными девушками, даже во вчерашней статье Abbyy. Все же понимают, чем цепануть глаз суровых айтишников :)

        См.тж: Keeping Abreast of Pornographic Research in Computer Science
        • –1
          Ok, может и не было эпатажем, но воспринималось однозначно как эпатаж. Еще задолго до появления сервисов поиска картинок и юбилейной выставки фотографий Лены люди, занимающиеся обработкой изображений, нашли полный вариант картинки и с хитрой усмешкой показывали его непосвященным :)
          • –1
            Мне кажется, вы переворачиваете картину с ног на голову.

            Задолго до появления сервисов поиска картинок — аудитория «Плейбоя» была на много порядков многочисленее, чем аудитория статей об обработке изображений.

            И поэтому намного вероятнее, что открыв статью, они с восторгом узнавали знакомую по «Плейбою» Лену — чем наоборот: открыв «Плейбой», узнавали Лену, знакомую по научным статьям.
            • –1
              Аудитория «Плейбоя» была многочисленнее, но пересечение этих аудиторий было ничтожным, даже в сравнении с и так малочисленной аудиторией статей по обработке изображений.
              • –1
                Ой ну конечно же, исследователи на переднем крае новой технологии были сплошь седовласые старцы и чопорные отцы семейств.
                • –1
                  Не знаю как Вам, а мне живые девушки всегда казались более приятными, чем бумажные, так что по сути я только эту картинку из Плейбоя и видел (ну и еще может пару раз обложки в сети)
                  • –1
                    Судя по тому, какие бури огорчения захлёстывают Хабр и другие профессиональные сообщества, когда в очередной раз ложится Pornolab — мои предпочтения по этой части разделяются большинством моих коллег :-)
                    • –1
                      «Все дивчины в город посмотались, не хотят колхозной жизнью жить»? Вот ведь никогда заранее не предсказать, где встретишь марсианина представителя иной цивилизации :))
    • 0
      Автор занулил на Лене все вейвлет-разности, вот тебе и потеря информации при сжатии
  • 0
    Большое спасибо за статью! Мне как раз на следующей неделе студентам объяснять вейвлеты, хотя, как оказалось, я бы и сам был не против, чтобы мне их вот так объяснили.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.