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