Shablon bo'yicha qidirish (template matching)

12-bob 6 kod bloki 2835 so'z

Eng sodda "topish" usuli

Shablon — kichik rasm bo'lagi. cv2.matchTemplate uni katta rasmning har joyiga qo'yib ko'radi va har pozitsiya uchun o'xshashlik bahosini beradi. Natija — rasm: unda eng yorqin (yoki eng qorong'i) nuqta eng yaxshi moslikni ko'rsatadi.

Bizning shablonimiz shakllar.png dan qirqib olingan, shuning uchun javobni aniq bilamiz: shablon.png = shakllar.png[270:410, 230:390] — uchburchak va uning atrofi, ya'ni chap yuqori burchagi (x=230, y=270).

rasm = cv2.imread(str(RASM / "shakllar.png"))
shablon = cv2.imread(str(RASM / "shablon.png"))
gray = cv2.cvtColor(rasm, cv2.COLOR_BGR2GRAY)
sh_gray = cv2.cvtColor(shablon, cv2.COLOR_BGR2GRAY)
h, w = sh_gray.shape
print(f"rasm: {gray.shape[1]}x{gray.shape[0]} | shablon: {w}x{h}")

natija = cv2.matchTemplate(gray, sh_gray, cv2.TM_CCOEFF_NORMED)
print(f"natija xaritasi: {natija.shape[1]}x{natija.shape[0]} "
      f"(= {gray.shape[1]} - {w} + 1, {gray.shape[0]} - {h} + 1)")
min_v, max_v, min_l, max_l = cv2.minMaxLoc(natija)
print(f"eng yaxshi moslik: {max_v:.4f}, joyi {max_l} | haqiqiy joy (230, 270)")

topildi = rasm.copy()
cv2.rectangle(topildi, max_l, (max_l[0] + w, max_l[1] + h), (0, 0, 255), 3)
ko_rsat(shablon, cv2.normalize(natija, None, 0, 255, cv2.NORM_MINMAX).astype(np.uint8), topildi,
        nom="shablon_asos.png", sarlavhalar=["shablon", "o'xshashlik xaritasi", "topilgan joy"],
        izoh="Xaritadagi eng yorqin nuqta — eng yaxshi moslik. U shablonning chap yuqori burchagiga to'g'ri keladi.")

rasm: 640x480 | shablon: 160x140
natija xaritasi: 481x341 (= 640 - 160 + 1, 480 - 140 + 1)
eng yaxshi moslik: 1.0000, joyi (230, 270) | haqiqiy joy (230, 270)

Xaritadagi eng yorqin nuqta — eng yaxshi moslik. U shablonning chap yuqori burchagiga to'g'ri keladi.

Natija xaritasi asl rasmdan kichik: shablon rasmdan chiqib ketmasligi uchun faqat (W-w+1) x (H-h+1) ta pozitsiya tekshiriladi. Shuning uchun topilgan koordinata chap yuqori burchak, markaz emas.

Oltita usul va ularning farqi

usullar = {
    "TM_SQDIFF": cv2.TM_SQDIFF, "TM_SQDIFF_NORMED": cv2.TM_SQDIFF_NORMED,
    "TM_CCORR": cv2.TM_CCORR, "TM_CCORR_NORMED": cv2.TM_CCORR_NORMED,
    "TM_CCOEFF": cv2.TM_CCOEFF, "TM_CCOEFF_NORMED": cv2.TM_CCOEFF_NORMED,
}
HAQIQAT = (230, 270)
qatorlar = []
for nom, m in usullar.items():
    r = cv2.matchTemplate(gray, sh_gray, m)
    mn, mx, mnl, mxl = cv2.minMaxLoc(r)
    eng_yaxshi = mnl if m in (cv2.TM_SQDIFF, cv2.TM_SQDIFF_NORMED) else mxl
    xato = ((eng_yaxshi[0] - HAQIQAT[0]) ** 2 + (eng_yaxshi[1] - HAQIQAT[1]) ** 2) ** 0.5
    qatorlar.append({"usul": nom, "eng yaxshi": "min" if "SQDIFF" in nom else "max",
                     "topilgan joy": str(eng_yaxshi), "xato, piksel": round(xato, 1)})
show(pd.DataFrame(qatorlar))

Shablon rasmdan aynan qirqib olingan, demak hamma usul uni xatosiz topishi kerak edi. Lekin jadvalga qarang: ikkitasi topa olmadi. TM_CCORR 122 piksel, TM_CCOEFF esa 187 piksel yanglishdi — ya'ni butunlay boshqa shaklni ko'rsatdi.

Sababi normallashtirishda. TM_CCORR shablon bilan rasm bo'lagining ko'paytmalari yig'indisini oladi: bo'lak umuman o'xshamasa ham, yorqin bo'lsa yig'indi katta chiqadi. Shuning uchun u har doim rasmning eng yorug' joyini yoqtiradi. TM_CCOEFF o'rtachani ayiradi, lekin natijani kattalikka bo'lmaydi — shuning uchun u kontrasti kuchli joyga og'adi.

_NORMED variantlari natijani ikkala bo'lakning kattaligiga bo'ladi. Shundan keyin ball 0–1 oralig'ida bo'ladi va "o'xshashlik" degani haqiqatan o'xshashlikni bildiradi.

Qoida: har doim _NORMED variantini ishlating, odatda TM_CCOEFF_NORMED ni.

:::gotcha SQDIFF da minMaxLoc ning qaysi qiymatini olish TM_SQDIFF va TM_SQDIFF_NORMED da eng yaxshi moslik — eng kichik qiymat, ya'ni minMaxLoc ning uchinchi qaytargani (min_loc). Qolgan to'rttasida esa max_loc. Buni chalkashtirish — shablon qidirishda eng ko'p uchraydigan xato. :::

Bir nechta moslik topish

minMaxLoc faqat bittasini beradi. Bir nechta bir xil obyekt bo'lsa, chegaradan yuqori hamma nuqtani olish kerak — va ularni birlashtirish, chunki har moslik atrofida o'nlab qo'shni nuqta yoqiladi.

kop = np.full((420, 560, 3), 245, np.uint8)
JOYLAR = [(40, 40), (250, 60), (120, 230), (380, 200)]
for x, y in JOYLAR:
    kop[y:y + h, x:x + w] = shablon
kop_gray = cv2.cvtColor(kop, cv2.COLOR_BGR2GRAY)
r = cv2.matchTemplate(kop_gray, sh_gray, cv2.TM_CCOEFF_NORMED)

CHEGARA = 0.9
ys, xs = np.where(r >= CHEGARA)
print(f"chegaradan yuqori nuqtalar: {len(xs)} ta (haqiqiy obyektlar: {len(JOYLAR)} ta)")

qutilar = [[int(x), int(y), w, h] for x, y in zip(xs, ys)]
indekslar = cv2.dnn.NMSBoxes(qutilar, [float(r[y, x]) for x, y in zip(xs, ys)], CHEGARA, 0.3)
tanlangan = sorted([tuple(qutilar[i][:2]) for i in np.array(indekslar).ravel()])
print(f"NMS dan keyin: {len(tanlangan)} ta | topilgan joylar: {tanlangan}")
print(f"haqiqiy joylar: {sorted(JOYLAR)}")

belgi = kop.copy()
for x, y in tanlangan:
    cv2.rectangle(belgi, (x, y), (x + w, y + h), (0, 0, 255), 3)
ko_rsat(cv2.normalize(r, None, 0, 255, cv2.NORM_MINMAX).astype(np.uint8), belgi, nom="kop_moslik.png",
        sarlavhalar=["o'xshashlik xaritasi — 4 ta yorqin nuqta", "NMS dan keyin topilganlar"],
        izoh="Chegaradan yuqori yuzlab nuqta bo'ladi; NMS ularni obyekt boshiga bittaga tushiradi.")

chegaradan yuqori nuqtalar: 196 ta (haqiqiy obyektlar: 4 ta)
NMS dan keyin: 4 ta | topilgan joylar: [(40, 40), (120, 230), (250, 60), (380, 200)]
haqiqiy joylar: [(40, 40), (120, 230), (250, 60), (380, 200)]

Chegaradan yuqori yuzlab nuqta bo'ladi; NMS ularni obyekt boshiga bittaga tushiradi.

NMS (Non-Maximum Suppression) — bir-biriga ko'p qismi bilan ustma-ust tushgan quti-lardan faqat eng yaxshisini qoldiradi. 0.3 — ruxsat etilgan ustma-ustlik ulushi (IoU). Bu funksiya obyekt topishning hamma turida ishlatiladi, YOLO da ham.

Shablon qidirish qayerda sinadi

Bu usulning cheklovini bilish uni ishlatishdan muhimroq. Uchta sinovni o'tkazamiz: o'lcham, burilish, yorug'lik.

def eng_yaxshi_ball(katta_gray, shablon_gray):
    r = cv2.matchTemplate(katta_gray, shablon_gray, cv2.TM_CCOEFF_NORMED)
    return round(float(cv2.minMaxLoc(r)[1]), 3)

show(pd.DataFrame([{"rasm o'lchami": f"x{k}", "eng yaxshi ball": eng_yaxshi_ball(
    cv2.resize(gray, None, fx=k, fy=k, interpolation=cv2.INTER_AREA), sh_gray)}
    for k in (0.7, 0.85, 0.95, 1.0, 1.05, 1.2, 1.5)]))

qatorlar = []
for burchak in (0, 5, 10, 20, 45, 90):
    M = cv2.getRotationMatrix2D((gray.shape[1] / 2, gray.shape[0] / 2), burchak, 1.0)
    o = cv2.warpAffine(gray, M, (gray.shape[1], gray.shape[0]), borderValue=245)
    qatorlar.append({"burilish": f"{burchak}°", "eng yaxshi ball": eng_yaxshi_ball(o, sh_gray)})
show(pd.DataFrame(qatorlar))

show(pd.DataFrame([{"yorug'lik": f"x{k}", "eng yaxshi ball": eng_yaxshi_ball(
    np.clip(gray.astype(np.float32) * k, 0, 255).astype(np.uint8), sh_gray)}
    for k in (0.4, 0.6, 0.8, 1.0, 1.3)]))

Uch jadval uch xil javob beradi:

Yorug'lik — muammo emas. Rasmni 0.4 barobar qorong'ilashtirsangiz ham ball 1.0 bo'lib qoladi. Sababi TM_CCOEFF_NORMED ning tuzilishi: u o'rtachani ayiradi va kattalikka bo'ladi, shuning uchun yorqinlikning bir tekis o'zgarishi natijaga umuman ta'sir qilmaydi.

O'lcham — jiddiy muammo. Atigi 5% farqda (x0.95 va x1.05) ball 1.0 dan 0.93 ga tushdi. x0.7 da 0.727, x1.2 da 0.807. Amalda 0.9 dan pastga tushgan ballga ishonib bo'lmaydi, demak 5% o'lcham farqi chegaraga olib keladi.

Burilish — eng jiddiy muammo. 5° da 0.897, 10° da 0.807, 20° da 0.683. Ya'ni yigirma daraja burilish mosliknni deyarli yo'q qiladi.

Demak shablon qidirish faqat obyekt aynan o'sha o'lchamda va o'sha burchakda bo'lganda ishlaydi.

Bu qanday ishlarda bo'ladi? Ekran avtomatlashtirish (tugma har doim bir xil), konveyer (kamera qotirilgan, detal bir xil), skanerlangan blank (logotip o'sha joyda), o'yin boti. Bular kam emas — shuning uchun usul hali ham keng ishlatiladi.

