takuroooのブログ

勉強したこととか

AtCoder Beginner Contest 139

9/1のABC139は4AC5WAだった。初めてコンテスト中にD問題解けたけど、いつものD問題よりも難易度が低く正解している人が多かった印象。

atcoder.jp

A問題

問題

3文字の文字列が2つ入力されて何文字一致しているかカウントする問題。

自分の回答

単純にループで数えただけ。他の人の回答も同じような感じだった。

s=input()
t=input()
 
cnt=0
for i in range(3):
    if s[i] == t[i]:
        cnt+=1
print(cnt)

B問題

問題

整数A、Bが与えられて、Aを1回加算するという操作を何回繰り返すとBにたどり着くかという問題。しかし、Aを1回加算するという操作を行うたびに合計数が-1される。初期値は1。 なので操作を1回行うと、合計数に A-1 が加算される。

自分の回答

上記操作をループで実行すればいいのだけれどもここで1WAしてしまった。

間違ったコード
def MAP():
    return map(int, input().split())
 
a,b=MAP()
 
t=1
cnt=0
while True:
    t -= 1
    t += a
    cnt += 1
    # このif文がループの先頭になければならない
    if b <= t:
        break
print(cnt)

このコードだとループの中の処理が必ず1回行われてしまう。そのため入力のB(プログラムの変数ではb)が1のときに間違った答えを出力してしまう。

正解したコード
def MAP():
    return map(int, input().split())
 
a,b=MAP()
 
t=1
cnt=0
while True:
    # if文をループの先頭に移動した。
    if b <= t:
        break
    t -= 1
    t += a
    cnt += 1
print(cnt)

ループを抜けるif文をループの先頭に書いて条件を満たしている場合は何もしないで抜けるようにした。
最初からちゃんとwhile t < b:と書いておけばよかった...境界条件は今後注意してしていこうと思う。

他の人の回答みて勉強になったこと

そもそもループしないでも

  • 1回の操作でA-1を加算する。
  • 初期値は1

なので(B - 1)  \div (A - 1) (切り上げる)で答えがでる。切り上げは以下のように書くことができる。

def ceil(x,y):
  return -(-x//y)

print(ceil(b-1, a-1)

C問題

問題

長さNのある数列が与えられて自分 >= 右隣が最大何回続くか?という問題。

自分の回答

1 <= N <= 105 なので単純にループで数えていけばいい。
自分 >= 右隣 ならカウンターを+1する。
自分 < 右隣 ならカウンターをリセットする。
を繰り返していき、カウンターの最大値を求める。

ちなみに与えられる数列がものすごく長い場合、sys.stdin.readline()を使うとinput()より数百msec速くなったことがあるので、こっちを使うようにしている。

import sys

input = sys.stdin.readline

def LIST():
    return list(map(int, input().split()))

N=int(input())
H=LIST()

p=H[0]
cnt = 0
max_cnt = 0
for h in H[1:]:
    if p >= h:
        # 自分 >= 右隣
        cnt += 1
        max_cnt = max(max_cnt, cnt)
    else:
        # 自分 < 右隣
        cnt = 0
    p = h

print(max_cnt)

D問題

問題

ある数列A={1,2,...,N}とそれを並べ替えた数列P={P1,P2,...PN}があって、

A[0] % P[0] = M0
A[1] % P[1] = M1
A[2] % P[2] = M2



を合計していったとき、最大値がいくつになるか?という問題。(%は余りを求める演算子)
Pをどうやって並べるかは自由。

自分の回答

例えば、A={1,2,3,4,5}だった場合、P={2,3,4,5,1}という数列Pを作ると余りの合計が最大値になる。

  • 1 % 2 = 1
  • 2 % 3 = 2
  • 3 % 4 = 3
  • 4 % 5 = 4
  • 5 % 1 = 0

つまり自分より+1大きい数に割ってもらえれば、余りが自分自身になり、それが余りとしての最大値になる。
(4だったら、5(=4+1)に割ってもらえれば、余りは4になる。)

これを考慮すると余りの合計とは1〜N-1の総和ということになる。(上記例だと1,2,3,4を足したものが答え)
1〜Nの総和はガウスの公式で

(N+1)  \times N \div 2

で求めることができる。

...なのだけれどもコンテスト中にいろいろ勘違いしてしてしまって回答が汚くなってしまったので割愛。 綺麗に書けば以下のように2行程度で書ける。

N = int(input())
print((1+N-1)*(N-1)//2)

結果

5WAが効いて茶色パフォーマンス止まりだった。 f:id:takuroooooo:20190908191341p:plain

転倒数とBinary Indexed Treeについて考える

前回のAtCoderのコンテストで転倒数というものが出題された。 atcoder.jp 転倒数というものを知らなかったので転倒数についてまとめてみる。またコンテストの問題をBinary Indexed Treeで解いてどういう処理の流れになっているかを整理する。コンテストの問題はBITを使わなくても解けるがBITを使うと高速に転倒数をカウントできるとのこと。(コンテストのテストケースで7倍速度の差があった。)

転倒数とは

ある数列に関して以下の条件を満たす組の数のこと
「自分より右にあって かつ 自分より値が小さい」

例えば、[3 1 2]という数列Aがあったとする。この数列の転倒数は2になる。 数え方は以下の通り。

数列Aの左端から見ていくと、
* 3からみたときの転倒数は、1と2の2つ
* 次に1から見たときの転倒数は一つもないので0
* 最後の2には右側に数字がないので転倒数は0
ということで転倒数は合計2つになる。

表っぽく表現するとこんな感じになる。
一番上の行が数列になっていて、その下の行が転倒数の組み合わせになっている。

f:id:takuroooooo:20190826083631p:plain

問題B - Kleene Inversion

前回のAtCoderの問題「B - Kleene Inversion」では、この数列AをK回繰り返したときの数列Bの転倒数を求めるというものだった。

先の数列A=[3 1 2]を使って表現すると、
K=1: B=[3 1 2]
K=2: B=[3 1 2 3 1 2]
K=3: B=[3 1 2 3 1 2 3 1 2]
となる。(先ほどの例はK=1のときの転倒数を求めたことになる。)

この問題は解説動画の33分あたりにある通り、数列A内で発生する転倒数2つの数列A間で発生する転倒数を数えることで解くことができる。

www.youtube.com

ここで数列A内で発生する転倒数2つの数列A間で発生する転倒数とはどういうものかを整理してみる。

数列A=[3 1 2]内で発生する転倒数

これは数列A=[3 1 2]の中で数えた転倒数の数のことで、最初の例で数えた転倒数のことを指す。

f:id:takuroooooo:20190826083631p:plain

2つの数列A間で発生する転倒数

これはK=2のときに発生する転倒数の中で2つの数列を跨っているもののこと。
数列A=[3 1 2]を2回繰り返したときの数列[3 1 2 3 1 2]の転倒数の合計は以下のように7つになる。

f:id:takuroooooo:20190826085835p:plain

この中で2つの数列を跨っている転倒数は3つある。
(以下の表の青枠の3つ)

f:id:takuroooooo:20190826090757p:plain

他の4つは、数列A=[3 1 2]内で発生する転倒数のこと。
(以下の表の赤枠)

f:id:takuroooooo:20190826091055p:plain

こうやってみると赤枠はKの数だけ発生することが分かる。
また青枠の数はK=2なら1つ、K=3なら3つ、K=4なら6つというように組み合わせの公式で求めることができる。

2つの数列A間で発生する転倒数というのは数列A=[3 1 2]を降順にソートした状態[3 2 1]の転倒数と一致する。

f:id:takuroooooo:20190826093125p:plain

Binary Indexed Treeによる転倒数のカウントについて考えてみる

転倒数はBITを使ってカウントすることができる。
以下のコードはB - Kleene InversionをBITで解いたもの。言語はPython

MOD = 10 ** 9 + 7
 
 
def MAP():
    return list(map(int, input().split()))
 
 
class BinaryIndexedTree:
    def __init__(self, tree_size):
        self.tree_size = tree_size
        self.tree = [0] * (self.tree_size + 1)
 
    def add(self, i, x):
        while 0 < i <= self.tree_size:
            self.tree[i] += x
            i += i & -i
 
    def sum(self, i):
        s = 0
        while 0 < i:
            s += self.tree[i]
            i -= i & -i
        return s
 
 
def count_inversion(A, max_num):
    bit = BinaryIndexedTree(max_num)
    x = 0
    for i, a in enumerate(A, start=1):
        bit.add(a, 1)
        x += i - bit.sum(a)
    return x
 
 
def main():
    N, K = MAP()
    A = MAP()
 
    tento_int = count_inversion(A, 2000)  # Aの内部で発生する転倒数
    tento_ext = count_inversion(sorted(A, reverse=True), 2000)  # AiとAjの間で発生する転倒数
 
    x = tento_int * K
    y = tento_ext * K * (K - 1) // 2
    print((x + y) % MOD)
 
 
if __name__ == "__main__":
    main()

数列[3 1 2]の転倒数を数える場合、上記コードの標準入力には、

3 1
3 1 2

を与える。

BITについては、Binary indexed treeを参照。

BITメソッド

BIT.add(i,x)

BITはadd(i,x)でインデックスiに値xを登録して、sum(i)でインデックス1〜iまでの累積和を計算するもの。 これをうまく使うと、 sum(i)
「自分と自分より左にある かつ 自分以下の値」
をカウントできる。
自分とはインデックスiのことで、例えばsum(3)は数字1と2と3がそれまで何個登場したか(何回add(i,x)されているか)を計算する。

BIT.sum(i)

これまでadd(i,x)で登録した数字の数をtotalとすると、total-sum(i)
「自分と自分より左にある かつ 自分を超えている値」
をカウントできる。
これは転倒数の定義と同じ意味のことを言っているので、BITで転倒数が求まることが分かる。

count_inversion()

コード中のcount_inversion()が実際にどうやってBITで転倒数をカウントしているかを整理する。
整理しやすいようにBITのサイズを4とする。(コードでは2000になっている。)

BITの最初の状態は 以下のように0初期化されている。
インデックスは1始まりで青マスがBITを表現している。 f:id:takuroooooo:20190826093741p:plain

1回目のループ(数列[3 1 2]の3を処理する)

最初のループでi=1a=3が入り、bit.add(a, 1)を実行するとBITクラスのself.tree

f:id:takuroooooo:20190826094303p:plain

となる。
緑マスは更新されたマス。(1が加算された。)
次に x += i - bit.sum(a)
で転倒数を求めている。

bit.sum(a)は、ループ1回目はa=3なのでbit.sum(3)になる。これは図の赤い数字の総和を返すので0+1=1が返る。

これは先にも触れた通り、 「自分と自分より左にある かつ 自分以下の値」 をカウントした結果になる。これは数列[3 1 2]の赤文字の中で3以下の数字をカウントしたものという意味なので答えは1。

i=1なのでx += i - bit.sum(a)xに0を加算している。
iはこれまでbit.add(a, 1)で登録した数字の総数を意味している。
i - bit.sum(a)「自分と自分より左にある かつ 自分を超えている値」を表しているので、0という結果が合っていることが分かる。([3 1 2]赤文字の中で3を超えている数字はない。)

2回目のループ(数列[3 1 2]の1を処理する)

2回目のループでi=2a=1が入り、bit.add(a, 1)を実行するとBITクラスのself.tree

f:id:takuroooooo:20190826102153p:plain

となる。
1回目のループと同様にx += i - bit.sum(a)で転倒数を求めている。

bit.sum(1)は赤い数字の合計なので1が返る。
これは数列[3 1 2]の赤文字の中で1以下の数字をカウントしたものという意味なので答えは1。

i=2なのでx += i - bit.sum(a)xに1を加算している。([3 1 2]赤文字の中で1を超えているものは3だけなので1つ。)

3回目のループ(数列[3 1 2]の2を処理する)

3回目のループでi=3a=2が入り、bit.add(a, 1)を実行するとBITクラスのself.tree

f:id:takuroooooo:20190826103159p:plain

となる。
1,2回目のループと同様にx += i - bit.sum(a)で転倒数を求めている。

bit.sum(2)は赤い数字の合計なので2が返る。
これは数列[3 1 2 ]の赤文字の中で2以下の数字をカウントしたものという意味なので答えは2。

i=3なのでx += i - bit.sum(a)xに1を加算している。([3 1 2 ]赤文字の中で2を超えているもの3だけなので1つ。)

count_inversionが返す値

3回のループでx=2になっている。
これは数列[3 1 2]の転倒数と一致する。

参考リンク

AtCoder 第一回日本最強プログラマー学生選手権-予選-

8/24にAtCoderで第一回日本最強プログラマー学生選手権-予選-が開催された。学生以外も参加できてレーティングが変化するとのことだったので参加したが、Aしか解けなかった...

atcoder.jp

A問題

問題

1〜M月、1〜D日から構成される高橋暦の中で積の日が何日あるかをカウントする問題。

m月d日としてときの
d _ {10}はdの10の位
d _ 1はdの1の位
とすると、積の日の条件は

  • d _ 1  >= 2
  • d _ {10} >= 10
  • d _ 1 \times d _ {10} =m

となる。

ループして上記条件に該当する日が何日あるかをカウントすればいいだけ。

自分の回答
M,D=map(int, input().split())
 
seki=0
for m in range(1,M+1):
    for d in range(1,D+1):
        str_d = str(d)
        if len(str_d)==2:
            d10 = int(str_d[0])
            d1  = int(str_d[1])
            if d10 >= 2 and d1 >= 2 and d10*d1 == m:
                seki+=1
print(seki)
他の人の回答みて勉強になったこと

10の位と1の位を分割するのにstrで文字列に変換する必要はなく、以下の書き方で変換できる。

d10 = d % 10 # dの10の位
d1 = d // 10 # dの1の位

また組み込み関数divmod()を使うと一行で書ける。

d10, d1 = divmod(d, 10) # (dの10の位, dの1の位)

divmod()を使うと下記のように書き直せる。

M, D = map(int, input().split())
seki = 0
for m in range(1, M + 1):
    for d in range(1, D + 1):
        d10, d1 = divmod(d, 10)
        if d10 >= 2 and d1 >= 2 and d10 * d1 == m:
            seki += 1
print(seki)

B問題

問題

数列AをK回繰り返しものを数列Bとしたとき、数列Bの中に転倒数はいくつあるか。(答えは10 ^ 9 + 7で割った余りで表示する。)

転倒 (数学) - Wikipedia

B問題は時間内に解くことはできなかった... 数列Aの中で発生する転倒数と、繰り返される数列A間で発生する転倒数がありこれらを別々に考えて計算する必要があった。

数列Aの中で発生する転倒数をtento1とすると、
tento _ 1  \times K
となり、

2つの数列A間で発生する転倒数をtento2とすると、
tento _ 2  \times (K \times (K-1)) \div 2
とすることができる。
(K \times (K-1)) \div 2は組み合わせの公式。K個の中から2つ選んだときの組み合わせ数を求めている。

上記2つの結果を足したものがが答えとなる。 (tento _ 1tento _ 2 はループなどで数える。 )

(時間外の)自分の回答
N,K=list(map(int, input().split()))
A=list(map(int, input().split()))
 
MOD=10**9+7
 
def count(A,N):
    arr=[0]*N
    for i, ai in enumerate(A[:-1]):
        cnt=0
        for aj in A[i+1:]:
            if ai > aj:
                cnt+=1
        arr[i]=cnt
    return arr
 
s1=sum(count(A,N))
s2=sum(count(sorted(A,reverse=True),N))
v=K*(K-1)//2
print((s1*K+v*s2)%MOD)

tento _ 1 はs1、tento _ 2 はs2に対応している。

他の人の回答みて勉強になったこと

転倒数を数えるのにBinary Indexed Tree(以下BIT)を使っている人がいた。

フェニック木 - Wikipedia

BITを使うことで転倒数を効率的に数えることができるみたい。
BITはもともと累積和を効率的に数えるためのデータ構造だが、使い方を工夫することで転倒数を数えることにも使えるらしい。

BITについては以下のスライドが参考になった。

www.slideshare.net

「BIT 転倒数」で検索すると色々記事が出てくるので、どういう仕組みなのか調べてみようと思う。

f:id:takuroooooo:20190826071227p:plain

AtCoder始めました

8月5日からAtCoderを始めた。

atcoder.jp

AtCoderとは

AtCoderとはホームページによると

オンラインで参加できるプログラミングコンテスト(競技プログラミング)のサイトです。リアルタイムのコンテストで競い合ったり、約2000問のコンテストの過去問にいつでも挑戦することが出来ます。

というもので、
ざっくり言うと出題される問題の解をプログラムで書いて、どれだけ早く問題を解けたかで競い合うもの。 調べてみるとプログラミングコンテストというものはAtCoderに限らず様々なものが定期的に開催されているよう。

codeforces.com

www.topcoder.com

csacademy.com

定期的に開催されるコンテストに出場して良いパフォーマンスを出すと自分のレート(レベルみたいなもの)が上がっていく仕組みがあり、現在のレートによって色で自分の実力が表現される。
例えば、レートが0以上400未満だと灰色、400以上800未満だと緑色のように400区切りで色分けされている。何色かがその人のある程度の実力を表しており、みんな上位の色になることがコンテスト参加へのモチベーションになっている。

各色がどの程度の実力なのかはAtCoderの中の人がブログでまとめてくれている。 chokudai.hatenablog.com

AtCoderを始めた理由

自分のレベルって他者と比べてどの辺りなのか興味があったので登録してみた。
まだ始めたばかりなのでなんとも言えないが、まだ一番下の灰色なのでまずは茶色を目指してコンテストに継続して参加していこうと思う。

f:id:takuroooooo:20190819223101p:plain

AtCoder登録してから2週間でやったこと

1.過去問解いた

まずはAtCoder Problemsというサイトを使って過去問解いて経験積むのが効果的という記事を見たのでAtCoder Beginner Contestの過去問(主にAB問題)を180問ほど解いた。 f:id:takuroooooo:20190819224042p:plain

2.コンテスト出た

コンテスト出なきゃレート上がらないので参加できそうなやつは出るようにしている。(解ける問題が少なくて順位が低い...) f:id:takuroooooo:20190819224520p:plain

3.人のコード読んだ

自分が解いた問題に関しては他の人がどんなプログラムを書いたのか読むようにしている。これがとても勉強になる。言語としてこういう書き方できるだという発見があったり、問題の解き方が参考になったりすることが多い。

今後やろうと思っていること

以下のQiitaの記事が参考になりそうなのでこれらを読みつつC問題の過去問を解いていこうと思う。

Random Erasing Data Augmentation

Data augumentation関連の論文メモ
図は論文からの引用

目次

概要

入力画像上に所定パラメータに従った矩形領域を生成するRandom Erasingというデータ拡張手法の提案。

f:id:takuroooooo:20190714182748p:plain

論文リンク

https://arxiv.org/pdf/1708.04896.pdf

著者

  • Zhun Zhong †§
  • Liang Zheng §
  • Guoliang Kang §
  • Shaozi Li †
  • Yi Yang §

†:Cognitive Science Department, Xiamen University, China
§:University of Technology Sydney

従来の課題

  • レーニングデータに対して、モデルの重みパラメータが多いと汎化能力が低下し、トレーニングデータに対してoverfittingしてしまう。
  • occlusion は汎化能力に対する影響が強い。しかしocclusionがあるトレーニングデータは少ない。
  • occlusion を施した画像を手動で生成することもできるがコストがかかる上に、occlusionのバリエーションも限定されてしまう。

提案手法

アルゴリズム

Radnom Erasing

  • レーニング中に、入力画像に対して矩形を重畳することでocclusionに対応したデータ拡張を実現する。
  • 矩形を生成するために以下のパラメータを決定する。
    • 矩形を描画する画像上のx,y座標
    • 矩形の幅と高さ
    • 矩形を埋める値
  • 実装が容易。

以下詳細なアルゴリズム

f:id:takuroooooo:20190714182649p:plain

記号 意味
p Random Erasingを実行する確率
S 入力画像の面積
H, W 入力画像の高さと幅
sl, sh 入力画像面積に対する矩形面積の比率のレンジ
r1, r2 画像上に描画される矩形のアスペクト比のレンジ
Se 画像上に描画される矩形の面積
He, We 画像上に描画される矩形の高さと幅
re 画像上に描画される矩形のアスペクト比 He/We
xe, ye 画像上に描画される矩形のxy座標

実験では以下の設定パラメータが一番性能が良いとされている。

  • p=0.5
  • sl=0.02, sh=0.4
  • r1=1/r2=0.3, r2=3.3

結果

f:id:takuroooooo:20190714190201p:plain Classificationの結果。 異なるモデル、データセットにおいてもRandom Erasingを使用することでテストエラーが下がっている。

矩形領域を埋める値

矩形領域をどんな値で埋めるか4パターン実験した。

  1. RGBそれぞれ[0-255]のランダム値を割りあてる。(RE-R)
  2. ImageNetの平均値 [125, 122, 114]。(RE-M)
  3. 全て0。(RE-0)
  4. 全て255。(RE-255)

実験では1のランダム値で矩形を埋める方法が最も性能が良かった。

f:id:takuroooooo:20190714185548p:plain

Object Detectionへの適用

Object Detectionではトレーニングデータに物体の位置情報(bounding box)があるので、論文では3つの方法が実験されている。

  1. 矩形を描画する位置を画像全体から選択する。(IRE)
  2. 矩形を描画する位置をbouding box内から選択する。(ORE)
  3. 1と2を組み合わせる。(I+ORE)

f:id:takuroooooo:20190714185901p:plain

実験では3の方法が最も性能が良かった。 f:id:takuroooooo:20190714185136p:plain

自分の実装

github.com


You Only Look Once: Unified, Real-Time Object Detection(CVPR2016)

ObjectDetection関連の論文メモ
図は論文からの引用

目次

概要

従来の2stageの物体検出手法とは異なり、バウンディングボックス予測とクラス認識を同時に行い、リアルタイムに動作するsingle networkの提案。

論文リンク

https://arxiv.org/pdf/1506.02640.pdf

著者

  • University of Washington
    • Joseph Redmon
    • Santosh Divvala
    • Ali Farhadi
  • Facebook AI Research
    • Ross Girshick

従来の課題

  • 従来手法で性能が高いR-CNN系は構成が2stageになっているため速度が遅い。
    • まずオブジェクトが存在しそうな領域を抽出し、抽出した各領域をに対してクラス分類を行う。
    • 抽出した領域の数だけCNNを動作させるので処理時間が長くなる。

提案手法

ネットワーク構成

f:id:takuroooooo:20190629183925p:plain

  • 24層のConv layers + 2層のfully connected layers
  • 活性化関数は、最終層以外はleaky ReLUを採用
  • 解像度が高い方が物体検出に有利になるので入力は448x448

検出方法

f:id:takuroooooo:20190629185707p:plain f:id:takuroooooo:20190629184603p:plain

  • 入力画像をSxSのグリッドに分割(論文では7x7)
  • 各グリッドに対してB個のバウンディングボックス情報を予測。バウンディングボックス情報は座標(x,y,w,h)とオブジェクトの中心座標を含んでいるかのスコアで構成される。
    • xとyはグリッドの左上からバウンディングボックスの中心座標までのオフセットを表現(レンジは0-1)
    • wとhは入力画像のWidthとHeightで正規化されたバウンディングボックスの大きさを表現(レンジは0-1)
    • スコア=Pr(Object) * IOUtruth-pred 物体が存在しない場合はスコア=0
  • 各グリッドのクラスの確率を予測。
    • 1つのグリッドにつき1つのクラスしか割り当てられない。
  • Non-maximal suppressionによって重複したバウンディングボックスを削除

ロス関数

f:id:takuroooooo:20190629185958p:plain

  • ロス関数は計算が簡易な二乗誤差を採用
  • 大きなバウンディングボックスのずれよりも小さなバウンディングボックスのずれのほうが重要。なので、wとhは平方根で誤差を計算する。平方根を使うことで大きい値のときの誤差が小さくなる。
  • 論文ではλcord=5 λnoobj=0.5を設定。これはほとんどのグリッドにオブジェクトの中心が含まれないため、オブジェクトの中心が含まれないロスの影響を小さくするための対策。

結果

f:id:takuroooooo:20190630121727p:plain f:id:takuroooooo:20190630121745p:plain f:id:takuroooooo:20190630121753p:plain

  • Fast R-CNNと比べてlocalization errorが高いが、background errorが低い。
  • Fast R-CNNは画像の一部分だけで推論するのに対して、YOLOは画像全体を見て推論するためackground errorが低くなる。

f:id:takuroooooo:20190630121936p:plain

参考リンク

Introduction to YOLO detection model

Spatial Pyramid Pooling in Deep Convolutional Networks for Visual Recognition

論文メモ
図は論文からの引用

目次

概要

入力画像のサイズによらず、固定サイズの特徴マップを出力するspatial pyramid poolingの提案。

論文リンク

https://arxiv.org/pdf/1406.4729.pdf

著者

  • Kaiming He
  • Xiangyu Zhang
  • Shaoqing Ren
  • Jian Sun

従来の課題

  • CNN(convolutional layers + fully-connected layers)の入力画像のサイズは固定である必要がある。(fully-connected layerの入力次元が固定のため)
  • これを回避するために入力画像に対してcropやwarpが使用されるが、これらの処理を行うことで入力画像のオブジェクトが欠けてしまったり歪みがでてしまう弊害が発生する。

提案手法

f:id:takuroooooo:20190623175933p:plain

  • spatial pyramid pooling layerは任意のサイズの特徴マップを出力することができる。
  • convolutional layersとfully-connected layersの間にspatial pyramid pooling layerを配置することで任意のサイズの画像を入力することができる。
  • 図では、spatial pyramid pooling layerは1x1, 2x2, 4x4の複数スケールの特徴マップを出力している。(multi-level pooling)
  • multi-level poolingを使うとオブジェクトの変形や空間レイアウトに対してロバストになる。

結果

f:id:takuroooooo:20190623210714p:plain

single-sizeトレーニングは224x224のみで学習
multi-sizeトレーニングは224x224と180x180で学習
テストはどちらも224x224で行う。

実装

github.com