プログラムC

質問

前にも質問したのですがヒルベルト曲線を用いて画像をスキャンするプログラムとビットマップの画像を読み込むプログラムを用いてお互いの座標を関連付けてヒルベルト曲線の座標にビットマップの１画素ずつの値を代入したいのですがどうしてもうまくいかなく質問しました。
前に質問した物はhttp://oshiete1.goo.ne.jp/kotaeru.php3?q=1106704
にあります。ヒルベルトは質問覧にビットマッピはＮＯ２の補足にあります。プログラムを書くと８００字を超えてしまうのでそのようにしました。
ヒルベルトは他に
#include<stdio.h>
int x,y;

int n;
void RUL(int n),DLU(int n),LDR(int n),URD(int n);
main() {
scanf("%d",&n);
printf("#位相%dのヒルベルト曲線\n",n);
x=0; y=0;printf("(%d %d) ",x,y);
RUL(8);
}
void RUL(int n) {
if(n<=0) {return;}
URD(n-1);x=x+1;printf("(%d %d)",x,y);
RUL(n-1);y=y+1;printf("(%d %d)",x,y);
RUL(n-1);x=x-1;printf("(%d %d)",x,y);
DLU(n-1);
}
void DLU(int n) {
if(n<=0) {return;}
LDR(n-1);y=y-1;printf("(%d %d)",x,y);
DLU(n-1);x=x-1;printf("(%d %d)",x,y);
DLU(n-1);y=y+1;printf("(%d %d)",x,y);
RUL(n-1);
}
void LDR(int n) {
if(n<=0) {return;}
DLU(n-1);x=x-1;printf("(%d %d)",x,y);
LDR(n-1);y=y-1;printf("(%d %d)",x,y);
LDR(n-1);x=x+1;printf("(%d %d)",x,y);
URD(n-1);
}
void URD(int n) {
if(n<=0) {return;}
RUL(n-1);y=y+1;printf("(%d %d)",x,y);
URD(n-1);x=x+1;printf("(%d %d)",x,y);
URD(n-1);y=y-1;printf("(%d %d)",x,y);
LDR(n-1);
}
があります。

回答No.2

JaritenCat · ベストアンサー

かなりてこずっているようですが、まずはプログラムの動きをきちんと理解しないと応用は厳しいと思います。
参考まで、BMPファイルを読み込んで、普通のデータとヒルベルト走査したデータを吐き出すサンプル（かなり手抜き）です。
画像データは、1024*1024のWindows標準BMPファイルで、24ビット深度のグレー画像(赤=青=緑)を想定しています。
出力ファイルは、1024*1024の8ビットグレーデータです。raw形式のファイルに対応したビューア(PhotoShopとか)で見れるはずです。

/* BMP画像のヒルベルト曲線走査 (c)2004 JaritenCat */
#include <stdio.h>
#include <stdlib.h>
#define N 10 /* ヒルベルト曲線の基数 2^N */
#define XSIZE (1<<N)
#define YSIZE (1<<N)
#define SIZE (XSIZE*YSIZE)
#define IMAGEFILE "test.bmp" /* 画像サイズは2^N*2^N 24bpp R=G=B(GRAY SCALE) */
#define NORMALFILE "out1.raw"
#define HILBERTFILE "out2.raw"
unsigned char bitimage[SIZE]; /* 画像データ */
unsigned char hilimage[SIZE]; /* 画像データ */
int idx=0; /* hilimage用インデックス */

