Jan 04

SLAM – принципы и ссылки на open source

Что такое SLAM?

SLAM - акроним для Simultaneous Location and Mapping

SLAM – акроним для Simultaneous Location and Mapping

Эта заметка – небольшая памятка на тему что такое SLAM. Здесь описаны основные принципы наиболее популярных методов SLAM (EKF, iSam, TORO и др). В отдельном разделе интересующиеся могут найти ссылки на свободные(!) реализации различных методов SLAM в виде готовых библиотек. А также перечислены блоги и проекты посвященные задаче SLAM. Если вы ищите готовую реализацию SLAM – собрал->запустил->получил карту => листайте к последнему разделу.

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

Представьте себе робота, оснащенного некоторым набором сенсоров (например обычной и дальномерной камерой) находящегося в некоторой неизвестной среде – например лабиринте Минотавра. Робот не обладает информацией об окружающем его пространстве равно как и своем положением в нем. Все что у него есть – показания сенсоров и возможность сохранять информацию о предыдущих измерениях. Его задача – слоняясь по лабиринту построить полную карту, дабы будущие Тесеи не теряли времени зазря в поисках супостата. На практике это означает что робот ищет ответы на вопросы “Где я?!” и “Как выглядит мир вокруг?!”.

В каждый момент времени в мозг робота передаются показания с сенсоров. С помощью методов визуальной одометрии или на основе анализа дальномерных данных – робот может определять свое смещение относительно предыдущего положения. В идеальном случае – когда его вычисления точны и безукоризнены – по одним этим данным возможно воссоздать карту местности, где он уже побывал и полностью описать траекторию его движения. В печальной реальности – на каждом шаге возникает небольшая погрешность вычислений (ошибка замеров/помехи/ограничения, накладываемые алгоритмами и т.п.). С течением времени общая, аккумулятивная ошибка продолжает нарастать таким образом, что не смотря на приемлимую точность определения локального смещения – общая глобальная карта положений робота будет полна искажений. И вот тут-то на помощь роботу и приходят методы Simultaneous Localization And Mapping или просто SLAM.

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

Первый принципиальный момент – SLAM не предполагает каких-либо знаний о среде – ни меток на местности/ни предварительной карты нет – все решения строятся только на результатах измерений датчиков (обычно это rgb- и дальномерная камеры, но, бывает, и дополнительное оборудование навроде гироскопа-IMU/gps-датчика и т.д.).

Второй не менее принципиальный момент – среда считается статичной. Это значит, что если робот проехал мимо фикуса, никто за его спиной этот же самый фикус двигать не станет. В кадре – в обозреваемом сенсорами пространстве – никакого постороннего движения нету – флюгера не крутятся, никто в кадре не прогуливается. Освещение радикально не изменяется – т.е. тени по стенам не скачут. Такие условия сложно гарантировать в естественной среде – приятно шелестящая листва или любопытная кошка запросто может дезориентировать робота в пространстве (ну, не то чтобы прям запросто – и отсекать динамическую часть можно, и делать поправку на нее). Однако, если пофантазировать на тему марсоходов – то даже в настоящем виде методы SLAM могут найти свое применение. В частности, робот-пылесос – яркий пример применения данной методики в 2D-пространстве. Существуют экспериментальные реализации данной задачи в 3D (квадроптер шныряющий по коридорам и беспилотный батискаф).

SLAM_robot_trajectory

SLAM – карта мира и траектория движения робота в нем

В общем случае SLAM можно описать как повторяющая последовательность шагов:
1) сканирование окружающего пространства
2) определение смещение на основе сравнения текущего кадра с предыдущим
3) выделение на текущем кадре особенностей-меток
4) сопоставление меток текущего кадра с метками полученными за всю историю наблюдений
5.1) обновление на основе этой информации положение робота за всю историю наблюдений
5.2) проверка на петли – не проходим ли мы повторно по одной и той же местности
5.3) выравнивание общей карты мира (отталкиваясь от положения меток и робота за всю историю наблюдений)

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

Представленные реализации разделяются на две большие группы – SLAM frontend и SLAM backend.

Задача SLAM-fronted‘а сводится к оценке пространственных отношений между особенностями сцены и позами робота с некоторым значением вероятности. SLAM-fronted – набор методов для преобразования полученных данных от сенсоров к унифицированному представлению (структуре специального вида – см. далее) подаваемому на вход непосредственно SLAM-ядру. В настоящее время, для этих целей используются графы специального вида (варьируются от взвешенного, основанного на результатах измерений, до динамической сети Байеса, вовсю отталкивающейся от вероятностной модели положения робота в мире). Данный компонент специфичен для робота (какие там у него сенсоры, как организовано преобразование входной информации и т.п.), а потому какой-то универсальной библиотеки, реализующей весь функционал я не встречал. Хотя список поддерживаемых сенсоров того же ROS – robot operaring systems впечатляет. Принципы выбора особенностей на каждом кадре здесь описаны не будут – интересующимся гуглить по SIFT, SURF, NARF, FAST и т.д.

SLAM-backend – SLAM-ядро – непосредственная реализация решения задачи SLAM – оптимизация полученных от фронтенда пространственных отношений с целью максимизации вероятности. Данная задача абстрагированна от того, каким образом получены входные данные – главное, чтобы формат представления (граф, сеть, матрица, список и т.д.) информации о среде и положении робота в нем совпадали. Например, в каких-то случаях необходима высокая точность и не принципиально время вычислений, в других случаях критичен быстрый результат. Если мы храним все наши перемещения и замеры в виде специального графа то мы в первом случае скормим этот граф на оптимизацию iSam’у, а во втором отдадим TORO’у.

SLAM в деталях

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

SLAM frontend:

1) Анализ и интеграция новых данных (data association). На этом этапе производится выделение особенностей (Feature/landmarks extraction) на вновь полученных данных (на основе RGB-информации, карты глубины, их комбинации, показаний дополнительных датчиков – гироскопа, GPS-приемника и др.) Особенности – это такие характеристики, которые легко могут быть выделены в среде и использоваться в дальнейшем для ориентации в пространстве. Желательно чтобы их можно было распознать под разным “углом зрения” с точки зрения используемых сенсоров. Критично чтобы они были стационарны. Желательно чтобы их можно было различать друг от друга – для того чтобы понять – не встречали ли мы их ранее. Самый простой пример особенностей – геометрические – углы, прямые.

2) Вычисление сдвига (Local Motion Estimation). На основе сопоставления нового набора особенностей с особенностями, полученными на предыдущем шаге можно определить как изменилось их расположение на сцене. Так как особенности сами по себе стационарны – очевидно что этот сдвиг – результат изменения положения камеры (робота). На основе этой информации можно выразить координаты камеры через систему линейных уравнений для решения которой используются различные методы и их комбинации (ICP, visual odometry – FOVIS, RGB-D, etc).

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

