Morphological image processing. Lectures from Yandex

Methods of such mathematical morphology in the context of image processing were proposed in 1964 by the French Jean-Pierre Serre and Georges Matheron. Jean Serre himself wrote his thesis on this topic. Soon after defending his dissertation in Paris, a whole center of mathematical morphology was opened, and much more time was spent on the study of these methods, a whole section of this kind.

The basis of these methods is set theory. It is assumed that any object in the image can also be represented as a set, or a set in two-dimensional space, or a set in three-dimensional space.

Today we will discuss methods applied only to two-dimensional space, the so-called binary morphology. But this all rather intuitively expands to the three-dimensional case. How does the image appear in the binary case?

Again, binary - this means we only have black, only white pixels. And then we fix the background color. Suppose we have a white background, then the object is given by a set of coordinates of points belonging to this object, and, respectively, belonging to the set. That is, the set of pairs x, y that belong to an object forms a set.

Even as in school (I do not know who started to study the theory of sets where) draw a set to explain what is the union of intersections and so on. Here the most intuitive concept is just the very same pictures. In the three-dimensional case, we add another coordinate, this is the brightness value. And the rest is all the same. The basic theory of operation of sets, I hope everyone knows and remembers.

If we have two sets a and b, we can combine them. This will be a set of points that occur in either a or b. We can cross them by intersection - there will be a lot of points that go both there and here. We can build an addition to the set, it will be a set of points that does not belong to the set a. And we can subtract one set from another, respectively, it will be a set of points belonging to the first and not belonging to the second.

In mathematical morphology, there are two more operations that may not be so basic, but also so clear. This is the central reflection of the set; here, by set, we mean the set of pairs x, y. If we have a set of these pairs x, y, then the central reflection will be the set reflected relative to the origin or some other, as it were, given origin.
Parallel transfer, respectively, shifted set by some given number z. If we had a origin here, the initial set a was here, then we moved it somewhere. But z is also a vector, respectively, that is, we shift in x and y.

Here the central reflection is displayed, respectively, if it was originally somewhere here, it can be reflected to the top.

These operations are used very widely in determining the basic operations of the mathematical morphology. In general, in mathematical morphology, all operations are defined by two sets. One set of itself is the image itself, with which we want to do something, and the second set is the so-called structural element, which is also sometimes called a structure-forming or primitive (structure elements or simply primitive).

This is usually a lot, that is, it looks the same as the picture. It is assumed in binary morphology that he also has only white and black points. It is usually significantly smaller than the image, that is, most often the size there is 3, 5, 15 pixels - no more.
This is some kind of mask, which we discussed when we talked about spatial lines of image filtering.

Accordingly, here are examples. Probably the two most common structural elements in the form of such a sheet and cube. When morphological processing takes place, then again, as in the case of linear spatial filtering, here we have this structural element that slides over the picture, and we look at the values, at the images that were under this structural element. Well, depending on whether certain conditions are met, a zero or one is put in the resulting image.

That is, we have our source and structural elements as input, initially the entire picture is flooded with black at the output, and we decide whether to set any pixel to white or not - depending on the conditions, on the values structural element and that piece of image that is under the structural element.

Two basic operations of mathematical morphology, on which absolutely everything is built, are the so-called delation, erosion. In Russian, they are called delation and dilatation, and expansion, and buildup, who in that much. In fact, this is, in fact, an extension of some kind, such a swelling of the object, which was originally on the image.

Erosion - narrowing, this is such a slimming object, which was on the image. And now we will see how it all happens.

Two more equally important operations that are used are opening and closing (opening / closing), which are constructed as a superposition of the first two basic ones. And actually, what they do, we will also talk about it.

These four operations are used most actively. We will continue to consider other derivative operations, which, in principle, are probably also used, but in a fairly limited set of tasks.

Let's move on to the consideration of these very tasks. What is the extension. Imagine that you have the original object, this is this little blue box inside, and the structural element here is represented in the form of this disk. For the structural element, the so-called initial element must be given, and most often the structural element is symmetric and the initial element coincides with its center.

