C言語でBMP画像を作ろう!
大学C言語の授業の定期試験で作成したレポート
Generate bmp image with C. · GitHub
1.目的
C言語を使ってファイルをバイナリストリームで開いてbmpファイルを作成しよう。
図1.この画像を生成する。
2.原理
2.1C言語でバイナリファイルを生成
C言語のstdio.hライブラリにはファイルを開く関数があるがそれを使うことで直接機械が読み取れるバイナリデータを書き込むことができる。
これを使うことで一からファイルを生成しよう。
2.2bmpとは?
bmpとは「bitmapimage」の略であり、imageという名前がついている通り画像ファイルだ。一般に使われているpngやjpegといった形式はバイナリデータが圧縮されているためC言語で扱うにはほかにライブラリが必要である。bmpファイルは圧縮しなくても画像ファイルとして作成することができ、バイナリデータを直接いじるのに複雑な操作が(pngなどと比べて)必要でなく容易である。そのため今回はbmpを使う。
3.ソースコード
1 |
//中京と書いてあるbmp画像を生成するプログラムです。 |
2 |
|
3 |
#include<stdio.h> |
4 |
#include"bmpsetting.h" |
5 |
#include”bmpsetting.h” は今のディレクトリからヘッダーファイル「bmpsetting.h」
を探してインクルードするマクロ。
Bmpsetting.hはbmpファイルのヘッダー情報を設定するための構造体と構造体を初期化するための関数が入っている。
7 |
int main(void){ |
8 |
|
9 |
FILE *BMPfp; |
10 |
errno_t error; |
11 |
|
12 |
return error; |
今回のプログラムはVisualStudio2013を使って作成した。VisualStudi2013ではセキュリティの意識が高く、fopenなどの関数が使えない。その代わりにfopen_sなどの関数を使われるように促される。
fopen_sはfopen関数と違い、FILE構造体を戻り値として返す形で開くファイルを設定せずにFILE構造体のインスタンスのアドレスを書きかえてファイルを開く。
fopen_sは戻り値としてerrno_t型の変数を返す。この変数の数値によってerrorが起こったかだけでなくerrorの種類がわかる。
bmpファイルに情報を書き込むためにはファイルにテキストではなくバイナリを書き込まなくてはならない。そのためfopen_s関数の第三引数において”w”ではなく”wb”のように”b”を加えることでファイルをテキストストリームではなくバイナリストリームで開いている。
13 |
int sfsdaf[10][18] = |
14 |
{ { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1 }, |
15 |
{ 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1 }, |
16 |
{ 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, |
17 |
{ 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1 }, |
18 |
{ 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1 }, |
19 |
{ 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1 }, |
20 |
{ 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1 }, |
21 |
{ 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1 }, |
22 |
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1 }, |
23 |
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1 } }; |
配列を宣言する際に(変数名)のように記述すると配列の配列が作成できる。これらの数値をつかってbmp画像に入力するデータを決める。
24 |
BMPFileHeader bmpFH = InitializeFileHeader(); |
25 |
BMPInfoHeader bmpIH = InitializeInfoHeader(); |
26 |
ColorPalette colP[2] = { |
27 |
{ 0x00, 0x00, 0x00, 0x00 }, //Black |
28 |
{ 0xFF, 0xFF, 0xFF, 0x00 } //White |
29 |
}; |
30 |
|
31 |
bmpIH.ImgHeight = 0x0A; |
32 |
bmpIH.ImgWidth = 0x12; |
33 |
unsigned int ByteperImgLine = ((0x12 / 8) + 1) + 1; |
34 |
bmpIH.ImgDateSize = 0x0A * ByteperImgLine; |
35 |
bmpFH.FileSize = bmpFH.DateOffSet + bmpIH.ImgDateSize; |
36 |
|
37 |
|
38 |
fwrite((char*)&bmpFH + 2, sizeof(BMPFileHeader)-2, 1, BMPfp); |
39 |
fwrite(&bmpIH, sizeof(BMPInfoHeader), 1, BMPfp); |
40 |
fwrite(colP, sizeof(ColorPalette), 2, BMPfp); |
41 |
bmpファイルには画像そのもののデータだけでなく、ヘッダデータが存在している。ここではそのヘッダデータを記述している。
ヘッダデータには二種類のヘッダがある。ひとつはファイルヘッダというものでどのような形式のbmp画像にもこれが存在する。もうひとつは情報ヘッダで、このヘッダはCORE型やINFO型などの型があり、INFO型が一般的であるらしい。今回はINFO型を使用した。これらの詳しい構成は付属のExcelファイルに記述した。
42 |
unsigned int num; |
43 |
char zero = 0; |
44 |
for (int row = 0; row < 10; row++){ |
45 |
num = 0; |
46 |
for (int column = 0; column < 18; column++){ |
47 |
num = num * 2 + sfsdaf[9 - row][column]; |
48 |
} |
49 |
fwrite(&num, sizeof(int), 1, BMPfp); |
50 |
} |
51 |
|
52 |
fclose(BMPfp); |
53 |
return 0; |
54 |
|
55 |
} |
BMPfpに用意したデータを書き込む。
fwrite関数はこのソースの記述で言うと、アドレス&numを初期位置としてsizeof(int)バイト分のデータを1個取り出してBMPfpに書き込むという処理をしている。
このソースコードではsfsdafを一番目の配列からではなく最後の配列から入力している。なぜこうするかというとbmpファイルは最初のイメージデータが左下から始まり右方向に進み、改行すると今度は上方向に進むので下から順番に積み上げるようにデータを入力しないといけないためだ
4.結果
図1のような画像を生成するつもりだったが、実際にプログラムを組んだところ画像が反転しさらに謎の黒棒がついた画像が出来上がった。
図2.反転してしまった画像
5.考察
図3.出来上がった画像のバイナリデータ
バイナリデータに数値を書き込む前のint型の数値は「0x3FF6D」だった。しかしこのバイナリファイルで対応する数値(図3で赤丸で囲った部分)では「0x6DFF03」になっている。
この問題をGoogle検索で調べたところ、どうやらCPUの処理による問題らしい。
バイナリデータに書き込まれたデータはリトルエンディアンという配置方法でデータが配置されたらしい。リトルエンディアンは数倍とあるデータを転送する際に一バイトずつ上位バイトを下位バイトに埋めていく方式であるらしい。
これを解決するためには上位バイトは上位バイトにそのまま配置するビッグエンディアンという配置方法を使う、もしくは1バイトずつデータを配置していけばいいらしい。
6.参考文献・参考サイト
6.1bmpのバイナリ構造について
プログラミング/BMPファイル仕様/バイナリ構造 - ルーチェ's Homepage:
URL http://www.ruche-home.net/program/bmp/struct#image-data
6.2fopen_s関数やfwrite関数について
MSDN: URL http://msdn.microsoft.com/ja-jp/library/z5hh6ee9.aspx
C言語標準ライブラリ関数ポケットリファレンス:葛西 朝雄、技術評論社、2009
6.3エンディアンについて
バイトオーダ - ビッグエンディアン/リトルエディアン:URL http://www.ertl.jp/~takayuki/readings/info/no05.html
TCO16 Marathon Match Round1 に参加しました。
今日の2時にTCOMM16Round1が終わったということで、自分の戦略をここにまとめておきます。
最終的な戦略
まず貪欲で初期解を作り、それをもとに遺伝的アルゴリズムでランダムで線を入れ替えて(なぜ削除ではなく入れ替えるなのかというとそれは、NP-1本必ず線を引かなければいけないと勘違いしていたからです。)得点を上げていく手法を使いました。
貪欲にも遺伝的アルゴリズムにもそれを評価するためのスコアが必要ですが、それには(分割できた植物のある領域の数)+(残った根の長さ)/(全体の根の長さ)という評価式を用いました。
(分割できた植物のある領域の数)は一本ずつ線を引くと考えて、それから線の上にあるか下にあるかで二分割するのを繰り返して分けました。
根の長さについては深さ優先探索を使い求めました。まずvector<int>rootsから木を構成します。(全体の根の長さ)を求めるにはこの次に、深さ優先探索を使って葉のスコアは0として、親は子のスコアと親と子の間の距離をそのスコアとするというのをすべての植物に対して行います。そしてすべての植物のスコアを足すと全体の長さがわかります。
(残った根の長さ)は深さ優先探索を使って各線について子と親の間に線が通っていたときに、元の子の座標を交点の座標に書きかえて子の子はすべて消すというのを繰り返します。そうすると、根の状態は切り取られた後の状態になるのでさっき全体の根の長さを求めた方法と同じことをやると残った根の長さがわかります。
この評価方法をそのまま使うと、深さ優先探索の再帰のコストが大きくなってしまうため、NPが多いときには探索する深さを制限して使うようにしていました。NPが多いときに使う理由は、NPが多いときには深さを制限してもある程度本当の得点に相関性のあるスコアが得られるからです。またNPが多いときはとくに再帰のコストが多くかかるからです。
その他に考えた戦略
評価式はそのままで山登り法を使った方法
正直これでもある程度うまくいったのですが、途中で遺伝的アルゴリズムを使ってみたくなり使うのをやめました。
評価式はそのままで焼きなまし法と遺伝的アルゴリズムを使った方法
遺伝的アルゴリズムの本に焼きなましと遺伝的アルゴリズムを合わせたハイブリッド手法には様々な利点があると書いてあったため使いました。しかし本をまともに読まず我流で書いたためか確かな効果は得られませんでした。この手法はコンテスト終了直前に書いていたのでパラメーターの調整が間に合わず提出できませんでした。
評価式に円の半径を使って貪欲法を使った方法
植物の根を植物の中心点から四象限に分けて、根の長さから四つの円を書いてそれがどれぐらい削られたかで判定する方法を使いました。これは得点との相関性がないことから最終的には使いませんでした。
反省
序盤にも書いた通りルールを勘違いしていたとというのが本当に悲しいです。次からは問題文をちゃんと読んでおきたいですね。
Exampleの結果だけ見ていて他のテストケースでのTLEを気にしていなかったのも終了後に気づいた反省点です。あと次は時間内にビジュアライザ作りたいと思いました。