takminの書きっぱなし備忘録 @はてなブログ

主にコンピュータビジョンなど技術について、たまに自分自身のことや思いついたことなど

主成分分析で直線フィッティングの導出

Tips コンピュータビジョン

先日こんなツイートをしました。

絵にするとこんな感じです。

f:id:takmin:20200917000054p:plain
直線フィッティング

それに対してありがたいことに、いくつか反応をいただきました。

主成分分析でできるという回答を複数からもらいました。

自分でも色々と試してみたところ、導出に成功しました。

というわけで、せっかくなので僕が試した方法をメモしておきます。

尚、今回このようなリプライもいただきましたが、まだこちらの内容は追えてません。

n個の点 (x_i,y_i)が与えられた時、これに最もフィットする２次元平面上の直線 ax+by+c=0を求めるものとします。 まずはn個の点 (x_i,y_i)の重心を求め、それが原点となるように各点を (x^\prime_i , y^\prime_i)へ移動します。


\begin{pmatrix}
x'_{i}\\
y'_i
\end{pmatrix}
=
\begin{pmatrix}
x_i\\
y_i
\end{pmatrix}
-
\begin{pmatrix}
\bar{x}\\
\bar{y}
\end{pmatrix}

ここで (\bar{x},\bar{y})は点群の重心です。


\begin{pmatrix}
\bar{x}\\
\bar{y}
\end{pmatrix}
=\frac{1}{n}\sum_{i}^{n}
\begin{pmatrix}
x_i\\
y_i
\end{pmatrix}

最初にこの重心移動した (x^\prime_i , y^\prime_i)の点群に対して最もフィットする直線 a'x+b'y+c' =0を求めることを考えます。

\sqrt{a'^{2}+b'^{2}} =1とすると、点 (x^\prime_i , y^\prime_i)とこの直線までの距離は、

\left| a^\prime x^\prime_i + b^\prime y^\prime_i + c^\prime \right|

で表せます。（どうしてかわからない人は自分で導出してみましょう。）

したがって、

 
\bf{A}=\begin{pmatrix}
a'\\
b'
\end{pmatrix}
,~~~
\bf{X}=\begin{pmatrix}
x'_1&y'_1\\
x'_2&y'_2\\
{\vdots}&{\vdots}\\
x'_n&y'_n
\end{pmatrix}