The main application of the extension is when we have some liquid objects and we need to build bridges between the pieces and, in general, the same connected component. It is often used in text recognition, that is, if we have a font of some kind, when there are obvious gaps in the letters, so that these letters are recognizable. That is, so that the contour, at least, was appropriate, then expansion is applied in particular. What is probably the main minus of all morphological methods? In what is needed every time it is very clear to choose a mask in size and in shape, because in particular this is very much dependent on the font size, and if we have a gap of, say, three pixels, it will connect this business, if more, it will not bind. Either it is necessary to apply several successive expansion operations, and see what happens, that is, such a technique.

The operation "erosion" is in some sense inverse to expansion. Not in the mathematical sense, inverse. Erosion or erosion is also called the following result. Here we have again a blue square, this is our original set. The disk is a structural element and the result of erosion is such a set that if we place, well, that is, so we move the structural element along our original set and take only those points that are covered by both the image and the structural element. That is, if we suddenly have a structural element begins to creep out of the picture, then all points of the structural element should be placed in the original object. Here the center does not play such a big role.

Here, respectively, examples of erosion. The same object that we had with the extension, the structural element is exactly the same, but here the original object is marked with a dotted line, and the result of erosion is painted in gray. Here, too, the original object and the result of erosion will be the line.
Another example of erosion is erosion followed by expansion. Here at first there was a picture of large squares and small dots. First, erosion was applied with a structural element whose size exceeds the size of small squares, but smaller than large ones. And we see that as a result we have only large ones left in the form of a very thinner one. And then you can use the extension to increase them.

In fact, such a consistent application of erosion and expansion forms the two most frequently used derivative operations. One of them is opening, opening. The second is closing. They differ only in the order of operation. Breaking - when we first produce erosion, then - expansion. Closing is the opposite.
Actually, the difference in effects is as follows: in the first case, when we apply erosion, we smooth out the contours of the object from the inside, that is, we round the corners of the object. And if we apply a closure, then the corners of the object are also smoothed here, but as if outside. That is, it turns out that in our case the opening reaction can be thought of as if you are rolling the contours of an object with a ball, they become smooth. A closure is when, on the contrary, we expand accordingly, and then we do erosion.

Their main properties are as follows. If we take the original element a, the structural element b, then the result of the opening will always lie inside the original object. And here is the opposite. The source object will contain a closure. If we have two sets c and d, c is a subset of d, then when choosing the same structural element, the result of the opening, the result of the closure will also be, that is, the nesting relation will be preserved. Properties 2 and 3 are the same. Well and repeated application of the same operation (opening, opening) will be equivalent to one opening, the same with closing.

Some more examples. Here, the initial set is a, as the set b and the structural element, here again the disk. The dotted line indicates the contours of the original object. Delation will look like this. If we have the size of a structural element larger than our jumper here between these objects, they will be divided into two components. Further, if we then carry out an expansion operation on top of this result, the result will look like this. The original will sprout a little, but, nevertheless, the jumper will not recover here. Here, to the initial set, we first apply the expansion operation, then the erosion operation. Here, the jumper is preserved, the corners are also smoothed and some more such bulges are filled.

By combining all these operations, you can perform various tasks. One of such classic is the so-called Hit-or-Miss Transform, and in Russian it is called the transformation “Success and Luck”. When you have an image, you know for sure that there must be an object of a certain shape in this image, you know its size and want to find its coordinates. Used composite structural element. One to highlight the object, the second - to highlight the background. That is, we are trying to describe the object we are looking for using the first structural object, and using the second, what the background around it will look like. Here is an example. It is indicated by an asterisk in a circle.

I will explain in the figure. Suppose we have an initial set a, which consists of combining three subsets x, y, z that are not related to each other, and we want to find the location where object x is located, that is, we know its size, we know its shape . Then we choose x as the first structural element, and as the second structural element we choose the difference between a small neighborhood around x and x, that is, what the background around this element will look like.

Next comes the following. We calculate the addition to the original set a, which is shown here here. Next, we produce erosion by a using the first mask x. It is clear that for us x itself is the object that was smaller than it, will be removed completely, only a piece of the object of that piece of y that was larger than the original mask will remain. Then we do the same, only apply the erosion operation to the complement of the original set, using the neighborhood mask, that is, a small neighborhood minus x. We will succeed here, here such a squiggle and a dot.

