পাঠ ০৭ · ৩৫-এর মধ্যে · মডিউল ১
Home / AI Courses / Computer Vision / SIFT & HOG

SIFT ও HOG — classical features

SIFT & HOG — pre-deep-learning feature descriptors
৮ মিনিট পড়া মাঝারি · Intermediate OpenCV কোডসহ

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

  • Feature কী — keypoint vs descriptor
  • SIFT-এর চারটি ধাপ
  • HOG-এর gradient histogram concept
  • OpenCV-তে SIFT ও HOG ব্যবহার

১ · Feature কী?

Feature = ছবির এমন একটি অংশ যা distinctive ও repeatable. ভিন্ন কোণ থেকে, ভিন্ন আলোয়, ভিন্ন আকারে — একই বস্তুর একই feature পাওয়া উচিত।

Two-step process:

  • Detection: এই pixel কি interesting? (corner, blob, junction)
  • Description: এই pixel-এর চারপাশে কী আছে? (vector representation)
কেন্দ্রীয় ধারণা

ছবিকে full pixel-এ compare করা impossible. কিন্তু ১০০-২০০ keypoint-এর descriptor compare — fast. এই trick থেকেই panorama stitching, AR, SLAM সম্ভব।

২ · SIFT — চারটি ধাপ

David Lowe (২০০৪) — Scale-Invariant Feature Transform. ১০ বছর CV-র সবচেয়ে cited paper.

ধাপ ১ — Scale-space extrema detection

  • ছবিকে কয়েকটি scale-এ Gaussian blur.
  • Difference of Gaussians (DoG) — adjacent blur level-এর difference.
  • 3D extrema (x, y, scale) — local maxima/minima. এগুলো keypoint candidate.

ধাপ ২ — Keypoint localization

  • Sub-pixel refinement — Taylor expansion দিয়ে accurate position.
  • Low-contrast point reject.
  • Edge response reject (only blob-like keypoint রাখা)।

ধাপ ৩ — Orientation assignment

  • Keypoint-এর চারপাশের 16×16 patch.
  • Gradient orientation histogram — dominant orientation বেছে।
  • একই keypoint-এ একাধিক orientation-ও সম্ভব।

ধাপ ৪ — Descriptor

  • Patch rotate — dominant orientation-এ align (rotation invariance).
  • 4×4 sub-region × ৮ orientation bin = ১২৮-D vector.
  • Normalize — illumination invariance.

ফলাফল: ছবির যেকোনো বস্তুর scale, rotation, illumination-নির্বিশেষে একই signature.

৩ · SIFT-এর invariance

  • Scale: DoG pyramid দিয়ে।
  • Rotation: dominant orientation alignment.
  • Illumination: gradient (absolute brightness নয়), descriptor normalize.
  • Affine (partial): small viewpoint change সহ্য করে — large না।

৪ · SURF, ORB — SIFT-এর বিকল্প

  • SURF (২০০৬): Speeded-Up Robust Features — Haar wavelet, integral image. SIFT-এর 3-5x fast.
  • ORB (২০১১): Oriented FAST + Rotated BRIEF. SIFT-এর 100x fast, free (SIFT/SURF patented ছিল)।
  • BRIEF, FREAK, AKAZE — অন্যান্য fast descriptor.

৫ · HOG — pedestrian detection-এর জাদু

Navneet Dalal & Bill Triggs (২০০৫, CVPR). মানুষ detect-এর সর্বশ্রেষ্ঠ classical descriptor.

মূল ধারণা: বস্তুর shape — gradient orientation distribution থেকে চিনে নেওয়া যায়। মানুষ-এ — head, shoulder, leg-এর gradient pattern বিশেষ।

HOG-এর pipeline

  1. Cell: ছবিকে 8×8 pixel cell-এ ভাগ।
  2. Gradient histogram: প্রতি cell-এ — সব pixel-এর gradient orientation কে ৯টি bin (0-180°)-এ histogram.
  3. Block normalization: 2×2 cell = 1 block. Block-wise L2 normalization — illumination invariance.
  4. Descriptor: সব block concatenate — large vector.
  5. Classifier: SVM train — pedestrian vs non-pedestrian.
HOG = ছবিকে গ্রিডে ভাগ → প্রতিটি ঘরে gradient-এর "কোণ ভোট" → ঐ pattern থেকে object identify. মানুষের body shape-এ shoulder slope, leg orient — এগুলো বিশেষ pattern.
SIFT vs HOG — দু'টি classical descriptor 🎯 SIFT Lowe, 2004 1️⃣ Scale-space extrema (DoG) 2️⃣ Keypoint localize + filter 3️⃣ Orientation assign 4️⃣ 128-D descriptor Use: matching, panorama, SLAM scale + rotation invariant 📊 HOG Dalal & Triggs, 2005 1️⃣ 8×8 cell ভাগ 2️⃣ Gradient histogram (9 bin) 3️⃣ Block L2 normalize 4️⃣ Concat → SVM classify Use: pedestrian, face, sign global shape descriptor SIFT = local sparse, HOG = dense global
SIFT — sparse keypoint matching. HOG — dense object detection. দু'টোই hand-crafted gradient-ভিত্তিক।

৬ · OpenCV-তে SIFT

Python · OpenCV 
import cv2
import numpy as np

# একটি synthetic textured image
np.random.seed(42)
img = np.random.randint(0, 256, (200, 200), dtype=np.uint8)

# SIFT
sift = cv2.SIFT_create()
keypoints, descriptors = sift.detectAndCompute(img, None)

print("Keypoint count:", len(keypoints))
print("Descriptor shape:", descriptors.shape)   # (N, 128)
print("First keypoint:")
kp = keypoints[0]
print(f"  position: ({kp.pt[0]:.1f}, {kp.pt[1]:.1f})")
print(f"  size (scale): {kp.size:.2f}")
print(f"  angle (orientation): {kp.angle:.1f}°")
print(f"  response (strength): {kp.response:.4f}")

    


    

      প্রতিটি keypoint-এ — position, scale, orientation. Descriptor 128-D vector — দু'টি ছবিতে এই vector compare করেই matching.
    


    
৭ · OpenCV-তে HOG


    

      

        
        Python · OpenCV
      

      
import cv2
import numpy as np

# একটি 64×128 synthetic ছবি (pedestrian detection size)
img = np.zeros((128, 64), dtype=np.uint8)
img[20:100, 20:44] = 200    # vertical body shape

# HOG descriptor
hog = cv2.HOGDescriptor(
    _winSize=(64, 128),
    _blockSize=(16, 16),
    _blockStride=(8, 8),
    _cellSize=(8, 8),
    _nbins=9
)

descriptor = hog.compute(img)
print("HOG descriptor shape:", descriptor.shape)
# (3780, 1) — Dalal-Triggs original size

# Norm
print("L2 norm:", np.linalg.norm(descriptor))

      

        
        
      

      

    


    

      Dalal-Triggs original setup: 64×128 window, 16×16 block, 8×8 cell, 9 bin → 3780-D feature vector. SVM-এ feed করলে — pedestrian / not.
    


    
৮ · DL-পূর্ব যুগে এদের রাজত্ব

    
    
      
  • SIFT: Image matching, panorama (Photoshop, Hugin), 3D reconstruction (Photo Tourism), SLAM (ORB-SLAM).
    • 
      
  • HOG+SVM: ২০০৫-২০১২ pedestrian detection benchmark.
    • 
      
  • HOG-cascade: Viola-Jones-এর successor.
    • 
      
  • Bag of Visual Words: SIFT cluster → image retrieval, classification.
    • 
    


    
৯ · DL-এ পরিবর্তন

    
    
      
  • ২০১২ AlexNet — CNN feature SIFT-এর চেয়ে ভাল। ১০ বছরের race ভেঙে পড়ে।
    • 
      
  • ২০১৪ R-CNN — HOG+SVM-এর জায়গায় CNN feature + SVM.
    • 
      
  • আজকের SuperPoint, D2-Net, LoFTR — SIFT-এর DL successor.
    • 
    


    

      কিন্তু SIFT/HOG মরেনি। Mobile AR (ARKit Marker tracking), low-power robot SLAM, satellite image alignment-এ এখনো ব্যাপকভাবে ব্যবহৃত। GPU ছাড়া realtime — DL এখনো reach করতে পারেনি।
    


  


  

    
    
  


  

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


    

      
        প্র ০১
        SIFT-এর "scale invariance" কীভাবে DoG pyramid দিয়ে অর্জিত হয়? Lindeberg-এর scale-space theory-র মূল insight কী?
      
      

        

          Tony Lindeberg (১৯৯৪) — Scale-space theory-র জনক। SIFT-এর গাণিতিক ভিত্তি।
        

        

          মূল problem:
        

        
    
          
  • একই বস্তু কাছ থেকে — বড় (high resolution detail).
    • 
          
  • দূর থেকে — ছোট (low resolution).
    • 
          
  • একই detector উভয় ক্ষেত্রে কাজ করতে হবে।
    • 
        

        

          Scale-space-এর insight:
        

        
    
          
  • ছবিকে অনেকগুলো $\sigma$-এ Gaussian blur — multi-scale representation.
    • 
          
  • $\sigma$ ছোট = fine detail, $\sigma$ বড় = coarse structure.
    • 
          
  • একটি বস্তু "natural scale"-এ extremum দেয় — সেটাই keypoint.
    • 
        

        

          DoG-র চমৎকারিত্ব:
        

        
    
          
  • Laplacian of Gaussian (LoG) — scale-space-এর "blob detector". কিন্তু compute ব্যয়বহুল।
    • 
          
  • DoG = $G_\sigma - G_{k\sigma}$ — দু'টি Gaussian-এর difference.
    • 
          
  • Mathematical proof: DoG ≈ scale-normalized LoG (Lowe-র paper-এ)।
    • 
          
  • ছবিকে একবার pyramid-এ blur করে nearby blur subtract — সাশ্রয়ী।
    • 
        

        

          Octave structure:
        

        
    
          
  • Octave = same resolution-এর কয়েকটি blur level.
    • 
          
  • Octave শেষে — ছবি 2x downsample → পরের octave.
    • 
          
  • একটি image-এ ৪-৫ octave সাধারণত।
    • 
        

        

          Extremum detection:
        

        
    
          
  • প্রতিটি pixel-এর 26 neighbor (8 same scale + 9 above + 9 below).
    • 
          
  • Local extremum (max বা min) → keypoint candidate.
    • 
        

        

          Keypoint-এর scale:
        

        
    
          
  • যে $\sigma$-এ extremum পাওয়া গেছে — সেটাই keypoint-এর "characteristic scale".
    • 
          
  • Descriptor compute হয় এই scale-এ proportional patch থেকে।
    • 
          
  • এটাই scale invariance-এর source.
    • 
        

        

          Theoretical foundation:
        

        
    
          
  • Lindeberg প্রমাণ: Gaussian = unique kernel যা scale-space axioms (causality, semi-group, isotropy) মেনে চলে।
    • 
          
  • Heat equation-এর সাথে সম্পর্ক: $\partial L / \partial \sigma = \nabla^2 L$।
    • 
          
  • Biological evidence: human retina-এ multi-scale Gaussian-like processing.
    • 
        

        

          মূল উপলব্ধি: SIFT মাটি থেকে design না — গভীর mathematical principle থেকে। এই pure mathematical insight-ই SIFT-কে dominantent করেছিল ১০ বছর।
        

      

    


    

      
        প্র ০২
        HOG pedestrian detection-এ SVM ব্যবহার হয় — কেন simple threshold বা random forest নয়? SVM-এর কী gain?
      
      

        

          এটি ML system design-এর একটি classic case study. Choice random ছিল না — গাণিতিক justification আছে।
        

        

          HOG descriptor-এর nature:
        

        
    
          
  • 3780-D dense feature — high dimensional.
    • 
          
  • Each dimension continuous, normalized.
    • 
          
  • Pedestrian vs non-pedestrian — generally separable.
    • 
        

        

          SVM-এর fit reason:
        

        
    
          
  • High-D linear separation: SVM linear kernel — simple decision boundary, fast inference.
    • 
          
  • Margin maximization: training-এ unseen sample-এ generalize ভাল।
    • 
          
  • Sparse support vector: 1000s of training image থেকে শুধু কিছু support vector — memory efficient.
    • 
          
  • Probabilistic interpretation: Platt scaling দিয়ে confidence score.
    • 
        

        

          Threshold কেন কাজ করে না?
        

        
    
          
  • Single dimension threshold — ৩৭৮০-D space-এ trivially অসম্পূর্ণ।
    • 
          
  • Multi-feature linear combination দরকার — সেটাই SVM.
    • 
        

        

          Random forest কেন কম optimal?
        

        
    
          
  • RF — axis-aligned split. 3780-D-এ explosion.
    • 
          
  • Continuous gradient bin — RF-এর discretization-এ subtle pattern lose.
    • 
          
  • Inference slower (tree traversal × 100 trees).
    • 
          
  • Model size বড় (each tree large).
    • 
        

        

          Neural network কেন না?
        

        
    
          
  • ২০০৫-এ — DL মৃতপ্রায়। Training infrastructure ছিল না।
    • 
          
  • Small dataset (INRIA — 2400 positive). MLP overfit.
    • 
          
  • SVM-এর margin theory better generalization বলে accepted.
    • 
        

        

          HOG+SVM-এর extension:
        

        
    
          
  • Kernel SVM: RBF, polynomial — non-linear decision. Slower.
    • 
          
  • Cascade: multi-stage SVM — early reject easy negative. Realtime.
    • 
          
  • Latent SVM (DPM): deformable parts — Felzenszwalb. ২০০৮-২০১২ rules.
    • 
        

        

          Modern parallel:
        

        
    
          
  • CNN feature extractor + linear classifier — same idea, learned features.
    • 
          
  • HOG → CNN feature, SVM → softmax linear.
    • 
          
  • Architecture continuity!
    • 
        

        

          মূল উপলব্ধি: ML algorithm choice = (1) data nature, (2) compute available, (3) interpretability need-এর intersection. HOG+SVM combination — ২০০৫-এর constraint-এ optimal.
        

      

    


    

      
        প্র ০৩
        SIFT patent-এর কারণে অনেক বছর open-source-এ ছিল না। ২০২০-এ patent expire. এই IP issue CV-র progress কীভাবে আকার দিয়েছে?
      
      

        

          এই গল্প — research patent vs open source-এর ক্ষেত্রে CV-র সবচেয়ে চেনা case study.
        

        

          Background:
        

        
    
          
  • SIFT — University of British Columbia patented (US 6,711,293, ২০০৪-২০২০)।
    • 
          
  • Lowe's algorithm — open paper, কিন্তু commercial use restricted.
    • 
          
  • OpenCV-তে SIFT non-free module-এ → standard install-এ অনুপস্থিত।
    • 
        

        

          Effect on research:
        

        
    
          
  • Alternative invention: ORB (Rublee et al., 2011) — explicitly "free SIFT alternative".
    • 
          
  • FREAK, BRIEF, AKAZE — patent-free landscape encourage.
    • 
          
  • SURF-ও patented — same problem.
    • 
          
  • Academic frustration: small research group cannot ship products.
    • 
        

        

          Effect on industry:
        

        
    
          
  • Photo apps — license fee. Photoshop UBC-কে fee দিত।
    • 
          
  • Open source projects — alternative develop. OpenSURF, RootSIFT.
    • 
          
  • Mobile/AR vendors — ORB choose. Android ARCore এখনো ORB-based.
    • 
        

        

          Patent expiration (March 2020):
        

        
    
          
  • OpenCV-এ SIFT main module-এ free.
    • 
          
  • Mobile apps SIFT-এ migrate.
    • 
          
  • Tutorials reopen.
    • 
          
  • কিন্তু ইতিমধ্যে DL feature (SuperPoint, etc.) উঠে এসেছে।
    • 
        

        

          Broader IP debate:
        

        
    
          
  • Pro patent: University funded basic research, return-on-investment.
    • 
          
  • Con patent: Open algorithm faster progress; alternatives waste effort.
    • 
          
  • Modern norm: ML papers patent-free, code on GitHub. Open culture.
    • 
          
  • Anthropic, OpenAI, Meta: models commercial but research papers free.
    • 
        

        

          Lesson:
        

        
    
          
  • IP friction often spurs innovation in alternatives.
    • 
          
  • Open source builds bigger ecosystems — see PyTorch dominance.
    • 
          
  • Patent's expiration timing affects technology adoption curves.
    • 
        

        

          Today's parallel:
        

        
    
          
  • Closed model (GPT-4) vs open model (Llama, Mistral).
    • 
          
  • Bangladesh-এর startup — open model-এ ভর করে।
    • 
          
  • SIFT story repeating in LLM era.
    • 
        

        

          মূল উপলব্ধি: Algorithm-এর success শুধু গণিত না — license, ecosystem, community-র উপরও। Engineer-এর IP awareness থাকা চাই।
        

      

    


    

      
        প্র ০৪
        আজ ২০২৬-এ একটি AR app বানাচ্ছেন যা phone-এ marker track করে। SIFT, ORB, বা SuperPoint — কোনটা বাছবেন? Trade-offs?
      
      

        

          এটি real production decision. Bangladesh-এর AR startup-গুলোর সামনে আজও এই trilemma.
        

        

          Use case profile:
        

        
    
          
  • Mobile phone — limited compute (~5W TDP).
    • 
          
  • Battery sensitive — multi-hour use.
    • 
          
  • 30+ FPS realtime চাই।
    • 
          
  • Poor lighting (Bangladesh outdoor / indoor lights mix).
    • 
          
  • Diverse phone hardware (low-end Android থেকে iPhone).
    • 
        

        

          SIFT — pros & cons:
        

        
    
          
  • ✅ Highest accuracy across illumination/scale.
    • 
          
  • ✅ Patent-free now.
    • 
          
  • ❌ Slow — 100ms+ per frame even with optimization.
    • 
          
  • ❌ Memory-heavy (128-D × hundreds of points).
    • 
          
  • Verdict: high-end iPhone-এ OK, mid-range Android struggle.
    • 
        

        

          ORB — pros & cons:
        

        
    
          
  • ✅ ~10x faster than SIFT.
    • 
          
  • ✅ Binary descriptor (256 bit) — memory tiny.
    • 
          
  • ✅ Hamming distance — fast matching.
    • 
          
  • ❌ Less robust to large viewpoint change.
    • 
          
  • ❌ Discriminative power slightly less.
    • 
          
  • Verdict: mobile AR-এ default choice. ARCore-এ ব্যবহৃত।
    • 
        

        

          SuperPoint — pros & cons:
        

        
    
          
  • ✅ DL-based — challenging condition (motion blur, low-light) handle.
    • 
          
  • ✅ Self-supervised — generalize ভাল।
    • 
          
  • ❌ Neural network — GPU/NPU চাই।
    • 
          
  • ❌ Mobile model 5-20 MB.
    • 
          
  • ❌ Battery drain.
    • 
          
  • Verdict: flagship phones (NPU available)-এ best.
    • 
        

        

          Modern hybrid approach:
        

        
    
          
  • ORB initial localization (fast, every frame).
    • 
          
  • Periodic SuperPoint refinement (slow, every 30 frames).
    • 
          
  • Pose drift correct.
    • 
          
  • iPhone Lidar + ORB — ARKit.
    • 
        

        

          Recent frontier:
        

        
    
          
  • LoFTR (2021): Detector-free dense matching. Slow but very accurate.
    • 
          
  • DISK (2020): Self-supervised local feature.
    • 
          
  • Deep VO/SLAM: ORB-SLAM3 (classical) vs DROID-SLAM (DL).
    • 
        

        

          Bangladesh-specific considerations:
        

        
    
          
  • Mid-range device dominant (Walton, Realme, Redmi).
    • 
          
  • 3G/4G data — model download size matters.
    • 
          
  • Outdoor light variation extreme.
    • 
          
  • Recommendation: ORB primary, SuperPoint fallback for premium devices.
    • 
        

        

          Decision matrix:
        

        
    
          
  • Premium iOS → ARKit native (ORB+VIO).
    • 
          
  • Premium Android → ARCore (ORB).
    • 
          
  • Mid-range Android → custom ORB pipeline.
    • 
          
  • Server-side AR → SuperPoint/LoFTR via cloud.
    • 
        

        

          মূল উপলব্ধি: "Best algorithm" নেই — best algorithm for context আছে। Hardware, energy, accuracy, latency-র multi-objective optimization.
        

      

    

  


  

    
 অনুশীলন

    
    
      
  1. 
        SIFT match: দু'টি ছবিতে SIFT detect করে BFMatcher দিয়ে match — কোডটি লিখুন।
        
    
          
          
    
            
    sift = cv2.SIFT_create()
