Gaussian Scale Space
Compute the Gaussian scale space of a 1D signal by convolving it with Gaussian kernels at multiple scales.
Given a 1D signal and a list of sigma (σ) values, compute the scale-space representation by convolving the signal with a 1D Gaussian kernel at each scale.
The 1D Gaussian kernel:
G(x,σ)=2π​σ1​e−2σ2x2​
Algorithm for each sigma:
- Determine kernel radius: r=⌈3σ⌉ (capture 99.7% of the distribution)
- Build the kernel: compute G(x,σ) for x∈[−r,r]
- Normalize the kernel so it sums to 1
- Convolve the signal with the kernel (using zero-padding at boundaries)
Return a list of lists, where each inner list is the smoothed signal at that scale. Round each value to 4 decimal places.
Example:
signal = [0, 0, 1, 0, 0] sigmas = [0.5]
[[0.0003, 0.1065, 0.7866, 0.1065, 0.0003]]
- Determine the kernel radius: r=⌈3σ⌉=⌈3⋅0.5⌉=⌈1.5⌉=2
- Build and normalize the kernel: compute G(x,0.5) for x∈[−2,2] and normalize so it sums to 1
- Convolve the signal
[0, 0, 1, 0, 0]with the normalized kernel, using zero-padding at boundaries, resulting in the smoothed signal - Round each value in the smoothed signal to 4 decimal places, yielding the output:
[[0.0003, 0.1065, 0.7866, 0.1065, 0.0003]]
Constraints:
- signal: List of floats (1D signal)
- sigmas: List of floats (sigma values for each scale)
- Return: List of lists (one smoothed signal per sigma)
- Kernel radius = ceil(3 * sigma)
- Use zero-padding for boundary handling
- Round to 4 decimal places
- Use math module for exp and sqrt
Background Knowledge
The Gaussian scale space is a fundamental concept in computer vision, particularly in feature detection and matching. It involves representing a signal at multiple scales by convolving it with Gaussian kernels of varying standard deviations (σ). The Gaussian kernel, also known as the Gaussian distribution, is a probability distribution that is commonly used to model the distribution of values in a signal. The 1D Gaussian kernel is defined as G(x,σ)=\frac{1}{\sqrt{2\pi}\sigma} e^{-\frac{x^2}{2\sigma^2}}. This kernel is symmetric around the origin and has a standard deviation of σ.
The concept of scale space is important in computer vision because it allows us to analyze a signal at different levels of detail. By convolving a signal with Gaussian kernels of increasing σ, we can capture features at multiple scales, from fine details to coarse structures. The Gaussian scale space is also useful for reducing noise in a signal, as the convolution process can help to smooth out high-frequency components. In the context of this problem, we are given a 1D signal and a list of σ values, and we need to compute the scale-space representation by convolving the signal with a 1D Gaussian kernel at each scale.
The algorithm for computing the Gaussian scale space involves several key steps, including determining the kernel radius, building the kernel, normalizing the kernel, and convolving the signal with the kernel. The kernel radius is typically chosen to capture 99.7% of the distribution, which corresponds to a radius of r=⌈3σ⌉. The kernel is then built by computing G(x,σ) for x∈[−r,r], and normalized so that it sums to 1. Finally, the signal is convolved with the kernel using zero-padding at the boundaries to prevent edge effects.
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.