square of n; and cube of ny. If the band of Nj; becomes full,
the memory required by every node is in the direct solution
approximately:
-2(/p- 1) -Xyp-l |
nj um Wh " us )V | 39.5): 16byte
APO qp
Iterative solution by point-Jacobi iteration. Also an it-
erative method has been developed for this application. In
the outer iteration loop of that iteration, the diagonal blocks
Ni; and Ny; are inverted and the effects of the blocks Nj,
and N,; are taken into account by an iteration. In an inner
iteration loop, the inversion of the block Ny; has been re-
placed by an iteration where only the diagonal band of the
submatrix is factorized.
The iterative solution is parallelized for a distributed system
by storing the block N»; in one node and sending a slice
of both Nj; and Nj, to each of the rest of the computation
nodes. Like in the direct solution, the block N;; is not stored
at all, and only the upper half of the band including the diag-
onal of Ny; is stored. For this method, the rest of the block
Nj, is stored in sets of linked lists which contain the both tri-
angulars of the block. Only the upper half of the band of N;,
is stored, and similarly as above, the block Ny, is stored in
a set of linked lists.
According to the same formulae as above, the preparing for
the iteration Le. factorizing the bands of the blocks Nj; and
N55 involves a number of operations linearly proportional to
the system dimension. Similarly, the operation counts of
both the outer and the inner loop are linearly dependent on
the system size.
The memory required by the iterative algorithm is n; -48byte
for the node responsible for N,, and By - 776 byte for the
nodes responsible for N;,.
In this iteration, the two models included in the matrix are
solved independently and the dependencies between the
models are solved iteratively. Another possible iteration not
yet implemented would solve both the terrain and the orien-
tation models on various subareas independently and take
the subarea boundaries into account by an iteration.
5.2 Test results on the normal equations’ solver.
Only very preliminary tests have been performed, but a few
fundamental results have been achieved.
The direct solution has appeared too slow: on any row order-
ing scheme, a system of 3475 equations which was solved
iteratively in six seconds, was solved by Cholesky block fac-
torization in no less than 40 minutes on one computation
node. The solution time by the direct solution is awaited to
be proportional to the square of the system dimension, and
thus solving a system of million equations on 68 transputers
would take several years by that method.
The iterative solution has proved significantly faster: the so-
lution of a million equations on 68 nodes could probably take
far less than an hour, which can be well coped with.
Probably the future solution method will be a combination
of the two: the direct solution is used for obtaining the initial
values for the iterative solution.
334
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
6 DETECTION AND MODELLING OF BREAKLINES
When developing the breakline detection algorithm, empha-
sis was put on handling of large areas when the number of
unknown DEM points becomes large. The main idea was
to lower the number of unknown DEM points by detecting
the locations were breaklines exist and modelling breaklines
With a denser grid on those places and using a sparser net-
work elsewhere. Possibilities of using triangles or squares
as elements in the denser parts of the DEM were studied by
implementing some general edge detection algorithms for
breakline detection from difference orthoimages.
6.1 Detection of breaklines from orthoimages
Breaklines can be regarded as gross errors of the mathe-
matical model if the object surface is modelled without con-
sidering breaklines, and smoothness constraints are used
for reconstruction of the smooth object surface. Detection
of the defects in the mathematical model by using difference
orthoimages was proposed, e.g., in (Ebner et a/., 1993) for
breakline detection and in (Hahn 1992) for automatic digi-
tal terrain model verification. The main idea of this kind of
residual analysis method is to compute one orthoimage per
input image. The difference images between the input im-
ages should be identical, if the geometric and the radiomet-
ric part of the mathematical model were correct. Large dif-
ferences between the orthoimages can therefore be caused
by breaklines.
The orthoimages and difference orthoimages (Figure 3)
were calculated in two different pyramid levels. The scale
of the original aerial image was approximately 1 : 15 000
and the heights of the 320 x 320 m? test area varied
from 5 to 27 metres. Several edge detection operators,
such as the Sobel, Prewitt, Kirsch, Robinson operators
and a symmetric exponential filter of infinite size (ISEF)
(Shen & Castan 1992) were implemented for breakline de-
tection from orthoimages in different pyramid levels. Due to
noisy orthoimages median filtering was used before using
the mask operators, while in the case of the ISEF-operator
image filtering and edge detection was performed at the
same time. The different masks operators gave results of
the same kind. However, the results of the ISEF-operator
Seemed to be better, e.g., more continuous breaklines were
obtained. The location of the most significant breakline
corresponding to a creek on the left hand side of the image
could be found more clearly in difference orthoimages than
in the left and right orthoimages, while the road on the right
corresponding to the other elongated but less significant
breakline could be distinguished more clearly from the left
and right orthoimages (Figure 3). After thresholding of the
edge images an edge linking method was needed.
6.2 Developing a method for breakline modelling
Breaklines on the object surface can be very complicated
and therefore only one of the simple cases was handled.
First, it was assumed that there is only one (or none) break-
line within a mesh and it passes through the whole mesh and
secondly, an assumption about the smoothness of break-
lines was made. Under these assumptions breaklines can
be approximated by a line segment. Because the Hough
transform is suitable for detection of straight lines, the suit-
ability of the Hough transform for linking the edge pixels
within a single mesh was tested. The goals of linking step
were to study:
The +
rately,
puted
pixels
mulatc
there
used |
noise.
transf
image
Were t
a higk
the wl
by us
were {
mesh
a nev
A hig
ing to
poten
globa
ing th
cantb
