Microsoft bmpファイルをラスタ順序逆にするには?

Microsoft の bmpファイルフォーマットというものがあります．

このフォーマットは，格納順序が画像の底辺(画像で言うと，ボトム)ラスタからトップラスタ(画像で言うと上)に向けて格納されています．

わけあって，トップのラスタからに並べ替えたいのですが，メモリがあまりありません．
全体を読み込んでから，逆順でファイルにはき出せば
良いと思いますが，これだと，
たとえば1GBのデータだと1GBのメモリが必要です．

メモリを使わずに，
ファイルをシークして読み込んでから，書き込むとすると，かなり遅そうです．

実装されているメモリ容量の単位で区切って読み書きするなどの
あまり複雑な事をせずに，スマートにラスタ順序を入れ替える方法をご存知でしたら，よろしくお願いします．

アプリは，単純だけど，仮想記憶でOSが勝手にスワップ
させるような方法も使いたくないです．

なにかアルゴリズムやファイルシステムの特性を使って
うまくできませんかね．

漠然としていると，まずいかもしれません．

メモリが128MB程度あって，画像bmpファイルが1GBの大きさがあるときに，ラスタの順序を入れ替えるのが目的です．
なるべく高速にやりたいです．
ディスクへのスワップはさけたいです．

No.1 ベストアンサー 回答者： jx-word 回答日時： 2005/05/05 21:00

1ライン分ずつシークして処理すればいいんじゃないでしょうか。

ファイルポインタのシークはメモリ上のポインタを書き換えるだけだから、そのコストはほとんど無視できるレベルだと思います。
ラインの境目で多少のロスが出るでしょうが、これもOS側がディスクキャッシュで吸収します。

なんとなく考えすぎているだけのように思えますので、実際に簡単なコードを書いて試してみてはいかがでしょうか。

この回答へのお礼

ありがとうございます．

>なんとなく考えすぎているだけのように思えますので、実際に簡単なコードを書いて試してみてはいかがでしょうか。

たとえば，1GBのデータとは，
24ビットフルカラーで，20000x20000
程度の画像を意味します．

ディスク側のキャッシュがどの程度の大きさなのかも知らずに質問しております．

ご回答は，「普通にプログラムすればいいのでは?」
ということですね．

ご回答の方法は，私はたしかに試してはいません．
ただし，仲間が，質問した内容でプログラムして，
「ものすごく遅かった」という評判だったので，
なにかいい方法はないものかなぁと考えて質問しました．

自分のマシンは，高速(2.7GHz)で，メモリもたくさん(2GB)つんでいるので，たぶん，どちらの方法も高速にはなると思うのですが，非力なマシンに対しても，そこそこの性能を出す方法が知りたいわけです．

一度，自分でも，試してみたいと思います．

しかし，非力なマシンは世の中たくさんありますし，アルゴリズムで速度が一変することも良くあります．
マシンパワーにあまり依存しない「知恵」は無いものでしょうか?


かなり前，アスキーという雑誌で，
画像を表現する容量として，16ビット×16ビットあれば大丈夫だろうという議論が，20年前にありました．
これは，65536x65536ということです．

当時は，途方も無い大きさに感じましたが，
わずか20年で，これに迫る大きさを末端のパソコンが
扱う時代になってきました．

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

お礼日時：2005/05/06 06:24

No.4 回答者： rentahero 回答日時： 2005/05/07 14:31

#2です。

#3の方法で問題ないと思います。（未検証）

一応#2の回答の補足への回答などを少し。

> 逆ラスタ順序での格納をファイルのシークでやるとしたら，
> ディスクを逆さまに読んでいくことになり，へたをすると
> ディスクが１回転してくる待ち時間が，毎ラスタごとに
> 入るのではないかと心配してました．そんなにディスク
> キャッシュが小さいことはないと思いますけど．

