The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B3b. Beijing 2008
623
Opening & Closing, Hit-or-Miss Transformation and etc. for
getting more information about morphological functions and
algorithms and their applications see (Gonzalez, 2002).
2.3 MST Algorithms
Given a connected, undirected and weighted graph G=(V,E), a
Minimum Spanning Tree T is a connected sub graph of G such
that there is no cycle in T and the edges in T create a path
between any two nodes in G, and the sum of the weights of the
edges in T is minimized.
The most prominent MST algorithms are Kruskal and Prime
which are considered Greedy algorithms.
In each phases of "Greedy algorithms, a decision is made that
appears to be good, without regard for future consequences.
Generally, this means that some local optimum is chosen. This
strategy is the source of the name for this class of algorithms.
When the algorithm terminates, we hope that the local optimum
is equal to the global optimum. If this is the case, then the
algorithm is correct; otherwise, the algorithm has produced a
suboptimal solution. Both of these algorithms find the optimal
solution of the problem but in different methods. Kruskal
algorithm finds MST based on edges but Prime algorithm find
MST based on Vertices, But both of them have the same result.
Since in this research Kruskal algorithm has been used, this
algorithm is introduced.
Kruskal algorithm was initially presented by Juseph Kruskal in
1965. steps of This algorithm are as follows:
1. Find the cheapest edge in the graph (if there is more
than one, pick one at random).
2. Find the cheapest unmarked edge in the graph that
doesn't close a cycle.
3. Repeat Step 2 until you reach out to every vertex of
the graph (or you have N Vertices and N-l edges,
where N is the number of Vertices.
Designing variety of networks like phone lines, Electronic and
hydraulic lines, TV cables, computer and road networks are the
Main applications of MST
3 APPROACH
In order to better understanding of the proposed road extraction
system implementation, Figure 1 denotes the diagram of it.
Using these diagram, different procedures of the proposed
system can be described as follows:
3.1 Input Images
Input data of the proposed road extraction system are multi-
spectral and pan-sharpened IKONOS images of Lavasan city in
Iran (with respectively 4 and 1 meters spatial resolution). The
proposed system investigates capability and amount of system
success in extraction of different shaped roads such as straight,
spiral, junction and square. No additional data is used for
implementation of the system except for what is mentioned.
Figure 2 represents the IKONOS tested images of Lavasan city
in Iran (with respectively 4 and 1 meters spatial resolution).
3.2 Pre-processing of Images
Image enhancement in order to modifying the value of image
pixels, is a classical method for improving the visual
perception. In this research Linear Histogram Stretching
technique using PCI Geomatica V9.1 software is used for
preprocessing of the images when it is needed. By using this
method. Image gray level values are transformed from
observation domain to complete dynamic domain using linear
transform function.
Although the processed image is more suitable than the original
image for some applications, in classification application (that
is used in this research) it is suggested not to use this technique
as much as possible. Because changing the gray level values
may mislead the classification procedure.
1. Input
2. Preprocessing
3. Classification
4. Post Processing
5. Road Extraction
6. Results
Figure 1. Semi- automatic road extraction Diagram
(c)
Figure 2. Multi-spectral and pan-sharpened IKONOS
images of Lavasan citv in Iran (Input images)
