Canny Edgeを改善してみたいと思って調べた時のメモ。Canny Edgeが何をやってるか知るにはいろいろ解説見るよりソースコード見たほうが速いだろと思ってOpenCVの実装を見てみた。
OpenCV3になってからかなりいろんなCPU,GPUの最適化が入っているのでコードとしてはすごく読みにくくなっている(1000行を超えている)。なので少し昔のバージョンのコードが良い(250行程度)。
https://github.com/opencv/opencv/blob/ff2af7d8bb822d47743429a994cc16b02b55f625/modules/imgproc/src/canny.cpp
その他、CannyEdgeが何をやろうとしているかの解説は、英語の動画だけど
https://www.youtube.com/watch?v=sRFM5IEqR2w
が分かりやすかったので余裕がある人は事前に見てみると良いと思う。
CannyEdgeの優れている特徴2つ
- どんな解像度の画像でもエッジを太さ1pxの線分として取り出す
- 2つの閾値でノイズとなるようなエッジを減らすことができる
Sobelフィルタ周りの技術
Canny EdgeはSobelフィルタの結果をインプットにして、エッジ検出された画像を出力する
SobelフィルタはX方向とY方向があるのでそれぞれGx,Gyとした時、
- エッジの強さ =
sqrt(Gx^2 + Gy^2) - エッジの方向 =
arctan(Gx / Gy)
で分かる。
エッジの中でもピークの点を見つける技術
(画像は最初に紹介した動画から)
エッジの方向が斜めとわかっていれば青を見ている時に黄色と赤のどちらよりも大きいかを調べれば良い
コード中に以下のような部分がある
/* sector numbers
(Top-Left Origin)
1 2 3
* * *
* * *
0*******0
* * *
* * *
3 2 1
*/
このようにエッジの方向が上下左右斜めの8方向のどれなのか判断したいというのがある。
これは先程のエッジの方向の式、arctan(Gx / Gy)で求められ、例えば右方向は-22.5度から22.5度まで、右上は22.5度から67.5度までとすればいいことが分かる。
これがコード中のよくわからないマジックナンバーを含むコードtg22xやtg67xのもととなる部分。実際は、arctanを計算するのではなくGxとGyの比を計算することで計算効率を上げている。(ちなみにコード上では、値を2^15倍してdoubleじゃなくintの比較で行うことでさらに効率化している。)この時以下の事実を使っている
tan(22.5度) = sqrt(2)-1 = 0.4142135623730950488016887242097
tan(67.5度) = sqrt(2)+1 = 2.4142135623730950488016887242097 = tan(22.5度)+2
実際のコードの部分
const int TG22 = (int)(0.4142135623730950488016887242097*(1<<CANNY_SHIFT) + 0.5);
int m = _mag[j];
if (m > low)
{
int xs = _x[j];
int ys = _y[j];
int x = std::abs(xs);
int y = std::abs(ys) << CANNY_SHIFT;
int tg22x = x * TG22;
if (y < tg22x)
{
if (m > _mag[j-1] && m >= _mag[j+1]) goto __ocv_canny_push;
}
else
{
int tg67x = tg22x + (x << (CANNY_SHIFT+1));
if (y > tg67x)
{
if (m > _mag[j+magstep2] && m >= _mag[j+magstep1]) goto __ocv_canny_push;
}
else
{
int s = (xs ^ ys) < 0 ? -1 : 1;
if (m > _mag[j+magstep2-s] && m > _mag[j+magstep1+s]) goto __ocv_canny_push;
}
}
}
pixelの場合分け
// calculate magnitude and angle of gradient, perform non-maxima supression.
// fill the map with one of the following values:
// 0 - the pixel might belong to an edge
// 1 - the pixel can not belong to an edge
// 2 - the pixel does belong to an edge
画像を走査する際、各pixelを以下の3パターンに分けている
- 2: 確実にエッジなpixel
- 1: 確実にエッジでないpixel
- 0: エッジかも知れないpixel
これは以下のような判断基準で付いている
- pixelの勾配値(エッジの強さ L2:
sqrt(Gx^2 + Gy^2)or L1:|Gx|+|Gy|)がhigh_thresholdを超えていれば、確実にエッジなpixel(2)にする - low_thresholdをを下回っていれば、確実にエッジでないpixel(1)にする
- thresholdの中間点がエッジかもしれないpixel(0)と判断される
- あるpixelの勾配値がhigh_thresholdを超えていても、x方向、y方向それぞれで1つ前のpixelが確実にEdgeのpixel(2)と判定されていれば、Edgeかもしれないpixel(0)と判断される
この後、0に判定されたものは2と判定したものと隣接していればエッジと判断される。
その他メモ
- map, mとかの配列は画像の2次元配列を1次元にして持っている
- e.g. map[i+1]だとx軸方向に+1, map[i+magstep]だとy方向に+1ということ
- Canny Edgeはもともとgray scaleの1チャネルの画像に対してかけるものだが、このコードはRGBなどの3チャネルにも対応していてこの場合、各ピクセルで3つの値の中で最大の勾配値を出した物を使うコードになっている