Hlavolam I
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.
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)
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:
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:
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.
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:
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.
Komentáře byly zrušeny
V EU teď máme složitou situaci s Cookies. Na komentáře jsem používal jistou službu třetí strany. Ta však používá Cookies poměrně, ehm, benevolentně. Tak jsem se rozhodl komentáře zrušit. Pokud chcete, můžete mi napsat přímo