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

Предыстория

Пару лет назад, в процессе выполнения одного проекта, связанного с выделением и сопровождением движущихся объектов, было просмотрено немало алгоритмов вычитания фона, и в итоге одним из самых интересных оказался тот, о котором дальше и пойдет речь. Основной его недостаток — куча патентов, которыми он защищен. Но одно из несомненных достоинств — наличие библиотеки под Linux, которую разрешено использовать в некоммерческих проектах. На странице ^[1] с его описанием можно найти эту самую библиотеку, а также 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 все опять же аналогично.

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

Алгоритм оказался достаточно простым и одним из самых быстродействующих среди тех, которые удалось попробовать (среди имеющих хоть какую-то адаптивность к фону и его постепенным изменениям, конечно же). Заинтересовавшимся рекомендую скачать ^[2] тестовую программу и самостоятельно его оценить на любой avi'шке.

Автор: DejmosSm

Источник ^[3]