تسريع التشابه الذاتي في الصورة

Question

أنا أكتب البرنامج الذي سوف توليد الصور.قياس واحد أريده هو كمية الذاتي "التشابه" في الصورة.كتبت البرمجية التالية التي تبدو على countBest-أفضل عشر مباريات لكل sizeWindow * sizeWindow النافذة في الصورة:

double Pattern::selfSimilar(int sizeWindow, int countBest) {
    std::vector<int> *pvecount;

    double similarity;
    int match;
    int x1;
    int x2;
    int xWindow;
    int y1;
    int y2;
    int yWindow;

    similarity = 0.0;

    // (x1, y1) is the original that's looking for matches.

    for (x1 = 0; x1 < k_maxX - sizeWindow; x1++) {
        for (y1 = 0; y1 < k_maxY - sizeWindow; y1++) {
             pvecount = new std::vector<int>();

             // (x2, y2) is the possible match.
             for (x2 = 0; x2 < k_maxX - sizeWindow; x2++) {
                 for (y2 = 0; y2 < k_maxY - sizeWindow; y2++) {
                     // Testing... 
                     match = 0;

                     for (xWindow = 0; xWindow < sizeWindow; xWindow++) {
                         for (yWindow = 0; yWindow < sizeWindow; yWindow++) {
                             if (m_color[x1 + xWindow][y1 + yWindow] == m_color[x2 + xWindow][y2 + yWindow]) {
                                 match++;
                             }
                         }
                     }

                     pvecount->push_back(match);
                 }
             }

             nth_element(pvecount->begin(), pvecount->end()-countBest, pvecount->end());

             similarity += (1.0 / ((k_maxX - sizeWindow) * (k_maxY - sizeWindow))) *
                 (*(pvecount->end()-countBest) / (double) (sizeWindow * sizeWindow));

             delete pvecount;
        }
    }

    return similarity;
}

والخبر السار هو أن الخوارزمية لا ما أريد:فإنه سيتم إرجاع قيمة من 0.0 إلى 1.0 حول كيفية الذاتية مماثلة' صورة.

الأخبار السيئة-كما أنا متأكد من أن كنت قد لاحظت بالفعل-هو أن الخوارزمية بطيئة للغاية.فإنه يأخذ (k_maxX - sizeWindow) * (k_maxY - sizeWindow) * (k_maxX - sizeWindow) * (k_maxY - sizeWindow) * sizeWindow * sizeWindow خطوات تشغيل.

بعض القيم النموذجية عن المتغيرات:

k_maxX = 1280
k_maxY = 1024
sizeWindow = between 5 and 25
countBest = 3, 4, or 5
m_color[x][y] is defined as short m_color[k_maxX][k_maxY] with values between 0 and 3 (but may increase in the future.)

الآن أنا لا قلق بشأن أثر الذاكرة التي اتخذتها pvecount.في وقت لاحق, يمكنني استخدام فرز مجموعة البيانات التي لا تضيف عنصر آخر عندما يكون أصغر من countBest.أنا فقط قلقة خوارزمية السرعة.

كيف يمكنني زيادة سرعة هذا ؟

Answer 1

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

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

diff = (m_color[x1 + xWindow][y1 + yWindow] - m_color[x2 + xWindow][y2 + yWindow]);
sum += diff*diff;

واستخدام مجموع بدلا من المباراة كما معيار التشابه (الآن أصغر يعني أفضل).

العودة إلى ما كنت طلبت حقا:أعتقد أنه من الممكن خفض وقت تشغيل عامل 2/sizeWindow (ربما تربيع؟), ولكن هذا هو قليلا فوضوي.إنه استنادا إلى حقيقة أن بعض أزواج الساحات قارنت يبقى نفسه تقريبا عندما تزايد y1 1.إذا إزاحة xOff = x2-x1 يوف = y2-y1 هي نفسها فقط أعلى (rsp.أسفل) خطوط عمودية من الساحات لم تعد (rsp.الآن, ولكن ليس قبل) مطابقة.إذا كنت الحفاظ على القيم لك حساب على المباراة في صفيف ثنائي الأبعاد فهرستها من قبل إزاحة xOff = x2-x1 يوف = y2-y1, ثم يمكن حساب قيمة جديدة لـ مباراة[xOff][يوف] عن y1 بنسبة 1 x1 يقيم نفسه قبل 2*sizeWindow المقارنات:

for (int x = x1; x < x1 + sizeWindow; x++) {
    if (m_color[x][y1] == m_color[x + xOff][y1 + yOff]) {
        match[xOff][yOff]--; // top stripes no longer compared
    }

    if (m_color[x][y1+sizeWindow] == m_color[x + xOff][y1 + sizeWindow + yOff]) {
        match[xOff][yOff]++; // bottom stripe compared not, but wasn't before
    }
}

(مثل القيم الممكنة ل يوف يتغير - من خلال تزايد y1 - من الفترة [y2 - y1, k_maxY - sizeWindow - y1 - 1] على الفترة [y2 - y1 - 1, k_maxY - sizeWindow - y1 - 2] يمكنك تجاهل مباريات مع الثاني مؤشر يوف = k_maxY - sizeWindow - y1 - 1 و يكون لحساب مباريات مع الثاني مؤشر يوف = y2 - y1 - 1 بشكل مختلف).ربما يمكنك أيضا الحفاظ على القيم قبل كم يمكنك زيادة/نقصان مباراة[][] أثناء حلقة في مجموعة للحصول على آخر 2/sizeWindow تسريع.

Answer 2

حسنا, أولا, هذا النهج غير مستقرة على الإطلاق.إذا قمت بإضافة الضجيج العشوائي إلى الصور الخاصة بك, وسوف تقلل إلى حد كبير من التشابه بين الصورتين.والأهم من ذلك من معالجة الصور نظر ليس بالكفاءة أو جيدة بشكل خاص.أقترح آخر النهج ؛ على سبيل المثال باستخدام المويجات النهج القائم على.إذا قمت بإجراء 2d DWT على الصورة الخاصة بك على مستويات قليلة مقارنة رفع معاملات, كنت على الارجح الحصول على نتائج أفضل.بالإضافة إلى تحويل المويجات المنفصلة O(n).

الجانب السلبي هو أن المويجات متقدمة رياضية الموضوع.هناك بعض جيدة أوبن كورس الملاحظات على المويجات و filterbanks هنا.