社長のつぶやきメモ帳

カンダシステム株式会社の社長をしている画像解析プログラマーのブログ

画像解析

直線補間

補間について少し書いてみます。間を補うと書いて補間。点と点の間を繋ぐ。私がプログラムを書き始めた頃は、直線描画のハードあるいはコードで作っていた。

o点とp点を繋ぐ。

X方向に3、Y方向に5進む。

 

多分上の図が望まれる。

 除算機能のないCPUがまれになった現在では、増分(Y/X、あるいはX/Y)を

求めておいて、累積させれば求まる。

 上の例で言うと、増分は3/5(=Y/X)となる。

 累積の結果1を超えた場合は上と右へ、超えない場合は右のみへ進める。

Yの累積値

Xの座標

Yの座標

Yの目標値

誤差

始点

1回補間後

3/5

3/5

-3/5

2回補間後

6/5->1/5

2

6/5

-1/5

3回補間後

4/5

3

1

9/5

-4/5

4回補間後

7/5->2/5

4

2

12/5

-2/5

4回補間後

5/5->0/5

15/5

 

 となる。

少し変ですね。

 これは丸め処理(四捨五入)が入ってないためです。

 丸め処理を入れる。

 累積結果に1/2を加えて判定すればよい。累積の初期値を1/2とする。

Yの累積値

Xの座標

Yの座標

Yの目標値

誤差

始点

1/2(初期値)

1回補間後

1/2+3/5->1/10+1

1

3/5

+2/5

2回補間後

1/10+3/5->7/10+0

2

6/5

-1/5

3回補間後

7/10+3/5->3/10+1

3

2

9/5

+1/5

4回補間後

3/10+3/5->9/10+0

4

2

12/5

-2/5

4回補間後

9/10+3/5->0/10+0

15/5

 

 となる。

 さてコードだが、右へr、上へu進ませる場合(2点間の距離が[r、u])、増分u/rを求める必要がある。

 r/uの性質上Real(float,double)を使いたくなるが、整数演算で間に合わす。

補間の距離に依存するが、2の16乗未満の画素数なら、16ビットのunsignedで足りる。

増分は16ビットの下駄を履かせて演算する。

 a=65536×u/r

 こうすると、Msb(最上位ビット)が1/2となる。

 同様に初期値1/2は32768となる。

 この初期値にaを累積させ、Xを1画素進めた時にYを増加させるかをキャリーで判定する。

 しかし、キャリービットを検知する言語でない場合、累積値の減少を判定する。

sample code

 void LineInterpolation( Cpoint p0, CPoint p1)

{

CPoint d= p1 – p0;

if ( d.x == 0 && d.y == 0 ) { return; }

unsigned short a= 65536 * d.y / d.x; // 16ビットの下駄を履かせて増分算出

unsigned short ds=  0×8000; // 初期値を1/2に

Cpoint p;

for( p= p0; p != p1; p.x++ ) { // X方向歩進

// ここに補間点pに対する処理を入れる。

If ( ds + a < ds ) { p.y++; } // キャリー判定とY方向歩進

ds += a; // 誤差の更新

}

}

これはモデルであり、使えるのは

r>=0 && u>=0 && |r|>=|u|、すなわち0~45度の区間に限る。

 老婆心ながら付け加えると、45~90度の区間はX座標とY座標を入れ替えればよい。

更に、-45度~0度の区間であれば、Yの符号を反転しY方向の増分を-1とする。

他の区間も同様で、X,Yの入れ替えと増分の符号反転で対応すればよい。

お気づきかもしれないが、このコードでは終点は描画されない。

 これは、On purpose!

 ちょっとした意味があります。

 次回、円弧補間を書くつもりですのでその時に。

金と力が

最近2,3の問題が持ち込まれた。残念ながら何れも解けていない。今日はその内の1つの問題の解を得ようと、知人の会社を訪ねた。結果はX。透明フィルムの凹凸を検出したいという事。 現在は、人間が、蛍光灯にかざし検査している。その作業も、慣れている人にしか出来ない様である。しかし、干渉顕微鏡であればよく見えるという。少しそちらを調べてみるか。 画像を扱う場合の大きなテーマは、「精度と処理速度を如何に保つか」であろう。精度を上げるためには、視野が狭くなる。被計測物の大きさ/視野の大きさ=取り込み画像数。 今日の被検査物は、1mX1.5m程の大きさである。1回の視野は200万画素のカメラで検出精度を考えるとせいぜい大きくしても2mm程度。 1mX1.5m/(2mmX2mm)≒40万回となる。 30フレーム/毎秒でとると、凡そ13000秒=3時間半。これでは。。。 もうひとつの別のテーマでは、十分な大きさがあり、すでに画像として取り込めている。電子顕微鏡画像であるが、そこに映し出されている画像からの輪郭抽出をしたい。 人間が見れば、確かに輪郭はあるのだが、場所によって濃度差はまちまちである。ゾーベル等、幾つかのフィルターをかけてみたが、人間のように上手くは切り出せない。 自分自身で輪郭が見えるのであるから、それを計算機に教えてやればよいわけだが。悲しいかな、それを明確に述べることが出来ない。確かにある部分はうっすらと暗い線が見える。 であれば、周囲との濃度差で見つけられそうだが。こういったジレンマは、苦痛であるが同時にそれを解けたときの喜びは。 可能であれば1年ほどのコストを掛けて(賭けて)見たいものであるが。