[發明專利]基于劣弧演化的點到隱式曲線距離計算方法

有效

• 申請號: 201310542392.X
• 申請日: 2013-10-30
• 公開（公告）號: CN103559400B
• 公開（公告）日: 2017-06-16
• 發明（設計）人: 胡明曉;吳文國;謝祖明;張新瑤
• 申請（專利權）人: 溫州大學
• 主分類號: G06F19/00
• 分類號: G06F19/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及數值計算領域，具體地說是一種為電子計算機提供點到隱式曲線距離的數值計算方法。

背景技術

點到隱式曲線的距離計算方法在模式識別、幾何建模、計算機視覺、醫學影像處理等領域具有重要應用價值，也是數值分析、計算機科學、逆向工程等學科的重要研究基礎。由于點到隱式曲線的距離的解析式一般很難得到甚至不可能得到，所以距離的計算通常是數值計算。

設所求距離是點p₀到隱式曲線f(x，y)＝0的距離，點到隱式曲線距離的數值計算通常有局部法和全局法之分。局部法含有一個迭代過程，如牛頓迭代法，它先以迭代方式求出隱式曲線上與p₀達到最小距離的點(稱為足點)，也就是先求解下列關于p的方程的根p^*：

其中，表示梯度算子，×為矢量叉乘。于是所求距離就是||p*-p₀||。迭代法收斂速度較快，但經常受奇點和初值選擇的影響，存在不收斂、陷入局部極值點等缺點，且對f(x，y)的光滑性要求較高。全局法則根據隱式函數j(x，y)的某種全局特性對足點進行二維搜索，如文獻“Geometric constraint solver using multivariate rational spline functions”(Elber，G.and Kim，M.-S.，In：Proceedings of the Sixth ACM Symposium on Solid Modeling and Applications，ACM，2001：pp.1-10)和文獻“Computation of the solutions of nonlinear polynomial systems”(Sherbrooke，E.C.and Patrikalakis，N.M.，Computer Aided Geometric Design，v10，1993：pp.379-405)所述方法，根據基函數的凸包性質，采用Bézier裁剪方法不斷排除非足點區域，得到候選足點，最后在這些候選足點中選取與p₀距離最小的點。全局法能保證魯棒計算，但計算量較大，對隱式函數有特殊要求(如凸性)。

此外，還有作為全局方法和局部方法之折中的方法，基本框架仍為迭代法，但每步迭代根據徑向導數搜索下一個足點的估計位置，參見文獻“Robust Computation of Foot Points on Implicitly Defined Curves”(Aigner，M.and Jittler，B.，In：Mathematical Methods for Curves and Surfaces：2004，Nashboro Press，2005：pp.1-10)。

當然，由于收斂速度和魯棒計算很難兩全，在許多需要計算點到隱式曲線距離的應用場合常常采用估算法，如基于曲率的二階估計、單純形估計。具體可參見文獻“Fitting B-spline curves to point clouds by curvature-based squared distance minimization”(Wang，Wenping；Pottmann，H.；et a1.，ACM Transactions on Graphics，25(2)，2006：214-238)和文獻“Implicit polynomial representation through a fast fitting error estimation”(Rouhani，M.；Sappa，A.D.，IEEE Transactions on Image Processing，21(4)，2012：2089-2098)。距離的估計不是本發明的設計目標，本發明的目標是精確計算與魯棒性。

發明內容

為了精確計算平面內的點到隱式曲線的距離，達到事先給定的任意小的容許誤差，并且不受曲線幾何形狀的影響，避免落入局部極值、依賴初值選擇等問題，本發明采用如下技術方案。

給定二維平面內的一個點p₀及一條隱式曲線，其中隱式曲線為某有界區域Ω上有定義且方向導數有界的二元函數f(x，y)依其零值集確定的單分支平面曲線，本發明的點p₀到所述隱式曲線距離的數值計算方法，包含如下步驟：