〈一般研究課題〉

生活用携帯情報機器のための高速距離変換 VLSI の実現に関する研究

助 成 研 究 者

中京大学

磯直行

生活用携帯情報機器のための高速距離変換VLSIの実現に関する研究
磯 直行（中京大学）

Implementation of Fast Distance Transform VLSIfor Mobile Terminals
Naoyuki Iso(Chukyo University)

Abstract:
The Euclidean distance transform is applied in various fields of image processing, such as patternrecognition and morphological filter. In this paper, we propose a hardware algorithm using a systolic
array that performs Euclidean distance transform. It is designed for mobile terminals so that hardware
resources, such as multipliers and comparators, are reduced and processing speed is efficient. It
performs Euclidean distance transform for an input of N × N binary image in 3N− 1 clocks, and the2size of the required hardware resources is O(N ). And, this algorithm was tried to implement in a field
programmable gate array (FPGA).

1. はじめに
距離変換は，2 値画像の各画素について，それに最も近い 0 画素との距離を求める処理である．
距離変換はコンピュータビジョン，パターン認識，モルフォロジフィルタ及びロボット工学などの分野で応用されている．これまでにユークリッド距離(L 2 )をはじめ，シティブロック距離(L 1 )，チェスボード距離(L ∞ )，八角形距離などに対する距離変換アルゴリズムが提案されている．[1]では，
2

ユークリッド距離変換に関して N × N の 2 値画像に対する O(N logN )時間のアルゴリズムを提案し− 101 −

2ている．その後，[2]〜[4]で計算時間が O(N )に改良された．特に[3]では，ユークリッド距離をはじめとする様々な距離定義に対しても有効な距離変換アルゴリズムを提案している．
一方，距離変換アルゴリズムのハードウェア化に関する研究も行なわれている．特に，ロボットビジョンなどの画像処理の応用分野ではリアルタイム処理が求められており，距離変換アルゴリズ
ムのハードウェア化は処理の高速化のためには必要不可欠なものである．例えば，[5]では並列アルゴリズムを用いたアーキテクチャを使用しているが，多くのハードウェア資源を消費してしまう．
ハードウェア資源を消費することは回路規模が大きくなることであり，従って消費電力が大きくなることを意味する．そのため，携帯端末やロボットのような電池で動作する機器で行う処理では，ハードウェア資源をできるだけ削減する工夫が必要である．[6]で提案されたハードウェアアルゴ
リズムでは，ハードウェア資源を節約する工夫をしているが，ワークメモリに対してランダムなアクセスを行なうために実際に必要とするハードウェア量は膨大である．
本論文は，シストリックアレイを用いた距離変換アルゴリズムに注目する．シストリックアレイ
は，H.T. Kung が[7]で提案した VLSI アルゴリズムアーキテクチャである．シストリックアレイは，単純な計算能力を持つセルが規則的に配置され，各セルで与えられたクロックごとに計算および隣接セルとの間でデータ交換を行なう．データの入出力は逐次的に行なわれ，処理は並列かつパイプライン的に動作する．シストリックアレイの利点は，データ交換が局所的にのみ行なわれるので遠距離配線による信号伝播遅延の影響が少ないこと，単純なセルの規則的な配列で構成されるため設計及びデバッグが容易であること，パイプライン処理，並列処理が効果的に適用できることである．
本論文では，[3]のアルゴリズムに基づいたシストリックアレイによるハードウェアアルゴリズ
ムを VLSI として実現することを目標とする． [3]のアルゴリズムの構成は，列ごとのスキャン(T1)と，行ごとのスキャン(T2)の 2 つの単純なステップからなり，ハードウェア化するには非常に扱いやすい．また，[3]のアルゴリズムでは N × N の入力画像に対して， N 個の 2 次関数の下側包絡線を求めるために 2 次関数同士の交点を求めている．しかし，この処理を効率良く実行するハードウェアを実現するのは難しい．そこで本論文は，シストリックアレイを用いることにより，2 次関数同士の交点を計算することなく下側包絡線を求めることにより高速化する．また，列ごとのスキャン(T1)では通常 2 回のスキャンが必要であるが，本論文では 1 回のスキャンで処理が終わるようにさらに高速化する．この結果，本論文で提案するアルゴリズムは N × N の 2 値画像の距離変換をクロ2ック数 3N − 1 で行い，O(N )のハードウェア資源を消費する．そして，本論文で提案したアルゴリズムの実用性を確かめるため，ソフトウェア的に内部回路を書き換え可能なハードウェアとしてFPGA(Field Programmable Gate Array)上に実現することを試みる．
本論文の構成について述べる．2 章では距離変換の定義とユークリッド距離変換について述べる．
3 章で提案するハードウェアアルゴリズムについて述べる．4 章で動作速度と回路サイズ，およびFPGAによる試作について述べる．5 章でまとめる．

