21. DETR 2020

Mở đầu

Detection Transformer DeTr 2020

Object detection systems based on transformers and bipartite matching loss for direct set prediction

Mục đích của Meta (Facebook) ở DeTr là xây dựng 1 object detection end-to-end trực tiếp (direct way). Tức dựa theo piple của detection mà loại bỏ bớt một số thành phần như Non-maximum suppression (NMS) và anchor generation ( xem lại Yolov2)

Ý tưởng cho thành phần khung mới là tạo 1 set-based global loss (loss tổng thể dựa trên tập hợp) và dự đoán duy nhất thông qua nối lưỡng cực (bipartite matching) bằng 1 transformer encoder-decoder architecture

Với 1 tập nhỏ các đối tượng truy vấn (object queries) cố định, DETR tìm hiểu quan hệ của các đối tượng và bối cảnh toàn cục (global image context) đối với dự đoán đầu cuối (final set of predictions) một cách song song. Ngoài ra, DETR còn có tác dụng trong panoptic segmentation

Mục đích của object detection là dự đoán 1 bounding boxes và phân loại labels cho mỗi object. Các modern detector làm nó theo cách gián tiếp, tức xác định các vấn đề phân loại và hồi quy trên 1 tập lớn các đề xuất (proposal), archor hoặc window center. Cách này bị ảnh hưởng đáng kể bởi các bước hậu xử lí (postprocessing). Để thay thế điều này, ta đề xuất phướng pháp dự đoán tập hợp trực tiếp (direct set prediction). Hướng đi end-to-end này đã thành công trong những cấu trúc phức tạp như machine translation hay speech recognition, nhưng chưa có trong object detection.

Encoder-Decoder architecture based on transformers,  phổ biến với sequence prediction. Và cơ chế self- attention miêu tả quan hệ các thành phần trong sequence. Ta hy vọng điều này phù hợp với set prediction (ví dụ như loại bỏ trùng lặp (duplicate predicttions)  

DETR không yêu cầu bất kì lớp tùy chỉnh (customized layers) nòa, do đó có thể sao chép vào các khung chứa CNN tiêu chuẩn hay transformer class.

Điểm đặc biệt của DETR là bipartite matching loss và transformers với (non-autogressive) parallel decoding

Thuật toán chi tiết

1. Đầu tiên ta nghiên cứu về pipeline hay dùng

    - bipartie matching losses cho set prediction

    - encoder-decoder architectures based  on the transformer, parallel decoding và object detection method

1.1 Set prediction

Chưa có mô hình học sâu nào dự đoán trực tiếp các tập hợp (directly predict sets). Task cơ bản  thường là multilabel classification (phân loại nhiều nhãn) mà thường xử lí bằng 1 vs rest, không dùng được cho detection do có cấu trúc giữa các phần tử (các hộp gần giống nhau near-idential boxes)

    - khó khăn đầu tiên: tránh near-duplicates (mà không dùng NMS như postprocessing) 

    -> Cần một suy luận toàn cục (global inference) có liên hệ giữa các thành phần để tránh dư thừa 

    -> Với constant-size set prediction, dùng dense fully connected networks là đủ nhưng tốn kém. Phương pháp chung là auto-regressive sequence (chuỗi hồi quy tự động) như Recurrent neural network RNN

    -> Trong mọi trường hợp, loss function cần bất biến với hoán vị của predictions (permutation-invariance)

    -> Hungarian algorithm, để tìm bipartite matching giữa ground-truth và prediction (mỗi target element có 1 unique match)

    -> Thay auto-regressive model bằng transformer với parallel decoding

1.2 Transformers and Parallel Decoding

Attention mechanism cũng có thể coi là neural network layer tổng hợp (aggregate) thông tin từ toàn bộ chuỗi đầu vào (input sequence). Với một trong những điểm mạnh là blobal computations và perfect memory, mà làm tốt hơn RNN

Được sử dụng trong auto-regressive bằng theo sau seq2seq model, để tạo tokenization (one by one). Nhưng do chi phí lớn (tỉ lệ thuận output length và hard to batch) -> parallel sequence generation.

Kết hợp transformer và parallel decoding cho trade-off giữa computational cost và khả năng thể hiện global computation cho set prediction

1.3 Object Detection

Ta directly predicting the set of detections với absolute box prediction

Set-based loss -> Bipartite matching loss -> Recurrent detector 

2. DETR Model

2 thành phần cần được chú ý là:

    - 1 set prediction loss tập trung unique matching giữa predicted và ground truth boxes

    - 1 architecture mà predict (trong 1 lượt) 1 set of objects và models liên hệ giữa chung

2.1 Object detection set predicts loss

    - Chọn N là fixed-size của set predictions (N > số lượng object trong 1 ảnh).

    - 1 trong những khó khăn chính là score predicted objects (class, position, size) với grough truth -> optimal bipartite matching sau đó optimize object-specific (bounding-box) loses.

    - Gọi y là gound truth set, y_ = {yi_}Ni=1 là tập N predictions. Ta thêm pad token (no object) để 2 bên bằng size. Để tìm bipartitie matching, ta tìm hoán vị của N phần tử mà :

Matching cost tính cả class predict và similarity của predicted. Mỗi phần tử i của ground truth có thể biểu diễn là yi = (ci,bi) (ci là target class label (có thể = no object token), bi thuộc [0,1]^4 là vector coordinate (4D giống yolov1)). Kết quả index delta(i) là xác xuất class ci (pdelta_(i)(ci)) và predicted box bdelta_(i)

Procedure này giống cách gán heuristic assignment rules (match proposal hoặc archor) với ground truth objects. Khác biệt là gán từng cái một (one-to-one) để không trùng lặp

    - Bước 2 là tính loss function (Hungarian loss) với mọi pairs

(linear combination của negative log-likelihood cho class prediction và box loss)
Với delta_ là phép gán tối ưu (optimal assignment) ở bước 1. Thực tế, ta down-weight log-probability khi ci = no-object theo hệ cơ số 10 cho class imbalance (giống Faster R-CNN) (matching cost giữa 1đối tượng bất kì và no-object là 1 hằng số). Ta dùng pdelta_(i)(ci) thay vì log-probabilities để phù hợp Lbox(.,.) (bounding box loss)

    - Bounding box loss: Lbox(.), Ta không chỉ dùng sai khác delta vị trí l1 để tránh việc khác scaling -> Dùng linear combination của l1 loss và IoU loss:

2.2 DETR architecture
Có 3 phần chính:

    - 1CNN backbone để extract feature

    - 1 encode-decoder transformer sử dụng cả image như context

    - 1 feed-forward network (FFN) để làm final detection prediction
-> Do là 3 phần nối tiếp nên dễ dàng implement với bất kì CNN backbone hay transformer architecture nào 

Backbone: input ximg thuộc R[3xH0xW0] (3 color channels), lower-resolution activation map f thuộc R[CxHxW]. Hay dùng C =2048, H,W = H0/32, W0/32

Transformer encoder: đầu tiên, 1x1 convolution giảm channel dimension của high-level activation map f từ C đến smaller dimension d (new feature map z0 thuộc R[dxHxW]. Encoder dùng sequence là input, collapse (biến) spatial dimension z0 thành 1 dimension (dxHW feature map). Là 1 permutation-invariant

Transformer decoder: dùng N embedding size d với multi-headed self-attention (không masked) và encoder-decoder attention. Điểm khác biệt là decode N object song song tại mỗi decoder layer, dùng 1 autoregressive model để predict output sequence 1 phần tử mỗi lần (one elemnet at a time). Decoder cũng là 1 permutation-invariant (không xét thứ tự trước sau của các object) (N input giống nhau thì cùng kết quả). 

Prediction feed-forward networks (FFNs): Final prediction được tính bởi 3 lớp perceptron với ReLU activation và hidden dimension d, và là linear projection layer. Output là predict normalized center coordinates, height và width của box và class label bởi softmax. Vì N lớn hơn số object of interest của image, nên 1 class đặc biệt no-object được thêm vào. Class này dùng như "background" class trong object detection cơ bản

Auxiliary decoding losses: Ta thấy rằng sẽ tốt hơn nếu dùng auxiliary losses trong decoder trong khi  training, đặc biệt để model output có số object chính xác cho mỗi class. Ta thêm prediction FFNs và Hungarian loss sau mỗi decoder layer. Mọi FFNs share parameter với nhau. Ta dùng thêm 1 shared layer-norm cho normalize input để prediction FFNs từ decoder layers khác nhau
Tối ưu Architect
Các block/layer trên đã được hoán đổi vị trí và thử qua rất nhiều lần (dataset COCO 2017, backbone Resnet50, test AP và AP50 https://arxiv.org/pdf/2005.12872v3.pdf ) để cho ra cấu trúc đủ và đúng vị trí như trên (thay đổi số lượng/thiếu layer/loss/block thì AP sẽ giảm)

=> Resnet50, 6 encoder, 6 decoder, 3 FFNs, width 256, 25 epochs (41.3M parameter) (DETR-DC5)

Training COCO: 8 GPU V100 cards 6 days

DETR for panoptic segmentation
Giống như mở rộng của Faster R-CNN thành Mask R-CNN cho task panoptic segmentation (khoanh vùng toàn cảnh). DETR cũng thêm 1 mask head (binary mask) tại ngay sau decoder output (DETR-R101)

Ta train DETR để predict boxes xung quanh "stuff" và "things". Predicting box cần train cần phải >0, vì Hugarian matching tính dựa vào khoảng cách. Ta cũng thêm 1 mask head để predict binary mask cho mỗi predicted boxes, lấy input là output của transformer decoder cho mỗi object và tính multi-head (M heads) attention score của embedding này qua output của encoder -> Sinh ra M attention heatmap cho mỗi object trong 1 small resolution. Để làm final prediction và  tăng resolution, FPN-like architect được dùng. Final resolution của mask có stride 4 và mỗi mask được supervised independent bằng DICE/F-1 loss và Focal loss

Mask head có thể train với DETR hoặc 1 mình (tách thành 2 bước), khi đó DETR chỉ dùng để predict boxes, thế thì freeze tất cả weight và chỉ train mask head cho 25 epochs

DETR không cần đến heuristic mà thwuongf dùng để align (căn chỉnh) mask khác nhau
Appendix

Implement

Hungarian algorithm
https://en.wikipedia.org/wiki/Hungarian_algorithm

https://www.youtube.com/watch?v=FQp9HJSg1zs&ab_channel=AustralianMathematicsCurriculumVideos

Là 1 method cho asignment problem, với bài toán matching 1 tập agents và 1 tập task 1 cách tốt nhất có thể (minimize cost hoặc maximize benefit) (O(n^3))

Các bước:

    - Tạo 1 cost matrix: tạo 1 cost matrix thể hiện cost hoặc benefit của mỗi agent đến mỗi task. Row thể hiện agents, columns thể hiện tasks, và cells là cost/benefit
    - Trừ giá trị nhỏ nhất row: với mỗi row, ta trừ giá trị nhỏ nhất cả row (cho tất cả cell trong row)-> Mỗi row sẽ có ít nhất 1 số 0

    - Trừ giá trị nhỏ nhất column: với mỗi column,ta trừ giá trị nhỏ nhất cả column (cho tất cả cell trong column) -> Mỗi column sẽ có ít nhất 1 số 0

    - Tìm 1 tập với minimum cost hoặc maximum benefit (test for an optimal assignment): Ta tìm 1 tập các số 0 trong matrix sao cho không có 2 số 0 nào cùng row hoặc column, mark những số 0 này (marked 0) (0*):

    Từ trên xuống dưới, với mỗi row, ta chọn 1 số 0 -> 0* mà không có 2 0* nào cùng row hay column

    - Tìm minimum set of covered entries: tìm số nhỏ nhất các lines (rows hoặc columns) cần để cover mọi số 0 trong matrix:

• Vẽ 1 line (cover mọi ô trên line) qua mọi 1 column đã marked (nếu mọi số 0 đã covered (0*) -> bước shift zeros)
  
• Tìm 1 số 0 chưa covered (0) và prime nó (0 -> 0'), nếu tất cả số 0 đã được covered thì kết thúc bước "Tìm minimum set of covered entries" ) (*)
• Nếu có 1 số 0 chung row với 1 marked 0* -> cover row đó, bỏ cover column của marked 0 -> (0')

• Ngược lại, nếu 1 số 0 chưa covered không chung hàng với row nào có 0* hoặc 0':
• a) Nếu có 1 số 0 marked, đến bước sau, nếu không thì ngừng lại, trả về kết quả cho "Ngược lại" loop
• b) Tìm 1 0' cho row đang xét (đang ở row 1 có 0*) (nên luôn là 1). Đến bước trước ( a) )
  
• c) Với mọi số 0 thuộc cái path đã lập ở 2 bước a) và b), biến 0' thành 0* và 0* thành 0 -> có thêm 0*
• d) bỏ cover mọi line và bỏ tất cả ' (0' -> 0)
  

  
• e) lặp lại các bước trước (về bước (*) ) đến khi (*) có thể kết thúc bước "Tìm minimum set of covered entries" 

  

     - Adjust the matrix (shift zeros): trừ minimum uncovered value từ mỗi uncovered cell, và thêm value đến mọi cell covered bởi 2 lines (tương đương trừ minimum uncovered value từ mỗi row chưa covered và thêm đúng giá trị đó vào các column đã covered) . Sau đó quay trở lại bước "test for an optimal assignment", lặp lại đến khi có assignment khả thi

    - Tính final assignment: Khi không có uncovered 0 nữa, asignment có thể tính được. Bằng cách nối mỗi agent và task bởi các số 0 chọn ở bước trước

- Theo thuật toán, ta sẽ có số lines dùng để cover mọi số 0 = số min (số people, số assignments)

- Trong trường hợp số people > số assignment -> Ta dùng biến giả (dummy variables) (thường có giá trị = max cost)

- Thuật toán trên dùng cho trường hợp minimum asignment (min cost)

- Từ Konig theorem, số minimum lines (minimum Vertex (đỉnh) cover) sẽ là n (size của maximun matching). Do đó, khi có n lines thỏa mãn, minimum cost assignmnet có thể tìm thông qua chỉ các số 0 trên matrix 

Tham khảo

- https://github.com/facebookresearch/detr

- https://arxiv.org/pdf/2211.12860v1.pdf (coDETR)

- https://arxiv.org/pdf/2005.12872v3.pdf

- https://www.kaggle.com/code/julian3833/detr-detection-transformer-train-0-189/notebook

- https://huggingface.co/facebook/detr-resnet-101

- https://en.wikipedia.org/wiki/Hungarian_algorithm

- https://www.youtube.com/watch?v=FQp9HJSg1zs&ab_channel=AustralianMathematicsCurriculumVideos