3D点云处理：空间中曲线与曲面的最佳拟合算法

需积分: 3 70 浏览量更新于2024-07-18 收藏 3.37MB PDF 举报

"Least Squares Orthogonal Distance Fitting of Curves and Surfaces in Space" 是一本专注于三维空间中曲线和曲面最小二乘正交距离拟合技术的书籍。作者Sung Joon Ahn在Fraunhofer IPA开发了一款高效软件，用于自动识别和处理3-D点云中的几何原形单元，如平面、球体、圆柱、圆锥和圆环。在当前不断发展的传感器技术背景下，3-D相机的应用越来越广泛，特别是在机器人、快速产品开发和数字工厂等领域。这些相机能够迅速生成大量的测量点数据。为了有效地处理这些3-D信息，并从点云中识别和理解三维物体模型，以便进一步在CAD系统中进行处理，需要稳定且高效的算法。本书详细阐述了用于空间中一般曲线和曲面的“最佳拟合”算法集合，这些算法在Fraunhofer软件中被实际应用。 “ODF”（Orthogonal Distance Fitting）是书中的核心概念，它是一种优化方法，通过最小化数据点到拟合曲线或曲面的正交距离来寻找最佳拟合模型。这种方法在处理噪声数据和不精确测量时特别有用，因为它考虑了实际测量中的误差，并试图找到一个与所有数据点正交距离最短的几何对象。书中内容可能涵盖了以下知识点： 1. 最小二乘法：这是一种常见的数学优化技术，用于找到一组参数，使得数据点到模型的残差平方和最小。 2. 正交距离：衡量实际数据点与拟合曲线或曲面之间的垂直距离，是评估拟合质量的关键指标。 3. 曲线和曲面拟合：包括线性、二次和其他复杂几何形状的拟合，以及针对不同几何实体（如平面、球面、圆柱面等）的专用拟合算法。 4. 误差分析：讨论拟合过程中可能出现的误差类型，如随机误差和系统误差，以及如何通过正交距离拟合来减小它们的影响。 5. 自动识别：描述了如何利用这些算法自动识别3-D点云中的几何特征。 6. 计算效率：强调算法的计算复杂性和效率，这对于实时处理大量3-D数据至关重要。 7. 实际应用：书中可能包含应用案例，展示如何将这些技术应用于机器人导航、产品设计和制造过程的自动化。这本书对于理解和应用3-D信息处理，特别是对从3-D点云数据中提取几何结构的工程人员和研究人员来说，是一份宝贵的资源。通过深入研究最小二乘正交距离拟合，读者可以掌握处理和分析三维数据的关键技术，从而在各种领域实现更精准的模型构建和数据分析。

XVIII List of Symbols

Δ : difference, update.

: transpose a vector/matrix.

f(·),F(·),G(·) : functions.

O(·) : computing complexity or storage space usage.

sign(·) : sign of a number.

tr(·) : trace of a matrix.

R : real number ﬁeld.

: n-dimensional real number space.

S : set of points.

xyz : moving (model) coordinate system.

XYZ : reference (machine) coordinate system.

Variables and parameters

l : number of form parameters.

m : number of data points.

n : dimensional degree of data points.

o : order of polynomials.

p : number of model parameters, p = l + n + s .

Also, index of power norm, e.g. L

-norm.

q : number of constraints.

s : number of rotation parameters.

,...,a

: form parameters of a model feature.

: position (translation) parameters of a model feature.

ω, ϕ, κ : rotation parameters (Euler angles) o f a model feature.

u, v : point location parameters for parametric features.



: location p arameters of the minimum distance point x



on a parametric feature from the given point x

Cor(ˆa

, ˆa

) : correlation coefﬁcient of the two estimated parameters ˆa

and ˆa

Cov(ˆa

, ˆa

) : covariance between the two estimated parameters ˆa

and ˆa

: distance between the two points X

and X



, d

=  X

− X



 .

t : safety margin for segmentation of point cloud. Also, computing time.

w, w

: (constraint) weighting values.

,...,w

: singular values of a matrix extracted by the SVD,

W =[diag(w

,...,w

)] .

α : step size factor for parameter update, e.g. a

k+1

= a

+ αΔa .

