طريقة التقريب التدريجي التكراري

في خوارزميات الاستيفاء الخاصة بـ PIA، ^{[ 1 ] [ 3 ] [ 9 ] [ 16 ]} تُستخدم كل نقطة بيانات كنقطة تحكم. ولتسهيل وصف صيغة تكرار PIA لأشكال المنحنيات والأسطح المختلفة، تُستخدم الصيغة التالية بشكل موحد: $${\displaystyle \mathbf {P} (\mathbf {t} )=\sum _{i=1}^{n}\mathbf {P} _{i}B_{i}(\mathbf {t} ).}$$ على سبيل المثال:

• لو${\displaystyle \mathbf {P} (\mathbf {t} )}$إذا كان منحنى B-spline،${\displaystyle \mathbf {t} }$هو كمية قياسية،${\displaystyle B_{i}(t)}$هي دالة أساسية من نوع B-spline، و${\displaystyle \mathbf {P} _{i}}$يشير إلى نقطة التحكم؛ ^{[ 8 ]}
• لو${\displaystyle \mathbf {P} (\mathbf {t} )}$هي رقعة B-spline مع${\displaystyle n_{u}\times n_{v}}$نقاط التحكم، ثم${\displaystyle \mathbf {t} =(u,v)}$و${\displaystyle B_{i}(\mathbf {t} )=N_{i}(u)N_{i}(v)}$، أين${\displaystyle N_{i}(u)}$و${\displaystyle N_{i}(v)}$هي دوال أساسية من نوع B-spline؛ ^{[ 8 ]}
• لو${\displaystyle \mathbf {P} (\mathbf {t} )}$هو مجسم ثلاثي المتغيرات من نوع B-spline مع${\displaystyle n_{u}\times n_{v}\times n_{w}}$نقاط التحكم، ثم${\displaystyle \mathbf {t} =(u,v,w)}$و${\displaystyle B_{i}(\mathbf {t} )=N_{i}(u)N_{i}(v)N_{i}(w)}$، أين${\displaystyle N_{i}(u)}$،${\displaystyle N_{i}(v)}$، و${\displaystyle N_{i}(w)}$هي دوال أساسية من نوع B-spline. ^{[ 17 ]}

بالإضافة إلى ذلك، يمكن تطبيق ذلك على منحنيات وأسطح NURBS، وأسطح T-spline، وأسطح Bernstein–Bézier المثلثية. ^{[ 18 ]}

بالنظر إلى مجموعة بيانات مرتبة${\displaystyle \mathbf {Q} _{i}}$مع المعلمات${\displaystyle t_{i}}$مُرضٍ${\displaystyle t_{1}<t_{2}<\cdots }$ل${\displaystyle i=1,2,\cdots ,n}$، منحنى المطابقة الأولي هو: ^{[ 1 ]}$${\displaystyle \mathbf {P} ^{(0)}(t)=\sum _{i=1}^{n}\mathbf {P} _{i}^{(0)}B_{i}(t)}$$ حيث نقاط التحكم الأولية لمنحنى المطابقة الأولي${\displaystyle \mathbf {P} _{i}^{(0)}}$يمكن اختيارها عشوائياً. لنفترض أنه بعد${\displaystyle k}$التكرار رقم 1،${\displaystyle k}$منحنى المطابقة${\displaystyle \mathbf {P} ^{(k)}(t)}$يتم إنشاؤه بواسطة

${\displaystyle \mathbf {P} ^{(k)}(t)=\sum _{i=1}^{n}\mathbf {P} _{i}^{(k)}B_{i}(t).}$

1

لبناء${\displaystyle (k+1)}$في المنحنى الأول، نحسب أولاً متجهات الفرق . $${\displaystyle \mathbf {\Delta } _{i}^{(k)}=\mathbf {Q} _{i}-\mathbf {P} ^{(k)}(t_{i}),\quad i=1,2,\cdots ,n}$$ واستخدمها لتحديث نقاط التحكم بواسطة $${\displaystyle \mathbf {P} _{i}^{(k+1)}=\mathbf {P} _{i}^{(k)}+\mathbf {\Delta } _{i}^{(k)}}$$ مما يؤدي إلى${\displaystyle (k+1)}$منحنى المطابقة الأول: $${\displaystyle \mathbf {P} ^{(k+1)}(t)=\sum _{i=1}^{n}\mathbf {P} _{i}^{(k+1)}B_{i}(t).}$$ وبهذه الطريقة، نحصل على سلسلة من المنحنيات${\textstyle \mathbf {P} ^{(\alpha )}(t),\alpha =0,1,2,\cdots }$، والتي تتقارب إلى منحنى حدي يقوم باستيفاء نقاط البيانات المعطاة، ^{[ 1 ] [ 9 ]} أي، $${\displaystyle \lim \limits _{\alpha \rightarrow \infty }\mathbf {P} ^{(\alpha )}(t_{i})=\mathbf {Q} _{i},\quad i=1,2,\cdots ,n.}$$

فيما يخص مسألة تركيب المنحنيات والأسطح باستخدام دوال B-spline، اقترح دينغ ولين تقريبًا تدريجيًا تكراريًا باستخدام طريقة المربعات الصغرى (LSPIA)، ^{[ 10 ] [ 19 ]،} والذي يسمح بأن يكون عدد نقاط التحكم أقل من عدد نقاط البيانات، وهو أكثر ملاءمة لمسائل تركيب البيانات واسعة النطاق. ^{[ 10 ]}

