2021apmcm post game Summary - edge detection

APMCM It is called xiaomeisai , Submit your thesis in English as Massey , The competition time is after the National Games and before the American Games , Therefore, it is suitable for MCM Warm up match of .
For the first time, I participated in this kind of formal competition , And writing in English , As a warm-up to the US race , It is necessary to spend four days practicing in advance . In daily classes and （ almost ） Under the condition of regular rest , Final , Our team can get the second prize , I am quite satisfied .

Prepare for the game

APMCM Four days , During this period, there are some mid-term exams , Therefore, it is very important to grasp the time . We'll find the discussion place half a month in advance , Excluding bookstores 、 Behind the coffee shop and the teaching building , We chose the study and discussion space of the general library . From eight in the morning to ten in the evening , During this period, I had a meal on Denggao road .
We mainly looked at the topics of previous years , Learned a little modeling skills , Then I bought Massey and Matlab Related information . There are also such considerations when choosing the place of discussion in the Library ： When encountering interdisciplinary problems, I can read relevant materials in time .

In the game

2021 In the Asia Pacific race ,A Question about edge detection , Involving graphics and image processing ;b Questions are highly interdisciplinary , Don't consider ;c Traditional data processing . We happen to have Gonzalez on hand 《 Graphics and image processing 》, And I just watched the section about edge detection , So we choose to rush A topic .
The race lasted four days .
After the library closes on the first day , We borrowed the conference room of the information institute to work until 1 a.m .
Later, I found that the efficiency was not high all night , After that, it unified eight in the morning and ten in the evening , Then they go back to their dormitories to tidy up .
Although the general direction has been determined on the first day , However, the implementation of the code has some functions, and it still takes some detours .
About information ： I choose HowNet and Tongfang , Problems encountered are CSDN and mathwork, in general , This problem is difficult to get started , But the comparison is in the direction of our group .
There are words , Renato is really using everything , I have seen countless versions .

Now on the question A Briefly describe our thinking and analysis of edge detection at that time ：

2021APMCM problem A

The problem background

Problem A
Image Edge Analysis and Application

With the development of science and technology, the demand for measurement accuracy of various workpieces and parts is getting higher and higher, and the requirements for measurement instruments are also getting more and more demanding. Various image measuring equipment such as digital image size measuring instrument are now gradually replacing the traditional manual caliper measurement application. Generally, after the camera is calibrated, based on the the dot matrix or checkerboard feature information of the calibrated image, the image can be corrected for distortion and the mapping relationship between the image coordinate space and the world coordinate space can be calculated.

The edge of the target object is very useful for image recognition and computer analysis. Image edge is the reflection of discontinuity of the local characteristics of an image. The edge can outline the target object and make it clear to the observer at a glance. The edge contains rich intrinsic information (such as orientation, step property and shape, etc.), which is an important attribute for extracting image features in image recognition. Image edge contour extraction is a very important processing in boundary segmentation and also a classical problem in image processing. The purpose of both contour extraction and contour tracking is to obtain the external contour features of an image. Applying certain methods where necessary to express the features of the contours to prepare for image shape analysis has a significant impact on performing high-level processing such as feature description, recognition and understanding.

The contour can be described as a set of ordered points, and the common expression of the contour is a polygon. Contours can be either closed or open. The closed contours on an image are all connected start to end, and the open contours generally intersect with the image boundary. In Figure 1, there are five closed contour curves. Although edge detection algorithms such as sobel and canny can detect the image edge pixels boundary based on the difference of image gray value, it does not take the contour as a whole. On an image, a contour corresponds to a series of pixel points. The contour describes a continuous sequence of points, and the edge pixel points can be assembled into a contour curve to describe the edge information of the image.

A sub-pixel is a virtual pixel defined between two physical pixels of an image acquisition sensor. To improve resolution or image quality, sub-pixel calculation is very useful. Image sub-pixel edge extraction is a more accurate method than traditional pixel edge extraction. Sub-pixel means that the coordinate value of each pixel point on the image is no longer integer positioning, but floating-point number positioning. If the accuracy is increased to 0.1 pixel using subpixel technique, it is equivalent to 10 times higher resolution of image system analysis.

For the following three schematic diagrams, in Figure 1, the object edge contour lines of the image have been extracted and the image edge contour has been segmented into basic graphics such as straight line segments, circular arc segments, and circles. In Figure 2, The edge contour of a rounded rectangle is divided into several geometric shapes. In Figure 3, an elliptical sub-pixel contour curve is shown drawn on the background of a grayscale pixel image grid.

Figure 1. Image Edge Detection

Figure 2. Segmentation Image Edge Contour

Figure 3. Sub-pixel Edge Contour of Image

subject

Question 1

