01 – изображение в компьютерном зрении

Что такое изображение?

пример ортографической проекции

пример ортографической проекции

Изображение – результат преобразования трехмерного пространства в двумерное. Каждый пиксель изображения – величина отраженного сценой светом в направлении камеры (есть и другие типы – MRI, рентгеновское излучение, изображения получаемые со всяких хитрых штуковин).

На практике рассматривают два основных вида преобразований:
Перспективная проекция (perspective projection) – вы сами создавали такие проекции с помощью фотоаппарата (об упрощенной модели перспективной проекции часто рассказывают на примере pinhole camera или камеры обскуры
Ортографическая проекция (orthographic projection) – получается, например, с неуправляемых шпионов-беспилотников

Что влияет на формирование изображения?

Свет – где находится источник(и) света, характеристики света.
Камера – где расположена, куда направлена, параметры
Сцена – динамическая или нет, какие отражающие свойства у поверхностей объектов в сцене и т.п.

Хорошее детальное описание процесса формирования изображения может быть найдено много где, например, если на ютубе поискать по строке “Fundamentals of image formation – Computer Vision-Professor Jitendra Malik” – находятся две 15 минутных лекции с картинками и разжевыванием. Как правило, для практических задач принимаются во внимание только параметры камеры, а все остальное списывается на погрешность измерений.

Как изображение “видит” компьютер?

Здесь есть два принципиально разных подхода – дискретный (конечный) набор данных или функция.

1) Бинарное изображение (представлены только два цвета – черный и белый) можно представить в виде числовой матрицы размером n на m. Единички соответствуют черному, а нолики белому цветам. Для представления изображения в градациях серого подойдет такой же двумерный массив, где каждый элемент будет содержать значение интенсивности – от 0 (совсем черный) до 255 (совсем белый). Для цветного изображения – будет уже три таких массива (для каждого из каналов RGB – свой массив). Разрешение изображения – число строк и столбцов. Видео – последовательность таких изображений (30 фреймов в секунду). Каждый пиксель изображения – представление множества точек пространства.

2) Для обработки вышеописанный подход не подходит так как получается медленно и неэффективно. А потому периодически рождались новые методы.

2.0) Можно думать об изображении как о некоторой функции – это может быть значительно удобней для вычислений. Функцию можно разложить с помощью дискретного преобразования Фурье – ДПФ (англ. – DFT, Discrete Fourier Transform). Ускоренный вариант – быстрое преобразование Фурье (англ. – FFT) можно получить за n*lg(n) операций. Зачем? Кратко – для сжатия, подробно – http://psi-logic.shadanakar.org/fft/fft7.htm. Грубо говоря, на выходе мы получим представление нашего сигнала (то бишь изображения) в виде суммы значения производных разных порядков этой функции в этой точке.

представление изображения в виде функции

представление изображения в виде функции

Как правило, сигнал – наше изображение – задан на некотором отрезке возможных значений. Для его представления используется разложение в косинусах с помощью метода – дискретное косинусное преобразование (DCT). На практике, изображение раскладывается на две базисные функции – двумерные синусоиды с разными углами наклона и фазами. Для ускорения разложения используется их декомпозиция на одномерные ДПФ. Используется, например, при сжатии в JPEG.

Так как частичная сумма ряда Фурье будет отличаться от сигнала на резких границах – возникает погрешность – ringing Gibb’s Phenomenon. С которой с переменным успехом борются по сию пору.

Спектр – изображение отражающее зависимость амплитуды от частоты и от направления синусоиды. Если какую-то часть спектра отсечь и выполнить обратное преобразование – получится изображение “отфильтрованное” по тем или иным характеристикам.

Развитие идеи ДКП – Фильтр Габора. Подобные фильтры позволяют находить края заданной ориентации и частоты. Если их объединить в банк фильтров – набор фильтров разного масштаба и ориентации – то можно получить описание локальной текстуры области изображения (в виде вектора признаков) и использовать для анализа.

2.1) пирамида изображений – Пирамида Гауссианmipmap

пример пирамиды изображения

пример пирамиды изображения

Простейшая пирамида – набор масштабируемых копий изображения. В ходе обработки возможны случаи, когда изображения можно исключить из обработки на основе анализа их малых представлений. Применяются для улучшения сопоставления шаблонов, кратномасштабный анализ изображений (multidimensional methods).

2.2) пирамида Лапласиана – вариация Пирамиды Гауссиан На каждом уровне хранится не масштабированная копия, а сигнал (данные изображения) определенной частоты. Эффективнее сжатие, прогрессивная передача данных сначала верхние уровни потом уточняем менее частыми данными

2.3) Ориентированные пирамиды. Получаются если к каждому уровню пирамиды Лапласиана применить ориентированный фильтр – например, фильтр Габора. Хранят информацию о структурах разного масштаба – частоты и ориентацию. Используется для синтеза детектора краев произвольной ориентации (а заодно и для синтеза изображений).

2.4) Вейвлет (wavelet – всплекс) разложение – разложение сигнала по набору масштабированных и смещенных версий одной базовой функции. Может оптимально закодировать сигнал одномерной функции – используется в JPEG2000, эффективен для медицинских изображений высокого разрешения\размытых границ – томограмм.

2.5) Популярные в последнее время – разреженные представления (sparse modeling) сигнала – через словарь – состоящий из фрагментов часто встречающихся в изображениях. Основные методы построения изображения по словарю: basic pursuit, matching pursuit, orthogonal matching pursuit, LARS – Lasso. Можно выбрать либо аналитические методы построения словаря – Curvelets, Countourlets, Surflets, Bandelets, Complex Wavelet Transform, Shearlet, Grouplet, Grouped bandelet. Или построить его с помощью одного из пакетных методов – на основе исходных данных. Наряду с методами строящими словарь на основе всех данных, существуют быстрые методы построения словарей с обучением на лету – после добавление нового элемента данных производится обновление словаря (K-SVD, Image Signature Dictionary). Иерархические словари используются для ускорения разложения.

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

Подробно про сжатие изображений – тут.

Библиотеки для построения словарей и работы со словарями есть в свободном доступе:
Sparse modeling software
sparselab.stanford.edu
от Minh N. Doтут
от Michael Eladтут

02 – (пред)обработка изображений

Обработка изображений

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

Все методы предобработки изображений объединяет одна особенность – на вход они получают изображение, и на выходе также выдают изображение. Методы эти, в зависимости от контекста, могут называться фильтрацией изображений, повышением качества (восстановлением) или, по-просту, предварительной обработкой изображения.

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

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

Какие на практике бывают разновидности брака:

Мона Лиза - когда не лады со светом

Мона Лиза – когда не лады со светом

Проблема – темное или пересвеченное изображение. Решение – повышение контраста (всего изображения целиком или его части) с помощью линейной коррекцией (или робастной линейной коррекцией). В случае неравномерного освещения, как правило достаточно применения метода single scale retinex (SSR) – принцип расписан на хабре – примеры применения там, конечно, своеобразны. Однако лучших результатов помогают добиться методы нелинейной коррекции – гамма коррекция или логарифмическая, Multi-Scale Retinex. Сравнение всех методов коррекции освещения в статье “A Comparison of the Multiscale Retinex With Other Image Enhancement Techniques”.

Мона Лиза - когда на изображении много шума

Мона Лиза – когда на изображении много шума

Проблема – зашумленное изображение. Шум бывает нескольких видов: соль и перец, белый шум – случайные белые пикселы, гауссов – колебания яркости распределяются по нормальному закону). Cамый легкий способ побороть шум – сделать серию кадров и по ним рассчитать среднее изображение. Обычно же, для борьбы с шумом используется линейная фильтрация (альтернативное название – операция свертка или, на английском, convolution with matrix). На практике, это процесс, когда значение каждого пикселя пересчитывается на основе его окрестности – значений соседних пикселей и специальных коэффициентов-весов (т.е. линейной комбинации). Какая конкретно окрестность и какие конкретно коэффициенты – определяет ядро применяемого фильтра. Ядро – это просто числовая матрица с подобранными коэффициентами. Эти коэффициенты называют степенями влияния или “ценностями”, определяющими вес пикселей из рассматриваемой окрестности. Полезно помнить, что сумма коэффициентов ядра должна быть равна 1, для того чтобы не изменялась средняя яркость/интенсивность. Из линейных фильтров наибольшее распространение получил гауссовский, построенный по принципу “взвешенного усреднения”. Как правило, не понятно насколько сильно зашумлено изображение, потому, на основе экспериментов при использовании гауссовского фильтра выбирают радиус в трое больше сигмы – среднеквадратичного отклонения. Однако есть немало и альтернативных методов фильтрации шума, из которых имеет смысл запомнить медианный фильтр, по сравнению с фильтром Гаусса, он не “размывает” изображение. anisotropic diffusion. Первые фильтры – Превитта, Собеля – сейчас практически не используются.

