提取主方向洋流过程算法描述

1 问题简述

我们需要从200条洋流中选取四条最有“特征”（相互间差距最大）的洋流进行分镜头追踪。以下主要针对选取四条洋流的过程进行详细叙述。

2 解决思路

洋流是一条三维空间内的曲线，更准确地说，对于一条在延伸中的洋流，它拥有四个维度。即坐标和当前时间。

也就意味着，我们在选择四条“特征”最明显的洋流时，要考虑这四条洋流的四个维度的“特征”是与其他洋流差距最大的。

为了准确的衡量这个“特征”，我们先选取一条基准洋流，然后将每条洋流的“特征”用两个变量和表示。其中表示当前洋流和基准洋流的主方向对应的极角差，表示当前洋流和基准洋流在整个过程中的离散Fréchet（弗雷歇）距离。然后我们用一个线性组合来将的二元组合成为一个数字。对所有这样的数字进行排序后，在序列中选取等距离的四个点即是我们需要的四条洋流。（这四条洋流满足他们之间的主方向和距离差距最大）

注1：离散Fréchet（弗雷歇）距离常用于评价空间里两条曲线相似度。它的推导过程如下：
假设一条洋流的轨迹为且长度为，另一条洋流的轨迹为且长度为。而两者运动位置的描述可以用一个变量的连续递增函数来刻画。用来表示一条曲线运动位置描述函数，用表示另一条曲线运动位置描述函数。同时为了方便讨论，我们将变量约束到区间内，那么有。我们用和分别表示时刻两条曲线在各自轨迹上的空间位置，那么两条曲线之间的距离会随着和函数本身的不同和变量的变化而不同，更为严格的Fréchet距离数学表达式如下：

注意到洋流由离散的点构成，因此考虑将上述公式拓展到离散Fréchet距离。
首先我们将上述两轨迹进行离散化，设曲线是由个轨迹点所组成，曲线是由个轨迹点所组成。使用和分别表示两轨迹点的顺序集合，则有和。同时，我们可以得到如下序列点对

其中，。
轨迹点之间的序列对之间长度定义为各序列对中欧式距离最大的值，表达式如下

那么其离散Fréchet距离定义如下

注2：之所以选择和来做为洋流之间比较的依据，原因在于，主方向提取算法（PCA）能够处理一条曲线的方向，但在降维的过程中损失了“距离”这一要素。而（离散Fréchet距离）的设置，弥补了这一不足。

一个简单的示意图

3 具体算法过程

3.1 第一步

使用PCA算法，对所有洋流提取主方向。（时间复杂度）

3.2 第二步

使用dbscan聚类算法，对PCA处理后得到的三维点云做聚类。最终将聚类后得到的点作为可能最终被选取洋流，不被聚类的点（边缘点）将被舍弃。（时间复杂度）

3.3 第三步

3.3.1 具体步骤一

在剩余的所有点代表的洋流中选取一条作为基准洋流（由于是差距比较，这里的选取可以任意而不影响结果）。（时间复杂度）

3.3.2 具体步骤二

用基准洋流和剩下的所有可行洋流计算主方向的极角差，和离散Fréchet距离。（时间复杂度）

3.3.3 具体步骤三

用一线性组合将和合成为一个数字，其中为指定常数。的选择决定了对和考虑的比重。（时间复杂度）

3.3.4 具体步骤四

对步骤三得到的所有进行排序，选取其中等距离的四个数字代表的洋流作为所要研究的洋流。（时间复杂度）

4 总结

4.1 时空复杂度分析

所有涉及操作的空间复杂度均低于OceanView中其他过程的空间复杂度，因此这里并不会产生空间使用超限的问题。

所有涉及操作的时间复杂度的瓶颈在于第一步中的全过程PCA算法和3.3.2中的计算离散Fréchet距离。但这里的所有时间复杂度均为预处理过程中的开销，并不会影响渲染过程。

4.2 算法优势

通过考虑不同维度，较为完整的囊括了洋流的绝大部分信息，使得算法过程中的洋流选择更易使人理解。

4.3 算法劣势

算法中存在一个超参，即结合和的常数。常数的选择将最终影响四条洋流的选择。