3D点云数据处理方法研究进展

doi:10.11896/jsjkx.240100132

摘要/Abstract

摘要： 点云是理解三维场景的重要形式之一,3D点云在海洋平台逆向建模、海底地形测绘、深水浮式结构系泊系统损伤测量及海底管线可视化等方面都有着重要应用。基于此,文中梳理了点云数据处理方法,将其分为传统处理算法和基于深度学习方法两大类;传统处理算法从滤波、对象识别与分类和配准3方面进行了介绍总结;基于深度学习方法从点云、体素化和多视图3方面进行了介绍总结。对各种算法的优缺点进行了归纳对比,并展望了3D点云处理技术未来的发展趋势与方向。

关键词: 3D点云, 数据处理, 传统方法, 深度学习

Abstract: Point cloud is one of the important forms to understand 3D scenes,and 3D point cloud has important applications in reverse modeling of offshore platforms,seabed topography mapping,damage measurement of mooring systems of deep-water floating structures,and visualization of submarine pipelines.Based on this,this paper sorts out the point cloud data processing methods and divides them into two categories:traditional processing algorithms and deep learning-based methods.The traditional processing algorithms are introduced and summarized from three aspects:filtering,object recognition,classification and registration.Based on the deep learning method,it is introduced and summarized from three aspects:point cloud,voxelization and multi-view.The advantages and disadvantages of various algorithms are summarized and compared,and the future development trend and direction of 3D point cloud processing technology are prospected.

Key words: 3D point clouds, Data processing, Traditional methods, Deep learning

中图分类号:

TP751.1

郭张翔, 闫天红, 周国强. 3D点云数据处理方法研究进展[J]. 计算机科学, 2024, 51(11A): 240100132-13. https://doi.org/10.11896/jsjkx.240100132

GUO Zhangxiang, YAN Tianhong, ZHOU Guoqiang. Research Progress of 3D Point Cloud Data Processing Methods[J]. Computer Science, 2024, 51(11A): 240100132-13. https://doi.org/10.11896/jsjkx.240100132

参考文献

[1]BAI Q P,SUN D H,ZHANG R,et al.Research on the application of 3D GIS in digital offshore drilling platforms [J].Bulletin of Surveying and Mapping,2011(6):73-75,79.
[2]FAN C C,DE X W,GUO J J,et al.Laser line scanning three-dimensional surveying of seafloor terrain based on triangular displacement method attitude correction [J].Optical Precision Engineering,2022,30(10):1170-1180.
[3]LIU B,LI X C G,ZENG J,et al.Application of underwaterthree-dimensional laser scanning in jacket platform damage measurement [J].Journal of Guangxi Academy of Sciences,2020,36(4):434-440.
[4]WU S H.Research on the application of three-dimensional laser scanning technology in offshore drilling platforms [D].Liaoning University of Engineering and Technology,2013.
[5]HUA B S,TRUONG Q T,TRAN M K,et al.Shrec'17:Rgb-d to cad retrieval with objectnn dataset[C]//Proc.Eurograph.Workshop 3D Object Retrieval.2017:25-32.
[6]HUA B S,PHAM Q H,NGUYEN D T,et al.Scenenn:A scene meshes dataset with annotations[C]//2016 Fourth International Conference on 3D vision(3DV).Ieee,2016:92-101.
[7]WU Z,SONG S,KHOSLA A,et al.3d shapenets:A deep representation for volumetric shapes[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.2015:1912-1920.
[8]ROYNARD X,DESCHAUD J E,GOULETTE F.Paris-Lille-3D:A large and high-quality ground-truth urban point cloud dataset for automatic segmentation and classification[J].The International Journal of Robotics Research,2018,37(6):545-557.
[9]HACKEL T,SAVINOV N,LADICKY L,et al.Semantic3d.net:A new large-scale point cloud classification benchmark[J].arXiv:1704.03847,2017.
[10]BEHLEY J,GARBADE M,MILIOTOA,et al.Semantickitti:A dataset for semantic scene understanding of lidar sequences[C]//Proceedings of the IEEE/CVF International Conference on Computer Vision.2019:9297-9307.
[11]ARMENI I,SENER O,ZAMIR A R,et al.3d semantic parsingof large-scale indoor spaces[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.2016:1534-1543.
[12]LI X,LI C,TONG Z,et al.Campus3d:A photogrammetry point cloud benchmark for hierarchical understanding of outdoor scene[C]//Proceedings of the 28th ACM International Conference on Multimedia.2020:238-246.
[13]DESCHAUD J E,DUQUE D,RICHA J P,et al.Paris-CARLA-3D:A real and synthetic outdoor point cloud dataset for challenging tasks in 3D mapping[J].Remote Sensing,2021,13(22):4713.
[14]WANG R,HUANG S,YANG H.Building3D:A Urban-ScaleDataset and Benchmarks for Learning Roof Structures from Point Clouds[C]//Proceedings of the IEEE/CVF International Conference on Computer Vision.2023:20076-20086.
[15]YANG H F,XIA H,CHEN X,et al.Application of image fusion in three-dimensional reconstruction of space targets [J].Infrared and Laser Engineering,2018,47(9):374-381.
[16]DING Z J,ZHAO Z Y,ZHANG C T,et al.Structured light three-dimensional reconstruction of deep sea landform lines by manned submersible [J].Infrared and Laser Engineering,2019,48(5):11-19.
[17]BALADO J,VAN OOSTEROM P,DÍAZ-VILARIÑOL,et al.Mathematical morphology directly applied to point cloud data[J].ISPRS Journal of Photogrammetry and Remote Sensing,2020,168:208-220.
[18]WAN P,ZHANG W,SKIDMORE A K,et al.A simple terrain relief index for tuning slope-related parameters of LiDAR ground filtering algorithms[J].ISPRS Journal of Photogrammetry and Remote Sensing,2018,143:181-190.
[19]VOSSELMAN G.Slope based filtering of laser altimetry data[J].International Archives of Photogrammetry and Remote Sensing,2000,33(B3/2;PART 3):935-942.
[20]ZHU X X,CHENG W,XI X H,et al.Hierarchical thresholdadaptive for point cloud filter algorithm of moving surface fitting[J].Acta Geodaetica et Cartographica Sinica,2018,47(2):153.
[21]AXELSSON P.DEM generation from laser scanner data usingadaptive TIN models[J].International Archives of Photogrammetry and Remote Sensing,2000,33(4):110-117.
[22]SITHOLE G,VOSSELMAN G.Filtering of airborne laser scanner data based on segmented point clouds[J].International Archives of Photogrammetry,Remote Sensing and Spatial Information Sciences,2005,36(part 3):W19.
[23]ZHANG K,CHEN S C,WHITMAN D,et al.A progressivemorphological filter for removing nonground measurements from airborne LIDAR data[J].IEEE Transactions on Geoscience and Remote Sensing,2003,41(4):872-882.
[24]DIAO X P,WU K.Improved moving window surface fittingmethod point cloud data filtering processing [J].Modern Mining,2011,27(6):59-61.
[25]SUN C L,SU W,WU H G,et al.Improved multi-level moving surface fitting lidar data filtering method [J].Infrared and Laser Engineering,2013,42(2):349-354.
[26]SOHN G,DOWMAN I J.Terrain surface reconstruction by the use of tetrahedron model with the MDL criterion[C]//International Archives of Photogrammetry Remote Sensing and Spatial Information Sciences.Natural Resources Canada,2002,34(3/A):336-344.
[27]HAUGERUD R A,HARDING D J.Some algorithms for virtual deforestation(VDF) of LIDAR topographic survey data[J].International Archives of Photogrammetry Remote Sensing and Spatial Information Sciences,2001,34(3/W4):211-218.
[28]SUI L C,ZHANG Y B,ZHANG S,et al.Airborne LiDAR point cloud data filtering based on progressive triangulation network [J].Journal of Wuhan University Information Science Edition,2011,36(10):1159-1163.
[29]HU J,YANG L,SHEN J　X,et al.A segmentation-based air-borne LiDAR point cloud data filtering [J].Journal of Wuhan University Information Science Edition,2012,37(3):318-321.
[30]PFEIFER N,KÖSTLI A,KRAUS K.Interpolation and filtering of laser scanner data-implementation and first results[J].International Archives of Photogrammetry and Remote Sensing,1998,32:153-159.
[31]KRAUS K.Linear least-squares interpolation[J].Photogrammetric Engineering,1972,26:487-493.
[32]LIU X.Airborne LiDAR for DEM generation:some critical issues[J].Progress in Physical Geography,2008,32(1):31-49.
[33]ZHANG W,QI J,WAN P,et al.An easy-to-use airborne LiDAR data filtering method based on cloth simulation[J].Remote Sensing,2016,8(6):501.
[34]BALLARD D H.Generalizing the Hough transform to detectarbitrary shapes[J].Pattern Recognition,1981,13(2):111-122.
[35]VOSSELMAN G,GORTE B G H,SITHOLE G,et al.Recog-nising structure in laser scanner point clouds[J].International Archives of Photogrammetry,Remote Sensing and Spatial Information Sciences,2004,46(8):33-38.
[36]FISCHLER M A,BOLLESR C.Random sample consensus:aparadigm for model fitting with applications to image analysis and automated cartography[J].Communications of the ACM,1981,24(6):381-395.
[37]SCHNABEL R,WAHL R,KLEINR.Efficient RANSAC forpoint-cloud shape detection[C]//Computer graphics forum.Oxford,UK:Blackwell Publishing Ltd,2007,26(2):214-226.
[38]ABDI H,WILLIAMS L J.Principal Component Analysis[J].Wiley Interdisciplinary Reviews:Computational Statistics,2010,2(4):433-459.
[39]WEINMANN M,JUTZI B,HINZ S,et al.Semantic point cloud interpretation based on optimal neighborhoods,relevant features and efficient classifiers[J].ISPRS Journal of Photogrammetry and Remote Sensing,2015,105:286-304.
[40]RABBANI T,VAN DEN HEUVEL F,VOSSELMANN G.Seg-mentation of point clouds using smoothness constraint[J].International Archives of Photogrammetry,Remote Sensing and Spatial Information Sciences,2006,36(5):248-253.
[41]KHALOO A,LATTANZI D.Robust normal estimation and region growing segmentation of infrastructure 3D point cloud models[J].Advanced Engineering Informatics,2017,34:1-16.
[42]KATZ S,TAL A.Hierarchical mesh decomposition using fuzzy clustering and cuts[J].ACM Transactions on Graphics(TOG),2003,22(3):954-961.
[43]SHAPIRA L,SHAMIR A,COHEN-OR D.Consistent meshpartitioning and skeletonisation using the shape diameter function[J].The Visual Computer,2008,24:249-259.
[44]PAPON J,ABRAMOV A,SCHOELER M,et al.Voxel cloud connectivity segmentation-supervoxels for point clouds[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.2013:2027-2034.
[45]YANG B,DONG Z,ZHAO G,et al.Hierarchical extraction ofurban objects from mobile laser scanning data[J].ISPRS Journal of Photogrammetry and Remote Sensing,2015,99:45-57.
[46]BESL P J,MCKAY N D.Method for registration of 3-D shapes[C]//Sensor fusion IV:Control Paradigms and Data Structures.Spie,1992,1611:586-606.
[47]ZHU J,JIN C,JIANG　Z,et al.Robust point cloud registrationbased on both hard and soft assignments[J].Optics & Laser Technology,2019,110:202-208.
[48]BENJEMAA R,SCHMITT F.Fast global registration of 3Dsampled surfaces using a multi-z-buffer technique[J].Image and Vision Computing,1999,17(2):113-123.
[49]YANG J,LI H,JIA Y.Go-icp:Solving 3d registration efficiently and globally optimally[C]//Proceedings of the IEEE International Conference on Computer Vision.2013:1457-1464.
[50]BIBER P,STRAßER W.The normal distributions transform:A new approach to laser scan matching[C]//Proceedings 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems(IROS 2003)(Cat.No.03CH37453).IEEE,2003,3:2743-2748.
[51]MAGNUSSON M,LILIENTHAL A,DUCKETT T.Scan registration for autonomous mining vehicles using 3D-NDT[J].Journal of Field Robotics,2007,24(10):803-827.
[52]DAS A,WASLANDER S L.Scan registration with multi-scale k-means normal distributions transform[C]//2012 IEEE/RSJ International Conference on Intelligent Robots and Systems.IEEE,2012:2705-2710.
[53]DAS A,WASLANDER S L.Scan registration using segmented region growing NDT[J].The International Journal of Robotics Research,2014,33(13):1645-1663.
[54]AIGER D,MITRA N J,COHEN-ORD.4-points congruent sets for robust pairwise surface registration[M]//ACM SIGGRAPH 2008.2008:1-10.
[55]MELLADO N,AIGER D,MITRAN J.Super 4 pcs fast globalpointcloud registration via smart indexing[C]//Computer Graphics Forum.2014,33(5):205-215.
[56]HUANG X,MEI G,ZHANG J.Feature-metric registration:Afast semi-supervised approach for robust point cloud registration without correspondences[C]//Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition.2020:11366-11374.
[57]XU Y,BOERNER R,YAO W,et al.Pairwise coarse registration of point clouds in urban scenes using voxel-based 4-planes congruent sets[J].ISPRS Journal of Photogrammetry and Remote Sensing,2019,151:106-123.
[58]MASUDA T,SAKAUE K,YOKOYA N.Registration and integration of multiple range images for 3-D model construction[C]//Proceedings of 13th International Conference on Pattern Recognition.IEEE,1996,1:879-883.
[59]KAMOUSI P,LAZARD S,MAHESHWARI A,et al.Analysis of farthest point sampling for approximating geodesics in a graph[J].Computational Geometry,2016,57:1-7.
[60]RUSINKIEWICZ S,LEVOY M.Efficient variants of the ICP algorithm[C]//Proceedings Third International Conference on 3-D Digital Imaging and Modeling.IEEE,2001:145-152.
[61]ZHONG Y.Intrinsic shape signatures:A shape descriptor for 3Dobject recognition[C]//2009 IEEE 12th International Confe-rence on Computer Vision Workshops,ICCV Workshops.IEEE,2009:689-696.
[62]FELDMAR J,AYACHE N.Rigid,affine and locally affine registration of free-form surfaces[J].International Journal of Computer Vision,1996,18(2):99-119.
[63]CHUA C S,JARVIS R.Point signatures:A new representation for 3d object recognition[J].International Journal of Computer Vision,1997,25:63-85.
[64]HUANG Y,DA F　P,TAO H　J.An automatic point cloud registration algorithm based on feature extraction [J].China Laser,2015,42(3):250-256.
[65]RUSU R B,MARTON Z C,BLODOW N,et al.Learning informative point classes for the acquisition of object model maps[C]//2008 10th International Conference on Control,Automation,Robotics and Vision.IEEE,2008:643-650.
[66]RUSU R B,BLODOW N,MARTON Z C,et al.Aligning point cloud views using persistent feature histograms[C]//2008 IEEE/RSJ International Conference on Intelligent Robots and Systems.IEEE,2008:3384-3391.
[67]RUSU R B,BLODOW N,BEETZ M.Fast point feature histograms(FPFH) for 3D registration[C]//2009 IEEE International Conference on Robotics and Automation.IEEE,2009:3212-3217.
[68]CHEN C S,HUNG Y P,CHENG J B.RANSAC-based DARCES:A new approach to fast automatic registration of partially overlapping range images[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1999,21(11):1229-1234.
[69]GELFAND N,MITRA N J,GUIBAS L J,et al.Robust global registration[C]//Symposium on Geometry Processing.2005.
[70]THEILER P W,WEGNER J D,SCHINDLER K.Keypoint-based 4-points congruent sets-automated marker-less registration of laser scans[J].ISPRS Journal of Photogrammetry and Remote Sensing,2014,96:149-163.
[71]STAMOS I,ALLEN P K.Geometry and texture recovery ofscenes of large scale[J].Computer Vision and Image Understanding,2002,88(2):94-118.
[72]YANG B,DONG Z,LIANG F,et al.Automatic registration of large-scale urban scene point clouds based on semantic feature points[J].ISPRS Journal of Photogrammetry and Remote Sensing,2016,113:43-58.
[73]HERNÁNDEZ J,MARCOTEGUI B.Point cloud segmentationtowards urban ground modeling[C]//2009 Joint Urban Remote Sensing Event.IEEE,2009:1-5.
[74]TAO W,HUA X,CHEN Z,et al.Fast and automatic registration of terrestrial point clouds using 2D line features[J].Remote Sensing,2020,12(8):1283.
[75]LI B J,LI Q Q,SHIW Z,et al.Feature extraction and modeling of urban building from vehicle-borne laser scanning data[J].International Archives of Photogrammetry,Remote Sensing and Spatial Information Science,2004,35:934-939.
[76]YANG B,ZANG Y.Automated registration of dense terrestrial laser-scanning point clouds using curves[J].ISPRS Journal of Photogrammetry and Remote Sensing,2014,95:109-121.
[77]ALDOMA A,TOMBARI F,DI STEFANO L,et al.A global hypotheses verification method for 3d object recognition[C]//Computer Vision-ECCV 2012:12th European Conference on Computer Vision.Florence,Italy,Part III 12.Springer Berlin Heidelberg,2012:511-524.
[78]BRENNER C,DOLD C,RIPPERDA N.Coarse orientation ofterrestrial laser scans in urban environments[J].ISPRS Journal of Photogrammetry and Remote sensing,2008,63(1):4-18.
[79]CHEN S,NAN L,XIAR,et al.PLADE:A plane-based descriptor for point cloud registration with small overlap[J].IEEE Transactions on Geoscience and Remote Sensing,2019,58(4):2530-2540.
[80]ZHANG X,GAO R,SUN Q,et al.An automated rectification method for unmanned aerial vehicle lidar point cloud data based on laser intensity[J].Remote Sensing,2019,11(7):811.
[81]LOWED G.Distinctive image features from scale-invariant keypoints[J].International Uournal of Computer Vision,2004,60:91-110.
[82]WANG F,YE Y,HUX,et al.Point cloud registration by combining shape and intensity contexts[C]//2016 9th IAPR Workshop on Pattern Recogniton in Remote Sensing(PRRS).IEEE,2016:1-6.
[83]JUNG S,SONG S,CHANG M,et al.Range image registrationbased on 2D synthetic images[J].Computer-Aided Design,2018,94:16-27.
[84]HERBERT B.Surf:Speeded up robust features[J].Computervision and image understanding,2008,110(3):346-359.
[85]YANG Y,CHEN W,WANG M,et al.Color point cloud registration based on supervoxel correspondence[J].IEEE Access,2020,8:7362-7372.
[86]LIU X,PENG X,YIN Y,et al.A coarse registration method of range image based on SIFT[C]//Electronic Imaging and Multimedia Technology V.SPIE,2007,6833:249-256.
[87]EO Y D,PYEON M W,KIMS W,et al.Coregistration of terrestrial lidar points by adaptive scale-invariant feature transformation with constrained geometry[J].Automation in Construction,2012,25:49-58.
[88]QI C R,SU H,MO K,et al.Pointnet:Deep learning on pointsets for 3d classification and segmentation[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.2017:652-660.
[89]JIANG M,WU Y,ZHAOT,et al.Pointsift:A sift-like network module for 3d point cloud semantic segmentation[J].arXiv:1807.00652,2018.
[90]LI Y,BU R,SUNM,et al.Pointcnn:Convolution on x-transformed points[J].Advances in Neural Information Processing Systems,2018,31.
[91]WANG Y,SUN Y,LIU Z,et al.Dynamic graph cnn for learning on point clouds[J].ACM Transactions on Graphics(tog),2019,38(5):1-12.
[92]XU Y,FAN T,XUM,et al.Spidercnn:Deep learning on point sets with parameterized convolutional filters[C]//Proceedings of the European conference on computer vision(ECCV).2018:87-102.
[93]LI Z,WANG F,WANG N.Lidar r-cnn:An efficient and universal 3d object detector[C]//Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition.2021:7546-7555.
[94]ZHANG Y,HU Q,XU G,et al.Not all points are equal:Learning highly efficient point-based detectors for 3d lidar point clouds[C]//Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition.2022:18953-18962.
[95]YUAN H,PANG J K,MO J W.Research on point cloud simplification algorithm based on voxelized grid subsampling [J].Television Technology,2015,39(17):43-47.
[96]MATURANA D,SCHERER S.Voxnet:A 3d convolutionalneural network for real-time object recognition[C]//2015 IEEE/RSJ International Conference on Intelligent Robots and Systems(IROS).IEEE,2015:922-928.
[97]HEGDE V,ZADEH R.Fusionnet:3d object classification using multiple data representations[J].arXiv:1607.05695,2016.
[98]BROCK A,LIM T,RITCHIE J M,et al.Generative and discriminative voxel modeling with convolutional neural networks[J].arXiv:1608.04236,2016.
[99]HE C,ZENG H,HUANG J,et al.Structure aware single-stage 3d object detection from point cloud[C]//Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition.2020:11873-11882.
[100]YE M,XU S,CAO T.Hvnet:Hybrid voxel network for lidar based 3d object detection[C]//Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition.2020:1631-1640.
[101]DENG J,SHI S,LI P,et al.Voxel r-cnn:Towards high perfor-mance voxel-based 3d object detection[C]//Proceedings of the AAAI Conference on Artificial Intelligence.2021,35(2):1201-1209.
[102]CHEN Y,LI Y,ZHANG　X,et al.Focal sparse convolutional networks for 3d object detection[C]//Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition.2022:5428-5437.
[103]SHI S,JIANG L,DENG J,et al.PV-RCNN++:Point-voxelfeature set abstraction with local vector representation for 3D object detection[J].International Journal of Computer Vision,2023,131(2):531-551.
[104]WU H,WEN C,LI W,et al.Transformation-equivariant 3d object detection for autonomous driving[C]//Proceedings of the AAAI Conference on Artificial Intelligence.2023,37(3):2795-2802.
[105]YANG H,WANG W,CHEN M,et al.Pvt-ssd:Single-stage 3d object detector with point-voxel transformer[C]//Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition.2023:13476-13487.
[106]KANG Z X,WANG S Z,CUI Y Y,et al.Transformer-based voxelized laser point cloud target detection algorithm [J].Laser and Infrared,2023,53(2):202-207.
[107]YANG Y　K,WANG A　H.Multi-scale laser point cloud learning network based on point-voxel combination [J].Laser Magazine,2023,44(4):134-139.
[108]LAWIN F J,DANELLJAN M,TSOSTEBERG P,et al.Deepprojective 3D semantic segmentation[C]//17th International Conference Computer Analysis of Images and Patterns(CAIP 2017).Ystad,Sweden,Part I 17.Springer International Publi-shing,2017:95-107.
[109]BOULCH A,GUERRY J,LE SAUX B,et al.SnapNet:3D point cloud semantic labeling with 2D deep segmentation networks[J].Computers & Graphics,2018,71:189-198.
[110]WU B,WAN A,YUE X,et al.Squeezeseg:Convolutional neural nets with recurrent crf for real-time road-object segmentation from 3d lidar point cloud[C]//2018 IEEE International Confe-rence on Robotics and Automation(ICRA).IEEE,2018:1887-1893.
[111]MILIOTO A,VIZZO I,BEHLEY J,et al.Rangenet++:Fast and accurate lidar semantic segmentation[C]//2019 IEEE/RSJ International Conference on Intelligent Robots and Systems(IROS).IEEE,2019:4213-4220.
[112]BARRERA A,GUINDEL C,BELTRÁN J,et al.Birdnet+:End-to-end 3d object detection in lidar bird's eye view[C]//2020 IEEE 23rd International Conference on Intelligent Transportation Systems(ITSC).IEEE,2020:1-6.
[113]ZHOU Y,SUN P,ZHANG Y,et al.End-to-end multi-view fusion for 3d object detection in lidar point clouds[C]//Conference on Robot Learning.PMLR,2020:923-932.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed