Convex Hull Area in Pixels

Question

I am calculating different attributes for connected regions of the image, with the final goal of classification. One of the attributes I am working with is a sparsity measure, calculated as the ratio of the area of the region (in pixels) and the area of the region's convex hull.

For now, I am doing this with OpenCV:

std::vector <cv::Point2f> region;
std::vector <cv::Point2f> convex_hull;
// fill the region ...
cv::convexHull(cv::Mat(region), convex_hull, false);

double ratio = (double)(region.size()) / std::abs(cv::contourArea(convex_hull));

The problems with this approach is that pixels are considered to have an area of 1 when calculating the region area, but are treated as points in convex hull calculation, causing disparity. An example would be a 4-pixel rectangle with the pixels coordinates ((1,1), (1,2), (2,1), (2,2)). Convex hull contains the same 4 points. But, the area of the region is calculated as 4 (counting the pixels), and the convex hull area as 1 (a 1x1 rectangle with corners in (1,1), (1,2), (2,1), (2,2)).

Can anybody suggest a way to compute these two areas in the same way, so that the range of my sparsity measure is in fact [0,1] and the region area never gets calculated as larger than convex hull area?

Answer 1

It is known that OpenCV contours are not useful for quantification. For example this issue was closed without any changes, not even to the documentation. I have also seen multiple questions on Stack Overflow related to this issue, which affects not only area measurements but also moment measurements.

The problem is that the contour is a polygon that joins the centers of the boundary pixels, and consequently is half a pixel off from the expected location of the boundary. The area of the polygon is off by approximately half its perimeter (depending on shape, so you can’t use this to correct for the bias).

In the DIPlib library*, we create outline polygons that instead join the four points at coordinates (x+0.5, y), (x-0.5, y), (x, y-0.5) and (x, y+0.5), for the pixel at coordinates (x, y). This idea was taken from this blog post by Steve Eddins, and corresponds to the crack code as proposed in

K. Dunkelberger, and O. Mitchell, "Contour tracing for precision measurement", Proceedings of the IEEE International Conference on Robotics and Automation, vol 2, 1985. [PDF]

The polygon created in this way is always exactly one pixel smaller in area that what you get by counting object pixels (and through Stereology we know that pixel counting is an unbiased estimator of size, so it is wise to add one to this area). The convex hull of this polygon will of course be compatible, and the ratios will always be in the range [0, 1].

DIPlib’s measurement function computes the “Size” (area in 2D) and “ConvexArea” (area of convex hull), as well as “Solidity” (their ratio).

^{* Disclaimer: I’m an author of DIPlib.}