Image stitching for mapping in Drone Programming - Time & Space Complexity

Time Complexity: Image stitching for mapping

O(n²)

Understanding Time Complexity

When stitching images for mapping, the program compares many small parts of images to join them correctly.

We want to know how the time needed grows as we add more images to stitch.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

for i in range(len(images)):
    for j in range(i + 1, len(images)):
        match_points = find_matching_points(images[i], images[j])
        if match_points:
            stitched_image = stitch(images[i], images[j], match_points)
            images[i] = stitched_image
            images.pop(j)
            break

This code tries to stitch each image with every other image by finding matching points and combining them.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops comparing pairs of images.
• How many times: The outer loop runs once per image, the inner loop compares with remaining images.

How Execution Grows With Input

As the number of images grows, the number of comparisons grows quickly because each image is compared with many others.

Input Size (n)	Approx. Operations
10	About 45 comparisons
100	About 4,950 comparisons
1000	About 499,500 comparisons

Pattern observation: The number of comparisons grows roughly like the square of the number of images.

Final Time Complexity

Time Complexity: O(n²)

This means if you double the number of images, the work to stitch them grows about four times.

Common Mistake

[X] Wrong: "The stitching time grows just a little when adding more images because each image is processed once."

[OK] Correct: Each image is compared with many others, so the total comparisons increase much faster than the number of images.

Interview Connect

Understanding how the stitching time grows helps you explain how your code handles many images efficiently, a useful skill in real projects.

Self-Check

"What if we used a method to only compare images that are close in location? How would the time complexity change?"

Practice

1. What is the main purpose of image stitching in drone programming?

easy

A. To combine multiple drone photos into one large map

B. To control the drone's flight path

C. To improve the drone's battery life

D. To send live video feed to the operator

Solution

1. Step 1: Understand image stitching concept

   Image stitching is about joining many photos to create a bigger picture.

2. Step 2: Identify the main use in drone programming

   It helps create large maps from many drone images for better area coverage.

3. Final Answer:

   To combine multiple drone photos into one large map -> Option A

4. Quick Check:

   Image stitching = combine photos [OK]

Hint: Image stitching means joining photos into one big map [OK]

Common Mistakes:

• Confusing image stitching with drone control
• Thinking it improves battery life
• Mixing it with live video streaming

2. Which of the following is the correct way to start stitching images side by side in a drone program?

easy

A. stitch(images, method='side_by_side')

B. stitch(images, method='fly_path')

C. stitch(images, method='battery_save')

D. stitch(images, method='live_feed')

Solution

1. Step 1: Identify stitching method names

   Side by side stitching joins images horizontally or vertically.

2. Step 2: Match method to stitching task

   Only 'side_by_side' matches the stitching method; others relate to flight or battery.

3. Final Answer:

   stitch(images, method='side_by_side') -> Option A

4. Quick Check:

   Method 'side_by_side' = stitching images side by side [OK]

Hint: Use method='side_by_side' to join images simply [OK]

Common Mistakes:

• Using unrelated methods like 'fly_path' or 'battery_save'
• Confusing stitching method with drone flight commands
• Misspelling method names

3. Given the code snippet:

images = ['img1.jpg', 'img2.jpg', 'img3.jpg']
stitched_map = stitch(images, method='overlap')
print(len(stitched_map))

What will be the output if stitched_map is a combined image with 3 parts?

medium

A. 1

B. 3

C. 0

D. Error

Solution

1. Step 1: Understand the stitch function output

   Stitching combines images into one big image, so the result is a single image object.

2. Step 2: Check what len() returns on the stitched image

   Most image objects do not support len(), so calling len() will cause an error.

3. Final Answer:

   Error -> Option D

4. Quick Check:

   len() on image object causes error [OK]

Hint: len() on stitched image causes error [OK]

Common Mistakes:

• Assuming length equals number of input images
• Expecting len() to work on image object
• Confusing list length with image object length

4. The following code is meant to stitch images with overlap detection but throws an error:

images = ['a.jpg', 'b.jpg']
stitched = stitch(images, method='overlap')
stitched.show()

What is the likely cause of the error?

medium

A. The method 'overlap' is not supported

B. The show() method does not exist for stitched images

C. The stitch function requires images to be loaded, not file names

D. The images list is empty

Solution

1. Step 1: Check input type for stitch function

   Stitch usually needs image data, not just file names as strings.

2. Step 2: Identify error cause

   Passing file names without loading images causes errors when stitching or showing.

3. Final Answer:

   The stitch function requires images to be loaded, not file names -> Option C

4. Quick Check:

   Input must be loaded images, not file names [OK]

Hint: Load images before stitching, not just file names [OK]

Common Mistakes:

• Assuming method 'overlap' is invalid
• Thinking show() method is missing
• Ignoring that images list is not empty

5. You want to create a stitched map from drone images but only include images that have at least 30% overlap with the previous one. Which approach best applies this condition in your stitching code?

hard

A. Stitch all images first, then crop the map to overlapping areas

B. Filter images by overlap percentage before stitching using a function

C. Use method='side_by_side' to ignore overlap

D. Manually stitch images without any overlap checks

Solution

1. Step 1: Understand the overlap condition

   Only images with at least 30% overlap should be included in stitching.

2. Step 2: Choose the best way to apply this condition

   Filtering images before stitching ensures only suitable images are combined.

3. Final Answer:

   Filter images by overlap percentage before stitching using a function -> Option B

4. Quick Check:

   Filter first, then stitch = correct approach [OK]

Hint: Filter images by overlap before stitching [OK]

Common Mistakes:

• Stitching all images then cropping
• Ignoring overlap and stitching side by side
• Manual stitching without overlap checks