Looking for differences in images

Hi, Habr!

Based on the article Writing a bot for the game “Find Difference”, an idea appeared to implement the search for third-party objects in a given image using computer vision algorithms.

Details - under the cut.
')

Description of the task.

The problem of identifying a third-party object arises in many situations - for example, in video recording tasks, when, for example, you need to turn on an alarm when an unauthorized person appears at night in a protected area.

At the same time, the main difficulty in signal processing is that the registration conditions can change - it depends on the time of day, the smoke in the room, the state of the recorder itself (for example, the lens is dusty). Therefore, it is necessary to use an algorithm that allows you to select a third-party object, regardless of the conditions in which the shooting is performed.

Information from morphological analysis

Without a mathematical introduction, of course, can not do!

Call the function

f(x):X → R 

image. In our problem, the f(x) value will correspond to the pixel brightness (ranging from 0 to 255).

Let L be the linear space of all images, F the class of all Borel functions that take numerical values, F _f be a subclass of F : F _f = {F ∈ F : F⊗f () ∈ L}.

And finally, we introduce the important concept of image shape : V _f = {F⊗f: F ∈ F _f } ⊂ L. Thus, the image shape is the maximum invariant of image transformations that it undergoes when changing the conditions of observation, changing shooting parameters. We will use the concept of form in image processing.

Algorithm

The main idea of ​​the algorithm is to single out a certain maximum image invariant, with which then we will compare the incoming images. The implementation of the algorithm is given in Python.

 from PIL import Image#    

• 1. Convert the input (color) image to gray - assign each pixel instead of color a brightness value in the range [0,255]
  

   im1 = Image.open('./img/test1.jpg')#  p1 = im1.convert('L')#      

  
  
• 2. Get the piecewise constant approximation of the image. It is necessary to split the input (smooth) image into a number of areas of constant brightness.
  
  g = ∑ ^N _{i = 1} A _i c _i (x),
  
  where c _i (x) is the brightness value, constant for the region A _i .
  
  

    for i in xrange(p1.size[1]):#   for j in xrange(p1.size[0]):#    for l in xrange(len(split_map[1])): if pix[j,i] in split_map[1][l]: pix[j,i]=split_map[0][l]#    , measure[l]+=1#   - break 

  
  We pre-divide the interval of brightness values ​​into equal intervals [0, ..., a_1], ..., [a_m, ..., 255]. Then we calculate the average brightness value for each group. After that, it remains only to walk through the image and assign each pixel an average brightness value for the group into which it falls. As a result, we obtain a partition of the input image into a number of regions of constant brightness A ₁ , ..., A _N. In parallel, we consider the power of each set of constant brightness (because the set is discrete — power is equal to the number of pixels). How the algorithm works on an example:
  

  Input Image

  
  
  

  Piecewise constant approximation

  
  
  The resulting piecewise constant approximation is the form of the image .
  
• 3. Now let's work with the input image (where we need to select a third-party element). To do this, find the projection of the input image on our form:
  P _{V g} f = ∑ ^N _{i = 1} = (∑ _{x sk ∈ A i} f (x _sk )) / (| A | _i ) ⋅ c _i (x).
  
  In other words, we calculate for the input image the normalized brightness value on each piecewise constant element of the form.
  

   def projector(img,split_form): p1 = img.convert('L');pix = p1.load();summ = [0]*len(split_form[2][1]); for l in xrange(len(split_form[2][1])):#     for i in xrange(p1.size[1]): for j in xrange(p1.size[0]): if split_form[3][j,i]==l: summ[l]+=pix[j,i] summ[l] = summ[l] / split_form[1][l]# ""   #         ""  for i in xrange(p1.size[1]): for j in xrange(p1.size[0]): if split_form[3][j,i]==l: pix[j,i] = summ[l] return p1 

  
  
• 4. That's it! After we have calculated the projection on our form, all that remains is to subtract from our form (the original image of the piecewise-constant image, without an external object) the projection of the new image onto the form pixel-by-pixel.
  
  Δ = g - P _{V g} f
  
  The difference of images will be the desired object.
  
  

   def differ(i1,i2): map1 = i1.load(); map2 = i2.load() for i in xrange(i1.size[1]):#   for j in xrange(i1.size[0]):#    map1[j,i] = map1[j,i] - map2[j,i] return i1 

  
  
  As an example, draw a foreign object on the original image. And further darken it so that it is not quite simple (we will model changes in registration conditions).
  
  
  
  The result of the script:
  
  
  
  Hooray! We got a third-party object on a uniform background - it is not difficult to select it and mark it on the original image. The task of detecting a foreign object is solved.
  

Conclusion

Conclusion: the algorithm of morphological image analysis was implemented - the selection of a foreign object in the image under the changed registration conditions, as well as the implementation in Python .

References

• 1. Bityukov Yu.I. Lectures on computer geometry; MAI, 2012
• 2. Pytyev Yu.P. Methods of morphological image analysis; Moscow, Fizmatlit 2010

Ps

Tell me how to type the formula? I want to see the beauty of Latex in the articles!