Мона Лиза - все как в тумане - когда не хватает резкости

Мона Лиза – все как в тумане – когда не хватает резкости

Проблема – нерезкое изображение. Общий принцип усиления границ – размыть изображение, вычесть полученный результат из исходного, тем самым получив сильные границы, а потом полученную разницу добавить к исходному. Основные методы: unsharp masking, Лапласиан/Лапласиан гауссиана – детали подробные тут.

Мона Лиза - нарушенный баланс цветов

Мона Лиза – нарушенный баланс цветов

Проблема – неправильные цвета (хорошо известная фотографам проблема баланса белого). Разделяют на интерактивные методы – серые (белые) карточки (более продвинутые – адаптация “Von Kries”). Или вероятностные – модель серого мира – Grayworld или, как вариант, – растяжение контрастности – autolevels.

Какую информацию можно извлечь из изображения?

Вспоминаем, что понаписано в предыдущей статье – изображение это, всего навсего, такая функция от двух переменных. Раз функция, то, при желании, можно искать ее производные. Вектор из частных производных для каждого пикселя – это градиент этого пикселя или его направление (orientation). Для изображения частные производные можно вычислять через разность текущего и соседнего значений пикселей (смачно разжеванные детали – тут). По градиентам всего изображения можно построить гистограмму ориентированных градиентов – histogram of oriented gradients, которая используется повсеместно.

Если у нас в распоряжении есть несколько изображений одной и той же сцены, сделанные через какие-то промежутки времени, то, для того чтобы определить динамическую составляющую сцены (как выносили сейф или качалась травка) можно рассчитать оптический потокoptical flow – вектор, отражающий движение пикселя от фрейма к фрейму, в зависимости от времени. В вике упоминаются методы для его вычисления по градиенту. Еще одна характеристика которая может быть полезна при анализе изображения – disparityневязка – насколько пиксель не совпадает с самим собой на двух изображениях

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

Границы могут быть образованы совершенно разными условиями – изменениями цвета/текстуры, разрывами поверхностями – когда нормаль резко меняется, вызванными перепадами освещения и тенями. Иногда рассматривают отдельно различные виды моделей границ – step\roof\spike\ramp. Простейший способ определения границ – вычисление производных функций изображения. На практике же используются стандартный кэни – Gradient of Gaussian (Canny) – подробно и наглядно на русском здесь. Как альтернатива – LoG (Laplacian of Gaussian  Marr-Hildreth).

При всем многообразии методов обработки изображений – их применение сопряжено с единственной проблемой – компьютер так и не может определить, насколько тот или иной метод, примененный к конкретному изображению улучшил его с точки зрения человека. Не смотря на то, что существуют метрики сравнения картинок – MSE – среднеквадратичная ошибка, пиковое отношение сигнал-шум – PSNR, они не учитывают человеческое восприятие. На данный момент универсальной метрики нет.

03 – features – локальные особенности – за что зацепиться взгляду

[pullquote align=”left|top” textalign=”center” width=”30%”]Лучше один раз увидеть…[/pullquote]

Local features – локальные особенности

Изображение, бесспорно, представляет собой самое емкое и лаконичное представление большего объема “нефильтрованной” информации. Нефильтрованной, потому как в большинстве случаев, в рамках определенной задачи, нам вполне достаточно некоей “выжимки” данных: есть на изображении объект интереса или нет, где он расположен, каковы его характеристики. Эпическое описание сцены со всеми подробностями, как правило, не является предметом первой необходимости. Да и второй тоже.

features - особые точки

features – особые точки

Особые точки (в разных источниках – features/characteristic points/local feature points/interest point/локальные особенности) – говоря неформально – “хорошо различимые” фрагменты изображения. Это точки (пиксели) с характерной (особой) окрестностью – т.е. отличающиеся своей окрестностью от всех соседних точек. Классический пример локальной особенности – вершина угла (а не какая-то произвольная точка на прямой или на однородном фоне). Описываются вектором признаков вычисляемых на основе интенсивности/градиентов или других характеристик точек окрестности. Используя особые точки можно  анализировать как изображения целиком так и объекты на них. Хорошие характерные точки позволяют справиться с изменением масштаба, ракурса и перекрытиями сцены или объекта.

Локальные особенности – краеугольный камень во многих высокоуровневых алгоритмах компьютерного зрения: отслеживание (tracking) и распознавание (recognition) объектов, 3d-реконструкция и навигация (SLAM и loop-closure). Используя характерные точки можно вычислить сдвиг (disparity) между двумя изображениями, произвести сегментацию на основе сдвига элементов сцены, рассчитать фундаментальную матрицу для калибровки стерео-пары или проиндексировать изображения для поиска.

Какими должны быть локальные особенности?

  • повторяемыми – должны находиться в одном и том же месте сцены независимо от ракурса и освещения
  • локальными – (как родинки у человека) – должны быть расположены в малой области и не страдать от перекрытий
  • компактными – по сравнению с общим числом пикселей изображения их должно быть в разы меньше
  • значимыми – уникальными – каждая особенность должна иметь свое собственное описание (чтобы сложно было перепутать их между собой)

Основные методы поиска локальных особенностей:

Виды преобразований.

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

Простейшим видом преобразования является параллельный перенос (сдвиг):

пример преобразования параллельный перенос

пример преобразования параллельный перенос

Подобие (перенос, масштаб, поворот):.

пример преобразования подобия

пример преобразования подобия

Афинное (дает хорошее приближение искажений претерпеваемых небольшим плоским фрагментом объекта при изменении радиуса):

пример аффинного преобразования

пример аффинного преобразования

Гомография – одна из простых разновидностей проективного преобразования. Это перспективное преобразование плоскости – преобразование между двумя видами одной и той же плоскости или преобразование между видами полученными с повернутой камеры (при общем центре проекций) – съемка со штатива. По сути – преобразование в однородных координатах.

пример преобразования гомография

пример преобразования гомография

Если распределить модели преобразований по возрастанию сложности то получится:

поворот -> масштаб -> афинное.

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

Как найти локальные особенности?

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

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

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

В качестве детектора, не чувствительного к масштабу была предложена концепция блобов (Blobe) – каплевидных окрестностей, в центре которых расположена особая точка. Внимание – ужас. Для определения таких окрестностей использовались лапласианы гауссианов (LoG – ЛОГ-фильтром) или разница гауссианов (DoG – DOG-фильтром). Несмотря на зловещее название тут тоже все просто. Изображение, как все помнят, мы представляем в виде функции. Лапласиан – сумма вторых частных производных функции в точке. Гауссиан – это просто гауссова функция – которой обрабатывают изображение. Соответственно лапласиан гауссиана – представление функции-изображения после применения оператора Гаусса, через сумму частных производных (его трехмерный график, при некоторой доле воображения, напоминает мексиканскую шляпку или сомбреро).

Характеристический размер блоба, теоретически, можно найти так: провести свертку размытого Гауссом изображения с помощью оператора Лапласа в нескольких масштабах и выбрать тот масштаб, на котором достигается максимальный отклик лапласиана. Для того чтобы это все работало на больших масштабах – необходима нормализация. Именно так и работали первые многомасштабные детекторы блобов. Одно но – лапласианы дорого считать. Лапласиан гауссиана можно приближенно представить в виде разницы двух гауссиан (с различным масштабом) – по русски это значит что мы “размазываем” исходное изображение с помощью оператора Гаусса (с разными значениями сигмы) и вычитаем одно из другого.

Детекторы углов и блобов можно использовать параллельно. На этой нехитрой идее выросли алгоритма Харис-Лапласа (Harris–Laplace) и Хессиан (Hessian affine region detector).
Общая идея – мы также выделяем углы на изображении, но уже с учетом характеристического размера: ищем точки максимизирующие отклик угла Харриса по изображению и отклик Лаплассиана по масштабу. Отклик – это просто значения функции после применения фильтра.

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

