Aug 03

CUDA+Visual Studio-NVidea NSight

…Обыденный при-дедлайновый раш. Лица с ярко выраженными следами напряженных раздумий. Все вокруг словно наэлектрилизовано, но при этом чувствуется легкий привкус надежды на светлое будущее. Тем более вроде бы удалось распараллелить алгоритм на CUDA, осталось все это собрать да слинковать…

Итак, вводные: некоторый модуль надо быстро-быстро собрать на студии (Visual Studio 10 Prof если быть точным). Этот модуль страстно хочет вызвать CUDA ядро. NVidea в тот момент, как раз приходила в себя, опосля пропажи паролей из developer’s zone. По этому поводу, на всякий случай, все ссылки на загрузки вели на страничку, живоописующую меры, принятые корпорацией в ответ на произвол хакеров. В связи с чем доставить на студию готовую примочку для компиляции *.cu файлов – NVidea Nsight было невозможно.

Что-ж, переходим к плану Бе – краткая памятка как компилировать CUDA ядро (*.cu) на Visual Studio:

  1. добавляем *.cu файл к проекту (Add->Add Existing Item) и выбираем наш файл My_Cuda_Kernel.cu
  2. щелкаем его правой кнопкой мыша и выбираем Свойства (Properties)
  3. находим пункт Item Type и вместо (Does not participate in build) Не учавствует в сборке выбираем – Custom Build Tool, ака ща я все сам соберу
  4. жмем Apply
  5. в свойствах появляется новый элемент – Custom Build Tool – в данном разделе нас интересуют Outputs and Command Line
  6. в вывод (Outputs) заносим что-нибудь вроде $(Platform)/$(Configuration)/My_Cuda_Kernel.cu.obj
  7. а в командную строку – непосредственно вызов компилятора: 
    cd c:\My_Project_Dir\src\cuda
nvcc -c -D__CUDACC__ My_Cuda_Kernel.cu 
-o ../../$(Platform)/$(Configuration)/My_Cuda_Kernel.cu.obj 
-gencode arch=compute_30,code=sm_30 -gencode arch=compute_30,code=compute_30 
--ftz=true --prec-div=false --prec-sqrt=false 
-DNVCC --include-path .,..,d:\Additional_Include_Dirs\include

При этом:

путь к nvcc(.exe) – должен быть в переменной системного окружения PATH
предполагается что объектники для *.cu и *.cpp файлов валятся в c:\My_Cuda_Project_Dir\$(Platform)\$(Configuration), а сами исходники лежат соответственно в c:\My_Cuda_Project_Dir\src и c:\My_Cuda_Project_Dir\src\cuda.
флаг -c – подсказывает компилятору что мы желаем видеть в результате сборки объектный файл
флаг -o – подсказывает как его назвать и куда положить
__CUDACC__,NVCC – данные флаги показывает что компиляция производится с помощью nvcс – и могут быть использованы в самом коде для разделения исходного кода на то, что должно компиляться хост компилятором, а что с помощью nvcc.
–ftz=true –prec-div=false –prec-sqrt=false – влияют на точность вычислений – чем меньше точность – тем быстрее, чтобы использовать упрощенные вычисления надо указать флаг –use_fast_math.
-gencode arch=compute_30,code=sm_30 – используя такой флаг мы указываем, под какие архитектуры мы будем собирать (их можно указывать несколько) наш модуль.
compute_30 – compute_* – мы указываем виртуальную архитектуру – это некоторый обобщенный набор методов которые будут поддерживаться
sm_30 – sm_* – указание конкретного устройства, набор инструкций которого мы хотим использовать и на котором предполагается наш код запускать. Кроме этого, мы указываем что мы хотим сгенерировать код для Just In Time Compilation – т.е. в нашем модуле будут не только конкретные инструкции для той или иной архитектуры, но и их промежуточное представление – PTX – оно может быть использовано драйвером видео-карты для компиляции наиболее оптимального набора инструкций, в случае если мы будем запускать наш код на более новых архитектурах.
Указанный отдельно, флаг arch – указывает, возможности какой архитектуры будут использоваться (при этом обратной совместимости нет и если вы собрали что-то под sm_30 – никто не гарантирует что это будет работоспособно на sm_20). Также надо принимать во внимание различие между минорными версиями архитектур одного поколения – код использующий возможности sm_13 (в которой была добавлена поддержка операций двойной точности) не будет работать на sm_12 (хотя возможно эмуляция данной функциональности).
Указанный отдельно флаг code – показывает под какую конкретную архитектуру видеокарты мы хотим собрать наш модуль

Литература по теме:
The CUDA Compiler Driver NVCC из NVidea SDK – подробная и актуальная информация по флагам компиляции nvcc и разъяснение основных этапов компиляции, а также как происходит вызов CUDA кода из обычных приложений
http://stackoverflow.com/questions/9363827/building-gpl-c-program-with-cuda-module – пример компиляции и линковки CUDA кода к c++ коду
http://llpanorama.wordpress.com/2008/05/21/my-first-cuda-program/ – простой и подробный пример для CUDA hello word

