Overview Object Detection ML

1. Object detection as a means of classification

  • Theo cách này, chúng ta sẽ dùng một cửa sổ trượt (sliding window) để lần lượt trượt qua bức ảnh. Tại mỗi vị trí cửa sổ trượt, ta áp dụng thuật toán classification, nếu độ confidence tại vị trí đó lớn hơn một ngưỡng nào đó, ta xác định vị trí đó có chứa object với nhãn tương ứng với confidence.
  • Vấn đề:
    • Kích thước của 1 object trong các bức ảnh khác nhau là khác nhau, vì vậy ta phải dùng rất nhiều sliding window với các kích thước khác nhau để xác định object –> Lâu, tốn tài nguyên tính toán.

2. Hog feature (Histogram of Oriented Gradients) (2005)

  • Không tốn kém về mặt tính toán, có thể ứng dụng vào một số ứng dụng real time: pedestrian detection, face detection, …
  • Tại mỗi vị trí cửa sổ trượt, tính hog features (1 vector) rồi đưa vào bộ phân loại SVM để xác định xem có object tại vị trí cửa số trượt đó không.

3. R-CNN (Region-based Convolutional Neural Networks) (2014)

  • Thay thế bộ phân loại dựa trên Hog feature để tăng độ chính xác bước classify.
  • Tuy nhiên, CNN tốn tài nguyên tính toán –> R-CNN
  • R-CNN: đưa ra thuật toán đề xuất object (object proposal) – Selective Search– để giảm số lượng bounding box đưa vào bộ phân loại xuống còn khoảng 2000.
    • Selective Search sử dụng các đặc tính local như hình dạng, cường độ sáng, màu sắc, … để xác định tất cả các bounding box có thể có của object.
    • Đưa các bounding box được đề xuất vào bộ phân loại CNN. Do input của các mạng neural là cố định nên phải resize các bounding box về kích thước cố định của mạng sử dụng. (vd: 224×224 cho VGG)

rcnn2

  • Các bước thuật toán:
    • Selective Search để đề xuất các bounding box
    • Feature extraction: Các bouding box được resize và đưa vào các mạng CNN (vd: VGG)
    • Train: Các feature vectors thu được được sử dụng để train hai model độc lập: SVM để classify nhãn của vector tương ứng với bounding box bounding box regressor để cải thiện độ chính xác trong việc dự đoán vị trí của bbox.

frcnn

  • Sử dụng L2 loss function (bbox regression) & cross entropy loss (classification)

4.  SPP-net (Spatial Pyramid Pooling) (2015)

  • SPP-net ra đời để khắc phục điểm yếu về tốc độ của R-CNN
  • Chỉ extract feature bằng CNN cho toàn bộ bức ảnh duy nhất một lần và sử dụng nó để tính feature vectors cho các bounding box. Việc này thực hiện được bằng cách chỉ lấy phần feature vectors tương ứng với bounding box tại layer convolution cuối cùng tương ứng với vị trí của bbox cho mỗi bbox được lựa chọn bởi Selective Search.
  • Feature vectors lấy được thông qua cách này cũng phải tính đến việc downsampling xảy ra trong quá trình extract feature bằng CNN (đơn giản chỉ là chia các tọa độ cho 16 đối với mạng VGG)
  • Do input của mạng phân loại là không đổi, mà các bbox lại có kích thước khác nhau, nên ta phải thực hiện thêm 1 trick: Sử dụng spatial pooling (aka ROI pooling).
    • Chia các bbox thành các bins, thực hiện max-pool trên các bins này (tức là với mỗi bin, chỉ lấy 1 giá trị max). Do số lượng bins là không đổi, ta thu được các vector với kích thước như nhau. (trong ví dụ, áp dụng 3 spatial pooling với các cách chia bins khác nhau)

sppnet

  • Vấn đề: Khó để thực hiện back-propagate qua spatial pooling nên các parameters chỉ được tuning tại các lớp fully connectect layers.
  • SPP đặt nền móng cho sự phổ biến của Fast-RCNN.
  • Sử dụng L2 loss function (bbox regression) & cross entropy loss (classification)

