ISPRS Commission III, Vol.34, Part 3A „Photogrammetric Computer Vision‘, Graz, 2002 
CONCLUSIONS 
The proposed algorithms combine efficiently the region 
growing techniques with principal component analysis. They 
are fast and also robust in noisy environments, and their 
robustness increase with increasing the number of dimensions. 
Many aspects are not yet explored, such as the applications in 
image processing. The definitions of geometrical properties of 
objects need to be studied better in discrete and noisy case, and 
applied in aggregation criteria. 
The algorithms have given good and useful results on laser 
scanning data, preparing the way to vectorialization, aspect that 
is very important for cartographic production. 
APPENDIX 
NOTES ON ALGORITHM IMPLEMENTATION 
Eigensystem analysis 
Eigensystem analysis is performed using EVCRG and GVLSP 
routines of IMSL Math Library. 
o Routine EVCRG computes the eigenvalues and 
eigenvectors of a real matrix. The matrix is first balanced. 
Orthogonal similarity transformations are used to reduce 
the balanced matrix to a real upper Hessenberg matrix. 
The implicit double-shifted QR algorithm is used to 
compute the eigenvalues and eigenvectors of this 
Hessenberg matrix. The eigenvectors are normalized such 
that each has Euclidean length of value one. The largest 
component is real and positive. The routines used in 
EVCRG are based on the EISPACK library. 
o Routine GVLSP computes the eigenvalues and 
eigenvectors of Az = 1Bz, with A symmetric and B 
symmetric positive definite. The Cholesky factorization B 
= RTR, with R a triangular matrix, is used to transform 
the equation Az = 1Bz, to 
(R-T AR-1)(Rz) = 1 (Rz) 
The eigenvalues and eigenvectors of C = R-T AR-1 are 
then computed. The generalized eigenvectors of A are 
given by z = R-1 x, where x is an eigenvector of C. 
Sorting 
Sorting is performed using SVRGP and SVRGN routines of 
IMSL Math Library. 
o Routine SVRGP sorts the elements of an array, A, into 
ascending order by algebraic value, keeping a record in P 
of the permutations to the array A. The routine SVRGP 
uses the algorithm discussed in SVRGN. 
o Routine SVRGN sorts the elements of an array, A, into 
ascending order by algebraic value. The array A is 
divided into two parts by picking a central element T of 
the array. The first and last elements of A are compared 
with T and exchanged until the three values appear in the 
array in ascending order. The elements of the array are 
rearranged until all elements greater than or equal to the 
central element appear in the second part of the array and 
all those less than or equal to the central element appear 
in the first part. The upper and lower subscripts of one of 
the segments are saved, and the process continues 
A - 294 
iteratively on the other segment. When one segment is 
finally sorted, the process begins again by retrieving 
the subscripts of another unsorted portion of the array. 
REFERENCES 
Curvature estimation 
S. Pulla, A. Razdan and G. Farin (2001), Improved 
curvature estimation for watershed segmentation of 3- 
dimensional meshes. 
P. Kresek, G. Lukács and R. R. Martin, Algorithms for 
computing curvatures from range data. 
C. K. Tang and G. Medioni, Robust estimation of curvature 
information from noisy 3D data for shape description. 
Eigensystem analysis 
G. H. Golub and C. F. Van Loan (1996), Matrix 
computations, The John Hopkins University Press, 
Baltimore and London. 
Hanson, Richard J., R. Lehoucq, J. Stolle, and A. Belmonte 
(1990), Improved performance of certain matrix eigenvalue 
computations for the IMSL/MATH Library, IMSL 
Technical Report 9007, IMSL, Houston. 
Martin, R.S., and J.W. Wilkinson (1968), Reduction of the 
symmetric eigenproblem Ax = IBx and related problems to 
standard form, Numerische Mathematik, 11, 99-119. 
Smith, B.T., J.M. Boyle, J.J. Dongarra, B.S. Garbow, Y. 
Ikebe, V.C. Klema, and C.B. Moler (1976), Matrix 
Eigensystem Routines - EISPACK Guide, Springer-Verlag, 
New York. 
Sorting 
Griffin, R., and K.A. Redish (1970), Remark on Algorithm 
347: An efficient algorithm for sorting with minimal 
storage, Communications of the ACM, 13, 54. 
Petro, R. (1970), Remark on Algorithm 347: An efficient 
algorithm for sorting with minimal storage, 
Communications of the ACM, 13, 624. 
Singleton, R.C. (1969), Algorithm 347: An efficient 
algorithm for sorting with minimal storage, 
Communications of the ACM, 12, 185-187.