OpenCV学习基础图像操作（十七）：泛洪与分水岭算法

原理

泛洪填充算法和分水岭算法是图像处理中的两种重要算法，主要用于区域分割，但它们的原理和应用场景有所不同，但是他们的基础思想都是基于区域迭代实现的区域之间的划分。

泛洪算法

泛洪填充算法（Flood Fill）是一种经典的图像处理算法，用于确定和标记与给定点连接的区域，通常在图像填充、分割、边界检测等方面应用广泛。为了更直观地理解泛洪填充算法，我们可以通过一系列生动的图像和步骤来介绍其工作原理。

假设我们有一个二维图像，每个像素可以有不同的颜色或灰度值。泛洪填充算法的目标是从某个起始像素开始，填充所有与其相连且具有相同颜色的像素。常见的应用包括图像编辑中的填充工具（如油漆桶工具）和迷宫求解等。

算法流程

以下是泛洪填充算法的基本步骤，配合图像说明：

选择起始点和目标颜色：
1. 选择图像中的一个起始像素点（如鼠标点击的位置），记作 (x, y)。
2. 确定要填充的目标颜色。
初始化队列：
- 将起始点 (x, y) 加入队列。
处理队列：
当队列不为空时，重复以下步骤：
- 从队列中取出一个像素点 (cx, cy)。
- 如果 (cx, cy) 的颜色等于目标颜色，则进行填充。
- 将 (cx, cy) 的四个邻居（上、下、左、右）加入队列（如果这些邻居还没有被处理过且颜色等于目标颜色）。

分水岭算法

分水岭算法是一种基于形态学和拓扑学的图像分割技术。它将图像视为一个拓扑地形，通过标记图像的不同区域（例如山脉和盆地）进行分割。分水岭算法的基本思想是通过模拟雨水从山顶流向盆地的过程，确定图像中不同区域的边界。

分水岭迭代过程：

把梯度图像中的所有像素按照灰度值进行分类，并设定一个测地距离阈值。
找到灰度值最小的像素点（默认标记为灰度值最低点），让threshold从最小值开始增长，这些点为起始点。
水平面在增长的过程中，会碰到周围的邻域像素，测量这些像素到起始点（灰度值最低点）的测地距离，如果小于设定阈值，则将这些像素淹没，否则在这些像素上设置大坝，这样就对这些邻域像素进行了分类。
随着水平面越来越高，会设置更多更高的大坝，直到灰度值的最大值，所有区域都在分水岭线上相遇，这些大坝就对整个图像像素的进行了分区。

实际应用时常结合其他预处理，来实现前后景的分割：

算法流程

梯度计算：首先计算图像的梯度，梯度可以使用 Sobel 算子或其他方法计算。梯度图像反映了图像中像素值变化的幅度。

$G(x,y)=\sqrt{(\frac{\partial I}{\partial x})^2+(\frac{\partial I}{\partial y})^2}$

其中，𝐼 是原始图像，𝐺是梯度图像。
标记区域：对图像进行标记，将前景对象和背景标记出来。可以使用形态学操作来获取这些标记。
- 确定前景：使用距离变换和阈值化来确定前景区域。
  
  $D(x,y)=distance\_tranform(I)$
  $foreground(x,y)=\begin{cases} 1 & \text{ if } D(x,y) > 1 \\ 0 & \text{ if } othersize \end{cases}$
- 确定背景：通过膨胀操作扩展前景区域，从而确定背景区域。
  
  $background(x,y)=dilate(foreground,kernel)$
确定未知区域：未知区域是背景和前景的差集。

$unknown=background-foreground$
连接组件标记：对前景区域进行连通组件标记，每个连通组件代表一个独立的前景对象。

$markers=connected\_components(foreground)$
分水岭变换：使用分水岭变换对梯度图像进行处理，分割图像中的不同区域。

$markers=watershed(G,markers)$

分水岭变换后，标记图像的边界区域将被标记为 -1。

API介绍

floodfill

int cv::floodFill	(	InputOutputArray 	image,   //输入图像
    InputOutputArray 	mask,                        //输入输出的maks
    Point 	seedPoint,                               //种子点
    Scalar 	newVal,                                  //信的
    Rect * 	r    ect = , 0                           // 存储填充区域的边界
    Scalar 	loDiff = , Scalar()                      // 允许填充的像素值差的下届
    Scalar 	upDiff = , Scalar()                      // 允许填充的像素值差的上届
    int 	flags = 4                                // 4联通或8联通
)

import cv2
import numpy as np
import matplotlib.pyplot as plt
def main():
    # 加载图像
    image_path = 'D:\code\src\code\lena.jpg'  # 替换为你的图像路径
    image = cv2.imread(image_path)
    if image is None:
        print("Error: Unable to load image.")
        return


    # 定义种子点和新颜色
    seed_point = (30, 30)  # 替换为你希望的种子点 (x, y)
    new_color = (0, 0, 255)  # 新颜色为绿色 (B, G, R)

    # 创建掩码，比原图多出两行两列
    mask = np.zeros((image.shape[0] + 2, image.shape[1] + 2), np.uint8)

    # 设置差值范围
    lo_diff = (10, 10, 10)
    up_diff = (10, 10, 10)

    image_src = image.copy()

    # 执行泛洪填充
    flags = 4  # 4-连通
    num, im, mask, rect = cv2.floodFill(image, mask, seed_point, new_color, lo_diff, up_diff, flags)

    # 显示填充后的图像
    plt.subplot(131),plt.imshow(image_src[...,::-1]),plt.title('Source Image'), plt.xticks([]), plt.yticks([])
    plt.subplot(132),plt.imshow(mask[...,::-1]),plt.title('Mask Image'), plt.xticks([]), plt.yticks([])
    plt.subplot(133),plt.imshow(image[...,::-1]),plt.title('Filled Image'), plt.xticks([]), plt.yticks([])
    plt.show()



if __name__ == '__main__':
    main()

watermeshed

cv::watershed	(	InputArray 	image,  //输入图像
InputOutputArray 	markers             //输入出的标记
)	
//即根据传入的确信区域以及原图，经过分水岭迭代后，得到的确信区域

import cv2
import numpy as np
import matplotlib.pyplot as plt
import imageio

def plot_image(image, title, save_path):
    plt.imshow(cv2.cvtColor(image, cv2.COLOR_BGR2RGB))
    plt.title(title)
    plt.axis('off')
    plt.savefig(save_path)
    plt.close()

def save_gif(frames, filename, duration=0.5):
    imageio.mimsave(filename, frames, duration=duration)

def watershed_segmentation(image_path):
    # Read the image
    image = cv2.imread(image_path)
    gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)

    # Apply thresholding
    ret, thresh = cv2.threshold(gray, 0, 255, cv2.THRESH_BINARY_INV + cv2.THRESH_OTSU)

    # Noise removal with morphological operations
    kernel = np.ones((3, 3), np.uint8)
    opening = cv2.morphologyEx(thresh, cv2.MORPH_OPEN, kernel, iterations=2)

    # Sure background area
    sure_bg = cv2.dilate(opening, kernel, iterations=3)

    # Finding sure foreground area
    dist_transform = cv2.distanceTransform(opening, cv2.DIST_L2, 5)
    ret, sure_fg = cv2.threshold(dist_transform, 0.7 * dist_transform.max(), 255, 0)

    # Finding unknown region
    sure_fg = np.uint8(sure_fg)
    unknown = cv2.subtract(sure_bg, sure_fg)

    # Marker labelling
    ret, markers = cv2.connectedComponents(sure_fg)

    # Add one to all labels so that sure background is not 0, but 1
    markers = markers + 1

    # Now, mark the region of unknown with zero
    markers[unknown == 255] = 0

    # Apply watershed
    markers = cv2.watershed(image, markers)
    image[markers == -1] = [255, 0, 0]  # Mark boundaries with red color

    # Collect frames for GIF
    frames = []
    for step in ['Original', 'Threshold', 'Morph Open', 'Sure BG', 'Sure FG', 'Unknown', 'Markers', 'Watershed']:
        if step == 'Original':
            frame = image.copy()
        elif step == 'Threshold':
            frame = cv2.cvtColor(thresh, cv2.COLOR_GRAY2BGR)
        elif step == 'Morph Open':
            frame = cv2.cvtColor(opening, cv2.COLOR_GRAY2BGR)
        elif step == 'Sure BG':
            frame = cv2.cvtColor(sure_bg, cv2.COLOR_GRAY2BGR)
        elif step == 'Sure FG':
            frame = cv2.cvtColor(sure_fg, cv2.COLOR_GRAY2BGR)
        elif step == 'Unknown':
            frame = cv2.cvtColor(unknown, cv2.COLOR_GRAY2BGR)
        elif step == 'Markers':
            frame = np.zeros_like(image)
            for i in range(1, ret + 1):
                frame[markers == i] = np.random.randint(0, 255, size=3)
        elif step == 'Watershed':
            frame = image.copy()
        
        frame_path = f"{step.lower().replace(' ', '_')}.png"
        plot_image(frame, step, frame_path)
        frames.append(imageio.imread(frame_path))
    
    return frames

# Main execution
image_path = 'D:\code\src\code\R-C.png'  # Replace with your image path
frames = watershed_segmentation(image_path)
save_gif(frames, 'watershed.gif', duration=1000)