Program Specification and Sample Program - PRMU Algorithm Contest 2009

プログラム要求仕様

概要

応募者には、サンプルプログラムに含まれる my_alg.c の関数my_alg_level1()、my_alg_level2()、またはmy_alg_level3() に独自のアルゴリズムを実装し、提出していただきます。

原則 C 言語 (ANSI C) での実装です。実装には、OpenCV-1.0 を利用していただくことができます。C++の使用、そのほかのライブラリの利用については alcon2009(あっと)nanase.comm.eng.osaka-u.ac.jp まで個別に相談して下さい。

応募者が実装する関数 my_alg_level1()、my_alg_level2()、my_alg_level3()のプロトタイプ宣言はそれぞれ以下のようになっています。

object *my_alg_level1(unsigned char *image, unsigned char *mask, int width, int height, int *n_object);
object *my_alg_level2(unsigned char *image, int width, int height, int *n_object);
object *my_alg_level3(unsigned char *image, int width, int height, int *n_object);

image、mask はそれぞれ対象画像とマスク画像、width と height は対象画像の幅と高さで、これらの入力を基に同じ種類の物体がどこにあるかを検出します。また、物体の総数を n_object に代入し、各物体領域を囲む最小矩形の左上座標、右下座標、およびラベルと代表例か否かを表すフラグを object 構造体の配列に格納してそのポインタを返却します。

入力について

応募者に実装してもらう関数の引数のうち、

unsigned char *image (対象画像)
unsigned char *mask (マスク画像、レベル1のみ)
int width (対象画像の幅)
int height (対象画像の高さ)

が関数への入力です。 int型のポインタ変数n_objectは出力に利用されます。

対象画像はwidth×height×3の長さを持つunsigned char型の配列として提供されます。画素は左上から右下へ順番に並んでおり（通常のラスタスキャンの順）、各画素のRGB値がこの順番で格納されています。座標(x, y)のRGB値は以下のように取り出すことができます。

object *my_alg_level1(unsigned char *image, unsigned char *mask, int width, int height, int *n_object)
{
    unsigned char r, g, b;
    int x, y;

    ...

    /* x, yの値の設定 */
    x = ...;
    y = ...;

    ...

    /* x, yの位置のRGB値を取得 */
    r = image[(x+y*width)*3+0];
    g = image[(x+y*width)*3+1];
    b = image[(x+y*width)*3+2];

    ....
}

またレベル1では、長さがwidth×heightのunsigned char型のポインタでマスク画像が提供されます。マスク画像は対象画像と同一のサイズで、物体領域が0、それ以外が255の値を持つ2値画像です。座標(x, y)の値は以下のように取り出すことができます。

object *my_alg_level1(unsigned char *image, unsigned char *mask, int width, int height, int *n_object)
{
    unsigned char m;
    int x, y;

    ...

    /* x, yの値の設定 */
    ...

    /* x, yの位置の値を取得 */
    m = mask[x+y*width];

    ....
}

出力について

実装した関数の出力は、

物体の総数
各物体領域を囲む最小矩形のラベル番号、代表例かどうかを表すフラグ、左上座標、右上座標をメンバに持つ object 型の配列

となります。物体数は関数にポインタ変数として渡される n_object に格納します。

各物体の情報を格納するための構造体 object はサンプルプログラムに含まれる alcon2009.h に以下のように定義されています。

typedef struct object_t {
    int label;  /* ラベル */
    int rep;    /* 代表例か(1:代表例、0:非代表例) */
    int x1, y1; /* 最小矩形の左上座標   */
    int x2, y2; /* 最小矩形の右下座標   */
} object;

labelはラベル番号です。物体の各種類に割り振った0から始まる通し番号を格納してください。
repは各種類の物体の代表例かどうかを表すフラグです。各種類の物体を代表する任意の物体ひとつを選び、その物体のみ1を設定してください。それ以外は0を設定してください。
x1とy1は物体領域を囲む最小矩形の左上座標を格納します。
x2とy2には物体領域を囲む最小矩形の右下座標を格納します。

object型配列の生成から関数の終了までの例を以下に示します。

