プログラミングC
第13回 演習問題


A問題(50点)

演習問題1(2次元配列の動的確保と文字列)

(提出ファイル名: prog01.c)

ハンドアウトLec13-6 (p.145)のサンプルプログラムlec13-4.cは2次元配列を動的に確保する方法の一例である。この方法はハンドアウトにあるとおり、行によって長さが違う場合にも応用ができる。この特徴を使って、各行に単語を一つづつ格納し、かつ各行の長さはその単語の長さちょうどになるような2次元配列を作成するプログラムを完成させよ。

以下に、このプログラムを完成させる際の考え方を列挙する

  for(i = 0; i < TATE; i++){
    printf("Word #%d (Length: %d): %s\n", i+1, strlen(arr[i]), arr[i]);
  }

実行例:
% ./a.out
Input word #1: to
Input word #2: Advance
Input word #3: Knowledge
Input word #4: for
Input word #5: Humanity
Word #1 (Length: 2): to
Word #2 (Length: 7): Advance
Word #3 (Length: 9): Knowledge
Word #4 (Length: 3): for
Word #5 (Length: 8): Humanity
%

ハンドアウトに掲載されているサンプルプログラムでは、malloc関数の戻り値を、
arr[i] = (int *)malloc(yoko * sizeof(int));
のように代入先の変数型に合うようにキャストしている。 一方、lec13-4.cの中ではそのようなキャストを行わず、
arr[i] = malloc(sizeof(int)*yoko);
のようにそのまま代入している。
malloc関数のプロトタイプ宣言を確認(コマンドman mallocで確認できる)すると、
void *malloc(size_t size);
となっている。void *型は、明示的にキャストをする必要なく任意のポインタ型に変換することができるので、本来はハンドアウトの掲載例のようなキャストを行う必要はなく、lec13-4.cのように書いて問題ない。
ハンドアウトの掲載例のような明示的なキャストを行うことの利点は、malloc関数で確保しようとしている領域の大きさが適切かどうかをコンパイラが確認し、問題がある(意図しない動作をしたり、セキュリティホールの原因となることもある)場合は警告が出せるようになることである。このようなプログラムの書き方についての詳細はコンピュータのセキュリティに関する情報を取りまとめているJPCERT/CCの記事などが参考になる。

B問題(50点)

演習問題2

最初に、ハンドアウト lec13-11,12 (p146) 中のプログラムlec13-7.cをコピーし、lec13-13 (p147) に示されたコンパイルオプションをつけた場合に例示された通りの動作になることを確認せよ。

まず、以下のコマンドで画像データを自分のディレクトリにコピーすること。

