The maze of God's perspective in robot vision

          First blog , First, let me introduce my own experience .. One for my students , since 2015 Annual contact circuit and analog electronics , After a year of study, I began to switch to the principle of single chip microcomputer . After a year of hard work , Finally, I was admitted to a specialized specialty of an undergraduate college . During college , To study the  AVR  STM32  SCM and uC/OS_II Embedded system . But in the previous study, I did not record the learning process , And accumulated some experience . Therefore, in the next study of combat control theory and algorithm ( In fact, I want to do missile precision guidance ) Use this platform , I hope all of you can give us your corrections and suggestions .
--------------------------------————————-- The dividing line of business ————————————-------------------------------

One 、 Robot hardware and source code ：

         Actually, I did this because I went to a robot maze competition with my classmates , The robot was bought by the teacher from another company （ You'll see ）, The main control chip of the robot is STM3210F Series of , Very classic Cortx-M3 Core chip . The shape of the robot is shown in Figure 1 ：

 

                                                                                       Figure 1 , Robot shape

     This robot has a week 8 An infrared reflection sensor , But in fact, only 3 individual . There's a SPI A serial port screen of the serial port . The following motors are two small power stepping motors . Generally speaking, the shell is pretty good ~

    Generally speaking, the robot factory code is an algorithm for the robot to explore the maze and an algorithm for the robot to walk along the wall （PID）. Because the maze to be walked is of fixed width and length , So to put it simply , The exploration algorithm in the factory code actually specifies a 8*8 Coordinates of , Let the robot from （0,0） Coordinates go to （8,8） Coordinates are OK . The turning priority of the robot at the fork of the road is X Axis and Y The positive direction of the axis takes precedence .

    Because when we got the robot, it was a week before the game , So I just make the clock division coefficient of the stepping motor pulse a little smaller , Let the robot run faster . Then I went to the game . It has to be said that the commercialization of this competition is really serious .

Two 、 The idea suddenly came to me

    I saw a video before , It should be a video of an international robot competition , There is also a maze robot in the video , But the robot should also use a camera to identify the best route after image processing . It happened that , A rectangle recognition algorithm was just done before the notice of this competition , Think about it. Although we can not reach the international level, it is not a problem to realize a function .

3、 ... and 、 Image recognition processing

    The premise of using computer to simulate robot to find the optimal path is to obtain the image information of labyrinth track . Take the orbit in Figure 2 as an example .

Figure 2

 

    Image processing needs to be grayed out first , In the process of edge detection . Grayscale processing uses MATLAB Of rgb2gray Function is OK .

     Edge detection simply means that the image is in a region where the intensity changes dramatically .

    Strength changes are generally divided into two types ：1、 Step change .2 Roof type change .

（ Reference herein duan_hy The author's Edge detection algorithm . Click to open the link ）;

 

 

Processed image

Four 、 Equivalence of maze image information .

    In my opinion , For ease of handling , After the edge detection is completed, the whole maze needs to be equivalent to a 17*17 Matrix . Because the maze is a 8*8 Maze of tracks . So the idea of equivalence is to put a lattice of the maze , And the walls of a grid length of the labyrinth are regarded as an element . So we need 16*16 Elements , Plus the edge is 17*17 Elements .

    An equivalent process requires X/Y The two directions are equivalent . Because the algorithms in the two directions are similar , Therefore, the following takes one direction as an example ：

    1、 First, determine the line coordinates of the image to be detected , Because there are eight paths , Divide the whole maze horizontally into 8 A portion is enough , The following figure shows the lines to be detected , hereinafter referred to as ‘ Detection line ‘.

    2、 The second step , Find the left and right edges of the maze , Then, each detection line is divided into 16 Share , Then, after the test, it is equivalent to the corresponding 17*17 The matrix of . The figure below is a schematic diagram

Because what we are testing is OK , So we need to separate one line from each line when we are equivalent to coordinates . After the test is successful, the following is true

The detection of columns is the same as that of rows , I won't go on and on . Here is a comparison between the original maze and the equivalent maze

                                                                                                             

 

Last , Is to write one that can be seen from the bottom right corner （0,0） Go to the upper left corner （7,7） The algorithm is OK .

Be careful ： You need to walk two pixels at a time , Simply put, roads and walls are elements , So every time you go through a coordinate , From （0,0） Go to the （0,1） It has gone through two elements （ A wall , One way ）;

Here I write a simple X,Y The positive direction of the axis first algorithm tried , It's more successful .

5、 ... and 、 summary

    In the future, the author will transplant the code to the main control chip as STM32F10X The actual test is carried out in the robot . Welcome your valuable comments .

I am a beginner , New to the bank , The basic knowledge of mathematics is limited. I'll laugh at you , Welcome to correct .

 

 

Attached test MATLAB Code

page2 = page1;
%%% The maze is converted to coordinate points 
xsData = zeros(16,16);
xs = zeros(8,599);
h=20;
x=1;
while h<387
    for i=1:599
        for j=1:5
            xs(x,i) = xs(x,i) + page1(h+j,i);
        end
        for j=1:5
            xs(x,i) = xs(x,i) + page1(h+j,i);
        end
        page2(h,i) = 255;
    end
    h=h+48;
%%%    plot(t,xs);
    x = x+1;%% Record the next test line 
end
%%% Deal with vertical lines below %%%%%%
sxax = zeros(8,10);%% Save vertical coordinates 
sxtime = 1;%% Vertical coordinate counting 
for i=1:8
    for j=1:599
        if xs(i,j)>2500 %% Vertical line detected 
            sxax(i,sxtime) = j;%% Save vertical coordinates 
            sxtime = sxtime+1;
        end
    end
    sxtime = 1;
end
%%% Next, deal with vertical coordinates %%%%
axmax = 0;%% Maximum coordinate value 
axmin = 500;%% Minimum coordinate value 
pagejs = 0;%% Image segmentation cardinality 
for i=1:8 
    for k=1:10
        if axmax<sxax(i,k)
            axmax = sxax(i,k);%% Get the maximum value of career change 
        end
        if sxax(i,k)>0
            if axmin > sxax(i,k)
                axmin = sxax(i,k);%% Get the minimum value of line change 
            end
        end
    end
    pagejs = (axmax - axmin)/16;
    
    for j=1:10
        if sxax(i,j) > 0 %% There are coordinates 
            xsData(i*2,floor((sxax(i,j)-axmin)/pagejs)+1) = 255;
        end
    end
    a = axmin;%% From minimum   The coordinates begin to line 
    while a<axmax
        for b=1:50
            page2(b+(50*(i-1)),a)=255;
        end
        imshow(page2);
        a = a+pagejs;
        a = floor(a);%% rounding 
    end
end
%%% following   Remove interference ..
for i=1:16
    for j=1:16
        if xsData(i,j)==255 %% A white dot is detected 
            if rem(j,2)>0 %% White dot coordinates must be singular 
                if xsData(i,j+1)==255 %% Detect the even coordinates next to the white dot 
                    xsData(i,j+1) = 0;%% Path is an obstacle , Indicates an error   correct 
                end
            else %% If it is not singular, it is an error   correct 
                xsData(i,j)=0;
            end
        end
    end
end
figure;
imshow(xsData);