Jul 16

Пример взаимодействия с web-сервисами (wcf) из андроид-приложения

Пример взаимодействия с web-сервисами (для .Net) из java-андроид-приложения. Перед использованием сниппета скачать и добавить к проекту библиотеку KSOAP2 (брать оттуда).

Предполагается, что на сервере 127.0.0.1, на порту 11111 крутится .NET-веб-сервис. Из андроид-приложения мы хотим вызвать зарегистрированную на нем функцию Remote_Function_Name с целочисленным параметром Param_For_Remote_Function. Веб-сервис поддерживает некоторую простейшую авторизацию, на основе анализа заголовка SOAP-запроса. Поэтому, формируя SOAP-запрос мы добавляем к заголовку Security_Header. Разумеется, эти параметры будут варьироваться в зависимости от NET-сервисов – что там за функции, какие у них параметры, каким образом производится анализ заголовков SOAP-запросов и т.п.

В данном примере, вызов удаленной функции осуществляется из андроид-приложения функцией Check_Soap_Service принимающей два параметра, используемые при формировании SOAP-запроса: Param_For_Remote_Function и Security_Header. Функция вызывается сразу при создании класса activity в методе onCreate().

Данные в тело (body) SOAP запроса добавляются вызовом метода addProperty. В данном примере тело запроса содержит только одну пару ключ-значение – “Param_For_Remote_Function” и ее значение переданное в функцию. Эти данные будут использоваться в качестве параметров вызываемой функции. Порядок – не важен, будьте внимательнее с регистром букв в названиях. Данные в заголовок SOAP запроса добавляются через формирования списка значений типа Element и передачей этого списка в качестве дополнительного параметра объекта soapEnvelope – soapEnvelope.headerOut. Список формируется с помощью отдельной функции Form_Header.

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

import org.ksoap2.SoapEnvelope;
import org.ksoap2.serialization.PropertyInfo;
import org.ksoap2.serialization.SoapObject;
import org.ksoap2.serialization.SoapPrimitive;
import org.ksoap2.serialization.SoapSerializationEnvelope;
import org.ksoap2.transport.HttpTransportSE;
/*
additional imports goes here
*/

public class Check_Soap extends Activity
{
    // for example only,
    // in real app you better get this data from settings file,
    private static final String SOAP_ACTION="http://tempuri.org/IServiceData/Remote_Function_Name";
    private static final String SOAP_METHOD_NAME="Remote_Function_Name";
    private static final String URL = "http://127.0.0.1:11111/ServiceData.svc";
    private static final String NAMESPACE="http://tempuri.org/";

    private Element Form_Header(String Security_Header_Value)
    {
        Element h = new Element().createElement(NAMESPACE, "Security_Header");
        h.addChild(Node.TEXT, Security_Header_Value);

        /*
        for several nodes it would be:
        Element h = new Element().createElement(NAMESPACE, "Security_Header");
        Element h_first = new Element().createElement(NAMESPACE, "Security_Header_Value_First");
    	h_first.addChild(Node.TEXT, Security_Header_Value_First);
        h.addChild(Node.ELEMENT, h_first);
        Element h_second = new Element().createElement(NAMESPACE, "Security_Header_Value_Second");
    	h_second.addChild(Node.TEXT, Security_Header_Value_Second);
        h.addChild(Node.ELEMENT, h_second);
        */
        return h;
    }

    public void Check_Soap_Service(String Security_Header,int Param_For_Remote_Function)
    {

        SoapObject Request = new SoapObject(NAMESPACE,SOAP_METHOD_NAME);

        // here you form body of your SOAP-request
        Request.addProperty("Param_For_Remote_Function", Param_For_Remote_Function);

        SoapSerializationEnvelope soapEnvelope = new SoapSerializationEnvelope(SoapEnvelope.VER11);
        soapEnvelope.dotNet = true;

        soapEnvelope.setAddAdornments(false);
        soapEnvelope.encodingStyle = SoapSerializationEnvelope.ENC;
        soapEnvelope.env=SoapSerializationEnvelope.ENV;
        soapEnvelope.implicitTypes = true;

        // here you form additional header's data for your SOAP request
        soapEnvelope.headerOut = new Element[1];
        soapEnvelope.headerOut[0] = Form_Header(Security_Header);

        soapEnvelope.setOutputSoapObject(Request);

        HttpTransportSE aht = new HttpTransportSE(URL);
        aht.debug = true;

        try
        {
            aht.call(SOAP_ACTION, soapEnvelope);
            SoapPrimitive resultString = ( SoapPrimitive)soapEnvelope.getResponse();
            //TODO: appropriate parsing and processing routine for resultString
            Log.i("Check_Soap_Service","resultString -  "+resultString);
        }
        catch (Exception e)
        {
            Log.i("Check_Soap_Service","Exception : "+e.toString());
        }
        finally
        {
            Log.i(getClass().getSimpleName(),"requestDump : "+aht.requestDump);
            Log.i(getClass().getSimpleName(),"responseDump : "+aht.responseDump);
        }
    }

