1.事の発端 - YOLOv3 by Tflite C++
これまでの取り組みで、Elixirの IOTソリューションである Nerves/rpiで、手書き数字認識 MNISTを動かすことが出来た。MNISTのニューラル・ネットワーク(NN)は Elixirのコードではなく、Portsを介して接続している C++拡張モジュールで実行するように設計にしている。NNのパフォーマンスと、NNの交換容易性を考えた選択である。
と言うことで、お次は物体検出(Object Detection)を動かしてみたくなるのが人情ではないか
新進気鋭のDETR、メジャーなYOLO,SSDと物体検出の Deep NNの選択肢はいくつもあるが、Tensorflow2.0での先駆者がいて、モデルをTensorflow lite(以下Tflite)にサクッと変換できて、C++でパパパッと動かせそうな YOLOv3を選択することにした。紆余曲折はあったが、Việt Hùngさんが公開されているGitHub(参考文献1)を利用することで、Python下ではあるが Tfliteで物体検出するところまで確認できた。
そう、ここまでは良かった‥‥それじゃ、Elixirの C++拡張モジュールにと始めたところで、はたと気づいた。えっ？ YOLOv3って Deep NNのモデルを持って来るだけじゃダメなのか？モデルの出力を Non-Maxmum-Suppressionで加工しないと意味のある結果が得られないのか？そんなの聞いてないよぉ～～。Deep Learningド素人のなせる業である
[*1]
そんな訳で、Elixirの練習がてら Non-Maximum-Suppressionを実験的に書いてみようと思う。
[*1]DETRにすれば Post-processingなんて要らないじゃないかというツッコミは無用です(^▽^;)
2.Non-Maximum-Suppresion (NMS)
YOLOv3-NNモデルが出力する推論結果は、検出すべき物体が含まれていると思われる領域(バウンディング・ボックス/BBOX)のリストと、その物体がそれぞれの分類クラスに属しているとした場合の確からさ(スコア)の表の二つのテンソル(表)のようだ。(下表)
| BBOX(x1,y1)-(x1,y2) | person | bicycle | car | motorbike | ‥ | ||
|---|---|---|---|---|---|---|---|
| 1 | (0.15,0.61)-(0.28,0.90) | 6.8231e-05 | 1.0191e-05 | 1.0669e-01 | 4.0651e-06 | ||
| 2 | (0.15,0.63)-(0.29,0.91) | 3.2955e-04 | 2.3640e-05 | 1.8690e-01 | 4.3996e-05 | ||
| 3 | (0.16,0.61)-(0.30,0.90) | 4.2045e-05 | 1.0668e-05 | 7.1642e-02 | 1.6618e-05 | ||
| ： | |||||||
| 注意)本表はYOLOv3-NNの生の出力データを加工し、NMSで扱い易い形式にしたものである。 |
そう、この段階では未だどの物体(分類クラス)が何処(BBOX)にあるのかは確定していないのだ。試しに YOLOv3-NNが出力した BBOXを描画してみると、案の定あちらこちらに重複した BBOXが描画される。(注ノイズと見做せるBBOXは篩い落とし済み)
そこで、Non-Maximum-Suppression(NMS)の出番である。NMSは分類クラス毎に、あるBBOXがその分類クラスに属するかどうかをスコアの値で判定し、またそのBBOXと重なりが多いBBOXを篩い落とすと言う手順を繰り返すことで、物体(分類クラス)が何処(BBOX)にあるのかを確定するアルゴリズムだ。
例えば、下の写真の dogについて NMSを疑似言語で記述するとこのようになる。
[*]20文字にもなる如何にも高度な手法のような名前のNMSではあるが、私の理解が正しければ単なる優先度付きリストを評価関数IOUでメンテナンスしているに過ぎないようだ‥‥
NMSアルゴリズム
dog_candidates := dogクラスに属すると思われる(BBOX, score)の組を集めリストをつくる.
与えられた score閾値を下回る scoreを持つ組を dog_candidatesから篩い落とす.
dog_list := [] -- 検出結果
while not empty?(dog_candidates) do
highest := dog_candidatesから scoreが最大の組を取り出し、かつリストから削除する.
dog_listに highestを追加する.
for item in dog_candidates do
iou := highestのBBOXとitemのBBOXの重なり度合いを計算する.
if iou >= iou閾値 then
-- itemは hightestと同じ領域と判断
dog_candidatesから itemを削除する. -- hard NMS
end
end
end
return dog_list
NMSの心臓部は、２つのBBOXの重なり度合いを計算する IOU - Intersection over Unionであろう。この評価関数によって、同一の検出物体上に重複するBBOXを一掃しているのである。
IOUの計算は、下式の如く２つのBBOXの交差面積をBBOXの総面積で除したモノだ。単純な交差面積を評価値とせず、このように総面積との比を評価値とすることで、２つのBBOXがぴったりと重なると評価値は 1.0、少しズレると 1.0よりも小さくなり、２つが完全に離れると評価値は 0.0となるといった具合に、BBOXの重なり度合いを巧く表現している。
このIOUを利用して MNSで重複するBBOXを取り除くと、上の写真は下の写真の様になり、dogが緑のBBOXの位置にいると推測結果が得られるのである。めでたしめでたし
3.実装
さあ、ココからが本番だ。上で理解した NMSのアルゴリズムを Elixirで実装してみよう。果たして私の理解に間違いがないか、実際にコードを書いて動かしてみようと言うのだ。まあ、Elixirの練習問題としても良さそうだし‥‥
まず最初に、NMSの優先度付きリストに入れる要素のデータ構造を定義しよう。要素を優先度順に並べるためにスコア(score:)が、またIOUを計算するためにBBOXの外形座標(box:)が必要だろう。さらに、IOU計算を省力化する目的で、BBOXの面積を予め計算して持っておくことにしよう(area:)。
nms.ex/構造体
defmodule Nms do
# candidate features
defmodule BBox do
defstruct score: 0.0, box: [0.0, 0.0, 1.0, 1.0], area: 1.0
end
<略>
end
ある一つの分類クラスについて NMSを実行する関数は下のコードの様になるかな。引数はそれぞれ、
- class - 分類クラス名(atom)
- socres - 次の引数のそれぞれのBBOXが classに属するとした時のスコアのリスト(boxesと同順)
- boxes - BBOXの外形座標(x1,y1)-(x2,y2)のリスト
- areas - 前の引数のそれぞれのBBOXの面積のリスト(boxesと同順)
- threshold - スコアの足切り閾値
- iou_threshold - 同一のBBOXと判定するiou閾値
とする。
関数non_maximum_suppressioの最初のパラグラフでは、scores,boxes,areasの三つのリストから優先度付きリスト candidatesを作っている。三つのリストをEnum.zipで三つ組{score, box, area}のリストに合成し、その中からスコアの足切り閾値を下回る組を捨て、残った三つ組をデータ構造BBoxに変換し、最後に scoreの値で降順に並び変えている。
その次の行では、優先度付きリストcandidatesが空でなければ、関数hard_nms_loopを呼び出し、推測結果の絞り込みを行っている。絞り込んだ推測結果(最終結果)は、引数で与えられた分類クラス名classと共にタプルにして、non_maximum_suppressionの呼び出し元に返すようにした。一方、candidatesが空リストだった場合は、nilを返している。
関数hard_nms_loopは、先にも触れた通り評価関数iouを用いて重複するBBOXを篩い落とし、推測結果の絞り込み、すなわち検出物体とその位置の確定を行っている。優先度付きリストcandidatesの先頭要素highest(スコアが最も高い)を確定リストresultに移し、残りのcandidatesリストから highestのBBOXと重複する要素を篩い落とす。この処理を candidatesが空リストになるまで繰り返している。
余談になるが、関数hard_nms_loopのコード・パターンは、Elixirで繰り返しを行うときの常套パターンの一つだ。
nms.ex/一つの分類クラスについてNMSを行う関数
@doc """
execute non-maximum-suppression for a given class.
"""
def non_maximum_suppression({class, scores}, boxes, areas, threshold \\ 0.0, iou_threshold \\ 1.0) do
# make a list of candidates in descent order of scores,
# and remove those whose scores are less than the threshold.
candidates =
Stream.zip([scores, boxes, areas])
|> Stream.filter(fn {score, _, _} -> score > threshold end)
|> Stream.map(fn {score, box, area} -> %BBox{score: score, box: box, area: area} end)
|> Enum.sort(&(&1.score >= &2.score))
if candidates != [], do: {class, hard_nms_loop(candidates, iou_threshold, [])}
end
defp hard_nms_loop([], _iou_threshold, result) do
# exsit condition
result
end
defp hard_nms_loop([highest|rest], iou_threshold, result) do
# update the list by removing candidates whose iou is greater than the iou_threshold.
candidates =
Stream.map(rest, &if(iou(&1, highest) < iou_threshold, do: &1))
|> Enum.filter(&(&1)) # remove nil
# and repeat again.
hard_nms_loop(candidates, iou_threshold, [highest|result])
end
IOUは定義式の通り。BBOXの面積は事前に計算しているので(area:)、それを使って計算を省力化している。
nms.ex/iou関数
@doc """
Intersection over Union
calculate the iou of the highest box (a) and the other one (b).
"""
def iou(%BBox{box: [bx1,by1,bx2,by2], area: barea}, %BBox{box: [ax1,ay1,ax2,ay2], area: aarea}) do
x1 = if bx1 > ax1, do: bx1, else: ax1 # max(bx1,ax1)
y1 = if by1 > ay1, do: by1, else: ay1 # max(by1,ay1)
x2 = if bx2 < ax2, do: bx2, else: ax2 # min(bx2,ax2)
y2 = if by2 < ay2, do: by2, else: ay2 # min(by2,ay2)
if x1 < x2 && y1 < y2 do
intersection = (x2-x1)*(y2-y1)
union = aarea + barea - intersection
intersection/union
else
0.0
end
end
さて、一つの分類クラスについてNMSを実行する関数non_maximum_suppressionが実装できたので、それを複数の分類クラスに適用できるように上位の関数multi_non_maximum_suppressionを用意しよう。引数は、non_maximum_suppressionの{class, scores}が、
- classs - 分類クラス名(atom)のリスト
- socres - (classes)×(boxes)の２次元のスコア・テーブル
と変わるが、これら以外の引数 boxes,threshold,iou_thresholdは、non_maximum_suppressionのモノと同じだ。また、BBOXの面積areasはここで事前計算する。
処理内容は、Enum.zipで classesとscoresの合成リストをつくり、そのリストの先頭から順次{class,scores}の組を取り出し、関数non_maximum_suppressionを呼んでいるだけだ。
nms.ex/複数のクラスに対しNMSを行う関数
@doc """
run non-maximum-suppression on all classes.
"""
def multi_non_maximum_suppression(classes, scores, boxes, threshold \\ 0.0, iou_threshold \\ 1.0) do
areas = Enum.map(boxes, fn [x1,y1,x2,y2] -> (x2-x1)*(y2-y1) end) # pre-calculation for efficiency.
Stream.zip(classes, scores)
|> Stream.map(&non_maximum_suppression(&1, boxes, areas, threshold, iou_threshold))
|> Enum.filter(&(&1)) # remove nil
end
4.動作確認
ふぅ～ん、実際に手を動かしてみたら、大したコード・ボリュームじゃなかったなぁ
それじぁ、動作確認をしてみようか。It's show time.
Tflite版YOLOv3-NNが吐き出した結果を加工して、入力データ: 分類クラス名リストcoco.names、スコア・テーブルscore.tbl、BBOX外形座標リストboxes.tblを用意した(下記)。スコア・テーブルscores.tblの書式は、column番号が分類クラスのインデックスに、row番号がBBOXのインデックスになるようにスコアを並べている。また、BBOX外形座標リストboxes.tblは、各行が一つのBBOXの外形座標(x1,y1)-(x2,y2)を表している。
coco.names
person
bicycle
car
motorbike
aeroplane
bus
train
truck
boat
：
：
scores.tbl
6.823187868576496840e-05 1.019169667415553704e-05 1.066979691386222839e-01 4.065169378009159118e-06 1.317119858867954463e-05 1.676548505201935768e-03 3.365738302818499506e-05 9.412788748741149902e-01 9.355776273878291249e-05 5.180143034522188827e-06 5.719354885513894260e-05 1.205967510031769052e-05 3.814199544649454765e-06 5.667620644089765847e-05 8.434390963429905241e-08 1.048248350343783386e-07 3.028156470463727601e-06 1.146629801951348782e-05 8.477470146317500621e-06 8.402558705711271614e-06 1.508674631622852758e-05 3.361973767823656090e-06 5.239470738160889596e-06 2.237774651803192683e-06 9.332276817985984962e-07 2.620106442918768153e-06 1.006587262963876128e-05 2.739164131071447628e-07 9.263640095014125109e-06 1.090604746423196048e-05 2.323717353647225536e-06 1.056878045346820727e-05 1.510467768639500719e-06 2.496107481420040131e-05 1.168375092674978077e-06 2.091049509544973262e-06 2.623926047817803919e-05 1.282797256862977520e-05 1.340092808277404401e-06 4.272680962458252907e-05 5.245727265901223291e-07 9.472506644669920206e-05 3.568823103705653921e-06 7.191679287643637508e-07 8.323501106133335270e-07 8.458096999675035477e-06 1.077742581401253119e-05 2.046131385213811882e-06 2.697764830372761935e-05 3.792782445088960230e-05 7.664812983421143144e-06 5.575193790718913078e-05 2.399990989943034947e-05 9.820710147323552519e-06 6.638962986471597105e-06 4.014592923340387642e-05 3.191641735611483455e-05 7.938613998703658581e-05 6.280541856540367007e-05 4.787364105141023174e-06 1.799743586161639541e-05 4.703098511527059600e-06 8.304800758196506649e-06 5.859017983311787248e-05 1.145158307735982817e-06 1.684235598986560944e-06 6.515334098367020488e-05 8.052366865740623325e-06 1.380421872454462573e-05 7.115391781553626060e-06 7.772104254399891943e-06 1.137964318331796676e-06 3.370090416865423322e-05 3.214468961232341826e-05 7.275918392224411946e-07 6.932511041668476537e-06 5.600458052867907099e-07 1.266318122361553833e-06 6.663075282631325535e-07 5.953302206762600690e-06
3.295589413028210402e-04 2.364088322792667896e-05 1.869059354066848755e-01 4.399651515996083617e-05 2.739750198088586330e-05 4.724414553493261337e-03 2.764295786619186401e-04 8.641108870506286621e-01 1.584580022608861327e-04 1.727543349261395633e-05 9.142618364421650767e-05 1.939055073307827115e-05 1.212180541187990457e-05 2.737266186159104109e-04 1.099450855690520257e-06 1.984613618333241902e-06 2.305042471562046558e-05 6.093980482546612620e-05 2.937319368356838822e-05 3.025973637704737484e-05 2.748097722360398620e-05 1.274023179576033726e-05 2.219159796368330717e-05 1.095295556297060102e-05 7.088174243108369410e-06 2.139653406629804522e-05 5.939520997344516218e-05 1.471554810450470541e-06 1.794807758415117860e-05 6.539969035657122731e-05 5.335667538020061329e-06 1.398381664330372587e-05 6.721715180901810527e-06 7.810056558810174465e-05 7.589640517835505307e-06 5.860704732185695320e-06 5.393229002947919071e-05 4.358727892395108938e-05 1.056460223480826244e-05 2.120233257301151752e-04 5.131036232342012227e-06 2.076637028949335217e-04 1.806955333449877799e-05 6.324935839074896649e-06 7.563340204796986654e-06 7.735522376606240869e-05 7.189816824393346906e-05 2.398145443294197321e-05 8.643691398901864886e-05 1.285218895645812154e-04 2.494399632269050926e-05 2.127208717865869403e-04 8.959390106610953808e-05 3.808855763054452837e-05 2.243775088572874665e-05 7.630504114786162972e-05 1.063154704752378166e-04 2.197253343183547258e-04 4.428221145644783974e-04 2.649219459271989763e-05 4.942186205880716443e-05 1.379559034830890596e-05 4.292027733754366636e-05 7.247913890751078725e-05 4.827716566069284454e-06 1.097995027521392331e-05 1.329977676505222917e-04 3.340891635161824524e-05 5.452079858514480293e-05 1.898256596177816391e-05 1.275174327020067722e-05 7.787702998029999435e-06 7.216002268251031637e-05 1.634570508031174541e-04 2.941032107628416270e-06 1.734806028252933174e-05 3.013904915860621259e-06 8.419494406552985311e-06 3.017551762241055258e-06 3.284832564531825483e-05
4.204513606964610517e-05 1.066840559360571206e-05 7.164267450571060181e-02 1.661840178712736815e-05 1.946679403772577643e-04 4.624030552804470062e-03 1.248325133929029107e-04 8.439986109733581543e-01 1.325647899648174644e-04 3.399840716156177223e-05 4.315400292398408055e-05 8.985141903394833207e-05 2.093255352519918233e-05 2.102141443174332380e-04 5.835835850120929535e-07 4.395380130972625921e-07 2.070291156996972859e-05 2.662898987182416022e-05 3.584103069442790002e-06 1.894125307444483042e-05 3.720490713021717966e-05 1.084910672943806276e-05 1.338532729278085753e-05 1.621225601411424577e-05 9.473196769249625504e-06 4.684231498686131090e-06 3.413808371988125145e-05 4.939222890243399888e-06 4.640043698600493371e-05 3.133594873361289501e-05 5.598893403657712042e-05 1.617513626115396619e-04 4.928297585138352588e-06 5.919664545217528939e-05 1.933000203280244023e-05 4.587190232996363193e-06 1.475936878705397248e-04 3.392058351892046630e-05 3.890907919412711635e-06 3.128572425339370966e-04 3.712652187459752895e-06 1.642289571464061737e-04 3.458169157966040075e-05 1.804313069442287087e-05 8.806015102891251445e-06 5.339587733033113182e-05 3.896790076396428049e-06 5.200977284403052181e-06 2.460868017806205899e-05 1.775948476279154420e-05 2.970939021906815469e-05 1.540191005915403366e-04 6.625405512750148773e-05 5.760035855928435922e-05 1.296904974878998473e-05 3.464831024757586420e-05 4.288140044081956148e-04 2.698941680137068033e-04 6.997895980020985007e-05 7.247451321745757014e-06 3.182993532391265035e-05 9.931518434314057231e-06 9.093588596442714334e-05 1.811637048376724124e-04 4.760443516715895385e-06 3.079392990912310779e-05 5.718427200918085873e-05 1.404331851517781615e-04 8.834720210870727897e-05 2.553519880166277289e-05 4.756878843181766570e-05 1.038753543980419636e-05 2.474052598699927330e-04 4.912166623398661613e-04 5.527168923435965553e-06 1.842612800828646868e-05 3.952689439756795764e-06 5.004489139537326992e-06 6.983292223594617099e-06 2.569638127170037478e-05
2.141349978046491742e-04 7.327161711145890877e-06 8.310123533010482788e-02 2.688079439394641668e-05 1.316405832767486572e-04 1.876669470220804214e-03 1.348707883153110743e-04 3.830283880233764648e-01 5.792133379145525396e-05 4.566706775221973658e-05 4.793427069671452045e-05 5.643047188641503453e-05 1.396228526573395357e-05 9.561139449942857027e-05 1.382234700031403918e-06 1.567874733154894784e-06 5.396487540565431118e-05 5.153810343472287059e-05 3.490228664304595441e-06 2.650713577168062329e-05 3.504218329908326268e-05 1.044183227350004017e-05 1.968074138858355582e-05 1.664610681473277509e-05 3.439804640947841108e-05 1.031178908306173980e-05 9.077262802748009562e-05 5.049585524830035865e-06 2.201323513872921467e-05 6.485253834398463368e-05 2.654065065144095570e-05 7.259456469910219312e-05 9.984497410187032074e-06 8.125203021336346865e-05 2.226223114121239632e-05 7.099859431036747992e-06 1.409257820341736078e-04 2.262825728394091129e-05 1.547672945889644325e-05 3.327370795886963606e-04 4.665563210437539965e-06 2.486210141796618700e-04 2.927202694991137832e-05 2.924671753135044128e-05 2.221307295258156955e-05 1.136325299739837646e-04 1.581334618094842881e-05 1.823420097935013473e-05 2.922664316429290920e-05 3.119639222859404981e-05 3.566333180060610175e-05 2.539567358326166868e-04 6.261624366743490100e-05 4.617902959580533206e-05 1.816661097109317780e-05 4.665774031309410930e-05 1.704684109427034855e-04 1.186020672321319580e-04 2.113755908794701099e-04 4.133152287977281958e-06 1.425666232535149902e-05 9.067100108950398862e-06 9.404206502949818969e-05 5.350566425477154553e-05 1.137757317337673157e-05 7.365386409219354391e-05 3.710444434545934200e-05 2.060660335700958967e-04 4.795782297151163220e-05 1.678623448242433369e-05 3.263914550188928843e-05 1.150378648162586614e-05 9.627835970604792237e-05 3.542761260177940130e-04 8.617737876193132252e-06 2.305794987478293478e-05 7.452178579114843160e-06 1.008910658129025251e-05 9.365158803120721132e-06 3.019568976014852524e-05
1.111672972911037505e-04 9.167587161064147949e-01 1.140993026638170704e-05 4.979462391929700971e-05 8.896911936062679160e-07 2.515498817956540734e-05 2.595421028672717512e-05 3.917758294846862555e-05 4.365235799923539162e-04 6.685728948241376202e-08 4.394419011077843606e-05 1.204225213768950198e-06 1.193557864098693244e-06 1.172782413050299510e-05 3.614626109538221499e-07 8.782109034655150026e-06 4.770378291141241789e-05 1.277769229091063607e-06 1.253869072570523713e-06 7.983323513371942681e-08 7.270646307233619154e-08 1.198792176637653029e-07 4.143213345741969533e-07 1.410215986652474385e-06 4.274033472029259428e-06 3.034375004062894732e-05 1.684631570242345333e-06 3.625260802664342918e-08 5.115765816299244761e-05 7.317503786907764152e-06 3.218255733372643590e-05 1.764341703847094323e-07 2.778787120405468158e-07 3.870104592351708561e-06 4.618541140644083498e-07 1.521627979172990308e-07 3.926351382688153535e-06 3.253123168178717606e-06 5.132431851961882785e-06 1.989245816957918578e-07 2.210223613019479671e-07 1.778643422767345328e-06 1.772473069650004618e-06 6.199597635259124218e-08 8.147371204358933028e-07 1.863025858028777293e-07 1.058495581673923880e-05 3.666876580155076226e-07 6.913739980518585071e-07 8.090635674307122827e-06 4.657482577385962941e-07 1.202133375954872463e-06 8.710592425131835626e-08 4.375529533717781305e-05 1.432528051736881025e-07 9.601244954637877527e-08 1.424823312845546752e-05 1.553245709828843246e-07 2.202560426667332649e-05 5.510364076144469436e-07 6.852551905467407778e-06 8.455580768895742949e-07 2.083910715100500965e-07 5.262019158180919476e-07 1.740232136171471211e-08 5.260044844135336461e-08 2.157501739930012263e-06 7.299531201709896777e-09 8.073609336634035571e-08 6.950968963792547584e-05 3.114529079084604746e-07 2.168558467019465752e-06 6.142910024209413677e-06 5.255913038126891479e-08 1.686599148342793342e-06 1.557546625008399133e-06 1.291269995817856397e-06 8.722413014083940652e-08 6.982706395319837611e-07 3.242487082388834096e-06
7.794093107804656029e-05 9.246695637702941895e-01 4.306713162804953754e-05 6.391252827597782016e-05 6.407260570995276794e-07 1.086163829313591123e-04 2.975487223011441529e-05 4.021501808892935514e-05 4.605675057973712683e-04 1.165478664688635035e-07 9.584448707755655050e-05 2.578892463134252466e-06 1.704681949377118144e-06 4.937892663292586803e-05 2.467643014369969023e-07 3.671530294013791718e-06 6.614587618969380856e-06 2.195423576267785393e-06 8.191698270820779726e-07 5.307428097012234502e-08 5.887653742320253514e-08 9.681619417278852779e-08 5.816877433062472846e-07 3.488070206003612839e-06 3.409254986763698980e-06 6.644122186116874218e-05 5.009459982829866931e-06 5.148149995193307404e-08 9.810305346036329865e-05 7.380787792499177158e-06 4.081073711859062314e-05 2.458015728734608274e-07 2.931662095306819538e-07 2.878688746932311915e-06 2.299814468642580323e-06 3.162496966524486197e-07 2.660090331119135953e-06 6.992949238338042051e-06 1.153746416093781590e-05 1.120369802265486214e-06 6.180995342219830491e-07 3.897663191310130060e-06 5.231960585660999641e-06 1.207551036941367784e-07 1.674421355346566997e-06 7.123908858375216369e-07 1.172098563984036446e-05 3.119970415355055593e-07 5.299854137774673291e-07 1.845576298364903778e-05 1.966099318906344706e-07 2.297484343216638081e-06 1.340061572818740387e-07 1.130378313973778859e-05 2.103465135405713227e-07 1.130614393218820624e-07 1.106669005821458995e-04 1.959160869091647328e-07 2.101333848258946091e-05 9.462303296459140256e-07 7.086471305228769779e-05 2.875198788387933746e-06 2.156047429480167921e-07 3.864741699999285629e-07 2.901869677884860721e-08 5.405711078765307320e-08 3.501221044643898495e-06 1.410314709460180893e-08 2.469043636210699333e-07 2.923364227171987295e-04 6.739630862284684554e-07 1.336927743977867067e-05 5.713390419259667397e-05 1.085311112092313124e-07 2.205288183176890016e-06 3.466587713774060830e-06 1.369406959383923095e-06 4.797285768631809333e-08 1.205094235956494231e-06 1.178925867861835286e-05
1.194452215713681653e-05 9.897935390472412109e-01 6.395332547981524840e-06 8.610441000200808048e-06 1.868732368848213810e-07 4.677203378378180787e-06 2.320383373444201425e-06 1.652381070016417652e-05 6.469472427852451801e-04 2.026255785381181340e-08 1.282309858652297407e-05 3.259102356878429418e-07 1.781241536491506849e-07 7.281864236574620008e-05 1.340366395652381470e-07 9.573267561790999025e-06 7.609963067807257175e-04 1.093820287678681780e-06 3.986404806255450239e-07 1.480945321929993952e-08 3.078623223018439603e-08 4.100384742855567310e-08 6.249383233125627157e-08 9.620671335142105818e-07 5.467323262564605102e-06 3.446752816671505570e-05 8.169031389115843922e-07 2.014686728557535389e-08 1.433658471796661615e-04 9.742524525790940970e-06 1.455210585845634341e-04 1.258688229199833586e-07 3.039727118903101655e-07 4.225569227855885401e-06 3.701621835716650821e-07 9.649390619870246155e-08 8.807758604234550148e-06 1.464042270526988432e-06 1.013619839795865119e-05 2.614369165598873224e-08 2.041824487264420895e-08 1.543354102295779740e-07 3.951532789869816042e-07 1.171866159666024032e-08 1.910054834297625348e-07 3.816435523162908794e-08 1.011400286188290920e-06 3.854497876432105841e-08 1.867376653308383538e-07 1.622254217181762215e-06 1.413346950585037121e-07 1.029288370091308025e-07 2.783618491264405748e-08 5.885394784854725003e-06 7.904312759876575001e-09 1.262640658694635931e-08 9.975806278816889971e-06 8.325004614562203642e-07 6.786158792237984017e-06 1.495706783316563815e-06 1.731344468680617865e-06 2.569531716289930046e-07 2.156243823492332012e-07 2.339971274523122702e-07 1.064431032204993244e-08 1.616711031715567515e-08 2.825120191118912771e-06 1.354777734441370285e-09 7.828128900655428879e-08 8.169807188096456230e-06 2.217733907627916778e-07 2.190100531151983887e-06 2.443315224809339270e-06 1.799245552547290572e-08 6.746591907358379103e-07 3.569602426978235599e-07 3.907582311057922198e-07 1.216773526380166004e-08 4.847779564443044364e-07 1.917981307997251861e-06
2.904678467530175112e-06 9.856343865394592285e-01 7.750058102828916162e-06 3.648495066954637878e-06 4.291632649255916476e-08 6.593422313017072156e-06 1.110371613322058693e-06 4.874066235061036423e-06 2.548436168581247330e-04 7.310941629867784286e-09 1.205697753903223202e-05 1.386233634548261762e-07 5.001222902478730248e-08 1.119353619287721813e-04 2.444907032383980550e-08 5.349381240193906706e-07 6.793312877562129870e-06 2.690532880933460547e-07 7.625168763070178102e-08 2.617208894051259449e-09 8.323899791662370262e-09 5.566360261610725502e-09 3.161254369388188934e-08 3.810199871168151731e-07 7.190968744907877408e-07 1.530779991298913956e-05 3.793319081069057574e-07 5.044484829852535768e-09 5.913031782256439328e-05 1.948519411598681472e-06 3.013808964169584215e-05 3.052891628385623335e-08 4.505405826193964458e-08 1.288515591113537084e-06 2.254084705555214896e-07 3.780734303404642560e-08 1.287342570321925450e-06 4.049829840369056910e-07 6.797719834139570594e-06 1.069205435300091267e-08 1.041439645632635802e-08 9.614163332116731908e-08 3.415252081140351947e-07 2.713624436267991769e-09 8.072176171936007449e-08 3.172852558464001049e-08 7.700721198489191011e-07 2.096059681377937522e-08 3.786760061075256090e-08 1.950823161678272299e-06 1.725339515701307391e-08 8.803407069990498712e-08 5.490387700035626040e-09 5.170439294488460291e-07 4.625434257832239382e-09 1.781064518091568516e-09 2.517411303415428847e-05 1.552049013753276085e-07 1.404112481395713985e-06 2.199026539528858848e-06 1.681932008068542928e-05 2.130454106463730568e-07 3.526539771314673999e-08 7.095356124864338199e-08 2.099003193478665708e-09 2.359666684270678161e-09 9.513320833320904057e-07 4.172596712592735457e-10 3.375030033225812076e-08 1.119056469178758562e-05 6.081912573563386104e-08 1.940600668604020029e-06 8.517084097547922283e-06 4.006218468077804573e-09 3.020699921307823388e-07 5.517967451851291116e-07 1.162052001291158376e-07 1.613464695182642572e-09 1.135905165483563906e-07 1.114734459406463429e-06
4.733443347504362464e-05 3.736545145511627197e-02 5.050629170000320300e-06 7.261598511831834912e-05 1.005599756354058627e-06 5.676603905158117414e-06 9.992558034355170093e-07 3.963530252804048359e-05 2.660065656527876854e-04 5.072565727459732443e-07 1.943010829563718289e-05 1.373353143208078109e-06 3.463135726633481681e-06 1.091708691092208028e-04 3.498543810565024614e-05 1.380031649023294449e-02 9.038657546043395996e-01 2.930480695795267820e-05 2.774049971776548773e-05 2.655799789863522165e-06 2.059794041997520253e-06 1.364676882076309994e-05 1.492560272708942648e-06 3.197284604539163411e-05 3.429658245295286179e-04 1.628097743378020823e-05 2.554396360210375860e-06 2.920647375503904186e-06 2.448550367262214422e-05 2.641166793182492256e-05 1.762207684805616736e-04 4.825967153010424227e-06 4.467054168344475329e-06 1.295595029660034925e-05 1.073720909516850952e-06 1.611787524780083913e-06 1.015775196719914675e-04 2.750313251453917474e-05 3.949829260818660259e-05 1.541795199955231510e-06 4.624386562568361114e-08 3.867681357405672316e-07 6.085079462536668871e-08 3.973957234393310500e-07 3.964594270655652508e-06 1.163881933052834938e-07 1.591319050930906087e-05 1.606199020898202434e-06 1.593046135894837789e-06 2.295063836754707154e-07 2.422245233901776373e-05 2.420653970602870686e-07 1.357166752313787583e-06 1.757263817125931382e-04 3.571232696231163573e-07 1.115623604164284188e-06 1.637541936361230910e-05 2.574549944256432354e-05 4.322849054005928338e-05 3.475587436696514487e-05 7.715021638432517648e-06 1.318195791100151837e-05 2.030817086051683873e-06 5.981171398161677644e-06 4.691647461640968686e-07 1.679606839388725348e-06 5.638356469717109576e-06 1.583711224384387606e-07 1.933687826749519445e-06 2.419465636194217950e-05 9.172870250040432438e-07 3.677040012917132117e-06 1.415771521351416595e-06 2.268588559672934934e-06 1.664161027292720973e-05 1.736596857426775387e-07 2.134941723852534778e-06 9.219593266607262194e-06 2.876433882192941383e-06 2.994585656779236160e-06
6.771110747649800032e-07 1.320897717960178852e-05 2.048385283615061780e-08 1.238550026982920826e-07 1.969190588368974204e-09 1.652712455779692391e-08 6.348019332413912252e-10 5.223756005534596625e-08 4.742475994135020301e-07 2.089705519736639872e-09 1.630728405643822043e-07 8.326384914880691213e-09 1.832885487829116755e-08 1.715466453333647223e-07 1.635557509871432558e-06 1.545281731523573399e-03 9.977301359176635742e-01 1.764051262398425024e-06 5.282333404466044158e-06 9.721125024952925742e-07 2.158339924562824308e-07 2.821051339196856134e-06 2.909993312982805946e-08 7.148159397729614284e-07 1.056767928275803570e-06 5.683944337420143711e-08 3.197337861138294102e-08 4.579730372711310338e-08 1.250859469337228802e-07 6.233956355572445318e-07 4.688739920766238356e-07 2.960225486958734109e-08 4.050619395457033534e-08 6.769422356001086882e-08 5.790246060399795169e-09 3.236650059079693165e-08 2.522550175854121335e-06 3.184700858582800720e-07 1.188684848330012755e-07 6.562860477288268157e-09 6.368794380762210494e-10 7.471030016859003808e-09 1.779642405663750537e-10 4.668621045311738271e-09 4.252135710203219787e-08 4.233276229559379544e-10 1.739646933174299193e-07 1.622450263027985784e-08 2.476548388585797511e-07 4.892502514231011901e-10 2.185671519328025170e-07 9.206483353452199481e-10 9.561266978153071250e-08 1.508672266936628148e-05 3.094075751164382382e-08 3.394148251345541212e-08 1.781876619588729227e-07 6.731302164553198963e-07 4.626047314104653196e-07 1.722061597320134751e-06 3.324768726997717749e-08 1.031003620255432907e-07 2.240850349721767998e-08 1.644050584559408890e-08 1.022646056725307062e-08 1.986457576208522369e-08 4.860632074610293785e-08 7.110868005533177438e-10 5.025371052624905133e-08 7.833862980533012887e-08 1.867510768249758257e-08 1.544667185271464405e-07 9.923213362128535664e-09 4.324931079935367961e-09 9.777706111435691128e-08 5.769814626077618414e-10 1.235595359361241208e-08 4.261462720478448318e-07 3.139732740464751259e-08 1.781974212633485877e-08
1.525861898699076846e-05 6.148030515760183334e-04 8.200102001865161583e-07 6.561630016221897677e-06 6.330341051352661452e-08 2.294870995456221863e-07 7.550815084300666058e-09 1.700942220850265585e-06 1.525060270068934187e-05 4.924651619830910931e-08 1.569616756569303107e-06 1.467062702431576326e-07 1.575706676248955773e-07 5.257971224637003615e-06 5.669737220159731805e-06 5.767906084656715393e-03 9.573225378990173340e-01 1.058187262970022857e-05 1.260017324966611341e-05 2.417507857899181545e-06 7.291096153494436294e-07 3.810810994764324278e-06 3.631922140812093858e-07 4.794656433659838513e-06 6.243724783416837454e-05 7.054214279378356878e-07 8.002579647836682852e-07 3.132633139557583490e-07 5.153249730938114226e-06 3.616560888985986821e-06 1.987597170227672905e-05 5.510025857802247629e-07 7.833424433556501754e-07 2.455259618727723137e-06 1.832917320143678808e-07 5.222461822995683178e-07 2.061539817077573389e-05 1.546339149172126781e-06 1.603629016244667582e-06 6.335885416319797514e-08 9.629021135992843483e-09 7.973322624366119271e-08 3.705781015383990962e-09 6.165538479763199575e-08 4.149657115704030730e-07 8.554676966809893202e-09 1.023229401653225068e-06 1.518674110911888420e-07 6.199804829520871863e-07 7.803442336751231778e-09 1.062319256561750080e-06 2.376772911816260603e-08 1.643206246626505163e-07 1.418349165760446340e-05 2.270296874939958798e-07 1.229281707537666080e-07 9.740178938955068588e-06 1.949729812622535974e-05 7.262043709488352761e-06 7.031338464003056288e-05 2.241230504296254367e-06 8.618747528998937923e-07 5.270952101454895455e-07 2.149617444047180470e-07 1.310174440050104749e-07 3.089285200985614210e-07 6.861098995614156593e-07 1.472746280484216186e-08 2.564536600857536541e-07 5.347629894458805211e-07 2.022469942630777950e-07 1.938532250278512947e-06 1.983578954423137475e-07 4.596757321451150347e-07 1.618958435756212566e-06 1.465550347745647741e-08 1.791851786947518121e-07 1.669115590630099177e-06 4.198299734525789972e-07 2.414714117549010552e-07
2.142801167792640626e-05 3.649458813015371561e-05 3.227232582503347658e-06 5.491000592883210629e-06 2.648427255280694226e-07 5.342984081835311372e-07 2.673327159641303297e-08 4.219910465508291963e-07 8.175888979167211801e-06 1.174336148324073292e-07 1.928962547026458196e-06 1.631063639706553658e-07 2.033175405813381076e-07 1.366568540106527507e-05 5.593758396571502090e-05 1.129954215139150620e-02 9.640510082244873047e-01 9.461666195420548320e-06 4.788306250702589750e-05 3.015046240761876106e-05 3.735043037522700615e-06 3.883369208779186010e-05 1.079276444215793163e-06 1.431700911780353636e-05 7.695692147535737604e-06 6.155925348139135167e-06 2.888808921852614731e-06 3.040854380742530338e-06 4.395314590510679409e-06 9.170219527732115239e-06 5.384517407946987078e-06 6.099849088059272617e-07 2.147732629964593798e-06 6.467697403422789648e-06 4.183291082426876528e-07 7.925178238110675011e-07 4.595441350829787552e-05 3.903391188941895962e-06 5.273527676763478667e-06 3.149548319925088435e-07 9.328194749969043187e-08 1.031539014206828142e-07 5.150555537625223224e-08 2.648285715167730814e-07 9.363182016386417672e-07 2.473330482644087169e-07 2.895516672651865520e-06 6.730676318511541467e-07 4.883866949967341498e-06 3.952986560307181207e-08 1.212114625559479464e-06 4.219763383161989623e-08 9.889755574477021582e-07 5.408745710155926645e-05 1.618493342903093435e-06 8.198589966923464090e-07 1.201772101921960711e-05 3.329766332171857357e-05 2.147893428627867252e-05 2.754573943093419075e-04 3.429048956604674459e-05 4.419681317813228816e-06 8.327032219312968664e-07 5.682876462742569856e-07 4.511545341756573180e-07 5.718038664781488478e-07 3.119528173556318507e-06 7.970006521418326884e-08 1.092984234674077015e-06 1.011694848784827627e-06 4.090502443432342261e-07 4.264961535227485001e-05 2.950687303382437676e-07 1.738186625743765035e-07 1.702528948044346180e-06 4.391258912050943763e-08 4.657563579257839592e-07 1.772612995409872383e-05 1.203116653414326720e-06 8.062766596594883595e-07
1.006889797281473875e-04 8.757123351097106934e-01 3.087661025347188115e-05 7.209957402665168047e-05 3.473118795227492228e-06 1.999864180106669664e-04 5.991132638882845640e-05 4.627716771210543811e-05 7.525473833084106445e-03 7.670477231158656650e-08 2.502846200513886288e-06 1.335395722890098114e-07 4.714253520887723425e-07 3.119453367617097683e-06 2.614087861729785800e-06 5.326492100721225142e-06 1.485753182350890711e-05 2.961299287562724203e-06 2.614860932226292789e-06 6.271910990562901134e-08 6.372282967959108646e-08 5.412885073496909172e-08 1.222573246195679531e-06 1.013436758512398228e-06 4.649769778097834205e-07 1.421292199665913358e-05 3.166343844895891380e-07 9.603956385717538069e-08 4.782055839314125478e-06 2.254398168588522822e-06 2.958946424769237638e-05 1.140437149160788977e-07 2.108753960783360526e-06 7.053205990814603865e-06 4.068244834343204275e-07 1.475041671028520796e-07 2.003581585086067207e-06 3.117594587820349261e-06 8.205296580854337662e-06 2.272440440265199868e-07 2.154446519853081554e-06 2.789084874166292138e-06 3.442221441218862310e-06 4.890069149610098975e-08 6.788557698200747836e-07 7.373880066552374046e-07 4.584040198096772656e-06 3.527242142808972858e-07 7.566382578261254821e-07 1.849443719947885256e-06 2.025484207024419447e-07 8.541597935618483461e-07 8.531173278925052728e-08 4.280914072296582162e-05 9.394588573741202708e-08 1.185278453164073653e-08 3.569298314687330276e-06 1.694833784426919010e-08 9.901833982439711690e-05 3.197904447915789206e-07 1.232883187185507268e-05 5.712641950594843365e-07 1.960818281077081338e-07 8.789416483523382340e-08 1.101501325706522039e-07 6.888294024065544363e-08 1.343634608019783627e-06 1.019813300473515483e-08 2.128081710850437958e-08 5.251176480669528246e-05 1.144177531386958435e-06 3.594713689381023869e-06 1.180797198685468175e-06 7.961727988003985956e-07 1.979184889933094382e-05 1.812702294046175666e-06 6.574821895810600836e-07 3.185459718224592507e-08 1.218196075569721870e-06 5.859843099642603192e-07
3.581581404432654381e-05 4.111636281013488770e-01 5.090031118015758693e-05 4.183022247161716223e-05 1.913196683744899929e-06 4.367286164779216051e-04 6.505565397674217820e-05 6.019397915224544704e-05 5.381719674915075302e-03 1.103527154100447660e-07 2.654640411492437124e-06 1.731330172560774372e-07 5.721451543649891391e-07 1.026252812152961269e-05 1.429215444659348577e-06 2.414674554529483430e-06 1.878682496680994518e-06 1.990941427720827051e-06 8.098180614979355596e-07 2.665015053082697705e-08 3.786269076044845860e-08 2.516615182912573800e-08 1.069904215000860859e-06 1.664804585743695498e-06 4.059016589508246398e-07 1.994587546505499631e-05 5.352304697225918062e-07 9.069967887853636057e-08 7.188482868514256552e-06 1.689475652710825671e-06 2.336080251552630216e-05 5.952651349616644438e-08 2.336043507966678590e-06 3.603162895160494372e-06 1.049713773682015017e-06 1.697733154060188099e-07 9.496071129433403257e-07 3.236746351831243373e-06 1.105993669625604525e-05 1.063166791936964728e-06 4.232207174936775118e-06 8.467349289276171476e-06 5.086622422822983935e-06 5.470597841394919669e-08 9.796453923627268523e-07 3.330503659526584670e-06 8.746126695768907666e-06 2.834736960721784271e-07 3.740122451745264698e-07 2.891180656661163084e-06 9.529507138950066292e-08 1.189609861285134684e-06 6.980138778089894913e-08 1.132664328906685114e-05 1.434991929727402749e-07 1.665308069220827747e-08 3.774521610466763377e-05 1.292170281885773875e-08 4.305499533074907959e-05 1.500305870649754070e-07 2.894558929256163538e-05 1.399051939188211691e-06 1.438461225689025014e-07 5.885982901077113638e-08 1.230641544225363759e-07 7.469929386161311413e-08 1.536676677460491192e-06 1.337699195858021994e-08 3.882732357851637062e-08 9.405385935679078102e-05 1.097609128919430077e-06 1.376768705085851252e-05 1.064514617610257119e-05 1.560728378535714000e-06 1.577397233631927520e-05 2.935298880402115174e-06 5.583459028457582463e-07 1.559648232785093569e-08 1.007173750622314401e-06 1.064676553141907789e-06
5.031576802139170468e-05 9.838563203811645508e-01 2.201710049121174961e-05 1.776823773980140686e-05 6.790642714804562274e-07 2.880413921957369894e-05 2.413236416032304987e-06 8.399374564760364592e-06 1.940933614969253540e-02 4.782447859952299041e-08 7.951287557261821348e-07 3.476376164712746686e-08 1.487709937464387622e-07 2.723783836700022221e-05 2.537815589676029049e-06 1.693745798547752202e-05 1.709444622974842787e-04 4.398723376652924344e-06 9.897236168399103917e-07 1.934492566135759262e-08 3.872257536841061665e-08 1.819580219830640999e-08 3.440637783569400199e-07 4.449723292054841295e-07 1.951659214682877064e-06 1.661109126871451735e-05 2.379353958303909167e-07 7.190761408537582611e-08 1.059338956110877916e-05 3.729116315298597328e-06 9.371999476570636034e-05 1.416269554965765565e-07 2.368104333072551526e-06 1.602633892616722733e-05 2.751746421836287482e-07 1.602954711188431247e-07 4.294991413189563900e-06 2.796385615511098877e-06 2.096769276249688119e-05 3.740578335964528378e-08 5.211777533986605704e-07 6.928797233740624506e-07 2.366524086028221063e-06 1.896131784917542973e-08 2.459173344959708629e-07 2.239121954517031554e-07 7.501382128793920856e-07 7.120364386992150685e-08 5.980662649562873412e-07 4.517947331805771682e-07 8.176441212981444551e-08 1.437358889688766794e-07 8.009108398709940957e-08 8.839525435178074986e-06 1.193241416785895126e-08 5.700000027530904845e-09 4.292015091778011993e-06 1.257016180034042918e-07 5.751333810621872544e-05 1.563440150675887708e-06 1.299149516853503883e-06 2.142181614317451022e-07 1.246102243612767779e-07 2.302152957156522461e-08 8.515039695566883893e-08 3.371064849488902837e-08 1.604703811608487740e-06 3.983783081196179410e-09 6.617137504605352660e-09 9.445571777177974582e-06 1.648227112127642613e-06 4.441445071279304102e-06 7.679177542740944773e-07 1.877779425285552861e-07 1.033745957101928070e-05 1.404216050104878377e-06 6.745706286892527714e-07 9.798875488797875732e-09 8.850082053868391085e-07 6.014805080667429138e-07
4.364112101029604673e-05 5.789486169815063477e-01 3.502785693854093552e-05 4.056826128362445161e-06 3.259948755385266850e-07 2.789501922961790115e-05 2.157136123059899546e-06 8.447776963294018060e-06 8.148004300892353058e-03 1.685893558089901489e-08 6.065970410418231040e-07 1.618814415849101351e-08 5.900351141008286504e-08 7.113697938621044159e-05 6.287798441917402670e-07 9.303670367444283329e-07 1.639504603190289345e-06 3.894376447988179279e-07 1.833659979411095264e-07 3.535874704141406255e-09 9.223145802650378755e-09 2.429274337245601600e-09 1.767803325947170379e-07 1.947332179952354636e-07 3.953196028305683285e-07 1.029308441502507776e-05 8.217639191343550920e-08 2.328342141311168234e-08 5.664034233632264659e-06 6.405152248589729425e-07 2.305837188032455742e-05 1.813366523606418923e-08 9.284401016884658020e-07 3.380475845915498212e-06 1.560631517349975184e-07 4.424539667979843216e-08 5.720220883631554898e-07 6.790935458411695436e-07 9.255655641027260572e-06 2.387930031488849636e-08 3.579919791718566557e-07 7.212585728666454088e-07 1.041105406329734251e-06 5.318647744445570424e-09 1.046379409785913595e-07 3.535456869485642528e-07 7.096411422935489099e-07 4.150805921199207660e-08 1.097323334420252650e-07 5.362362003324960824e-07 1.366677349068368130e-08 9.637953013452715822e-08 1.046589481745741068e-08 7.610108241351554170e-07 9.522292288011158234e-09 1.874846944360797352e-09 1.031607007462298498e-05 5.707962102974306617e-08 2.464555109327193350e-05 1.979089802262024023e-06 1.139517735282424837e-05 2.676277404134452809e-07 2.768653040163826518e-08 1.470619537258244236e-08 1.667171112273990730e-08 7.184048023134437244e-09 7.714691037108423188e-07 1.218716239037576088e-09 3.035310447430106251e-09 2.314349876542109996e-05 4.300794103073712904e-07 5.276631782180629671e-06 3.621087898864061572e-06 2.117113808708381839e-07 3.593230303522432223e-06 1.290738509851507843e-06 1.238107785184183740e-07 1.503192348373261211e-09 2.440634432332444703e-07 2.279953719153127167e-07
boxes.tbl
1.511856615543365479e-01 6.153428554534912109e-01 2.890989184379577637e-01 9.019110202789306641e-01
1.515782922506332397e-01 6.369622349739074707e-01 2.914983034133911133e-01 9.129445552825927734e-01
1.673157066106796265e-01 6.111273169517517090e-01 3.002985715866088867e-01 9.048678278923034668e-01
1.645127385854721069e-01 6.411798000335693359e-01 3.034389615058898926e-01 9.078508019447326660e-01
1.953448951244354248e-01 1.388918012380599976e-01 7.106329202651977539e-01 7.521506547927856445e-01
1.766764223575592041e-01 2.121135890483856201e-01 7.258042693138122559e-01 7.428085803985595703e-01
2.178265899419784546e-01 1.523171067237854004e-01 7.500317096710205078e-01 7.421321272850036621e-01
2.025802284479141235e-01 2.075580656528472900e-01 7.541937232017517090e-01 7.400828599929809570e-01
2.678036093711853027e-01 1.437307745218276978e-01 9.143273234367370605e-01 4.166271388530731201e-01
3.867540955543518066e-01 1.593933850526809692e-01 9.441379904747009277e-01 4.168986082077026367e-01
3.703043162822723389e-01 1.772131919860839844e-01 9.397996068000793457e-01 4.504815340042114258e-01
4.266189336776733398e-01 1.524845957756042480e-01 9.704619646072387695e-01 4.128557443618774414e-01
1.419988423585891724e-01 1.470747888088226318e-01 7.585548758506774902e-01 7.488733530044555664e-01
1.517858803272247314e-01 1.534263938665390015e-01 7.402682900428771973e-01 7.910283207893371582e-01
1.842089444398880005e-01 1.317918896675109863e-01 8.087166547775268555e-01 7.512792348861694336e-01
1.741631627082824707e-01 1.594470441341400146e-01 8.007158041000366211e-01 7.781489491462707520e-01
前章で実装した NMSに、上記の入力データを読み込む機能とコマンドラインI/Fを追加したモノが下のコードである。併せて、Windows上で escriptを使用したいので mix.exsにも手を加えている。
nms.ex/NMSコマンドライン・アプリ
defmodule Nms do
@moduledoc """
Non Maximum Suppression (experimental)
"""
# candidate features
defmodule BBox do
defstruct score: 0.0, box: [0.0, 0.0, 1.0, 1.0], area: 1.0
end
##############################################################################
# parameter file loader
##############################################################################
@doc """
load a table with applying the option.
[option] format: formatter function for input.
transposed: transpose the table if it is true.
"""
def load_table(fname, opts \\ []) do
formatter = Keyword.get(opts, :format, &String.trim/1)
transposed? = Keyword.get(opts, :transposed, false)
try do
{ :ok,
File.stream!(fname)
|> Stream.map(formatter)
|> (if transposed?, do: &transposed/1, else: &(&1)).()}
rescue
File.Error -> {:error, fname}
end
end
@doc """
formatter: convert white-spase separated text to the list of float.
it allows the string representation of an integer.
"""
def float_list(line) do
String.split(line) |> Enum.map(&elem(Float.parse(&1), 0))
end
@doc """
formatter: convert text to the atom.
"""
def to_atom(line) do
String.trim(line) |> String.to_atom
end
@doc """
get the transposed table.
"""
def transposed(mat) do
Stream.zip(mat) |> Enum.map(&Tuple.to_list/1)
end
##############################################################################
# output result
##############################################################################
@doc """
put the nms result to the device.
"""
def puts_boxes(device, {class, boxes}) do
IO.puts(device, "#{class}:")
Enum.each(boxes, fn %BBox{box: [x1,y1,x2,y2]} ->
IO.puts(device, "#{x1} #{y1} #{x2} #{y2}")
end)
end
##############################################################################
# Multi Non Maximum Suppression
##############################################################################
@doc """
run non-maximum-suppression on all classes.
"""
def multi_non_maximum_suppression(classes, scores, boxes, threshold \\ 0.0, iou_threshold \\ 1.0) do
areas = Enum.map(boxes, fn [x1,y1,x2,y2] -> (x2-x1)*(y2-y1) end) # pre-calculation for efficiency.
Stream.zip(classes, scores)
|> Stream.map(&non_maximum_suppression(&1, boxes, areas, threshold, iou_threshold))
|> Enum.filter(&(&1)) # remove nil
end
@doc """
execute non-maximum-suppression for a given class.
"""
def non_maximum_suppression({class, scores}, boxes, areas, threshold \\ 0.0, iou_threshold \\ 1.0) do
# make a list of candidates in descent order of scores,
# and remove those whose scores are less than the threshold.
candidates =
Stream.zip([scores, boxes, areas])
|> Stream.filter(fn {score, _, _} -> score > threshold end)
|> Stream.map(fn {score, box, area} -> %BBox{score: score, box: box, area: area} end)
|> Enum.sort(&(&1.score >= &2.score))
if candidates != [], do: {class, hard_nms_loop(candidates, iou_threshold, [])}
end
defp hard_nms_loop([], _iou_threshold, result) do
# exsit condition
result
end
defp hard_nms_loop([highest|rest], iou_threshold, result) do
# update the list by removing candidates whose iou is greater than the iou_threshold.
candidates =
Stream.map(rest, &if(iou(&1, highest) < iou_threshold, do: &1))
|> Enum.filter(&(&1)) # remove nil
# and repeat again.
hard_nms_loop(candidates, iou_threshold, [highest|result])
end
@doc """
Intersection over Union
calculate the iou of the highest box (a) and the other one (b).
"""
def iou(%BBox{box: [bx1,by1,bx2,by2], area: barea}, %BBox{box: [ax1,ay1,ax2,ay2], area: aarea}) do
x1 = if bx1 > ax1, do: bx1, else: ax1 # max
y1 = if by1 > ay1, do: by1, else: ay1 # max
x2 = if bx2 < ax2, do: bx2, else: ax2 # min
y2 = if by2 < ay2, do: by2, else: ay2 # min
if x1 < x2 && y1 < y2 do
intersection = (x2-x1)*(y2-y1)
union = aarea + barea - intersection
intersection/union
else
0.0
end
end
##############################################################################
# CLI main
##############################################################################
@doc """
main of command line interface.
usage: nms [option] <class file> <score file> <box file>
[option] --score: score threshold (0.0..1.0)
--iou: iou threshold (0.0..1.0)
"""
def main(argv \\ []) do
{opts, files, _} = OptionParser.parse(argv, strict: [score: :float, iou: :float, output: :string])
threshold = Keyword.get(opts, :score, 0.0)
iou_threshold = Keyword.get(opts, :iou, 1.0)
output = Keyword.get(opts, :output, "con") ##[CAUTION!:shoz:20/11/08] windows only
result = with \
[class_tbl, score_tbl, box_tbl] <- files,
{:ok, classes} <- load_table(class_tbl, format: &to_atom/1),
{:ok, scores } <- load_table(score_tbl, format: &float_list/1, transposed: true),
{:ok, boxes } <- load_table(box_tbl, format: &float_list/1)
do
{:ok, multi_non_maximum_suppression(classes, scores, boxes, threshold, iou_threshold)}
end
with \
{:ok, predictions} <- result,
{:ok, file} <- File.open(output, [:write])
do
Enum.each(predictions, &puts_boxes(file, &1))
File.close(file)
end
end
end
mix.exs
defmodule Nms.MixProject do
use Mix.Project
def project do
[
app: :nms,
version: "0.1.0",
elixir: "~> 1.10",
start_permanent: Mix.env() == :prod,
deps: deps(),
escript: escript()
]
end
# Run "mix help compile.app" to learn about applications.
def application do
[
extra_applications: [:logger]
]
end
# Run "mix help deps" to learn about dependencies.
defp deps do
[
# {:dep_from_hexpm, "~> 0.3.0"},
# {:dep_from_git, git: "https://github.com/elixir-lang/my_dep.git", tag: "0.1.0"}
]
end
defp escript do
app_name = "nms"
[
main_module: Nms,
shebang: "#! escript \"%~f0\" %*\n",
path: "#{app_name}.bat"
]
end
end
スコアの閾値を0.25、iouの閾値を0.5として実行してみよう。
bicycle 1台、truck 一台、dog 一匹を見つけたようだ。BBOXを画像上に描画してみると‥‥うむ、良さそうだね
C:>mix escript.build
Compiling 1 file (.ex)
Generated escript nms.bat with MIX_ENV=dev
C:>nms.bat coco.names scores.tbl boxes.tbl --score 0.25 --iou 0.5
bicycle:
0.21782658994197845 0.1523171067237854 0.7500317096710205 0.7421321272850037
truck:
0.15118566155433655 0.6153428554534912 0.28909891843795776 0.9019110202789307
dog:
0.3867540955543518 0.15939338505268097 0.9441379904747009 0.41689860820770264
C:>show_nms.py dog.jpg dog.res -c "#00FF00"
5.次の一歩
さて、それらしい結果が得られたので、きっとNMSアルゴリズムに対する理解は合っているであろう。世の中には、Soft-NMSなるモノもあるようだが、当初の目的は達成されたので次に駒を進めよう。
Nervesで YOLOv3を動かすことが本丸のGOALであった。ここでおこなった Elixirによる NMSの実装は、あくまでもアルゴリズムを理解できているかどうかを確かめる実験だ。パフォーマンスetc.はこれっぽっちも考慮していない。C++で実装し直して Elixir拡張モジュールに組み込まねばなるまい‥‥
参考文献
- Implementing YOLO v3 in Tensorflow (TF-Slim)
- 【物体検出】SSD(Single Shot MultiBox Detector)の解説
- End-to-End Object Detection with Transformers (DETR) の解説
おまけ
NMSの実行結果を目視確認するために、BBOXを画像上に描画するユーティリティをPython&Pillowでちょこちょこと書いた。残念ながら、Elixirには手軽に利用できる Graphics/Image processingライブラリは未だ無いようだ‥‥自分で作った方が速いかもな
show_nms.py
# !/usr/local/bin/python
# -*- coding: utf-8 -*-
################################################################################
# show_nms.py
# Description: show nms result
#
# Author: shoz
# Date: Sun Nov 08 23:13:22 2020
# Last revised: Sun Nov 08 23:13:22 2020
# Application: Python 3.7.4
################################################################################
# <IMPORT>
import os,sys
import argparse
import re
from PIL import Image, ImageDraw
# <SUBROUTINE>###################################################################
# Function: load box table
# Description:
# Dependencies:
################################################################################
def load_boxes(fname):
current = None
classes = dict()
with open(fname, "r") as f:
for line in f:
m = re.match(r"([\w ]+):", line)
if m:
current = m.group(1)
classes[current] = []
else:
box = tuple(map(float, line.split()))
classes[current].append(box)
return classes
# <SUBROUTINE>###################################################################
# Function: draw box on image
# Description:
# Dependencies:
################################################################################
def draw_boxes(im, boxes, color='#FFFFFF', width=3):
w, h = im.size
draw = ImageDraw.Draw(im)
for y1,x1,y2,x2 in boxes:
draw.rectangle((int(w*x1), int(h*y1), int(w*x2), int(h*y2)), outline=color, width=width)
# <SUBROUTINE>###################################################################
# Function: draw box on image
# Description:
# Dependencies:
################################################################################
def parse_item(str, color='#FFFFFF'):
m = re.match(r"([\w ]+)(#[0-9A-Fa-f]{6})?", str)
if m:
return m.groups(color)
else:
return None
# <MAIN>#########################################################################
# Function: CLI Main
# Description:
# Dependencies:
################################################################################
if __name__ == '__main__':
parser = argparse.ArgumentParser(description="Gathering changed files")
parser.add_argument('img',
help="image file")
parser.add_argument('tbl',
help="boxes table file")
parser.add_argument('output', nargs='?',
help="output image file")
parser.add_argument('-i', '--items', nargs='+',
help="select item classes")
parser.add_argument('-q', '--quiet', action='store_true',
help="don't show image")
parser.add_argument('-l', '--list', action='store_true',
help="print item classes")
parser.add_argument('-c', '--color', default='#FFFFFF',
help="default color")
parser.add_argument('-b', '--border', type=int, default=3,
help="border width of box")
args = parser.parse_args()
classes = load_boxes(args.tbl)
if args.list:
print(list(classes))
exit()
if args.items:
items = [parse_item(item, args.color) for item in args.items]
else:
items = [(item, args.color) for item in list(classes)]
im = Image.open(args.img)
for item,color in items:
draw_boxes(im, classes[item], color, args.border)
if not args.quiet:
im.show()
if args.output:
im.save(args.output)
# show_nsm.py