Harrisコーナー検出

目的

このチュートリアルでは

  • We Harrisのコーナー検出の背景にある概念を理解します.
  • 以下の関数の使い方を学びます: cv2.cornerHarris(), cv2.cornerSubPix()

理論

前チュートリアルでコーナーとは全方向に対して画素値の大きな変化が観測される領域であることを学びました.初期のComputer Visionにおけるコーナー検出の試みとして Chris Harris と Mike StephensA Combined Corner and Edge Detector という論文で提案したHarrisのコーナー検出と呼ばれる方法があります.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) を最大化します.具体的には,上式第二項の最大化を意味します.上式に対してTaylor展開を適用し幾つかの数学処理(詳細を知りたければHarrisのコーナー検出について解説している一般的な本を参照してください)を行うと,最終的に以下のような式が得られます:

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

Mは以下のように定義される

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_xI_y はそれぞれ画像のx方向とy方向の勾配を表す( cv2.Sobel() を使えば簡単に計算できます).

ようやくメインの処理になります.上記の処理の後,スコアを計算し,探索ウィンドウ内にコーナーを含むか否かを決定します.

R = det(M) - k(trace(M))^2

ここで
  • det(M) = \lambda_1 \lambda_2
  • trace(M) = \lambda_1 + \lambda_2
  • \lambda_1\lambda_2 はMの固有値(eigen values)

つまり,これらの固有値によって対象領域がコーナー,エッジ,平坦な領域のどれかを判断します.

  • |R| が小さい時,すなわち \lambda_1\lambda_2 の両方の値が小さい時,この領域は平坦な領域である.
  • R<0 の時,すなわち \lambda_1 >> \lambda_2 もしくはその逆である時,この領域はエッジである.
  • R が大きい時,すなわち \lambda_1\lambda_2 の両方の値が大きい時,この領域はコーナーである.

上記の関係は以下の図でうまく示されています:

Classification of Image Points

Harrisのコーナー検出を適用した結果は各画素が上記のスコア( R )を表すグレースケール画像になります.適切な閾値処理を施すと,画像中のコーナーを検出できます.単純な画像を使って試してみましょう.

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

OpenCVは cv2.cornerHarris() という関数を提供しています.引数は:

  • img - 入力画像.グレースケール画像もしくはfloat32型のデータ.
  • blockSize - コーナー検出の際に考慮する隣接領域のサイズ.
  • ksize - Sobelの勾配オペレータのカーネルサイズ.
  • k - 式中のフリーパラメータ.

以下に例を示します:

import cv2
import numpy as np

filename = 'chessboard.jpg'
img = cv2.imread(filename)
gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)

gray = np.float32(gray)
dst = cv2.cornerHarris(gray,2,3,0.04)

#result is dilated for marking the corners, not important
dst = cv2.dilate(dst,None)

# Threshold for an optimal value, it may vary depending on the image.
img[dst>0.01*dst.max()]=[0,0,255]

cv2.imshow('dst',img)
if cv2.waitKey(0) & 0xff == 27:
    cv2.destroyAllWindows()

結果画像を以下に示します:

Harris Corner Detection

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

コーナー検出の精度を可能な限り上げたいと思う事があるかもしれません.OpenCVには cv2.cornerSubPix() という,検出したコーナーの精度をサブピクセル精度まで改善する関数があります.まず初めにHarrisのコーナー検出を適用します.次に,検出したコーナーの中心座標(一つのコーナーに複数の画素がある可能性があるため,その中心座標を与えます)を与えて,検出精度を向上します.Harrisのコーナー検出器で検出されたコーナーを赤く,refinementで改善されたコーナーを緑色で示しています.この関数を使うためにはrefinementの繰り返し計算の終了条件を定義する必要があります.繰り返し計算の最大回数や達成精度などが終了条件に挙げられます.また,コーナー検出に使う隣接領域のサイズも定義する必要があります.

import cv2
import numpy as np

filename = 'chessboard2.jpg'
img = cv2.imread(filename)
gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)

# find Harris corners
gray = np.float32(gray)
dst = cv2.cornerHarris(gray,2,3,0.04)
dst = cv2.dilate(dst,None)
ret, dst = cv2.threshold(dst,0.01*dst.max(),255,0)
dst = np.uint8(dst)

# find centroids
ret, labels, stats, centroids = cv2.connectedComponentsWithStats(dst)

# define the criteria to stop and refine the corners
criteria = (cv2.TERM_CRITERIA_EPS + cv2.TERM_CRITERIA_MAX_ITER, 100, 0.001)
corners = cv2.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]

cv2.imwrite('subpixel5.png',img)

結果を以下に示します.幾つか重要な場所を拡大して表示してあります:

Corner Detection with SubPixel Accuracy

補足資料

課題