Unit VI: Motion Analysis (6 Hours)

Motion analysis is a critical area in computer vision and image processing, focusing on understanding
the movement of objects or features in dynamic scenes. This unit covers methods for estimating
motion, analyzing trajectories, and understanding dynamic environments.

1. Dynamic Scene Analysis

 Definition: Dynamic scene analysis involves identifying and interpreting motion within a
sequence of images or video frames. It is used in applications like surveillance, robotics, and
autonomous driving.

 Challenges:

o Handling occlusions

o Noise in motion estimation

o Complex and overlapping motions

2. Estimating Motion Vectors

Motion vectors represent the displacement of pixels or features between consecutive frames.

(a) Sequential Search Algorithm

 Description: A brute-force approach that searches for the best match for a pixel or block in
the next frame within a predefined search window.

 Steps:

1. Define a search window around the pixel/block.

2. Compute a similarity metric (e.g., Mean Squared Error, MSE) for each candidate
position.

3. Choose the position with the best match.

 Advantages: Simple and accurate for small motions.

 Disadvantages: Computationally expensive.

(b) Logarithmic Search Algorithm

 Description: An efficient algorithm that reduces the search space iteratively.

 Steps:

1. Divide the search window into quadrants.

2. Test the center and boundaries of the quadrants for the best match.

3. Narrow down the search to the quadrant with the best match.

4. Repeat until the search converges.

  Advantages: Faster than sequential search.

 Disadvantages: May miss the global optimum for large motions.

(c) Hierarchical Search

 Description: A multi-resolution approach where motion estimation is performed on a

pyramid of image resolutions.

 Steps:

1. Generate a pyramid of images (low to high resolution).

2. Perform motion estimation at the lowest resolution.

3. Refine the estimate progressively at higher resolutions.

 Advantages: Efficient for large motions.

 Disadvantages: Increased complexity in implementation.

3. Motion Analysis

Motion analysis encompasses a range of techniques to infer motion patterns and dynamics in a
scene.

Differential Motion Analysis Methods

 Principle: Based on temporal and spatial gradients of intensity.

 Approach: Compute the rate of change of intensity values (optical flow) to estimate motion.

 Common Techniques:

o Lucas-Kanade method

o Horn-Schunck method

4. Trajectory Detection

 Definition: The process of identifying and tracking the paths of moving objects over time.

 Techniques:

o Feature-based tracking: Use interest points like corners (e.g., Harris detector).

o Model-based tracking: Use predefined object models.

o Blob tracking: Track connected regions of pixels.

5. Optical Flow Analysis

 Definition: Optical flow refers to the apparent motion of image brightness patterns between
frames.
  Methods:

o Correspondence of Interest Points:

 Identify key points (e.g., using SIFT or SURF).

 Track these points across frames to compute motion vectors.

o Differential Methods:

 Estimate flow by solving the optical flow equation:

Ixu+Iyv+It=0I_x u + I_y v + I_t = 0,
where IxI_x, IyI_y, and ItI_t are spatial and temporal intensity derivatives,
and uu, vv are motion components.

6. Kalman Filters

 Definition: A recursive estimation algorithm that predicts and updates the state of a system
over time, based on noisy measurements.

 Use in Motion Analysis:

o Predict the trajectory of objects.

o Smooth noisy motion data.

o Combine measurements from multiple sources.

 Steps:

1. Prediction: Estimate the next state using a motion model.

2. Update: Refine the prediction using observed data.

 Advantages: Efficient and robust to noise.

 Applications: Object tracking, autonomous navigation.

Applications of Motion Analysis

 Video surveillance and anomaly detection

 Traffic monitoring

 Human activity recognition

 Autonomous vehicles

 Animation and special effects

This unit equips learners with the foundational methods to analyze and understand motion in
dynamic scenes, critical for advancements in computer vision and related domains.
Dynamic Scene Analysis

Dynamic Scene Analysis is the process of analyzing and interpreting the motion and changes that
occur within a sequence of images or video frames. This is crucial in fields such as computer vision,
robotics, video surveillance, and autonomous driving, where understanding the movement of
objects and changes in the scene is necessary for decision-making or interaction with the
environment.

Dynamic scene analysis involves detecting, tracking, and predicting the motion of objects,
recognizing activities, and understanding temporal changes.

Key Concepts in Dynamic Scene Analysis

1. Motion Detection and Estimation:

o Objective: Identify moving objects or regions within a video or image sequence.

o Techniques:

 Background Subtraction: Compare each frame to a background model to

detect moving objects.

 Optical Flow: Measure the apparent motion of objects between two

consecutive frames based on the change in pixel intensity.

2. Object Tracking:

o Objective: Follow the movement of specific objects over time across multiple
frames.

o Techniques:

 Point-based Tracking: Track feature points (e.g., corners, edges) that remain
distinct across frames.

 Region-based Tracking: Track entire regions or objects by comparing image

patches or using contour-based methods.

 Kalman Filter: Predict the state of moving objects and correct tracking
estimates in the presence of noise.

3. Trajectory Detection:

o Objective: Identify the path or trajectory followed by an object over time.

o Methods:

 Feature Matching: Track distinct features and compute the trajectory by

matching them across frames.

 Optical Flow-based Trajectory: Use the flow vectors (from optical flow) to
predict the movement trajectory.

4. Motion Segmentation:
 o Objective: Group pixels or regions that exhibit similar motion behavior, often used
for segmenting moving objects from the background.

o Techniques:

 Clustering-based: Grouping pixels based on their motion vectors.

 Optical Flow Segmentation: Use optical flow to partition regions with similar
movement patterns.

5. Scene Flow:

o Definition: Scene flow refers to the 3D motion of points in the environment,

representing the motion of objects in three-dimensional space over time.

o Calculation: It can be computed using stereo vision or depth information combined

with optical flow.

Challenges in Dynamic Scene Analysis

1. Occlusions:

o When objects move in front of each other, the visibility of one object is blocked by
another, making motion tracking difficult.

2. Noise and Artifacts:

o Dynamic scenes often contain noise (due to lighting variations, sensor errors, or
compression artifacts), which can affect the accuracy of motion analysis.

3. Fast Motion:

o High-speed objects can be challenging to track due to motion blur and rapid changes
in position between frames.

4. Complex Motion Patterns:

o Real-world motion can be highly complex, with non-linear movements, rotations,

and interactions between multiple objects, which makes it difficult to separate
individual object movements.

5. Scale Variations:

o Objects may appear smaller or larger in different frames due to distance changes or
camera zooming, complicating tracking.

Methods in Dynamic Scene Analysis

1. Differential Methods (Optical Flow)

o Principle: Optical flow methods estimate the motion of pixels based on intensity
gradients over time. By solving the optical flow equation, motion vectors for each
pixel can be computed. Ixu+Iyv+It=0I_x u + I_y v + I_t = 0
  Ix,IyI_x, I_y are spatial image gradients,

 ItI_t is the temporal gradient (change over time),

 u,vu, v are the motion components in the x and y directions.

o Common Techniques:

 Horn-Schunck Method

 Lucas-Kanade Method

2. Block Matching (for Motion Estimation)

o Divide the image into blocks and use a search algorithm (e.g., sequential,
hierarchical search) to estimate the displacement of each block between frames.

3. Kalman Filtering for Object Tracking

o A recursive algorithm that combines predictions with noisy measurements to

estimate the state (position, velocity) of moving objects.

4. Feature-based Motion Detection

o Interest Points: Points such as corners or blobs are identified and tracked through
frames. These points serve as distinctive features for tracking object motion.

o Methods: Harris corner detector, SIFT, or SURF.

5. Model-based Tracking

o Use a model of the object (e.g., shape, size, appearance) to track its movement over
time. Methods like active contours (snakes) and particle filters are often used in this
case.

Applications of Dynamic Scene Analysis

1. Autonomous Vehicles:

o Understanding and predicting the motion of surrounding objects (pedestrians,

vehicles) to navigate safely.

2. Surveillance Systems:

o Detecting unusual or suspicious activity in video feeds by analyzing motion patterns

in real time.

3. Robotics:

o Mobile robots rely on dynamic scene analysis for navigation, obstacle avoidance,
and interaction with dynamic environments.

4. Human-Computer Interaction:

o Gesture recognition and motion capture for controlling devices or virtual

environments.
 5. Sports Analytics:

o Tracking athletes' movements and actions in games to analyze performance.

Tools and Techniques for Dynamic Scene Analysis

 OpenCV: A popular computer vision library that provides tools for motion detection, optical
flow, and tracking.

 TensorFlow and PyTorch: Deep learning frameworks that can be used for training models to
detect and track moving objects.

 MATLAB: Provides built-in functions for video processing, object detection, and tracking.

Conclusion

Dynamic scene analysis plays a crucial role in understanding and interpreting motion in real-world
environments. It encompasses a variety of techniques, from basic optical flow analysis to more
advanced tracking and trajectory detection methods, providing the foundation for applications in
autonomous systems, surveillance, and interactive technologies. Understanding the challenges and
methods in this field is key to developing effective motion analysis solutions.

Estimating Motion Vectors Using Sequential Search Algorithm

The Sequential Search Algorithm is one of the simplest methods used to estimate motion vectors in
video frames. Motion vectors represent the displacement of a pixel or a block of pixels from one
frame to the next. Estimating these motion vectors is an essential step in many motion analysis
tasks, such as object tracking, video compression, and optical flow estimation.

The sequential search method estimates motion by searching for the best matching block in the next
frame for a given block in the current frame. This is done by comparing pixel intensities in both
frames and selecting the block that minimizes the difference.

Steps Involved in Sequential Search Algorithm

1. Divide the image into blocks:

o Divide both the current and next frames into smaller blocks (e.g., 8x8 or 16x16
pixels). Each block in the current frame is compared to a corresponding block in the
next frame.

2. Define the search window:

o Choose a search window in the next frame around the block of interest. The size of
the search window determines how far from the original block you are willing to
search for the best match.

3. Compute similarity measure:

 o For each possible location within the search window, compute a similarity measure
between the current block and the candidate block in the next frame.

o A common similarity measure is Sum of Absolute Differences (SAD) or Mean

Squared Error (MSE):

 SAD: SAD=i,j∑∣I1(i,j)−I2(i,j)∣ where I1(i,j)I_1(i,j) and I2(i,j)I_2(i,j) represent

pixel values in the current and next frame, respectively, and the summation
is over all pixels in the block.

 MSE: MSE=1N∑i,j(I1(i,j)−I2(i,j))2\text{MSE} = \frac{1}{N} \sum_{i,j} (I_1(i,j) -

I_2(i,j))^2 where NN is the number of pixels in the block.

4. Find the best match:

o Search through all candidate positions in the search window to find the one with the
smallest difference (i.e., minimum SAD or MSE value).

5. Compute the motion vector:

o The displacement between the block in the current frame and the best-matching
block in the next frame is the motion vector.

o The motion vector is represented as (dx,dy)(dx, dy), where:

 dxdx is the horizontal displacement (difference in x-coordinates),

 dydy is the vertical displacement (difference in y-coordinates).

Example of Sequential Search

Assume you have a block from frame 1 (current frame) and want to find the best match in frame 2
(next frame) within a search window.

1. Block from Frame 1:

o Consider a block B1B_1 of size 8x8 in the current frame.

2. Search Window in Frame 2:

o Define a search window around the corresponding position of B1B_1 in frame 2 (for
example, a 16x16 region).

3. Compute SAD or MSE:

o For each possible position in the search window, calculate the SAD or MSE between
B1B_1 and the candidate blocks in frame 2.

4. Find the Minimum SAD/MSE:

o After calculating the similarity for all candidate blocks, select the one with the
smallest SAD or MSE value.

5. Motion Vector:
 o The displacement between the center of B1B_1 and the best match in frame 2 is the
motion vector for that block.

Advantages of Sequential Search Algorithm

 Simplicity: It is easy to implement and understand.

 Accuracy for small motions: When motion between consecutive frames is small, this
method works well and provides accurate motion vector estimates.

Disadvantages of Sequential Search Algorithm

 Computationally expensive: It requires searching through all candidate blocks in the search
window, which can be slow, especially for larger windows or high-resolution images.

 Not efficient for large motions: If there is a large displacement between consecutive frames,
the search window might not be large enough to capture the motion, and this algorithm may
miss the correct match.

 Sensitive to noise and illumination changes: Variations in lighting or noise can lead to
incorrect matches, as the similarity measure is based on pixel intensities.

Improvements and Alternatives

To improve the efficiency and accuracy of motion vector estimation, alternative methods and
optimizations can be used:

 Logarithmic Search Algorithm: Reduces the search space by using a logarithmic approach to
find the best match.

 Hierarchical Search: Performs motion estimation at multiple image resolutions, refining the
estimate at higher resolutions.

 Block Matching with Subpixel Accuracy: Uses interpolation techniques to improve the
precision of motion vector estimation.

Applications

 Video Compression: Used in compression algorithms like MPEG, H.264, where motion
vectors help reduce the amount of data needed to represent moving objects.

 Object Tracking: In robotics and surveillance, sequential search can be used to track objects
in a video sequence.

 Optical Flow Estimation: Helps estimate the flow of pixels between consecutive frames for
various applications, such as 3D reconstruction and scene understanding.
Logarithmic Search Algorithm for Motion Estimation

The Logarithmic Search Algorithm is a more efficient method for estimating motion vectors in video
frames compared to the brute-force Sequential Search Algorithm. It is designed to reduce the
computational complexity of searching for the best match in a given search window. By using a
logarithmic approach to narrow down the search space, the algorithm speeds up the motion
estimation process while maintaining accuracy.

How Logarithmic Search Algorithm Works

The key idea behind the logarithmic search algorithm is to reduce the size of the search window
progressively. Instead of examining every possible block in the search window (as in sequential
search), it looks for a good match by searching in smaller intervals, halving the search space with
each step. This results in fewer computations and faster execution.

Steps Involved in the Logarithmic Search Algorithm

1. Define the Search Window:

o Like the sequential search, the search window in the next frame is defined around
the initial block of interest in the current frame. This window has a predefined size,
typically much larger than the block itself.

2. Choose the Center of the Search Window:

o Start by considering the center of the search window as the initial candidate for the
best match.

3. Halve the Search Window:

o In the first step of the logarithmic search, the algorithm divides the search window
into four regions: top, bottom, left, and right.

o It checks the match in the center and compares the similarity measure (e.g., SAD or
MSE) between the current block and the candidate blocks in the search window.

4. Refine the Search:

o Based on the similarity measure, the algorithm selects the region with the best
match (the one that minimizes the difference between the current block and
candidate blocks). It then proceeds by narrowing the search space further into
smaller regions (again halving the search space).

o This process continues iteratively, progressively refining the location of the best
match.

5. Convergence:

o The algorithm continues to halve the search window until it converges to the point
where no further reduction in search space is possible, or the difference between
the current and previous match is sufficiently small.
 6. Determine the Motion Vector:

o Once the best match is found, the displacement (or motion vector) is calculated as
the difference in the position between the initial block in the current frame and the
best-matching block in the next frame.

Example of Logarithmic Search Algorithm

Let's say you have a block B1B_1 in frame 1, and you want to find the best match for it in frame 2
using a search window of size 16x16 pixels.

1. Initial Search Window:

o Start with a 16x16 search window around the corresponding location in frame 2.

2. Divide the Window:

o Divide the search window into 4 quadrants (top, bottom, left, right) and evaluate the
similarity (SAD or MSE) for each region.

3. Select the Best Region:

o Find the region with the lowest SAD/MSE value. Suppose it’s the top-left quadrant.

4. Narrow Down the Search:

o Now focus on this top-left quadrant, and divide it again into smaller regions.

5. Repeat the Process:

o Repeat this process of halving the search space and refining the match until the
algorithm converges on the best matching block.

6. Motion Vector:

o The displacement between the initial block and the best-matching block gives the
motion vector, indicating how far the block has moved from one frame to the next.

Advantages of Logarithmic Search Algorithm

1. Faster Than Sequential Search:

o By halving the search window progressively, the logarithmic search reduces the
number of candidate blocks to check, leading to faster computation.

2. Improved Efficiency:

o Unlike the sequential search, which checks every possible candidate block in the
search window, the logarithmic search narrows down the candidates efficiently,
reducing the computational cost.

3. Better for Large Motions:

 o The logarithmic search can handle larger motions better than sequential search
because it reduces the search space dynamically, making it more effective when the
displacement is substantial.

Disadvantages of Logarithmic Search Algorithm

1. May Not Always Find the Global Minimum:

o Since the search space is reduced progressively, the algorithm might miss the global
minimum if the optimal match lies outside the reduced search region.

2. Requires a Good Initial Estimate:

o The efficiency of the algorithm depends on starting with an approximate initial

position. If the initial estimate is far off, the algorithm may take longer to converge
or may not converge to the best solution.

3. Still Computationally Expensive for Large Search Windows:

o While the logarithmic search is faster than sequential search, it still requires
checking multiple regions within the search window, which can be computationally
expensive for large images or high-resolution video.

Applications of Logarithmic Search Algorithm

 Video Compression: In video compression algorithms (like H.264 or MPEG), motion vectors