افترض وجود${\displaystyle m}$نقاط البيانات و${\displaystyle n}$نقاط التفتيش، حيث${\displaystyle n\leq m}$ابدأ بالمعادلة ( 1 )، والتي تعطي${\displaystyle k}$منحنى المطابقة كـ $${\displaystyle \mathbf {P} ^{(k)}(t)=\sum _{j=1}^{n}\mathbf {P} _{j}^{(k)}B_{j}(t).}$$ لإنشاء${\displaystyle (k+1)}$أولاً، قم بحساب متجهات الفرق لنقاط البيانات ^{[ 10 ] [ 19 ]}$${\displaystyle {\boldsymbol {\delta }}_{i}^{(k)}=\mathbf {Q} _{i}-\mathbf {P} ^{(k)}(t_{i}),\quad i=1,2,\cdots ,m}$$ ثم متجهات الفرق لنقاط التحكم $${\displaystyle \mathbf {\Delta } _{j}^{(k)}={\frac {\sum _{i\in I_{j}}{c_{i}B_{j}(t_{i}){\boldsymbol {\delta }}_{i}^{(k)}}}{\sum _{i\in I_{j}}c_{i}B_{j}(t_{i})}},\quad j=1,2,\cdots ,n}$$ أين${\displaystyle I_{j}}$هي مجموعة فهارس نقاط البيانات في${\displaystyle j}$المجموعة رقم th، التي تقع معاييرها ضمن نطاق الدعم المحلي لـ${\displaystyle j}$دالة الأساس رقم 1، أي${\displaystyle B_{j}(t_{i})\neq 0}$. ال${\displaystyle c_{i}}$هي أوزان تضمن تقارب الخوارزمية، وعادة ما تُؤخذ على النحو التالي:${\displaystyle c_{i}=1,i\in I_{j}}$.

وأخيرًا، نقاط التحكم الخاصة بـ${\displaystyle (k+1)}$يتم تحديث المنحنى بواسطة${\displaystyle \mathbf {P} _{j}^{(k+1)}=\mathbf {P} _{j}^{(k)}+\mathbf {\Delta } _{j}^{(k)},}$مما يؤدي إلى${\displaystyle (k+1)}$منحنى المطابقة${\displaystyle \mathbf {P} ^{(k+1)}(t)}$وبهذه الطريقة، نحصل على سلسلة من المنحنيات، ويتقارب المنحنى النهائي مع نتيجة مطابقة المربعات الصغرى لنقاط البيانات المعطاة. ^{[ 10 ] [ 19 ]}

