Answers.Body: <p>I assume that you are familiar with homogeneous transformations and the meaning of <em>global</em> and <em>local</em> coordinate frames. If not, global frame is the fixed frame; a reference frame for your whole problem, such as the starting position of your robot. Local frame should be placed anywhere <strong>on</strong> your robot, preferably in the middle-point of the virtual line (called &quot;<em>robot base</em>&quot;) that connects the two actuating wheels in the back of your robot (given that you follow the differential drive setup). If not, just place the local frame anywhere that makes sense on the robot, such as its geometrical center.</p>
  <p>Answering your questions:</p>
  <blockquote>
  <p>How do I know where the lines intersect?</p>
  </blockquote>
  <p>The accepted answer in <a href="https://stackoverflow.com/questions/12747955/how-do-i-quickly-find-the-closest-intersection-in-2d-between-a-ray-and-m-polylin" title="This">this</a> is <strong>by far</strong> the best I have seen around, which I have also used successfully for a project regarding robotic exploration in an unknown maze.</p>
  <blockquote>
  <p>How do I find the angles of the lines using computer vision?</p>
  </blockquote>
  <p>You <strong>DON'T</strong> need computer vision for that. For every line, pick 2 points expressed in global frame (x1,y1),(x2,y2) and calculate the slope of the line as:</p>
  <pre><code>lambda = (y2-y1) / (x2-x1)
  </code></pre>
  <p>Then the angle of the line is <code>atan(lambda)</code>, in global frame. Do this for all lines and then subtract the angles of any two lines to find their relative angle (pay attention to the sign).</p>
  <p>Alternatively, I would personally use the <a href="https://en.wikipedia.org/wiki/Random_sample_consensus" rel="nofollow noreferrer" title="RANSAC">RANSAC</a> algorithm to de-noise the detected points and give me the line equation based on the consensus of all points. This line equation should already have the slope in it:</p>
  <pre><code>y = ax + b
  </code></pre>
  <p>where <em>a</em> is the slope and <em>b</em> is the vertical offset. Then do the aforementioned steps, i.e. atan(a) and subtraction to find the relative angle between two lines.</p>
  <p>If you <strong>explicitly</strong> want to use computer vision, maybe train a neural network on known angles and then classify images of lines to output their angles. This approach will be by far the most painful and I do NOT recommend it at all.</p>
  <blockquote>
  <p>How do I update this information based on my coordinates?</p>
  </blockquote>
  <p>This can be quite tricky. If the line points are detected by your on-board camera, you first of all need to convert them from the camera's coordinate frame (found in the camera's datasheet) to your robot's local frame, as explained above. To do this, you need to calculate the static transformation between the two frames (static because it will never change if the camera is fixed on the robot, you only define it once).</p>
  <p>Then you need to convert the detected line equation from your robot's frame to the global frame. In order to do so, you need to keep track of the robot's pose (position + orientation) while it moves in the 2D or 3D space. This is generally a hard task because it needs an excellent implementation of your localization algorithms, such as an Extended Kalman Filter or Particle Filter. The localization algorithm will provide you with the information that you need at any point in time in order to convert the lines/points from your robot frame to the global frame and visualize them.</p>
  <p>In short: you need to transform the detected lines / points from <strong>camera frame -&gt; robot (local) frame -&gt; global frame</strong>. The first transformation is static (calculated once and never changes) whereas the second one is dynamic (changes every time the robot moves or turns). The first one is fairly easy to calculate but the second one can be a real pain.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-05-28T13:11:06.683Z
Answers.LastActivityDate: 2020-07-29T23:01:25.673Z
Answers.LastEditDate: 2020-07-29T23:01:25.673Z
Answers.UserDisplayName: pcko1
Answers.Body: <p>Finding lines in an image often leads to the Hough line transform. Many libraries implement it, including <a href="https://docs.opencv.org/3.4.1/d6/d10/tutorial_py_houghlines.html" rel="nofollow noreferrer">OpenCV</a>. Getting the lines should answer subsequent questions (and it doesn't, please consider having one question per post, and some other sites on <a href="https://stackexchange.com/">StackExchange</a> may be better suited than AI.SE).</p>
  
  <p>Alternative approaches based on Machine Learning may also exist. It may be interesting at this point to look into libraries that do human pose/gait recognition. Some library may be repurposed to recognize the "field gait", assuming the field outer mark is its "gait"-equivalent.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-05-27T14:40:23.990Z
Answers.LastActivityDate: 2018-05-27T14:40:23.990Z
Answers.UserDisplayName: Eric Platon
Answers.Body: <p>I suggest you first consider your coordinate systems.  There are two.</p>
  
  <p><strong>Field Coordinate Axis</strong></p>
  
  <p>Field boundary corners are in field coordinates (for example): { (-50.0, -35.0, 0), (50.0, -35.0, 0), (-50.0, -35.0, 0), (50.0, -35.0, 0) }, all values in meters.</p>
  
  <p>At any moment in time the camera in the robot: is at (x, y, z) and oriented relative to north by angle theta, measured clockwise when looking from above the field. The value of z may be 2.0 (for example).</p>
  
  <p><strong>Image Coordinate Axis</strong></p>
  
  <p>The coordinate axes of the camera images is (w, h).
  You have frames in time (perhaps every 33 msec containing grids in a the w-h coordinate axis with 1080 x 960 pixels (for example) providing an index range (&lt;0, 1079>, &lt;0, 959>).</p>
  
  <p><strong>Maintaining Orientation of Short Robots (small Z)</strong></p>
  
  <p>You are correct that the Harris feature detection may not work because z (the distance from the surface of the field to the center of the camera lens) may not be sufficient for that algorithm unless the robot is near a corner.  The rectangle of the field boundary is not at all rectangular in the camera's w-h focal plane.  For the same reasons, finding lines and then locating their intersections is not the optimal approach either.</p>
  
  <p>Pretend you are the robot.  As the robot survey's the field, it can assemble a model of the 360 degree periphery.  What it sees is a gradually curved line with three upside down v shapes representing the field corners.  Unless the robot is almost on top of one of the corners, all four features that correspond to the corners of the field boundary will only vaguely appear to be corners at all.</p>
  
  <p><strong>Mathematics of Obtuse Corner Detection</strong></p>
  
  <p>Two tangent lines stem from each corner.  They intersect at a discontinuity of the line's derivative, dw/dh, the slope in 2D phase space of the camera frame.  The angle found between these two tangent lines will usually be closer to 175 degrees than 90 degrees, yet they are still detectable because the rest of line has no other like discontinuities of slope.  From a Fourier transform perspective, the 360 degree line is actually a periodic waveform primarily comprised of the 4th, 12th, 20th, 28th, and 36th harmonics.  If you are good with that level of mathematics and you record past frames, you can exploit Fourier's series and FFTs for high accuracy in corner detection.</p>
  
  <p>As you develop your theory and your software, you may find that other aspects of play need to be considered.  It may be best to think of those aspects now.  Fortunately, if another player or official blocks a portion of the field's boundary line, it will create a discontinuity in the line itself, but not the slope of the line in the w-h plane of the camera's image.  Your implementation will need to differentiate those two types of differences, which is hardly an insurmountable problem.  Discontinuity in a line and discontinuity in its derivative are mathematically distinct naturally.</p>
  
  <p><strong>Redundancy in Feedback Channels</strong></p>
  
  <p>If the robot can sense its location and orientation in other ways and know x, y, z, and theta above with some degree of reliability, the expected location of the obtuse angles and the detected ones can be compared to determine the probability that the robot is properly detecting is orientation.</p>
  
  <p><strong>Questions in This Context</strong></p>
  
  <p>In this context the questions you listed need some reorientation.</p>
  
  <p><strong>How do I know where the lines intersect?</strong></p>
  
  <p>The line has two edges that may lie on the same pixel in many cases, so that is not easy to detect in an image with many other lines.  If the line is of a particular color, hue detection can assist in line detection.  If the above corroborative data analysis is employed, then misinterpretation of edges can be corrected quickly in real time.  Once the lines are found, the detection of dh/dw at any given point on the line can be estimated using linear regression of segments and windowing (looking at short segments one at a time).  When an otherwise relatively stable slope quickly shifts 5 or 10 degrees in angle between windows, you have a high probability that you've found a distant field corner.  A shift in 70 to 80 degrees combined with a lower h value in the frame is indicative of a corner in close proximity.</p>
  
  <p><strong>How do I find the angles of the lines using computer vision?</strong></p>
  
  <p>Edge detection, systematic elimination of candidate edges that are not likely field boundaries, and then linear regression of the best candidates.</p>
  
  <p><strong>How do I update this information based on my coordinates?</strong></p>
  
  <p>Just save them in an appropriate array of x, y, z, theta vectors, indexed by frame number.  You will probably want to keep track of what you think your robot's x, y, z, and theta values are and constantly test your assumptions against your most recent inputs.  Otherwise, your robot can become disoriented.  The more ways you can detect location and orientation, the higher reliability you will have in the overall system.  If your vision can detect some feature at each goal that will not change during the game, it may help.  Ultimately your x, y, z, and theta are the parameters in a model and the use of gradient descent and auto-correlation and other auto-correction techniques need to be applied to keep your robot's orientation model continuously updated.</p>
  
  <p><strong>Recommend Diving Into the Math First</strong></p>
  
  <p>The 3D trig to work all of the above out in detail is initially daunting but not that far beyond high school trig if the researcher develops some clear diagrams first and then takes the time to resurrect any rusty mathematics skills or hone some new ones.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-05-29T08:09:41.333Z
Answers.LastActivityDate: 2018-05-29T08:09:41.333Z
Answers.UserDisplayName: Douglas Daseeco
Body: <p>I  want to use computer vision to allow my robot to detect the corners of a soccer field based on its current position. Matlab has a detectHarrisFeatures feature, but I believe it is only for 2D mapping.</p>
  <p>The approach that I want to try is to collect the information of the lines (using line detection), store them in a histogram, and then see where the lines intersect based on their angles.</p>
  <p>My questions are:</p>
  <blockquote>
  <ol>
  <li>How do I know where the lines intersect?</li>
  <li>How do I find the angles of the lines using computer vision?</li>
  <li>How do I update this information based on my coordinates?</li>
  </ol>
  </blockquote>
  <p>I am in the beginning stages of this task, so any guidance is much appreciated!</p>
  
Tags: <algorithm><computer-vision><matlab>
Title: How to use computer vision to find corners of a soccer field based on location coordinates?
UserDisplayName: aa1
ThreadText: # How to use computer vision to find corners of a soccer field based on location coordinates?
  
  (Asked by: username_0 on 2018-05-23)
  
  I want to use computer vision to allow my robot to detect the corners of a soccer field based on its current position. Matlab has a detectHarrisFeatures feature, but I believe it is only for 2D mapping.
  
  The approach that I want to try is to collect the information of the lines (using line detection), store them in a histogram, and then see where the lines intersect based on their angles.
  
  My questions are:
  
  > 1. How do I know where the lines intersect?
  > 2. How do I find the angles of the lines using computer vision?
  > 3. How do I update this information based on my coordinates?
  
  I am in the beginning stages of this task, so any guidance is much appreciated!
  
  **Tags:** algorithm, computer-vision, matlab
  
  ---
  
  ## 3 answers
  
  ### Answer by username_1 on 2018-05-28. Score: 1 | Accepted answer
  
  I assume that you are familiar with homogeneous transformations and the meaning of global and local coordinate frames. If not, global frame is the fixed frame; a reference frame for your whole problem, such as the starting position of your robot. Local frame should be placed anywhere on your robot, preferably in the middle-point of the virtual line (called "robot base") that connects the two actuating wheels in the back of your robot (given that you follow the differential drive setup). If not, just place the local frame anywhere that makes sense on the robot, such as its geometrical center.
  Answering your questions:
  
  How do I know where the lines intersect?
  
  The accepted answer in this is by far the best I have seen around, which I have also used successfully for a project regarding robotic exploration in an unknown maze.
  
  How do I find the angles of the lines using computer vision?
  
  You DON'T need computer vision for that. For every line, pick 2 points expressed in global frame (x1,y1),(x2,y2) and calculate the slope of the line as:
  lambda = (y2-y1) / (x2-x1)
  
  Then the angle of the line is atan(lambda), in global frame. Do this for all lines and then subtract the angles of any two lines to find their relative angle (pay attention to the sign).
  Alternatively, I would personally use the RANSAC algorithm to de-noise the detected points and give me the line equation based on the consensus of all points. This line equation should already have the slope in it:
  y = ax + b
  
  where a is the slope and b is the vertical offset. Then do the aforementioned steps, i.e. atan(a) and subtraction to find the relative angle between two lines.
  If you explicitly want to use computer vision, maybe train a neural network on known angles and then classify images of lines to output their angles. This approach will be by far the most painful and I do NOT recommend it at all.
  
  How do I update this information based on my coordinates?
  
  This can be quite tricky. If the line points are detected by your on-board camera, you first of all need to convert them from the camera's coordinate frame (found in the camera's datasheet) to your robot's local frame, as explained above. To do this, you need to calculate the static transformation between the two frames (static because it will never change if the camera is fixed on the robot, you only define it once).
  Then you need to convert the detected line equation from your robot's frame to the global frame. In order to do so, you need to keep track of the robot's pose (position + orientation) while it moves in the 2D or 3D space. This is generally a hard task because it needs an excellent implementation of your localization algorithms, such as an Extended Kalman Filter or Particle Filter. The localization algorithm will provide you with the information that you need at any point in time in order to convert the lines/points from your robot frame to the global frame and visualize them.
  In short: you need to transform the detected lines / points from camera frame -> robot (local) frame -> global frame. The first transformation is static (calculated once and never changes) whereas the second one is dynamic (changes every time the robot moves or turns). The first one is fairly easy to calculate but the second one can be a real pain.
  
  
  ---
  
  ### Answer by username_2 on 2018-05-27. Score: 2
  
  Finding lines in an image often leads to the Hough line transform. Many libraries implement it, including [OpenCV](https://docs.opencv.org/3.4.1/d6/d10/tutorial_py_houghlines.html). Getting the lines should answer subsequent questions (and it doesn't, please consider having one question per post, and some other sites on [StackExchange](https://stackexchange.com/) may be better suited than AI.SE).
  
  Alternative approaches based on Machine Learning may also exist. It may be interesting at this point to look into libraries that do human pose/gait recognition. Some library may be repurposed to recognize the "field gait", assuming the field outer mark is its "gait"-equivalent.
  
  
  ---
  
  ### Answer by username_3 on 2018-05-29. Score: 1
  
  I suggest you first consider your coordinate systems. There are two.
  
  **Field Coordinate Axis**
  
  Field boundary corners are in field coordinates (for example): { (-50.0, -35.0, 0), (50.0, -35.0, 0), (-50.0, -35.0, 0), (50.0, -35.0, 0) }, all values in meters.
  
  At any moment in time the camera in the robot: is at (x, y, z) and oriented relative to north by angle theta, measured clockwise when looking from above the field. The value of z may be 2.0 (for example).
  
  **Image Coordinate Axis**
  
  The coordinate axes of the camera images is (w, h).
  You have frames in time (perhaps every 33 msec containing grids in a the w-h coordinate axis with 1080 x 960 pixels (for example) providing an index range (<0, 1079>, <0, 959>).
  
  **Maintaining Orientation of Short Robots (small Z)**
  
  You are correct that the Harris feature detection may not work because z (the distance from the surface of the field to the center of the camera lens) may not be sufficient for that algorithm unless the robot is near a corner. The rectangle of the field boundary is not at all rectangular in the camera's w-h focal plane. For the same reasons, finding lines and then locating their intersections is not the optimal approach either.
  
  Pretend you are the robot. As the robot survey's the field, it can assemble a model of the 360 degree periphery. What it sees is a gradually curved line with three upside down v shapes representing the field corners. Unless the robot is almost on top of one of the corners, all four features that correspond to the corners of the field boundary will only vaguely appear to be corners at all.
  
  **Mathematics of Obtuse Corner Detection**
  
  Two tangent lines stem from each corner. They intersect at a discontinuity of the line's derivative, dw/dh, the slope in 2D phase space of the camera frame. The angle found between these two tangent lines will usually be closer to 175 degrees than 90 degrees, yet they are still detectable because the rest of line has no other like discontinuities of slope. From a Fourier transform perspective, the 360 degree line is actually a periodic waveform primarily comprised of the 4th, 12th, 20th, 28th, and 36th harmonics. If you are good with that level of mathematics and you record past frames, you can exploit Fourier's series and FFTs for high accuracy in corner detection.
  
  As you develop your theory and your software, you may find that other aspects of play need to be considered. It may be best to think of those aspects now. Fortunately, if another player or official blocks a portion of the field's boundary line, it will create a discontinuity in the line itself, but not the slope of the line in the w-h plane of the camera's image. Your implementation will need to differentiate those two types of differences, which is hardly an insurmountable problem. Discontinuity in a line and discontinuity in its derivative are mathematically distinct naturally.
  
  **Redundancy in Feedback Channels**
  
  If the robot can sense its location and orientation in other ways and know x, y, z, and theta above with some degree of reliability, the expected location of the obtuse angles and the detected ones can be compared to determine the probability that the robot is properly detecting is orientation.
  
  **Questions in This Context**
  
  In this context the questions you listed need some reorientation.
  
  **How do I know where the lines intersect?**
  
  The line has two edges that may lie on the same pixel in many cases, so that is not easy to detect in an image with many other lines. If the line is of a particular color, hue detection can assist in line detection. If the above corroborative data analysis is employed, then misinterpretation of edges can be corrected quickly in real time. Once the lines are found, the detection of dh/dw at any given point on the line can be estimated using linear regression of segments and windowing (looking at short segments one at a time). When an otherwise relatively stable slope quickly shifts 5 or 10 degrees in angle between windows, you have a high probability that you've found a distant field corner. A shift in 70 to 80 degrees combined with a lower h value in the frame is indicative of a corner in close proximity.
  
  **How do I find the angles of the lines using computer vision?**
  
  Edge detection, systematic elimination of candidate edges that are not likely field boundaries, and then linear regression of the best candidates.
  
  **How do I update this information based on my coordinates?**
  
  Just save them in an appropriate array of x, y, z, theta vectors, indexed by frame number. You will probably want to keep track of what you think your robot's x, y, z, and theta values are and constantly test your assumptions against your most recent inputs. Otherwise, your robot can become disoriented. The more ways you can detect location and orientation, the higher reliability you will have in the overall system. If your vision can detect some feature at each goal that will not change during the game, it may help. Ultimately your x, y, z, and theta are the parameters in a model and the use of gradient descent and auto-correlation and other auto-correction techniques need to be applied to keep your robot's orientation model continuously updated.
  
  **Recommend Diving Into the Math First**
  
  The 3D trig to work all of the above out in detail is initially daunting but not that far beyond high school trig if the researcher develops some clear diagrams first and then takes the time to resurrect any rusty mathematics skills or hone some new ones.
  
  
  ---
  
  