ラドン変換を用いた回転対応テンプレートマッチングの実装

## はじめに

本記事はOpenCVアドベントカレンダー14日目の記事です．

https://qiita.com/advent-calendar/2024/opencv

もともとはロボットの位置認識で以下のようなラドン変換を活用する論文を見かけて、試しに真似て実装を試みていたのですが、途中で「これテンプレートマッチングにも使えそう」と思って路線変更してテンプレートマッチングを実装した次第です。同じ画像をアフィン変換で回転と平行移動させただけの画像であれば簡単に実装できましたが、他の画素値が影響するテンプレートマッチングではなかなか難しかったです。

https://ieeexplore.ieee.org/document/9981308

今回作成したプログラムは以下のGitHubに公開されています。参考になれば幸いです。

https://github.com/hijimasa/radon-template-matching

## ラドン変換とは

ラドン変換とは、1917年に数学者のRadonによって発見された変換式で、医療のCTスキャンに応用されています。
CTスキャンを例に説明すると、ある角度$\theta$だけ傾いた撮像面に対して垂直なX線を照射したとき、ある点$x'$で撮像面に当たるX線の強度$F(x')$は、物体のX線吸収係数分布$f(x,y)$を撮像面からの距離で積分した値として求めることができます。このX線の強度$F(x')$をすべての角度$\theta$において求めることで撮像面でのX線の強度分布$F(x',\theta)$を得られます。このとき、$f(x,y)$から$F(x',\theta)$への変換をラドン変換といい、逆方向の変換を逆ラドン変換といいます。CTスキャンではこの逆ラドン変換を用いて物体内部の状態を取得するわけです。画像処理では、積分の代わりに画素値の総和を用いて表現します。

![Screenshot from 2024-12-13 22-42-44.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3326389/25ad73b6-4dd2-93cf-7958-6b7acda1a0fc.png)


## ラドン変換でテンプレートマッチングする流れ

ラドン変換でテンプレートマッチングする手順を以下に示します。

```mermaid
flowchart TD
    start1([開始])
    node1[テンプレート画像と<br>対象画像をラドン変換]
    node2[変換後の画像の各行（各角度）についてフーリエ変換]
    node3[フーリエ変換後の画像をマッチング]
    node4[得られた傾きに基づいて<br>対象ラドン変換画像の0度<br>および90度の成分を<br>マッチング]
    data1[/マッチングした位置<br>=テンプレートの傾き/]
    data2[/0度成分のマッチング位置<br>=x方向の平行移動量/]
    data3[/90度成分のマッチング位置<br>=y方向の平行移動量/]
    end1([終了])
    start1 --> node1 --> node2 --> node3
    node4 --> end1
    node3 ---> data1
    node2 --> node4
    data1 -->node4
    node4 --> data2
    node4 --> data3
    data2 ~~~ end1
    data3 ~~~ end1
```

具体的には、ラドン変換後の画像を各傾きにおいてフーリエ変換することで振幅成分が平行移動量によらずマッチング可能な特徴として扱えるようになることを利用しています。
これによって、フーリエ変換後の画像をマッチングすることで対象画像に対するテンプレートの傾きを容易に推定することが可能になります。
あとは、求めたテンプレートの傾きに応じてテンプレートを傾けて通常のテンプレートマッチングをしても良かったのですが、せっかくなので対象画像の0度および90度成分のマッチング結果がそれぞれx,y方向の移動量に対応しているという性質を利用することにしました。

実行例を以下に示します。
![result.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3326389/8470e3cf-26fe-02c5-94c5-1a5b0a88e471.png)


## 実装のポイント

以下に今回のテンプレートマッチングの実装のポイントを解説していきます。

### フーリエ変換時の窓関数の利用

ラドン変換後の画像をフーリエ変換する際に、そのままフーリエ変換してしまうと画像の幅に対してフーリエ変換後の周波数が整数倍ではない場合に、両端の波形が不連続となり意図しない高周波成分を生成してしまうことがあります。そのため、ラドン変換後の画像にフーリエ変換する際には適当な窓関数を適用する必要があるそうです。今回はラドン変換前のテンプレート画像および対象画像の双方に大きなガウス窓関数を適用することで、改善を図っています。

### フーリエ変換後の画像のマッチング方法について

フーリエ変換後のマッチングについてはOpenCVがデフォルトで用意しているSSD(Sum of Squared Difference)や正規化相互相関(NCC:Normalized Cross-Correlation)ではうまくいかなかったので、SAD(Sum of Absolute Difference)を使用することにしました。

以下の記事にあるように、SADは一部の異常な値を許容できるそうなので、テンプレートと対象画像の違いを許容するように作用したのではないかと考えられます。

https://qiita.com/pachi-dragon/items/394b26b1621de92bfd98

### ラドン変換から平行移動量を求めるマッチング方法

本テンプレートマッチングを行う上で一番の鬼門であり、最もよくわかっていない部分です。
まず対象画像の0度または90度に対応する行を取得し、テンプレート画像のラドン変換後画像の対応する角度の行を取得します。
テンプレートマッチングの要領でテンプレート画像の行のサイズ分だけ対象画像の行を取り出し、平均値の比を使用してデータの大まかな大きさを調整します。
その後、調整後の対象画像の行の一部とテンプレート画像の行をそれぞれの平均値で差分を取ります。得られた対象画像の行の差分とテンプレート画像の行の差分の差の標準偏差を対象画像の行の一部とテンプレート画像の乖離度として、最小値を見つけるようにマッチングを行います。

試行錯誤の末に見つけた条件なので定量的な評価はできていないですが、テンプレート画像に対して対応する対象画像の領域の外側が与える影響をうまく避けてマッチングできている気がします。

## おわりに

今回はラドン変換を用いたテンプレートマッチングの実装について説明しました。
フーリエ変換後の画像のマッチングにSADを使用するところまではうまく説明できそうですが、その後のラドン変換後の画像のマッチングについてはもう少し考察が必要だと感じました。
また、窓関数の利用に関してはラドン変換後の画像に対して行えば処理をもっと早くできると思うので、そのうち改善すると思います。
画像処理に関して知見のある方はぜひ回転対応可能なテンプレートマッチングであるラドン変換によるテンプレートマッチングに挑戦してみてはいかがでしょうか。