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 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

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
9) added Windows specific exports to almost all classes

Why do you have to edit some iSam sources:

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”
     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 (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
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 –
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

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).

how to build LAPACK (for use via CHOLMOD) –
Prebuilt libraries for Microsoft Visual Studio –

Идеальный процесс разработки – утопия или 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 – хорош тем что включает в себя из коробки все вышеперечисленное и мериады того упомянуто по ссылкам ниже –
TeamCity (бесплатная лицензия для небольших проектов) –
С этими лично не знаком – но, судя по отзывам, заслуживают внимания:
CruiseControl – бесплатный целиком и полностью –
Любопытен Apache Continuum – если ваш проект на maven – то развертывание проекта сводится к указанию pom-файла –


Введение в Continuous Integration на русском:

Лаконичная памятка-шпаргалка по Continuous Integration – (на момент написании статьи доступен для скачивания напрямую вот отсюда)

Фаулер про Continuous Integration:
Фаулер про Continuous Integration совместно с базами данных:
Фаулер про Continuous Delivery:

сравнение систем непрерывной интеграции –
сравнение систем создания документации –
сравнение систем по управлению проектами –
сравнение систем отслеживания ошибок –
Список систем для авто-сборки –

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

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 – карта мира и траектория движения робота в нем

В общем случае 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. На момент написания – инструкция по сборке устарела и требуется как следует прошерстить раздел на предмет каждой ошибки. Гипотетически, если следовать уточнениям в ссылках ниже – и использовать эталонную систему авторов – т.е. 64 разрядную убунту – должно работать. Лично я собрать то ее собрал (на убунте 32), убив пару дней, однако спорадически возникающие сегфолты и пропадающий gui задушил желание поиграться на корню.

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

  1. Ошибки вида can’t locate node, can’t find node – лечатся с помощью
  2. Ошибки rosmake:
    1. Во-первых не надо лениться заглядывать в лог файл сборки.
    2. Во-вторых перед сборкой желательно ознакомиться с инструкцией –
    3. если не помогает – читать до просветления:
  3. Если при сборке ноет что не находится findg2o.cmake – надо его найти в пакете g2o и либо смейк-скрипт подправить для rgbdslam либо сам файл переименовать.
  4. Ошибки запуска (вида can not locate launch file) – см тут.
  5. И, на посошок, репозиторий ежели что для всего проекта хранится тут –

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

Еще есть интересная библиотека Phovo. Скачать ее можно оттуда – В своем составе, кроме всего прочего имеет приложения использующее SLAM-реализацию из mrpt, и реализованные автором алгоритмы визуальной одометрии (на основе

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

Также учтите что для того чтобы завести NVidea toolkit под линуксом – придется немного попотеть: как установить cuda toolkit под ubuntu –

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

DBow: Hierarchical bag-of-word library for C++ – описание
последняя версия DBoW –

iSAM: Incremental Smoothing and Mapping
по мотивам –
страничка автора iSam:

Еще одна из вариаций SLAM-backend (на этапе оптимизации позволяет изменять структуру графа, ускоряя процес оптимизации)

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

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

ну и вика:

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

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

Karto – коммерческая версия SLAM (есть триалка и опенсурсный вариант с последним коммитом от 2010 года)
в описании проскальзывали утверждения о том что работает лучше чем iSam

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

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

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

как 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++;)
	{[RgbImageCur.step * i + j] = rgb_color_info[k].b;[RgbImageCur.step * i + j + 1] = rgb_color_info[k].g;[RgbImageCur.step * i + j + 2] = rgb_color_info[k].r;

по ссылке расписано как произвести обратную операцию – скопировать данные из контейнера Mat:

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;

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

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

В данной статье речь пойдет о библиотеке 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 –

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 система упомянутая во втором этапе детально описана там

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

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

Есть куча однотипного файлА, содержимое которых надо последовательно мапить в память, да потом еще и процессить. Есть снипет на прибустованных крестах для сей благородной цели: в текущей директории, в лексикографическом порядке, все файлы с расширением .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*) &vector_of_int[0], size);

// Close the file

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
echo ERROR: Give me file name to count lines in!
echo        usage line_counter.bat file_name.txt

объяснения тут

Как удалить все папки 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!
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
echo Ok.

:: check package integrity and unpack them

set apach_log_arch=%CD%\
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

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

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

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


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

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

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

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

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

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

4. svn commit