Документ взят из кэша поисковой машины. Адрес оригинального документа : http://imaging.cs.msu.su/~yurin/basic_literature.html
Дата изменения: Mon Feb 1 17:22:25 2010
Дата индексирования: Sat Apr 9 22:46:09 2016
Кодировка: Windows-1251
Imaging lab: people
Home     People     Activities     Research     Publications    

 

Yurin's home page

My graduate students

How to program

Basic Literature

Important links

Some notes on Computer Vision topics

Current C++ codes

Research problems for students

Dmitry V. Yurin personal page

Основная литература:

 

Приведенный здесь список литературы не претендует на полноту в каком либо-смысле: ни по охвату тем, ни по всестороннему освещению темы и ее подтем, ни по полноте литературы по какой либо теме. Наоборот, основной принцип - минимализм. Т.е. приводится литература только по некоторым областям обработки изображений, и только та, которая затрагивает наиболее важные аспекты и наиболее перспективные методы. Естественно присутствует значительная доля субъективности: отбор тем определяется моими интересами, а набор ссылок по теме отражает мое личное мнение.

 

Численные методы
Основы обработки изображений (книги, учебники)
Алгоритмы Брезенхэма
Фильтрация
Поиск характеристических особенностей на изображениях
   Поиск характеристических точек (уголков, ярких/темных пятен)
   Выделение границ
   Поиск прямых линий на изображениях
   Прочие характеристические особенности
Совмещение изображений (Image Registration)
   На основе интегральных преобразований:
   На основе оптического потока:
   На основе характеристических точек:
Пространство переменных разрешений (Scale Space Theory)
Восстановление 3D
RANSAC
Mean-Shift
Reviews

 

