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

Предыстория

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

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

Пример использования есть в заголовочном файле библиотеки. Для изображения в градациях серого:

#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’шке.