A method, performed in an apparatus, for updating a background model used for background subtraction of an image, comprising: receiving an image being part of a sequence of images, classifying each pixel in the image as being foreground or background by performing background subtraction using a background model which comprises a collection of background samples for each pixel in the image, wherein the collection of background samples associated with the pixel is indexed, updating the background model by, for each pixel in the image being classified as background: selecting (S06a) a background sample (242, 342) in the collection of background samples associated with the pixel which fulfils a similarity condition, the similarity condition being fulfilled with respect to a background sample (242, 342) if the background sample differs from the image data in the pixel by less than a similarity threshold, replacing (S06b) the background sample which fulfils the similarity condition with image data of the pixel, wherein the step of selecting (S06a) comprises iteratively searching the collection of background samples associated with the pixel by comparing the image data of the pixel to the background samples in the collection of background samples one by one until a background sample which fulfils the similarity condition is found, wherein the iterative search is initiated at an index in the collection of background samples which follows an index used to initiate an iterative search with respect to pixels in a preceding image in the image sequence. receiving an image being part of a sequence of images, classifying each pixel in the image as being foreground or background by performing background subtraction using a background model which comprises a collection of background samples for each pixel in the image, wherein the collection of background samples associated with the pixel is indexed, updating the background model by, for each pixel in the image being classified as background: selecting (S06a) a background sample (242, 342) in the collection of background samples associated with the pixel which fulfils a similarity condition, the similarity condition being fulfilled with respect to a background sample (242, 342) if the background sample differs from the image data in the pixel by less than a similarity threshold, replacing (S06b) the background sample which fulfils the similarity condition with image data of the pixel, wherein the step of selecting (S06a) comprises iteratively searching the collection of background samples associated with the pixel by comparing the image data of the pixel to the background samples in the collection of background samples one by one until a background sample which fulfils the similarity condition is found, wherein the iterative search is initiated at an index in the collection of background samples which follows an index used to initiate an iterative search with respect to pixels in a preceding image in the image sequence. selecting (S06a) a background sample (242, 342) in the collection of background samples associated with the pixel which fulfils a similarity condition, the similarity condition being fulfilled with respect to a background sample (242, 342) if the background sample differs from the image data in the pixel by less than a similarity threshold, replacing (S06b) the background sample which fulfils the similarity condition with image data of the pixel, wherein the step of selecting (S06a) comprises iteratively searching the collection of background samples associated with the pixel by comparing the image data of the pixel to the background samples in the collection of background samples one by one until a background sample which fulfils the similarity condition is found, wherein the iterative search is initiated at an index in the collection of background samples which follows an index used to initiate an iterative search with respect to pixels in a preceding image in the image sequence.