: Build a mathematical model, analyze the method and process of extracting sub-pixel edge with 1/10 pixel accuracy and above, extract sub-pixel edge contour boundaries of the main edge parts of the objects on the three images (Pic1_1, Pic1_2, Pic1_3) in Annex 1, and convert the edge sub-pixel point data into ordered edge contour curve data, with the need to considering how to eliminate the interference effects of edge burrs and shadow parts of the edges. Note that the Pic1_3 image was taken under relatively complex lighting conditions, with more interference information.

a)Please draw the extracted edge contours in different colors on the image, output it as a color edge contour image and save it as png image format for submission. The file names are pic1_1.png, pic1_2.png, pic1_3.png.

b)Output the edge contour data in the format of EdgeContoursOutput.xls file in Annex 1, and output the data of the Pic1_1 and Pic1_2 images to the corresponding Sheet1 and Sheet2 of the worksheet respectively. The output data contains the total edge contours count, the total edge contours length in the image coordinate space, point count and length of each contour curve, and the X and Y coordinate data of each contour point.

c)The total contour curves count on each image and the point count and length data on each curve should be given in the paper. See Table 1, Table 2 and Table 3.

Question 2

：While the measured image is taken, there is a dot matrix calibration plate placed at the same horizontal height of the target object. The diameter of the dots on the calibration plate is 1 mm, and the center distance between two dots is 2 mm. Annex 2 contains three calibration plate images taken at different angles and one product image (Pic2_4.bmp). Please build a mathematical model, use the calibration plate image information to conduct image rectification analysis of the product image and consider how to calculate, as accurately as possible, the actual physical sizes of the edge segmentation fitting curve segments on the product image. Please calculate the length (mm) of each edge contour, and finally calculate the total edge contours length (mm). According to the contour data labeling shown in Figure 4, output the data results of the table format files such as EdgeContoursLengthOutput.xls in Annex 2.

Figure 4. Image Contour Data Labeling

Question 3

: Two sub-pixel contour edge data (EdgeContour1.xls and EdgeContour2.xls) are provided in Annex 3, and the shape are shown in Figure 5. Please build a mathematical model, analyze the automated segmentation and fitting of edge contour curve data into straight line segments, circular arc segments (including circles), or elliptical arc segments (including ellipses), and discuss the model method or strategy for automated segmentation and fitting of edge contours. The blue curve starts from the blue digit 1 label and outputs the model calculation result data along the arrow direction. The green curve starts from the green digit 1 label and outputs the model calculation result data along the arrow direction. Please fill in the parameters of the segmented curve segments into the table in the table format. Submit Table 7 and Table 8 (regarding contour 1 and contour 2 segmentation data) in the paper. Note that the type of the lines in this table is populated according to the actual type.

Figure 5. Edge Contour Curve Data

Remark:

1. SweepAngle indicates the sweep angle from the start point to the end point, angular system;
2. Size indicates the radius value of specified ellipse or elliptic arc in the X and Y directions;
3. RotationAngle indicates the rotation angle value of specified ellipse or elliptic arc, angular system;
4. For the direction of rotation angle, the rotation direction from positive direction of x-axis to positive direction of y-axis is positive direction, and vice versa is negative direction.
5. All image coordinate points are expressed under the image coordinate system, that is, the upper left corner is the (0,0) origin, the positive direction of the X-axis is to the right, and the positive direction of the Y-axis is downward.

analysis

First , For this kind of problem containing technical terms , Timely translation into Chinese is very important . Within half an hour of getting the question, I got A、B、C Three questions word And pdf Version translation , We can discuss and determine the topic in time , Here I thank my friend and his WPS members .
Of course , There will always be imperfections in the turnover , When you encounter problems with individual words or sentences, you still have to check them one by one .
After many references , We got a preliminary impression of the topic ：
Perform edge detection on the given image , And mark the edge , Count different sub-pixel structures according to the requirements of the topic .
This is the time , It's time for Gonzalez to come in handy . There are no white flowers in 160 oceans .
Tianjie fighting skill ：“ Chapter ten ： Image segmentation ”！
From the point of 、 Line and edge detection , To multi threshold processing , This book provides us with a key angle to cut into the problem , Of course , Follow this idea and then go online to find information , It will also be much clearer .

Basic knowledge of

Edge model

Different images have different gray levels , There are usually obvious edges at the boundary , This feature can be used to segment the image . Edge detection is a common method to segment an image according to gray mutation .

Edge models can be classified according to their gray Profile . It can be divided into Step model 、 Slope model and Roof edge model etc. .
Although noise and edges can cause edges to deviate from the ideal shape , However, the edge of the image can still be recognized by using the characteristics of the edge model . In the process , We use it “ gradient ” As an image f Anywhere in （x,y） At the edge of the strength and direction of the tool , use ∇f Represents it , And define it as a vector .

