1: #include <stdlib.h>
2: #include <stdio.h>
3: #include <string.h>
4: #include <math.h>
5: #include <GL/glut.h>
6:
7: #include "pgm.h"
8: #include "chaincode.h"
9:
10: #define Round(v) ((int)(v+0.5))
11:
12: /*minimal size to consider an "object" as length of chaincode*/
13: #define DECENT_SIZED_OBJECT 100
14:
15: #define ONE_THIRD (1.0 / 3.0)
16: #define ONE_HALF (1.0 / 2.0)
17: #define ONE_SIXTH (1.0 / 6.0)
18: #define ONE_TWELTH (1.0 / 12.0)
19: #define ONE_24TH (1.0 / 24.0)
20: #define ONE_32ND (1.0 / 32.0)
21:
22: typedef struct
23: {
24: coord corner1;
25: coord corner2;
26: coord corner3;
27: coord corner4;
28: }object;
29:
30: typedef struct
31: {
32: /*The corners of the board. corner1 and corner2 are always opposite
33: (diagnol), just like corner3 and corner4 too.*/
34: object corners;
35:
36: /*The sides. The numbers represent the to corners that the point is
37: between. The first number is the corner that it is closest to.*/
38: coord side14, side13, side23, side24;
39: coord side31, side32, side41, side42;
40:
41: /*The points surrounding the middle square. The number indicates the
42: closest corner.*/
43: coord middle1, middle2, middle3, middle4;
44: }ttt;
45:
46: /*Evil globals, but not do-able otherwise.*/
47: static PGMImage *img_cur; /*current*/
48: static PGMImage *img_original; /*original*/
49: static PGMImage *img_pers_corr; /*perspective correction*/
50: static PGMImage *img_grayscale;
51: static PGMImage *img_moravec; /*moravec*/
52: static int HSIZE;
53: static int VSIZE;
54: static int MVAL;
55:
56: static ttt *ttt_board; /*pointer to a ttt structer containing the board info*/
57:
58: const RGB_INT white = {255, 255, 255};
59: const RGB_INT yellow = {255, 255, 0};
60: const RGB_INT magenta = {255, 0, 255};
61: const RGB_INT cyan = {0, 255, 255};
62: const RGB_INT red = {255, 0, 0};
63: const RGB_INT green = {0, 255, 0};
64: const RGB_INT blue = {0, 0, 255};
65: const RGB_INT black = {0, 0, 0};
66:
67: const RGB_INT gray = {128, 128, 128};
68: const RGB_INT lt_yellow = {255, 255, 128};
69: const RGB_INT lt_magenta = {255, 128, 255};
70: const RGB_INT lt_cyan = {128, 255, 255};
71:
72: const RGB_INT lt_red = {255, 128, 128};
73: const RGB_INT lt_green = {128, 255, 128};
74: const RGB_INT lt_blue = {128, 128, 255};
75:
76: const RGB_INT dk_yellow = {128, 128, 0};
77: const RGB_INT dk_magenta = {128, 0, 128};
78: const RGB_INT dk_cyan = { 0, 128, 128};
79:
80: const RGB_INT dk_red = {128, 0, 0};
81: const RGB_INT dk_green = { 0, 128, 0};
82: const RGB_INT dk_blue = { 0, 0, 128};
83:
84: /*pointer to an array of pointers which point to the first nodes in each of
85: the chain codes.*/
86: list_info* chain_codes;
87:
88: /*hold the points farthest away from each other for each object*/
89: /*coord corner1[MAX_CHAINS], corner2[MAX_CHAINS];
90: coord corner3[MAX_CHAINS], corner4[MAX_CHAINS];*/
91: /*object all_objects[MAX_CHAINS];*/
92: static object *all_objects;
93:
94: /*use double buffered output and keep running enable idle callback to call
95: detect_corners() over and over simulating realtime response.
96: Is set to TRUE or FALSE.*/
97: int is_buffered;
98:
99: /*used to determine if abstract lines should be drawn to the screen.
100: Set to <0 if no abstract lines are to be drawn. Otherwise
101: is set to the number of objects found (AKA number of chaincodes).*/
102: int draw_abstract_lines = -1;
103:
104: /*used to draw the single object most likely to be considered the
105: tic-tac-toe board. Should be <0 if this should not be drawn.
106: Should be equal to the chain-code number (from 0 to MAX_CHAINS - 1)
107: if it is to be drawn.*/
108: int draw_abstract_board = -1;
109:
110:
111: /**************Drawing funcitions************************************/
112: /********************************************************************/
113:
114: void setCPixel(int ix, int iy, RGB_INT color)
115: /*Same as setIPixel except that the last parameter is an RGB color*/
116: {
117: float x = (ix*2.0)/HSIZE - 1.0;
118: float y = (iy*2.0)/VSIZE - 1.0;
119:
120: float red = (float)color.red/(float)MVAL;
121: float green = (float)color.green/(float)MVAL;
122: float blue = (float)color.blue/(float)MVAL;
123:
124: glColor3f(red, green, blue);
125:
126: glBegin(GL_POINTS);
127: glVertex2f (x, y);
128: glEnd();
129: }
130:
131: void setCLines(int ix1, int iy1, int ix2, int iy2, RGB_INT color)
132: /*Similar as setIPixel except that this one draws a line between the first set
133: of points given and the second set in the RGB color specified*/
134: {
135: float x1 = (ix1*2.0)/HSIZE - 1.0;
136: float y1 = (iy1*2.0)/VSIZE - 1.0;
137: float x2 = (ix2*2.0)/HSIZE - 1.0;
138: float y2 = (iy2*2.0)/VSIZE - 1.0;
139:
140: float red = (float)color.red/(float)MVAL;
141: float green = (float)color.green/(float)MVAL;
142: float blue = (float)color.blue/(float)MVAL;
143:
144: glColor3f(red, green, blue);
145:
146: glBegin(GL_LINES);
147: glVertex2f (x1, y1);
148: glVertex2f (x2, y2);
149: glEnd();
150: }
151:
152: void setCRect(int ix1, int iy1, int ix2, int iy2, RGB_INT color)
153: /*Similar as setIPixel except that this one draws a line between the first set
154: of points given and the second set in the RGB color specified*/
155: {
156: float x1 = (ix1*2.0)/HSIZE - 1.0;
157: float y1 = (iy1*2.0)/VSIZE - 1.0;
158: float x2 = (ix2*2.0)/HSIZE - 1.0;
159: float y2 = (iy2*2.0)/VSIZE - 1.0;
160:
161: float red = (float)color.red/(float)MVAL;
162: float green = (float)color.green/(float)MVAL;
163: float blue = (float)color.blue/(float)MVAL;
164:
165: glColor3f(red, green, blue);
166:
167: glBegin(GL_POLYGON);
168: glVertex2f (x1, y1);
169: glVertex2f (x1, y2);
170: glVertex2f (x2, y2);
171: glVertex2f (x2, y1);
172: glEnd();
173: }
174:
175: /* =================================================================
176: * drawString - outputs a string of characters to the graphics port
177: *
178: * x, y: defines the starting location to draw the text
179: * note: this point is the lower left anchor of
180: * the first character - a character's decending
181: * portion would be drawn below this point.
182: * theFont: points to the glut font to be used
183: * theString: holds the string to be output -- up to 255 ch
184: * ----------------------------------------------------------------- */
185: void drawString(int ix, int iy, void *theFont, char theString[256],
186: RGB_INT color)
187: {
188: float x = (ix*2.0)/HSIZE - 1.0;
189: float y = (iy*2.0)/VSIZE - 1.0;
190: int i;
191:
192: float red = (float)color.red/(float)MVAL;
193: float green = (float)color.green/(float)MVAL;
194: float blue = (float)color.blue/(float)MVAL;
195:
196: glColor3f(red, green, blue);
197:
198: glRasterPos2f(x, y);
199: for (i = 0; theString[i] != '\0'; i++) /* draw the chars one at a time */
200: glutBitmapCharacter(theFont, theString[i]);
201: }
202:
203: void showColor (PGMImage *img)
204: {
205: int i, j; /*loop counting: i = y, j = x*/
206:
207: GLubyte checkImage[(*img).height][(*img).width][3];
208:
209: for(i = 0; i < (*img).height; i++)
210: {
211: for(j = 0; j < (*img).width; j++)
212: {
213: checkImage[i][j][0] = (GLubyte) (*img).data[i][j].red;
214: checkImage[i][j][1] = (GLubyte) (*img).data[i][j].green;
215: checkImage[i][j][2] = (GLubyte) (*img).data[i][j].blue;
216: }
217: }
218: /*draw the current image*/
219: glPixelStorei(GL_UNPACK_ALIGNMENT, 1);
220: glRasterPos2f(-1, -1);
221: glDrawPixels((*img).width, (*img).height, GL_RGB,
222: GL_UNSIGNED_BYTE, checkImage);
223:
224: glFlush();
225: }
226:
227: /*called by showAbstract()*/
228: void display_labels(int x_coord, int y_coord, char* more_text)
229: {
230: char text[40]; /*for displaying the locations in text form*/
231: int offset = 8; /*offset text # pixels from location*/
232:
233: sprintf(text, "%s (%d, %d)\0", more_text, x_coord, y_coord);
234: drawString(x_coord + offset, y_coord + offset,
235: GLUT_BITMAP_TIMES_ROMAN_10, text, blue);
236: }
237:
238: /*display the global abstract data*/
239: void showAbstract(object* object_list, ttt *ttt_data)
240: {
241: int i;
242:
243: /* coord hor_top1, hor_top2;
244: coord hor_bot1, hor_bot2;
245: coord ver_rgt1, ver_rgt2;
246: coord ver_lft1, ver_lft2;
247: */
248: list_info temp;
249:
250: glPointSize(2); /*make points more visible, if desired*/
251: /*glLineWidth(4);*/
252:
253: /*draw the chaincodes*/
254: /*chain_codes is a global pointer to an array of list_info types*/
255: for(i = 0; (i < MAX_CHAINS) && chain_codes && chain_codes[i].cur; i++)
256: {
257: memcpy(&temp, &chain_codes[i], sizeof(list_info));
258: while(RetrieveNextNode(&temp).cur)
259: {
260: setCPixel(RetrieveInfo(&temp).location.x,
261: RetrieveInfo(&temp).location.y, gray);
262: Advance(&temp);
263: }
264: }
265:
266: /*first check for non-null pointer, next check for dereferenced pointers
267: in the array of head pointers and lastly make sure things stay in
268: bound of the max incase all MAX_CHAINS number of chains are used.*/
269: /*draw_abstract_lines is the global that holds the number of "objects"
270: to draw abstract information for*/
271: for(i = 0; i < draw_abstract_lines && i < MAX_CHAINS; i++)
272: {
273: setCLines(object_list[i].corner1.x, object_list[i].corner1.y,
274: object_list[i].corner3.x, object_list[i].corner3.y,yellow);
275: setCLines(object_list[i].corner4.x, object_list[i].corner4.y,
276: object_list[i].corner2.x, object_list[i].corner2.y,yellow);
277: setCLines(object_list[i].corner3.x, object_list[i].corner3.y,
278: object_list[i].corner2.x, object_list[i].corner2.y,yellow);
279: setCLines(object_list[i].corner4.x, object_list[i].corner4.y,
280: object_list[i].corner1.x, object_list[i].corner1.y,yellow);
281:
282: setCPixel(object_list[i].corner1.x, object_list[i].corner1.y,dk_red);
283: setCPixel(object_list[i].corner2.x, object_list[i].corner2.y,dk_blue);
284: setCPixel(object_list[i].corner3.x, object_list[i].corner3.y,white);
285: setCPixel(object_list[i].corner4.x, object_list[i].corner4.y,dk_green);
286:
287: /*labels for corner points*/
288: display_labels(object_list[i].corner1.x, object_list[i].corner1.y, "c1");
289: display_labels(object_list[i].corner2.x, object_list[i].corner2.y, "c2");
290: display_labels(object_list[i].corner3.x, object_list[i].corner3.y, "c3");
291: display_labels(object_list[i].corner4.x, object_list[i].corner4.y, "c4");
292: }
293:
294: /*if there is board to draw and just make sure there isn't a NULL pointer*/
295: if((draw_abstract_board > -1) && ttt_data)
296: {
297: /*This code should draw the bounding box*/
298: /*setCLines(ttt_data->corners.corner1.x,
299: ttt_data->corners.corner1.y,
300: ttt_data->corners.corner3.x,
301: ttt_data->corners.corner3.y,blue);
302: setCLines(ttt_data->corners.corner4.x,
303: ttt_data->corners.corner4.y,
304: ttt_data->corners.corner2.x,
305: ttt_data->corners.corner2.y,blue);
306: setCLines(ttt_data->corners.corner3.x,
307: ttt_data->corners.corner3.y,
308: ttt_data->corners.corner2.x,
309: ttt_data->corners.corner2.y,blue);
310: setCLines(ttt_data->corners.corner4.x,
311: ttt_data->corners.corner4.y,
312: ttt_data->corners.corner1.x,
313: ttt_data->corners.corner1.y,blue);
314: setCPixel(ttt_data->corners.corner1.x,
315: ttt_data->corners.corner1.y, red);
316: setCPixel(ttt_data->corners.corner2.x,
317: ttt_data->corners.corner2.y, red);
318: setCPixel(ttt_data->corners.corner3.x,
319: ttt_data->corners.corner3.y, red);
320: setCPixel(ttt_data->corners.corner4.x,
321: ttt_data->corners.corner4.y, red);
322: */
323:
324: setCLines(ttt_data->side13.x,
325: ttt_data->side13.y,
326: ttt_data->side42.x,
327: ttt_data->side42.y,blue);
328: setCLines(ttt_data->side31.x,
329: ttt_data->side31.y,
330: ttt_data->side24.x,
331: ttt_data->side24.y,blue);
332: setCLines(ttt_data->side23.x,
333: ttt_data->side23.y,
334: ttt_data->side41.x,
335: ttt_data->side41.y,blue);
336: setCLines(ttt_data->side32.x,
337: ttt_data->side32.y,
338: ttt_data->side14.x,
339: ttt_data->side14.y,blue);
340:
341: setCPixel(ttt_data->middle1.x, ttt_data->middle1.y, red);
342: setCPixel(ttt_data->middle2.x, ttt_data->middle2.y, red);
343: setCPixel(ttt_data->middle3.x, ttt_data->middle3.y, red);
344: setCPixel(ttt_data->middle4.x, ttt_data->middle4.y, red);
345:
346: setCPixel(ttt_data->side13.x, ttt_data->side13.y, red);
347: setCPixel(ttt_data->side14.x, ttt_data->side14.y, red);
348: setCPixel(ttt_data->side23.x, ttt_data->side23.y, red);
349: setCPixel(ttt_data->side24.x, ttt_data->side24.y, red);
350: setCPixel(ttt_data->side31.x, ttt_data->side31.y, red);
351: setCPixel(ttt_data->side32.x, ttt_data->side32.y, red);
352: setCPixel(ttt_data->side41.x, ttt_data->side41.y, red);
353: setCPixel(ttt_data->side42.x, ttt_data->side42.y, red);
354:
355: /*labels for middle points*/
356: display_labels(ttt_data->middle1.x, ttt_data->middle1.y, "m1");
357: display_labels(ttt_data->middle2.x, ttt_data->middle2.y, "m2");
358: display_labels(ttt_data->middle3.x, ttt_data->middle3.y, "m3");
359: display_labels(ttt_data->middle4.x, ttt_data->middle4.y, "m4");
360:
361: /*lables for side points*/
362: display_labels(ttt_data->side13.x, ttt_data->side13.y, "s13");
363: display_labels(ttt_data->side14.x, ttt_data->side14.y, "s14");
364: display_labels(ttt_data->side23.x, ttt_data->side23.y, "s23");
365: display_labels(ttt_data->side24.x, ttt_data->side24.y, "s24");
366: display_labels(ttt_data->side31.x, ttt_data->side31.y, "s31");
367: display_labels(ttt_data->side32.x, ttt_data->side32.y, "s32");
368: display_labels(ttt_data->side41.x, ttt_data->side41.y, "s41");
369: display_labels(ttt_data->side42.x, ttt_data->side42.y, "s42");
370: }
371: glFlush();
372: }
373:
374: /**********************Support functions*******************************/
375: /***********************************************************************/
376:
377: void pxlcpy(PGMImage *dest, int dest_row, int dest_col,
378: PGMImage *src, int src_row, int src_col)
379: {
380: /*make sure values are within bounds*/
381: if(dest_col > 0 && dest_col < (*dest).width
382: && dest_row > 0 && dest_row < (*dest).height
383: && src_col > 0 && src_col < (*src).width
384: && src_row > 0 && src_row < (*src).height)
385: {
386: (*dest).data[dest_row][dest_col].red =
387: (*src).data[src_row][src_col].red;
388:
389: (*dest).data[dest_row][dest_col].green =
390: (*src).data[src_row][src_col].green;
391:
392: (*dest).data[dest_row][dest_col].blue =
393: (*src).data[src_row][src_col].blue;
394: }
395: }
396:
397: int rgb_avg(RGB_INT cur_pxl)
398: {
399: /*convert each RGB to the average of the original*/
400: return ((cur_pxl.red + cur_pxl.green + cur_pxl.blue) / 3);
401: }
402:
403: /*Returns average (with RGB avg) pixel value for the image passed in.*/
404: int img_pxl_avg(PGMImage* img)
405: {
406: int i, j; /*loop counting*/
407: int sum = 0;
408: int temp;
409:
410: for(i = 0; i < (*img).height; i++)/*collumn*/
411: for(j = 0; j < (*img).width; j++)/*row*/
412: sum += rgb_avg((*img).data[i][j]);
413:
414:
415: temp = (sum / ((*img).height * (*img).width));
416:
417: return temp;
418: }
419:
420: /*1st: pixel one of type RGB_INT
421: 2nd: pixel one of type RGB_INT
422: 3rd: differnce allowed to be considered "equal" or close enough*/
423: int pxlcmp (RGB_INT pxl1, RGB_INT pxl2, int range)
424: {
425: return ((abs((rgb_avg(pxl1) - rgb_avg(pxl2)))) < range);
426: }
427:
428: /*return >0 if number of pixels is greater than img. pxl. avg., return <0 if
429: number of pixesl is less than img. pxl. avg. and return zero of equal*/
430: int background(int treash_value, PGMImage* img)
431: {
432: int i, j; /*loop counting*/
433: int pxl_less = 0, pxl_more = 0;
434:
435: for(i = 0; i < (*img).height; i++)/*collumn*/
436: for(j = 0; j < (*img).width; j++)/*row*/
437: {
438: if(rgb_avg((*img).data[i][j]) < treash_value)
439: pxl_less++;
440:
441: if(rgb_avg((*img).data[i][j]) > treash_value)
442: pxl_more++;
443: }
444:
445: if(pxl_less > pxl_more)
446: return -1;
447: else if(pxl_less < pxl_more)
448: return 1;
449: else
450: return 0;
451: }
452:
453: /*Used by showColor() and detect_pieces()*/
454: coord find_dividers(coord point1, coord point2, float t)
455: {
456: coord temp;
457:
458: temp.x = (int)(((1.0 - t) * point1.x) + (t * point2.x));
459: temp.y = (int)(((1.0 - t) * point1.y) + (t * point2.y));
460:
461: return temp;
462: }
463:
464: /******Perspective correction*******************************************
465: ***********************************************************************/
466: void pers_corr(PGMImage* new_img, PGMImage* org_img)
467: {
468: /******************X direction variables*********/
469:
470: /*i and j are the left half, k and l are the right half*/
471: float i, k; /*loop counting x dir*/
472: int j, l, row; /*loop counting x dir*/
473: int old_i, old_k; /*x dir. counting to remove moire iterference*/
474:
475: float ins_s = 2.2; /*insert constant starting value x dir.*/
476: float ins_k = ins_s; /*current insert x dir.*/
477:
478: /*The halfway marks in the width.*/
479: int mid_width_left = ((*new_img).width / 2) - 1;
480: int mid_width_right = ((*new_img).width / 2);
481:
482: /******************Y direction variables*********/
483:
484: float m; /*loop counting y dir*/
485: int n, col; /*loop counting y dir*/
486: int old_n = (*new_img).height, old_n_inc; /*y dir remove moire iterference*/
487:
488: float ins_t = 2.0; /*insert constant starting value y dir.*/
489: float ins_j = ins_t; /*current insert value y dir.*/
490:
491: /*since the x dir is calculated from the middle, the middle is always
492: mapped to the middle. Since the y dir is calculated from the top the
493: image is pushed to the bottom. To correct this add to the new pixel
494: location this value to recenter the image.*/
495: int recenter = ((*new_img).height / ins_t);
496:
497: /*just to be thourough clear the memory and reset maxes*/
498: memset(new_img, 0, sizeof(PGMImage));
499: (*new_img).height = (*org_img).height;
500: (*new_img).width = (*org_img).width;
501: (*new_img).maxVal = (*org_img).maxVal;
502:
503: /****x direction correction******/
504:
505: /*Loop through each row from top to bottom...*/
506: /*for(row = ((*new_img).height - 1); row >= 0; row--)*/
507: for(m = n = ((*new_img).height - 1);
508: m >= 0, n >= 0;
509: m -= ins_j, n--)
510: {
511: /*...reset moire interference removal counter x dir...*/
512: old_i = ((*new_img).width / 2) - 1;
513: old_k = ((*new_img).width / 2);
514:
515: /****y direction correction******/
516: /*...so each half is ajusted to remove perspective effect...*/
517: /*initalize the x and y starting conditions*/
518: for(i = j = mid_width_left, k = l = mid_width_right;
519: /*x ending conditions*/
520: i >= 0, j >= 0, k < (*new_img).width, l < (*new_img).width;
521: /*incremental*/
522: i -= ins_k, j--, k += ins_k, l++)
523: {
524: for(;old_i >= (int)i; old_i--) /*...in the left half...*/
525: for(old_n_inc = old_n; old_n_inc >= m; old_n_inc--)
526: pxlcpy(new_img, old_n_inc + recenter, old_i, org_img, n, j);
527:
528: for(;old_k <= (int)k; old_k++) /*...in the right half.*/
529: for(old_n_inc = old_n; old_n_inc >= m; old_n_inc--)
530: pxlcpy(new_img, old_n_inc + recenter, old_k, org_img, n, l);
531: }
532: /*Move the new image x_coord pixel counter to next new image pixel*/
533: ins_k -= ((ins_s - 1.0) / (*new_img).height);
534: ins_j -= ((ins_t - 1.0) / (*new_img).width);
535:
536: old_n = m; /*store for next row*/
537: }
538:
539:
540: }
541:
542: /*****convert color to grayscale****************************************
543: ***********************************************************************/
544: void color_to_gray(PGMImage* new_img, PGMImage* org_img)
545: {
546: int row, col; /*loop counting*/
547: RGB_INT cur_pxl; /*current pixel*/
548:
549: (*new_img).height = (*org_img).height;
550: (*new_img).width = (*org_img).width;
551: (*new_img).maxVal = (*org_img).maxVal;
552:
553: /*Starting with the top row...*/
554: for(row = (*new_img).height - 1; row >= 0; row--)
555: for(col = 0; col < (*new_img).width - 1; col++)
556: {
557: cur_pxl = (*org_img).data[row][col]; /*more readable*/
558:
559: /*convert each RGB to the average of the original*/
560: (*new_img).data[row][col].red = rgb_avg(cur_pxl);
561: (*new_img).data[row][col].green = rgb_avg(cur_pxl);
562: (*new_img).data[row][col].blue = rgb_avg(cur_pxl);
563: }
564: }
565:
566: /*******Edge highlighting**********************************************
567: **********************************************************************/
568: void moravec(PGMImage* new_img, PGMImage* org_img)
569: {
570: int row, col; /*loop counting*/
571: int i, j, k, l; /*Sanka, Hlavac & Boyle; p. 97 f. 4.73*/
572: int running_sum;
573: float K = .5; /*.125 according to org. formula, but .5 is brighter*/
574: int max_val = 0, row_max, col_max; /* max porportion value in image*/
575:
576: memset(new_img, 0, sizeof(PGMImage));
577: (*new_img).height = (*org_img).height;
578: (*new_img).width = (*org_img).width;
579: (*new_img).maxVal = (*org_img).maxVal;
580:
581: /*starting at the top row*/
582: for(row = (*new_img).height - 1 - 1; row > 0; row--)
583: for(col = 1; col < (*new_img).width - 1; col++) /*left col start*/
584: {
585: i = row;
586: j = col;
587: running_sum = 0;
588:
589: /*Sanka, Hlavac & Boyle; p. 97 f. 4.73*/
590: for(k = i - 1; k <= i + 1; k++) /*row*/
591: for(l = j - 1; l <= j + 1; l++) /*column*/
592: running_sum += abs(rgb_avg((*org_img).data[k][l]) -
593: rgb_avg((*org_img).data[i][j]));
594:
595: /*assign the new pixel value*/
596: /*since it all the data is initalized to 0, we only worry when it
597: shouldn't be*/
598: if((int)(K * running_sum) >= 128)
599: {
600: (*new_img).data[row][col].red = 255;
601: (*new_img).data[row][col].green = 255;
602: (*new_img).data[row][col].blue = 255;
603: }
604: /*this is the original code...*/
605: /*(*new_img).data[row][col].red = (int)(K * running_sum);
606: (*new_img).data[row][col].green = (int)(K * running_sum);
607: (*new_img).data[row][col].blue = (int)(K * running_sum);*/
608: }
609: }
610:
611: /*******Corners*****************************************************
612: *******************************************************************/
613:
614: /*takes two coordinates as x and y pairs and returns the distence betweem them
615: as a decimal*/
616: float findDist(int x1, int y1, int x2, int y2)
617: {
618: return sqrt(((x1 - x2) * (x1 - x2)) + ((y1 - y2) * (y1 - y2)));
619: }
620:
621: /*1st param: The array of coords that the first point of the major axis is
622: returned in.
623: 2nd: The array of coords that the second point of the major axis is
624: returned in.
625: 3rd: The array of chain codes that are searched through to find the major
626: axes.*/
627: /* Note: the ending condition is when a NULL chainCodes value is reached.
628: Thusly, it works like a string requiring it to have the last legal value
629: followed by a null value.*/
630: void findFirstTwoCorners(object *objects_array, list_info* chainCodes)
631: {
632: int i; /*loop counting*/
633: list_info temp, search;
634: double max_dist, test_dist;
635:
636: /*printf("\nFinding first 2 corners.\n");*/
637:
638: /*as long as there are codes to check, keep checking. Note: the ending
639: condition is when a NULL chainCodes value is reached. Thusly, it works
640: like a string requiring it to have the last legal value followed by a
641: null value.*/
642: for(i = 0; ((i < MAX_CHAINS) && chainCodes[i].cur); i++)
643: {
644: memcpy(&temp, &chainCodes[i], sizeof(list_info));
645:
646: max_dist = 0.0; /*reset this for each iteration*/
647:
648: /*printf("checking list: %d\n", i);*/
649:
650: while(RetrieveNextNode(&temp).cur) /*while there are nodes to check*/
651: {
652: /*set the faster moving search pointer to temp,
653: this increases the effiecency a lot compared to
654: setting it equal to the first node..*/
655: memcpy(&search, &temp, sizeof(list_info));
656:
657: while(RetrieveNextNode(&search).cur)
658: {
659: /*setCPixel(RetrieveInfo(&temp).location.x,
660: RetrieveInfo(&temp).location.y, green);*/
661:
662: /*determine if found a new maximum distance between two locations*/
663: if((test_dist = findDist(RetrieveInfo(&search).location.x,
664: RetrieveInfo(&search).location.y,
665: RetrieveInfo(&temp).location.x,
666: RetrieveInfo(&temp).location.y))>max_dist)
667: {
668: max_dist = test_dist;
669: objects_array[i].corner1.x = RetrieveInfo(&temp).location.x;
670: objects_array[i].corner1.y = RetrieveInfo(&temp).location.y;
671: objects_array[i].corner2.x = RetrieveInfo(&search).location.x;
672: objects_array[i].corner2.y = RetrieveInfo(&search).location.y;
673: }
674: Advance(&search);
675: }
676: Advance(&temp);
677: }
678: /*printf("point1: %d %d\n", max1[i].x, max1[i].y);
679: printf("point2: %d %d\n", max2[i].x, max2[i].y);*/
680: }
681: }
682:
683: /*1st param: Array of coords for the first corner of each chain code.
684: 2nd param: Array of coords for the second corner of each chain code.
685: The first two parameters should equal the first two parameters "returned"
686: from the findFirstTwoCorners() function.
687: 3rd: Array of coords "returned" with the third corners.
688: 4th: Array of coords "returned" with the fourth corners.
689: 5th: Pointer pointing to the array of chaincode pointers, obtained from
690: showChain().*/
691: void findSecondTwoCorners(object *objects_array, list_info* chain_code_array)
692: {
693: int i; /*loop counting*/
694: list_info temp;
695: float temp_dist1, temp_dist2; /*distance between point and each corner*/
696: coord canidate_coord1, temp_coord;
697: float canidate_dist1, max_dist;
698: int corner_count;
699:
700: /*printf("\nFinding last 2 corners.\n\n");*/
701:
702: /*for each chain code find the corners*/
703: for(i = 0; (i < MAX_CHAINS) && chain_code_array[i].cur; i++)
704: {
705: memcpy(&temp, &chain_code_array[i], sizeof(list_info));
706:
707: /*reset these for the next chain code*/
708: max_dist = 0.0;
709: corner_count = 1;
710:
711: /*while there are nodes in the chain code to check*/
712: /*if there isn't a next node cur is NULL, which is checked*/
713: while(RetrieveNextNode(&temp).cur)
714: {
715: /*setCPixel(RetrieveInfo(&temp).location.x,
716: RetrieveInfo(&temp).location.y, color1);*/
717:
718: /*determine the first canidate coord for corner 3/4*/
719: if(((RetrieveInfo(&temp).location.x == objects_array[i].corner1.x)
720: && (RetrieveInfo(&temp).location.y == objects_array[i].corner1.y))
721: || ((RetrieveInfo(&temp).location.x == objects_array[i].corner2.x)
722: &&(RetrieveInfo(&temp).location.y == objects_array[i].corner2.y)))
723: {
724: /*if this corner found is the first of the two allready known
725: corners, then set the first canidate coord data and reset data
726: to find the next canidate corner point*/
727: if(corner_count == 1)
728: {
729: canidate_coord1.x = temp_coord.x;
730: canidate_coord1.y = temp_coord.y;
731: canidate_dist1 = max_dist;
732:
733: corner_count = 2; /*set for next corner*/
734: max_dist = 0.0;
735: }
736: else if(corner_count == 2)
737: {
738: /*the second canidate is always a corner*/
739: all_objects[i].corner4.x = temp_coord.x;
740: all_objects[i].corner4.y = temp_coord.y;
741:
742: max_dist = 0.0; /*set for next corner canidate*/
743: }
744: }
745:
746: /*calculate the distance between the current point being checked and
747: each corner point*/
748: temp_dist1 = findDist(all_objects[i].corner1.x,
749: all_objects[i].corner1.y,
750: RetrieveInfo(&temp).location.x,
751: RetrieveInfo(&temp).location.y);
752: temp_dist2 = findDist(all_objects[i].corner2.x,
753: all_objects[i].corner2.y,
754: RetrieveInfo(&temp).location.x,
755: RetrieveInfo(&temp).location.y);
756:
757: /*if the current point is the furthest away sofar, store this point
758: untill it is overridden or becomes a canidate point*/
759: if((temp_dist1 + temp_dist2) > max_dist)
760: {
761: temp_coord.x = RetrieveInfo(&temp).location.x;
762: temp_coord.y = RetrieveInfo(&temp).location.y;
763:
764: max_dist = (temp_dist1 + temp_dist2);
765: }
766:
767: Advance(&temp);
768: }
769:
770: /*from the three canidate coords find the two real corners.*/
771: /*the second canidate will always be a corner, must test 1 vs 3, where
772: three is in the variables temp_coord and max_dist.*/
773: if(canidate_dist1 > max_dist) /*first canidate*/
774: {
775: all_objects[i].corner3.x = canidate_coord1.x;
776: all_objects[i].corner3.y = canidate_coord1.y;
777: }
778: else /*third canidate*/
779: {
780: all_objects[i].corner3.x = temp_coord.x;
781: all_objects[i].corner3.y = temp_coord.y;
782: }
783: /*printf("corner3: (%d, %d) corner4: (%d, %d)\n", corner3[i].x,
784: corner3[i].y, corner4[i].x, corner4[i].y);*/
785: }
786: }
787:
788: /*takes a pointer to an image, and a pointer pointing to an array of
789: chain codes pointers, here each chainCode pointer needs to be accessed
790: by calculating the memory address.*/
791: void showBound(list_info* chainCodes, object *all_objects)
792: {
793: /* int i;*/
794:
795: /*find the first two corners. they will be across a diagnal.*/
796: findFirstTwoCorners(all_objects, chainCodes);
797: /*find the second two corners. they will be across a diagnal too.*/
798: findSecondTwoCorners(all_objects, chainCodes);
799: /*
800: for(i = 0; chainCodes[i] && i < MAX_CHAINS; i++)
801: {
802: setCLines(corner1[i].x, corner1[i].y, corner3[i].x, corner3[i].y,yellow);
803: setCLines(corner4[i].x, corner4[i].y, corner2[i].x, corner2[i].y,yellow);
804: setCLines(corner3[i].x, corner3[i].y, corner2[i].x, corner2[i].y,yellow);
805: setCLines(corner4[i].x, corner4[i].y, corner1[i].x, corner1[i].y,yellow);
806: setCPixel(corner1[i].x, corner1[i].y, magenta);
807: setCPixel(corner2[i].x, corner2[i].y, magenta);
808: setCPixel(corner3[i].x, corner3[i].y, magenta);
809: setCPixel(corner4[i].x, corner4[i].y, magenta);
810: }*/
811: }
812:
813: /*returns the number of objects found*/
814: /*places the corner info in the global corners data*/
815: int detect_corners(list_info* current_chaincodes, object *objects_array)
816: {
817: int i; /*temporarily holds number of chaincodes*/
818:
819: /*clear the array of objects*/
820: memset(objects_array, 0, sizeof(object) * MAX_CHAINS);
821:
822: showBound(current_chaincodes, objects_array);
823:
824: /*when this stops, i holds the number of chaincodes*/
825: for(i = 0; (i < MAX_CHAINS) && chain_codes && chain_codes[i].cur; i++);
826:
827: return i;
828: }
829:
830: /*******Find the game board********************************************
831: **********************************************************************/
832:
833: float compare_length(float length1, float length2)
834: {
835: float denom_check = fabs((length1 + length2) / 2);
836: if(denom_check == 0)
837: {
838: /*the only way to possibly pull this off is if one point is
839: is considered more than one corner. This is most likely
840: to happen where the chain was only two or three nodes long.*/
841: /*Just set the error to the maximum value obtained from float.h,
842: since such a small chain is not what we are looking for.*/
843:
844: /*error24to13[i] =*/ return FLT_MAX;
845: }
846: else
847: /*error24to13[i] =*/return fabs(length1 - length2) / denom_check;
848: }
849:
850: /*determines which object is the game board and determine moves made in
851: the game.*/
852: /*takes the number of object corners (equal to # of chaincodes) as param.*/
853: int detect_game(list_info *current_chaincodes, object *object_array)
854: {
855: float length2to4[MAX_CHAINS], length1to3[MAX_CHAINS]; /*side pairs*/
856: float length1to4[MAX_CHAINS], length2to3[MAX_CHAINS]; /*side pairs*/
857: float length1to2[MAX_CHAINS], length3to4[MAX_CHAINS]; /*diagnaols*/
858:
859: float error24to13[MAX_CHAINS], error14to23[MAX_CHAINS];/*opp. sides*/
860: float error14to13[MAX_CHAINS], error23to24[MAX_CHAINS];/*share corner*/
861: float error31to32[MAX_CHAINS], error41to42[MAX_CHAINS];/*share corner*/
862: float error12to34[MAX_CHAINS];/*diagnaols*/
863:
864: float error_avg;/*average of the errors stored in error##to## variables*/
865:
866: int i, k; /*loop counting*/
867: /*float denom_check; /*make sure denominators are not zero*/
868: list* temp;
869:
870: /*the most likely object (0 to num_of_corners) that is to be considered
871: as the board. The float is the error associated with this object.*/
872: int most_likely = -1;
873: float ml_error = FLT_MAX; /*just to make sure*/
874:
875: /*for each chaincode*/
876: for(i = 0; (i < MAX_CHAINS) && current_chaincodes &&
877: current_chaincodes[i].cur; i++)
878: {
879: /*count the number of nodes in the chaincode. Unless the size is
880: considered long enough, skip it and move on.*/
881: if(Length(¤t_chaincodes[i]) < DECENT_SIZED_OBJECT)
882: continue;
883:
884: /*since points 1 & 2 are at a diagnal, and 3 & 4 are at a diagnol,
885: then the dist between 2 and 4 & 1 and 3 should be close
886: in value.*/
887: length2to4[i] = findDist(object_array[i].corner2.x,
888: object_array[i].corner2.y,
889: object_array[i].corner4.x,
890: object_array[i].corner4.y);
891: length1to3[i] = findDist(object_array[i].corner1.x,
892: object_array[i].corner1.y,
893: object_array[i].corner3.x,
894: object_array[i].corner3.y);
895:
896: /*the other side pair*/
897: length1to4[i] = findDist(object_array[i].corner1.x,
898: object_array[i].corner1.y,
899: object_array[i].corner4.x,
900: object_array[i].corner4.y);
901: length2to3[i] = findDist(object_array[i].corner2.x,
902: object_array[i].corner2.y,
903: object_array[i].corner3.x,
904: object_array[i].corner3.y);
905:
906: /*diagnols... always will be 1 & 2 and 3 & 4*/
907: length1to2[i] = findDist(object_array[i].corner1.x,
908: object_array[i].corner1.y,
909: object_array[i].corner2.x,
910: object_array[i].corner2.y);
911: length3to4[i] = findDist(object_array[i].corner3.x,
912: object_array[i].corner3.y,
913: object_array[i].corner4.x,
914: object_array[i].corner4.y);
915:
916: /*calculate percent errors for all edge (and diagnal) combinations*/
917: error24to13[i] = compare_length(length2to4[i], length1to3[i]);/*op.side*/
918: error14to23[i] = compare_length(length1to4[i], length2to3[i]);
919: error14to13[i] = compare_length(length1to4[i], length1to3[i]);/*1 crn.*/
920: error23to24[i] = compare_length(length2to3[i], length2to4[i]);
921: error31to32[i] = compare_length(length1to3[i], length2to3[i]);
922: error41to42[i] = compare_length(length1to4[i], length2to4[i]);
923: error12to34[i] = compare_length(length1to2[i], length3to4[i]);/*diag.*/
924:
925: /*average all of the error values together*/
926: error_avg = ((error24to13[i] + error14to23[i] + error14to13[i] +
927: error23to24[i] + error31to32[i] + error41to42[i] +
928: error12to34[i]) / 7);
929:
930: /*printf("error avg: %f\n\n", error_avg);*/
931: /*determine if the current object is considered the most likely to
932: be the ttt board so far. Average of all the error##to##'s.
933: If the current is */
934: if(ml_error > error_avg)
935: {
936: most_likely = i;
937: ml_error = error_avg;
938: }
939: }
940:
941: printf("Object %d is most likely the board with %f\%% error.\n",
942: most_likely, ml_error * 100);
943:
944: return most_likely; /*return the object number that is the board*/
945: }
946:
947: coord search_moravec(coord point1, coord point2, PGMImage *moravec)
948: {
949: int i, j; /*loop counting*/
950: float t;
951: coord temp1, temp2;
952: float dist = findDist(point1.x, point1.y, point2.x, point2.y);
953: int search_size = 3; /*'radius' that defines the neighborhood of a point*/
954:
955: coord most_likely_corner = {-1, -1};
956: int most_likely_sum1 = 0, most_likely_sum2 = 0;
957: int sum_moravec_points1, sum_moravec_points2;
958:
959: /*return find_dividers(point1, point2, ONE_THIRD);*/
960:
961: /*calculate the coordinates where the divider edges should be.*/
962: for(t = 0; t < ONE_TWELTH;t += (1 / dist))
963: {
964: /*check in both the + and - directions simultaniously.*/
965: temp1 = find_dividers(point1, point2, ONE_THIRD + t);
966: temp2 = find_dividers(point1, point2, ONE_THIRD - t);
967:
968: /*clear this before next iteration*/
969: sum_moravec_points1 = sum_moravec_points2 = 0;
970:
971: /*search the neighborhood for edge 'hits' in the moravec image*/
972: for(i = -(search_size); i <= search_size; i++)
973: {
974: for(j = -(search_size); j <= search_size; j++)
975: {
976: if(rgb_avg((*moravec).data[temp1.y + i][temp1.x + j]) > 128)
977: {
978: setCPixel(temp1.x + j, temp1.y + i, red);
979: sum_moravec_points1++;
980: }
981: if(rgb_avg((*moravec).data[temp2.y + i][temp2.x + j]) > 128)
982: {
983: setCPixel(temp2.x + j, temp2.y + i, red);
984: sum_moravec_points2++;
985: }
986:
987: }
988: }
989:
990: /*if the current point in the search is the best, return it*/
991: /*reusing search_size seems good, since it is about the right size*/
992: if((search_size <= sum_moravec_points1) &&
993: (most_likely_sum1 <= sum_moravec_points1) &&
994: !most_likely_sum2)
995: {
996: most_likely_sum1 = sum_moravec_points1;
997: most_likely_corner = temp1;
998: }
999: else if(((search_size <= sum_moravec_points2) &&
1000: (most_likely_sum2 <= sum_moravec_points2) &&
1001: !most_likely_sum1))
1002: {
1003: most_likely_sum2 = sum_moravec_points2;
1004: most_likely_corner = temp2;
1005: }
1006: }
1007:
1008: /*if a sutible point is not found, return the theoretical point*/
1009: if((most_likely_corner.x < 0) || (most_likely_corner.y < 0))
1010: {
1011: most_likely_corner = find_dividers(point1, point2, ONE_THIRD);
1012: }
1013:
1014: /* printf("(%d, %d)\n", most_likely_corner.x, most_likely_corner.y);*/
1015: return most_likely_corner;
1016: }
1017:
1018:
1019: coord find_intersection(coord line1_point1, coord line1_point2,
1020: coord line2_point1, coord line2_point2)
1021: {
1022: float line1_slope, line2_slope; /*temp slope holding variables*/
1023: float denominator, numerator; /*temp fraction holding varaibles*/
1024: float x_float; /*use to avoid obscure roundoff errors*/
1025: coord target = {-1, -1}; /*initalize temp target point*/
1026:
1027: /*find slope for first line*/
1028: if((line1_point1.x - line1_point2.x) != 0)
1029: {
1030: line1_slope = ((float)(line1_point1.y - line1_point2.y)) /
1031: ((float)(line1_point1.x - line1_point2.x));
1032: }
1033: else /*otherwise handle the undefined slope*/
1034: {
1035: /*find slope for secon line when first is undefined*/
1036: if((line2_point1.x - line2_point2.x) != 0)
1037: {
1038: line2_slope = ((float)(line2_point1.y - line2_point2.y)) /
1039: ((float)(line2_point1.x - line2_point2.x));
1040: }
1041: else /*this should never happen, but could if someone specifed the same
1042: line twice*/
1043: return target; /*target is initalized to (-1, -1)*/
1044:
1045: /*since the slope is undefined the x coord in known*/
1046: target.x = line1_point1.x;
1047: target.y = line2_slope * target.x + line2_point1.y; /*y = mx + b*/
1048: printf("line one has undefined slope\n");
1049: return target;
1050: }
1051:
1052: /*find slope for second line*/
1053: if((line2_point1.x - line2_point2.x) != 0)
1054: {
1055: line2_slope = ((float)(line2_point1.y - line2_point2.y)) /
1056: ((float)(line2_point1.x - line2_point2.x));
1057: }
1058: else
1059: {
1060: /*since the slope is undefined the x coord in known*/
1061: target.x = line1_point1.x;
1062: target.y = line1_slope * target.x + line1_point1.y; /*y = mx + b*/
1063: printf("line two has undefined slope\n");
1064: return target;
1065: }
1066:
1067: /*if both lines have defined slopes find the target point*/
1068: /* slope is m and defined by:
1069: (y1 - y2)
1070: m = ---------
1071: (x1 - x2)
1072:
1073: target calculated by setting Yt = M1*(Xt - Xa) + Ya equal to
1074: Yt = M2 * (Xt - Xc) + Yc to get
1075:
1076: (Xa*M1 - M2*Xc + Yc - Ya)
1077: Xt = -------------------------
1078: M1 - M2
1079:
1080: then to get the y coordinate sub Xt into:
1081:
1082: Yt = M1 * (Xt - Xa) + Ya
1083:
1084: Where line1_point1 = a
1085: line1_point2 = b
1086: line2_point1 = c
1087: line12point2 = d
1088: and are indicated as subscripts of their X or Y coordinate.
1089: M1 = line1_slope
1090: M2 = line2_slope
1091: */
1092:
1093: /*calculate the x coords nominator and demoninator*/
1094: numerator = (((float)((float)line1_point1.x * line1_slope)
1095: - (float)((float)line2_point1.x * line2_slope)
1096: + (float)line2_point1.y - (float)line1_point1.y));
1097: denominator = (float)(line1_slope - line2_slope);
1098:
1099: /*find the x coord, store is as a float to avoid obscure round off errors
1100: when using it to calculate the y coord.*/
1101: x_float = numerator / denominator;
1102:
1103: target.x = (int)x_float;
1104:
1105: /*find the y coord*/
1106: target.y = line1_slope * ((float)x_float - (float)line1_point1.x)
1107: + (float)line1_point1.y;
1108:
1109: return target;
1110: }
1111:
1112: /*anchor - the corner closest to the side divider point being looked for.
1113: common - the corner that the line between itself and the anchor corner contains
1114: the target divider point.
1115: anchor_opposite - the corner adjacent to the anchor corner & oppsoite common.
1116: common_opposite - the corner adjacent to the common corner & oppposite anchor.
1117: */
1118: /*return the divider point*/
1119: coord find_side_points(coord anchor, coord common, coord anchor_opposite,
1120: coord common_opposite, PGMImage *moravec)
1121: {
1122: coord temp1, temp2;
1123:
1124: temp1 = find_dividers(anchor, anchor_opposite, ONE_24TH);
1125: temp2 = find_dividers(common, common_opposite, ONE_24TH);
1126:
1127: return search_moravec(temp1, temp2, moravec);
1128: }
1129:
1130:
1131: /*find the ttt boards cross lines coordinates*/
1132: void detect_ttt_board(object board_object, ttt *board_details,
1133: PGMImage *moravec)
1134: {
1135: /*copy the corners into the ttt datatype*/
1136: memcpy(&(board_details->corners), &board_object, sizeof(object));
1137:
1138: board_details->side13 = find_side_points(board_object.corner1,
1139: board_object.corner3,
1140: board_object.corner2,
1141: board_object.corner4, moravec);
1142:
1143: board_details->side14 = find_side_points(board_object.corner1,
1144: board_object.corner4,
1145: board_object.corner2,
1146: board_object.corner3, moravec);
1147:
1148: board_details->side23 = find_side_points(board_object.corner2,
1149: board_object.corner3,
1150: board_object.corner1,
1151: board_object.corner4, moravec);
1152:
1153: board_details->side24 = find_side_points(board_object.corner2,
1154: board_object.corner4,
1155: board_object.corner1,
1156: board_object.corner3, moravec);
1157:
1158: board_details->side31 = find_side_points(board_object.corner3,
1159: board_object.corner1,
1160: board_object.corner4,
1161: board_object.corner2, moravec);
1162:
1163: board_details->side32 = find_side_points(board_object.corner3,
1164: board_object.corner2,
1165: board_object.corner4,
1166: board_object.corner1, moravec);
1167:
1168: board_details->side41 = find_side_points(board_object.corner4,
1169: board_object.corner1,
1170: board_object.corner3,
1171: board_object.corner2, moravec);
1172:
1173: board_details->side42 = find_side_points(board_object.corner4,
1174: board_object.corner2,
1175: board_object.corner3,
1176: board_object.corner1, moravec);
1177:
1178: /*correct the length of the lines that is shortend to calculate them
1179: in the first place above. simply find the intersection of the *short*
1180: line with that of the outside line between the corners.*/
1181: board_details->side13 = find_intersection(board_details->side13,
1182: board_details->side42,
1183: board_details->corners.corner1,
1184: board_details->corners.corner3);
1185: board_details->side14 = find_intersection(board_details->side14,
1186: board_details->side32,
1187: board_details->corners.corner1,
1188: board_details->corners.corner4);
1189: board_details->side23 = find_intersection(board_details->side23,
1190: board_details->side41,
1191: board_details->corners.corner2,
1192: board_details->corners.corner3);
1193: board_details->side24 = find_intersection(board_details->side24,
1194: board_details->side31,
1195: board_details->corners.corner2,
1196: board_details->corners.corner4);
1197: board_details->side31 = find_intersection(board_details->side31,
1198: board_details->side24,
1199: board_details->corners.corner3,
1200: board_details->corners.corner1);
1201: board_details->side32 = find_intersection(board_details->side32,
1202: board_details->side14,
1203: board_details->corners.corner3,
1204: board_details->corners.corner2);
1205: board_details->side41 = find_intersection(board_details->side41,
1206: board_details->side23,
1207: board_details->corners.corner4,
1208: board_details->corners.corner1);
1209: board_details->side42 = find_intersection(board_details->side42,
1210: board_details->side13,
1211: board_details->corners.corner4,
1212: board_details->corners.corner2);
1213:
1214: /*now that the sides are found, find the intersections to find the
1215: middle points*/
1216:
1217: board_details->middle1 = find_intersection(board_details->side14,
1218: board_details->side32,
1219: board_details->side13,
1220: board_details->side42);
1221:
1222: board_details->middle2 = find_intersection(board_details->side23,
1223: board_details->side41,
1224: board_details->side24,
1225: board_details->side31);
1226:
1227: board_details->middle3 = find_intersection(board_details->side31,
1228: board_details->side24,
1229: board_details->side32,
1230: board_details->side14);
1231:
1232: board_details->middle4 = find_intersection(board_details->side41,
1233: board_details->side23,
1234: board_details->side42,
1235: board_details->side13);
1236:
1237: }
1238:
1239: /*****Find the pieces***************************************************
1240: ***********************************************************************/
1241:
1242: /*Takes four points that must be in order going around the region. Also,
1243: needs a pointer to an image with the moravec filter applied.*/
1244: int search_area(coord point1, coord point2, coord point3, coord point4,
1245: PGMImage *moravec)
1246: {
1247: /*The following variables are used to calculate the existence of a marble
1248: at a location on the board or not. Uses the following basic formula
1249: new_point = ((t-1) * 1st point) + (t * 2nd point)
1250: where the start & end coords are opposite sides of the area being
1251: searched. If you take the entire area of a single position on a ttt
1252: board, the area that is searched is the region that is bouned by the
1253: points halfway between those passed in to this function.*/
1254:
1255: float t, s, r; /*hold values incrementing from 0 to 1*/
1256: coord t_start, t_end, s_start, s_end;
1257: coord temp_t, temp_s, temp_r;
1258: float dist_t, dist_s, dist_r;
1259:
1260: /*pixel count of those over the threashhold and total pixels*/
1261: int pixel_count = 0, moravec_count = 0;
1262:
1263: t_start = find_dividers(point1, point2, ONE_HALF);
1264: t_end = find_dividers(point1, point4, ONE_HALF);
1265:
1266: s_start = find_dividers(point3, point2, ONE_HALF);
1267: s_end = find_dividers(point3, point4, ONE_HALF);
1268:
1269: dist_t = findDist(t_start.x, t_start.y, t_end.x, t_end.y);
1270: dist_s = findDist(s_start.x, s_start.y, s_end.x, s_end.y);
1271:
1272: /*march two points along that parallel each other in the search area*/
1273: for(t = 0.0, s = 0.0; t <= 1.0; t += (1.0 / dist_t), s += (1.0 / dist_s))
1274: {
1275: temp_t = find_dividers(t_start, t_end, t);
1276:
1277: temp_s = find_dividers(s_start, s_end, s);
1278:
1279: dist_r = findDist(temp_t.x, temp_t.y, temp_s.x, temp_s.y);
1280:
1281: /*march a single point along that starts at temp_s and ends
1282: at temp_t. This fills in the region for the search.*/
1283: for(r = 0.0; r <= 1.0; r += (1 / dist_r))
1284: {
1285: temp_r = find_dividers(temp_s, temp_t, r);
1286:
1287: /*talley the number of edge points found (rgb. avg. >= 128)*/
1288: if(rgb_avg((*moravec).data[temp_r.y][temp_r.x]) >= 128)
1289: {
1290: setCPixel(temp_r.x, temp_r.y, blue);
1291: moravec_count++;
1292: }
1293: pixel_count++; /*increment the number of pixels*/
1294: }
1295:
1296: }
1297:
1298: /*if the number of edge pixels is greater than 10% of the total, then
1299: this is an edge of marble. The percent is there because there could be
1300: a few small blobs that get counted when the shouldn't that otherwise
1301: would give a positive hit that a marble was found*/
1302: /*printf("total: %d moravec: %d\n", pixel_count, moravec_count);*/
1303: if(moravec_count >= (pixel_count / 20))
1304: return TRUE;
1305:
1306: /*otherwise a marble isn't here*/
1307: return FALSE;
1308: }
1309:
1310: /*takes the object number that is determined to be the board*/
1311: void detect_pieces(ttt *board_data, PGMImage* moravec)
1312: {
1313: if(search_area(board_data->middle1, board_data->middle3,
1314: board_data->middle2, board_data->middle4, moravec))
1315: printf("middle has a piece\n");
1316: else
1317: printf("middle has no piece\n");
1318:
1319:
1320: if(search_area(board_data->corners.corner1, board_data->side13,
1321: board_data->middle1, board_data->side14, moravec))
1322: printf("corner 1 has a piece\n");
1323: else
1324: printf("corner 1 has no piece\n");
1325:
1326:
1327: if(search_area(board_data->corners.corner2, board_data->side23,
1328: board_data->middle2, board_data->side24, moravec))
1329: printf("corner 2 has a piece\n");
1330: else
1331: printf("corner 2 has no piece\n");
1332:
1333:
1334: if(search_area(board_data->corners.corner3, board_data->side31,
1335: board_data->middle3, board_data->side32, moravec))
1336: printf("corner 3 has a piece\n");
1337: else
1338: printf("corner 3 has no piece\n");
1339:
1340:
1341: if(search_area(board_data->corners.corner4, board_data->side41,
1342: board_data->middle4, board_data->side42, moravec))
1343: printf("corner 4 has a piece\n");
1344: else
1345: printf("corner 4 has no piece\n");
1346:
1347:
1348: if(search_area(board_data->side31, board_data->side13,
1349: board_data->middle1, board_data->middle3, moravec))
1350: printf("side 1-3 has a piece\n");
1351: else
1352: printf("side 1-3 has no piece\n");
1353:
1354: if(search_area(board_data->side41, board_data->side14,
1355: board_data->middle1, board_data->middle4, moravec))
1356: printf("side 1-4 has a piece\n");
1357: else
1358: printf("side 1-4 has no piece\n");
1359:
1360: if(search_area(board_data->side42, board_data->side24,
1361: board_data->middle2, board_data->middle4, moravec))
1362: printf("side 2-4 has a piece\n");
1363: else
1364: printf("side 2-4 has no piece\n");
1365:
1366: if(search_area(board_data->side32, board_data->side23,
1367: board_data->middle2, board_data->middle3, moravec))
1368: printf("side 2-3 has a piece\n");
1369: else
1370: printf("side 2-3 has no piece\n");
1371:
1372: }
1373:
1374:
1375: /* =================================================================
1376: * Callback functions.
1377: *
1378: * color = displayed graphics in window
1379: * menu = menu event handling
1380: * keyboard = deyboard event handling
1381: * ----------------------------------------------------------------- */
1382: void color(void)
1383: {
1384: /*glClear (GL_COLOR_BUFFER_BIT);*/
1385:
1386: /*show the current image*/
1387: showColor(img_cur);
1388:
1389: /*show the current abstract information*/
1390: showAbstract(all_objects, ttt_board);
1391:
1392: }
1393:
1394: void buffer()
1395: {
1396: /*if the drawing state of all objects is enabled, recalculate*/
1397: if(draw_abstract_lines >= 0)
1398: draw_abstract_lines = detect_corners(chain_codes, all_objects);
1399:
1400: /*if the drawing state of the object most likely to be the board is
1401: found, recalulate*/
1402: if(draw_abstract_board >= 0)
1403: draw_abstract_board = detect_game(chain_codes, all_objects);
1404:
1405: glutPostRedisplay();
1406: }
1407:
1408: #define RESTART 0
1409: #define PERS_CORR 3
1410: #define COLOR_TO_GRAY 4
1411: #define MORAVEC 5
1412: #define EDGES 6
1413: #define CORNERS 7
1414: #define BUFFERS 8
1415: #define GAME 9
1416: #define PIECES 10
1417:
1418: /*this is not a callback function, but is used inside menu() for setting
1419: new states of execution*/
1420: void reset_state(PGMImage* new_current)
1421: {
1422: img_cur = new_current;
1423: draw_abstract_lines = -1;
1424: draw_abstract_board = -1;
1425: free_chaincodes(&chain_codes);
1426: }
1427:
1428: void menu(int selection)
1429: {
1430: if(selection == RESTART)
1431: {
1432: reset_state(img_original);
1433: }
1434: if(selection == PERS_CORR)
1435: {
1436: pers_corr(img_pers_corr, img_cur);
1437: reset_state(img_pers_corr);
1438: }
1439: if(selection == COLOR_TO_GRAY)
1440: {
1441: color_to_gray(img_grayscale, img_cur);
1442: reset_state(img_grayscale);
1443: }
1444: if(selection == MORAVEC)
1445: {
1446: moravec(img_moravec, img_cur);
1447: reset_state(img_moravec);
1448: }
1449: if(selection == EDGES)
1450: {
1451: showChain(img_cur, &chain_codes);
1452: }
1453: if(selection == CORNERS)
1454: {
1455: showChain(img_cur, &chain_codes);
1456:
1457: draw_abstract_lines = detect_corners(chain_codes, all_objects);
1458: }
1459: if(selection == BUFFERS)
1460: {
1461: if(is_buffered == FALSE)
1462: {
1463: glutIdleFunc(buffer);
1464: is_buffered = TRUE;
1465: }
1466: else
1467: {
1468: glutIdleFunc(NULL);
1469: is_buffered = FALSE;
1470: }
1471: }
1472: if(selection == GAME)
1473: {
1474: /*need an image with the moravec filter applied*/
1475: /*don't calculating this if it is the current image!!!
1476: Bad things happen like memseting to zero the current image.*/
1477: if(img_cur != img_pers_corr)
1478: pers_corr(img_pers_corr, img_cur);
1479:
1480: showChain(img_pers_corr, &chain_codes);
1481: detect_corners(chain_codes, all_objects);
1482:
1483: /*do moravec first, then perspective to prevent the loss of edges
1484: from doing the perspective first*/
1485: moravec(img_moravec, img_cur);
1486: pers_corr(img_pers_corr, img_moravec);
1487:
1488: /*detect the ttt game board*/
1489: draw_abstract_board = detect_game(chain_codes, all_objects);
1490: detect_ttt_board(all_objects[draw_abstract_board], ttt_board,
1491: img_pers_corr);
1492:
1493: pers_corr(img_pers_corr, img_cur);
1494: img_cur = img_pers_corr;
1495: }
1496: if(selection == PIECES)
1497: {
1498: /*need an image with the moravec filter applied*/
1499: /*don't calculating this if it is the current image!!!
1500: Bad things happen like memseting to zero the current image.*/
1501: if(img_cur != img_pers_corr)
1502: pers_corr(img_pers_corr, img_cur);
1503:
1504: /*detect the ttt game board*/
1505: showChain(img_pers_corr, &chain_codes);
1506: detect_corners(chain_codes, all_objects);
1507: moravec(img_moravec, img_cur);
1508: pers_corr(img_pers_corr, img_moravec);
1509: draw_abstract_board = detect_game(chain_codes, all_objects);
1510: detect_ttt_board(all_objects[draw_abstract_board], ttt_board,
1511: img_pers_corr);
1512:
1513: /*detect the locations of the pieces*/
1514: detect_pieces(ttt_board, img_pers_corr);
1515:
1516: pers_corr(img_pers_corr, img_cur);
1517: img_cur = img_pers_corr;
1518:
1519: glFlush();
1520: return;
1521: }
1522:
1523: glutPostRedisplay(); /*redraw the image*/
1524: }
1525:
1526: void keyboard(unsigned char key, int x, int y)
1527: {
1528: switch (key)
1529: {
1530: case 27:
1531: exit(0);
1532: break;
1533: }
1534: }
1535:
1536: void mouse(int button, int state, int x, int y)
1537: {
1538: char temp[50];
1539:
1540: if(button == GLUT_LEFT_BUTTON && state == GLUT_DOWN)
1541: {
1542: sprintf(temp, "(x, y): (%d, %d) red: %d green: %d blue: %d\n",
1543: x, VSIZE - y, (*img_cur).data[VSIZE - y][x].red,
1544: (*img_cur).data[VSIZE - y][x].green,
1545: (*img_cur).data[VSIZE - y][x].blue);
1546: setCRect(0, 0, 200, 12, black);
1547: glColor3f(1.0, 0.0, 0.0);
1548: drawString(0, 0, GLUT_BITMAP_TIMES_ROMAN_10, temp, red);
1549: glFlush();
1550: }
1551: }
1552:
1553:
1554: /* =================================================================
1555: * init() & parse_command_line()
1556: * initalize none-OpenGL related things.
1557: * ----------------------------------------------------------------- */
1558:
1559: /*set global flag variables from things specified at commandline.*/
1560: /*return the filename specified, if none specified exit().*/
1561: char* parse_command_line(int argc, char** argv)
1562: {
1563: /*parse the command line*/
1564: if(argc == 1)
1565: {
1566: printf("To few parameters.\n");
1567: printf("Usage: research <file.pgm>\n");
1568: exit(1);
1569: }
1570: else if(argc == 2)
1571: {
1572: return argv[1];
1573: }
1574: else
1575: {
1576: printf("To many parameters.\n");
1577: printf("Usage: research <file.pgm>\n");
1578: exit(1);
1579: }
1580: }
1581:
1582: char* init (int argc, char** argv)
1583: {
1584: char* PGMfileName;/*pointer to the string containing the filename*/
1585:
1586: /*parse the command line*/
1587: PGMfileName = parse_command_line(argc, argv);
1588:
1589: /*
1590: * Read in image file. - note: sets our global values, too.
1591: * ----------------------------------------------------------------- */
1592:
1593: /*allocate memory for original image*/
1594: img_original = (PGMImage*) malloc(sizeof(PGMImage));
1595: getPGMfile(PGMfileName, img_original);
1596: HSIZE = (*img_original).width;
1597: VSIZE = (*img_original).height;
1598: MVAL = (*img_original).maxVal;
1599:
1600: img_cur = img_original; /*VERY IMPORTANT to set this*/
1601:
1602: /*allocate memory for pers. corr. image*/
1603: img_pers_corr = (PGMImage*) malloc(sizeof(PGMImage));
1604: (*img_pers_corr).width = HSIZE;
1605: (*img_pers_corr).height = VSIZE;
1606: (*img_pers_corr).maxVal = 255;
1607:
1608: img_grayscale = (PGMImage*) malloc(sizeof(PGMImage));
1609: (*img_grayscale).width = HSIZE;
1610: (*img_grayscale).height = VSIZE;
1611: (*img_grayscale).maxVal = 255;
1612:
1613: img_moravec = (PGMImage*) malloc(sizeof(PGMImage));
1614: (*img_moravec).width = HSIZE;
1615: (*img_moravec).height = VSIZE;
1616: (*img_moravec).maxVal = 255;
1617:
1618:
1619: all_objects = (object*) malloc(sizeof(object) * MAX_CHAINS);
1620: memset(all_objects, 0, sizeof(object) * MAX_CHAINS);
1621:
1622: ttt_board = (ttt*) malloc(sizeof(ttt));
1623: memset(ttt_board, 0, sizeof(ttt));
1624:
1625: return PGMfileName;
1626: }
1627:
1628:
1629: int main(int argc, char** argv)
1630: {
1631: char* PGMfileName;
1632: int WindowID; /*unique window id, there is only one used*/
1633: int i; /*looping variable*/
1634:
1635: /*
1636: * Call our init function to define non-OpenGL related things.
1637: * Have init return a pointer to the filename, used to display the
1638: * filename in the titlebar of the window.
1639: * ----------------------------------------------------------------- */
1640: PGMfileName = init (argc, argv);
1641:
1642: /*
1643: * Initialize the glut package.
1644: * ----------------------------------------------------------------- */
1645: glutInit(&argc, argv);
1646: glutInitDisplayMode (GLUT_SINGLE | GLUT_RGB);
1647:
1648: /*
1649: * Define a new window (its size, position and title).
1650: * ----------------------------------------------------------------- */
1651: glutInitWindowSize (HSIZE, VSIZE); /*size*/
1652: glutInitWindowPosition (10, 10); /*position*/
1653: WindowID = glutCreateWindow (PGMfileName); /*title*/
1654: glutSetWindow(WindowID);
1655: glutDisplayFunc(color);
1656:
1657: /*
1658: * select clearing color - white
1659: */
1660: glClearColor (1.0, 1.0, 1.0, 0.0);
1661:
1662: /*
1663: * initialize viewport values
1664: */
1665: glMatrixMode(GL_PROJECTION);
1666: glLoadIdentity();
1667: glOrtho(-1.0, 1.0, -1.0, 1.0, -1.0, 1.0);
1668:
1669: /*add menus*/
1670: glutCreateMenu(menu);
1671: glutAddMenuEntry("Restart", RESTART);
1672: glutAddMenuEntry("perspective correction", PERS_CORR);
1673: glutAddMenuEntry("color to gray", COLOR_TO_GRAY);
1674: glutAddMenuEntry("moravec", MORAVEC);
1675: glutAddMenuEntry("edges", EDGES);
1676: glutAddMenuEntry("corners", CORNERS);
1677: glutAddMenuEntry("detect game", GAME);
1678: glutAddMenuEntry("detect pieces", PIECES);
1679: glutAddMenuEntry("toggle buffering", BUFFERS);
1680: glutAttachMenu(GLUT_RIGHT_BUTTON);
1681:
1682: glutMouseFunc(mouse);
1683: glutKeyboardFunc(keyboard);
1684: glutMainLoop();
1685:
1686: /*
1687: * When we reach here, we've left the event loop and are ready to
1688: * exit.
1689: * ----------------------------------------------------------------- */
1690: return 0;
1691: }
1692: