ミンコフスキー距離を絵にしてみた

ミンコフスキー距離ぃ？

ミンコフスキー距離は以下の記事を拝見して知った。
Rubyでミンコフスキー距離 - Qiita

名前からして特殊相対性理論のアレかと思ったら違った（アレってなんだよ）。

まずユークリッド距離

ミンコフスキー距離を説明する前に，ユークリッド距離を説明します。これはごくふつうの距離の定義。

$n$ 次元空間は座標が $n$ 個の数の組で表されるわけなんだけど，二点間の距離がその二点の座標値でどのように表されるか，という問題がありまして。

我々の住んでいるこの 3 次元空間だったらば，点 $\boldsymbol x$ の座標を $(x_1, x_2, x_3)$ とし，点 $\boldsymbol y$ の座標を $(y_1, y_2, y_3)$ とすれば，その間の距離 $D(\boldsymbol x, \boldsymbol y)$ は

D(\boldsymbol x, \boldsymbol y) = \sqrt{ \sum_{i=1}^3 (x_i - y_i)^2 }

になります，と。
ピタゴラスの定理の 3 次元版みたいなもんですな。

（まあ，距離がこんなふうに表せるためには，どんな座標系でもいいわけではなくて，座標軸が直交している，などの条件を満たさないといけないのだけれど。）

ところが，世の中には，そういう普通の距離とは違う，別の距離の定義を考えたい人もいるようでして。

距離の概念を一般化するわけ。
すると，いろんな距離の定義がありうることになるので，それらを互いに区別するため，上で述べたやつ（ふつうっぽい距離）は「ユークリッド距離」と呼ぶことに。

マンハッタン距離

アメリカ人はマンハッタンて言わはったんやけど，あてら日本人には京都や札幌の街を思い浮かべてもろたほうがよろしおますわ。

つまり，道が碁盤目みたいになってて，どこからどこへ行くんでも，真東か真西，真北か真南への移動の組み合わせになる，いうことですわ。

ほしたら，移動するときの最短距離は，東西方向の座標値の差の絶対値と，南北方向の座標値の差の絶対値を足したもんになりますやろ？

つまり，

D(\boldsymbol x, \boldsymbol y) = \left|x_1 - y_1\right|+\left|x_2 - y_2\right|

いうことですわ。
これをマンハッタン距離言いますねん。

ユークリッド距離は 3 次元で，マンハッタン距離は 2 次元で説明しましたけど，どっちも任意の次元でいけますわ。

一般化

ユークリッド距離とマンハッタン距離はまるきり違うように見えるけれど，天才が見たら統一的に理解できるらしい。

つまり，こんなものを考えると。

D_p(\boldsymbol x, \boldsymbol y) = \left( \sum_{k=1}^n \left| x_i - y_i \right|^p \right)^{\frac 1 p}

ここに $p$ というパラメーターが入っている。

$p=1$ のときを考えると，

D_1(\boldsymbol x, \boldsymbol y) = \sum_{k=1}^n \left| x_i - y_i \right|

となって，確かにマンハッタン距離の $n$ 次元版になってる。

$p=2$ のときはというと，

D_2(\boldsymbol x, \boldsymbol y) = \left( \sum_{k=1}^n \left| x_i - y_i \right|^2 \right)^{\frac 12}

になる。よくよく見ればユークリッド距離だ。

このようにして一般化したのをミンコフスキー距離というらしい。

ねぇ，いま Wikipedia で「ミンコフスキー距離」を引こうとしたでしょ。載ってないからね！

ところで，上ではマンハッタン距離も物理空間で説明しちゃったけど，一般の距離の概念は物理空間とはかけはなれた空間上で考えていい。
たとえばある文書と別の文書の内容が近いかどうか，ある画像と別の画像が似ているかどうか，についても，文書間や画像間に何らかの距離を定義して考えることができる。

これを絵にしたい

なんか式だけ見てもピンとこないので，絵にしたい。

こんなふうに考えよう。簡単に絵にするために，空間は 2 次元であるとする。
で，原点からの距離が等しい点を結んで等高線を描こう。

注　「等高線」という言葉を使ったのはただのアナロジー。「高さ」は出てこないので，本当は等高線ではない。原点からの距離が等しい点の集まりだから，「等距離線」とでも呼ぶべきもの。しかし，以下ではアナロジーとして「等高線」という語を使い続けることにする。

ただ，等高線そのものを描くのはちょっと難しいので，こんな工夫をする。
距離が 0 以上 0.2 未満のエリアを全部同じ色で塗る。同じように 0.2 以上 0.4 未満のエリアを別の色で，0.4 以上 0.6 未満をまた別の色で，と塗り分ける。
すると，塗り分けの境界線が等高線になっている，と。

こんな塗り分けには階段関数を使うといいね。

コード

えーっと，Rust で描くぞ。

「え？　なんでまた Rust？」
「なんか好感が持てるから。以上。」

せっかくなので，Rust を触ったことが無い人でも再現できるようにね。
Rust のインストールは簡単（たとえ Windows でも）。rustup というものを使う。インストール方法は調べてくれ。

で，入れると cargo というコマンドが使えるようになるので，

cargo new minkowski

とやって出てきたファイル群の中の Cargo.toml というファイルの

[dependencies]

のあとに，

image = "0.23.14"

を追加する。image っていう画像関係のライブラリーを使うぞ，と伝えるわけ。

次に src/main.rs を

extern crate image;

// 0 から max までを n 分割するような階段関数
fn step(v: f64, max: f64, n: u32) -> f64 {
    (v / max * n as f64).floor() / (n as f64) * max
}

fn write_png (func: &dyn Fn(f64, f64) -> f64, filename: &str) {
    let half_width = 150; // 画像の縦／横のピクセル数の半分
    let width = half_width * 2;
    let u = 1.0; // X 軸，Y 軸の端の絶対値
    let v1 = 2.0; // 最大輝度に達する値

    let mut imgbuf = image::ImageBuffer::new(width, width);

    let k = u / (half_width as f64);
    for (ix, iy, pixel) in imgbuf.enumerate_pixels_mut() {
        let x = (ix as f64 - half_width as f64 + 0.5) * k;
        let y = (half_width as f64 - iy as f64 - 0.5) * k;
        let v = func(x, y);
        let l = (step(v, 1.0, 5) / v1 * 255.0) as u8;
        *pixel = image::Luma([l]);
    }
    imgbuf.save(filename).unwrap();
}

fn main() {
    let exponents = vec![1, 2, 3, 10];
    for p in exponents {
        let d = |x: f64, y: f64| (x.abs().powi(p) + y.abs().powi(p)).powf(1.0/(p as f64));
        write_png(&d, &format!("d{}.png", p));
    }
}

にする。

そしたら

cargo run

と打つだけ。
これでコンパイラーが走り，実行ファイルが出来，実行される。
結果，パラメーター $p$ が 1, 2, 3, 10 のときの画像が書き出される。

ちなみに今の場合，実行時間を気にする必要はない（一瞬で終わる）のだけれど，上記のコマンドだと実行速度を犠牲にしてデバッグしやすいコンパイルが行われるらしい。

なので，本番の実行時は

cargo run --release

とやって，実行時間を優先したコンパイルをやらせるのがよろしい，と。

結果

$p = 1$（マンハッタン距離）

東に 100 ｍ 行くのと，東に 50 m 行って北に 50 m 行くのとが同じ距離になるのが見て取れるね。

$p = 2$（ユークリッド距離）

等高線が円になっている。方向に関して均質な距離であることが分かる。

$p = 3$

等高線が「丸い四角」というか「四角い丸」というか。

$p = 10$

もはや「角の取れた正方形」。

そして，$p \rightarrow \infty$ の極限を取ると，完全な正方形になる。
このときの距離をチェビシェフ距離というのだそうな。
マンハッタン距離を 45 度回転させた形。

感想

結果について

画像見て気付いたけど，この「丸い四角」って，いわゆるスーパー楕円の一種だわね。
スーパー楕円は，書体デザインから（？）陸上競技場の設計まで幅広く使われているらしい。

ミンコフスキー距離がものすごく分かった，という気はしなかった。ただ，$p$ を大きくすればチェビシェフ距離に近づいていく，というのは絵にしたことで分かりやすくなったと思う。

Rust のコードについて

浮動小数点数に整数を掛けるだけで，いちいちあらわに型変換を書かなくてはならないのはちょっとめんどくさい。

コンパイラーがとにかく親切。
ただ，間違った書き方をして，コンパイラーに「○○じゃね？」とか言われてそのとおりに直したら動いた，っていうのを繰り返しても，ずっと理解が浅いまま。
基礎をきちんと学ばないといけないと思う。

とはいえ，この程度のコードならわりとカジュアルに書けて，「とてつもなく難しい」感じはしない。