2. 定義

B ={b i, j }(b i, j ∈{0,1})をサイズ N × N の 2 値画像とし，(i, j )を 2 値画像の i 行 j 列の要素とする．
B={bi, j }に対するユークリッド距離変換 D={di, j }は次式で与えられる．

− 102 −

ユークリッド距離変換を行なう[3]のアルゴリズムは列のスキャン(T1)と行のスキャン(T2)の 2 つのステップで構成される．以下，T1と T2 の処理についてそれぞれ説明する．
2.1 列のスキャン（T1）T1 では2 値画像 B={bi, j }の各列における距離変換 G ={gi, j }を計算する．すなわち，各列 j に対して，を計算する．ただし，列 j の要素がすべて 1 であるときは，gi, j = ∞(0eieN − 1)とする．
2.2 行のスキャン（T2）T2 では T1 で計算された G={gi, j }からユークリッド距離変換 D={di, j }を計算する．画素(i, j )から k
列内の最も近い 0 値の画素との距離は，で与えられる．よって，画素(i, j )の距離値 di, j を求めるためには，i 行内の gi, j(0ekeN− 1)をスキャンし，を計算すればよい．
計算を簡単にするため，本論文ではユークリッド距離の 2 乗を求めることにする．つまり，
f ki( j)=( j − k)2+ g 2i, k とする．このようにすると f ki( j)は j を変数とする 2 次関数とみなすことができる．そこで，行 i について，(0ekeN−1)のすべての 2 次関数 f ki( j)を 1 つのグラフに描くことを考え る （ 図 1 ）． 距 離 変 換 の 定 義 か ら ， す べ て の 曲 線 の 下 側 包 絡 線 が 行 i の 各 画 素 の 距 離 値di, j(0e jeN −1)に対応する．

ij）
f（3if（j）
2if（j）
4i
f（j）
1g2i,（2 j）

g2i,（3 j）

g2i,（1 j）

図1

ユークリッド距離と下側包絡線− 103 −g2i,（4 j）

3. ハードウェアアルゴリズム
本章では，シストリックアレイを用いたハードウェアアルゴリズムを提案する．このアルゴリズ
ムも[3]のアルゴリズムと同様に T1, T2の 2 つのステップから構成される．
3.1 T1 のアルゴリズム
T1 では列ごとの処理を行なうため，列 j を固定して考える．T1 をシストリックアレイで実現するときの単純手法は次の通りである．図 2 のように N 個のセルが横方向に並んだ 1 次元シストリックアレイを考え，2 値画像の列入力 b0, j b1, j b2, j … bN−1, j をこの順にセル 0 に入力する．セル 0 はカウンタを 1 つもち，他のセルはレジスタを 1 つもつ．セル 0 のカウンタは，0 が入力されると値を 0にセットし，1 が入力されるとカウンタを +1 する．各レジスタおよびカウンタはクロックごとに右へシフトする．このようにすると，最後の入力 bN−1, j がセル 0 に入力されたとき，レジスタ値 0のセル c より左側のセルにはセル c からの距離がレジスタにセットされた状態になる．セル c とそれより右側のセルとの距離を求めるため，列入力を逆順にセル N−1 に入力し同じことを行なう．
各セルにおいて順方向入力に対する距離と逆方向のそれとを比較し，小さいほうを採用し T1 の出力とする．この方法では T1 の実現に列を 2 回スキャンする．また，各セルでは順方向と逆方向の距離値を保持するための 2 つのレジスタと 1 つの比較器が必要である．[6]では，列のスキャンを 1 回で済ます回路を提案しているが，セル間の通信が隣接したセルだけでなく遠く離れているセル同士でも必要となり，セル間を接続するための配線のハードウェア量が大きくなってしまう．

bN−1, j ・・・ b2, j b1, j b0, j

図2

簡単な T1 のハードウェア構成

本論文では，スキャンを 1 回で行なうために各セルのレジスタに確定フラグ（Valid Flag，以下VF と表記）を持たせる．VF=1 のとき，そのセルではそれから最も近いレジスタ値 0 を持つセル cとの正しい距離がレジスタにセットされており，その値が確定していることを示す．VF の値はレジスタ値とともにクロックごとに右へシフトする．ただし，セル 0 の VF の値はクロックごとに0 をセットする．また，左のセルから順に 0,1,2 ・・・,N−1 の値を用意する（図 3）．これらを固定入力と呼ぶ．

− 104 −

図3

フラグ VF のセット

