回転に強い画像からの文字検索（テンプレートマッチング、AKAZE特徴量）

国立国会図書館デジタルコレクションには著作権の切れた大量の書籍が置かれている。

以前から調査で凄くお世話になっているサイトだ。

ERROR: The request could not be satisfied

しかし画像データのため、文字検索が使えない。

また古い文献をデジタル化しているため、

旧字体が利用されている
汚れや書き込みがそのまま含まれている

と、OCRを使っても文字抽出の精度は期待できなかった。

「でも、知りたいのは『指定の文字』が含まれているかどうかなんだよなー」

と、同じように悩んでいる人は多いと思う。

テンプレートマッチングの問題
回転を考慮したテンプレートマッチング
1. テンプレートマッチングの結果
AKAZE特徴マッチングを試してみる
1. 特徴点検出
2. 特徴点の対応付け
まとめ
1. ソースコード
  1. テンプレートマッチングのソースコード
  2. AKAZE特徴量のソースコード

前回、前々回と「大日本文書」「陰徳太平記」から画像処理により該当文字を抜き出した。

古文書に先祖の名前が存在するかの調査（大日本古文書編）

今回のあらすじ。陰徳太平記ではなく、大日本文書（毛利、吉川、小早川など）でやると可能性が広がるかもしれません。（また知らない書物…）ありがたき情報！すぐやってみ...

「大日本文書」を眺めてみると、「陰徳太平記」と比べて文字の大きさが揃っていなかった。

また文字の90度回転などが存在した。

そこで、ロバストな文字画像検索について追加検討してみた。

テンプレートマッチングの問題

テンプレートマッチングは使い古された手法だ。

考え方は、対象画像とテンプレート画像を比較し、テンプレート画像をスライドさせて、もっともよくマッチする場所を探すというもの。

大学時代の研究テーマの1つだったが、テンプレートマッチングは、アルゴリズムの特性上、いくつかの問題がある。

外界からのノイズに弱い（画像毎に光源が異なる）
画像の回転・拡大に弱い（ピクセル単位で比較のため）

今回の対象を見ると、ノイズは無いものの回転・拡大が存在している。

近年はどのような試みで対処しているのだろうか？

【ノイズ】明るさやコントラストに影響されない手法（NCC）

たとえば正規化相互相関（NCC：Normalized Cross Correlation）という手法は明るさやコントラストに影響されない。

NCC(Normalized Cross Correlation)では、分子の部分で輝度値の内積を計算する。分母の数値は分子の数値を正規化するための数値。

$\rm NCC = \frac{\displaystyle \sum_{y} \sum_{x} A(x,y) B(x,y)} {\displaystyle \sqrt{\sum_{y} \sum_{x} A(x,y)^2 \sum_{y} \sum_{x} B(x,y)^2}}$

ここで、画像上の2つのブロックを $A,B$ とし、ブロックの各画素の輝度値を $A(x,y), B(x,y)$ と置く。 $x,y$ はブロック内の画素の位置を表す。

こんな手法は私が学生時代から使い古し済だ。

他にも色々あるけど、文書内検索は輝度の影響が低いので結局SSDが一番良いと思ってる。

手法	特徴
SAD（Sum of Absolute Difference）	画素値の差の絶対値の和でスコアを求める
SSD（Sum of Squared Difference）	画素値の差の2乗の和でスコアを求める
NCC（Normalized Cross Correlation）	正規化相互相関。明るさやコントラストに影響されない
ISC（Increment Sign Correlation）	増分符号相関。部分的に起こる大きなノイズや遮蔽に強い
SRF（Statistical Reach Feature）	統計的リーチ特徴法。照明変動、遮蔽、撮影時のノイズに強い

【回転・拡大】特徴量を用いる手法（Haar Like、AKAZE）

特徴量といえば顔検出のHaar Likeが真っ先にあがる。

Haar Likeでは明度差、HOGでは輝度の勾配方向を使って表現する。

次の動画ではHaar Like特徴量による顔検出の検出過程が見られる。

OpenCV Face Detection: Visualized from Adam Harvey on Vimeo.