kp1, des1 = sift.detectAndCompute(img1, None)
kp2, des2 = sift.detectAndCompute(img2, None)
bf = cv2.BFMatcher(cv2.NORM_L2, crossCheck=True)
matches = sorted(bf.match(des1, des2), key=lambda m: m.distance)
print(f"Top match dist: {matches[0].distance:.2f}")
    
          
    
        
    
      
    2. 

      
  2. 
        HOG dimension: 64×128 window, 16×16 block, 8×8 stride, 8×8 cell, 9 bin — descriptor dimension কত?
        
    
          
          
    
            
    Window per dim: $(64-16)/8 + 1 = 7$ horizontal, $(128-16)/8 + 1 = 15$ vertical = 105 block. প্রতি block 4 cell × 9 bin = 36. Total 105 × 36 = 3780.
    
          
    
        
    
      
    3. 

      
  3. 
        ভাবুন: SIFT keypoint detect-এ DoG-র বদলে Harris corner ব্যবহার করলে কী হতো?
        
    
          
          
    
            
    Harris corner = single scale. Scale invariance থাকত না। দূর থেকে নেওয়া ছবিতে keypoint match হতো না। SIFT-এর scale-space pyramid এই সমস্যার সমাধান।
    
          
    
        
    
      
    4. 
    

  


  

    
 আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

    

    

      কোড রানার কাজ না করলে? ব্রাউজারে কাজ না করলে
      Google Colab
      ব্যবহার করুন — Google-এর ফ্রি অনলাইন Python পরিবেশ, শুধু Gmail অ্যাকাউন্ট লাগে।
    

  







  
  
     এই পাঠে ভুল পেয়েছেন? জানান
  





  
    
 পূর্ববর্তী পাঠ

    
পাঠ ০৬ · Edge detection