とした時、最もフィットする直線を求めるには、 f(\bf{A}, c') = \left( \bf{X} \bf{A} + c' \bf{1} \right) ^T \left( \bf{X} \bf{A} + c' \bf{1} \right) を最小化する \bf{A}を \bf{A}^T \bf{A} = 1 の条件の下で求めることになります。

尚、 \bf{1}は要素がすべて１の n\times 1ベクトルです。

さて、このようにある拘束条件のもとで最小化を行うような問題はラグランジュの未定乗数法を使って解くことができます。 つまり

F(\bf{A}, c', \lambda) = \left( \bf{X} \bf{A} + c' \bf{1} \right) ^T \left( \bf{X} \bf{A} + c' \bf{1} \right) - \lambda \left( \bf{A}^T \bf{A} - 1 \right)

と置き、 \frac{\partial F}{\partial \bf{A}} = \frac{\partial F}{\partial c'} = \frac{\partial F}{\partial \lambda} = 0 となる \bf{A}および c'を求めます。

まず \frac{\partial F}{\partial c'}=0は

c' = -\frac{1}{n}\bf{1}^T\bf{X}{A}

と求まります。 ここで \bf{X}は重心が原点のため、 \bf{1}^T\bf{X} = 0となるので、

c' = 0

となります。 次に \frac{\partial F}{\partial \bf{A}} = 0 は、計算すると、

\bf{X}^T\bf{X}\bf{A} = \lambda \bf{A}

となります。すなわち、 \bf{X}^T\bf{X}の固有ベクトルを求めれば \bf{A}が求まることになります。 ここで \bf{X}^T\bf{X}は共分散行列なので、共分散行列の固有値問題＝主成分分析を行っていることと同じであることがわかりました。

さて、ここで固有値が最も大きい固有ベクトル（第１主成分）が求める直線方向のベクトルとなるわけですが、 (a', b')はその直線の法線ベクトルなので、第１主成分と直行する第２主成分を \bf{A}とします。

最後にここで求まった (a', b', c')から (a, b, c)は以下のように求まります。

a = \frac{a'}{\sqrt{a'^{2} + b'^{2}}}

b = \frac{b'}{\sqrt{a'^{2} + b'^{2}}}

c = -a \bar{x} -b \bar{y}

コンピュータビジョン今昔物語 - 深層学習がＣＶの世界をどう変えたか - (JPTA Tech Talk講演資料)

コンピュータビジョン 勉強会 Survey 機械学習

今回、ＣＶ勉強会に何度か参加＆発表していただいたJin Yamanakaさんにお誘いいただき、JTPA (Japan Technology Professional Association)というところで、「コンピュータビジョン今昔物語 -深層学習がCVの世界をどう変えたか-」という大上段なタイトルで講演させていただきました。

www.meetup.com

このJTPAのTech Talkでは、機械学習/深層学習の勉強会を開催してきたそうなのですが、私自身「これ」という深層学習の専門があるわけではないので、コンピュータビジョン全体の基礎的な技術の変遷を、深層学習と絡めて広く浅く網羅した話をさせていただきました。

ちなみにここで紹介した深層学習の技術は、「既存の技術を置き換えるために、深層学習は何をクリアしなくてはならないか？」という視点で、紹介するのが適当と思ったものを選んだつもりです。

当日は時間の関係でSemantic Segmentationの話がきちんと出来なかったので、参加者の方には後でこちらにアップした資料を見返していただけるとありがたいです。

www.slideshare.net

2020/07/18 全日本コンピュータビジョン勉強会「CVPR2020読み会」（後編）発表資料まとめ

コンピュータビジョン 勉強会 学会

先々週の前編に引き続き、関東、名古屋、関西のCV勉強会が合同で「全日本コンピュータビジョン勉強会 - CVPR2020読み会（後編）-」をオンラインにて行いました。

今回、私は発表はありませんでしたが、例のごとく資料やリンク等を（自分のために）まとめておきます。

kantocv.connpass.com

2020/07/18 第三回全日本コンピュータビジョン勉強会「CVPR2020読み会」後編 ツイートまとめ - Togetter

前回同様Youtube Liveでも配信しました。 www.youtube.com

発表資料のリンク（発表順。敬称略。）

発表者 論文タイトル 発表資料
yumash TPNet: Trajectory Proposal Network for Motion Prediction https://www.slideshare.net/yumashino/tpnet-trajectory-proposal-network-for-motion-prediction
alfredplpl Detecting Attended Visual Targets in Video https://www.slideshare.net/yasunoriozaki12/detecting-attended-visual-targets-in-video-237017752
sandglass Proxy Anchor Loss for Deep Metric Learning https://speakerdeck.com/satokeiju/cvpr2020du-mihui-proxy-anchor-loss-for-deep-metric-learning
yasutomo57jp Disentangling and Unifying Graph Convolutions for Skeleton-Based Action Recognition https://www.slideshare.net/yasutomo57jp/disentangling-and-unifying-graph-convolutions-for-skeletonbased-action-recognition-237017395
t2kasa PolarMask: Single Shot Instance Segmentation With Polar Representation https://speakerdeck.com/t2kasa/20200718-cvpr-2020-polar-mask
smygw72 There and Back Again: Revisiting Backpropagation Saliency Methods https://www.slideshare.net/ssuserda79d5/cvpr2020-there-and-back-again-revisiting-backpropagation-saliency-methods-237017288
Tkarasawa_ Self-Supervised Monocular Scene Flow Estimation https://speakerdeck.com/takarasawa_/self-mono-sf
Tres Retina-Like Visual Image Reconstruction via Spiking Neural Model https://speakerdeck.com/sietedm/retina-like-visual-image-reconstruction-via-spiking-neural-model
s_aiueo32 Meta-Transfer Learning for Zero-Shot Super-Resolution https://speakerdeck.com/sansandsoc/meta-transfer-learning-for-zero-shot-super-resolution
Kenji RandLA-Net: Efficient Semantic Segmentation of Large-Scale Point Clouds https://speakerdeck.com/tsukamotokenji/di-san-hui-quan-ri-ben-konpiyutabiziyonmian-qiang-hui-hou-bian

全日本CV勉強会＠オンラインは、コロナが落ち着くまで引き続き開催していきたいなあと思ってますので、宜しくお願い致します。

2020/07/04全日本コンピュータビジョン勉強会「CVPR2020読み会」（前編）発表資料まとめ

コンピュータビジョン 勉強会 学会

コロナ禍でしばらく中止していたコンピュータビジョン勉強会＠関東ですが、今回名古屋および関西のCV勉強会と共催で、オンラインで、コンピュータビジョンのトップカンファレンスCVPR2020の論文読み会を行いました。

 

今回も発表者が多数のため、前後編に分けて行います。後編は7/18に開催予定です。

オンライン開催ははじめてでしたが、それぞれの勉強会の幹事の皆さんの協力でなんとか無事運営することができました。
今回、色々と反省する点もあったので、次回はもっと良い会にしたいと思います。


以下、今回の発表資料等へのリンクをまとめます。

kantocv.connpass.com


2020/07/04 第三回全日本コンピュータビジョン勉強会「CVPR2020読み会」前編 ツイートまとめ - Togetter


今回、Zoomの映像をYoutube Liveへも転送して配信しました。

www.youtube.com


発表資料へのリンク

発表者 論文タイトル 発表資料
akihiro_fujii Revisiting Knowledge Distillation via Label Smoothing Regularization https://www.slideshare.net/AkihiroFujii2/200704-revisiting-knowledge-distillation-via-label-smoothing-regularization
kzykmyzw 3D Packing for Self-Supervised Monocular Depth Estimation https://www.slideshare.net/KazuyukiMiyazawa/3d-packing-for-selfsupervised-monocular-depth-estimation
tereka Erasing Integrated Learning: A Simple yet Effective Approach for Weakly Supervised Object Localization https://speakerdeck.com/tereka114/erasing-integrated-learning-a-simple-yet-effective-approach-for-weakly-supervised-object-localization
takmin BSP-Net: Generating Compact Meshes via Binary Space Partitioning https://www.slideshare.net/takmin/20200704-bspnet-cvpr2020
yu4u SuperGlue: Learning Feature Matching With Graph Neural Networks https://www.slideshare.net/ren4yu/supergluelearning-feature-matching-with-graph-neural-networks-cvpr20
conta_ Deep Snake for Real-Time Instance Segmentation https://www.slideshare.net/takanoriogata1121/20200704-deep-snake-for-realtime-instance-segmentation
p_shiko Momentum Contrast for Unsupervised Visual Representation Learning https://speakerdeck.com/pshiko/cvpr2020du-mihui-onrain-qian-bian-momentum-contrast-for-unsupervised-visual-representation-learning
suganuma When NAS Meets Robustness: In Search of Robust Architectures against Adversarial Attacks https://www.slideshare.net/MasanoriSuganuma/when-nas-meets-robustnessin-search-of-robust-architectures-againstadversarial-attacks-236607860
doiken Unsupervised Learning of Probably Symmetric Deformable 3D Objects from Images in the Wild https://www.slideshare.net/MasanoriSuganuma/when-nas-meets-robustnessin-search-of-robust-architectures-againstadversarial-attacks
peisuke A Quantum Computational Approach to Correspondence Problems on Point Sets https://speakerdeck.com/peisuke/a-quantum-computational-approach-to-correspondence-problems-on-point-sets

 

今回は久々に私も発表を行いました。BSP-NetというBest Student Paperを取った、Deep Learningで3D Meshを表現する研究についてです。