Вейвлеты в обработке сигналов. Дубль три

Угадайте кто? Для тех кто не знает или сдается, поясню, что на фотографии изображен известный французский ученый Стефан Малла (Stephane Mallat).

"Чем же он так известен?" - спросите вы. А тем, что в конце 80-х годов прошлого века Малла предложил достаточно уникальный на тот момент времени подход взаимосвязи теории вейвлет-преобразования и теории банков фильтров. Последнее позволило осуществить определенный толчок в дальнейшем развитии цифровой обработки сигналов различной размерности. Помимо этого Малла имеет достаточно впечатляющий послужной список в плане публикаций и известен как автор книги A Wavelet Tour of Signal Processing, о которой и пойдет речь в настоящем посте. На данный момент времени книга существует в трех изданиях. И хотя никакой информации о первом я не нашел, отмечу, что второе и третье издания в англоязычных версиях вышли в 1999 и 2008 годах, соответственно, в издательстве Academic Press. В русскоязычной версии, на данный момент времени, существует перевод второго издания, вышедший в издательстве Мир в 2005 году, который едва ли можно считать образцом перевода зарубежных книг. Русский перевод читается очень плохо, плюс, если учесть, что автор книги не пожалел математической основы, получается полный кошмар. Поэтому, вероятнее, лучше анализировать англоязычную версию. В общем и целом книга очень интересная.

Особо порадовало третье издание с доработанными главами и новым материалом, затрагивающим исследования в области представления, аппроксимации и восстановления сигналов за последние 15 лет. Среди новых составляющих третьего издания можно выделить: Radon Transform and Tomography, Block Thresholding for Denoising, Geometric Representations with Adaptive Triangulations, Curvelets and Bandlets, JPEG-2000 Image Compression, Compressive Sensing и так далее. Положительный эффект на восприятие материала оказывают пояснительные примеры, появившиеся в главах третьего издания. Официально в свободный доступ книга не выложена, однако, на некоторых файлообменниках она может быть найдена, например, здесь. Дополнительные материалы, затрагивающие главы книги, можно найти на ее официальном сайте. Покупка книги может быть осуществлена через сайт amazon.com.

Seam Carving Algorithm или чудеса умного ресайзинга изображений

На данный момент времени достаточно актуальной с точки зрения обработки изображений является задача автоматического изменения их размера. Последнее связано с большим количеством электронных устройств, выводящих изображения на экраны (дисплеи мониторов персональных компьютеров, ноутбуков, мобильных телефонов, PDA  и так далее) различного формата. Поэтому исходя из сказанного выше, хотелось бы "подогнать" изображение под формат экрана и отобразить его. "Используя основы цифровой обработки сигналов, а, именно, наборы дециматоров, интерполяторов и памятуя о теореме Котельникова-Уиттекера-Шеннона-Найквиста изменяем размер картинки и нет проблем", - скажете вы. Однако применительно к изменению размера изображения (image resaizing) в результате выполнения этой операции могут произойти значительные искажения пропорций объектов изображенных на нем. "Хорошо, тогда предложим обычную обрезку (image cropping)". Но в этом случае "важные" объекты на цифровом изображении могут быть удалены. Возникает необходимость разработки методики, позволяющей осуществлять ресайзинг изображения в зависимости от его содержимого (контента). Пример подобного рода алгоритмов можно найти в следующей статье: Avidan S., Shamir  A. Seam Carving for Content-Aware Image Resizing, 2007, скачать которую можно здесь. Понятно изложенную презентацию с курса Computer Vision University of Washington, 2010 и демонстрационный видеоролик по данному алгоритму можно скачать здесь и здесь, соответственно. Так же есть информация на blog.piclab.ru (ссылка), Wikipedia (ссылка) и habrahabr.ru (ссылка).

Общая идея алгоритма Seam Carving (дословно переводится как контурное вырезание по шву), для примера понижения разрешения цветного изображения, состоит в следующем:
1. Преобразуем исходное цветное изображение в изображение в градациях серого (grayscale image).

2. Вычисляем амплитуду градиента grayscale изображения с использованием, например, операторов Собеля, Робертса, Превитт. В данном случае градиентное изображение представляет собой что-то вроде карты значимости исходного изображения, показывающей то, где последнее содержит много деталей, которые в результате ресайзинга нужно оставить.

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

4. Осуществляем удаление пикселей, принадлежащих путям минимальной стоимости найденных на шаге 3.

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