koobas.hobune.stream
Find corners/edges on a shape using own implementation
I'm trying to get the corners of the following shape:
By corners I mean this (red dots):
The minimum quantity of points that can define this shape.
And I have implemented the following:
public Shape Optimize()
{
// If the vertices are null or empty this can't be executed
if (vertices.IsNullOrEmpty())
return this; // In this case, return the same instance.
if (!edges.IsNullOrEmpty())
edges = null; //Reset edges, because a recalculation was requested
// The corners available on each iteration
var corners = new Point[] { Point.upperLeft, Point.upperRight, Point.downLeft, Point.downRight };
//The idea is to know if any of the following or previous vertice is inside of the the array from upside, if it is true then we can add it.
Point[] vs = vertices.ToArray();
for (int i = 0; i < vertices.Count - 1; ++i)
{
Point backPos = i > 0 ? vs[i - 1] : vs[vertices.Count - 1],
curPos = vs[i], //Punto actual
nextPos = i < vertices.Count - 1 ? vs[i + 1] : vs[0];
// We get the difference point between the actual point and the back & next point
Point backDiff = backPos - curPos,
nextDiff = nextPos - curPos,
totalDiff = nextPos - backPos;
if (corners.Contains(backDiff) || corners.Contains(nextDiff) || corners.Contains(totalDiff))
AddEdge(curPos, center); // If any of the two points are defined in the corners of the point of before or after it means that the actual vertice is a edge/corner
}
return this;
}
This works rectangled shapes, but rotated shapes are very sharp, so, this code doesn't work well:
Blue pixels (in this photo and the following) are the
verticesvariable processed onOptimizemethod.Green pixels are the detected corners/edges (on both photos).
But sharpness in a shape only defines the side inclination, so what can I do to improve this?
Also, I have tested Accord.NET BaseCornersDetector inherited classes, but the best result is obtained with HarrisCornersDetector, but:
Many edges/corners are innecesary, and they aren't in the needed place (see first photo).
Well, after hours of research I found a library called Simplify.NET that internally runs the Ramer–Douglas–Peucker algorithm.
Also, you maybe interested on the Bresenham algorithm, with this algorithm you can draw a line using two Points.
With this algorithm, you can check if your tolerance is too high, comparing the actual points and the points that this algorithm outputs and making some kind of percentage calculator of similarity.
Finally, is interesting to mention Concave Hull and Convex Hull algorithms.
All this is related to Unity3D.
My outputs:
And my implementation.
It's very important to say, that points needs to be sorted forcing them to be sorted. If the shape is concave as you can see on the second photo maybe you need to iterate walls of the shape.
You can see an example of implementation here. Thanks to @Bunny83.
Also answered here: https://stackoverflow.com/a/52952874/3286975
Thanks Bunny83 for guide me !! :)
This is a quite difficult task as the exact points completely depends on the way the edges of the shape are drawn. They are probably drawn with the popular Bresenham algorithm. However to exactly reproduce a certain pattern in many cases you have to pick the exact right corner points for that line. If it's just one pixel off it won't match the pattern. Analysing a shape like this becomes extremely difficult. If you're happy with a good approximation you may try to first group the border point into straight line segments. Next you try to combine consecutive line segments if their direction angle is "about" the same. As soon as a line segment has a direction that is too far from the original angle you will start a new line segment and basically have found a "necessary" corner. This approach does not necessarily reproduce the exact same shape but it should be a very close approximation depending on how large you set the angle threshold.
Once you found your corners you could re-run bresenham between your corners to see if it fits or not. However the main question is what you do if it doesn't match ^^.
Thanks again for your answer Bunny83. I have implemented this algorithm in a fiddle so every body can see it: https://dotnetfiddle.net/aPOhPi but I don't make it work. I will do some research about your algorithm. :P
Just for detecting the outer bounds of a shape i've written a simple straight forward implementation over here. It just deter$$anonymous$$es all border pixels of a shape in the right order. Though it has some limitations in order to avoid issues with connected shapes it enforces a gap of 1 pixel between shapes. When removing a shape from the source image i just remove a 1 pixel border around it. Of course this question was about finding the outline of a shape, not a filled shape.
The actual concrete implementation i've posted in the comments below my answer. The code is on pastebin and the webgl live example is on github pages.
Though as i said reducing the number of points is not trivial and you can't guarantee a certain solution is the best one unless you literally tested all possible combinations (and for a shape like yours this would take ages).
Damn, I just realised the question i just mentioned was your own question x)
I think on the following logic.
The first point of my shape will always be a corner.
Following this, we will get the slope of the following points and we will add them to a global mean.
If the global mean changes drastically, we will suppose that the previous point to the actual is a corner.
What do you think?
Actually i wouldn't constrain myself to assume the first point is a corner ^^. What you could do is calculate a "bresenham error score" based on all points in between two (potential) corner points. As long as this error score stays within a certain threshold we can just move either the start or end point further to the next point on the shape border. The error score should ensure to get a clear indication when the line goes too much off the trail. With the bresenham algorithm all points / pixels should never have a greater distance from our actual (mathematical) line than "0.5". To calculate an error score you may multiply the measured distance from each point to the line by 2 so we get an error between 0-1 if it's in the "good" range and a value greater than 1 if it's in the "bad" range. Now we can apply a power to that error (probably a higher power like 4 or 8). This will amplify the error greater than 1 and also reduce the error if smaller than 1. Sum up the error score of all points between start and end and divide by the number of points. This score if we get a perfect fit should stay below 1 and would be 0 for an exact fit (only happens for horizontal, vertical or diagonal lines). Now you can just try moving the ends of a line segment outwards and if the score is still within a certain threshold you keep going. However if moving to the next point skyrockets the error you essentially have found a corner. Though it all depends on what threshold you set and how greate the tolerance for errors can be.
So, what you mean, is that I have to create a segment where (x1, y1) = actual point && (x2, y2) is the last corner. And compare it's slope with the slope of the previous point (where (x1, y1) = actual point - 1), if the actual slope is different from current slope we can define the previous point as a corner?