Развитием идеи блобов явились детекторы областей: EBR (edge-based regions), IBR (Intensity-Extrema-Based Region), MSER (Maximally stable external regions). Характерных областей на изображении будет значительно меньше чем блобов, но, с точки зрения семантического описания сцены, они более информативны. К сожалению, на информацию о применении в практических задачах такого подхода я не натыкался.

Как описать локальные особенности? Дескрипторы особых точек (feature descriptor)

После того как особые точки найдены их надо друг с дружкой сравнивать. Для этого необходимо некоторое компактное представление характерных особенностей. Они должны быть:

  • Простыми – представление должно быть быстро вычислимым.
  • Уникальными – разные точки должны иметь разное представление.
  • Локальными – как и сама особая точка ее представление должно зависеть лишь от небольшой окрестности.
  • Инвариантными к максимально большему числу преобразований.

Обычно используется вектор-признаков. И вопрос только в одном – по каким характеристикам вычислять этот дескриптор.

Интуитивно простой способ – отталкиваться от интенсивности пикселей в окрестности точки. Однако, такой подход обеспечивает инвариантность только к сдвигу. Впрочем, для видео, вариант с нормализованной интенсивностью может и подойти (для сравнения можно использовать банальные SAD/SSD). Есть некоторые подходы для создания классификатора не так сильно реагирующего на изменение яркости (нормирование яркости, локальная нормализация гистограмма).

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

Тем не менее, в практических задачах уже давно эталоном стал дескриптор SIFTScale-invariant feature transform и его производные – SURF, GLOH и PCA-SIFT. Самый его жирный минус – для использования необходим патент.

Состоит из трех основных компонентов:

  • Детектор на основе разницы гауссиан – DoG – служит для определения положения и характерного масштаба особой точки на изображении.
  • Гистограмма градиентов, используется для определения ориентации особой точки (берется самый сильный градиент).
  • Дескриптор конструируется на основе направлений всех градиентов орестности.

Инвариантен к малому сдвигу и изменениям освещения.

Более компактное представление дескриптора практиковалось в методы PCA-SIFT. Использование цветовой информации нашло свое отражении в дескрипторе RGB-SIFT (3 SIFT для каждого канала) а также C-SIFT, rgSIFT.

С перспективными искажениями (множество всяких разных эллипсов упрямо проецируются в один и тот же круг) используется метод аффинной адаптации.

Для усиления дескриптора, можно учитывать контекст (формы или глобальный) – рассматривая взаиморасположение других особых точек, находящихся в некоторой окрестности вокруг первой точки.

Готовое приложение для сравнения всех детекторов в OpenCV (SIFT, SURF, ORB, FREAK и тд) с гуи и исходниками доступно здесь – https://code.google.com/p/find-object/

Для сравнительно недавнего (2011) сравнения дескрипторов и детекторов особых точек гуглить:
Steffen Gauglitz Tobias Höllerer Matthew Turk
Evaluation of Interest Point Detectors and Feature Descriptors for Visual Tracking

Сравнение дескрипторов:
http://computer-vision-talks.com/2011/08/feature-descriptor-comparison-report/
http://computer-vision-talks.com/2012/08/a-battle-of-three-descriptors-surf-freak-and-brisk/

05 – машинное обучение для классификации изображений

Машинное обучение – для компьютерного зрения

компьютерное зрение - как научить компьютер думать

компьютерное зрение – как научить компьютер думать

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

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

Машинное обучение это когда компьютеру скормили учебную выборку данных (положительные и отрицательные примеры), а он на их основе научился работать с новыми данными(не входящими в учебную выборку). Конкретный объект можно описать с помощью признаков и характеристик, если проанализировать несколько объектов одного класса – можно выделить их общие признаки, и при изучении нового объекта отталкиваться от нашего представления о базовом классе, для того чтобы понять относится ли новый объект к известному нам классу. Например, мы хотим распознавать на любом изображении человека. Тогда нам нужна учебная выборка содержащая и не содержащая людей. Люди должны быть разные – высокие, толстые, в разных одеждах и позах. При обработке учебной выборки формируется классификатор содержащий описание признаков людей, который, при применении к новому изображению, с некоторой долей вероятности (проценту совпавших признаков) будет распознавать или не распознавать людей.

Сколько всего объектов для распознавания? Примерно это число существительных плюс число объектов, описываемых словосочетаниями, не включая абстрактные, не материальные сущности + .. – … Словом много их. На практике, нам не нужен доскональный анализ каждой букашки на изображении – в силу приземленности, нас интересует сугубо практичная информация, навроде представлен ли на изображении конкретный объект. Или, что несколько более обобщенно – относится ли изображение к заданному классу – содержит ли он объект(ы) определенного типа (пейзаж/таракашку/атомный ледокол). Класс (категория) содержит информацию о том, как мы можем взаимодействовать с объектом (кошку вполне можно погладить за ухом, от тигра надо тикать). С другой стороны то, как мы можем взаимодействовать с объектом – функции объекта – зависят от наблюдателя – в кошке при виде мышки проснется охотник, в женщине – паника.

В идеальном мире разделение по категориям было бы простым – либо объект входит в данную категорию, либо нет: на основе набора свойств общих для всех элементов из категории. Это так называемые жесткие идеальные категории. На практике не все так просто – если кто-то любит лакомиться кактусами, это еще не повод заносить их в класс “еда”. Потому принято использовать так называемые естественные категории (Natural Categories by Rosch). В них каждый класс определяется наилучшими примерами-прототипами и, при сравнении неизвестного класса, можем задать некоторую степень (вероятность) соответствия категории. Нечеткие правила гораздо более гибкие и больше подходят для реальных задач классификации.

В психологии (ну, вы помните про кучу смежных отраслей, да?) используется термин каноническая перспектива (“Когнитивная психология”, Роберт Солсо) – такой эталонный экземпляр класса, по которому для человека проще всего опознать предмет. Скажут вам класс “кошка”, а на ум как-то сам собой приходит какой-нибудь Барсик, с расцарапанной по весне разбойничей мордой. Одна из упрощенных моделей мышления человека – feed-forward architecture – когда нет априорной информации о наблюдаемой сцене (человек без понятия что ему должны показать). При этом не обязательна обратная связь – т.е. никто не уточнит что качан капусты на мяч футбольный смахивает весьма отдаленно, хотя формой схожи. Хороший классификатор должен обеспечивать эквивалентные возможности.

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

Основные методы категоризация изображений:
Knn – метод ближайших соседей
и методы на основе машинного обучения
random forest – случайные леса
SVM – метод опорных векторов
boosting
neural networks – нейронные сети

Внимание – далее все тоже самое только оно расписано чуть более подробно с использованием разнузданной лексики из теории вероятности.

У всех объектов заданного класса есть некоторые схожие признаки. Распределение этих признаков (пусть неизвестное, пусть сложное) – одинаковое для всех всех объектов внутри класса. Имея некоторый конечный набор данных мы сможем оценить вероятностные характеристики – построить правила – некоторую функцию. Функция эта будет получать на вход характеристики важные для ответа на вопрос “Является ли эта штука объектом класса А?” – т.е. это классическая для тервера вероятность чего-то при условии таком-то. Пока, для упрощения, считаем что характеристики вычисляются на основе взаиморасположения особых точек.

Разновидности классификаций:

1) бинарная классификация – рассматриваем 2 класса

2) многоклассовая классификация – классов больше двух

3) регрессия – классов вообще нет, есть различные значения функции (определение возраста, веса)

4) кластеризация – делим наше пространство значений функции на решающие регионы с помощью решающих правил.
Каждое решающее правило – это одна из функций некоторого параметрического семейства. Эта функция будет являться классификатором.
Отдельно стоит упомянуть функцию потерь отражающую число неправильно предсказанных классов с помощью заданного классификатора.
Наша задача – определить такое параметрическое семейство, что функция потреь будет минимально. Параметрическое семейство будет формироваться в виде нейронной сети.

