wards automatic 
small houses and 
base (maps). The 
her investigation 
ination condition 
‚ (3) the capacity 
mization method 
thod for optimal 
rch method. The 
id approximately 
ition methods to 
ition of regional 
has been applied 
x buildings with 
is, illumination 
y of imagery and 
iderable position 
>d map. Third is 
ly-built buildings. 
gnition accuracy, 
| method which 
first step is the 
rial optimization 
on so as to solve 
ep is the newly- 
ptimal building 
] third problems. 
p-based building 
Extended from 
  
the previous method 
/ Step 2: 
Newly-built 
building extraction 
  
  
  
  
   
  
isting 
ilding 
   
  
building 
  
ction database 
ding change 
By matching and comparing imagery with maps to 
automatically identify a building status on maps as "existing", 
"changed (demolished and need to re-examine)" or "newly- 
built", this method realizes a service which provide "building 
change detection information" to users. The service named 
"HouseDiff" allows users to investigate only the parts of 
imagery that are most likely changed, which will lead to the 
reduction of cost and labour. 
The remainder of this paper will focus on the two steps 
extended from the previous method (Ogawa et al, 1999), which 
are, the building recognition (Step 1) in chapter 2, and the 
newly-built building extraction (Step 2) in chapter 3. Chapter 4 
provides the experimental results that demonstrate the validity 
of the proposed method and discussion. Finally, chapter 5 gives 
a conclusion. 
2. BUILDING RECOGNITION 
The first step is the building recognition. It determines whether 
the buildings still exist by matching the new imagery and the 
old map. This step focuses on the boundaries of buildings to 
evaluate the difference between imagery and maps. The 
boundaries can be extracted effectively if map figures are 
utilized as a guide of those presence, position, and direction. 
We regard the building boundary extraction as a combinatorial 
optimization problem of light-dark and dark-light edge 
segments along the building map figure using graph theory 
known as the shortest path search method. The shortest path is 
calculated by Dijkstra method using weighted undirected graph 
of edge segments. The evaluation of the difference between 
imagery and map figures is done by an energy cost of the 
shortest path search calculation considering the edge quality 
information (i.e. distance from map figure line, edge power, 
edge continuity, and edge presence). The optimization method 
allows to resolve the large and complex combinatorial problem 
and to extract the optimal boundaries with the acceptable 
position error and various types of target buildings (i.e. 
brighter than background, darker than background, and its 
à 225 degrees direction 
End edge extraction filter 
    
=== Building polygon POLYGONij 
<= Target polyline POLYLINEijk «= Light-dark edge segment 
zm Dark-light edge segment 
[—] Edge search range 
combination). Furthermore, it becomes possible to extract a 
building with weak boundaries due to similar materials of roof 
and background, and partly occluded by trees. 
Figure 2 and 3 show the algorithm outlines. Figure 4 shows an 
example of results that confirmed the validity of this algorithm. 
  
  
begin 
Step 1.1: Edge segments graph construction 
(a) For each parcel PARCELi in the map; For each building 
polygon POLYGONij in the parcel; For each polyline 
POLYLINEijk in the building polygon; 
(b) Extract candidate edge segments along the polyline 
(c) Extract vector data (both end point) for each edge 
segment, and calculate its weight (equation (1)) 
(d) Construct a weighted undirected graph of edge segments 
(e) Add virtual links to the graph to connect all edge 
segments, and calculate those weight (equation (1)) with 
penalty factor (weighted twice) 
Step 1.2: Optimal building boundary extraction 
(a) Search the shortest path from POLYLINEijk start point to 
POLYLINEijk end point using the weighted undirected graph 
by Dijkstra method (combinatorial optimization of edge 
segments by minimizing energy cost) 
Step 1.3: Change detection by edge quality evaluation 
(a) Calculate the edge quality evaluated value EdgeValue of 
each optimal building boundary (equation (2)) 
(b) Calculate the edge quality evaluated value EdgeValueAll 
of whole building by a linear weighted combination of 
EdgeValues (equation (3)) 
(c) Evaluate the EdgeValueAll and detect the change 
(equation (4)) 
(d) Output the detected change information (demolished, 
need to re-examine) 
end 
  
Figure 2. Optimal building boundary extraction algorithm 
     
  
LineLength 
LineLength : Length of target polyline 
l; : Length of light-dark edge segment 
l; : Length of dark-light edge segment 
pl, : Projected length of light-dark edge segment 
Virtual link between edge segments Optimal edge path(incl. virtuallink)  p/, : Projected length of dark-light edge segment 
Step 1.1: Edge segments graph 
Step 1.2: Optimal building boundary Step 1.3: Change detection by edge quality evaluation 
construction extraction 
Figure 3. Optimal building boundary extraction