実のところ、今のHDDのシリンダ構成(http://e-words.jp/w/ZCAV.html)とか、LBA(http://e-words.jp/w/LBA.html)がなぜできたかとかそういうのを考えると、もうシリンダ面にどうセクタが並んでいるのかなんて、予測できないんですよ。だから、シリンダ1回転の間のギャップウェイトとかは、今は考慮しなくてもいい（本当のところは考慮できないが正しい）んです。
もちろんヘッドシークの時間は関係あるんですが、それを考慮するしてもやっぱり物理メモリを調べて空きメモリの何割かを利用してバッファリングするぐらいしかできないです。これは試してないので、何割とれば最適化はわかりません。
ヘッドシークを最小限にするために読み＆書きのファイル位置の切り替えを最小限にすることと、先読みキャッシュ＆書き込みキャッシュを最大限に利用するためにキャッシュ容量を最大限に確保することは相反するためです。

> このあたり，なんとなく昔の64KByteセグメントの時代を
> 思い出しました．スモールモデルとかラージモデルとか
> あったときの話です．

わかります。私がＰＣでプログラム書き始めたころ（も15年近く前）でもまだＤＯＳ時代でした。最初に使ったＣコンパイラはLSI-C86 試食版でした。

フロッピの場合、回転速度を考慮しないと最速アクセスはできないんでしたよねえ。

弁解＆ヨタ話でした。

参考URL：http://e-words.jp/w/ZCAV.html, http://e-words.jp/w/LBA.html

この回答へのお礼

たびたびありがとうございます．

>シリンダ1回転の間のギャップウェイトとかは、今は考慮しなくてもいい（本当のところは考慮できないが正しい）んです。

「そこのところをぜひ考慮したい」という質問だったのですが，伝わらなかったみたいですね．
申し訳ありません．

>先読みキャッシュ＆書き込みキャッシュを最大限に利用するためにキャッシュ容量を最大限に確保することは相反するためです。

それは，どこをアクセスするか分からない場合ですね．
かならずアクセスするところだけキャッシュに入れれば，キャッシュは大きい方が良いと思いますよ．
CPUのキャッシュとは違いますから．

実際，そんなに簡単なことを質問したつもりはありません．頭を絞らないと，質問にも書いた，シンプルだけど高速で逆ラスタで格納できるアルゴリズムはできないでしょう．そこがまた面白いところでもあります．

しばらく楽しめそうです．

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

お礼日時：2005/05/07 18:44

No.3 回答者： jx-word 回答日時： 2005/05/07 03:44

#1です。

あのあとよく考えてみたら、1ラインごとに処理をしていたらHDDのヘッドシークの時間がかかることに気がつきました。申し訳ありません。

で、高速化の方法ですが、基本は1ラインごとに交換するとして、バッファを数ライン分用意してReadFileとWriteFileをまとめて処理してはいかがでしょうか。
この場合、バッファがスワップアウトされたら本末転倒ですので、バッファはスワップ禁止にします。

1. GlobalMemoryStatusで物理メモリの空き容量を取得し、バッファ容量をどのぐらいにするか決める。
2. VirtualAllocでバッファを確保する。
3. VirtualLockでバッファをスワップ禁止にする。
4. このバッファを使ってラインの交換をする。
5. VirtualUnlock, VirtualFreeで後始末。

VirtualLockは使ったこと無いんですが、MSDNを見る限りこれでいけそうな気がします。

この回答へのお礼

たびたびありがとうございます．

>1. GlobalMemoryStatusで物理メモリの空き容量を取得し、バッファ容量をどのぐらいにするか決める。

物理的にとれるだけのメモリをまず，調査して，それを最大限に生かすようにすると言うわけですね．

このあたり，なんとなく昔の64KByteセグメントの時代を思い出しました．スモールモデルとかラージモデルとかあったときの話です．現在は，リニアな空間をつかった単純なプログラムの時代かと思っていたのですが，
そうも行かないようですね．

問題が単純なだけに，クリアーな解はなくて，
ゴシゴシと書かなくてはならないということがだんだん分かってきました．

bmpファイルのラスタは，32ビットバウンダリに合わせてあるので，4バイト単位で取得すればいいですね．

お礼日時：2005/05/07 06:59

No.2 回答者： rentahero 回答日時： 2005/05/06 14:36

え～っと。

非圧縮のＢＭＰの処理ですよね。
１ＧＢ読んで１ＧＢ書かないといけないということは
わかりますよね？

ということは、最低でも画像のフルコピーをやるのと同じコストは確実にかかります。

フルコピーに係る処理は

１．ヘッダのメモリを確保して読み込み。
２．コピー先にヘッダを書き込み
３．ヘッダにあるライン容量分のメモリ確保
４．ライン数分くりかえし
５．コピー元から１ライン読み込み
６．コピー先に１ライン書き込み
７．４にもどる
８．おわり

逆順のフルコピーに係る処理は

１．ヘッダのメモリを確保して読み込み。
２．コピー先にヘッダを書き込み
３．ヘッダにあるライン容量分のメモリ確保
４．ライン数分くりかえし
５a．コピー元の未読み出し中最後のラインの先頭へシーク
５．コピー元から１ライン読み込み
６．コピー先に１ライン書き込み
７．４にもどる
８．おわり

上記に５ａの処理が追加されただけです。

遅いＰＣで１ＧＢのフルコピーをやるとそれだけで１秒単位のかなりの時間がかかります。
そこは、アルゴリズムで何とかなるような構造ではないです、というかほとんどディスクとPCIバスのベンチマークの世界です。

ファイルシステムの特性という部分では、ＤＯＳ時代でかつ、クラスタ単位で１ラインのデータが入ってると確定しているのであれば、クラスタのつなぎ変えで処理できたかもしれないけど、クラスタ長が固定のFAT上ではwindows bmp（に限らずたいていの汎用画像フォーマット）ではありえないです。ヘッダもあるし、縦横のdot数もデータサイズも可変だし。

この回答へのお礼

ありがとうございます．

>ということは、最低でも画像のフルコピーをやるのと同じコストは確実にかかります。

もともと，ラスタ順序を変えずにフルコピーするのよりも速くなるとは思っていません．

基本的に，ディスクの回転時間で，格納されているデータを単に読み出す時間はかかります．
書く時間も当然必要です．

この際，キャッシュの容量や，バスの速度が遅ければ，
さらにかかるでしょうね．
通常，メモリが潤沢にあれば，この差はほとんどゼロに等しくなり，ディスクの回転時間による読み出し時間に近くなると思います．

逆ラスタ順序での格納をファイルのシークでやるとしたら，ディスクを逆さまに
読んでいくことになり，へたをするとディスクが１回転してくる待ち時間が，毎ラスタごとに入るのではないかと心配してました．そんなにディスクキャッシュが小さいことはないと思いますけど．


>そこは、アルゴリズムで何とかなるような構造ではないです、というかほとんどディスクとPCIバスのベンチマークの世界です。

そうなんですか．

どうやら，自分でいくつかコードを書いて，
実験した方が良いようですね．

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

お礼日時：2005/05/06 23:37