Area Estimation for Images with Defined Edges

Area measurement from scaled images is a very important technique in many fields, from land area measurements to quality checking of electronics. However, although the analytic solutions for the area of regular shapes are known, most real-world samples are irregularly shaped.

For this activity, our algorithm of interest is Green’s theorem. What is Green’s theorem? It is a relation between a double integral to a contour integral…. In layman’s terms it is an equation that somewhat relates the area of a shape to its perimeter. This relation is given by:

Figure 1. Green's Theorem

Using this formula and assigning values for F₁ and F₂, we can obtain a formula for the area:

Figure 2. Area using contour integral

With its discrete form given by:

Figure 3. Discrete area approximation using contour integral.

At the beginning, I didn’t realize that scilab had a follow command so I tried to come up with my own edge detection algorithm. My plan was to utilize the fact that my images were binary.

Figure 4. Pixel orientation

 

The figure is a layout of adjacent pixels. My theory was that if all the surrounding pixels has a value of 1, it is not an edge, else it is. Using this algorithm I was able to isolate the contour of a rectangle:

Figure 5. Rectangular contour

Now my next problem was following the contour. This I was not able to do. My main problem here is preventing the backtracking of the algorithm. In a 1 dimensional path like the contour there are 2 ways to go my problem was how to keep it moving forward. Because of this I gave up on this feat.

Using the command follow, I obtained the an array of coordinates for the contour of the following shapes to use for the algorithm. And from there I was able to obtain an estimate of the area:

 

Figure 6. Binary Rectangular Image

 Theoretical Area: 60000 pixels

Area obtained through 

Green's Theorem: 60000 pixels

Figure 7. Circular Binary Image

 Theoretical Area: 96211.275 pixels pixels

Area obtained through 

Green's Theorem: 95319 pixels

For the rectangular shape, Green's theorem was able to discern the correct area while there is a 0.927% error for the circular shape. This of course is within the margin of error for the algorithm.

The next part of the activity is a real world application of area estimation. What I did was obtain a map of Colorado from Google Maps:

Figure 8. Map of Colorado

 I chose Colorado because of the simplicity of its shape. Then I transformed it to a binary image containing only the basic shape:

Figure 9. Binary image of the shape of Colorado

Using this I obtained the area of Colorado in pixels. Using the conversion factor of 1.8867924528301886792452830188679 km/pixel, I obtained the actual area of 265,738.7 km²

Comparing it to the actual area of 269,837 km², the error the algorithm incurred was only 1.52%, which shows that the algorithm was effective in its estimation. I took a detour because of my failure to read the instructions but since I was able to complete the activity, I would give myself a 9/10.

Image types and formats

For this activity we discussed the different types and formats for digital images. Most digital images can be categorized into 4 basic types, depending on the type of information the image carries:

1.     Binary Images: known to be either black or white, these types of images can only carry binary information- meaning their pixel values can only be either 1 or 0. These kinds of images are usually used for document and line art, like the one below:

Figure 1. http://xkcd.com/832/

 

 

 

 

   

          

FileName: bw.bmp

FileSize: 75166

Format: PNG

Width: 740

Height: 1674

Depth: 8

StorageType: indexed

NumberOfColors: 2

ResolutionUnit: centimeter

XResolution: 72.000000

YResolution: 72.000000 

Matrix Size: 1674 740    

      Grayscale Images: these are typically known as black and white images, images of this type have pixels that carry an integer value between 0(black) and 255(white). This type is usually used if there is a need to portray the image in graytones.

Figure 2. Lions Head To Head. © 2010 Nick Brandt

FileName: grayscale.bmp
FileSize: 637478
Format: BMP
Width: 858
Height: 740
Depth: 8
StorageType: indexed
NumberOfColors: 256
ResolutionUnit: centimeter
XResolution: 28.350000
YResolution: 28.350000
Matrix Size: 740 858       

      

 

      True color images: are images that have 3 channels, one for each of the primary colors of light. Each channel has 256 (0-255) levels and once overlaid, different colors are produced. The total number of color combinations possible for a true color image is 256³ or  1.6million+ colors these types of images are usually taken photographs and complex images like below:

Figure 3. © Ookami original art

FileName: tcolor.bmp
FileSize: 67038
Format: JPEG
Width: 460
Height: 345
Depth: 8
StorageType: truecolor
NumberOfColors: 0
ResolutionUnit: inch
XResolution: 100.000000
YResolution: 100.000000
Matrix Size:  345 460 3    

      Indexed Images: colored images whose colors are represented numbers which correspond to colors in a predetermined colormap. For this kinds of images, 2 parts are stored, 1^st is the image itself and secondly is the colormap. These kinds of images thereby tend to have less color information than true color images since these images are constrained by the size of their respective colormaps. These images are usually computer generated graphics since these have limited palette of colors.

Figure 4. Clairy Clefairy Wings [Red] © Clairy

FileName: index.bmp
FileSize: 10358
Format: BMP
Width: 79
Height: 116
Depth: 8
StorageType: indexed
NumberOfColors: 256

                                                                   ResolutionUnit: centimeter

                                                          XResolution: 0.000000

                                                          YResolution: 0.000000     

                                                          Matrix Size: 116 79

Next is about file formats. There are 2 types of file formats used in images depending on the image compression algorithm used to create the image. One is lossless compression, and the other is lossy compression. Lossless compression is, as its name implies, a compression algorithm where no loss of information is incurred.  Examples of lossless format would be TIFF and PNG.

TIFF- A flexible file format which can either be lossless or lossy. It is an image format that when used, normally does not do compression at all which makes for large file sizes.

PNG- a file format that looks for patterns to compress the file size. This compression is exactly reversible, causing no loss of information.

Lossy compression on the other hand stores the image using compression algorithms that sacrifices loss of information for smaller file sizes. Well known lossy formats include JPG and GIF.

JPG- an image format that is optimized for photographs and images with continuous tones. Has a very high compression ratio with minimal quality loss.

GIF- Compresses the image by assigning a 256 colormap for the image and replaces patterns with abreviations. This format is optimized for images with fewer colors since for images with many colors it would approximate the image using the available palette.

The main bulk of the activity is to modify an image into different types. Take the true color image above, using the SIP function im2gray we obtain:

Figure 5. Ookami grayscaled

By grayscaling the image the color channel disappears. Now if we use the function im2bw using 0.5 as threshold:

Figure 6. Ookami black and white

This is especially useful when scanning hand-drawn graphs. Take the graph I used for activity 1 for example:

Figure 7. Acitvity 1 Graph

If we take its histogram:

Figure 8. Histogram of the gray level values of the graph.

We can see that most of the light areas are above 0.5 so we use this as a threshold to obtain:

Figure 9. Black and white version of the activity 1 graph

We can see that all that is left of the background are bits of speckles and the graph obtained had a good solid line. Lowering the threshold any lower and we would obtain a graph with broken lines. Therefore in order to remove the remaining speckles, we would need to employ other techniques than thresholding. I’m thinking of using Fourier analysis to remove the high frequencies to remove the speckles. All in all this was a demanding activity due to the extra research on types and formats. But since I was able to separate most of the background from the graph, I’d give myself 8/10.