object *my_alg_level1(unsigned char *image, unsigned char *mask, int width, int height, int *n_object)
{
    /* これは例です。n_objectとobject型の配列が適切に設定されるのであれば */
    /* どのように書いていただいても問題ありません                         */
    ...

    object *obj;

    ...

    *n_object = (物体の総数); /* 物体数の設定 */
    obj = (object *)malloc(*n_object * sizeof(object));

    /* 配列objの各要素を設定 */
    ...

    return obj;
}

サンプルプログラム

レベル1のアルゴリズムを実装したサンプルプログラムはこちらからダウンロードしてください。 UNIX 環境用に文字コードがEUC、圧縮形式が tar.gz のものと Microsoft Windows 環境用に文字コードが Shift-JIS、圧縮形式が ZIP のものを用意しています。（最終更新日：2009/5/11）

alcon2009-1_1-EUC.tar.gz (EUC) (2009/5/11 update)
alcon2009-1_1-SJIS.zip (Shift-JIS) (2009/5/11 update)

alcon2009-1_0-EUC.tar.gz (EUC) (evaluation.cとmy_alg.cにバグ報告あり）

alcon2009-1_0-SJIS.zip (Shift-JIS) (evaluation.cとmy_alg.cにバグ報告あり）

不明な点やバグなどを発見された場合は alcon2009(あっと)nanase.comm.eng.osaka-u.ac.jp までご連絡ください。

コンパイルと実行

サンプルプログラムを展開したディレクトリ内で make コマンドを実行します。

# make

成功すると、alcon2009 というファイルが生成されています。

プログラムのコマンド引数は以下の通りです。

# ./alcon2009 -l {1|2|3} [-e 正解ファイル名] 対象画像名.ppm [マスク画像名.pgm]

-l オプションではレベルを指定します。1、2、3のいずれかを指定してください。
実装したアルゴリズムのスコアを表示する場合は -e オプションを指定し、その後に正解ファイル名を指定してください。サンプルデータには正解ファイル（ファイル名：対象画像名_groundtruth.txt）を用意しています。正解ファイルのフォーマットについては後述します。
対象画像はバイナリ PPM 形式です。
マスク画像はバイナリ PGM 形式です。レベル1の場合のみ指定してください。

プログラムを実行すると、種類ごとに物体を囲む矩形を描画した画像（ファイル名：対象画像名_result.ppm）が生成されます。

例えば、サンプルプログラムに実装されているアルゴリズムをレベル1のサンプルデータlevel1-5.ppmに対して実行し、スコアを表示した場合、以下のように結果が表示され、サンプルデータと同じディレクトリにlevel1-5_result.ppm が生成されます（ただし、以下の例は、出力の説明を行うための例で、実際のlevel1-5.ppmに対するサンプルプログラムの出力とは異なります。また、実際の出力画像には座標の情報は含まれません）。

# ./alcon2009 -l 1 -e level1-5_groundtruth.txt level1-5.ppm level1-5_mask.pgm
入力画像ファイル  : level1-5.ppm
マスク画像ファイル: level1-5_mask.pgm

           抽出矩形                             正解矩形
     左上座標     右下座標   ラベル  ->   左上座標     右下座標  　ラベル  正誤
o (  67,   51) ( 233,  191)    0     -> (  67,   51) ( 233,  191)    0      o
  ( 275,  180) ( 438,  312)    1     -> ( 275,  180) ( 438,  312)    3      x
  (  81,  283) ( 247,  424)    0     -> (  81,  283) ( 247,  424)    0      o
  ( 541,  502) ( 683,  594)    1     -> ( 541,  502) ( 683,  594)    3      x
  ( 104,  593) ( 261,  761)    1     -> ( 104,  593) ( 261,  761)    3      x
o ( 392,  700) ( 508,  856)    1     -> ( 392,  700) ( 508,  856)    0      x
  ( 527,  834) ( 689,  961)    0     -> ( 527,  834) ( 689,  961)    3      x
o ( 610,  420) ( 710,  530)    2     -> (----, ----) (----, ----)    -      x
  (----, ----) (----, ----)    -     -> ( 261,  471) ( 413,  579)    0      x

得点:  21.428571
処理時間: 1.185819 [秒]

出力された各物体に対し、対応すると考えられる正解物体の最小矩形がその種類を表すラベル番号と共に表示されます。出力されたラベル番号がこの正解ラベル番号と同じであれば、正しい結果となります。上の例では、出力画像における左上の2つの赤い矩形に相当する1番と3番のみが正しい結果となります。

出力画像における緑の矩形については、代表例が赤い矩形の代表例と同じ種類の物体であったため、すべて間違いとなります。

また、出力画像中の黄色い矩形のように、出力された物体領域に対し、対応する正解物体領域がない場合、正解には"(---,---) (---,---) -"と表示されます。

さらに、出力画像の真ん中の旗のように領域が抽出されなかった物体については、結果として"(---,---) (---,---) -"、正解として対応する正解物体の情報が表示されます。

得点の出し方の詳細については審査基準を参照して下さい。

アルゴリズム

サンプルプログラムにはlevel1のアルゴリズムが実装されています。このアルゴリズムは、マスク画像を用いて対象画像から物体領域を抽出し、物体領域の円形度に基づいたクラスタリングにより物体の種類を決定します。

サンプルプログラムのアルゴリズムは、まずマスク画像を用いて抽出した対象画像内の物体領域に物体番号を割り振り、物体の総数を数えます。

int **obj_id = (int **)malloc(height*sizeof(int *));
for (i = 0; i < height; i++) obj_idl[i] = (int *)malloc(width*sizeof(int));

/* 物体領域に番号を割り振り、数を数える */
n = assign_id(mask, width, height, obj_id);

必要なメモリを確保してから、各物体領域に対して、面積と周囲長を算出し、これを基に円形度を算出します。

/* 必要な領域の確保 */
area = (int *)malloc(n * sizeof(int));
len  = (double *)malloc(n * sizeof(double));
circ = (double *)malloc(n * sizeof(double));
	
obj  = (object *)malloc(n * sizeof(object));

/* 面積を得る */
calculate_area(obj_id, width, height, n, area);

/* 周囲長を得る */
calculate_length(obj_id, width, height, n, len);

/* 円形度の算出 */
for (i = 0; i < n; i++) {
   circ[i] = 4.0*PI * area[i] / (len[i]*len[i]);
}

得られた円形度に基づきk-means法を適用することで、物体をクラスタリングします。 level1では、物体が2種類であることが与えられているため、k=2とします。出力された各クラスタに含まれる物体が同じ種類の物体となります。よって、クラスタ番号を物体の種類を表すラベルと考え、object構造体のメンバであるlabelに各物体のラベルを格納します。さらに、各種類の物体の代表例を決定します。ここでは、各クラスタ内の物体のうち、物体番号が最も小さいものを代表例としています。

/* k-means法クラスタリング */
k_means(circ, obj, n);
/* クラスタ代表の決定 */
for (i = 0; i < n; i++) obj[i].rep = 0;
for (j = 0; j < NUM_CLASS; j++) {
    for (i = 0; i < n; i++) {
        if (obj[i].label == j) {
            obj[i].rep = 1;
            break;
        }
    }
}

各物体領域を囲む最小矩形を見つけて、object構造体のメンバに格納します。

/* 最小矩形を見つける */
find_rect(obj_id, width, height, n, obj);

以上がサンプルプログラムに実装されているアルゴリズムです。最後に、確保したメモリを解放して関数は終了します。

正解ファイルのフォーマット

正解ファイルのフォーマットは以下の通りです。テスト用の画像を自作してスコアを出力する場合に参考にしてください。

n
x1_1 y1_1 x2_1 y2_1 l_1
x1_2 y1_2 x2_2 y2_2 l_2

...

x1_n y1_n x2_n y2_n l_n

n	画像に含まれる物体の総数
x1_1	物体1の最小矩形の左上 x 座標
y1_1	物体1の最小矩形の左上 y 座標
x2_1	物体1の最小矩形の右下 x 座標
y2_1	物体1の最小矩形の右下 y 座標
l_1	物体1のラベル
x1_2	物体2の最小矩形の左上 x 座標
...	...

お問い合わせは

alcon2009(あっと)nanase.comm.eng.osaka-u.ac.jp

目次