ul 2004
out the
ini and
lar the
on of a
esented.
5) is the
the one
et al’s
struction
fact, the
seen as
graphs,
aning of
ainment,
enerated
yncluded
retrieve
say that
aph path
ate to be
op of an
night be
ed, let us
of urban
the one
id corner
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B4. Istanbul 2004
Legend ^ ^ \
Slope classes
0- 45°
LME
Me
167 ZZ /
D» =
Figure 6. An example of the meaning within the context of the
urban scene that may be inferred from a graph path.
Let us go through the given path starting from polygon 3, the
useful external border. On the first level of adjacency the steep
polygon /98 is found which is contained by the previous one.
This, in turn, contains //at polygon 200 on the second level of
adjacency. Polygon 200 contains several others and, in
particular, contains steep polygons 250, 256, 260 which all
together contain flat polygon 257 belonging to the fourth and
last level of adjacency. In terms of urban scene, the meaning of
this sequence of spatial relations of adjacency and containment
is the existence of a building (pictured on the bottom left-hand
side of Figure 6) whose boundary is almost shaped by the
rectangular dark green polygon displayed
4. CONCLUSIONS
The first steps towards the development of a graph-based scene
analysis technique have been presented in this paper. A
neighbourhood graph was generated within the initial
unstructured data set to bring in topological information. This
task was accomplished by generating a TIN based on the
Delaunay triangulation. Two classes of polygonal regions were
generated gathering flat and steep TIN facets respectively.
Now that those polygonal regions were generated, the next step
is the automated generation of graphs (considering the polygon
centroids as its nodes) which has not been fully implemented
yet and is currently being explored. Subject to our further work
is the subsequent aggregation of those nodes into identified
meaningful structures; these, in turn, should be clustered into
homogenous regions; after the delineation of cluster shapes an
analysis process will have to be carried out (either by pattern
recognition or interpretation procedures). The aim of the final
cluster shapes analysis is the retrieval of higher level
information, e.g., sets of buildings, vegetation areas, and say,
land-use parcels.
The results we are expecting to obtain might be useful to
Support land-use mapping, image understanding or, generally
Speaking, to support clustering analysis and generalization
processes.
1051
REFERENCES
Anders, K.-H.; Sester, M.; Fritsch, D. (1999), Analysis of
settlement structures by graph-based clustering. Semantische
Modellierung, SMATI 99, 41-49. Munich (Germany).
Barnsley, M.J.; Barr, S.L. (1997), Distinguishing urban land-
use categories in fine spatial resolution land-cover data using a
graph-based, structural pattern recognition system. Comput.,
Environ. And Urban Systems, Vol. 21, No; 3/4: ; 209-225.
Elsevier Science Ltd.
Barr, S.L., Barnsley, M.J. (1996), Inferring urban land-use from
satellite sensor images using kernel-based spatial
reclassification. Photogrammetric Engineering and Remote
Sensing, No. 62: 949-958.
Barr, S.L, Barnsley, M.J. (1997), A region-based, graph-
theoretic data model for the inference of second-order thematic
information from — remotely-sensed images. International
Journal of Geographical Information Science, Vol. 11, No. 6:
555-576. Taylor & Francis Ltd.
Bunn, A.G.; Urban, D.L.; Keitt, T.H. (2000), Landscape
connectivity: A conservation application of graph theory.
Journal of Environmental Management, no.59, 265-275.
Academic Press (USA).
Edelsbrunner, H.; Kirkpatrick, D.G.; Seidel, R. (1983), On the
shape of a set of points in the plane. of /EEE Transactions on
Information Theory, V 01.29, no.4: 551-559.
Eyton, J.R. (1993), Urban land-use classification and modelling
using cover-type frequencies. Applied Geography, Vol. 13:
111-121.
Forberg, A.; Raheja, JL. (2002), Generalization of 3D
settlement structures on scale-space and structures recognition.
Work Report, Institut für Photogrammetrie und Fenerkundung
(Universität der Bundeswehr München), Lehrstuhl für
Kartographie (Technische Universität München), Munich
(Germany).
Gibbons, A. (1989), Algorithmic Graph Theory. Cambridge
University Press, Cambridge (UK).
Gross, J.; Yellen, J. (1999), Graph Theory and Its Applications.
CRC Press, Boca Ratón (Florida, USA).
Kirkpatrick, D.G.; Radke, J.D. (1985), A framework for
computational ^ morphology. Computational ^ Geometry
(ToUSSAINT, G.T., ed.), 217-248. North- Holland, Amsterdam
(The Netherlands).
Laurini, R.; Thompson, D. (1992), Fundamentals of Spatial
Information, 5. Academic Press, London (UK).
Nardinocchi, C., Gianfranco, F., Zingaretti, P. (2003),
Classification and filtering of laser data. ISPRS Workshop on
3D reconstruction from airborne laser scanner and InSAR data.
Dresden (Germany).
Radke, J.D. (1982), Pattern Recognition in Circuit Networks,
PhD thesis, Department of Geography, University of British
Columbia (USA ).