Egyptian Informatics Journal（2015）16，175开罗大学埃及信息学杂志www.elsevier.com/locate/eijwww.sciencedirect.com原创文章基于和声搜索的G1有理三次Bézier曲线数据拟合Najihah Mohameda，*，Ahmad Abd Majidb，Abd Rahni Mt Piahba马来西亚彭亨大学工业科学技术学院，Lebuhraya Tun Razak，26300Kuantan，马来西亚彭亨b马来西亚槟榔屿大学数学科学学院，11800 USM，接收日期：2014年12月3日;修订日期：2015年3月23日;接受日期：2015年2015年6月6日在线发布摘要提出了一种用于有理三次Bézier曲线数据拟合的元启发式算法--和声搜索（HS）。 HS算法是一种无导数的实参数优化算法，它的灵感来自于音乐即兴创作过程中寻找完美和谐状态的过程。HS算法适用于多变量非线性优化问题。它主要是通过对整个数据集的每一段节点使用具有G1连续性的有理三次Bézier曲线进行数据拟合来实现的。这种方法在使技术自动化方面有重大贡献。HS用于优化中间点的位置和形状参数的值。测试轮廓图像和对比实验分析，以显示有效性和鲁棒性。HS和其他两种不同的元启发式算法之间的统计测试中使用的几个轮廓图像的分析。所有的算法都得到了一个近似最优解，但HS算法得到的结果优于其他两种算法。©2015由Elsevier B.V.代表开罗大学计算机与信息学院制作和主办。 这是一篇基于CC BY-NC-ND许可证的开放获取文章（http：//creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍数据拟合是计算机图形学和数学中的一个重要研究领域，也是计算机图形学、图像处理、形状*通讯作者。开罗大学计算机和信息系负责同行审查。建模和数据挖掘。根据不同的应用，不同类型的曲线，如参数曲线，隐式曲线和细分曲线用于拟合。数据拟合一般分为近似和插值两种类型。在近似拟合方案下，曲线必须合理地接近数据点，但不是必需的 [12]以其为经。有理Bézier曲线具有简洁的几何表达形式，并且可以通过移动控制点或修改权值进行变形，因此在CAD/CAGD领域得到了广泛的应用。研究了有理Bézier函数数据拟合，确定了基于Hausdorff距离的曲线最佳二次曲线逼近http://dx.doi.org/10.1016/j.eij.2015.05.0011110-8665© 2015由Elsevier B. V.代表开罗大学计算机与信息学院制作和主办。这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier关键词有理三次Bézier;数据逼近;和声搜索3223hiX1=2JS 1/4秒¼1=2jp-pS ¼1北纬176度 Mohamed等人函数[7]，利用C_（？）u;v_（？）-连续概念用B_（？）zier曲线逼近有理B_（？）zier曲线[1]，并利用全局Lp-误差加权逐步迭代逼近方案，逐步调整控制点，作为逼近有理B_（？）zier曲线的迭代方法[9]。最近，一些研究人员，如黄等。[6]通过比较Hausdorff 距离、移位控制和基于L2范数的逼近三种方法，得到了用三次Bézier逼近n次Bézier的偏移量，从而得到了更好的逼近效果。而Yanget al.[21]着重于曲面上的曲线，提出了一种基于三次有理Bézier曲面的抛物线逼近方法。本研究还使用了近似曲线和精确曲线之间的Hausdorff距离;近似值控制在用户指定的公差范围内。Shen等人[17]提出了一种证明近似作为一种优化方法，以选择三次有理Bézier曲线中的适当权重来近似给定曲线。该方法的误差由其四面体的大小控制，通过细分曲线段使其收敛于零。Stamati和Fudos[20]提出了一种快速曲线逼近方法，该方法用三次有理Bézier曲线逼近原始数据。该方法结合了最小二乘近似和连续，的约束，以确保G1相邻之间的连续性本文首先概述了有理三次贝塞尔曲线、最小二乘误差和基于中心法的参数化方法以及数据拟合的一些基本概念。还对HS进行了温和的概述。我们提出的数据集的两个部分之间的G1连续性的概念。最后给出了该方法的在四种不同的轮廓图像上，将该方法与遗传算法和粒子群优化算法进行本文还进行了统计分析，以验证该方法的可靠性和有效性。2. 有理三次Be′zier数据拟合有理三次贝塞尔函数定义为：设f是给定的一组数据点，其中s10为了实现HS，Eq. （4）作为目标函数。本 研究中的HS参数为HM=5，HMCR=0.9，PAR=0.3和bw=0.03。所有这些参数值都是HS社区的常用选择，并且也得到了[13]的经验结果的支持。根据Omran和Mahdavi[13]的结果，一般来说，使用小型HM似乎是一个很好的逻辑选择，具有减少空间需求的额外优势。事实上，由于HM类似于音乐家的短期记忆， 已知是小的，使用小的HM是合乎逻辑的，因为在论文中 使用的HM 的最小值是 5 。至于 HMCR ，HMCR的大值（例如0.95）通常改善HS的性能。实验表明，使用一个相对较小的PAR恒定值似乎提高了HS的性能。首先，从图像的轮廓边界提取的所有数据被分解成几个曲线段。拟合所有数据的程序包括3个部分：原始段、两段之间的段和结束段。表1G1连续性分析。第n节图5图6图7图8bxb yBxByBxByBxBy14.26051098 4.260510980.018935340.0189353410.4311878010.431187800.599106520.5991065220.164403730.047070520.047070520.381010310.381010391.729658801.7296588034567电话：+86-21- 277452417传真：+86-21 - 277452417电话：+86-031 - 8888888传真：+86-031 - 888888881.01815645 1.018156450.015850932.55695847 2.556958473.304165270.418119911.530581220.371982734.124178863.304165270.418119911.530581220.371982734.124178864.322937582.059560261.818494520.887087111.170724194.322937582.059560261.818494520.887087111.170724195.192186891.325443460.921384560.651614961.089338125.192186891.325443460.921384560.651614961.089338128910112019 - 04 - 22 00：00：00粤ICP备16033243号-10.30432804 0.304328043.74608222 3.74608222-2.631916940.437264590.409990409-3.877514530.659458040.437264590.409990416.624298580.423078817.932916190.202155431.234692810.423078817.932916190.202155431.234692811.067433860.395542240.846027431.668669111.067433860.395542240.846027431.6686691112 - 1.50717641 0.1875559713-2.00241487 4.3100860414 1.04244158 1.0424415815 1.73650617 1.73650617180N. Mohamed等人半]6.1. 原始部分图8字母“S”轮廓拟合数据高光段由113个数据点组成，HS误差=0.0008，GA误差=0.0025，PSO误差=0.0803。在该部分中，仅奇数段（1，3，.. . ），并且将在没有任何约束的情况下近似分段中的所有数据。w1和w2的大小在0; 2 . C1和C2的搜索空间估计如下：设线段由点集d1; d2;···; d endd 2 R2组成，Cω1和Cω2是线段上的极值点. 每个Cω1和Cω2的大小由下式确定：Cωi½jdmax-dminj的大小;1/1;2/96.2. 两段对于该部分，偶数段（2，4，.. . ），并且段中的所有数据将用某些约束近似，这些约束如下：假设一组数据有三个段，段1、段2和段3与图 3（a）、有理三次Be′zier曲线的每一段(a)飞机（1875个数据点）(b)梨（1433个数据点）-o HSx GA* PSO- o HSx GA* PSO- o HSx GA* PSO- o HSx GA* PSO(c) 字母图9测试轮廓图像的每个片段的最小最小二乘误差。轮廓图像HS* GAx PSOG_1有理三次Bézier曲线的数据拟合1812ΣΣ表2 四个轮廓图像的描述性数据最好最糟糕是说中值方差标准偏差字母HS0.05000.14000.10870.10630.000990.03153GA0.09000.17000.15990.15330.001720.04151PSO0.23000.73000.56100.53770.037450.19353字母HS0.11510.25670.16480.16330.001290.03597GA0.18370.90360.60070.59630.036360.19068PSO0.71271.15920.93620.95950.010720.10354飞机HS0.04370.08900.0682470.066650.000130.01161GA0.02900.13930.0742570.07120.000470.02162PSO0.10820.37160.225880.222150.002410.04910梨HS0.01230.02220.016950.01680.000000.00274GA0.02350.04260.032260.03210.000030.00512PSO0.11070.24820.1745530.17280.001790.04227应包括：C0;C1;C2;C 3;C4，控制点。所有这些三个部分是G1。因此，数据拟合在段中必须填充组内0.052788262 87 0.000607涉及段1和段3的某些约束。1和2的大小是1/2;2：5]。虽然Cω1和Cω2的搜索空间类似于前一节，但其中一个变量，Ci1/2xi;yi1/2取决于另一个变量，对于该变量，第一卷;第二卷 必须是共线的。对于本节，HS的决策变量的数量减少。6.3. 端部区段如果总数据点是偶数，则将考虑结束段，段结束。段中的所有数据都将近似于某些约束，这些约束是：表3正态性检验Kolmogorov–Smirnov统计DFSig.统计DFSig.字母0.087300.2000.960300.308字母0.108300.2000.971300.572字母0.169300.0290.943300.109字母0.101300.2000.947300.138字母0.172300.0240.932300.056字母0.183300.0120.935300.067飞机_HS0.073300.2000.980300.825飞机_GA0.102300.2000.962300.345飞机_PSO0.112300.2000.953300.204梨_HS0.172300.0240.938300.079梨_GA0.102300.2000.973300.621Pear_PSO0.088300.2000.948300.153表4独立组方差分析。ANOVA变异来源SSDFMSFp值F临界值(a)字母组间组内3.6815338651.164919164.846453025287891.8407670.01339137.47453781.16929E-273.101296（b）组内组间字母“s”总8.9742847551.40285450110.37713926287894.4871420.016125278.27651.56918E-383.101295757（c）组内组间飞机总数0.478740.0873930.566133287890.239370.001005238.2945.03791E-363.101295757(d)梨组间0.45320599520.226603373.4631.99546E-433.101296共计0.505994257182N. Mohamed等人端[半小时后见]半]表5两个样本方差的F检验双样本F检验了产生差异的双样本F检验了产生差异的双样本F检验了产生差异的GAHSPSOHSPSOGA(a)字母是说0.1599266670.10868是说0.5610433330.10868是说0.5610433330.1599267方差0.0017230990.000994方差0.0374525360.000994方差0.0374525360.0017231意见3030意见3030意见3030DF2929DF2929DF2929F1.733516623F37.67896352F21.73556516P（F=f）1-尾巴0.072201294P（F=f）1-尾巴2.71646E-16P（F=f）1-尾巴4.75936E-13F临界单尾1.619899621F临界单尾1.860811435F临界单尾1.860811435双样本F检验了产生差异的双样本F检验了产生差异的双样本F检验了产生差异的HSGAHSPSOGAPSO(b)字母是说0.1648333330.6007是说0.1648333330.936147是说0.60070.936147方差0.0012934920.03636方差0.0012934920.010721方差0.0363595120.010721意见3030意见3030意见3030DF2929DF2929DF2929F0.035575064F0.120647051F3.391337565P（F=f）1-尾巴1.4988E-14P（F=f）1-尾巴8.71309E-08P（F=f）1-尾巴0.000769416F临界单尾0.537399965F临界单尾0.537399965F临界单尾1.860811435双样本F检验了产生差异的双样本F检验了产生差异的双样本F检验了产生差异的HSGAHSPSOGAPSO(c)飞机是说0.0682470.074257是说0.0682466670.22588是说0.0742566670.22588方差0.0001350.000468方差0.0001347650.002411209方差0.0004675740.002411意见3030意见3030意见3030DF2929DF2929DF2929F0.288223F0.055891197F0.193916687P（F=f）1-尾巴0.000634P（F=f）1-尾巴6.20171E-12P（F=f）1-尾巴1.54586E-05F临界单尾0.412637F临界单尾0.412636754F临界单尾0.412636754F-双样本方差检验F-双样本方差检验F-双样本方差检验HS GA HS PSO GA PSO(d) 梨平均值0.03226平均值0.01695 0.174553平均值0.03226 0.174553333差异7.51776E-06 2.62E-05 差异7.51776E-06 0.001787差异2.62E-05 0.001786553观察30 30观察30 30df 29 29 df 29 290.0042079690.014673P（F=f）单尾F临界单尾0.000607464P（F=f）一-尾巴0.412636754F临界单尾0P（F=f）one-尾巴0.412636754F临界单尾00.412637假设一组数据有两个最后的段，segend-1;segend如图3（b）所示。所有这两个段都应该具有G1连续性的平滑关节。因此，在seg中拟合数据必须满足涉及segend-1的某些约束。1和2的大小是1/2;2：5]。在寻找C1的同时和C2类似于前一节，但其中一个变量，C1，x1，y1，取决于最后一个接头处的另一个变量也就是说，第一节段 ;C3; segend-1C0;segend 节段末端必须是共线的。7. 演示和实验结果建议的数据拟合方法已在图1和图2中实际实施。4-7（a）.每个数据段在其域中均匀分布的u值处进行评估，以在0; 1的间隔上生成201个数据点的集合。图4（d）、5（d）、6（c）和7（d）是最佳拟合曲线，其中OG是原始图，RB是相应的有理Bézier曲线。 图图4（c）示出了连接G_1有理三次Bézier曲线的数据拟合183表6假设方差不等的两个样本的Tt检验：假设方差不等的双样本t检验：双样本假设不相等方差t检验：假设方差HS GA HS PSO GA PSO(a) 字母平均值0.10868 0.159927平均值0.10868 0.561043 平均值0.159926667 0.5610433差异0.000993991 0.001723差异0.000993991 0.037453 0.001723099 0.0374525观察30 30观察30 30假设平均差异0假设平均偏差0假设0平均偏差df 54 df 31 df 32tstat-5.38485789t stat-12.6362865tstat-11.1000084P（T=t）单尾8.08374E-07P（T=t）one-尾巴4.56312E-14P（T=t）one-尾巴8.30798E-13t临界单尾2.397409645t临界单尾2.452824193t临界单尾2.448677634P（T=t）双尾1.61675E-06P（T=t）二-尾巴9.12624E-14P（T=t）二-尾巴1.6616E-12t临界双尾2.669984796t临界双尾2.744041919t临界双尾2.738481482t检验：假设方差不等的双样本t检验：双样本假设不相等方差t检验：假设方差HS GA HS PSO GA PSO(b) 字母平均值0.164833333 0.6007平均值0.164833333 0.936147 平均值0.6007 0.936147差异0.001293492 0.03636差异0.001293492 0.010721 差异0.036359512观察30 30观察30 30假设平均差异0假设平均偏差0假设0平均偏差DF 31 DF 36 DF 45tstat-12.3030977t stat-38.5419363tstat-8.4676361P（T=t）单尾9.14105E-14P（T=t）one-尾巴3.6084E-31P（T=t）one-尾巴3.63208E-11t临界单尾1.695518783t临界单尾1.688297714t临界单尾1.679427393P（T=t）双尾1.82821 E-13P（T=t）二-尾巴7.2168E-31P（T=t）二-尾巴7.26417E-11t临界双尾2.039513446t临界双尾2.028094001t临界双尾2.014103389t检验：假设方差不等的双样本t检验：双样本假设不相等方差t检验：假设方差HS GA HS PSO GA PSO(c) 飞机平均值0.068247 0.074257平均值0.068246667 0.22588平均值0.074256667 0.22588差异0.000135 0.000468差异0.000134765 0.002411 差异0.000467574 0.002411观察30 30观察30 30假设平均差异0假设平均偏差0假设0平均偏差DF 44 DF 32 DF 40tstat-1.34127tstat-17.1112491tstat-15.4782647P（T=t）单尾0.093358P（T=t）一-尾巴5.79073E-18P（T=t）one-尾巴8.71294E-19t临界单尾1.30109t临界单尾1.308572793t临界单尾1.303077053P（T=t）双尾0.186717P（T=t）二-尾巴1.15815E-17P（T=t）二-尾巴1.74259E-18t临界双尾1.68023t临界双尾1.693888748t临界双尾1.683851013t检验：假设方差不等的双样本t检验：双样本假设不相等方差t检验：假设方差HS GA HS PSO GA PSO(d) 梨0.01695 0.03226平均值0.01695 0.174553 平均值0.03226 0.174553差异7.51776E-06 2.62E-05差异7.51776E-06 0.001787 差异2.62142E-05 0.001787观察30 30观察30 30假设0假设0（接下页）184N. Mohamed等人表6（续）t检验：假设方差不等的双样本t检验：双样本假设不相等方差t检验：假设方差HSGAHSPSO遗传粒子群算法平均偏差平均偏差平均偏差DF44东风29DF30测试状态P（T=t）1--14.43826451.33021E-18测试统计-20.3800972P（T=t）one-4.92526E-19测试状态P（T=t）1--18.30518713.95498E-18尾巴t临界单尾P（T=t）双尾2.4141343682.66042E-18尾巴t临界单尾2.46202136P（T=t）2 -9.85052E-19尾巴尾巴t临界单尾P（T=t）双尾2.4572615427.90995E-18t临界双尾2.692278266测试临界双尾2.756385904t临界双尾2.749995654在每个段中的所有Ci，表1总结了上述测试轮廓图像的G1每个测试函数的b值根据公式计算。（八）、7.1. 与其他方法的比较和分析我们的G1HS方法对于上述测试轮廓图像表现良好为了支持这一主张，与最近的基于软计算技术的替代曲线拟合进行了比较 有一些软计算方法用于此数据拟合问题，如Ga′lvez等人使用GA的B样条曲线拟合。[4]、Sarfraz[19]和Yahya[15-16]提出了一种用粒子群算法这里比较了HS、GA和PSO在相似数据点上的应用。PSO的程序取自[2]。 图 8突出显示了字母“s”的一部分，并表明HS在相同的时间范围内更好地接近数据点。图9总结了测试轮廓图像和图表中每个段的最小二乘误差;第一幅图像的段4和10、第三幅图像的段3以及第四幅图像的段15中HS的输出大于其他段，因为段前有尖点。然而，HS方法通过查看数据集中的最小二乘误差的总和来更好地概述。7.2. 统计分析所有的进化算法，包括HS，GA和PSO都是基于随机种群的搜索方法。因此，无法保证始终达到最佳解决方案因此，为了否定HS算法能更好地逼近全局最优解的保证，本文对使用该算法的优化问题进行了比较，并进行了统计分析采用HS、GA和PSO三种方法的四个轮廓的30个样本数据进行总最小二乘误差的计算，所有数据的计算时间都是固定的。从表2中可以清楚地看出，基于描述性数据的所有图像的主要方法是HS。所有样本数据均已通过Shapiro-Wilks统计学评估其正态性，以验证其方差之间的显著性差异。正态性结果见表3。根据表4，有足够的证据表明，在1 -10%的显著性水平下1.4988· 10-14 ， 8.7131· 10-8; 0.0006 ， 6.2017· 10-12;0.0006，0.0000）。虽然表5显示，在1-10%的显著性水平下，HS的平均值是与GA和PSO相比最小的值8.0837· 10-7，4.5621· 10-14; 9.1411· 10-14，3.6084· 10-31; 0.0934,5.7907· 10-18; 1.3302· 10-18，4.9253· 10-19）。同时，表6也支持HS与其他两种方法相比的相同这些结果表明，在这项研究中，HS被发现为所有测试轮廓图像的每个片段使用有理三次贝塞尔进行数据拟合提供了最佳拟合。这些结果有力地表明，HS方法是更稳定和准确的GA和PSO相比。8. 结论一个衍生的自由实参数优化技术，基于HS，实现数据拟合。该技术优化了有理三次Be′zier曲线的控制点和形状参数，以逼近数据集。对于整个数据集的每个分段节点，通过G1连续性进行数据拟合的技术，有理贝塞尔最终在逼近数据时产生最佳结果。它提供了具有有效计算成本的最佳拟合。在四种不同的轮廓图像上进行了HS、GA和PSO的比较，并对每个30个样本数据集进行了统计检验。通过对样本数据的统计分析，有充分的证据表明，HS法的误差值小于其他两种方法。引用[1] 蔡宏健，王国健. 基于有理Bézier曲线端点连续条件的矩阵表示 ， 给 出 了 有 理 B é zier 曲 线 的 约 束 逼 近 . Comput AidedDes2010;42（6）：495-504.[2] Das S，Abraham A，Konar A.粒子群最佳化与差异演化演算法：技术分析、应用与混合观点。Stud Comput Intel（SCI）2008;116：1-38.[3] Ga'lvezA，IglesiasA. 一种有效的自由节点样条数据拟合的粒子群优化方法。Comput AidedDes 2011;43（12）：1683-92.G_1有理三次Bézier曲线的数据拟合185[4] 放大图片作者：A.基于迭代两步遗传算法的多项式B样条曲面重构方法Inf Sci2012;182：56-76.[5] 吉姆ZW，西姆K-B。无参数设置和声搜索算法。应用数学计算2010;217：3881-9.[6] 黄文祥，靳春杰，王国杰.用三次LN 曲线逼近Bézier曲线应用数学计算2011;218：3083-92.[7] 作者：Kim T.基于Hausdorff距离求两个相容二次曲线的卷积曲线的最佳二次曲线逼近。Comput Aided Des2009;41（7）：513-24.[8] Lee KS，Geem ZW.一种新的连续工程优化元启发式算法：和声搜索理论与实践。计算方法应用机械工程2005;194：3902-33.[9] 卢湖 有理Bézier曲线的基于样本的多项式逼近。J Comput ApplMath2011;235（6）：1557-63.[10] Mahdavi M，Fesanghary M，Damangir E.一种求解优化问题的改进和声搜索算法。应用数学计算2007;188（2）：1567-79.[11] 马什湾计算机图形学和CAD应用几何学。第2版，London：Springer-Verlag; 2005年。[12] Mortenson ME. Geometric Modeling.加拿大：John Wiley&Sons;1997年。[13] 迈赫达维· 奥姆兰全球最佳和声搜索。应用数学计算2008;198：643-56.[14] Yahya F，Ali JM，Majid AA，Ibrahim A. 阿拉伯字符G1曲线拟合的自动生成。在：计算机图形成像和可视化国际会议CGIV 06; 2006年。p. 1比6[15] Yahya ZR，M Piah AR，Majid AA.基于粒子群优化的G1连续二次曲线拟合。2011年第15届信息可视化国际会议; 2011年。第497-501页。[16] Yahya ZR，Piah ARM，Majid AA.用进化计算拟合二次曲线。J Math Stat2012;8（1）：107-10.[17] 沈丽艳，袁春明，高晓生.证明了参数空间曲线与三次B样条曲线的近似。计算机辅助设计2012;29：643-63。[18] 萨尔弗拉兹湾基于模拟退火算法的三次样条轮廓矢量化。IntJ Comp Math2010;87（8）：1736-51.[19] 萨尔弗拉兹湾图像轮廓矢量化的智能方法。JSoftware EngAppl 2012;5：78-83.[20] 斯塔马蒂五世、富多斯岛重建3D特征边界。Comput-Aid DesAppl 2008;5（1[21] 杨永健，曾伟，杨春玲，孟晓雄，勇俊华，邓波. NURBS曲面上的G1连续近似曲线.计算机辅助设计2012;44：824-34。
我的内容管理
收起
我的收益 登录查看自己的收益
我的积分
登录查看自己的积分
我的C币
登录后查看C币余额
我的收藏 
我的下载 
下载帮助 