    @Override
    public void onCreate(Bundle savedInstanceState)
    {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.main);

        // test our web-service
        // fake parameters for remote function
        String Security_Header_String="User_ID_1";
        int Soap_Request_Id=1;
        Check_Soap_Service(Security_Header_String,Soap_Request_Id);
    }
}

Полезные ссылки KSOAP2, SOAP в связке с JAVA и Android
вики KSOAP2:
http://code.google.com/p/ksoap2-android/wiki/CodingTipsAndTricks
Взаимодействие с .NET-вебсервисами из андроида:
http://romenlaw.blogspot.com/2008/07/consuming-wcf-web-service-using-java.html
пример реализации клиента для аспшного вебсервиса:
http://naveenbalani.com/index.php/2011/01/invoke-webservices-from-android/
полный пример андроид-клиента для SOAP-запросов:
http://stackoverflow.com/questions/2589486/how-to-call-a-wcf-service-using-ksoap2-on-android
Андроид, формирование заголовков SOAP-запросов:
http://stackoverflow.com/questions/2566026/ksoap2-android-not-valid-soap
http://stackoverflow.com/questions/5613675/how-to-set-soap-header-using-ksoap2-android
пример REST-веб-сервиса:
http://senior.ceng.metu.edu.tr/2009/praeda/2009/01/11/a-simple-restful-client-at-android/
Основные ошибки работы с SOAP-сервисами из андроид:
http://stackoverflow.com/questions/6215480/trying-to-connect-android-app-to-net-svc-webservice-and-server-responds-media
http://stackoverflow.com/questions/5921170/invoke-wcf-web-service-using-ksoap2-on-android-app-failed-with-the-following-erro
Не забывайте о правильности настроек самого NET-сервера:
http://stackoverflow.com/questions/6166589/making-a-wcf-service-android-compatible
утилита для отслеживания веб-трафика (в том числе для .NET проектов)
http://www.fiddler2.com/fiddler2/
описание KSOAP:
http://androidwsproject.blogspot.com/2010/04/android-ksoap2-framework.html
http://unknownerror.net/2011-06/41434-ksoap2-webservice.html
http://people.unica.it/bart/2010/12/03/ksoap2-patch-for-user-defined-objects-and-arrays/

Jul 13

Как работает Kinect Fusion

Описание алгоритма Kinect Fusion


На основе анализа кадров глубины, получаемых с сенсора Kinect (или аналогов) формируется детализированное 3D-представление обозреваемой сцены. Данные обрабатываются в реальном режиме. Высокая скорость и детализация достигается за счет использования для всех расчетов GPU, а также новаторским подходом к применению уже известных алгоритмов. В открытой реализации данного проекта в рамках библиотеке PCL поддержимаются лишь два последних поколения видео-карт (с расширенным набором инструкций и большим числом ядер) – архитектуры Fermi и Kepler (по спецификации NVidia – архитектуры 20 и 30 соответственно).

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

  • преобразование показаний камеры глубины в трехмерное облако точек и нормалей к ним
  • вычисление матрицы преобразования между двумя облаками точек, полученных с камеры глубины на текущей и предыдущей итерации, на основе этого преобразования определяется смещение камеры в глобальном пространстве, используя алгоритм ICP – Iterative Closet Point.
  • обновление сцены – на основе полученных данных мы формируем новые значения функции TSDF, которая и содержит текущее представление о сцене
  • используем значения функции TSDF для рендеринга (визуализации) сцены а также получаем сглаженные значения облака точек и нормалей к ним.

Судя по отзывам на www.pcl-developers.org – при известном желании возможно использовать топовые карты предыдущих поколений (архитектуры 13). В более старых моделях видео-карт отсутствует поддержка ряда операций над числами с плавающей точкой, что делает невозможным компиляцию. Эмуляция данных операций – теоретически возможна – но даже при условии успешной имплементации таковых, скорость обработки будет не удовлетворительной.

Очевидное ограничение на размер сцены присутствует в модуле KinFu. Расширение алгоритма Kinect Fusion – Kintinuous предлагает по мере приближения камеры к границам куба – выгружать часть сцены из памяти видео-карты во внутренее представление модели “всего мира”. Эта идея нашла свое отражение в модуле KinFu Large Scale.

А теперь все тоже самое, но по шагам:

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

I Этап – подготовительный

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

II Этап – Бесконечный цикл работы ядра алгоритма Kinect Fusion, состоящий из четырех основных шагов

1) преобразование показаний камеры глубины

