DOI: https://doi.org/10.1137/25m1742916
PMID: https://pubmed.ncbi.nlm.nih.gov/42583065
تاريخ النشر: 2026-07-16
المؤلف: Yunpeng Shi وآخرون
الموضوع الرئيسي: التحليل الهندسي وتدفقات الانحناء
نظرة عامة
تقدم هذه القسم خوارزمية جديدة لمحاذاة الصور غير المتجانسة، والتي تعتبر ضرورية لمجموعة متنوعة من تطبيقات رؤية الكمبيوتر. تستفيد الطريقة المقترحة من مبادئ النقل الأمثل، مما يدمج كفاءة تقنيات فورييه السريعة مع موثوقية مقاييس الاحتمال المقطعة. على وجه التحديد، تحسب الخوارزمية المحاذاة بين صورتين بحجم \( L \times L \) باستخدام مسافة 2-فاسرشتاين المقطعة، محققة تعقيد حسابي قدره \( O(L^2 \log L) \).
تُبرز متانة الخوارزمية، مما يظهر فعاليتها في التعامل مع التحولات مثل الترجمة، والدوران، والتشوهات في الصور. لا تعزز هذه التطورات سرعة عمليات محاذاة الصور فحسب، بل تحافظ أيضًا على دقة عالية، مما يجعلها مساهمة قيمة في مجال رؤية الكمبيوتر.
مقدمة
تتناول مقدمة هذه الورقة البحثية المهمة الحرجة لمحاذاة الصور الصلبة في رؤية الكمبيوتر، مع التركيز بشكل خاص على الصور غير المتجانسة التي قد تختلف في التوزيعات الأساسية. تكافح طرق الارتباط التقليدية مع هذه الصور بسبب حساسيتها للتشوهات، مما يستلزم استكشاف مقاييس بديلة للمحاذاة. يقترح المؤلفون استخدام نظرية النقل الأمثل، وبشكل خاص مسافة فاسرشتاين المقطعة، التي تقدم نهجًا أكثر متانة من خلال اعتبار الصور كقياسات احتمالية وحساب الحد الأدنى من تكلفة نقل الكتلة بينها.
تسلط الورقة الضوء على التحديات الحسابية المرتبطة بمسافة فاسرشتاين في الأبعاد العالية، والتي يمكن أن تعيق تطبيقها في مهام محاذاة الصور. لمعالجة ذلك، يقدم المؤلفون خوارزمية سريعة تقلل من مسافة 2-فاسرشتاين المقطعة، محققة تعقيدًا حسابيًا قدره \(O(L^2 \log L)\) لمحاذاة صورتين بحجم \(L \times L\). تم إثبات أن طريقتهم متينة ضد الصور غير المتجانسة وقابلة للتوسع لمجموعات البيانات الكبيرة. ستفصل الأقسام اللاحقة من الورقة إعداد المشكلة، والأعمال ذات الصلة، وتطوير الخوارزمية، والثبات النظري لمسافة فاسرشتاين المقطعة، والتح validations التجريبية باستخدام مجموعات بيانات مثل MNIST وcryo-EM. كما يوفر المؤلفون الوصول إلى كودهم لمزيد من البحث والتطبيق.
النتائج
في هذا القسم، يقدم المؤلفون نتائج عددية تبرز مزايا مسافة فاسرشتاين المقطعة في مهام محاذاة الصور. تم هيكلة النتائج في أربعة أقسام فرعية: تناقش القسم 4.1 التوقيت الحسابي لمختلف مسافات النقل على الصور ذات الأحجام المتزايدة، بما في ذلك أدائها في المحاذاة الدورانية. توضح القسم 4.2 الخصائص المفيدة لمسافة فاسرشتاين المقطعة لتسجيل الصور. تظهر القسم 4.3 استقرار مسافة فاسرشتاين المقطعة عند تطبيقها على صور الإسقاط التوموغرافي للأجسام ثلاثية الأبعاد تحت زوايا عرض متغيرة. أخيرًا، تفصل القسم 4.4 النتائج التجريبية لخوارزمية المؤلفين المطبقة على محاذاة مجموعة بيانات أرقام MNIST المائلة والمُدَوَّرة، بما في ذلك الاختبارات مع الضوضاء الإضافية.
كما يوسع المؤلفون تحليلهم في القسم 4.4 من خلال مقارنة طريقتهم ضد تقنيات حسابية راسخة لتقريب مسافات فاسرشتاين وفاسرشتاين المقطعة. يشيرون إلى أنه بينما يعد نهج مونت كارلو لتقدير مسافة فاسرشتاين المقطعة ممكنًا، فإن طريقتهم، التي تستخدم اتجاهات الإسقاط المتساوية، تتفوق على العينة العشوائية في سياق المحاذاة الصلبة. تشير النتائج إلى أن مسافة 2-فاسرشتاين المقطعة المفلترة بالمنحدر هي المقياس الأكثر فعالية بشكل عام، خاصة في السيناريوهات التي تتضمن تحولات كبيرة في الصور. يتم تلخيص التوقيتات والتعقيدات الحسابية لمختلف المقاييس في الجدول 6، مما يكشف أن مسافة 2-فاسرشتاين المقطعة المفلترة بالمنحدر، على الرغم من كونها أبطأ قليلاً من مسافة 2-فاسرشتاين المقطعة القياسية، توفر أداءً متفوقًا في المحاذاة.
المناقشة
في هذا القسم، يتناول المؤلفون مشكلة محاذاة الصور من خلال الحركة الصلبة، مع التركيز بشكل خاص على محاذاة صورة الهدف \( g(x) \) إلى صورة المرجع \( f(x) \) من خلال تقليل مقياس المسافة. تمثل الصور كقياسات احتمالية مدعومة على القرص الواحد، مع الهدف من العثور على معلمات الترجمة والدوران المثلى التي تقلل المسافة \( d(f, T_s R_\theta g) \). يصنف المؤلفون خوارزميات المحاذاة الحالية إلى طرق تحسين محلي وطرق بحث شاملة، مع تسليط الضوء على قيود كل نهج. يقترحون خوارزمية جديدة تسرع البحث الشامل من أجل المحاذاة الدورانية، محققة تعقيدًا حسابيًا قدره \( O(L^2 \log L) \) باستخدام مسافة فاسرشتاين المقطعة، مما يتناقض مع تعقيد \( O(L^6) \) للطرق الساذجة.
يناقش المؤلفون أيضًا الأسس النظرية لمسافة فاسرشتاين المقطعة، موضحين استقرارها بالنسبة للتغيرات في زوايا العرض للصور التوموغرافية. يقدمون حدودًا على مقاييس المسافة، موضحين أن مسافة فاسرشتاين المقطعة أقل حساسية للتغيرات في اتجاه الإسقاط مقارنة بالمقاييس التقليدية مثل المسافة الإقليدية. بالإضافة إلى ذلك، يقدمون متغيرًا مفلترًا بالمنحدر لمسافة فاسرشتاين المقطعة، مما يعزز محاذاة الصور من خلال تحسين تمييز المكونات عالية التردد. تشير النتائج التجريبية إلى أن هذا النهج المفلتر بالمنحدر يحسن بشكل كبير أداء المحاذاة، خاصة لمجموعات البيانات مثل MNIST، مما يشير إلى إمكانية استخدامه في تطبيقات مثل المجهر الإلكتروني بالتبريد (cryo-EM).
DOI: https://doi.org/10.1137/25m1742916
PMID: https://pubmed.ncbi.nlm.nih.gov/42583065
Publication Date: 2026-07-16
Author(s): Yunpeng Shi et al.
Primary Topic: Geometric Analysis and Curvature Flows
Overview
This section presents a novel algorithm for aligning heterogeneous images, which is crucial for various computer vision applications. The proposed method leverages optimal transport principles, integrating the efficiency of fast Fourier techniques with the reliability of sliced probability metrics. Specifically, the algorithm computes the alignment between two images of size \( L \times L \) using the sliced 2-Wasserstein distance, achieving a computational complexity of \( O(L^2 \log L) \).
The robustness of the algorithm is highlighted, demonstrating its effectiveness in handling transformations such as translations, rotations, and deformations in the images. This advancement not only enhances the speed of image alignment processes but also maintains high accuracy, making it a valuable contribution to the field of computer vision.
Introduction
The introduction of this research paper addresses the critical task of rigid image alignment in computer vision, particularly focusing on heterogeneous images that may differ in underlying distributions. Traditional correlation methods struggle with these images due to their sensitivity to deformations, necessitating the exploration of alternative metrics for alignment. The authors propose utilizing optimal transport theory, specifically the sliced Wasserstein distance, which offers a more robust approach by treating images as probability measures and calculating the minimal cost of transporting mass between them.
The paper highlights the computational challenges associated with the Wasserstein distance in high dimensions, which can hinder its application in image alignment tasks. To address this, the authors introduce a fast algorithm that minimizes the sliced 2-Wasserstein distance, achieving a computational complexity of \(O(L^2 \log L)\) for aligning two \(L \times L\) images. Their method is demonstrated to be both robust against heterogeneous images and scalable for large datasets. The subsequent sections of the paper will detail the problem setup, related works, algorithm development, theoretical stability of the sliced Wasserstein distance, and experimental validations using datasets such as MNIST and cryo-EM. The authors also provide access to their code for further research and application.
Results
In this section, the authors present numerical results that highlight the advantages of the sliced Wasserstein distance in image alignment tasks. The results are structured into four subsections: Section 4.1 discusses the computational timing for various transport distances on images of increasing sizes, including their performance in rotational alignment. Section 4.2 illustrates the beneficial properties of the sliced Wasserstein distance for image registration. Section 4.3 demonstrates the stability of the sliced Wasserstein distance when applied to tomographic projection images of 3-D objects under varying viewing angles. Finally, Section 4.4 details the experimental outcomes of the authors’ algorithm applied to the alignment of a shifted and rotated MNIST digit dataset, including tests with additive noise.
The authors also extend their analysis in Section 4.4 by comparing their method against established computational techniques for approximating the Wasserstein and sliced Wasserstein distances. They note that while the Monte Carlo approach for estimating the sliced Wasserstein distance is feasible, their method, which utilizes equispaced projection directions, outperforms random sampling in the context of rigid alignment. The results indicate that the ramp-filtered sliced 2-Wasserstein distance is the most effective metric overall, particularly excelling in scenarios with significant image shifts. The timing and computational complexities for various metrics are summarized in Table 6, revealing that the ramp-filtered sliced 2-Wasserstein distance, despite being slightly slower than the standard sliced 2-Wasserstein distance, provides superior alignment performance.
Discussion
In this section, the authors address the problem of aligning images through rigid motion, specifically focusing on the alignment of a target image \( g(x) \) to a reference image \( f(x) \) by minimizing a distance metric. The images are represented as probability measures supported on the unit disk, with the objective of finding optimal translation and rotation parameters that minimize the distance \( d(f, T_s R_\theta g) \). The authors categorize existing alignment algorithms into local optimization and exhaustive search methods, highlighting the limitations of each approach. They propose a novel algorithm that accelerates exhaustive search for rotational alignment, achieving a computational complexity of \( O(L^2 \log L) \) using the sliced Wasserstein distance, which contrasts with the \( O(L^6) \) complexity of naive methods.
The authors also discuss the theoretical underpinnings of the sliced Wasserstein distance, demonstrating its stability with respect to changes in viewing angles for tomographic images. They provide bounds on the distance metrics, showing that the sliced Wasserstein distance is less sensitive to changes in projection direction compared to traditional metrics like the Euclidean distance. Additionally, they introduce a ramp-filtered variant of the sliced Wasserstein distance, which enhances image alignment by improving the distinguishability of high-frequency components. The empirical results indicate that this ramp-filtered approach significantly improves alignment performance, particularly for datasets like MNIST, suggesting its potential utility in applications such as cryo-electron microscopy (cryo-EM).