tography by in-
e, as the nature
onsidered tem-
:loud/image. If
elonged to the
hanges in sub-
manent objects
y
>.
ed
he urban scene
[ION
ent passages of
lifferent times)
ions and com-
point cloud is
responding 3D
nerated in sub-
| the associated
ın environment
cater for these
d (Urban Data
or comparison
rate graph the-
3D point cloud
/idence grid as
rid occupies a
| on certain at-
hese attributes
rmal along X,
nsity and mean
'spectively and
lized values of
RÀ + WnpNp
np
(1)
0.5 are Occu-
25 and ug. —
Wnp = 0.0625
se weights are
magnitude and
sity and color)
nment and also
cy grid method
grids are con-
(np — 1)) and
used to formu-
associated un-
rocess in each
uitable for ana-
3.2 Similarity Map Construction
In order to obtain a similarity map in each passage, the 3D evid-
ence grid in successive passages is compared. Instead of finding
the overall graph/grid similarity, we are more interested in meas-
uring the similarity of each cell as this indicates exactly which
part of the 3D cartography has changed. Currently, many dis-
tances have been developed to compare two objects (in this case
cell) according to the type of attributes, such as x? or Mahalan-
obis. However, when working with real values, the most widely
used (and simplest) metric is Minkowski measure dp:
k 1
dp(x,y) = [> wile: -w] ? with p » 0 Q)
i=1
In this measure, x; and y; are the values of the i^ attribute de-
scribing the individuals x and y. W; is the numerical weight cor-
related with this attribute. k is the total number of attributes. In
order to transform Minkowski distance (2) into a similarity meas-
ure sp a value D; is introduced, that corresponds to the difference
between the upper and the lower bounds of the range of the i
attribute:
k p
wey = [2-7
iz] T
1
|? withp > 0 3)
This similarity function may provide a measure indicating the
amount of changes occurring in a 3D grid cell in subsequent pas-
sages but it remains silent on the type of change taking place.
Now this information could be useful when deciding how to handle
these changes in the 3D cartography. Thus, in order to get more
insight into the type of changes we incorporate the notion of dis-
tance between individuals or objects studied in Cognitive Sci-
ences. For this purpose, we use the method proposed by Tversky
(Tversky, 1977) to evaluate the degree of similarity S; , between
two individuals x and y respectively, described by a set of attrib-
utes A and B, by combining the four terms AUB, ANB, A—B
and B — A into the formula:
f(An B)
f(AU B) t af(A — B) * Bf(B — A)
As we want to compare a pair of individuals (in this case, cells
in successive passages) described by a set of numerical attributes,
we combine the definitions proposed by Tversky and Minkowski.
In these measures, we use Tversky's model to compare the two
sets of attributes describing the individuals; the function f of this
model is the Minkowski's formula as rewritten in (3). The para-
meter p of this formula equals 1 since in Tversky's model the
function f corresponds to a linear combination of the features.
Now, depending upon the way the parameters o and Ó are in-
stantiated, different kinds of cognitive models of similarity can
be expressed. By instantiating à. = 3 = 0 we obtain the sym-
metric similarity measure Sym while by instantiating a = 0 and
B = —1 we obtain the asymmetric similarity measure ASym.
Now we use these values to fill up similarity map S 55 as shown
in Fig. 2. The values of ASym allow to evaluate the degree of
inclusion between the first cell (reference) into the second cell
(target). Hence, with the attributes (along with their correspond-
ing weights) assigned to these cells (discussed in § 3.1), the value
of ASym can be used to assume the type of changes occurring
in the 3D grid cell as summarized in Tab. 1 where x and y are
the same 3D grid cell in different passages. These values of Sym
and ASyms not only help in ascertaining the type of changes oc-
curring but also the most suitable action required to handle that
particular 3D grid cell. Condition 1 is automatically handled in
the incremental updating phase where as for condition 2 and 3,
Automatic Reset function is called into action.
This similarity map Smap is updated in each passage and only
the different cells (with Sym < Similaritythreshold) along with
their associated uncertainty values are kept in the map whereas
the remaining cells considered as identical cells (with high level
(4)
Sz.,y =
of similarity) are deleted from the map. Hence, this not only re-
duces the size of the map progressively in subsequent passages,
but also avoids possible storage memory issues for large point
clouds in case of large mapping areas (see § 5, Fig. 8, for more
details).
(c)
Figure 2: Formulation of 3D evidence grids and similarity map.
(a) & (b) show the 3D point clouds (P(n,) and P(n, — 1))
mapped onto an evidence grid of cell size L? respectively. In
(c), the similarity map obtained from the two evidence grids.
[ET Condition | Possible assumption ]
I | ASym;,, < ASymy,z Addition of structure
(could be new construction or earlier
misclassified objects)
2 ASyms,y > ASymy,z Removal of structure
(could be demolition)
3 | A5ymz,y = ASymy = Modification of structure
(depending on the value of Sym)
Table 1: Type of changes
3.3 Associated Uncertainty
Let the cell scores of a particular cell j in n number of passages:
Cl Css 2 C2, Dean fid sequence of random variables,
then the n*" sample variance s,” is given as:
j ^j y?
x S d (Cs, PA Ct.)
;2
sù =
n—1
then, adding and subtracting el
E 1 n j hj xy ED NS
Sn = n= j. S (Ce CE i + C nci E. cl) |
pun
Expanding and solving this to get
;2 1 2 =; e.
M mue-38 0-208, - 05»
n—1
; Le T RID
* 2 >. (C$, = er XC | = C$, )] * (C$. E C$.) |
k=1
Using the standard mean (77; Gi. — (n—- 06i the
sum-term simplifies to 0:
2 = a ; TU
[n - 255, 9 ( - 065, = CF, + (Ch, - 05, Y]
sj 2 =
" 0-1
Further simplification yields
$ 6 2
82 = (222), Gi Sy
" (n= 1) 751 n
The uncertainty associated with each cell in the map u? is hence
estimated and updated in each passage (n > 1) using the follow-
ing relations:
(n ET 2) (Cs, = e " 1 (5)
(n — 1) n
) ub y +
uh = [(