% cp /home/course/prog1/public_html/2022/ex/ex13/pbms/* .

次にlec13-7.cを以下のようにコンパイルオプションでマクロ定義を変えてコンパイルし、Lec13-13に例示されている四種類の実行ファイルを生成する。

% gcc lec13-7.c -DINV -o inv
% gcc lec13-7.c -DINV -DROTL -o invrotl
% gcc lec13-7.c -DFLIPLR -o fliplr
% gcc lec13-7.c -DINV -DFLIPLR -DROTL -o invfliplrrotl

コピーした画像データを使って、Lec13-13に載っている通りの動作をするかを確認する。

% cat p1.pbm | ./inv | display - 
% cat p1.pbm | ./invrotl | display - 
% cat p1.pbm | ./fliplr | display - 
% cat p1.pbm | ./invfliplrrotl | display - 

確認が完了したら、以下の説明をよく読んで問題に取り組むこと。

テンプレートprog02_template.clec13-7.cを再設計し、メモリの確保と画像データの読み込みを別々の関数に分離している。また、lec13-7.cが備えていた画像処理の機能に代えて、読み込んだ画像に正方形を追加で描画してから出力する機能を持たせている。ただし、いくつかの関数は未完成のままになっている。このテンプレートを元に、プログラムを完成させよ。

(提出ファイル名: prog02.c)

各関数の内容は以下のとおりである。未完成、完成の別も表示している。未完成の関数は完成させること。完成済みの関数は変更してはならない。

char **pbm_alloc(int x, int y)
(未完成)大きさx×yのchar型の2次元配列を確保しそのアドレスを返す。領域の確保に失敗したら、 それまでにこの関数で確保した領域を解放し、NULLを返す。
void pbm_free(char **pbm, int x, int y)
(完成済み)大きさx×yの2次元配列pbmを解放する。引数 x,y はここでは使用されていないが、他の関数と整合性を とるために入れてある。
void pbm_write(char **pbm, int x, int y)
(完成済み)大きさx×yのchar型の2次元配列をPBM画像として出力する。2次元配列の要素には'1'か'0'(それぞれ黒、白の画素に対応)が 入っていると仮定している。
char **pbm_read(int *x, int *y)
(未完成)この関数はまず、標準入力から入力されたPBM形式のヘッダと画像の大きさを読み取り、 その画像を格納できるchar型の2次元配列を確保する。
続いて標準入力から入力される画素値を読み取り、確保した2次元配列に格納する。
PBM形式では、画像データ部分に余分な空行、空白を入れてよいことになっている。このような場合でも scanf関数のフォーマット指示子" %c"("(空白文字)%c", %cの前にスペースを入れる) を用いることでこれを読み飛ばせるので、この通り実装して空行、空白の有無に関わらず正しくデータを読み取れるようにすること。
最後に入力されたx,yのポインタが示す変数に画像の横幅と高さを代入し、 確保した2次元配列のポインタを返す。
この関数を作る際、画像の入力の処理はlec13-7.cを参考にすると良いが、 pbm_read関数内での2次元配列の確保はmalloc関数を直接呼び出さず、 上のpbm_alloc関数を用いて関数を作成すること。
また、読み込みに失敗した場合は、エラーメッセージを表示せず、 それまでにこの関数で確保したメモリ領域を解放し、NULLを返すようにせよ。
void pbm_square(char **pbm, int x, int y, int d, char col)
(未完成)大きさx×yの画像pbmに半辺長(一辺の長さの半分)dの正方形をcolで指定された色('1'または'0'、それぞれマクロでBLACK、WHITEと定義されている)で描画する。
int main(int argc, char *argv[])
(完成済み)上の関数を使い、データ処理の全体制御を行う。コマンドライン引数としてpbm_square関数で描画する正方形のサイズを、読み込んだ画像のサイズに対する比率(0-1の範囲)で受け取る。
lec13-7.cと同様に、マクロ定義によってpbm_square関数による描画色を黒・白のいずれかにするかをコンパイルオプションで選択できるようになっている。

テンプレートはそのままコンパイルが出来るように作ってあるので、ダウンロードしたらまずコンパイルしてみとよい。ただし、未完成の関数を埋めない限り、例の通りに動作するわけではない。テンプレートを提出ファイル名prog02.cでコピーして、変更を進めること。変更の際は、少しずつ処理を足しながらこまめにコンパイルしていくことで、文法の誤りを早く見つけることが出来るはずである。

以下に、コンパイルと実行の例を示す。なお、この実行例の中で使われている./invは、冒頭でlec13-7.cをコンパイルして生成したものである。

コンパイル・実行例:
% gcc prog02.c -DWHSQUARE -o whsquare
% gcc prog02.c -DBKSQUARE -o bksquare
% cat p1.pbm | ./bksquare 0.7 | display -



% cat p1.pbm | ./inv | ./whsquare 0.5 | display -


%

確認のため、他の画像でも同様に実行してみること。


演習問題3

(提出ファイル名: prog03.c)

問題2を応用し、簡単な画像処理を行なうプログラムを作成する。 下記に、この問題で使用するヘッダファイル、マクロ定数、関数のプロトタイプ 宣言を示す。関数定義は、問題2までの関数の中から必要なものを コピーして使用する。

#include <stdio.h>
#include <stdlib.h>

#define BLACK '1'
#define WHITE '0'

char **pbm_alloc(int, int);
void   pbm_free(char **,int, int);
char **pbm_read(int *, int *);
void   pbm_write(char **, int, int);
本問題では白黒2値画像に対してモルフォロジと呼ばれる処理の一部を作成する。 これから作る処理は、画像上の画素一つを取り出してP(x,y)とするとき、 その周辺の画素値を読み出し、それらの値に対してある演算を行い。 その結果を新たな画像の画素P'(x,y)とするものである。 この処理は、画像上の画素すべてに対して1回ずつ行う。 下図は注目する画素の「周辺」の定義を、注目する画素の上下左右としたときの説明図である。

このとき、大きさW×Hの画像内の点P(x,y)に注目するとすると、 座標値x=0となる点、x=W-1となる点、y=0となる点、y=H-1となる点の 周辺画素は画像をはみ出したところに位置してしまう。 画像の上下左右の端の画素に注目する際、参照できない周辺画素は、 その注目する画素の値を用いることとする。

注目している画素とその周辺の画素の値を計算して、新たな画像の画素の値を決めるわけだが、 この計算方法によって画像処理の性質が決まる。ここでは、モルフォロジ処理の中から、黒い点に対しての2種類の処理をつくろう。

名前発音意味操作
erosionエロージョン収縮注目する画素とその周辺の画素が全て黒なら結果を黒に、それ以外は白にする
dilationダイレーション膨張注目する画素とその周辺の画素が一つでも黒なら結果を黒に、それ以外は白にする

エロージョンは黒い線や領域を細く,ダイレーションは太くする効果がある。白黒2値画像に2つの処理を適用した結果を下に示す。

エロージョン 元画像 ダイレーション

それでは、実際にこれらの処理を行う関数を作成していく。 関数名には動詞のerodeとdilateを使ったほうが良いので以下のように定義する。

char **pbm_erode(char **pbm, int x, int y);  /* エロージョンを行う関数 */
char **pbm_dilate(char **pbm, int x, int y); /* ダイレーションを行う関数 */
pbmは入力する画像の配列。x,yは画像の横幅と高さである。 関数の中で入力する画像と同じ大きさの2次元配列をpbm_alloc関数で確保し、 その配列に結果を書き込む。操作を行ったあとは新しい配列のポインタを返すように作る。 各関数の中身は以下のように作成せよ。

