December 22, 2012 at 15:04Looking for differences in images
Hello, Habr!
Based on the article We are writing a bot for the game “Find the Difference” an idea has appeared to implement a search for third-party objects in a given image using computer vision algorithms.
Details - under the cut.
The problem of distinguishing an external object arises in many situations - for example, in video recording tasks, when, for example, you need to turn on the alarm when an unauthorized person appears at night in a protected area.
At the same time, the main difficulty of signal processing is that the registration conditions can vary - it depends on the time of day, the smoke of the room, the state of the recorder (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 shooting is performed.
Of course, one cannot do without a mathematical introduction!
Call the function
Let L be the linear space of all images, F be the class of all Borel functions taking 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. So, by the image form we mean the maximum invariant of image transformations to which it undergoes when changing the observation conditions, changing the shooting parameters. We will use the concept of form when processing images.
The main idea of the algorithm is to highlight a certain maximum image invariant, with which we will then compare the incoming images. The implementation of the algorithm is given in Python.
Conclusion: an algorithm for morphological analysis of images was implemented - the selection of a foreign object in the image under changed registration conditions, an implementation in Python was also obtained .
Tell me how to type formulas? I want to see the beauty of Latex in the articles!
Based on the article We are writing a bot for the game “Find the Difference” an idea has appeared to implement a search for third-party objects in a given image using computer vision algorithms.
Details - under the cut.
Description of the task.
The problem of distinguishing an external object arises in many situations - for example, in video recording tasks, when, for example, you need to turn on the alarm when an unauthorized person appears at night in a protected area.
At the same time, the main difficulty of signal processing is that the registration conditions can vary - it depends on the time of day, the smoke of the room, the state of the recorder (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 shooting is performed.
Information from morphological analysis
Of course, one cannot do without a mathematical introduction!
Call the function
f(x):X → Rf(x)will correspond to the brightness of the pixel (ranging from 0 to 255). Let L be the linear space of all images, F be the class of all Borel functions taking 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. So, by the image form we mean the maximum invariant of image transformations to which it undergoes when changing the observation conditions, changing the shooting parameters. We will use the concept of form when processing images.
Algorithm
The main idea of the algorithm is to highlight a certain maximum image invariant, with which we will then 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. We obtain a piecewise-constant approximation of the image. It is necessary to divide 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 that is 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 consider the average brightness value for each group. After that, it remains only to go through the image and assign each pixel the 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 areas of constant brightness A 1 , ..., A N . In parallel, we consider the power of each set of constant brightness (since the set is discrete - the 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 expression . - 3. Now let's work with the input image (on which we need to select a third-party element). To do this, we 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 a normalized brightness value for each piecewise constant shape element.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 onto our form, all that remains is to subtract the projection of the new image onto the form pixel by pixel from our form (the original image of a piecewise-constant image, without an external object).
Δ = g - P V g f
Image difference - this 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, we’ll draw an extraneous object in the original image. And further darken it so that it is not quite simple (we will simulate changes in the registration conditions).
The result of the script:
Hurray! We got a third-party object on a homogeneous background - it will not be difficult to select it and mark it in the original image. The problem of detecting a foreign object has been solved.
Conclusion
Conclusion: an algorithm for morphological analysis of images was implemented - the selection of a foreign object in the image under changed registration conditions, an implementation in Python was also obtained .
References
- 1. Bityukov Yu.I. Lectures on computer geometry; MAI, 2012
- 2. Pytiev Yu.P. Methods of morphological image analysis; Moscow, Fizmatlit 2010
Ps
Tell me how to type formulas? I want to see the beauty of Latex in the articles!