| GISdevelopment.net ---> Technology ---> Image Processing |
Computing percentage of geographical area based on aerial image
E. C. Tan and D. Xiao
School of Computer Engineering, Nanyang technological University,
Nanyang Avenue, Singapore 639798
Email: asectan@ntu.edu.sg
Abstract
Software implementation of algorithms which calculate the relative percentage of a geographical area of an aerial image displayed on a computer screen is described. The enclosed region can be of any shape and the methods have useful applications in geosciences.
1. Introduction
Consider studying a satellite remote-sensing image of bush fire or forest fire. The image is colored-coded and one is interested to know the percentage of the area on fire in relation to a larger surrounded area. The shape of the area is usually irregular. In the absence of any proper tool, the two areas can only be estimated by crude eye inspection. Of course, a more accurate method of calculating the areas can be done by manually tracing the required regions on a piece of graph paper and then approximating the areas by counting all the small whole squares plus all the fractional portions. This will take up a lot of time. Moreover, a small estimation error can mean a large actual error because of the vastness of the landscape.
Our objective here is to present novel techniques which can compute the percentage accurately using a PC. The image under study must first be scanned into the PC, or is captured in a digital form which can be stored in the PC. The proposed algorithms can count the number of pixels of an enclosed region on the computer screen in order to obtain the area.
2. Algorithms
Area calculations based on specific mathematical representations have been explored by some researchers [1]-[8]. The two techniques which we propose are: (i) the line-scanning method, and (ii) the contour-gyration method. They are more general than the existing methods. Furthermore, it is very easy to implement and apply the methods. As long as an image can be displayed on a computer screen, the area of any specific region can be calculated.
2.1 Line-scanning algorithm
The basic idea is to scan the area in range line by line, and count all the valid points (pixels).
2.2 Contour-gyration algorithm
The basic idea is to traverse the entire region of interest from an interior point which acts as the starting point, under a specified rule. If there is no path, retreat a step to find a new one until eventually retreating to the starting point. All points traversed are counted to make up the area.
3. Implementations
3.1 Line-scanning algorithm
There are three methods to implement the line-scanning algorithm.
There are also three methods to implement the contour-gyration algorithm.
As a first example shown in Fig.1, the percentage of the area of the small enclosed region in the middle with respect to the larger enclosed area is 48.1%. The single-limit method of the line-scanning algorithm outperformed all other methods. It took only 0.72s on a Pentium III machine to compute the required result.
Fig.1 Relative percentage of area calculation
As a second example, consider the aerial image in Fig. 2(a). In order to compute the relative designated area with respect to the darken area, two colors are used to shade the required regions first, as shown in Fig. 2(b). Then we apply one of our algorithms to compute the relative percentage. The value is 11.7%. That is, the darken area (green colour) occupies 13.1% of the designated area (blue plus green colours). The time to compute this value takes only 1.98 sec.
Fig. 2(a). An aerial image
Fig. 2(b). Percentage of green area relative to blue+green area
References
Software implementation of algorithms which calculate the relative percentage of a geographical area of an aerial image displayed on a computer screen is described. The enclosed region can be of any shape and the methods have useful applications in geosciences.
1. Introduction
Consider studying a satellite remote-sensing image of bush fire or forest fire. The image is colored-coded and one is interested to know the percentage of the area on fire in relation to a larger surrounded area. The shape of the area is usually irregular. In the absence of any proper tool, the two areas can only be estimated by crude eye inspection. Of course, a more accurate method of calculating the areas can be done by manually tracing the required regions on a piece of graph paper and then approximating the areas by counting all the small whole squares plus all the fractional portions. This will take up a lot of time. Moreover, a small estimation error can mean a large actual error because of the vastness of the landscape.
Our objective here is to present novel techniques which can compute the percentage accurately using a PC. The image under study must first be scanned into the PC, or is captured in a digital form which can be stored in the PC. The proposed algorithms can count the number of pixels of an enclosed region on the computer screen in order to obtain the area.
2. Algorithms
Area calculations based on specific mathematical representations have been explored by some researchers [1]-[8]. The two techniques which we propose are: (i) the line-scanning method, and (ii) the contour-gyration method. They are more general than the existing methods. Furthermore, it is very easy to implement and apply the methods. As long as an image can be displayed on a computer screen, the area of any specific region can be calculated.
2.1 Line-scanning algorithm
The basic idea is to scan the area in range line by line, and count all the valid points (pixels).
2.2 Contour-gyration algorithm
The basic idea is to traverse the entire region of interest from an interior point which acts as the starting point, under a specified rule. If there is no path, retreat a step to find a new one until eventually retreating to the starting point. All points traversed are counted to make up the area.
3. Implementations
3.1 Line-scanning algorithm
There are three methods to implement the line-scanning algorithm.
- Full-template method: All points in a template must be scanned one by one. Although this method is inefficient for dealing with a single large area, it is relatively effective if a graph is diffused all around the screen
- Single-limit method: The method is to limit the scanning range in either the horizontal or the vertical orientation. For example, if the horizontal limits are set, vertical scan should be employed. On the other hand, horizontal scan is applied under the vertical limits. In vertical scan, firstly, it selects an arbitrary column across the graph as the starting line to be scanned. It then performs vertical scan, column by column towards both the left and right directions until blank columns (without any valid point in a whole column) are met in the two directions.
- Double-limit method: It is in fact, a both-orientation-limit method.
There are also three methods to implement the contour-gyration algorithm.
- Recursive method: It calculates the area from a point, and then performs recursion on all its eight adjacent points.
- Stack method: A stack is used to record the information of accessed points in order to identify the retreated route.
- Color method: To reduce the memory expense in a two-dimension array and a huge stack, some hardware attributes of points can be used to record the information instead. Colors are adequate to record the information such as accessed flags and retreating path.
As a first example shown in Fig.1, the percentage of the area of the small enclosed region in the middle with respect to the larger enclosed area is 48.1%. The single-limit method of the line-scanning algorithm outperformed all other methods. It took only 0.72s on a Pentium III machine to compute the required result.
Fig.1 Relative percentage of area calculation
As a second example, consider the aerial image in Fig. 2(a). In order to compute the relative designated area with respect to the darken area, two colors are used to shade the required regions first, as shown in Fig. 2(b). Then we apply one of our algorithms to compute the relative percentage. The value is 11.7%. That is, the darken area (green colour) occupies 13.1% of the designated area (blue plus green colours). The time to compute this value takes only 1.98 sec.
Fig. 2(a). An aerial image
Fig. 2(b). Percentage of green area relative to blue+green area
References
- Franklin, W.R. Calculating map overlay polygons' areas without explicitly calculating the polygons-implementation. Proceedings of the 4th International Symposium on Spatial Data Handling, Univ. Zurich, vol.1, p. 151-60, Zurich, Switzerland, 1990.
- Geuk Lee; Hee Yeung Hwang. An operation efficiency analysis on breadth first quadtree. Proceedings TENCON '93. 1993 IEEE Region 10 Conference on 'Computer, Communication, Control and Power Engineering' (Cat. No.93CH3286-2), p. 660-3 vol.2, IEEE New York, NY, USA, 1993.
- Tanaka, T.; Takahashi, T. Precise rendering method and its application for highlight generation. Transactions of the Information Processing Society of Japan, Vol: 33 Iss: 4 p. 471-80, Japan, 1992.
- Hu Baoxin; Wang Jianwu; Zhu Chongguang. A valid method applied to area calculation in wheat production estimation. IGARSS '93. 1993 International Geoscience and Remote Sensing Symposium (IGARSS'93). Better Understanding of Earth Environment (Cat. No.93CH3294-6), p. 532-3 vol.2, IEEE New York, NY, USA, 1993.
- Hauser, D.L.; Wayner, P.C.; Taylor, D.L. An algorithm for improving the accuracy of discrete ROI integrals. Medical Physics, Vol: 22 Iss: 6 p. 723-32, USA, 1995.
- Goodman, T.N.T.; Ong, B.H. Calculating areas of box spline surfaces. Computer Aided Design, Vol: 27 Iss: 6 p. 479-86, UK, 1995.
- Weih, R.C., Jr. The effect of slope on area calculations in a geographic information system. Proceedings: International Symposium on Spatial Accuracy of Natural Resource Data Bases. Unlocking the Puzzle, p. 132-40, USA, 1994.
- Lee, Li-Chyn. Comparison of Monte Carlo and Analytic Critical Area Calculation. The University of Arizona (0009), MS dissertation, pp: 81, USA, 1992.
- Aho, Alfred V. Data Structures and Algorithms. Addison-Wesley, 1987.