Каждый кадр глубины перед обработкой проходит фильтрацию (билатеральным фильтром) – для сглаживания. Преобразуем карту глубины в набор из 3D-вершин – (X,Y,Z) – облако точек (в координатном пространстве камеры – НЕ глобальном). Банально каждая точка из матрицы глубины перемножается с матрицей обратной для матрицы камеры на отдельном ядре GPU. Вычисляем нормали к ним (направление перпендикуляров к плоскости) используя данные о соседних с текущей вершинах.

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

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

2) Определение смещения камеры в пространстве относительно предыдущего фрейма.

Для этого используем ICP – Iterative Closet Point алгоритм, обрабатывая два облака точек – с текущего и предыдущего кадров глубины, а также знание о предыдущей позиции камеры в глобальном пространстве. Здесь надо принять во внимание используемое упрощение – расхождение между двумя фреймами глубины будут не значительны из-за особенностей кинекта. Это позволяет использовать в ICP не облака точек, а их проективную проекцию на матрицу глубины (point-to-plane вместо point-to-point) – выгода очевидна – меньше данных для обработки – быстрее.
Алгоритм прост и распаралеливается на GPU:

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

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

3) интеграция полученных данных в общую сцену

Зная положение камеры в глобальном пространстве мы можем перевести показания камеры с текущего кадра глубины в нашу общую “картину мира” представляемую в Kinect Fusion в виде функции особого вида – TSDF.

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

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

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

4) восстановление общей сцены

Для рендеринга используется метод бросания лучей “ray casting“. Сцена строится на основе замеров пересечения лучей с визуализируемой поверхностью. Каждый луч – направление взгляда с определенной точки на воксельный куб. Каждое ядро GPU занимается поиском вокселя, сквозь который проходит луч, в котором, при этом, значения TSDF функции – меняет знак – т.е. там находится некоторая поверхность. Освещение сцены (тени, отражения) вычисляются на основе следующих, дополнительных проходов луча. Для теней – инициируется еще один луч направленный от точки поверхности к источнику свету – в случае пересечения луча с поверхностью – воксель, находящийся в точке нового пересечения затеняется. Для отражений направления луча изменяется на основе вычисленного значения нормали к найденной точке поверхности.

Данные полученные на этапе raycasting’a могут быть использованы для более точного позиционирования камеры в глобальном пространстве. Вычисляемые значения нормалей, а так же обратная проекция облака точек на карту глубины полученные на этапе бросания лучей на модель (а чем не аналог работы сенсора кинекта?) получаются более сглажеными и, за счет интеграции с общим представлением модели – более полными.

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

Kinect Fusion и бесконечная сцена: Kintinuous, KinFu Large Scale и их некоторые различия

Из описания алгоритма очевидно что размер сцены ограничен размерами воксельного куба, а детализация – заданными размерами проецируемой области (KinFu – 3 метра). Для преодаления ограничений заложенных в алгоритм Kinect Fusion – в настоящее время существует два независимых расширения алгоритма: Kintinuous и KinFu Large Scale

Во время инициализации работы алгоритма – начальная позиция камеры рассчитывается как центр этого куба. Оба расширения предлагают задать некоторое граничное значение (расстояние от центра куба до текущего положения камеры в этом кубе), при достижении которого производится сдвиг сцены, хранимой в кубе. В KinFu Large Scale можно задать процент перекрытия двух соседних кубов – по умолчанию 2.5% от размера куба (в Kintinuous – 2 вокселя). Память видеокарты, в которой хранится куб – трехмерный массив из вокселей – трактуется как циклический буфер, таким образом модификация оригинального алгоритма KinFu сводится к дополнительным изменениям индексации этого массива во время обновления значений TSDF функции, описывающей сцену и этапа “бросания лучей”, для вычисления сдвига и поворота на основе полученных данных.

UPDATE от 22.08.2012 не верно был описан принцип использования FOVIS в Kintinuous
Дополнительно, в Kintinuous для работы со сценой содержащей обширные гладкие участки (стены/шкафы) с которыми алгоритм ICP, используемый для позиционирования камеры в пространстве, справлялся не лучшим образом – наблюдается частые потери в пространстве и, как следствие, “наслоение” карт глубины и смазанная сцена. В Kintinuous же карты глубины подаются в одну из реализаций методов визуальной одометрии – FOVIS, предоставляющую более стабильное определение местоположения камеры и минимизирующее число Reset’ов – ситуаций когда камера заплутается в пространстве. Причем используется какая-то реализация FOVIS на CPU.

Данные о сцене, которые выходят из области анализа (не попадают в сдвинутый куб) выгружаются в промежуточное представление. В Kintinuous это представление – pose-graph. Каждое новое положение (узел графа) содержит соответствующую поверхность, полученную для этого участка сцены, а также данные о положении текущего куба в рамках глобальной системы координат,и матрица поворота и вектор сдвига. В Kinfu Large Scale для этого используется особая структура, созданная на основе облака точек.

После этапа бросания лучей, облако точек, представляющее собой изученную поверхность, подвергается триангуляции (greedy mesh triangulation). В KinFu Large Scale для триангуляции используется алгоритм движущихся кубиков (marching cubes). При запросе накопленные данные интегрируются в общую модель глобальной сцены.

Существующие ограничения KinFu Large Scale: не терпит резких перемещений камеры, не всегда корректно производится вычисление нового положения камеры во время сдвига куба, работает не стабильно. Зато уже сейчас есть масса информации для экспериментов.

Создатели Kintinuous обещают в скором времени выложить свой код в открытй доступ, в состав PCL.

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

В основе статьи лежит анализ брошюр от Microsoft, а также материалы проекта PCL, в особенности, исходный код модулей KinFu и KinFu Large Scene из trunk, предлагающий свободную реализацию Kinect Fusion, а также вспомогательные работы по используемым алгоритмам.
KinectFusion: Real-Time Dense Surface Mapping and Tracking
KinectFusion: Real-time 3D Reconstruction and Interaction Using a Moving Depth Camera

форумы библиотеки PCL – кладезь знаний о внутренностях реализации KinFu и не только:
www.pcl-developers.org
www.pcl-users.org

в качестве возможных вариаций для применения:
робот, использующий данный метод для локализации себя на неизвестной местности и составлении карты этой местности: http://code.google.com/p/ic2020/wiki/Installation
свободно распространяемая версия метода FOVIS: http://code.google.com/p/fovis/
http://developkinect.com/ – интересный сайт с обзором возможных применений kinect и смежных технологий
Рабочая (но закрытая) реализация Kinect Fusion на OpenCL. Отсканированные элементы сцены могут быть распечатаны на 3d-принтере – http://reconstructme.net/

Описание алгоритма Kinect Fusion простым языком (насколько это вообще возможно) на английском:
http://razorvision.tumblr.com/post/15039827747/how-kinect-and-kinect-fusion-kinfu-work

Любые поправки и уточнения горячо приветствуются! 🙂

Jul 12

Your Kindle Needs Repair – как восстановить читалку

Одним безмятежным вечером, страдая от приступа прокрастинации я неожиданно обратил внимание то, что прошивка в моем киндле далеко не самая последняя, а на сайте амазона инструкция по обновлению прошивки состоит из пяти простых и понятных шагов… этой невинной инструкцией я и обязан увлекательнейшими часами восстановления своей разлюбезной читалки категорично утверждающей что:
“Your Kindle Needs Repair.
Please contact Kindle Customer Service at
http://www.kindle.com/support”.

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

Обратите внимание – данный способ я лично пробовал для своего Kindle Touch. На других – не проверял, но подозреваю что с небольшими изменениями он применим и для иных версий читалок.

UPDATE 27.10.2014
По состоянию на сейчас, удобнее восользоваться лив-сд диском который сам все за вас сделает 🙂
кубрик:
инструкция по применению на русском: тут.

Что нам потребуется для возвращения kindle к жизни:

1) KindleSelectBoot – пакет содержащий утилиту MfgTool и профили загрузки для киндла (diags, fastboot, main)
скачать отсюда – ссыль
2) fastboot – данное тулзуевина поможет нам подменить испорченные образы системы, на исправные
скачать отсюда – ссыль
3) libusb – драйверы и библиотеку для работы с киндлом в режиме fastboot
брать отсюда – ссыль
4) ядро системы и вспомогательные системные файлы для Kindle: mmcblk0p1.img (основной образ системы), mmcblk0p2.img (образ для диагностики с поддержкой SSH)
брать отсюда (с разумением какая версия и для какого устройства Touch/не Touch вам нужна) – глянуть список
5) Putty для Windows – выбрать нужную версию там

Если система не Windows – искать по выше указанным названиям на http://www.mobileread.com/forums.

Как восстановить киндл – подробная инструкция:

1) В корень диска распакуем KindleSelectBoot (наприме в C:\KindleSelectBoot)
2) подключаем киндл по USB к компьютеру
3) зажимаем кнопку питания на киндле, когда она начинает мигать – стремительно зажимаем кнопку Home и после этого, нежно отпускаем кнопку питания. Только после этого отпускаем кнопку Home.
4) Windows осознает что в систему добавлено новое устройство (USB/HID device) и пытается ставить драйвера. Если самостоятельно найти не может – помогаем.
5) Запускаем MfgTool из папки KindleSelectBoot
6) Выбираем profile – Kindle diags и нажимаем Start
7) на экране киндла появляется диагностическое меню – выбираем там U) Usb device mode
8) Kindle подключается как флешка и со слезами на глазах можно наблюдать на нем все наши книжки
9) копируем прямо в корень файл новый образ системы – mmcblk0p1.img
10) отключаем kindle-флешку, повторяем пункт 3
11) перезапускаем MfgTool
12) выбираем profile – fastboot и жмем Start
13) Windows приходит к мысли что в системе появилось еще одно USB-устройство, для того чтобы ее использовать – необходимо установить драйвер от libusb. Для этого распакуем скачанный архив libusb и вручную укажем Windows где ждет не дождется своего часа нужный нам драйвер (если хотите – запустите установщик inf-wizard из корня папки с libusb – везде жать next, а в конце – “Install now …”).
14) распковываем содержимое архива c fastboot в корень диска (наприме C:\fastboot) – т.е. путь к самой программе будет c:\fastboot\fastboot.exe
15) в эту же папку помещаем второй образ системы (диагностический с поддержкой ssh) – mmcblk0p2.img – т.е. полный путь будет c:\fastboot\mmcblk0p2.img
16) запускаем командную строку: нажимаем Windows+R (пуск-выполнить и вводим cmd)
17) в коммандной строке последовательно:

