Cで回転プログラムの高速化を

Question

Cで、90枚の画像を、それぞれ0度から９０度まで回転させるプログラムを作りました。
回転の処理は重く時間がかかるため、
それぞれの角度の回転後の位置を配列に格納して、
その値を参照して画像を回転させていこうと思ったのですが、

例えば、画像が300*300としたら回転座標を入れる配列は2次元で２つとりますよね？
kaitenX[90][300]
kaitenY[90][300]
これで、例えば元画像を50度回転させる時のx,y座標が10,50の所の回転後の座標は
kaitenX[50][10]の値（回転後のx座標の値)　と
kaitenY[50][50]の値（回転後のY座標の値）を
参照さしてやればいいと思うのですが、

このとき、回転後の画像をtemp[300][300]という回転後の出力用配列に
代入していくとき、

どうやって代入していけばよいでしょうか？

まさか、

for(r=0;r<90;r++) //rは角度情報
  for(i=0;i<300;i++)
    for(j=0;j<300;j++)
    {
      temp[i][j] = Gengazo[r][kaitenx[r][j]][kaiteny[r][i]]
    }

なんて風には書けませんよね＾＾；（自分で一応試したけどダメでした）

回転後の座標を格納するまでは出来ると思うのですが、
格納後、どうやってその値を参照させて、格納させていけばいいか
わかりません。

教えていただけませんでしょうか？

また、もっと高速化できる効率の良い方法があれば教えて下さい。

fatbowler · Accepted Answer

ANo.4の補足に対する回答です。

> > 回転後の座標から回転前の座標を参照できるようにしたほうがよいの>ではないですか？
> >も正にその通りで、参照の紐付けを逆にしておけば、代入の必要がな>くなります。
> 
> この部分の方法がよくわかりませんでした。参照の紐付けをすれば代入の必要がなくなる。
> というのが、具体的にどうすればよいのか検討がつきませんでした。

（回転後のx座標）＝（回転前の座標、回転）
（回転後のy座標）＝（回転前の座標、回転）
ではなく、
（回転前のx座標）＝（回転後の座標、回転）
（回転前のy座標）＝（回転後の座標、回転）
とするべきだ、ということです。
必要なのは後者だけなのに、紐付けを前者の方式でやっておいて、改めてループで
後者に変換しようとしています。
始めから紐付けを後者の方式でやっておけば、わざわざ代入しなくて済みます。

> 時間がかかるのは、Cos Sinの計算なんですね！！（回転全体のプログラムが遅いのかと思ってました）
> 先に、その計算をしてやって、配列に入れておけば、
> 後は普通に回転のプログラムを組んで、Cos Sinの計算の部分だけ、
> 最初に作っておいた配列を参照してやるように作ればいいということですよね？

そうです。三角関数に限らず、平方根[sqrt()]、対数[log()]など、四則演算に展開できないものは
みんな計算が遅いです。（厳密には、四則演算の中でも割り算は遅いです。）
計算が遅いものをテーブル化しておくのは、高速化の際の上等手段です。

> 回転前の現画像のx座標,y座標って、普通に(0,0)～(300,300)ですよね？
> 自分の場合、最初に90枚の画像をsrc[90][300][300]に一気に取り込んでしまってます。
> いわば、この添え字が回転前のx,y座標だと思うのですが・・・

「最初に90枚の画像を取り込む」という処理は、厳密には画像ではなく、座標の取り込みだけですよね？
だったら、どんな画像でも同じ処理を行うのでプログラムで計算する必要性はなく、
これも別途計算しておいてテーブル引きが可能です。
（回転前のx座標）＝（回転後の座標、回転）
（回転前のy座標）＝（回転後の座標、回転）
の２つの配列を、sinやcosで計算するのではなく、データとしてプログラムに直書き
することができるという意味です。

また、前回の回答で抜けていましたが、表示の際に画像のBITイメージをVRAMに展開する処理が
あると思いますが、その際の計算量をなるべく減らすのが、実行時の高速化に繋がります。
具体的には、座標のデータだけでなく、BITイメージを90枚分あらかじめ作っておくということです。
（既にやっていますか？）
可能なら、VRAMと同じメモリ形式に90枚分のイメージをあらかじめ作っておいて、
表示の際にはVRAMにmemcopy()するだけにできれば理想的ですが。

fatbowler · Answer

概ね回答は出揃っているようですが。

> temp[kaitenx[r][j]][kaiteny[r][i]] = Gengazo[r][j][i];
> この書き方が出来るのかどうかが知りたいので
> 回答お願いします！！

何も問題ありません。
kaitenx[r][j] == x
kaiteny[r][i] == y
であれば、
temp[kaitenx[r][j]][kaiteny[r][i]] == temp[x][y] 
となります。
もちろん、kaitenx[][]やkaiteny[][]は整数型であり、0以上である必要はありますが。

