Stroke detection and shape strokes in C #

Question

I need to find the stroke and wrap around this shape

my code finds a circle but the wrong inner circle

for (int r = 1; ; r++) //r is radius { int found = 0; //counts found pixels int wrong = 0; //counts pixels that are on the circle but have different color that desirable int good = 0; //counts pixels that are on the circle with desirable color for (int y = point.Y - r ; y <= point.Y + r ; y++) //point is the center of the figure (110,110) { for (int x = point.X - r ; x <= point.X + r; x++) { if((x - point.X) * (x - point.X) + (y - point.Y)*(y - point.Y) == r*r) //is on the circle { found++; if (img.GetPixel(x, y).ToArgb() != color.ToArgb()) // has given color (black) { wrong++; } else { good++; } } } } outerRadius = r; if (found == wrong) break; //circumcircle found if (found == good) innerRadius = r; //incircle found } 

As a result, I get the following: (red circle, blue color)

I can not find why this is not working. Please help me.

Answer 1

The main problem is that you assume that the points that "on" have all the mathematical points have the correct distance from the center of the circle.

In truth, they will not, they will have a small distance inside or outside, since the pixels are on a fixed grid and the circle has infinite resolution.

This means that at each iteration there will be only a few pixels, which will be calculated as an "on" circle, and thus found will never count all the pixels of the circle.

I understand the premise of your algorithm, but you need to find out if you found one of the pixels in the circle differently, which will take into account the slight differences between the pixel grid and the optimal location of the circle.

Also, if you only do this for a particular type of form, why not just do it mathematically? A circle is easily calculated, the radius of which is equal to the distance from the center to one of the corners, and the inner circle is the distance from the center to the center of one of the edges.

If you need to do this for random shapes, then this will not work, but then you have another problem, where do you place the center?

Here I can illustrate:

Here I illustrated a circle with a radius of 4. A yellow pixel is the center, red is the one that falls exactly in a circle, mathematically according to your formula. There are 2 extra outside images.

However, two green problems.

For A, which has X = -1 (1 to the left of) the center, and Y = -4 (4 above the center), your formula ends as:

 (-1)*(-1) + (-4)*(-4) == 4*4 1 + 16 == 16 17 == 16 

For B, which is slightly inside, has Y = -3:

 (-1)*(-1) + (-3)*(-3) == 4*4 1 + 9 == 16 10 == 16 

So, as you can see, your approach to finding all the pixels that make up a circle is wrong. In fact, most likely you find only four pixels directly up, down, left or right, and sometimes an odd pixel here and there.

At least I would modify the circle search algorithm using the Bresenham Circle Algorithm or Midpoint Circle Algorithm:

 IEnumerable<Point> MidpointCirclePoints(int x0, int y0, int radius) { int x = radius; int y = 0; int radiusError = 1 - x; while (x >= y) { yield return new Point(x + x0, y + y0); yield return new Point(y + x0, x + y0); yield return new Point(-x + x0, y + y0); yield return new Point(-y + x0, x + y0); yield return new Point(-x + x0, -y + y0); yield return new Point(-y + x0, -x + y0); yield return new Point(x + x0, -y + y0); yield return new Point(y + x0, -x + y0); y++; if (radiusError < 0) radiusError += 2 * y + 1; else { x--; radiusError += 2 * (y - x) + 1; } } } 

This will find all the points that are on the circle for everyone, but note that some points can be returned twice, in particular in the right, lower, left and left pixels, as well as every 45 degrees.

But again, please note that your algorithm will not work correctly for a random pixel of pixels, since you will not be able to correctly position the center, this will only work with a strictly symmetrical shape