Метод обучения – метод оценки параметров для параметрического семейства по некоторой эмпирической выборке. Обучение это не тупое заучивание, а возможность делать выводы анализируя новые данные. Формально, процесс обучения классификатора прост – на основе обучающей выборки строим признаки изображения и обучаем классификатор. Тестируем его и если качество работы не удовлетворительное – запускаем цикл обучения повторно. Важно верно подобрать данные для тренировки иначе можем столкнуться с явлением переобучения – когда полученная функция идеально описывает обучающую выборку, а не объектов в целом (это может быть связано и с шумом в исходных данных и в сложности модели).

Общая схема обучения (Features -> Coding -> Spatial pooling):
Для каждого изображения
– вычисляем признаки изображения (например по-пиксельно)
– разбиваем их на несколько категорий-кластеров (для усиления влияния на непосвященных можно воспользоваться термином “квантование признаков”, в случае неравномерного распределения признаков – в большинстве случае – лучше использовать адаптивное квантование с помощью K-средних)
– определяем область для вычисления (например, с помощью пространственной пирамиды – изображения разбиваем на области, и вычисляем признаки отдельно для каждой области, причем берем несколько уровней разделения – на 4 на 16 и т.п. частей)
– вычисляем признаки – агрегируем (гистограммы, мешок слов)
Используем один из методов категоризации на полученном наборе мешков слов, для формирования классификатора.

Гистограмму для описания распределения признаков можно строить по регулярной сетке или с помощью кластеризации (адаптивно). Используются различные подходы к ее вычислению: гистограммы цветов/градиентов/разреженных визуальных слов/ плотных визуальных слов. Каждый вид признаков можно рассчитывать по всему изображению, а можно по отдельной области. Часто используется пирамида разбиений из трех уровней (1+4+16 гистограммы).

Для сравнения гистограмм используются: пересечение гистограммы (histogram intersection), расстояние Манхэтена, L1 distance, расстояние хи-квадрат и т.п.

составляем лицо медведя на основе визуальных "слов" из словаря

составляем лицо медведя на основе визуальных “слов” из словаря

Один из метод агрегирования – мешок слов. Принимаем часто повторяющийся фрагмент изображения за визуальное слово. В конкретном изображении может встречать ровно один раз, несколько или ни одного раза. На их основе составляем словарь – базовый набор из фрагментов которые часто повторяются в коллекции изображений. Часто используется совместно и разреженная и плотная версия представления слов (Dense words PhowGray PhowColor – попросту говоря с перекрытиями или без). При построении словаря актуальной становится проблема золотой середины – чтобы слов было не слишком много (опять переобучение), но и не слишком мало (когда словами нельзя описать все признаки) – методы решения – использование деревьев словарей, хеширования.

Оценка качества работы классификатора

Эмпирический риск – отражает уровень ошибки тренировки – средняя вероятность ошибки, цель обучения классификатора – минимизация эмпирического риска. Во время тренировки руководствуемся правилом бритвы Окама (в науке это правда называется “Принцип структурной минимизации риска”) – и выбираем наиболее простую модель из тех, что достаточно точно описывают объект-категорию.

Для проверки качества можно использовать метод скользящего контроля (Cross validation)

Различают ошибки первого и второго рода – ошибки классифицированные и пропущенные. Их любят отображать на ROC-кривой – отражающей зависимость чувствительности и ошбки второго рода (ROC – receiver operating characteristic).

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

Виды классификаторов
1) Линейный классификатор.
Обладая достаточно развитым абстрактным мышлением можно представить себе множество признаков как набор точек в пространстве. Классификатор при таком представлении будет гиперплоскостью (линейной функцией) разделяющий множество признаков. Нас интересует какая гиперплоскость лучше – какой классификатор лучше подойдет для задачи категоризации объекта по признакам. Сухим языком эта задача формулируется как поиск гиперплоскости, максимизирующую отступ между положительными и отрицательными примерами (можно также учитывать влияние шума – добавив параметр минимизации доли признаков ошибочно отнесенных к “не своей” группе). На этот вопрос можно ответить с помощью метода опорных векторов (SVM – support vector machine).

2) Не-линейные.
Да где вы видели в реальном мире ситуацию, когда применимо линейное разделение? Однако уж больно подкупает кажущаяся простота линейного подхода. И был придуман простой способ избежать ужасов хитровыдуманных функций. Исходное пространство параметров отображается на многомерное пространство признаков (feature space), где обучающаяся выборка будет линейно разделима. (представьте что у вас на листке – двухмерном пространстве – есть набор из взаимнопересекающихся фигур, которые на этом листке никак не разделяются, но если вы перенесете этот же набор в трехмерное пространство все получится). Для упрощения вычислений, вычисляется ядровая функция – kernel trick, если она неотрицательно определена (Mercer’s condition) – тогда мы можем построить нелинейную решающую функцию в исходном пространстве.

Простейший пример ядра это полиномиальное.
1 выбрать признаки для изображения \мешок слов
2 выбрать ядро для этого вектор признака
3 вычслить матрицу значений ядра для каждой пары примеров из обучающей выборки
4 матрицу грузим в библиотеку SVM для получения весов и опорных векторов
5 во время вывода вычислить значения ядра для тест образца и каждого опорного вектора
и взять взвешенную сумму для получения значений решающей функции.

Не существует формулировки для многоклассовой категоризации, приходится комбинировать бинарные:
– один против всех (формируем классификатор отдельно для каждого класса против остальных, применим метод опорных векторов к образцу и назначим класс – для которых он наиболее выделен – достоверное решение)
– один против одного (построим классификатор для каждой пары классов на основе метода опорных векторов, МОВ голосует за классы выбираем класс с наибольшим числом голосов(

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

04 – поиск преобразования между особыми точками и немного моделирования

Сопоставление изображений

Когда изображения не сопоставляются

Когда изображения не сопоставляются

В интернетах гуляет немало фотографий эйфелевой башни. Одни из них сделаны спозаранку, другие – когда уже вечерело, одни сделаны чуть ли не у ее подножия, на других она высится над Парижем. Однако наш острый ум ни на секунду не сомневается, что во всех случаях это именно она – Эйфелева башня.

Что же позволяет нам проявлять столь похвальную прозорливость? У Эйфелевой башни есть некоторые характерные особенности которые мы можем безошибочно определить на всех снимках, не взирая на различия в освещении, ракурсе съемки или перекрытия (людьми или постройками). Более того – на основании снимка мы можем примерно прикинуть откуда он был сделан и определить условия съемки. (Нет, это не столько для того чтобы ощутить свое всемогущество – такая возможность пригодится при 3д реконструкции объектов и сцен, или построении панорам).

Если немного отвлечься от сладких грез о Париже и вернуться к нехитрым выкладкам из теории компьютерного зрения получается вот что: на изображении мы можем выделить характерные точки. Если изображений в нашем распоряжении несколько – мы можем попытаться определить – есть ли на них общие особые точки. Если мы найдем некоторое количество общих особых точек – тогда мы сможем полнее описать наблюдаемую сцену – в случае если сменился ракурс обзора. Это поможет определить как переместились особые точки по сравнению с предыдущим кадром (для описания движения объекта или частей объекта) – т.е. сможем оценить изображение уже на более высоком уровне.

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

Заранее нельзя сказать каким образом получен набор изображений для анализа – потому следует рассматривать все возможные варианты преобразований, отбирая те преобразования, при которых совпадает максимальное количество особых точек.

Общий алгоритм поиска преобразования между двумя изображениями на основе особых точек:

  • Находим особые точки
  • Вычисляем дескрипторы особых точек
  • Сопоставляем точки по дескрипторам – получая соответствия точек
  • По этому набору соответствий вычислить модель преобразования (не забывая про ошибки измерения положения точек)

Особая точка на первом изображении потенциально может соответствовать любой из особых точек второго изображения (мы же не можем заранее предсказать как изменилась сцена или сместилась эта точка). Потому, при анализе используются наборы из возможных пар соответствий. Проверять каждую особую точку на соответствие со всеми особыми точками второго изображения – способ конечно надежный но слишком уж ресурсоемкий. Для ускорения анализа сейчас принято составлять гипотезы для набора разных точек в совокупности – MND – mutual neighbor distance и проверять, насколько они согласуются друг с другом. Например, разбивая изображения на отдельные участки – сетку, или отбирая пары случайным образом . Те точки, которые соответствуют модели преобразования называются inliers, те которые нет – выбросы – outliers. Дескрипторы сравниваются как обычно – SSD, SAD, кросс-кореляцией, пересечением гистограмм.

Надо отметить, что потенциально может быть полезно и попиксельное сопоставление (при поиске по шаблону или построении панорам) – однако для практики это скорей экзотика. Полноты описания ради – функции оценки попиксельного сопоставления – SSD, SAD, градиентный спуск, многомасштабное сопоставление.

Моделируя изображения

Для того, чтобы описать объект или целую сцену редко необходима вся информация о цвете и текстуре. В конце-концов, несколькими контурами а ля “палка палка огуречик” можно схематично изобразить и ледовое побоище и утро в сосновом бору. Что позволяет заявлять о том, что львиную долю изображений можно как-то аппроксимировать в виде набора простых (геометрических) моделей (линии, окружности). Простые модели, в свою очередь, можно составлять из набора особых точек. Как это сделать?

Существует целое семейство задач связанных с параметрами модели изображения на основе особых точек – model fitting – “подгонка” модели. Методы решения разделяют на робастные (выбросы не оказывают влияния на результирующую модель) и не робастные (неустойчивые к выбросам – например заданы точки удовлетворяющие модели и надо вычислить параметры этой модели)

1) Неробастные методы

Подгонка прямых линий
При заданном наборе точек, мы ищем прямую наилучшим образом их аппроксимирующую.
Решение – методом наименьших квадратов что упрощенно решается через сингулярное разложение – SVD (singular value decomposition).

В случае обобщенной модели, когда задан набор признаков и необходимо найти ее параметры используется все тот же метод наименьших квадратов, однако он уже называется DLT – Direct Linear Transform (или метод максимального правдоподобия, или минимизация суммы квадратов отклонения. Метод полных квадратов показывает наилучшие результаты. Однако для сложной модели, при использовании этого метода производится оптимизация алгебраической ошибки лишенной физического смысла, меж тем как для каждой модели есть и разумная ошибка, имеющая физический смысл. Методы минимизирующие эту ошибку называется gold standard.

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

2) Робастные методы
а) M-оценки – с целью уменьшение влияния далеких точек вводится некоторая функция модели. Решается с помощью метода взвешенных наименьших квадратов. Недостатки – необходимо хорошее первое приближение, как найти минимум целевой функции.

На практике, такие задачи разбиваются на две части:
выбрать приближение – функцию, а потом итеративно его уточнять (как пример – взвешенный итеративный МНК).

b) RANSACRANdom SAmple Consensus
Параметры модели оцениваются не по всем данным, а по малой части не содержащей выбросы. Заранее неизвестно, какая часть не содержит выбросы – случайно делаем выборки несколько раз и для каждой выборки оцениваем модель и ее качество.

Регулируется несколькими параметрами:
– размер – минимальное количество точек для оценки параметров (например для прямой – две точки)
– количество выборок
– требуемая вероятность что правильная точка будет правильно классифицирована

Хорошо и часто работает на практике. Применяется для сопоставления изображений.
Недостатки:
не всегда удается хорошо оценить параметры по минимальной выборке
– много настраиваемых параметров (если порог не корректен – будут проблемы)
– иногда требуется слишком много итераций
– не срабатывает при очень высокой доле выбросов
– часто есть лучший способ нежели равновероятно выбирать точки

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

В вариации M-SAC для оценки порога используются M-оценки – это дает прирост точности и не влияет на вычислительную сложность.

Альтернатива RANSAC – LMS (Least median squares). Из его минусов – может выбрать неверную гипотезу. Не работает если больше половины точек выбросы. Потому на практике малопригоден.

Еще одна альтернатива RANSAC – схемы голосования (voting scheme). Пространство параметров называется фазовым пространством. Схемы голосования используются для поиска семейства кривых заданных параметрически.

Каждый признак голосует за все модели которым удовлетворяет. Те модели, за которые проголосовало наибольшее число признаков мы принимаем за искомый результат. Мы считаем, что выбросы\шумные данные не будут голосовать согласованно. Практической реализацией схем голосования будут преобразования специального вида, прореживающие наборы специальных точек на два класса – принадлежащих заданной преобразованием модели и нет.

Самое известное преобразование – преобразование Хафа (Hough Transform). Эффективно в случае если на изображении мало точек для перебора.

Альтернатива – преобразование Радона (Radon transform). Эффективен если мало возможных конфигураций кривых.

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

Machine Learning – links

Machine learning intro:

http://habrahabr.ru/company/yandex/blog/208034/ – comprehensive lection from Yandex (in russian)
http://ciml.info/ – A Course in Machine Learning by Hal Daumé III
http://alex.smola.org/teaching/cmu2013-10-701/index.html – Intro to Machine Learning ’13, by Carnegie Mellon University
http://alex.smola.org/teaching/berkeley2012/ – Scalable Machine Learning ’12, Berkley
http://openclassroom.stanford.edu/MainFolder/CoursePage.php?course=MachineLearning – Machine Learning from Andrew Ng
http://ufldl.stanford.edu/wiki/index.php/UFLDL_Tutorial – brief overview of advanced concepts
solution for above cources – https://github.com/danluu/UFLDL-tutorial
http://cs229.stanford.edu/materials.html – Machine Learning from Stanford
http://machinelearningmastery.com/start-here/ – practical recommendation to apply methods of ML – language, libraries, frameworks

Deep Learning:

http://deeplearning.stanford.edu/tutorial/ – great intro to world of deep learning
http://cvn.ecp.fr/personnel/iasonas/deeplearning.html – another intro
http://timothymasters.info/Deep_learning.html
http://deeplearning.net/tutorial/
http://markus.com/deep-learning-101/
https://developer.nvidia.com/deep-learning – toolset overview from NVidia
https://developer.nvidia.com/deep-learning-courses – cource from NVidia
http://cs.stanford.edu/people/karpathy/convnetjs/ – Javascript library for training Deep Learning models within browser
https://medium.com/@jiefeng/deep-learning-playbook-c5ebe34f8a1a – overview of toolset/libraries
https://jmozah.github.io/links/ – yet another links collection

Few video about deep learning:
http://techtalks.tv/deep_learning_nyu_spring_2014/
https://www.youtube.com/playlist?list=PLnDbcXCpYZ8lCKExMs8k4PtIbani9ESX3 – RE.WORK Deep Learning Summit
https://www.youtube.com/watch?v=PlhFWT7vAEw&list=PLjK8ddCbDMphIMSXn-w1IjyYpHU3DaUYw – Deep learning from Oxford

Udacity cources:

https://www.udacity.com/course/viewer#!/c-ud617/ – Intro to hadoop and reduce
https://www.udacity.com/course/ud359 – Intro to data science
https://www.udacity.com/course/viewer#!/c-ud675/ – Machine learning supervised learning
https://www.udacity.com/course/viewer#!/c-ud741/ – Machine learning – unsupervised learning
https://www.udacity.com/course/viewer#!/c-ud820/ – Reinforcement learning

Artificial Neural Networks:

http://neuralnetworksanddeeplearning.com/
http://www.theprojectspot.com/tutorial-post/introduction-to-artificial-neural-networks-part-1/7/
http://cs231n.stanford.edu/ – Convolutional Neural Networks for Visual Recognition

how to build fovis library under windows

So, you want to build and use Fovis library (which can estimate 3D motion of RGB-D camera or stereo pairs) under Windows?

Quick and dirty how-to compile it:

Create empty root folder for your build – for example name it fovis_win.

Install Prerequirements:
1) Download Eigen and install it.
2) Download cmake-gui and install it.
3) Download cygwin (with patch utility) and install it.
4) Download missing headers for windows from https://code.google.com/p/msinttypes/ and extract them at your root folder into msinttypes subfolder (so both include files would be located at fovis_win/msinttypes). You cannot build fovis without it.
5) For building examples (for examples only, so you can skip it) you need OpenNI install it to default path (c:\program files\openni). Also you would need freenect. You should build it at the root folder, so you will get all libraries and include under fovis_win/frenect/..
6) Download fovis and extract it at the root folder (all files would be located at fovis_win/libfovis).
7) Download archive with patch for fovis – libfovis.patch – and extract it in the folder fovis_win.

(update 02.09.2013 patch with minor fix for compilation with Visual Studio 2012 – libfovis_VS2012.patch)

