ViBe — алгоритм вычитания фона

  • Tutorial
Предыстория

Пару лет назад, в процессе выполнения одного проекта, связанного с выделением и сопровождением движущихся объектов, было просмотрено немало алгоритмов вычитания фона, и в итоге одним из самых интересных оказался тот, о котором дальше и пойдет речь. Основной его недостаток — куча патентов, которыми он защищен. Но одно из несомненных достоинств — наличие библиотеки под Linux, которую разрешено использовать в некоммерческих проектах. На странице с его описанием можно найти эту самую библиотеку, а также demo-программы под Windows и Android, ссылки на патенты (где и можно найти основные описания алгоритма) и прочую интересную информацию.


image

Использование алгоритма

Пример использования есть в заголовочном файле библиотеки. Для изображения в градациях серого:
#include "vibe-background.h"
  
  int main(int argc, char **argv){
     // Создать модель ViBe
     vibeModel_t *model = libvibeModelNew();

     // stride - количество байт, занимаемое одной строкой изображения 
     uint8_t *image_data = acquire_image(stream);
     int32_t width = get_image_width(stream);
     int32_t height = get_image_height(stream);
     int32_t stride = get_image_stride(stream);

     // Матрица для выходных данных
     uint8_t *segmentation_map = malloc(stride * height);
  
     // Инициализируем модель первым кадром
     libvibeModelAllocInit_8u_C1R(model, image_data, width, height, stride);
  
     // Обрабатываем все следующие кадры
     // Результаты вычитания - в segmentation_map
     while(!finished(stream)){
        image_data = acquire_image(stream);
        libvibeModelUpdate_8u_C1R(model, image_data, segmentation_map);
     }

     // освобождаем память
     libvibeModelFree(model);
  }


Его внутренности

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

Структура vibeModel_t:
typedef struct
{ 
        u8b  *samples;
        u32b numberOfSamples;
        u32b sizeOfSample;
} pixel;

typedef struct
{
   pixel *pixels;
   u32b width;
   u32b height;
   u32b stride;
   u32b numberOfSamples;
   u32b matchingThreshold;
   u32b matchingNumber;
   u32b updateFactor;   
}  vibeModel;

typedef vibeModel vibeModel_t;


Что здесь зачем — будет в дальнейшем понятно из алгоритма.
Создаем модель, задаем значения по умолчанию и инициализируем random.

vibeModel *libvibeModelNew()
{
        vibeModel *model = (vibeModel*)calloc(1,sizeof(vibeModel));
        if (model)
        {
                model->numberOfSamples    = 20;
                model->matchingThreshold  = 20;
                model->matchingNumber     = 2;
                model->updateFactor       = 16;
        }
        u32b seed = time(0);
        srand(seed);
        return model;
}


Далее, чтобы не писать здесь кучу кода, предположим, что у нас есть некоторая функция
u32b getRandPixel(const u8b *image_data, const u32b width, const u32b height, const u32b stride, const u32b x, const u32b y);

которая возвращает значение случайно выбранного пикселя, находящегося рядом с пикселем [x.y]. Тогда инициализация модели выглядит так:

s32b libvibeModelAllocInit_8u_C1R(vibeModel *model, const u8b *image_data, const u32b width, const u32b height, const u32b stride)
{
        if (!model || !image_data || !width || !height || !stride || (stride<width)) return 1;
	// Сохраняем размеры кадра
        model->width  = width;
        model->height = height;
        model->stride = stride;
	// Создаем модели для каждого пикселя 
        model->pixels = 0;
        model->pixels = (pixel*)calloc(model->width*model->height, sizeof(pixel));
	if (!model->pixels) return 1;

	// Для каждой из них выделяем память под заданное число сэмплов.
        for (u32b i=0; i < model->width*model->height; i++)
        {
                model->pixels[i].numberOfSamples=model->numberOfSamples;
                model->pixels[i].sizeOfSample = 1;
                model->pixels[i].samples = 0;
                model->pixels[i].samples = (u8b*)calloc(model->numberOfSamples,sizeof(u8b));
                if (!model->pixels[i].samples) return 1;
        }

	// Заполнение модели.
	// Требуется заполнить сэмплы. При этом в один из них пишется само значение соответствующего пикселя,
	//  а остальные случайным образом заполняются значениями соседних.
        u32b n=0;
        for (u32b j=0; j < model->height; j++)
        {
                for (u32b i=0; i < model->width; i++)
                {
                        model->pixels[n].samples[0] = image_data[i+j*stride];
                        for (u32b k=1; k < model->numberOfSamples; k++)
                                model->pixels[n].samples[k] = getRandPixel(image_data, width, height, stride, i, j);
                        n++;
                }
        }
        return 0;
}


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

// pix_data - значение пикселя
// pixel - модель соответствующего пикселя из vibeModel
s32b comparePixel(u8b pix_data, pixel *pixel, u32b matchingThreshold, u32b matchingNumber)
{        
        u32b matchingCounter=0;
	// Сравниваем со всеми сэмплами
        for (u32b i=0; i<pixel->numberOfSamples; i++)
        {                
                if (abs((s32b)pix_data-(s32b)pixel->samples[i]) < matchingThreshold)
                {
			// Если разница меньше порогового значения для количества сэмплов MatchingNumber,
			// то считаем, что в данном месте нет отличий от фона
                        matchingCounter++;
                        if (matchingCounter >= matchingNumber)
                                return 1;
                }
        }
        return 0;
}


Еще потребуется функция
updateModel(vibeModel *model, u8b pix_data, u32b width, u32b height, u32b stride, u32b x, u32b y);

которая, как и getRandPixel(...), длинная и простая, так что код не привожу. Делает она следующее: при вызове, с вероятностью 1/model->updateFactor, записывает значение pix_data в случайно выбранный сэмпл модели пикселя [x,y], и также в один из сэмплов находящегося рядом пикселя (тоже случайного).

Ну и, наконец, основная функция:

s32b libvibeModelUpdate_8u_C1R(vibeModel *model, const u8b *image_data, u8b *segmentation_map)
{
        s32b ad = model->stride - model->width;

        if (!model || !image_data || !segmentation_map) return 1;
        if (model->stride < model->width) return 1;

        u32b n=0;
        for (u32b j=0; j < model->height; j++)
        {
                for (u32b i=0; i < model->width; i++)
                {
			// сравниваем каждый пиксель с моделью
                        if (comparePixel(image_data[n], &(model->pixels[n]), model->matchingThreshold, model->matchingNumber))
                        {
				// совпадает с фоном - обновляем модель в данной точке
                                segmentation_map[n] = 0;
                                updateModel(model, image_data[n], model->width, model->height, model->stride,i,j);

                        }
                        else
                        {
				// отличие от фона
                                segmentation_map[n] = 0xFFU;
                        }
                        n++;
                }
                if (model->stride > model->width)
                        n+=ad;
        }
        return 0;
}

Для libvibeModelUpdate_8u_C3R все опять же аналогично.

Общие впечатления

Алгоритм оказался достаточно простым и одним из самых быстродействующих среди тех, которые удалось попробовать (среди имеющих хоть какую-то адаптивность к фону и его постепенным изменениям, конечно же). Заинтересовавшимся рекомендую скачать тестовую программу и самостоятельно его оценить на любой avi'шке.
Share post
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 10

    +11
    А поподробнее про структуру самого алгоритма, но без кода, а схемами/блок схемами/картинками?
    Код это полезно, но вчитываться лениво.
      –4
      Вы даже не представляете насколько лениво рисовать блок-схемы.
      В принципе они есть, например, в штатовском патенте, вместе с описанием алгоритма. Но добавление сюда его перевода увеличит статью еще в несколько раз.
        0
        Вы-бы тогда, раз лень описывать по нормальному, хотябы свой исходник полностью приложили, чтобы по нему можно было полностью разобраться в алгоритме.
          0
          Согласен, исходник в ближайшее время куда-нибудь выложу.
            0
            Вы только не забудьте сюда ссылку выложить)
        +5
        Согласен с комментарием. Если уж решили рассказать об алгоритме, то хотя бы принцип опишите, пожалуйста, а не просто: вот код, изучайте, вот патент, читайте.
        0
        Скачал демку с их сайта. Может я что-то не то делал с ней, но результат не превзошел таковых у модели обновления фона с помощью фильтра с бесконечным импульсным откликом. Шума все равно очень много он оставляет. Правда по видео сложно понять, применялись ли после вычитания операции сужения/расширения, может после них результат станет хорошим.
          0
          Не применялись, судя по всему. Результат работы их программы внешне полностью совпадал с моей реализацией. Размыкание, конечно, немало шумов убирает.
          Плюс к тому можно поиграться с порогами и подстроить алгоритм под конкретную задачу (с настройками по умолчанию у него слишком высокая чувствительность).
          По фильтру с бесконечным импульсным откликом — ViBe будет куда менее требователен к ресурсам, т.к. здесь для каждой точки делается только несколько вычитаний, сравнений и копирований.
            0
            Ну судя по статье я насчитал только 2 порога: количество сэмплов(надо полагать <= 8 ?) и вероятность updateFactor. Не чтобы алгоритм был очень чувствителен…
            Ну для ФБИО на каждой итерации нужно только 2 умножения «скаляр-матрица» и 1 сложение матриц и 1 вычитание матричное.
              0
              updateFactor влияет на то, как быстро обновляется модель фона.
              Пороги — это в первую очередь matchingThreshold и matchingNumber

        Only users with full accounts can post comments. Log in, please.