Color-based tracking in Drone Programming - Time & Space Complexity

Time Complexity: Color-based tracking

O(n)

Understanding Time Complexity

When a drone tracks colors, it checks many pixels to find the right one.

We want to know how the time to find colors grows as the image size grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

for pixel in image_pixels:
    if pixel.color == target_color:
        drone.move_to(pixel.position)
        break

This code looks at each pixel in the image to find the first pixel matching the target color, then moves the drone there.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each pixel's color in the image.
• How many times: Up to once per pixel, until the target color is found.

How Execution Grows With Input

As the number of pixels grows, the drone may check more pixels to find the color.

Input Size (n)	Approx. Operations
10	Up to 10 color checks
100	Up to 100 color checks
1000	Up to 1000 color checks

Pattern observation: The number of checks grows roughly in direct proportion to the number of pixels.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the color grows linearly with the number of pixels in the image.

Common Mistake

[X] Wrong: "The drone checks only one pixel no matter the image size."

[OK] Correct: The drone may need to check many pixels before finding the target color, so time grows with image size.

Interview Connect

Understanding how checking pixels scales helps you explain how your code handles bigger images efficiently.

Self-Check

"What if the drone had to find all pixels of the target color instead of stopping at the first? How would the time complexity change?"

Practice

1. What is the main purpose of color-based tracking in drone programming?

easy

A. To make the drone follow an object by detecting its color

B. To control the drone's altitude using GPS

C. To improve the drone's battery life

D. To send commands to the drone via remote control

Solution

1. Step 1: Understand color-based tracking concept

   Color-based tracking means the drone uses color detection to follow an object.

2. Step 2: Identify the main goal

   The goal is to detect and follow an object by its color, not altitude or battery.

3. Final Answer:

   To make the drone follow an object by detecting its color -> Option A

4. Quick Check:

   Color-based tracking = follow object by color [OK]

Hint: Focus on color detection as the tracking method [OK]

Common Mistakes:

• Confusing color tracking with GPS control
• Thinking it manages battery or remote commands
• Mixing color tracking with altitude control

2. Which of the following code snippets correctly initializes a color filter for red in a drone's tracking system?

easy

A. red_filter = {'lower': (0, 255, 255), 'upper': (10, 100, 100)}

B. red_filter = {'lower': [100, 0, 0], 'upper': [255, 10, 10]}

C. red_filter = {'low': (0, 100, 100), 'high': (10, 255, 255)}

D. red_filter = {'lower': (0, 100, 100), 'upper': (10, 255, 255)}

Solution

1. Step 1: Check correct keys for filter dictionary

   The keys should be 'lower' and 'upper' to define color range.

2. Step 2: Verify value types and ranges

   Values must be tuples with HSV ranges; red_filter = {'lower': (0, 100, 100), 'upper': (10, 255, 255)} uses correct keys and tuples.

3. Final Answer:

   red_filter = {'lower': (0, 100, 100), 'upper': (10, 255, 255)} -> Option D

4. Quick Check:

   Correct keys and tuple values = red_filter = {'lower': (0, 100, 100), 'upper': (10, 255, 255)} [OK]

Hint: Look for 'lower' and 'upper' keys with tuple HSV values [OK]

Common Mistakes:

• Using wrong dictionary keys like 'low' or 'high'
• Using lists instead of tuples for HSV values
• Swapping lower and upper HSV ranges

3. Given the following code snippet for detecting a blue object, what will be printed if the detected object's center is at (150, 200)?

blue_filter = {'lower': (100, 150, 0), 'upper': (140, 255, 255)}
object_center = (150, 200)
if 100 <= object_center[0] <= 140:
    print('Blue object detected at', object_center)
else:
    print('No blue object detected')

medium

A. Blue object detected at (150, 200)

B. SyntaxError

C. No blue object detected

D. RuntimeError

Solution

1. Step 1: Check the condition on x-coordinate

   Condition checks if 100 <= 150 <= 140, which is false because 150 > 140.

2. Step 2: Determine which print executes

   Since condition is false, else block runs printing 'No blue object detected'.

3. Final Answer:

   No blue object detected -> Option C

4. Quick Check:

   150 not in 100-140 range = No detection [OK]

Hint: Check numeric range conditions carefully [OK]

Common Mistakes:

• Assuming 150 is within 100 to 140 range
• Confusing syntax errors with logic errors
• Ignoring else block output

4. The following code is intended to detect a green object and print its position, but it raises an error. What is the error and how to fix it?

green_filter = {'lower': (40, 50, 50), 'upper': (80, 255, 255)}
object_center = None
if green_filter['lower'][0] <= object_center[0] <= green_filter['upper'][0]:
    print('Green object at', object_center)
else:
    print('No green object detected')

medium

A. SyntaxError due to incorrect dictionary keys; fix keys to 'low' and 'high'

B. TypeError because object_center is None; fix by assigning a tuple to object_center

C. IndexError because green_filter keys are missing; add keys

D. No error; code runs correctly

Solution

1. Step 1: Identify the error cause

   object_center is None, so accessing object_center[0] causes TypeError.

2. Step 2: Fix the error

   Assign a tuple like (x, y) to object_center before using it in condition.

3. Final Answer:

   TypeError because object_center is None; fix by assigning a tuple to object_center -> Option B

4. Quick Check:

   None used as index causes TypeError [OK]

Hint: Check variable types before indexing [OK]

Common Mistakes:

• Ignoring NoneType indexing error
• Changing dictionary keys incorrectly
• Assuming code runs without error

5. You want the drone to follow a yellow object but only if its detected center's y-coordinate is above 100. Which code snippet correctly implements this condition using color-based tracking?

yellow_filter = {'lower': (20, 100, 100), 'upper': (30, 255, 255)}
object_center = (120, 150)

# Choose the correct condition to check

hard

A. if yellow_filter['lower'][0] <= object_center[0] <= yellow_filter['upper'][0] and object_center[1] > 100:
print('Following yellow object')

B. if yellow_filter['lower'][1] <= object_center[1] <= yellow_filter['upper'][1] and object_center[0] > 100:
print('Following yellow object')

C. if yellow_filter['lower'][0] <= object_center[1] <= yellow_filter['upper'][0] and object_center[0] > 100:
print('Following yellow object')

D. if yellow_filter['lower'][1] <= object_center[0] <= yellow_filter['upper'][1] and object_center[1] > 100:
print('Following yellow object')

Solution

1. Step 1: Understand HSV and coordinate roles

   yellow_filter keys 'lower' and 'upper' define hue range at index 0; object_center[0] is x, object_center[1] is y.

2. Step 2: Check condition for hue and y-coordinate

   Hue check uses object_center[0] between lower and upper hue; y-coordinate must be > 100.

3. Final Answer:

   if yellow_filter['lower'][0] <= object_center[0] <= yellow_filter['upper'][0] and object_center[1] > 100: print('Following yellow object') -> Option A

4. Quick Check:

   Hue range on x and y > 100 condition = if yellow_filter['lower'][0] <= object_center[0] <= yellow_filter['upper'][0] and object_center[1] > 100: print('Following yellow object') [OK]

Hint: Match hue with x, check y > 100 separately [OK]

Common Mistakes:

• Mixing x and y coordinates in conditions
• Using wrong indices for hue or saturation
• Checking y-coordinate against hue range