cd c:\fastboot
fastboot flash diags mmcblk0p2.img
fastboot setvar bootmode diags
fastboot reboot

при этом киндл перезагружается с новым ядром в котором есть ssh-сервер
18) переподключаем kindle к нашему компьютеру – повторяем пункт 3
19) перезапускаем MfgTool снова в режиме диагностики
20) на kindle запускаем ssh сервер: последовательно выбирая N)->U)->Z)->X)->X)
21) Windows в очередной раз сходит с ума от нового устройства – на этот раз это RNDIS/Ethernet Gadget, драйвер для которого он не в настроении находить самостоятельно. Поможем ему выбирая драйвер вручную из списка доступных: сетевой адаптер ->производитель – Microsoft Corporation, тип – Microsoft Windows Mobile Remote Adapter. (спасибо этому посту)
22) в сетевых соединениях получается новое подключение – нам надо залезть в одну сеть с нашим киндлом (192.168.15.0) – указываем что мы, например, 192.168.15.3 и пробуем пропинговать сам kindle – его ip – 192.168.15.244
23) запускаем putty и подключается к киндлу по указанному айпи через ssh-соединение

login:root
password:mario

24) а теперь заливаем новый рабочий образ:

dd if=/mnt/us/mmcblk0p1.img of=/dev/mmcblk0p1 bs=4K

Все. теперь у вас новая система (прошивка 5.0.0).
25) Для уверенности можете удалить настройки/закладки/коллекции – но скорее всего это не требуется и ваша читалка вернулась на круги своя (проверить это можно вывести его из режима диагностика см далее). Если же вы хотите почистить все окончательно:

sync
dd if=/dev/zero of=/dev/mmcblk0p3 bs=4K count=1K

26) теперь осталось вывести аппарат из режима диагностики:
вводим в консоли

rm /mnt/us/ENABLE_DIAGS
idme -d --bootmode main
reboot

Ну а уже после этого можно снова попытаться обновить прошивку! 😉

Полезные ссылки по восстановления kindle:

http://beznervov.com/computers/hard/elektronnye-knigi/kindlu-touch-unbrick-debrick-i-polnyj-navorot/ – Подробная инструкция на русском с картинками. Там же есть ссылка на весь набор программ для Windows в одном архиве, однако там еще содержатся моды для киндла и драйвер для RNDIS/Ethernet Gadget у меня категорически отказался работать.

http://www.mobileread.com/forums/showthread.php?t=170929 – Английский первоисточник (обратите внимание – там масса пользительных ссылок).

Jun 07

аналог команды из линукса в …

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

И приходится задавать поисковикам одинаковые вопросы:

Например, какой в Solaris аналог линухового trace, или какая команда выполняет роль ldd в MacOs.

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

http://bhami.com/rosetta.html

Apr 03

pure c – как получить список сетевых интерфейсов

На линуксах. С помощью getifaddrs. Не забыть освобождать память под ifaddrs.
Эта функция просто выводит айпи адреса сетевых интерфейсов.
Если необходимо получить стастику – надо работать с адресами семейства AF_PACKET.

int check_net_interfaces()
{
    struct ifaddrs *ifaddr;
    int family, s;

    if (getifaddrs(&ifaddr) == -1)
    {
        perror("getifaddrs");
	return -1;
    }

    struct ifaddrs *ifa = ifaddr;
    for (ifa = ifaddr; ifa != NULL; ifa = ifa->ifa_next)
    {
        if (ifa->ifa_addr != NULL)
        {
            int family = ifa->ifa_addr->sa_family;
            if (family == AF_INET || family == AF_INET6)
            {
                char ip_addr[NI_MAXHOST];
                int s = getnameinfo(ifa->ifa_addr,
                    ((family == AF_INET) ? sizeof(struct sockaddr_in) :
                    sizeof(struct sockaddr_in6)),
                    ip_addr, sizeof(ip_addr), NULL, 0, NI_NUMERICHOST);
                if (s != 0)
                {
                    printf("getnameinfo failed - can't determine our ip_interfaces");
                    return -1;
                }
                else
                {
                    /* add some processing here */
                    printf("IP - %s",ip_addr);
                }
            }
        }
    }
    freeifaddrs(ifaddr);
    return 0;
}

