ArUco marker landing in Drone Programming - Time & Space Complexity

Time Complexity: ArUco marker landing

O(f * m)

Understanding Time Complexity

When programming a drone to land using ArUco markers, it is important to understand how the time needed to process images grows as the number of markers or image size increases.

We want to know how the drone's processing time changes when it looks for markers in each camera frame.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

for each frame in video_stream:
    detected_markers = detect_aruco_markers(frame)
    for marker in detected_markers:
        pose = estimate_pose(marker)
        adjust_drone_position(pose)
    if landing_condition_met():
        land_drone()
        break

This code processes each video frame to find ArUco markers, estimates their position, and adjusts the drone's position until it lands.

Identify Repeating Operations

• Primary operation: Looping through each video frame and then looping through each detected marker in that frame.
• How many times: The outer loop runs once per frame (depends on video length), and the inner loop runs once per detected marker in that frame.

How Execution Grows With Input

As the number of frames increases, the processing time grows linearly because each frame is checked once. Within each frame, if more markers appear, the time grows with the number of markers.

Input Size (n)	Approx. Operations
10 frames, 1 marker/frame	~10 marker checks
100 frames, 5 markers/frame	~500 marker checks
1000 frames, 10 markers/frame	~10,000 marker checks

Pattern observation: The total operations grow roughly with the number of frames times the number of markers per frame.

Final Time Complexity

Time Complexity: O(f * m)

This means the time grows proportionally to the number of frames (f) and the number of markers (m) detected in each frame.

Common Mistake

[X] Wrong: "The time to detect markers is constant no matter how many markers are in the frame."

[OK] Correct: Detecting markers involves checking parts of the image and processing each marker found, so more markers mean more work and more time.

Interview Connect

Understanding how processing time grows with input size helps you explain how your drone program will behave in real situations, showing you can think about efficiency and scalability.

Self-Check

"What if the drone processes only every other frame instead of every frame? How would the time complexity change?"

Practice

1. What is the main purpose of using an ArUco marker in drone landing?

easy

A. To help the drone locate a precise landing spot using camera vision

B. To increase the drone's flying speed

C. To improve the drone's battery life

D. To enable the drone to fly higher

Solution

1. Step 1: Understand ArUco marker function

   ArUco markers are visual tags that drones detect with cameras to find exact positions.

2. Step 2: Connect marker use to landing

   The drone uses the marker to center itself and land precisely where the marker is placed.

3. Final Answer:

   To help the drone locate a precise landing spot using camera vision -> Option A

4. Quick Check:

   ArUco marker = precise landing spot [OK]

Hint: ArUco markers guide landing, not speed or battery [OK]

Common Mistakes:

• Thinking ArUco markers affect speed
• Confusing marker use with battery improvement
• Assuming marker helps flying altitude

2. Which of the following is the correct Python syntax to detect an ArUco marker using OpenCV?

easy

A. corners, ids, rejected = cv2.aruco.detectMarkers(image, dictionary)

B. corners, ids = cv2.aruco.detectMarkers(image dictionary)

C. corners, ids, rejected = cv2.detectMarkers(image, dictionary)

D. corners, ids, rejected = cv2.aruco.detectMarker(image, dictionary)

Solution

1. Step 1: Recall OpenCV ArUco detection syntax

   The correct function is cv2.aruco.detectMarkers with parameters (image, dictionary).

2. Step 2: Check returned values

   It returns corners, ids, and rejected candidates, so three outputs are expected.

3. Final Answer:

   corners, ids, rejected = cv2.aruco.detectMarkers(image, dictionary) -> Option A

4. Quick Check:

   Correct function and outputs = corners, ids, rejected = cv2.aruco.detectMarkers(image, dictionary) [OK]

Hint: Remember detectMarkers returns three values with cv2.aruco [OK]

Common Mistakes:

• Missing comma between arguments
• Using wrong function name detectMarker
• Not unpacking all three return values

3. Given this code snippet for ArUco marker detection, what will be printed if no markers are found?

corners, ids, rejected = cv2.aruco.detectMarkers(frame, dictionary)
if ids is None:
    print("No markers detected")
else:
    print(f"Detected {len(ids)} markers")

medium

A. Detected 0 markers

B. No markers detected

C. Error: ids is undefined

D. Detected None markers

Solution

1. Step 1: Understand detectMarkers output when no markers found

   When no markers are detected, ids is None, not an empty list.

2. Step 2: Follow the if condition

   The code checks if ids is None, then prints "No markers detected".

3. Final Answer:

   No markers detected -> Option B

4. Quick Check:

   ids is None means no markers [OK]

Hint: ids is None means no markers, not empty list [OK]

Common Mistakes:

• Assuming ids is empty list when no markers
• Expecting length of None causes error
• Printing zero markers instead of message

4. This code snippet is intended to center the drone over the detected ArUco marker. What is the bug?

corners, ids, _ = cv2.aruco.detectMarkers(frame, dictionary)
if ids is not None:
    cX = int(corners[0][0][0][0])
    cY = int(corners[0][0][0][1])
    move_drone_to(cX, cY)
else:
    print("Marker not found")

medium

A. Using move_drone_to with wrong parameters

B. Missing check if corners is empty

C. Incorrect indexing of corners to get center point

D. No bug, code works correctly

Solution

1. Step 1: Analyze corners indexing

   corners[0][0] is a list of marker corner points; [0][0] accesses first corner point, not center.

2. Step 2: Identify correct center calculation

   Center should be average of all four corners, not just first point.

3. Final Answer:

   Incorrect indexing of corners to get center point -> Option C

4. Quick Check:

   Center = average corners, not first corner [OK]

Hint: Center is average of corners, not first corner point [OK]

Common Mistakes:

• Using first corner as center
• Not averaging corner points
• Ignoring possibility of empty corners

5. You want the drone to land on an ArUco marker by centering it and then descending. Which sequence of steps in code best achieves this?

hard

A. Detect marker -> Descend quickly -> Calculate center -> Move drone to center

B. Descend slowly -> Detect marker -> Move drone randomly -> Confirm landing

C. Move drone randomly -> Detect marker -> Descend quickly -> Confirm landing

D. Detect marker -> Calculate center -> Move drone to center -> Descend slowly -> Confirm landing

Solution

1. Step 1: Understand safe landing sequence

   First detect the marker and find its center to position the drone accurately.

2. Step 2: Move drone to center and descend carefully

   After centering, descend slowly to avoid missing the marker or crashing.

3. Final Answer:

   Detect marker -> Calculate center -> Move drone to center -> Descend slowly -> Confirm landing -> Option D

4. Quick Check:

   Correct landing sequence = Detect marker -> Calculate center -> Move drone to center -> Descend slowly -> Confirm landing [OK]

Hint: Center first, then descend slowly for safe landing [OK]

Common Mistakes:

• Descending before centering marker
• Moving drone randomly without marker detection
• Descending too fast risking crash