/* byte*4 → unsigned long 変換(リトルエンディアン) */
unsigned long ctol(unsigned char a, unsigned char b, unsigned char c, unsigned char d) {
return (unsigned long)a|((unsigned long)b<<8)|((unsigned long)c<<16)|((unsigned long)d<<24);
}
/* byte*2 → unsigned short 変換(リトルエンディアン) */
unsigned short ctos(unsigned char a, unsigned char b) {
return (unsigned short)a|((unsigned short)b<<8);
}
/* ヒルベルト走査（再帰） n:ブロックサイズ p:走査パターン x,y:基準点 */
void hilbert(int n, int p, int x, int y) {
if (n>1) {
hilbert(n/2, (p+4)%8, x+(p&1)*(n/2), y+((p>>1)&1)*(n/2));
hilbert(n/2, p, x+((((p>>1)^(p>>2)))&1)*(n/2), y+((p^(p>>2)^1)&1)*(n/2));
hilbert(n/2, p, x+(~p&1)*(n/2), y+(~(p>>1)&1)*(n/2));
hilbert(n/2, 7-p, x+(((p>>1)^(p>>2)^1)&1)*(n/2), y+((p^(p>>2))&1)*(n/2));
} else {
/* ここでヒルベルト走査のidx番目の座標x,y が求まっている */
hilimage[idx]=bitimage[x+y*XSIZE]; idx++;
}
}
/* メインルーチン */
int main(void) {
FILE *fp;
int x,y,c;
unsigned char buf[54]; /* BMPファイル(Windows標準BMP 24bpp パレットなし)のヘッダ用 */
/* BMPファイルを開く */
if ((fp=fopen(IMAGEFILE,"rb"))==NULL) { printf(IMAGEFILE" open error\n"); return -1; }
if (fread(buf,sizeof(unsigned char),54,fp) != 54) { printf("header read error\n"); fclose(fp); return -1; }
if (ctos(buf[28],buf[29])!=24) { printf("bit count error\n"); fclose(fp); return -1; }
if (ctol(buf[18],buf[19],buf[20],buf[21])!=XSIZE) { printf("width error\n"); fclose(fp); return -1; }
if (ctol(buf[22],buf[23],buf[24],buf[25])!=YSIZE) { printf("height error\n"); fclose(fp); return -1; }
/* ファイルから画像データ(bitimage)へ変換する */
for (y=0; y<YSIZE; y++) {
for (x=0; x<XSIZE; x++) {
if ((c=fgetc(fp))==EOF) {printf(IMAGEFILE" data read error\n"); fclose(fp); return -1; }
bitimage[x+(YSIZE-1-y)*XSIZE]=c; /* グレースケールを想定しているので赤をデータとする */
fgetc(fp); fgetc(fp); /* 緑、青を読み飛ばす */
}
}
fclose(fp);
/* 画像データ書き出し */
if ((fp=fopen(NORMALFILE,"wb"))==NULL) { printf(NORMALFILE" open error\n"); return -1; }
if (fwrite(bitimage, sizeof(unsigned char), SIZE, fp) != SIZE) { printf(NORMALFILE" write error\n"); fclose(fp); return -1; }
fclose(fp);
/* ヒルベルト走査 */
hilbert(XSIZE,0,0,0);
if (idx != SIZE) { printf("hilbert scan error\n"); return -1; }
/* 走査データ書き出し */
if ((fp=fopen(HILBERTFILE,"wb"))==NULL) { printf(HILBERTFILE" open error\n"); return -1; }
if (fwrite(hilimage, sizeof(unsigned char), SIZE, fp) != SIZE) { printf(HILBERTFILE" write error\n"); fclose(fp); return -1; }
fclose(fp);

return 0;
}

お礼

JaritenCatさんに聞きたいのですが上のプログラムをどのようにかえればいいのですか＞＜？ヒルベルト走査したデータを吐き出したものとBMPの座標を関連ずけるには。。。
ポインタを使えばうまくいきますでしょうか？

補足

ありがとうございます。はいかなりてこずっております・・・。もうお手上げ状態なのです。
ＲＥＤＨＡＴを使っておりＧＩＭＰだとビューアでみれませんでした＞＜。ファイルはできていますが。

回答No.7

JaritenCat

画像の見方その２(pgmファイルにする方法)

(1)header.txt というファイルを作ってください。内容は、

P5
1024
1024
255

です。(各行に、識別子、xサイズ、yサイズ、色サイズ)

(2)画像データにヘッダを付けて新しいファイルを作ります。
例えば、
DOS窓なら、 copy /b header.txt +out2.raw out2.pgm
Unixなら、 cat header.txt out2.raw > out2.pgm

この out2.pgm がPGM形式の画像データです。
gimpでも対応しているはずです。

お礼

ありがとうございます。試してみます。
質問したｂｍｐとヒルベルトを関連付けて１次元配列で表せました★

回答No.6

JaritenCat

＞やはり画像の座標とヒルベルトスキャンの座標を関連付けでヒルベルトスキャンの順番のピクセルの値を１次元配列にしてそれを圧縮しないと駄目みたいです・・・。

ANo.2のプログラムでは、hilimageがその１次元配列ですが・・・これでは駄目ですか？（それをファイルに書き出したのがout2.rawです）

BMP画像→ラスタスキャン(bitimage[])→ヒルベルトスキャン(hilimage[])の逆をしたいのであれば、hilbert関数の中の
hilimage[idx]=bitimage[x+y*XSIZE]; idx++;
を逆にした関数を新しく作って呼び出せばいいでしょう。
bitimage2[idx2]=hilimage[x+y*XSIZE]; idx2++;
という風に。
これをBMPファイルにしたければ、ヘッダを付けてデータを３回ずつ書き出すだけです。(Y方向に注意)

ちなみに、bzip2方式で圧縮したのは、ANo.3のout.tbzです。

補足

out2.rawというのは１次元配列のファイルだったのですか
＞＜。ファイルでなく１次元配列の中身をみたいのですがhilimageの1次元配列を・・・。
bitimage2[idx2]=hilimage[x+y*XSIZE]; idx2++;
にかえたのですが
hilbert scan errorとでてしまいます。
アドバイスお願い致します。

回答No.5

JaritenCat

＞どのようにしたら見れますか？

WindowsでしたらフリーソフトのIrfanViewが対応しているようです。
http://www8.plala.or.jp/kusutaku/
画像サイズを1024x1024、ヘッダサイズ0、8BPPで開いてください。
out1.rawは普通に見えるはずです。当たり前の事ですが、IrfanViewはヒルベルトスキャンには対応してませんのでout2.rawはぐちゃぐちゃに見えます。

