第1页 / 共189页
第2页 / 共189页
第3页 / 共189页
第4页 / 共189页
第5页 / 共189页
第6页 / 共189页
第7页 / 共189页
第8页 / 共189页
tensor voting理论详解（代码实现）.pdf
LIST OF TABLES
LIST OF FIGURES
ACKNOWLEDGMENT
ABSTRACT
Introduction
Objectives
Free-Space Modeling
Change Detection
Tensor Voting
Terrain Extraction
Challenges
Approaches
Contributions
Organization of Thesis
Background
Range Data
Triangulation
Structured Light
Time-of-Flight
Representation
Methods
Segmentation
Registration
Spatial Data Structures
Modeling
Indoor
Urban
Terrain
Free-Space
Change Detection
Tensor Voting
Summary
Free-Space Modeling for Change Detection
Introduction
Problem
Approach
Contributions
Organization of Chapter
Free-Space Modeling from a Single Viewpoint
Free-Space of a Single Scan
Preprocessing of Scans
The Free-Space Polyhedron
Free-Space Queries
The Spherical Quad-Tree
Spherical Parameterization
Hierarchical Subdivision
Spatial Queries
Change Detection
SQT Volumes
Scan Index Octree
Detecting Changes
Results
Indoor Experiments
Outdoor Experiments
Performance
Summary
Tensor Voting Theory
Introduction
Types of Structure
Encoding Structure
Voting Procedure
Inferring Structure
Contributions
Organization of Chapter
Formulation
Normal and Tangent Subspaces
Representing Structure
Communicating Structure
Fundamental Stick Vote
Computing a Vote Component
Collecting Votes
Attenuation
Traditional Weight Profile
Selection of a Curvature Penalty
Intuition
Decoupling Distance and Angle
Smooth Weight Profile
Differentiation
Derivative of Saliency
Derivative of Vote Tensor
Derivative of Traditional Weight
Derivative of Smooth Weight
Discussion
Curvature Penalty
Weight Profiles
Computational Complexity
Gradient Computation
Summary
Terrain Extraction by Tensor Voting
Introduction
Problem
Approach
Contributions
Organization of Chapter
Multi-Scale Tensor Voting
Sampling Issues
Fine-to-Coarse Token Refinement
Sample Selection and Masking
Inter-Scale Communication
Saliency Threshold
Terrain Extraction
Approach
Coarse-to-Fine Extraction
Line-Segment Search
Discussion
Experiments
Token Refinement Results
Terrain Extraction Results
Summary
Conclusion
Contributions to Free-Space Modeling
Inference
Representation
Change Detection System
Contributions to Tensor Voting
Theory
Practical Application to Terrain Extraction
Future Work
Free-Space
Change Detection
Tensor Voting
Terrain Extraction
Combining Methods
Summary
References
Derivative of an Eigenvalue
Tensor Voting Algorithm
BY FREE-SPACE MODELING AND TENSOR VOTING
RANGE DATA ANALYSIS
By
Bradford James King
A Thesis Submitted to the Graduate
Faculty of Rensselaer Polytechnic Institute
in Partial Fulfillment of the
Requirements for the Degree of
DOCTOR OF PHILOSOPHY
Major Subject: COMPUTER SCIENCE
Approved by the
Examining Committee:
Charles V. Stewart, Thesis Adviser
Daniel Freedman, Member
Barbara M. Cutler, Member
I. Volkan Isler, Member
Rensselaer Polytechnic Institute
Troy, New York
December 2008
(For Graduation December 2008)
该文档是极速PDF编辑器生成，如果想去掉该提示,请访问并下载：http://www.jisupdfeditor.com/
c Copyright 2008
by
Bradford James King
All Rights Reserved
ii
CONTENTS
LIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ix
ACKNOWLEDGMENT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii
ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiv
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.1 Free-Space Modeling . . . . . . . . . . . . . . . . . . . . . . .
1.1.2 Change Detection . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.3 Tensor Voting . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.4 Terrain Extraction . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
2
2
4
4
7
8
1.3 Approaches
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.5 Organization of Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2. Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.1 Range Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.1.1 Triangulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.1.2
Structured Light
. . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.3 Time-of-Flight . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1.4 Representation . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.1
Segmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.2 Registration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.3
Spatial Data Structures
. . . . . . . . . . . . . . . . . . . . . 21
2.3 Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.1
Indoor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.2 Urban . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3.3 Terrain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3.4 Free-Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
iii
2.3.5 Change Detection . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4 Tensor Voting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3. Free-Space Modeling for Change Detection . . . . . . . . . . . . . . . . . . 29
3.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.1.1 Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.1.2 Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.1.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.1.4 Organization of Chapter . . . . . . . . . . . . . . . . . . . . . 31
3.2 Free-Space Modeling from a Single Viewpoint
. . . . . . . . . . . . . 32
3.2.1 Free-Space of a Single Scan . . . . . . . . . . . . . . . . . . . 32
3.2.2 Preprocessing of Scans . . . . . . . . . . . . . . . . . . . . . . 36
3.2.3 The Free-Space Polyhedron . . . . . . . . . . . . . . . . . . . 37
3.2.4 Free-Space Queries . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3 The Spherical Quad-Tree . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.3.1
Spherical Parameterization . . . . . . . . . . . . . . . . . . . . 43
3.3.2 Hierarchical Subdivision . . . . . . . . . . . . . . . . . . . . . 44
3.3.3
Spatial Queries . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.4 Change Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.4.1
3.4.2
SQT Volumes . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
Scan Index Octree
. . . . . . . . . . . . . . . . . . . . . . . . 48
3.4.3 Detecting Changes
. . . . . . . . . . . . . . . . . . . . . . . . 49
3.5 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.5.1
Indoor Experiments . . . . . . . . . . . . . . . . . . . . . . . . 51
3.5.2 Outdoor Experiments . . . . . . . . . . . . . . . . . . . . . . . 51
3.5.3 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4. Tensor Voting Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.1.1 Types of Structure . . . . . . . . . . . . . . . . . . . . . . . . 63
4.1.2 Encoding Structure . . . . . . . . . . . . . . . . . . . . . . . . 64
4.1.3 Voting Procedure . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.1.4
Inferring Structure . . . . . . . . . . . . . . . . . . . . . . . . 67
iv
4.1.5 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.1.6 Organization of Chapter . . . . . . . . . . . . . . . . . . . . . 69
4.2 Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.2.1 Normal and Tangent Subspaces . . . . . . . . . . . . . . . . . 70
4.2.2 Representing Structure . . . . . . . . . . . . . . . . . . . . . . 70
4.2.3 Communicating Structure . . . . . . . . . . . . . . . . . . . . 71
4.2.4 Fundamental Stick Vote . . . . . . . . . . . . . . . . . . . . . 72
4.2.5 Computing a Vote Component . . . . . . . . . . . . . . . . . . 73
4.2.6 Collecting Votes . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.3 Attenuation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.3.1 Traditional Weight Profile . . . . . . . . . . . . . . . . . . . . 77
4.3.2
4.3.3
Selection of a Curvature Penalty . . . . . . . . . . . . . . . . . 77
Intuition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.3.4 Decoupling Distance and Angle . . . . . . . . . . . . . . . . . 84
4.3.5
Smooth Weight Profile . . . . . . . . . . . . . . . . . . . . . . 86
4.4 Differentiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.4.1 Derivative of Saliency . . . . . . . . . . . . . . . . . . . . . . . 89
4.4.2 Derivative of Vote Tensor
. . . . . . . . . . . . . . . . . . . . 90
4.4.3 Derivative of Traditional Weight . . . . . . . . . . . . . . . . . 91
4.4.4 Derivative of Smooth Weight . . . . . . . . . . . . . . . . . . . 91
4.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.5.1 Curvature Penalty . . . . . . . . . . . . . . . . . . . . . . . . 93
4.5.2 Weight Profiles
. . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.5.3 Computational Complexity . . . . . . . . . . . . . . . . . . . . 96
4.5.4 Gradient Computation . . . . . . . . . . . . . . . . . . . . . . 96
4.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5. Terrain Extraction by Tensor Voting . . . . . . . . . . . . . . . . . . . . . 99
5.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
5.1.1 Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
5.1.2 Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
5.1.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
5.1.4 Organization of Chapter . . . . . . . . . . . . . . . . . . . . . 101
5.2 Multi-Scale Tensor Voting . . . . . . . . . . . . . . . . . . . . . . . . 102
5.2.1
Sampling Issues . . . . . . . . . . . . . . . . . . . . . . . . . . 102
v
5.2.2 Fine-to-Coarse Token Refinement . . . . . . . . . . . . . . . . 103
5.2.3
5.2.4
5.2.5
Sample Selection and Masking . . . . . . . . . . . . . . . . . . 105
Inter-Scale Communication . . . . . . . . . . . . . . . . . . . . 107
Saliency Threshold . . . . . . . . . . . . . . . . . . . . . . . . 109
5.3 Terrain Extraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
5.3.1 Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
5.3.2 Coarse-to-Fine Extraction . . . . . . . . . . . . . . . . . . . . 113
5.3.3 Line-Segment Search . . . . . . . . . . . . . . . . . . . . . . . 115
5.3.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
5.4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
5.4.1 Token Refinement Results . . . . . . . . . . . . . . . . . . . . 119
5.4.2 Terrain Extraction Results . . . . . . . . . . . . . . . . . . . . 125
5.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
6. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
6.1 Contributions to Free-Space Modeling . . . . . . . . . . . . . . . . . . 133
6.1.1
Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
6.1.2 Representation . . . . . . . . . . . . . . . . . . . . . . . . . . 133
6.1.3 Change Detection System . . . . . . . . . . . . . . . . . . . . 133
6.2 Contributions to Tensor Voting . . . . . . . . . . . . . . . . . . . . . 134
6.2.1 Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
6.2.2 Practical Application to Terrain Extraction . . . . . . . . . . 134
6.3 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
6.3.1 Free-Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
6.3.2 Change Detection . . . . . . . . . . . . . . . . . . . . . . . . . 136
6.3.3 Tensor Voting . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
6.3.4 Terrain Extraction . . . . . . . . . . . . . . . . . . . . . . . . 137
6.3.5 Combining Methods
. . . . . . . . . . . . . . . . . . . . . . . 137
6.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
APPENDICES
A. Derivative of an Eigenvalue . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
B. Tensor Voting Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
vi
LIST OF TABLES
3.1
Experiment Sizes and Times . . . . . . . . . . . . . . . . . . . . . . . . 58
4.1 Gradient Computation Time by Method . . . . . . . . . . . . . . . . . 97
5.1
5.2
5.3
5.4
5.5
5.6
Token Refinement Performance: ’86-Field-West . . . . . . . . . . . . . . 123
Token Refinement Performance: ’86-Field-East . . . . . . . . . . . . . . 123
Token Refinement Performance: ERDC-Track . . . . . . . . . . . . . . 124
Terrain Extraction Performance: ’86-Field-West
. . . . . . . . . . . . . 129
Terrain Extraction Performance: ’86-Field-East . . . . . . . . . . . . . . 129
Terrain Extraction Performance: ERDC-Track . . . . . . . . . . . . . . 130
B.1 Algorithm VoteComplete() . . . . . . . . . . . . . . . . . . . . . . . 172
B.2 Algorithm VoteComponent() . . . . . . . . . . . . . . . . . . . . . . 173
B.3 Algorithm VoteWeightTraditional() . . . . . . . . . . . . . . . . . 173
B.4 Algorithm VoteWeightSmooth() . . . . . . . . . . . . . . . . . . . . 173
vii
viii
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
