| 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)
На основе интегральных преобразований:Классическая работа, классический метод. Ищется преобразование подобия: сдвиг, поворот, масштабирование. Все на основе преобразования Фурье. В этой работе алгоритм из предыдущей статьи перенесен на преобразование Хартли, что дает значительное ускорение и экономию памяти, особенно, если требуется взаимно совмещать более 2-х изображений. Кроме того предложен новый алгоритм поискадругой модели преобразования: сдвиг и перекос (skew). Детально описаны процедуры, которые надо выполнять до и после преобразования Хартли (как впрочем и для фурье), чтобы избежать появления артефактов связанных с краями изображения и его конечным размером. Интересное приложеие первого алгоритма для построения мозаик. Важных добавлений два: взаимная согласованная регистрация изображений ( с расширением преобразования подобия до проективнгого преобразования и корректная обработка движущихся объектов (часто на панорамных изображениях переещающийся объект, например человек виден как 1 или 2 полупрозрачных призрака, иногда пол-человека). Если применить алгоритм из второй статьи - все сохранится, но будет выигрыш в скорости и расходе памяти.
На основе оптического потока:Классика как детектирования характеристических точек, так и совмещения изображений с субпиксельной точностью. Простейшая модель преобразования (сдвиг). Очень ясно написана. ТАк же как и первая статья, но поиск преобразования - афинная модель (6 параметров). То же, что и предыдущая статья, но гораздо детальнее и подробнее. Интересное математическое приложение про блочные матрицы. Та же идея, что и в предыдущих статьях, но максимально полная модель - поиск проективного преобразования (8 параметров), подход по пирамиде детальности, что расширяет диапазон применимости: все методы оптичеаского потока работают только в малых отклонениях, сваливаются в ближайший локальный минимум. Пирамида детальности частично эту проблему снимает. Кроме того предлагается другой алгоритм глабальной регистрации (используются оба -сначала глобальная регистрация, потом доуточнение до субпиксельной точности). Глобальнгый алгоритм интересен тем, что похож на то, как видит человек.
На основе характеристических точек:Один из алгоритмов наиболее развиваемого в настоящее время подхода - по характеристическим точкам. Освещены все основные этапы. По статье - алгоритм превосходит упомянутые выше, кроме более позднего алгоритма (Zokai, Wolberg 2005)в котором в свою очередь утверждается, что он лучше этого. В значительной степени эффективность алгоритмов совмещения по характеристическим точкам определяется детектором такиъх точек - см. раздел Поиск характеристических точек (уголков, ярких/темных пятен)
Пространство переменных разрешений (Scale Space Theory)
Восстановление 3DЛучший учебник по восстановлению трехмерных сцен. Рассматриваются все аспекты приложения проективной геометрии. Приводится и поясняется большое количество различных алгоритмов, глубоко излагается теория. Одна из первых статей по фундаментальной матрице. Имеет смысл читать, так как многое в более поздних работах опускается как уже известное. Как по имеющейся фундаментальной матрице для пары изображений преобразовать их так, чтобы эпиполярные линии были строго горизонтальны (т.е. переход к виртуальным камерам, оптические оси которых параллельны), соответствующие эпиполярные линии были в одинаковых строках изображений, прямые в 3D линии остаются прямыми. (т.е. переход к задаче стандартного стерео, если же база была сравнима по сравнению с расстоянием до сцены, то алгоритмы стандартного стерео как правило неприменимы, но ректификация все равно работает). В статье приводится новый алгоритм вычисления фундаментальной матрицы. Практически его использование особого смысла не имеет, достаточно 7-точечного алгоритма, погруженного в RANSAC, см. книгу Хартли и Зиссермана (выше). Однако статья замечательна тем, что в ней излагается два методы вычисления погрешности того, что получилось. Это очень важно в том числе и в алгоритмах, приводимых в книге: когда считать, что точка лежит на эпиполярной линии, а когда нет. Также в статье более корректно ставится задача нелинейной минимизации. Вообще говоря хзадача вычисления фундаментальной матрицы обязательно включает 3 этапа: 1) 7-точечный (или любой другой достаточно простой) алгоритм погруженный в RANSAC, 2) после отсева ложных соответствий, вычисление ФМ (например тем же алгоритмом) но уже по все оставшимся верным соответствиям, 3) уточнение полученного результата прямой нелинейной минимизацией. Только после выполнения всех этапов результат можно считать достоверным. В частности, следует упомянуть, что RANSAC служит не только для отсева ложных соответствий, но и таких конфигураций из 7 соответствий, по которым получается слишком неточная матрица или же такая конфигурация вырожденная (например точки в 3D лежат на поверхности второго порядка). Считается, что при наличии точечных соответствий между двумя кадрами можно восстановить фундаментальную матрицу. Если найдены прямые линии и междукадровые соответствия для них, то для двух изображений это не ведет к наложению каких либо ограничений, подобных эпиполярным. Одноко, если такие линии и маждукадровые соответствия известны для трех кадров, то можно найти трифокальный тензор, который ведет даже к более жестким ограничениям, чем эпиполярные. Эта статья замечательна тем, что в ней показывается как на основании прямых линий и соответствий между ними только для двух кадров можно восстановить фундаментальную матрицу. Если в анализируемой трехмерной сцене присутствуют плоскости и их удалось обнаружить, то по известным гомографиям можно вычислить фундаментальную матрицу. В сатье показано как это сделать и какова будет точность. В частности показано, что если сцена состоит из большого числа фрагментов плоскостей, то стандартные по-точечные методы обеспечат лучшую точность, однако, если плоскостей всего 2, то точность будет выше. Выходя за рамки этой статьи, следует сказать, что после выявления гомографий, их можно уточнить методами совмещения изображений с помощью алгоритмов оптического потока (см. соответствующий раздел на этой странице) до субпиксельной точности совмещения. Такая процедура может дать лучшую точность, чем на основе оценки гомографии и фундаментальной матрицы по характеристическим точкам, так как при существенном изменении угла наблюдения характеристические точки могут смещаться относительно истинного положения. Другой интерес к этой работе может вызывать существование 6-точечного алгоритма восстановления фундаментальной матрицы (требуется, чтобы 4 точки их этих 6 гарантированно лежали на плоскости в 3D). Если в составе трехмерной сцены обнаружена всего одна плоскость, но занимающая значительную часть сцены, то дальнейший поиск ФМ c помощью 6-точечного алгоритма будет существенно быстрее для процедуры RANSAC, а при точном определении гомографии, наведенной этой плоскостью есть шансы получить и лучшую точность восстановления ФМ. Хороший алгоритм стерео на графах.
RANSAC
Mean-ShiftReviewsСм. также страницу автора: http://homes.esat.kuleuven.be/~tuytelaa/. Хороший обзор детекторов от классика. Большой список литературы. Рассмотрено много разных детекторов. Даны пояснения, рекомендации по выбору детектора для конкретных задач. Указаны сильные и слабые стороны. Хороший обзор методов Shape From Shading. Приводятся результаты полученные путем обработки одних и тех же данных различными алгоритмами - как картинки, так и цифры: времч, точность. Видно, что результат как правило не предсказуем, идеального и надежного алгоритма нет. Однако следует иметь в виду, что при восстановлении некоторых трехмерных сцен по изображениям другого пути нет, в частности, для матовых одноцветных гладких поверхностей (как гипсовые скульптуры и барельефы) алгоритмы основаннные на триангуляции (в т.ч. на характеристических точках) работать не будут, так как точек там просто нет!
|
