Online Hough forest tracking with graph matching 2015.07.15 Ilchae Jung

목차 On-line hough forest with tracking Hough forests for multi-parts +graph matching experiment

hough forest

Preliminary Inputs of Hough forests for training and testing Define a patch as 𝑃 𝑖 = 𝐼 𝑖 , 𝑐 𝑖 , 𝑑 𝑖 𝐼 𝑖 : the feature channels of patch 𝑐 𝑖 : the class label 𝑑 𝑖 : the offset to center 이미지에서 뽑은 패치들은 피처 채널들과 클래스 레이블, 패치의 센터에서 오브젝트의 센터까지의 오프셋으로 정의됩니다. 패치의 크기는 저 같은 경우 16 x 16입니다. 패치는 다양한 피처 채널들을 갖고 있습니다. 타겟의 바운딩 박스 안에서 파지티브 패치가, 그 외에서 네거티브 패치가 추출됩니다. 무의미한 보팅을 피하기 위해 네거티브 패치는 오프셋을 갖지 않습니다. Bounding Box |G| G. Hist. LUV

Training Hough Forests Training Data Subsampling with replacement Subsets (찬미 질문) 트리로 나눈다는게 한 바운딩박스에서 온 패치들을 트리에 묶은건지? 트래킹에서 같은 object의 셋임? 트리는 어떻게 만드는지 다시 자세히 볼것 Split function 𝑓 𝜃 is stored , 𝑇 1 𝑇 2 𝑇 𝐾 Class distribution & Offset

The hypothesis for object location 𝐱 Testing Hough Forests Testing data Mean과 variance를 갖고 있어서 , , , 𝑇 1 𝑇 2 𝑇 𝐾 𝑝 ℎ(𝐱) 𝑃 𝑖 = 1 𝑇 𝑇 𝑘 𝑝(ℎ(𝐱)| 𝑇 𝑘 ) = 1 𝑇 𝑇 𝑘 𝑝 ℎ(𝐱) 𝑐, 𝑇 𝑘 𝑝 𝑐 𝑇 𝑘 The hypothesis for object location 𝐱 Come from offsets Class probability

Hough Forests for On-line Tracking Predict the location of target at following frame Check the confidence of the prediction Update Hough forests by using the tracked target 𝐹= 𝑘∈𝐾 𝑇 𝑘 Time Time 𝐹= 𝑘∈𝐾 𝑇 𝑘 Prediction Output 𝑇 1 , 𝑇 2 ,…, 𝑇 𝐾 Update forests Reliable? Yes

Predict Location of Target Reliable? 𝑇 1 , 𝑇 2 ,…, 𝑇 𝐾 Update forests 𝐹= 𝑘∈𝐾 𝑇 𝑘 Prediction Each patch arrives at a leaf node Hough votes are accumulated in Hough space The target is located by performing Non-maximal suppression in Hough space 이렇게 학습된 포레스트를 테스팅 타임에 사용할 수 있습니다. 캔디데이트 윈도우에서 랜덤하게 추출된 패치들을 포레스트에 입력으로 사용합니다. 각 패치에 대해 허프 포레스트는 클래스 디스트리부션과 오프셋을 반환합니다. 이를 갖고 이미지와 동일한 크기를 갖는 호프 보팅 맵에 패치로부터 오프셋만큼 떨어진 곳에 클래스 디스트리뷰션과 오프셋으로 만들어진 웨이트만큼 보팅합니다. 그 결과 오른쪽과 같은 호프 보팅 맵이 생성됩니다. (찬미)호프 보팅맵이 prediction한 location인듯! Hough vote 𝑝 ℎ(𝐱) 𝑃 𝑖 Use value as confidence 𝑐 Accumulate

Check Confidence of Prediction Reliable? 𝑇 1 , 𝑇 2 ,…, 𝑇 𝐾 Update forests 𝐹= 𝑘∈𝐾 𝑇 𝑘 Prediction Hough vote of target location can serves as confidence 𝑐 Compare the confidence 𝑐 by current HF with the confidence by initial HF 𝑐 0 Three conditions (i) Reliable if 𝑐>𝛼 ∙𝑐 0 , update & target tracked (ii) Ambiguous if 𝛼 ∙𝑐 0 >𝑐>𝛽 ∙𝑐 0 , no update & target tracked (iii) Unreliable if 𝑐<𝛽 ∙𝑐 0 , no update & target missing C. Leistner et al. Improving classifiers with unlabeled weakly-related video. In CVPR, 2011.

Proposed Random Tree , We call leaf node information as statistics Fix! We call leaf node information as statistics An internal node maintains own statistics and two 2×𝑉 tables which store statistics of children candidates Columns of the table represent the binary tests Rows of the table represent proportion of positive and negative data 제가 제안한 방법은 단순히 의미 없는 스플릿을 하는 노드를 고치는 것이지만 기존의 문제점들을 한번에 해결하였습니다. 스플릿이 의미가 없는 이유로는 데이터가 부족하여 잘못 학습된 것도 있지만 시간에 따라 데이터가 변한 것도 있습니다. 𝑓 Θ 1 𝑓 Θ 2 𝑓 Θ 𝑉 𝑝 n 𝑝 p , and For left child node For right child node

Update Tables Binary Tests are applied to each patch arrived at the node 모든 인터널 노드는 이제 리프 노드가 가지고 있던 정보와 함께 모든 바이너리 테스트에 대한 자식 노드에게 물려줄 정보들을 저장하고 있는 테이블을 갖고 있습니다. 자식이 두 명이므로 두 개의 테이블을 갖게 됩니다. 노드에 도달한 패치에 서로 다른 바이너리 테스트들을 적용하여 테이블의 셀을 업데이트 합니다. 테이블의 셀에는 클래스 디스트리뷰션과 같은 스테티스틱스 들을 저장합니다. (찬미) patch에 대해 f 기준으로 오른쪽/왼쪽 probability를 높인다 𝑓 Θ 1 𝑓 Θ 2 𝑓 Θ 𝑉 𝑝 n 𝑝 p For left child node, 𝑓 Θ 1 𝑓 Θ 2 𝑓 Θ 𝑉 𝑝 n 𝑝 p For right child node,

