More than 1 year has passed since last update.

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

Last updated at 2021-12-22Posted at 2018-11-12

ミンコフスキー距離ぃ？

ミンコフスキー距離は以下の記事を拝見して知った。
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));
    }
}