A method for segmenting complex structured raster halftone images based on composite morphological operators. Edge detection algorithms
UDC: 004.932.72CH GRNTI: 28.23.15 DOI: 10.15643/jscientia.2016.6.195
OPTIMAL ALGORITHMS FOR EXTRACTING IMAGE CONTOURS IN SYSTEM-TECHNICAL VISION
E. E. Pelevin*, S. V. Balyasny
Tula State University Russia, 300012, Tula, Lenin Ave., 92 * email: [email protected]
The article discusses the issue of recognizing image contours in robotics. The objects of study are four contour identification algorithms: Kirsch, Robinson, Canny and Marr-Hildreth. Using these algorithms, often used in modern robotics, a study was conducted on the efficiency of identifying image contours in technical vision systems with various types of objects receiving input. The results of the studies showed that the Canny method is the most effective in identifying contours in an image. During the work, it was revealed that this method allows one to achieve high sharpness and detail. The second most effective method for identifying linear contours was the Marr-Hildreth method. Based on the results of the study, we can conclude that there are the most universal algorithms, but each of them is suitable for certain classes of images in its own way.
Keywords: Kirsch, Robinson, Canny, Marr-Hildreth, operator, recognition, contour, robotics, technical vision system (VS).
OPTIMAL ALGORITHM OF EDGE DETECTION WITHIN THE SYSTEM OF COMPUTER VISION
E. E. Pelevin*, S. V. Balyasny
Tula State University
Prospect Lenina 92, 300012, Tula, Russia
* email: [email protected]
The article touches upon the edge detection of digital images in robotics. Four algorithms of edge identification singled out by Kirsh, Robinson, Canny and Marr-Hildreth serve as the subject matter of the research. With the help of these algorithms widely used in the modern robotics, the research of efficiency of edge detection of images within the systems of computer vision which accept various input types of objects has been done. The results of the research done have shown that the method of Canny is the most effective in edge detection of images. During the work process, it has been found out that this method allows achieving both high definition and refinement. The method of Marr-Hildreth has become the second efficient method in edging of line contours. Based on the research results, the following conclusion can be drawn: there are more universal algorithms, but each of them fits particular classes of images differently.
Keywords: Kirsh, Robinson, Canny, Marr-Hildreth, operator, edge detection, contour, robotics, computer vision system.
Undoubtedly, in the age of computer technology, robotics occupies an increasingly important place in modern science. This is due to the introduction of new equipment in factories, gas stations, airports and other areas of human activity. Part of these innovative systems is a program with one or another algorithm for recognizing the contours of images, for example, the implementation of highlighting the contours of various parts or mechanisms. All subsequent operation of the robotic system as a whole depends on the effectiveness of this algorithm.
Currently, there are a large number of different contour selection algorithms, but only a few of them have become widespread, namely due to their versatility. In this work, the most popular algorithms will be considered: the Kirsch operator, the Robinson operator, the Canny edge detector and the Marr-Hildreth method. To test these methods, a test image (Fig. 1) will be used.
The first of the methods considered is the Kirsch operator. This method was developed by Roussel A. Kirsch in 1971. This algorithm is based on the use of a detection matrix (mask), which is sequentially rotated along eight main sides
Rice. 1. Original image for edge detection.
lights: north, northwest, west, southwest, south, southeast, east and northeast. After research, Roussel A. Kirsch derived the following masks for each cardinal direction:
5 5 5 -3 0 -3 -3 -3 -3J
COMPUTER SCIENCE | Juvenis scientia 2016 No. 6
In this case, the boundary value is defined as the maximum value that can be found using the mask. A certain mask helps the direction to produce the maximum value. From this we can conclude that the ko mask allows you to select vertical boundaries, and the k5 mask allows you to select diagonal ones. It is also noticeable from the masks that the latter are similar to the first four, but are their mirror image along the central axis of the matrix used.
When processing the test image, you can get the following result (Fig. 2).
Rice. 2. Identification of contours by the Kirsch operator.
Later in 1977, the Robinson operator was developed, which, in fact, was an analogue of the Kirsch method, but thanks to the use of coefficients o, 1 and 2, it became easier to implement. The matrices that this operator uses are symmetrical about their central axes, each of which is filled with zeros. Thanks to this, you can use only the first four matrices, and obtain the remaining results by inverting the first ones. The Robinson operator would look like this:
Rice. 3. The result of the Robinson operator.
Despite the simplicity of the previous operator, the Canny edge detector eventually gained the most popularity. The method was first described in 1983 by scientist John Canny in his master's thesis. This method is superior in efficiency to many modern ones, even if it was developed more than thirty years ago. Its distinctive feature is the elimination of noise on the contours of the image, which undoubtedly affects the final result. This algorithm consists of performing the following steps:
Blurring the original image c) using the Gaussian method ^(r, c). ^(r, c)=f(r,c)*G(r,c,6);
Perform a gradient search. The boundaries are marked where the gradient takes on its maximum value;
Suppression of non-maxima. Only local maxima are marked as boundaries;
The resulting boundaries are determined by suppressing all edges not associated with the defined boundaries.
The result of the algorithm is the contours in the image. Due to its features, this method is little susceptible to noise (Fig. 4).
It follows from the matrices that after each of them is sequentially applied to the pixel and its surroundings, the maximum value it receives will be considered the gradient value. The gradient angle can then be approximated as the angle of the line filled with zeros in the mask that gives the maximum response.
As in the previous case, you can process the original images (Fig. 3).
Rice. 4. The result of the Canny method.
The latest method for edge detection in digital images is called Mugg-Bigge, which was developed in 1980. It implies the detection of curves in all areas where there is a sharp change in the brightness of groups of pixels. This method is simple and works by convolving the original image
expressions with the LoG function or as a fast approximation with DoG. When the method works, the zeros in the reverse result indicate the contours of the image. For the method to work, you must adhere to the following steps of the algorithm:
Blur the image using the Gaussian method;
Applying the Laplace operator to a blurred image (often the first two steps are combined into one);
A cycle of calculations is carried out and the resulting result is looked at for a change in sign. If the sign changes from negative to positive and the value changes by more than some specified threshold, then it is necessary to define this point as a boundary;
To obtain better results, the step using the Laplace operator can be performed through hysteresis, that is, as implemented in the Canny algorithm.
The result of this algorithm on the test image will be as follows (Fig. 5).
Based on the research conducted, we can conclude that for recognizing mechanisms and other objects consisting of curved contours, the Canny method can be most effectively used in robotics, which allows achieving the greatest sharpness of boundaries and high detail. For identifying linear contours of objects, for example, in cases where vision systems are used on conveyor lines, the Marr-Hildreth method is best suited, which identifies even small linear contours in images. Thus, all the described selection algorithms can be used in robotics, but each of them is most effective for a certain class of tasks, and is also aimed at obtaining a result of a certain quality.
LITERATURE
1. Ammeral L. Principles of programming in machine graphics / L. Ammeral. M.: Sol System, 1992. 665 p.
2. Butakov E.A. Image processing on a computer: monograph. / E.A. Butakov, V.I. Ostrovsky, I.L. Fadeev. M.: Radio and communication, 1987. 205 p.
3. Pratt W. Digital image processing / W. Pratt. M.: Mir, 1982. T. 2. 716 p.
4. Tu J. Principles of pattern recognition / J. Tu, R. Gonzalez. M.: Mir, 1978. 764 p.
5. Fain V.S. Image identification / V.S. Fine. M.: Nauka, 2003. 322 p.
6. Yanshin V. Image processing in C language for IBM PC: Algorithms and programs / V. Yanshin, G. Kalinin. M.: Mir, 1994. 358 p.
For discrete images, the calculation of partial derivatives comes down to calculating the difference in brightness of neighboring pixels in various ways, i.e., in fact, to spatial filtering. The elements can be either individual points or their aggregates, united according to the principle of proximity of any properties. In the latter case, segmentation of a complex image turns into a hierarchical process. If brightness is selected as a characteristic of homogeneity, then for a discrete image, connected pixels that have the same or similar brightness are grouped into a homogeneous area. In the latter case, the result of segmentation will be determined by the choice of the proximity threshold level. For binary images, the condition of proximity in brightness is trivial and the decision about whether a pixel belongs to a segment is made based on connectivity analysis. Kirsch compass masks are yet another type of derivative mask which are used for edge detection. This operator is also known as direction mask. In this operator we take one mask and rotate it in all the eight compass directions to get edges of the eight directions. We are going to use OpenCV function filter2D to apply Kirsch operator to images. It can be found under Imgproc package. Its syntax is given below − Filter2D(src, dst, depth, kernel, anchor, delta, BORDER_DEFAULT); The function arguments are described below − It is source image. It is destination image. It is the depth of dst. A negative value (such as -1) indicates that the depth is the same as the source. It is the kernel to be scanned through the image. It is the position of the anchor relative to its kernel. The location Point (-1, -1) indicates the center by default. It is a value to be added to each pixel during the convolution. By default it is 0. BORDER_DEFAULT We let this value by default. Apart from the filter2D() method, there are other methods provided by the Imgproc class. They are described briefly − cvtColor(Mat src, Mat dst, int code, int dstCn) It converts an image from one color space to another. dilate(Mat src, Mat dst, Mat kernel) It dilates an image by using a specific structuring element. equalizeHist(Mat src, Mat dst) It equalizes the histogram of a grayscale image. filter2D(Mat src, Mat dst, int depth, Mat kernel, Point anchor, double delta) It convolves an image with the kernel. GaussianBlur(Mat src, Mat dst, Size ksize, double sigmaX) It blurs an image using a Gaussian filter. integral(Mat src, Mat sum) It calculates the integral of an image. The following example demonstrates the use of Imgproc class to apply Kirsch operator to an image of Grayscale. Import org.opencv.core.Core; import org.opencv.core.CvType; import org.opencv.core.Mat; import org.opencv.highgui.Highgui; import org.opencv.imgproc.Imgproc; public class convolution ( public static void main(String args) ( try ( int kernelSize = 9; System.loadLibrary(Core.NATIVE_LIBRARY_NAME); Mat source = Highgui.imread("grayscale.jpg", Highgui.CV_LOAD_IMAGE_GRAYSCALE); Mat destination = new Mat(source.rows(),source.cols(),source.type()); Mat kernel = new Mat(kernelSize,kernelSize, CvType.CV_32F) ( ( put(0,0,-3); put( 0,1,-3); put(1,2,-3); 0,5); put(2,1,5); put(2,2,5) ); Imgproc.filter2D(source, destination, -1, kernel); destination); ) catch (Exception e) ( System.out.println("Error: " + e.getMessage()); ) ) ) One of the main goals of computer vision in image processing is to interpret the content in the image. To do this, it is necessary to qualitatively separate the background from the objects. Segmentation divides an image into its component parts or objects. It separates the object from the background so that images can be easily processed and its content can be identified. In this case, identifying contours in an image is a fundamental tool for high-quality image segmentation. This article attempts to study the performance of commonly used edge extraction algorithms for further image segmentation, as well as their comparison using the MATLAB software tool. Image segmentation is a huge step for image analysis. It divides an image into its component parts or objects. The level of detail of the divided areas depends on the problem being solved. For example, when the objects of interest no longer maintain integrity and are broken into smaller, component parts, the segmentation process should be stopped. Image segmentation algorithms are most often based on the discontinuity and similarity of values in the image. The luminance discontinuity approach is based on sudden changes in intensity values, while similarity is based on dividing the image into areas that are similar according to a number of predefined criteria. Thus, the choice of image segmentation algorithm directly depends on the problem that needs to be solved. Edge detection is a part of image segmentation. Consequently, the effectiveness of solving many image processing and computer vision problems depends on the quality of the extracted boundaries. Isolating them in an image can be classified as segmentation algorithms that are based on brightness discontinuities. The process of detecting precise brightness discontinuities in an image is called the edge extraction process. Gaps are sudden changes in a group of pixels that are the boundaries of objects. The classic edge detection algorithm involves image convolution using an operator that is sensitive to large differences in brightness in the image, and returns zero when passing through homogeneous areas. A huge number of edge detection algorithms are now available, but none of them is universal. Each of the existing algorithms solves its own class of problems (i.e., qualitatively identifies boundaries of a certain type). To determine the appropriate edge detection algorithm, it is necessary to take into account parameters such as the orientation and structure of the edge, as well as the presence and type of noise in the image. The geometry of the operator establishes the characteristic direction in which it is most sensitive to boundaries. Existing operators are designed to find vertical, horizontal or diagonal boundaries. Isolating the boundaries of objects is a difficult task in the case of a highly noisy image, since the operator is sensitive to changes in brightness, and, therefore, noise will also be considered as some object in the image. There are algorithms that can significantly eliminate noise, but in turn, they significantly damage the edges of the image, distorting them. And since most processed images contain noise, noise reduction algorithms are very popular, but this affects the quality of the selected contours. Also, when detecting the contours of objects, there are problems such as finding false contours, positioning of contours, missing true contours, interference in the form of noise, high computation time, etc. Therefore, the goal is to examine and compare many processed images and analyze quality of algorithms in various conditions. This article makes an attempt to review the most popular contour selection algorithms for segmentation, as well as their implementation in the MATLAB software environment. The second section introduces the fundamental definitions that are used in the literature. The third one provides theoretical and mathematical explanations of various computer approaches to edge extraction. Section four provides a comparative analysis of different algorithms, accompanied by images. The fifth section contains an overview of the results obtained and a conclusion. Image segmentation is the process of dividing a digital image into many regions or sets of pixels. In fact, it is the division into different objects that have the same texture or color. The result of segmentation is a set of regions covering the entire image together and a set of contours extracted from the image. All pixels from the same region are similar in some characteristic, such as color, texture, or intensity. Adjacent areas differ from each other in these same characteristics. Various approaches to finding boundaries between regions are based on inhomogeneities in brightness intensity levels. Thus, the choice of image segmentation method depends on the problem that needs to be solved. Area-based methods are based on continuity. These algorithms divide the entire image into subregions depending on certain rules, for example, all pixels in a given group must have a certain gray value. These algorithms rely on common patterns of intensity values in clusters of neighboring pixels. Threshold segmentation is the simplest type of segmentation. Based on this, areas can be classified according to a basic range of values that depend on the intensity of the image pixels. Thresholding converts the input image to binary. Segmentation methods based on region detection directly find abrupt changes in intensity values. Such methods are called boundary methods. Edge detection is a fundamental problem in image analysis. Edge extraction techniques are commonly used to find irregularities in a grayscale image. Detecting discontinuities in a grayscale image is the most important approach for edge detection. The boundaries of objects in the image greatly reduce the amount of data that needs to be processed, and at the same time preserves important information about the objects in the image, their shape, size, and quantity. The main feature of the edge detection technique is the ability to extract an accurate line with good orientation. The literature describes many algorithms that allow you to detect the boundaries of objects, but nowhere is there a description of how to evaluate the processing results. The results are assessed purely individually and depend on the area of their application. Edge detection is a fundamental tool for image segmentation. Such algorithms convert the input image into an image with the outlines of objects, mainly in gray tones. In image processing, especially in computer vision systems, important changes in the brightness level in the image, physical and geometric parameters of the object in the scene are considered using contour extraction. This is a fundamental process that outlines objects, thereby gaining some knowledge about the image. Edge detection is the most popular approach for detecting significant discontinuities. A boundary is a local change in brightness in an image. They typically run along the edge between two areas. Borders can be used to gain basic knowledge about an image. Their acquisition functions are used by advanced computer vision algorithms and in areas such as medical image processing, biometrics and the like. Edge detection is an active area of research as it facilitates high-level image analysis. There are three types of breaks in halftone images: point, line, and border. Spatial masks can be used to detect all three types of inhomogeneities. A large number of algorithms for identifying contours and boundaries are presented and described in the technical literature. This paper discusses the most popular methods. These include: the Roberts, Sobel, Prewitt, Kirsch, Robinson operator, the Canny algorithm and the LoG algorithm. The Roberts boundary selection operator was introduced by Lawrence Roberts in 1964. It performs simple and fast calculations of the two-dimensional spatial dimension in an image. This technique emphasizes regions of high spatial frequency that often correspond to edges. A halftone image is supplied to the operator input. The pixel value of the output image at each point implies a certain value of the spatial gradient of the input image at the same point. The Sobel operator was introduced by Sobel in 1970. This edge detection method uses derivative approximation. This allows edge detection where the gradient is highest. This method detects the number of gradients in an image, thereby highlighting regions of high spatial frequency that correspond to boundaries. Overall, this resulted in finding the estimated absolute magnitude of the gradient at each point in the input image. This operator consists of two matrices of size 3×3. The second matrix differs from the first only in that it is rotated 90 degrees. This is very similar to the Roberts operator. Detecting boundaries with this method is computationally much simpler than the Sobel method, but it leads to greater noise in the resulting image. Boundary detection by this operator was proposed by Prewitt in 1970. The correct direction in this algorithm was to estimate the magnitude and orientation of the boundary. Even though edge detection is a very labor-intensive task, this approach gives very good results. This algorithm is based on the use of 3 by 3 masks, which take into account 8 possible directions, but straight directions give the best results. All convolution masks are calculated. Edge detection by this method was introduced by Kirsch in 1971. The algorithm is based on using just one mask, which is rotated in eight main directions: north, northwest, west, southwest, south, southeast, east and northeast. The masks look like this: The boundary value is defined as the maximum value found using the mask. The direction defined by the mask gives the maximum value. For example, mask k 0 corresponds to a vertical boundary, and mask k 5 corresponds to a diagonal boundary. You can also notice that the last four masks are actually the same as the first ones, they are a mirror image about the central axis of the matrix. Robinson's method, introduced in 1977, is similar to the Kirsch method, but is simpler to implement due to the use of coefficients 0, 1 and 2. The masks of this operator are symmetrical about a central axis filled with zeros. It is enough to get the result from processing the first four masks; the rest can be obtained by inverting the first ones. The maximum value obtained after applying all four masks to the pixel and its surroundings is considered the magnitude of the gradient, and the angle of the gradient can be approximated as the angle of the lines of zeros in the mask that give the maximum response. The Marr-Hildreth (1980) method is an edge detection technique in digital images that detects continuous curves wherever rapid and abrupt changes in the brightness of a group of pixels are noticeable. This is a fairly simple method, it works by convolving an image with a LoG function or as a fast approximation with DoG. Zeros in the processed result correspond to contours. The edge detector algorithm consists of the following steps: The Laplacian-Gaussian contour extraction algorithm was proposed in 1982. This algorithm is the second derivative, defined as: It is carried out in two steps. In the first step, it smoothes the image and then calculates the Laplace function, which leads to the formation of double contours. Defining contours comes down to finding zeros at the intersection of double boundaries. The computer implementation of the Laplace function is usually carried out through the following mask: The Laplacian usually uses the pixel being on the dark or light side of the border. Canny edge detector is one of the most popular edge detection algorithms. It was first proposed by John Canny in his master's thesis in 1983, and is still superior to many algorithms developed later. An important step in this algorithm is the elimination of noise on the contours, which can significantly affect the result, while maintaining the boundaries as much as possible. This requires careful selection of the threshold value when processing with this method. Algorithm: Unlike the Roberts and Sobel operators, the Canny algorithm is not very sensitive to image noise. This section presents the results of the previously described algorithms for detecting the boundaries of objects in an image. All described algorithms were implemented in the MATLAB R2009a software environment and tested on a university photograph. The goal of the experiment is to obtain a processed image with perfectly defined contours. The original image and the results of its processing are presented in Figure 1. Figure 1 - Original image and the result of various contour extraction algorithms When analyzing the results obtained, the following patterns were revealed: the Roberts, Sobel and Prewitt operators give very different results. Marr-Hildreth, LoG and Canny found the contours of the object in almost the same way, Kirsch and Robinson gave the same result. But observing the results obtained, we can conclude that the Canny algorithm copes an order of magnitude better than others. Image processing is a rapidly growing area in the discipline of computer vision. Its growth is based on high achievements in digital image processing, the development of computer processors and information storage devices. In this article, an attempt was made to study in practice methods for identifying the contours of objects based on discontinuities in the brightness of a halftone image. The relative performance of each of the methods presented in this article was studied using the MATLAB software tool. Analysis of the image processing results showed that methods such as Marr-Hildreth, LoG and Canny give almost identical results. But still, when processing this test image, the best results can be observed after running the Canny algorithm, although under other conditions another method may be better. Even taking into account the fact that the issue of detecting edges in an image is quite well covered in modern technical literature, it still remains a rather labor-intensive task, since high-quality edge detection always depends on many factors influencing the result. 1. Canny J.F. (1983) Finding edges and lines in images, Master's thesis, MIT. AI Lab. TR-720. The invention relates to means for processing digital images. The technical result is to increase the accuracy of identifying the boundaries of complexly structured images due to the formation of a set of directionally filtered images from the original halftone image through local processing with a compound morphological operator. In the method, the specified operator is formed from linear structure-forming elements with different orientation parameters relative to the image raster of equal length, each filtered image is obtained by interaction of the linear structure-forming element of the composite morphological operator with the original image, the brightness of the pixels in the filtered image is obtained by performing three morphological operations for each pixel of the original image interaction of the original image with a linear structure-forming element. 6 ill. The present invention relates to the field of digital image processing. Segmentation, that is, the selection of homogeneous areas in the original digital image, is one of the most important tasks in computer vision systems, which are used in many scientific, technical and manufacturing industries: medicine, metallography, aerial photography, robotics, flaw detection, security and law enforcement systems, and others. Real raster images obtained from CCD matrices of video cameras may contain shaded and overexposed areas. The same image may contain light objects on a dark background and, conversely, dark objects on a light background with varying degrees of shading. The result is a complexly structured image, the division of which into segments is an ambiguous task. In this case, to improve the quality of segmentation, it is necessary to use segment selection technologies based on modeling of segmentation processes implemented in the human visual analyzer. Today, many different segmentation methods are known, among which we can highlight methods that use information about the connectivity of areas: growing areas, combining areas according to a given rule, dividing and merging areas, segmentation by morphological divides, applications of graph theory methods. The method of growing areas in its simplest implementation [Gonzalez R.S. Digital image processing [Text] / R.S. Gonzalez, R.E. Woods. - M.: Tekhnosphere, 2005. - 1072 p. - ISBN 5-94836-028-8. - P.875] can be described as follows: In the original image, points (crystallization centers) are selected, presumably belonging to the selected areas, for example, these can be points with the maximum brightness level; Next, from these points, the growth of regions begins, that is, the joining of neighboring points to the already existing points of the region, while a certain criterion of their proximity is used, for example, a difference in brightness specified by a certain threshold value; Stopping the growth of areas based on some condition, for example, the maximum deviation of the brightness of new points in the area from the brightness level of the crystallization center or the maximum area of segments. The disadvantage of this method is that pixels of the same segment may have brightness levels, the difference of which exceeds the a priori specified one, and in other fragments of the same image the opposite situation may occur, when pixels of different segments will be identified as pixels of the same segment, since their differences in brightness levels do not exceed the a priori specified one. Another method, close to the previous one, is the region merging algorithm / M.Baatz, A.Schape. - Journal of Photogrammetry and Remote Sensing. Volume 58. Issue 3-4. - Herbert Wichmann Verlag, 2004, pp. 239-258]. It is based on the idea that the pixels of the original image are essentially homogeneous areas, but at the same time they have equally minimal sizes. In this case, the segmentation method must perform merging of neighboring regions that are closest in some parameter (for example, color or texture), determined based on distance analysis (heterogeneity, a function of merging cost), until it is satisfied (or violated) some specified condition (for example, on the size of segments or their number). For this algorithm, the problem of determining crystallization centers completely disappears, but the problem of determining the moment of completion of the merger process becomes especially urgent. In this implementation, as in many others, this is done using a limitation on the size and number of segments, which greatly reduces the flexibility of the method. Texture information is often used when growing and merging areas / Shaw M.; Bhaskar R.; Ugarriza L.G. ; Saber E.; Amuso V.]. However, the use of texture information during growing is limited by the fact that for texture analysis (usually the calculation of various features described in mathematical statistics), as a rule, it is already necessary to have an area larger than one pixel, which is impossible during growing (adding a single pixel to the area). Close to the stated one is the segmentation method / Mantao X., Qiyong G., Hongzhi L., Jiwu Z.], which fundamentally consists of two stages: growing and subsequent merging of segments. Growing regions in this case is used to perform initial oversegmentation, and merging regions, based on graph theory methods, aims to achieve the final optimal state of segmentation. Determination of crystallization centers in this method occurs automatically on the basis of a gradient image obtained from the original one using the Kirsch mask operator. The use of a gradient image here makes it possible to quite universally solve the problem of automatic detection of crystallization centers, since the minima of the gradient image function will correspond to points with a maximally homogeneous neighborhood (potential growth centers of segments). However, the disadvantage of using the Kirsch operator in this situation is its spatial limitation (the neighborhood of only 3x3 pixels is analyzed), whereas when searching for crystallization centers it would be useful to examine the neighborhood of a point on large scales in order to take into account low-frequency changes in the image brightness function and, thus, carry out a more accurate subsequent determination of growth centers. The approach is free of this drawback [Minchenkov M.V. An algorithm for automatic segmentation of raster images based on the growth of clusters from the maxima of the R-value [Electronic resource] / M.V. Minchenkov. - Proceedings of the Graphicon 2004 conference. - Access mode: /2004/ Proceedings /Technical_ru/sl.pdf. - p.2], based on a Rayleigh detector of the boundaries of area objects, which uses analysis areas of various sizes. A common disadvantage of all of these methods is a strict rule for completing the merging process, based on the number of segments in the image or their sizes. This condition sharply reduces the universality of the method for a given configuration. Isolating the contours of objects on halftone raster images can be done in conjunction with selecting the objects themselves. For this, threshold segmentation methods are usually used based on the average brightness value of pixels, for example [RF patent No. 2325044 “Gradient method for identifying the contours of objects on a halftone raster image matrix”] proposes a gradient method for identifying the contours of objects on a halftone raster image matrix, which consists in the fact that for all pixels of the raster image, the norm or the square of the norm of the gradient of the change in their brightness is calculated, then on a new black-and-white monochrome matrix, in black on a white background, all elements are highlighted for which the value of the norm or the square of the gradient norm is greater than the threshold value, and as the contours of objects on monochrome matrix, coherent configurations of black elements are taken, for the chosen method of calculating the gradient, the coefficient is experimentally determined, then the threshold value of the square of the gradient norm is calculated as the product of this coefficient by the sum of the squares of the average values of the brightness change modules of neighboring pixels in rows and columns whose values exceed the overall average levels of non-zero changes, respectively, in rows and columns, and among the connected configurations of black elements on a monochrome matrix, configurations in which the number of incoming elements is less than 5-7 elements are immediately discarded; for the remaining configurations, the average degree of neighborhood is calculated - the quotient of dividing the sum over all elements of the configuration elements adjacent to it by the sum of the elements in the configuration, and those configurations with an average degree of neighborhood less than 3 are discarded, and the remaining ones are accepted as the desired contours of objects. The disadvantages of this method include too many empirically adjustable parameters, which does not allow one to obtain decision rules suitable for images of the same class obtained under different conditions or at different noise levels. With fuzzy segments, it is almost impossible to select such parameters. The closest to the claimed method is the method of image processing according to US patent N 5351305, published on September 27, 1994, MKI G06K 9/40, in which a plurality of directionally filtered images are obtained from the original image by frequency filtering. The output image is generated by selecting each image element either from one of the directionally filtered images or from the original image, depending on the presence or absence of a contrast boundary adjacent to the selected (processed) element of the original image. In this case, the presence of a contrast boundary for a selected image element is determined by calculating the eigenvector and comparing its length with a predefined threshold value. If there is no boundary, the corresponding element of the output image is taken equal to the corresponding element of the input image. If there is a boundary, the corresponding element of the output image is taken to be equal to the corresponding element of the directionally filtered image in which the filtering direction is closest to the defined boundary direction. In the image processing method described above, when determining the image boundary, it is possible that the length of the eigenvector for neighboring image elements changes near the threshold value. In this case, selective noise amplification may occur, caused by sampling adjacent pixels from different images (original and directionally filtered), resulting in degraded output image quality. In addition, source images with different noise levels require significantly different threshold values, while this method does not provide for adaptive changes in this threshold value, which leads to the impossibility of high-quality processing of images with different noise levels. In the presence of a boundary, elements of the output image are sampled from only one of the directionally filtered images, which leads to the complete suppression of all details of the source image that differ in direction from the detected boundary, even in the case when these details are clearly visible in the source image. The technical objective of the proposed method is to increase the accuracy of identifying the boundaries of segments of complexly structured images and, as a consequence, to improve the quality of segmentation (better correspondence to human perception of the image), as well as to increase the degree of automation of the process of analysis and classification of image segments. The task is achieved by creating a set of directionally filtered images from the original halftone image by local processing with a compound morphological operator. The output image is formed from filtered images obtained by processing the original image with a compound morphological operator. In this case, a composite morphological operator is formed from linear structure-forming elements of equal length V, but with different orientation parameters relative to the image raster. Each filtered image is obtained by interacting the linear structure-forming element of the composite morphological operator with the original image F. The brightness of the pixels in the filtered image is obtained as follows. When placing the center of the linear structure-forming element at pixel p with coordinates ij of the original image F, the linear structure-forming element B p () selects three subsets from the set of pixels of image F: 1) where V>q,s>1; s After defining the three subsets, the total brightness value of the pixels in the subsets A1:S1 and A2:S2 is calculated. Then the difference D=S1-S2 is calculated. The new value of pixel brightness is determined by recurrent formulas, in set A2: lk = lk +D and in set A3: qs = qs -D. After the mask of the composite morphological operator passes all the pixels of the original image F, that is, after determining the filtered images for all linear structure-forming elements of the composite morphological operator, the final image G is determined by summing the brightness of the pixels of the filtered images with the same coordinates, and the minimum brightness of the pixel of the final image is determined Gmin and the maximum brightness of the final image Gmax and shift and normalize it according to the formula Figure 1 shows a diagram of the algorithm that implements the presented method. Figure 2 shows a continuation of the algorithm diagram that implements the presented method. Figure 3 shows an example of a linear structure-forming element of a composite morphological operator B( , V) with =1, V=3, =3. Figure 4 shows an example of processing a binary image with a compound morphological operator presented in Figure 3 according to the algorithm diagram presented in Figures 1 and Figure 2. Figure 5 shows an example of processing a binary image with a compound morphological operator presented in Figure 3 according to the algorithm diagram presented in Figures 1 and Figure 2. FIG. 6 shows an example of processing the images shown in FIG. 4 using the Prewitt detector. The method is carried out according to the algorithm diagram presented in Fig.1 and Fig.2. In block 1, the pixels of the original raster halftone image F are entered into the computer, the vertical size is N, and the horizontal size is M. In block 2, a composite morphological operator is formed, including linear structure-forming elements of length V. Block 3 organizes a cycle according to the structure-forming elements of the composite morphological operator . As a result of this cycle, we obtain directionally filtered images. Figure 3 shows an example of the formation of a compound morphological operator. On it, one structure-forming element of the composite morphological operator is highlighted in units, corresponding to the filtration direction =1 for V=3 and =3. For each value in blocks 4-19, an image F() is determined, filtered by direction. The essence of directional filtration is as follows. When placing the center of the linear structure-forming element at pixel p with coordinates ij of the original image F, the linear structure-forming element B p () selects three subsets from the set of pixels F: 1) where V>q,s>1; s Each compound morphological operator produces a triad of sets A1, A2 and A3 for each parameter value and pixel p. Subset A1 is a subset of elements of set F that lie on the structure-forming element B(). Subset A2 is a subset of elements of set F that lie above or to the left of the structure-forming element B(). Subset A3 is a subset of elements of set F that lie below or to the right of the structure-forming element B(). We believe that there is a possibility that each structure-forming element of a composite morphological operator is an element of the segment boundary. Then the average brightness of pixels on both sides of the segment boundary should differ from each other. Comparison of these brightnesses can confirm or refute the hypothesis. The image elements F, which are on both sides of the segment boundary, define the subsets A2 and A3. In blocks 6-9, the sum S1 of the brightness of the pixels of subset A2 for the linear structure-forming element B p () is determined. In this case, the parameters of the cycles k and l in blocks 7 and 8 take the following values, depending on the parameter for the pixel with coordinates ij: 0: k=i-int(V/2), i-1; l=j-int(V/2), j-int(V/2)+V-1; 1: k=i-int(V/2), i+int(V/2)-1; l=j-int(V/2), j+int(V/2)+V-1-k; 2: k=i-int(V/2), i+int(V/2); l=j-int(V/2), j-1; 3: k=i-int(V/2)-1, i+int(V/2); l=k-1, j+int(V/2)-1. In blocks 10-12, the sum S2 of pixel brightnesses of set A3 is determined for the linear structure-forming element B p (). In this case, the parameters of the cycles s and q in blocks 10 and 11 take the following values, depending on the parameter for the pixel with coordinates ij: 0: s=i-1, i+int(V/2); q=j-int(V/2), j-int(V/2)+V-1; j+int(V/2); 3: s=i-int(V/2), i+int(V/2); q=j-int(V/2)-1, k-1. In block 13, the parameter D=S1-S2 is calculated, which determines how significant the difference in the brightness of the pixels of set A2 and set A3 is. To accumulate this significance, the parameter D is added to the brightness of the pixels of set A2, and the parameter D is subtracted from the brightness of the pixels of set A3. These procedures are implemented in blocks 14-16 and 17-19, respectively. In blocks 20-26, the output image G is determined. To do this, the brightness in pixels with the same coordinates in the resulting filtered images is summed (blocks 20-23). The maximum Gmax and minimum Gmin elements of the resulting image are determined and then shifted and normalized according to the formula The process of processing test images using the proposed method is illustrated in Figs. 4-6. Figure 4a shows a test binary image that has a clear boundary of segments, with a spectrum lying in the region of lower spatial frequencies. Figure 4b shows this image after processing with a composite morphological operator, implemented according to the algorithm of Figures 1 and Figure 2 and with the structure-forming elements shown in Figure 3. Figure 5a shows a test binary image that has a clear boundary of segments, with a spectrum lying in the region of high spatial frequencies. Figure 5b shows this image after processing with a composite morphological operator, implemented according to the algorithm of Figures 1 and Figure 2 and with the structure-forming elements shown in Figure 3. Let us carry out a comparative assessment at the expert level of the efficiency of edge detection by the proposed composite morphological operator and the operator based on the Prewitt edge detector. FIG. 6a shows the image (FIG. 4a) obtained after being processed by the Prewitt edge detector, and FIG. 6b shows the image (FIG. 5a) obtained after being processed by the Prewitt edge detector. The test image of Fig. 4a refers to images whose spectrum lies in the region of lower spatial frequencies. The test image of Fig. 5a refers to images whose spectrum lies in the region of high spatial frequencies. Thus, we can obtain comparative characteristics of image processing with different spatial spectra. When expertly assessing the quality of segmentation, the dynamic range between the average brightness of the pixels of the original image (background) and the average brightness of the pixels at the actual boundary of the segment in the processed images was taken into account. It was assumed that the larger this dynamic range, the more resistant the segmentation process is to the influence of interference. Analysis of experimental results on processing test images using the proposed morphological operator showed that the boundaries of the segments have the form of a “Mexican hat”, regardless of the spatial frequencies that the image occupies, which significantly increases the dynamic range at the boundaries of the segment and thereby increases the noise immunity of the segmentation process. A method for segmenting complexly structured raster halftone images based on composite morphological operators, which consists in the fact that from the original halftone image, by local processing with a composite morphological operator, a set of images are formed, filtered in direction, and the output image is obtained from the filtered images, characterized in that the composite morphological operator formed from linear structure-forming elements with different orientation parameters relative to the image raster of equal length V
and each filtered image is obtained through the interaction of the linear structure-forming element of the composite morphological operator with the original image F,
wherein the brightness of the pixels in the filtered image is obtained by performing for each pixel p
original image F
three morphological operations of interaction of the original image F
with a linear structure-forming element B p (), as a result of which three subsets are obtained 1) where V>q ,
s>1; s Sr.No.
Argument
1
2
3
4
5
6
7
Sr.No.
Method & Description
1
2
3
4
5
6
Example
Introduction
Image segmentation
Edge detection algorithms
Roberts operator
Sobel operator
Operator Prewitt
Operator Kirsha
Robinson's cameraman
Contour selection using the Marr-Hildreth method
Contour selection using LoG method
Canny Boundary Detector
Experimental results
conclusions
List of used literature
2. Canny J.F. (1986) A computational approach to edge detection, IEEE Transaction on Pattern Analysis and Machine Intelligence, 8, pp. 679-714.
3. Courtney P, Thacker N.A. (2001) Performance Characterization in Computer Vision: The Role of Statistics in Testing and Design, Chapter in: Imaging and Vision Systems: Theory, Assessment and Applications, Jacques Blanc-Talon and Dan Popescu (Eds.), NOVA Science Books.
4. Hanzi Wang (2004) Robust Statistics for Computer Vision: Model Fitting, Image Segmentation and Visual Motion Analysis, Ph.D thesis, Monash University, Australia.
5. Huber P.J. (1981) Robust Statistics, Wiley New York.
6. Kirsch R. (1971) Computer determination of the constituent structure of biological images, Computers and Biomedical Research, 4, pp. 315–328.
7. Lakshmi S, Sankaranarayanan V. (2010) A Study of edge detection techniques for segmentation computing approaches, Computer Aided Soft Computing Techniques for Imaging and Biomedical Applications. — P. 35-41.
8. Lee K., Meer P. (1998) Robust Adaptive Segmentation of Range Images, IEEE Trans. Pattern Analysis and Machine Intelligence, 20(2). — P. 200-205.
9. Marr D, Hildreth E. (1980) Theory of edge detection, Proc. Royal Society of London, B, 207. - P. 187–217.
10. Marr D. (1982) Vision, Freeman Publishers.
11. Marr P., Doron Mintz. (1991) Robust Regression for Computer Vision: A Review, International Journal of Computer Vision, 6(1). - P. 59-70.
12. Orlando J. Tobias, Rui Seara (2002) Image Segmentation by Histogram Thresholding Using Fuzzy Sets, IEEE Transactions on Image Processing, Vol.11, No.12. - P. 1457-1465.
13. Punam Thakare (2011) A Study of Image Segmentation and Edge Detection Techniques, International Journal on Computer Science and Engineering, Vol 3, No.2. — P. 899-904.
14. Rafael C., Gonzalez, Richard E. Woods, Steven L. Eddins (2004) Digital Image Processing Using MATLAB, Pearson Education Ptd. Ltd, Singapore.
15. Ramadevi Y. (2010) Segmentation and object recognition using edge detection techniques, International Journal of Computer Science and Information Technology, Vol 2, No.6. — P. 153-161.
16. Roberts L. (1965) Machine Perception of 3-D Solids, Optical and Electro-optical Information Processing, MIT Press.
17. Robinson G. (1977) Edge detection by compass gradient masks, Computer graphics and image processing, 6. - P. 492-501.
18. Rousseeuw P. J., Leroy A. (1987) Robust Regression and outlier detection, John Wiley & Sons, New York.
19. Senthilkumaran N., Rajesh R. (2009) Edge Detection Techniques for Image Segmentation - A Survey of Soft Computing Approaches, International Journal of Recent Trends in Engineering, Vol. 1, No. 2. - P. 250-254.
20. Sowmya B., Sheelarani B. (2009) Color Image Segmentation Using Soft Computing Techniques, International Journal of Soft Computing Applications, Issue 4. - P. 69-80.
21. Umesh Sehgal (2011) Edge detection techniques in digital image processing using Fuzzy Logic, International Journal of Research in IT and Management, Vol.1, Issue 3. - P. 61-66.
22. Yu, X, Bui, T.D. & et al. (1994) Robust Estimation for Range Image Segmentation and Reconstruction, IEEE trans. Pattern Analysis and Machine Intelligence, 16(5). — P. 530-538.Drawings for RF patent 2510897
;
. ; .CLAIM
;