お礼

やはり画像の座標とヒルベルトスキャンの座標を関連付けでヒルベルトスキャンの順番のピクセルの値を１次元配列にしてそれを圧縮しないと駄目みたいです・・・。
画像がみれないので・・・。一度質問を締め切ってまた質問させていただきます。

補足

そうですかあ＞＜。out2.rawをbzip2にかけそれを添付メールなどして解凍しout2.rawを表示させたいのですが・・・。プログラムはどんな感じになりますでしょうか？

回答No.4

JaritenCat

＞rawだとプロパティーをみると種類が未知の種別で開けません。

当然です。ここで言っているrawファイルは、最近はやりのデジカメrawファイルではなく、ヘッダーなしの生データです。Adobe Photoshopが汎用フォーマット(*.RAW)と言っているものです。ヘッダがないのでプロパティを表示させようとしてもファイル種別を判別できるわけがありません。ファイルサイズを見れば分かると思いますが、1024*1024バイトとまったく同じです。

out1.raw は画像をラスタスキャンしたデータです。
画像の左上から右下に向かって、左→右を上→下の順に走査しています。
out2.raw は画像をヒルベルトスキャンしたデータです。
画像の左上から右上に向かって、ヒルベルト曲線の順に走査しています。

補足

朝から回答ありがとうございます。どのようにしたら見れますか？拡張子を*.bmpとしたら未知の種別ではなくなったんですがみれませんでした。

回答No.3

JaritenCat

ANo.2のコメントへの回答です。
＞ヒルベルト走査したデータを吐き出したものとBMPの座標を関連ずけるには。。。

関連付ける必要がありますか？？
out1.raw(bitimage[])は原画を普通にスキャンした生の画像データ(1024*1024=1048576バイト)ですし、out2.raw(hilimage[])はヒルベルトスキャンした画像データです。
両者のファイルを別の圧縮プログラムで読み込んで圧縮後のデータサイズを比較すればいいのでは？
本当にヒルベルトスキャンの座標列が必要であれば、前の質問で回答したとおりです。

ちょっと興味があったのでWindowsでよく使われるアーカイバを使って手持ちの画像を圧縮比較してみました。（圧縮ファイルにはヘッダや誤り符号などが入っているので、単純にデータサイズの比較にはなっていません）
out1.raw　　1,048,576　　out2.raw　1,048,576
out1.gca　　　567,435　　out2.gca　　591,466
out1.bza　　　637,553　　out2.bza　　668,852
out1.tbz　　　637,569　　out2.tbz　　669,014
out1.rar　　　673,723　　out2.rar　　752,542
out1.cab　　　800,716　　out2.cab　　786,455
out1.lzh　　　804,140　　out2.lzh　　787,234
out1.yz1　　　763,410　　out2.yz1　　789,967
out1.zip　　　801,776　　out2.zip　　789,905

辞書式アルゴリズムを使ったやつはヒルベルトの方が若干サイズが小さくなっていますが、より高圧縮アルゴリズムだと逆にサイズが大きくなっている感じです。ちなみに、GCAがBlockSorting(BWT)+RangeEncoder(エントロピー符号化)を使っているらしいです。見事な圧縮率です。

お礼

rawだとプロパティーをみると種類が未知の種別で開けません。

補足

上の結果はＮＯ２のプログラムの結果から出したものなのでしょうか？
僕がやろうとしていたものはヒルベルトの座標列[x,y]をピクセルデータimg[x][y][k]に代入したいんです。kはrgbの値です。
0[0,0]
1[0,1]
2[1,1]
・
・
・
をbuf[0]=img[0][0][k],buf=img[0][1][k],buf[2]=img[1][1][k]・・・というような１次元配列で表示させこれに適当な名前をつけこれを圧縮アルゴリズムにかけたいのです。
ＮＯ２のプログラムと同じ様な結果が出ますかね？
JaritenCatさんはすごいですね★専門家みたいです！

回答No.1

ffffff_2004

プログラムはいいですから、何をしたいのかが、
わかりません。整理してもらえますか？

そもそも、ヒルベルトってなんですか？
ヒルベルトである必要ありますか？
もう少し、問題を単純化して考える必要があると思います。要は、座標変換をしたいんですか？

全てを説明できるようになれば、おのずと解決方法が
見えてくるかもしれませんね。

補足

ヒルベルトは下記を見てください。http://homepage1.nifty.com/mstak/Program/Java-12/Fractal/Hilbert.html
したいことはＢＭＰ画像を２次元相関を保ったまま１次元配列に変換できるヒルベルトスキャンとＢＷＴ変換とエントロピー符号化を用いた圧縮方式を組み合わせどれくらい圧縮できるかを調べたいのです。それでヒルベルトスキャンの方がわからなくて質問しました。もう一つの方は大丈夫なのですが・・・。