Harrisコーナー検出

目的

本章では、

• Harrisコーナー検出の背後にある概念を理解する。
• 次の関数について見ていく。 cv.cornerHarris(), cv.cornerSubPix()

理論

前章では、コーナーが画像中であらゆる方向に輝度の大きな変化を持つ領域であることを見た。これらのコーナーを見つける初期の試みの一つは、Chris Harris & Mike Stephens によって1988年の論文 A Combined Corner and Edge Detector で行われた。そのため、現在ではHarrisコーナー検出器と呼ばれている。彼はこの単純なアイデアを数学的な形にまとめた。基本的には、あらゆる方向への変位 \((u,v)\) に対する輝度の差を求める。これは次のように表される。

\[E(u,v) = \sum_{x,y} \underbrace{w(x,y)}_\text{window function} \, [\underbrace{I(x+u,y+v)}_\text{shifted intensity}-\underbrace{I(x,y)}_\text{intensity}]^2\]

窓関数は、矩形窓か、または下にあるピクセルに重みを与えるガウス窓のいずれかである。

コーナー検出のためには、この関数 \(E(u,v)\) を最大化しなければならない。つまり、第2項を最大化しなければならない。上式にテイラー展開を適用し、いくつかの数学的手順を経ると（完全な導出については、お好みの標準的な教科書を参照のこと）、最終的に次の式が得られる。

\[E(u,v) \approx \begin{bmatrix} u & v \end{bmatrix} M \begin{bmatrix} u \\ v \end{bmatrix}\]

ここで

\[M = \sum_{x,y} w(x,y) \begin{bmatrix}I_x I_x & I_x I_y \\ I_x I_y & I_y I_y \end{bmatrix}\]

ここで、\(I_x\) と \(I_y\) はそれぞれx方向およびy方向の画像微分である。（これらは cv.Sobel() を使えば簡単に求められる。）

次に主要な部分に入る。この後、彼らはスコア、すなわち窓がコーナーを含むかどうかを判定する式を作成した。

\[R = \det(M) - k(\operatorname{trace}(M))^2\]

ここで

• \(\det(M) = \lambda_1 \lambda_2\)
• \(\operatorname{trace}(M) = \lambda_1 + \lambda_2\)
• \(\lambda_1\) と \(\lambda_2\) は \(M\) の固有値である

したがって、これらの固有値の大きさによって、ある領域がコーナーかエッジか平坦かが決まる。

• \(|R|\) が小さいとき、これは \(\lambda_1\) と \(\lambda_2\) がともに小さいときに起こり、その領域は平坦である。
• \(R<0\) のとき、これは \(\lambda_1 >> \lambda_2\) またはその逆のときに起こり、その領域はエッジである。
• \(R\) が大きいとき、これは \(\lambda_1\) と \(\lambda_2\) がともに大きく、かつ \(\lambda_1 \sim \lambda_2\) のときに起こり、その領域はコーナーである。

これは次のように分かりやすい図で表せる。

image

したがって、Harrisコーナー検出の結果は、これらのスコアを持つグレースケール画像となる。適切なスコアでしきい値処理を行うと、画像中のコーナーが得られる。これを単純な画像で実行してみよう。

OpenCVにおけるHarrisコーナー検出器

OpenCVにはこの目的のための関数 cv.cornerHarris() がある。その引数は次のとおり。

• img - 入力画像。グレースケールかつfloat32型でなければならない。
• blockSize - コーナー検出で考慮する近傍のサイズ
• ksize - 使用するSobel微分のアパーチャパラメータ。
• k - 式中のHarris検出器の自由パラメータ。

以下の例を参照のこと。

import numpy as np
import cv2 as cv
 
filename = 'chessboard.png'
img = cv.imread(filename)
gray = cv.cvtColor(img,cv.COLOR_BGR2GRAY)
 
gray = np.float32(gray)
dst = cv.cornerHarris(gray,2,3,0.04)
 
#result is dilated for marking the corners, not important
dst = cv.dilate(dst,None)
 
# Threshold for an optimal value, it may vary depending on the image.
img[dst>0.01*dst.max()]=[0,0,255]
 
cv.imshow('dst',img)
if cv.waitKey(0) & 0xff == 27:
 cv.destroyAllWindows()

以下に3つの結果を示す。

image

サブピクセル精度のコーナー

ときには、最大限の精度でコーナーを求める必要がある。OpenCVには、検出したコーナーをサブピクセル精度でさらに高精度化する関数 cv.cornerSubPix() が用意されている。以下に例を示す。いつものように、まずHarrisコーナーを求める必要がある。次に、これらのコーナーの重心（1つのコーナーに複数のピクセルが集まっていることがあるので、その重心を取る）を渡して高精度化する。Harrisコーナーは赤いピクセルで、高精度化したコーナーは緑のピクセルで示す。この関数では、反復をいつ停止するかの基準を定義する必要がある。指定した反復回数に達するか、一定の精度に達するか、いずれか早い方で停止する。また、コーナーを探索する近傍のサイズも定義する必要がある。

import numpy as np
import cv2 as cv
 
filename = 'chessboard2.jpg'
img = cv.imread(filename)
gray = cv.cvtColor(img,cv.COLOR_BGR2GRAY)
 
# find Harris corners
gray = np.float32(gray)
dst = cv.cornerHarris(gray,2,3,0.04)
dst = cv.dilate(dst,None)
ret, dst = cv.threshold(dst,0.01*dst.max(),255,0)
dst = np.uint8(dst)
 
# find centroids
ret, labels, stats, centroids = cv.connectedComponentsWithStats(dst)
 
# define the criteria to stop and refine the corners
criteria = (cv.TERM_CRITERIA_EPS + cv.TERM_CRITERIA_MAX_ITER, 100, 0.001)
corners = cv.cornerSubPix(gray,np.float32(centroids),(5,5),(-1,-1),criteria)
 
# Now draw them
res = np.hstack((centroids,corners))
res = np.int0(res)
img[res[:,1],res[:,0]]=[0,0,255]
img[res[:,3],res[:,2]] = [0,255,0]
 
cv.imwrite('subpixel5.png',img)

以下が結果であり、いくつかの重要な位置をズームしたウィンドウで可視化して示している。

image

追加リソース

練習問題