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.

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

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

Книга по компьютерному зрению

На данный момент существует не очень большое количество хороших книг по тематике компьютерного зрения (машинного зрения). В особенности русскоязычных. Надеяться остается только на зарубежные издания. Да и если они выходят в России, то с очень большой задержкой (в лучшем случае 3-5 лет). Плюс к этому время потраченное автором на написание книги и ее выход на западе. Достаточно большой срок по меркам развития современной науки и в частности компьютерного зрения (однако, конечно, фундамент остается неизменным). Здесь речь идет именно о новизне книги в плане ее согласования с современным течением дел в данной конкретной области. Практически единственный вариант решения проблемы новизны книги - формирование ее электронной версии, которая постоянно обновляется. Тяжело сказать встречается ли это в России (наверно, да, но редко), однако на западе такие варианты практикуются достаточно активно.

Примером может служить книга по компьютерному зрению руководителя Interactive Visual Media Group at Microsoft Research Ричарда Зелиски (Richard Szelicki). Более подробно об авторе можно почитать здесь. Полное названием книги Computer Vision: Algorithms and Applications. Полную историю написания книги рассказать тяжело, так как я не обладаю этой информацией. Однако можно точно отметить, что в течение нескольких лет электронная версия этой книги обновлялась на ее официальном сайте, где последний вариант книги и можно скачать. Дополнительно необходимо отметить, что основным достоинством книги Ричарда Зелиски является ее новизна (в смысле отмеченном выше), ну и конечно то, что ее автор является практикующим специалистом в области компьютерного зрения, читавшим (апробировавшим) свой материал в нескольких известных мировых университетах, например, Стэнфордском. На данный момент книга завершена, хотя естественно, с большой долей вероятности, будет происходить ее дальнейшее развитие. А завершена потому, что в нынешнем 2010 известное зарубежное издательство Springer взялось за ее публикацию. Сейчас печатный вариант книги можно заказать на сайте amazon.com. Вот дорогие авторы книг к чему надо стремиться! Ну и самое главное: читателю нужны хорошо понятные книги (отечественные или западные), а не только понятные вам!