are used to describe how objects in the video move from one frame to another. The
logarithmic search helps efficiently estimate these motion vectors, reducing the amount of
data needed for encoding.

 Optical Flow Estimation: The logarithmic search can be used in optical flow-based methods
to estimate the motion of each pixel in the image sequence by finding the best match in
consecutive frames.

 Object Tracking: The algorithm is used to track objects over time by estimating the motion
vectors for regions of interest, providing real-time tracking in video surveillance or
autonomous systems.

Comparison: Logarithmic Search vs. Sequential Search

Feature Sequential Search Logarithmic Search

Reduces the search space

Search Space Checks all positions in the search window.
progressively.

Speed Slow for large windows. Faster due to halving the search space.

Can be accurate but computationally Can miss the global minimum but
Accuracy
expensive. faster.
Feature Sequential Search Logarithmic Search

Complexity O(N^2) for a search window of size N×N O(log N) for halving the search space.

Hierarchical Search Algorithm for Motion Estimation

The Hierarchical Search Algorithm (also known as the Pyramid Search or Multi-Resolution Search)
is a technique used in motion estimation that reduces computational complexity while improving
accuracy. It is particularly effective for large displacements and high-resolution images or videos. The
basic idea is to estimate motion at multiple image resolutions, progressively refining the motion
estimate from coarse to fine levels.

How Hierarchical Search Algorithm Works

The Hierarchical Search approach builds an image pyramid, which consists of multiple versions of
the image at different resolutions. The algorithm performs motion estimation starting from the
coarsest (lowest resolution) level and progressively moves to higher (finer) resolutions, refining the
motion vectors at each level.

Steps Involved in the Hierarchical Search Algorithm:

1. Build the Image Pyramid:

o The first step is to create an image pyramid from the input video frames. The
pyramid is a set of images where each level contains a downsampled version of the
original image.

o The lowest level (Level 0) is the original high-resolution image.

o The subsequent levels are downsampled versions of the original, typically by a factor
of 2 (e.g., Level 1 is half the resolution of Level 0, Level 2 is a quarter, and so on).

2. Motion Estimation at Coarse Levels:

o Start with the lowest resolution (coarse level) of the pyramid. The motion estimation
is relatively simple here because the image is low-resolution, so fewer computations
are needed.

o At this level, estimate the motion vector by using techniques like block matching or
any other motion estimation method.

o This initial motion vector serves as a starting guess for the motion vectors at finer
resolutions.

3. Refining the Motion Vector at Higher Levels:

o After obtaining the motion vector at the coarse level, the algorithm moves to the
next higher resolution level (finer resolution).

o The initial motion vector from the coarse level is used as the starting point for
motion estimation at this higher resolution.
 o The motion estimation is then performed using a smaller search window, and the
motion vector is refined.

4. Repeat the Process:

o This process is repeated, moving from the lower-resolution levels to the higher-
resolution levels. At each higher resolution, the motion vectors are refined based on
the estimates from the lower levels.

o As the resolution increases, the precision of the motion vectors improves.

5. Final Motion Vector:

o At the highest resolution (finest level), the motion vector is refined to its final value.

o The final motion vector represents the best estimate of the motion between the two
frames.

Advantages of Hierarchical Search Algorithm

1. Handles Large Displacements:

o The hierarchical approach works well when there is large motion between
consecutive frames because the initial estimate is obtained at a coarse resolution,
which reduces the risk of missing the correct match due to large displacements.

2. Improved Accuracy:

o By starting with a rough estimate at lower resolutions and refining the motion vector
at higher resolutions, the hierarchical approach avoids problems like local minima,
which are common in traditional motion estimation techniques.

3. Efficiency in High-Resolution Images:

o The algorithm is efficient for high-resolution images or videos. Instead of searching

through a large search window at full resolution, the search space is reduced at each
lower resolution, making the overall process faster.

4. Robustness to Noise and Illumination Changes:

o The multi-resolution nature of the algorithm helps make it more robust to noise or
small illumination changes, as the estimation at each level is progressively refined
with increasing resolution.

Disadvantages of Hierarchical Search Algorithm

1. Computational Complexity of Pyramid Construction:

o Constructing the image pyramid involves downsampling the image multiple times,
which can be computationally expensive, especially for high-resolution video or
large sequences.

2. Multiple Passes Through the Image:

 o The hierarchical approach requires multiple passes through the image at different
resolutions, which can increase the overall computational time, especially for large-
scale images.

3. Memory Usage:

o Storing the pyramid and working with multiple image versions increases the memory
requirements, which can be a constraint on resource-limited devices.

4. Not Ideal for Small Motions:

o While hierarchical search works well for large motions, it can be less efficient for
cases where the motion between consecutive frames is small. In such cases, simpler
motion estimation methods like block matching or the logarithmic search might be
more efficient.

Example of Hierarchical Search Algorithm in Action

1. Original Frame (High Resolution):

o Suppose you have two consecutive frames in a video. The first step is to build an
image pyramid for both frames.

2. Level 0 (Coarse Resolution):

o At the lowest resolution, estimate the motion vector between the two frames. This
is done using a simple motion estimation technique (e.g., block matching).

o This initial estimate will be rough but should capture the general motion.

3. Level 1 (Medium Resolution):

o Use the estimated motion vector from Level 0 as the starting guess and perform
motion estimation at this higher resolution (a more detailed version of the frames).

o The motion vector is refined based on this level.

4. Level 2 (Fine Resolution):

o Move to the highest resolution in the pyramid. The motion vector is further refined
based on the previous estimates.

5. Final Motion Vector:

o The final motion vector is obtained after refining at each resolution level,
representing the precise displacement of objects in the frame.

Applications of Hierarchical Search Algorithm

 Video Compression: Used in video compression algorithms like MPEG, H.264, and HEVC,