Численные методы

  • Дж.Форсайт, М.Малькольм, К.Моулер. Машинные методы математических вычислений. // М.:Мир. 1980. 280 стр. Пер. с англ. Х.Д.Икрамова. \n Оригинал: George E. Forsythe, Michael A. Malcolm. Cleve B. Moler. Computer Methods for Mathematical Computations. //Prentice-hall, inc. Englrwood clifs, N.J. 07632. 1977.

    На мой взгляд, именно в этой книге и именно в ее старом издании наиболее понятно изложено применение сингулярного разложения матриц для решения задачи наименьших квадратов с регуляризацией (глава 9). Решение пере- и недоопределенных системы алгебраических линейных уравнений. Рассмотрены все важные аспекты, связанные с сингулярным разложением, даны четкие пояснения и численные примеры: необходимость нормировки данных перед применением сингулярного разложения, какие именно сингулярные числа следует занулять (регуляризация), нуль-пространство и построение общего решения (с произвольными параметрами) для недоопределенных линейных систем. Единственная неточность - при описании регуляризации не сказано, что это связано с теорией возмущений для сингулярных чисел и векторов и не приведена формулировка теоремы Вейля. Об этом можно прочитать в книге
    Дж.Деммель. Вычислительная линейная алгебра. Теория и приложения. / Пер с англ. -М.Мир, 2001. -430с. ил. ISBN 5-03-003402-1
    Кроме того - в параграфе 2.6 очень поучительный разбор численного решения квадратного уравнения. Показано, что это нельзя делать по "школьной формуле", откуда и какие берутся ошибки округления, как их обойти и как делать правильно. Много численных примеров.


  • Press et al, "Numerical recipes in C", Cambridge University Press, 1992.

    Замечательный учебник по численным методам, содержащий также полные тексты всех описываемых вычислительных процедур на С. На самом деле - библиотека программ с документацией-учебником. Описание математических принципов достаточно подробно, хотя может быть не столь строго, как в некоторых отечественных учебниках. Достоинствами книги являются тексты программ и необычайно широкий охват различных областей вычислительной математики. Это и интегрирование, и решение линейных алгебраических и дифференциальных уравнений, и разложения матриц, и нелинейные методы минимизации, включая многомерные, и вычисление спец. функций, и методы наименьших квадратов и многое, многое другое. Все приводимые процедуры в достаточной степени замкнутые и автономные. Код хорошо документирован, наряду и с математическим описанием алгоритма в соответствующем параграфе. Таким образом, код полностью можно понять. Может быть, качество кода несколько уступает таким классическим библиотекам как NAG, LAPACK, NETLIB, но в данном случае достоинство понятность кода и автономность - редко какая функция использует более 1-3 других. Кроме того, процедуры из этой книги очень часто используются в научных публикациях (использовалась процедура ... из Numerical Recipes).


  • Н.Вирт АЛГОРИТМЫ + СТРУКТУРЫ ДАННЫХ = ПРОГРАММЫ. М.: Мир. 1977.

    Хорошая книга по классическим алгоритмам: сортировка, деревья. Показано, как по массиву можно найти медиану быстрее, не выполняя полную сортировку массива.


  • Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы. Построение и анализ. 2-е издание. Издательство: Вильямс, 2005 г. 1296 стр. ISBN 5-8459-0857-4, 0-07-013151-1

    Сортировки, деревья, алгоритмы на графах, динамическое программирование, жадные алгоритмы, вычислительная сложность, NP-полные задачи, оптимальный алгоритм перемножения нескольких матриц и многое другое. Стандартный и классический учебник по Computer Science за рубежом. Очень хорошо написан. Образцовый стиль описания алгоритмов.


  • Брэйсуэлл Р., "Преобразование Хартли. Теория и приложения", Москва "Мир", 1990, ISBN 5-03-001632-5 .

    Полностью эквивалентно преобразованию Фурье для случая вещественных сигналов, но вычислительно гораздо эффективнее (меньше требует памяти, работает быстрее).


  • Ю.Люк. Специальные математические функции и их аппроксимации. /Пер. с англ. Г.П.Бабенко под ред. К.И.Бабенко. -М.:Мир 1980. -608 с.

  • М.Абрамовиц, И.Стиган. Справочник по специальным функциям с формулами, графиками, таблицами. /Пер. с англ. под ред. В.А.Диткина и Л.Н.Кармазиной. -М.:Наука 1979. -832 с, с ил.

    Последние две книги - справочники, но не стоит ими пренебрегать. Например:
    1) алгоритм быстрой свертки с Гауссом (ниже) построен именно на аппроксимирующей формуле из второй книги;
    2) предположим требуется новая спец. функция - интеграл от нуля до x от функции Бесселя нулевого порядка. Численное интегрирование - долгая и сложная процедура (функция осциллирующая и знакопеременная!). А в первой книге есть аппроксимация с точностью до 1.5e-8, надо только 20-40 умножений и однократно вычислить sin, cos и sqrt.
    Много информации также по статистическим различным распределениям. В частности во второй книге есть определение и разные аппроксимации и ассимптотики для процентных точек распределения Стьюдента (очень полезно при обработке данных с погрешностями).

  •  

    Основы обработки изображений (книги, учебники)

  • У. Прэтт. Цифровая обработка изображений: Пер с англ. -М.:Мир,1982. 790 C. в 2 т.

  • Л.Шапиро, Дж.Стокман. Компьютерное зрение //Пер. с англ. -М.:БИНОМ. Лаборатория знаний, 2006. -752 с.,8 с.ил.: ил.

  •  

    Алгоритмы Брезенхэма

  • Уилтон Р. Видеосистемы персональных компьютеров IBM PC и PS/2. Руководство по программированию/ Пер. с англ. К.Г.Смирнова; Под ред. В.Л.Григорьева. - М.: Радио и связь, 1994. -384 с.:ил.

    В целом книга устарела и не представляет интереса. Но в ней содержится описание алгоритмов Брезенхэма рисования прямых линий, эллипсов, заливки (закраски) областей. Эти алгоритмы показывали впечатляющую производительность еще древних компьютерах. Отказываться от них сегодня было бы неверно. На самом деле графические библиотеки и встроенные в железо процедуры реализуют именно эти алгоритмы. Если требуется выполнять похожие операции при обработке изображений, незнание не может служить извинением.
  •  

    Фильтрация

  • Л.П.Ярославский, Цифровая обработка сигналов в оптике и голографии. Введение в цифровую оптику. -М.:Радио и связь, 1987. 296 с.:ил. УДК 681.3:535.

    Лучшее описание ранговых алгоритмов целиком, а не только медианной фильтрации, которая есть только один и простейший из этой группы.

  • Carlo Tomasi,Roberto Manduchi. Bilateral Filtering for Gray and Color Images. //In Proc. of the Sixth International Conference on Computer Vision (ICCV), Bombay, India, January 1998. -P.839-846, PDF

    Еще один алгоритм, который может быть отнесен к классу ранговых алгоритмов. Ссылка на статью приводится в связи с тем, что в последнее время этот алгоритм становится все более популярным. Качество результата хорошее.

  • I.T. Young, L.J. van Vliet 'Recursive implementation of the gaussian filter' // Signal Processing (44), pp. 139-151, 1995.

    Алгоритм быстрого вычисления свертки с функцией Гаусса и ее первыми тремя производными. Независимо от величины сигма, на каждую точку данных требуется примерно 12 умножений.

  • A.Lukin "Tips&Tricks: Fast Image Filtering Algorithms" // Proceedings of GraphiCon'2007, Moscow, Russia, June 2007, pp. 186-189. PDF, 163 Kb

    Отличный обзор по быстрой реализации ряда фильтров.

  • William T. Freeman, Edward H. Adelson Y. The Design and Use of Steerable Filters //IEEE Transactions on Pattern Analysis and Machine Intelligence, 1991, -V.13, -P.891-906. PDF

  • Ben Weiss. Fast median and bilateral filtering//ACM Transactions on Graphics (TOG, Proceedings of the ACM SIGGRAPH'06 Conference), July 2006. -V.25, No.3, -P.519-526. ISSN:0730-0301. Page & PDF & Slides & Movies

    Фантастически быстрый алгоритм вычисления медианной фильтрации.

  • Y.Deng, S.Kenney, M.S.Moore and B.S.Manjunath, "Peer group filtering and perceptual color image quantization", Proc. IEEE International Symposium on Circuits and Systems VLSI , (ISCAS'99), Orlando, FL, vol 4, pp.21-4 , June 1999. PDF

    Перевод изображения из TrueColor в индексное с отличным качеством. Хорошо во всяких задачах классификации и сегментации, остаются только важные цвета, причем в смысле похожем на понимание человека. Алгоритм медленный, на счет быстрой реализации мне не известно.

  • Ilia Safonov. Automatic Correction of Amateur Photos Damaged by Backlighting// Proceedings of GraphiCon'2006, Novosibirsk, Akademgorodok, Russia, July 2006, pp. 80-89. PDF

    Существенно выравниваются яркости изображений: яркие объекты-темные объекты. Качество хорошее.

  •  

     

     

    Поиск характеристических особенностей на изображениях

     

    Поиск характеристических точек (уголков, ярких/темных пятен)

  • C. G. Harris and M. Stephens, "A combined corner and edge detector," In Proc. 4th Alvey Vision Conf., Manchester, pages 147-151, 1988. PDF
  • C. Tomasi and T. Kanade. Shape and Motion from Image Streams: a Factorization Method - Part 3 Detection and Tracking of Point Features. //Tech. report CMU-CS-91-132, Computer Science Department, Carnegie Mellon University, April, 1991. PDF

    Предыдущие две статьи - два классических детектора характеристических точек. Очень похожи, отличие в том, что в первой не надо вычислять квадратный корень (только умножения и сложения). Европейцы предпочитают Харриса, американцы - Канаде-Лукаса (вторая статья). На сегодняшний день в чистом виде использовать не следует, но современные ScaleSpace детекторы построены как правило на базе этих двух классических.

  • David G. Lowe, "Object recognition from local scale-invariant features," International Conference on Computer Vision, Corfu, Greece (September 1999), pp. 1150-1157. PDF
  • D.G. Lowe. Distinctive image features from scale-invariant keypoints. //International Journal of Computer Vision 2004, -V. 60, -No. 2, -P. 91-110. PDF.

    Предыдущие две статьи описывают лучший на сегодняшний день детектор характеристических точек, естественно ScaleSpace. Вообще говоря, по современным представлениям детектор точек должен состоять из следующих трех этапов: 1) построение ScaleSpace и детектирование точек на каждом уровне детальности; 2) уточнение положения точки до субпиксельной точности и выбор разрешения на котором она проявляется наилучшим образом; 3) построение вектора параметров, описывающего точку так, чтобы при выполнении сопоставления точек на двух (или более) изображениях можно было просто считать расстояния между такими векторами параметров по некоторой метрике, для тех точек для которых такое расстояние минимально считается, что они соответствуют друг другу.
    Детектор SIFT замечателен именно третьим этапом. Первый этап - реализован простейшим образом, добивались максимального быстродействия. Второй этап - стандартный, обчно так делают все.

  • K. Mikolajczyk, C. Schmid. Scale & Affine Invariant Interest Point Detectors. //International Journal of Computer Vision. -V. 60, -No. 1, -P. 63-86, October 2004. PDF.

    Наоборот, в этом детекторе первый и второй этапы максимально проработаны. Третий этап существенно уступает по качеству SIFT, хотя используется весьма красивая и математически глубоко проработанная теория дифференциальных инвариантов. Векторы параметров получаются более похожими для различных объектов. Причина видимо в том, что дифференциальные инварианты считаются в точке, в то время как SIFT строит вектор параметров эмпирически, по сути - локальные гистограммы градиента яркости по окрестности точки. Размерность вектора параметров в этом детекторе около 10, а у SIFT - 128. Статья хороша очень детальной проработкой первых двух этапов.

  • A. Baumberg. Reliable feature matching across widely separated views. //In Proc. CVPR, pages 774--781, 2000. PDF.

    Аналогично предыдущей статье, приняты все меры по улучшению точности детектирования и достижению аффинной инваниантности. Дескрипторы - другие, инвариантные к вращению. Построены на основе преобразования Фурье-Меллина.

  • G. J. Burghouts and J. M. Geusebroek. Performance evaluation of local colour invariants // Comput. Vision Image Understanding 2009, -V. 113, -P.48-62. PDF.

    См. также страницу автора:
    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 требуется внести минимальные изменения.

  • Tinne Tuytelaars and Krystian Mikolajczyk (2008) "Local Invariant Feature Detectors: A Survey", Foundations and TrendsR in Computer Graphics and Vision: Vol. 3: No 3, pp 177-280. http://dx.doi.org/10.1561/0600000017 PDF.

    См. также страницу автора:
    http://homes.esat.kuleuven.be/~tuytelaa/.

    Хороший обзор детекторов от классика. Большой список литературы. Рассмотрено много разных детекторов. Даны пояснения, рекомендации по выбору детектора для конкретных задач. Указаны сильные и слабые стороны.

  • Krystian Mikolajczyk, Cordelia Schmid. A performance evaluation of local descriptors //IEEE Transactions on Pattern Analysis and Machine Intelligence. Oct. 2005. -V.27, -No.10, -P.1615-1630. PDF. PDF. PDF. PDF.

    Предложен дескриптор GLOH. Срвниваются:
    - GLOH,
    - SIFT,
    - Shape context,
    - PCA-SIFT,
    - Moments,
    - Cross correlation,
    - Steerable filters,
    - Spin images,
    - Differential invariants,
    - Complex filters.
    Очень важная статья.

  • V. Gouet, P. Montesinos and D. Pele. A fast matching method for color uncalibrated images using differential invariants. //In Proceedings of the British Machine Vision Conference, Southampton, 1998. PDF.

    Статья посвящена несколько иной теме: в качестве дескрипторов характеристических точек используются дифференциальные инварианты. Изображения цветные - поэтому инварианты считаются для различных цветовых компонент. Основной акцент в статье сделан на решение следующей задачи: есть 2 изображения, часть точек уже верно сопоставлена. Как найти и сопоставить дополнительные точки с минимальными затратами. Имеются в виду такие характеристические точки, которые на первом этапе сопоставить не удалось, так как по дескриптору - на другом изображении было много кандидатов, а теперь уже восстановлена эпиполярная геометрия и сопоставление производится с наложением эпиполярных ограничений.

  •  

    Выделение границ

  • Canny J. A computational approach to edge detection // IEEE Trans. PAMI. 1986. V. 8. P. 34-43. PDF, более подробный технический отчет, чем сама сатья.

    Классическая и самая главная статья по выделению границ. Основные моменты: классификация типов границ (step edge, roof edge, etc.). Использование модуля градиента яркости для обнаружения step edge. Градиенты вычисляются путем свертки с производной функции Гаусса. Основная структура: модуль градиента -> non maxima supression -> гистерезисное ограничение.

  • Di Zenzo S. "A note on the gradient of multi-image", Computer Vision Graphics Image Process, Vol. 33. pp. 116-125, 1986
  • A. Cumani, 'Edge Detection in Multispectral Images,' Computer Vision, Graphics and Image Processing: Graphical Models Image Processing, 53, 1, January 1991, 40-51. Postscript, IEN Technical Report #373, April 1989  ,  Aldo Cumani's Home Page

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

  • F. Devernay. "A Non-Maxima Suppression Method for Edge Detection with Sub-Pixel Accuracy", INRIA techreport RR-2724, 20 pages, PDF

    Отчет поясняет как процедуру Non Maxima Supression в трех предыдущих статьях можно выполнить с субпиксельной точностью.

  • Florack, L. M. J., ter Haar-Romeny, B. M., Koenderink, J. J., Viergever, M. A. Scale and the Differential Structure of Images. //Image and Vision Computing, July/August 1992, -V. 10, -No. 6, -P. 376-388. PDF

    В этой статье надо на страницах 384-385 смотреть почему плох оператор Лапласа в качестве детектора границ - смещение границы на величину пропорциональную локальной кривизне изолинии (обычно совпадает с кривизной границы).

  • Tony Lindeberg. Scale selection for differential operators. Technical report, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, S-100 44 Stockholm, Sweden, Jan. 1994. (ISRN KTH NA/P--94/05--SE). Shortened version in Proc. 8th Scandinavian Conference on Image Analysis, (Tromso, Norway), pp. 857--866, May 1993. PDF

  • Tony Lindeberg. Edge Detection and Ridge Detection with Automatic Scale Selection //Technical report ISRN KTH NA/P--96/06--SE. Department of Numerical Analysis and Computing Science, Royal Institute of Technology, S-100 44 Stockholm, Sweden, Jan 1996. //International Journal of Computer Vision, vol. 30, number 2, pp. 117--154, 1998. //Shortened version in Proc. IEEE Conf. on Computer Vision and Pattern Recognition, CVPR'96, San Francisco, California, june 1996, pages 465--470. //Shortened version in Linde, Sparr (Eds.): Proc. Swedish Symposium on Image Analysis, SSAB'96, Lund, Sweden, pages 24--28, march 1996. PDF

    В статьях Canny, Di Zenzo, Cumani производные по x,y от яркости изображения вычисляются путем свертки изображения с первой производной функции Гаусса. Величина сигма задается с потолка (на основе имеющейся априорной информации). Понятно, что на реальных изображениях границы размытые и нечеткие. Насколько - неизвестно. Поэтому важно правильно выбирать масштаб вычисления производной (величина сигма), и не одинаково для всего изображения, а адаптивно, для каждой точки изображения. Последние две статьи посвящены как раз этой проблеме. Основная - последняя, предыдущая - в качестве дополнительного пояснения. Подробнее см. раздел "Scale Space Theory".

  • 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

    Обнаружение границ на цветных изображениях. Границы инвариантные к теням, бликам, условиям освещения.

  • Таким образом, по современным представлениям детектор границ (Edge detector, Step edge) должен быть устроен следующим образом:

    - выбор метода детектирования согласно целевой задаче:
    -- Если изображение серое - то по статье Канни
    -- Если изображение цветное, то если требуется найти все линии, то по Кумани, если требуется исключить влияние освещения, бликов, и т.п. - выбрать один из методов согласно статье Гернсброека.
    -- Процедуры выделения хребтов на аналогах "модуля градиента", и, если надо, гистерезисного ограничение - согласно статье Канни.
    - Выбранная процедура должна быть погружена в методику Scale Space, в каждой точке масштаб для найденной линии выбирается таким, на котором граница проявляется наилучшим образом.
    PS: В отношении реализации свертки с функциями Гаусса и ее производными - см. статью о быстрой свертке с Гауссом в разделе Фильтрация
    PPS: Процедуру Non Maxima Supression следует выполнять согласно отчету Frederic Devernay (4-я статья в списке).
    PPPS: О неточности найденных границ - можно прочитать в статье:
  • Кравцов А.A., Сидоркина О.C., Юрин Д.В. "Модифицированный рэлеевский детектор слабоконтрастных границ двумерных объектов на изображении" // Труды конференции Графикон 2006, 16-я международная конференция по компьютерной графике и ее приложениям, Россия, Новосибирск, Академгородок, 1-5 июля 2006. -С.351-354. PDF, 403 Kb (in Russian)
  •  

    Поиск прямых линий на изображениях

  • Cheyne Gaw Ho, Rupert C. D. Young, Chris D. Bradfield, Chris R. Chatwin, 'A Fast Hough Transform for the Parametrisation of Straight Lines using Fourier Methods', Real-Time Imaging, vol.6, num.2, pp.113-127, 2000
  • Volegov D.B., Gusev V.V., Yurin D.V. 'Straight Line Detection on Images via Hartley Transform. Fast Hough Transform, In Conference Proceedings. 16-th International Conference on Computer Graphics and Application GraphiCon'2006, July 1 - 5, 2006, Novosibirsk, Akademgorodok, Russia. PDF.

    Вторая статья - 100% перенос перовой с преобразования Фурье на преобразование Хартли. Выигрыш в затратах памяти и быстродействии. Других серьезных отличий нет. По функциональности и свойствам подходы полностью эквивалентны. Относительно предварительного выделения границ на изображении перед применением процедуры Быстрого преобразования Хафа - см. раздел Выделение границ, это особенно нужно для цветных изображений, кроме того во всех случаях методика ScaleSpace делает результат поиска линий более обоснованным и менее подверженным шуму.

  •  

    Прочие характеристические особенности

  • J. Matas, O. Chum, U. Martin, T Pajdla. Robust wide baseline stereo from maximally stable extremal regions. //Proceedings of the British Machine Vision Conference, -V. 1, -P. 384-393, London, 2002. PDF.

    Похоже на характеристические точки, но не точки, а маленькие сегменты, существенно отличающиеся по цветояркостным характеристикам от окружения. Признана лучшей статьей на конференции BMVC2002.

  •  

     

     

    Совмещение изображений (Image Registration)

     

    На основе интегральных преобразований:

  • B.S. Reddy, B.N. Chatterji, "An FFT-based technique for translation, rotation, and scale-invariant image registration", IEEE PAMI, Vol. 5(8), pp. 1266-1271, August, 1996.

    Классическая работа, классический метод. Ищется преобразование подобия: сдвиг, поворот, масштабирование. Все на основе преобразования Фурье.

  • Dmitry Yurin. Image Registration: Color Image Synthesis from Data Obtained from Satellites Pushbroom Cameras // In Conference Proc. The 18th International Conference on Computer Graphics and Vision GraphiCon'2008, June 23-27, 2008, Moscow, Russia. -P.142-150. PDF

    В этой работе алгоритм из предыдущей статьи перенесен на преобразование Хартли, что дает значительное ускорение и экономию памяти, особенно, если требуется взаимно совмещать более 2-х изображений. Кроме того предложен новый алгоритм поискадругой модели преобразования: сдвиг и перекос (skew). Детально описаны процедуры, которые надо выполнять до и после преобразования Хартли (как впрочем и для фурье), чтобы избежать появления артефактов связанных с краями изображения и его конечным размером.

  • James Davis. Mosaics of scenes with moving objects. In Proc. Computer Vision and Pattern Recognition Conf., pages 354--360, 1998. PDF.

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

  •  

    На основе оптического потока:

  • C. Tomasi and T. Kanade. Shape and Motion from Image Streams: a Factorization Method - Part 3 Detection and Tracking of Point Features. //Tech. report CMU-CS-91-132, Computer Science Department, Carnegie Mellon University, April, 1991. PDF.

    Классика как детектирования характеристических точек, так и совмещения изображений с субпиксельной точностью. Простейшая модель преобразования (сдвиг). Очень ясно написана.

  • Jianbo Shi and Carlo Tomasi, "Good features to track", IEEE Conference on Computer Vision and Pattern Recognition (CVPR'94) (Seattle), June 1994, P. 593-600. PDF.

    ТАк же как и первая статья, но поиск преобразования - афинная модель (6 параметров).

  • J. Shi and C. Tomasi. Good features to track. Technical Report TR-93-1399, Cornell University, November 1993. PDF

    То же, что и предыдущая статья, но гораздо детальнее и подробнее. Интересное математическое приложение про блочные матрицы.

  • Siavash Zokai, George Wolberg. Image Registration Using Log-Polar Mappings for Recovery of Large-Scale Similarity and Projective Transformations //IEEE Transactions on Image Processing, Vol. 14, No. 10, October 2005. PDF

    Та же идея, что и в предыдущих статьях, но максимально полная модель - поиск проективного преобразования (8 параметров), подход по пирамиде детальности, что расширяет диапазон применимости: все методы оптичеаского потока работают только в малых отклонениях, сваливаются в ближайший локальный минимум. Пирамида детальности частично эту проблему снимает. Кроме того предлагается другой алгоритм глабальной регистрации (используются оба -сначала глобальная регистрация, потом доуточнение до субпиксельной точности). Глобальнгый алгоритм интересен тем, что похож на то, как видит человек.

  •  

    На основе характеристических точек:

  • Y. Dufournaud, C. Schmid, and R. Horaud, "Matching images with different resolutions", Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR'00), 2000 (Hilton Head Island, SC, USA). -V. 1, -P. 612-618. ISBN: 0-7695-0662-3. PDF

    Один из алгоритмов наиболее развиваемого в настоящее время подхода - по характеристическим точкам. Освещены все основные этапы. По статье - алгоритм превосходит упомянутые выше, кроме более позднего алгоритма (Zokai, Wolberg 2005)в котором в свою очередь утверждается, что он лучше этого. В значительной степени эффективность алгоритмов совмещения по характеристическим точкам определяется детектором такиъх точек - см. раздел    Поиск характеристических точек (уголков, ярких/темных пятен)

  •  

    Пространство переменных разрешений (Scale Space Theory)

  • Witkin A.P. Scale-Space Filtering. //Proceedings of the 8:th International Joint Conference on Artificial Intelligence, Karlsruhe, West Germany, 1983, August 8-12, -P. 1019-1022.
  • Koenderink J.J., van Doorn A.J. The Structure of Images //Biological Cybernetics 1984, Vol. 50, -P.363-370.
  • Koenderink J.J., van Doorn A.J. Representation of Local Geometry in the Visual System. //Biological Cybernetics 1987, -V.55, -P.367-375.
  • Tony Lindeberg: Scale-Space Theory in Computer Vision, Kluwer Academic Publishers, Dordrecht, Netherlands, 1994. См. также PDF Lindeberg, Tony. Scale-space theory: A basic tool for analysing structures at different scales. //Journal of Applied Statistics,21, 2 (1994), pp. 224-270.
  • Lindeberg, Tony. Detecting salient blob-like image structures and their scales with a scale-space primal sketch: a method for focus-of-attention //International Journal of Computer Vision,11, 3 (1993), pp. 283-318.
  • Lindeberg and Garding: Shape-adapted smoothing in estimation of 3-D depth cues from affine distortions of local 2-D brightness structure, //Image and Vision Computing 1997, -V. 15, -P. 415--434. PDF
  • C. Schmid, R. Mohr. Local Grayvalue Invariants for Image Retrieval. //IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI) 1997, -V. 19, -No. 5, -P. 530-534. PDF
  • Florack, L. M. J., ter Haar-Romeny, B. M., Koenderink, J. J., Viergever, M. A. Scale and the Differential Structure of Images. //Image and Vision Computing, July/August 1992, -V. 10, -No. 6, -P. 376-388. PDF
  • L.M.J. Florack, B.M. Ter Haar Romeny, J.J. Koenderink, and M.A. Viergever/ General Intensity Transformations and Differential Invariants. //Journal of Mathematical Imaging and Vision, vol. 4, no. 2, 171-187 (1994). PDF
  •  

    Восстановление 3D

  • R. Hartley, A. Zisserman. Multiple View Geometry in Computer Vision. Cambridge University Press 2004, 672 p., ISBN: 0521540518.

    Лучший учебник по восстановлению трехмерных сцен. Рассматриваются все аспекты приложения проективной геометрии. Приводится и поясняется большое количество различных алгоритмов, глубоко излагается теория.

  • Краткое пояснение по достижимой точности восстановления 3D по стерео PDF

  • Математический вывод фундаментальной матрицы. Что и откуда берется, математические подробности.PDF

  • Сайт с публикациями Хартли.

  • Сайт Visual Geometry Group Оксфорд, Великобритания.

  • H.C. Longuet-Higgins. A Computer Algorithm for Reconstructing a Scene From Two Projections," Nature, vol. 293, pp. 133-135, Sept 1981.

    Одна из первых статей по фундаментальной матрице. Имеет смысл читать, так как многое в более поздних работах опускается как уже известное.

  • Richard I. Hartley. Theory and Practice of Projective Rectification //International Journal of Computer Vision 1999. -V.35. -No.2. -P.115-127.PDF.

    Как по имеющейся фундаментальной матрице для пары изображений преобразовать их так, чтобы эпиполярные линии были строго горизонтальны (т.е. переход к виртуальным камерам, оптические оси которых параллельны), соответствующие эпиполярные линии были в одинаковых строках изображений, прямые в 3D линии остаются прямыми. (т.е. переход к задаче стандартного стерео, если же база была сравнима по сравнению с расстоянием до сцены, то алгоритмы стандартного стерео как правило неприменимы, но ректификация все равно работает).

  • Gabriella Csurka, Cyril Zeller, Zhengyou Zhang, Olivier D. Faugeras. Characterizing the Uncertainty of the Fundamental Matrix //Computer Vision and Image Understanding: CVIU 1997, -V.68, -No.1,-P.18-36, PDF.

    В статье приводится новый алгоритм вычисления фундаментальной матрицы. Практически его использование особого смысла не имеет, достаточно 7-точечного алгоритма, погруженного в RANSAC, см. книгу Хартли и Зиссермана (выше). Однако статья замечательна тем, что в ней излагается два методы вычисления погрешности того, что получилось. Это очень важно в том числе и в алгоритмах, приводимых в книге: когда считать, что точка лежит на эпиполярной линии, а когда нет. Также в статье более корректно ставится задача нелинейной минимизации. Вообще говоря хзадача вычисления фундаментальной матрицы обязательно включает 3 этапа: 1) 7-точечный (или любой другой достаточно простой) алгоритм погруженный в RANSAC, 2) после отсева ложных соответствий, вычисление ФМ (например тем же алгоритмом) но уже по все оставшимся верным соответствиям, 3) уточнение полученного результата прямой нелинейной минимизацией. Только после выполнения всех этапов результат можно считать достоверным. В частности, следует упомянуть, что RANSAC служит не только для отсева ложных соответствий, но и таких конфигураций из 7 соответствий, по которым получается слишком неточная матрица или же такая конфигурация вырожденная (например точки в 3D лежат на поверхности второго порядка).

  • C. Sagues, A.C. Murillo, F. Escudero and J.J. Guerrero. From lines to epipoles through planes in two views //Pattern Recognition, Volume 39, Issue 3, March 2006, Pages 384-393., PDF.

    Считается, что при наличии точечных соответствий между двумя кадрами можно восстановить фундаментальную матрицу. Если найдены прямые линии и междукадровые соответствия для них, то для двух изображений это не ведет к наложению каких либо ограничений, подобных эпиполярным. Одноко, если такие линии и маждукадровые соответствия известны для трех кадров, то можно найти трифокальный тензор, который ведет даже к более жестким ограничениям, чем эпиполярные.
    Эта статья замечательна тем, что в ней показывается как на основании прямых линий и соответствий между ними только для двух кадров можно восстановить фундаментальную матрицу.

  • Luong, Q.-T. Faugeras, O.D. Determining the fundamental matrix with planes: instability and newalgorithms //Proceedings on CVPR 1993. -P.489-494. PDF.

    Если в анализируемой трехмерной сцене присутствуют плоскости и их удалось обнаружить, то по известным гомографиям можно вычислить фундаментальную матрицу. В сатье показано как это сделать и какова будет точность. В частности показано, что если сцена состоит из большого числа фрагментов плоскостей, то стандартные по-точечные методы обеспечат лучшую точность, однако, если плоскостей всего 2, то точность будет выше.
    Выходя за рамки этой статьи, следует сказать, что после выявления гомографий, их можно уточнить методами совмещения изображений с помощью алгоритмов оптического потока (см. соответствующий раздел на этой странице) до субпиксельной точности совмещения. Такая процедура может дать лучшую точность, чем на основе оценки гомографии и фундаментальной матрицы по характеристическим точкам, так как при существенном изменении угла наблюдения характеристические точки могут смещаться относительно истинного положения. Другой интерес к этой работе может вызывать существование 6-точечного алгоритма восстановления фундаментальной матрицы (требуется, чтобы 4 точки их этих 6 гарантированно лежали на плоскости в 3D). Если в составе трехмерной сцены обнаружена всего одна плоскость, но занимающая значительную часть сцены, то дальнейший поиск ФМ c помощью 6-точечного алгоритма будет существенно быстрее для процедуры RANSAC, а при точном определении гомографии, наведенной этой плоскостью есть шансы получить и лучшую точность восстановления ФМ.

  • V. Kolmogorov and R. Zabih. Computing visual correspondence with occlusions using graph cuts. In International Conference on Computer Vision, Vancouver, Canada, July 2001. PDF.

    Хороший алгоритм стерео на графах.

  • Michael H. Lin, Carlo Tomasi: Surfaces with Occlusions from Layered Stereo. //IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2003.

  • S. Birchfield and C. Tomasi. Multiway cut for stereo and motion with slanted surfaces. Proceedings of the Seventh IEEE International Conference on Computer Vision, Kerkyra, Greece, September 1999, pp. 489--495. PDF.

  •  

    RANSAC

  • M. Fischler and R. Bolles. Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography. //Communications of the ACM, -V. 24. -No. 6. -P.381-395, June 1981.

  • P.H.S.Torr, A.Zisserman. MLESAC: A New Robust Estimator with Application to Estimating Image Geometry. //Computer Vision and Image Understanding, vol. 78, pp. 138-156, 2000. PDF

  • A. Konouchine, V. Gaganov, V. Veznevets. AMLESAC: A New Maximum Likelihood Robust Estimator. //Proc. of 15-th International Conference on Computer Graphics and Applications (GraphiCon'2005). Novosibirsk Akademgorodok, Russia, June 20 - 24, 2005, PDF

  •  

    Mean-Shift

  • D. Comaniciu, V. Ramesh, P. Meer, Real-Time Tracking of Non-Rigid Objects Using Mean Shift. //Proc. IEEE Conf. Computer Vision and Pattern Recognition. June 2000. -V.2, -P.142-149.

  • D. Comaniciu, P. Meer. Mean Shift Analysis and Applications. //IEEE Int'l Conf. Computer Vision (ICCV), Kerkyra, Greece 1999. -P.1197-1203.

  • Reviews

  • Tinne Tuytelaars and Krystian Mikolajczyk (2008) "Local Invariant Feature Detectors: A Survey", Foundations and TrendsR in Computer Graphics and Vision: Vol. 3: No 3, pp 177-280. http://dx.doi.org/10.1561/0600000017 PDF.

    См. также страницу автора:
    http://homes.esat.kuleuven.be/~tuytelaa/.

    Хороший обзор детекторов от классика. Большой список литературы. Рассмотрено много разных детекторов. Даны пояснения, рекомендации по выбору детектора для конкретных задач. Указаны сильные и слабые стороны.

  • Ruo Zhang, Ping-sing Tsai, James Edwin Cryer, Mubarak Shah. Shape from Shading: A survey. //IEEE Transactions on Pattern Analysis and Machine Intelligence 1999. -V.21, -P.690-706. PDF.

    Хороший обзор методов Shape From Shading. Приводятся результаты полученные путем обработки одних и тех же данных различными алгоритмами - как картинки, так и цифры: времч, точность. Видно, что результат как правило не предсказуем, идеального и надежного алгоритма нет. Однако следует иметь в виду, что при восстановлении некоторых трехмерных сцен по изображениям другого пути нет, в частности, для матовых одноцветных гладких поверхностей (как гипсовые скульптуры и барельефы) алгоритмы основаннные на триангуляции (в т.ч. на характеристических точках) работать не будут, так как точек там просто нет!
  • V. Lepetit and P. Fua, Monocular Model-Based 3D Tracking of Rigid Objects: A Survey //Foundations and Trends in Computer Graphics and Vision, October 2005. -V.1, -No.1, -P.1-89. PDF. PDF.

  •