Mar 30

pure c – как измерить время

Простой снипет на сях для подсчета секунд между двумя замерами:

Как мы помним, структура timeval имеет вот такой простецкий вид:

typedef struct timeval {
  long tv_sec;
  long tv_usec;
} timeval;

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

    struct timezone       tz;
    struct timeval        start_period;
    struct timeval        end_period;
    long MY_TIMEOUT_IN_SECONDS = 60; 

    gettimeofday(&start_period,&tz);

    /* some hard work here */

    gettimeofday(&end_period,&tz);

    if ( (end_period.tv_sec - start_period.tv_sec) >= MY_TIMEOUT_IN_SECONDS )
    {
         /* some reaction */
    }

В случае необходимости большей точности имеет смысл учитывать также значение tv_usec из структуры timeval.

Ссылки для развития кругозора:
1. Полезнейшие но не особо известные утилиты из sys/time.h (timeradd,timersub,timercmp,…):
http://linux.die.net/man/3/timercmp
2. Полезнейшие но не особо известные утилиты из ctime.h (clock,difftime,asctime,…):
http://www.cplusplus.com/reference/clibrary/ctime/
3. плюсовый путь – чревато добавлением новой зависимости:
http://www.boost.org/doc/libs/1_42_0/doc/html/date_time.html
4. брутальный путь – через регистры для высокой точности (там же снипеты есть)
http://en.wikipedia.org/wiki/Rdtsc

Mar 21

Симуляторы сети

Симуляторы сети:
NetSim
GloMoSim
NS_3
OMNeT++
Integrated Multiprotocol Network Emulator/Simulator

Mar 16

Back to pure C – как распарсить строку без регэкспов

Надо парсить строку. Хочется регеэкспов от Posix – но никто не обещает posix-совместимых систем. Проект сишный и плюшки C++ как то не уместны, потому же boost – нельзя. И вообще с учетом закостенелости процесса развертывания – сторонние либы включать адски не желательно. Под такие ограничения прекрасно подходит функция strtok из ANSI C.

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

    char* test_string = "a:bgf,tre";
    char* pch = strtok (test_string,":,");
    while (pch != NULL)
    {
        /*
           TODO: processing string parts
        */
        pch = strtok (NULL, ":,");
    }

Ее приемница, функция strsep умеет работать с массивом строк, но, при этом проигрывает в портабельности.
Пример использования strsep для парсинга строк, с разбивкой на пробелы и табы, нагло скопипащенный из мана:

char **ap, *argv[10], *inputstring;

for (ap = argv; (*ap = strsep(&inputstring, " \t")) != NULL;)
    if (**ap != '\0')
    {
        /*
           TODO: processing string parts
        */
       if (++ap >= &argv[10])
          break;
    }

В качестве зы – ссылка на код утилиты grep, где можно посмотреть как работать с символами wildcard при анализе имен файлов:
http://cm.bell-labs.com/cm/cs/tpop/grep.c

Mar 04

Андроид – создание Custom ListView

Рано или поздно приходит момент, когда набор стандартных виджетов становится тесен. Хочется добавить к базовым возможностям контролов дополнительные опции, способные обогатить интерфейс и улучшить пресловутый UX(User experience). Все что необходимо для расширения функциональности виджетов – немного покопаться в документации.

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

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

I Этап


1. На основе ArrayAdapter создаем свой собственный объект – My_Custom_Adapter – он будет хранить все возможные типы строк в нашем ListView (например строка с текстом и строка, где кроме текста есть какая-нибудь иконка).
2. Для хранения всех элементов – all_items в сниппете – можно использовать любой класс-контейнер (в зависимости от ваших целей) – например ArrayList. Продумайте какой-тип объектов лучше подходит для ваших целей. В нашем примере – достаточно использовать обычные строки для заголовков. Для простоты определения типа элементов ArrayList создадим TreeSet, в который будем заносить индексы элементов второго типа.
3. Переопределяем для него функцию getView() – которая в зависимости от типа строчки возвращает view, соответствующее типу строки.
4. Переопределяем функцию getItemViewType() – она возвращает тип элемента по его индексу (а все индексы элементов второго типа мы храним в TreeSet’e).
5. Определим функции для добавления строк в наш ListView обоих типов – add_Item_Type_1(), add_Item_Type_2() – в любом случае, элемент добавляется в общий массив ArrayList, но если мы добавляем элемент второго типа – его индекс заносится в контейнер типа TreeSet. Важно после любого изменения в ArrayList вызывать метод notifyDataSetChanged() – для обновления картинки на экране телефона.
6. Набор методов для обновления адаптера при изменении информации (например при пересчете каких характеристик, обновлении данных с сервера и т.п.) – удобно объединить в одну функцию – Clear_Data().

Шаблонный сниппет для создания адаптера для CustomListView.

private class My_Custom_Adapter extends ArrayAdapter
{
    private LayoutInflater my_Inflater;