where motion vectors are needed to represent how blocks of pixels move between frames.
Hierarchical search improves the efficiency of motion estimation, reducing the amount of
data needed for encoding.
  Object Tracking: In applications like surveillance or robotics, hierarchical search can be used
to track objects over time, especially when they move across the scene in significant ways.

 Optical Flow Estimation: Used in computer vision for estimating the flow of pixels between
two frames. Hierarchical search allows for more accurate and efficient optical flow
estimation in complex scenes.

 3D Reconstruction: Hierarchical search is often used in multi-view stereo systems to

estimate the depth of a scene by refining motion vectors across different levels of
resolution.

Here’s a comparison of Sequential Search, Logarithmic Search, and Hierarchical Search algorithms
in a table format:

Feature Sequential Search Logarithmic Search Hierarchical Search

Reduces search space Uses multiple image

Examines every
progressively by resolutions, starting with
Search Strategy candidate block in the
halving it in each low resolution and refining
search window.
iteration. at higher resolutions.

Reduces the search

Reduces the search
complexity by using
Search Space No reduction in search space logarithmically
progressively smaller
Reduction space. by dividing it into
search windows at higher
smaller regions.
resolutions.

Efficient for large motions

Faster than sequential and high-resolution images,
Slow, especially for large
Speed search due to reduced but slower than logarithmic
windows.
search space. search due to multiple
passes.

Can miss the global Very accurate, avoids local

High accuracy, but
minimum due to minima by refining
Accuracy computationally
narrowing down search estimates across
expensive.
space. resolutions.

More complex due to

High, O(N^2) for a Lower than sequential
Computational pyramid construction, but
search window of size search, O(log N) for
Complexity efficient for large images or
N×N halving search space.
significant motions.

Better than sequential

Excellent at handling large
Handling Large Less efficient for large search but still
displacements by starting
Motions displacements. struggles with large
from coarse estimates.
motions.

Memory Usage Low memory usage, only Low memory usage, Higher memory usage due
requires storing the works on the current to the image pyramid and
Feature Sequential Search Logarithmic Search Hierarchical Search

current frame and frame and search

multiple resolution levels.
search window. window.

Can be suitable for Suitable for high-resolution,

Not ideal for real-time
Suitable for Real-Time real-time processing large motion estimation but
processing due to high
Processing with small search may not be real-time due
computational cost.
windows. to pyramid construction.

Sensitive to noise and Can be more robust Robust to noise and

Robustness to
illumination changes than sequential search, illumination changes due to
Noise/Illumination
due to exhaustive but still sensitive to the multi-resolution
Changes
search. large differences. approach.

Video compression, object

Simple motion Video compression,
tracking, optical flow
estimation, video real-time object
Typical Applications estimation, 3D
analysis with small tracking with moderate
reconstruction in high-
motions. motions.
resolution scenarios.

Summary

 Sequential Search is straightforward but computationally expensive, suitable for small

motions but not ideal for large displacements or high-resolution videos.

 Logarithmic Search reduces the search space efficiently, making it faster than sequential
search, but may miss the global optimum in some cases.

 Hierarchical Search is particularly effective for large motions and high-resolution video,
using a coarse-to-fine strategy. It is more accurate and robust but requires more memory
and computation due to the pyramid construction.

Motion Analysis and Differential Motion Analysis Methods

Motion analysis is a crucial concept in computer vision and video processing, where the primary
objective is to detect, track, and analyze the movement of objects or regions between consecutive
frames of a video or image sequence. The idea is to extract motion information that can be useful
for various applications like object tracking, video compression, and scene understanding.

There are different methods for motion analysis, one of which is differential motion analysis, which
estimates the movement of pixels or objects by analyzing changes between frames.

1. Motion Analysis Overview

Motion analysis aims to identify the displacement of pixels or regions of interest between two
consecutive video frames. It is often performed by computing motion vectors—representing the
movement of blocks or points between the frames. The core idea is to detect motion by comparing
the intensity or color of pixels between frames, and the computed motion vectors are used to
understand object movements or scene changes.

Methods for Motion Analysis:

 Optical Flow:

o One of the most common motion analysis techniques.

o Optical flow estimates the motion of pixel intensities by calculating the changes in
pixel values between consecutive frames.

o It assumes that the intensity of a point in a scene does not change as it moves
between frames. This method works well for small motions and relatively static
scenes.

 Block Matching Algorithm (BMA):

o Divides the image into blocks and searches for the best matching block in the next
frame.

o The displacement of the matching block gives the motion vector.

 Feature-based Motion Estimation:

o Tracks specific features (like corners or edges) between frames.

o The motion of these features gives an indication of the overall motion in the scene.

 Global Motion Estimation:

o Estimating the motion of the entire image or a large part of it (e.g., rigid
transformations, homographies).

o Methods like RANSAC (Random Sample Consensus) are used to estimate the global
motion between frames.

2. Differential Motion Analysis Methods

Differential motion analysis focuses on estimating motion by computing the gradients of image
intensity functions over time. The main assumption is that motion can be approximated using the
differences (or gradients) between consecutive frames. This approach is based on the idea that
motion between frames causes changes in pixel intensity, which can be used to infer displacement.

Key differential motion analysis techniques include:

a. Optical Flow (Differential Method)

Optical flow is a classic differential method used to estimate the motion of objects in a video
sequence. It assumes that the motion of a point between two frames can be approximated by the
gradient of the intensity values in the image.

 Optical Flow Equation: The Optical Flow Equation is a differential equation that relates the
intensity of pixels in two frames to their motion. For a given point in the image, it assumes
that the change in intensity over time is due to the motion of the point.

Ixu+Iyv+It=0I_x u + I_y v + I_t = 0

Where:

o IxI_x and IyI_y are the spatial derivatives of the image intensity.

o uu and vv are the velocity components (motion vectors) in the x and y directions.

o ItI_t is the temporal derivative (change in intensity over time).

 Assumptions:

o Brightness Constancy: The intensity of a point does not change as it moves between
frames.

o Small Motion: The motion between consecutive frames is small, so the motion
vectors can be approximated using linear equations.

 Applications:

o Object tracking: Tracking the movement of specific features in a video.

o Scene analysis: Understanding the movement patterns within a scene.

o Optical Flow Algorithms: The most common algorithms to compute optical flow are
the Horn-Schunck method and Lucas-Kanade method.

b. Horn-Schunck Method (Global Optical Flow)

The Horn-Schunck method is one of the most widely used approaches for optical flow computation.
It aims to minimize an energy function that balances the consistency of the image's motion
(brightness constancy) and smoothness of the optical flow (spatial smoothness).

 Energy Function: E(u,v)=∫∫[(Ixu+Iyv+It)2+α2(Ix2+Iy2)(ux2+uy2+vx2+vy2)]dxdyE(u, v) = \int \

int \left[ (I_x u + I_y v + I_t)^2 + \alpha^2 (I_x^2 + I_y^2) (u_x^2 + u_y^2 + v_x^2 + v_y^2) \
right] dx dy Where:
 o uu and vv are the motion components in the x and y directions.

o Ix,Iy,ItI_x, I_y, I_t are the image gradients in the x, y, and t directions.

o α\alpha is the regularization parameter that controls the smoothness of the flow.

The method works by iteratively updating the motion fields and minimizing this energy function.

c. Lucas-Kanade Method (Local Optical Flow)

The Lucas-Kanade method is another widely used differential method for optical flow estimation. It
is a local method that computes the optical flow for small regions of the image using a set of
neighboring pixels.

 Assumption:

o The flow is constant within a small window of pixels.

 Basic Equation: The Lucas-Kanade method solves the optical flow equation in a local
neighborhood using the least squares method:

[IxIyItIy][uv]=−[ItIx]\begin{bmatrix} I_x & I_y \\ I_t & I_y \\ \end{bmatrix} \begin{bmatrix} u \\ v \

end{bmatrix} = - \begin{bmatrix} I_t \\ I_x \\ \end{bmatrix}

Where uu and vv are the horizontal and vertical components of the optical flow.

 Advantages:

o Efficient and works well for small displacements.

o Suitable for local flow estimation in high-texture areas of the image.

3. Differential Motion Analysis in Video Compression and Tracking

 Motion Estimation in Video Compression:

o Differential motion analysis plays a vital role in video compression techniques like
MPEG and H.264, where motion vectors are used to predict the difference between
consecutive frames. This helps reduce the amount of data required for encoding the
video.

 Tracking Objects in Video:

o Differential motion analysis is essential in tracking moving objects in a sequence of

video frames. Techniques such as optical flow and Kalman filtering use the estimated
motion vectors to predict and track the positions of objects over time.

 Scene Understanding:

o Differential methods can also be used in scene analysis to understand the structure
of dynamic scenes, helping to identify moving objects or detect changes in a video.
Summary of Differential Motion Analysis

Method Description Applications

Estimates motion by calculating the change in Object tracking, video

Optical Flow
pixel intensity between frames. compression, scene analysis.

Horn-Schunck A global optical flow method minimizing an Accurate motion estimation in

Method energy function for motion estimation. uniform motion scenes.

Lucas-Kanade A local optical flow method that estimates motion Suitable for tracking small
Method in small regions based on intensity gradients. features and high-texture areas.

Conclusion

Differential motion analysis methods, especially optical flow, are fundamental techniques for motion
estimation in computer vision. These methods compute motion vectors by analyzing intensity
gradients and temporal changes between frames. Techniques like Horn-Schunck and Lucas-Kanade
offer different approaches—global vs. local—each with its strengths and weaknesses, depending on
the motion scale and the scene dynamics. These methods are widely used in applications such as
object tracking, video compression, and scene understanding.

Trajectory Detection in Motion Analysis

Trajectory detection refers to the process of identifying and tracking the path or movement of
objects or points of interest over time in a video or image sequence. It involves computing and
analyzing the trajectory, which is typically represented as a series of position estimates at different
time points. This is important for understanding object behavior, tracking moving objects, or
identifying patterns in dynamic scenes.

Key Concepts in Trajectory Detection

1. Trajectory: A trajectory is the path that a moving object follows through space over time. In
video analysis, the trajectory is usually represented by a sequence of positions of an object
(or point) in consecutive frames.

2. Tracking: Trajectory detection typically starts with tracking, where the position of an object
is identified in the first frame and its movement is followed across subsequent frames.
Tracking methods can be point-based (tracking specific features or points) or region-based
(tracking larger areas or objects).

3. Object Detection: Before trajectory detection, object detection must often be performed to
locate objects of interest. This can be done using various computer vision techniques, such
as background subtraction, optical flow, or machine learning-based methods like YOLO (You
Only Look Once).
 4. Motion Models: In trajectory detection, motion models are used to predict the future
positions of an object. These models can range from simple linear motion models (constant
speed or direction) to more complex models involving acceleration or rotation.

Methods for Trajectory Detection

1. Optical Flow-based Trajectory Detection

 Optical flow can be used to estimate the displacement of points or regions between
consecutive frames. By integrating the optical flow vectors over time, trajectories can be
estimated.

 Steps:

o Detect feature points or regions (using methods like corner detection).

o Compute optical flow between consecutive frames to estimate motion.

o Accumulate the motion information to form trajectories.

 Challenges: Works well for small, slow-moving objects and requires well-defined feature
points.

2. Kalman Filter for Trajectory Estimation

 The Kalman filter is a widely used statistical method for estimating the trajectory of an
object based on noisy observations. It predicts the position and velocity of an object based
on the previous state and measurements, updating the trajectory as new data comes in.

 Steps:

o Initial state estimation (position and velocity).

o Prediction of future state using a motion model.

