Appendix J - chaincode.c
1: #include "linked_list.h"
2: #include "chaincode.h"
3: #include "ttt_vision.h"
4: #include "pgm.h"
5: #include < string.h >
6:
7: /*******Evil globals*********************************/
8:
9: int cur_threash_val; /*for speed optimization of chain code recursion*/
10: int back_ground;
11:
12: const RGB_INT chaincode_color = {255, 255, 255};
13:
14: extern bool display_verbose;
15:
16: /******CHAIN CODE************************************************
17: ****************************************************************/
18:
19: /*returns TRUE if the chain code loops around itself, otherwise false*/
20: int checkCode(list_info* list_pointers, int x_current, int y_current,
21: int x_check, int y_check, int dir)
22: {
23: list_info temp;
24:
25: ToFirst(list_pointers);
26:
27: while(!AtEnd(list_pointers))
28: {
29: /*needed to check two nodes ahead in following if*/
30: temp = RetrieveNextNode(list_pointers);
31:
32: /*check two consecutive points*/
33: if((RetrieveInfo(list_pointers).location.x == x_current) &&
34: (RetrieveInfo(list_pointers).location.y == y_current) &&
35: (RetrieveInfo(list_pointers).code == dir) &&
36: (RetrieveNextInfo(list_pointers).location.x == x_check) &&
37: (RetrieveNextInfo(list_pointers).location.y == y_check) &&
38: (RetrieveNextNode(&temp).cur)) /*don't count the new node already*/
39: {
40: return TRUE; /*The chain code end looped around*/
41: }
42: else
43: /*currentNode = RetrieveNextNode(list_pointers);*/
44: Advance(list_pointers);
45: }
46: return FALSE;
47: }
48:
49: /*
50: Preconditions:
51: 1st parameter: integer value containing the current x coordinate.
52: 2nd parameter: integer value containing the current y coordinate.
53: 3rd parameter: pointer to the pgm image being used.
54: Postconditions: return true if pixel is deemed boarder of object, false
55: otherwise.*/
56: int checkThings(int x_check, int y_check, PGMImage *img)
57: {
58:
59: /*check for being in bounds*/
60: if((x_check < 0) || (y_check < 0) || (x_check >= (*img).width) ||
61: (y_check >= (*img).height))
62: return FALSE;
63:
64: /*tests if the next pixel is greater than the threashing value. This
65: value (cur_threash_val) should be set to the return value of
66: img_pxl_avg(). Also, checks if the pixel is considered in the background
67: or forground agains the value in back_ground. If so, return true to
68: indicate create new node.*/
69: if((rgb_avg((*img).data[y_check][x_check]) > cur_threash_val)
70: && (back_ground < 0))
71: return TRUE;
72:
73: /*same thing as above, just for things less than, rathur than greater than*/
74: if((rgb_avg((*img).data[y_check][x_check]) < cur_threash_val)
75: && (back_ground > 0))
76: return TRUE;
77:
78: return FALSE;
79: }
80:
81: chain neighborhood_point(int x_coord, int y_coord, int dir)
82: {
83: chain temp = {{x_coord, y_coord}, dir};
84:
85: if(dir == EAST)
86: temp.location.x++;
87: else if(dir == NORTHEAST)
88: {
89: temp.location.x++;
90: temp.location.y++;
91: }
92: else if(dir == NORTH)
93: temp.location.y++;
94: else if(dir == NORTHWEST)
95: {
96: temp.location.x--;
97: temp.location.y++;
98: }
99: else if(dir == WEST)
100: temp.location.x--;
101: else if(dir == SOUTHWEST)
102: {
103: temp.location.x--;
104: temp.location.y--;
105: }
106: else if(dir == SOUTH)
107: temp.location.y--;
108: else if(dir == SOUTHEAST)
109: {
110: temp.location.x++;
111: temp.location.y--;
112: }
113:
114: return temp;
115: }
116:
117: /*determines the chain code for a starting pixel*/
118: /*this chain code uses 8 connectivity*/
119: /*Note: There are many different coordinate systems at work in this function.*/
120: /*The (*img).data[][] are column major and have are therefore [y][x] or [j][i].
121: This is also asuming (0,0) is bottom left, where the other code assumes
122: top left is (0, 0). If it looks strange, look harder!!!*/
123: /*Preconditions:
124: 1st parameter: pointer to the pgm image being used.
125: 2nd parameter: integer value containing the current x coordinate.
126: 3rd parameter: integer value containing the current y coordinate.
127: 4th parameter: integer value containing the current direction code.
128: 5th parameter: pointer to the last node of the chain code.
129: 6th parameter: pointer to the first node of the chain code.*/
130: /*This function assumes the (0, 0) point is in the lower left*/
131:
132: int chaincode(PGMImage *img, int x, int y, int dir, list_info* list_pointers)
133: {
134: int i; /*loop counting*/
135: int next /*next direction to check*/;
136: chain next_point_to_check; /*next_point_to_check What else?*/
137:
138: next = (dir + 5) % 8; /*better initail choice?*/
139:
140: /*printf("next: %d x: %d y: %d\n", next, x, y);*/
141: for(i = 0; i < 8; i++)
142: {
143: /*determine the next point to check*/
144: next_point_to_check = neighborhood_point(x, y, next);
145:
146: if(checkThings(next_point_to_check.location.x,
147: next_point_to_check.location.y, img))
148: {
149: /*setCPixel(next_point_to_check.location.x, next_point_to_check.location.y,
150: chaincode_color);*/
151:
152: /*create the new node to go last in the chain*/
153: InsertAfter(next_point_to_check, list_pointers);
154: /*Advance(list_pointers);*/
155:
156: /*if the next chaincode function in the recursion or the current state
157: is the final state of the the chain code; recursively returns DONE
158: back through all the levels to stop the chain code.*/
159: if(checkCode(list_pointers, x, y, next_point_to_check.location.x,
160: next_point_to_check.location.y, dir))
161: {
162: return NONE;
163: }
164:
165: if(NONE == chaincode(img, next_point_to_check.location.x,
166: next_point_to_check.location.y, next,
167: list_pointers))
168: return NONE;
169: }
170:
171: /*set next for next iteration*/
172: next = (next + 1) % 8;
173: }
174: return FALSE;
175: }
176:
177: /*returns true if the point is already in one of the chains, false otherwise*/
178: int alreadyFound(int initThreashFlag, int i, int j, list_info* found)
179: {
180: int k; /*loop counting*/
181: list_info temp; /*temporary node pointer*/
182:
183: /*while there are codes to check...*/
184: for(k = 0; (k < MAX_NUMBER_OF_CHAINS) && (found[k].head); k++)
185: {
186: memcpy(&temp, &found[k], sizeof(list_info));
187: while(!AtEnd(&temp)) /*...check them.*/
188: {
189: /*if point has already been found*/
190: if((RetrieveInfo(&temp).location.x == i) &&
191: (RetrieveInfo(&temp).location.y == j))
192: {
193: return TRUE;
194: break;
195: }
196: Advance(&temp);
197: }
198: /*Don't forget the last point!!!*/
199: if((RetrieveInfo(&temp).location.x == i) &&
200: (RetrieveInfo(&temp).location.y == j))
201: {
202: return TRUE;
203: break;
204: }
205: }
206:
207: return FALSE;
208: }
209:
210: /*saves a chain code to file. Was usefull during debuging now is just
211: a cool thing to leave in*/
212: /*1st: pointer to beginning of a chaincode
213: 2nd: the index of the chain code for destiqushing the 'chain' files*/
214: void saveChainCode(list_info save_chain, int count)
215: {
216: char filename[12];
217: FILE* outfile;
218: sprintf(filename, "chain%d", count);
219: outfile = fopen(filename, "w"); /*output file for chaincode*/
220: /*printf("Writing chain code to file %s.\n", filename);*/
221:
222: ToFirst(&save_chain);
223: while(!AtEnd(&save_chain))
224: {
225:
226: fprintf(outfile, "%d %d %d\n", RetrieveInfo(&save_chain).location.x,
227: RetrieveInfo(&save_chain).location.y,
228: RetrieveInfo(&save_chain).code);
229: Advance(&save_chain);
230: }
231: fclose(outfile);
232: }
233:
234:
235:
236: /*frees the memory that the chain code(s) are using*/
237: /*aogccp = address of global chain code pointer*/
238: /*upon success the pointer whose address is passed in is set to NULL.*/
239: void free_chaincodes(list_info** aogccp)
240: {
241: int i; /*loop counting*/
242:
243: /*for each chaincode, free all of the nodes.*/
244: for(i = 0; aogccp && (*aogccp) && (*aogccp)[i].cur && i < MAX_CHAINS; i++)
245: {
246: FreeList(&(*aogccp)[i]);
247: }
248:
249: free(*aogccp); /*free the array of pointers to chaincodes*/
250:
251: *aogccp = NULL; /*set global to NULL indicating there isn't a chaincode*/
252: }
253:
254:
255: list_info* showChain(PGMImage *original, list_info** original_chains)
256: {
257: int i, j; /*loop counting*/
258: int count = 0; /*array index holder*/
259: int initThreashFlag = img_pxl_avg(original);
260: list_info *the_lists;
261:
262: if(display_verbose)
263: printf("Finding chain code(s). ");
264:
265: /*If the_lists point to an array of list_infos (chaincodes), then free
266: the memory before allocating more. If the_lists is NULL, then there
267: aren't allocated chaincodes and nothing will change.*/
268: free_chaincodes(original_chains);
269:
270: /*allocate an array of pointers to chainCodes, then initalize their
271: values to NULL*/
272: the_lists = (list_info*)
273: malloc(MAX_NUMBER_OF_CHAINS * sizeof(list_info));
274: memset(the_lists, 0, MAX_NUMBER_OF_CHAINS * sizeof(list_info));
275:
276: cur_threash_val = initThreashFlag; /*set global variables*/
277: back_ground = background(initThreashFlag, original);
278:
279: /*search image until a pixel is found with threasholded value of the
280: object. i & j will then contain the starting coordinate.*/
281: for(i = 0; i < (*original).width; i++) /*x direction*/
282: {
283: for(j = (*original).height - 1; j >= 0; j--) /*y direction*/
284: {
285: /*skip to the next iteration if pixel isn't "good" enough*/
286: if(!checkThings(i, j, original))
287: continue;
288:
289: /*skip to the next iteration, which will be at the top of the next
290: collumn. This is true when the pixel has already been found in
291: one of the chain codes.*/
292: else if(alreadyFound(initThreashFlag, i, j, the_lists))
293: break;
294:
295: else
296: {
297: /*printf("chaincode: %d\n", count);*/
298: /*printf("The starting coordinate is (x, y): (%d, %d)\n", i, j);*/
299:
300: /*Initalize the lists*/
301: InitList(&the_lists[count]);
302:
303: chaincode(original, i, j, SOUTHEAST, &the_lists[count]);
304:
305: if(the_lists[count].cur != NULL)/*avoid writing zero length chain*/
306: {
307: /*send the chaincode data to file, usefull for debuggin.*/
308: saveChainCode(the_lists[count], count);
309: count++; /*advance the beginning counter*/
310: }
311:
312: /*force end of loops, leaving code when finished looping
313: to still execute, since the number of chains is filled to max.*/
314: if(count >= MAX_NUMBER_OF_CHAINS)
315: i = (*original).width;
316:
317: break; /*check the next collumn*/
318: }
319: }
320: }
321: if(display_verbose)
322: printf("%d were found.\n", count);
323:
324: *original_chains = the_lists;
325: return the_lists;
326: }