Convolution, correlation, and Fourier transformation
Department of Data Communication Networks and Systems
Lecturer Shukhrat Palvanov
Introduction
Fundamental Operations in Signal Processing
Signal processing involves analyzing, modifying, and extracting information from signals (1D: audio, 2D: images).
Two key mathematical tools are convolution and correlation.
Both operations help in understanding how signals interact with systems or with other signals.
Why Convolution and Correlation are Important
Convolution: Models how a signal changes when it passes through a system (e.g., filtering noise, blurring/sharpening an image, applying an impulse response).
Correlation: Measures the similarity between two signals or patterns (e.g., detecting a known pattern inside a larger signal, template matching in images).
Widely applied in areas like communications, audio processing, computer vision, medical imaging, and machine learning.
Signals in Time and Space�
1D Signals (Time Domain)
Represented as a function of time: x(t) or x[n].
Examples:
2D Signals (Spatial Domain)
Represented as a function of two variables: f(x,y).
Examples:
Key Idea:
What is Convolution?�
Definition: Convolution is a mathematical operation that combines two signals to form a third signal.
It describes how the shape of one signal is modified by another (usually a filter or system).
In signal processing, convolution is used to model the effect of an input signal passing through a linear time-invariant (LTI) system.
In image processing, convolution means applying a kernel (filter matrix) to an image to extract or modify features.
Key Concept: Flip → Shift → Multiply → Sum.
Convolution Formula (1D – Discrete)�
Key Points:
Convolution Formula (Continuous)
Key Points:
Convolution Intuition�
Convolution can be thought of as a four-step process:
Intuitively, convolution measures the amount of overlap between two signals as one slides over the other.
In 1D: overlap of waveforms.
In 2D: overlap of image regions with a filter/kernel.
�Convolution shows how much one function “matches” another when shifted and combined.
Convolution Example (1D)
Common Kernels in Image Processing
Image Blurring
Blurring is achieved by averaging the values of neighboring pixels.
A smoothing (low-pass) filter reduces high-frequency components such as noise and sharp edges.
Kernel Example (3×3 Average Filter):
Effects of Blurring:
Removes random noise.
Reduces image details.
Useful as a preprocessing step before edge detection or compression.
Applications:
Noise reduction in images.
Background smoothing.
Computer vision preprocessing.
Edge Detection
Edge detection highlights regions in an image where intensity changes sharply.
Achieved using convolution with special kernels (high-pass filters).
Common Kernels:
Sobel Operator (Horizontal & Vertical): Detects edges in specific directions.
Prewitt Operator: Similar to Sobel but simpler.
Laplacian Filter: Detects edges regardless of orientation.
Effects of Edge Detection:
Identifies object boundaries.
Enhances structural details.
Forms the basis of many computer vision tasks (object recognition, segmentation).
Applications:
Medical imaging (detecting tumors, structures).
Self-driving cars (lane detection).
Facial recognition and object tracking.
Properties of Convolution
What is Correlation?�
Correlation is a mathematical operation that measures the similarity between two signals (or functions).
Unlike convolution, correlation does not flip the signal.
Mathematical Formula (Discrete):
Key Points:
Shows how much one signal resembles another at different shifts.
Often used to detect the presence of a known pattern in a larger signal.
In 2D (images), correlation is used for template or pattern matching.
�Correlation “slides” one signal over another and calculates the degree of similarity at each position.
Cross-Correlation�
Cross-correlation measures the similarity between two different signals as one is shifted over the other.
Mathematical Formula (Discrete):
Key Points:
High correlation value → signals are similar at that shift.
Low (or negative) correlation value → signals are dissimilar.
Used when comparing two different signals.
Applications:
Pattern recognition (detecting a known signal in noise).
Time delay estimation in communications.
Feature matching in computer vision.
Auto-Correlation�
Auto-correlation measures the similarity of a signal with itself at different time shifts (lags).
Mathematical Formula (Discrete):
Key Points:
Maximum value occurs at zero lag (n=0).
Symmetric function:
Useful to find repeating patterns and periodicity in signals.
Applications:
Detecting periodic signals (e.g., speech, ECG).
Signal energy and power analysis.
Identifying fundamental frequency in music and communications.
Correlation Example (1D)�
�Let two sequences be:
Step-by-Step Process:
Shift y[n] over x[n].
Multiply overlapping values.
Sum the products for each shift.
Result (Cross-Correlation):
Interpretation:
Peak value occurs where y[n] best aligns with x[n].
Shows the position where the two signals are most similar.
Correlation in 2D (Images)�
In 2D, correlation measures the similarity between an image and a smaller pattern (template) by sliding the template across the image.
Key Points:
Produces a correlation map showing similarity at each location.
High value = strong match between template and image region.
Unlike convolution, no flipping of the template is done.
Applications:
Template matching (e.g., face detection, object recognition).
Tracking moving objects in video.
Quality inspection in manufacturing (pattern alignment).
Advantages of Fourier Transform in Image Processing�
What is Fourier Transform (FT)?�
A powerful mathematical tool that converts a signal or image from the spatial (time/space) domain into the frequency domain.
Instead of analyzing the values of pixels directly, FT focuses on how often intensity values change.
Basic Idea
Importance of FT in Image Processing�
Mathematical Background�Fourier Series vs Fourier Transform�
Fourier Series: Represents periodic signals as a sum of sinusoids.
Fourier Transform (FT): Extends the concept to non-periodic signals.
In image processing, signals (images) are generally non-periodic → FT is used.
2D Fourier Transform�
2D Fourier Transform
Interpretation
Why Important?
Fourier Transform Properties
1. Linearity
FT of a sum = Sum of FTs
Useful for combining signals.
2. Shift Property
A shift in spatial domain → phase change in frequency domain.
Image translation does not affect magnitude spectrum.
3. Scaling (Dilation)
Enlarging an image in spatial domain shrinks its spectrum in frequency domain.
Compression in spatial domain expands the spectrum.
4. Convolution Theorem
Convolution in spatial domain = Multiplication in frequency domain.
Very useful for image filtering (blurring, sharpening).
5. Symmetry
For real-valued images, the Fourier spectrum is symmetric.
Frequency Representation of Images
Key Concept
An image can be expressed as a combination of low-frequency and high-frequency components.
Fourier Transform separates these components clearly.
Low Frequencies
Located near the center of Fourier spectrum.
Represent smooth intensity variations (background, lighting, gradual changes).
Carry the overall structure of the image.
High Frequencies
Located at the edges of the spectrum.
Represent rapid intensity changes (edges, fine details, noise).
Important for sharpness and texture.
Discrete Fourier Transform (DFT)
Why DFT?
Visualization of Fourier Spectrum
Magnitude and Phase
Log Transformation
Thank you