পাঠ ০৬ · ৩৫-এর মধ্যে · মডিউল ১

Home / AI Courses / Computer Vision / Edge detection

Edge detection — Sobel ও Canny

Edge detection — Sobel and Canny algorithms

৭ মিনিট পড়া মাঝারি · Intermediate OpenCV কোডসহ

এই পাঠে যা শিখবেন

Image gradient — partial derivative
Sobel ও Prewitt operator
Canny edge detector — চারটি step
OpenCV-তে edge detection

১ · Edge কী?

Edge = ছবিতে যেখানে intensity হঠাৎ বদলায়। বিড়ালের কালো শরীর ও সাদা background-এর সীমানা — সেটাই edge.

Mathematically — edge মানে gradientImage Gradientএকটি pixel-এ intensity কোন দিকে কত দ্রুত বদলাচ্ছে — partial derivative দ্বারা। Vector quantity — direction + magnitude.-এর high magnitude:

$$\nabla I = \left( \frac{\partial I}{\partial x}, \frac{\partial I}{\partial y} \right)$$

Discrete ছবিতে partial derivative = neighboring pixel-এর difference.

কেন্দ্রীয় ধারণা

Edge detection = প্রতিটি pixel-এ gradient বের করা → high magnitude pixel = edge. Different operator (Sobel, Prewitt, Roberts) — gradient compute করার ভিন্ন kernel.

২ · Sobel operator

Irwin Sobel (১৯৬৮) — দু'টি 3×3 kernel: $S_x$ ও $S_y$।

$$S_x = \begin{bmatrix} -1 & 0 & 1 \\ -2 & 0 & 2 \\ -1 & 0 & 1 \end{bmatrix}, \quad S_y = \begin{bmatrix} -1 & -2 & -1 \\ 0 & 0 & 0 \\ 1 & 2 & 1 \end{bmatrix}$$

$S_x$ — horizontal gradient (vertical edge highlight).
$S_y$ — vertical gradient (horizontal edge highlight).
মাঝের row/column-এ 2 — center pixel-এ extra weight (Gaussian-like smoothing).

Gradient magnitude:

$$|G| = \sqrt{G_x^2 + G_y^2} \approx |G_x| + |G_y|$$

Gradient direction:

$$\theta = \arctan\left( \frac{G_y}{G_x} \right)$$

৩ · Prewitt ও Roberts

Prewitt — Sobel-এর কাছাকাছি কিন্তু weight সমান (1, 1, 1). Sobel-এর smoothing-এর সুবিধা নেই — noise-prone.

Roberts cross — 2×2 — দ্রুত কিন্তু low accuracy. Historical interest.

Scharr — Sobel-এর rotation invariance improved version. OpenCV-তে available.

৪ · Canny — gold standard

John Canny (১৯৮৬) — তার MIT MS thesis-এ formal "optimal edge detector" বের করেন। চারটি step:

Gaussian blur: noise কমাতে — $\sigma = 1.4$ typical.
Sobel gradient: magnitude ও direction.
Non-maximum suppression: gradient-এর direction-এ neighbor পিছিয়ে — শুধু local maxima রাখা। Edge thin করে।
Double threshold + hysteresis:
- $T_{\text{high}}$-র উপরে = strong edge.
- $T_{\text{low}}$-র নিচে = discard.
- মাঝে = "weak" — strong edge-এর সাথে connected হলে keep, নয়তো discard.

Canny-র চারটি step — একজন কাঁচা painter-এর finishing touches. Blur = canvas মসৃণ, Sobel = pencil sketch, NMS = sharper line, hysteresis = noise বাদ দিয়ে continuous line draw. ১৯৮৬-র algorithm এখনো production-এ — কারণ আর better classical option নেই।

৫ · Optimal edge detector — Canny-র তিন criteria

Canny formally প্রমাণ করেন — যেকোনো edge detector-এর তিনটি criteria থাকতে হবে:

Good detection: low miss + low false positive.
Good localization: detected edge ও true edge-এর দূরত্ব minimum.
Single response: এক edge-এ multiple response না।

এই তিনের optimization থেকে — Gaussian-এর first derivative-এ পৌঁছান। Sobel approximation, NMS thinning, hysteresis robustness.

Canny pipeline — Gaussian-এ smoothing থেকে hysteresis-এ connected edge map. ১৯৮৬-র algorithm আজও gold standard.

৬ · OpenCV-তে Sobel