SLAM backend:

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

2) Обновление общего представления о карте мира и траектории робота (Global Optimisation)
На основе вновь полученных данных производится уточнение текущих представлений о мире – пересчет позиций робота (state estimation), особенностей и их вероятностей. Дополнительно производится поиск замыканий (loop closure – ситуаций, когда робот возвращается в те места где уже побывал). После всех вычислений обновляется общее представление мира – позы робота (state update) и координаты особенностей (landmark update).

На основе глобальной структуры, хранящей все перемещения робота и представление мира в любой момент времени возможно воссоздать карту миру с траекторией движения робота. Для визуализации (Reconstructing world map) используются сторонние средства к методам SLAM особого отношения не имеющие.

Методы SLAM

Популярнейшим методом для решения был EKM – Extended Kalman Filter.
На каждом шаге у нас есть набор ранее полученных особенностей (landmark) и только что поступившие данные (дальномерные и RGB). На основании новых и предыдущих кадров мы можем определить смещение робота (используя методы визуальной одометрии) и предсказать новую позицию робота. С другой стороны, из нового кадра, мы можем выделить местоположение особенностей и вычислить положение робота относительно их. На основе разницы между двумя этими оценками позиций робота обновляются вероятности/веса для всех особенностей и корректируются позы-траектория движения робота. Детальное описание – по ссылкам ниже. В качестве структуры для хранения информации о мире и траектории движения робота – используется разрастающаяся со временем матрица ковариации, содержащая на каждом шаге исчерпывающую информацию о нашем текущем представлении мира. В случае большего числа поз – лучше подойдет particle filter, видео – отличный пример из курса ai-class от Sebastian Thrun.

Loop closure – обнаружение петлей. Обособлено от задач SLAM стоит вопрос как отслеживать ситуации когда робот возвращается туда, где уже побывал (в литературе это называется loop closure – замыкание, петля). Одно из решений – так называемая корзина “слов” (англ. Bags of Binary Words). Каждому кадру ставится в соответствие дескриптор (BRIEF descriptor), вычисляемый на основе визуальных особенностей изображения. Для хранения информации о изображениях, на основе данных для обучения, формируется словарь в виде дерева, содержащий “слова” для представления дескрипторов и их веса (отражающих насколько часто они встречались в наборе изображений для обучения). Для формирования “слова” производится поиск визуальных особенностей на основе данных для тренинга и их последующая группировка (с помощью метода k-среднего). Каждый последующий уровень дерева получается путем повторения данной операции с дескриптором родительского узла. В результате, при анализе ново-поступивших данных производится быстрое (см дистанция Хэмминга) разложение идентификатора текущего кадра в линейную комбинацию узлов дерева, где в роли коэффициентов выступают их веса – вероятности.

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

В настоящее время наиболее быстрые результаты дает TORO (ценою точности вычисления).
Данный метод определяет конфигурация графа при которой вероятность наблюдаемых особенностей будет максимальна. Подходов к решению подобных задач – видимо не видимо (гуглить по “Sparse Bundle Adjustments”, “Structure from motion”, “Visual SLAM”), в основу TORO лег метод стохастического градиентного спуска – (SGD – stochastic gradient descent). Суть данного метода в последовательной оптимизации всего графа для каждого ограничения  (взаимного расположения особенностей и робота). Для объединения данных оптимизации с нескольких ограничений используются специальные коэффициенты для корректировки значений остатка. Ключевое достижение данного метода – представление данных для SGD – в TORO используется дерево параметров в качестве индексов для линейного уравнения поз робота.

Хочу попробовать поиграться со SLAM – есть ли что-нибудь готовое?

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

Желающим поиграться с какой-нибудь готовой реализацией можно посоветовать RGBDSLAM. На момент написания – инструкция по сборке устарела и требуется как следует прошерстить раздел http://answers.ros.org/ на предмет каждой ошибки. Гипотетически, если следовать уточнениям в ссылках ниже – и использовать эталонную систему авторов – т.е. 64 разрядную убунту – должно работать. Лично я собрать то ее собрал (на убунте 32), убив пару дней, однако спорадически возникающие сегфолты и пропадающий gui задушил желание поиграться на корню.

Желающим попытать счастья настоятельно рекомендую ознакомиться:

  1. Ошибки вида can’t locate node, can’t find node – лечатся с помощью http://www.ros.org/wiki/fuerte/Installation/Overlays
  2. Ошибки rosmake:
    1. Во-первых не надо лениться заглядывать в лог файл сборки.
    2. Во-вторых перед сборкой желательно ознакомиться с инструкцией – http://answers.ros.org/question/40059/ros-rgbdslam-fuerte-support/
    3. если не помогает – читать до просветления:
      http://answers.ros.org/question/12708/rgbdslam-installation-problem/
  3. Если при сборке ноет что не находится findg2o.cmake – надо его найти в пакете g2o и либо смейк-скрипт подправить для rgbdslam либо сам файл переименовать.
  4. Ошибки запуска (вида can not locate launch file) – см тут.
  5. И, на посошок, репозиторий ежели что для всего проекта хранится тут – http://alufr-ros-pkg.googlecode.com/svn/trunk/

Возможный результат можно посмотреть тут.

Еще есть интересная библиотека Phovo. Скачать ее можно оттуда – http://code.google.com/p/photoconsistency-visual-odometry/. В своем составе, кроме всего прочего имеет приложения использующее SLAM-реализацию из mrpt, и реализованные автором алгоритмы визуальной одометрии (на основе http://vision.in.tum.de/_media/spezial/bib/steinbruecker_sturm_cremers_iccv11.pdf)

Из минусов – солидный список зависимостей, не все из которых собираются простым make install (одна unstable версия PCL чего стоит – внимательнее смотрите в cmake, какие компоненты вам действительно нужны).

Также учтите что для того чтобы завести NVidea toolkit под линуксом – придется немного попотеть: как установить cuda toolkit под ubuntu – http://sn0v.wordpress.com/2012/05/11/installing-cuda-on-ubuntu-12-04/

Ссылки на реализацию SLAM и связанных с ними компонент

DBow: Hierarchical bag-of-word library for C++ – описание
последняя версия DBoW – http://webdiis.unizar.es/~dorian/index.php?p=32