    private static final int TYPE_1 = 0;
    private static final int TYPE_2 = 1;

    private TreeSet Second_Items_Set = new TreeSet();
    private ArrayList My_Custom_Object all_items;

    public My_Custom_Adapter(Context context, int textViewResourceId, ArrayList My_Custom_Object items)
    {
        super(context, textViewResourceId, items);
        mInflater = (LayoutInflater)getSystemService(Context.LAYOUT_INFLATER_SERVICE);
        this.all_items = items;
    }

    public View getView(int position, View convertView, ViewGroup parent)
    {
        int type = getItemViewType(position);
        View v = convertView;

        switch (type)
        {
            case TYPE_1:
                           v = mInflater.inflate(R.layout.base_row_for_first_type, null);
                           break;
            case TYPE_2:
                           v = mInflater.inflate(R.layout.base_row_for_second_type, null);
                           break;
            default:
                           // todo: deal with this situation
                           break;
        }

        My_Custom_Object cur_element = all_items.get(position);

        switch (type)
        {
            case TYPE_1:
                           if (cur_element != null)
                           {
                               // TODO: According to object's data
                               // fill layout with appropriate data:
                               // specified picture, text, etc
                           }
                           break;
            case TYPE_2:
                           if (cur_element != null)
                           {
                               // TODO: According to object's data
                               // fill layout with appropriate data:
                               // specified picture, text, etc
                           }
                           break;
            default:
                           // todo: deal with this situation
                           break;
        }
        return v;
    }

    public void add_Item_Type_1(final String item_name)
    {
        item_type_1_list.add(item_name);

        notifyDataSetChanged();
    }

    public void add_Item_Type_2(final String item_name)
    {
        item_type_2_list.add(item_name);
        Second_Items_Set.add(all_items.size()-1);

        notifyDataSetChanged();
    }

    @Override
    public int getItemViewType(int position)
    {
        return Second_Items_Set.contains(position) ? TYPE_2 : TYPE_1;
    }

    public void Clear_Data()
    {
        Second_Items_Set.clear();
        all_items.clear();
        clear();
    }
}

II Этап

Cоздаем лайауты для различных типов строк, а также соответствующим образом их инициируем данными в методе getView() нашего адаптера.
Ссылки на функции, которые должны вызываться при нажатии – можно прописать прямо в xml-файлах разметки, заполнив поле onClick (в сниппете это – put_name_of_your_function_here), установив значение clickable в true, или в коде – как вам удобней.

<!--?xml version="1.0" encoding="utf-8"?-->
<LinearLayout
    xmlns:android="http://schemas.android.com/apk/res/android"
        android:id="@+id/custom_row_item"
        android:layout_width="fill_parent"
        android:layout_height="fill_parent"
        android:clickable="true"
    android:onClick="put_name_of_your_function_here"
        >
<!-- PUT Your Markup here -->
</LinearLayout>

III Этап

Для лайаута самой активити используем типовый лайаут для ListView:

<!--?xml version="1.0" encoding="utf-8"?-->
<LinearLayout
xmlns:android="http://schemas.android.com/apk/res/android"
android:id="@+id/custom_list_view"
android:orientation="vertical"
android:layout_width="wrap_content"
android:layout_height="fill_parent"
>
<ListView
    android:id="@id/android:list"
    android:layout_width="fill_parent"
    android:layout_height="fill_parent"
    />
</LinearLayout>

На основе ListActivity создаем свою собственную активити, в которую добавляем созданным нами адаптер.
Создаем метод который будет устанавливать адаптер для нашей активити – Prepare_Adapter(), а также метод Update_Activity_By_Some_Rule() который будет обновлять данные в нем по некоторым вашим правилам – например подгружая соответствующие строчки для очередной записи, отображаемой в ListView.

public class My_List_Activity extends ListActivity
{

    private ArrayList all_objects = null;
    private My_Custom_Adapter Cur_Adapter;

    @Override
    public void onCreate(Bundle savedInstanceState)
    {
    	setContentView(R.layout.custom_list_view);
    	super.onCreate(savedInstanceState);
        Prepare_Adapter();
    }

    private void Prepare_Adapter()
    {
        if (Cur_Adapter == null)
        {
            this.Cur_Adapter = new My_Custom_Adapter(this, R.layout.base_row_for_first_type, all_objects);
        }
        else
        {
            Cur_Adapter.Clear_Data();
        }
        setListAdapter(this.Cur_Adapter);
    }

    private void Update_Activity_By_Some_Rule()
    {
    	Cur_Adapter.add_Item_Type_1("Test item 1");
    	Cur_Adapter.add_Item_Type_2("Test item 2");
    }
}

Android и Custom ListView еще ссылки на эту тему:
http://www.softwarepassion.com/android-series-custom-listview-items-and-adapters/
http://www.pocketmagic.net/?p=1678
http://www.androidsnippets.com/clickable-listview-items