From 0d1f5979dd1d6062af118fae3a1aa1863ea596f2 Mon Sep 17 00:00:00 2001 From: Christian C Date: Fri, 7 Mar 2025 21:58:41 -0800 Subject: Library directories --- Makefile | 27 ++-- lib/algo/avl_tree.c | 159 ++++++++++++++++++++ lib/algo/flood_fill.c | 33 +++++ lib/color.c | 36 +++++ lib/dir.c | 69 +++++++++ lib/file.c | 15 ++ lib/lib.c | 4 + lib/png.c | 64 +++++++++ lib/seg/mask_data.c | 263 +++++++++++++++++++++++++++++++++ lib/seg/util.c | 360 ++++++++++++++++++++++++++++++++++++++++++++++ lib/time.c | 13 ++ src/lib/algo/avl_tree.c | 159 -------------------- src/lib/algo/flood_fill.c | 33 ----- src/lib/color.c | 36 ----- src/lib/dir.c | 69 --------- src/lib/file.c | 15 -- src/lib/lib.c | 4 - src/lib/png.c | 64 --------- src/lib/seg/mask_data.c | 263 --------------------------------- src/lib/seg/util.c | 360 ---------------------------------------------- src/lib/time.c | 13 -- 21 files changed, 1035 insertions(+), 1024 deletions(-) create mode 100644 lib/algo/avl_tree.c create mode 100644 lib/algo/flood_fill.c create mode 100644 lib/color.c create mode 100644 lib/dir.c create mode 100644 lib/file.c create mode 100644 lib/lib.c create mode 100644 lib/png.c create mode 100644 lib/seg/mask_data.c create mode 100644 lib/seg/util.c create mode 100644 lib/time.c delete mode 100644 src/lib/algo/avl_tree.c delete mode 100644 src/lib/algo/flood_fill.c delete mode 100644 src/lib/color.c delete mode 100644 src/lib/dir.c delete mode 100644 src/lib/file.c delete mode 100644 src/lib/lib.c delete mode 100644 src/lib/png.c delete mode 100644 src/lib/seg/mask_data.c delete mode 100644 src/lib/seg/util.c delete mode 100644 src/lib/time.c diff --git a/Makefile b/Makefile index 53bf441..238fb87 100644 --- a/Makefile +++ b/Makefile @@ -6,19 +6,26 @@ INC_DIR=include/ # Source files SRC_DIR=src/ -SRC_OBJ_DIR=$(BUILD_DIR)obj/src/ +SRC_OBJ_DIR=$(BUILD_DIR)obj/$(SRC_DIR) SRC_SRCS=$(shell find $(SRC_DIR) -iname \*.c) SRC_OBJS_sub=$(subst $(SRC_DIR),$(SRC_OBJ_DIR),$(SRC_SRCS)) SRC_OBJS=$(SRC_OBJS_sub:.c=.o) SRC_OBJ_DIRS_sub=$(shell find $(SRC_DIR) -type d) SRC_OBJ_DIRS=$(subst $(SRC_DIR),$(SRC_OBJ_DIR),$(SRC_OBJ_DIRS_sub)) -$(info $(SRC_SRCS)) -$(info $(SRC_OBJ_DIR)) -$(info $(SRC_OBJ_DIRS)) -$(info $(SRC_OBJS)) - # Library files +LIB_DIR=lib/ +LIB_OBJ_DIR=$(BUILD_DIR)obj/$(LIB_DIR) +LIB_SRCS=$(shell find $(LIB_DIR) -iname \*.c) +LIB_OBJS_sub=$(subst $(LIB_DIR),$(LIB_OBJ_DIR),$(LIB_SRCS)) +LIB_OBJS=$(LIB_OBJS_sub:.c=.o) +LIB_OBJ_DIRS_sub=$(shell find $(LIB_DIR) -type d) +LIB_OBJ_DIRS=$(subst $(LIB_DIR),$(LIB_OBJ_DIR),$(LIB_OBJ_DIRS_sub)) + +$(info $(LIB_SRCS)) +$(info $(LIB_OBJ_DIR)) +$(info $(LIB_OBJ_DIRS)) +$(info $(LIB_OBJS)) # Include raylib if we want a visual experience ifdef RAYLIB @@ -55,7 +62,7 @@ default: clean build build: $(BUILD_DIR)$(EXE) -$(BUILD_DIR)$(EXE): $(SRC_OBJS) +$(BUILD_DIR)$(EXE): $(SRC_OBJS) $(LIB_OBJS) @echo LD --\> $@ @gcc -o $@ $(LDFLAGS) $^ @@ -63,10 +70,14 @@ $(SRC_OBJ_DIR)%.o: $(SRC_DIR)%.c @echo CC $< --\> $@ @gcc -o $@ $(CFLAGS) -c $< +$(LIB_OBJ_DIR)%.o: $(LIB_DIR)%.c + @echo CC $< --\> $@ + @gcc -o $@ $(CFLAGS) -c $< + clean: @echo Cleaning build files... @-rm -rf $(OBJ_DIR) $(BUILD_DIR) - @mkdir -p $(BUILD_DIR) $(SRC_OBJ_DIRS) + @mkdir -p $(BUILD_DIR) $(SRC_OBJ_DIRS) $(LIB_OBJ_DIRS) run: $(BUILD_DIR)$(EXE) @echo Executing... diff --git a/lib/algo/avl_tree.c b/lib/algo/avl_tree.c new file mode 100644 index 0000000..db4fa4b --- /dev/null +++ b/lib/algo/avl_tree.c @@ -0,0 +1,159 @@ +#include +#include + +#include +#include + +// Get the height of an AVL node +uint8_t get_height(struct AVLNode* node) +{ + if (node == NULL) { + return 0; + } + return node->height; +} + +// Get the Maximum Height between two +uint8_t max_height(uint8_t a, uint8_t b) +{ + return (a > b) ? a : b; +} + +// Get the balance factor of a node +ssize_t get_balance_factor(struct AVLNode* node) +{ + if (node == NULL) { + return 0; + } + return get_height(node->left) - get_height(node->right); +} + +// Rotate an AVL node right +struct AVLNode* right_rotate(struct AVLNode* parent) +{ + struct AVLNode* child1 = parent->left; + struct AVLNode* child2 = child1->right; + + child1->right = parent; + parent->left = child2; + + parent->height = max_height(get_height(parent->left), get_height(parent->right)) + 1; + child1->height = max_height(get_height(child1->left), get_height(child1->right)) + 1; + return child1; +} + +// Rotate an AVL node left +struct AVLNode* left_rotate(struct AVLNode* parent) +{ + struct AVLNode* child1 = parent->right; + struct AVLNode* child2 = child1->left; + + child1->left = parent; + parent->right = child2; + + parent->height = max_height(get_height(parent->left), get_height(parent->right)) + 1; + child1->height = max_height(get_height(child1->left), get_height(child1->right)) + 1; + return child1; +} + +// Create AVL node +struct AVLNode* create_avl_node(void* data, bool_t (*compare)(void*, void*)) +{ + struct AVLNode* node = (struct AVLNode*)malloc(sizeof(struct AVLNode)); + if (node == NULL) { + return NULL; + } + node->data = data; + node->compare = compare; + node->left = NULL; + node->right = NULL; + node->height = 1; // Leaf initially + return node; +} + +// Insert data into AVL tree +struct Result avl_insert(struct AVLNode* node, void* data, bool_t (*compare)(void*, void*)) +{ + struct Result result; + // 1. Standard BST insertion + if (node == NULL) { + return (struct Result) {create_avl_node(data, compare), TRUE}; + } + + struct MaskData *node_data = (struct MaskData*)node->data; + if (node->compare(data, node_data)) { + result = avl_insert(node->left, data, compare); + if (!result.success) { + fprintf(stderr, "Failed to insert!"); + return result; + } + node->left = (struct AVLNode*)result.data; + } else if (node->compare(node->data, data)) { + result = avl_insert(node->right, data, compare); + 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}; +} + +// In-order traversal print pointer +void print_in_order(struct AVLNode* root) +{ + if (root != NULL) { + print_in_order(root->left); + printf("%p ", root->data); + print_in_order(root->right); + } +} + +// Free avl tree nodes starting at root +void free_avl_tree(struct AVLNode* root) +{ + if (root != NULL) { + free_avl_tree(root->left); + free_avl_tree(root->right); + free(root); + } +} + +// Free avl tree and their data starting at root +void free_avl_tree_nodes(struct AVLNode* root) +{ + if (root != NULL) { + free_avl_tree_nodes(root->left); + free_avl_tree_nodes(root->right); + if (root->data != NULL) { + free(root->data); + } + free(root); + } +} diff --git a/lib/algo/flood_fill.c b/lib/algo/flood_fill.c new file mode 100644 index 0000000..62db658 --- /dev/null +++ b/lib/algo/flood_fill.c @@ -0,0 +1,33 @@ +#include + +// Flood +// Floods a mask from a given set of image to determine the contiguous regions +// 1. Check that the (x,y) is within the picture +// 2. Check if the (x,y) coordinate in the mask is unused +// 3. Check if the (x,y) coordinate in the image is non-background +// 4. Check if the (x,y) coordinate in the image is the same color as the fill color +// 5. If all hold, set the label for the pixel, and check each neighbor +// Otherwise, stop flooding +bool_t flood(uint8_t* image, uint16_t* mask, size_t width, size_t height, size_t channels, size_t x, size_t y, uint8_t* fill_color, uint16_t label) +{ + if ((x >= width) | (y >= height)) { + return FALSE; + } + size_t coord = x + y*width; + if (mask[coord] != 0) { + return FALSE; + } + if (color_zero(&(image[coord*channels]), channels)) { + return FALSE; + } + if (color_equal(&(image[coord*channels]), fill_color, channels)) { + mask[coord] = label; + flood(image, mask, width, height, channels, x, y+1, fill_color, label); + flood(image, mask, width, height, channels, x, y-1, fill_color, label); + flood(image, mask, width, height, channels, x+1, y, fill_color, label); + flood(image, mask, width, height, channels, x-1, y, fill_color, label); + return TRUE; + } + return FALSE; +} + diff --git a/lib/color.c b/lib/color.c new file mode 100644 index 0000000..902a93d --- /dev/null +++ b/lib/color.c @@ -0,0 +1,36 @@ +#include +#include +#include + +// Color Equal to Background +// Background: zeros in RGB, alpha can be whatever +bool_t color_zero(uint8_t* color1, size_t channels) { + for (size_t idx = 0; idx < channels; idx++) { + if (idx == 3) { + break; + } + if (color1[idx] != 0) { + return FALSE; + } + } + return TRUE; +} + +// Color Equality +// Determine if two colors are identical +bool_t color_equal(uint8_t* color1, uint8_t* color2, size_t channels) { + for (size_t idx = 0; idx < channels; idx++) { + if (color1[idx] != color2[idx]) { + return FALSE; + } + } + return TRUE; +} + +// Print out the `channels` length color vector +void print_color(uint8_t* color, size_t channels) { + for (size_t index = 0; index < channels; index++) { + printf("%hhu ", color[index]); + } + printf("\n"); +} diff --git a/lib/dir.c b/lib/dir.c new file mode 100644 index 0000000..be2a2ac --- /dev/null +++ b/lib/dir.c @@ -0,0 +1,69 @@ +#include +#include +#include +#include +#include + +// Is directory +bool_t is_directory(char* dirname) { + struct stat st; + if (stat(dirname, &st) == 0) { + if (S_ISDIR(st.st_mode)) { + return TRUE; + } + } + return FALSE; +} + +// List directory +char** list_directory(char* dirname) { + DIR *d; + struct dirent *dir; + d = opendir(dirname); + char** file_names = (char**)malloc(sizeof(char*)); + if (!file_names) { + return NULL; + } + file_names[0] = NULL; + size_t file_count = 0; + if (d) { + while ((dir = readdir(d)) != NULL) { + if (dir->d_type == DT_REG) { + // When a regular file is reached + /// Create space for it in the list + file_names = realloc(file_names, (file_count+1+1)*sizeof(char*)); + /// Create space for the name + file_names[file_count] = calloc(strlen(dir->d_name)+1, sizeof(char)); + /// Copy the name + strcpy(file_names[file_count], dir->d_name); + /// Mark the end of the file list with a NULL entry + file_names[++file_count] = NULL; + } + } + return file_names; + } + return NULL; +} + +// Get full path +char* full_path(char* dir, char* file) +{ + char* fpath = NULL; + size_t dir_len = strlen(dir); + size_t file_len = strlen(file); + fpath = (char*)calloc(dir_len+file_len+2,sizeof(char)); + strcpy(fpath,dir); + strcpy(fpath+dir_len+1,file); + fpath[dir_len] = '/'; + return fpath; +} + +// Determines if file name has tif file extension +bool_t is_tif_ext(char* file_name) +{ + size_t file_len = strlen(file_name); + if ((file_name[file_len-3] == 't') && (file_name[file_len-2] == 'i') && (file_name[file_len-1] == 'f')) { + return TRUE; + } + return FALSE; +} diff --git a/lib/file.c b/lib/file.c new file mode 100644 index 0000000..b6ec1d0 --- /dev/null +++ b/lib/file.c @@ -0,0 +1,15 @@ +#include +#include + +// Write array to a file +bool_t write_array(char* output_file_name, void* array, size_t size) +{ + FILE *file = fopen(output_file_name, "wb"); + if (file == NULL) { + fprintf(stderr, "Error opening file %s\n", output_file_name); + return FALSE; + } + fwrite(array, size, 1, file); + fclose(file); + return TRUE; +} diff --git a/lib/lib.c b/lib/lib.c new file mode 100644 index 0000000..c1f26fc --- /dev/null +++ b/lib/lib.c @@ -0,0 +1,4 @@ +#include + +const uint32_t SCREEN_WIDTH = 640; +const uint32_t SCREEN_HEIGHT = 480; diff --git a/lib/png.c b/lib/png.c new file mode 100644 index 0000000..d12a765 --- /dev/null +++ b/lib/png.c @@ -0,0 +1,64 @@ +#include + +#include +#include + +// Save bitmap to file +void save_png(struct bitmap_t* bitmap, char* fname) +{ + FILE *fp; + png_structp png_ptr = NULL; + png_infop info_ptr = NULL; + uint8_t pixel_size = 3; + uint8_t pixel_depth = 8; + png_byte ** row_pointers = NULL; + size_t x, y; + fp = fopen(fname, "wb"); + if (fp == NULL) { + fprintf(stderr, "Error opening file\n"); + return; + } + png_ptr = png_create_write_struct(PNG_LIBPNG_VER_STRING, NULL, NULL, NULL); + if (png_ptr == NULL) { + fprintf(stderr, "Error creating write structure\n"); + fclose(fp); + return; + } + info_ptr = png_create_info_struct(png_ptr); + if (info_ptr == NULL) { + fprintf(stderr, "Error creating info structure\n"); + fclose(fp); + return; + } + if (setjmp(png_jmpbuf(png_ptr))) { + fprintf(stderr, "Error setting jmp\n"); + fclose(fp); + return; + } + png_set_IHDR(png_ptr, info_ptr, + bitmap->width, bitmap->height, + pixel_depth, + PNG_COLOR_TYPE_RGB, PNG_INTERLACE_NONE, PNG_COMPRESSION_TYPE_DEFAULT, + PNG_FILTER_TYPE_DEFAULT); + + row_pointers = png_malloc(png_ptr, bitmap->height*sizeof(png_byte*)); + for (y = 0; y < bitmap->height; y++) { + png_byte *row = png_malloc(png_ptr, sizeof(uint8_t)*bitmap->width*pixel_size); + row_pointers[y] = row; + for (x = 0; x < bitmap->width; x++) { + *row++ = bitmap->image_buffer[x + y*bitmap->width].red; + *row++ = bitmap->image_buffer[x + y*bitmap->width].green; + *row++ = bitmap->image_buffer[x + y*bitmap->width].blue; + } + } + png_init_io(png_ptr, fp); + png_set_rows(png_ptr, info_ptr, row_pointers); + png_write_png(png_ptr, info_ptr, PNG_TRANSFORM_IDENTITY, NULL); + for (y = 0; y < bitmap->height; y++) { + png_free(png_ptr, row_pointers[y]); + } + png_free(png_ptr, row_pointers); + png_destroy_write_struct(&png_ptr, &info_ptr); + fclose(fp); +} + diff --git a/lib/seg/mask_data.c b/lib/seg/mask_data.c new file mode 100644 index 0000000..8c4b037 --- /dev/null +++ b/lib/seg/mask_data.c @@ -0,0 +1,263 @@ +#include +#include + +#include + +// 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; +} + +// Get mask label data +struct AVLNode* get_mask_data(uint16_t* masks, uint32_t width, uint32_t height) +{ + struct AVLNode* root = NULL; + for (size_t y = 0; y < height; y++) { + for (size_t x = 0; x < width; x++) { + size_t coord = x + y*width; + if (masks[coord] != 0) { + root = increase_label_area_alloc(root, masks[coord]); + if (is_on_mask_boundary(masks, width, height, x, y)) { + increase_label_perimeter(root, masks[coord]); + } + } + } + } + return root; +} + +// Filter out small masks in mask +void filter_small_masks(uint16_t* masks, uint32_t width, uint32_t height, size_t min_area, size_t min_perimeter) +{ + struct AVLNode* root = get_mask_data(masks, width, height); + struct AVLNode* small_label_tree = NULL; + small_label_tree = get_small_labels(NULL, root, min_area, min_perimeter); + for (size_t y = 0; y < height; y++) { + for (size_t x = 0; x < width; x++) { + size_t coord = x + y*width; + if (in_uint16_t_tree(small_label_tree, masks[coord])) { + masks[coord] = 0; + } + } + } + free_avl_tree(small_label_tree); + free_avl_tree_nodes(root); +} diff --git a/lib/seg/util.c b/lib/seg/util.c new file mode 100644 index 0000000..677e8f5 --- /dev/null +++ b/lib/seg/util.c @@ -0,0 +1,360 @@ + #include +#include +#include +#include +#include +#include +#include +#include + +// Suppress Tiff Warnings +void TiffDummyHandler(const char* module, const char* fmt, va_list ap) +{ + // ignore errors and warnings (or handle them your own way) +} + +// 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; +} + +// Dilate masks by one 4-connected pixel +void dilate(uint16_t** mask, uint32_t width, uint32_t height) +{ + uint16_t *new_mask = _dilate(*mask, width, height); + if (new_mask != NULL) { + free(*mask); + *mask = 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)); + memcpy(new_mask, mask, 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); + 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] = 0; + continue; + } + } + if ((x+1) != width) { + proposed_position = xy_to_coord(x+1, y, width, height); + if (mask[proposed_position] == 0) { + new_mask[current_position] = 0; + continue; + } + } + if (y != 0) { + proposed_position = xy_to_coord(x, y-1, width, height); + if (mask[proposed_position] == 0) { + new_mask[current_position] = 0; + continue; + } + } + if ((y+1) != height) { + proposed_position = xy_to_coord(x, y+1, width, height); + if (mask[proposed_position] == 0) { + new_mask[current_position] = 0; + continue; + } + } + } + } + return new_mask; +} + +// Erode masks by one 4-connected pixel +void erode(uint16_t** mask, uint32_t width, uint32_t height) +{ + uint16_t *new_mask = _erode(*mask, width, height); + if (new_mask != NULL) { + free(*mask); + *mask = 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++) { + dilate(&new_mask, width, height); + } + for (size_t count = 0; count < num_pixels; count++) { + erode(&new_mask, width, height); + } + // 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; +} + +// Close up masks by N-pixels +// Update pointer +void closeup(uint16_t** mask, uint32_t width, uint32_t height, size_t num_pixels) +{ + uint16_t *new_mask = _closeup(*mask, width, height, num_pixels); + if (new_mask != NULL) { + free(*mask); + *mask = 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) +{ + TIFFSetWarningHandler(TiffDummyHandler); + //-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; +} + +// Reduce a mask to the contiguous regions +uint16_t* _reduce_contiguous_regions(uint16_t* masks, uint32_t width, uint32_t height, uint16_t* total_labels) +{ + uint16_t starting_label = 1; + uint16_t* new_masks = (uint16_t*)calloc(width*height, sizeof(uint16_t)); + if (new_masks == NULL) { + 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 channels = 2; // uint16_t = 2*uint8_t + if (flood((uint8_t*)masks, new_masks, width, height, channels, x, y, &(((uint8_t*)masks)[coord*channels]), starting_label)) { + starting_label++; + } + } + } + if (total_labels != NULL) { + *total_labels = starting_label; + } + return new_masks; +} + +// Reduce a mask to the contiguous regions +// Automatically update pointer to contiguous mask +// Freeing previous mask +void reduce_contiguous_regions(uint16_t** masks_p, uint32_t width, uint32_t height, uint16_t* total_labels) +{ + if (masks_p == NULL) { + return; + } + uint16_t* new_masks = _reduce_contiguous_regions(*masks_p, width, height, total_labels); + if (new_masks != NULL) { + free(*masks_p); + *masks_p = new_masks; + } +} diff --git a/lib/time.c b/lib/time.c new file mode 100644 index 0000000..085ef80 --- /dev/null +++ b/lib/time.c @@ -0,0 +1,13 @@ +#include + +// Difference in Time +// Compute the difference between timespec structs +double diff_time(struct timespec *time1, struct timespec *time0) { + return (time1->tv_sec - time0->tv_sec) + + (time1->tv_nsec - time0->tv_nsec) / 1000000000.0; +} + +// Get Current Time +void get_time(struct timespec *ts) { + timespec_get(ts, TIME_UTC); +} diff --git a/src/lib/algo/avl_tree.c b/src/lib/algo/avl_tree.c deleted file mode 100644 index db4fa4b..0000000 --- a/src/lib/algo/avl_tree.c +++ /dev/null @@ -1,159 +0,0 @@ -#include -#include - -#include -#include - -// Get the height of an AVL node -uint8_t get_height(struct AVLNode* node) -{ - if (node == NULL) { - return 0; - } - return node->height; -} - -// Get the Maximum Height between two -uint8_t max_height(uint8_t a, uint8_t b) -{ - return (a > b) ? a : b; -} - -// Get the balance factor of a node -ssize_t get_balance_factor(struct AVLNode* node) -{ - if (node == NULL) { - return 0; - } - return get_height(node->left) - get_height(node->right); -} - -// Rotate an AVL node right -struct AVLNode* right_rotate(struct AVLNode* parent) -{ - struct AVLNode* child1 = parent->left; - struct AVLNode* child2 = child1->right; - - child1->right = parent; - parent->left = child2; - - parent->height = max_height(get_height(parent->left), get_height(parent->right)) + 1; - child1->height = max_height(get_height(child1->left), get_height(child1->right)) + 1; - return child1; -} - -// Rotate an AVL node left -struct AVLNode* left_rotate(struct AVLNode* parent) -{ - struct AVLNode* child1 = parent->right; - struct AVLNode* child2 = child1->left; - - child1->left = parent; - parent->right = child2; - - parent->height = max_height(get_height(parent->left), get_height(parent->right)) + 1; - child1->height = max_height(get_height(child1->left), get_height(child1->right)) + 1; - return child1; -} - -// Create AVL node -struct AVLNode* create_avl_node(void* data, bool_t (*compare)(void*, void*)) -{ - struct AVLNode* node = (struct AVLNode*)malloc(sizeof(struct AVLNode)); - if (node == NULL) { - return NULL; - } - node->data = data; - node->compare = compare; - node->left = NULL; - node->right = NULL; - node->height = 1; // Leaf initially - return node; -} - -// Insert data into AVL tree -struct Result avl_insert(struct AVLNode* node, void* data, bool_t (*compare)(void*, void*)) -{ - struct Result result; - // 1. Standard BST insertion - if (node == NULL) { - return (struct Result) {create_avl_node(data, compare), TRUE}; - } - - struct MaskData *node_data = (struct MaskData*)node->data; - if (node->compare(data, node_data)) { - result = avl_insert(node->left, data, compare); - if (!result.success) { - fprintf(stderr, "Failed to insert!"); - return result; - } - node->left = (struct AVLNode*)result.data; - } else if (node->compare(node->data, data)) { - result = avl_insert(node->right, data, compare); - 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}; -} - -// In-order traversal print pointer -void print_in_order(struct AVLNode* root) -{ - if (root != NULL) { - print_in_order(root->left); - printf("%p ", root->data); - print_in_order(root->right); - } -} - -// Free avl tree nodes starting at root -void free_avl_tree(struct AVLNode* root) -{ - if (root != NULL) { - free_avl_tree(root->left); - free_avl_tree(root->right); - free(root); - } -} - -// Free avl tree and their data starting at root -void free_avl_tree_nodes(struct AVLNode* root) -{ - if (root != NULL) { - free_avl_tree_nodes(root->left); - free_avl_tree_nodes(root->right); - if (root->data != NULL) { - free(root->data); - } - free(root); - } -} diff --git a/src/lib/algo/flood_fill.c b/src/lib/algo/flood_fill.c deleted file mode 100644 index 62db658..0000000 --- a/src/lib/algo/flood_fill.c +++ /dev/null @@ -1,33 +0,0 @@ -#include - -// Flood -// Floods a mask from a given set of image to determine the contiguous regions -// 1. Check that the (x,y) is within the picture -// 2. Check if the (x,y) coordinate in the mask is unused -// 3. Check if the (x,y) coordinate in the image is non-background -// 4. Check if the (x,y) coordinate in the image is the same color as the fill color -// 5. If all hold, set the label for the pixel, and check each neighbor -// Otherwise, stop flooding -bool_t flood(uint8_t* image, uint16_t* mask, size_t width, size_t height, size_t channels, size_t x, size_t y, uint8_t* fill_color, uint16_t label) -{ - if ((x >= width) | (y >= height)) { - return FALSE; - } - size_t coord = x + y*width; - if (mask[coord] != 0) { - return FALSE; - } - if (color_zero(&(image[coord*channels]), channels)) { - return FALSE; - } - if (color_equal(&(image[coord*channels]), fill_color, channels)) { - mask[coord] = label; - flood(image, mask, width, height, channels, x, y+1, fill_color, label); - flood(image, mask, width, height, channels, x, y-1, fill_color, label); - flood(image, mask, width, height, channels, x+1, y, fill_color, label); - flood(image, mask, width, height, channels, x-1, y, fill_color, label); - return TRUE; - } - return FALSE; -} - diff --git a/src/lib/color.c b/src/lib/color.c deleted file mode 100644 index 902a93d..0000000 --- a/src/lib/color.c +++ /dev/null @@ -1,36 +0,0 @@ -#include -#include -#include - -// Color Equal to Background -// Background: zeros in RGB, alpha can be whatever -bool_t color_zero(uint8_t* color1, size_t channels) { - for (size_t idx = 0; idx < channels; idx++) { - if (idx == 3) { - break; - } - if (color1[idx] != 0) { - return FALSE; - } - } - return TRUE; -} - -// Color Equality -// Determine if two colors are identical -bool_t color_equal(uint8_t* color1, uint8_t* color2, size_t channels) { - for (size_t idx = 0; idx < channels; idx++) { - if (color1[idx] != color2[idx]) { - return FALSE; - } - } - return TRUE; -} - -// Print out the `channels` length color vector -void print_color(uint8_t* color, size_t channels) { - for (size_t index = 0; index < channels; index++) { - printf("%hhu ", color[index]); - } - printf("\n"); -} diff --git a/src/lib/dir.c b/src/lib/dir.c deleted file mode 100644 index be2a2ac..0000000 --- a/src/lib/dir.c +++ /dev/null @@ -1,69 +0,0 @@ -#include -#include -#include -#include -#include - -// Is directory -bool_t is_directory(char* dirname) { - struct stat st; - if (stat(dirname, &st) == 0) { - if (S_ISDIR(st.st_mode)) { - return TRUE; - } - } - return FALSE; -} - -// List directory -char** list_directory(char* dirname) { - DIR *d; - struct dirent *dir; - d = opendir(dirname); - char** file_names = (char**)malloc(sizeof(char*)); - if (!file_names) { - return NULL; - } - file_names[0] = NULL; - size_t file_count = 0; - if (d) { - while ((dir = readdir(d)) != NULL) { - if (dir->d_type == DT_REG) { - // When a regular file is reached - /// Create space for it in the list - file_names = realloc(file_names, (file_count+1+1)*sizeof(char*)); - /// Create space for the name - file_names[file_count] = calloc(strlen(dir->d_name)+1, sizeof(char)); - /// Copy the name - strcpy(file_names[file_count], dir->d_name); - /// Mark the end of the file list with a NULL entry - file_names[++file_count] = NULL; - } - } - return file_names; - } - return NULL; -} - -// Get full path -char* full_path(char* dir, char* file) -{ - char* fpath = NULL; - size_t dir_len = strlen(dir); - size_t file_len = strlen(file); - fpath = (char*)calloc(dir_len+file_len+2,sizeof(char)); - strcpy(fpath,dir); - strcpy(fpath+dir_len+1,file); - fpath[dir_len] = '/'; - return fpath; -} - -// Determines if file name has tif file extension -bool_t is_tif_ext(char* file_name) -{ - size_t file_len = strlen(file_name); - if ((file_name[file_len-3] == 't') && (file_name[file_len-2] == 'i') && (file_name[file_len-1] == 'f')) { - return TRUE; - } - return FALSE; -} diff --git a/src/lib/file.c b/src/lib/file.c deleted file mode 100644 index b6ec1d0..0000000 --- a/src/lib/file.c +++ /dev/null @@ -1,15 +0,0 @@ -#include -#include - -// Write array to a file -bool_t write_array(char* output_file_name, void* array, size_t size) -{ - FILE *file = fopen(output_file_name, "wb"); - if (file == NULL) { - fprintf(stderr, "Error opening file %s\n", output_file_name); - return FALSE; - } - fwrite(array, size, 1, file); - fclose(file); - return TRUE; -} diff --git a/src/lib/lib.c b/src/lib/lib.c deleted file mode 100644 index c1f26fc..0000000 --- a/src/lib/lib.c +++ /dev/null @@ -1,4 +0,0 @@ -#include - -const uint32_t SCREEN_WIDTH = 640; -const uint32_t SCREEN_HEIGHT = 480; diff --git a/src/lib/png.c b/src/lib/png.c deleted file mode 100644 index d12a765..0000000 --- a/src/lib/png.c +++ /dev/null @@ -1,64 +0,0 @@ -#include - -#include -#include - -// Save bitmap to file -void save_png(struct bitmap_t* bitmap, char* fname) -{ - FILE *fp; - png_structp png_ptr = NULL; - png_infop info_ptr = NULL; - uint8_t pixel_size = 3; - uint8_t pixel_depth = 8; - png_byte ** row_pointers = NULL; - size_t x, y; - fp = fopen(fname, "wb"); - if (fp == NULL) { - fprintf(stderr, "Error opening file\n"); - return; - } - png_ptr = png_create_write_struct(PNG_LIBPNG_VER_STRING, NULL, NULL, NULL); - if (png_ptr == NULL) { - fprintf(stderr, "Error creating write structure\n"); - fclose(fp); - return; - } - info_ptr = png_create_info_struct(png_ptr); - if (info_ptr == NULL) { - fprintf(stderr, "Error creating info structure\n"); - fclose(fp); - return; - } - if (setjmp(png_jmpbuf(png_ptr))) { - fprintf(stderr, "Error setting jmp\n"); - fclose(fp); - return; - } - png_set_IHDR(png_ptr, info_ptr, - bitmap->width, bitmap->height, - pixel_depth, - PNG_COLOR_TYPE_RGB, PNG_INTERLACE_NONE, PNG_COMPRESSION_TYPE_DEFAULT, - PNG_FILTER_TYPE_DEFAULT); - - row_pointers = png_malloc(png_ptr, bitmap->height*sizeof(png_byte*)); - for (y = 0; y < bitmap->height; y++) { - png_byte *row = png_malloc(png_ptr, sizeof(uint8_t)*bitmap->width*pixel_size); - row_pointers[y] = row; - for (x = 0; x < bitmap->width; x++) { - *row++ = bitmap->image_buffer[x + y*bitmap->width].red; - *row++ = bitmap->image_buffer[x + y*bitmap->width].green; - *row++ = bitmap->image_buffer[x + y*bitmap->width].blue; - } - } - png_init_io(png_ptr, fp); - png_set_rows(png_ptr, info_ptr, row_pointers); - png_write_png(png_ptr, info_ptr, PNG_TRANSFORM_IDENTITY, NULL); - for (y = 0; y < bitmap->height; y++) { - png_free(png_ptr, row_pointers[y]); - } - png_free(png_ptr, row_pointers); - png_destroy_write_struct(&png_ptr, &info_ptr); - fclose(fp); -} - diff --git a/src/lib/seg/mask_data.c b/src/lib/seg/mask_data.c deleted file mode 100644 index 8c4b037..0000000 --- a/src/lib/seg/mask_data.c +++ /dev/null @@ -1,263 +0,0 @@ -#include -#include - -#include - -// 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; -} - -// Get mask label data -struct AVLNode* get_mask_data(uint16_t* masks, uint32_t width, uint32_t height) -{ - struct AVLNode* root = NULL; - for (size_t y = 0; y < height; y++) { - for (size_t x = 0; x < width; x++) { - size_t coord = x + y*width; - if (masks[coord] != 0) { - root = increase_label_area_alloc(root, masks[coord]); - if (is_on_mask_boundary(masks, width, height, x, y)) { - increase_label_perimeter(root, masks[coord]); - } - } - } - } - return root; -} - -// Filter out small masks in mask -void filter_small_masks(uint16_t* masks, uint32_t width, uint32_t height, size_t min_area, size_t min_perimeter) -{ - struct AVLNode* root = get_mask_data(masks, width, height); - struct AVLNode* small_label_tree = NULL; - small_label_tree = get_small_labels(NULL, root, min_area, min_perimeter); - for (size_t y = 0; y < height; y++) { - for (size_t x = 0; x < width; x++) { - size_t coord = x + y*width; - if (in_uint16_t_tree(small_label_tree, masks[coord])) { - masks[coord] = 0; - } - } - } - free_avl_tree(small_label_tree); - free_avl_tree_nodes(root); -} diff --git a/src/lib/seg/util.c b/src/lib/seg/util.c deleted file mode 100644 index 677e8f5..0000000 --- a/src/lib/seg/util.c +++ /dev/null @@ -1,360 +0,0 @@ - #include -#include -#include -#include -#include -#include -#include -#include - -// Suppress Tiff Warnings -void TiffDummyHandler(const char* module, const char* fmt, va_list ap) -{ - // ignore errors and warnings (or handle them your own way) -} - -// 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; -} - -// Dilate masks by one 4-connected pixel -void dilate(uint16_t** mask, uint32_t width, uint32_t height) -{ - uint16_t *new_mask = _dilate(*mask, width, height); - if (new_mask != NULL) { - free(*mask); - *mask = 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)); - memcpy(new_mask, mask, 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); - 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] = 0; - continue; - } - } - if ((x+1) != width) { - proposed_position = xy_to_coord(x+1, y, width, height); - if (mask[proposed_position] == 0) { - new_mask[current_position] = 0; - continue; - } - } - if (y != 0) { - proposed_position = xy_to_coord(x, y-1, width, height); - if (mask[proposed_position] == 0) { - new_mask[current_position] = 0; - continue; - } - } - if ((y+1) != height) { - proposed_position = xy_to_coord(x, y+1, width, height); - if (mask[proposed_position] == 0) { - new_mask[current_position] = 0; - continue; - } - } - } - } - return new_mask; -} - -// Erode masks by one 4-connected pixel -void erode(uint16_t** mask, uint32_t width, uint32_t height) -{ - uint16_t *new_mask = _erode(*mask, width, height); - if (new_mask != NULL) { - free(*mask); - *mask = 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++) { - dilate(&new_mask, width, height); - } - for (size_t count = 0; count < num_pixels; count++) { - erode(&new_mask, width, height); - } - // 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; -} - -// Close up masks by N-pixels -// Update pointer -void closeup(uint16_t** mask, uint32_t width, uint32_t height, size_t num_pixels) -{ - uint16_t *new_mask = _closeup(*mask, width, height, num_pixels); - if (new_mask != NULL) { - free(*mask); - *mask = 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) -{ - TIFFSetWarningHandler(TiffDummyHandler); - //-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; -} - -// Reduce a mask to the contiguous regions -uint16_t* _reduce_contiguous_regions(uint16_t* masks, uint32_t width, uint32_t height, uint16_t* total_labels) -{ - uint16_t starting_label = 1; - uint16_t* new_masks = (uint16_t*)calloc(width*height, sizeof(uint16_t)); - if (new_masks == NULL) { - 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 channels = 2; // uint16_t = 2*uint8_t - if (flood((uint8_t*)masks, new_masks, width, height, channels, x, y, &(((uint8_t*)masks)[coord*channels]), starting_label)) { - starting_label++; - } - } - } - if (total_labels != NULL) { - *total_labels = starting_label; - } - return new_masks; -} - -// Reduce a mask to the contiguous regions -// Automatically update pointer to contiguous mask -// Freeing previous mask -void reduce_contiguous_regions(uint16_t** masks_p, uint32_t width, uint32_t height, uint16_t* total_labels) -{ - if (masks_p == NULL) { - return; - } - uint16_t* new_masks = _reduce_contiguous_regions(*masks_p, width, height, total_labels); - if (new_masks != NULL) { - free(*masks_p); - *masks_p = new_masks; - } -} diff --git a/src/lib/time.c b/src/lib/time.c deleted file mode 100644 index 085ef80..0000000 --- a/src/lib/time.c +++ /dev/null @@ -1,13 +0,0 @@ -#include - -// Difference in Time -// Compute the difference between timespec structs -double diff_time(struct timespec *time1, struct timespec *time0) { - return (time1->tv_sec - time0->tv_sec) - + (time1->tv_nsec - time0->tv_nsec) / 1000000000.0; -} - -// Get Current Time -void get_time(struct timespec *ts) { - timespec_get(ts, TIME_UTC); -} -- cgit v1.2.1