Android Paperカメラの核心に触れるパート２

さてさてPaperカメラの第二弾

数学的な話ですが（笑

デジタル2値画像の距離変換について，これまでシティブロック(4近傍)距離とチェスボード(8近傍)距離については高速な方法が提案されていたが，実用上最も重要なユークリッド距離については決定的な方法は知られていなかった．

ところが最近，ShihとWuによって非常に効率的な方法が提案された．この方法は，3x3のウインドウで画像を2回(順方向に1回，逆方向に1回)走査するだけで正確なユークリッド距離変換が求まるという画期的なもので，通常サイズの画像ならほとんど一瞬で距離変換が完了する．

Frank Y. Shih and Yi-Ta Wu, ``Fast Euclidean distance transformation in two scans using a 3 x 3 neighborhood," Computer Vision and Image Understanding, vol.93, no.2, pp.195-205, Feb. 2004.

また，ボクセルデータなどの3次元画像への拡張も既に同著者によってなされている．

なんのこっちゃ？？いやいや、実は
こんな画像を作るのに必要なのですが・・・・・・・
画像の輪郭を描画するのにユークリッド距離を計算するんですが、平方根の計算があるので計算に時間がかかってしまいます。

上記の理論を適用すると
640x480の画像は614400回も計算が必要になります。

じゃあどうするの？？？

全部足し算と引き算で計算するのです。

こんな感じ

int min, max;
if ( workx < 0 ) workx = -workx;
if ( worky < 0 ) worky = -worky;
if ( workx < worky )
{
min = workx;
max = worky;
} else {
min = worky;
max = workx;
}

int total1=((( max << 8 ) + ( max << 3 ) - ( max << 4 ) - ( max << 1 ) +
( min << 7 ) - ( min << 5 ) + ( min << 3 ) - ( min << 1 )) >> 8 );

if ( workx2 < 0 )
　　　 workx2 = -workx2;
if ( worky2 < 0 )
workrky2 = -worky2;

if ( workx2 < worky2 )
{
min = workx2;
max = worky2;
}
else
{
min = worky2;
max = workx2;
}

int total2=((( max << 8 ) + ( max << 3 ) - ( max << 4 ) - ( max << 1 ) +
( min << 7 ) - ( min << 5 ) + ( min << 3 ) - ( min << 1 )) >> 8 );
r=(total1+total2);
//rは距離、エッジ強度を２とすれば(total1+total2)/2*2=total1+total2と簡略出来る
これならば半分の時間で計算出来ます。

でもですね、この計算はカメラデータyuvをRGBに変換してエッジ計算すると

Galaxy S2(2CPU)で30ms

Galaxy S3(4CPU)で20msかかっちゃいます。


エフェクトするのにちょっと厳しいせめて10msで完了しないとダメダメ

で次に行うのが並列処理

カメラからYUVデータが来たらRGB変換とエッジ処理

エフェクトはあらかじめ並列処理が完了したエッジデータを使用すればいいのですが・・・・


これでも厳しい～

じゃあPaperカメラは？？どうやってんの？？？？


この答は次回で（笑


おまけ：激重い計算プログラム（参考にしちゃダメですよん）
見てのとおりループ計算のオンパレード
計算時間は加算・引き算<掛け算<割さん<平方根の順にクソ重くなる
(short)rint(sqrt(workx*workx+worky*worky))なんて計算したら使い物になりゃしません
エレガントに足し算・引き算・ビットシフトで計算すいりゃ平方根も必要ありません


通常の計算方法
double Wx[3][3] ={{-base1,base3,base1},
{-base2,base4,base2},
{-base1,base3,base1}} ;
double Wy[3][3] ={{-base1,-base2,-base1},
{base3,base4,base3},
{base1,base2,base1}} ;

double Wx2[3][3] ={{0,0,0},
{0,1,0},
{0,0,-1}} ;
double Wy2[3][3] ={{0,0,0},
{0,0,1},
{0,-1,0}} ;
for(i=1;i {
for(j=1;j {
int a, aa, r, rr, g, gg , b, bb, counts,glay;
a = aa = r = rr = g = gg = b = bb = counts = 0;
for(ii=-1;ii<2;ii++)
{
for(jj=-1;jj<2;jj++)
{
　　 aa = pixelsSrc[(i+ii) + (j+jj) * width ] & 0xFF000000;
　　　　r = pixelsSrc[(i+ii) + (j+jj) * width ] & 0x00FF0000;
　　　　 r = r >> 16;
　　　　 g = pixelsSrc[(i+ii) + (j+jj) * width ] & 0x0000FF00;
　　　　 g = g >> 8;
　　　　 b = pixelsSrc[ (i+ii) + (j+jj) * width ] & 0x000000FF;

　　f[ii+1][jj+1]=r;
}
}
workx =0.0 ;
worky =0.0 ;
for(ii=0;ii<3;ii++)
{
　　 　　　　for(jj=0;jj<3;jj++)
　　　　{
workx += Wx[ii][jj]*f[jj][ii] ;
　　　　}
}
for(ii=0;ii<3;ii++)
{
　　　　for(jj=0;jj<3;jj++)
　　　　{
worky += Wy[ii][jj]*f[jj][ii] ;
　　　　}
}
workx2 =0.0 ;
worky2 =0.0 ;
for(ii=0;ii<3;ii++)
{
for(jj=0;jj<3;jj++)
{
workx2 += Wx2[ii][jj]*f[jj][ii] ;
}
}
for(ii=0;ii<3;ii++)
{
for(jj=0;jj<3;jj++)
{
worky2 += Wy2[ii][jj]*f[jj][ii] ;
}
}


int total1=(short)rint(sqrt(workx*workx+worky*worky));
int total2=(short)rint(sqrt(workx2*workx2+worky2*worky2));
r=(total1+total2)/2*shickness_lebel;