Here is a complete working example that you can try in LINQPad :

 void Main() { int size = 256; int radius = 110; // of the square, not of the circles var b = new Bitmap(size, size); using (Graphics g = Graphics.FromImage(b)) { g.Clear(Color.White); g.FillPolygon(Brushes.Black, new[] { new Point(size / 2, size / 2 - radius), new Point(size / 2 + radius, size / 2), new Point(size / 2, size / 2 + radius), new Point(size / 2 - radius, size / 2) }); } int incircleRadius; int circumcircleRadius; if (FindCircles(b, out incircleRadius, out circumcircleRadius)) { using (Graphics g = Graphics.FromImage(b)) { g.DrawEllipse(Pens.Red, new Rectangle( size / 2 - circumcircleRadius, size / 2 - circumcircleRadius, circumcircleRadius * 2 + 1, circumcircleRadius * 2 + 1)); g.DrawEllipse(Pens.Blue, new Rectangle( size / 2 - incircleRadius, size / 2 - incircleRadius, incircleRadius * 2 + 1, incircleRadius * 2 + 1)); } } b.Dump(); } bool FindCircles(Bitmap input, out int incircleRadius, out int circumcircleRadius) { int midX = input.Width / 2; // already we're introducing inaccuracies int midY = input.Height / 2; // what if the bitmap is an even number? int largestPossibleRadius = Math.Min(midX, midY); incircleRadius = 0; circumcircleRadius = 0; for (int r = 30; r < largestPossibleRadius; r++) { bool allBlack = true; bool allWhite = true; // Bresenhams Circle Algorithm foreach (Point p in MidpointCirclePoints(midX, midY, r)) { // input.GetPixel(pX, pY).R.Dump(); bool isBlack = input.GetPixel(pX, pY).R < 128; // dummy test if (isBlack) { // input.SetPixel(pX, pY, Color.Green); allWhite = false; } else { // input.SetPixel(pX, pY, Color.Green); allBlack = false; } // Debug // input.SetPixel(pX, pY, Color.Green); } if (allBlack) { incircleRadius = r; } else if (allWhite) { circumcircleRadius = r - 1; break; } } return incircleRadius > 0 && circumcircleRadius > 0;; } IEnumerable<Point> MidpointCirclePoints(int x0, int y0, int radius) { int x = radius; int y = 0; int radiusError = 1 - x; while (x >= y) { yield return new Point(x + x0, y + y0); yield return new Point(y + x0, x + y0); yield return new Point(-x + x0, y + y0); yield return new Point(-y + x0, x + y0); yield return new Point(-x + x0, -y + y0); yield return new Point(-y + x0, -x + y0); yield return new Point(x + x0, -y + y0); yield return new Point(y + x0, -x + y0); y++; if (radiusError < 0) radiusError += 2 * y + 1; else { x--; radiusError += 2 * (y - x) + 1; } } } 

Output:

Answer 2

I would suggest that your algorithm continues the search. It seems that when he finds a black pixel, he assumes that he is "good" for the inscribed circle. In your case, I think that it ends up constantly hitting black pixels at the corners of the rectangle up to the radius described.

Indeed, as soon as you find a white pixel, the last good value for the inscribed should be the one you take. I have not tested this, but I think this will work, or at least help you solve the problem:

 bool isStillInscribed = true; int inscribedCircleRadius = 0; for (int r = 1; ; r++) //r is radius { int found = 0; //counts found pixels int wrong = 0; //counts pixels that are on the circle but have different color that desirable for (int y = point.Y - r ; y <= point.Y + r ; y++) //point is the center of the figure (110,110) { for (int x = point.X - r ; x <= point.X + r; x++) { if((x - point.X) * (x - point.X) + (y - point.Y)*(y - point.Y) == r*r) //is on the circle { found++; if (img.GetPixel(x, y).ToArgb() != color.ToArgb()) // has given color (black) { wrong++; //we are now outside the shape; cannot be inscribed anymore isStillInscribed = false; } } } } //if the last checked circle radius still did not find any different //coloured pixels, then this radius is still inscribed if (isStillInscribed) inscribedCircleRadius = r; outerRadius = r; if (found == wrong) break; //circumcircle found }