ViBe - background subtraction algorithm

Prehistory

A couple of years ago, in the process of executing one project related to the selection and maintenance of moving objects, many background subtraction algorithms were scanned, and in the end one of the most interesting was the one that will be discussed further. Its main drawback is a bunch of patents by which it is protected. But one of the undoubted advantages - the presence of a library under Linux, which is allowed to use in non-commercial projects. On the page with its description you can find this very library, as well as demo-programs for Windows and Android, links to patents (where you can find the basic descriptions of the algorithm), and other interesting information.

Use of the algorithm

An example of use is in the library header file. For grayscale 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); } 

')

His insides

Next will be the most interesting. The developers did not show the source code of the library, but if there is a description from the patent, the h-file and the library, a couple of nights of time and several liters of coffee are enough to parse it.
So, how it works.

The vibeModel_t structure:

 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; 

What is the reason here - it will be further clear from the algorithm.
Create a model, set default values ​​and initialize 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; } 

Further, in order not to write a lot of code here, suppose that we have some function

 u32b getRandPixel(const u8b *image_data, const u32b width, const u32b height, const u32b stride, const u32b x, const u32b y); 

which returns the value of a randomly selected pixel near the [xy] pixel. Then the model initialization looks like this:

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

The model is ready. The libvibeModelAllocInit_8u_C3R function is arranged in a similar way, but each sample contains not one byte, but three.
This is followed by the very subtraction of the background and the updating of its model. To begin, consider the function of comparing one pixel with a background model, it is arranged as follows:

 // 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; } 

Still need a function

 updateModel(vibeModel *model, u8b pix_data, u32b width, u32b height, u32b stride, u32b x, u32b y); 

which, like getRandPixel (...), is long and simple, so I don’t cite the code. It does the following: when called, with a probability of 1 / model-> updateFactor, writes the pix_data value to a randomly selected sample of the [x, y] pixel model, and also to one of the samples of the adjacent pixel (also random).

And finally, the main function:

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

For libvibeModelUpdate_8u_C3R, everything is again the same.

General impressions

The algorithm turned out to be quite simple and one of the fastest among those that we managed to try (among those who have at least some adaptability to the background and its gradual changes, of course). Interested recommend downloading a test program and independently evaluate it on any avi'shke.