Run cygwin and type:
cd path-to-fovis_win/libfovis
patch -p1<../libfovis.patch After that you can create build directory for cmake - fovis_win/libfovis/build. run cmake-gui && press configure & generate. It will create Visual Studio project files under build directory. NOTE:
Default search paths from CMakefiles:
Openni library – c:/program files/Openni.
freenect library – ../freenect/
msinttypes headers- ../msinttypes/
If CMake can’t find something using this path – you should set appropriate path via cmake-gui.

Brief patch overview:
– added export definitions for class/functions for windows target
– fixed minor issues for includes/defines for windows target
– added aligned memory operation for windows target
– tictoc.hpp – added support for windows timing routines
– examples – fixed floor->std::round, working with signal for windows target

How to build iSam under Windows

Due to ill fate I need to quickly build iSam for using it into existing project as SLAM backend. Under Windows 🙁 In this article I want to share my experience.

iSam under Windows

iSam under Windows

Disclaimer: I am sure that such way is not optimal and express “best practices”, so, in case you have enough time – better to avoid such strategy of quick fixes. But I hope that provided methods can be useful and probably can force some one to add appropriate patches to iSam or SuiteSparse.

Let’s start.

1. Firstly, you need acquire necessary dependencies. Download Eigen, boost, cmake-gui and cygwin.
For building sdl under windows you need dxguid.lib which can be found in DirectX SDK.

2. SDL – can be build under Windows out of box without any problems
just download it from the site above and follow build instructions.

3. Download and buid SuiteSparse – you can find patch and build instruction for Windows here – here.

4. Download patch for building iSam under Windows – isam_win.diff

4. checkout iSam library from svn repository:
svn co https://svn.csail.mit.edu/isam

5. pray for all gods and apply patch from cygwin’s command line:
cd Your-root-directory/iSam-folder
patch -p2 <../isam_win.diff

6. Run cmake-gui and set it up to iSam.

Enable “advanced mode” checkbox. Push “Configure” button.
At every step it will complain that something is not found – point it out manually.

1) set up SDL path:
include directory,
path to SDLMain.lib and SDL.lib
2) check USE_GUI box
3) add Eigen include folder
4) Add CHOLMOD include path and path to libcholmod.lib
5) path to CXSParse library – libsxsparse.lib

After that you can generate VS project solution.
But wait!
You still need to perform some tuning to all sub-projects:

For isamlib project
add following include path:
1) path to cs.h (SuiteSparce/CXSparse)
2) path to SuiteSparce_config.h (SuiteSparce/SuiteSparce_config)

For sub-projects isam, addRemove, anchorNodes, covariances, stereo, example add following libraries (from SuiteSparse package) for linking:
1) libcolamd.lib
2) libamd.lib

For isam sub-project you should manually add source containing getopt routine – file isam/xgetopt.cpp from this package. Actually you can use any implementation, for example from lcm library.

For generateSpheresICRA2012 projects add include path to boost/include.

After that it should compile.

Note: by default it doesn’t create dynamic library. If you need isam.dll you have to manually change isamlib project configuration type (Properties->General) from “static library” to “Dynamic library” and add libcolamd/libamd libraries for linking.

Short patch overview:
1) covariance.cpp – header fix
2) utils.cpp – added gettimeofday functions
3) files Node.cpp, Factor.cpp with implementation of constructor are added to isamlib project
4) slam.cpp, cholesky.cpp dynamic allocation is added (instead of C99 standards check for example this)
5) Loader.cpp, Viewer.cpp – added fix for include
6) Collections.cpp – use glEnable(GL_NORMALIZE) instead of GL_RESCALE_NORMAL (because by default on Windows is installed opengl 1.1 check this)
7) isam.cpp – added windows specific main functions (check this)
8) added XGetOpt.h/XGetOpt.c from http://www.codeproject.com/Articles/1940/XGetopt-A-Unix-compatible-getopt-for-MFC-and-Win32
9) added Windows specific exports to almost all classes

Why do you have to edit some iSam sources:
http://thetweaker.wordpress.com/2010/05/05/stdvector-of-aligned-elements/
http://eigen.tuxfamily.org/dox/TopicStlContainers.html
http://www.mcs.anl.gov/research/projects/mpi/mpich1-old/docs/mpichntman/node10.htm

How to build SuiteSparse under Windows using Visual Studio

Howto: SuiteSparse under Windows

Patch and build instructions for compiling SuiteSparse under windows using cl.exe and other routine from Visual Studio.

UPDATE 13.04.2013: tested for SuiteSparse 4.0.2 only

SuiteSpare – exists only for *nix-based systems. Officially. But if you want – you can build it and use under windows.

I have to build iSam library under Windows and because it depends on several libraries from SuiteSpare I had to firstly build SuiteSparse. For iSam I need only several libraries from SuiteSparse – AMD, CAMD, COLAMD, CXSparse and, finally, CHOLMOD.

You should take into account that CHOLMOD can be build using fortran-based libraries (using BLAS and LAPACK), using ACML library (Core Math Library) or without them. If it is crucial for you to achieve the best performance – and if you are absolutely sure that you use it – you have to see notes at the end of this article.

Instructions below for building CHOLMOD without any additions as LAPACK, BLAS or METIS (used flags are -DNSUPERNODAL -DNPARTITION).

Instructions step by step:
1. Download and install cygwin.
2. Add to cygwin.bat (c:/cygwin by default) routines for setting up Visual Studio environments:
     call “c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\bin\vcvars32.bat”
or
     call “c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\bin\amd64\vcvars64.bat”
(exact path depend on VisualStudio install path and your target architecture)
3. Download patch for building SuiteSparse under Windows – suitesparse_win and save it into root directory in which located SuiteSparse folder.
4. Run cygwin with cygwin.bat, cd into SuiteSparse directory and type:
     patch -p1<../SuiteSparse_win.diff

UPDATE 13.04.2013:
For linking your binaries using Visual Studio link utility you have to copy link.exe from VS’s bin folder –
(by default –
C:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\bin\link.exe and
C:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\bin\x86_amd64\link.exe
)
into cygwin bin folder (by default – c:\cygwin\bin\).
You should name them as link_32.exe and link_64.exe accordingly.
Such trick is necessary due to existance of “link” routine from Cygwin programms set.

5. Now you can build all desired libraries:
     make isam_libs

There are two types of build : “win32 debug” and “x64 release”.
You can switch between them by changing variables CFLIB, LINK at makefile SuiteSparse_config.mk (from SuiteSparse_config folder). DO not forget to restart cygwin with appropriate variable set scripts (call to vcvars32.bat or vcvars64.bat)!

Note: Path to the Visual Studio’s libraries are set in that file also. If it is differ from your – linking error as “cannot open file ‘LIBCMT.LIB” – just change it.
You can get appropriate path by typing
echo $LIBPATH
this var should been set by vcvars*.bat script during startup of cygwin.

Brief patch description:
– CXSparse – all *.c renamed into *.cpp
– CXSparse – added c-style casts for every memory allocation routine
– all variables CC, CF, ARCHIVE, RUNLIB, LIB are changed to appropriate for Visual Studio
– *.deff files for export symbols were added
– and probably some other minor changes

Notes 1:
There is port of SuiteSparse under Windows – https://github.com/PetterS/SuiteSparse.
Under project folder you can find Visual Studio solution files for building CHOLMOD and some others (AMD, CAMD, COLAMD,CCOLAMD).
But_1 – it has modified version of CHOLMOD for use ACML (Core Math Library – AMD library for building SuiteSpare (yeah, yeah it can be used on intel machines).
But_2 – it has settings for x64, for x86 you have to manually edit project settings
But_3 – not all of the libraries have valid export definition files (without them your library will compile without any exported functions).

Notes 2:
you can try to build CHOLMOD using LAPACK and BLAS. I spent the whole day to give try it but with no luck. Few tips: use mingw compiler, do not forget that gfortran and all x64 routine in cygwin should be appropriately pointed in SuiteSparse_config.mk.

Notes 3:
In case you wish to setup SuiteSparse as Visual Studio project you should keep in mind internal structure of SuiteSparse and different approaches to build it (for example – with and without support of complex numbers – which reflected in recompile the same source with different flags).

Links:
how to build LAPACK (for use via CHOLMOD) – http://www.kitware.com/blog/home/post/231
Prebuilt libraries for Microsoft Visual Studio – http://icl.cs.utk.edu/lapack-for-windows/lapack/#libraries
http://www.netlib.org/lapack/

Идеальный процесс разработки – утопия или Continuous Integration?

Какой такой Continuous Integration?

Существуют немало приемов облегчающих разработку и сопровождение программ в промышленных масштабах – тестирование, система управления версиями, система отслеживания ошибок, автоматизированная система сборки и развертывания и т.д. Continuous Integration – объединяет все эти компоненты в единое целое, работающее по гибким правилам оптимальным для компании или проекта.

Continuous Integration глазами непосвященных

Continuous Integration глазами непосвященных

Процесс разработки програмного обеспечения – достаточно скользкая тема. Про нее много писано и модно говорено, но нередко, при общении с коллегами, возникают абсурдные ситуации – когда вроде все знают как хорошо и по-правильному, но работают по старинке – самоотвержено борясь с одними и теми же проблемами. Программисту сложно объяснить старшему (младшему, да и вообще, любому) менеджменту преимущества процесса разработки с точки зрения бизнеса. А не-программист (даже если он и руководитель) не знает с чего начать, чтобы заинтересовать свой отдел в процессе разработки не путем номенклатурного воздействия, а конкурентными преимуществами следования процесу разработки, заточенного под нужны отдела и специфику компании.

Эта статья – некоторая выжимка как теории так и опыта, которую можно взять за основу (а можно и не брать) при обсуждении светлого будущего с манагерами и между разработчиками.

Примерный сценарий как бы это могло выглядеть в до приторности идеальном мире:

Разработчик неторопливо потягивает кофе попутно изучая свежую прессу в виде rss-ленты его излюбленных блогов. Внезапно раздается тревожное треньканье и одновременно в жаббер и на емейл приходит оповещение что где-то приключилась беда. В письме указана ссылка на внутренний портал, где можно прочитать описание ошибки, которую необходимо исправить. Программист делает суровое лицо супермена и логинится в веб-портал системы управлению проектами, выбирая раздел баг-трекер. В списке новых работ одиноко мерцает тревожным желтым огоньком не закрытая задача – значит приоритет срочности средний. Он читает описание проблемы. Ошибку создал один из заказчиков, а служба поддержки уже запросила первичную информацию о среде окружения, версии продукта, воспроизводимости ошибки и т.д. Теперь дело за ним – повелителем битов и байтов! Он решительно переводит ошибку с представителя службы поддержки на себя и изменяет ее статус на “В работе”. Заказчик и тех-саппорт сразу же получают оповещения о том, что отдел разработчиков не дремлет.

– Итак, – размышляет разработчик, – для начала надо попробовать воспроизвести проблему! Для этого надо взять самую свежую версию продукта. Это проще простого – прямо через веб-интерфейс легким кликом мыши инициируем checkout проекта из системы контроля версий – весь исходный код, все зависимости и вспомогательные утилиты устанавливаются на машине разработчика. Так вот сразу лезть в код боязно, он все еще верит в доброе и светлое и надеется, что удастся обойтись малой кровью – поэтому запускает команду “быстренько все собрать и развернуть прям-как-для-продакшн на тестовом сервере №1”. Процессоры пыхтя перелопачивает все потоки сборки стремясь не вызвать у разработчика раздражения из-за мучительно долгого билда. Тем временем, на тестовом сервере производится создание новой виртуальной машины, воссоздается конфигурация идентичная установленой у заказчика. Развертывается база данных, создаются пользователи, запускаются сервисы и, в конце-концов, только что собранный продукт, еще с пылу с жару, устанавливается на подготовленную чистую систему.

Разработчик сверяется с предоставленным пользовательским сценарием ( use case – инструкцией – как же воспроизвести проблему – обязательный полем в описании ошибки в системе улучшения качества продукта):
– Сюда ввести вот это, выставить вот такой таймаут… Ага! Вот оно! Почему то стерлись все данные в базе. Хмыыыы. Придется лезть в код…, – смиряется он с неизбежным и отодвигает недопитое кофе на край стола – в свое время, рыцари примерно с таким же энтузиазмом опускали забрало при виде недобитых ветряных мельниц.

Пока проект загружается программист размышляет: “Хорошо что все свои предпочтения можно выставить один раз для всего проекта и при любом чекауте автоматически весь код будет индентирован так, как ты привык, в специальной директории будут аккуратно сложены свеже-сгенерированные файлы проектов для той самой, единственной IDE, которая всем IDE IDE, а если каких-то зависимостей на машине разработчика нету – они будут скачаны с билд-сервера, причем именно той версии, которая должна быть использована для этой версии проекта. При этом я могу сразу заняться работой, а не тратить дни на борьбу с инструментами.”

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

Стремительный полет мысли, пулеметная дробь от ударов по клавишам – как будто бы фикс готов. Пробуем прогнать проблемный сценарий – вуаля! ошибка не возникает.

Что ж, приходит время для добавления исправлений в основную ветвь разработки. Разработчик вновь набирает всего одну комманду и, откинувшись в кресло, следит что ему торопливо пишут pre-commit скрипты. Первым делом они обновили его версию кода (вдруг кто-то внес какие-то правки пока он искал ошибку). После этого был инициирован “быстрый билд” – когда проект собирается под все платформы (чтобы сразу заметить не сломан ли билд) и прогоняются только самые главные тесты. Нововведения проверяются статическими анализаторами кода на соответствие проектным стандартам и индентируются в соответствии с корпоративными стандартами. И наконец код добавляется в репозиторий, в отдельную(!) ветку.

Тут за работу берутся post-commit скрипты – сразу запуская “большой билд” во время которого прогоняются все самые пустяковые проверки – чтобы гарантировать, что внесенные изменения не поломали чего-то еще. В это же время самые суровые коллеги нашего героя получают приглашения провести code-review вместе с раскрашенным diff-ом измененных файлов и ссылкой на описание ошибки и вынести свой вердикт – нужен ли такой код проекту.
Пока они выражают свое одобрение мастерству и стилю, отмечая про себя ранее не виданные методы и тем самым професионально растя над собой – все тесты завершаются с зеленым статусом.

“Все в порядке!”, заключает программист изучив прямо на портале логи билда и тестов, “все в порядке” – подтверждают коллеги-ревьюверы и он с чистой совестью нажимает кнопку merge (слияния ветки посвященный багу за нумером таким-то и основной линии разработки). После чего переводит задачу в статус решено и возвращается к кофе. В это время собирается патч и отсылается клиенту.

Подобные сценарии (в том или ином приближении) обычное дело в компаниях где процесс разработки строится вокруг и на основе методик Continuous Integration/Continuous Delivery – системы непрерывной интеграции\системы непрерывного развертывания – как противовес явлению метко описываемому на английском как Integration Hell. Если бы было необходимо описать эту систему парой фраз это были бы: “всегда есть рабочая версия”, “оно само собралось”, “все всегда в курсе”.

Структуру ее можно представить в виде отдельных модулей примерно так:

Из чего состоит Continuous Integration

Из чего состоит Continuous Integration

И все было бы как в сказке если бы не одно но – готового решения нет. Поймите меня правильно – есть несколько достойных систем CI с помощью которых можно вершить чудеса, но настраивать ее и ломать устоявшиеся привычки – придется именно вам. Залог успеха любых перемен – это чтобы людям было действительно удобнее выполнять свою работу по-новому. Удобно, это когда с помощью одной команды можно сделать чекаут, получить все зависимости проекта, собрать его и развернуть всю систему на тестовом сервере. Удобно, когда перед релизом не ломается билд праймлайна не смотря на армаду коммитов и мозгодробительные мержи. Для внедрения методологии разработки критично то, как ее внедрили – сами по себе компоненты не станут серебрянной пулей в мгновение ока истребляющей старые болячки. Отдельный вопрос как ее интегрировать в уже существующую инфраструктуру. Особенно, в случае если она представляет из себя образцово-показательный хаос – с другой стороны именно из него то и будем творить мир.

Почему-то очень часто люди упираются в какие-то смешные проблемы технического плана – навроде того “а вот у нас с базой данных это жеж не сработает”, “мы не можем континиус интегрейшн – у нас же невообразимо хитровыдуманные железяки”. Поймите – нет какого-то эталонного списка фич, которые кровь из носа должны быть у вас в процессе. Не надо бросаться очертя голову сделать сразу все. Такие вещи за день не делаются. И за два. Начните с грубого приближения и доведите все до рабочей конфигурации. Оцените результат. Вдумчиво изучите раздел Ссылок по теме в конце статьи – оттуда можно подчерпнуть немало новых идей. Имея опыт и новые знания – решите чего вашей системе не хватает.

5 “простых” шагов для внедрения Continuous Integration

Готовой инструкции, как ваш проект перевести на новые рельсы нет и быть может. Но начать можно с этого.

1) Реорганизация кода

