とある無職の悪戦記録: OpenCVのArUcoマーカーをRS符号とかLFSRとかで大量生成

　適当なアルゴリズム処理でArUcoコードを作成

　4x4の大きさで、塗りつぶし(白・黒)および生成済みのマーカーに対して4bit以上の距離のものを使用。事前定義の辞書(4x4_1000)に入っているものは緑の枠を表示している。アルゴリズムというか、どちらかといえばブルートフォース的なやりかただけど。

　このやり方だと5x5くらいが限界。5x5なら25bitなのでforループでゴリ押しできる範囲。6x6では36bitになるから、計算量が2000倍も増える。処理時間が一気に増える。

　3x3、4x4、5x5で最小距離を変えたときに作れるマーカーの数。

　5x5程度のマーカーであれば距離の遠いマーカーをアルゴリズム的に作れる。それ以上の大きさになると結構面倒。乱数で作る手もあるけど、結局はある程度の計算時間が必要になる。

***

　試しにリードソロモン符号でArUcoを生成。

　処理の内容としては、12バイトのバッファを用意して、その前方4バイトに対してループカウンタの値を設定、リードソロモン符号化を行って12バイトへ拡張した後に、末尾8バイト(つまりRS符号のみ)を64bitのビットパターンとして8x8のArUcoを作っている。

　いくつかマーカーを作ったときの、距離のヒストグラム

　例えば初めの16個のマーカーを使った場合、最小距離が22なので、11bit誤ると別のマーカーに誤認する可能性がある、みたいな感じだと思う。同じように考えると、1000個のマーカーを使う場合は最小距離が13なので6bit誤りまでは耐えられるはず。

　RS符号は8バイトなので、4バイトまでの誤りを訂正できる。データ部の4バイトを削除しているので、RS符号の8バイトが残っている限り、データ部の4バイトを復元できる。つまり8バイトのRS符号は、4バイトのデータ部のあらゆる組み合わせに対してユニークなビット列となる。つまり2^32個のマーカーはすべてユニークなビットパターンであることを保証できる(ただしArUcoは回転でビット再配置が行われるのでもう少し複雑な話になる)。

　使いやすいRSエンコーダ(8bit向け)だと作成できるマーカーは4x4か8x8の2種類、パディングビットを含めれば6x6のマーカーも可能、という感じで、任意の大きさのマーカーを作れるわけではないけど、とはいえ乱数に頼ったりせずに任意の大きさの辞書をある程度の品質で作れるという点ではRS符号はアリな気がする。

　ユニーク値が必要なだけなら連番を直接マッピングしても2^64までユニークだけど、連続したID(例えば1,2,3)が似たマーカーになるとか、比較的早い段階(例えば1と128とか)で回転対称になる、みたいな問題がある。

/* RS符号をハッシュ関数的に使う着想はFHSSによるものだけど、FHSSでRS符号をホッピングパターンに使う例はググってもほとんど見つけられないのよな。。。 */

***

　LFSR(62bit)のレジスタをArUco(8x8)のビットパターンに使うとこんな感じ

　マーカーが1万を超えれるとRSのほうが若干有利だけど、全体的に見ればだいぶ優秀。RSと違って変なノッチも無いし、黒体放射みたいなきれいな形になる。ただしLFSRのビット幅によっては極端に性能が劣化するので適当な幅を選ぶ必要があるのと、レジスタの初期値からある程度の数は真っ白(or XNORを使うなら真っ黒)に近いマーカーになるので、最初に適当な数(数百から数千程度)を読み飛ばす必要がある。

　LFSRはビット幅をある程度自由に設定できるので、任意の大きさのマーカーを作る際にも便利。

　LFSR(48)、ArUco(7x7)