Hlavolam I

... Petr Blahoš, 15. 10. 2018 ComputerVision Python

Zadání hlavolamu je takové: Na obrázku je bludiště. Začínáte uprostřed. Můžete jít kterýmkoliv směrem (i diagonálně), vždy o tolik, jaké je číslo na políčku, na kterém stojíte. Cílem je dostat se ven, na políčko těsně sousedící s hrací plochou.

Hlavolam

Obrázek jsem oskenoval z knihy a v Gimpu vyrovnal, upravil barvy a kontrast, a odstranil okolí. A teď potřebuji dostat čísla do pole.

Cílem není ukázat si přesný postup, jak zdigitalizovat jakýkoliv obrázek, ale pohrát si s tímto obrázkem, a zdigitalizovat jen jej.

Rozkouskování

Začneme běžným způsobem. Načteme obrázek, převedeme na odstíny šedi, trošku rozmázneme, a uděláme threshold, neboli odstranění/zčernání pixelů s nižší hodnotou než je práh (threshold), a převedení ostatních na bílou. Proč děláme to rozmáznutí? Abychom si ta čísla pěkně zakulatili. Schválně, zkuste si to bez rozmáznutí, uvidíte, jak budou některá čísla kostrbatá, nebo děravá.

import cv2
import numpy as np

img = cv2.imread("hlavolam.jpg")
gr = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
gr = cv2.blur(gr, (7, 7))
gr = cv2.threshold(gr, 190, 255, cv2.THRESH_BINARY_INV)[1]

cv2.imshow("1", gr)
cv2.waitKey(0)

Nerozmazané a rozmazané

Nebudeme moc zjišťovat, kde jsou hranice jednotlivých buňek. Obrázek jsem v Gimpu vyrovnal, takže věřím, že čáry jsou rovnoměrné, a vodorovné/svislé. Tak jen spočítáme, že celkově je to síť 21x21. Najdeme její vnější hranice.

(__im2, cnts, __hierarchy) = cv2.findContours(gr, cv2.RETR_EXTERNAL,
                                              cv2.CHAIN_APPROX_SIMPLE)
# get the biggest shape
cnts.sort(key=cv2.contourArea)
cnt = cnts[-1]
# draw the selected contour into the source image
# so that we can check what we found
cv2.drawContours(img, [cnt], -1, (0, 255, 255), 4)

# find the enclosing square
x, y, w, h = cv2.boundingRect(cnt)
# to check the boundary
cv2.rectangle(img, (x, y), (x + w, y + h), (0, 255, 0), 2)

cv2.imshow("1", img)
cv2.waitKey(0)

Tohle už je taková klasika. Najdeme kontury, z nich vybereme tu největší. Kdybychom věřili, že nám na obrázku nezůstal žádný šum ve formě pixelů ležících mimo síť s čísly, tak bychom nemuseli řadit a brát poslední/největší, prostě bychom vzali tu jedinou. Takhle je to ale bezpečnější. Teď si ještě nakreslíme celou síť, ať vidíme, že někde nejsme úplně mimo.

SZ = 21
w0 = w / SZ
h0 = h / SZ
for i in range(SZ):
    for j in range(SZ):
        cv2.rectangle(
            img,
            (int(x + i * w0 + 10), int(y + j * w0 + 10)),
            (int(x + i * w0 + w0 - 10), int(y + j * h0 + h0 - 10)),
            (255, 0, 0), 3,
        )
cv2.imshow("1", img)
cv2.waitKey(0)

Celkem to jde. Všimněte si, že rovnou zmenšujeme ty čtverečky o 10 z každé strany. Vypadá to ale, že někde to nestačí. Tak změnšíme trošku víc.

for i in range(SZ):
    for j in range(SZ):
        cv2.rectangle(
            img,
            (int(x + i * w0 + 10), int(y + j * w0 + 12)),
            (int(x + i * w0 + w0 - 14), int(y + j * h0 + h0 - 12)),
            (255, 0, 0), 3,
        )

Nalezení vzorů

Tak, a teď konečně začne ta skutečná práce. Počítač samozřejmě sám od sebe číslo nepozná. Musíme mu jej ukázat. Nejprve si napíšeme pomocnou funkci, která nám do zvolené buňky nakreslí číslo, a součadnice buňky. Tím pádem poznáme, zda jsme se při zaměřování čísel, která použijeme jako vzory, trefili. Funkci také využijeme později, až se budeme dívat na celkový výsledek.

def mark_square(img, x, y, x0, y0, w0, h0, text='X'):
    COLOR = 255
    if 3 == len(img.shape):
        COLOR = (0, 0, 255)
    cv2.putText(img, str(text),
                (int(x0 + x * w0 + 0.3 * w0), int(y0 + y * h0 + 0.7 * h0)),
                cv2.FONT_HERSHEY_SIMPLEX,
                1.4, COLOR, 2, cv2.LINE_AA)
    cv2.putText(img, "%s" % (x, ),
                (int(x0 + x * w0 + 3), int(y0 + y * h0 + 0.6 * h0)),
                cv2.FONT_HERSHEY_SIMPLEX,
                0.4, COLOR, 1, cv2.LINE_AA)
    cv2.putText(img, "%s" % (y, ),
                (int(x0 + x * w0 + 3), int(y0 + y * h0 + 0.8 * h0)),
                cv2.FONT_HERSHEY_SIMPLEX,
                0.4, COLOR, 1, cv2.LINE_AA)

Vybereme si pár kandidátů na naše vzory, a zvýrazníme si je, abychom viděli, jestli jsme zaměřili správně:

KNOWN_NUMBERS = [
    # number, x-coord, y-coord
    (1, 9, 2),
    (2, 9, 5),
    (3, 10, 1),
    (4, 10, 2),
    (5, 11, 2),
    (6, 13, 1),
    (7, 13, 2),
    (8, 9, 1),
    (9, 6, 3),
]
for (n, xx, yy) in KNOWN_NUMBERS:
    mark_square(img, xx, yy, x, y, w0, h0, n)

cv2.imshow("1", img)
cv2.waitKey(0)

Tak vidíme, že pro každé číslo jsme si našli jeden vzor. Teď si je musíme vytáhnout a schovat na později. Nejprve funkcičku, která nám vytáhne oříznutý obdélníček z buňky:

def extract_square(img, x, y, x0, y0, w0, h0):
    x_base = int(x0 + x * w0)
    y_base = int(y0 + y * h0)
    h0 = int(h0)
    w0 = int(w0)
    return img[y_base + 12:y_base + h0 - 12, x_base + 10:x_base + w0 - 14]

Jenže ten obrázek bude kdoví kde. Takže si jej ještě ořízneme tak, aby obsahoval opravdu jen to číslo - bez jakýchkoliv černých okrajů. To uděláme tak, že najdeme všechny kontury, a najdeme jejich maximální a minimální X a Y souřadnice. Vezmeme tento podobrázek, a znormalizujeme velikost. (To je vznešený název pro: Zvětšíme vždycky na stejnou velikost.) Musíme ale taky pamatovat na případ, kdy ve čtverečku není nic.

def find_fit_square(img, x, y, x0, y0, w0, h0):
    sub_img = extract_square(img, x, y, x0, y0, w0, h0)
    (__im2, cnts, __hierarchy) = cv2.findContours(sub_img, cv2.RETR_EXTERNAL,
                                                  cv2.CHAIN_APPROX_SIMPLE)
    if not cnts:
        return None
    min_x = min_y = 100000
    max_x = max_y = -100000
    for i in cnts:
        c = i.reshape((i.shape[0] * i.shape[-1]))
        min_x = min((min_x, min(c[0::2])))
        max_x = max((max_x, max(c[0::2])))
        min_y = min((min_y, min(c[1::2])))
        max_y = max((max_y, max(c[1::2])))

    sub_sub = sub_img[min_y:max_y, min_x:max_y]
    res = cv2.resize(sub_sub, (int(w0), int(h0)), interpolation=cv2.INTER_CUBIC)
    return res

Tak, a teď už si vytáhneme jednotlivé obrázky pro naše vzorová čísla.

TEMPLATES = []
for (n, xx, yy) in KNOWN_NUMBERS:
    TEMPLATES.append((n, find_fit_square(gr, xx, yy, x, y, w0, h0)))

Vlastní porovnání

Pro porovnání použijeme funkci cv2.matchTemplate. Máme výhodu, že všechna čísla jsou stejně velká. Přesně k tomu tato funkce je. matchTemplate hledá obrázek v obrázku. V naší situaci vlastně budeme zjišťovat, zda je obrázek tak nějak na souřadnicích [0, 0], takže bychom mohli nějak optimalizovat, ale proč se exponovat. Takže budeme procházet obrázek buňku po buňce. Každou buňku porovnáme s našimi vzory, a ten nejlepší prohlásíme za správný. Výsledek zakreslíme do obrázku, a ten nejen zobrazíme, ale i uložíme, protože práce s OpenCV okny není zrovna pohodlná.

OUTPUT_ARRAY = [[0]*SZ for i in range(SZ)]

for i in range(SZ):
    for j in range(SZ):
        sq = find_fit_square(gr, i, j, x, y, w0, h0)
        if sq is None:
            continue

        results = []
        for (number, templ) in TEMPLATES:
            result = cv2.matchTemplate(sq, templ, cv2.TM_CCOEFF)
            (_, score, _, _) = cv2.minMaxLoc(result)
            results.append((score, number))

        if results:
            results.sort()
            mark_square(img, i, j, x, y, w0, h0, results[-1][1])
            OUTPUT_ARRAY[j][i] = results[-1][1]

cv2.imwrite("output.jpg", img)
cv2.imshow("1", img)
cv2.waitKey(0)

Kousek výstupního obrázku:

První výstup

Ladění

Jak vidíte, ještě to není ono. Abychom si trochu vizualizovali, co vlastně porovnáme, napíšeme si funkci, která nám zobrazí detaily jednoho porovnání.

def visualize_search(img, TEMPLATES, x, y, w0, h0, xx, yy):
    out = np.zeros((300, 2000), dtype=np.uint8)
    sq = find_fit_square(img, xx, yy, x, y, w0, h0)

    X = 20
    results = []
    for (number, templ) in TEMPLATES:
        result = cv2.matchTemplate(sq, templ, cv2.TM_CCOEFF)
        out[20:20 + sq.shape[0], X:X + sq.shape[1]] = sq
        out[150:150 + templ.shape[0], X:X + templ.shape[1]] = templ
        (_, score, _, _) = cv2.minMaxLoc(result)
        results.append((score, number))
        X += sq.shape[1] + 5

    best = max([i[0] for i in results])
    X = 20
    for (val, num) in results:
        cv2.putText(out, "%0.2f" % (val / best, ),
                    (X, 120),
                    cv2.FONT_HERSHEY_SIMPLEX,
                    0.4, 255, 1, cv2.LINE_AA)
        X += sq.shape[1] + 5

    cv2.imshow("1", out)
    cv2.waitKey(0)

Když tuto funkci zavoláme s x a y souřadnicemi buňky, pro kterou chceme ladit hledání, dostaneme něco takového:

Ladění chybně detekovaného obrázku

Tedy informaci, že nejlepší výsledek dává 9. Zároveň vidíme, že čísla jsou děravá a kostrbatá, a sem tam se objeví tečka. Takže se vrátíme na začátek, a obrázek si hned po thresholdu zatáhneme pomocí morfologických transformací.

img = cv2.imread(fn)
gr = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
gr = cv2.threshold(gr, 190, 255, cv2.THRESH_BINARY_INV)[1]

kernel = np.ones((2, 2), dtype=np.uint8)
gr = cv2.morphologyEx(gr, cv2.MORPH_OPEN, kernel)
gr = cv2.morphologyEx(gr, cv2.MORPH_CLOSE, kernel)

(__im2, cnts, __hierarchy) = cv2.findContours(gr, cv2.RETR_EXTERNAL,
                                              cv2.CHAIN_APPROX_SIMPLE)

Dále přidáme tu špatně detekovanou jedničku mezi vzory:

KNOWN_NUMBERS = [
    # number, x-coord, y-coord
    (1, 9, 2), (1, 10, 16),
    (2, 9, 5),
    (3, 10, 1),
    (4, 10, 2),
    (5, 11, 2),
    (6, 13, 1),
    (7, 13, 2),
    (8, 9, 1),
    (9, 6, 3),
]

# ...

visualize_search(gr, TEMPLATES, x, y, w0, h0, 10, 16)

Teď už nám to detekuje správně jedničku, a na druhém místě je devítka.

Ladění chybně detekovaného obrázku

To by šlo, takže teď už jen budeme přidávat vzory. Naštěstí je ve výsledném obrázku docela dobře vidět, která čísla jsou ještě špatně. Můj finální seznam vzorů je:

KNOWN_NUMBERS = [
    # number, x-coord, y-coord
    (1, 9, 2), (1, 10, 16), (1, 14, 12),

    (2, 9, 5), (2, 2, 6), (2, 2, 7), (2, 12, 17), (2, 9, 15),

    (3, 10, 1), (3, 10, 11), (3, 10, 14), (3, 10, 18), (3, 18, 5),
    (3, 2, 4), (3, 16, 9),

    (4, 10, 2), (4, 1, 7), (4, 1, 8),

    (5, 11, 2), (5, 18, 9), (5, 1, 11), (5, 3, 16),
    (6, 13, 1), (6, 9, 16),

    (7, 13, 2), (7, 1, 10), (7, 3, 4), (7, 11, 0),

    (8, 9, 1), (8, 6, 4), (8, 20, 11), (8, 4, 6),

    (9, 6, 3), (9, 6, 12),
]

A výsledek:

Konečný výstup

Závěr

Tímto jsme získali OUTPUT_ARRAY s otiskem bludiště, se kterým budeme pracovat příště. Můžete namítnout, že by bylo rychlejší to prostě přepsat. Bylo. Ale to bychom se nic nenaučili.

Celý, ikdyž trochu upravený, prográmek najdete jako gist zde. Jen si k němu musíte stáhnout hlavolam.jpg.