光束平差法：现代综合理论

需积分: 10 128 浏览量更新于2024-07-14 收藏 881KB PDF 举报

"Bundle Adjustment：A Modern Synthesis" 是一篇由 Bill Triggs, Philip McLauchlan, Richard Hartley 和 Andrew Fitzgibbon 合著的关于光束平差法的综述性文章，收录在 Vision Algorithms: Theory and Practice 的文集中，出版于2000年，属于 Springer-Verlag 出版社的 Lecture Notes in Computer Science (LNCS) 系列，文献标识号为 10.1007/3-540-44480-7_21。光束平差法（Bundle Adjustment）是计算机视觉领域中的一个核心概念，主要用于优化多视图几何中的参数估计问题。该方法旨在同时校正相机参数和场景三维结构，以最小化图像中特征点的重投影误差。这一过程涉及对大量图像对应关系的处理，通常是在估计相机姿态和重建三维几何形状时使用。在文章中，作者们对光束平差法进行了全面的分析和综合，讨论了其理论基础、优化算法以及在实际应用中的挑战。他们回顾了光束平差的历史发展，解释了基本的数学模型，包括相机模型、投影方程以及误差度量。同时，文章还涵盖了不同的优化策略，如非线性最小二乘法（Levenberg-Marquardt 算法）和基于梯度下降的方法。光束平差法的基本思想是通过调整相机参数（如内参、外参）和场景点坐标，使得所有视图中特征点的重投影误差平方和最小。在实际操作中，这通常表现为一个大规模的非线性优化问题，因为涉及到大量的未知参数和观测数据。因此，文章可能还会讨论有效的数值求解技术，如稀疏矩阵求解器和迭代简化等策略，以提高计算效率和结果的精度。此外，作者可能会探讨光束平差在实际应用中的扩展，例如大规模场景重建、SLAM（Simultaneous Localization And Mapping）系统、机器人导航等领域，并给出相应的实例和实验结果，展示光束平差在解决实际问题中的效能和实用性。 "Bundle Adjustment：A Modern Synthesis" 是一篇深入探讨光束平差法的学术论文，不仅提供了理论基础，还涵盖了实际应用和技术细节，对于理解并实施计算机视觉中的多视图几何问题具有重要参考价值。

linear, least squares gives the Best Linear Unbiased Estimator (BLUE), where ‘best’ means minimum

variance

Any weighted least squares model can be converted to an unweighted one (W

= 1) by pre-

multiplying z

, z

, 4z

by any L

satisfying W

= L

. Such an L

can be calculated efﬁciently

from W

or W

−1

using Cholesky decomposition (§B.1).

= L

is called a standardized

residual, and the resulting unweighted least squares problem min

(x)k

is said to be in

standard form. One advantage of this is that optimization methods based on linear least squares

solvers can be used in place of ones based on linear (normal) equation solvers, which allows ill-

conditioned problems to be handled more stably (§B.2).

Another peculiarity of the SSE cost function is its indifference to the natural boundaries between

the observations. If observations z

from any sources are assembled into a compound observation

vector z

≡ (z

, . . . , z

)

, and their weight matrices W

are assembled into compound block diagonal

weight matrix W ≡ diag(W

, . . . , W

), the weighted squared error f(x) ≡

4z(x)

W 4z(x) is

the same as the original SSE cost function,

(x)

(x). The general quadratic form of

the SSE cost is preserved under such compounding, and also under arbitrary linear transformations

of z

that mix components from different observations. The only place that the underlying structure

is visible is in the block structure of W. Such invariances do not hold for essentially any other cost

function, but they simplify the formulation of least squares considerably.

3.3 Robustiﬁed Least Squares

The main problem with least squares is its high sensitivity to outliers. This happens because the

Gaussian has extremely small tails compared to most real measurement error distributions. For robust

estimates, we must choose a more realistic likelihood model (§3.1). The exact functional form is

less important than the general way in which the expected types of outliers enter. A single blunder

such as a correspondence error may affect one or a few of the observations, but it will usually leave

all of the others unchanged. This locality is the whole basis of robustiﬁcation. If we can decide

which observations were affected, we can down-weight or eliminate them and use the remaining

observations for the parameter estimates as usual. If all of the observations had been affected about

equally (e.g. as by an incorrect projection model), we might still know that something was wrong, but

not be able to ﬁx it by simple data cleaning.

We will adopt a ‘single layer’ robustness model, in which the observations are partitioned into

independent groups z

, each group being irreducible in the sense that it is accepted, down-weighted

or rejected as a whole, independently of all the other groups. The partitions should reﬂect the types

of blunders that occur. For example, if feature correspondence errors are the most common blunders,

the two coordinates of a single image point would naturally form a group as both would usually be

invalidated by such a blunder, while no other image point would be affected. Even if one of the co-

ordinates appeared to be correct, if the other were incorrect we would usually want to discard both

for safety. On the other hand, in stereo problems, the four coordinates of each pair of correspond-

ing image points might be a more natural grouping, as a point in one image is useless without its

correspondent in the other one.

Henceforth, when we say observation we mean irreducible group of observations treated as a

unit by the robustifying model. I.e., our observations need not be scalars, but they must be units,

probabilistically independent of one another irrespective of whether they are inliers or outliers.

It may be possible (and even useful) to do better with either biased (towards the correct solution), or nonlinear estima-

tors.

As usual, each independent observation z

contributes an independent term f

(x |z

) to the total

cost function. This could have more or less any form, depending on the expected total distribution of

inliers and outliers for the observation. One very natural family are the radial distributions, which

have negative log likelihoods of the form:

(x) ≡

( 4z

(x)

(x) ) (3)

Here, ρ

(s) can be any increasing function with ρ

(0) = 0 and

(0) = 1. (These guarantee that

at 4z

= 0, f vanishes and

= W

). Weighted SSE has ρ

(s) = s, while more robust variants

have sublinear ρ

, often tending to a constant at ∞ so that distant outliers are entirely ignored. The

dispersion matrix W

−1

determines the spatial spread of z

, and up to scale its covariance (if this is

ﬁnite). The radial form is preserved under arbitrary afﬁne transformations of z

, so within a group,

all of the observations are on an equal footing in the same sense as in least squares. However, non-

Gaussian radial distributions are almost never separable: the observations in z

can neither be split

into independent subgroups, nor combined into larger groups, without destroying the radial form.

Radial cost models do not have the remarkable isotropy of non-robust SSE, but this is exactly what

we wanted, as it ensures that all observations in a group will be either left alone, or down-weighted

together.

As an example of this, for image features polluted with occasional large outliers caused by cor-

respondence errors, we might model the error distribution as a Gaussian central peak plus a uni-

form background of outliers. This would give negative log likelihood contributions of the form

f(x) = −log



exp(−

) + 



instead of the non-robust weighted SSE model f(x) =

, where

= 4x

is the squared weighted residual error (which is a χ

variable for a correct

model and Gaussian error distribution), and  parametrizes the frequency of outliers.

-10 -5 0 5 10

Gaussian -log likelihood

Robustified -log likelihood

3.4 Intensity-based methods

The above models apply not only to geometric image features, but also to intensity-based matching of

image patches. In this case, the observables are image gray-scales or colors I rather than feature co-

ordinates u, and the error model is based on intensity residuals. To get from a point projection model

u = u(x) to an intensity based one, we simply compose with the assumed local intensity model

I = I(u) (e.g. obtained from an image template or another image that we are matching against),

premultiply point Jacobians by point-to-intensity Jacobians

, etc. The full range of intensity mod-

els can be implemented within this framework: pure translation, afﬁne, quadratic or homographic

patch deformation models, 3D model based intensity predictions, coupled afﬁne or spline patches for

surface coverage, etc., [1, 52, 55, 9, 110, 94, 53, 97, 76, 104, 102]. The structure of intensity based

bundle problems is very similar to that of feature based ones, so all of the techniques studied below

can be applied.

We will not go into more detail on intensity matching, except to note that it is the real basis

of feature based methods. Feature detectors are optimized for detection not localization. To lo-

calize a detected feature accurately we need to match (some function of) the image intensities in

its region against either an idealized template or another image of the feature, using an appropri-

ate geometric deformation model, etc. For example, suppose that the intensity matching model is

f(u) =

ρ(kδI(u)k

) where the integration is over some image patch, δI is the current intensity

prediction error, u parametrizes the local geometry (patch translation & warping), and ρ(·) is some

intensity error robustiﬁer. Then the cost gradient in terms of u is g

δI

. Similarly,

the cost Hessian in u in a Gauss-Newton approximation is H

≈

(

)

. In a feature

based model, we express u = u(x) as a function of the bundle parameters, so if J

we have

a corresponding cost gradient and Hessian contribution g

= g

and H

= J

. In other

words, the intensity matching model is locally equivalent to a quadratic feature matching one on the

‘features’ u(x), with effective weight (inverse covariance) matrix W

= H

. All image feature error

models in vision are ultimately based on such an underlying intensity matching model. As feature

covariances are a function of intensity gradients

(

)

, they can be both highly variable be-

tween features (depending on how much local gradient there is), and highly anisotropic (depending

on how directional the gradients are). E.g., for points along a 1D intensity edge, the uncertainty is

large in the along edge direction and small in the across edge one.

3.5 Implicit models

Sometimes observations are most naturally expressed in terms of an implicit observation-constraining

model h(x, z) = 0, rather than an explicit observation-predicting one z = z(x). (The associated

image error still has the form f(z

− z)). For example, if the model is a 3D curve and we observe

points on it (the noisy images of 3D points that may lie anywhere along the 3D curve), we can

predict the whole image curve, but not the exact position of each observation along it. We only have

the constraint that the noiseless image of the observed point would lie on the noiseless image of the

curve, if we knew these. There are basically two ways to handle implicit models: nuisance parameters

and reduction.

Nuisance parameters: In this approach, the model is made explicit by adding additional ‘nuisance’