في طريقة PIA المحلية، ^{[ 12 ]} تُقسّم نقاط التحكم إلى نقاط تحكم نشطة وثابتة، ويُشار إلى رموزها الفرعية بـ${\textstyle I=\left\{i_{1},i_{2},\cdots ,i_{I}\right\}}$و${\textstyle J=\left\{j_{1},j_{2},\cdots ,j_{J}\right\}}$على التوالي. افترض أن${\textstyle k}$منحنى المطابقة هو${\textstyle \mathbf {P} ^{(k)}(t)=\sum _{j=1}^{n}\mathbf {P} _{j}^{(k)}B_{j}(t)}$حيث تحقق نقاط التحكم الثابتة $${\displaystyle \mathbf {P} _{j}^{(k)}=\mathbf {P} _{j}^{(0)},\quad j\in J,\quad k=0,1,2,\cdots .}$$ ثم، من جهة أخرى، الصيغة التكرارية لمتجه الفرق${\textstyle \mathbf {\Delta } _{h}^{(k+1)}}$يتوافق مع نقاط التحكم الثابتة $${\displaystyle {\begin{aligned}\mathbf {\Delta } _{h}^{(k+1)}&=\mathbf {Q} _{h}-\sum _{j=1}^{n}\mathbf {P} _{j}^{(k+1)}B_{j}(t_{h})\\&=\mathbf {Q} _{h}-\sum _{j\in J}\mathbf {P} _{j}^{(k+1)}B_{j}(t_{h})-\sum _{i\in I}\left(\mathbf {P} _{i}^{(k)}+\mathbf {\Delta } _{i}^{(k)}\right)B_{i}(t_{h})\\&=\mathbf {Q} _{h}-\sum _{j=1}^{n}\mathbf {P} _{j}^{(k)}B_{j}(t_{h})-\sum _{i\in I}\mathbf {\Delta } _{i}^{(k)}B_{i}(t_{h})\\&=\mathbf {\Delta } _{h}^{(k)}-\sum _{i\in I}\mathbf {\Delta } _{i}^{(k)}B_{i}(t_{h}),\quad h\in J.\end{aligned}}}$$ On the other hand, the iterative formula of the difference vector ${\textstyle \mathbf {D} _{l}^{(k+1)}}$ corresponding to the active control points is $${\displaystyle {\begin{aligned}\mathbf {\Delta } _{l}^{(k+1)}&=\mathbf {Q} _{l}-\sum _{j=1}^{n}\mathbf {P} _{j}^{(k+1)}B_{j}(t_{l})\\&=\mathbf {Q} _{l}-\sum _{j=1}^{n}\mathbf {P} _{j}^{(k)}B_{j}(t_{l})-\sum _{i\in I}\mathbf {\Delta } _{i}^{(k)}B_{i}(t_{l})\\&=\mathbf {\Delta } _{l}^{(k)}-\sum _{i\in I}\mathbf {\Delta } _{i}^{(k)}B_{i}(t_{l})\\&=-\mathbf {\Delta } _{i_{1}}^{(k)}B_{i_{1}}(t_{l})-\mathbf {\Delta } _{i_{2}}^{(k)}B_{i_{2}}(t_{l})-\cdots +\left(1-B_{l}(t_{l})\right)\mathbf {\Delta } _{l}^{(k)}-\cdots -\mathbf {\Delta } _{i_{I}}^{(k)}B_{i_{I}}(t_{l}),\quad l\in I.\end{aligned}}}$$ Arranging the above difference vectors into a one-dimensional sequence, $${\displaystyle \mathbf {D} ^{(k+1)}=\left[\mathbf {\Delta } _{j_{1}}^{(k+1)},\mathbf {\Delta } _{j_{2}}^{(k+1)},\cdots ,\mathbf {\Delta } _{j_{J}}^{(k+1)},\mathbf {\Delta } _{i_{1}}^{(k+1)},\mathbf {\Delta } _{i_{2}}^{(k+1)},\cdots ,\mathbf {\Delta } _{i_{I}}^{(k+1)}\right]^{T},\quad k=0,1,2,\cdots ,}$$ the local iteration format in matrix form is, $${\displaystyle \mathbf {D} ^{(k+1)}=\mathbf {T} \mathbf {D} ^{(k)},\quad k=0,1,2,\cdots ,}$$ where ${\textstyle \mathbf {T} }$ is the iteration matrix: $${\displaystyle \mathbf {T} ={\begin{bmatrix}\mathbf {E} _{J}&-\mathbf {B} _{1}\\0&\mathbf {E} _{I}-\mathbf {B} _{2}\end{bmatrix}},}$$ where ${\textstyle \mathbf {E} _{J}}$ and ${\textstyle \mathbf {E} _{I}}$ are the identity matrices and $${\displaystyle \mathbf {B} _{1}={\begin{bmatrix}B_{i_{1}}\left(t_{j_{1}}\right)&B_{i_{2}}\left(t_{j_{1}}\right)&\cdots &B_{i_{I}}\left(t_{j_{1}}\right)\\B_{i_{1}}\left(t_{j_{2}}\right)&B_{i_{2}}\left(t_{j_{2}}\right)&\cdots &B_{i_{I}}\left(t_{j_{2}}\right)\\\vdots &\vdots &\vdots &\vdots \\B_{i_{1}}\left(t_{j_{J}}\right)&B_{i_{2}}\left(t_{j_{J}}\right)&\cdots &B_{i_{I}}\left(t_{j_{J}}\right)\\\end{bmatrix}},\mathbf {B} _{2}={\begin{bmatrix}B_{i_{1}}\left(t_{i_{1}}\right)&B_{i_{2}}\left(t_{i_{1}}\right)&\cdots &B_{i_{I}}\left(t_{i_{1}}\right)\\B_{i_{1}}\left(t_{i_{2}}\right)&B_{i_{2}}\left(t_{i_{2}}\right)&\cdots &B_{i_{I}}\left(t_{i_{2}}\right)\\\vdots &\vdots &\vdots &\vdots \\B_{i_{1}}\left(t_{i_{I}}\right)&B_{i_{2}}\left(t_{i_{I}}\right)&\cdots &B_{i_{I}}\left(t_{i_{I}}\right)\\\end{bmatrix}}.}$$ The above local iteration format converges and can be extended to blending surfaces^[12] and subdivision surfaces.^[20]

The PIA format for implicit curve and surface reconstruction is presented in the following.^[11] Given an ordered point cloud ${\textstyle \left\{\mathbf {Q} _{i}\right\}_{i=1}^{n}}$ and a unit normal vector ${\textstyle \left\{\mathbf {n} _{i}\right\}_{i=1}^{n}}$ on the data points, we want to reconstruct an implicit curve from the given point cloud. To avoid a trivial solution, some offset points ${\textstyle \left\{\mathbf {Q} _{l}\right\}_{l=n+1}^{2n}}$ are added to the point cloud.^[11] They are offset by a distance ${\textstyle \sigma }$ along the unit normal vector of each point $${\displaystyle \mathbf {Q} _{l}=\mathbf {Q} _{i}+\sigma \mathbf {n} _{i},\quad l=n+i,\quad i=1,2,\cdots ,n.}$$ Assume that ${\textstyle \epsilon }$ is the value of the implicit function at the offset point $${\displaystyle f\left(\mathbf {Q} _{l}\right)=\epsilon ,\quad l=n+1,n+2,\cdots ,2n.}$$ Let the implicit curve after the ${\textstyle \alpha }$th iteration be $${\displaystyle f^{(\alpha )}(x,y)=\sum _{i=1}^{N_{u}}\sum _{j=1}^{N_{v}}C_{ij}^{(\alpha )}B_{i}(x)B_{j}(y),}$$ where ${\textstyle C_{ij}^{(\alpha )}}$ is the control point.