5. Fast R-CNN (2015)

  • Fast R-CNN sử dụng ý tưởng của RCNN và SPP và giải quyết được vấn đề của SPP: end-to-end training.
  • Thực hiện back propagate qua lớp spatial pooling bằng cách sự dụng phép tính khá tương tự như tính max-pooling gradient.
  • Ngoài ra, Fast R-CNN thực hiện training bbox regression bằng neural network đồng thời cùng với việc phân loại. Đây là điểm nhấn của Fast R-CNN, thực hiện multitask training, không chia bbox regression và classification thành hai mạng khác nhau. Từ đó giảm thời gian tính toán của thuật toán.
  • Fast R-CNN có độ chính xác cao hơn SPP do thực hiện được end-to-end training so với SPP không training được lớp spatial pooling nên có kết quả kém hơn; training time Fast R-CNN nhanh hơn 9x so với R-CNN trong khi infer time nhanh hơn 213 lần. Các con số này so với SPP lần lượt là 3x (training) và 10x (inferencing) (VGG 16).
  • Sử dụng L1 loss function (bbox regression) & cross entropy loss (classification)

6. Faster R-CNN (2015)

  • Cải thiện tốc độ so với Fast R-CNN
  • Thay thế Selective Search (phần tốn thời gian nhất trong Fast R-CNN) bằng một mạng CNN gọi là Region Proposal Network (RPN) để tạo ra các bbox. –> Loại bỏ hoàn toàn các kỹ thuật của Computer Vision truyền thống.
  • RPN có thể đóng vai trò là một mạng Single Object Detector hoặc tạo các bbox đề xuất cho mạng Fast RCNN.
  • Để giải quyết vấn đề tỷ lệ và kích thước của object thay đổi, Faster R-CNN giới thiệu một kỹ thuật: anchor boxes. Tại mỗi vị trí, bài báo gốc sử dụng 3 anchor boxes lần lượt có kích thước 128×128, 256×256 và 512×512 và các tỷ lệ 1:1, 2:1 và 1:2. Vì vậy, tại mỗi vị trí, ta có 9 boxes mà tại đó RPN predict xác xuất nó là background hay foreground. Ta áp dụng bbox regression để cải thiện anchor box tại mỗi vị trí.
  • Cách thức RPN làm việc (link):
    • Input ảnh 800×800, đưa qua một feature extractor (vd VGG 16). Sau khi đã downsampling 16 lần, output vectors [512, 50, 50]. Một mạng RPN được áp dụng cho các feature maps này, tạo ra (512*9*9) tọa độ của các bbox do đó output là các vectors 512*9*9*4 (bbox regression) và 512*9*9*2 (classification).
    • Cách tạo ra các anchor boxes: Tại mỗi vị trí trên feature maps, tương ứng với một vùng (box) trên image (ví dụ: Điểm (0, 0) trên feature map tương ứng với một vùng [0, 0, 16, 16] trên image). Tính center của box này, sau đó vẽ 9 anchor boxes tương ứng các scales và ratios. Do mỗi feature map có kích thước 50×50 –> có 50*50*9 anchor boxes ứng với mỗi feature map. Do việc xác định các anchor boxes thực hiện trên ảnh gốc –> chỉ cần thực hiện trên 1 feature map –> tổng có 50*50*9 = 22500 anchor boxes.
    • Anchor boxes được xem là positive nếu IoU > 0.7 và negative nếu IoU < 0.4; mọi anchor boxes có IoU thuộc [0.4, 0.7] hoặc nằm ngoài ảnh đều bị bỏ qua.
    • Do số anchor negative chiếm số đông nên ta chỉ dùng 128 anchor negative và 128 anchor positive để thực hiện training từng vòng lặp (với batch_size=2).
    • Loss funtion L1 (bbox regression) và cross entropy (classification)
    • Để giảm tính redundancy do các anchor boxes overlap với nhau, áp dụng NMS (Non-Maximum Suppression) trước khi thực hiện spatial pooling (aka ROI pooling). NMS không làm giảm độ chính xác thuật toán, đồng thời giảm rõ rệt số lượng anchor boxes về còn khoảng 2000.
    • Áp dụng Fast R-CNN cho 2000 anchor boxes này và ta thu được kết quả cuối cùng.

1*wwKCoG-VtBycFeACBES4nA

  • Kết quả:
    • inference: 5 FPS trên GPU
    • VGG backend: 73.2% mAP.

7. Yolo (một nhóm thuật toán thuộc nhóm Single Shot Detection)

  • YOLO v1: sử dụng framework Darknet được train trên tập ImageNet-1000. Nó không thể tìm thấy các object nhỏ nếu chúng xuất hiện dưới dạng một cụm. Phiên bản này gặp khó khăn trong việc phát hiện các đối tượng nếu hình ảnh có kích thước khác với hình ảnh được train.
  • Yolo v1 (2015)
    • Chia ảnh thành SxS cells (ví dụ 7×7 cells). Cell được coi là positive nếu chứa center của object.
    • Mỗi cell predict N bounding box –> số bbox là S*S*N. Mỗi bbox bao gồm 5 predictions: x, y, h, w, confidence. (x,y) là tọa độ của tâm bbox predicted; (h, w) lần lượt là chiều dài, rộng của bbox tỷ lệ với ảnh gốc; confidence là IoU giữa bbox predicted và bbox groundtruth.
    • Giả sử S=7, N=2, xét trên tập dataset VOC (20 nhãn) –> mỗi grid output (4+1)*2+20=30 output –> mỗi ảnh có 7*7*30 output.
    • For each cell,
       For each ground_truth_bbox:
       check if the cell contains bbox center or not,
       if yes:
       encode the box with respective values of bbox, label and binary encoding of object present or not[1 in this case].
    • Nếu 1 cell có 2 center của bbox, có thể chọn random lấy một center hoặc tăng số lượng cells (ví dụ lên 16×16) –> giải quyết trong Yolo v2.
    •  Network (Darknet) – Mạng để predict ra (SxSxN) bounding box

1*9S71g07aSqSl8GA3BoYv4A

    • Loss function: 3 loss functions (coor & classify loss just be calculated if obj loss > 0.5)
      • Coordinates error
      • Objectness score
      • Classification error
  • 1*aseMLqFdGUfCz7tLmtVTcQ
    •  Result: 63.4 mAP với  45 FPS (frames per second).
  • Yolo v2 (2016)
    • So sánh với Yolo v1
      • At 67 FPS, YOLOv2 gets 76.8 mAP on VOC 2007. At 40 FPS, YOLOv2 gets 78.6 mAP, outperforming state-of-the-art methods like Faster R-CNN with ResNet and SSD while still running significantly faster
      • Sử dụng anchor boxes tại mỗi grid cell, giúp giải quyết vấn đề có nhiều center bbox tại một cell
      • Scales và ratios cho anchor boxes được config dựa trên dataset, do đó việc hiểu rõ dataset là rất quan trọng. Đây là lần đầu tiên một giải thuật DL thực hiện điều này.
      • Số lượng grid cell mặc định tăng từ 7×7 lên 13×13 và có thể config nếu muốn bắt được các object nhỏ hơn. Đây là thông số cần phải check trước khi sử dụng Yolo v2.
      • Để lựa chọn số lượng anchor boxes, ta có thể sử dụng k-mean clustering (link, link):
        • Trong nhiều bài toán, các bbox thường có các strong pattern (ví dụ automatic car: car, pedestrian).
        • Do đó, chúng ta có thể lựa chọn số lượng anchor boxes bằng cách tìm top-k anchor boxes bao phủ tốt nhất toàn bộ ground truth bbox. Tốt nhất ở đây mang nghĩa cân bằng giữa hàm loss và độ phức tạp tính toán vì rõ ràng càng nhiều anchor box thì IoU càng nhỏ, nếu k=tổng số bbox trong training set thì IoU = 1.
        • Metric khoảng cách trong thuật toán k-mean được sử dụng là 1 – IoU.
        • Để xác định số k, ta thử lần lượt k=2, 3, … cho tới khi loss giảm không đáng kể. Khi đã xác định được k, ta đồng thời cũng xác định được luôn kích thước (tỷ lệ) của từng bbox (chính là tọa độ centroid của cluster tương ứng).
      • Giới thiệu Batch Normalize, giống với Network in Network, sử dụng conv 1×1 và global average pooling;  giảm sự thay đổi giá trị unit trong hidden layer, do đó sẽ cải thiện được tính ổn định của neural network.
      • Thay đổi encoding cho x, y, h, w như sau: (link) (sigma func = sigmoid)
    • 1*38-Tdx-wQA7c3TX5hdnwpw 1*gyOSRA_FDz4Pf5njoUb4KQ
      • Multi-Scale Training: YOLO v1 có điểm yếu là phát hiện các đối tượng với các kích cỡ đầu vào khác nhau. Điều này được giải quyết bằng YOLO v2, nó được train với kích thước ảnh ngẫu nhiên trong khoảng 320*320 đến 608*608 (sau đó resize về 448×448 ???). Điều này thực hiện được bởi vì khi loại bỏ các lớp fully connected layer, ta chỉ còn lại các lớp conv, pooling, vốn không cố định input dimension. Khi áp dụng các lớp này cho ảnh kích thước ngẫu nhiên (ví dụ 320×320, 608×608, …), ta sẽ được các feature maps kích thước khác nhau (ví dụ: 10×10, 11×11, …, 19×19). Từ các feature maps này, ta có thể tính loss function theo các grid kích thước tương ứng trên input image (tương ứng sẽ chia image thành grid 10×10, …, 19×19???). Yolov2 thực hiện việc resize này mỗi 10 epoches.
      • Sử dụng darknet 19: Phức tạp hơn mạng darknet sử dụng trong Yolov1.
      • High Resolution Classifier:  Pretrain classifier model với ImageNet input 224×224. Sau đó, loại bỏ 1×1000 fully connected layer và thêm 4 conv layers + 2 fully connected layer (random init weights)  –> để resize input network từ 224×224 thành 448×448.
      • Tại bước detection, image 448×448 sẽ được resize về 416×416, output size là 13x13x125. Để làm được điều này, tác giả của yolov2 bỏ lớp conv cuối cùng, thêm vào 3 lớp 3×3 conv layer + 1 lớp 1×1 conv layer với số filter là 125 để thu được 13x13x125 output layer.

yolov2_2

      • Fine-Grained Features: Do khi qua các lớp conv layer, kích thước ảnh/feature maps ngày càng bị giảm đi, do đó có mất mát thông tin nhiều, dẫn tới khó phát hiện các vật thể nhỏ. Để khắc phục phần nào vấn đề này, Yolov2 đề xuất một cơ chế passthrough: reshapes the 26 × 26 × 512 layer to 13 × 13 × 2048. Then it concatenates with the original 13 × 13 ×1024 output layer. Now we apply convolution filters on the new 13 × 13 × 3072 layer to make predictions.

yolov2_passthrough

  • Yolo 9000: TODO
  • Yolo v3 (2018)
    • Yolov3 achieves 33.4 IOU@0.5:0.95 mAP and 57.9 IOU@0.5 mAP. The author takes a dig on why we switched our metrics and supports IOU@0.5(VOC style). Using VOC style mAP, Yolov3 is very robust
    • Thay đổi nhỏ so với Yolo v2: Thay  thế darknet19 thành darknet 53 để làm bộ feature extraction; giới thiệu residual blockFPN (Feature Pyramid Networks).

1*OR-qjl2FeR8NQOVZEfl67g1*dLeXxT3zleyN2MLEu6NZxg

      • Trong một số dataset, một instance có thể có nhiều nhãn (multilabel) (ví dụ: woman, person). Do đó, Yolov3 thay lớp softmax bằng các lớp logistic classifier (sigmoid) tương ứng với từng class.
    • 1*4HLPGIqe9WTjMOfvab-uLQ
      • Sử dụng binary cross entropy
      • Nhờ việc sử dụng skip connection, các feature map đằng sau có nhiều thông tin hơn về các feature map đằng trước. Điều này giúp Yolov3 hoạt động tốt hơn với các đối tượng nhỏ so với Yolov2. Tuy nhiên, nó cũng khiến thuật toán này hoạt động kém hơn với các đối tượng large và medium so với Yolov2. Việc sử dụng cơ chế FPN cũng giúp Yolov3 hoạt động tốt hơn với các small object.
      • Yolov3 thực hiện predict tại 3 scale (link). Kết quả nào tốt hơn sẽ lấy scale đó làm output.
      • Yolov3 sử dụng tổng cộng 9 anchors, tại mỗi scale sử dụng 3 anchors. (Điểm này khác với Yolov2, khi mà ở Yolov2 ta có thể lựa chọn số lượng anchors boxes).
      • Số lượng prediction bbox của Yolov3 lớn hơn ~10x Yolov2. Do đó, Yolov3 chạy lâu hơn nhưng có kết quả tốt hơn Yolov2, đặc biệt đối với các small object.
    • 1*d4Eg17IVJ0L41e7CTWLLSg
      • Encoding is done in the following way. A gt box is attached to the anchor which has max_iou. Only anchors of the cell which contain the gt_box center are considered for the anchors.
      • Since Yolov3 uses 3 scales, 52×52, 26×26 and 13×13. The bounding boxes are encoded individually on each scale. loss is calculated on each layer individually and later summed.
      • Benchmark

