概要
Q.41〜83では、エッジや領域を抽出し、形状・勾配・色・スケールなどを特徴として表します。 画像処理100本ノックの各問題を、前段の処理とのつながりが分かるようまとめました。
シリーズは次の4記事です。
Q.41〜46 CannyとHough変換
Q.41〜46では、Canny法で輪郭を抽出し、そのエッジ画像からHough変換で直線を検出します。 「画素の濃度変化」から「画像中の直線」へ処理を段階的に積み上げるアルゴリズムです。
Cannyエッジ検出
勾配強度と方向(Q.41)
ガウシアンフィルタでノイズを抑え、Sobelフィルタでx方向とy方向の勾配fx、fyを求めます。
const magnitude = Math.sqrt(fx * fx + fy * fy);
const angle = Math.atan2(fy, fx);
角度は0、45、90、135度の4方向へ量子化します。
非極大値抑制(Q.42)
勾配方向の前後にある画素と強度を比較し、局所最大でない値を0にします。これにより太い エッジ応答を1画素程度へ細くします。
ヒステリシス閾処理(Q.43)
強いエッジはそのまま残し、弱いエッジは強いエッジへ接続している場合だけ残します。 単一の閾値より、輪郭の途切れとノイズを両方抑えやすくなります。
Hough直線検出
Hough空間への投票(Q.44)
直線をρ = x cosθ + y sinθで表します。エッジ画素ごとに複数のθを試し、対応する
(ρ, θ)へ投票します。同じ直線上の画素はHough空間の同じ場所へ票を集めます。
Hough空間のNMS(Q.45)
投票数が多い場所の周囲を比較し、近傍より大きい極大値だけを残します。似たパラメータの 直線候補が大量に残ることを防ぎます。
画像上の直線へ戻す(Q.46)
上位の(ρ, θ)を直線の式へ戻し、画像の端点を計算してCanvasへ重ねて描画します。
処理のつながり
Hough変換へ元画像を直接渡すのではなく、Cannyで得た細いエッジ画像を入力にします。 平滑化、勾配、細線化、閾処理、投票、NMSという流れを追うと、各処理が次段の入力を 整える役割を持っていることが分かります。
Cannyで結果が変わる箇所
勾配方向は連続値ですが、非極大値抑制では周囲のどの2画素と比較するかを決めます。方向を 0・45・90・135度へ丸める簡易実装と、隣接画素を補間して比較する実装では細線化の精度が 変わります。
ヒステリシス閾値処理では、強いエッジから8近傍をたどり、弱いエッジのうち接続しているものだけを 残します。単純に2値化する処理ではありません。高い閾値と低い閾値の比率、ガウシアンの大きさを 固定して複数画像で比較すると調整しやすくなります。
Hough投票の実装
エッジ画素ごとにθを走査し、ρ = x cos θ + y sin θへ投票します。ρは負になるため、
画像対角長を加えて配列添字へ変換します。計算量はおおよそ
O(エッジ画素数 × θの分割数)です。
投票配列を画像として可視化すると、直線候補が交点として現れます。検出本数だけを見るよりも、 角度刻みが粗すぎないか、似た候補をNMSでまとめられているかをデバッグしやすくなります。
Q.47〜55 モルフォロジー処理
Q.47〜55では、画素の近傍関係から形を整えるモルフォロジー処理を実装します。二値画像の 膨張・収縮を基本として、ノイズ除去、穴埋め、境界や小領域の抽出へ発展させます。
基本となる膨張と収縮
| 問題 | 処理 | 結果 |
|---|---|---|
| Q.47 膨張 | 4近傍に前景があれば注目画素も前景にする | 白い領域が広がる |
| Q.48 収縮 | 4近傍に背景があれば注目画素も背景にする | 白い領域が縮む |
実装では入力と出力を別のバッファにします。同じバッファを読み書きすると、先に更新した画素が 後続画素の判定へ混ざり、1回の処理で必要以上に領域が変化するためです。
膨張と収縮を組み合わせる
| 問題 | 処理順 | 用途 |
|---|---|---|
| Q.49 オープニング | 収縮→膨張 | 大きな形を保ちながら小さな前景ノイズを消す |
| Q.50 クロージング | 膨張→収縮 | 前景内部の小さな穴や切れ目を埋める |
繰り返し回数を増やすほど除去・補完できる領域は大きくなりますが、残したい形も変わります。
差分から特徴を抽出する
| 問題 | 計算 | 抽出するもの |
|---|---|---|
| Q.51 モルフォロジー勾配 | 膨張−収縮 | 物体の境界 |
| Q.52 トップハット | 原画像−オープニング | 背景より明るい小領域 |
| Q.53 ブラックハット | クロージング−原画像 | 背景より暗い小領域 |
膨張・収縮の出力を最終結果にするだけでなく、原画像との差を取ることで、構造要素より小さい 特徴だけを取り出せます。
グレースケール画像への拡張(Q.54、Q.55)
二値画像では前景・背景の論理条件として説明できます。グレースケール画像では、膨張を近傍の 最大値、収縮を近傍の最小値として実装します。この定義を使えばトップハットと ブラックハットを濃淡画像へ適用できます。
構造要素をコードで表す
構造要素は「近傍のどの位置を見るか」を表す座標オフセットの配列にすると、十字、正方形、円形を 同じ走査コードで扱えます。構造要素が大きいほど太い線を残したり大きな穴を埋めたりできますが、 細部も失われます。
const cross = [
[0, -1],
[-1, 0],
[0, 0],
[1, 0],
[0, 1],
] as const;
二値画像では前景を0/1へ正規化してから論理条件を適用します。RGBAの255をそのまま足し合わせる
実装と混在させないことが重要です。グレースケールでは同じオフセットを使い、最大値・最小値を
選びます。
反復とバッファ管理
膨張や収縮を複数回適用するときは、各反復の入力を固定し、別バッファへ結果を書いてから交換します。 走査中に同じ配列を更新すると、左上から右下へ処理した場合だけ一方向へ領域が伸びる、といった 走査順依存の不具合が起きます。
オープニングやクロージングは同じ回数・同じ構造要素で構成し、入力、途中結果、最終結果を並べて 表示すると、ノイズ除去と形状変化の境界を確認できます。
Q.56〜60 テンプレートマッチングとラベリング
画像中から既知の小画像を探すテンプレートマッチング(Q.56〜59)と、二値画像を領域ごとに 分ける連結成分ラベリング(Q.60)を解説します。どちらも画像中を走査して対応関係を探しますが、 前者は画素値の類似度、後者は前景画素の接続を扱います。
テンプレートマッチング
入力画像上でテンプレートと同じ大きさの窓を移動し、各位置で評価値を計算します。
| 問題 | 評価値 | 選ぶ位置 | 性質 |
|---|---|---|---|
| Q.56 SSD | 差の二乗和 | 最小 | 大きな差へ強いペナルティを与える |
| Q.57 SAD | 差の絶対値和 | 最小 | 計算が単純 |
| Q.58 NCC | 正規化相互相関 | 最大 | 明るさの倍率変化に比較的強い |
| Q.59 ZNCC | 平均を引いた正規化相互相関 | 最大 | 明るさの加算変化にも強い |
for (let y = 0; y <= imageHeight - templateHeight; y++) {
for (let x = 0; x <= imageWidth - templateWidth; x++) {
const score = compareAt(x, y);
// 最良の位置と評価値を更新する
}
}
SSDとSADは元画像とテンプレートの明るさが変わると評価が悪化します。NCCはベクトルの長さで 正規化し、ZNCCはさらに平均値を引くことで、模様の対応へ注目します。
連結成分ラベリング(Q.60)
二値画像の前景画素を走査し、上下左右でつながる画素へ同じラベルを付けます。異なる仮ラベルが 同じ領域だと判明した場合は、同値関係を記録して後から統合します。
最終的なラベルを色へ変換すると、独立した領域を視覚的に確認できます。斜め方向も同じ領域として 扱う8近傍版は、後続の実装で扱います。
使い分け
テンプレートマッチングは「この見た目がどこにあるか」、ラベリングは「前景がいくつの領域に 分かれているか」を求めます。前者は対象の見本がある場合、後者は二値化後の物体数や面積を 調べる前処理として利用できます。
類似度指標を選ぶ
テンプレートと切り出し領域の画素差を比較する代表的な方法は次のとおりです。
| 指標 | 特徴 |
|---|---|
| SAD | 絶対差の和。軽量で外れ値の影響がSSDより小さい |
| SSD | 差の二乗和。大きな差を強く罰する |
| NCC | 内積を大きさで正規化し、全体の明るさの尺度差に比較的強い |
| ZNCC | 平均も引くため、明るさの加算変化にも強い |
NCC系では分母が0になる単色領域を処理する必要があります。また、テンプレートが入力画像より大きい 場合を先に拒否すると、走査範囲の負値や配列外参照を防げます。総当たりの計算量は探索位置数と テンプレート面積の積になるため、テンプレートを大きくすると急速に重くなります。
ラベリングを実装する2つの方法
幅優先探索・深さ優先探索では、未訪問の前景画素を見つけるたびに近傍をたどります。理解しやすい 一方、大きな領域ではキューのサイズに注意が必要です。2パス法では仮ラベルを付け、Union-Findで 同値なラベルを統合します。
4近傍と8近傍では斜めに接する画素を同一物体とみなすかが変わります。小さな対角線パターンを テスト画像にすると、意図した接続規則になっているかを確認できます。
Q.61〜65 連結数と細線化
Q.61〜65では二値図形のつながり方を数え、形を壊さずに輪郭画素を削る細線化へ進みます。 画素の値だけでなく、近傍画素の接続関係を扱うトポロジー寄りの処理です。
連結数(Q.61、Q.62)
注目画素の周囲8画素を順にたどり、背景から前景へ切り替わる回数を数えます。
| 連結数 | 局所形状の例 |
|---|---|
| 0 | 孤立点または内部 |
| 1 | 端点 |
| 2 | 通常の線 |
| 3以上 | 分岐点 |
Q.61は4連結、Q.62は8連結の考え方で周囲とのつながりを分類します。前景と背景のどちらを 4連結にするかで、斜めに接する画素の解釈が変わります。
基本的な細線化(Q.63)
細線化は、図形の連結性を保つ条件を満たす境界画素だけを削除し、変化がなくなるまで反復します。 すべての境界画素を同時に消すのではなく、削除候補を一度記録してからまとめて反映します。
Hilditch法(Q.64)
Hilditch法では、近傍の前景数、連結数、削除済み候補との関係など複数の条件を確認します。 線を短くしたり分断したりしない「単純点」だけを削除することが中心です。
Zhang-Suen法(Q.65)
Zhang-Suen法は削除方向の異なる2つのサブ反復を交互に行います。上下左右の特定の積が0になる 条件を入れ替えることで、一方向だけが偏って削られるのを防ぎます。
実装時の注意
反復処理には「削除された画素が0なら終了」という収束判定を入れます。また、走査中に入力を 書き換えないことが重要です。更新タイミングが変わると、同じアルゴリズムでも走査順に依存した 結果になります。
接続性を数える
細線化では、対象画素を削除しても前景のつながりが変わらないかを近傍パターンから判定します。 8近傍を円周順に並べ、背景から前景へ切り替わる回数を数えることで、端点、線上、分岐点を 区別できます。単に近傍の前景数だけで削除すると、線が途中で切れる可能性があります。
4近傍の前景と8近傍の背景を組み合わせるなど、前景・背景の接続規則を同時に考える必要があります。 細線化は「線を細くするフィルタ」というより、トポロジーを保ったまま削除可能な画素を反復して 取り除く処理です。
収束とテスト
各サブ反復では削除候補をマークするだけにし、全画素の判定後にまとめて削除します。削除数が0に なれば収束です。念のため最大反復回数も設けると、条件ミスによる無限ループを防げます。
1画素幅の線、2画素幅の線、輪、T字分岐を入力にし、線が消えないこと、輪が切れないこと、 分岐数が保たれることを確認すると実装の回帰テストになります。
Q.66〜69 HOG特徴量
Q.66〜69では、物体の輪郭や形状を表すHOG(Histogram of Oriented Gradients)特徴量を 4段階で実装します。後半の画像認識と物体検出でも再利用する重要な特徴量です。
勾配強度と角度(Q.66)
x方向とy方向の輝度差から勾配を求めます。
const magnitude = Math.sqrt(gx * gx + gy * gy);
const angle = (Math.atan2(gy, gx) * 180) / Math.PI;
向きの反転を同じ輪郭として扱うため角度を0〜180度へ収め、20度刻みの9方向へ量子化します。
セルごとの方向ヒストグラム(Q.67)
画像を8×8画素のセルに分けます。各画素の勾配強度を、その角度に対応するビンへ加算します。 これにより64画素の情報を「どの向きの輪郭がどれだけ強いか」という9次元の値へ要約します。
ブロック正規化(Q.68)
周囲3×3セルのヒストグラムを使ってL2正規化します。
normalized = value / sqrt(sum(value²) + ε)
局所的な明るさやコントラストが変わっても、輪郭方向の比率を比較しやすくなります。
特徴量を描画する(Q.69)
各セルの中心から、9方向のヒストグラム値に比例した長さの線を描きます。数値配列だけでは 分かりにくいHOGが、物体の輪郭に沿った線の集合として見えるようになります。
HOGが後続処理で果たす役割
RGB画素をそのまま学習器へ入れる代わりに、HOGで形状を表す特徴ベクトルへ変換します。 Q.96のニューラルネットワーク学習とQ.97以降のスライディングウィンドウでは、同じHOG実装を 使って顔らしさを判定します。
勾配をヒストグラムへ入れる
各画素でgxとgyを求め、強度m = sqrt(gx² + gy²)と方向
θ = atan2(gy, gx)へ変換します。明暗が反転しても同じ輪郭として扱うHOGでは、方向を
0〜180度へ正規化します。
方向を最も近いビンへ丸めるだけでなく、隣接する2ビンへ角度距離に応じて強度を分配すると、 ビン境界付近で特徴量が急変しにくくなります。セル境界についても周囲へ補間する実装があります。
ブロック正規化の実装
隣接セルをブロックとして連結し、L2正規化する例は次の式です。
v' = v / sqrt(Σv² + ε²)
εは一様領域で分母が0になることを防ぎます。ブロックを重ねながら走査するため、1つのセルが
複数回正規化される点がHOGの特徴です。セル数、方向ビン数、ブロックサイズから最終ベクトルの
次元数を計算し、配列長をテストすると走査漏れを見つけやすくなります。
セルを小さくすれば細かな形状を表せますが、次元数と計算量が増え、位置ずれにも敏感になります。 分類器まで含めて精度と処理時間を比較してパラメータを決めます。
Q.70〜72 HSVカラートラッキング
Q.70〜72では、HSVの色相を使って対象色を抽出し、二値マスクとして画像へ適用します。 最後にモルフォロジー処理でマスクのノイズと穴を整えます。
色相によるカラートラッキング(Q.70)
RGBをHSVへ変換し、青に対応する色相範囲の画素を255、それ以外を0にします。RGB値は明るさで 3成分とも変わりますが、HSVの色相は「何色か」を分離して扱えます。
const [h] = rgbToHsv(r, g, b);
mask[index] = lowerHue <= h && h <= upperHue ? 255 : 0;
色相は0度と360度が連続するため、赤のように境界をまたぐ色を抽出する場合は範囲判定を 2つに分ける必要があります。
マスクを画像へ適用する(Q.71)
マスクが前景の画素だけ元画像を残し、背景画素を0にします。RGB各成分へ同じマスク条件を 使うことで、対象色の領域だけを表示できます。
マスクを形態学的変換で整える(Q.72)
色の閾値だけでは、小さな孤立ノイズや前景内部の穴が残ります。クロージングで穴を埋め、 オープニングで孤立した前景を除去してから元画像へ適用します。
色相による二値化
↓
クロージング(穴を埋める)
↓
オープニング(孤立ノイズを消す)
↓
元画像へマスクを適用
RGBからHSVへの変換で注意する点
RGBを0〜1へ正規化し、最大値max、最小値min、差deltaを求めます。明度Vはmax、
彩度Sはmax === 0なら0、それ以外はdelta / maxです。色相Hは最大のチャンネルに
よって式を切り替え、最後に0〜360度へ正規化します。
無彩色ではdelta === 0となり、色相を計算できません。この場合はH = 0など一定値へします。
赤色は色相環の0度をまたぐため、「340度以上または20度未満」のようにOR条件で範囲を表します。
閾値を調整する手順
まず色相だけで候補を可視化し、次に彩度の下限で灰色や白い領域を除き、明度の範囲で暗部・反射を 調整します。いきなり3条件を同時に変えるより、各マスクと画素数を表示した方が原因を追いやすく なります。
照明条件が大きく変わる環境では固定閾値だけでは安定しません。色見本から範囲を推定する、 ホワイトバランスを補正する、連結成分の面積や形状も使う、といった次段の処理が必要です。
Q.73〜76 画像ピラミッドと顕著性マップ
Q.73〜76では、画像の縮小・拡大から複数スケールの表現を作り、スケール間の差を使って 高周波成分と顕著性マップを求めます。
縮小してから拡大する(Q.73)
画像を小さくして元のサイズへ戻すと、細かな情報が失われます。元画像と見比べることで、 解像度の低下が輪郭や模様へ与える影響を確認できます。
ピラミッド差分(Q.74)
元画像から縮小・拡大した画像を引くと、縮小時に失われた細部が残ります。これはローパス画像を 引いて高周波成分を取り出す処理と考えられます。
ガウシアンピラミッド(Q.75)
画像を段階的に縮小し、異なる解像度の画像群を作ります。同じ物体でも、近距離では大きく、 遠距離では小さく見えるため、複数スケールで特徴を調べる土台になります。
原画像 → 1/2 → 1/4 → 1/8 → 1/16
顕著性マップ(Q.76)
異なるスケールの画像を同じ大きさへ戻して差を取り、複数の組み合わせを加算します。 周囲と異なる構造が複数スケールで強調され、人の注意を引きやすい領域の候補になります。
空間フィルタとの関係
ガウシアンピラミッドの各段は、平滑化してから間引くことで作るのが基本です。平滑化せずに 縮小すると高周波成分が低周波へ折り返すエイリアシングが発生します。Q.9のガウシアン フィルタと画像補間が、ここではマルチスケール処理の部品として再登場します。
ピラミッドを実装する順序
各段は「ガウシアン平滑化 → 2画素ごとの間引き」で作ります。縮小後のサイズを
Math.floor(width / 2)とするのか切り上げるのかを統一し、奇数サイズの画像でも配列長が
一致するようにします。
元サイズへ戻すときは補間を使いますが、拡大しても失われた高周波が復元されるわけではありません。 元画像と拡大画像の差が細部を表すため、この差を段ごとに保存するのがラプラシアンピラミッドです。
顕著性マップを安定して合成する
異なる段の差を取る前に、幅と高さを完全に揃えます。1画素のずれでも画像全体に偽の輪郭が出ます。 各差分マップは値域が異なるため、個別に正規化してから加算するか、同じ尺度のまま重み付けするかを 明示します。
処理時間とメモリは、元画像に加えて各縮小画像と差分画像を保持するかで変わります。表示に不要な 中間結果は再利用できますが、学習時は各段を並べて可視化すると、エイリアシングや位置ずれを 見つけやすくなります。
Q.77〜80 ガボールフィルタ
Q.77〜80ではガボールフィルタを生成し、回転、畳み込み、方向別応答の合成までを実装します。 ガボールフィルタは方向と空間周波数の両方を選択でき、エッジやテクスチャの特徴抽出に使えます。
カーネルを生成する(Q.77)
ガウシアン窓と正弦波を掛け合わせてカーネルを作ります。σが応答する範囲、波長λが
対象とする模様の細かさ、角度θが方向を決めます。
G(x, y) = exp(-(x'² + γ²y'²) / 2σ²) cos(2πx' / λ + ψ)
生成後は係数の絶対値和などで正規化し、画像全体の明るさが過度に変わらないようにします。
方向を変える(Q.78)
座標を0、45、90、135度へ回転し、方向の異なる4種類のカーネルを描画します。角度ごとに 縞模様の向きが変わることを確認できます。
画像へ適用する(Q.79)
各方向のカーネルをグレースケール画像へ畳み込みます。特定方向の線や縞とカーネルが一致した 場所で大きな応答が得られます。
方向別応答を合成する(Q.80)
4方向の応答を画素ごとに加算し、向きに偏らない特徴画像を作ります。単一方向のエッジ検出から、 複数方向をまとめたテクスチャ表現へ発展させる処理です。
Sobelフィルタとの違い
Sobelは主に局所的な輝度勾配を求めます。ガボールフィルタは方向に加えて周波数も指定できるため、 一定間隔の縞や繰り返し模様へ選択的に反応できます。
カーネルの各パラメータ
ガボールカーネルは、向きθに合わせて座標を回転したx'、y'を使います。
x' = x cos θ + y sin θ
y' = -x sin θ + y cos θ
g(x, y) = exp(-(x'² + γ²y'²) / 2σ²) cos(2πx' / λ + ψ)
λは反応する縞の間隔、θは向き、σは観測範囲、γは楕円率、ψは波の位相です。
1つずつ変えたカーネル画像を表示すると、出力との対応を理解しやすくなります。
実装と正規化
カーネルサイズは通常σに対して十分大きい奇数にします。係数の平均を引いてDC成分を抑えると、
一様な明るさへの反応を減らせます。正・負の応答を表示するときは絶対値を取る方法と、128を0として
符号を残す方法で見え方が異なります。
方向と波長の組み合わせごとに畳み込みが必要なため、フィルタバンクは計算量が増えます。 同じカーネルを毎フレーム生成せずキャッシュし、必要な方向数と画像解像度を用途に合わせて絞ります。
Q.81〜83 Hessian・Harrisコーナー検出
Q.81〜83では、画像中の角や交点を特徴点として抽出します。Hessian法は二階微分、Harris法は 一次微分から作る構造テンソルを利用します。
Hessianによるコーナー検出(Q.81)
x方向・y方向の二階微分Ixx、Iyyと混合微分Ixyを求め、Hessian行列の行列式を
応答値とします。
det(H) = Ixx Iyy - Ixy²
応答が閾値を超え、近傍で局所最大となる画素をコーナーとして描画します。
Harris検出の構造テンソル(Q.82)
SobelフィルタからIx、Iyを求め、Ix²、Iy²、IxIyをガウシアンで平滑化します。
これらは局所領域でどの方向に輝度が変化しているかを表します。
Harris応答(Q.83)
構造テンソルMから次の応答を計算します。
R = det(M) - k trace(M)²
平坦領域では2方向とも変化が小さく、エッジでは一方向だけ、コーナーでは2方向とも変化が 大きくなります。大きな正の応答から局所最大点を選びます。
エッジ検出との違い
エッジは一方向の大きな変化でも反応します。コーナーはx・yの両方向に変化するため、画像の 位置合わせや追跡で再検出しやすい点として利用できます。
固有値で応答を理解する
構造テンソルの2つの固有値をλ1、λ2とすると、両方が小さい場所は平坦、片方だけ大きい場所は
エッジ、両方が大きい場所はコーナーです。Harris応答は固有値分解を直接行わず、行列式とトレースで
この性質を近似します。
Hessianの行列式は2階微分から得られ、明るい・暗い塊状構造への応答に使えます。微分はノイズを 増幅するため、どちらもガウシアン平滑化のスケールと微分カーネルの大きさが結果へ強く影響します。
コーナーを点として選ぶ
応答画像を閾値処理するだけでは、1つのコーナー周辺に多数の点が残ります。近傍で最大の応答だけを 残すNMSを行い、必要なら上位N点や最小距離を指定します。画像サイズが変わる場合は固定値ではなく、 最大応答に対する比率で閾値を決めると調整しやすくなります。
検証では画像を少し平行移動・回転し、同じ物理点が再検出されるかを確認します。単に点数が多い 検出器より、位置が安定し、点が画像全体へ適度に分散する設定がマッチングや追跡に向いています。
まとめ
Q.41〜83では、輪郭や領域を見つける処理から、形状・勾配・色・スケールを特徴として扱う処理へ進みます。 複数の特徴を組み合わせるQ.84以降の分類・検出は、次の記事で扱います。