みんな大好き物体検出のデファクトスタンダードFaster R-CNNの特許を読んだ

# はじめに
Faster R-CNN[^Ren_nips15] の特許らしいです。

<blockquote class="twitter-tweet" data-lang="ja"><p lang="ja" dir="ltr">各位　Faster R-CNN特許です。ご査収ください。<br>Faster R-CNN patent was granted.<a href="https://t.co/Bxnjz5s1WU">https://t.co/Bxnjz5s1WU</a> <a href="https://t.co/MwAohEN712">pic.twitter.com/MwAohEN712</a></p>&mdash; Yosuke Shinya (@shinya7y) <a href="https://twitter.com/shinya7y/status/950336282395226113?ref_src=twsrc%5Etfw">2018年1月8日</a></blockquote>

わたし、気になります！ということで、どんな感じか翻訳＆解説してみます。

（2018/01/15 追記）弁理士の先生にコメントを頂きましたのでまとめに記載しました！

## Disclaimer
外国出願はあまりしたことがないので米国特許の請求項の読み方に慣れているわけではなく、並列・従属関係が間違っている可能性があります。特に請求項4については、どう読んだのかを文末に記載してありますのでプロの方のコメントお待ちしております=D

また、請求項のみを読んでおり、実施例は見ていません。

## Faster R-CNN
R-CNN, Fast R-CNN, Faster R-CNNについて理解している前提のほうが楽しめると思いますので、下記の神解説をおさらいしましょう。
[Deep Learningによる一般物体検出アルゴリズムの紹介](http://tech-blog.abeja.asia/entry/object-detection-summary)
[論文紹介: Fast R-CNN&Faster R-CNN](https://www.slideshare.net/takashiabe338/fast-rcnnfaster-rcnn)

端的には、下記のような感じです。

- **CNNによるクラス分類**：固定サイズの画像を入力[^1]とし、画像全体をクラス分類する
- **R-CNN**：何かしらの手法（非deep）で大量の物体候補の領域を抽出し、物体候補領域を固定サイズにリサイズしてCNNに入力し、背景クラスを含むクラス分類をすることでCNNを物体検出に応用
- **Fast R-CNN**：物体候補の領域を抽出しCNNでクラス分類するのはR-CNNと同じだが、予め特徴抽出用のCNNにより画像全体の特徴マップを作成しておき、物体候補の領域に対応する特徴マップをRoI Poolingにより切り出すことで特徴抽出を共通化し高速化＋特徴マップを作成するCNNにもbackprop可
- **Faster R-CNN**：Fast R-CNNに対し、物体候補の領域の抽出にCNNベースのRegion Proposal Network (RPN) を利用することで、物体候補領域の高精度化を実現しつつ、真のend-to-end学習を実現

# 特許の内容
では実際に特許の内容を見ていきましょう。請求項毎に、オリジナルの請求項、翻訳した請求項、解説を記載しております。

## 請求項1

> 1. A method comprising: receiving an input image; generating a convolutional feature map; identifying, by a first type of neural network, a candidate object in the input image; determining, by a second type of neural network, a category of the candidate object; and assigning a confidence score to the category of the candidate object, wherein the first type of neural network comprises a translation invariant component configured to: classify an anchor based on overlap with a ground-truth box; and predict a shift and a scale of the anchor.

*入力画像を受け取る工程と、畳み込み特徴マップを生成する工程と、第一のニューラルネットワークによって入力画像中の物体候補を特定する工程と、第二のニューラルネットワークによって物体候補のカテゴリを特定し、物体候補のカテゴリーに信頼度スコアを割り当てる工程とから構成される方法であって、
第一のニューラルネットワークは正解ボックスとの重なりに基づいてアンカーを分類し、アンカーのシフトとスケールを予測するように構成された並進不変な構成要素を更に備えることを特徴とする方法。*

方法クレームです。何かしらのCNNにより畳み込み特徴マップを生成し、Region Proposal Network (RPN) （＝第一のニューラルネットワーク）によりregion proposalを生成し、RPNにより生成されたregion proposalに対し、Fast R-CNN（＝第二のニューラルネットワーク）により物体の検出を行う構成が端的に記載されています。

Wherein以下に、Faster R-CNNの一番の貢献であるRPNの構成が記載されており、正解ボックスとのIoUによってアンカーを選択し、物体候補のスケールと位置のシフトを予測することが記載されていることが分かります。

また、もう１つのポイントとして、「第一のニューラルネットワークは並進不変な構成要素を更に備える」という限定がなされています。これは、文献[^Ren_nips15] に記載の "Translation-Invariant Anchors" の段落の内容であると考えられます。すなわち、既存手法として比較されているMultiBox[^Szegedy_arXiv14] では、画像に対し固定数 (e.g. 800) のアンカーを利用しており、それぞれ異なるパラメータを持つことになります（YOLOv1とかもそうですね）。一方、Faster R-CNNでは、各アンカーは並進不変でパラメータを共有しており、パラメータ数を削減することで過学習のリスクを低減できており、その部分が本発明を特徴づける内容として記載されています。この部分は、Faster R-CNNのPAMI版の論文では下記のように記載されています。

> An important property of our approach is that it is translation invariant, both in terms of the anchors and the functions that compute proposals relative to the anchors.

Heさんはこのhead部分の共通化にはこだわりがあるようで、Feature Pyramid Networks (FPN)[^Lin_cvpr17] 
 においてマルチスケールの特徴マップを利用する場合にも、異なるスケール間でもheadのネットワークの共通化をしています。

## 請求項2
> A method as claim 1 recites, wherein the convolutional feature map is generated by a Zeiler and Fergus model or a Simonyan and Zisserman model deep convolutional neural network.

*請求項1に記載の方法であって、前記畳み込み特徴マップはZeilerとFergusのモデルまたはSimonyanとZissermanのモデルである深層畳み込みニューラルネットワークにより生成されることを特徴とする方法。*

ILSVRC'13の優勝モデルであるZFNetと、ILSVRC'14の２位のモデルであるVGGNetを利用して畳み込み特徴マップを生成するという限定です。こういう限定が意味があるのかは良く分からないですね。私も後ろの方の請求項に○○特徴を利用するとか書いたことはいっぱいありますが…

ちなみにZFNetおよびVGGNetが記載されている理由は、文献[^Ren_nips15] で実際に実験に利用されているからだと思います（逆に実験に利用されていない他の有名モデルは記載されていない）。ということで、MSR(A)における論文公開にかかる特許の出願の何かしらルールや慣習があるのかもしれません。

## 請求項3
> 3. A method as claim 1 recites, further comprising training the convolutional feature map, the first type of neural network, and the second type of neural network using at least one of: stochastic gradient descent; or back-propagation.

*請求項1に記載の方法であって、更に前記畳み込み特徴マップ、前記第一のニューラルネットワーク、前記第二のニューラルネットワークを、確率的勾配降下法または誤差逆伝播法の少なくともいずれかによって訓練する工程から構成されることを特徴とする方法。*

誤差逆伝播法and/or確率的勾配降下法で学習するという限定です。これもどれほど意味があるのか分かりませんが、end-to-endで学習できる点もFaster R-CNNの大きな貢献であり、また学習の仕方も少しポイントがあったりするので、実施例との兼ね合いで重要なのかもしれません。

## 請求項4
> 4. A method as comprising: receiving an input image; generating a convolutional feature map; identifying, by a first type of neural network, a candidate object in the input image, wherein the identifying the candidate object in the input image comprises: generating one or more anchors at a point of the input image; determining an overlap of individual ones of the one or more anchors to a ground-truth box; assigning a label to each anchor of the one or more anchors based at least in part on the overlap; assigning a score to the label based at least in part on the overlap; and identifying the candidate object at the point based at least in part on the score; determining, by a second type of neural network, a category of the candidate object, wherein the first type of neural network and the second type of neural network share at least one algorithm; and assigning a confidence score to the category of the candidate object.

*入力画像を受け取る工程と、畳み込み特徴マップを生成する工程と、第一のニューラルネットワークによって入力画像のある点に1つ以上のアンカーを生成することで入力画像中の物体候補を特定する工程と、前記1つ以上のアンカーのそれぞれと正解ボックスとの重なりを測定する工程と、前記1つ以上のアンカーの各アンカーに前記重なりに基づいてラベルを割り当てる工程と、前記重なりに基づいて前記ラベルにスコアを割り当て、そのスコアに基づいて前記の点の物体候補を特定する工程と、前記第一のニューラルネットワークと少なくとも1つのアルゴリズムを共有する第二のニューラルネットワークによって前記物体候補のカテゴリーを決定する工程と、前記物体候補の前記カテゴリに信頼度スコアを付加することを特徴とする方法。*

独立クレームになっています。請求項1と分けてこのクレームを作っている意図は分かりませんが、相違点としては、後のクレームで限定されるように複数のスケールとアスペクト比を持つアンカーを1つの特徴マップに対し定義する点と、第一のニューラルネットワークと第二のニューラルネットワークがアルゴリズムを共有する点です。

このアルゴリズムの共有というのは恐らくRegion Proposal Network (RPN) とFast R-CNNの2つのネットワークが層を共有することを指しています。方法クレームなのでそのような表現なのでしょうか。PAMI版の下記のSectionの部分です。

> 3.2 Sharing Features for RPN and Fast R-CNN

## 請求項5
> 5. A method as claim 4 recites, wherein the identifying the candidate object in the input image further comprises: identifying an anchor corresponding to a highest score, the highest score corresponding to a percentage of the overlap; shifting the anchor corresponding to the highest score to better define the candidate object; and scaling the anchor corresponding to the highest score to better define the candidate object.

*請求項4に記載の方法であって、前記入力画像中の物体候補の特定は、前記重なり率をスコアとし最大スコアに対応するアンカーを特定する工程と、前記最大スコアに対応するアンカーをシフトすることで物体候補をより正確に定義する工程と、前記最大スコアに対応するアンカーをスケーリングすることで物体候補をより正確に定義する工程とを更に含む方法。*

IoUに基づいて正例のアンカーを特定する部分です。

## 請求項6
> 6. A method as claim 4 recites, wherein the generating the one or more anchors at the point of the input image comprises generating a set of anchor boxes; the set anchor boxes having three scales and three aspect ratios.

*請求項4に記載の方法であって、前記入力画像のある点に1つ以上のアンカーの生成は、3つのスケールと3つのアスペクト比を持つアンカーボックスの集合を生成することを特徴とする方法。*

アンカーの種類を論文の通り、3つのスケールと3つのアスペクト比の9個のアンカーボックスに限定するクレームです。

## 請求項7
7. A method as claim 4 recites, wherein the label is positive when the overlap exceeds a threshold level.

*請求項4に記載の方法であって、前記ラベルは前記重なりが閾値以上となった際に正例となることを特徴とする方法。*

（学習時にロスをかけるために）正解ボックスと一定以上のIoUとなったアンカーが物体候補を検出したとみなす限定です。

請求項8以降もクレームはあるのですが、システムクレーム等の焼き直しなので翻訳はここまでです。

# まとめ
Fast R-CNNからFaster R-CNNへの進化部分（論文のcontribution部分）がミニマムの（＝権利範囲の広い）特許となっており、なるほどーという感じです。Feature Pyramid Networks (FPN)[^Lin_cvpr17] やMask R-CNN[^He_iccv17] 等、Faster R-CNNの進化系は全て権利範囲に含まれますね。YOLOv2やSSD等のSingle Shot系は含まれないと思いますが、逆にこちら系の特許もあるかもですが。

日本出願はあるのでしょうかね。

[@hayahara](https://twitter.com/hayahara) 先生から下記のようなコメントを頂きましたので許可を頂いて転載します。大変参考になります。
（Facebookでのカジュアルなコメントですので、内容を担保するものではありません）

> 私の方で簡単に見たところ、本特許は、米国のみの出願のように思えます。日本国については、PCT（国際特許出願）も分割出願もありません。

> ご指摘のとおり「第一のニューラルネットワークは並進不変な構成要素を更に備える」がポイントとなります。日本特許庁であれば、その「構成要素」を明確にしろ！と言われる恐れがあります。如何にも、米国らしい効果的な記載に見えます。実は、出願人の出願時の落としどころのクレームは、請求項４であった可能性も高いと思います。一方で、請求項１は、勝負クレームであって、とれたらラッキー、だったのではないでしょうか？取れなかったら、請求項１～３を削除する補正だけで済みます。

> 請求項１の「第一のニューラルネットワークは正解ボックスとの重なりに基づいてアンカーを分類し、アンカーのシフトとスケールを予測するように構成された並進不変な構成要素」とは、－＞
請求項４の「第一のニューラルネットワークによって入力画像のある点に1つ以上のアンカーを生成することで入力画像中の物体候補を特定する工程と、
前記1つ以上のアンカーのそれぞれと正解ボックスとの重なりを測定する工程と、
前記1つ以上のアンカーの各アンカーに前記重なりに基づいてラベルを割り当てる工程と、
前記重なりに基づいて前記ラベルにスコアを割り当て、そのスコアに基づいて前記の点の物体候補を特定する工程と」
に対応していますね。
やはり、請求項１の効果的記載で特許が取れれば、ラッキーと考えて、請求項４を抑えとしていたのではないでしょうか？

> 何故、請求項４は、請求項１に従属させなかったか？ということですが、請求項１のwhereinの上段は、従来技術としての意味合いであって、従来技術＋本発明として構成されています。しかし、請求項４の構成では、請求項１のwhereinの上段部分の構成も混ざってしまってうまく記載できないためです。そのために、あえて、請求項４を独立請求項に構成したと思われます。一般的によくやる手法に過ぎず、２つの独立請求項にした意味はないと思われます。


## 請求項4の構造
クレームがどこが並列関係でどこが従属関係になっているのか分かりにくかったです。プロが読めば一意に読めるのだと思いますが、、、

全体としてComprising: A; B; and C. という形だと思うのですが、途中でwhereinが入っていたり、; and ... が入っていたりするので、合ってるか自信がないです。取り敢えず下記のような並列・従属関係だと解釈しました。

- A method as comprising:
    - receiving an input image; generating a convolutional feature map;
    - identifying, by a first type of neural network, a candidate object in the input image,
        - wherein the identifying the candidate object in the input image comprises:
            - generating one or more anchors at a point of the input image;
    - determining an overlap of individual ones of the one or more anchors to a ground-truth box;
    - assigning a label to each anchor of the one or more anchors based at least in part on the overlap;
    - assigning a score to the label based at least in part on the overlap; and identifying the candidate object at the point based at least in part on the score; 
    - determining, by a second type of neural network, a category of the candidate object,
        - wherein the first type of neural network and the second type of neural network share at least one algorithm;
    - and assigning a confidence score to the category of the candidate object.

# 参考文献
[^1]: R-CNN系のコンテキスト前提。FCN＋Global Average Poolingのような構成であれば入力サイズはなんでも良い。
[^Ren_nips15]: S. Ren, K. He, R. Girshick, and J. Sun, "Faster R-CNN: Towards Real-time Object Detection with Region Proposal Networks," in Proc. of NIPS, 2015.
[^Szegedy_arXiv14]: C. Szegedy, S. Reed, D. Erhan, and D. Anguelov, "Scalable, High-Quality Object Detection," in arXiv:1412.1441, 2014.
[^Lin_cvpr17]: T. Lin, P. Dollar, R. Girshick, K. He, B. Hariharan, and S. Belongie, "Feature Pyramid Networks for Object Detection," in Proc. of CVPR, 2017.
[^He_iccv17]: K. He, G. Gkioxari, P. Dollar, and R. Girshick, "Mask R-CNN," in Proc. of ICCV, 2017.