λ : Adding factor with the Levenberg-Marquardt algorithm.

Also, Lagrangian multiplier.

: square sum of (weighted) distance errors.



i=1

or σ

 Pd

or σ

 P(X − X



)

rms

: rms distance error, σ

rms



/m .

List of Symbols XIX

Vectors and vector functions

∇ : gradient operator,

∇  (∂/∂x)

=(∇

, ∇

)

=(∂/∂x,∂/∂y,∂/∂z)

a : model parameter vector, a

 (a

, a

)=(a

,...,a

) .

ˆa : estimated model parameter vector.

: form parameter vector, a

 (a

,...,a

) .

: position parameter vector, a

 X

=(X

) .

: rotation parameter vector, a

 (ω,ϕ,κ) .

b : special parameter vector for parametric features, b

 (a

, u

,...,u

) .

Also, algebraic parameter vector for algebraic features,

 (b

,...,b

) with p = number of algebraic parameters.

d : distance column vector, d  (d

,...,d

)

with d

= X

− X



 .

f (·) : function vector.

n : normal vector.

, r

: direction cosine vector of the x-, y- and z-axis, respectively.

u : location parameter vector for parametric features, u =(u, v)



: location parameter vector of the minimum distance point x



on a parametric feature from the given point x

, u



=(u



)

, x

: partial derivatives of x(a

, u) .

= ∂x/∂u , x

= ∂

x/∂u∂u , x

= ∂

x/∂u∂v ,etc.

x, X : general coordinate vector for a point in frame xyz and XYZ, respectively.

x =(x, y, z)

, X =(X, Y, Z)

, x = R(X − X

) .

Also, coordinate column vector, X

 (X

,...,X

) .



: coordinate column vector, X

T

 (X

T

,...,X

T

) .

, X

: coordinate vector of a g iven point in frame xyz and XYZ, respectively.

=(x

)

, X

=(X

)



, X



: coordinate vector of the minimum distance point on a model

feature from the given point x

and X

, respectively.



=(x



)

, X



=(X



)

: origin of the model coordinate frame xyz referenced to

the machine coordinate frame XYZ, X

=(X

)

X : coordinate vector of the mass center of {X

}

i=1

X =



i=1

Matrices

Cor(ˆa) : correlation matrix of the estimated model parameters ˆa .

Cov(ˆa) : covariance matrix of the estimated model parameters ˆa .

FHG matrix : Vector and matrix group of ∇f , H = ∂

f/∂x∂x and G

derived from implicit feature equatio n f(a

, x)=0.

XHG matrix : Vector and matrix group of ∂x/∂u , H = ∂

x/∂u∂u and G

derived from parametric feature description x(a

, u) .

G : special matrix deﬁned in Sect. 3.2.2 for implicit features or

in Sect. 4.2.3 for parametric features.

H : Hessian matrix. H = ∂

f/∂x∂x or H = ∂

x/∂u∂u .

Also, inertia tensor of centroidal moment of a point set.

1. Introduction

The parametric model description of real objects is a subject relevant to coordinate

metrology, reverse engineering, and computer/machine vision, with which objects

are represented by their model parameters estimated from the measurement data

(object reconstruction, Fig. 1.1). The parametric model description has a wide range

of application ﬁelds, e.g. manufacturing engineering, particle physics, and the en-

tertainment industry. The alternative to parametric model description is facet model

description that describes objects by using the polygonal mesh generated from a

point cloud. Although the facet model description is adequate for object visualiza-

tion and laser lithography, it does not provide applications with such object model

information as shape, size, position, and rotation of the object. The facet model de-

scription has a limited accuracy in representing an object and demands considerable

data memory space. For a faithful representation of objects using a polygonal mesh,

a dense point cloud should be available as input data.

On the other hand, the parametric model description provides applications with

highly compact and effective information about the object. The minimum number of

the data points required for estimating model parameters is usually about the same

as the number of model parameters. The data reduction ratio from a dense point

cloud to the parametric model description is usually to the order of one thousandth.

The parametric model description is preferred by most applications because of its

usability and ﬂexibility. For certain applications, such as in coordinate metrology

and motion analysis, only the parametric model description is of real interest. If a

real object can once be represented by its model parameters, the parametric model

description can then be converted or exported to other formats including the facet

model description (product data exchange [59]). The disadvantage of the parametric

model description is the analytical and computational difﬁculties encountered in

estimating the model parameters of real objects from their measurement data (point

cloud).

This work aims at using the parametric model description for reconstructing

real objects from their measurement points. The overall procedures for object re-

construction can be divided into two elements, 3-D measurement and 3-D data pro-

cessing (Fig. 1.1). In recent years, noticeable progress has been made in optical

3-D measurement techniques through interdisciplinary cooperation between opto-

electronics, image processing, and close-range photogrammetry. Among the diverse

optical 3-D measuring devices, the laser radar is capable of measuring millions of

S.J. Ahn: Least-Squares Orthogonal Distance Fitting, LNCS 3151, pp. 1-16, 2004.

2 1. Introduction

Real objects

Applications:

coordinate metrology,

reverse engineering

Object description

shape, size, position,

and rotation parameters

3-D point cloud

3-D measurement:

photogrammetry, CT,

acoustic, tactile method

3-D data processing:

segmentation,

curve/surface fitting

Fig. 1.1. Parametric model recovery of real objects

dense 3-D points in a few seconds under various measuring conditions such as object

surface material, measuring range, and ambient light [43], [56], [78]. An example

of the application of laser radar is the digital documentation of an engineering plant

that mainly consists of simple geometric elements such as plane, sphere, cylinder,

cone, and torus. Demands for 3-D measurement techniques and the 3-D data vol-

ume to be processed are rapidly increasing with continuing scientiﬁc and technical

development.

In contrast to the recent progress made in 3-D measurement techniques, that of

software tools for 3-D data processing has virtually stagnated. The software tools

that are currently available demand an intensive user action for documenting a com-

plex real world scene. In practice, segmentation and outlier elimination in a point

cloud is the major bottleneck of the overall procedure and is usually assisted by a

human operator. It is accepted that no general software tool exists for the fully auto-

mated 3-D data processing of a real world scene [43], [56], [78]. Thus, considering

the remarkable 3-D data throughput of advanced 3-D measuring devices, the devel-

opment of a ﬂexible and efﬁcient software tool for 3-D data processing with a high

degree of accuracy and automation is urgently required for applications of advanced

optical 3-D measurement techniques in many engineering ﬁelds.

With the software tools for 3-D data processing, model ﬁtting algorithms play

a fundamental role in estimating the object model parameters from a point cloud.

These are usually based on the least-squares method (LSM) [36] determining model

parameters by minimizing the square sum of a predeﬁned error-of-ﬁt. Among the

various error measures, the shortest distance (also known as geometric distance,

orthogonal distance, or Euclidean distance in literature) between the model feature

and the given point is of primary concern where dimensional data is being pro-

cessed [1], [29], [61]. For a long time however, the analytical and computational

difﬁculties encountered in computing and minimizing the geometric distance errors

blocked the development of appropriate ﬁtting (orthogonal distance ﬁtting, ODF)

algorithms [20], [21]. To bypass the difﬁculties associated with ODF, most data

processing software tools use the approximating measures of the geometric error

[22], [26], [32], [48], [51], [53], [67], [73], [76]. Nevertheless, when a highly ac-

curate and reliable estimation of model parameters is essential to applications, the

only possibility available is to use the geometric distance as the error measure to

剩余138页未读，继续阅读

虾大爷301

粉丝: 0

3D点云处理：空间中曲线与曲面的最佳拟合算法

Least-squares-fitting-of-two-3-D-point-sets

Image Deformation Using Moving Least Squares

aproksymacja.zip_in_least squares_least-square-fitting

Progressive and iterative approximation for least squares B-spline curve and surface fitting

Least_squares_fitting_2.py

Circular and linear regression: Fitting circles and lines by least squares

Least Squares Fitting：最小二乘拟合实现-matlab开发

A SYNTHESIS OF RECENT ADVANCES IN THE METHOD OF LEAST SQUARES

nonlinear-least-squares-fitting:Python中的1D和2D非线性最小二乘拟合示例

CHAPTER5-leastsquares.rar_leastsquares_英语学习

最新资源