まず，レジスタ値 0 のセル c より左側のセルでの距離値を確定することを考える．図 3 は，0 がセル 0 に入力された後，連続で 1 が入力される状況で，どのような条件で距離値が確定するかを表している．図 3 では，フラグを丸印で表し，VF=0 のとき白丸で，VF=1 のとき黒丸で表している．セルのレジスタ値が確定するのは，そのセルの固定入力とそのセルよりも右側のレジスタ値0 のセル c との距離が一致したときである．つまり，クロックごとにレジスタ値，カウンタ値および VF が右にシフトし，その後，レジスタ値が確定したかどうかを調べ，確定したなら VF=1 とする．図 3 はレジスタ値，カウンタ値および VF が右にシフトした後の状態であり，その後，網掛けのセルでのレジスタ値が確定する（このとき VF=1 となる）．例えば図 3(c)では，セル 2 の固定入力が 2 で，セル 4 との距離が 2 であるためレジスタの値を確定する（VF=1 にする）．図 3(e)でも同様にセル 3 でレジスタ値が確定する．
次にレジスタ値 0 のセル c より右側のセルでの距離値のセットおよびレジスタ値を確定するときを考える．図 4 のように，すべてのセルに接続する Input 信号を導入する．列入力はセル 0 のほ
かに Input にも入力される．各セルはレジスタ値および VF が右にシフトしたあと，Input=0 のとき VF=0 のセルのレジスタに固定入力をセットし VF=1 とする．その結果，セル 0 より右側にあるセルで距離が確定していないセルのレジスタに，セル 0 からの距離がセットされる．これによりセル0 より右側のセルのレジスタに 1 クロックで距離値がセットされる．

− 105 −

図4

スキャンを 1 回で行なう T1 のハードウェア構成さらに工夫することで，各セルにカウンタや比較器を用意することなく距離値を確定することができる．まず，距離値は固定入力を直接レジスタにセットすればセル 0 のカウンタは必要としない．つまり，列入力は Input にのみ与えられる．また，セル 0 の左からの入力は∞が入るものとする．これは列のすべての値が 1 の場合を考慮しているためである．次に，距離値をセットするタイミングについて述べる．レジスタ値 0 のセル c に近いセル順に距離をセットするので，あるセルにおいて，そのレジスタに入っている距離値が確定するとき，右隣のセルは VF=1 で自身はVF=0 である．さらに図 3 より，レジスタ値 0 のセルが右に 2 つシフトするたび距離が確定することがわかる．ここで新しい制御信号 SS(Set Singal，以下 SS と表記)を導入する．SS はクロックごとに Input が 0 のとき 0 をとり，1 のとき以前の SS 値を反転した値をとる．SS は，列入力に 1 が連続しているとき，偶数番めと奇数番めを区別する信号である．
提案するアルゴリズムは，図 4 に SS 信号を加えた構成である（図 5）．各セルの内部構成を図 6に示す．図 5 の FF はフリップフロップであり，クロックごとに値が取り込まれ変化する．また，各セルはレジスタ値および VF が右にシフトしたあと，右隣のセルの VF，自身の VF，Input，SSの値から固定入力をレジスタにセットし VF=1 にするかどうかを決定する．それは次の条件によって決定される．

図5

T1 のハードウェア構成と制御信号 SSの生成− 106 −

図6T1 のセルの内部構成(a) Input=0 かつ自身のセルの VF=0 のとき，固定入力をレジスタにセットし，自身の VF を 1 にセットする．
(b) SS=0かつ自身のセルのVF=0かつ右隣のセルの VF=1 のとき，固定入力をレジスタにセットし，自身の VF を 1 にセットする．
列データが入力され始めて N クロック後，Output に g1, j が出力される．それ以降，g2, j，g3, j が順次出力される．N クロック以降，つまり bN−1, j が入力された後の Input には N 個の 1 を入力することとする．T1を実行するにはクロック数 2N が必要である．
例として，2 値画像の列データが b7b6b5 … b0=11011101 のときのセルの振る舞いを図 7 に示す．図7 ではクロックごとに(a)→(b)→(c)→…の状態をとる．各状態は，レジスタ値および VF がシフトし，固定入力がセットされた後の状態である．(a)は初期状態である．実線の太矢印の入力がセル内のレジスタにセットされる．図 7 の 8 クロック目の状態(i)では，まだセル 0 のレジスタ値は確定していない．しかし，2 クロック後の状態(k)で正しい値がセットされる．ある時点でレジスタに値がセットされていなくても Outputに出るまでの間に正しい値がセットされる．
最後に乗算器を削減する方法について述べる．T2 では T1 の出力を 2 乗したもの，すなわち，2i, jg を用いるので，このために乗算器が必要となる．T1 ではセル内のレジスタにセットされる値は固定入力値であり，一度セットされると T1 の処理中に変化することはない．よって，T1 の固定入力にはじめから 2 乗した値を用意しておけばこの乗算器は必要ない．

− 107 −

図7T1 のアルゴリズムの動作例

