International Archives of Photogrammetry and Remote Sensing. Vol. XXXII, Part 5. Hakodate 1998 
A TRACKER 
FOR BROKEN AND CLOSELY-SPACED LINES 
Naoki CHIBA 
Chief Researcher, 
Mechatronics Research Center, 
SANYO Electric Co., Ltd., JAPAN 
chiba@mech.rd.sanyo.co.jp 
Takeo KANADE 
Professor, 
School of Computer Science, 
Carnegie Mellon University, USA 
tk@cs.cmu.edu 
Commission V, Working Group IC V/III 
KEY WORDS: Line Tracking, Motion Estimation, Optical Flow, Morphology, Shape Recovery 
ABSTRACT 
We propose an automatic line tracking method which is robust in tracking broken and closely-spaced line segments over 
an image sequence. The method uses both the grey-level information of original images and the geometric attributes 
of line segments. 
By using a hierarchical optical-flow estimation technique, we can obtain a good prediction of line segment motion in a 
consecutive frame. There remains the need to distinguish closely-spaced lines which are common in man-made objects. 
Discrimination of these lines is achieved by use of a direction attribute rather than an orientation attribute. Due to 
line extraction problems, a single line segment may be broken into several segments. A proposed matching similarity 
function enables us to perform multiple collinear-line segment matching, instead of merely one-to-one matching. 
Experiments using noisy and complicated real image sequences taken with a hand-held camcorder confirm the robustness 
of our method in difficult tasks. 
1. INTRODUCTION 
Automatic line segment tracking through an image se- 
quence is a difficult problem in motion estimation for two 
reasons. First, due to the difficulty in edge extraction, 
the extracted end points of each line segment are not re- 
liable. Furthermore, a single line segment may be broken 
into multiple line segments over image frames. Second, 
when line segments are very closely spaced, it is hard to 
track and distinguish one line segment from another be- 
cause they have similar orientations. 
The procedure for line tracking typically consists of 
two steps: a prediction step and a matching step. There 
are two popular prediction techniques: Kalman filter- 
based prediction [4], and methods that apply epipolar 
constraints for prediction [1, 11]. Kalman filter-based 
techniques have two main problems: First, they take sev- 
eral frames to obtain reliable results. Second, they have 
difficulty in setting up the uncertainties for the segment 
tracking, which is usually tuned by hand. For these rea- 
sons they can track only simple objects or scenes on a long 
image sequence. The problem of using epipolar constraint 
is that it requires camera calibration or a good method to 
obtain from unknown motion, which is usually sensitive 
to noise. 
For the matching step, several attributes of each line 
segment have been introduced [7, 3]. They include the 
end points and the orientation of each line, as well as 
the distance and the overlapping length between line seg- 
ments. However, these methods are easily confused when 
676 
the input consists of closely-spaced line segments, which 
is common in a scene with man-made objects. They are 
also unable to deal with broken line segments. 
We propose a new line tracking method that predicts 
the motion of line segments reliably based on our hi- 
erarchical optical-flow estimation, discriminates closely- 
spaced line segments accurately by comparing the line 
directions, and matches multiple collinear line segments 
by using our similarity function. 
There have been many approaches to optical flow es- 
timation reviewed in [2]. However, there remains one big 
problem: these techniques cannot handle insufficiently 
textured areas. We solve the problem by using a sim- 
ple filling operation. Even when line motion prediction is 
reliable, it is hard to distinguish closely-spaced lines. We 
introduce a line direction attribute obtained at the edge 
extraction stage. While many matching functions have 
already been introduced [3, 4, 7, 11], very few of them 
deal with multiple line segments that are broken over an 
image sequence due to the problem of edge extraction. 
We propose a simple and expandable similarity function 
to track collinear multiple line segments. 
Our method is robust enough to handle real world 
image sequences taken with a hand-held camcorder. It 
can be used to provide line correspondences over an image 
sequence for recovering the shape of a man-made object 
with line features, such as buildings or an indoor view of 
a room. 
1.1 | 
Our p 
Lucas. 
tend i 
in sec 
we us 
preser 
sectio 
resear 
1.2 : 
Lines 
ing tk 
extra 
olding 
segme 
2. 
Asa 
ment 
based 
use a 
errors 
lem v 
2.1 
The 1 
estim 
plem 
track 
three 
y as 
boun 
assur 
prop 
T 
ing p 
Then 
follov 
wher 
the c 
2.2 
The 
Luca 
moti 
prox 
can 
lem 
not « 
flow 
mult