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

質問

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]]
}

なんて風には書けませんよね＾＾；（自分で一応試したけどダメでした）

回転後の座標を格納するまでは出来ると思うのですが、
格納後、どうやってその値を参照させて、格納させていけばいいか
わかりません。

教えていただけませんでしょうか？

また、もっと高速化できる効率の良い方法があれば教えて下さい。

回答No.5

fatbowler · ベストアンサー

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()するだけにできれば理想的ですが。

お礼

回答ありがとうございます！！

代入のところ言いたいことがわかりました！！
丁寧な説明ありがとうございます！

早速、色々試してみたいと思います！
ちなみに、cos,sinの計算を先にやっただけでも、
なかなか早くなりました！

最後の表示の際の話はちょっと理解できないですが、
まずは１つ１つやっていこうと思うので、
とりあえず座標計算の短縮を目指します！！

ありがとうございました！

回答No.4

fatbowler

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

> 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個ですのでご注意下さい。

お礼

皆さん、たくさんの回答ありがとうございます！！とても助かります！

おかげで少しずつですが解ってきました。

ここに、皆さんの回答に対する質問を書こうと思ったのですが、

文字数が超えてしまったので、すみませんが、補足の方へ書かせてもらいます！

補足

皆さん回答ありがとうございます！！

お礼に書ききれなかったので、すみませんが補足に書かせてもらってます！

まず、
> temp[kaitenx[r][j]][kaiteny[r][i]] = Gengazo[r][j][i];

このような書き方が出来る事が知れて大収穫でした！！ありがとうございます。

それと、
回転後の座標を求めるのに、回転前のX,Y座標が必用なことはわかっていますが、書き方がまずかった思います。ご指摘ありがとうございます。

ただ、
> > temp[i][j] = Gengazo[r][kaitenx[r][j]][kaiteny[r][i]]
> このような書き方をしたいのであれば、
> 回転後の座標から回転前の座標を参照できるようにしたほうがよいの>ではないですか？
>も正にその通りで、参照の紐付けを逆にしておけば、代入の必要がな>くなります。

この部分の方法がよくわかりませんでした。参照の紐付けをすれば代入の必要がなくなる。というのが、具体的にどうすればよいのか検討がつきませんでした。
（ただ、下に書きますが、高速化が一番の目的なので、Cos,Sinのテーブルを作る方が良いなら、これまで書いた方法は気にしないで下さい、むしろテーブルを作って高速化する方を詳しく知りたいです！）

そして、高速化のところのアドバイスですが、

>高速化という話でしたら、ANo.3に書かれたテーブル引きの方法が常套手段で、非常に効果的です。

この指摘はとてもありがたかったです！
私が一番したいことは、高速化なので、
こういう高速化の方法を教えていただき感謝です！
時間がかかるのは、Cos Sinの計算なんですね！！（回転全体のプログラムが遅いのかと思ってました）
先に、その計算をしてやって、配列に入れておけば、
後は普通に回転のプログラムを組んで、Cos Sinの計算の部分だけ、
最初に作っておいた配列を参照してやるように作ればいいということですよね？

最後の
>更に高速化を求めるなら、回転前のx座標、y座標を、(90×300×300)個ずつ準備する
>方法があります。
>実行時に浮動小数点計算をしなくて済むので、更に高速に実行できるはずです。

この部分は、すみません。ちょっと解りませんでした。
回転前の現画像のx座標,y座標って、普通に(0,0)～(300,300)ですよね？
自分の場合、最初に90枚の画像をsrc[90][300][300]に一気に取り込んでしまってます。
いわば、この添え字が回転前のx,y座標だと思うのですが・・・
すみません。よく理解できてないので意味不明なこと言ってるかもしれません（＞＜）

すみませんが、その辺をもう少し教えていただけますか？

（また、高速化を説明してるサイトがあれば、そちらを教えていただくだけでも結構ですので、よろしくお願いします）

回答No.3

buriburi3

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

回答No.2

maku_x

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/

お礼

回答ありがとうございます！！
回転後の画像は、切れていて問題ないので、配列は300*300にしました。

また、ご指摘の
temp[kaitenx[r][j]][kaiteny[r][i]] = Gengazo[r][j][i];

は、その通りでした！書き間違えてました！

１つ聞きたいのは、このような書き方で正しく動くのでしょうか？
配列の添え字のところに、配列を書くなんて、書けたら便利ですけど
ちゃんと動くかどうか不安で・・・

（データを[y][x]であらわすのは知ってました。ありがとうございます）

temp[kaitenx[r][j]][kaiteny[r][i]] = Gengazo[r][j][i];
この書き方が出来るのかどうかが知りたいので
回答お願いします！！

回答No.1

Werner

回転前画像上の座標(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]]
このような書き方をしたいのであれば、
回転後の座標から回転前の座標を参照できるようにしたほうがよいのではないですか？
（上で例にあげて説明してきたのは、「回転前の座標から回転後の座標を参照」するための配列ですからね。）
まあ、回転方向が逆転するだけなのでたいした問題ではないかもしれませんが。