他にはHOGで人体検出や、SIFTやSURFなど。最近のOpenCVではAKAZEが実装された。

【回転・拡大】機械学習を用いる手法（R-CNN）

拡大に対してロバストにするため、R-CNNなどの機械学習を使う手法も存在する。

が、今回の目的のためには入力データや計算量も増えて扱い辛い。

回転を考慮したテンプレートマッチング

前々回のテンプレートマッチング手法を複数対応するように変更した。

更に、OpenCVで90度ずつ回転させるように変更を行った。

# テンプレート画像をグレースケールで読み込む
img_rotate_0 = cv2.imread(tem_img[i], 0)
# 回転対応
img_rotate_180 = cv2.rotate(img_rotate_0, cv2.ROTATE_180)
img_rotate_90_clockwise = cv2.rotate(img_rotate_0, cv2.ROTATE_90_CLOCKWISE)
img_rotate_90_counterclockwise = cv2.rotate(img_rotate_0, cv2.ROTATE_90_COUNTERCLOCKWISE)

# テンプレート画像をグレースケールで読み込む

img_rotate_0 = cv2.imread(tem_img[i], 0)

# 回転対応

img_rotate_180 = cv2.rotate(img_rotate_0, cv2.ROTATE_180)

img_rotate_90_clockwise = cv2.rotate(img_rotate_0, cv2.ROTATE_90_CLOCKWISE)

img_rotate_90_counterclockwise = cv2.rotate(img_rotate_0, cv2.ROTATE_90_COUNTERCLOCKWISE)

なお「房」の字のように簡単にテンプレートにする文字を文書から発見できない場合は、自分でテンプレートを作って徐々に高精細な画像に差し替えていく。

テンプレートマッチングの結果

凄く地味だが1分近くのビデオを撮影した。

大日本古文書に対するテンプレートマッチングの一例

分かりにくいが「保」を「促」と間違えている例は幾つかある。

でも、このような形で眺めていくと高速に古文書の中から該当の文字が書かれているか判断できる。

はい、おしまい。

……。

ん？

そう言えば「角川日本地名大辞典（旧地名編）」に書かれていた人物名がヒットしないんだよねぇ……

実装誤りは無いと思うけど……。

1ページずつ目視で確認するか……。

見つけた！

斜め45度ーーーーーーー！

テンプレートマッチング泣かせの

まさかの傘連判状

角川日本地名大辞典はどうやってチェックしたんだろうか……

プロの検索能力に叶わず……。

AKAZE特徴マッチングを試してみる

OpenCV3では、特許で保護されている次の2つがcontribライブラリに移動になった。

SIFT (Scale-invariant feature transform)
SURF (Speed-Upped Robust Feature)

そして代わりにライセンス的に利用しやすい KAZE、A-KAZE がcoreライブラリに含まれている。

AKAZEはSIFTをベースに開発され、検出対象のオブジェクトのスケールの異なる画像や回転している画像同士からのマッチングが可能。

早速試してみよう！

特徴点検出

大学時代の研究テーマの一つだったが、社会人になって使ったことは無かった。

20年ぶり……。

import cv2

# 画像表示
def imshow(img):
    cv2.namedWindow("Result", cv2.WINDOW_NORMAL)
    cv2.imshow('Result', img) 
    cv2.waitKey(0) 
    cv2.destroyAllWindows()

# img1の読み出し
img1 = cv2.imread('yasu_nippon.png') 
# img1をグレースケールで読み出し
gray1 = cv2.cvtColor(img1,cv2.COLOR_BGR2GRAY) 

akaze = cv2.AKAZE_create()
kp1, des1 = akaze.detectAndCompute(gray1, None)

img_akaze = cv2.drawKeypoints(img1, kp1, img1, flags=cv2.DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS)
cv2.imwrite('match.png', img_akaze)
imshow(img_akaze)

import cv2

# 画像表示

def imshow(img):

cv2.namedWindow("Result", cv2.WINDOW_NORMAL)

cv2.imshow('Result', img)

cv2.waitKey(0)

cv2.destroyAllWindows()

# img1の読み出し

img1 = cv2.imread('yasu_nippon.png')

# img1をグレースケールで読み出し

gray1 = cv2.cvtColor(img1,cv2.COLOR_BGR2GRAY)

akaze = cv2.AKAZE_create()

kp1, des1 = akaze.detectAndCompute(gray1, None)

img_akaze = cv2.drawKeypoints(img1, kp1, img1, flags=cv2.DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS)

cv2.imwrite('match.png', img_akaze)

imshow(img_akaze)

で、結果。

何だこりゃ？こんな数＆場所だけの特徴点じゃ全然足りないでしょ……。

理由は、SIFTは周囲の8ピクセルとの値を比較をして極値を求めているので、検出される特徴点の数が入力される画像の拡大縮小に影響されるためだ。

だったら、拡大してみる。

# 拡大
ex_temp = 2
img1 = cv2.resize(img1, None, interpolation=cv2.INTER_LINEAR, fx = ex_temp, fy = ex_temp)

# 拡大

ex_temp = 2

img1 = cv2.resize(img1, None, interpolation=cv2.INTER_LINEAR, fx = ex_temp, fy = ex_temp)

お！改善した。

でも、今度は特徴点が画像中央に集中していて文字の端から特徴量が検出されて無いのが目立つ。

理由は画像に平滑化フィルタ処理（smoothing）を行う際に、画像の端は処理が行えないからだろう。

周囲に何も文字が存在しない参照画像を書籍から取り出して、再度実行してみた。

うん、良いね。

特徴点の対応付け

あ～～～嫌な言葉だ……大学時代の研究を思い出す。

研究は3年間「形状復元」をやってきましたが・・・

February 26, 2005本題こっち。HTTP_USER_AGENT　などに残っている上記のロボット検索エンジンのボットは、次の通りです。Googlebot（グーグルボット）Yah...

正直楽しくなかった。いや会社員も楽しくないな……。もう何もしたくない。

コードは次のようになる。

# BFMatcherオブジェクトの生成
bf = cv2.BFMatcher(cv2.NORM_HAMMING, crossCheck=True)
# Match descriptorsを生成
matches = bf.match(des1, des2)
# matchesをdescriptorsのdistance順(似ている順)にsortする 
matches = sorted(matches, key = lambda x:x.distance)

# img3に検出結果(最初の60点)を描画
img3 = cv2.drawMatches(img1, kp1, img2, kp2, matches[:60], None, flags = cv2.DrawMatchesFlags_NOT_DRAW_SINGLE_POINTS)
cv2.imwrite('match.png',img3)

# 画像表示
imshow(img3)

# BFMatcherオブジェクトの生成

bf = cv2.BFMatcher(cv2.NORM_HAMMING, crossCheck=True)

# Match descriptorsを生成

matches = bf.match(des1, des2)

# matchesをdescriptorsのdistance順(似ている順)にsortする

matches = sorted(matches, key = lambda x:x.distance)

# img3に検出結果(最初の60点)を描画

img3 = cv2.drawMatches(img1, kp1, img2, kp2, matches[:60], None, flags = cv2.DrawMatchesFlags_NOT_DRAW_SINGLE_POINTS)

cv2.imwrite('match.png',img3)

# 画像表示

imshow(img3)

そして結果を見ると、動作はしているっぽい。

計算時間は5秒程度。うーん長い。

では、メイン結果

文字の大きさが違う場合！

文字の大きさが違う＆回転がある場合！

糞じゃねーか！かすりもしてねーよ。

ここから「K近傍法」とかを使って正しい結果を抽出しようとしている記事は沢山見つかるけど、そもそも一本も繋がってないじゃん！

まとめ

特徴点マッチングが予想以上に使い物にならなかった……。

世の中では

「AKAZE特徴量マンセー」

的な記事が多いので、小生の技術力不足の問題なのか……。

ソースコード

画像処理を求めている人にとってはショボいけど、デジタル文書の文字検索を求めている人には有効だろう

テンプレートマッチングのソースコード

import cv2
import sys
import numpy as np
import functools
print = functools.partial(print, flush=True)

def match_template(img, img_gray, template, thr_img, color):
    # テンプレート画像の幅、高さを取得
    width, height = template.shape[::-1]
    
    # テンプレートマッチングの実行(比較方法cv2.TM_CCORR_NORMED)
    result = cv2.matchTemplate(img_gray, template, cv2.TM_CCORR_NORMED)

    # 検出結果から検出領域の位置を取得
    loc = np.where(result >= thr_img)
    for top_left in zip(*loc[::-1]):
        bottom_right = (top_left[0] + width, top_left[1] + height)
        cv2.rectangle(img, top_left, bottom_right, color, 4)
    
    # 類似度が最小,最大となる画素の類似度、位置を調べ代入する
    min_val, max_val, min_loc, max_loc = cv2.minMaxLoc(result)
    return img, max_val

# 色がテンプレート毎に変わる
A_COLOR = [(0,0,255),(255,0,0),(128,0,128),
           (0,128,0),(128,128,0),(51,102,255),
           (51,102,255),(51,102,255)]

# メインルーチン
if __name__ == "__main__":
    num = sys.argv[1]
    dir = sys.argv[2]
    img = cv2.imread(dir + "/" + num + ".jpg") # 画像を読み込む

    # 可変長のテンプレート対応
    tem_img = [] 
    thr_img = []
    for i in range(3, len(sys.argv), 2):
        tem_img.append(sys.argv[i])
        # 類似度の設定(0~1)
        thr_img.append(float(sys.argv[i + 1]))

    # 画像をグレースケールで読み込む
    img_gray = cv2.imread(dir + "/" + num + ".jpg",0)
    max_val = 0
    for i in range(len(tem_img)):
#        print(str(i) + " : " + str(tem_img[i]))

        # テンプレート画像をグレースケールで読み込む
        img_rotate_0 = cv2.imread(tem_img[i], 0)
        # 回転対応
        img_rotate_180 = cv2.rotate(img_rotate_0, cv2.ROTATE_180)
        img_rotate_90_clockwise = cv2.rotate(img_rotate_0, cv2.ROTATE_90_CLOCKWISE)
        img_rotate_90_counterclockwise = cv2.rotate(img_rotate_0, cv2.ROTATE_90_COUNTERCLOCKWISE)
        for tem in [img_rotate_0, img_rotate_180, img_rotate_90_clockwise, img_rotate_90_counterclockwise]:
            img, val = match_template(img, img_gray, tem, thr_img[i], A_COLOR[i])
            if (val > max_val):
               max_val = val
    # 最も似ている領域の類似度を表示
    print(num + " ," + str(max_val))
    if (max_val >= min(thr_img)):
       cv2.imwrite("out/" + dir + "_" + num + "_1.jpg", img)

import cv2

import sys

import numpy as np

import functools

print = functools.partial(print, flush=True)

def match_template(img, img_gray, template, thr_img, color):

# テンプレート画像の幅、高さを取得

width, height = template.shape[::-1]

# テンプレートマッチングの実行(比較方法cv2.TM_CCORR_NORMED)

result = cv2.matchTemplate(img_gray, template, cv2.TM_CCORR_NORMED)

# 検出結果から検出領域の位置を取得

loc = np.where(result >= thr_img)

for top_left in zip(*loc[::-1]):

bottom_right = (top_left[0] + width, top_left[1] + height)

cv2.rectangle(img, top_left, bottom_right, color, 4)

# 類似度が最小,最大となる画素の類似度、位置を調べ代入する

min_val, max_val, min_loc, max_loc = cv2.minMaxLoc(result)

return img, max_val

# 色がテンプレート毎に変わる

A_COLOR = [(0,0,255),(255,0,0),(128,0,128),

(0,128,0),(128,128,0),(51,102,255),

(51,102,255),(51,102,255)]

# メインルーチン

if __name__ == "__main__":

num = sys.argv[1]

dir = sys.argv[2]

img = cv2.imread(dir + "/" + num + ".jpg") # 画像を読み込む

# 可変長のテンプレート対応

tem_img = []

thr_img = []

for i in range(3, len(sys.argv), 2):

tem_img.append(sys.argv[i])

# 類似度の設定(0~1)

thr_img.append(float(sys.argv[i + 1]))

