| Home People Activities Research Publications |
|
|
Dmitry V. Yurin personal pageОсновная литература:Приведенный здесь список литературы не претендует на полноту в каком либо-смысле: ни по охвату тем, ни по всестороннему освещению темы и ее подтем, ни по полноте литературы по какой либо теме. Наоборот, основной принцип - минимализм. Т.е. приводится литература только по некоторым областям обработки изображений, и только та, которая затрагивает наиболее важные аспекты и наиболее перспективные методы. Естественно присутствует значительная доля субъективности: отбор тем определяется моими интересами, а набор ссылок по теме отражает мое личное мнение. Численные методы Основы обработки изображений (книги, учебники) Алгоритмы Брезенхэма Фильтрация Поиск характеристических особенностей на изображениях Поиск характеристических точек (уголков, ярких/темных пятен) Выделение границ Поиск прямых линий на изображениях Прочие характеристические особенности Совмещение изображений (Image Registration) На основе интегральных преобразований: На основе оптического потока: На основе характеристических точек: Пространство переменных разрешений (Scale Space Theory) Восстановление 3D RANSAC Mean-Shift Reviews
Численные методыНа мой взгляд, именно в этой книге и именно в ее старом издании наиболее понятно изложено применение сингулярного разложения матриц для решения задачи наименьших квадратов с регуляризацией (глава 9). Решение пере- и недоопределенных системы алгебраических линейных уравнений. Рассмотрены все важные аспекты, связанные с сингулярным разложением, даны четкие пояснения и численные примеры: необходимость нормировки данных перед применением сингулярного разложения, какие именно сингулярные числа следует занулять (регуляризация), нуль-пространство и построение общего решения (с произвольными параметрами) для недоопределенных линейных систем. Единственная неточность - при описании регуляризации не сказано, что это связано с теорией возмущений для сингулярных чисел и векторов и не приведена формулировка теоремы Вейля. Об этом можно прочитать в книге
Замечательный учебник по численным методам, содержащий также полные тексты всех описываемых вычислительных процедур на С. На самом деле - библиотека программ с документацией-учебником. Описание математических принципов достаточно подробно, хотя может быть не столь строго, как в некоторых отечественных учебниках. Достоинствами книги являются тексты программ и необычайно широкий охват различных областей вычислительной математики. Это и интегрирование, и решение линейных алгебраических и дифференциальных уравнений, и разложения матриц, и нелинейные методы минимизации, включая многомерные, и вычисление спец. функций, и методы наименьших квадратов и многое, многое другое. Все приводимые процедуры в достаточной степени замкнутые и автономные. Код хорошо документирован, наряду и с математическим описанием алгоритма в соответствующем параграфе. Таким образом, код полностью можно понять. Может быть, качество кода несколько уступает таким классическим библиотекам как NAG, LAPACK, NETLIB, но в данном случае достоинство понятность кода и автономность - редко какая функция использует более 1-3 других. Кроме того, процедуры из этой книги очень часто используются в научных публикациях (использовалась процедура ... из Numerical Recipes). Хорошая книга по классическим алгоритмам: сортировка, деревья. Показано, как по массиву можно найти медиану быстрее, не выполняя полную сортировку массива. Сортировки, деревья, алгоритмы на графах, динамическое программирование, жадные алгоритмы, вычислительная сложность, NP-полные задачи, оптимальный алгоритм перемножения нескольких матриц и многое другое. Стандартный и классический учебник по Computer Science за рубежом. Очень хорошо написан. Образцовый стиль описания алгоритмов. Полностью эквивалентно преобразованию Фурье для случая вещественных сигналов, но вычислительно гораздо эффективнее (меньше требует памяти, работает быстрее). Последние две книги - справочники, но не стоит ими пренебрегать. Например: 1) алгоритм быстрой свертки с Гауссом (ниже) построен именно на аппроксимирующей формуле из второй книги; 2) предположим требуется новая спец. функция - интеграл от нуля до x от функции Бесселя нулевого порядка. Численное интегрирование - долгая и сложная процедура (функция осциллирующая и знакопеременная!). А в первой книге есть аппроксимация с точностью до 1.5e-8, надо только 20-40 умножений и однократно вычислить sin, cos и sqrt. Много информации также по статистическим различным распределениям. В частности во второй книге есть определение и разные аппроксимации и ассимптотики для процентных точек распределения Стьюдента (очень полезно при обработке данных с погрешностями).
Основы обработки изображений (книги, учебники)
Алгоритмы БрезенхэмаВ целом книга устарела и не представляет интереса. Но в ней содержится описание алгоритмов Брезенхэма рисования прямых линий, эллипсов, заливки (закраски) областей. Эти алгоритмы показывали впечатляющую производительность еще древних компьютерах. Отказываться от них сегодня было бы неверно. На самом деле графические библиотеки и встроенные в железо процедуры реализуют именно эти алгоритмы. Если требуется выполнять похожие операции при обработке изображений, незнание не может служить извинением.
ФильтрацияЛучшее описание ранговых алгоритмов целиком, а не только медианной фильтрации, которая есть только один и простейший из этой группы. Еще один алгоритм, который может быть отнесен к классу ранговых алгоритмов. Ссылка на статью приводится в связи с тем, что в последнее время этот алгоритм становится все более популярным. Качество результата хорошее. Алгоритм быстрого вычисления свертки с функцией Гаусса и ее первыми тремя производными. Независимо от величины сигма, на каждую точку данных требуется примерно 12 умножений. Отличный обзор по быстрой реализации ряда фильтров. Фантастически быстрый алгоритм вычисления медианной фильтрации. Перевод изображения из TrueColor в индексное с отличным качеством. Хорошо во всяких задачах классификации и сегментации, остаются только важные цвета, причем в смысле похожем на понимание человека. Алгоритм медленный, на счет быстрой реализации мне не известно. Существенно выравниваются яркости изображений: яркие объекты-темные объекты. Качество хорошее.
Поиск характеристических особенностей на изображениях
Поиск характеристических точек (уголков, ярких/темных пятен)Предыдущие две статьи - два классических детектора характеристических точек. Очень похожи, отличие в том, что в первой не надо вычислять квадратный корень (только умножения и сложения). Европейцы предпочитают Харриса, американцы - Канаде-Лукаса (вторая статья). На сегодняшний день в чистом виде использовать не следует, но современные ScaleSpace детекторы построены как правило на базе этих двух классических. Предыдущие две статьи описывают лучший на сегодняшний день детектор характеристических точек, естественно ScaleSpace. Вообще говоря, по современным представлениям детектор точек должен состоять из следующих трех этапов: 1) построение ScaleSpace и детектирование точек на каждом уровне детальности; 2) уточнение положения точки до субпиксельной точности и выбор разрешения на котором она проявляется наилучшим образом; 3) построение вектора параметров, описывающего точку так, чтобы при выполнении сопоставления точек на двух (или более) изображениях можно было просто считать расстояния между такими векторами параметров по некоторой метрике, для тех точек для которых такое расстояние минимально считается, что они соответствуют друг другу. Детектор SIFT замечателен именно третьим этапом. Первый этап - реализован простейшим образом, добивались максимального быстродействия. Второй этап - стандартный, обчно так делают все. Наоборот, в этом детекторе первый и второй этапы максимально проработаны. Третий этап существенно уступает по качеству SIFT, хотя используется весьма красивая и математически глубоко проработанная теория дифференциальных инвариантов. Векторы параметров получаются более похожими для различных объектов. Причина видимо в том, что дифференциальные инварианты считаются в точке, в то время как SIFT строит вектор параметров эмпирически, по сути - локальные гистограммы градиента яркости по окрестности точки. Размерность вектора параметров в этом детекторе около 10, а у SIFT - 128. Статья хороша очень детальной проработкой первых двух этапов. Аналогично предыдущей статье, приняты все меры по улучшению точности детектирования и достижению аффинной инваниантности. Дескрипторы - другие, инвариантные к вращению. Построены на основе преобразования Фурье-Меллина. См. также страницу автора: http://staff.science.uva.nl/~mark/downloads.html. Для понимания статьи вероятно необходимо прочитать также статью J. M. Geusebroek, R. van den Boomgaard, A. W. M. Smeulders, and H. Geerts. Color invariance. IEEE Trans. Pattern Anal. Machine Intell., 23(12):1338-1350, 2001. PDF Модификация детектора SIFT для работы с цветными изображениями. Модифицирован 3 этап - построение дескриптора. Вводится семейство дескрипторов, инвариантных к теням, бликам и т.п. К недостаткам можно отнести то, что дескриптор зависит от того, насколько заметный перепад цвета, но не зависит от того, от какого к какому именно цвету перепад (edge). Также недостатком является то, что первые два этапа - собственно детектирование точек, определение масштаба и уточнение координат полностью взяты от серого SIFT. Это облегчает сравнения качества, проводимые в статье, но не решает проблему обнаружения особенностей, которые при переводе цветного изображения в серое теряются или становятся слабо заметными. В целом статья - хорошее решение, которое обязательно должно приниматься во внимание при разработке новых детекторов/дескрипторов. Легко реализуется - в код оригинального SIFT требуется внести минимальные изменения. См. также страницу автора: http://homes.esat.kuleuven.be/~tuytelaa/. Хороший обзор детекторов от классика. Большой список литературы. Рассмотрено много разных детекторов. Даны пояснения, рекомендации по выбору детектора для конкретных задач. Указаны сильные и слабые стороны. Предложен дескриптор GLOH. Срвниваются: - GLOH, - SIFT, - Shape context, - PCA-SIFT, - Moments, - Cross correlation, - Steerable filters, - Spin images, - Differential invariants, - Complex filters. Очень важная статья. Статья посвящена несколько иной теме: в качестве дескрипторов характеристических точек используются дифференциальные инварианты. Изображения цветные - поэтому инварианты считаются для различных цветовых компонент. Основной акцент в статье сделан на решение следующей задачи: есть 2 изображения, часть точек уже верно сопоставлена. Как найти и сопоставить дополнительные точки с минимальными затратами. Имеются в виду такие характеристические точки, которые на первом этапе сопоставить не удалось, так как по дескриптору - на другом изображении было много кандидатов, а теперь уже восстановлена эпиполярная геометрия и сопоставление производится с наложением эпиполярных ограничений.
Выделение границКлассическая и самая главная статья по выделению границ. Основные моменты: классификация типов границ (step edge, roof edge, etc.). Использование модуля градиента яркости для обнаружения step edge. Градиенты вычисляются путем свертки с производной функции Гаусса. Основная структура: модуль градиента -> non maxima supression -> гистерезисное ограничение. Предыдущие две статьи - как правильно обобщить метод Канни от серых к цветным изображениям. Идея предложена в первой из них. Полностью корректный математический подход дан во второй. Идея - замена модуля градиента модулем цветового градиента (подробнее - см. статьи), для определения направлений и величины "цветового градиента" используются собственные векторы и собственные значения корреляционной матрицы первых производных. Все остальное остается так же как и в статье Канни. Отчет поясняет как процедуру Non Maxima Supression в трех предыдущих статьях можно выполнить с субпиксельной точностью. В этой статье надо на страницах 384-385 смотреть почему плох оператор Лапласа в качестве детектора границ - смещение границы на величину пропорциональную локальной кривизне изолинии (обычно совпадает с кривизной границы). В статьях Canny, Di Zenzo, Cumani производные по x,y от яркости изображения вычисляются путем свертки изображения с первой производной функции Гаусса. Величина сигма задается с потолка (на основе имеющейся априорной информации). Понятно, что на реальных изображениях границы размытые и нечеткие. Насколько - неизвестно. Поэтому важно правильно выбирать масштаб вычисления производной (величина сигма), и не одинаково для всего изображения, а адаптивно, для каждой точки изображения. Последние две статьи посвящены как раз этой проблеме. Основная - последняя, предыдущая - в качестве дополнительного пояснения. Подробнее см. раздел "Scale Space Theory". Обнаружение границ на цветных изображениях. Границы инвариантные к теням, бликам, условиям освещения. Таким образом, по современным представлениям детектор границ (Edge detector, Step edge) должен быть устроен следующим образом: - выбор метода детектирования согласно целевой задаче:PS: В отношении реализации свертки с функциями Гаусса и ее производными - см. статью о быстрой свертке с Гауссом в разделе Фильтрация PPS: Процедуру Non Maxima Supression следует выполнять согласно отчету Frederic Devernay (4-я статья в списке). PPPS: О неточности найденных границ - можно прочитать в статье:
Поиск прямых линий на изображенияхВторая статья - 100% перенос перовой с преобразования Фурье на преобразование Хартли. Выигрыш в затратах памяти и быстродействии. Других серьезных отличий нет. По функциональности и свойствам подходы полностью эквивалентны. Относительно предварительного выделения границ на изображении перед применением процедуры Быстрого преобразования Хафа - см. раздел Выделение границ, это особенно нужно для цветных изображений, кроме того во всех случаях методика ScaleSpace делает результат поиска линий более обоснованным и менее подверженным шуму.
Прочие характеристические особенностиПохоже на характеристические точки, но не точки, а маленькие сегменты, существенно отличающиеся по цветояркостным характеристикам от окружения. Признана лучшей статьей на конференции BMVC2002.
Совмещение изображений (Image Registration)
На основе интегральных преобразований: |
