পাঠ ০৭ · ৩৫-এর মধ্যে · মডিউল ১
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