سؤال التعقيد الأساسي - التنزل

Question

أحاول تقييم تعقيد بعض خوارزميات تصفية الصور الأساسية. كنت أتساءل عما إذا كنت تستطيع التحقق من هذه النظرية؛

بالنسبة لبكسل أساسي من قبل مرشح بكسل مثل عكس عدد العمليات ينمو خطيا بحجم الإدخال (بالبكسل) و

دع S = طول جانب الصورة دع M = # بكسل الإدخال

معكوس هو أمر O (م) أو O (S ^ 2).

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

دع r = دائرة نصف قطرها فلورف

التناسف هو من أجل O (M * ((R + R * 2) ^ 2) = O (M * (4R ^ 2) = O (MR ^ 2)

أو يجب أن اسمحوا ن = حجم فلتر الإضطاء (الحي) في بكسل؟

o (m * (n)) = O (MN)

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

إذا كان لديك أي روابط إلى ورقة حيث تم توثيق ذلك، فسيكون موضع تقدير كبير.

أطيب التحيات،

غافين

Answer 1

O (MN) يبدو صحيحا إذا فهمت أنه بالنسبة لكل بكسل في الصورة، فإن التنزل هو تعديل قيم بكسل في الحي N، بغض النظر عن N يجري المربع. N يمكن أن يكون أفضل مثلث أفضل ... ولكن توفير البكسل في الحي يتم ضبطه لكل بكسل في الصورة ثم O (MN) أكثر منطقية، لأن التبعية في البكسل المعدلة لكل بكسل في الصورة المصدر.

ومن المثير للاهتمام، في حي غير منتظم، قد يتم تعديل بعض البكسل من قبل قناع الحي أكثر من غيرها، ولكن O (MN) لن يقف.

إذا كان الحي أمرا أساسيا في بكسل ف ثم انتقل إلى P القادم الذي لم يكن في الحي (بمعنى أن كل بكسل يتم تحويله مرة واحدة)، فهذا لا يقف.