IROS2019国际学术会议论文集 1307_第1页
IROS2019国际学术会议论文集 1307_第2页
IROS2019国际学术会议论文集 1307_第3页
IROS2019国际学术会议论文集 1307_第4页
IROS2019国际学术会议论文集 1307_第5页
已阅读5页,还剩2页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

Normal Distribution Mixture Matching based Model Free Object Tracking Using 2D LIDAR Baehoon Choi1 HyungGi Jo1and Euntai Kim1 Abstract In this paper a novel normal distribution mixture matching based model free object tracking algorithm using 2D LIDAR is proposed Each target object is modeled as a normal distribution mixture that captures the distribution of the points scanned from the surface of the object This novel representation enables normal distribution transform NDT to accurately estimate the motion of objects even if the shape of the points differs depending on where it is observed Our evaluation of the proposed algorithm shows good performance in practical applications In addition we provides an alternative way of segmentation and data association using occupancy grid map to avoid a problem that defi nes a distance metric between the mixture and the point cloud As a result the proposed algorithm works in real time in our experiments I INTRODUCTION Multiple Object Tracking MOT is an essential part for mobile robot applications Since the environment keeps changing the systems have to keep an eye on the envi ronment for their safety LIDAR has a capability to be a good eye since it collects a lot of highly accurate distance measurements very quickly in 2D to 3D space As it provides rich information it plays important roles in many systems such as simultaneous localization and mapping SLAM obstacle detection and avoidance to navigate safely However the data size of LIDAR is too large to interpret The scan points must be grouped according to their origin so that individual objects can be analyzed And each group must be associated with the existing object information although the point group will look different depending on the observed location Thereafter the object information needs to be updated appropriately In this paper we propose a new multiple object tracking al gorithm using 2D LIDAR The proposed algorithm describes the surface of each object as a normal distribution mixture The normal distribution mixture is associated with an object level point cloud And then they update their parameters using the associated point cloud In this process the normal distribution transform NDT is applied to fi nd the spatial displacement of each object having various shapes The main contributions of this paper are to formulate equations for calculating objects displacements and to develop an alternative way to segment the point cloud and associate normal distribution mixtures with point clouds We show that the proposed algorithm works accurately and precisely in real world applications 1Baehoon Choi HyungGi Jo and Euntai Kim are with School of Electrical and Electronic Engineering Yonsei University Seoul Korea choibae hygijo etkim yonsei ac kr The remainder of this paper is confi gured as follows In Section II the previous researches on tracking multiple ob jects using LIDAR are briefed The proposed algorithm will be introduced in Section III In section IV some experiments of the proposed algorithm in real world situations will be provided Finally the paper will be concluded in section V II RELATEDWORKS Over the past few decades several approaches have been proposed to track objects using LIDAR In early researches 1 2 LIDAR is applied to track small objects such as pedestrian by modeling the objects as a single point e g mean of points Sato et al 1 computed weighted mean of the measurement points and tracked them by global nearest neighbor association and Kalman fi lter Meissner et al 2 extracted a point from grid representation and applied random fi nite set Bayes fi lter for tracking pedestrian at intersection Following that several authors 3 4 tried to model the object s shape for tracking bigger objects e g car by a rectangle The box model provided ways of handling occlusion and split that the point model can t Furthermore several model free approaches 5 10 have been proposed The authors of 5 7 modeled the object shape with the local occupancy grid The local occupancy grid based representation provided better precision than point or box models and robustness to the uncertainty of segmen tation and data association In some approaches 8 9 the authors proposed approaches tracking grid map instead of tracking individual objects They estimated the occupancy and the velocity of each grids Wang et al 10 proposed the target state representation using boundary points for jointly estimating the state of sensor and moving objects independent of their shapes They applied a variant of point set registration algorithm iterative closest point ICP 11 for coarse data association Even with unpredictable shaped objects they ve got competitive tracking results However the algorithm takes 300ms per frame on average which is not appropriate for real time applications NDT 12 is a point set matching algorithm that align a normal distributions with another point set The primary use of NDT has been SLAM as many point set registration algorithms have done 13 14 Takubo et al 13 proposed a high resolution grid map building algorithm using NDT They made use of the neighbor cells if a cell had only one or two points Saarineen et al 14 formulated the recursive update of normal distribution elements for long term mapping In this paper we obtained an idea to develop model free tracking from NDT in SLAM 2019 IEEE RSJ International Conference on Intelligent Robots and Systems IROS Macau China November 4 8 2019 978 1 7281 4003 2 19 31 00 2019 IEEE455 Compute the gradient and the Hessian Find the new guess for the increment of the score Update the previous state using guess Compute the gradient and the Hessian Find the new guess for the increment of the score III C Prediction III D Data Association III E Normal Distribution Mixture Matching III F Update Previous StatesLIDAR data III D Segmentation Estimated States Update the previous state using guess Compute the gradient and the Hessian Find the new guess for the increment of the score Is converged Fig 1 An overview of the proposed algorithm The input is a 2D LIDAR scan data and the estimation of the target state is recursively updated III MULTIPLEOBJECTTRACKINGUSINGNORMAL DISTRIBUTIONMIXTUREMATCHING In this section the proposed multiple object tracking algorithm using normal distribution mixture matching is presented The overall process is shown in Fig 1 A Target Model A set of the multiple object states at time t is represented as Xt xt 1 xt Mt where Mtis the number of target objects at time t Each object state xt i is defi ned by a set of 2D normal distributions N t i n t i n Nt i n 1 where Nt i is the number of normal distribution elements of the target i at time t and a velocity vector vt i vt i x vt i y Tthat is shared by all the elements of the object The normal distribution describes the mean and covariance of the points around Then the object state gives a direct description of how the point cloud is distributed over the object We assumed that the number of the normal distribution elements is set to be proportional to the size of the object For the assumption the state space is divided into regular grids and each grid can have at most one element at a time It is shown in Fig 2 For the sake of simplicity the time index t and the object index i are omitted hereafter B Ego Motion The motion of ego robot can be applied by the transitions of the normal distributions according to the transition of the state space If the state space moves linearly only the means of normal distributions move to the opposite direction If the state space rotates the means moves considering the rotation and the covariances also rotate to the opposite direction on its location C Prediction In the prediction step all the normal distribution elements are translated with their previous velocity Since the time elapsed is very short the amount of rotation is ignored in the prediction step and estimated in the matching step Then the predicted mean of n th normal distribution element can be computed very simply as n n vdt Fig 2 An example of target representation Each target is modeled by a normal distribution mixture and a velocity vector Each cell has at most one normal distribution element where dt is the elapsed time Since the rotation is ignored the covariance matrices are not changed in the prediction step This predicted states are used to defi ne the search space in the data association step and to make an initial displacement in the matching step After the translation some grids can have more than one normal distribution elements In that case the distributions are merged into a single distribution Let two normal dis tributions N 1 1 and N 2 2 with x1i N1 i 1 and x2i N2 i 1 as their samples respectively are given Since they are sample means and covariances the parameters are computed as 1 1 N1 X i x1i 1 1 N1 1 X 1 11TN1 X 1 11TN1 T where X1 x11 x1N1 1nis a column vector with n ones and 2and 2are computed similarly Then the mean of the merged normal distributions is computed as N1 1 N2 2 N1 N2 1 Also N1 1 1 X1XT 1 N1 1 T 1 2 N2 1 2 X2XT 2 N2 2 T 2 3 N1 N2 1 XXT N1 N2 T X1XT 1 X2XT 2 N1 N2 T 4 456 a b Fig 3 An example of the connected occupancy grid based segmentation a First step building a polar occupancy grid map b Second step applying a connected component labeling algorithm where X X1 X2 and is the merged covariance Substituting 1 2 and 3 into 4 we can obtain the covariance of the merged distribution as N1 N2 1 N1 1 1 N2 1 2 N1N2 N1 N2 1 2 1 2 T 5 D Segmentation and Data Association A set of points is obtained by LIDAR scanning the surfaces of objects around The set needs to be divided into several segments representing objects to analyze individual objects In the proposed algorithm the connected occupancy grid based segmentation is applied as shown in Fig 3 First we build a polar occupancy grid map using the point cloud Since LIDAR senses by rotating we applied the polar grid instead of the cartesian to describe the measurement space And then the connected component labeling algorithm is ap plied to the occupancy grid map The occupied neighbors are labeled as an identical segment It is similar to the distance based segmentation but it contains the spatial information In the data association the segmented point clouds are paired with the mixtures Each predicted normal distribution mixture fi nds the segments around on the occupancy grid map then the segments around are combined for applying the matching algorithm This approach solves both the segmentation and the data association in an alternative way from the distance based segmentation and the data association using a distance metric between the mixture and point cloud This segmentation method takes more time than the distance based segmentation that computes only the distance between consecutive points However as once the occupancy grid map is built and the occupied cells get its segment identity the association between normal distribution mixture and point cloud can be made very easily by checking the cells around the normal distribution element Consequently the time complexity of this alternative algorithm depends on the amount of the scan points and the size of the grid E Normal Distribution Mixture Matching The purpose of the normal distribution mixture matching is to fi nd the displacement of each target i i dxi dyi d i from the time t 1 to the time t using the associated point cloud The resultant displacement is employed to estimate the velocity of the target and to update the mixture New ton s method in optimization is adapted to fi nd the optimal displacement Using a given displacement of the object the object state mean can be updated as n T t 1 n Rd t 1 n cr cr d 1 n N 6 where n is the mixture index Rd is the rotation matrix with angle d cris the center of rotation and d is the displacement dx dy In our implementation a point maxn n x 2 minn n x 2 maxn n y 2 minn n y 2 is employed as cr The covariance matrix is updated using only the rotation angle d as n Rd t 1 nRT d 1 n N 7 The bar notation represents the temporarily updated value here As the probability density of the normal distribution is p x exp x T 1 x 2 8 the score of the displacement can be defi ned as s X j exp z j n j T 1 n j z j n j 2 9 where j is the scan index in the associated segment n j is the index of the normal distribution element which the scan j is corresponded Thus the displacement that maximizes the score s can be a solution For the sake of generality the optimization problem maxs is rewritten as minf s In the Newton s method the vector is iteratively updated as where H g 10 457 H is the Hessian of f Hkl 2f k l and g is the transposed gradient of f gk f k For simplicity the innovation yj is defi ned as yj zj n j for equation 9 Then a summand of f can be represented as fj exp yT j 1 n j yj 2 11 Using 11 the elements of the gradient g is computed as gj k fj k fj yj yj k yT j 1 yj k exp yT j 1 yj 2 12 and the elements of the Hessian matrix H is computed as Hj kl 2fj k l yT j l 1 yj k exp yT j 1 yj 2 yT j 1 2 yj k l exp yT j 1 yj 2 yT j 1 yj k yT j 1 yj l exp yT j 1 yj 2 13 where the Jacobian matrix J of yjat the displacement vector is J yj yj 1 0 x cr x sind y cr y cosd 0 1 x cr x cosd y cr y sind 14 and then the second derivatives of yjare 2 yj k l x cr x cosd y cr y sind x cr x sind y cr y cosd k l 3 0 0 otherwise 15 Finally the Hessian and the gradient of f are computed as H X j Hj g X j gj 16 Then the vector is H 1g 17 In practice H is replaced by H I in the case that H is not positive defi nite Algorithm 1 Normal Distribution Mixture Matching Require A target state x N n n N n 1 vt i Require An associated segment zj J j 1 1 Set initial displacement 2 repeat 3 Update nand nfor n using 4 Compute the Hessian H and the gradient g 5 H 1g 6 7 until converged 8 return The estimated displacement F Update In the update step the target state estimation is updated with the converged displacement fi rst The means and the covariance matrices are computed by equations 6 and 7 In case that more than one normal distributions are in a cell they are merged into a single normal distribution element using equations 1 and 5 Then the normal distributions are updated with the points in the associated segment The points in each segment forms normal distribution mixture and they are merged into the target state If a cell consists of only one or two points due to insuffi cient angular resolution of LIDAR the points in the segment is upsampled to make a normal distribution In case that there is a cell having scan points but no normal distribu tion element a new normal distribution element is attached into the target state To handling false data association only the cells close to the existing are considered candidates for the attachment Conversely if there is a normal distribution element in the empty cell of the occupancy grid map the element needs to be deleted If there is an unassociated segment for consecutive times a new target state is initialized In case that a target is initialized multiple times by over segmentation the target state is merged into one at the moment well segmented and associated with an identical segment And the targets unassociated for consecutive times are removed from the target list IV EXPERIMENTRESULTS To evaluate the proposed algorithm we perform exper iments at various locations on Yonsei University campus using a 2D LIDAR UTM 30LX mounted on a robot at about 40cm height The algorithm performed in x y 10m 10m 10m 10m region using 0 1m 0 1m grids There are various types of objects in the environment including pedestrians In the following sections we provide both quantitative and qualitative analysis of our algorithm For the quantitative evaluation the proposed algorithm is compared with a classic tracking algorithm The baseline algorithm clusters the object level point cloud using adaptive breaking point detection algorithm 15 and tracks objects with nearest neighbor data association and independent 458 Fig 4 Four trajectories of the walking pedestrians data set Fig 5 The estimated velocity distribution of four of the walking pedestrians data set TABLE I QUANTITATIVEEVALUATIONRESULTS speed directionIDswitch Baseline0 90250 762211 21 Proposed0 54190 50235 64 Kalman fi lters for each cluster centroid We refered sev eral model free tracking algorithms 5 10 in Section II however it is diffi cult to compare it in a fair way because of diffi culty of both impartial and direct comparison using common environments Therefore the classical algorithm is chosen for comparison In the qualitative evaluation section we provide cases of success and failure and analyze how it failed Furthermore we measure the computation time to see practicality of the proposed algorithm A Quantitative Evaluation To measure the stability of the estimation we collected a data set including 14 walking pedestrians and compare the precision of the estimation When the identical pedestrian has multiple target IDs due to ID switches the IDs are considered as one pedestrian Fig 4 shows the trajectories of a part of the pedestrian data set and Fig 5 shows the distributions of the estimated velocities of them Since the gait of the pedestrians is not a constant motion their speed and posture have some variations However the walking pedestrian has specifi c moving direction and a certain speed Therefore the precise estimation of the moving direction and the certain speed could be a goal of the tracking algorithm As shown in Fig 5 and Table I the proposed algorithm has smaller standard de viations for both estimations on speed and moving direction The cluster centroid shows the unexpected motion caused by the changing shape over and under segmentations and the occlusions from the varying posture of the pedestrian Meanwhile the proposed algorithm tries to fi nd the best match between the mixture and the point cloud every frame therefore is less affected by the va

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论