∇f(x,y)≡grad[f (x,y)]≡$\left[\begin{array}{c}{g}_x(x,y)\\ g_y(x,y)\end{array}\right]$=$\left[\begin{array}{c}\frac{\partial f(x,y)}{\partial x}\\ \frac{\partial f(x,y)}{\partial y}\end{array}\right]$

Gradient vector at point (x,y) The amplitude of the M(x,y) Given by its Euclidean vector norm .
The angle is relative to x Axis measured counterclockwise . spot （x,y） The direction of the edge at this point is orthogonal to the direction of the gradient vector at this point .

Algorithm

Edge detector

Sobel operator Is a discrete differential operator . It combines Gaussian smoothing with differential derivation , It is used to calculate the approximate gradient of image gray function .Sobel The operator first convolutes the image pixels , Then the threshold operation is done for the gray value of the new pixel , To determine the edge information .
if Gx It's the original picture x Convolution in direction ,Gy It's the original picture y Convolution in direction .
Sobel The operator can smooth and suppress the noise , But the edge is thicker , And there may be false edges .

Canny Edge detector Based on three basic goals ： Low error rate 、 The edge points should be well positioned 、 Single edge point effect .
Based on three basic goals , For the edge of one-dimensional step polluted by additive Gaussian white noise, the numerical optimization is used , The following conclusions can be drawn , That is, a better approximation of the optimal step edge detector is the Gaussian first derivative .

canny The steps of edge detection algorithm are summarized as follows ：
1. Use a Gaussian filter to smooth the input image .
2. Calculate gradient amplitude image and angle image .
3. Apply non maximum limits to gradient amplitude images .
Double threshold processing and connectivity analysis are used to detect and connect edges

Pepper and salt blur

Salt and pepper noise is the random appearance of black and white pixels on the image . At the specified signal-to-noise ratio SNR（ Its value range is [0, 1] Between ） after , Calculate the total number of pixels SP, Get the number of pixels to noise , And randomly obtain the position of each pixel to be noisy P(i, j) And specify the pixel value as 255 perhaps 0.

Noise reduction

1. Neighborhood averaging method is a spatial domain smoothing noise technology , It is a linear filtering technology ．

2. The basic principle of median filtering is to replace the value of a point in a digital image or digital sequence with the median value of each point in a neighborhood of that point . Median filter is a nonlinear processing method to suppress noise ． This method is simple , Easy to implement , And it can Better protect the boundary ‚ But sometimes thin lines and small areas in the image will be lost , The size and shape of the window sometimes have a great impact on the filtering effect , At the same time, it should be pointed out that it has no obvious effect on filtering Gaussian noise .

3．Winner Filtering is to make the original image f（x,y） And its restored image g（x,y） The restoration method with the minimum mean square error between ． Wiener The image filtering of Gaussian white noise by filtering is compared with the neighborhood average method , Good filtering effect . It has better selectivity than linear filter , It can better save the edge and high-frequency details of the image . although Wiener Filtering can obtain satisfactory results in most cases , Especially for images with white noise , But when the signal-to-noise ratio is low , The effect often cannot make People are satisfied . in addition , The minimum mean square error criterion does not necessarily match human visual effects .

Hough Transformation

standard Hough Transformation (SHT) Use parametric representation of lines ：

Variable rho Is the distance from the origin to the line along a vector perpendicular to the line .θ Is the vertical projection from the origin to the line relative to the positive x The angle measured clockwise by the shaft （ In degrees ）.θ The range is –90° ≤ θ < 90°. The angle of the line itself is θ + 90°, Also relative to positive x Measured clockwise by the shaft .

Matlab The image processing toolbox provides 3 One and Hough Transform related functions . function hough() Implements the concepts discussed above ; function houghpeaks() seek Hough Peak value of transformation （ High count of accumulation units ）; function houghlines() Extract line segments from the original image based on the results from the other two functions .

Partial image processing

Add noise to the picture with different parameters , Then Gauss 、 Salt and pepper filtering .

summary

1. It's important to find a teammate with good code , When the model comes out and is applied to practical problems, there are still many holes , The algorithm needs to be improved , Even ready-made code must be understood , Not to mention writing code based on algorithms .
2. mathtype It's delicious . Why doesn't this blog post have too many formulas , Because with latex It's too troublesome to write the formula ！
3. mathwork It's about matlab Introduction of some algorithms and functions , If you don't understand it when using it, you can go to the top first .
4. HowNet is easy to use , But the key words should be found , Under the category of computer vision , Even edge detection has many applications , Find the right direction for the competition topic .
5. Having a professional book at hand will be much more convenient .

Reference material ： Gonzalez 《 Graphics and image processing 》