خوارزمية لويد

📅 آخر تحديث: ٢٨ يوليو ٢٠٢٦
✍️ نُشر في: ٢٨ يوليو ٢٠٢٦
📷 يحتوي على 11 صور
الموسوعة الحرة

في الهندسة الكهربائية وعلوم الحاسوب ، تُعرف خوارزمية لويد ، أو تكرار فورونوي ، أو استرخاء فورونوي، وهي خوارزمية سُميت نسبةً إلى ستيوارت ب. لويد، وتُستخدم لإيجاد مجموعات من النقاط متساوية التباعد في مجموعات فرعية من الفضاءات الإقليدية ، وتقسيم هذه المجموعات الفرعية إلى خلايا محدبة منتظمة الشكل والحجم. [ 1 ] وكما هو الحال في خوارزمية التجميع k -means ، تُحدد هذه الخوارزمية مركز كل مجموعة في التقسيم بشكل متكرر، ثم تُعيد تقسيم المدخلات وفقًا لأقرب مركز. في هذا السياق، تُحسب عملية المتوسط ​​بتكامل على منطقة من الفضاء، بينما تُنتج عملية أقرب مركز مخططات فورونوي .

على الرغم من أن الخوارزمية تُطبَّق بشكل مباشر على المستوى الإقليدي ، إلا أنه يمكن تطبيق خوارزميات مماثلة على فضاءات ذات أبعاد أعلى أو على فضاءات ذات مقاييس غير إقليدية . تُستخدم خوارزمية لويد لإنشاء تقريبات دقيقة لتقسيمات فورونوي المركزية للمدخلات، [ 2 ] والتي يمكن استخدامها في التكميم والتردد والتنقيط . تشمل التطبيقات الأخرى لخوارزمية لويد تنعيم شبكات المثلثات في طريقة العناصر المحدودة .

مثال على خوارزمية لويد. يظهر مخطط فورونوي لمواقع المواقع الحالية (باللون الأحمر) في كل تكرار. تشير الدوائر الرمادية إلى مراكز خلايا فورونوي.
طريقة لويد، التكرار 1
التكرار 1
طريقة لويد، التكرار الثاني
التكرار الثاني
طريقة لويد، التكرار 3
التكرار 3
طريقة لويد، التكرار 15
التكرار 15
في الصورة الأخيرة، تقع المواقع بالقرب من مراكز خلايا فورونوي. وقد تم العثور على تجزئة فورونوي مركزية.

تاريخ

اقترح ستيوارت ب. لويد من مختبرات بيل هذه الخوارزمية لأول مرة عام 1957 كتقنية لتعديل رمز النبض . انتشر عمل لويد على نطاق واسع، لكنه ظل غير منشور حتى عام 1982. [ 1 ] طوّر جويل ماكس خوارزمية مماثلة بشكل مستقل ونُشرت عام 1960، [ 3 ] ولهذا السبب تُعرف الخوارزمية أحيانًا باسم خوارزمية لويد-ماكس.

وصف الخوارزمية

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

ثم يقوم الجهاز بتنفيذ خطوة الاسترخاء التالية بشكل متكرر:

  • يتم حساب مخطط فورونوي للمواقع k .
  • يتم دمج كل خلية من خلايا مخطط فورونوي، ويتم حساب مركز الثقل.
  • ثم يتم نقل كل موقع إلى مركز خلية فورونوي الخاصة به.

التكامل وحساب مركز الثقل

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

تقريب

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

الحساب الدقيق

على الرغم من أن التضمين في فضاءات أخرى ممكن أيضًا، إلا أن هذا التوضيح يفترض الفضاء الإقليدي باستخدام معيار L2 ويناقش السيناريوهين الأكثر صلة، وهما بعدين وثلاثة أبعاد على التوالي.

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

  • في بعدين، تتصل حواف الخلية المضلعة بموقعها، مما يخلق مجموعة من المثلثات على شكل مظلة.
  • في ثلاثة أبعاد، تكون الخلية محاطة بعدة مضلعات مستوية يجب تقسيمها إلى مثلثات أولاً:
    • احسب مركز وجه المضلع، على سبيل المثال متوسط ​​جميع رؤوسه.
    • يؤدي توصيل رؤوس وجه المضلع بمركزه إلى تكوين مثلث مستوٍ على شكل مظلة.
    • بشكل بديهي، يتم الحصول على مجموعة من رباعيات الأوجه عن طريق توصيل مثلثات غلاف الخلية بموقع الخلية.

يتم الآن حساب تكامل الخلية ومركز كتلتها ( مركز ثقلها ) كمزيج مرجح من مراكز ثقل عناصرها البسيطة (يُشار إليها فيما يلي بـجأنا{\textstyle \mathbf {c} _{i}}).

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

بالنسبة لخلية ثنائية الأبعاد تحتوي على n من الأشكال المثلثية البسيطة ومساحة متراكمةأج=∑أنا=0نأأنا{\textstyle A_{C}=\sum _{i=0}^{n}a_{i}}(أينأأنا{\textstyle a_{i}}(مساحة المثلث البسيط)، يتم حساب مركز الخلية الجديد على النحو التالي:

ج=1أج∑أنا=0نجأناأأنا{\displaystyle C={\frac {1}{A_{C}}}\sum _{i=0}^{n}\mathbf {c} _{i}a_{i}}

وبالمثل، بالنسبة لخلية ثلاثية الأبعاد بحجمVج=∑أنا=0نvأنا{\textstyle V_{C}=\sum _{i=0}^{n}v_{i}}(أينvأنا{\textstyle v_{i}}(حيث يمثل حجم مجسم رباعي الأوجه البسيط)، يتم حساب مركز الثقل على النحو التالي:

ج=1Vج∑أنا=0نجأناvأنا{\displaystyle C={\frac {1}{V_{C}}}\sum _{i=0}^{n}\mathbf {c} _{i}v_{i}}

التقارب

في كل مرة تُجرى فيها خطوة استرخاء، تُصبح النقاط موزعة بشكل أكثر انتظامًا: تتباعد النقاط المتقاربة، وتتقارب النقاط المتباعدة. في بُعد واحد، ثبت أن هذه الخوارزمية تتقارب إلى مخطط فورونوي مركزي، يُسمى أيضًا تجزئة فورونوي مركزية . [ 4 ] في الأبعاد الأعلى، توجد بعض نتائج التقارب الأقل دقة. [ 5 ] [ 6 ]

يتقارب الخوارزمية ببطء، أو قد لا تتقارب إطلاقًا بسبب قيود الدقة العددية. لذا، تتوقف تطبيقات خوارزمية لويد في الواقع العملي عادةً بمجرد أن يصبح التوزيع "جيدًا بما فيه الكفاية". أحد معايير الإنهاء الشائعة هو التوقف عندما تقل أقصى مسافة تحركها أي نقطة في تكرار ما عن عتبة محددة مسبقًا. يمكن تسريع التقارب عن طريق زيادة مرونة النقاط، وذلك بتحريك كل نقطة مسافة ω مضروبة في المسافة إلى مركز الكتلة، وعادةً ما تُستخدم قيمة ω أقل بقليل من 2. [ 7 ]

التطبيقات

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

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

مسافات مختلفة

تُستخدم خوارزمية لويد عادةً في الفضاء الإقليدي . يلعب البُعد الإقليدي دورين في الخوارزمية: فهو يُستخدم لتحديد خلايا فورونوي، كما يُستخدم لاختيار مركز الثقل كنقطة تمثيلية لكل خلية، لأن مركز الثقل هو النقطة التي تُقلل متوسط ​​مربع البُعد الإقليدي إلى النقاط الموجودة في خليتها. يمكن استخدام مسافات بديلة، ونقاط مركزية بديلة عن مركز الثقل. على سبيل المثال، استخدم هاوسنر (2001) صيغةً مُعدّلة من مقياس مانهاتن (مع اتجاهات متغيرة محليًا) لإيجاد تبليط صورة ببلاطات مربعة تقريبًا تتوافق اتجاهاتها مع خصائص الصورة، واستخدمها لمحاكاة بناء الفسيفساء المُبلّطة . [ 11 ] في هذا التطبيق، وعلى الرغم من تغيير المقياس، استمر هاوسنر في استخدام مراكز الثقل كنقاط تمثيلية لخلايا فورونوي. ومع ذلك، بالنسبة للمقاييس التي تختلف بشكل كبير عن الإقليدية، قد يكون من المناسب اختيار النقطة التي تقلل متوسط ​​مربع المسافة كنقطة تمثيلية، بدلاً من مركز الثقل. [ 12 ]

انظر أيضاً

مراجع

  1. 1 2 لويد، ستيوارت ب. (1982)، "التكميم باستخدام طريقة المربعات الصغرى في PCM"، معاملات IEEE في نظرية المعلومات ، 28 (2): 129-137 ، doi : 10.1109/TIT.1982.1056489 ، S2CID 10833328 .
  2. ↑ دو، تشيانغ ؛ فابر، فانس؛ غونزبرغر، ماكس (1999)، "تبليطات فورونوي المركزية: التطبيقات والخوارزميات"، مجلة SIAM ، 41 (4): 637-676 ، Bibcode : 1999SIAMR..41..637D ، doi : 10.1137/S0036144599352836.
  3. ↑ ماكس، جويل (1960)، "التكميم لتحقيق الحد الأدنى من التشوه"، معاملات معهد مهندسي الراديو في نظرية المعلومات ، 6 (1): 7-12 ، doi : 10.1109/TIT.1960.1057548.
  4. ↑ دو، تشيانغ ؛ إميليانينكو، ماريا ؛ جو، ليلي (2006)، "تقارب خوارزمية لويد لحساب تجزئة فورونوي المركزية"، مجلة SIAM للتحليل العددي ، 44 : 102-119 ، CiteSeerX 10.1.1.591.9903 ، doi : 10.1137/040617364 .
  5. ↑ سابين، إم جيه؛ غراي، آر إم (1986)، "التقارب العالمي والاتساق التجريبي لخوارزمية لويد المعممة"، معاملات IEEE في نظرية المعلومات ، 32 (2): 148-155 ، doi : 10.1109/TIT.1986.1057168.
  6. ↑ إميليانينكو، ماريا؛ جو، ليلي؛ راند، ألكسندر (2009)، "عدم التدهور والتقارب العالمي الضعيف لخوارزمية لويد في R d "، مجلة SIAM للتحليل العددي ، 46 : 1423-1441 ، doi : 10.1137/070691334.
  7. ↑ شياو، شياو. "طريقة لويد للاسترخاء المفرط لحساب تجزئة فورونوي المركزية." (2010).
  8. ↑ ديوسن، أوليفر؛ هيلر، ستيفان؛ فان أوفرفيلد، كورنيليوس؛ ستروثوت، توماس (2000)، "النقاط العائمة: طريقة لحساب رسومات التنقيط"، منتدى رسومات الحاسوب ، 19 (3): 41-50 ، CiteSeerX 10.1.1.233.5810 ، doi : 10.1111/1467-8659.00396 ، S2CID 142991 ، وقائع يوروغرافيكس  .
  9. ↑ سيكورد، أدريان (2002)، "التنقيط الموزون لفورونوي"، وقائع ندوة الرسوم المتحركة والتقديم غير الواقعي (NPAR) ، ACM SIGGRAPH ، الصفحات 37-43 ، doi : 10.1145/508530.508537 ، ISBN  1-58113-494-0، S2CID 12153589 .
  10. ↑ دو، تشيانغ ؛ غونزبرغر، ماكس (2002)، "توليد الشبكة وتحسينها بناءً على تجزئة فورونوي المركزية"، الرياضيات التطبيقية والحساب ، 133 ( 2-3 ): 591-607 ، CiteSeerX 10.1.1.324.5020 ، doi : 10.1016/S0096-3003(01)00260-0 .
  11. ↑ هاوسنر، أليخو (2001)، "محاكاة الفسيفساء الزخرفية"، وقائع المؤتمر السنوي الثامن والعشرين حول رسومات الحاسوب والتقنيات التفاعلية ، ACM SIGGRAPH ، الصفحات 573-580 ، doi : 10.1145/383259.383327 ، ISBN  1-58113-374-X، S2CID 7188986 .
  12. ↑ ديكرسون، ماثيو ت .؛ إبستين، ديفيد ؛ وورتمان، كيفن أ. (2010)، "مخططات فورونوي المستوية لمجاميع الدوال المحدبة، والمسافة المُنعّمة، والتمدد"، وقائع الندوة الدولية السابعة حول مخططات فورونوي في العلوم والهندسة (ISVD 2010) ، الصفحات 13-22 ، arXiv : 0812.0607 ، doi : 10.1109/ISVD.2010.12 ، ISBN  978-1-4244-7606-0، S2CID 15971504 .
  • DemoGNG.js هو برنامج محاكاة رسومي بلغة جافا سكريبت لخوارزمية LBG ونماذج أخرى، ويتضمن عرض مناطق فورونوي.