مخطط الرفع

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

تقوم خوارزمية الرفع بتحليل أي تحويل موجي منفصل ذي مرشحات محدودة إلى سلسلة من عوامل الالتفاف الأولية، والتي تسمى خطوات الرفع، مما يقلل عدد العمليات الحسابية بمقدار النصف تقريبًا. كما يتم تبسيط معالجة حدود الإشارة. ^{[ 2 ]}

يطبق تحويل المويجات المنفصل عدة مرشحات بشكل منفصل على الإشارة نفسها. وعلى النقيض من ذلك، في مخطط الرفع، تُقسّم الإشارة كما لو كانت سحابًا. ثم تُطبّق سلسلة من عمليات الالتفاف والتجميع على الإشارات المقسمة.

يُظهر الشكل أعلاه أبسط نسخة من تحويل الموجة الأمامية المعبر عنها في مخطط الرفع.${\displaystyle P}$تعني خطوة التنبؤ، والتي ستُدرس بشكل منفصل. تحسب خطوة التنبؤ دالة الموجة في تحويل الموجة، وهي عبارة عن مرشح تمرير عالي . أما خطوة التحديث فتحسب دالة القياس، مما ينتج عنه نسخة أكثر سلاسة من البيانات.

كما ذُكر أعلاه، تُعدّ طريقة الرفع أسلوبًا بديلًا لإجراء تحويل المويجات المنفصلة (DWT) باستخدام المويجات ثنائية التعامد. ولإجراء تحويل المويجات المنفصلة باستخدام طريقة الرفع، يجب اشتقاق خطوات الرفع والتحجيم المقابلة من المويجات ثنائية التعامد. مرشحات التحليل (${\displaystyle g,h}$يتم أولاً كتابة ) الموجة المحددة في مصفوفة متعددة الأطوار

${\displaystyle P(z)={\begin{bmatrix}h_{\text{even}}(z)&g_{\text{even}}(z)\\h_{\text{odd}}(z)&g_{\text{odd}}(z)\end{bmatrix}},}$

أين${\displaystyle \det P(z)=z^{-m}}$.

مصفوفة متعددة الأطوار هي مصفوفة 2 × 2 تحتوي على مرشحات التمرير المنخفض والتمرير العالي للتحليل، حيث يتم تقسيم كل مرشح إلى معاملاته متعددة الحدود الزوجية والفردية وتطبيعها. ومن ثم، تُحلل المصفوفة إلى سلسلة من مصفوفات مثلثية علوية وسفلية 2 × 2، كل منها بعناصر قطرية تساوي 1. تحتوي المصفوفات المثلثية العلوية على معاملات خطوات التنبؤ، بينما تحتوي المصفوفات المثلثية السفلية على معاملات خطوات التحديث. يمكن استخراج مصفوفة تتكون من أصفار فقط باستثناء القيم القطرية لاستنتاج معاملات خطوة القياس. تُحلل مصفوفة متعددة الأطوار إلى الشكل التالي:

${\displaystyle P(z)={\begin{bmatrix}1&a(1+z^{-1})\\0&1\end{bmatrix}}{\begin{bmatrix}1&0\\b(1+z)&1\end{bmatrix}},}$

أين${\displaystyle a}$يمثل معامل خطوة التنبؤ، و${\displaystyle b}$يمثل معامل خطوة التحديث.

يظهر أدناه مثال على عملية استخراج أكثر تعقيدًا تتضمن خطوات متعددة للتنبؤ والتحديث، بالإضافة إلى خطوات التحجيم؛${\displaystyle a}$يمثل معامل خطوة التنبؤ الأولى،${\displaystyle b}$يمثل معامل خطوة التحديث الأولى،${\displaystyle c}$يمثل معامل خطوة التنبؤ الثانية،${\displaystyle d}$يمثل معامل خطوة التحديث الثانية،${\displaystyle k_{1}}$يمثل معامل القياس للعينات الفردية، و${\displaystyle k_{2}}$معامل القياس للعينات الزوجية:

${\displaystyle P(z)={\begin{bmatrix}1&a(1+z^{-1})\\0&1\end{bmatrix}}{\begin{bmatrix}1&0\\b(1+z)&1\end{bmatrix}}{\begin{bmatrix}1&c(1+z^{-1})\\0&1\end{bmatrix}}{\begin{bmatrix}1&0\\d(1+z)&1\end{bmatrix}}{\begin{bmatrix}k_{1}&0\\0&k_{2}\end{bmatrix}}.}$

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

لإجراء تحويل CDF 9/7، يلزم أربع خطوات رفع: خطوتان للتنبؤ وخطوتان للتحديث. يؤدي تحليل الرفع إلى تسلسل خطوات الترشيح التالي. ^{[ 3 ]}

${\displaystyle d_{l}=d_{l}+a(s_{l}+s_{l+1}),}$

${\displaystyle s_{l}=s_{l}+b(d_{l}+d_{l-1}),}$

${\displaystyle d_{l}=d_{l}+c(s_{l}+s_{l+1}),}$

${\displaystyle s_{l}=s_{l}+d(d_{l}+d_{l-1}),}$

${\displaystyle d_{l}=k_{1}d_{l},}$

${\displaystyle s_{l}=k_{2}s_{l}.}$

طُوِّر مخطط الرفع المعمم بواسطة جويل سوليه وفيليب ساليمبييه، ونُشر في أطروحة الدكتوراه لسوليه. ^{[ 4 ]} وهو يستند إلى مخطط الرفع الكلاسيكي، ويُعمِّمه بإزالة قيدٍ كامنٍ في بنيته. يتضمن مخطط الرفع الكلاسيكي ثلاثة أنواع من العمليات:

1. يقوم تحويل المويجات الكسول بتقسيم الإشارة${\displaystyle f_{j}[n]}$في إشارتين جديدتين: إشارة العينات الفردية المشار إليها بـ${\displaystyle f_{j}^{o}[n]}$وإشارة العينات الزوجية المشار إليها بـ${\displaystyle f_{j}^{e}[n]}$.
2. تُحسب خطوة التنبؤ قيمة تنبؤية للعينات الفردية، بناءً على العينات الزوجية (أو العكس). ثم تُطرح هذه القيمة التنبؤية من العينات الفردية، مما يُنشئ إشارة خطأ.${\displaystyle g_{j+1}[n]}$.
3. تُعيد خطوة التحديث معايرة فرع التردد المنخفض باستخدام جزء من الطاقة التي أُزيلت أثناء عملية أخذ العينات الفرعية. في حالة الرفع الكلاسيكي، يُستخدم هذا من أجل "إعداد" الإشارة لخطوة التنبؤ التالية. وتستخدم هذه الخطوة العينات الفردية المتوقعة.${\displaystyle g_{j+1}[n]}$لإعداد الأزواج${\displaystyle f_{j}^{e}[n]}$(أو العكس). يتم طرح هذا التحديث من العينات الزوجية، مما ينتج الإشارة المشار إليها بـ${\displaystyle f_{j+1}[n]}$.

تتميز هذه الخوارزمية بقابليتها للعكس نظرًا لبنيتها. في جهاز الاستقبال ، تُحسب خطوة التحديث أولًا، ثم تُضاف نتيجتها إلى العينات الزوجية، وبعد ذلك يُمكن حساب التنبؤ نفسه تمامًا لإضافته إلى العينات الفردية. لاستعادة الإشارة الأصلية، يجب عكس تحويل المويجات الكسولة. تتضمن خوارزمية الرفع المعممة نفس أنواع العمليات الثلاثة. مع ذلك، تتجنب هذه الخوارزمية قيد الجمع والطرح الذي كان يفرضه الرفع التقليدي، وهو ما يترتب عليه بعض النتائج. على سبيل المثال، يجب أن يضمن تصميم جميع الخطوات قابلية الخوارزمية للعكس (وهو أمر غير مضمون في حال تجنب قيد الجمع والطرح).