1*YpNE9OQeshABhBgjyEXlLA

8. SSD — Single shot detector with VGG16 (2016)

  • Giới thiệu
    • Released after YOLO and Faster RCNN, this paper achieves 74.3 mAP at 59fps for 300×300 input size images. We call this network SSD300. Similarly SSD512 achieves 76.9% mAP surpassing Faster R-CNN results.
    • Trong Faster R-CNN, một mạng RPN được theo sau một bộ classifier để bbox regression và classification. Việc có một RPN làm tăng tính chính xác nhưng nó cũng đồng thời làm giảm tốc độ thuật toán.
    • Single Shot Detection đưa ra ý tưởng không dùng RPN để đề xuất ra các ROIs mà trực tiếp predict bbox & classes từ feature maps. Single Shot Detection thực hiện điều này nhờ ý tưởng về sliding windows
    • Trong sliding windows, các windows trượt trên các feature maps để phát hiện object. Với mỗi loại object, ta sử dụng các kích thước window khác nhau –> cần quá nhiều window với các kích thước khác nhau để detect object. Single Shot Detection đưa ra ý tưởng, chỉ sử dụng các window này như một khởi tạo của bbox, sau đó chúng ta có một bộ detector để predict đồng thời bbox & class của window hiện tại.

1_tE6DUwv6VIHu1KlwYmSBTw

    • Cách làm này khá giống với khái niệm anchor trong Faster R-CNN, tuy nhiên, Single Shot Detection đồng thời predict cả bbox và class (Faster R-CNN sử dụng 2 mạng riêng để predict bbox và class).
    • Tại mỗi vị trí trên feature map, ta có K anchors/windows, mỗi anchor cho một predict cụ thể nào đó. Tất cả các vị trí trên feature map đều sử dụng các anchor có kích thước như nhau.
    • Single Shot Detection thường không phát hiện được các object nhỏ
  • SSD
    • Là Single Shot Detection sử dụng mạng VGG 16 là feature extractor. Sau đó thêm một số lớp conv layers theo sau nó và các conv filters để predict

1_1C5hgYTdBvCdCYWbXEaVww

    • Tuy nhiên, do conv layers làm giảm kích thước các feature maps, nên ta chỉ có thể detect được object kích thước lớn. Do đó, chúng ta thực hiện object detection từ nhiều feature maps tại các levels khác nhau.

1_k0eFZw1jlF9xPvhzBKt6LQ

    • Tổng quan quá trình:

1*wsRz5bRgckDEPcNgfcE1Pw

  • Nhận xét:
    • SSD sử dụng các layer nằm ở level cao, do đó đã bị giảm độ phân giải (resolution) –> không detect được những object nhỏ, vốn khó detect được nếu độ phân giải input image nhỏ. Do đó, chúng ta có thể cần phải tăng độ phân giải của input image.
    • SSD không sử dụng upsampling để tạo thành FPN như trong Yolo3 mà dùng luôn các feature map ở high-level layer để predict.

9. Feature Pyramid Networks  (2017)

  • Hạn chế của Faster R-CNN:
    • Không phát hiện được các object nhỏ
    • Vấn đề imbalance class chưa được xem xét đúng mức (lấy ngẫu nhiên 256 mẫu anchor boxes không phải là cách phù hợp nhất để giải quyết vấn đề imbalance classes).
  • FPN đề xuất:
    • Feature Pyramid network
    • Focal loss: Bản chất là thêm một hệ số vào hàm cross entropy để giải quyết vấn đề imbalance classes (do số lượng sample background >> foreground và số lượng object của các class chênh lệch nhau lớn).
      • Cross Entropy

cross_entropy1cross_entropy2

      • Focal loss:

focal_loss

10. Retinanet (FPN +Focal loss)

1*0-GVAp6WCzPMR6puuaYQTQ

11. Nhận xét

  • Sau khi Faster R-CNN ra đời, với đề xuất khái niệm anchor boxes, khái niệm này đã được sử dụng trong các thuật toán Single Shot Detection (Yolo v2/v3, SSD) để cải thiện hiệu quả.

12. Reference

3 thoughts on “Overview Object Detection ML

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s