Цели у данной задачи две:
собираться все должно быстро (+ см. пункт 2). (стремиться надо к тому чтобы минут десять занимал обычный билд, не более часа – полный – со всеми тестами)
– должна быть возможность прогнать авто-тесты по отдельным модулям/компонентам.

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

Минус – очень сложно выбрать золотую середину и вовремя остановиться. Почаще вспоминать главную цель этого шага.

2) Настройка автоматической системы сборки

Цель – в любом окружении проект собирается сам, без помощи разработчика.

Разработчик не должен тратить время сражаясь с зоопарком зависимостей и особенностями конкретной платформы.
Есть простое правило – для любой цели есть своя, одна(!) лаконичная команда. Совершенно не принципиально кто конкретно будет ее выполнять – ant/maven/cmake/make/scons/bash/… – ваш проект – вы и выбирайте. Сделать можно на чем угодно.

Минус – придется крепко помучаться разрабатывая билд-скрипты.

3) Все, все, все в репозиторий!

Цель – хранение всех рабочих версий продукта.

В любой момент – можно посмотреть на код позапрошлогоднего релиза и собрать его.
Организацию структуры репозитория я здесь обсуждать не буду. Но она:
1. должна быть
2. должна быть не слишком вычурная
И да, хранить необходимо все, что нужно разработчику чтобы начать работать с кодом: все зависимости, тесты, сторонние утилиты, схемы базы данных, скрипты для загрузки тестовых данных, эмуляторы сети или хитроумных устройств.

Минусы – придется продумывать стратегию хранения – разграничение основной линии от исследовательской, по каким критериям определять возможность объединения нового кода с основной линии (код ревью, статические анализаторы и т.п.).

4) Тесты

Цель – у нас всегда должен быть рабочий продукт.

Если проект не собирается – продукт не рабочий. Если проект собирается, но не работает – продукт не рабочий.
Такой код в репозиторий попасть не должен. Может быть, абсолютно все автоматически протестировать и нельзя – но к этому определенно имеет смысл стремиться. Тестирование обязательно должно быть в pre-commit скриптах. Необязательно оно должно быть всеобъемлющее – но основные функции должны быть проверены. Апологетам теории, что есть вещи которые протестировать нельзя – давайте называть вещи своими именами – да, разработка тестов для некоторых задач не самая тривиальная вещь. Да, в некоторых случаях понадобятся объекты-заглушки, тестовые схемы данных, скрипты для эмуляции действий пользователя… Но все это сделать возможно.

Минус – объем кода для тестов может привысить размер кода продукта. Но повторяю – не обязательно сразу все – начните с критичных функций.

5) Соблюдение процесса разработки

Continuous Integration в процессе работы

Continuous Integration в процессе работы

Цель – чтобы все это заработало. Самый сложный шаг. Здесь указаны некоторые (не все!) пункты способствующие распространению идей Continuous Integration в светлые головы коллег. Повторение идей упомянутых выше не случайно.

1. На пальцах объяснить разработчикам, что одно дело, когда их рабочая копия не собирается, и совсем другое, когда основная версия из репозитория, утверждает что какой-то супостат добавил не-posix функции. накануне релиза.
2. Попробовав смержить результат двух месяцев автономной разработки с основной веткой – даже самый ярый противник каждодневных коммитов поневоле задумается. Чем чаще коммиты – тем меньше проблем при слиянии кода. У всех.
3. Поиграть в новичка на проекте – задавая уймы недалеких вопросов – тогда решение об авто-документации по сборке проекта, по зависимостям, по бизнес-логике приходит как то само собой.
4. Основная линия разработки священна и юные падованы не должны протягивать к ней свои шаловливые лапки без должного контроля.
Вносить правки в файлы конфигурации сборки – должны лишь избранные, отягощенные проклятием ответственности.
5. По коммиту должно быть легко узнать к какой задаче он привязан в баг-трекере. Кто автор. Ключевое слово – “легко” – в одно касание мыши.
6. Code Review – это не “Кто-то будет хаять мой код?!”, а обмен знаниями и масса возможностей для професионального роста.
7. Не важно кому люб Eclipse, а кто фанат Visual Studio. Билд скрипты не завязаны ни на IDE, ни на компилятор, ни на ОС разработчика. Но умеют генерить файлы проекта для любимой IDE каждого разработчика, при необходимости не чураются кросс-компиляции.
8. База данных хранится в системе контроля версий (структуры таблиц, пользователи, тестовые данные). При тестировании – создается своя, уникальная, никак не связанная с другими копия базы. Изменения в базе данных – также хранятся в системе контроля версий и привязаны к версиям продукта в виде зависимостей.
9. Тесты желательно сгрупировать по типам или целям. Так они станут быстрее и информативнее.
10. Развертывание продукта и его конфигурирование – полностью автоматизировано. Одна команда запускает все что нужно и для заказчика и для тестера и для руководителя проекта. Команд и целей для развертывания будет несколько, но скрипт пусть будет один. Не должен тестер тыкать в далее, вбивать куда-то пароли или выбирать пути установки для того чтобы начать тестирование.
11. В скрипте развертывания должна быть опция – “откатить все изменения и оставить систему какой была до установки”
12. Структуру репозиторию надо продумывать – выделять общие компоненты и зависимости между проектами, по возможности упрощать структуру – чтобы можно было легко определить где лежит исходный код, где тесты где документация.
13. Все заинтересованные люди должны быть информированы как о ходе работы по проекту (список задач, изменения их статусов, результативность разработчиков) так и о состоянии рабочей версии (результаты билдов и тестов) – Email, RSS, SMS – да как угодно.

И, на посошок, пару слов о системах CI, которые смогут объединить функции всех вышеупомянутых подсистем в одно целое:
Microsoft TFS – хорош тем что включает в себя из коробки все вышеперечисленное и мериады того упомянуто по ссылкам ниже – http://ru.wikipedia.org/wiki/Team_Foundation_Server
TeamCity (бесплатная лицензия для небольших проектов) – http://www.jetbrains.com/teamcity/
С этими лично не знаком – но, судя по отзывам, заслуживают внимания:
CruiseControl – бесплатный целиком и полностью – http://cruisecontrol.sourceforge.net/
Любопытен Apache Continuum – если ваш проект на maven – то развертывание проекта сводится к указанию pom-файла – http://continuum.apache.org/

Ссылки

Введение в Continuous Integration на русском:
http://habrahabr.ru/post/82724/

Лаконичная памятка-шпаргалка по Continuous Integration – http://refcardz.dzone.com/refcardz/continuous-integration (на момент написании статьи доступен для скачивания напрямую вот отсюда)

Фаулер про Continuous Integration:
http://martinfowler.com/articles/continuousIntegration.html
Фаулер про Continuous Integration совместно с базами данных:
http://martinfowler.com/articles/evodb.html
Фаулер про Continuous Delivery:
http://martinfowler.com/delivery.html

сравнение систем непрерывной интеграции – http://en.wikipedia.org/wiki/Comparison_of_continuous_integration_software
сравнение систем создания документации – http://en.wikipedia.org/wiki/Comparison_of_documentation_generators
сравнение систем по управлению проектами – http://en.wikipedia.org/wiki/Comparison_of_project_management_software
сравнение систем отслеживания ошибок – http://en.wikipedia.org/wiki/Comparison_of_issue-tracking_systems
Список систем для авто-сборки – http://en.wikipedia.org/wiki/List_of_build_automation_software

Литература (водится в интернетах)
Pragmatic Project Automation автор Mike Clark
Continuous Integration: Improving Software Quality and Reducing Risk автор Paul Duvall
на момент публикации есть вот тут:
!интересный! репозиторий с материалами по теме – http://buildrelease.googlecode.com/hg/Trunk/
(обратите внимание на разделы BRESystem/theory/ и, особенно, на Trunk/BreBooks)