o Correction of prediction with new measurements (e.g., detected positions).

 Applications: Used for tracking moving objects in noisy environments, such as vehicles in
traffic or people in surveillance videos.

 Challenges: Works best when the object's motion is approximately linear and when noise is
Gaussian.

3. Feature-based Tracking

 Feature-based tracking involves detecting and tracking specific features (e.g., corners,
edges, or blobs) in consecutive frames. These features can be tracked across frames using
algorithms like Lucas-Kanade optical flow, or SIFT (Scale-Invariant Feature Transform) and
SURF (Speeded-Up Robust Features) for robust feature tracking.

 Steps:

o Detect interest points (features) in the first frame.

o Track these features in subsequent frames based on their local image context.
 o The trajectory is formed by linking the tracked points over time.

 Challenges: Feature matching can be difficult when objects move fast, are occluded, or
undergo drastic changes in appearance.

4. Mean-Shift Tracking

 Mean-shift tracking is a non-parametric iterative algorithm that locates the maximum of a

probability distribution, such as the color histogram or texture of the object being tracked.

 Steps:

o Select an object region in the initial frame.

o Track the region's motion in subsequent frames by computing the color histogram or
other features.

o Move the region iteratively to the new location by maximizing the similarity
between the object's features and the current frame.

 Applications: Effective for tracking moving objects with consistent appearance, such as a
person’s face or a vehicle.

 Challenges: Sensitive to object appearance changes, occlusions, or background clutter.

5. Deep Learning-based Trajectory Detection

 Deep learning methods, such as convolutional neural networks (CNNs) and recurrent
neural networks (RNNs), are increasingly used for trajectory detection. These methods can
learn complex features and motion patterns directly from the data.

 Steps:

o Use CNNs for detecting and tracking objects or features.

o Use RNNs (e.g., LSTMs) to model the temporal sequence of object movements.

o The network is trained to predict the trajectory of objects over time.

 Applications: Object tracking in complex scenarios, autonomous driving, and surveillance.

 Challenges: Requires large amounts of labeled data for training, computationally expensive.

6. Multiple Hypothesis Tracking (MHT)

 Multiple Hypothesis Tracking is used when multiple objects are moving in the scene, and
the system has to track the trajectories of each object. It involves generating multiple
hypotheses for the trajectory of each object and maintaining a set of potential trajectories.

 Steps:

o Track the movement of all potential objects by associating detected positions with
existing trajectories.

o Update the trajectories based on the most likely hypothesis.

o Handle occlusions and object interactions.

  Applications: Used in multi-object tracking, such as tracking multiple pedestrians in
surveillance videos.

 Challenges: Complex to implement, especially in scenes with many occlusions or interactions

between objects.

Applications of Trajectory Detection

1. Video Surveillance:

o Security and monitoring: Detecting and tracking the movement of individuals or

vehicles within a surveillance system. Trajectories help identify suspicious behavior
or potential threats.

2. Autonomous Vehicles:

o Path planning and collision avoidance: Autonomous vehicles track other vehicles,
pedestrians, or obstacles in their environment to plan safe paths and avoid
collisions.

3. Sports Analytics:

o Player and ball tracking: Analyzing players’ movements, ball trajectories, and game
dynamics in sports like soccer, basketball, or tennis.

4. Human-Computer Interaction (HCI):

o Gesture recognition: Detecting the motion of human limbs or hands to interpret

gestures or control interfaces.

5. Robotics:

o Path following: Robots track the movement of objects or their own position within
an environment for navigation tasks.

Challenges in Trajectory Detection

1. Occlusion: When objects are blocked by other objects, their trajectories can be lost
temporarily. Handling occlusions in real-time is a significant challenge.

2. Noise: Measurement noise (due to camera movement, environmental factors, or object

appearance changes) can make it difficult to accurately track and predict trajectories.

3. Non-rigid Motion: If the object changes shape or deformation occurs (e.g., human body
parts in motion), trajectory estimation can be more complex.

4. Multiple Objects: In scenes with many objects, managing multiple trajectories and ensuring
accurate tracking across frames becomes challenging.
Summary of Trajectory Detection Methods

Method Description Applications Challenges

Tracks pixel movements by Object tracking, Limited to small motions,

Optical Flow
estimating optical flow. scene analysis. sensitive to noise.

Predicts object positions

Vehicle tracking, Assumes linear motion, not
Kalman Filter using a dynamic model and
robot navigation. ideal for non-rigid motion.
noisy observations.

Feature-based Tracks specific features Face tracking, object Sensitive to occlusion and
Tracking across frames. tracking. feature matching.

Tracks regions by maximizing Object tracking with

Mean-Shift Sensitive to appearance
similarity between consistent
Tracking changes and occlusion.
histograms. appearance.

Uses CNNs and RNNs for

Deep Learning- Complex tracking Requires large data sets and
learning and predicting
based Detection scenarios. computational power.
trajectories.

Multiple Maintains multiple Computationally expensive,

Multi-object tracking
Hypothesis hypotheses for object challenging in complex
in crowded scenes.
Tracking trajectories. environments.

Optical Flow Analysis Based on Correspondence of Interest Points

Optical flow analysis is a technique used in computer vision to estimate the motion of objects
between consecutive frames of a video or image sequence. Optical flow measures the apparent
velocity of objects or features within an image based on the change in pixel intensities over time.
This method is particularly useful for motion estimation, object tracking, and understanding the
dynamics of a scene.

When combined with correspondence of interest points, optical flow analysis becomes more
effective at tracking specific features across frames. Interest points are distinctive locations in the
image that are easily recognizable and trackable, such as corners, edges, or blobs. By establishing the
correspondence of these points between consecutive frames, we can compute the motion (optical
flow) of the corresponding objects.

1. Overview of Optical Flow

Optical flow refers to the pattern of apparent motion of objects in a visual scene caused by the
relative motion between the observer (camera) and the scene. It is a vector field that represents the
displacement of pixels or features from one frame to another.

