Gaussian Scale Space

mediumPROFeature Detection and MatchingComputer Vision 1

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 ( $\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, \sigma) = \frac{1}{\sqrt{2\pi}\sigma} e^{-\frac{x^2}{2\sigma^2}}$

Algorithm for each sigma:

Determine kernel radius: $r = \lceil 3\sigma \rceil$ (capture 99.7% of the distribution)
Build the kernel: compute $G(x, \sigma)$ for $x \in [-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

Input

signal = [0, 0, 1, 0, 0]
sigmas = [0.5]

Output

[[0.0003, 0.1065, 0.7866, 0.1065, 0.0003]]

Reasoning

Determine the kernel radius: $r = \lceil 3\sigma \rceil = \lceil 3 \cdot 0.5 \rceil = \lceil 1.5 \rceil = 2$
Build and normalize the kernel: compute $G(x, 0.5)$ for $x \in [-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

More from Computer Vision 1

Semi-Global Matching Cost Aggregationhard Compute Depth Map from Disparitymedium Stereo Rectification Checkeasy Oriented BRIEF Descriptorhard Non-Maximum Suppression (NMS)easy

Concept primerPREVIEW

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 ( $\sigma$ ). 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, \sigma) =$ \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 $\sigma$ .

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 $\sigma$ , 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 $\sigma$ 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 = \lceil 3\sigma \rceil$ . The kernel is then built by computing $G(x, \sigma)$ for $x \in [-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.

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

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.

solution.py

Python 3.13

Test results