3.2 T2 のアルゴリズム
T2 は行ごとの処理であるため，T1 のときと同様，行 i を固定して扱う．[3]では下側包絡線を得るため 2 次関数同士の交点を求めているが，この処理を実行する効率的なハードウェアの実現は困難である．そこで，シストリックアレイ構造を利用した次のハードウェアアルゴリズムを考える．
2 次関数 f ki(x)の値は x=k から 1 画素離れるごとに 1,3,5,7,…ずつ増えていく．よって，クロック2が入力されるごとに g i, j に 1,3,5,…を順次加えていき f ki(x)の値を計算する．
T2 を計算するハードウェア構成を図 8 に示し，セルの内部構成を図 9 に示す．入力は T1 の出力
2の 2 乗，すなわちで g i, j ある．各セルはクロックが入力されるごとに最小な入力値をレジスタにセットする．
1 ク ロ ッ ク 後 の 図 8 の 上 か ら 1 行 目 の セ ル に は ， す べ て 2 次 関 数 の f ki (x)(0ekeN−1)のk−1exek+1 の範囲で構成される下側包絡線の値が保持される．次のクロックでは 2 行目のセルにすべての関数の k−2exek +2の部分で構成される下側包絡線の値が保持される．
0exeN−1 のすべての範囲で関数 f 0i(x)がその間数値を計算するにはクロック数 N−1 が必要である．また，すべての行についてパイプライン的に計算できるので，このアルゴリズムでは，すべての行に対する下側包絡線を求めるためにクロック数 2N−1 を必要とし，N × N−1 個のセルが必要である．

− 108 −g2i, 0g2i, 1g2i, 2g2i, 3g2i, 4

図8T2 のハードウェア構成

図9T2 のセル i, jの内部構成

g2i, 5g2i, 6g2i, 74. 動作速度と回路規模，FPGA による試作

N × N の 2 値画像を入力とする場合を考える．セル間のデータ交換及びセル内の計算を 1 クロックで行なうものとする．T1の処理と T2の処理は，それぞれ 2N クロック，2N−1 クロック必要である．
しかし，T1，T2 はともに行ごとにデータ入出力とシフトが行なわれるので，T1 の出力と T2 の入力を直接接続すればパイプライン的に動作でき，処理全体で必要なクロック数は 3N−1 である．
次に回路規模について考える．T1では各セルについてレジスタおよびセレクタが必要であるので，2それぞれ N 個必要である．T2 ではレジスタが N ( N −1)個必要で，加算器，比較器については− 109 −2O(N )個必要である．また，各セルの状態を決定するコントローラとセルのフラグ，そして配線資源が必要である．
そして，このユークリッド距離変換ハードウェアアルゴリズムの実用性を確認するため，ソフトウェア的に内部回路を書き換え可能なハードウェアとして Field Programmable Gate Array (FPGA)を使用した試作を行なう． FPGA は VLSI よりも動作速度は遅いながらも回路の動作は十分確認できる．試作は現在進行中であるが， VLSI に近い大規模 FPGA が搭載された評価ボードを用いることで，実現可能性に対する信憑性は高いと考えられる．FPGA の設計には、東京大学大規模集積システム設計教育研究センター（VDEC）から提供された各種 EDA ツールを利用した．

5. おわりに
2 値画像に対するユークリッド距離変換を行なうハードウェアアルゴリズムを，シストリックアレイを用いて実現した．アルゴリズムは[3]のアルゴリズムに基づいて構成された．T1 の変換を 1 回のスキャンで実現し，乗算器を使わずに下側包絡線を得ることができる．クロック数 3N−1 で処理2を行い，ハードウェア量は O(N )である．また，提案したハードウェアアルゴリズムの実用性を確認するため FPGA による試作を行なった．

参考文献[1] M.N. Kolountzakis and K.N. Kutulakos,
images,Fast computation of Euclidean distance maps for binary

Information processing letters, 43, pp.181-184, 1992.

[2] L. Chen and H.Y.H. Chuang,

A fast algorithm for Euclidean distance of 2-D binary image,

Information processing letters, 51, pp.25-29, 1994.
[3] T. Hirata,

A unified linear-time algorithm for computing distance maps,

Information processingletters, 58, pp.129-133, 1996.
[4] M. Miyazawa, P.F. Zeng, N. Iso and T. Hirata,
Transform,

A Systolic Algorithm for Euclidean DistanceIEEE Transactions on Pattern Analysis and Machine Intelligence, 28, 7, pp.1127-1134,

2006.
[5] D.W. Paglieroni,

A unified distance transformation algorithm and architecture,

Machine Vision

Appl. 5, pp.47-55, 1992.
[6] P.F. Zeng and T. Hirata,

ユークリッド距離変換アルゴリズムのハードウェア化に関する研究,

情処研報, 2002-AL-84, pp.17-24, 2002.
[7] H.T. Kung,

Why systolic architecture?,

IEEE Computer, 15, 1, pp.37-46, 1982.

− 110 −