iSAM: Incremental Smoothing and Mapping
http://people.csail.mit.edu/kaess/isam/
по мотивам – http://www.cc.gatech.edu/~kaess/pub/Kaess08tro.pdf
страничка автора iSam:
http://www.cc.gatech.edu/~dellaert/FrankDellaert/Frank_Dellaert/Frank_Dellaert.html

Еще одна из вариаций SLAM-backend (на этапе оптимизации позволяет изменять структуру графа, ускоряя процес оптимизации)
http://www.tu-chemnitz.de/etit/proaut/forschung/robustSLAM.html.en

Список api связанных со SLAM имплементированных в библиотеке MRPT – Mobile Robot Programming Toolkit:
http://www.mrpt.org/List_of_SLAM_algorithms

Занимательное обсуждение различных алгоритмов SLAM:
http://stackoverflow.com/questions/1080533/slam-algorithm

ну и вика:
http://en.wikipedia.org/wiki/Simultaneous_localization_and_mapping

UPDATE от 11.01.2012
Наткнулся в запасниках еще на некоторые материалы. Добавляю.

Вопрос новичка – что такое SLAM – и развернутые ответы “для начинающих”:
http://www.mrpt.org/node/441
Описание свеженькой (от 2012 года) книжки про SLAM
Оглавление интересное.
http://www.mrpt.org/SLAM_book_2012

Karto – коммерческая версия SLAM (есть триалка и опенсурсный вариант с последним коммитом от 2010 года)
в описании проскальзывали утверждения о том что работает лучше чем iSam
http://www.kartorobotics.com
http://www.willowgarage.com/blog/2010/04/19/karto-mapping-now-open-source-and-coderosorg

Описание еще одного метода loop closing:
http://jochen.sprickerhof.de/software/elch/
по ссылке на странице можно зайти на сайт опенсурсного продукта – The 3D Toolkit – в котором кроме SLAM есть средства для просмотра облака точек, определения поверхностей и т.п.

update 03102013
Презентация с roboconf.ru:
“SLAM – путеводные крошки в мире людей” SLAM – Intro with algo and libs

зы уточнения/поправки рьяно приветствуются

Oct 11

как cv::Mat заполнить массивом из unsigned char

Наши исходные данные:
Универсальный контейнер cv::Mat из библиотеки openCV в который мы страстно жаждем запихнуть обычное RGB изображение.
RGB изображение к нам приходит от сторонних функций, которые выдают данные в виде отдельных массивов unsigned char для каждого из цветов каналов.

В исходном примере это массив элементов PixelRGB из библиотеки PCL, где каждому элементу ставится в соответствие простенькая структура содержащая значения всех цветовых каналов:

struct PixelRGB
{
      unsigned char r, g, b;
};

В контейнере cv::Mat все данные хранятся в одномерном массиве в виде последовательных характеристик каждой точки.
То есть для нашего трехмерного случая получается в таком виде:
[bgr-1][bgr-2]….[bgr-n] где [bgr-1] – соответственно характеристика голубого, зеленого и красного цветов первого пикселя.
Порядок хранения данных важен – т.е. grb или rgb не подойдет, в OpenCV данные о цвете хранятся именно в таком порядке – BGR – blue,green,red.

Свойства cv::Mat – rows и cols – говорят сами за себя – число строк и столбцов соответственно. cv::Mat.step – число элементов массива в каждой строке. Для трехмерного случая длина одной строки получается 640*3 = 1920.

Сниппет кода для заполнения контейнера cv::Mat массивом из unsigned char: 

int your_rgb_image_width = 640;
int your_rgb_image_height = 480;

PixelRGB* rgb_color_info = new PixelRGB[your_rgb_image_width*your_rgb_image_width];
Mat cv_rgb_image (your_rgb_image_height,your_rgb_image_width,CV_8UC3);
// fill Mat multidimensional array with unsigned char data
for(int i = 0,k=0;i < cv_rgb_image.rows;i++)
{
	for(int j = 0;j < cv_rgb_image.step;j+=3,k++;)
	{
		cv_rgb_image.data[RgbImageCur.step * i + j] = rgb_color_info[k].b;
		cv_rgb_image.data[RgbImageCur.step * i + j + 1] = rgb_color_info[k].g;
		cv_rgb_image.data[RgbImageCur.step * i + j + 2] = rgb_color_info[k].r;
	}
}

по ссылке расписано как произвести обратную операцию – скопировать данные из контейнера Mat:
http://jayrambhia.wordpress.com/2012/06/23/get-data-from-mat-cvmat-in-opencv/

update 17.11.2012
Что делать, в случае, если данные о цвете желательно хранить в виде целочисленного 32-разрядного числа – uint32_t, меж тем как на вход подается все тот же массив unsigned char?
В большинстве случаев (зависит от системы/компилятора) uint32_t эквивалентен unsigned int, uint8_t – unsigned char. Т.е. сниппет можно использовать как пример для преобразования RGB данных из массива unsigned char в unsigned int.

Как запаковать RGB-данные из unsigned char в unsigned int:

void pack_rgb_to_int(uint32_t& rgb_value, uint8_t red_value, uint8_t green_value,uint8_t blue_value)
{
	rgb_value = ((int)red_value) << 16 | ((int)green_value) << 8 | ((int)blue_value);
}

Как распаковать RGB-данные из unsigned int в unsigned char:

void unpack_rgb_from_int(uint32_t& rgb_value, uint8_t& red_value, uint8_t& green_value,uint8_t& blue_value)
{
	red_value   = (rgb_value >> 16) & 0x0000ff;
	green_value = (rgb_value >> 8)  & 0x0000ff;
	blue_value  = (rgb_value)       & 0x0000ff;
}

Sep 20

Как работает Kintinious: визуальная одометрия

Одна из ключевых особенностей Kintinious – стабильная работа методов позиционирования камеры в пространстве. Многие ждут когда же они выложат свой код (дада, они собирались это сделать) но мало кто знает что часть кода вобщем-то и так доступна. В частности, одна из ключевых компонент используемых в их работе – набор методов визуальной одометрии – вполне себе открыт для всех, кого интересуют как же работает Kintinious, как ориентируется в пространстве вертолет из ролика – http://www.youtube.com/watch?v=aiNX-vpDhMo.

В данной статье речь пойдет о библиотеке fovis – Fast Odometry from VISion – предназначенной для визуальной одометрии – т.е. для определения изометрии (движения) камеры на основе анализа последовательных фреймов. Смещение камеры однозначно определяется двумя характеристиками – матрицей поворота и вектором сдвига. Альтернативые методы описания смещения – кватернионы, с учетом масштабирования и т.п. здесь не будут рассматриваться. Путем анализа последовательных кадров получаемых с кинекта – кадров глубины и rgb-изображений – можно вычислить изометрию для каждой пары кадров. Располагая данными о том как камера перемещалась в пространстве относительно любой пары последовательных кадров можно во-первых отследить весь ее путь, и, во-вторых, сконструировать сформировать общую сцену, в рамках которой происходило движение камеры.