Python · OpenCV

import cv2
import numpy as np

# একটি synthetic বাক্স ছবি
img = np.zeros((100, 100), dtype=np.uint8)
img[30:70, 30:70] = 200

# Sobel — note: dtype CV_64F to capture negative gradients
gx = cv2.Sobel(img, cv2.CV_64F, dx=1, dy=0, ksize=3)
gy = cv2.Sobel(img, cv2.CV_64F, dx=0, dy=1, ksize=3)

# magnitude
mag = np.sqrt(gx**2 + gy**2)
mag = np.uint8(np.clip(mag, 0, 255))

print("Original min/max:", img.min(), img.max())
print("Gx range:", gx.min(), gx.max())
print("Mag max:", mag.max(), " (edge pixels)")
print("Edge pixel count:", np.count_nonzero(mag > 50))

CV_64F ব্যবহার — কারণ gradient negative হতে পারে। uint8 ব্যবহার করলে negative clip → wrong result. magnitude calculate-এর পরই abs/clip.

৭ · OpenCV-তে Canny

Python · OpenCV

import cv2
import numpy as np

# Synthetic ছবি — দুটি rectangle
img = np.zeros((150, 200), dtype=np.uint8)
img[20:60, 30:80] = 180
img[80:130, 100:170] = 120

# Canny — দু'টি threshold
edges_low  = cv2.Canny(img, 50, 100)    # বেশি sensitive
edges_high = cv2.Canny(img, 100, 200)   # কম sensitive

print("Low threshold edge pixels:", np.count_nonzero(edges_low))
print("High threshold edge pixels:", np.count_nonzero(edges_high))

# Auto threshold — median-based heuristic
v = np.median(img)
sigma = 0.33
lo = int(max(0, (1.0 - sigma) * v))
hi = int(min(255, (1.0 + sigma) * v))
auto = cv2.Canny(img, lo, hi)
print(f"Auto: lo={lo}, hi={hi}, edges={np.count_nonzero(auto)}")

Threshold pair tuning critical. Median-based auto-tuning common. 50/100, 100/200, ratio 1:2 বা 1:3.

৮ · কোথায় ব্যবহার

Document scanning: page boundary detect.
License plate: rectangular plate localize.
Lane detection: self-driving car-এর প্রথম step.
Medical: tumor boundary, vessel segmentation.
OCR preprocess: text contour finding.
Industrial inspection: defect/crack detection.
SLAM: feature point tracking.

Canny "deep learning" নয় কিন্তু আজও CV pipeline-এর backbone. GPU-এ realtime, deterministic, no training data — অনেক production-এ এটাই default.

ভাবনার প্রশ্ন

প্র ০১ Canny-তে দু'টি threshold (low ও high) কেন? একটি threshold পর্যাপ্ত নয় কেন?

এটি Canny-র সবচেয়ে clever idea. Single threshold-এর দু'টো বড় সমস্যা — দু'টি ভিন্ন direction থেকে।

Single high threshold-এর সমস্যা:

True edge-এর কিছু অংশ-এ gradient সামান্য কম হয় (lighting, surface curve).
সেগুলো discard হলে — edge "broken". একটি বিড়ালের contour ছেদ ছেদ।
Connected component, contour-finding ভাঙে।

Single low threshold-এর সমস্যা:

Noise-এর gradient পার হয়।
False edge সর্বত্র — output unusable.

Hysteresis-এর genius:

$T_{\text{high}}$: "এটি অবশ্যই edge" — confident detection.
$T_{\text{low}}$: "এটি edge হতে পারে" — candidate.
Connection rule: low candidate-কে শুধু তখনই keep — যদি সরাসরি বা chain-এ একটি high pixel-এর সাথে connected.

Visual:

Edge-এর strong center → high threshold pass.
Edge-এর তলায় সামান্য weak — low pass, connected to strong → keep.
Isolated noise — low pass হলেও কোনো high-এর সাথে connected না → discard.

Connectivity definition:

4-connectivity: শুধু up/down/left/right.
8-connectivity: diagonal-ও। Canny-তে 8 ব্যবহৃত — natural curve preserve.

Threshold ratio:

Canny-র recommendation: 1:2 to 1:3.
1:2 — aggressive (more edges).
1:3 — conservative (cleaner).
Image-specific tuning দরকার — auto Canny (median-based) common heuristic.

Implementation:

BFS/DFS — strong edge-এর neighbor check.
Recursive flood-fill — কিন্তু stack overflow risk.
OpenCV-এ optimized — pixel-by-pixel iterative.

মূল উপলব্ধি: Hysteresis = "context-aware" decision. Local pixel-এর gradient-এর বদলে neighborhood considering. এই idea — region growing, watershed, MRF — সব classical CV-তে।

প্র ০২ একটি video stream-এ Canny apply করলে frame-to-frame edge map অস্থির — flickering. কেন? সমাধান কী?

Edge detection temporal stability-এ পরিচিত weak. Production video processing-এ এটি বড় challenge.

কেন flickering?

Sensor noise: frame-by-frame photon shot noise pixel value-এ ±2-5 variation.
Threshold edge case: gradient ঠিক $T_{\text{low}}$-এর কাছে — কখনো pass, কখনো না।
Hysteresis dependency: connectivity পরিবর্তন → entire chain flip.
JPEG compression: video codec frame-ভেদে ভিন্নভাবে compress — block edges shifting.

সমাধান কৌশল:

Heavier pre-blur: $\sigma = 2-3$, kernel 7×7 বা 9×9 — noise কমায় কিন্তু edge localization কম।
Temporal smoothing: consecutive frames-এর edge map weighted average.
```
edge_smooth = 0.7 * edge_smooth + 0.3 * edge_current
```
Bilateral filter pre-process: edge preserve করে noise কমায়।
3D Canny: spatio-temporal — time-axis-এও Gaussian smoothing.
Adaptive threshold: frame-এর histogram-নির্ভর — auto tuning.
Optical flow guidance: previous frame-এর edge motion-compensate করে current-এ overlay. Edge consistent.

Modern alternative:

HED (Holistically-nested Edge Detection): 2015 — CNN-based, much more stable.
RCF (Richer Convolutional Features): multi-scale CNN edge.
BDCN, DexiNed: recent SOTA.

Trade-off:

DL edge detector — stable, accurate, কিন্তু GPU চাই।
Canny — CPU realtime, কিন্তু flicker-prone.
Mobile/edge — Canny + temporal smoothing pragmatic.

Industry example:

Self-driving lane detection: Canny + temporal Kalman filter.
Augmented reality: HED — stable for AR overlay.
Video editing: bilateral + Canny — Photoshop-like edge mask.

মূল উপলব্ধি: Single-frame algorithm video-তে naively apply — সর্বদা suboptimal. Temporal coherence একটি আলাদা design dimension.

প্র ০৩ Sobel kernel-এ মাঝের row/column-এ 2 — 1 না কেন? এই weighting-এর গাণিতিক justification?

এটি Sobel-কে Prewitt-এর চেয়ে সুপিরিয়র করেছে। ১৯৬৮-তে যেটি hand-tuning, পরে mathematical derivation.

Prewitt vs Sobel:

$$P_x = \begin{bmatrix} -1 & 0 & 1 \\ -1 & 0 & 1 \\ -1 & 0 & 1 \end{bmatrix}, \quad S_x = \begin{bmatrix} -1 & 0 & 1 \\ -2 & 0 & 2 \\ -1 & 0 & 1 \end{bmatrix}$$

Sobel-এর justification (১): Smoothing + differentiation.

$S_x$ = $[1, 2, 1]^T \otimes [-1, 0, 1]$ (outer product).
$[1, 2, 1]$ — Gaussian-like 1D smoothing.
$[-1, 0, 1]$ — central difference (derivative).
মানে — Sobel = Gaussian smooth + central difference combined.

Sobel-এর justification (২): Pascal triangle.

$[1, 2, 1]$ = binomial coefficient $\binom{2}{0}, \binom{2}{1}, \binom{2}{2}$।
Discrete approximation of Gaussian — central limit theorem-এর ভিত্তিতে।

Sobel-এর justification (৩): Optimal isotropy.

Scharr (২০০০) প্রমাণ করেন — 3×3 kernel-এ rotation-invariance maximize করার weight.
Scharr kernel: $[3, 10, 3] \otimes [-1, 0, 1]$ — Sobel-এর extension.
Sobel কে শক্তিশালী optimal-এর কাছাকাছি, Prewitt অনেক দূরে।

Practical comparison:

Noise robustness: Sobel > Prewitt (smoothing থাকায়)।
Localization: equal.
Rotation: Scharr > Sobel > Prewitt.
Speed: equal (separable kernel).