O'lcham muammosini qisman yechish mumkin: shablonni bir necha o'lchamda sinab ko'rish (image pyramid).

def piramida_qidir(katta_gray, shablon_gray, koeflar=np.arange(0.5, 1.55, 0.05)):
    """Shablonni turli o'lchamda sinaydi; eng yaxshi ball, joy va koeffitsiyentni qaytaradi."""
    eng = (-1.0, None, None)
    for k in koeflar:
        s = cv2.resize(shablon_gray, None, fx=k, fy=k, interpolation=cv2.INTER_AREA)
        if s.shape[0] > katta_gray.shape[0] or s.shape[1] > katta_gray.shape[1]:
            continue
        r = cv2.matchTemplate(katta_gray, s, cv2.TM_CCOEFF_NORMED)
        _, mx, _, mxl = cv2.minMaxLoc(r)
        if mx > eng[0]:
            eng = (round(float(mx), 3), mxl, round(float(k), 2))
    return eng

qatorlar = []
for koef in (0.7, 0.85, 1.0, 1.2, 1.5):
    o = cv2.resize(gray, None, fx=koef, fy=koef, interpolation=cv2.INTER_AREA)
    oddiy = eng_yaxshi_ball(o, sh_gray)
    ball, joy, topilgan_k = piramida_qidir(o, sh_gray)
    qatorlar.append({"rasm o'lchami": f"x{koef}", "oddiy qidiruv": oddiy, "piramida": ball,
                     "piramida topgan koef": topilgan_k})
