Greedy Searchのプログラムについて

質問

現在、Greedy　Searchについてプログラムを組み、Linuxで実行をしていますが、セグメントエラーが発生します。
配列数の不足によるものかと思い、配列の数を1000に増やして宣言したりしましたが、結果は同じになります。
何度か見直しても原因が発見できないので、ヒント、アドバイスをいただけたら幸いです。

#define SRC_X_SIZE 352 入力画像縦サイズ　
#define SRC_Y_SIZE 288 入力画像横サイズ

#define MB_SIZE 16 マクロブロックサイズ
#define MB_X_NUM 22 TB number (SRC_X_SIZE/TB_X_SIZE)
#define MB_Y_NUM 18 TB number (SRC_Y_SIZE/TB_Y_SIZE)

#define SW_SIZE 7 探索窓サイズ

#include "includes.h"
/*===============================================================
routine : FullSearch
return val : int
input par : float *premap
float *crtmap
float *vecy
float *vecx
function : full search
===============================================================*/
int fullSearch(float *premap, float *crtmap, float *vecy, float *vecx)
{
double sum;
double min[100];
register int i, j, k, m, n, x, y, xx, yy;
int ma[100],na[100],check[1000][1000];
for (y = 0, yy = 0; y < SRC_Y_SIZE; y += MB_SIZE, yy++) {
for (x = 0, xx = 0; x < SRC_X_SIZE; x += MB_SIZE, xx++) {
ma[k],na[k]=0;
min[k] = DBL_MAX;
k=0;
check[m][n]=0;
do{
k++;
/*探索範囲*/
for (n = -SW_SIZE + 6 + na[k]; n <= SW_SIZE - 6 + na[k]; n += 1)
for (m = -SW_SIZE + 6 + ma[k]; m <= SW_SIZE - 6 + ma[k]; m += 1) {
/*既にチェックした座標かどうかの確認*/
if(check[m][n]==0)
{
/*画像端部の処理*/
if ((y + n < 0) || (x + m < 0) ||
(SRC_Y_SIZE < y + n + MB_SIZE - 1) ||
(SRC_X_SIZE < x + m + MB_SIZE - 1)) continue;
/*誤差の計算*/
sum = 0.0;
for (j = 0; j < MB_SIZE; j++)
for (i = 0; i < MB_SIZE; i++) {
sum += fabs(crtmap[(y + j)*SRC_X_SIZE + (x + i)] -
premap[(y + n + j)*SRC_X_SIZE + (x + m + i)]);
}
/*動きベクトルの更新*/
if (sum < min[k]) {
min[k] = sum;
na[k] = n;
ma[k] = m;
}
check[m][n] = 1;
}
}
/*前段階の最小値と比較*/
if(min[k-1] <= min[k]){
na[k] = na[k-1];
ma[k] = ma[k-1];
}
}while((na[k] != na[k-1]) && (ma[k] != ma[k-1])); /*前段階の座標と一致するまで処
理を繰り返す*/
vecy[yy*MB_X_NUM + xx] = na[k];
vecx[yy*MB_X_NUM + xx] = ma[k];
}
}
return 0;
}

回答No.3

kmee · ベストアンサー

C言語は
・基本的に書いてある順番に実行されます。
・初期化していない変数には何が入っているか不定です。
・配列の添字が宣言の範囲内かどうかのチェックはしません。
等の特徴があります。

> ma[k],na[k]=0;
> min[k] = DBL_MAX;
> k=0;

数学ではよく見かける表現ですが、プログラムとしては問題です。
この「k=0」以前にkの値を設定している箇所がありません。そのため、これ以前のkには何が入っているか不定です。 -7かもしれないし573474かもしれない。
記述した順番に実行されるので、「ma[k],na[k]=0;」「min[k] = DBL_MAX;」のkはその不定な値がそのまま使われます。上の-7だった場合は「ma[-7],na[-7]=0;」「min[-7] = DBL_MAX;」です。
ここで「配列の範囲外」とエラーになればまだわかりやすいのですが、Cではそのチェックをしません。なにくわぬ顔で実行しようとします。そしてたまたま動作してしまうこともありますが、大抵はSegmentation Faultが発生します。

> check[m][n]=0;
も同様。この時点でmもnも値が入っていません。

それから、
> ma[k],na[k]=0;
ですが、C言語には「カンマ演算子」というのがあります。これは、カンマで区切られた式を順番に評価する(そして、最後に評価した値を返す)というものです。上の式は
・ma[k] を評価
・na[k] =0 を評価(して、式の値である0を返す)
となります。 ma[k]=0の意味はありません。

> do{
> k++;
ここでも、場合によっては k>=100となる可能性があります。na[k],ma[k],min[k]の範囲外です。自前でエラーチェックするべきです。
/* もっとも、中を見ると、直前の値を使うだけですから、添字を工夫すれば na[2],ma[2],min[2] で十分です。 */

思ったのですが
na[k]=0
check[m][n]=0
って
na[k]=0 (すべてのkについて)
check[m][n]=0(すべての m,nについて)
の意味でつかってませんか?だとしたら、Cにはそんな機能はありません。ループを使って一つずつ代入してください。

お礼

自己解決できました。回答ありがとうございました。

回答No.4

kmee

あと、既に指摘のある#defineですが

> #define SRC_X_SIZE 352 入力画像縦サイズ　

「他から持ってきた」とありますが、そのファイルでもこうなっているのですか?
それとも、ここに書いたときにコメントを付けたしたのですか?
前者なら「352 入力画像縦サイズ」がSRC_X_SIZEマクロの値になります。

回答No.2

Tacosan

「#includeの部分から25行下の部分」?
#include から 25行下は「/*探索範囲*/」の次の
for (n = -SW_SIZE + 6 + na[k]; n <= SW_SIZE - 6 + na[k]; n += 1)
だけど, ここで k を初期化してる?

for (x = 0, xx = 0; x < SRC_X_SIZE; x += MB_SIZE, xx++) {
の次の行,
ma[k],na[k]=0;
の時点では k は初期化されてないよね.
あと, この文で ma[k] って何か意味あるの?

補足

ma[k],na[k]=0;　の次の次の行でk=0;としました。
もしかしたらそれ以前にkを初期化しないといけないのでしょうか・・・？
ma[k],na[k]は一回の探索ごとに、探索範囲の最小値であった部分の座標を格納し、次の探索範囲の決定のために使用しています。

回答No.1

Tacosan

#define は変.
あと, fullSearch の中で k はいつ初期化してるの?

greedy search なのに「fullSearch」というのも謎だが....

お礼

自己解決できました。回答ありがとうございました。

補足

#defineですが、本文中の固有値の説明のため、他の関数部分から引っ張ってきたものです。無視してください。
また、フルサーチとなっている部分はもともとフルサーチのプログラムだったものを直したものなので、そう記述してあります。
ややこしくなってしまい、申し訳ないです。
kは一応#includeの部分から25行下の部分で初期化しているつもりです。