Now, if we further construct the intersection of these two results, we will get the center of our element x, which we were looking for. If there are several such objects, then you need correspondingly several masks.

Another morphological application of operations is to fill the area. We have a contour, and you want to fill everything inside. All this can also be done with the help of morphological operations. Here they will need several at once. A necessary condition for this simple algorithm is knowledge of at least one point inside the element that you want to fill.

Actually, then the operation will occur as follows. We take a certain structural element, for example, this one, we have our initial set, its complement, we initially build, respectively, x0 - this is some kind of point inside the element.

That is, in fact, this pixel. This is the point inside the object that we want to fill. We build an extension of this point with our structural element.

We build and intersect with the addition of k every time, at every step, and until we do this, until our xk ceases to differ from xk-1.
It turns out flooded object. In this case, the contour should be no thinner than half of the structural element? In addition, it is also possible to solve an important problem about the selection of connected components (selection of components of connectivity), also with the help of the sequential application of morphological operations. If anyone remembers, in the first lecture I told about a two-pass algorithm for the selection of connected components. In my opinion, he is more successful than the one that can be done with the help of morphology. But nevertheless, to be aware of.

In fact, when discussing morphological operations, there is a certain set of tasks that, not exactly accepted, but it is known that can be solved with the help of morphological pieces.
If we want to select a connected component, the minus is again that we need to know again some point that belongs to the connected component. That is, for example, we have such a component, and there is a point n initially, which, we know for sure, belongs to this component. Then we take a certain structural element. Again, x0 is the point itself, as in the case of filling all the same, only we intersect not with the addition to the original set, but with the original set itself. The rest of the algorithm is exactly the same.
We sequentially build the extension of the initial point and intersect the result with the initial set. Naive fill, yes.

The next task, which can be solved using morphological operations, is the construction of a convex hull of an object. For example, we have an object of this type, and we want to construct a convex hull of it. A certain polygon of the minimum area describing our object. Then here we will need as many as 4 structural elements that look that way. These crosses mean that it does not matter to us what value will be here, it is important to us that here there is one, here here is a zero. Here we are not particularly interested. But the center is in our center. Here we have, for example, it doesn’t matter what we have here, surely a single one.

The bottom line is that they must be different. You can try, let's talk about what is happening here, then we will think about why the square will not work. A square without a center tells us that we must have a single here. The result, respectively, of this Hit-or-Miss with masks of this kind or with edinichkami required, will be different. If we run, requiring only one of the faces, or if we demand the presence of all.

I think if you choose a different set of these very structural elements, if it is possible to add another diagonal there, then we can build a smaller figure. Accordingly, what happens here: for each of these structural elements, we perform this Hit-or-Miss and combine it with the original figure.

The next thing you can do is build the so-called object thinning. That is something like a skeleton, but not a skeleton. I do not want you to remember the operations that can be done. I want you from this lecture to remember what the 4 basic operations look like, this is respectively expansion, erosion, opening, closing, and understanding how they work. And plus to this, we also knew what can be done in principle with the help of morphological operations - what can be done to fill, you can build a shell, you can select connected components, and you can do what I am now enumerating.

In principle, if you think a little, you can understand how using this constructor you can get this. That is, my goal is simply to say, convey to you what can be done through these operations.

Accordingly, here for different operations the number of structural elements that you need varies. That is, here they need 8 to build the very refinement of this type, they are constructed accordingly as follows. We need to take the source element, build Hit-or-Miss for each of these bs and subtract what was.

, b1, b2, b3, b4, b5, b6, b7, b8. , . , . .
, , .

, . - , , , , , , . , . — , . , , .

, , . , . : , , , . . , , .

, , , . .

. k , b — , , b. b. — , . , , , , , . . , , 8 , b1, b2, b3, b4, b1, b2 — , 90 , b3 — 180, b4 — 270. b5, b6, b7, b8 , . h — .

, , , , . , , , . , .

, , — , , , , closing, opening. , . , - . , , .