|
|
|
Poster Session R
|
The algorithm converting 2DRE quadtree to vector
Xiao Ke
Institute of Remote Sensing Application Chinese Academy of Sciences
P.O. Box 775, Beijing 100101, P.R., China
Abstract
This paper advances and analyses an algorithm converting 2DRE quadtree to vector in order to extract the boundarys of fields in an image in its 2DRE quadtree format. The boundarys of fields in images are represented in the form of coordinates of the ends of vectors for displaying the fields’ shape and outputting the vectors easily. In this paper, the base of the algorithm is introduced first; then the algorithm is described in detail; finally the features and the complexities of time and space of the algorithm is estimated and analyzed.
In the work of remote sensing image processing and geographic information system, the conversion between different data structures is an important and interesting topic. Quadtrees, especially 2DRE quadtree have a lot of advantages such as regularity, flexibility, saving space of storage and the property easy to represent structural information of images while chain code-vector is the data structure used to detect and describe the boundaries and shapes of fields in an image. Both of the two structures have their own advantages and disadvantages in different situations and suit different uses in practice. In a completed image processing system or geographic information system there should be some data structures and flexible conversions between them for their corresponding uses So the research on the algorithm converting the two data structures is significant.
1. Field’ boundarys and chain code
Given a field in an image, its boundary can be served as a graphical polygon or a closed curve. So a format representing it can be defined.
As Fig. 1 showing, i = 1,234, 4 represent four directions of 90° * i, clockwise respectively. So a curve on a plane can be described with a series of connected unit vectors, then the boundary of a field as a closed curve can also be rep-
resented in this way. The sequence of vectors is called “chain Code” [1].
Fig. 2 shows a field in an image; Table 1 is the chain codes representing the boundary of the field from point. A. It can be seen that the shape for the boundary and the bmp and crank features of the curve are displayed by a series o numbers very clearly.
Fig 1 Rule of direction codes
Fig 2. A field in an image
Table 1 The Chain Code of the Field’s boundary in Fig. 2
| 0 |
3 |
0 |
1 |
0 |
3 |
0 |
3 |
0 |
1 |
| 0 |
0 |
1 |
1 |
1 |
1 |
1 |
2 |
2 |
2 |
| 3 |
2 |
1 |
1 |
1 |
0 |
1 |
2 |
2 |
2 |
| 2 |
2 |
3 |
3 |
3 |
3 |
3 |
3 |
0 |
3 |
2. Boundary Tracking
Suppose there is a 2DRE quadtree representing an image in which the elements are the contiguous areas of points with value ‘1’ . The “field” is composed of these kind of contiguous areas.
Based on the discussion in last section, from any point on the boundary, according to the directions of a series of unit vectors, the chin codes of the boundary can be determined. The last vector must point at the initial point since the curve is closed. So if the initial point and the sequence of vectors and given, the shape and the position are also be determined. Again, since the curve is closed, any point on the boundary can be treated as the initial point. For convenience, the first element is chosen as the initial point. The reason is: first, it is definitely on the boundary of the first, it is definitely on the boundary of the field; second, it is located at upleft corner ( not necessarily upmost or leftmost, as the situation of smooth curve in mathematics ). So the initial tracking direction will be defined easily.
Before tracking procedure, the initial point pair ( P1,1, P1,0) should be given where P1.1 is the point in the field and P1.0is background point. As mentioned above, the point represented by the first element in quadtree is served as P1,1, and because it is located at upleft corner of the field, the initial direction is determined as 0. So, the relation between P1,0and P1,1 is
|
|
|
|
|
|
|
