Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>If you're writing your own library, then creating a robust solution for this problem will allow you to develop several independent chunks of code that you can string together to solve other problems, too. I'll assume that you want to find the corners of the checkerboard under arbitrary rotation, under varying lighting conditions, in the presence of image noise, with a little nonlinear pincushion/barrel distortion, and so on.</p> <p>Although there are simple kernel-based techniques to find whole pixels as edge pixels, when working with filled polygons you'll want to favor algorithms that can find edges with sub-pixel accuracy so that you can perform accurate line fits. Even though the gradient from dark square to white square crosses several pixels, the "true" edge will be found at some sub-pixel point, and very likely not the point you'd guess by manually clicking. </p> <p>I tried to provide a simple summary of edge finding in this older SO post: <a href="https://stackoverflow.com/questions/8836933/what-is-the-relationship-between-image-edges-and-gradient/8873576#8873576">what is the relationship between image edges and gradient?</a></p> <p>For problems like yours, a robust solution is to find edge points along the dark-to-light transitions with sub-pixel accuracy, then fit lines to the edge points, and use the line angles. If you are processing a true camera image, and if there is an uncorrected radial distortion in the image, then there are some potential problems with measurement accuracy, but we'll ignore those.</p> <p>If you want to find an accurate fit for an edge, then it'd be great to scan for sub-pixel edges in a direction perpendicular to that edge. That presupposes that we have some reasonable estimate of the edge direction to begin with. We can first find a rough estimate of the edge orientation, then perform an accurate line fit.</p> <p>The algorithm below may appear to have too many steps, but my purpose is point out how to provide a robust solution.</p> <ol> <li>Perform a few iterations of erosion on black pixels to separate the black boxes from one another.</li> <li>Run a connected components algorithm (blob-finding algorithm) to find the eroded black squares.</li> <li>Identify the center (x,y) point of each eroded square as well as the (x,y) end points defining the major and minor axes.</li> <li>Maintain the data for each square in a structure that has the total area in pixels, the center (x,y) point, the (x,y) points of the major and minor axes, etc.</li> <li>As needed, eliminate all components (blobs) that are too small. For example, you would want to exclude all "salt and pepper" noise blobs. You might also temporarily ignore checkboard squares that are cut off by the image edges--we can return to those later.</li> </ol> <p>Then you'll loop through your list of blobs and do the following for each blob:</p> <ol start="7"> <li>Determine the direction roughly perpendicular to the edges of the checkerboard square. How you accomplish this depends in part on what data you calculate when you run your connected components algorithm. In a general-purpose image processing library, a standard connected components algorithm will determine dozens of properties and measurements for each individual blob: area, roundness, major axis direction, minor axis direction, end points of the major and minor axis, etc. For rectangular figures, it can be sufficient to calculate the topmost, leftmost, rightmost, and bottommost points, as these will define the four corners.</li> <li>Generate edge scans in the direction roughly perpendicular to the edges. These must be performed on the <strong>original, unmodified</strong> image. This generally assumes you have bilinear interpolation implemented to find the grayscale values of sub-pixel (x,y) points such as (100.35, 25.72) since your scan lines won't fall exactly on whole pixels.</li> <li>Use a sub-pixel edge point finding technique. In general, you'll perform a curve fit to the edge points in the direction of the scan, then find the real-valued (x,y) point at maximum gradient. That's the edge point.</li> <li>Store all sub-pixel edge points in a list/array/collection.</li> <li>Generate line fits for the edge points. These can use Hough, RANSAC, least squares, or other techniques.</li> <li>From the line equations for each of your four line fits, calculate the line angle.</li> </ol> <p>That algorithm finds the angles independently for each black checkerboard square. It may be overkill for this one application, but if you're developing a library maybe it'll give you some ideas about what sub-algorithms to implement and how to structure them. For example, the algorithm would rely on implementations of these techniques:</p> <ul> <li>Image morphology (e.g. erode, dilate, close, open, ...)</li> <li>Kernel operations to implement morphology</li> <li>Thresholding to binarize an image -- the Otsu method is worth checking out</li> <li>Connected components algorithm (a.k.a blob finding, or the OpenCV contours function)</li> <li>Data structure for blob</li> <li>Moment calculations for blob data</li> <li>Bilinear interpolation to find sub-pixel (x,y) values</li> <li>A linear ray-scanning technique to find (x,y) gray values along a specific direction (which will also rely on bilinear interpolation)</li> <li>A curve fitting technique and means to determine steepest tangent to find edge points</li> <li>Robust line fit technique: Hough, RANSAC, and/or least squares</li> <li>Data structure for line equation, related functions</li> </ul> <p>All that said, if you're willing to settle for a slight loss of accuracy, and if you know that the image does not suffer from radial distortion, etc., and if you just need to find the angle of the parallel lines defined by all checkboard edges, then you might try..</p> <ol> <li>Simple kernel-based edge point finding technique (Laplacian on Gaussian-smoothed image)</li> <li>Hough line fit to edge points</li> <li>Choose the two line fits with the greatest number of votes, which should be one set of horizontal-ish lines and the other set of vertical-ish lines</li> </ol> <p>There are also other techniques that are less accurate but easier to implement:</p> <ol> <li>Use a kernel-based corner-finding operator</li> <li>Find the angles between corner points.</li> </ol> <p>And so on and so on. As you're developing your library and creating robust implementations of standalone functions that you can string together to create application-specific solutions, you're likely to find that robust solutions rely on more steps than you would have guessed, but it'll also be more clear what the failure mode will be at each incremental step, and how to address that failure mode.</p>
    singulars
    1. This table or related slice is empty.
    1. POEdge detection / angle
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USCommunity
    1. USRethunk
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POEdge detection / angle
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COVery nice answer. So basically, find the steepest gradient in the edge spread function and that is the most accurate place to calculate the angle? And for sub pixel accuracy, I should interpolate the edge spread function to find the true steepest gradient?
      singulars
      1. PO
      1. USillumi
    2. COThere are a number of different ways to find the steepest gradient. A number of curve-fitting techniques will work, such as cubic splines. Once you have a curve you can find the gradient. (It's been a while since I've had to code this, but that's what I recall.) Given a choice between various curve-fitting techniques, choose the one that is simpler and that you can debug. Even if a more complicated algorithm gives "better" fit results, noise of all sorts--lighting, shadows, etc.--tend to limit edge-finding accuracy to about 1/4 pixel in the real world. That's plenty good.
      singulars
      1. PO
      1. USRethunk
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload