IEEE
TRANSACTIONS
ON
PATTERN
ANALYSIS
AND
MACHINE
INTELLIGENCE,
VOL.
PAMI-7,
NO.
2,
MARCH
1985
SC
Li
1LL11,e
(roiv)
X
I
2D
N
IsfWrch
plane
N
Fig.
4.
3D
search
space
for
intra-
and
inter-scanline
search.
This
may
be
viewed
as
a
rectangular
solid
seen
from
above.
The
side
faces
cor-
respond
to
the
right
and
left
stereo
images.
Connected
edges
in
each
image
form
sets
of
intersections
(nodes)
in
this
space.
Each
set
is
called
a
3D
node.
Selection
of
a
set
of
paths
is
done
at
every
3D
node.
Fig.
5.
Connected
edge
u
1
is
on
the
left
of
U2.
puted
based
on
the
cost
obtained
by
the
intra-scanline
search
on
each
2D
search
plane.
This
leads
to
the
following
condi-
tion:
When
we
examine
the
correspondence
of
two
3D
nodes
(i.e.,
two
connected
edges),
one
in
the
right
and
one
in
the
left
image,
the
connected
edges
which
are
on
the
left
of
these
two
connected
edges
in
each
image
must
already
be
processed.
A
connected
edge
ul
is
said
to
be
on
the
left
of
u2,
if
all
the
edges
in
ul
are
on
the
left
of
those
in
u2
on
the
scanlines
which
u1
and
U2
share.
The
"left-of"
relationship
is
transitive;
if
there
is
a
connected
edge
U3
and
u1
is
on
the
left
of
U3
and
U3
is
on
the
left
of
u2,
then
ul
is
on
the
left
of
u2
(if
u1
and
u2
share
any
scanlines).
Fig.
5
illustrates
this
concept.
The
order
of
two
connected
edges
which
do
not
satisfy
both
the
relations
in
Fig.
5
may
be
arbitrarily
specified.
We
assign
an
ordering
index
from
left
to
right
for
every
connected
edge
in
an
image.
This
ordering
is
possible
without
contradiction
when
a
connected
edge
never
crosses
a
scanline
more
than
once
and
when
two
connected
edges
never
intersect
each
other.
Our
edge-linking
process
which
will
be
explained
in
Section
IV
is
devised
so
that
it
does
not
produce
such
cases.
Now
we
will
present
how
the
cost
of
a
3D
path
is
defined.
Suppose
we
assign
indexes
[0:
U]
to
connected
edges
in
the
right
image,
and
[0:
V]
in
the
left.
The
left
and
right
ends
of
an
image
are
treated
as
connected
edges
for
convenience:
the
left
ends
are
assigned
index
0.
Let
u
=
(u,
v)
be
a
3D
node
made
by
a
connected
edge
u
in
the
right
image
and
a
con-
nected
edge
v
in
the
left
image.
Let
C(u)
be
the
cost
of
the
optimal
set
of
paths
which
reach
to
the
3D
node
u.
The
cost
C(u)
is
computed
as
follows:
e(u)
C(u)
=
min
£
{D(I(u;
t),
I(u
-
i(t);
t);
t
{i}
t
=
s(u)
+
C(u
-
i(t);
t)}
C(O)
=
O,
i.e.,
C(O;
t)
=
0
for
all
t
where u
=
(u,
v),
i(t)
=
(i(t),
j(t)),
O
i(t)
<
u,
O
-<
j(t)
-<
v,
i(t)
+
j(t)
*
O.
(2)
Here,
C(u;
t)
is
the
cost
of
the
path
on
scanline
t
in
the
optimal
set;
that
is,
C(u)
=
et(=U),(u)
C(u;
t),
and
D(m,
k;
t)
is
the
cost
of
the
optimal
3D
primitive
path
from
node
k
to
node
m
on
the
2D
plane
for
scanline
t.
A
3D
primitive
path
is
a
partial
path
between
two
3D
nodes
on
a
2D
search
plane
and
it
has
no
vertices
at
the
nodes
belonging
to
a
3D
node.
So
a
3D
primi-
tive
path
is
a
chain
of
2D
primitive
paths
and
an
intra-scanline
search
is
necessary
to
obtain
the
optimal
3D
primitive
path
on
a
2D
plane
between
two
given
3D
nodes.
The
function
I(u;
t)
gives
the
index
of
a
2D
node
belonging
to
the
3D
node
u
for
scanline
t.
The
numbers
s(u)
and
e(u)
specify
respectively
the
starting
and
ending
scanlines
between
which
the
3D
node
u
exists.
The
cost
C(u)
is
minimized
on
the
function
i(t).
A
3D
node
u
-
i(t)
gives
the
start
node
of
the
3D
primitive
path
on
scanline
t.
The
inter-scanline
constraint
is
represented
by
i(t).
For
example,
if
i(t)
is
independent
of
i(t
-
1),
there
are
no
constraints
between
scanlines
and
the
search
represented
by
(2)
becomes
equivalent
to
a
set
of
intra-scanline
searches
which
are
performed
independently
on
each
scanline.
Intui-
tively,
i(t)
must
be
equal
to
i(t
-
1)
in
order
to
keep
the
con-
sistency
constraint.
The
iteration
starts
at
u
=
(0,
0)
and
computes
C(u)
for
each
3D
node
u
in
ascending
order
of
u.
At
each
3D
node
the
i(t)'s
which
give
the
minimum
are
recorded.
The
sequence
of
2D
primitive
paths
which
forms
the
3D
primitive
path
is
also
re-
corded
on
each
scanline.
The
set
of
paths
which
gives
C(U)
at
the
3D
node
U
=
(U,
V)
(which
is
the
3D
node
formed
by
the
right
ends
of
stereo
images)
is
obtained
as
the
optimal
set.
It
should
be
noted
that
when
there
are
no
connected
edges
except
for
the
right
and
left
sides
of
the
images,
the
algorithm
(2)
works
as
a
set
of
intra-scanline
searches
repeated
on
each
scanline
independently.
In
this
sense,
the
3D
algorithm
com-
pletely
contains
the
2D
one.
D.
Computational
Cost
for
Inter-Scanline
Search
The
number
of
2D
primitive
paths
which
should
be
exam-
ined
in
the
3D
search
space
to
compute
C(U)
by
(2)
can
be
estimated
to
be
O(TU2
V2M2N2),
where
T
stands
for
the
number
of
scanlines
in
the
images,
U
and
V
are
for
the
num-
bers
of
connected
edges
in
the
right
and
left
images,
and
M
and
N
for
the
(average)
numbers
of
edge
points
in
one
scanline
in
the
right
and
left
images,
respectively.
This
estimate
is
ob-
tained
as
follows:
the
number
of
3D
nodes
in
the
search
space
is
O(UV),
at
each
3D
node
we
should
examine
O(UV)
sets
of
3D
primitive
paths,
each
set
has
O(T)
paths,
and
each
3D
142
剩余15页未读，继续阅读
xuxinyan2012
- 粉丝: 0
- 资源: 2
我的内容管理
展开
最新资源
- AirKiss技术详解：无线传递信息与智能家居连接
- Hibernate主键生成策略详解
- 操作系统实验：位示图法管理磁盘空闲空间
- JSON详解：数据交换的主流格式
- Win7安装Ubuntu双系统详细指南
- FPGA内部结构与工作原理探索
- 信用评分模型解析：WOE、IV与ROC
- 使用LVS+Keepalived构建高可用负载均衡集群
- 微信小程序驱动餐饮与服装业创新转型：便捷管理与低成本优势
- 机器学习入门指南：从基础到进阶
- 解决Win7 IIS配置错误500.22与0x80070032
- SQL-DFS：优化HDFS小文件存储的解决方案
- Hadoop、Hbase、Spark环境部署与主机配置详解
- Kisso：加密会话Cookie实现的单点登录SSO
- OpenCV读取与拼接多幅图像教程
- QT实战：轻松生成与解析JSON数据
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
