求快速2D十字形中值滤波算法（支持+、x两种核类型）

Got it, let's tackle this cross-shaped median filter problem—both the standard "+" (axis-aligned) and "x" (diagonal) kernels. The naive sliding window with sorting is way too slow for large images, and since standard histogram-based methods only work for square kernels, we need a custom optimized solution that leverages the cross's unique structure.

Axis-Aligned "+" Cross Kernel #

The key here is to use a rolling histogram that updates incrementally as the cross slides across the image, instead of recalculating the entire window's pixel distribution every time.

How it works: #

1. Initialize the histogram: For the starting cross position, count the frequency of each pixel value in the horizontal line (center row, spanning kernel width) and vertical line (center column, spanning kernel height). Important: subtract the center pixel once, since it's counted twice in the horizontal+vertical lines.
2. Slide the cross horizontally:
   • Remove the pixel values that are sliding out of the left end of the horizontal line.
   • Add the pixel values that are sliding into the right end of the horizontal line.
   • The vertical line stays the same, so no changes there.
3. Slide the cross vertically:
   • Remove the pixel values that are sliding out of the top end of the vertical line.
   • Add the pixel values that are sliding into the bottom end of the vertical line.
   • The horizontal line stays the same, so no changes there.
4. Find the median: For each updated histogram, iterate through the frequency counts until you reach the middle position of the cross's total pixel count.

Quick Pseudocode Snippet: #

import numpy as np

def plus_cross_median_filter(image, kernel_size):
    h, w = image.shape
    half_k = kernel_size // 2
    total_pixels = 2 * kernel_size - 1  # subtract 1 for overlapping center
    median_pos = total_pixels // 2 + 1
    
    # Initialize histogram (assuming 8-bit image, 0-255)
    hist = [0] * 256
    # Populate initial cross (center at (half_k, half_k))
    # Horizontal line
    for x in range(half_k - half_k, half_k + half_k + 1):
        val = image[half_k, x]
        hist[val] += 1
    # Vertical line (subtract center once to fix double count)
    for y in range(half_k - half_k, half_k + half_k + 1):
        val = image[y, half_k]
        hist[val] += 1
    hist[image[half_k, half_k]] -= 1
    
    # Process each pixel with boundary handling
    output = np.zeros_like(image)
    for y in range(h):
        # Adjust vertical histogram when moving down past the initial row
        if y > half_k:
            # Remove top pixel from previous vertical cross
            top_y = y - kernel_size
            if top_y >= 0:
                top_val = image[top_y, x] if x >=0 else 0
                hist[top_val] -= 1
            # Add new bottom pixel to current vertical cross
            bottom_val = image[y, half_k]
            hist[bottom_val] += 1
        
        for x in range(w):
            # Adjust horizontal histogram when moving right past initial column
            if x > half_k:
                # Remove left pixel from previous horizontal cross
                left_x = x - kernel_size
                if left_x >= 0:
                    left_val = image[y, left_x]
                    hist[left_val] -= 1
                # Add new right pixel to current horizontal cross
                right_val = image[y, x]
                hist[right_val] += 1
            
            # Find median from histogram
            count = 0
            median_val = 0
            for val in range(256):
                count += hist[val]
                if count >= median_pos:
                    median_val = val
                    break
            output[y, x] = median_val
    return output

Diagonal "x" Cross Kernel #

This follows the same rolling histogram logic, but we're dealing with two diagonal lines instead of axis-aligned ones.

How it works: #

1. Initialize the histogram: Count pixel values in the main diagonal (top-left to bottom-right) and anti-diagonal (top-right to bottom-left) of the cross. Again, subtract the center pixel once to avoid double-counting.
2. Slide the cross:
   • When sliding right/down, remove the pixels that are sliding out of the top-left end of the main diagonal and top-right end of the anti-diagonal.
   • Add the new pixels entering the bottom-right end of the main diagonal and bottom-left end of the anti-diagonal.
3. Find the median: Same as the "+" cross—use the updated histogram to find the middle value quickly.

Key Note: #

Make sure to handle image boundaries properly (clamp the kernel to the image edges, or use zero/reflect padding if needed) to avoid index errors during sliding.

Why This Is Faster #

The naive approach runs in O(WHK log K) time, where K is the number of pixels in the cross. The rolling histogram approach runs in O(WHL) time, where L is the number of possible pixel values (e.g., 256 for 8-bit images). This is a massive speedup, especially for large images or large kernel sizes.

内容的提问来源于stack exchange，提问作者james