The basic equation for optical flow is:

Ixu+Iyv+It=0I_x u + I_y v + I_t = 0

Where:

 IxI_x, IyI_y, and ItI_t are the image gradients in the xx, yy, and time (tt) directions.

 uu and vv are the optical flow components in the xx and yy directions.

This equation assumes that the motion is small and the intensity of a pixel remains constant across
frames, which is known as the brightness constancy assumption.

2. Interest Points in Optical Flow

Interest points (also called keypoints) are distinctive, repeatable locations in an image that can be
reliably tracked across multiple frames. These points typically correspond to areas with significant
texture or contrast, such as corners, edges, or blobs. Common methods for detecting interest points
include:

 Harris Corner Detector: Detects corners where there is a significant change in intensity in
multiple directions.

 SIFT (Scale-Invariant Feature Transform): Finds keypoints that are invariant to scaling,
rotation, and affine transformations.

 SURF (Speeded-Up Robust Features): A faster alternative to SIFT, used for detecting and
describing keypoints.

 FAST (Features from Accelerated Segment Test): Detects corners efficiently in real-time
applications.

Once interest points are detected, they serve as the basis for matching corresponding points
between consecutive frames.

3. Correspondence of Interest Points

The key idea of optical flow analysis based on interest points is to track how these keypoints move
between frames. Correspondence refers to the process of finding the matching interest points in
successive frames, which can then be used to compute motion vectors.

Steps Involved in Correspondence of Interest Points:

1. Detection of Interest Points:

o Detect interest points (keypoints) in the first frame using methods like Harris, SIFT,
or FAST.

2. Tracking Interest Points Across Frames:

o For each interest point in the current frame, search for the corresponding interest
point in the next frame. This is often done by matching the local image region
around the point (using techniques like SSD (Sum of Squared Differences) or NCC
(Normalized Cross-Correlation)).
 3. Estimating Optical Flow:

o Once the corresponding points are found, the displacement (motion vector) of each
interest point can be calculated. The optical flow vector represents the
displacement of the keypoint from one frame to the next.

4. Motion Vector Computation:

o For each interest point, the displacement in the x and y directions (uu and vv) is
computed. These vectors can be visualized as arrows showing the direction and
magnitude of motion.

4. Methods to Match Correspondence of Interest Points

There are several techniques used to find the correspondence of interest points in successive
frames:

a. Template Matching (Direct Matching)

 Template matching involves searching for a region in the next frame that is similar to the
patch around the interest point in the current frame.

 Process:

o For each interest point in the first frame, extract a small window or patch around it.

o Slide this patch across the second frame and calculate a similarity measure (e.g., SSD
or NCC) at each location.

o The location with the highest similarity is considered the correspondence of the
interest point.

 Advantages:

o Simple and effective for tracking small, well-defined patches.

 Challenges:

o Sensitive to large motion, occlusions, and changes in scale or rotation.

b. Optical Flow Estimation using Local Search

 Lucas-Kanade Method: A widely used method for estimating optical flow. This method
assumes that the optical flow is constant in a small local neighborhood around each interest
point.

o Process:

 For each interest point, compute the image gradients (IxI_x, IyI_y, and ItI_t).

 Use these gradients to estimate the flow components uu and vv by solving

the optical flow equation for each small neighborhood around the interest
point.

 Advantages:
 o Works well for small displacements and in scenarios where pixel intensities remain
relatively constant.

 Challenges:

o It assumes that the flow is constant within a small window, which may not hold for
larger motions or non-rigid deformations.

c. Feature-based Tracking (e.g., KLT Tracker)

 KLT (Kanade-Lucas-Tomasi) tracker is based on the Lucas-Kanade method and tracks

keypoints across frames.

o Process:

 Detect interest points in the initial frame.

 Track these points by matching them in subsequent frames using optical

flow estimation.

 Update their locations iteratively based on the flow.

 Advantages:

o Efficient and works well for tracking well-defined, stable keypoints.

 Challenges:

o Can fail if there is a significant motion, occlusion, or large changes in appearance.

d. Epipolar Geometry and Feature Matching

In scenarios where there is more camera movement, epipolar geometry can help in matching
corresponding points. The epipolar constraint defines a relationship between points in two images
based on the camera's motion, which can be used to refine the correspondence between interest
points.

 Process:

o Use the camera’s motion parameters (like rotation and translation) to define an
epipolar plane, which restricts the search for matching points to a line in the second
frame.

 Advantages:

o Improves the robustness of point matching in stereo vision or multi-view setups.

 Challenges:

o Requires accurate camera calibration and can be computationally expensive.

5. Applications of Optical Flow Based on Interest Point Correspondence

 Object Tracking: Track the movement of specific objects by following the trajectory of
interest points, such as people, vehicles, or animals.
  Motion Estimation: Estimate the motion of objects in video sequences, which is useful in
video compression (e.g., predicting the next frame), or in dynamic scene analysis.

 3D Reconstruction: When combined with stereo vision, optical flow analysis can help
reconstruct the 3D structure of a scene by tracking points across multiple views.

 Robot Navigation: In autonomous robots, interest points can be tracked to estimate the
robot’s motion in an environment, aiding in tasks like path planning and obstacle avoidance.

6. Challenges in Optical Flow Based on Interest Point Correspondence

1. Occlusion: If an object becomes occluded between frames, it becomes difficult to track the
correspondence of interest points accurately.

2. Large Motion: Optical flow techniques based on interest points can struggle with large
motions, especially if the object moves a large distance between frames.

3. Noise and Illumination Changes: Variations in lighting, noise, or changes in object

appearance can make it challenging to track points reliably.

4. Feature Matching Errors: Incorrect feature matching due to similar-looking regions or

repeated patterns in the image can lead to errors in the estimated motion vectors.