{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "44e5ce7f",
   "metadata": {},
   "source": [
    "# Lesson 4: Flood Fill and Connected Components\n",
    "\n",
    "Once we have a binary image (e.g., from thresholding, Lesson 3), a natural next question is: *how many separate blobs are there, and where are they?* Two tools answer this:\n",
    "\n",
    "- **Flood fill** grows a region from a single seed pixel, spreading to all connected neighbors that share a similar value.\n",
    "- **Connected component labeling** finds *all* such regions in a binary image at once, labeling each with a unique ID."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "53cb5cb2",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import cv2\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ad7a36dc",
   "metadata": {},
   "source": [
    "## Create a binary image of several blobs\n",
    "\n",
    "Let's load a grayscale image of some fruit on a dark background, using Lesson 3 to threshold the image and remove the salt noise."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8ad1f4cd",
   "metadata": {},
   "outputs": [],
   "source": [
    "img = cv2.imread('../img/fruit.jpg', cv2.IMREAD_GRAYSCALE)\n",
    "_, im_bin = cv2.threshold(img, 0, 255, cv2.THRESH_BINARY + cv2.THRESH_OTSU)\n",
    "kernel = np.ones((3, 3), np.uint8)\n",
    "im_bin2 = cv2.morphologyEx(im_bin, cv2.MORPH_OPEN, kernel)\n",
    "\n",
    "fig, axes = plt.subplots(1, 3, figsize=(10,4))\n",
    "axes[0].imshow(img, cmap='gray', vmin=0, vmax=255)\n",
    "axes[0].set_title('Original')\n",
    "axes[0].axis('off')\n",
    "axes[1].imshow(im_bin, cmap='gray', vmin=0, vmax=255)\n",
    "axes[1].set_title('Thresholded')\n",
    "axes[1].axis('off')\n",
    "axes[2].imshow(im_bin2, cmap='gray', vmin=0, vmax=255)\n",
    "axes[2].set_title('After opening')\n",
    "axes[2].axis('off')\n",
    "plt.tight_layout()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "51d1b6eb",
   "metadata": {},
   "source": "<p class=\"image-attribution\">Image source: Stan Birchfield</p>"
  },
  {
   "cell_type": "markdown",
   "id": "9aed1b4c",
   "metadata": {},
   "source": [
    "## Flood fill from a seed point\n",
    "\n",
    "Flood fill starts at a seed pixel and spreads outward to all connected pixels within a tolerance of the seed value, painting them a new color. The classic algorithm keeps a \"frontier\" of pixels still to visit (implemented as a stack or queue): Pop a pixel; if it's foreground and not yet filled, mark it filled and push its 4-connected neighbors onto the stack. Repeat until the stack is empty, at which point every pixel reachable from the seed by a path of foreground pixels has been found."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "85e34f86",
   "metadata": {},
   "outputs": [],
   "source": [
    "def flood_fill_stack(binary, seed):\n",
    "    \"\"\"Classic flood fill: an explicit stack holds the frontier of pixels still to visit.\"\"\"\n",
    "    filled = np.zeros_like(binary, dtype=bool)\n",
    "    h, w = binary.shape\n",
    "    stack = [seed]\n",
    "    while stack:\n",
    "        x, y = stack.pop()\n",
    "        if x < 0 or x >= w or y < 0 or y >= h:\n",
    "            continue\n",
    "        if filled[y, x] or binary[y, x] == 0:\n",
    "            continue\n",
    "        filled[y, x] = True\n",
    "        stack.extend([(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)])  # 4-connected neighbors\n",
    "    return filled"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ac913742",
   "metadata": {},
   "source": [
    "Here we seed the algorithm with a pixel inside the first banana."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "04a24323",
   "metadata": {},
   "outputs": [],
   "source": [
    "seed = (60, 110)  # (x, y) inside the first banana\n",
    "im_region_filled = flood_fill_stack(im_bin2, seed)\n",
    "\n",
    "im_filled = cv2.cvtColor(im_bin2, cv2.COLOR_GRAY2RGB)\n",
    "im_filled[im_region_filled] = (255, 140, 0)\n",
    "\n",
    "plt.imshow(im_filled)\n",
    "plt.scatter(*seed, c='red', s=30, marker='x')\n",
    "plt.title(f'Flood fill from scratch ({im_region_filled.sum()} pixels filled)')\n",
    "plt.axis('off')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a28e0330",
   "metadata": {},
   "source": [
    "## Flood fill from a seed point\n",
    "\n",
    "`cv2.floodFill` does exactly the same thing, just considerably faster because it is compiled."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7936b606",
   "metadata": {},
   "outputs": [],
   "source": [
    "# floodFill needs a mask 2 pixels larger than the image, and modifies the image in place\n",
    "im_filled_cv2 = cv2.cvtColor(im_bin2, cv2.COLOR_GRAY2RGB)\n",
    "im_mask = np.zeros(np.add(im_bin2.shape, (2, 2)), dtype=np.uint8)\n",
    "\n",
    "cv2.floodFill(im_filled_cv2, im_mask, seed, (255, 140, 0))\n",
    "\n",
    "plt.imshow(im_filled_cv2)\n",
    "plt.scatter(*seed, c='red', s=30, marker='x')\n",
    "plt.title('Flood fill from one seed (red x)')\n",
    "plt.axis('off')\n",
    "plt.show()\n",
    "\n",
    "im_region_filled_cv2 = np.all(im_filled_cv2 == (255, 140, 0), axis=-1)\n",
    "print(f'The two implementations match exactly: {np.array_equal(im_region_filled, im_region_filled_cv2)}')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9ab456bc",
   "metadata": {},
   "source": [
    "## Connected components: label every blob at once\n",
    "\n",
    "Instead of picking seeds by hand, the connected-component labeling algorithm (`cv2.connectedComponentsWithStats`) scans the whole image and assigns every blob its own integer label. (The classic algorithm, which is omitted for brevity, is known as *union-find*, and it requires two passes through the image, as well a traversal of the equivalence table.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "75a90b3d",
   "metadata": {},
   "outputs": [],
   "source": [
    "num_labels, labels, stats, centroids = cv2.connectedComponentsWithStats(im_bin2, connectivity=8)\n",
    "\n",
    "# Give each label a distinct random color for visualization\n",
    "colors = np.array([(0,0,0), (255,0,0), (0,200,0), (0,0,255), (180,180,0), (0,180,180), (180,0,180)])\n",
    "\n",
    "im_colored = colors[labels].astype(np.uint8)\n",
    "\n",
    "plt.imshow(im_colored)\n",
    "for label in range(1, num_labels):\n",
    "    cx, cy = centroids[label]\n",
    "    plt.text(cx, cy, str(label), color='white', ha='center', va='center', fontsize=12, fontweight='bold')\n",
    "plt.title('Connected components, colored and labeled')\n",
    "plt.axis('off')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "33c88544",
   "metadata": {},
   "source": [
    "The connected-component labeling algorithm also returns handy stats (e.g., bounding box, area, centroid). This additional information is essentially free, as it requires almost no extra computation (as we will see in Lesson 5)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ea664b4e",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(f'Found {num_labels - 1} blobs (plus the background as label 0)\\n')\n",
    "print(f'{\"label\":>5} {\"area\":>6} {\"centroid\":>16}')\n",
    "for label in range(1, num_labels):\n",
    "    area = stats[label, cv2.CC_STAT_AREA]\n",
    "    cx, cy = centroids[label]\n",
    "    print(f'{label:>5} {area:>6} ({cx:6.1f}, {cy:6.1f})')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "678ac611",
   "metadata": {},
   "source": [
    "## Filtering blobs by size\n",
    "\n",
    "A common use of connected components is to discard small, noise-like blobs and keep only significant ones. Here we choose a threshold that removes the small apples (blobs 2 and 6)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3a3e1120",
   "metadata": {},
   "outputs": [],
   "source": [
    "min_area = 3000\n",
    "img_minsize = np.zeros_like(im_bin2)\n",
    "for label in range(1, num_labels):\n",
    "    if stats[label, cv2.CC_STAT_AREA] > min_area:\n",
    "        img_minsize[labels == label] = 255\n",
    "\n",
    "fig, axes = plt.subplots(1, 2, figsize=(8, 3.5))\n",
    "axes[0].imshow(im_bin2, cmap='gray')\n",
    "axes[0].set_title('All blobs')\n",
    "axes[0].axis('off')\n",
    "axes[1].imshow(img_minsize, cmap='gray')\n",
    "axes[1].set_title(f'Blobs with area > {min_area}')\n",
    "axes[1].axis('off')\n",
    "plt.tight_layout()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "53abce0b",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "1. Change `connectivity=8` to `connectivity=4` in `connectedComponentsWithStats`. Construct a binary image (e.g., a diagonal staircase of single pixels) where 4-connectivity and 8-connectivity give a *different* number of components.\n",
    "2. Use `cv2.floodFill` with a nonzero `loDiff`/`upDiff` tolerance on a grayscale (not binary) image, and describe what changes."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.x"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}