機略戦記

Maneuver warfare

論文ザクッと読み: KNN Matting

そんなに新しい論文でも無いけど、このKNN Mattingという論文が面白かった。

http://cqf.io/papers/KNN_Matting_CVPR2012.pdf

KNN Mattingとは、Image Mattingと呼ばれる画像処理タスクを行う手法の1つである。

そもそもImage mattingとは

全然しらなかったんだけど画像処理のタスクとしてImage Mattingと呼ばれるタスクがあるらしい。

Image Mattingとはどんなタスクなのか?

まず、概要としてはImage Matting画像を背景と前景に分離するタスクだ。 そのために、2つの入力画像を必要とし、処理の結果として1つの画像を返す。

  • 入力
    • その1: Input ... 背景と前景を分離したい画像(下図: 右から2番目)
    • その2: Trimap ... 後で説明する(下図: 一番右)
  • 出力
    • Output ... 前景と背景を分離するalpha image. (下図: 一番左)

f:id:Shinya_131:20171015122803p:plain

InputとOutputはそのまんまだから特に説明は無い。 面白いのはTrimapと呼ばれる入力画像だ。これは通常は人が描いてやらねばいけないもので、3つの色で構成される。

  1. 真っ白な部分 ... 確実に前景であると指定した領域。
  2. 真っ黒な部分 ... 確実に背景であると指定した領域。
  3. 上記以外の灰色な部分 ... 背景であるか前景であるかTrimap作成時には明示しなかった領域。

このTrimapでどこが前景でどこが背景なのか一部分を人が指定してやる事で、残る灰色の部分にある前景と背景の境界を、アルゴリズムが判定してくれるというわけだ。

KNN Matting

さて、前述したようにImage MattingではTrimapの灰色な領域をアルゴリズムが前景と背景に判定してくれる。

判定方法には様々な手法があり、今回読んだ論文ではk近傍法(KNN)を利用しているようだ。残念ながら僕の数学力と英語力ではこれ以上の説明できるほど詳しくは理解できなかった。

KNN Mattingを動かしてみる

さて、素晴らしい事にGithubにKNN Mattingの実装があったので動かしてみた。

  • 1つは、KNN Mattingのauthorの1人であるDingzeyu LiがコミットしているMatlabのコードだ。

github.com

  • もう1つは、どなたなのかは分からないがPythonで実装してくれたコードだ。

github.com

Python版のコードには、オリジナルのMatlab版コードとやや異なる実装になっている部分があるらしい。

Python版コードのリポジトリにあったISSUEよると、

The original code uses an approximate nearest neighbour with two levels of spatial coherence.

だが、Python版ではそうなっていないらしい。

参照: https://github.com/MarcoForte/knn-matting/issues/1

Matlab版の冒頭に、こんな部分があるので、おそらくこの辺りが再現されていないと言うことなんだろう。

% [10;2] means 10 neighbors with default(level) spatial coherence and 
% 2 neighbors with weak spatial coherence.
nn = [10; 2];

https://github.com/dingzeyuli/knn-matting/blob/master/src/knn_matting.m#L3

精度や動作速度にどんな影響があるのかは良くわからなかった。

とにかくPython版を動かしてみる。

f:id:Shinya_131:20171015134644p:plain

動かしてみた。

Core i5を積んだMacBook Proで約1分ほどかかる。 scipy.sparse.linalg.spsolve()してる辺りが重いようである。

他の画像でもやってみよう。 似たような色合いの背景と前景がどこまで上手く分離出来るのかやってみたい。

これは今私が居る部屋においてある机とリモコンである。

f:id:Shinya_131:20171015155920p:plain:w300

こいつ用にTrimapを描いてみる。 かなりざっくり目に。

f:id:Shinya_131:20171015160013p:plain:w300

KNN-Matting...あ、ダメっぽい。

f:id:Shinya_131:20171015160037p:plain:w300

元の画像にAlphaChannelとして統合してみよう。 分かりやすいように背景は青くした。

f:id:Shinya_131:20171015160125p:plain:w300

Trimapをもうちょっと丁寧に書いてもう一度…

f:id:Shinya_131:20171015161513p:plain:w300

f:id:Shinya_131:20171015161604p:plain:w300

んんんー、ちょっと改善したけどダメですね。

他の画像で試してみる。

f:id:Shinya_131:20171015164633p:plain:w300

f:id:Shinya_131:20171015164656p:plain:w300

f:id:Shinya_131:20171015164802p:plain:w300

おお! これはかなり良い。 本の下側の部分が上手く切り取れてないですが、そこ以外は大体キレイですね。

リモコンは背景との色が近すぎるのかな。

よく読んでないけど、元論文によると色空間をRGBじゃなくてHSVにしたら上手く行ったケースが紹介されているようですね。

色空間によっては上手く行ったりするんだろうか。

そういえば、ハイパーパラメーターも全くいじってないですね。 あ、そもそもGithubにISSUとして上げられていたweak spatial coherenceが設定出来ないという問題もありましたね。 この辺りも改善の余地がある可能性が。

補足と感想

今回は、2012年に発表されたKNN mattingを動かしてみたが、その後もこのImage Mattingのジャンルでは色々な手法が検討されているようだ。例えば、DeepLarningでImage Mattingを行う"Deep Matting"とか。

KNN以外の主要や、手法間の比較については、このサイトが参考になる。

Alpha Matting Evaluation Website

この技術については、使い道が色々ありそうであり、気が向いたらまたいじってみようと思う。

scipy.miscにimreadが無いと言われる問題

結論

Pillow ( Pillow: the friendly PIL fork )をインストールすれば治る。

pipを使ってるならこう:

$ pip install Pillow

症状

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-6-f982853d0813> in <module>()
     58     import matplotlib.pyplot as plt
     59     import scipy.misc
---> 60     main()

<ipython-input-6-f982853d0813> in main()
     46 
     47 def main():
---> 48     img = scipy.misc.imread('donkey.png')[:, :, :3]
     49     trimap = scipy.misc.imread('donkeyTrimap.png')[:, :, :3]
     50     alpha = knn_matte(img, trimap)

AttributeError: module 'scipy.misc' has no attribute 'imread'

no attributeと言われる。

原因

Miscellaneous routines (scipy.misc) — SciPy v0.19.1 Reference Guide

Note that Pillow (https://python-pillow.org/) is not a dependency of SciPy, but the image manipulation functions indicated in the list below are not available without it.

との事です。

「目的に縛られずに無駄なことをやる」

ここから先、しばらくの間、「目的に縛られずに無駄な事をやる」というのをやって行きたいと思う。具体的には何に使えるのかハッキリしない技術をちょこっと試してみたりと言うのを趣味として積極的にやっていこうと思う。

まだ役に立つかどうかハッキリしない技術」というのは「役に立たない技術」とは全く違う。先のことは予測するのが難しいから価値がハッキリしていないだけである。

仕事では、目的を達するための手段として技術を使いたい。 だから、趣味として目的に縛られずに色々やっていこうと言うのが今考えている。それは長期的に見ると仕事の助けにもなりそうだと考えている。

発端

ある日こんなツイートが流れてきた。

slack-redir.net

僕が尊敬(というか畏怖)しているエンジニアの方が、このツイートを見て共感を示した上で、「目的に縛られずに無駄なことをやろう」とつぶやいていたのが結構長いこと印象に残っている。

何かの役に立つのかわからない、小さな技術的な試みや実験の類が蓄積して、ノウハウに転化するのだと。

企業も似ている

自分がいくつかのデータ分析プロジェクト、特にKPIの設計などに携わる上で感じたことがある。

それは、投資に対して、「短期的な価値は予測(定量化)しやすい」のに対して「長期的な価値は予測(定量化)しにくい」という事だ。

※ ここでは「投資」はお金だけじゃなくて、人とか時間とか設備とかの投資を含めた意味で使っている。以降も同じ

例えば、

  • 事業における投資について、既存事業への投資はリターンを予測しやすいが、新規事業へのリターンは予測しにくい。とか。
  • 研究開発では、生産設備研究への投資は原価削減効果としてすぐ現れるが、イノベーションのための研究はどのくらいの収益に結びつくのか予測しにくい、とか。
  • ソフトウェア開発の現場で、新機能の追加が売上に与える影響は予測しやすいが、コードリファクタリングによる可読性の向上はどう収益に結びつくのか予測しにくい。とか

もちろん、新規常業への投資も、イノベーションのための研究も、コードリファクタリングも、長期的に見れば収益を生み得る。予測が難しいだけである。

にもかかわらず、定量的に予測可能な範囲でだけ投資先を決めてしまうと、「長期的に見ると最適では無くなる」という事が起きるのでは無いだろうか。

それにどう対処すべきか

予測可能な短期への投資をしなければ、そもそも長期的に存続できない。 そして、予測できない長期にも投資しなければ長期的に見て最適とは言えない。

思いつく対処策として、「投資可能なリソースの内一定枠を長期投資に回す」と言うのが有り得そうだ。その枠の中では、短期的な収益を目指さなくても良い事にする事で予測困難なものに対して投資が行える。

投資可能なりソースを、

  • 時分割で長期に配分すると: Googleにかつてあったと言う20%ルールや、freeeの「巨匠」制度 ( http://type.jp/et/feature/1468 )
  • 組織で分割して長期に配分すると: 大企業がもつ「基礎研究所」という組織

になるのかなと。

最初の話しに戻る

目先に役に立つ事しかやっていないと、長期的に見て良くない気がしたので、あえてすぐには役に立たない事を練習していこう。

Atom + python3.5 type hinting

はじめに

Python3.5以降に導入されたType HintsをAtomで便利に使うための設定についてのメモしておきます。

前提

Type Hintsはプログラムの処理内容に影響を与えない。 その代わり、mypy( mypy - Optional Static Typing for Python )などの静的解析ツールを使って、アノテーション通りの型が渡されているかチェックする事が出来る。

やりたい事

AtomでType Hintsを含むコードを書く時に、

  1. アノテーションと矛盾するコードを書いたらその場で警告を出して欲しい。
  2. Type Hintsを含むコードを正しくSyntax highlightして欲しい。

やり方

要約だけ先に書いておくと、

  1. は、linter-mypy 入れたら出来ました。
  2. は、magicpython 入れたら出来ました。

結果としてこんな感じになりました。

f:id:Shinya_131:20171011231739p:plain

1. Type hintsに基づいた警告をその場で出す。

Linter ( AtomLinter )という便利なツールがあり、このツールを使うと現在editしているソースコードが'規約'に違反していないかチェックして、違反していれば警告を出してくれる。どんな'規約'に従ってチェックをしてくれるのかと言うと、そこはLinter-pluginと呼ばれるplugin次第で色々チェックできて、例えば linter-python-pep8 であれば、PEP8に違反していないかチェックしてくれる。

LinterのMypy pluginを入れれば型アノテーションに対するチェックが出来る。

atom.io

2. Type Hintsを含むコードを正しくSyntax highlightする。

とても残念な事に、Atomに標準で入っているlanguage-pythonが提供するsyntax highlightはType Hintsに対応していない。( ※2017/10/11現在 )

この問題は、language-pythonのISSUE上で2015年6月から議論されている。

Support for Type Hints (PEP484) · Issue #94 · atom/language-python · GitHub

とりあえず結論としては、MagicPythonをインストールしましょう。

atom.io

補足と感想

Atom: language-pythonのType hints対応について: タイトルしか読んでないけど「デフォルトでMagicPython使うようにしよう」みたいな議論が起きてそうです。Replace language-python with MagicPython by 1st1 · Pull Request #13877 · atom/atom · GitHub

Type Hintsについて: 関数の戻り値を説明する時、「listが返る。listの要素としてはstrもしくはNoneが入る」とコメントするより-> List[Optional[str]]と書くほうがずっと簡潔で正確で、しかも機械でチェックする事も出来てとても便利ですね。

R: 複数のvectorやfactorに対してすべての組み合わせを列挙する関数なんだっけ

結論

expand.grid()

解説

library(dplyr)
library(tidyr)

week <- c('月', '火', '水', '木', '金', '土', '日')
am_or_pm <- c('AM', 'PM')

expand.grid(week=week, am_or_pm=am_or_pm) %>%
  arrange(week, am_or_pm)

こうすると、

   week am_or_pm
1    月       AM
2    月       PM
3    火       AM
4    火       PM
5    水       AM
6    水       PM
7    木       AM
8    木       PM
9    金       AM
10   金       PM
11   土       AM
12   土       PM
13   日       AM
14   日       PM

こういう結果が得られる。

R: factor型の変数から「次のlevelのfactor」を得たい

課題

> week <- factor(c('月', '火', '水', '木', '金', '土', '日'), levels=c('月', '火', '水', '木', '金', '土', '日'))
> week
[1] 月 火 水 木 金 土 日
Levels: 月 火 水 木 金 土 日
> monday <- week[1]
> monday
[1] 月
Levels: 月 火 水 木 金 土 日

こういう前提の時に、変数mondayからを得たい。

結論

こうすると取れる。

> week[as.numeric(monday) + 1]
[1] 火
Levels: 月 火 水 木 金 土 日

感想

  • mondayas.numeric(数値にする)って概念的におかしい気がするので、なんかもうちょっと別の書き方ができないものか。

全体最適を行うためには「部分非最適」を受け入れる必要がある

大体の仕事は、いくつかの機械や人、あるいは組織が連携して働いて最終的な成果(製品とかサービスとか)を作る。

このような仕事において、最終的な成果を増やすためには、「改善を行って効果がある部分」と「ない部分」がある事を認識する必要がある。それを分かっていないと改善するつもりで悪化させてしまう事になる。

そのような場合がある事を、いくつかの例とその背後にある原則を使って説明する。

例え話その1: あるパン工場

あるパン工場の生産ラインを想像してみよう。

  1. 小麦粉と水をまぜ、そこにイーストを入れる。
  2. 温めて生地を発酵させる。
  3. パンの形に成形する。
  4. 焼く。
  5. 包装する。
  6. 箱詰めする。

6つの加工機器を経て、パンが完成する一連の工程である。

これらの工程は、以下のように順番に行う必要がある。

1 → 2 → 3 → 4 → 5 → 6

先ほどのパン工場について、1〜6それぞれの工程が処理できる量は異なるものと仮定しよう。つまり、「1. 小麦と水を練る機械は1時間あたりパン110個分の生地を練れる」「4. パンを焼く機械は1時間あたり100個のパンを焼ける」とかだ。

あなたはこのパン工場の生産速度を改善したいものとする。
あなたならどんな基準で改善すべき工程を選ぶだろうか?

さて、このパン工場の1〜6の工程には、改善するとパンの生産量が増える工程と、改善してもパンの生産量が増えない工程とがある。

例えば、2.生地を発酵させる機械が1時間辺り100個分しか処理できないのに、1.小麦と水を練る機械が1時間あたり150個分の生地を練れるようになってもパンの生産量は増えない。2.生地を発酵させる機械の前に発酵待ちパンが積み上がっていくだけである。1時間で150個分練って、100個分しか発酵させられないので、1時間で50個ずつ発酵待ちの生地が溜まっていく。

あるいは、4. パンを焼く機械が1時間あたり120個しか処理できないのに、5. 包装する機械が1時間あたり180個処理できるようになってもパンの生産量は増えない。5. 包装する機械は1時間の内、累計40分だけパンを包装し、残りの時間はパンが焼けるのを待つことになる。

このように、パンの生産量はパン工場どこを改善しても増えるという訳ではないこのような想定の時、パンの生産量を増やすのは、1〜6の中で最も遅い工程に対する改善のみである。

例え話その2: ピクニックに行く小学生達

  • 小学1年生〜6年生までの小学生が1人ずつ、計6人でピクニックに出かけたとする。
  • それぞれが歩く速度は以下としよう。
1年生さん < 2年生さん < 3年生さん < 4年生さん < 5年生さん < 6年生さん
  • ピクニックに出た6人の小学生が皆で一本道を進む時、このピクニック隊が進むスピードはもっとも足が遅い小学生によって決まる。6年生さんが、ちびっこマラソンで3kmを10分で走れる俊足の小学生であっても全く関係ない
  • ピクニック隊全体の速度を上げたい時、いくら6年生さんが歩くスピードを早めても意味が無い。
    • 1年生さん〜5年生さんが置いてきぼりになって隊列が伸びるだけである。
    • 全体のスピードがあるのは、1年生さんが歩くスピードが上がった時だけである。
  • だから、やるべき事は、1番遅い1年生さんの荷物を、その他の小学生さんが肩替わりしてあげる事である。例えば6年生さんが1年生さんの荷物を持ってあげる。こうすれば全体のスピードが上がる。

この時、荷物を肩替わりした6年生さんのスピードは、「6年生さんだけが歩く時」より遅くなるが、それは、全体のパフォーマンスに全く悪影響を与えていない。むしろ、全体のスピードは上がっている。全体を最適するためには部分の非最適を許容しなければならない。

強度と重さ

左右から引っ張られる1本の鎖の紐を想像しよう。「この鎖の強度を決めるのは、鎖の最も弱い部分である。それ以外を強化しても全体の強度は上がらない

ここまで見てきた様々な例のように、「改善した時、システム全体に効果が出るのはボトルネックの部分のみ」という原則に支配される事象を「鎖の強度世界」と呼ぼう。

一方、別の原則が支配する世界もある。例えば「鎖の重さ」だ。これは、全体のどこを重くしても、鎖全体の重さが増す。このような原則に支配される世界を鎖の重さ世界と呼ぶこととする。

大抵の仕事は鎖の強度世界

「鎖の強度世界」「鎖の重さ世界」この違いを産むのは何であろうか。それは、「システムを構成する各要素が連動するかどうか」である。複数の要素が連動して動き、全体として何か役割を果たす。だからそれらの要素の中にボトルネックが生まれ「鎖の強度世界」の原則が働くようになる。相互作用が無ければ「鎖の重さ世界」のように単純な累積によってパフォーマンスが決まる。

大抵の仕事は「鎖の強度世界」の原則に従う、最終成果物を作るまでに複数の物や人が連動しない仕事というのは少ない。

ソフトウェア開発方法論や生産管理への適用

さて、「鎖の強度世界」という世界観に基づいた方法論は様々ある。 (というか、これこそが様々な生産活動の方法論に共通する一般法則なのでは無いかと私は思う)

根本は同じ「ボトルネックへ集中せよ」である。(ただし、「何がボトルネックなのか?」という考え方はぜんぜん違うが…)

「鎖の強度世界」ではボトルネックへの投資だけが価値を持つ。逆に、ボトルネック以外への投資を絞っても全体のパフォーマンスは落ちない。むしろ、ボトルネック以外への投資を絞り、ボトルネックへ再投資することが全体のパフォーマンスの向上に繋がる。

だから、「あらゆる非効率を許さない」というスタンスは、個別最適化であり、全体最適を損なう考え方なのである。

「あらゆる非効率を許さない」というスタンスは、「生地を発酵させる機械が満タンなのにどんどん生地を練る行為」であり、「6年生さんを全速力で走らせる行為」であり、「クリティカルパスを気にしない行為」であり、「価値あるストリーの優先順位を気にしない行為」であり、どうしようもなく間違っている行為なのである。

https://www.amazon.co.jp/%E3%82%B6%E3%83%BB%E3%82%B4%E3%83%BC%E3%83%AB-%E3%82%A8%E3%83%AA%E3%83%A4%E3%83%95-%E3%82%B4%E3%83%BC%E3%83%AB%E3%83%89%E3%83%A9%E3%83%83%E3%83%88-ebook/dp/B0081M7YEE/ref=dp_kinw_strp_1www.amazon.co.jp