Библиотека содержит набор методов визуальной одометрии, скомпонованных таким образом чтобы обеспечить разумный компромисс между точностью и вычислительной эффективностью. Для расчетов используются CPU (хотя было бы эффективней распараллелить SIMD операции на GPU).

Общий алгоритм визуальной одометрии из библиотеки FOVIS выглядит так:

  1. Подготовка данных (фреймов rgb и глубины), далее, когда упоминается текущий фрейм – имеется в виду данные с кадра глубины и rgb-фрейма, полученные на текущей итерации.
  2. Поиск характерных особенностей на текущем кадре (FAST) – характерные особенности это, например, углы
  3. Сегментация – изображение разбивается на прямоугольные участки, в каждом из которых отбирается заданное число самых ярко выраженных характерных особенностей
  4. Определяем смещение текущего фрейма относительно предыдущего
  5. На его основе найденного смещения производим поиск и сравнение характерных особенностей не сразу во всем изображении, а по соответствующим другу-другу участкам Для сравнения и выравнивания используется несколько методов:
    1. Значение SAD (sum of absolute difference) – абсолютная сумма различий между двумя особенностями + выравнивание на основе метода наименьших квадратов
    2. Конструируется граф, где каждая вершина соответствует совпавшей паре особенностей. Ребра проводятся между вершинами в случае если расстояние между особенностями не превосходит заданного порогового значения, на протяжении анализа всей последовательности. (Т.е. на двух кадрах мы нашли несколько особенностей – например углы здания – евклидово расстояние между ними будет постоянным от кадра к кадру). В этом графе ищется максимальный связный подграф – т.е. все вершины которого соединены ребрами. (как альтернатива RANSAC)
  6. Финальное выравнение результатов:
    1. Минимизации евклидовой дистанции между совпавшими особенностями
    2. Минимизации ошибки проектирования (с предыдущего кадра на текущий и наоборот)
    3. Минимизация масштабного отклонения с помощью ключевых кадров
  7. Дополнение общей сцены данными из текущего сцены

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

Описание алгоритмы FOVIS подробно:

I Этап – визуальная одометрия

1. Подготовка данных

RGB изображение упрощается в градации серого – grayscale –  на основе следующего округления – финальный цвет пикселя равен округленному значению суммы (0.2125 * R + 0.7154 * G + 0.0721 * B).

Cоздается пирамида для того чтобы упростить поиск фич при различном масштабе
Число уровней можно задать (VisualOdometryOptions значение max-pyramid-level) – по умолчанию – 3 первый уровень – исходная картинка, последующие – вдвое меньше предыдущей.

Каждый уровень фильтруется с помощью Гауса (для того чтобы влияние соседних пикселей на текущий уменьшалось с увеличением расстояния до него). В сопутствующей работе указано что сигма должна быть 0.85, однако в коде библиотеки используется ядро 1/16*[ 1 4 6 4 1 ] что соответствует почти 1.0.

2. Поиск характерных особенностей (FAST)

Детальное описание FAST – можно найти здесь(ССЫЛКА)

Изначально исходный кадр разбивается на окружности с диаметров 7 пикселей (длина окружности 16), для каждой проверяется наличие особенностей и их значение. Для этого изучается яркость соседених пикселей в окружности пикселя-кандидата, где длина окружности 16. На основании наиболее распространных описаний конфигурации углов – не всех так как всех для 16 будет 3^6 – а для наиболее характерных. т.е.  Фактически это дерево вариантов по которому производится бинарный поиск. Если данный регион изображения удовлетворяет условию поиска – для него вычисляется значение особенности на основе значений яркости соседних пикселей. Каждой особенности ставится в соответствие данные из кадра глубины, если данных по ней не находится – то данная особенность отбрасывается.

3. Сегментация

Необходимо отобрать наиболее сильные, характерные особенности – для этого применяется простенький фильтр: на все изображение, фигурально выражаясь, набрасывается сетка, каждая ячейка которой рассматривается отдельно. Среди всех особенностей, что попадали в эту ячейку, отбираются наиболее ярковыраженные (по их значению) в количестве регулируемом параметром max_keypoints_per_bucket (здесь и далее, данный параметр – значение набора типа VisualOdometryOptions содержащему набор значений, набор по умолчанию состоит из рекомендованных значений и формируется с помощью вызова функции getDefaultOptions).

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

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

4. Определение изометрии – смещения

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

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

5. Поиск и сравнение характерных особенностей

Каждой особенности ставится в соответствие 80-байтовый дескриптор содержащий усредненные значения яркости пикселей в окрестности особенности размером 9 на 9, за исключением верхнего правого пикселя.
При сравнении двух особенностей вычисляется абсолютная сумма различий их дескрипторов (SAD – sum-of-absolute difference) – SIMD инструкции. Здесь кроется потенциальная возможность для оптимизации – данные вычисление эффективней было бы выполнять на GPU.

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

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

Определяем максимально полный подграф с помощью “жадного” алгоритма и обновляем на его основе наш список особенностей. Оставшиеся после этого особенности принято называть “inliers” но я продолжаю использовать термин “особенности”.

6. Финальная стадия выравнивания

1) Выравнивание полученного движения минимизацией ошибок проектирования особенностей. Проектирование используется двустороннее – с текущего на предыдущий кадр и с предыдущего на текущий – за счет этого мы еще раз уточняем наше значение изометрии при этом из набора особенностей удаляются особенности с высокими показателями ошибок. ( оригинальный метод гуглить по названию “Improving vision-based control using efficient second order minimization techniques”)
2) Для уменьшения небольшого масштабного отклонения – используется техника ключевых участков-фреймов: движение определяется сравнением предыдущего кадра-ссылки с текущим. Если движение камеры по предыдущему фрейму вычисляется не успешно и на новом кадре обнаружено достаточно число особенностей (ref_frame_change_threshold) – ссылочный кадр меняется. Иначе производится попытка сравнения текущего кадра не с ссылочным, а с предыдущим в последовательности, в случае неудачи с пред-предыдущим и т.д.. Такой прием используется для избавления от колебаний в случае если точка обзора не меняется значительно.

II Этап – SLAM 

