AForge.NET

  :: AForge.NET Framework :: Articles :: Forums ::

Minimum bounding rectangle?

Forum to discuss AForge.NET Framework, its features, API, how-tos, etc.

Minimum bounding rectangle?

Postby JuKu » Tue Nov 13, 2018 1:32 pm

Ok, I need _minimum_ bounding rectangle for my blobs. This is different than basic bounding rectangle; please see http://www.datagenetics.com/blog/march12014/index.html. At the end of the page a video game application is shown, illustrating the difference. (I'm not building a game, just trying to find the size and orientation of objects).

A: Has anyone implemented this already?

B: If not, I think the following would be the way to go. If you have better ideas, I'd like to hear them. Also, if you have hints, there are functions I've missed in the framework etc, I would be happy to receive pointers. The basic idea is simple, called caliber algorithm, described in the above link. So:

- Find convex hull of the blob. Easy enough, http://www.aforgenet.com/framework/features/blobs_processing.html.
- For each hull outline segment:
--Rotate the outline so that the segment is horizontal. (Does this routine exist?)
-- Find the bounding rectangle of the rotated blob (GetBoundingRectangle method).
-- Calculate the area of the rectangle.

The minimum rectangle is the rectangle that gives the smallest area, the orientation is the rotation of the blob.

Although not simple, but this sounds doable. I think this will take me a few days to get right. Before I start spending those, I'd like to double check with you if you see easier ways, have done all or some of this already, warn me about things to be careful about etc. I already see an issue about rotation origins: Of course, the bounding rectangle needs to be around the object, not just right size and tilt.

Any replies are greatly appreciated!
JuKu
 
Posts: 16
Joined: Wed Nov 13, 2013 10:44 am

Re: Minimum bounding rectangle?

Postby JuKu » Thu Nov 22, 2018 12:10 pm

Ok, no takers, so I built it myself. Here is a slightly tested version, seems to work ok. Input is blob's convex hull, see GetBlobsOutline() and GetConvexHull().
Code: Select all
        private List<IntPoint> GetMinimumBoundingRectangle(List<IntPoint> Outline)
        {
            // Using caliber algorithm to find the minimum bounding regtangle
            // (see http://www.datagenetics.com/blog/march12014/index.html):

            // For each line segment,
            // Rotate the hull so that the segment is horizontal.
            // Get the hull bounding rectangle
            // Measure the area
            // If first iteration or the area is smaller than the previous one,
            // store the area, the rectangle and the rotation with point
            // The solution is the stored rectangle, rotated back to original orientation.

            bool first = true;
            IntPoint minXY = new IntPoint();
            IntPoint maxXY = new IntPoint();
            double SmallestArea = 0;
            double AngleOfsolution = 0;
            IntPoint SolutionMin = new IntPoint();
            IntPoint SolutionMax = new IntPoint();
            IntPoint SolutionOrg = new IntPoint();

            for (int i = 1; i < Outline.Count; i++) // For each line segment,
            {
                double angle = GetAngle(Outline[i - 1], Outline[i]);
                List<IntPoint> RotatedOutline = RotateOutline(-angle, Outline, Outline[i - 1]); // Rotate the hull so that the segment is horizontal.
                PointsCloud.GetBoundingRectangle(RotatedOutline, out minXY, out maxXY);    // Get the hull bounding rectangle
                double area = RectangleArea(minXY, maxXY);
                if (first || (area < SmallestArea))
                {
                    SmallestArea = area;        // store the area, the rectangle and the rotation
                    AngleOfsolution = angle;
                    SolutionMin = minXY;
                    SolutionMax = maxXY;
                    SolutionOrg = Outline[i - 1];
                    first = false;
                }
            }
            List<IntPoint> rect = new List<IntPoint>() { SolutionMin, new IntPoint(SolutionMax.X, SolutionMin.Y),
                SolutionMax ,new IntPoint(SolutionMin.X, SolutionMax.Y) };
            rect = RotateOutline(AngleOfsolution, rect, SolutionOrg); // stored rectangle, rotated back to original orientation and place
            return rect;
        }

        // ===========
        private IntPoint RotatePoint(double angle, IntPoint p, IntPoint o)
        {
            // If you rotate point (px, py) around point (ox, oy) by angle theta you'll get:
            // p'x = cos(theta) * (px-ox) - sin(theta) * (py-oy) + ox
            // p'y = sin(theta) * (px-ox) + cos(theta) * (py-oy) + oy

            double theta = angle * (Math.PI / 180.0); // to radians
            IntPoint Pout = new IntPoint();
            Pout.X = Convert.ToInt32(Math.Cos(theta) * (p.X - o.X) - Math.Sin(theta) * (p.Y - o.Y) + o.X);
            Pout.Y = Convert.ToInt32(Math.Sin(theta) * (p.X - o.X) + Math.Cos(theta) * (p.Y - o.Y) + o.Y);
            return Pout;
        }

         // ===========
       private List<IntPoint> RotateOutline(double theta, List<IntPoint> Outline, IntPoint RotOrigin)
        {
            // returns the outline, rotated by angle around RotOrigin
            List<IntPoint> Result = new List<IntPoint>();
            IntPoint Pout = new IntPoint();
            foreach (var p in Outline)
            {
                Pout = RotatePoint(theta, p, RotOrigin);
                Result.Add(Pout);
            }
            return Result;
        }

        // ===========
        private double RectangleArea(IntPoint p1, IntPoint p2)
        {
            return Math.Abs(((double)p2.X - (double)p1.X) * ((double)p2.Y - (double)p1.Y));
        }

       // ===========
        private double GetAngle(IntPoint p1, IntPoint p2)
        {
            // returns the angle between line (p1,p2) and horizontal axis, in degrees
            double A = 0;
            if (p2.X == p1.X)
            {
                if (p2.Y > p1.Y)
                {
                    return 90;
                }
                else
                {
                    return 270;
                }
            }
            else
            {
                A = Math.Atan(Math.Abs((double)(p1.Y - p2.Y) / (double)(p1.X - p2.X)));
                A = A * 180.0 / Math.PI; // in deg.
            }
            // quadrants: A is now first quadrant solution
            if ((p1.X < p2.X) && (p1.Y <= p2.Y))
            {
                return A;   // 1st q.
            }
            else if ((p1.X > p2.X) && (p1.Y < p2.Y))
            {
                return A + 90; // 2nd q.
            }
            else if ((p1.X > p2.X) && (p1.Y >= p2.Y))
            {
                return A + 180; // 3rd q.
            }
            else
            {
                return 360 - A; // 4th q.
            }
        }

 
JuKu
 
Posts: 16
Joined: Wed Nov 13, 2013 10:44 am




Return to AForge.NET Framework

cron