ソフトウェアエンジニアの技術ブログ：Software engineer tech blog

– 映像中から、映っている物体の動きを抽出するのをオプティカルフローと呼ぶ
– 特徴点抽出とピクセル値の変化から、映像フレーム間における注目ピクセル(特徴点)の移動を計算する
– 移動前と移動後の特徴点を線分で結ぶとオプティカルフローが得られる

### 勾配法
時間変化と空間的な濃度勾配を基礎に置く

### ブロックマッチング法
画像中のある大きさの領域をテンプレートとし、次のフレームの画像内のある評価関数に基づき探索する

### 勾配法の原理
画像は2次元、流体は3次元
画像には奥行き方向成分の情報が欠落している為、移動ベクトルを一意的に求めることができないが、前提条件(仮定)を補うことで、一意的な解を推定する

▼前提条件
(1)移動前後の明るさは普遍
E'(x+u, y+v) = E(x,y)
(2)画像は滑らかである(時間的、空間的に微分可能)
(3)移動量はわずかである
(4)近傍画素も同じ動きをする
画像ピラミッドを使って小さいものから推定する

– 物体の形状でも特徴的な箇所だけ注目して検出する方法
– 特徴点は、画像の中の線の端点や交差点、角が用いられる
– 抽出された輪郭線はチェーンコード化され、内側と外側の輪郭が区別される

### 基本
・edge: 差異を認識できる境界がある
・corner: edgeが集中する点
・flat: edgeでもcornerでもない、特徴が何も認識できない点
-> 再現性、識別性が必要

## 特徴点検出の手順
edge検出 -> corner検出　の流れになる

### edgeの検出
輝度が大きく変化している点(水平方向と垂直方向の2方向): Magnitudeと呼ぶ
-> 輝度の変化率を計算する
-> スムージングとは、変化量を計算する際に、周辺部分も考慮する方法
-> 周辺の対象範囲と重み付けの定義にはPrewitt, Sobel, Gaussianなどがある

### Cornerの検出
– Harris Corner Detectorが良く使用される。行列の特性を利用した手法
-> 固有ベクトル：　変化量の方向性を表す、edgeの向き
-> 固有値が大きい: 変化量を良く説明できる

変化量をまとめた行列の固有ベクトルからedgeの向き、固有値の大きさから変化量の大きさがわかる
複数の固有ベクトルがある場合、複数のedgeがある、すなわちcornerとなる

変化量を二次微分してI(x)” = 0となる点が特徴点

なんやろう、頭蒸発しそうだ。。

– 画像から、「標識」など特定の物体を検出する際に、テンプレートマッチングと呼ばれる手法が良く使用される
– 予め指定パターンの画像を用意し、このパターンと画像部分を照らし合わせながら探索する
– 具体的には入力画像の一部分とテンプレート画像の類似度を求め、類似度が最も大きい場所を探索する
– 類似度の計算方法には「SSD」「SAD」「NCC」などがある

### SSD(Sum of Squared Difference)
画素値の差分の二乗和(二乗誤差)で類似度を評価する
この値が宰相になる場所が類似度が高いことになる
SSD(dx, dy) = (w-1)Σx=0 * (h-1)Σy=0(I(dx + x, dy + y)- T(x,y))^2

### SAD(Sum of Absolute Difference)
SADでは、画素値の差分の絶対値の和で類似度を評価する
この場合も、値が最小になる場所が類似度が高くなる
SSD(dx, dy) = (w-1)Σx=0 * (h-1)Σy=0|I(dx + x, dy + y)- T(x,y))|
※SSDに比べ、計算量が少なく、外れ値の影響を受けにくい。ただし、照明の影響を受けやすい

### NCC(Normalized Cross Correlation)
正規化相互相関で類似度を評価する
NCC(dx,dy) = ΣΣ[I(dx + x, dy +y)T(x,y)]/√ΣΣ[I(dx+x,dy+y)]^2√ΣΣ[T(x,y)]^2
最大値1.0に最も近くなった走査位置が類似する
※照明の影響を受けにくいが、計算量が多い
※画像をベクトルとみなして内積を計算する為、ベクトルのながさ(照明)に影響を受けない

SSD,SADは画像のテンプレート画像と入力画像のサイズの違いをどうやって評価しているかわからんな。
(w-1)Σx=0 * (h-1)Σy=0でシグマが二つ並んだ二重和だから、Σでx=0→横幅のmax(w-1)まで、かつ、y=0→縦幅のmax(h-1)まで計算してるって理解で合っている？
SADとSSDはわかるが、NCCの二乗をルートで割ったので割る値を求めているのか良くわからんな。NCCはベクトルだから向きが回転しててもOKってこと？

ヒストグラムとは？
-> 統計で度数分布を示すグラフの一つ。横軸に階級、縦軸に度数をとり、各階級の度数を長方形の柱で示す。

define('cherry', 'cherry.jpg');

$img = imagecreatefromjpeg(cherry);
$imagex = imagesx($img);
$imagey = imagesy($img);

$histogramR = array(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
$histogramG = array(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
$histogramB = array(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0);

for($y = 0; $y < $imagey; $y++){
	for($x = 0; $x < $imagex; $x++){
		$rgb = imagecolorat($img, $x, $y);
		$r = ($rgb >> 16) & 0xFF;
		$g = ($rgb >> 8) & 0xFF;
		$b = $rgb & 0xFF;
		$histogramR[(int)($r/16)]++;
		$histogramG[(int)($g/16)]++;
		$histogramB[(int)($b/16)]++;
	}
}

function writeHistogram($value, $char){
	echo $value;
	for($i=0; $i<$value; $i++){
		echo $char;
	}
}

echo 'Red <br>';
foreach($histogramR as $countR){
	writeHistogram($countR/100, 'r');
	echo '<br>';
}

Red
53.32rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
41.12rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
446.61rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
470.27rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
505.77rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
263.59rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
238.95rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
178.22rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
118.97rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
86.47rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
72.66rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
65.12rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
56.57rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
46.29rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
39.89rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
48.98rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr

OpenCVでは一次元ヒストグラムでは横軸が明度、縦軸が明度のピクセル数
二次元ヒストグラムでは、横軸が色相、縦軸が彩度、グラフの各点の明るさがピクセル数の数を示す。
cvCreateHist関数などを用いる
ヒストグラムを利用して画像同士の類似度を計算する

なるほど、写真からカテゴライズする時などはヒストグラムを使うのか。
顔認証にもヒストグラムは使われているのでしょうか。。。

モルフォロジー変換とは、画像中の幾何学的な構造を解析したり処理したりする時に用いられる数学的手法の一つ
数理形態学(mathematical morphology)と呼ぶ
1960年G.Matheron, J.Serraによって提起
ノイズ除去、テクスチャ解析、エッジ検出など各種の画像処理に用いられる
モルフォロジー変換にはdilate(膨張)、erode(縮退)、open、closeという基礎的な演算処理があり、OpenCVでは関数で提供されている
dilateは微小領域を削除する為、ノイズの除去などに使用される
delationは入力画像の前景を広げる効果があり、erodionは入力画像の前景を狭める効果がある

### アルゴリズム
– 多次元空間における集合論として展開される
– サイジング n x n(縦横がそれぞれn画素)の2次元デジタル画像を入力すると、フィルタ画素のサイズを r x rとすると、モルフォロジー演算に要する計算量はO(n^2r^2)となる
– 大きなフィルタを小さなフィルタに分割して繰り返し処理を行う方法やフィルタを1次元フィルタに分解して処理する方法、距離変換アルゴリズムを用いてモルフォロジー演算を行う手法などが提案されている
– n x nの2値画像I{Iij}において、F = {(i,j)| Iij = 1}を前景、B = {(i,j)| Iij = 0}を背景と呼ぶ
– 物体と背景の隣接時に、0 -> 1にするのがdelate, 1 -> 0にするのがerode

基本的な原理はわかりました。

撮影時のカメラの傾きから、画像自体が傾いて撮られる事が良くある
そのような場合、ハフ変換で直線を得た後に、その傾きの角度から画像を補正する事ができる
文字認識の前処理としてよく使われる

二値化 -> エッジ検出　-> ハフ変換　-> 傾き補正　-> 文字認識　の流れか？
回転させながら行検出するアルゴリズムもあるみたいですね。

傾いている対象が長方形の場合、輪郭を走査して、最小二乗法の直線近似で、誤差のある点を除きながら直線を求めることもできる。反復法で誤差を収束させるので、速度に難がある

補正する対象が何かや、求めるパフォーマンスによって、採用するアルゴリズムが変わってくるというのは面白い
OpenCVと機械学習はかなり繋がっていますね。

ハフ変換(Hough)は、画像から直線や曲線を抽出し、それを数式で表現したい時に用いられるアルゴリズム
通常はエッジ検出を行った後の画像に対してハフ変換を行う(二値化した後にゴミを除去し、細線化処理を行う)
OpenCVには、直線を検出するcvHoughLine2や、円を検出するcvHoughCirclesが用意されている

### ハフ変換のアルゴリズム
– 座標軸を変換する
– ρ=x∗cosθ+y∗sinθとしてρとθで表す。ρかθのどちらかの値が決まれば、直線を求めることができる
– θは0≦θ＜π
– 元画像に存在する点の数の中で、多く交差する箇所が求めたい直線になる

– 円を検出したい場合は(x−p)^2+(y−q)^2=r^2を使用する

エッジ検出した点それぞれのρ、θをプロットした曲線のうち、多くの線が重なり合っている点(ρ、θが同じ)の中から、最も直線が存在する可能性が高い組み合わせを探す処理を行っている

なるほど、θが同じだから、直線とみなすわけですね。
角度が同じものを直線とみなすので、抽出する直線の数が多ければ、実態の直線よりも幾何学的なアウトプットになりそうです。

画像からモノの輪郭だけを抽出することをエッジ検出という
エッジとは、ピクセル値が極端に変わった箇所を強調して抽出するが、より高度な処理が必要
その中でも特にCannyアルゴリズムが性能が高いと言われている

imagefilter ( $image , IMG_FILTER_EDGEDETECT );
imagefilter ( $image , IMG_FILTER_BRIGHTNESS , 20 );
imagefilter ( $image , IMG_FILTER_CONTRAST , -255 );

### measure of overall sharpness and generating a score
imagecolorat — ピクセルの色のインデックスを取得

chicks.jpg

cherry.jpg

function getBlurAmount($image){
	$size = getimagesize($image);
	$image = ImageCreateFromJPEG($image);
	imagefilter($image, IMG_FILTER_EDGEDETECT);
	$blur = 0;
	for ($x = 0; $x < $size&#91;0&#93;; $x++){
		for ($y =0; $y< $size&#91;1&#93;; $y++){
			$blur += imagecolorat($image, $x, $y) & 0xFF;
		}
		return $blur;
	}
}

$e1 = getBlurAmount("chicks.jpg");
$e2 = getBlurAmount("cherry.jpg");
echo "relative blur of first image is" . $e1 / min($e1, $e2) .", and relative blur of second image is" . $e2 / min($e1, $e2) . ".<br>";
echo $e1. "<br>";
echo $e2;

relative blur of first image is1.0578699268003, and relative blur of second image is1.
55206
52186

### Cannyアルゴリズム
1. ノイズ削減
-> 画像を平滑化してノイズ削減
2. 画像の輝度勾配を見つける
-> 平滑化された画像からSobelフィルタを使って縦方向(G_y)と横方向(G_x)の1次微分を取得、2つの微分画像からにエッジの勾配と方向を求める
3. 非極大値の抑制
　-> エッジと関係ない画素を取り除く(勾配方向に対して極大値であるか確認)
4. Hysteresisを使った閾値処理
　-> minVal と maxVal を使って、正しいエッジとそうでないエッジを区分する
OpenCVではcv2.Canny() を使う

エッジ検出単体でというより、組み合わせて使うイメージか・・・

2値化とは、画像のある範囲のピクセル値を0か1など2つの値に変換することを指す
物体の輪郭を明確にしたい時などに使用する
2値のどちらに振り分けるかを決定する値を閾値といいう

例:
モノクロモデルで色が0〜255までの256階調の画像を0〜127の値は0に、128〜255の値は255に変換する

OpenCVおよびPythonはUbuntuで開発したいので、18.04を起動してlampを構築し、php-gdを入れます。

$ vagrant init ubuntu/bionic64
$ vagrant up
$ vagrant ssh
$ uname -a
Linux ubuntu-bionic 4.15.0-96-generic #97-Ubuntu SMP Wed Apr 1 03:25:46 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux

// install tasksel
$ sudo apt install tasksel
// lamp install
$ sudo tasksel install lamp-server
$ apachectl -v
Server version: Apache/2.4.29 (Ubuntu)
$ mysql --version
mysql  Ver 14.14 Distrib 5.7.29, for Linux (x86_64) using  EditLine wrapper
$ php --version
PHP 7.2.24-0ubuntu0.18.04.3 (cli) (built: Feb 11 2020 15:55:52) ( NTS )
$ sudo service apache2 start

// gd install
$ apt-cache search gd | grep php
$ sudo apt-get install php7.2-gd

header ("content-type: image/png");

$filename = "chicks.jpg";
$image = ImageCreateFromJPEG ( $filename );

imagefilter ( $image , IMG_FILTER_EDGEDETECT );
imagefilter ( $image , IMG_FILTER_GRAYSCALE );
imagefilter ( $image , IMG_FILTER_SMOOTH , 8 );
imagefilter ( $image , IMG_FILTER_BRIGHTNESS , 20 );
imagefilter ( $image , IMG_FILTER_CONTRAST , -255 );

imagepng ( $image );
imagedestroy ( $image );

IMG_FILTER_EDGEDETECT: 画像の輪郭抽出
IMG_FILTER_GRAYSCALE：REC.601 luma (Y’) の計算と同じ係数を使い、 重み付けを赤、緑、青のコンポーネントごとに変えることで、 画像を白黒
IMG_FILTER_SMOOTH：画像を滑らかにする
IMG_FILTER_BRIGHTNESS：画像の輝度
IMG_FILTER_CONTRAST：画像のコントラスト

EDGEDETECTをなくすと、こうなる

BRIGHTNESSとCONTRASTで2値化している。

grayscaleのアルゴリズム

線形RGB空間において重み合計（英語版）を計算しなければならない。それはつまり、ガンマ圧縮関数は最初にガンマ拡張によって取り除かれるということである
...
光度は3つの線形的な光の強さの値の重み合計として計算

REC.601 luma

The Rec. 601 signal can be regarded as if it is a digitally encoded analog component video signal, and thus the sampling includes data for the horizontal and vertical sync and blanking intervals. Regardless of the frame rate, the luminance sampling frequency is 13.5 MHz. The samples are uniformly quantized using 8 or 10 bit PCM codes in the YCbCr domain.

For each 8 bit luminance sample, the nominal value to represent black is 16 and the value for white is 235. Eight-bit code values from 1 through 15 provide footroom, and can be used to accommodate transient signal content such as filter undershoots. Similarly, code values 236 through 254 provide headroom and can be used to accommodate transient signal content such as filter overshoots. The values 0 and 255 are used to encode the sync pulses and are forbidden within the visible picture area. The Cb and Cr samples are unsigned and use the value 128 to encode the neutral color difference value, as used when encoding a white, grey or black area.

REC 601は色変換の規格ってことか？