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