Why not 3 or 4?

$[1, 3, 1]$ — over-smoothing edge attenuate.
$[1, 4, 1]$ — center-heavy, neighbor contribution lost.
$[1, 2, 1]$ — sweet spot.

Higher-order alternatives:

5×5 Sobel: $[1, 4, 6, 4, 1]$ binomial — large blur, distant edge detect.
Derivative of Gaussian (DoG): continuous mathematical version.
Sobel-Feldman, Scharr — optimized variants.

মূল উপলব্ধি: Hand-tuned 1968 kernel — পরে mathematically optimal-এর সাথে coincide. Engineering intuition-এর শক্তি। Modern CNN একই pattern শেখে — convergent evolution.

প্র ০৪ Canny ৪০ বছরের পুরোনো। আজকের HED, RCF, EDTER — DL-based edge detector কি Canny-কে replaced করেছে? কোন domain-এ কোনটা?

এটি classical-vs-DL debate-এর microcosm. উত্তর — replacement না, complement.

Canny-র সীমাবদ্ধতা:

Single scale: fixed kernel — fine ও coarse edge দু'টোই capture করতে পারে না।
No semantic: "object boundary" বনাম "texture edge" আলাদা করতে পারে না।
Threshold sensitive: manual tuning per-image.
Texture noise: grass, fur — false edge.

HED (Holistically-nested Edge Detection, 2015):

VGG backbone — multi-scale edge prediction.
Each conv stage থেকে edge map.
Trained on BSDS500 — human-annotated boundaries.
Semantic — object boundary preferred over texture.

RCF (2017), BDCN (2019), EDTER (2022):

Better backbone, transformer-based.
BSDS500 ODS F1 score: Canny ~0.61, HED ~0.78, EDTER ~0.83.
Human ~0.80 — DL এখন human level.

কোন domain-এ Canny এখনো champion:

Industrial inspection: high-contrast metal surface — Canny accurate ও fast.
Document analysis: page boundary, table line — clean geometry.
Embedded/microcontroller: CNN অসম্ভব।
Medical (regulated): FDA-approved deterministic algorithm.
Real-time mobile: battery, latency.
Augmented reality marker tracking: latency-critical.

কোন domain-এ DL essential:

Natural image segmentation: semantic boundary দরকার।
Outdoor scene: grass, tree, sky — texture vs semantic.
Image editing tools: Adobe Sensei, Photoshop "object selection".
Autonomous driving: lane, sign, car — semantic awareness.

Hybrid pipelines:

Coarse DL edge → fine Canny refinement.
Canny ROI proposal → CNN classify.
HED training-এ Canny weak supervision.

Compute trade-off:

Canny: ~0.5 ms per 1MP frame on CPU.
HED: ~50 ms on GPU, ~500 ms on CPU.
EDTER: ~100 ms GPU.
1000x cost difference!

মূল উপলব্ধি: "Old vs new" বাইনারি ভাবা ভুল। Tool-এর spectrum বুঝে use case-এর সাথে match — সেটাই engineer-এর কাজ। Canny ও EDTER দু'টোই tool box-এ থাকা উচিত।

অনুশীলন

Sobel manual: $S_x$ apply 3×3 input $\begin{bmatrix} 0&50&100 \\ 0&50&100 \\ 0&50&100 \end{bmatrix}$ এর কেন্দ্র pixel-এ। হাতে হিসাব।

$G_x = (-1)(0) + 0 + (1)(100) + (-2)(0) + 0 + (2)(100) + (-1)(0) + 0 + (1)(100) = 100 + 200 + 100 = 400$।

(সাদা→কালো diagonal-এ strong horizontal gradient).
Canny tuning: একটি ছবিতে Canny apply — edge খুব dense বা খুব sparse হলে threshold কোন দিকে?
- Dense edge → both threshold বাড়ান (less sensitive).
- Sparse edge → both কমান (more sensitive).
- Ratio 1:2 - 1:3 maintain রাখুন।
ভাবুন: Sobel ও Laplacian দু'জনেই edge detect করে। কোনটি কখন বেশি ভালো?

Sobel = first derivative — edge-এর gradient direction পায়। Direction-aware applications-এ (Hough, gradient orientation histogram).

Laplacian = second derivative — edge-এর zero-crossing — sharper localization কিন্তু noise-prone. Marr-Hildreth (LoG) edge detector-এ।