Edge Count Heuristic

1. Background Knowledge

Early computer vision often relied on simple, hand‑crafted measures instead of learned features. One of the most fundamental ideas is an edge: a location in the image where intensity (brightness) changes abruptly. Intuitively, edges correspond to object boundaries, texture changes, or illumination transitions. Many classic algorithms (like Canny, Sobel, etc.) are built around detecting such changes and then using them for higher‑level tasks like segmentation or recognition.

In a grayscale image, each pixel has a single intensity value (e.g., in $[0, 255]$). An edge can be approximated by checking how different a pixel is from its neighbors. If the absolute difference in intensity is large enough (above some threshold), we call that location an edge. The problem you’re given is an extremely simplified version of edge detection: instead of computing gradients or using filters, it just checks intensity differences with the four direct neighbors (up, down, left, right).

---

2. Algorithm/Approach

This task is a straightforward grid traversal + local comparison pattern:

• Traverse every pixel in the 2D image.
• For each pixel, compare its intensity to each of its existing 4‑neighbors (top, bottom, left, right).
• If any neighbor differs by more than a given threshold, mark the pixel as an edge pixel.
• Count how many pixels satisfy this condition.

You do not need advanced edge detectors; you just need careful iteration and boundary handling.

---

3. Step-by-Step Strategy

4. Understand inputs and outputs

• Input: a 2D array image[h][w] of grayscale values (ints) and an integer threshold.
• Output: a single integer: the number of edge pixels.

2. Set up neighbor directions

• The 4‑neighbors of (i, j) are:
• Up: (i-1, j)
• Down: (i+1, j)
• Left: (i, j-1)
• Right: (i, j+1)

3. Iterate over all pixels

count = 0
for i in range(h):
for j in range(w):
# decide if (i, j) is an edge pixel

4. For each pixel, check neighbors safely

• Only check a neighbor if it is inside the image bounds.
• Compute diff = abs(image[i][j] - image[ni][nj]).
• If diff > threshold for any neighbor, mark this pixel as edge.

Pseudocode:

is_edge = False
for each (di, dj) in [(1,0), (-1,0), (0,1), (0,-1)]:
ni, nj = i + di, j + dj
if 0 <= ni < h and 0 <= nj < w:
if abs(image[i][j] - image[ni][nj]) > threshold:
is_edge = True
break
if is_edge:
count += 1

5. Return the count

• After the loops finish, output count.

---

4. Common Pitfalls

• Boundary pixels:

• Do not access neighbors outside the image (e.g., i-1 when i = 0).

• Always check bounds before indexing.

• Threshold condition:

• Use the correct comparison: “exceeds a threshold” usually means > (not >=), unless the problem states otherwise.

• Double counting:

• You should count pixels, not neighbor pairs.

• Once a pixel is determined to be an edge (one neighbor passes the threshold), stop checking other neighbors for that pixel.

• Confusing “any neighbor” with “all neighbors”:

• The condition is satisfied if any of the 4 neighbors has a difference greater than the threshold.

---

5. Time & Space Complexity

• Let the image size be $h \times w$ and $n = h \cdot w$.
• For each pixel, you check at most 4 neighbors (constant work).

Time complexity:

• $O(n)$ (linear in the number of pixels).

Space complexity:

• $O(1)$ extra space (besides the input image and a few variables), since you only keep a count and temporary values.