Estimating Areas in Images

Last lab session, we were told that we can estimate areas of shapes found in images - nice! To do so however, we had to make use of the consequence of a very mathematical thing - Green's Theorem.

It's been very long since I last seen this kind of math so please let me do so here. Green's Theorem states that if you have two functions \(M(x,y)\) and \(N(x,y)\) which have continuous first partial derivatives on a region \(R\) in a plane, then if the curve \(C\) bounding \(R\) is a sectionally smooth simple closed curve in that plane, then:
\begin{equation}\label{green}\iint_R\left(\dfrac{\partial N}{\partial x}-\dfrac{\partial M}{\partial y}\right)\,\mathrm{d}x\,\mathrm{d}y=\oint_C\left[M(x,y)\,\mathrm{d}x+N(x,y)\,\mathrm{d}y\right]\end{equation}
[1] This meant that one way to evaluate the integral on the right hand side of \eqref{green} is to evaluate the integral on its left hand side, and vice versa - assuming the conditions on \(M(x,y)\) and \(N(x,y)\) are met.

Looking at \eqref{green}, we are already hinted at areas in the form of regions \(R\) becoming curves \(C\) bounding \(R\) - and indeed we can use Green's Theorem to formulate another theorem to evaluating areas of \(R\) by looking at the curves \(C\) bounding them. If \(R\) is bounded by a sectionally smooth simple closed curve \(C\), then the area \(A\) of \(R\) can be evaluated using:
\begin{equation}\label{area}A=\dfrac{1}{2}\oint_C\left[x\,\mathrm{d}y-y\,\mathrm{d}x\right]\end{equation}
[1], which, when discretized gives us:
\begin{equation}\label{disc_area}A=\lim_{s\to\infty}\dfrac{1}{2}\sum_{n=0}^s[x_ny_{n+1}-y_nx_{n+1}]\end{equation}
where \((x_n,y_n)\) correspond to the points lying on \(C\) bounding \(R\) [2].

Thus we can estimate the areas of shapes in images by first detecting its edges, then use \eqref{disc_area} to evaluate its estimated area - neat! Our problem now, however is finding a way to detect the edges in our images. Fortunately, Google, being our friend, was able to help us in obtaining methods to detect edges in images. After looking at the codes in [3] and [4], I was able to find five methods - Roberts, Sobel, Scharr, Prewitt, and Canny. These were available using the skimage.filters and cv2 packages for Python.

Having equipped ourselves with the methods to detect edges, our next problem lies in sorting them. Apparently, to use \eqref{area} and \eqref{disc_area} properly, we should sort the coordinates of our edges such that the contour goes counterclockwise. One way to do this it to get the shape's centroid, being the average of the \(x\) and \(y\) coordinates of the edges, subtract it to the already obtained set of edge coordinates \((x_n,y_n)\), convert into polar coordinates \((r_n,\theta_n)\) and sort in increasing \(\theta_n\),  before finally putting it back into cartesian coordinates \((x_n,y_n)\) and using \eqref{disc_area} to evaluate the area.

Putting this into code form, we get

def get_area(f_name,f_type, method, res):
    # Load the chosen image
    u1 = np.uint8(255*rgb2gray(io.imread(f_name+f_type)).astype(int))
    
    # Determine which method to detect edges in the image
    if method == "roberts":
        edges = roberts(u1)
    elif method == "sobel":
        edges = sobel(u1)
    elif method == "scharr":
        edges = scharr(u1)
    elif method == "prewitt":
        edges = prewitt(u1)
    else:
        edges = Canny(u1, 0, 250)
    
    # Get coordinate of edges, adjust resolution, and centroid of shape
    x, y = np.nonzero(edges)
    x, y = x[0::res], y[0::res]
    x_c, y_c = np.average(x), np.average(y)

    # Convert coord into polar coord
    x, y = x - x_c, y - y_c
    r = np.sqrt(x**2 + y**2)
    theta = np.arctan(y/x)
    coord = list(zip(r, theta))

    # Sort coord by increasing theta, and convert back to cartesian coord
    def getKey(item):
        return item[1]
    r_s, theta_s = np.array(list(zip(*sorted(coord, key=getKey))))
    x, y = r_s*np.cos(theta_s), r_s*np.sin(theta_s)

    # Get the area from sorted x and y
    area = 0
    for n in range(len(x)):
        if n == len(x) - 1:
            area += x[n]*y[0] - y[n]*x[0]
        else:
            area += x[n]*y[n+1] - y[n]*x[n+1]
    
    return area

The code presented lets you load any binary image (which contains the isolated shape) of your choice, and depending on the method and resolution you want it to detect edges and sample edge coordinates, give you an area in terms of square pixels. Pretty neat right?

Using this code, we were tasked to obtain the areas of five shapes whose area we knew, and compare that given area to the theoretical area of the shapes. In my case, I used a square, triangle, circle, rectangle, and trapezoid, as shown in Figure 1.

Figure 1: The shapes I used in testing the code that estimates area of shapes in images.

The square had side length of \(20\,\text{pix}\) so that it had an area of  \(400\,\text{pix}^2\), the triangle having base and height length of \(20\,\text{pix}\) each so that it had an area of \(200\,\text{pix}^2\), the circle having diameter of \(20\,\text{pix}\) so that it had an area of \(100\pi\,\text{pix}^2\approx314.15\,\text{pix}^2\), the rectangle having length and width of \(40\,\text{pix}\) and \(20\,\text{pix}\) respectively so that it had an area of \(800\,\text{pix}^2\), and the trapezoid having height of \(24\,\text{pix}\) and base lengths of \(36\,\text{pix}\) and \(18\,\text{pix}\) so that it had an area of \(648\,\text{pix}^2\).

Before running the code onto these shapes, I wanted to see the edges each edge detection method gave me after using them. Doing so for the square, I got Figure 2.

Figure 2: The resulting edges each edge detection method gave out for the square.

Out of the five, I noticed that the Roberts method gave the thinnest and accurate edge for the square. The Sobel and Prewitt methods gave out similar edges albeit Prewitt having brighter gray value. The Scharr method gave out a fairly accurate edge comparable to that of the Sobel and Prewitt method, and the Canny method gave out thin edge like Roberts, but has distorted three of four corners of the square. Despite this, I continued running the code for the Canny, because while the square was distorted, it still resembled a square.

And so I ran the code for each shape, for each method. I compiled them each and plotted the areas obtained by each method for each shape so that I can compare how accurate each method was without looking at numbers. Doing so, I got Figure 3.

Figure 3: The resulting area obtained for each shape using the five methods. The black line mark
the theoretical area of that shape.

Notice that from first look, across all shapes, area obtained using Prewitt edge detection method were highly inaccurate. Further, all edge detection methods were inaccurate in obtaining the area of the circle. Lastly, it appears that more or less, Roberts, Sobel, and Scharr edge detection methods appear to be more accurate and precise in estimating the area of the shapes, while Canny was just precise in being inaccurate.

While it may seem very hard to know which method stood out among the rest, it is reasonable to plot the errors each method had in estimating the area of the shapes. So I did that, and got Figure 4.

Figure 4: The relative error each edge detection method had in estimating the area
of each shape. Relative error for circle is not shown because it had magnitude
much greater than that presented here.

Looking at Figure 4, we immediately see that Scharr is the most unreliable edge detection method in estimating the area of the shape in images. Further, the relative error for the Roberts, Sobel, and Prewitt edge detection methods, including Canny was significantly less, such that excluding Canny there was relatively high deviation in relative error for each shape. Notice that the relative error Canny edge detection had in estimating area of shapes is precise and consistent, whereas the other three had no error in estimating error of square, however varied in error in estimating area of other shapes.

From this, and because of the fact that relative error for the Canny method was precise, I thought that the Canny edge detection method was the most reliable method to detect edges to estimate the area of the shape in images. Interesting.

We were then asked to check how these errors changed as the sampling rate for each image was changed. In this case, I lowered the resolution of the image by changing the sampling rate in reading the edges. This is seen in line 19 of the code. By changing res, I am able to change the step size in which the edge coordinates are sampled on. Again, I did this for each method for the square since it appeared that all edge detection methods were very accurate in estimating its area. Doing so, I got Figure 5.

Figure 5: How the relative error each edge detection method had in estimating the area
of the square as the sampling step size, i.e. the resolution, was changed. Note that
increasing step size mimicked the decreased the resolution of the image as
lesser edge coordinates were sampled as a result.

As expected, it can be seen that each edge detection method was most accurate when the sampling step size was smallest, i.e. resolution is largest, and as resolution was decreased by increasing the sampling step size, the relative error increased

Finally, we were told to estimate some land area in Google Maps. For my case, I wanted to test it on our house since it was easy to obtain a theoretical land area. After calling my dad, he told me that our house had a land area of \(400\,\text{m^2}\). With this in mind, I hoped the estimated area I had was close to this value.

I took a screenshot of our house in Google Maps, isolated my house, and drew an outline of the shape of our lot. The process of doing this is shown in Figure 6.

Figure 6: Process in obtaining binarized image of shape of my house. I took a screenshot
in Google Maps, isolated my house and drew an outline, then binarized it.

To obtain the area, I decided to use the Canny edge detection method to get my edges since I thought it to be the most reliable. After using the code in estimating the area, I got an area of \(119852.2583\,\text{pix}^2\). However this is not what I wanted, since land area was measured in \(\text{m}^2\), and not in \(\text{pix}^2\). Fortunately there was a scale in the screenshot which gave me that \(86\,\text{pix}\) corresponded to \(5\,\text{m}\). Thus I used this conversion factor. Using it I finally got the estimated area to be \(\sim405\,\text{m}^2\), which is pretty close to the theoretical value of \(400\,\text{m}^2\). Pretty neat, if you asked me!

I had so much fun doing this because I feel that it is bringing me closer to understanding how to track objects in images. All I had to do now is to know how to do so without using an external image processing program. But nice!

References:
[1] L. Leithold, TC7: The calculus 7, Chapter 14 (Addison-Wesley Publishing Company, Inc., USA, 1996).
[2] M. Soriano, Activity 3: Area estimation in images using Green's theorem (Philippines, 2017).
[3] n. a., Edges detectors (Web): Accessed last 05/09/18 on http://scikit-image.org/docs/dev/auto_examples/edges/plot_edge_filter.html#sphx-glr-auto-examples-edges-plot-edge-filter-py.
[4] n. a., Canny edge detector (Web): Accessed last 05/09/18 on http://scikit-image.org/docs/dev/auto_examples/edges/plot_canny.html#sphx-glr-auto-examples-edges-plot-canny-py