String Art のアルゴリズム
円形に並べたピンに糸を張ることで任意の画像を出す芸術のこと。
アルゴリズムを考えよう
動画
動画のまとめ
ピンが N 本あるので、糸の張りかたは N(N-1)/2 通り。
N(N-1)/2 通りの「糸を1本だけ張った画像」を 0/1 で線形結合し、ターゲット画像との誤差を最小化する
解が 0/1 という制約付きの連立方程式に帰着できる
ただし変数は数万個みたいなオーダー
ここの最小化について、擬似逆行列で方程式を解くのは微妙だった→貪欲法で良い結果だった、と結論づけている
感想
なんか CT スキャンのラドン積分をうまくやればもうちょっとスマートにできる気がするな
いやちがうか?
糸を一本しか使っちゃいけない…という制約を入れるとかなり探索空間小さくなるのでは?
この制約下であれば貪欲法で最適解が得られそう