// search.c V1.00 27.2.2000 #include #include "vision.h" #include "search.h" #define DEBUG 0 /***************************************************************** ********** UTILITY FUNCTIONS ********** *****************************************************************/ /***************************************************** Function that adds a new node to a list. Returns pointer to the beginning of the new list. Parameters: ----------- *list: Pointer to the beginning of the list. index: If 1 follow index links, else follow node links. arg_value: Value to be added. If arg_value is already in the list, nothing will be added. ******************************************************/ NODE *add_node(NODE *list, int index, int arg_value) { NODE *temp = NULL; // ----- If list is empty, add first node ----- if(list == NULL) { NODE *p = (NODE *)malloc(sizeof(NODE)); if(p == NULL) return NULL; p->value = arg_value; p->index_link = NULL; p->node_link = NULL; return p; } temp = list; // ----- Add index node ----- if(index == 1) { while( (temp->value != arg_value) && (temp->index_link != NULL) ) temp = temp->index_link; // ----- If arg_value was not found, add new node ----- if(temp->value != arg_value) { NODE *p = (NODE *)malloc(sizeof(NODE)); if(p == NULL) { printf("Unable to allocate memory (add_node)!"); return NULL; } p->value = arg_value; p->index_link = NULL; p->node_link = NULL; temp->index_link = p; } // ----- Add data node ----- } else { while( (temp->value != arg_value) && (temp->node_link != NULL) ) temp = temp->node_link; // ----- If arg_value was not found, add new node ----- if(temp->value != arg_value) { NODE *p = (NODE *)malloc(sizeof(NODE)); if(p == NULL) { printf("Unable to allocate memory (add_node)!"); return NULL; } p->value = arg_value; p->index_link = NULL; p->node_link = NULL; temp->node_link = p; } } return list; } /****************************************************** Free memory allocated for a list. Parameters: ----------- *list: List to be removed. index: If 1 follow index links, else follow node links. ******************************************************/ void free_list(NODE *list, int index) { NODE *previous; while(list != NULL) { previous = list; if(index == 1) list = list->index_link; else list = list->node_link; free(previous); } } /****************************************************** Function that compares two classes. If classes are equal, function returns 1. ******************************************************/ int equal_classes(NODE *list, int index_class, int class) { int equals = 0; NODE *temp = list; // ----- Always use the smaller class value as index value ----- if(index_class == class) return 1; else if(index_class > class) { int temp_class = class; class = index_class; index_class = temp_class; } if(temp == NULL) return 0; // ----- Search for index_class ----- while( (temp->value != index_class) && (temp->index_link != NULL) ) temp = temp->index_link; // ----- If index_class was found, search data nodes ----- if(temp->value == index_class) { temp = temp->node_link; while( (temp->value != class) && (temp->node_link != NULL) ) temp = temp->node_link; // ----- If data node was found, return 1 ----- if(temp->value == class) equals = 1; } return equals; } /***************************************************** Function that marks two classes as equal. *****************************************************/ NODE *mark_as_equal(NODE *list, int index_class, int class) { NODE *temp; // ----- Always use the smaller class value as index value ----- if(index_class == class) return; else if(index_class > class) { int temp_class = class; class = index_class; index_class = temp_class; } list = add_node(list, 1, index_class); temp = list; while(temp->value != index_class) temp = temp->index_link; temp->node_link = add_node(temp->node_link, 0, class); return list; } /****************************************************** Function that returns the class of a neighboring pixel. Parameters: ----------- *area_classes: Array that contains the classes of pixels row, col: Coordinates of the present pixel cols: Number of pixels per row. neighbor: Indicates neighbor (0=left, 1=upper) ******************************************************/ int return_class(int *area_classes, int row, int col, int cols, int neighbor) { if(neighbor == 0) { if(col > 0) return area_classes[(row*cols)+col-1]; else return 0; } else { if(row > 0) return area_classes[((row-1)*cols)+col]; else return 0; } } /******************************************************************** Function that combines dimension data of equal classes using recursion. Parameters: ----------- *equal_data: List, that contains data on equal classes. *this_class: Pointer to the index node of this class. class_dimensions[][]: Table that list the dimensions (=border coordinates) of each class. parent_class: Class that is "at the top" of this recursive chain. this_class: Class that is to be processed now. ********************************************************************/ void process_equal_classes(NODE *equal_data, NODE *this_class, int class_dimensions[MAX_CLASSES][5], int parent_class) { int i, j; NODE *equal = this_class->node_link; NODE *temp = NULL; // ----- Process all classes marked as equal with this class ----- while(equal != NULL) { if(class_dimensions[equal->value][4] == 1) { if(class_dimensions[equal->value][0] < class_dimensions[parent_class][0]) class_dimensions[parent_class][0] = class_dimensions[equal->value][0]; if(class_dimensions[equal->value][1] > class_dimensions[parent_class][1]) class_dimensions[parent_class][1] = class_dimensions[equal->value][1]; if(class_dimensions[equal->value][2] > class_dimensions[parent_class][2]) class_dimensions[parent_class][2] = class_dimensions[equal->value][2]; if(class_dimensions[equal->value][3] < class_dimensions[parent_class][3]) class_dimensions[parent_class][3] = class_dimensions[equal->value][3]; class_dimensions[equal->value][4] = 0; // ------ Find the index node corresponding to equal (if it exists) ----- temp = equal_data; while( (temp->value != equal->value) && (temp->index_link != NULL) ) temp = temp->index_link; if(temp->value == equal->value) process_equal_classes(equal_data, temp, class_dimensions, parent_class); } equal = equal->node_link; } } /***************************************************************** ********** SEARCH FUNCTIONS ********** *****************************************************************/ /********************************************************************** Function for searching landmark areas from the picture. The function returns the coordinates of separate landmark areas that were found in an array: array[0]: Number of landmark areas that were found array[1]: X coordinate of first area array[2]: Y coordinate of first area array[3]: X coordinate of second area ... ... Parameters: ----------- picture_: Preprocessed picture that contains only the valid pixels of the original picture. area_threshold: Persentage of the color in an area pixel (0-100) *area_color: Pointer to the area color array(picture_r, _g or _b) **********************************************************************/ int *simpleNeighborSearch(bitPicture *picture) { // --- Array of classes assigned to each pixel in the original picture --- int *area_classes = NULL; // --- List, that contains data on which classes are equal ----- NODE *equal_data = NULL; // --- Table that lists the dimensions (border coordinates) of --- // --- each class (0=upper, 1=right, 2=lower, 3=left, 4 indicates --- // --- state of these dimensions (0=passive, 1=active)) --- int class_dimensions[MAX_CLASSES][5]; // ----- Pointer to the coordinates of found landmark areas ----- int *result_coordinates = NULL; int next_class = 1; int i, j; int rows, cols; // ----- Check picture ----- if(picture == NULL) { printf("Null picture parameter (simpleNeighborSearch)!\n"); return NULL; } rows = picture->y_size; cols = picture->x_size; // ----- Allocate memory for area_classes ----- area_classes = (int *)malloc(rows*cols*sizeof(int)); if(area_classes == NULL) { printf("Memory allocation failed (simpleNeighborSearch)!\n"); return NULL; } // ----- Initialize area_classes ----- for(i=0; ibuf[i*cols+j] > 0) { // ----- Read class values of the neighboring pixels ----- int temp_left = return_class(area_classes, i, j, cols, 0); int temp_upper = return_class(area_classes, i, j, cols, 1); int temp_class_value; if(DEBUG) printf("\nleft: %d\t\tupper: %d\n", temp_left, temp_upper); // ----- Assign a class value to present pixel ----- if( (temp_left == 0) && (temp_upper == 0) ) { if(DEBUG) printf("a1 (%d,%d): next_class:%d\n", j, i, next_class); temp_class_value = next_class; next_class++; } else if( (temp_left != temp_upper) && (temp_left > 0) && (temp_upper > 0) ) { if(DEBUG) printf("a2 (%d,%d): next_class:%d\n", j, i, next_class); if(temp_upper > temp_left) temp_class_value = temp_left; else temp_class_value = temp_upper; equal_data = mark_as_equal(equal_data, temp_left-1, temp_upper-1); } else { if(temp_left > temp_upper) { if(DEBUG) printf("a3_a (%d,%d): next_class:%d\n", j, i, next_class); temp_class_value = temp_left; } else { if(DEBUG) printf("a3_b (%d,%d): next_class:%d\n", j, i, next_class); temp_class_value = temp_upper; } } // ----- Process the class only if the total number of ----- // ----- classes is within the set limit MAX_CLASSES ----- if(temp_class_value <= MAX_CLASSES) { area_classes[i*cols+j] = temp_class_value; // ----- If not already marked, mark dimensions as active ----- if(class_dimensions[temp_class_value-1][4] == 0) class_dimensions[temp_class_value-1][4] = 1; // ----- Update class_dimensions ----- if(i < class_dimensions[temp_class_value-1][0]) class_dimensions[temp_class_value-1][0] = i; if(j > class_dimensions[temp_class_value-1][1]) class_dimensions[temp_class_value-1][1] = j; if(i > class_dimensions[temp_class_value-1][2]) class_dimensions[temp_class_value-1][2] = i; if(j < class_dimensions[temp_class_value-1][3]) class_dimensions[temp_class_value-1][3] = j; if(DEBUG) printf("UPDATED %d (%d,%d): %d %d %d %d %d\n", temp_class_value, i, j, class_dimensions[temp_class_value-1][0], class_dimensions[temp_class_value-1][1], class_dimensions[temp_class_value-1][2], class_dimensions[temp_class_value-1][3], class_dimensions[temp_class_value-1][4]); } } // ----- If the current pixel is not valid ----- else { area_classes[i*cols+j] = 0; } } } // ----- Combine dimension data of equal classes ----- // After this section, table class_dimensions will contain as many // active rows as there are separate landmark areas in the original // picture. Active rows will contain border coordinates of the separate // landmark areas, even if the areas contain more than one class. // However, these areas are not necessarily big enough to be included // in the returned coordinates. if(equal_data != NULL) { NODE *temp_index = equal_data; // ----- Process all index nodes ----- while(temp_index != NULL) { // ----- Process this index node if it has equal ----- // ----- classes and it is active ----- if( (temp_index->node_link != NULL) && (class_dimensions[temp_index->value][4] == 1) ) { process_equal_classes(equal_data, temp_index, class_dimensions, temp_index->value); } temp_index = temp_index->index_link; } } // ----- Allocate memory for result_coordinates ----- result_coordinates = (int *)malloc(sizeof(int)); if(result_coordinates == NULL) { printf("Memory allocation failed (simpleNeighborSearch)!\n"); return NULL; } result_coordinates[0] = 0; // ----- Calculate centerpoints of each landmark area ----- for(i=0; i= MIN_AREA_SIZE) && (temp_dx >= MIN_AREA_SIZE) ) { if(DEBUG) printf("\n%d: dy=%d dx=%d\n", i+1, temp_dy, temp_dx); temp_dy = class_dimensions[i][0] + (int)(temp_dy/2); temp_dx = class_dimensions[i][3] + (int)(temp_dx/2); result_coordinates[0]++; result_coordinates = (int *)realloc(result_coordinates, (result_coordinates[0]*2+1) * sizeof(int)); if(result_coordinates == NULL) { printf("Memory allocation failed (simpleNeighborSearch)!\n"); return NULL; } result_coordinates[result_coordinates[0]*2] = temp_dy; result_coordinates[result_coordinates[0]*2-1] = temp_dx; } // ----- If the area is not big enough, mark it as inactive ----- else { class_dimensions[i][4] = 0; } } } if(DEBUG && (equal_data != NULL)) { NODE *temp1 = equal_data; NODE *temp2; printf("\n\nEQUAL_DATA:\n"); while(temp1 != NULL) { printf("\n%d: ", temp1->value); temp2 = temp1->node_link; while(temp2 != NULL) { printf("%d, ", temp2->value); temp2 = temp2->node_link; } temp1 = temp1->index_link; } } // ----- Free memory allocated for equal_data ----- if(equal_data != NULL) { NODE *temp = equal_data; while(temp != NULL) { free_list(temp->node_link, 0); temp = temp->index_link; } free_list(equal_data, 1); } return result_coordinates; }