Визуальная одометрия дает достаточно точные результаты, но нужна общая целостность. При совмещении данных от нее может возникнуть наложение и перекрытие данных в случае повторного перемещения камеры над одним и тем же местом. Для корректной обработки подобной ситуации нужны алгоритмы SLAM умеющие обрабатывать – loop closure – повторные посещения одной и той же области. В библиотеку FOVIS методы SLAM не включены, однако их описание присутствует в предыдущих работах, потому, считаю логичным привести здесь дальнейшие шаги общего алгоритма воссоздания общей сцены.

Задачи SLAM решаются на отдельной машине – данные на сервер SLAM подаются в общем виде – карты глубины уменьшены до 128×96 так, что расстояние между соседними пикселями 5 см. Для разрешения замыканий сцены (этим термином я буду оперировать рассуждая о loop closure) используется сравнения набора ключевых фреймов с новым фреймом. Новые ключевые фреймы добавляются когда общее движение по сравнению с текущим фреймом превышает 25 см и 10 градусов.

Когда создается новый ключевой фрейм, производится сравнение, с помощью процедуры RANSAC на ключевых точках (определяемых все тем же FAST) текущего фрейме и фрейма полученного 4 секунды назад. Процедура RANSAC – это просто случайная выборка среди набора особенностей. Так как замыкание сцены требует сравнения не обязательно последовательных кадров, в RANSAC предполагаемые совпадение ключевых точек определяются используя дескриптор Калондра (гуглить по фразе “Calonder randomized tree descriptor – Keypoint signatures for fats learning and recognition”. In europian conference on computer vision 58-71). Ключевая точка считается похожей на точку из предыдущего фрейма, если расстояние к наиболее подходящей ключевой точке предыдущего фрейма имеет соотношение меньше чем 0.6 по сравнению со следующей наиболее подходящей точке.

RANSAC совпадение устанавливается между фреймами если на них совпало минимум 10 особенностей.

Далее аналогично FOVIS производится выравнивание на основе минимизации ошибок обратной проекции между эталонным (полученным 4 секунды назад) и текущим кадром. Финальное выравнивание относительной позиции между двумя ключевыми кадрами получается путем решения системы выравнивания двух ключевых фреймов минимизирующую общую ошибку репроекции. (гуглить по словам “sparse bundle-adjustment” или “ams05-visualodometry.pdf”)

III Этап выравнивание

Показания скорости и направления из систем I и II суммируются с показаниями юнита IMU и передаются на вход в расширенный фильтр кальмана (extended kalman filter). Фильтр сглаживает их показания и выдает управляющему модулю.

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

Используемая литература:

исходный код библиотеки FOVIS – http://code.google.com/p/fovis/

Closed-form solution of absolute orientation using unit quaternions

Visual Odometry and Mapping for Autonomous Flight Using an RGB-D Camera

RGB-D Mapping: Using Depth Cameras for Dense 3D Modeling of Indoor Environments – SLAM система упомянутая во втором этапе детально описана там

Уточнения, вопросы и возражения – яростно приветствуются! 🙂

Sep 19

С++ – обход всех файлов в папке и мапинг в память

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

#include <boost/filesystem.hpp>
#include <boost/interprocess/file_mapping.hpp>
#include <boost/interprocess/mapped_region.hpp>

using boost::interprocess;

/****** ... and somewhere at very important program ***********/

const boost::filesystem::path base_dir (".");
std::string extension (".zzz");
	
for (boost::filesystem::directory_iterator it (base_dir); it != boost::filesystem::directory_iterator (); ++it)
{		
    boost::filesystem::path p = it->path ();
    if(boost::filesystem::is_regular_file (it->status ()) && boost::filesystem::extension (it->path ()) == extension)
    {			
	//mapping & processing
        file_mapping file_mapper(it->path().string(), read_only);
        mapped_region mapped_reg(file_mapper, read_only);
        double * double_pointer = (double *)mapped_reg.get_address();
        size_t elements  = region.get_size()/sizeof(double);
        
        // to get name only without extension
        string fname =boost::filesystem::basename (p);
    }
}

на голом std мапинг содержимого файла сразу в вектор можно сделать вот эдак:


ifstream input_data_stream("file_with_data.bin");

// Determine the file length
input_data_stream.seekg(0, ios_base::end);
size_t size=is.tellg();
input_data_stream.seekg(0, ios_base::begin);

// Create a vector to store the data
vector<int> vector_of_int(size/sizeof(int));
// Load the data
input_data_stream.read((int*) &vector_of_int[0], size);

// Close the file
input_data_stream.close();

Sep 19

Bat-ники для мелочей

Не, ну линуксы рулят конечно и все такое. Однако многие частенько недооценивают неказистую “мощь” батников. А, меж тем, в умелых руках он вполне себе позволяет автоматизировать большую часть всякой рутины. В данном статье будут лежать windows bat-скрипты для разных задач.

Как подсчитать число строк в файле bat-скрипт:

:: count number of lines in file as 1st parameters
Find /V /C "" < C:\tst.txt

полный батник для подсчета строк:

@echo off
if "%1" == "" goto usage
for /f %%a in ('find /V /C "" ^< %1') do set Num_Line=%%a
echo at file %1 %Num_Line% lines
goto end
:usage
echo ERROR: Give me file name to count lines in!
echo        usage line_counter.bat file_name.txt
:end

объяснения тут
http://social.technet.microsoft.com/Forums/en-US/ITCG/thread/1867323d-e6c7-440f-83a4-2bdc9b4432d5

Как удалить все папки svn из проекта (да, все-все, и вложенные тоже): 

:: clean all project from .svn subfolders
for /f "tokens=* delims=" %%i in ('dir /s /b /a:d *.svn') do (
rd /s /q "%%i"
)

Как вывести список всех файлов в папке и всех подпапках: 

dir /B /A /S &gt; file_listing.txt

Пример установочного скрипта (когда с нсисом и иже с ними заморачиваться чрезмерно)
тут есть снипеты для
– проверка какая версия JRE установлена
– проверка наличия/существования файла по указанному пути
– извлечение файлов из архивов 7z/zip
– копирование файлов (dll библиотеки и jar-файла) в папки bin и lib JRE
– поиск файла по маске в указанной папке на примере архива java библиотеки для логирования

:: sample installation script
@echo off
echo Determine JRE installation...
FOR /F "skip=2 tokens=2*" %%A IN ('REG QUERY "HKLM\Software\JavaSoft\Java Runtime Environment" /v CurrentVersion') DO set jre_version=%%B
FOR /F "skip=2 tokens=2*" %%A IN ('REG QUERY "HKLM\Software\JavaSoft\Java Runtime Environment\%jre_version%" /v JavaHome') DO set jre_full_path=%%B
echo Ok.
::IF DEFINED jre_full_path (
::ECHO JRE version - %jre_version%, JRE path - %jre_full_path%
::)
IF NOT DEFINED jre_full_path (
echo Can't locate JRE location. You should install JRE first and execute this script again!
pause
exit
)
echo determine 7z installatin...
set zip_exec="c:\Program Files\7-Zip\7z.exe"
if NOT exist %zip_exec% (
echo Can't locate 7z executable %zip_exec%
echo You need it to extract data from archive
echo install it and run this script again
pause
exit
)
echo Ok.

:: check package integrity and unpack them

set apach_log_arch=%CD%\apache-log4j-1.2.16.zip
if NOT exist %apach_log_arch% (
echo integrity check failed - copy in current folder archive with apache log library:
echo %apach_log_arch% not exist, can't continue deployment
pause
exit
)

echo extracting %apach_log_arch%...
%zip_exec% x -y %apach_log_arch%>NUL
set apach_log_path=%CD%\apache-log4j-1.2.16\
echo Ok

:: start copy files
set JRE_BIN=%jre_full_path%\bin
set JRE_LIB=%jre_full_path%\lib\ext


for /f "tokens=*" %%f in ('dir /B /S %apach_log_path%\*NTEventLogAppender.dll') do (
set apach_log_dll=%%f
)

for /f "tokens=*" %%f in ('dir /B /S %apach_log_path%\*log4j-1.2.16.jar') do (
set apach_log_jar=%%f
)

if not defined apach_log_dll (
echo Can't find NTEventLogAppender.dll in %apach_log_path% exiting
pause
exit
)

if not defined apach_log_jar (
echo Can't find log4j-1.2.16.jar in %apach_log_path% exiting
pause
exit
)

echo Copy files...
if defined apach_log_dll xcopy %apach_log_dll% "%JRE_BIN%" /S /Y>NUL
if defined apach_log_jar xcopy "%apach_log_jar%" "%JRE_LIB%" /S /Y>NUL
:: add your own
echo Ok

echo Delete temporary files...
rmdir /s /q "%apach_log_path%"
echo Ok

echo Congratulations - all dependencies are installed

pause

Sep 12

Как добавить все файлы в svn-репозиторий

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

Если проект изначально пустой – т.е. кто-то за вас создал пустой svn-репозиторий и вам необходимо добавить туда все файлы проекта – план действий тот же – делаем чекаут пустого проекта и добавляем в папку весь свой проект.

Рекурсивное добавление всех файлов и папок в систему контроля версий svn:

3. svn add –force * –auto-props –parents –depth infinity -q

после чего синхронизируем локальную копию с рабочей:

4. svn commit

Sep 01

Портирование С++ приложений с Linux под Windows

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

Несмотря на то, что указывается Linux, описанное ниже справедливо для всех POSIX-систем – MacOs, Solaris, BSD,…

Выравнивание структур:

Windows:

__declspec( align( align_value ) )

Linux:

__attribute__ ((aligned (align_value)))

какая-нибудь простенькая макра будет полезна:

#ifdef WIN32
#define ALIGN_DATA(align_value) __declspec(align(align_value))
#else
#define ALIGN_DATA(align_value) __attribute__ ((aligned (align_value)))
#endif

Выравание структур под Windows/Linux, дополнительная информация:
Описание MSDN выравнивания для Windows: http://msdn.microsoft.com/ru-ru/library/83ythb65.aspx
Обсуждение тонкостей кросс-платформенного выравнивания структур (обратить внимание на директиву pragma pack): http://www.rsdn.ru/forum/cpp/3368697.flat.aspx
Обсуждение атрибута __attribute__ ((__packed__)) в Windows: http://stackoverflow.com/questions/1537964/visual-c-equivalent-of-gccs-attribute-packed
Описание принципов по которым можно узнать текущее выравнивание структур/классов с учетом виртуальных методов/наследования – http://www.rsdn.ru/forum/cpp/1461439.aspx

Динамическое выделение памяти с учетом выравнивания:

Windows:

Выделение памяти:

void * _aligned_malloc(
    size_t size,
    size_t alignment
);

Освобождение памяти:

void _aligned_free (
   void *memblock
);

Linux:

Выделение памяти:

int posix_memalign(
    void **memptr,
    size_t alignment,
    size_t size
);

Освобождение памяти:

void free(void *ptr); // yeah, yeah - ordinal free in posix systems do all job

Выделение памяти в куче с выравниванием, дополнительные ссылки:
MSDN описание функции _aligned_malloc – http://msdn.microsoft.com/en-us/library/8z34s9c6(v=vs.80).aspx
Список функций для работы с выравненными данными – http://msdn.microsoft.com/en-us/library/fs9stz4e(v=vs.80).aspx
описание функции posix_memalign – http://pubs.opengroup.org/onlinepubs/009696699/functions/posix_memalign.html
в общем, про выравнивание структур – http://en.wikipedia.org/wiki/Data_structure_alignment

Математические функции:

Windows:

Представление бесконечности и не числового значения:

numeric_limits::infinity()
numeric_limits::quiet_NaN( )

Проверка на NAN:

int isnan(real-floating x);

Округление:

std::floor, std::ceil
[//code]

!Обратить внимание на правила округления.

Linux:

Представление бесконечности и не числового значения:
[code lang="cpp"]
INFINITY
NAN

Проверка на NAN:

int isnan(real-floating x);

Округление:

double round(double x);

Макра:

#ifdef WIN32
#define INFINITY numeric_limits::infinity()
#define NAN numeric_limits::quiet_NaN( )
#define isnan _isnan
#endif

Ссылки по теме математических функций в Windows/Linux:
isnan от Posix – http://pubs.opengroup.org/onlinepubs/9699919799/functions/isnan.html
_isnan MSDN – http://msdn.microsoft.com/en-us/library/aa298428(v=vs.60).aspx
POSIX-овый math.h с описанием – http://pubs.opengroup.org/onlinepubs/009695299/basedefs/math.h.html

Экспорт функций:

Под Винду студия создает *.lib файлы, только в случае, если если есть функции, объявленные с соответствующий модификатором – __declspec(dllexport). Хотя вместо них можно использовать def-файлы (Module-Definition (.Def) Files). Под Linux же подобные ухищрения ни к чему – все символы/функции будут доступны из статической библиотеки. Напрашивается очередная макра для экспорта функций для Linux/Windows:

 #ifdef WIN32
 #define FOVIS_EXPORT __declspec(dllexport)
 #else
 #define FOVIS_EXPORT
 #endif

Портирование Linux-проектов на Windows, разное:

Не хватка заголовочных файлов “stdint.h” и “inttypes.h” при сборке Linux-проектов на Windows:
Необходимо поблагодарив разработчиков вот этого проекта – http://code.google.com/p/msinttypes/ – скачать готовый архив с нужными заголовками и подключить их к проекту.

Linux-Windows словарь функций:
указано название linux-функции, ее Windows аналог (если существует) и необходимые заголовочные файлы:
http://suacommunity.com/dictionary/index.php

Интересная статья на тему использования в экспортированных классах стандартных контейнеров, ворнингов c4251 – needs to have dll-interface to be used by clients of class – http://www.unknownroad.com/rtfm/VisualStudio/warningC4251.html

UPDATE 11.02.2013
получив немало новых впечатлений в процессе единоборств с библиотекой iSam, спешу добавить еще несколько легко забываемых ньюансов:

Аналоги ключей компиляции Windows/Linux:

Указать уровень оптимизации: -O2 для Linux, /O2 для Windows.
Указать выходной файл: -o для Linux, /Fo для Windows.
Указать модель исключений (при сочетании C++ и C кода): -fexceptions для Linux, /EHac для Windows.

А вообще:
список опций компилятора Visual Studio
http://msdn.microsoft.com/en-us/library/9s7c9wdw%28v=vs.71%29.aspx
список опций компилятора GNU gcc
http://gcc.gnu.org/onlinedocs/gcc/Invoking-GCC.html#Invoking-GCC

Комплексные числа

#ifdef WIN32
#include <complex>
typedef std::complex<double> name_of_your_complex_type;
#define CS_REAL(x) real(x)
#define CS_IMAG(x) imag(x)
#define CS_CONJ(x) conj(x)
#define CS_ABS(x) abs(x)
std::complex<double> I(0,1); // value 0 + 0i
#else
#include <complex.h>
#define name_of_your_complex_type double _Complex
#define CS_REAL(x) creal(x)
#define CS_IMAG(x) cimag(x)
#define CS_CONJ(x) conj(x)
#define CS_ABS(x) cabs(x)
#endif

некоторые детали по использованию комплексных чисел:
http://stdcxx.apache.org/doc/stdlibug/20-2.html

Aug 06

Ошибка линковки: some_func already defined in some_file.obj или some_file.cpp: multiple definition of some_func

Собираете эдак вы значит какой-нибудь архи-важный проект. Витаете где-то в высоких абстракциях. А то и озадачиваетесь вопросами бизнес-логики. И тут билд валится. С формулировкой:
error LNK2005: some_func already defined in some_file.obj или some_file.cpp: multiple definition of some_func(). Вполне может быть, что эту самую функцию some_func() вы лично и в глаза то не видели, и не трогали, и ваще – какого ???

Что делать?
Ищете заголовочный файл с этой функцией.
Находите там кроме заголовка функции (или метода класса) еще и ее определение.
Если есть библиотека/объектник с искомой функцией, которую вы линкуете к своему проекту – комментируете определение в заголовочном файле. Если нет – пишите перед заголовком слово inline. Если там весь из себя c++ с классами, методы которых за каким-то лешим определены чуть ниже объявления класса (см method_A в примере ниже) – выносите их в соответствующий .cpp файл, добавляя его в сборку. Для успеха сборки будет достаточно запихнуть определение в описание класса – но как то это не по людски.Собираете проект, находите виновного и тыкаете ему в нос ниженаписанное:

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

Представьте что у вас есть такой вот хедер: header_example.h

#ifndef MY_HEADER
#define MY_HEADER

#include <iostream>

using namespace std;

inline void my_func_1()
{
        cout << "my_func_1" << endl;
};

int my_func_2(int arg1, int arg2)
{
        cout << "my_func_2"<<endl;
        return arg1+arg2;
};

class A
{
public:
	virtual ~A(){/* some implementation here*/};
	void method_A();

};

void A::method_A()
{
	// some very usefull code here
}


#endif

предположим, эти функции всю жизнь дергались исключительно из файлика: additional.cpp

#include "header_example.h"

void one_more_func()
{
        my_func_1();
};

и все было хорошо до тех пор пока их не решили задействовать в дополнительном модуле: main.cpp

#include "header_example.h"

void one_more_func();

int main(int argc, char* argv[])
{
        cout << "main "  << endl;
        one_more_func();
        return 0;
}

мейкфайл для всего этого добра выглядит так: Makefile

CC	=	g++
OBJS	=	main.o additional.o

all:	test_exec

test_exec:	$(OBJS)
	$(CC) -o test_exec $(OBJS)

%.o:	%.cpp
	$(CC) -c $< -o $@

clean:
	rm -f *.o
	rm -f test_exec

при попытке сборке линковщик озадаченно сетует:

additional.o: In function `A::method_A()’:
additional.cpp:(.text+0x0): multiple definition of `A::method_A()’
main.o:main.cpp:(.text+0x0): first defined here
additional.o: In function `my_func_2(int, int)’:
additional.cpp:(.text+0xb): multiple definition of `my_func_2(int, int)’
main.o:main.cpp:(.text+0x0): first defined here
collect2: ld returned 1 exit

что слишком много развелось функций по имени my_func_2(int, int). А мы ведь помним что такое хедеры и что значит строки #include “my_header.h” или #include “my_source.cpp”? Линкеру на вход подается два объектных файла, содержащих описаную в хедере функцию. Только его никто не предупредил что эта функция, вообще-то, одна и та же, а сам он не в силах уразуметь которую из них ему использовать при линковке.

Мораль – оставляйте в заголовочных файлах только заголовки функций, их определение – выносите в *.cpp/*.c.

Aug 06

ostringstream – как на c++ число в строку перевести

Навязший уже на устах вопрос на собеседованиях – как на крестах целое число перевести в строку. Многие начинают вспоминать старые добрые sprintf, itoa. Cпору нет, с некоторыми оговорками их вполне можно использовать для представления целых и не очень чисел в виде массива символов. Но если мы говорим о c++ (именно что си с плюсами) – есть более удобное и универсальное решение.

Стандартная библиотека содержит незаслужено малоизвестный класс – ostringstream. Он предоставляет удобный интерфейс потоков ввода-вывода и прекрасно пережевывает все встроенные типы данных. Результирующую строку легко получить с помощью метода str();

Небольшой пример демонстрирующий возможности класса ostringstream для преобразования целых и дробных чисел в обычную std:string.

#include <iostream>
#include <sstream>
#include <string>

using namespace std;

int main(int argc, char* argv[])
{
        float  v1   = 34.5691;
        string s1   = "std:string example";
        char   c1[] = "pure c array";
        int    i1   = 25;

        ostringstream out;

        out<<"float - " << v1 <<endl << "this is s1 - "<<s1<<endl;
        out << "char[] -  "<<c1<<endl <<"ordinary int - " <<i1<<endl;

        cout << out.str() << endl;

        return 0;
}

Aug 03

Где искать работу для программиста зарубежом

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

В качестве отправной точки для составления резюме можно использовать любопытную книжку – The google resume (водится в интернетах, на английском). Старенькое, но, как ни странно, не теряющее свою актуальность руководство по составлению резюме на американский лад с сайта компьютеры – тут.
Ежели английский не самое ваше сильное место (его надо подтянуть!!111) – имеет смысл поискать носителей языка, готовых за скромную мзду подправить все возможные ляпы. Таких людей всегда в избытке на всевозможных биржах труда – odesk.com/guru.com, но есть и те кто специализируются на предоставлении сервиса профессиональной корректировки резюме – например – http://www.globalenglishediting.com (не кликайте, не ссылка).

Иногда, репутация говорит сама за себя – многие работодатели мониторят активность программистов на github‘е или личных блогах. Единственный пост раскрывающий всю подноготную новаторского метода обработки данных или собственный интересный проект способен привлечь больше внимания чем самое выверенное резюме.

Отдельного упоминания заслуживают и ваша сетевая репутация – если вы специалист в какой-то области и ваша репутация на stackoverflow это подтверждает – работодатели будут рвать друг-дружку в клочья за вас.
http://codility.com/, http://www.topcoder.com/ – если вы предпочитаете, чтобы за вас говорили ваши дела, то эти сервисы предоставляют возможность, решая головоломные задачки или тесты, заработать себе признание не только среди коллег, но и среди работодателей.

Возможно, имеет смысл вложиться в подтверждение своей экспертизы, получив _уважаемый_ сертификат – например от brainbench‘а, тем более что там частенько проводятся акции, когда в тестировании по некоторым технологиям можно принять участие бесплатно.

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

  1. www.linkedin.com – профессиональная интернациональная соц сеть
  2. www.xing.com – профессиональная соц. сеть, популярна в Европе
  3. www.viadeo.com

Если вы привыкли ловить на живца – крупные международные хантинговые сайты

  1. www.glassdoor.com
  2. www.monster.com
  3. http://www.jobserve.com
  4. www.dice.com – статьи посвященные IT и море вакансий
  5. www.indeed.com – удобный и лаконичный поиск
  6. www.gigajob.com
  7. www.efinancialcareers.com – работа в финансовом секторе
  8. http://www.computerfutures.com/

Полезные ссылки

  1. www.salary.com – этот сайт поможет составить представление о примерном уровне зарплат.
  2. www.payscale.com – любопытный ресурс для того чтобы примерно представлять себе уровень зарплат в индустрии. Содержит материалы посвященные эффективному поиску работу.
  3. http://blog.upstart.com/2013/05/how-to-negotiate-job-offer.html – как обсуждать условия работы чтобы не продешевить
  4. www.meetup.com – для социализации на новом месте

Поиск работы в США

  1. www.10xmanagement.com – интересный подход к подбору персонала – данная компания сама проверяет вашу квалификацию и, на основе результатов, может связать вас с тем или иным клиентом. В том числе для частичной занятости.
  2. http://gaganpreet.github.io/hn-hiring-mapped/src/web/ – это вакансии от стартапов
  3. http://www.sql.ru/forum/1029564/podborka-komu-v-ssha-i-ne-tolko – общие рекомендации по составлению резюме для поиска работы в США
  4. https://forum.privet.com/viewtopic.php?f=2&t=180806 – личный опыт – поиск работы в США
  5. http://islandofatlas.net/2013/10/04/a-hackers-guide-to-the-bay-area.html – советы бывалых по Силиконовой долине
  6. http://habrahabr.ru/post/126708/ – жизнь программиста в Кремниевой долине и полезные советы по быту
  7. http://news.dice.com/2011/12/14/job-hunting-silicon-valley – некоторые советы по поиску работу в кремниевой долине
  8. http://blog.sendtoinc.com/2013/12/11/silicon-valley-internship-j1-visa/ – как устроиться интерном в стартап

Поиск работы в Канаде

  1. www.workopolis.com – работа в Канаде
  2. http://artefact.lib.ru/canada/ – масса практической информации о тонкостях иммиграции в Канаду

Поиск работы в Германии

  1. www.stepstone.de один из самых популярных сайтов для поиска работы в Германии
  2. www.jobomat.de
  3. www.meinestadt.de
  4. www.kleinanzeigen.de
  5. www.academics.de
  6. www.opportuno.de
  7. www.arbeitsagentur.de
  8. http://habrahabr.ru/post/184512/ – личный опыт – работа в Германии

Поиск работы в Англии

  1. www.indeed.co.uk
  2. www.lawfirmuk.net/immigration_genaralinfo.html – информация по рабочим визам в Англию

Поиск работы в Австралии

  1. www.seek.com.au
  2. www.careerone.com.au
  3. habrahabr.ru/post/143617/ – личный опыт – Австралия рабочая иммиграция

Поиск работы в Голландии

  1. http://habrahabr.ru/sandbox/60439/ – личный опыт – поиск работы в Голландии
  2. http://forum.awd.ru/viewtopic.php?f=76&t=173177 – личный опыт – Нидерланды рабочая иммиграция

Поиск работ во Франции

  1. www.jobsinparis.fr – работа во Франции для англоязычных

Поиск работы на Кипре

  1. www.cyprusjobs.com – работа на Кипре

Поиск работы в Болгарии

  1. http://zayac7777.livejournal.com – переезд работа в Болгарии

Поиск работы в ОАЭ и сопредельных государств залива

Здесь востребованы в основном веб-разработчики и специалисты уровня архитекторов. Нет налогов. Достаточно низкий общий уровень it.

  1. http://dubai.dubizzle.com/jobs/ – вакансии в Дубае
  2. http://www.bayt.com/
  3. http://www.naukrigulf.com
  4. http://chatru.com/uae/index.php/topic,204067.0.html – список рекрутинговых агентств

Учеба за рубежом

  1. http://scholarshipdb.net/ – агрегатор вакансий для аспирантов и кандидатов наук вузов всего мира
  2. http://habrahabr.ru/post/142854/ – учеба в Японии
  3. http://habrahabr.ru/post/173413/ – Поступление в MIT
  4. http://habrahabr.ru/post/169791/ – Магистратура в Германии

Update 17.05.2014

Удаленная работа

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

  1. www.odesk.com
  2. www.guru.com
  3. www.elance.com
  4. www.utest.com
  5. www.scriptlance.com
  6. www.freelancer.com – вобравший в себя www.getafreelancer.com и www.rentacoder.com