狠狠撸

狠狠撸Share a Scribd company logo

NDT-TKU

?Download as PPTX, PDF?
?
Booch Lin
Booch Lin

NDT-TKU is an improved 3D Normal Distributions Transform method for mobile robotic mapping proposed by Takeuchi from Nagoya University. It uses a two-stage converging process where the voxel size is adjusted based on point density during registration. This allows for higher accuracy while reducing computation compared to a single voxel size. The key aspects of NDT-TKU include overlapping voxels, trilinear interpolation, and dividing the registration into converging and adjustment states.

1 of 20
Downloaded 44 times
NDT - TKU heaton
What is ndt_tku ?A 3-D Scan Matching using Improved 3-D Normal Distributions Transform for Mobile Robotic Mapping ?名古屋大學 竹內先生(TAKEUCHI)提出的 NDT 優化版 ?Autoware/ros/src/computing/perception/localization/packages/n dt_localizer/nodes/ndt_matching_tku/
Why is ndt_tku ?是指導教授提出的 ?PCL 的 cuda 化極度麻煩，工程師表示不如自幹一套，然後 cuda 化
Outline ndt_tku ? ND ? NDT in slam ? NDT_TKU
Normal Distribution ? 正態分佈 - 是一個在數學、物理及工程等領域都非常重要的機率分佈，由於這個分布函數具有很多 非常漂亮的性質.使得其在諸多涉及統計科學離散科學等領域的許多方面都有著重大的影響力. ? 符合 ? 台灣收入分佈 ? 不符合 ? 骰子各面機率，我跟連家人的收入分佈。
Normal Distribution Transform Subdivide the space occupied by the scan into a grid of cells. A PDF is computed for each cell, based on the point distribution within the cell
NDT in tunnel - 3D
如何表示點雲的機率分布 ? multivariate probability function p(~x)l ? mean ? covariance
Scan registration ? The current scan is represented as a point cloud X = {~x1, . . . , ~xn}. Assume that there is a spatial transformation function T(~p, ~x) that moves a point ~x in space by the pose ~p. ? Given some PDF p(~x) for scan points , the best pose ~p should be the one that maximises the likelihood function
Scan registration ? Given a set of points X = {~x1, . . . , ~xn}, a pose ~p, and a transformation function T(~p, ~x) to transform point ~x in space by ~p, the NDT score function s(~p) for the current parameter vector is ? Using such a Gaussian approximation, the influence of one point from the current scan on the NDT score function is
Newton’s algorithm for ? Newton’s algorithm can be used to find the parameters ~p that optimise s(~p) ? Newton’s method iteratively solves the equation H?~p = ?~g ? g and H are partial differential and second order partial differential of optimizing function. They are
流程
我知道大家看數字很痛苦 但我只是要說算這個很麻煩。
About ND Voxel size ? 太小 ? 運算量大，memory 消耗大 ? 匹配精確 ? 但小於五個點，則很難形成正態分佈 ? 太大 ? 運算量少 ? 匹配不精確
NDT - TKU version 格子重疊 ? 提高精確度 ? 運算量提高，一點點雲會有八個格子 ? Trilinear interpolation
图片有感
TKU - ND Voxel size 將收斂流程分成兩階段 ? Converging state 按照距離切分 ND Voxel size，並運算 ? Adjust state 到一定次數後則通通用 最小格子來運算
ENDING THANKs FOR YOUR ATTENTION. Reference 1. A 3-D Scan Matching using Improved 3-D Normal Distributions Transform for Mobile Robotic Mapping(網路上不公開) 2. The Three-Dimensional Normal-Distributions Transform — an Efficient Representation for Registration, Surface Analysis, and Loop Detection 3. The Normal Distributions Transform:A New Approach to Laser Scan Matching
Other 1. Parameter a. voxel size b. step size c. iterative times
score detail

More Related Content