Define the difference vector of data points as^[11]$${\displaystyle {\begin{aligned}{\boldsymbol {\delta }}_{k}^{(\alpha )}&=0-f^{(\alpha )}(x_{k},y_{k}),\quad k=1,2,\cdots ,n,\\{\boldsymbol {\delta }}_{l}^{(\alpha )}&=\epsilon -f^{(\alpha )}(x_{l},y_{l}),\quad l=n+1,n+2,\cdots ,2n.\end{aligned}}}$$ Next, calculate the difference vector of control coefficients $${\displaystyle {\boldsymbol {\Delta }}_{ij}^{(\alpha )}=\mu \sum _{k=1}^{2n}B_{i}(x_{k})B_{j}(y_{k}){\boldsymbol {\delta }}_{k}^{(\alpha )},\quad i=1,2,\cdots ,N_{u},\quad j=1,2,\cdots ,N_{v},}$$ where ${\textstyle \mu }$ is the convergence coefficient. As a result, the new control coefficients are $${\displaystyle C_{ij}^{(\alpha +1)}=C_{ij}^{(\alpha )}+{\boldsymbol {\Delta }}_{ij}^{(\alpha )},}$$ leading to the new algebraic B-spline curve $${\displaystyle f^{(\alpha +1)}(x,y)=\sum _{i=1}^{N_{u}}\sum _{j=1}^{N_{v}}C_{ij}^{(\alpha +1)}B_{i}(x)B_{j}(y).}$$ The above procedure is carried out iteratively to generate a sequence of algebraic B-spline functions ${\textstyle \left\{f^{(\alpha )}(x,y),\quad \alpha =0,1,2,\cdots \right\}}$. The sequence converges to a minimization problem with constraints when the initial control coefficients ${\textstyle C_{ij}^{(0)}=0}$.^[11]

Assume that the implicit surface generated after the ${\textstyle \alpha }$th iteration is $${\displaystyle f^{(\alpha )}(x,y,z)=\sum _{i=1}^{N_{u}}\sum _{j=1}^{N_{v}}\sum _{k=1}^{N_{w}}C_{ijk}^{(\alpha )}B_{i}(x)B_{j}(y)B_{k}(z),}$$ the iteration format is similar to that of the curve case.^[11][21]

To develop fairing-PIA, we first define the functionals as follows:^[13]$${\displaystyle {\mathcal {F}}_{r,j}(f)=\int _{t_{1}}^{t_{m}}B_{r,j}(t)fdt,\quad j=1,2,\cdots ,n,\quad r=1,2,3,}$$ where ${\textstyle B_{r,j}(t)}$ represents the ${\textstyle r}$th derivative of the basis function ${\textstyle B_{j}(t)}$,^[8] (e.g. B-spline basis function).

Let the curve after the ${\textstyle k}$th iteration be $${\displaystyle \mathbf {P} ^{[k]}(t)=\sum _{j=1}^{n}B_{j}(t)\mathbf {P} _{j}^{[k]},\quad t\in [t_{1},t_{m}].}$$ To construct the new curve ${\textstyle \mathbf {P} ^{[k+1]}(t)}$, we first calculate the ${\textstyle (k+1)}$st difference vectors for data points,^[13]$${\displaystyle \mathbf {d} _{i}^{[k]}=\mathbf {Q} _{i}-\mathbf {P} ^{[k]}(t_{i}),\quad i=1,2,\cdots ,m.}$$ Then, the fitting difference vectors and the fairing vectors for control points are calculated by^[13]$${\displaystyle {\begin{aligned}{\boldsymbol {\delta }}_{j}^{[k]}&=\sum _{h\in I_{j}}B_{j}(t_{h})\mathbf {d} _{h}^{[k]},\quad j=1,2,\cdots ,n\\{\boldsymbol {\eta }}_{j}^{[k]}&=\sum _{l=1}^{n}{\mathcal {F}}_{r,l}\left(B_{r,j}(t)\right)\mathbf {P} _{l}^{[k]},\quad j=1,2,\cdots ,n\\\end{aligned}}}$$ Finally, the control points of the ${\displaystyle (k+1)}$st curve are produced by^[13]$${\displaystyle \mathbf {P} _{j}^{[k+1]}=\mathbf {P} _{j}^{[k]}+\mu _{j}\left[\left(1-\omega _{j}\right){\boldsymbol {\delta }}_{j}^{[k]}-\omega _{j}{\boldsymbol {\eta }}_{j}^{[k]}\right],\quad j=1,2,\cdots ,n,}$$ where ${\displaystyle \mu _{j}}$ is a normalization weight, and ${\displaystyle \omega _{j}}$ is a smoothing weight corresponding to the ${\displaystyle j}$نقطة التحكم رقم 1. يمكن استخدام أوزان التنعيم لضبط درجة النعومة بشكل فردي، مما يوفر مرونة كبيرة في تحقيق النعومة. ^{[ 13 ]} كلما زاد وزن التنعيم، زادت نعومة المنحنى الناتج. يتم الحصول على المنحنى الجديد كما يلي: $${\displaystyle \mathbf {P} ^{[k+1]}(t)=\sum _{j=1}^{n}B_{j}(t)\mathbf {P} _{j}^{[k+1]},\quad t\in [t_{1},t_{m}].}$$ وبهذه الطريقة، نحصل على سلسلة من المنحنيات${\textstyle \left\{\mathbf {P} ^{[k]}(t),\;k=1,2,3,\cdots \right\}}$تتقارب المتتالية إلى حل طريقة التنعيم التقليدية القائمة على تقليل الطاقة عندما تكون جميع أوزان التنعيم متساوية (${\textstyle \omega _{j}=\omega }$). ^{[ 13 ]} وبالمثل، يمكن توسيع نطاق تطبيق تحليل الأداء المتكامل (PIA) ليشمل حالة السطح.

التقريب التكراري التدريجي للمربعات الصغرى المتساوية هندسيًا (IG-LSPIA). ^{[ 14 ]} بالنظر إلى مسألة القيمة الحدية ^{[ 15 ]}$${\displaystyle \left\{{\begin{aligned}{\mathcal {L}}u=f,&\quad {\text{in}}\;\Omega ,\\{\mathcal {G}}u=g,&\quad {\text{on}}\;\partial \Omega ,\end{aligned}}\right.}$$ أين${\textstyle u:\Omega \to \mathbb {R} }$هو الحل المجهول،${\textstyle {\mathcal {L}}}$هو المؤثر التفاضلي ،${\textstyle {\mathcal {G}}}$هو عامل الحدود، و${\textstyle f}$و${\textstyle g}$هي دوال متصلة. في طريقة التحليل الهندسي المتساوي ، تُستخدم دوال أساس NURBS ^{[ 8 ] كدوال شكلية لإيجاد الحل العددي لمسألة القيمة الحدية هذه. [ 15 ]} وتُستخدم دوال الأساس نفسها لتمثيل الحل العددي.${\textstyle u_{h}}$والتخطيط الهندسي${\textstyle G}$: $${\displaystyle {\begin{aligned}u_{h}\left({\hat {\tau }}\right)&=\sum _{j=1}^{n}R_{j}({\hat {\tau }})u_{j},\\G({\hat {\tau }})&=\sum _{j=1}^{n}R_{j}({\hat {\tau }})P_{j},\end{aligned}}}$$ أين${\textstyle R_{j}({\hat {\tau }})}$تشير إلى دالة الأساس NURBS،${\textstyle u_{j}}$هو معامل التحكم. بعد استبدال نقاط التجميع ^{[ 22 ]}${\textstyle {\hat {\tau }}_{i},i=1,2,...,{m}}$بالتحويل إلى الشكل القوي للمعادلة التفاضلية الجزئية ، نحصل على مشكلة منفصلة ^{[ 22 ]}$${\displaystyle \left\{{\begin{aligned}{\mathcal {L}}u_{h}({\hat {\tau }}_{i})=f(G({\hat {\tau }}_{i})),&\quad i\in {\mathcal {I_{L}}},\\{\mathcal {G}}u_{h}({\hat {\tau }}_{j})=g(G({\hat {\tau }}_{j})),&\quad j\in {\mathcal {I_{G}}},\end{aligned}}\right.}$$ أين${\textstyle {\mathcal {I_{L}}}}$و${\textstyle {\mathcal {I_{G}}}}$تشير إلى الرموز السفلية لنقاط التجميع الداخلية والحدودية، على التوالي.

ترتيب معاملات التحكم${\textstyle u_{j}}$الحل العددي${\textstyle u_{h}({\hat {\tau }})}$إلى${\textstyle 1}$متجه عمودي ذو أبعاد${\textstyle \mathbf {U} =[u_{1},u_{2},...,u_{n}]^{T}}$يمكن إعادة صياغة المسألة المتقطعة في شكل مصفوفة كما يلي: $${\displaystyle \mathbf {AU} =\mathbf {b} }$$ أين${\textstyle \mathbf {A} }$هي مصفوفة التجميع و${\textstyle \mathbf {b} }$هو متجه الحمل.

افترض أن قيم الحمل المتقطعة هي نقاط بيانات${\textstyle \left\{b_{i}\right\}_{i=1}^{m}}$ليتم تركيبه. بالنظر إلى التخمين الأولي لمعاملات التحكم${\textstyle \left\{u_{j}^{(0)}\right\}_{j=1}^{n},n<m}$، نحصل على دالة مزج أولية ^{[ 14 ]}$${\displaystyle U^{(0)}({\hat {\tau }})=\sum _{j=1}^{n}A_{j}({\hat {\tau }})u_{j}^{(0)},\quad {\hat {\tau }}\in [{\hat {\tau }}_{1},{\hat {\tau }}_{m}],}$$ أين${\textstyle A_{j}({\hat {\tau }})}$،${\textstyle j=1,2,\cdots ,n}$يمثل هذا مزيجًا من مشتقات مختلفة الرتب لدوال أساس NURBS المحددة باستخدام المؤثرات.${\textstyle {\mathcal {L}}}$و${\textstyle {\mathcal {G}}}$$${\displaystyle A_{j}({\hat {\tau }})=\left\{{\begin{aligned}{\mathcal {L}}R_{j}({\hat {\tau }}),&\quad {\hat {\tau }}\ {\text{in}}\ \Omega _{p}^{in},\\{\mathcal {G}}R_{j}({\hat {\tau }}),&\quad {\hat {\tau }}\ {\text{in}}\ \Omega _{p}^{bd},\quad j=1,2,\cdots ,n,\end{aligned}}\right.}$$ أين${\textstyle \Omega _{p}^{in}}$و${\textstyle \Omega _{p}^{bd}}$يشير كل منهما إلى داخل وحدود نطاق المعلمة، على التوالي.${\textstyle A_{j}({\hat {\tau }})}$يتوافق مع${\textstyle j}$معامل التحكم رقم 1. افترض أن${\textstyle J_{in}}$و${\textstyle J_{bd}}$تمثل هذه المجموعات مؤشرات معاملات التحكم الداخلي والحدودي، على التوالي. وبدون فقدان للعمومية ، نفترض كذلك أن معاملات التحكم الحدودي قد تم الحصول عليها باستخدام فرض قوي أو ضعيف وأنها ثابتة، أي $${\displaystyle u_{j}^{(k)}=u_{j}^{*},\quad j\in J_{bd},\quad k=0,1,2,\cdots .}$$ ال${\textstyle k}$دالة المزج رقم 1، التي تم إنشاؤها بعد${\textstyle k}$يُفترض أن التكرار رقم 1 من IG-LSPIA، ^{[ 14 ]} يكون على النحو التالي: $${\displaystyle U^{(k)}({\hat {\tau }})=\sum _{j=1}^{n}A_{j}({\hat {\tau }})u_{j}^{(k)},\quad {\hat {\tau }}\in [{\hat {\tau }}_{1},{\hat {\tau }}_{m}].}$$ ثم، متجهات الفرق لنقاط التجميع (DCP) في${\textstyle (k+1)}$يتم الحصول على التكرارات باستخدام $${\displaystyle {\begin{aligned}{\boldsymbol {\delta }}_{i}^{(k)}&=b_{i}-\sum _{j=1}^{n}A_{j}({\hat {\tau }}_{i})u_{j}^{(k)}\\&=b_{i}-\sum _{j\in J_{bd}}A_{j}({\hat {\tau }}_{i})u_{j}^{(k)}-\sum _{j\in J_{in}}A_{j}({\hat {\tau }}_{i})u_{j}^{(k)},\quad i=1,2,...,m.\end{aligned}}}$$ علاوة على ذلك، قم بتجميع جميع قيم الأحمال التي تقع معاييرها ضمن النطاق المحلي لـ${\textstyle j}$دالة المشتقات، أي${\textstyle A_{j}({\hat {\tau }}_{i})\neq 0}$، إلى${\textstyle j}$المجموعة رقم 1 المقابلة لـ${\textstyle j}$معامل التحكم رقم 1، ويرمز إلى مجموعة مؤشرات معامل التحكم رقم 1.${\textstyle j}$مجموعة قيم الحمل كـ${\textstyle I_{j}}$وأخيرًا، يمكن إنشاء الفروقات لمعاملات التحكم (DCC) على النحو التالي: ^{[ 14 ]}$${\displaystyle d_{j}^{(k)}=\mu \sum _{h\in I_{j}}A_{j}({\hat {\tau }}_{h}){\boldsymbol {\delta }}_{h}^{(k)},\quad j=1,2,...,n,}$$ أين${\textstyle \mu }$هو وزن تطبيع لضمان تقارب الخوارزمية.

وبالتالي، يتم تحديث معاملات التحكم الجديدة عبر الصيغة التالية، $${\displaystyle u_{j}^{(k+1)}=u_{j}^{(k)}+d_{j}^{(k)},\quad j=1,2,...,n,}$$ وبالتالي، فإن${\textstyle (k+1)}$يتم إنشاء دالة المزج st على النحو التالي: $${\displaystyle U^{(k+1)}({\hat {\tau }})=\sum _{j=1}^{n}A_{j}({\hat {\tau }})u_{j}^{(k+1)}.}$$ تُجرى عملية التكرار المذكورة أعلاه حتى يتم الوصول إلى دقة المطابقة المطلوبة والحصول على سلسلة من وظائف المزج $${\displaystyle \left\{U^{(k)}({\hat {\tau }}),k=0,1,\dots \right\}.}$$ يتقارب IG-LSPIA إلى حل مسألة التجميع المقيدة للمربعات الصغرى. ^{[ 14 ]}

لنفترض أن n هو عدد نقاط التحكم و m هو عدد نقاط البيانات.

لو${\textstyle n=m}$، صيغة PIA التكرارية في شكل مصفوفة هي ^{[ 1 ]}$${\displaystyle {\begin{aligned}\mathbf {P^{(\alpha +1)}} &=\mathbf {P^{(\alpha )}} +\mathbf {\Delta } ^{(\alpha )}\\&=\mathbf {P} ^{(\alpha )}+\mathbf {Q} -\mathbf {B} \mathbf {P} ^{(\alpha )}\\&=\left(\mathbf {I} -\mathbf {B} \right)\mathbf {P} ^{(\alpha )}+\mathbf {Q} \end{aligned}}}$$ أين $${\displaystyle {\begin{aligned}\mathbf {Q} &=\left[\mathbf {Q} _{1},\mathbf {Q} _{2},\cdots ,\mathbf {Q} _{m}\right]^{T}\\\mathbf {P^{(\alpha )}} &=\left[\mathbf {P} _{1}^{(\alpha )},\mathbf {P} _{2}^{(\alpha )},\cdots ,\mathbf {P} _{n}^{(\alpha )}\right]^{T}\\\mathbf {\Delta } ^{(\alpha )}&=\left[\mathbf {\Delta } _{1}^{(\alpha )},\mathbf {\Delta } _{2}^{(\alpha )},\cdots ,\mathbf {\Delta } _{n}^{(\alpha )}\right]^{T}\\\mathbf {B} &={\begin{bmatrix}B_{1}(t_{1})&B_{2}(t_{1})&\cdots &B_{n}(t_{1})\\B_{1}(t_{2})&B_{2}(t_{2})&\cdots &B_{n}(t_{2})\\\vdots &\vdots &\ddots &\vdots \\B_{1}(t_{m})&B_{2}(t_{m})&\cdots &B_{n}(t_{m})\\\end{bmatrix}}.\end{aligned}}}$$ يرتبط تقارب خوارزمية PIA بخصائص مصفوفة التجميع. إذا كان نصف القطر الطيفي لمصفوفة التكرار${\displaystyle \mathbf {I} -\mathbf {B} }$أقل من${\displaystyle 1}$إذا كان الأمر كذلك، فإن طريقة PIA متقاربة. وقد ثبت أن طرق PIA متقاربة لمنحنيات وأسطح بيزير، ومنحنيات وأسطح بي-سبلاين، ومنحنيات وأسطح NURBS، وأسطح برنشتاين-بيزير المثلثية، وأسطح التقسيم الفرعي (لوب، كاتمول-كلارك، دو-سابين). ^{[ 2 ]}

لو${\textstyle n<m}$، LSPIA في شكل مصفوفة هو ^{[ 10 ] [ 19 ]}$${\displaystyle {\begin{aligned}\mathbf {P^{(\alpha +1)}} &=\mathbf {P^{(\alpha )}} +\mu \mathbf {B} ^{T}\mathbf {\Delta } ^{(\alpha )}\\&=\mathbf {P} ^{(\alpha )}+\mu \mathbf {B} ^{T}\left(\mathbf {Q} -\mathbf {B} \mathbf {P} ^{(\alpha )}\right)\\&=\left(\mathbf {I} -\mu \mathbf {B} ^{T}\mathbf {B} \right)\mathbf {P} ^{(\alpha )}+\mu \mathbf {B} ^{T}\mathbf {Q} .\end{aligned}}}$$ عندما تكون المصفوفة${\textstyle \mathbf {B} ^{T}\mathbf {B} }$إذا كانت غير منفردة ، فيمكن الحصول على النتائج التالية: ^{[ 23 ]}

دليل منذ${\textstyle \mathbf {B} ^{T}\mathbf {B} }$غير منفرد، و${\textstyle \mu >0}$، ثم${\textstyle \lambda (\mu \mathbf {B} ^{T}\mathbf {B} )>0}$. علاوة على ذلك، $${\displaystyle \lambda (\mu \mathbf {B} ^{T}\mathbf {B} )=\mu \lambda (\mathbf {B} ^{T}\mathbf {B} )<2{\frac {\lambda (\mathbf {B} ^{T}\mathbf {B} )}{\lambda _{0}}}<2.}$$ في ملخص،${\textstyle 0<\lambda (\mu \mathbf {B} ^{T}\mathbf {B} )<2}$.

البرهان: من الشكل المصفوفي ذي الصيغة التكرارية، نحصل على ما يلي: $${\displaystyle {\begin{aligned}\mathbf {P^{(\alpha +1)}} &=\left(\mathbf {I} -\mu \mathbf {B} ^{T}\mathbf {B} \right)\mathbf {P} ^{(\alpha )}+\mu \mathbf {B} ^{T}\mathbf {Q} ,\\&=\left(\mathbf {I} -\mu \mathbf {B} ^{T}\mathbf {B} \right)\left[\left(\mathbf {I} -\mu \mathbf {B} ^{T}\mathbf {B} \right)\mathbf {P} ^{(\alpha -1)}+\mu \mathbf {B} ^{T}\mathbf {Q} \right]+\mu \mathbf {B} ^{T}\mathbf {Q} ,\\&=\left(\mathbf {I} -\mu \mathbf {B} ^{T}\mathbf {B} \right)^{2}\mathbf {P} ^{(\alpha -1)}+\sum _{i=0}^{1}\left(\mathbf {I} -\mu \mathbf {B} ^{T}\mathbf {B} \right)\mu \mathbf {B} ^{T}\mathbf {Q} ,\\&=\cdots \\&=\left(\mathbf {I} -\mu \mathbf {B} ^{T}\mathbf {B} \right)^{\alpha +1}\mathbf {P} ^{(0)}+\sum _{i=0}^{\alpha }\left(\mathbf {I} -\mu \mathbf {B} ^{T}\mathbf {B} \right)^{\alpha }\mu \mathbf {B} ^{T}\mathbf {Q} .\\\end{aligned}}}$$ وفقًا للفرضية المذكورة أعلاه، فإن نصف القطر الطيفي للمصفوفة${\textstyle \mu \mathbf {B} ^{T}\mathbf {B} }$يرضي $${\displaystyle 0<\rho \left({\mu \mathbf {B} ^{T}\mathbf {B} }\right)<2}$$ وبالتالي فإن نصف القطر الطيفي لمصفوفة التكرار يحقق $${\displaystyle 0<\rho \left({\mathbf {I} -\mu \mathbf {B} ^{T}\mathbf {B} }\right)<1.}$$ متى${\textstyle \alpha \rightarrow \infty }$$${\displaystyle \left(\mathbf {I} -\mu \mathbf {B} ^{T}\mathbf {B} \right)^{\infty }=0,\ \sum _{i=0}^{\infty }\left(\mathbf {I} -\mu \mathbf {B} ^{T}\mathbf {B} \right)^{\alpha }={\frac {1}{\mu }}\left(\mathbf {B} ^{T}\mathbf {B} \right)^{-1}.}$$ نتيجة ل، $${\displaystyle \mathbf {P} ^{(\infty )}=\left(\mathbf {B} ^{T}\mathbf {B} \right)^{-1}\mathbf {B} ^{T}\mathbf {Q} ,}$$ أي،${\textstyle \mathbf {B} ^{T}\mathbf {B} \mathbf {P} ^{(\infty )}=\mathbf {B} ^{T}\mathbf {Q} }$وهذا يُعادل المعادلة العادية لمسألة المطابقة. وبالتالي، فإن خوارزمية LSPIA تتقارب إلى نتيجة المربعات الصغرى لتسلسل مُعطى من النقاط.

أظهر لين وآخرون أن خوارزمية LSPIA تتقارب حتى عندما تكون مصفوفة التكرار منفردة. ^{[ 18 ]}

• ملاءمة البيانات التكيفية: تُقسّم نقاط التحكم إلى نقاط تحكم نشطة ونقاط تحكم ثابتة . في كل جولة تكرارية، إذا وصل خطأ ملاءمة نقطة بيانات إلى دقة محددة، تُثبّت نقطة التحكم المقابلة لها ولا تُحدّث. تُكرّر هذه العملية التكرارية حتى تُثبّت جميع نقاط التحكم. يُحقق هذا الأسلوب أداءً جيدًا في ملاءمة البيانات واسعة النطاق من خلال تقليل عدد نقاط التحكم النشطة بشكل تكيفي. ^{[ 31 ]}
• ملاءمة البيانات واسعة النطاق: من خلال دمج T-spline مع PIA، تم اقتراح خوارزمية ملاءمة تزايدية مناسبة لملاءمة مجموعات البيانات واسعة النطاق. خلال التكرار التزايدي، تعيد كل جولة جديدة من التكرارات استخدام المعلومات من الجولة السابقة لتوفير العمليات الحسابية. بينما تنخفض سرعة تقارب الخوارزمية التكرارية التقليدية نقطة بنقطة مع زيادة عدد نقاط التحكم، فإن حساب كل خطوة تكرارية في PIA لا يرتبط بعدد نقاط التحكم؛ وهذا ما يمنح PIA قدرة فائقة على ملاءمة البيانات. ^{[ 10 ]}
• الملاءمة المحلية: استنادًا إلى الخاصية المحلية لـ PIA، تم اقتراح سلسلة من تنسيقات PIA المحلية. ^{[ 12 ] [ 32 ]}

بالنسبة لإعادة بناء المنحنيات والأسطح الضمنية، تتجنب PIA مجموعة المستوى الصفري الإضافية ومصطلح التنظيم، مما يحسن بشكل كبير من سرعة خوارزمية إعادة البناء. ^{[ 11 ]}

أولًا، تُؤخذ عينات من نقاط البيانات على المنحنى الأصلي. ثم، يُولّد منحنى التقريب متعدد الحدود الأولي أو منحنى التقريب النسبي لمنحنى الإزاحة من هذه النقاط المأخوذة. أخيرًا، يُقرّب منحنى الإزاحة تكراريًا باستخدام طريقة PIA. ^{[ 33 ]}

عند إدخال نموذج شبكة مثلثية، يقوم البرنامج أولاً بإنشاء شبكة سداسية الأوجه أولية، ثم يستخرج الشبكة الرباعية للسطح كشبكة حدودية أولية. خلال التكرارات، تُقيّد حركة كل رأس من رؤوس الشبكة لضمان صحتها. وأخيرًا، يُطابق النموذج السداسي الأوجه مع نموذج الإدخال المُعطى. يضمن البرنامج صحة الشبكة السداسية الأوجه المُولّدة، أي أن قيمة جاكوبي عند كل رأس من رؤوس الشبكة أكبر من الصفر. ^{[ 34 ]}

أولًا، تُحوّل بيانات الصورة إلى تسلسل أحادي البعد باستخدام مسح هيلبرت. ثم تُطابق نقاط البيانات هذه باستخدام خوارزمية LSPIA لإنشاء منحنى هيلبرت. أخيرًا، يُؤخذ عينات من منحنى هيلبرت، ويمكن إعادة بناء الصورة المضغوطة. تحافظ هذه الطريقة على معلومات الجوار للبكسلات بشكل جيد. ^{[ 35 ]}

بفرض وجود مجموعة من نقاط البيانات، نقوم أولاً بتعريف دالة التنعيم، ثم نحسب متجه الفرق المُلائم ومتجه التنعيم لنقطة التحكم؛ بعد ذلك، نُعدّل نقاط التحكم باستخدام أوزان التنعيم. وفقًا للخطوات السابقة، يمكن توليد منحنى وسطح التنعيم بشكل تكراري. نظرًا لوجود معلمات تنعيم كافية، يمكن لهذه الطريقة تحقيق تنعيم شامل أو محلي. كما أنها تتميز بمرونة تعديل متجهات العقد، وأوزان التنعيم، أو معلمات البيانات بعد كل جولة تكرار. تُعد طريقة تقليل الطاقة التقليدية حالة خاصة من هذه الطريقة، أي عندما تكون جميع أوزان التنعيم متساوية. ^{[ 13 ]}

تُعتبر قيم الأحمال المُجزأة مجموعة من نقاط البيانات، ويُستخدم مزيج من الدوال الأساسية ودوالها المشتقة كدالة مزج للمطابقة. تُعدّل هذه الطريقة تلقائيًا درجات حرية الحل العددي للمعادلة التفاضلية الجزئية وفقًا لنتيجة مطابقة دالة المزج مع قيم الأحمال. إضافةً إلى ذلك، يرتبط متوسط ​​زمن التكرار لكل خطوة بعدد نقاط البيانات فقط (أي نقاط التجميع) ولا يرتبط بعدد معاملات التحكم. ^{[ 14 ]}