# 画像をグレースケールで読み込む

img_gray = cv2.imread(dir + "/" + num + ".jpg",0)

max_val = 0

for i in range(len(tem_img)):

# print(str(i) + " : " + str(tem_img[i]))

# テンプレート画像をグレースケールで読み込む

img_rotate_0 = cv2.imread(tem_img[i], 0)

# 回転対応

img_rotate_180 = cv2.rotate(img_rotate_0, cv2.ROTATE_180)

img_rotate_90_clockwise = cv2.rotate(img_rotate_0, cv2.ROTATE_90_CLOCKWISE)

img_rotate_90_counterclockwise = cv2.rotate(img_rotate_0, cv2.ROTATE_90_COUNTERCLOCKWISE)

for tem in [img_rotate_0, img_rotate_180, img_rotate_90_clockwise, img_rotate_90_counterclockwise]:

img, val = match_template(img, img_gray, tem, thr_img[i], A_COLOR[i])

if (val > max_val):

max_val = val

# 最も似ている領域の類似度を表示

print(num + " ," + str(max_val))

if (max_val >= min(thr_img)):

cv2.imwrite("out/" + dir + "_" + num + "_1.jpg", img)

利用方法は下記のようなコマンドとなる。

#!/bin/bash

dir="nippon"
for file in `\find $dir -maxdepth 1 -type f -printf '%f\n' | sed 's/\.[^\.]*$//' | sort -n`; do
    python ssd_multi.py $file $dir "ho_nippon.png" 0.98 "yasu_nippon.png" 0.98 "ho_mini_nippon.png" 0.98 "yasu_mini_nippon.png" 0.98 "bou_nippon.png" 0.985
done

#!/bin/bash

dir="nippon"

for file in `\find $dir -maxdepth 1 -type f -printf '%f\n' | sed 's/\.[^\.]*$//' | sort -n`; do

python ssd_multi.py $file $dir "ho_nippon.png" 0.98 "yasu_nippon.png" 0.98 "ho_mini_nippon.png" 0.98 "yasu_mini_nippon.png" 0.98 "bou_nippon.png" 0.985

done

AKAZE特徴量のソースコード

import cv2
import time
import functools
print = functools.partial(print, flush=True)

# 画像表示
def imshow(img):
    cv2.namedWindow("Result", cv2.WINDOW_NORMAL)
    cv2.imshow('Result', img) 
    cv2.waitKey(0) 
    cv2.destroyAllWindows()

# 特徴点検出器
def detector(name):
    if (name == "AgastFeature"):
        detector = cv2.AgastFeatureDetector_create()
    elif (name == "FAST"):
        detector = cv2.FastFeatureDetector_create()
    elif (name == "MSER"):
        detector = cv2.MSER_create()
    elif (name == "AKAZE"):
        detector = cv2.AKAZE_create()
    elif (name == "BRISK"):
        detector = cv2.BRISK_create()
    elif (name == "KAZE"):
        detector = cv2.KAZE_create()
    elif (name == "ORB"):
        detector = cv2.ORB_create()
    else:
        detector = cv2.SimpleBlobDetector_create()
    return detector

# img1の読み出し
img1 = cv2.imread('yasu_akaze.png') 
# img2の読み出し
#img2 = cv2.imread('n8_2/49.jpg') 
#img2 = cv2.imread('n8_2/51.jpg') 
img2 = cv2.imread('n8_1/124.jpg') 
#img2 = cv2.imread('n9_1/143.jpg') 

# 拡大
ex_temp = 2
img1 = cv2.resize(img1, None, interpolation=cv2.INTER_LINEAR, fx = ex_temp, fy = ex_temp)

# img1をグレースケールで読み出し
gray1 = cv2.cvtColor(img1,cv2.COLOR_BGR2GRAY) 
# img2をグレースケールで読み出し
gray2 = cv2.cvtColor(img2,cv2.COLOR_BGR2GRAY) 

start = time.time()

akaze = detector("AKAZE")
# kp1 = akaze.detect(gray1, None)
# kp2 = akaze.detect(gray2, None)
# ORB、GFTT、AKAZE、KAZE、BRISK、SIFTは特徴点だけではなく特徴量も計算
kp1, des1 = akaze.detectAndCompute(gray1, None)
kp2, des2 = akaze.detectAndCompute(gray2, None)

t = time.time() - start

print(t)

if (False):
   img_akaze = cv2.drawKeypoints(img1, kp1, img1, flags=cv2.DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS)
   cv2.imwrite('match.png', img_akaze)
   imshow(img_akaze)
else:
   # BFMatcherオブジェクトの生成
   bf = cv2.BFMatcher(cv2.NORM_HAMMING, crossCheck=True)
   # Match descriptorsを生成
   matches = bf.match(des1, des2)
   # matchesをdescriptorsのdistance順(似ている順)にsortする 
   matches = sorted(matches, key = lambda x:x.distance)

   # img3に検出結果(最初の10点)を描画
   img3 = cv2.drawMatches(img1, kp1, img2, kp2, matches[:60], None, flags = cv2.DrawMatchesFlags_NOT_DRAW_SINGLE_POINTS)
   cv2.imwrite('match.png',img3)

   #画像表示
   imshow(img3)

import cv2

import time

import functools

print = functools.partial(print, flush=True)

# 画像表示

def imshow(img):

cv2.namedWindow("Result", cv2.WINDOW_NORMAL)

cv2.imshow('Result', img)

cv2.waitKey(0)

cv2.destroyAllWindows()

# 特徴点検出器

def detector(name):

if (name == "AgastFeature"):

detector = cv2.AgastFeatureDetector_create()

elif (name == "FAST"):

detector = cv2.FastFeatureDetector_create()

elif (name == "MSER"):

detector = cv2.MSER_create()

elif (name == "AKAZE"):

detector = cv2.AKAZE_create()

elif (name == "BRISK"):

detector = cv2.BRISK_create()

elif (name == "KAZE"):

detector = cv2.KAZE_create()

elif (name == "ORB"):

detector = cv2.ORB_create()

else:

detector = cv2.SimpleBlobDetector_create()

return detector

# img1の読み出し

img1 = cv2.imread('yasu_akaze.png')

# img2の読み出し

#img2 = cv2.imread('n8_2/49.jpg')

#img2 = cv2.imread('n8_2/51.jpg')

img2 = cv2.imread('n8_1/124.jpg')

#img2 = cv2.imread('n9_1/143.jpg')

# 拡大

ex_temp = 2

img1 = cv2.resize(img1, None, interpolation=cv2.INTER_LINEAR, fx = ex_temp, fy = ex_temp)

# img1をグレースケールで読み出し

gray1 = cv2.cvtColor(img1,cv2.COLOR_BGR2GRAY)

# img2をグレースケールで読み出し

gray2 = cv2.cvtColor(img2,cv2.COLOR_BGR2GRAY)

start = time.time()

akaze = detector("AKAZE")

# kp1 = akaze.detect(gray1, None)

# kp2 = akaze.detect(gray2, None)

# ORB、GFTT、AKAZE、KAZE、BRISK、SIFTは特徴点だけではなく特徴量も計算

kp1, des1 = akaze.detectAndCompute(gray1, None)

kp2, des2 = akaze.detectAndCompute(gray2, None)

t = time.time() - start

print(t)

if (False):

img_akaze = cv2.drawKeypoints(img1, kp1, img1, flags=cv2.DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS)

cv2.imwrite('match.png', img_akaze)

imshow(img_akaze)

else:

# BFMatcherオブジェクトの生成

bf = cv2.BFMatcher(cv2.NORM_HAMMING, crossCheck=True)

# Match descriptorsを生成

matches = bf.match(des1, des2)

# matchesをdescriptorsのdistance順(似ている順)にsortする

matches = sorted(matches, key = lambda x:x.distance)

# img3に検出結果(最初の10点)を描画

img3 = cv2.drawMatches(img1, kp1, img2, kp2, matches[:60], None, flags = cv2.DrawMatchesFlags_NOT_DRAW_SINGLE_POINTS)

cv2.imwrite('match.png',img3)

#画像表示

imshow(img3)