基于人体截面点云的围度尺寸计算
|
摘要
为简化围度尺寸计算过程,首先将三维人体截面点云转化到平面坐标系内,然后采用快速比较法获取点集中的4个极值点,并根据极值点将点集分成4个子区域,根据每个子区域点集的凸包具有单调性这种特性,对区域内点集的x和z坐标值进行排序比较去掉部分凹点,再通过计算点与相邻2点组成向量的叉积判断其夹角范围获取截面凸包点,将最终凸包点连接起来即为人体围度尺寸。结果表明:本文方法与Graham扫描法相比,二者时间复杂度相同,计算结果一致,但本文方法在程序上更容易实现,且通过简单的排序比较法简化初始点集可减少凸包顶点回溯迭代次数,从而提高计算人体围度尺寸的效率。
In order to simplify the calculation process on the circumference size,the coordinates of section points in space were first transformed to 2-D plane. Then by the quick comparing sorting,four extreme points were acquired,and based on the extremes points the point set was divided into four subsets. The convex hull of every subset was monotonous,so some concave points were directly deleted by sorting and comparing the coordinates x and z. The final convex hull points were determined by the inner angle of the adjacent three points calculated by the cross product. The line by connecting the points in order was the body circumference line and its length was the size. Comparing with the Graham scanning method,the method has the same time complexity and same results. However,it is easier to be programmed,and by simplifying the point set by easily sorting and comparing,the method can reduce the number of backtracks and effectively improve the computing efficiency of body's circumference sizes.
In order to simplify the calculation process on the circumference size,the coordinates of section points in space were first transformed to 2-D plane. Then by the quick comparing sorting,four extreme points were acquired,and based on the extremes points the point set was divided into four subsets. The convex hull of every subset was monotonous,so some concave points were directly deleted by sorting and comparing the coordinates x and z. The final convex hull points were determined by the inner angle of the adjacent three points calculated by the cross product. The line by connecting the points in order was the body circumference line and its length was the size. Comparing with the Graham scanning method,the method has the same time complexity and same results. However,it is easier to be programmed,and by simplifying the point set by easily sorting and comparing,the method can reduce the number of backtracks and effectively improve the computing efficiency of body's circumference sizes.
引文
[1]方群,尚媛园,郭国栋,等.基于点云模型的人体尺寸提取算法[J].光学技术,2017,43(6):528-532.FANG Qun,SHANG Yuanyuan,GUO Guodong,et al.Extraction of human body measures based on 3D point clouds[J].Optical Technique,2017,43(6):528-532.
[2]葛宝臻,郭华婷,彭博,等.基于人体特征提取的模特体型尺寸自动测量方法[J].纺织学报,2012,33(4):129-135.GE Baozhen,GUO Huating,PENG Bo,et al.Automatic model style measurement based on automatic body feature extraction from 3-D scanning data[J].Journal of Textile Research,2012,33(4):129-135.
[3]赖军,王博,付全,等.基于点云模型的人体尺寸自动提取方法[J].中南大学学报(自然科学版),2014,45(8):2676-2683.LAI Jun,WANG Bo,FU Quan,et al.Automatic extraction method of human body sizes based on 3Dpoint clouds[J].Journal of Central South University(Science and Technology Edition),2014,45(8):2676-2683.
[4]温佩芝,马超,胡俊榕,等.基于国家标准的三维扫描人体尺寸提取技术[J].计算机工程与科学,2014,36(6):1114-1119.WEN Peizhi,MA Chao,HU Junrong,et al.Measurement of human body's feature dimensions based on the national standards[J].Computer Engineering&Science,2014,36(6):1114-1119.
[5]GRAHAM R L.An efficient algorithm for determining the convex hull of a finite planar set[J].Information Processing Letters,1972,1(4):132-133.
[6]JOSE Oswaldo Cadenas,GRAHAM M Megson,CRIS LLuengo Hendriks.Preconditioning 2D integer data for fast convex hull computations[J].Pios One,2016,11(3):e0149860.
[7]刘凯,夏苗,杨晓梅.一种平面点集的高效凸包算法[J].工程科学与技术,2017,49(5):109-116.LIU Kai,XIA Miao,YANG Xiaomei.An effective 2Dconvex hull algorithm[J].Advanced Engineering Sciences,2017,49(5):109-116.
[8]李必栋,闫浩文,王中辉,等.坐标排序的离散点凸包生成算法[J].测绘科学,2017,42(2):14-17.LI Bidong,YAN Haowen,WANG Zhonghui,et al.Algorithm of convex hull generation for point sets based on sorted coordinate[J].Science of Surveying and Mapping,2017,42(2):14-17.
[9]NG Chi,LIM Johan,LEE Kyeong.A fast algorithm to sample the number of vertexes and the area of the random convex hull on the unit square[J].Computational Statistics,2014,29(5):1187-1205.
[10]WANG Pu,EMMERICH Michael,LI Rui,et al.Convex hull-based multi-objective genetic programming for maximizing ROC performance[J].IEEE Transactions on Evolutionary Computation,2015,19(2):188-200.
[11]GU Xiaoqing,CHUNG Fulai,WANG Shitong.Fast convex-hull vector machine for training on large-scale ncRNA data classification tasks[J].Knowledge-Based Systems,2018,151(7):149-164.
[12]陈明晶,方源敏,陈杰.初始凸包对改进快速凸包算法效率的影响[J].测绘科学,2016,41(7):23-27.CHEN Mingjing,FANG Yuanmin,CHEN Jie.Influence of initial convex hull on the efficiency of quick-hull algorithm[J].Science of Surveying and Mapping,2016,41(7):23-27.
[2]葛宝臻,郭华婷,彭博,等.基于人体特征提取的模特体型尺寸自动测量方法[J].纺织学报,2012,33(4):129-135.GE Baozhen,GUO Huating,PENG Bo,et al.Automatic model style measurement based on automatic body feature extraction from 3-D scanning data[J].Journal of Textile Research,2012,33(4):129-135.
[3]赖军,王博,付全,等.基于点云模型的人体尺寸自动提取方法[J].中南大学学报(自然科学版),2014,45(8):2676-2683.LAI Jun,WANG Bo,FU Quan,et al.Automatic extraction method of human body sizes based on 3Dpoint clouds[J].Journal of Central South University(Science and Technology Edition),2014,45(8):2676-2683.
[4]温佩芝,马超,胡俊榕,等.基于国家标准的三维扫描人体尺寸提取技术[J].计算机工程与科学,2014,36(6):1114-1119.WEN Peizhi,MA Chao,HU Junrong,et al.Measurement of human body's feature dimensions based on the national standards[J].Computer Engineering&Science,2014,36(6):1114-1119.
[5]GRAHAM R L.An efficient algorithm for determining the convex hull of a finite planar set[J].Information Processing Letters,1972,1(4):132-133.
[6]JOSE Oswaldo Cadenas,GRAHAM M Megson,CRIS LLuengo Hendriks.Preconditioning 2D integer data for fast convex hull computations[J].Pios One,2016,11(3):e0149860.
[7]刘凯,夏苗,杨晓梅.一种平面点集的高效凸包算法[J].工程科学与技术,2017,49(5):109-116.LIU Kai,XIA Miao,YANG Xiaomei.An effective 2Dconvex hull algorithm[J].Advanced Engineering Sciences,2017,49(5):109-116.
[8]李必栋,闫浩文,王中辉,等.坐标排序的离散点凸包生成算法[J].测绘科学,2017,42(2):14-17.LI Bidong,YAN Haowen,WANG Zhonghui,et al.Algorithm of convex hull generation for point sets based on sorted coordinate[J].Science of Surveying and Mapping,2017,42(2):14-17.
[9]NG Chi,LIM Johan,LEE Kyeong.A fast algorithm to sample the number of vertexes and the area of the random convex hull on the unit square[J].Computational Statistics,2014,29(5):1187-1205.
[10]WANG Pu,EMMERICH Michael,LI Rui,et al.Convex hull-based multi-objective genetic programming for maximizing ROC performance[J].IEEE Transactions on Evolutionary Computation,2015,19(2):188-200.
[11]GU Xiaoqing,CHUNG Fulai,WANG Shitong.Fast convex-hull vector machine for training on large-scale ncRNA data classification tasks[J].Knowledge-Based Systems,2018,151(7):149-164.
[12]陈明晶,方源敏,陈杰.初始凸包对改进快速凸包算法效率的影响[J].测绘科学,2016,41(7):23-27.CHEN Mingjing,FANG Yuanmin,CHEN Jie.Influence of initial convex hull on the efficiency of quick-hull algorithm[J].Science of Surveying and Mapping,2016,41(7):23-27.