Library directories

2 files changed, 623 insertions, 0 deletions

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 <lib/seg/mask_data.h>
+#include <lib/seg/util.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;
+}
+
+// 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 <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>
+
+// 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;
+  }
+}