تعريف

مخطط الرفع المعمم هو تحويل ثنائي يتبع هذه القواعد:

1. يقوم هذا الأسلوب بفصل المدخلات إلى دفق من العينات ذات الأرقام الزوجية ودفق آخر من العينات ذات الأرقام الفردية. ويُشار إلى هذا أحيانًا باسم تحويل المويجات الكسول .
2. يحسب هذا الإجراء خريطة تنبؤ . تحاول هذه الخطوة التنبؤ بالعينات الفردية مع مراعاة العينات الزوجية (أو العكس). توجد خريطة من فضاء العينات في${\displaystyle f_{j}^{e}[n]}$إلى مساحة العينات في${\displaystyle g_{j+1}[n]}$في هذه الحالة، العينات (من${\displaystyle f_{j}^{e}[n]}$) تم اختياره ليكون المرجع لـ${\displaystyle f_{j}^{o}[n]}$تُسمى هذه السياقات . ويمكن التعبير عنها على النحو التالي:

   ${\displaystyle g_{j+1}[n]=P(f_{j}^{o}[n];f_{j}^{e}[n]).}$

3. يحسب هذا الإجراء خريطة التحديث . تحاول هذه الخطوة تحديث العينات الزوجية مع مراعاة العينات الفردية المتوقعة. وهي بمثابة تحضير لخطوة التنبؤ التالية، إن وجدت. ويمكن التعبير عنها كما يلي:

   ${\displaystyle f_{j+1}[n]=U(f_{j}^{e}[n];g_{j+1}[n]).}$

من الواضح أن هذه التطبيقات لا يمكن أن تكون أي دوال. ولضمان قابلية عكس المخطط نفسه، يجب أن تكون جميع التطبيقات الداخلة في التحويل قابلة للعكس. في حال نشأت التطبيقات ووصلت إلى مجموعات منتهية (إشارات منفصلة ذات قيم محدودة)، فإن هذا الشرط يكافئ القول بأن التطبيقات أحادية (تقابل). علاوة على ذلك، إذا كان التطبيق ينتقل من مجموعة إلى مجموعة أخرى لها نفس العدد ، فيجب أن يكون تقابليًا .

في مخطط الرفع المعمم، يتم تجنب قيد الجمع/الطرح بإدراج هذه الخطوة في عملية الربط. وبهذه الطريقة يتم تعميم مخطط الرفع الكلاسيكي.

• تحويلات الموجات الصغيرة التي تربط الأعداد الصحيحة بالأعداد الصحيحة
• تحويل فورييه مع إعادة بناء دقيقة على مستوى البت ^{[ 9 ]}
• بناء الموجات الصغيرة بالعدد المطلوب من عوامل النعومة وعزوم التلاشي
• بناء الموجات الصغيرة المطابقة لنمط معين ^{[ 10 ]}
• تطبيق تحويل المويجات المنفصلة في JPEG 2000
• التحويلات القائمة على البيانات، على سبيل المثال، الموجات الصغيرة التي تتجنب الحواف ^{[ 11 ]}
• تحويلات المويجات على الشبكات غير القابلة للفصل ، على سبيل المثال، المويجات الحمراء والسوداء على شبكة الخماسي ^{[ 12 ]}

• تعتمد خوارزمية فيستل في علم التشفير على فكرة مشابهة لتقسيم البيانات وتطبيق الدوال بالتناوب مع الجمع. وتُستخدم هذه الفكرة في كل من خوارزمية فيستل وخوارزمية الرفع لتحقيق التشفير وفك التشفير المتناظر.

• مخطط الرفع – وصف موجز لخوارزمية التحليل إلى عوامل
• مقدمة عن مخطط الرفع
• تحويل المويجات السريع