{"id":11201,"date":"2019-12-13T09:00:25","date_gmt":"2019-12-13T14:00:25","guid":{"rendered":"https:\/\/blogs.mathworks.com\/pick\/?p=11201"},"modified":"2020-06-25T09:23:58","modified_gmt":"2020-06-25T13:23:58","slug":"minimally-bounded-rectangles-and-more","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/pick\/2019\/12\/13\/minimally-bounded-rectangles-and-more\/","title":{"rendered":"Minimally Bounded Rectangles, and more!"},"content":{"rendered":"
<\/p>\n

Brett<\/a>‘s Pick this week is A suite of minimal bounding objects<\/tt><\/a>, by John D’Errico<\/a>. I also give a shout-out to julien diener<\/a>, for his 2D minimal bounding box<\/a> function.<\/p>\n

<\/p>\n

During the course of developing some code to automatically track objects in videos, I found that I needed to create a “minimal bounding rectangle” to enclose detected points. There is a very nice demo<\/a> in the Computer Vision Toolbox in which points used to track a moving face are delineated by a polygon<\/i> created by the polyshape<\/tt><\/a> command. All well and good; it works nicely, and is very fast. But for other reasons, I preferred to work with an ‘images.roi.Rectangle’ object, as created by the drawrectangle<\/tt><\/a> command (which is itself a convenience function for rectangle()<\/tt><\/a>.)<\/p>\n

A modified version of the aforementioned example looks like this:<\/p>\n

vidObj = VideoReader('tilted_face.avi'<\/span>);\r\nvideoFrame = readFrame(vidObj);\r\ntogglefig('Face Tracker'<\/span>)\r\nimgH = imshow(videoFrame);\r\nfaceDetector = vision.CascadeObjectDetector();\r\nbbox = faceDetector(videoFrame);\r\nbboxPoints = bbox2points(bbox(1, :));\r\nthisPoly = polyshape(bboxPoints);\r\nhold on<\/span>\r\npolyH = plot(thisPoly, 'FaceAlpha'<\/span>, 0, 'EdgeColor'<\/span>, 'y'<\/span>, 'LineWidth'<\/span>, 2);\r\npoints = detectMinEigenFeatures(rgb2gray(videoFrame), 'ROI'<\/span>, bbox);\r\npointTracker = vision.PointTracker('MaxBidirectionalError'<\/span>, 2);\r\npoints = points.Location;\r\ninitialize(pointTracker, points, videoFrame);\r\noldPoints = points;\r\ntic;\r\nwhile<\/span> hasFrame(vidObj)\r\n    % Get the next frame, update the visualization:<\/span>\r\n    videoFrame = readFrame(vidObj);\r\n    imgH.CData = videoFrame;\r\n    % Track the points. Note that some points may be lost.<\/span>\r\n    [points, isFound] = pointTracker(videoFrame);\r\n    visiblePoints = points(isFound, :);\r\n    oldInliers = oldPoints(isFound, :);\r\n    if<\/span> size(visiblePoints, 1) >= 2 % need at least 2 points<\/span>\r\n        [xform, oldInliers, visiblePoints] = estimateGeometricTransform(...<\/span>\r\n            oldInliers, visiblePoints, 'similarity'<\/span>, 'MaxDistance'<\/span>, 4);\r\n        bboxPoints = transformPointsForward(xform, bboxPoints);\r\n        thisPoly = polyshape(bboxPoints);\r\n        polyH.Shape = thisPoly;\r\n        oldPoints = visiblePoints;\r\n        setPoints(pointTracker, oldPoints);\r\n    end<\/span>\r\n    imgH.CData = videoFrame;\r\n    drawnow\r\nend<\/span>\r\nt = toc;\r\n% Clean up<\/span>\r\nrelease(pointTracker);\r\n\r\n% (Processing the while loop takes about 6.5 seconds on my laptop.)<\/span>\r\n 
\"\" <\/p>
But how would one replace the polygon with a rotated rectangle? Fortunately for us, there's the File Exchange, where a search for \"minimal bounding rectangle\" quickly turned up John's \"suite\" of functions for minimally bounding circles, spheres, parallelograms, quadrilaterals, semicircles, triangles, and rectangles.<\/p>
As we've come to expect, John's functions are well written and commented. It was a simple matter to replace the polygon with a minimally bounded rectangle, which not surprisingly computes the convex hull of the input points. One note: John's function returned the x-<\/i> and y-<\/i> coordinates of the target rectangle, and the area and perimeter of the same:<\/p>
[rectx,recty,area,perimeter] = minboundrect(x,y,metric)\r\n<\/pre>\n
(In fact, one can elect, using the 'metric' parameter, to minimize by area or perimeter, with area being the default.) I needed the rotation angle<\/i> of the triangle, to use as an input in drawrectangle<\/tt>. It took a moment to modify minboundrect<\/tt> to return as an additional output the edgeangles<\/i> parameter, which is computed internally. In moments, we had:<\/p>\n
vidObj.CurrentTime = 0; % Reset and reuse the VideoReader object<\/span>\r\nvideoFrame = readFrame(vidObj);\r\n%togglefig('Face Tracker', true) %Clear and reuse figure<\/span>\r\n%imgH = imshow(videoFrame);<\/span>\r\nbbox = faceDetector(videoFrame);\r\n% hRect = drawrectangle('Position', bbox, ...<\/span>\r\n%     'FaceAlpha', 0, 'Color', 'y', 'LineWidth', 2);<\/span>\r\nbboxPoints = bbox2points(bbox(1, :));\r\npoints = detectMinEigenFeatures(rgb2gray(videoFrame), 'ROI'<\/span>, bbox);\r\npointTracker = vision.PointTracker('MaxBidirectionalError'<\/span>, 2);\r\npoints = points.Location;\r\ninitialize(pointTracker, points, videoFrame);\r\noldPoints = points;\r\ntic;\r\nwhile<\/span> hasFrame(vidObj)\r\n    % Get the next frame, update the visualization:<\/span>\r\n    videoFrame = readFrame(vidObj);\r\n%     imgH.CData = videoFrame;<\/span>\r\n    % Track the points. Note that some points may be lost.<\/span>\r\n    [points, isFound] = pointTracker(videoFrame);\r\n    visiblePoints = points(isFound, :);\r\n    oldInliers = oldPoints(isFound, :);\r\n    if<\/span> size(visiblePoints, 1) >= 2 % need at least 2 points<\/span>\r\n        [xform, oldInliers, visiblePoints] = estimateGeometricTransform(...<\/span>\r\n            oldInliers, visiblePoints, 'similarity'<\/span>, 'MaxDistance'<\/span>, 4);\r\n        bboxPoints = double(transformPointsForward(xform, bboxPoints));\r\n        % |vertToPos| is a helper function I wrote; it is the inverter for<\/span>\r\n        % <https:\/\/www.mathworks.com\/help\/vision\/ref\/bbox2points.html |bbox2points|>.<\/span>\r\n        test = 'john'<\/span>;\r\n        switch<\/span> test\r\n            case<\/span> 'john'<\/span>\r\n                [rectx, recty, theta] = ...<\/span>\r\n                    minboundrect(bboxPoints(:,1), bboxPoints(:,2));\r\n                rectPos = vertToPos([rectx, recty]);\r\n            case<\/span> 'julien'<\/span>\r\n                [rect, theta] = minBoundingBox(bboxPoints');\r\n                rectPos = vertToPos(rect');\r\n        end<\/span>\r\n        theta = 360-rad2deg(theta(1));\r\n        hRect.Position = rectPos;\r\n        hRect.RotationAngle = theta;\r\n        oldPoints = visiblePoints;\r\n        setPoints(pointTracker, oldPoints);\r\n    end<\/span>\r\n%     imgH.CData = videoFrame;<\/span>\r\n    drawnow\r\nend<\/span>\r\nt = toc;\r\n% Clean up<\/span>\r\nrelease(pointTracker);\r\n<\/pre>\n
Looping over all the video frames took 8.3 seconds; minboundrect<\/tt> added about 4 msec per frame overhead. (Not bad!).<\/p>\n
As a side note, I also found my way to (and tested--see the switch-case in the code above) julien's '2D minimal bounding box' contribution. julien (who apparently eschews capitalization) wrote that his code is \"fully vectorized,\" and thus \"is better for big set of points.\" I didn't test the difference on a large dataset, but for my use case, I could detect no performance difference. Very nice, gentlemen--thank you both!<\/p>\n
As always, I welcome your thoughts and comments<\/a>.<\/p>\n