ANo.1に書かれている、
> そう考えると、写像を配列で保持するためには、
> 　kaitenX[90][300][300] /*[角度][回転前x][回転前y]*/
> 　kaitenY[90][300][300] /*[角度][回転前x][回転前y]*/
> という配列が必要なのではないでしょうか。
は理解されていますか？
|x'|　＝　|　cosθ　-sinθ　|　|x|
|y'|　＝　|　sinθ　 cosθ　|　|y|
なので、回転前のx座標、y座標の両方の情報が必要になります。
また、
> > temp[i][j] = Gengazo[r][kaitenx[r][j]][kaiteny[r][i]]
> このような書き方をしたいのであれば、
> 回転後の座標から回転前の座標を参照できるようにしたほうがよいのではないですか？
も正にその通りで、参照の紐付けを逆にしておけば、代入の必要がなくなります。

高速化という話でしたら、ANo.3に書かれたテーブル引きの方法が常套手段で、非常に効果的です。
const double cos_r[90] = {
　1.0000,　0.9998,　0.9994,　0.9986,　0.9976,　0.9962,　0.9945,　0.9925,
　・・・
};
といったテーブルを定義しておいて、cos(r)を計算する代わりにこのテーブルから
値を引っ張ってくるのですが、メモリは無駄遣いしますが劇的に早くなるはずです。
（もちろん、実際にはもっと有効桁数を多くしますが。）
更に高速化を求めるなら、回転前のx座標、y座標を、(90×300×300)個ずつ準備する
方法があります。
実行時に浮動小数点計算をしなくて済むので、更に高速に実行できるはずです。
使用できるメモリとスピードとのトレードオフなので、実際にはこのバランスによって
決めることになりますが。

他の方の回答のいいとこ取りで失礼しました。
また念のため、0度～90度なら90個ではなく91個ですのでご注意下さい。

buriburi3 · Answer

ご質問の回答とは異なりますが
三角関数(特にcos)を使用している場合、いちいち計算すると遅いので1度刻みの値しか使わない事が分かっているのでしたら予め計算した結果を定数テーブルに持っておくと速くなります。

maku_x · Answer

1辺が a(画素)の画像を θ だけ回転する場合、回転後の画像の1辺の長さ l(画素)は、
l = a * (cosθ + sinθ)
となります。0≦θ≦π/2(90°) のとき、θ=π/4 (45°)のときに l は最大値を取り、a = 300 のとき
l = 426.264... ≒ 427
です。
なので、temp[300][300] は、
temp[427][427]
と、十分な大きさの配列にしなければなりません。

また、
> temp[i][j] = Gengazo[r][kaitenx[r][j]][kaiteny[r][i]]
は、
temp[kaitenx[r][j]][kaiteny[r][i]] = Gengazo[r][j][i];
ではないでしょうか。

＃ 但し、画像データのように (x,y)座標を多次元配列で表現する場合は、常識的には ImageData[y][x] の様に、x座標が配列の添え字の右側に来るように書きます。

なお、他の画像の回転方法を知りたければ、netpbm (Linux 等の UNIX系OS で画像処理を行なうプログラム群) の中の pnmrotate を参照してください。(参考URLからダウンロードできる圧縮ファイルの中に、editor/pnmrotate.c と言うソースコードがある。)

＃ でも、同じような処理をしてるっぽい。

参考URL：http://netpbm.sourceforge.net/

Werner · Answer

回転前画像上の座標(x0,y0)の画素が、
回転によって回転後画像上の座標(x1,y1)に移動するとき、
　回転後(x1,y1) = 回転前(x0,y1)
という代入を行うが、
このときの(x0,y0)→(x1,y1)の写像を配列に格納したいと言うことですよね？

だとすると、
> 例えば、画像が300*300としたら回転座標を入れる配列は2次元で２つとりますよね？
> kaitenX[90][300]
> kaitenY[90][300]
> これで、例えば元画像を50度回転させる時のx,y座標が10,50の所の回転後の座標は
> kaitenX[50][10]の値（回転後のx座標の値)　と
> kaitenY[50][50]の値（回転後のY座標の値）を
> 参照さしてやればいいと思うのですが、
これではうまくいかないのでは？
これだと、回転前のx座標が同じなら回転後のx座標も必ず同じになってしまいます。
実際は、回転前のy座標だけが変化しても、回転後はx,y両方変化しますよね？

そう考えると、写像を配列で保持するためには、
　kaitenX[90][300][300] /*[角度][回転前x][回転前y]*/
　kaitenY[90][300][300] /*[角度][回転前x][回転前y]*/
という配列が必要なのではないでしょうか。


もし、画像データを一次元配列に image[x+y*width] のように格納すれば、
　kaiten[90][90000] /* 回転後x+回転後y*300 = [角度][回転前x+回転前y*300] */
という配列1つで済ますことはできます。


> temp[i][j] = Gengazo[r][kaitenx[r][j]][kaiteny[r][i]]
このような書き方をしたいのであれば、
回転後の座標から回転前の座標を参照できるようにしたほうがよいのではないですか？
（上で例にあげて説明してきたのは、「回転前の座標から回転後の座標を参照」するための配列ですからね。）
まあ、回転方向が逆転するだけなのでたいした問題ではないかもしれませんが。

Cで回転プログラムの高速化を

ANo.4の補足に対する回答です。

概ね回答は出揃っているようですが。

この回答への補足

ご質問の回答とは異なりますが

1辺が a(画素)の画像を θ だけ回転する場合、回転後の画像の1辺の長さ l(画素)は、

回転前画像上の座標(x0,y0)の画素が、

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング