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

Угадайте кто? Для тех кто не знает или сдается, поясню, что на фотографии изображен известный французский ученый Стефан Малла (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 (ссылка).

Microsoft Computer Vision School

Как и было отмечено на конференции ГрафиКон'2010 летом этого года (с 28 июля по 3 августа) в Москве на базе МГУ им. М.В. Ломоносова  пройдет школа Мicrosoft по компьютерному зрению (Microsoft Computer Vision School, MSCVS). Более подробная информация здесь. Школа спонсируется исследовательским подразделением компании Microsoft (Microsoft Research) и организована совместно с МГУ им. М.В. Ломоносова. Цели школы: предоставить студентам уникальную возможность узнать фундаментальные и новейшие результаты по компьютерному зрению и анализу изображений от ведущих мировых ученых данной области; предоставить возможность студентам обменяться опытом друг с другом и с преподавателями школы.

Принять участие в школе могут студенты старших курсов, аспиранты и молодые ученые, интересующиеся компьютерным зрением и анализом изображений. Рабочий язык школы - английский, однако некоторые доклады будут на русском, поэтому участники должны владеть обоими языками. Минимальная подготовка участников должна включать вводный курс по алгоритмам и базовые навыки по программированию (на C++). Всем принятым к участию в школе претендентам будет оплачено участие в школе: проживание, питание и культурно-развлекательная программа. Студенты должны будут оплатить проезд в Москву и обратно. В ограниченном количестве случаев школа оплатит проезд частично или полностью.

Школа включает в себя лекции, практические занятия, проект по программированию и сессию стендовых докладов участников школы.

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

Нужно обязательно туда попасть. С the 21st Jyväskylä Summer School по числам не накладывается.

Учимся с использованием Videotapes

Интересным (для многих известным) фактом обучения в некоторых зарубежных университетах является возможность использования готовых видеозаписей (videotapes) лекционных материалов курсов. Это является, как мне кажется, неплохим подспорьем в образовании (самообразовании, если ты не являешься, скажем, студентом Massachusetts Institute of Technology, MIT). Однако это конечно не означает, что там на лекции не ходят! Для себя отмечу плюсом прослушать лекцию Гильберта Стренга (Gibert Strang) по "Линейной алгебре" или по "Вычислительным наукам и инженерии". Поэтому, приведу несколько примеров вышеозначенных материалов, которые, как мне кажется, можно связать с предметами физического факультета Ярославского государственном университета им. П.Г. Демидова.

1. Strang G. Linear Algebra (18.06), 2010. Massachusetts Institute of Technology (ссылка). Обновленная страница данного курса за 2011 год (ссылка).
2. Strang G. Computational Science and Engineering I (18.085), 2008. Massachusetts Institute of Technology (ссылка).
3. Strang G. Computational Science and Engineering I (18.085), 2007. Massachusetts Institute of Technology (ссылка)
4. Ng A. Machine Learning (CS229), 2009. Stanford University (ссылка).
5. Osgood B.G. The Fourier Transform and its Application (EE261), 2009. Stanford University (ссылка). 

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

Курс "Компьютерное зрение" 2011

С 11 февраля начинает свою работу страница курса-факультатива "Компьютерное зрение" специальности "Радиотехника".

В настоящем разделе размещена информация, затрагивающая литературу, ссылки и лекционный материал по тематике курса.

Место и время проведения 

Физический факультет (2-ой учебный корпус), к. 203а, каждую неделю по пятницам, с 12.00 до 13.35.

Темы лекционных занятий

1. Введение в компьютерное зрение (презентация .ppt).
2. Формирование изображений. Камера и ее основные характеристики (презентация .ppt).
3. Анализ бинарных изображений. Первое понятие о распознавании объектов (презентация .ppt).
4. Введение в Matlab (презентация .ppt, примеры .rar). Seam Carving Algorithm - "контурное вырезание по шву" (презентация .ppt, пример реализации .rar).
5. Фильтрация и улучшение изображений (презентация .ppt).
6. Цвет и освещенность. Приложение в задачах компьютерного зрения (презентация .ppt).
7. Сегментация изображений и обнаружение контуров (презентация .ppt).
8. Основные понятия распознавания образов (презентация .ppt).

Дополнительные материалы

1. Szelicki R. Computer Vision: Algorithms and Applications. Springer, 2010 (ссылка).
2. Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer, 2009 (ссылка).
3. Конушин А. и др. Курс "Введение в компьютерное зрение", 2010. Лаборатория компьютерной графики при ВМК МГУ (ссылка).
4. Конушин А. и др. Курс "Введение в компьютерное зрение", 2011. Лаборатория компьютерной графики при ВМК МГУ (ссылка).
5. Kemelmacher I., Rao R., Seitz S., Shapiro L. Computer Vision (CSE 455), 2003 - 2010. University of Washington (ссылка).
6. Lazebnik S. Computer Vision (COMP 776), 2008 - 2011. The University of North Carolina at Chapel Hill (ссылка).
7. Thrun S. Computer Vision / Introduction to Computer Vision (CS 223b), 2004 - 2009. Stanford University (ссылка).
8. Darrell T. Computer Vision (CS 280), 2009. University of California, Berkeley (ссылка).
9. Duraiswami R. Fundamentals of Computer Vision (CMSC 828d), 2000 / Computer Vision (CMSC 426), 2005. UMIACS (ссылка). 
10. Torralba A. Advances in Computer Vision (6.869), 2010. Massachusetts Institute of Technology (ссылка).
11. Ng A. Machine Learning (CS229), 2009. Stanford University (ссылка).
12. Конушин A. Семантическая классификация изображений, 2010. Сomputer Science клуб при ПОМИ РАН (ссылка).
13. Ерухимов В. Компьютерное зрение и библиотека OpenCV, 2011. Сomputer Science клуб при ПОМИ РАН (ссылка).
14. Сетевой журнал "Компьютерная графика и мультимедиа" (ссылка).
15. Efros A. Learning-Based Methods in Vision (16-721), 2009. Carnegie Mellon University (ссылка).
16. Efros A. Computational Photography (15-463 / 15-862), 2010. Carnegie Mellon University (ссылка).

Руководитель курса: асс. каф. ДЭС Волохов В.А.

Книга по статистическому обучению

Выход интересных книг по тематике машинного обучения, интеллектуального анализа данных и всего, что с этим связано продолжается. В общем, подобного рода книги на западе, не новы. В настоящем посте кратко опишу и оставлю ссылку на книгу, опубликованную в 2009 году в издательстве Springer и затрагивающую вышеозначенную проблематику. Название книги: The Elements of Statistical Learning: Data Mining, Inference, and Prediction, видимо можно перевести как "Элементы статистического обучения: интеллектуальный анализ данных, вывод и предсказание". Книга существует в электронном варианте, последний вариант можно скачать здесь. Авторы книги: Тревор Гасти (Trevor Hastie), Роберт Тибширани (Robert Tibshirani), Джером Фридман (Jerome Friedman). Все являются действующими преподавателями Stanford University.

Из авторов перечисленных выше мне особо известен Джером Фридман, публиковавшийся в смежных работах с Лео Брейманом (Leo Breiman). Последний являлся по моему мнению гениальным ученым в своей области, известным научной общественности, например, по теореме Шэннона-Бреймана-Макмиллана (Shannon-Breiman-McMillan theorem, 1957) в теории информации или алгоритму "случайного леса" (Random Forest, 2001), используемого в задачах связанных с регрессией и классификацией. Кратко, что есть в книге: Boosting, Neural Networks, Support Vector Machines, Random Forests and et al. В общем есть что посмотреть и есть с чем разобраться.

Экзамен по курсу "Цифровая фильтрация" 2010

Структура экзамена

Экзамен состоит из трех частей:
1. Один теоретический вопрос из предложенного списка. Вопросы можно скачать здесь.
2. Задача из раздела "Специальные типы цифровых фильтров". Задачи можно скачать здесь.
3. Задача из подраздела "Синтез цифровых БИХ-фильтров методом билинейного z-преобразования". Задачи можно скачать здесь.

Место и время проведения

1. Группа РЭ-41, второй учебный корпус, 19.01.11 с 9:00.
2. Группа РЭ-42, второй учебный корпус, 10.01.11 с 9:00.

Замечание: Вопросы, затрагивающие материал настоящего курса, могут быть заданы в комментариях настоящего раздела или присланы по электронной почте.

Руководитель курса: асс. каф. ДЭС Волохов В.А.