画像の端の処理、 ループの範囲の設定(横は0からx-1、縦は0からy-1の範囲である)、 論理演算等を間違えやすいので気をつけること。

作成した関数を呼び出すようにしたmain関数を示すので、これを用いよ。 #elifは、#else#ifdefが複合したもので、 C言語での「else if」に相当する。 ここに作成した2つの関数を入れ、コンパイル時にERODEかDILATEを定義し、 どちらの関数を呼ぶかを決定する。

int main(){
  char **pbm1, **pbm2;
  int ix,iy;

  pbm1 = pbm_read(&ix,&iy);
  if(pbm1==NULL){
    fprintf(stderr,"Invalid image format.");
    exit(1);
  }

  #ifdef ERODE
  pbm2=pbm_erode(pbm1,ix,iy);
  pbm_free(pbm1,ix,iy);
  #elif DILATE
  pbm2=pbm_dilate(pbm1,ix,iy);
  pbm_free(pbm1,ix,iy);
  #else
  pbm2=pbm1;
  #endif

  /* 画像を書きだす */
  pbm_write(pbm2,ix,iy);
  /* 画像領域の解放 */
  pbm_free(pbm2,ix,iy);
  return 0;
}
最後にコンパイルと実行の例を示す。-Dオプションは定義するマクロ名の指定、 -oオプションは生成されるファイルの名前を指定するオプションである。
実行例:
%  gcc prog03.c -DERODE -o erode 
%  gcc prog03.c -DDILATE -o dilate 
%  cat p1.pbm | ./erode | display - 

%  cat p1.pbm | ./dilate | display - 

Extra問題

演習問題4

(提出ファイル名: prog04.c)

この問題は、問題3の続きである。

問題3で作成したエロージョンとダイレーションの処理は、複数回繰り返すことで より効果を大きく出すことができる。 また、エロージョンの後にダイレーションを行うとオープニングという演算になり、 孤立点や細い線の除去ができる。逆、つまり、ダイレーションの後にエロージョンを行うと クロージングという演算になり、不連続な点の接続と穴埋めができる。

以下に、例を挙げる

% cat ryo.pbm | ./erode | ./erode | display - % cat ryo.pbm | ./dilate | ./dilate | display -
% cat ryo.pbm | ./erode | ./dilate | display - % cat ryo.pbm | ./dilate | ./erode | display -

エロージョンとダイレーションを繰り返せば、白黒画像の画質をいろいろと調整することができるが、 コマンドの連結で表現するのは少し大変である。そこで、コマンドライン引数でエロージョンと ダイレーションの処理をどの順序で行うのかを与えることにしよう。ついでに、コマンドライン引数に ファイル名が与えられたら、標準入力ではなく、そのファイルから画像データを取得するようにする。 例えば、実行ファイル名をmorphとして以下のような利用方法を想定する。

実行例:
% ./morph - ryo.pbm | display -

% ./morph -eeeddd ryo.pbm | display -

% cat ryo.pbm | ./morph -dddddeeeee | display -

% ./morph ryo.pbm
Error: Invalid operation 'r'
Usage: ./morph -[ed...] [filename]
% ./morph -cde ryo.pbm
Error: Invalid operation 'c'
実行ファイル名の後に、第1引数としてハイフンの後にeとdで構成された文字列を与える。これが、eがエロージョン、 dがダイレーションの処理を行うことを表す。ハイフンのみの場合は、処理をせずに入力画像を そのまま出力する。また、第2引数として文字列が存在すれば、 それをファイル名として画像を読み込むようにする。出力は前回までと変わらず、標準出力に 出力することとする。以下のリストを参考にして、プログラムを完成させよ。
// プロトタイプ宣言とmainのおおよその流れ
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BLACK '1'
#define WHITE '0'

char **pbm_alloc(int, int);
void   pbm_free(char **,int, int);
void   pbm_write(char **, int, int);
char **pbm_read(FILE *, int *x, int *y); /* 要変更 */
char **pbm_dilate(char **pbm, int x, int y);
char **pbm_erode(char **pbm, int x, int y);
//(外部変数は使用しない)

int main(int argc, char *argv[])
{
//  (変数宣言)

//  (コマンドライン解析)

//  (行うべき処理が指定されていない場合はエラー)

//  (ファイルが指定されていない場合はstdinを、それ以外はファイルをopenし
//   ファイルポインタを得て、pbm_read関数の引数とする)

//  (指定された処理の実行:複数指定された場合は処理の繰返し。
//   pbm_dilate, pbm_erode関数を繰り返し呼ぶと、メモリの解放が必要になる。)

//  (最後に結果の出力)

//  (メモリの解放)

  return 0;
}

//(各関数の記述)