NDT-TKU

  • 2. What is ndt_tku ?A 3-D Scan Matching using Improved 3-D Normal Distributions Transform for Mobile Robotic Mapping ?名古屋大學 竹內先生(TAKEUCHI)提出的 NDT 優化版 ?Autoware/ros/src/computing/perception/localization/packages/n dt_localizer/nodes/ndt_matching_tku/
  • 3. Why is ndt_tku ?是指導教授提出的 ?PCL 的 cuda 化極度麻煩，工程師表示不如自幹一套，然後 cuda 化
  • 4. Outline ndt_tku ? ND ? NDT in slam ? NDT_TKU
  • 5. Normal Distribution ? 正態分佈 - 是一個在數學、物理及工程等領域都非常重要的機率分佈，由於這個分布函數具有很多 非常漂亮的性質.使得其在諸多涉及統計科學離散科學等領域的許多方面都有著重大的影響力. ? 符合 ? 台灣收入分佈 ? 不符合 ? 骰子各面機率，我跟連家人的收入分佈。
  • 6. Normal Distribution Transform Subdivide the space occupied by the scan into a grid of cells. A PDF is computed for each cell, based on the point distribution within the cell
  • 9. Scan registration ? The current scan is represented as a point cloud X = {~x1, . . . , ~xn}. Assume that there is a spatial transformation function T(~p, ~x) that moves a point ~x in space by the pose ~p. ? Given some PDF p(~x) for scan points , the best pose ~p should be the one that maximises the likelihood function
  • 10. Scan registration ? Given a set of points X = {~x1, . . . , ~xn}, a pose ~p, and a transformation function T(~p, ~x) to transform point ~x in space by ~p, the NDT score function s(~p) for the current parameter vector is ? Using such a Gaussian approximation, the influence of one point from the current scan on the NDT score function is
  • 11. Newton’s algorithm for ? Newton’s algorithm can be used to find the parameters ~p that optimise s(~p) ? Newton’s method iteratively solves the equation H?~p = ?~g ? g and H are partial differential and second order partial differential of optimizing function. They are
  • 14. About ND Voxel size ? 太小 ? 運算量大，memory 消耗大 ? 匹配精確 ? 但小於五個點，則很難形成正態分佈 ? 太大 ? 運算量少 ? 匹配不精確
  • 15. NDT - TKU version 格子重疊 ? 提高精確度 ? 運算量提高，一點點雲會有八個格子 ? Trilinear interpolation
  • 17. TKU - ND Voxel size 將收斂流程分成兩階段 ? Converging state 按照距離切分 ND Voxel size，並運算 ? Adjust state 到一定次數後則通通用 最小格子來運算
  • 18. ENDING THANKs FOR YOUR ATTENTION. Reference 1. A 3-D Scan Matching using Improved 3-D Normal Distributions Transform for Mobile Robotic Mapping(網路上不公開) 2. The Three-Dimensional Normal-Distributions Transform — an Efficient Representation for Registration, Surface Analysis, and Loop Detection 3. The Normal Distributions Transform:A New Approach to Laser Scan Matching
  • 19. Other 1. Parameter a. voxel size b. step size c. iterative times

Editor's Notes

  • #4: 虽然是这样说，但是这是好几周前说的
  • #6: 连续的，数学只要能表示出来就能算
  • #7: 先切成一格一格 The normal-distributions transform can be described as a method for compactly representing a surface. 正態分佈給出了點雲的分段平滑表示，具有連續的導數。 每個PDF可以看作是局部表面的近似值，描述了表面的位置以及其取向和平滑度。 A 2D laser scan from a mine tunnel (shown as points) and the PDFs describing the surface shape. Each cell is a square with 2 m side length in this case. Brighter areas represent a higher probability. PDFs have been computed only for cells with more than five points.
  • #8: 3D-NDT surface representation for a tunnel section, seen from above. Brighter, denser parts represent Higher probabilities. The cells have a side length of 1 m
  • #9: D-dimensional normal random process, the likelihood of having measured ~x is where ~yk=1,..., m are the positions of the reference scan points contained in the cell. 正態分佈給出了點雲的分段平滑表示，具有連續的導數。 每個PDF可以看作是局部表面的近似值，描述了表面的位置以及其取向和平滑度。 协方差矩阵的特征向量和特征值可以表达表面信息 . Each PDF can be seen as an approximation of the local surface, describing the position of the surface as well as its orientation and smoothness
  • #10: 當前掃描被表示為點雲X = {?x1，...。 。 。 ，?xn}。 假設有一個空間變換函數T（?p，?x）通過姿態p移動空間中的點?x。 給定一些用於掃描點的PDF p（?x）（例如，等式6.1），最佳姿態p應該是最大化似然函數的姿態 使用近似法去取得最近值, 這是一個疊代過程 n學生身高(X) à X~(135, 102)
  • #11: 收斂的參數計算 學力偏差值，上一頁的 -4 , -2 , 0 , 2 , 4 ，為只表示的點值正規化
  • #12: 老樣子超過15個符號我們就不要理會 https://www.youtube.com/watch?v=Quw4ZHLH2CY 利用微分找出切線，疊代法趨近找出 function = 0 的根
  • #13: s
  • #14: 但跟其他算法比算快了(Iterative Closest Point，迭代最近点)
  • #15: 格子大小 ND Voxel size 包含點多少的定值，通常至大於五個點，形成正態分布 太大也會讓nd不好形成 迭代次數 iterative times 決定格子大小變成最主要優化的手段 必須取決sensor 類型
  • #16: 這並非TKU提出來的。 Peter Biber and Wolfgang Stra?er: “The Normal Distributions Transform:A New Approach to Laser Scan Matching”, Proceedings of the 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2743–2748, 2003 那麼就會需要降低運算量
  • #18: 通常是四次切割
  • #19: CODE TRANSFER TO JJ