APMCM It's called little beauty , Submit your paper in English as meisai , The game time is after the national game and before the American game , Therefore, it is very suitable as MCM Warm up match .

For the first time in such a formal competition , And it's written in English , As a warm-up to the US game , 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 win the second prize , I'm quite satisfied .

<> Pre match preparation

APMCM Four days , There are some mid-term exams during the period , Therefore, the grasp of time is very important . We'll find a place for discussion half a month in advance , Excluding bookstores , Behind the cafe and teaching building , We chose the study and discussion space of the general library . From 8 a.m. to 10 p.m , During the meal at Denggao Road .
We mainly looked at the topics of previous years , Learned a little modeling skills , Then I bought Massey and Matlab Relevant information of . There are also such considerations in choosing the place of discussion in the library : In case of interprofessional problems, you can read relevant materials in time .

<> During the game

2021 Asia Pacific race ,A About edge detection , Involving graphics and image processing ;b The questions are highly interdisciplinary , Not considered ;c Traditional data processing . We happen to have Gonzalez on hand 《 Graphics and image processing 》, And I just watched the section on edge detection , So we chose to rush A topic .
The game lasted four days .
After the library closed on the first day , We borrowed the conference room of the information institute to work until 1 a.m .
Later, it was found that the efficiency was not high all night , After that, it was unified from eight in the morning to ten in the evening , Then they go back to their dormitories to tidy up .
Although the general direction was determined on the first day , However, the implementation of the code has some functions, and the repetition still takes some detours .
About information : I chose HowNet and Tongfang , Have a problem CSDN and mathwork, in general , This problem is difficult to get started , But the comparison is in the direction of our group .
If there's anything else , Renato is really using it all , I've seen countless versions .

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

<>2021APMCM problem A

<> 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

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

<>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


* SweepAngle indicates the sweep angle from the start point to the end point,
angular system;
* Size indicates the radius value of specified ellipse or elliptic arc in the
X and Y directions;
* RotationAngle indicates the rotation angle value of specified ellipse or
elliptic arc, angular system;
* 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.
* 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 professional terms , Timely translation into Chinese is very important . I got it within half an hour of getting the question A,B,C Three question word and pdf Version translation , Our group was able to discuss the selected topics in time , I would like to thank my friends and his friends here WPS member .
of course , There will always be imperfections , When you encounter problems with individual words or sentences, you still have to check them one by one .
After multiple references , We got a preliminary impression of the subject :
Edge detection of the given picture , And mark the edge , Count different sub-pixel structures according to the requirements of the topic .
At this time , It's time Gonzalez came in handy . There are no white flowers in 160 oceans .
Tianjie fighting skill :“ Chapter 10 : image segmentation ”!
From point , Line and edge detection , To multi threshold processing , This book provides us with a key perspective to cut into the problem , of course , Follow this idea and then go online to find information , It will be much clearer .

<> Basic knowledge

<> Edge model

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

Edge models can be classified according to their gray profile . Can be divided into step models , 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 “ gradient ” As an image f Anywhere in the (x,y) Tool for edge strength and direction at , use ∇f Represent it , And define it as a vector .

∇f(x,y)≡grad[f (x,y)]≡ [ g x ( x , y ) g y ( x , y ) ] \begin{bmatrix} g_x
(x,y)\\ g_y (x,y) \end{bmatrix}[gx​(x,y)gy​(x,y)​]= [ ∂ f ( x , y ) ∂ x ∂ f ( x
, y ) ∂ y ] \begin{bmatrix} \cfrac{\partial f (x,y)}{\partial x}\\
\cfrac{\partial f (x,y)}{\partial y} \end{bmatrix}⎣⎢⎢⎡​∂x∂f(x,y)​∂y∂f(x,y)​​⎦⎥⎥⎤

Gradient vector at point (x,y) Amplitude at 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 is orthogonal to the direction of the gradient vector at that point .

<> algorithm

<> Edge detector

Sobel operator
Is a discrete differential operator . It combines Gaussian smoothing and differential derivation , It is used to calculate the approximate gradient of image gray function .Sobel The operator first convolutes the image pixels , Then do threshold operation on the generated new pixel gray value , 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 false edges may appear .

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

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

<> Salt and pepper 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 be denoised , And randomly obtain the position of each pixel to be denoised P(i, j) And specify the pixel value as 255 perhaps 0.

<> noise reduction

1. Neighborhood averaging method is a spatial domain noise smoothing 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 the point . Median filter is a nonlinear processing method to suppress noise . This method is simple , Easy to implement , And can
Better protection of the border ‚ But sometimes thin lines and small areas in the image are lost , The size and shape of the adopted 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) Restoration method with minimum mean square error between . Wiener
Comparison between image filtering and neighborhood average method for Gaussian white noise , Good filtering effect . It has better selectivity than linear filter , It can better save the edge and high-frequency detail information 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 doesn't make
Human satisfaction . in addition , The minimum mean square error criterion does not necessarily match the human visual effect .

<>Hough Transform

standard Hough Transform (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 normal x Angle of shaft measured clockwise ( In degrees ).θ The scope is –90° ≤
θ < 90°. The angle of the line itself is θ + 90°, Also relative to positive x Shaft measured clockwise .

Matlab The image processing toolbox provides 3 Geyu Hough Transform related functions . function hough() Implements the concepts discussed earlier ; function houghpeaks() seek Hough Peak value of transformation ( High count of accumulation unit ); function houghlines() Line segments are extracted 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 Gaussian , Salt and pepper filtering .

<> summary

* It's important to find a teammate with good code , When the model comes out, there are still many holes in applying it to practical problems , The algorithm needs to be improved , Even ready-made code has to be understood , Let alone write code according to the algorithm .
* mathtype Really fragrant . Why doesn't this blog post have too many formulas , Because use latex It's too much trouble to type the formula !
* 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 .
* HowNet works well , But the key words should be found , Under the category of computer vision , Even edge detection has many applications , We should find the right direction for the competition topic .
* Having a professional book at hand will be much more convenient .
reference material : Gonzalez 《 Graphics and image processing 》

©2019-2020 Toolsou All rights reserved,
C++ of string of compare usage MySQL Basics Commonly used sentence ( Add / delete / modify query )C Language of a Gobang game implementation QT5.9 Use of learning notes QSqlQuery Method of Qt Getting Started tutorial 【 Basic controls 】QCalendarWidget calendar control java Polymorphic array of web Front end signature plug-in _signature_pad Plug in implements electronic signature function centos7 install RabbitMqspringboot use redis Experiment 4 Automated test tools - software test