parameters representing something equivalent to model-consistent estimates of the unknown noise

free observations, i.e. to z with h(x, z) = 0. The most direct way to do this is to include the entire

parameter vector z as nuisance parameters, so that we have to solve a constrained optimization prob-

lem on the extended parameter space (x, z), minimizing f(z − z) over (x, z) subject to h(x, z) = 0.

This is a sparse constrained problem, which can be solved efﬁciently using sparse matrix techniques

(§6.3). In fact, for image observations, the subproblems in z (optimizing f(z − z) over z for ﬁxed z

and x) are small and for typical f rather simple. So in spite of the extra parameters z, optimizing this

model is not signiﬁcantly more expensive than optimizing an explicit one z = z(x) [14, 13, 105, 106].

For example, when estimating matching constraints between image pairs or triplets [60, 62], instead

of using an explicit 3D representation, pairs or triplets of corresponding image points can be used as

features z

, subject to the epipolar or trifocal geometry contained in x [105, 106].

However, if a smaller nuisance parameter vector than z can be found, it is wise to use it. In the

case of a curve, it sufﬁces to include just one nuisance parameter per observation, saying where along

the curve the corresponding noise free observation is predicted to lie. This model exactly satisﬁes the

constraints, so it converts the implicit model to an unconstrained explicit one z = z(x, λ), where λ

are the along-curve nuisance parameters.

The advantage of the nuisance parameter approach is that it gives the exact optimal parameter

estimate for x, and jointly, optimal x-consistent estimates for the noise free observations z.

Reduction: Alternatively, we can regard h(x, z) rather than z as the observation vector, and hence

ﬁt the parameters to the explicit log likelihood model for h(x, z). To do this, we must transfer the

underlying error model / distribution f(4z) on z to one f(h) on h(x, z). In principle, this should be

done by marginalization: the density for h is given by integrating that for 4z over all 4z giving the

same h. Within the point estimation framework, it can be approximated by replacing the integration

with maximization. Neither calculation is easy in general, but in the asymptotic limit where ﬁrst

order Taylor expansion h(x, z) = h(x, z + 4z) ≈ 0 +

4z is valid, the distribution of h is a

marginalization or maximization of that of 4z over afﬁne subspaces. This can be evaluated in closed

form for some robust distributions. Also, standard covariance propagation gives (more precisely, this

applies to the h and 4z dispersions):

hh(x, z)i ≈ 0 , hh(x, z) h(x, z)

i ≈

h4z 4z

−1

(4)

where W

−1

is the covariance of 4z. So at least for an outlier-free Gaussian model, the reduced

distribution remains Gaussian (albeit with x-dependent covariance).

4 Basic Numerical Optimization

Having chosen a suitable model quality metric, we must optimize it. This section gives a very rapid

sketch of the basic local optimization methods for differentiable functions. See [29, 93, 42] for more

details. We need to minimize a cost function f(x) over parameters x, starting from some given initial

estimate x of the minimum, presumably supplied by some approximate visual reconstruction method

or prior knowledge of the approximate situation. As in §2.2, the parameter space may be nonlinear,

but we assume that local displacements can be parametrized by a local coordinate system / vector of

free parameters δx. We try to ﬁnd a displacement x → x+δx that locally minimizes or at least reduces

the cost function. Real cost functions are too complicated to minimize in closed form, so instead we

minimize an approximate local model for the function, e.g. based on Taylor expansion or some other

approximation at the current point x. Although this does not usually give the exact minimum, with

luck it will improve on the initial parameter estimate and allow us to iterate to convergence. The art

of reliable optimization is largely in the details that make this happen even without luck: which local

model, how to minimize it, how to ensure that the estimate is improved, and how to decide when

convergence has occurred. If you not are interested in such subjects, use a professionally designed

package (§C.2): details are important here.

4.1 Second Order Methods

The reference for all local models is the quadratic Taylor series one:

f(x + δx) ≈ f(x) + g

δx +

δx

H δx g ≡

(x) H ≡

(x)

quadratic local model gradient vector Hessian matrix

(5)

For now, assume that the Hessian H is positive deﬁnite (but see below and §9). The local model is

then a simple quadratic with a unique global minimum, which can be found explicitly using linear

剩余71页未读，继续阅读

yyw213321

粉丝: 0
资源: 7

光束平差法：现代综合理论

Bundle Adjustment —A Modern Synthesis（全部文档）

BUNDLE ADJUSTMENT RULES

Bundle Adjustment —A Modern Synthesis

使用nerf进行三维重建，如何进行bundle adjustment

python 实现Bundle Adjustment算法

bundle adjustment 玩具程序

Can not parse this input:{"path":"Animations/Player/Left","__requestType__":"path","bundle":"","preset":"default","priority":0}

使用matlab语言，实现一个使用梯度下降法的bundle adjustment

Bundle Adjustment算法的详细介绍

ios获取bundleid

最新资源

Can not parse this input:{"path":"Animations/Player/Left","requestType":"path","bundle":"","preset":"default","priority":0}