show(pd.DataFrame(qatorlar))

Piramida ishladi: oddiy qidiruvda 0.727 va 0.807 bo'lgan hollarda ball 1.0 ga qaytdi. Bundan tashqari oxirgi ustunga qarang — topilgan koeffitsiyent rasm o'lchamiga aniq mos keldi (x0.7 → 0.7, x1.2 → 1.2, x1.5 → 1.5). Ya'ni piramida nafaqat topadi, balki obyekt qanchalik uzoqda ekanini ham aytadi.

Narxi bor: har koeffitsiyent uchun qidiruv qayta bajariladi, demak 21 koeffitsiyent — 21 barobar sekin. Va burilish muammosi baribir qoladi.

Eng xavfli xato: ball 1.0, lekin joy noto'g'ri

Endi shablonni boshqa joydan qirqamiz — yashil to'rtburchakning bir bo'lagini, ya'ni deyarli bir tekis sohani:

tekis_shablon = gray[60:200, 240:330]                    # yashil to'rtburchak + ostidagi fon
TEKIS_HAQIQAT = (240, 60)
r = cv2.matchTemplate(gray, tekis_shablon, cv2.TM_CCOEFF_NORMED)
_, mx, _, mxl = cv2.minMaxLoc(r)
xato = ((mxl[0] - TEKIS_HAQIQAT[0]) ** 2 + (mxl[1] - TEKIS_HAQIQAT[1]) ** 2) ** 0.5
print(f"ball: {mx:.4f} | topilgan joy: {mxl} | haqiqiy joy: {TEKIS_HAQIQAT} | xato: {xato:.0f} piksel")
print(f"ball 0.99 dan yuqori pozitsiyalar soni: {int((r > 0.99).sum())}")

