5 パターン認識 void clustering—using—NNmethod( ) double min—distance, distance; だ距離に関する変数 * / mt y, x, 1 , J; だ制御変数など intthreshold; だ同一のクラスタ内に含める距離の最大値 * / だ NN(Nearest Neighbour 法によるクラスタリングを行う * / 111 lnt 1 れ ln char str[10] ; do { だ最も近いクラスタの番号 * / だ作業用文字列 だ threshold を変えながら何度か試す printf("NN 法によって点列をクラスタリングします . vn"); printf(" しきい値 ( クラスタの半径 ) : " ) ; scanf("%d" &threshold); printf(" データを分類してクラスタを形成し , 結果を¥ n " ) ; printf(" 画像として作成しています . *n"); だ image2[y][x] の初期化 * / x_size2 = x_sizel; y_size2 = y_sizel; for ( y = 0 ; y く y_size2; y + + ) for ( x = 0 ; x く x_sizeX x + 十 ) image2[y][x] = imagel[y][x] ; /*No. 0 の点を No. 0 のクラスタ代表点に設定する * / num clstr = 0 ; for ( i = 0 ; i く 2 ; i + + ) / ☆クラスタの総数 - 1 ☆ / center—clstr[num_clstr][i] = points [0][i] ; draw—a—circle( points[()][()] , points[()][l] , threshold ) ; draw-a-circle( points[0] 回 , points[0][1] , 5 ) ; point—cIstr[0] = 0 ; num ClStr 十十 ; だ No. 1 から No. num_pnts-l までの点を分類する * / for ( i = 1 ; i < num_pnts; i 十 + ) { だ最も近いクラスタ :No. min_num と距離 :min_distance * / min distance = 10000.0 ; for (j = 0 ; j < num_clstr; j 十十 ) { distance = calc—distance( points[i][()] , points[i][l] , center-clstr[j] 回 , center-clstr[j][l]); if ( distance く min distance ) { if ( min—distance く threshold ) { mm_num = 」 ; min distance = distance;

118 5 パターン認識 だクラスタ中心が移動したかどうかのチェック * / radius clstr[i] = (int)distance; if ( distance > radius clstr[i]) points[j][0] , points[j][l]); center clstr[i][()] , center_clstr[i][l] , distance = calc distance( if ( point—clstr[j] = for (j = 0 ; j く num_pnts; j + + ) { for ( i = 0 ; i く num clstr; i + + ) { / * 各クラスタの意味上の半径を求める * / center—clstr[i][l] = (int)( sum—y / sum—number ) ; center clstr[i][O] = (int)( sum_x / sum_number ) ; sum—y = sum—y 十 points[j][l] ; sum—x = sum—x 十 points[j][()] ; sum_number = sum_number 十 1.0 ; if ( point—clstr[j] = for (j = 0 ; j く num_pnts; j + + ) { sum_number = 0.0 ; sum—y = 0.0 ; sum x = 0.0 ; for ( i = 0 ; i く num_clstr; i + + ) { / * 各クラスタの代表点を修正する point clstr[i] = mm_num; だ No. i の点をクラスタ No. min_num へ属させる * / for ( y = 0 ; y く y_size2; y + + ) x_size2 = x_sizel ; y_size2 = y_size 1 ; だ image2[y][x] の初期化 * / if ( finish = = 1 ) { だ処理終了 * / if ( distance > 1.0 ) finish = 0 ; だ許容誤差 = 1.0 * / center—clstr[i][o] , center-clstr[i][l]); init_cntr cIstr[i][O] , init_cntr_clstr[i][l] , distance = calc distance( for ( i = 0 ; i く num_clstr; i + + ) { finish = 1 ;

4 画像の圧縮符号化法 scanf("%d" &K number); } while ( K—number く 8 Ⅱ K_number > MAX CLUSTERS ) ; だ仮代表べクトルの設定 * / for ( i = 0 ; i く K—number; i + + ) { x = random int( x block ) ; y = random—int( y—block ) ; for ( j = 0 ; j く DIMENSION; j + + ) { main-vector[i][j] = vector[y][x] 阯 / * K - 平均法によってべクトルのクラスタリングを行う * / finish = 0 ; counter = 0 ; while ( ! finish ) { counter 十十 ; printf("%d 回目のクラスタリング中です . ¥Ⅱ " , counter ) ; / * クラスタの初期代表点への代人 * / for ( i = 0 ; i < K number; i + + ) { for ( j = 0 ; j < DIMENSION; j + + ) init_main—vector[i] = main_vector[i] [j] ; だ各プロックの所属クラスタ番号の初期化 * / for ( y = 0 ; y く y_block; y + + ) for ( x = 0 ; x < x block; x + + ) cluster[y][x] = だ各点の所属クラスタを決定する * / for ( y = 0 ; y < y_block; y + + ) { for ( x = 0 ; x く x_block; x + + ) { だ各クラスタ代表点との距離を求める * / min—distance = 255 * 255 * DIMENSION; for ( i = 0 ; i く K number; i + + ) { distance = calc distance( y, x, i ) ; if ( distance < min distance){ min distance = distance; mm_num = 1 ; for ( i = 0 ; i く K_number; i + + ) { だ各クラスタの代表点を修正する * / cluster[y][x] = min_num; だ [y][x]7' ロックをクラスタ No. min_num ー、属させる * / 91

5 パターン認識 int radius_clstr[MAX PNTS] ; / * クラスタの意味上の半径 * / 117 int finish; int counter; / * 処理終了に関するフラグ * / だ処理回数 printf ( " K - 平均法によって点列をクラスタリングします . vn"); printf()K ( クラスタ総数 ) の値を入力して下さい . yn"); do { ' , num—pnts / 2 ) ; printf(" ( 1 以上 %d 以下 ) ・ scanf("%d" &K_number); } while ( K number く 1 Ⅱ K—number > ( num—pnts / 2.0 ) ) ; printf(" データを分類してクラスタを形成し , 結果を " ) ; printf(" 画像として作成します . vn"); だ番号はランダム順にされているので , No. 0—K_number-1*/ だの点列を最初の K_number 個のクラスタ中心に設定する num ClStr = K number; for ( i = 0 ; i く num clstr; i + + ) for ( j = 0 ; j く 2 ; j + + ) center-clstr[i][j] = points[i][j] ; finish = 0 ; counter = 0 ; while ( ! finish ) { counter 十十 ; printf("%d 回目のクラスタリング中です . vn", counter ) ; / * クラスタの初期代表点への代入 * / for ( i = 0 ; i く num clstr; i + + ) { for ( j = 0 ; j く 2 ; j + + ) init—cntr_clstr[i][j] = center—clstr[i][j] ; radius_clstr[i] = 10 ; だ defalt 値 * / だ各点の所属クラスタ番号の初期化ツ for ( i = 0 ; i < num_pnts; i 十十 ) point—clstr[i] = / * 各点の所属クラスタを決定する * / for ( i = 0 ; i く num—pnts; i + + ) { だ各クラスタ代表点との距離を求める * / min distance = 10000.0 ; for(j = o;j < num clstr;j + + ) { distance = calc distance( points[i][()] , points[i][l] , center-clstr[j][0] , center-clstr[j][l]); if ( distance く min distance){ min distance = distance; nun_num = 」 ;

5 パターン認識 double calc_distance( int xl, int yl, int x2, int y2 ) / * (x1,y1),(x2,y2) 間の距離を返す関数 return sqrt( ( x2- xl 当 x2- xl ) + ( y2- yl 戸 ( y2- yl ) ) ; void draw a_straight—line( int xl, int yl, int x2, int y2 ) 層 image2[y][x] 上に ( xl , yl ) , ( x2 , y2 ) 間の直線を発生させる . * / / * t: 内分点発生用制御変数ツ double distance, step, t; int x, y; / * 描く点の座標 * / distance = calc—distance( xl, yl, x2, y2 ) ; だ 2 点間の距離 * / step = 1.0 / ( 1.5 * distance); / * 発生させる内分点の総数 * / t = 0.0 ; while ()< 1.0 ) { x = (int)( い x2 + ( 1.0 - t 戸 xl ) ; y = (int)( い y2 + ( 1.0 - t 戸 yl ) ; if( x > = 0 & & x < x_size2 & & y > = 0 & & y く y_size2 ) image2[y][x] = DARK PIXEL; だ暗い点 * / t = t 十 step; int random int( int n ) / * 0 以上 n - 1 以下の整数の乱数を返す * / points[num—pnts - 1 Ⅱ 0 ] = x; num_pnts 十十 ; if ( num—pnts く MAX PNTS - 2 ) { if ( imagel[y][x] = = MAX BRIGHTNESS ) { for(x = 0 ; x く x—sizel; x + + ) { for ( y = 0 ; y < y—sizel; y + + ) { num—pnts = 0 ; int x, y; だループ変数 * / 層 imagel[y][x] 中の白画素のデータを points[][] に代入 * / void obtain—points data( ) return (int)( (double)rand( ) / ( (double)RAND MAX + 1.0 戸 n ) ; 109

90 4 画像の圧縮符号化法 unsigned int seed; / * 乱数のシード * / だ乱数の初期化響 printf ( " 乱数の系列を初期化します . *n"); printf(" 乱数のシード ( 任意の正の整数 ) : " ) ; scanf("%d" &seed); if(seed< 1 ) seed= 1 ; srand( seed ) ; double calc distance( int y, int x, int Ⅱ ) だ [ y Ⅱ x ] プロックのべクトルと No. n 代表べクトル間の距離計算響 / * 制御変数 * / lnt 1 ; double sum; / * 作業変数 * / sum = 0 ; for ( i = 0 ; i く DIMENSION; i + + ) sum = sum + ( vector[y][x][i] - main-vector[n][i]) * ( vector[y][x][i] - main-vector[n][i]); return( sqrt( sum ) ) ; void cIustering—using—Kmeans( ) だ K - 平均法によるクラスタリングを行う * / int K_number; / * K の値 ( 生成するクラスタの総数 ) * / int i, j, x, y, xs, ys; だ制御変数など * / double min distance, distance; / * 距離に関する変数☆ / int min_num; だ最も近いクラスタの番号 * / int finish; だ処理終了に関するフラグ * / int counter; だ処理回数 * / unsigned char init—main—vector[MAX CLUSTERS][DIMENSION] ; だ代表べクトル響 double sum[DIMENSION] , sum—number, difference; だ作業用変数 * / int original—data size, coded—data—size; だデータ量に関する変数 * / double compression—rate; だ圧縮率 printf("***** べクトル量子化法 do { printf(" 代表べクトルの本数 ( 8 ~ % d ) : " MAX CLUSTERS ) ;

160 7 動画像処理 例題 7-4 : プロックマッチングによるオプティカルフローの決定 図 7.9 に示したプロックマッチングに基づいて , 連続する 2 枚のフレー ム間のオプティカルフローを決定するプログラムを作成せよ . このとき , 速度べクトルを求める点を , 第 1 フレームの横方向 , 縦方向とも一定画 素間隔で設定せよ . 解答例 : だ速度べクトルを求めるプログラム motion. c 響 #include く stdio. h> #include く stdlib. h> #include<math. h> #include"mypgm. h" void copy—image 1—t0—image2( ) /*imagel を image2 へコピーする * / int x, y; だループ変数 * / X Size2 = X sizel; y_size2 = y—sizel; for(y=O; y<y_sizel; y 十十 ) for()= 0 ; x<x_sizel; x 十 + ) image2[y][x] = imagel[y][x] ; void draw_vector( int xl, int yl, int vx, int vy ) / * image2[y][x] に ( xl , yl ) の速度べクトル ( vx , vy ) を描画する . * / だ t : 内分点発生用制御変数 * / double distance, step, t; int x2, y2; だ終 * / だ描く点の座標 * / int x, y; X2 = xl 十 vx; y2 =yl 十 vy; distance = sqrt( ( x2- xl 戸 ( x2- xl ) + ( y2- yl 戸 ( y2- yl ) ) ; step = 1.0 / ( 1.5 * distance ) ; t = 0.0 ; while ( t く 1.0 ) { x = (int)( に x2 + ( 1.0 - t 戸 xl ) ; y = (int)( い y2 + ( 1.0 - t 戸 yl ) ; if( x > = 0 & & x < x_size2 & & y > = 0 & & y く y—size2 ) image2 [y][x] = (unsigned char)MAX BRIGHTNESS; t = t 十 step;

66 3 2 値画像処理 例題 3-6 : Houqh 変換 あらかじめいくつかの直線を含む 2 値原画像 ( 白 : 255 , 黒 : 0 ) を作成 した後 , その画像を読み込んで H 。 ugh 変換を施し , の平面上の分布を 画像として保存するプログラムを作成せよ . ただし , の平面を表す 2 次元配列の要素数は日方向は 360 , 〃方向は 720 とし , 各要素の値は 255 を上限値にせよ . 解答例 : だ Hough 変換のプログラム Hough. c * / #include<stdio. h> #inclu de<stdlib. h> #include<math. h> #include"mypgm. h" #define PI 3.141592653589 / * 円周率 #define MAX THETA 360 だ〃軸のサイズ ( 0.5 [ deg ト 1 画素 ) * / 720 / * p 軸のサイズ #define MAX RHO void draw a_straight_line( int xl, int yl, int x2, int y2 ) / * image2[y][x] 上の 2 点 ( xl , yl ) , ( x2 , y2 ) 間の直線上の配列要素☆ / / * の値をインクリメントする . * / だ t : 内分点発生用制御変数☆ / double distance, step, t; intx,y; だ描く点の座標 * / distance = sqrt( (x2-x1)*(x2-x1) + ( y2- yl 戸 ( y2- yl ) ) ; だ 2 点間の距離 * / step= 1.0 / ( 1.5 * distance); / * 発生させる内分点の総数 * / t = 0.0 ; while ( t く 1.0 ) { x = (int)( い x2 + ( 1.0 - t 戸 xl ) ; y = (int)( い y2 + ( 1.0 - t 戸 yl ) ; if( x > = 0 & & x < x_size2 & & y > = 0 & & y く y_size2 t = t 十 step; image2[y][x] + + ; & & image2[y][x] く MAX BRIGHTNESS ) { / ☆ p を計算するルーチン (draw_a_curve で使われている ) * / int —calc rho( double px, double py, double r_mg, int theta )

6 立体認識 解答例 / * 画像を簡易 3 次元表示するプログラム draw3D. c * / #include<stdio. h> #include<stdlib. h> #include<math. h> #include"mypgm. h" 139 void draw a_straight_line( int xl, int yl, int x2, int y2, int brightness ) だ image2[y][x] 上に ( xl , yl ) , ( x2 , y2 ) 間の直線を描画する . だ線の明るさは brightness ( 0 ~ 255 ) で指定する . double distance, step, t; だ t : 内分点発生用制御変数 * / intx,y; だ描く点の座標 * / distance = sqrt( (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1) ) ; / * 2 点間の距離 * / step= 1.0 / ( 1.5 * distance); / * 発生させる内分点の総数 * / t= 0.0 ; while ()< 1.0 ) { x = (int)( い x2 + ( 1.0 - t 戸 xl ) ; y = (int)( t * y2 + ( 1.0 - t 戸 yl ) ; if( 0 く = x & & x く x_size2 & & 0 <= y & & y < y_size2 ) image2 [y][x] = (unsigned char)brightness; t = t 十 step; void draw_3D_graph( ) int y, x; int plot_step; / * ループ変数 * / だ線の描画間隔 [ 画素 ] 2 ~ 10 程度 float plot-ratio; / * 階調方向の倍率 0.0 ~ 1.0 ( = 255 画素戸 / int plot—height; だ階調方向の高さ = 256.0 * plot_ratio * / / * グラフの想定横幅 ( 画素 ) 響 x_size2 = x_sizel 十 y_sizel / 2 ; だグラフの想定縦幅 ( 画素 ) * / y—size2 = y—sizel 十 256 ; if ( x—size2 > MAX IMAGESIZE Ⅱ y_size2 > MAX IMAGESIZE ) { printf ( " 画像が想定最大サイズを超えています . vn"); exit(l); } else { / * 描画パラメータ ( plot_step, plot_ratio ) の指定 * / printf(" 線の間隔 ( 画素 , 2 ~ 10 程度 ) : " ) ; scanf("%d" &plot_step);

116 5 パターン認識 たな点 P3 が所属されたとき , これまでのクラスタ中心 0 から , , P2, の平 均点である R へと , CI のクラスタ中心が移動する . CI 2 図 5.8 K - 平均法におけるクラスタ中心の更新の例 / * K - 平均法によるクラスタリングを行う☆ / void clustering—using—Kmeans( ) ( これより前は例題 5.1 の例題のプログラムと同じ ) K - 平均法による点のクラスタリングのプログラム Kmeans. c こでは生成するクラスタの総数 ( = の値を入力する . であるが , クラスタリングを実行することができる . 使用方法その他は NN 法と同様 NNmethod( ) 以下を次の部分で置き換えることによって K - 平均法による 例題 5.1 の解答例のプログラムにおいて , 関数 void clustering_using_ 解答例 : うプログラムを作成せよ . 例題 5-1 と同様な原画像に対して , K - 平均法によるクラスタリングを行 例題 5-2 : K - 平均法による 2 次元平面上の点列のクラスタリング int K number; int y, x, 1 , J; だ K の値 ( 生成するクラスタの総数 ) * / だ制御変数など double min—distance, distance; だ距離に関する変数 * / lnt min num; / * 点に対して最も近いクラスタの番号 * / double sum—x, sum—y, sum_number; だクラスタの作業変数☆ / int init—cntr—clstr[MAX_PNTS][2] ; / * クラスタの初期位置 * /