連結数と細線化アルゴリズムをTypeScriptで実装する【画像処理100本ノック】

目次

1. 概要
2. 連結数q61q62
3. 基本的な細線化q63
4. hilditch法q64
5. zhang-suen法q65
6. 実装時の注意

概要

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になる 条件を入れ替えることで、一方向だけが偏って削られるのを防ぎます。

• Q.61〜65のデモ
• Ans061.ts〜Ans065.ts

実装時の注意

反復処理には「削除された画素が0なら終了」という収束判定を入れます。また、走査中に入力を 書き換えないことが重要です。更新タイミングが変わると、同じアルゴリズムでも走査順に依存した 結果になります。