スタンフォード/CS131/宿題3-1 ハリスコーナー検出器

Stanford University/CS131/宿題3-1をやる。今回の宿題は、ハリスコーナー検出器、RANSAC、HOG記述子をカバーしている。

スポンサーリンク

Introduction: Panorama Stitching

Panorama stitching is an early success of computer vision. Matthew Brown and David G. Lowe published a famous panoramic image stitching paper in 2007. Since then, automatic panorama stitching technology has been widely adopted in many applications such as Google Street View, panorama photos on smartphones, and stitching software such as Photosynth and AutoStitch.
パノラマステッチは、コンピュータビジョン早期の成功だ。マシュー・ブラウンとデイビッド・G・ロウは、2007年に有名なpanoramic image stitching paperを発表している。それ以降、自動パノラマステッチ技術は、グーグルストリートビュー、スマホのパノラマ写真、PhotosynthやAutoStitch等のステッチソフトなどの多くのアプリに適用されている。

In this assignment, we will detect and match keypoints from multiple images to build a single panoramic image. This will involve several tasks:
この課題では、複数の画像からキーポイントを検出・マッチさせて、単一のパノラマ画像を構築する。これにはいくつかの作業が関わる。

  1. Use Harris corner detector to find keypoints.
    キーポイント検出にハリスコーナー検出器を使用する。
  2. Build a descriptor to describe each point in an image.
    画像の各点を記述するための記述子を構築する。
    Compare two sets of descriptors coming from two different images and find matching keypoints.
    2画像の2記述子を比較して一致するキーポイントを検出する。
  3. Given a list of matching keypoints, use least-squares method to find the affine transformation matrix that maps points in one image to another.
    一致キーポイントのリストを所与とし、最小二乗法を用いて、1つの画像の点を別の画像へマッピングするアフィン変換行列を求める。
  4. Use RANSAC to give a more robust estimate of affine transformation matrix.
    RANSACを使ってアフィン変換行列のよりロバストな推定を与える。
    Given the transformation matrix, use it to transform the second image and overlay it on the first image, forming a panorama.
    変換行列を所与とし、それを用いて2番目の画像を変換して最初の画像にかぶせてパノラマ画像を作成する。
  5. Implement a different descriptor (HOG descriptor) and get another stitching result.
    別の記述子(HOG記述子)を実装して別のステッチ結果を得よ。

Part 1 Harris Corner Detector (20 points)

In this section, you are going to implement Harris corner detector for keypoint localization. Review the lecture slides on Harris corner detector to understand how it works. The Harris detection algorithm can be divide into the following steps:
このセクションでは、キーポイントローカライゼーション用のハリスコーナー検出器を実装する。講義スライドを見直してハリスコーナー検出器の仕組みを理解する。ハリス検出アルゴリズムは以下のステップに分けられる。

  1. Compute $x$ and $y$ derivatives ($I_x, I_y$) of an image
    画像の$x$と$y$微分係数($I_x, I_y$)を比較する。
  2. Compute products of derivatives ($I_x^2, I_y^2, I_{xy}$) at each pixel
    各画素の微分係数($I_x^2, I_y^2, I_{xy}$)の積を算出する。
  3. Compute matrix $M$ at each pixel, where
    以下のMの条件を満たす各画素の行列$M$を算出する。
    $$
    M = \sum_{x,y} w(x,y)
    \begin{bmatrix}
    I_{x}^2 & I_{x}I_{y} \\
    I_{x}I_{y} & I_{y}^2
    \end{bmatrix}
    $$
  4. Compute corner response $R=Det(M)-k(Trace(M)^2)$ at each pixel
    各画素のコーナー応答$R=Det(M)-k(Trace(M)^2)$を算出する。
  5. Output corner response map $R(x,y)$
    コーナー応答マップ$R(x,y)$を出力する。

Step 1 is already done for you in the function harris_corners in panorama.py. Complete the function implementation and run the code below.
panorama.pyのharris_corners関数のステップ1は飛ばして、関数実装を完了してから下のコードを実行せよ。

-Hint: You may use the function scipy.ndimage.filters.convolve, which is already imported in panoramy.py
ヒント:scipy.ndimage.filters.convolveが使えるかも知れない(このモジュールは既にインポート済み)。

import numpy as np
from skimage import filters
from skimage.feature import corner_peaks
from skimage.io import imread
import matplotlib.pyplot as plt
from time import time
from __future__ import print_function

%matplotlib inline
plt.rcParams['figure.figsize'] = (20.0, 14.0) # set default size of plots
plt.rcParams["font.size"] = "17"
plt.rcParams['image.interpolation'] = 'nearest'
plt.rcParams['image.cmap'] = 'gray'
# for auto-reloading extenrnal modules
#%load_ext autoreload
#%autoreload 2
import numpy as np
from scipy.ndimage.filters import convolve

def harris_corners(img, window_size=3, k=0.04):
    """
    Compute Harris corner response map. Follow the math equation
    R=Det(M)-k(Trace(M)^2).
    Hint:
        You may use the function scipy.ndimage.filters.convolve, 
        which is already imported above        
    Args:
        img: Grayscale image of shape (H, W)
        window_size: size of the window function
        k: sensitivity parameter
    Returns:
        response: Harris response image of shape (H, W)
    """
    H, W = img.shape
    window = np.ones((window_size, window_size))
    response = np.zeros((H, W))
    dx = filters.sobel_v(img)
    dy = filters.sobel_h(img)
    ### YOUR CODE HERE
    Ix2 = convolve(dx**2, window)
    Iy2 = convolve(dy**2, window)
    Ixy = convolve(dx*dy, window)
    for i in range(H):
        for j in range(W):
            M=np.array([[Ix2[i,j],Ixy[i,j]],[Ixy[i,j],Iy2[i,j]]])
            response[i,j]=np.linalg.det(M)-k*np.trace(M)**2
    ### END YOUR CODE
    return response
#from panorama import harris_corners

img = imread('sudoku.png', as_gray=True)

# Compute Harris corner response
response = harris_corners(img)

# Display corner response
plt.subplot(1,2,1)
plt.imshow(response)
plt.axis('off')
plt.title('Harris Corner Response')

plt.subplot(1,2,2)
plt.imshow(imread('solution_harris.png', as_gray=True))
plt.axis('off')
plt.title('Harris Corner Solution')
plt.show()

Once you implement the Harris detector correctly, you will be able to see small bright blobs around the corners of the sudoku grids and letters in the output corner response image. The function corner_peaks from skimage.feature performs non-maximum suppression to take local maxima of the response map and localize keypoints.
ハリス検出器を正しく実装したら、出力のコーナー応答画像の数独グリッドと文字のコーナー周囲に微小な明るい斑点を見ることができる。skimage.featureの関数corner_peaksは、非最大抑制を実行し、レスポンスマップの極大値を取得してキーポイントをローカライズする。

# Perform non-maximum suppression in response map
# and output corner coordiantes
corners = corner_peaks(response, threshold_rel=0.01)

# Display detected corners
plt.imshow(img)
plt.scatter(corners[:,1], corners[:,0], marker='x')
plt.axis('off')
plt.title('Detected Corners')
plt.show()