diff options
Diffstat (limited to 'src/lib/seg')
| -rw-r--r-- | src/lib/seg/mask_data.c | 226 | ||||
| -rw-r--r-- | src/lib/seg/util.c | 292 |
2 files changed, 0 insertions, 518 deletions
diff --git a/src/lib/seg/mask_data.c b/src/lib/seg/mask_data.c deleted file mode 100644 index 2f3a51a..0000000 --- a/src/lib/seg/mask_data.c +++ /dev/null @@ -1,226 +0,0 @@ -#include <lib/seg/mask_data.h> - -#include <stdio.h> - -// Allocate Mask Data for Label -struct MaskData* create_mask_data(uint16_t label) -{ - struct MaskData *data = (struct MaskData*)malloc(sizeof(struct MaskData)); - data->label = label; - data->area = 0; - data->perimeter = 0; - return data; -} - -// Compare mask data labels -bool_t compare_labels(struct MaskData* left, struct MaskData* right) -{ - return left->label < right->label; -} - -// Create AVL Mask node -struct AVLNode* create_avl_mask_node(struct MaskData* data) -{ - struct AVLNode* node = (struct AVLNode*)malloc(sizeof(struct AVLNode)); - if (node == NULL) { - return NULL; - } - node->data = data; - node->compare = (bool_t (*)(void*,void*))&compare_labels; - node->left = NULL; - node->right = NULL; - node->height = 1; // Leaf initially - return node; -} - -// Insert MaskData into the AVL Tree -struct Result insert_mask(struct AVLNode* node, struct MaskData* data) -{ - struct Result result; - // 1. Standard BST insertion - if (node == NULL) { - return (struct Result) {create_avl_mask_node(data), TRUE}; - } - - struct MaskData *node_data = (struct MaskData*)node->data; - if (node->compare(data, node_data)) { - result = insert_mask(node->left, data); - if (!result.success) { - fprintf(stderr, "Failed to insert!"); - return result; - } - node->left = (struct AVLNode*)result.data; - } else if (node->compare(node->data, data)) { - result = insert_mask(node->right, data); - if (!result.success) { - fprintf(stderr, "Failed to insert!"); - return result; - } - node->right = (struct AVLNode*)result.data; - } else { - return (struct Result) {node, FALSE}; - } - - // 2. Update height of the ancestor node - node->height = 1 + max_height(get_height(node->left), get_height(node->right)); - - ssize_t balance = get_balance_factor(node); - - // 4. If the node becomes unbalanced - - // LeftLeft - if ((balance > 1) && node->compare(data, node->left->data)) { - return (struct Result) {right_rotate(node), TRUE}; - } - // RightRight - if ((balance < -1) && node->compare(node->right->data, data)) { - return (struct Result) {left_rotate(node), TRUE}; - } - // LeftRight - if ((balance > 1) && node->compare(node->left->data, data)) { - return (struct Result) {right_rotate(node), TRUE}; - } - // RightLeft - if ((balance < -1) && node->compare(data,node->right->data)) { - return (struct Result) {left_rotate(node), TRUE}; - } - return (struct Result) {node, TRUE}; -} - -// Allocate a label's Mask data in a tree -// If it already exists, skip the allocation -struct AVLNode* insert_mask_alloc(struct AVLNode* node, uint16_t label) -{ - struct MaskData* data = create_mask_data(label); - struct Result result = insert_mask(node, data); - if (!result.success) { - free(data); - } - return (struct AVLNode*)result.data; -} - -// Print AVL Node Mask Data Label -void print_label(struct AVLNode* root) -{ - if (root != NULL) { - print_label(root->left); - struct MaskData* data = root->data; - printf("%d: (%zu, %zu) ", data->label, data->area, data->perimeter); - print_label(root->right); - } -} - -// Increase the label's area -bool_t increase_label_area(struct AVLNode* root, uint16_t label) -{ - if (root == NULL) { - return FALSE; - } - struct MaskData* data = (struct MaskData*)root->data; - if (data->label == label) { - data->area++; - } - else if (data->label > label) { - return increase_label_area(root->left, label); - } - else if (data->label < label) { - return increase_label_area(root->right, label); - } - return TRUE; -} - -// Increase the label's perimeter -bool_t increase_label_perimeter(struct AVLNode* root, uint16_t label) -{ - if (root == NULL) { - return FALSE; - } - struct MaskData* data = (struct MaskData*)root->data; - if (data->label == label) { - data->perimeter++; - } - else if (data->label > label) { - return increase_label_perimeter(root->left, label); - } - else if (data->label < label) { - return increase_label_perimeter(root->right, label); - } - return TRUE; -} - -// Increase the label's area -// Create an AVL node if it doesn't exist -struct AVLNode* increase_label_area_alloc(struct AVLNode* root, uint16_t label) -{ - struct AVLNode* new_root = root; - bool_t success = increase_label_area(new_root, label); - if (success == FALSE) { - new_root = insert_mask_alloc(new_root, label); - increase_label_area(new_root, label); - } - return new_root; -} - -// Increase the label's perimeter -// Create an AVL node if it doesn't exist -struct AVLNode* increase_label_perimeter_alloc(struct AVLNode* root, uint16_t label) -{ - struct AVLNode* new_root = root; - bool_t success = increase_label_perimeter(new_root, label); - if (success == FALSE) { - new_root = insert_mask_alloc(new_root, label); - increase_label_perimeter(new_root, label); - } - return new_root; -} - -// Comparison of uint16_ts -bool_t compare_uint16_t(uint16_t* s1, uint16_t* s2) -{ - return *s1 < *s2; -} - -// In-order traversal print pointer -void print_in_order_uint16_t(struct AVLNode* root) -{ - if (root != NULL) { - print_in_order_uint16_t(root->left); - printf("%d ", *((uint16_t*)root->data)); - print_in_order_uint16_t(root->right); - } -} - -// Check if uint16_t in AVLTree with uint16_t* data -bool_t in_uint16_t_tree(struct AVLNode* root, uint16_t value) -{ - if (root == NULL) { - return FALSE; - } - if (*((uint16_t*)root->data) == value) { - return TRUE; - } else if (value < *((uint16_t*)root->data)) { - return in_uint16_t_tree(root->left, value); - } else { - return in_uint16_t_tree(root->right, value); - } -} - -// Filter out small masks -// Assumption: Contiguous labeling -struct AVLNode* get_small_labels(struct AVLNode* removal_tree, struct AVLNode* label_tree, size_t min_area, size_t min_perimeter) -{ - struct AVLNode* return_tree = removal_tree; - if (label_tree != NULL) { - return_tree = get_small_labels(return_tree, label_tree->left, min_area, min_perimeter); - struct MaskData* node_data = (struct MaskData*)label_tree->data; - if ((node_data->area < min_area) || (node_data->perimeter < min_perimeter)) { - // Insert - struct Result result = avl_insert(return_tree, &node_data->label, (bool_t (*)(void*,void*))compare_uint16_t); - if (result.success) { - return_tree = result.data; - } - } - return_tree = get_small_labels(return_tree, label_tree->right, min_area, min_perimeter); - } - return return_tree; -} diff --git a/src/lib/seg/util.c b/src/lib/seg/util.c deleted file mode 100644 index 10b8fa8..0000000 --- a/src/lib/seg/util.c +++ /dev/null @@ -1,292 +0,0 @@ -#include <lib/seg/util.h> -#include <lib/algo/flood_fill.h> -#include <lib/png.h> -#include <tiffio.h> -#include <assert.h> -#include <stdio.h> -#include <stdlib.h> -#include <string.h> - -// Convert x,y coords to linear coordinate -size_t xy_to_coord(size_t x, size_t y, uint32_t width, uint32_t height) -{ - return x + y*width; -} - -// Determine if coordinate is on a mask boundary -// Assumes mask is (WxH) -bool_t is_on_mask_boundary(uint16_t* mask, uint32_t width, uint32_t height, size_t x, size_t y) -{ - size_t starting_coord = xy_to_coord(x, y, width, height); - size_t proposed_position; - uint16_t current_value = mask[starting_coord]; - - // Left neighbor - if (x != 0) { - proposed_position = xy_to_coord(x-1, y, width, height); - if (mask[proposed_position] != current_value) { - return TRUE; - } - } - // Right neighbor - if ((x+1) != width) { - proposed_position = xy_to_coord(x+1, y, width, height); - if (mask[proposed_position] != current_value) { - return TRUE; - } - } - if (y != 0) { - proposed_position = xy_to_coord(x, y-1, width, height); - if (mask[proposed_position] != current_value) { - return TRUE; - } - } - if ((y+1) != height) { - proposed_position = xy_to_coord(x, y+1, width, height); - if (mask[proposed_position] != current_value) { - return TRUE; - } - } - return FALSE; -} - -// Dilate masks by one 4-connected pixel -uint16_t* dilate(uint16_t* mask, uint32_t width, uint32_t height) -{ - uint16_t *new_mask = (uint16_t*)calloc(width*height,sizeof(uint16_t)); - for (size_t y = 0; y < height; y++) { - for (size_t x = 0; x < width; x++) { - size_t current_position = xy_to_coord(x, y, width, height); - if (mask[current_position] != 0) { - new_mask[current_position] = mask[current_position]; - continue; - } - size_t proposed_position; - if (x != 0) { - proposed_position = xy_to_coord(x-1, y, width, height); - if (mask[proposed_position] != 0) { - new_mask[current_position] = mask[proposed_position]; - continue; - } - } - if ((x+1) != width) { - proposed_position = xy_to_coord(x+1, y, width, height); - if (mask[proposed_position] != 0) { - new_mask[current_position] = mask[proposed_position]; - continue; - } - } - if (y != 0) { - proposed_position = xy_to_coord(x, y-1, width, height); - if (mask[proposed_position] != 0) { - new_mask[current_position] = mask[proposed_position]; - continue; - } - } - if ((y+1) != height) { - proposed_position = xy_to_coord(x, y+1, width, height); - if (mask[proposed_position] != 0) { - new_mask[current_position] = mask[proposed_position]; - continue; - } - } - } - } - return new_mask; -} - -// Erode masks by one 4-connected pixel -uint16_t* erode(uint16_t* mask, uint32_t width, uint32_t height) -{ - uint16_t *new_mask = (uint16_t*)calloc(width*height,sizeof(uint16_t)); - for (size_t y = 0; y < height; y++) { - for (size_t x = 0; x < width; x++) { - size_t current_position = xy_to_coord(x, y, width, height); - if (mask[current_position] != 0) { - new_mask[current_position] = mask[current_position]; - continue; - } - bool_t erode = FALSE; - size_t proposed_position; - if (x != 0) { - proposed_position = xy_to_coord(x-1, y, width, height); - if (mask[proposed_position] == 0) { - new_mask[current_position] = mask[proposed_position]; - continue; - } - } - if ((x+1) != width) { - proposed_position = xy_to_coord(x+1, y, width, height); - if (mask[proposed_position] == 0) { - new_mask[current_position] = mask[proposed_position]; - continue; - } - } - if (y != 0) { - proposed_position = xy_to_coord(x, y-1, width, height); - if (mask[proposed_position] == 0) { - new_mask[current_position] = mask[proposed_position]; - continue; - } - } - if ((y+1) != height) { - proposed_position = xy_to_coord(x, y+1, width, height); - if (mask[proposed_position] == 0) { - new_mask[current_position] = mask[proposed_position]; - continue; - } - } - } - } - return new_mask; -} - -// Close up masks by N-pixels -uint16_t* closeup(uint16_t* mask, uint32_t width, uint32_t height, size_t num_pixels) -{ - uint16_t *new_mask = (uint16_t*)calloc(width*height,sizeof(uint16_t)); - memcpy(new_mask, mask, width*height*sizeof(uint16_t)); - for (size_t count = 0; count < num_pixels; count++) { - uint16_t *new_labels = dilate(new_mask, width, height); - free(new_mask); - new_mask = new_labels; - } - for (size_t count = 0; count < num_pixels; count++) { - uint16_t *new_labels = erode(new_mask, width, height); - free(new_mask); - new_mask = new_labels; - } - // Retain original mask at the very least - for (size_t y = 0; y < height; y++) { - for (size_t x = 0; x < width; x++) { - size_t coord = x + y*width; - if (mask[coord] != 0) { - if (new_mask[coord] != mask[coord]) { - new_mask[coord] = mask[coord]; - } - } - } - } - return new_mask; -} - -// Combine Label Masks -// For all empty spaces in the destination, put the extra label if it exists -// Allocates an array if destination is unallocated -uint16_t* combine_masks(uint16_t *destination, uint16_t *extra_labels, uint32_t width, uint32_t height) -{ - if (destination == NULL) { - destination = (uint16_t*)calloc(width*height, sizeof(uint16_t)); - } - for (size_t y = 0; y < height; y++) { - for (size_t x = 0; x < width; x++) { - size_t coord = x + y*width; - if (destination[coord] == 0) { - destination[coord] = extra_labels[coord]; - } - } - } - return destination; -} - -// Process Tif File to Labels -// width, height will be overwritten with image dimensions -// starting_label_p will be incremented for each label found in the image -uint16_t* tif_to_labels(char* tif_file_name, uint32_t *width, uint32_t *height, uint16_t *starting_label_p) -{ - //-TIFF-IMAGE-OPEN------------------------------- - TIFF *tif = TIFFOpen(tif_file_name, "r"); - if (!tif) { - fprintf(stderr, "Failed to open TIFF file\n"); - return NULL; - } - - //-TIFF-FIND-DIMENSIONS-------------------------- - size_t channels = 1; - TIFFGetField(tif, TIFFTAG_IMAGEWIDTH, width); - TIFFGetField(tif, TIFFTAG_IMAGELENGTH, height); - - tmsize_t STRIP_LENGTH = TIFFStripSize(tif); - tmsize_t STRIP_COUNT = TIFFNumberOfStrips(tif); - if ((*width)*(*height)*3 == STRIP_LENGTH*STRIP_COUNT) { - channels = 3; - } else if ((*width)*(*height)*4 == STRIP_LENGTH*STRIP_COUNT) { - channels = 4; - } - - //-TIFF-LOAD-DATA-------------------------------- - void* buffer = malloc(STRIP_LENGTH*sizeof(uint8_t)); - if (buffer == NULL) { - fprintf(stderr, "Memory allocation error\n"); - TIFFClose(tif); - return NULL; - } - uint8_t* image_data = calloc((*width)*(*height)*channels,sizeof(uint8_t)); - if (image_data == NULL) { - fprintf(stderr, "Memory allocation error\n"); - free(buffer); - TIFFClose(tif); - return NULL; - } - for (size_t y = 0; y < STRIP_COUNT; y++) { - tmsize_t strip_size = TIFFReadRawStrip(tif, y, buffer, STRIP_LENGTH); - assert(strip_size == STRIP_LENGTH); - for (size_t x = 0; x < STRIP_LENGTH; x++) { - image_data[x + y*STRIP_LENGTH] = ((uint8_t*)buffer)[x]; - } - } - free(buffer); - - //-FLOOD-FILL-SEGMENTATION----------------------- - //-CONTIGUOUS-REGION-FINDING--------------------- - uint16_t *labels = NULL; - labels = (uint16_t*)calloc((*width)*(*height),sizeof(uint16_t)); - if (labels == NULL) { - fprintf(stderr, "Memory allocation error\n"); - free(image_data); - TIFFClose(tif); - return NULL; - } - // Flood fill on each pixel - // Increase label for each success - for (size_t y = 0; y < *height; y++) { - for (size_t x = 0; x < *width; x++) { - size_t coord = x + y*(*width); - if(flood(image_data, labels, *width, *height, channels, x, y, &(image_data[coord*channels]), *starting_label_p)) { - *starting_label_p += 1; - } - } - } - free(image_data); - TIFFClose(tif); - return labels; -} - -// Convert mask to bitmap -struct bitmap_t* uint16_to_bitmap(uint16_t* buffer, uint32_t width, uint32_t height) -{ - struct pixel_t* out_buffer = (struct pixel_t*)calloc(width*height, sizeof(struct pixel_t)); - if (out_buffer == NULL) { - return NULL; - } - struct bitmap_t* bitmap = (struct bitmap_t*)malloc(sizeof(struct bitmap_t)); - if (bitmap == NULL) { - free(out_buffer); - return NULL; - } - for (size_t y = 0; y < height; y++) { - for (size_t x = 0; x < width; x++) { - size_t coord = x + y*width; - uint8_t red = (buffer[coord] & 0xF00) >> 4*2; - uint8_t green = (buffer[coord] & 0x0F0) >> 4*1; - uint8_t blue = (buffer[coord] & 0x00F) >> 4*0; - out_buffer[coord].red = red | (red << 4); - out_buffer[coord].green = green | (green << 4); - out_buffer[coord].blue = blue | (blue << 4); - } - } - bitmap->image_buffer = out_buffer; - bitmap->width = (size_t)width; - bitmap->height = (size_t)height; - return bitmap; -} |