0 引　言

智能化设计是当前非常活跃的前沿研究领域，其涉及多领域学科交叉并依赖于大数据等技术的支持。对于船舶工程来说，每艘船几乎都是一个定制品，新的船型都需要重新设计或进行改型设计等个性化设计。传统的设计方法非常依赖设计者，引入智能设计的可以大大减少设计者的工作量^[1]。

数据库（Database）是计算机技术在船海工程中的典型应用，通过数据库技术可以建立船舶复杂数据之间的关联，提高海量信息的管理能力^[2]。数据库技术也通常运用在各类船舶的初步设计当中，例如海军船舰数据库^[3]、船舶性能数据库^[4]。越来越多的学者在船型数据库的基础上挖掘船型中的知识因子^[5]。SQL是一门用于操作关系型数据库的语言，其特点为简洁高效、非过程化、在数据库方面高度统一^[6]，能够应用在船舶领域中需要处理大量数据的场景，提高生产效率。在船舶设计方面，魏方以^[7]基于SQL数据库设计了一套主尺度设计系统，可以估算设计船舶的技术和经济指标。利用SQL统一管理船舶数据，能显著提高船舶生产建造效率与安全性、高效管理船舶的各类数据^[8]。

在船舶数据库的基础上，快速准确地匹配与母型船最相近的信息成为迫切的需求。而船舶的型线匹配，不同于单纯的几何线段匹配方法，更多的着眼于船舶性能上和尺度上的匹配。如Dynamic Time Warping（DTW）算法等许多算法经常用于匹配各类几何型线，但适用于船舶型线几何特征的匹配方法仍然较少。当前的船舶初步设计中，型线匹配主要是从船舶的各类性能参数入手而非船体型线本身^[9]。无论是船型参数还是船舶性能，都由多个参数组成，因此需要高维数据的搜索匹配算法。KD-Tree 是空间二分树的一种特殊情况，该结构广泛应用于高维空间关键数据的检索^[10]。KD-Tree算法常与KNN（K-Nearest-Neighbor）搜索算法共同使用，用于复杂数据的搜索匹配。Aleo等^[11]利用KD-Tree在数百万个对象中能够对11维的参数进行有效搜索。Jiao等^[12]基于KD-Tree构建船舶轨迹点的数据集，提高了复杂船舶轨迹数据中辨识异常点的效率。

因此，本文基于SQL建立船舶数据库解决船舶数据种类繁多复杂的问题。同时，使用B样条对船体的特征线进行拟合，求取对应特征线的B样条控制点作为型线匹配依据。并首次提出将KD-Tree算法用于船体型线的匹配中，以提高在船舶数据库中的搜索匹配速度，在保证一定的相似度同时输出性能较优的船型。

1 船体型线数据库 1.1 MySQL数据库的建立

本文通过对阿芙拉油船的船体曲面进行基于径向基函数（Radial Based Function, RBF）插值的曲面变形^[13]，对船体型值点进行改变生成了120艘变型船体作为数据库的原始数据集。型线数据包含船舶的型值点的三维位置信息，同时为更精准地计算船体型线的性能，减少过渡区对性能计算的误差，将船体分为主体、船尾、尾轴、船首、球首5个部位，并将部位信息一并存储在型线数据中，如图1所示。

船体型线数据库由型值数据表和特征线数据表组成。导入新的船型数据时，对导入数据进行重复点、异常点去除操作。同时，对导入船型的特征进行提取、拟合和计算，将结果导入特征线数据表中，并自动编号排序。在用户输入待匹配的船型数据后，将计算特征线数据并与数据库中的特征线数据表进行快速搜索匹配，并输出对应的船型的型值和性能数据。数据库的结构以及数据流如图2所示。

为实现使用MySQL对任意型线进行高效的存储以及调用，并便于后续数据库功能的拓展，本文使用相同前缀的表保存各船的型值数据，如表1所示。

同时，针对船型曲面的特征，建立特征线数据表，结构如表2所示。

1.2 特征线的选取与求取B样条控制点

在数据库中储存的船体型线，均以三维型值点的形式保存。为了保留船体曲面细节，每一艘船保存的型值点都高达几十万个。因此，采用船舶的特征线对船体曲面的特征进行提取、概括以实现降维是必要的。根据船舶型线图中的3组线图以及各部位的曲面复杂情况，本文在纵剖面处等距选取了5条特征线；在水线面等距选取了5条特征线；在横剖面处，分别在船舶主体、船尾、尾轴分别选取了5条特征线，如图3所示。

利用B样条拟合的方法，对选取的特征线进行拟合。同时，基于B样条的形状由控制点确定且控制点的三维坐标表征了样条的形状和位置的特性。在本文中，以特征线上的型值点作为拟合点，B样条的基本形式为：

$ \begin{array}{c}P\left(t\right)=\displaystyle\sum _{i=0}^{n}{N}_{i,k}\left(t\right){P}_{i}。\end{array} $

(1)

式中：$ {P}_{i}(i=\mathrm{0,1},\cdot \cdot \cdot ,n) $为B样条的控制点；n为控制点的数量；$ {N}_{i,k}\left(t\right) $为k阶的基函数。B样条的基函数由Cox-de Boor递归公式^[14]计算得出：

$ \begin{array}{c}{N}_{i,1}\left(t\right)=\left\{\begin{aligned} &1 ,{t}_{i} < x < {t}_{i+1}，\\ &0 ,{\rm {otherwise}}。\end{aligned}\right. \end{array} $

(2)

$ \begin{array}{c}{N}_{i,k}\left(t\right) = \displaystyle\frac{t-{t}_{i}}{{t}_{i+k-1} - {t}_{i}}{N}_{i,k-1}\left(t\right) + \displaystyle\frac{{t}_{i+k}-t}{{t}_{i+k} - {t}_{i+1}}{N}_{i+1,k-1}\left(t\right)。\end{array} $

(3)

其中：$ {t}_{0} \leqslant {t}_{1} \leqslant {t}_{2} \leqslant \cdots \leqslant {t}_{n+k} $为节点矢量的非递减序列。在B样条的拟合过程中，实验发现：12个控制点足以拟合数据并且不会产生过拟合。同时，将拟合阶数设置为常用的3阶B样条保证足够的平滑度和灵活性。在拟合的过程中，用型值点间的距离近似代替弧长以确定每个型值点对应的参数$ t $，其中第一个型值点参数为0，第$ s(s > 1) $个型值点参数为：

$ \begin{array}{c}{t}_{s}=\frac{\displaystyle\sum _{i=2}^{s}\left[{\displaystyle\left({x}_{i}-{x}_{i-1}\right)}^{2}+{\displaystyle\left({y}_{i}-{y}_{i-1}\right)}^{2}\right]} {\displaystyle\sum _{i=2}^{m}\left[{\left({x}_{i}-{x}_{i-1}\right)}^{2}+{\left({y}_{i}-{y}_{i-1}\right)}^{2}\right]}。\end{array} $

(4)

为了保证拟合后对应的主尺度不发生变化，在型线的首端和末端设置节点，随后通过节点矢量由Cox-de Boor递归公式计算基函数。B样条的拟合步骤完成后，将控制点坐标保存至特征线数据表中。B样条的拟合结果如图4所示。

可知，点划线表示的B样条的拟合曲线能与实线表示的船体原始型线紧密贴合，圆圈表示的B样条控制点分布于型线的两端，能够很好地控制船舶的主尺度不发生变化。随后，将控制点坐标归一化后存入数据库中。

2 基于KD-Tree的船体型线匹配方法

在特征线数据表中，每艘船有300个三维特征线控制点。通过构造函数将数据整理成以KD-Tree的形式保存。在构造函数中，设特征线控制点数据集在线性空间$ {\mathit{R}}^{\mathit{n}} $表达为$ ({p}_{1},{p}_{2},\cdot \cdot \cdot ,{p}_{k}) $，其中k为控制点数据的维度。在数据集最大方差的维度 max ($ {d}_{i}\left)\right(1 \leqslant i \leqslant k) $划分左右子树：

$ \begin{array}{c}{d}_{i}=\displaystyle\frac{1}{N-1}\sum _{j=1}^{N}{\left({p}_{i,j}-\overline{{p}_{i}}\right)}^{2}\end{array}。$

(5)

式中，$ N\mathrm{为}{p}_{i}\mathrm{的}\mathrm{数}\mathrm{据}\mathrm{量} $。同时，二叉树的每一个节点$ n $记载了特征线控制点的坐标集合$ P $、切分轴$ r $、指向右子树指针$ pt{r}_{r} $和指向左子树指针$ pt{r}_{l} $：

$ \begin{array}{c}n=\left(P,r,pt{r}_{r},pt{r}_{l}\right)\end{array} 。$

(6)

树的构建过程如下：1）在子树的分配过程中，假设当前节点切分轴为$ r(1 \leqslant r \leqslant k) $，若待分配数据中的$ {p}_{r}{{'}} < {p}_{r} $则该数据被分配至左子树，反之则分配至右子树。2）对整个数据集S进行遍历操作，每一次循环中确定一个方差最大处的切分轴r。对数据集S中第r个坐标按照大小进行排序，将S中小于中位数的部分设为$ {S}_{L} $，将S中大于中位数的部分设为$ {S}_{R} $。3）在下一次遍历中，将$ {S}_{L} $作为左子树的数据集，将$ {S}_{R} $作为右子树的数据集，分别进行KD-Tree操作。直至不可分割，遍历过程中形成的节点为中间节点，结束后不可分割的节点为叶子节点。构建函数流程如图5所示。

搜索函数的实现过程如下：1）建立有k维的空数组L，用以暂存输出节点；2）根据输入点$ {p}' $，从根节点向下搜索，按照节点中保存的切分轴，若$ {p}_{r}' < {p}_{r} $则进入左子树搜索，反之则进入右子树搜索，直至到达一个叶子节点，并将该节点标记为访问过。若L中为空，则将该叶子节点放入L中，若L不为空且该节点在r维度上与目标的距离小于L中离目标最远的节点，则替换离目标最远的节点；3）若当前节点不为根节点，则进行“回溯”搜索，访问上一个节点，若上一个节点已被访问，则继续“回溯”；4）计算当前节点与切分轴的距离$ l $，若$ l $大于L中距离目标值最远的节点且L中已满，则在切分轴另一侧的超平面不会有更近的点；5）若$ l $小于L中最远节点或L不满，则在切分轴另一侧可能存在更近的点，则从当前节点进行操作；6）若遍历后，当前节点为根节点，输出结果数组L。搜索函数的流程如图6所示。

在搜索过程中，为了平衡型线三个维度上的数量级影响，搜索函数对控制点数据进行了归一化处理，并采用等权重对数据进行映射处理。在搜索过程中，采用高维空间的欧式距离$ d $作为输入数据与样本的误差：

$ \begin{array}{c}d=\sqrt{\displaystyle\frac{1}{n}\sum _{i=1}^{n}{\left({p}_{i}'-{p}_{i}\right)}^{2}}\end{array} 。$

(7)

通过构建函数将数据库中船型的特征线数据集以树结构保存，后续使用搜索函数提升船体型线的匹配效率。同时，为定量分析2组型线数据的匹配程度，定义匹配度如下：

$ {\rho = {e^{ - A \cdot d}} \times 100{\text{%}} }。$

(8)

式中：$ \rho $为相似度指标；d为2组型线间的差值，A为缩放系数。缩放系数A由数据量级决定，使得相似度指标$ \rho $映射在0～1，便于后续结果的验证与分析。

3 模拟实验与分析

本文实验数据通过计算机仿真得到，通过RBF曲面变形得到船体型值点数据，每艘船约有十万个三维型值点。通过商业软件Shipflow中的叠模绕流法和薄湍流边界层法得到各船对应的总阻力参数。模拟试验测试了基于SQL数据库的读取速度和基于文本文件的读取速度。在对船型的型线分析过程中，取型线的最值和取特征线是频繁操作，2种方法读取的速度如表3所示。

其中，数据库中的船体的型值点可以通过SQL语句直接选择指定方向和位置的型值点最值。而基于文本数据的数据调用需要对所读取的数据进行识别和清洗操作。因此，在取型线最值操作中，基于SQL读取数据的平均耗时约为0.22290 s，相比基于文本读取方式读取速度提升约73.38%。2种方法的耗时组成如图7所示。

在提取船体特征线过程中，基于SQL的数据提取方法中，通过筛选语句即可定向提取位于纵剖线、水线面和横剖线3个方向的特征线的型值点。基于文本的特征线提取方法中，需要对通过循环迭代搜索的方式提取位于特征线的型值点。2种方法的耗时对比如表4所示。

可知，基于SQL的特征线提取方法比基于文本的方法平均耗时节约16.91%且主要耗时步骤不同。在基于SQL的方法中，需要多次连接数据库，从数据库中分批次调用需要的型值数据进行特征线提取操作。在基于文本文件的方法中，先从文件中所有的数据调用并保存在内存中，再进行数据处理操作，耗时步骤主要为数据的识别、筛选和排序。因此当单个船体型线数据量更大的，2种方法的耗时差距将扩大。2种方法各步骤的耗时对比如图8所示。

在型线匹配阶段，模拟实验对比了基于KD-Tree算法的匹配耗时和基于搜索排序算法匹配的耗时。为了对比2种方法随数据量增加时的增长趋势，模拟实验分别建立了含有100、200、300、400、500艘船舶数据的测试数据库。在测试样船相同，待匹配样本相同的情况下，2种匹配方法的平均耗时如图9所示。

可知，在5个数据量大小不同的测试数据库中，基于KD-Tree算法的搜索匹配平均耗时分别比直接搜索排序算法的平均耗时减少了34.31%、64.01%、79.16%、84.16%、86.01%。同时，随着数据量的增加，直接搜索排序算法的搜索匹配平均耗时大致上呈线性增加，而基于KD-Tree算法的搜索匹配平均耗时增加速度明显更缓慢。以数据量作为自变量，分别以2种方法的匹配平均耗时为因变量进行线性拟合。由拟合结果可知，基于线性拟合方程，直接搜索排序算法的平均耗时增加速度约为基于KD-Tree算法的16倍。基于KD-Tree算法的搜索匹配算法只需沿树结构进行搜索，省去了计算待匹配船型与无序样本的相似度再排序输出相似船型的步骤。可以推测，在数据库更大时，基于KD-Tree算法的搜索匹配将更有效率。

最后，针对基于特征线和KD-Tree算法的匹配精度问题，进行了模拟试验如下：选取数据集外的5艘测试船，分别基于船型特征线和主尺度数据（船长L、船宽B、型深D、设计吃水T、方形系数$ {C}_{B} $、菱形系数$ {C}_{p} $、水线面系数$ {C}_{wpa} $）在数据库中匹配船型。同时，按式(8)计算所匹配船型的匹配度$ \rho $，结果如图10所示。

可知，基于特征线的匹配方法在测试集中能实现90%以上的匹配度，而基于主尺度数据匹配方法的匹配度均低于基于特征线的匹配方法且方差较大。同时，基于特征线匹配的方法能在满足足够相似度的前提下，根据数据库中已有的性能数据输出其中性能最优的船型。另选一艘测试船，基于主尺度匹配方法和基于特征线匹配所得到的船型相关性能参数如表5所示。

可知，在保证船型相似度的情况下，基于特征线的匹配方法能够基于设计航速的总阻力系数筛选出其中性能最优的船型，在母型船的选型阶段选出与需求相近且性能指标最优的船型。

4 结　语

本文提出的基于SQL数据库和KD-Tree算法的船体型线快速搜索匹配方法，能有效储存调用船舶初步设计过程中繁多复杂的数据。该方法在提取船舶型线数据和求取型线极值的过程中，能够将数据提取速度提高约73.88%。该方法在提取船舶特征线的过程中，能够将速度提取约16.91%。该方法在船型搜索匹配的过程中，在数据库大小不同的情况下，能够将速度提高34.31%～84.16%。并在数据库更大时，该方法的效率优势将更加显著，初步验证了该方法的有效性。同时，基于特征线的匹配方法能够考虑船体本身的三维形状，相比于现有的基于主尺度的匹配方法，在测试数据库中能够将匹配度提高至90%以上。该方法能够在考虑型线匹配度的同时基于数据库中已有的数据，在满足相似度要求的情况下输出性能最优的型线。后续，将考虑利用神经网络模型对数据库中的型线进行特征提取，实现型线总阻力的快速预报，为提高船型优化效率奠定基础。