th, tw = tekis_shablon.shape
tekis_belgi = rasm.copy()
cv2.rectangle(tekis_belgi, mxl, (mxl[0] + tw, mxl[1] + th), (0, 0, 255), 3)
cv2.rectangle(tekis_belgi, TEKIS_HAQIQAT, (TEKIS_HAQIQAT[0] + tw, TEKIS_HAQIQAT[1] + th), (0, 180, 0), 3)
ko_rsat(tekis_shablon, tekis_belgi, nom="tekis_shablon.png",
        sarlavhalar=["bir tekis shablon", "qizil — topilgan, yashil — haqiqiy"],
        izoh="Ball 1.0000, lekin joy noto'g'ri: bir tekis shablon bir necha joyga bir xil mos keladi.")

ball: 1.0000 | topilgan joy: (40, 110) | haqiqiy joy: (240, 60) | xato: 206 piksel
ball 0.99 dan yuqori pozitsiyalar soni: 74

Ball 1.0000, lekin joy noto'g'ri: bir tekis shablon bir necha joyga bir xil mos keladi.

Ball 1.0000 — mukammal. Joy esa noto'g'ri, katta to'rtburchak ustiga tushgan.

Sababi: bu shablonda ma'lumot yo'q. U "yuqorisi bir xil rang, pastki qismi boshqa bir xil rang" degan naqshdan iborat, xolos. TM_CCOEFF_NORMED o'rtachani ayirib, kattalikka bo'lgani uchun haqiqiy ranglar ahamiyatsiz bo'lib qoladi — katta to'rtburchakning cheti ham aynan shunday naqsh beradi. Kod buni sanab ham ko'rsatdi: balli 0.99 dan yuqori 74 ta pozitsiya bor. Algoritm shulardan eng yuqorisini tanladi, u esa bizga kerak bo'lgani emas.

:::gotcha Yuqori ball to'g'ri javob degani emas Shablon bir tekis bo'lsa yoki takrorlanuvchi naqsh (g'isht, panjara, katak) bo'lsa, ball yuqori chiqadi, lekin joy tasodifiy bo'ladi. Ikki himoya: (1) shablonda burchak va qiya chekka bo'lsin — bir tekis soha tanlamang; (2) ikkinchi eng yaxshi ballni ham tekshiring — agar u birinchisiga juda yaqin bo'lsa, javob ishonchsiz. :::

Burilishga ham chidaydigan, va "bu joy o'ziga xosmi?" degan savolni o'zi hal qiladigan usul kerak — kalit nuqtalar, keyingi bob.

Xulosa

Talaba ishi

1. hujjat.jpg dan bitta so'zni qirqib olib, uni hujjat_toza.png da qidiring. Ball qancha va nega? Perspektiva o'zgarishi shablon qidirishga qanday ta'sir qiladi?
2. Chegarani 0.7, 0.8, 0.9, 0.95 qilib, ko'p moslik topish kodini qayta ishga tushiring. Qaysi qiymatda soxta moslik paydo bo'ladi, qaysida haqiqiylari yo'qoladi?
3. piramida_qidir ga burilish ham qo'shing (har koeffitsiyent uchun 0°, 10°, 20°...). Necha barobar sekinlashdi? Bu yondashuv amalda maqbulmi?
4. Rangli shablon bilan (cv2.matchTemplate uch kanalli rasmni ham qabul qiladi) va kulrang bilan ballarni solishtiring. Rang qo'shimcha aniqlik berdimi?