Grow Tree Again Keep tables after node split Collect data continuously 𝒑𝒖𝒓𝒊𝒕𝒚= 𝒊 𝒄 𝒑 𝒄 𝑷 𝒊 𝒍𝒐𝒈⁡(𝒑(𝒄| 𝑷 𝒊 ) Keep tables after node split Collect data continuously Correct meaningless split Keep watching class purity and offset variance Other binary test is chosen!! 노드 스플릿을 한 후에도 인터널 노드는 계속해서 스테티스틱스 테이브를 유지하고 있습니다. 그리고 데이터가 매번 업데이트 되는 와중 더 유의미한 스플릿을 하는 바이너리 테스트가 선택될 경우 다시 스플릿을 수행합니다. 그 결과 서브 트리들은 모두 제거됩니다. 여기까지하면 온라인 어뎁테이션도 가능하지만 테이블리 많은 데이터로 인해 세츄레이션되ㅡㄴ 문제가 있습니다. Propagate statistics Propagate statistics again Child node create empty tables Child node can be split

Forgetting function At a node, weight 𝜂 + of 𝑁 𝑘 + positive data arriving in the 𝑘-th 𝜂 + = 𝑘=−∞ 𝑘 0 𝑁 𝑘 + 𝜏 𝑘 0 −𝑘 𝜏: learning rate 𝑘 0 : current order Weight of negative data is calculated in same way (찬미)처음부터 다 하는건가? –무한대 부터 시작하는거 뭐징 ….

Limitation Weakness for non-rigid object Voting vectors Non-maximal suppression

Online hough forest with graph matching OHF0 OHF1 OHF2 OHF3 Tracking with top K matching

+Graph matching

Introduction of graph matching Finding matches between two GRAPHS yia= 1 if node i in G corresponds to node a in G’ yia= 0 otherwise Slide from “Learning Graphs to Match”, Minsu Cho, Karteek Alahari, and Jean Ponce,ICCV 13

Introduction of graph matching Maximizing the matching score S Slide from “Learning Graphs to Match”, Minsu Cho, Karteek Alahari, and Jean Ponce,ICCV 13

Introduction of graph matching How to measure the matching score S ? Each node & each edge has its own attribute Node similarity function Slide from “Learning Graphs to Match”, Minsu Cho, Karteek Alahari, and Jean Ponce,ICCV 13

Introduction of graph matching How to measure the matching score S ? Each node & each edge has its own attribute. Node similarity function Edge similarity function Slide from “Learning Graphs to Match”, Minsu Cho, Karteek Alahari, and Jean Ponce,ICCV 13

Introduction of graph matching How to measure the matching score S ? Sum of SV and SE values for the assignment y Slide from “Learning Graphs to Match”, Minsu Cho, Karteek Alahari, and Jean Ponce,ICCV 13

Introduction of graph matching How to measure the matching score S ? Slide from “Learning Graphs to Match”, Minsu Cho, Karteek Alahari, and Jean Ponce,ICCV 13

Graph matching detail 𝑠.𝑡 𝑊 𝑖𝑎;𝑗𝑏 = 𝑆 𝑉 𝒂 𝑖 , 𝒂 𝑎 ′ =0 𝑖𝑓 𝑖=𝑗, 𝑎=𝑏 𝑆 𝐸 𝒂 𝑖𝑗 , 𝒂 𝑎𝑏 ′ =exp⁡(−𝑑𝑖𝑠𝑡( 𝑎 𝑖𝑗 , 𝑎 𝑎𝑏 )) 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 𝒈𝒓𝒂𝒑𝒉 𝒎𝒂𝒕𝒄𝒉𝒊𝒏𝒈 𝒘𝒊𝒕𝒉 𝒑𝒐𝒘𝒆𝒓 𝒎𝒆𝒕𝒉𝒐𝒅 𝒊𝒏𝒑𝒖𝒕:𝑾 ∈ 𝑹 𝒏 𝒕 𝒏 𝒔 × 𝒏 𝒕 𝒏 𝒔 𝒐𝒖𝒕𝒑𝒖𝒕 :𝒗𝒆𝒄𝒕𝒐𝒓 𝒂 𝑎=𝑟𝑎𝑛𝑑 𝑛 𝑡 𝑛 𝑠 , 1 ; 𝑤ℎ𝑖𝑙𝑒 𝑐𝑜𝑛𝑣𝑒𝑟𝑔𝑒 𝑎=𝑊∗𝑎 𝑓𝑜𝑟 𝑖=1: 𝑛 𝑠 𝑓𝑜𝑟 𝑗=1: 𝑛 𝑡 𝑎 𝑖,𝑗 = 𝑎 𝑖,𝑗 𝑠𝑢𝑚 𝑎 𝑖,: 𝑒𝑛𝑑 𝑓𝑜𝑟 𝑒𝑛𝑑 𝑓𝑜𝑟 𝑒𝑛𝑑 𝑤ℎ𝑖𝑙𝑒

Experiment jeany OHF OHF+GM 70 59 19 34 13 16 71 62 6 50 52 33 45 44 47 53 61 7 9 35.7 38.5

Discussion 1. 초기 part 설정에 대한 고찰 2. 일부 part의 실패 3. Geometric feature로 vector-between-centers는 바람직하지 않다