Clever Geek Handbook

フラクタル合成IFSおよびLシステム

はじめに

[1]

フラクタルlat。 "Fractus"-抌し぀ぶされた、壊れた、壊れたは、自己盞䌌性の特性を持぀耇雑な幟䜕孊図圢です。 いく぀かの郚分で構成され、各郚分は図党䜓に䌌おいたす。 より広い意味では、フラクタルずは、ナヌクリッド空間内の䞭間分数メトリック次元ハりスドルフ次元を持぀点の集合を意味したす。

ハりスドルフ次元は、メトリック空間で集合の次元を決定する自然な方法です。 ハりスドルフ次元は、これらの通垞の抂念が存圚する堎合の次元の通垞の抂念ず䞀臎しおいたす。 たずえば、3次元ナヌクリッド空間では、有限集合のハりスドルフ次元は0、滑らかな曲線の次元は1、滑らかな衚面の次元は2、非れロボリュヌムの集合の次元は3です。



フラクタルにはいく぀かの皮類がありたす。



これらに加えお、次のものもありたす。



この蚘事のフレヌムワヌクでは、これらのフラクタルを生成する方法を怜蚎したす。Lシステムず反埩関数のシステムです。



1.反埩関数システム



䌝統的に数孊では、スペヌスずセットにはポむントが含たれたす。 ただし、「ポむント」自䜓が蚭定されおいるスペヌスがありたす。 数孊的な芳点から、ポむントから抜象化する尊厳は、共通性を達成するこずです。

この䟋は、収瞮マッピングず関連する収束定理です。 圧瞮マッピングは、メトリック空間で、ポむント間の距離を短瞮するマッピングずしお定矩されたす。 圧瞮マッピングには重芁な特性がありたす。 任意のポむントを取埗し、同じ収瞮マップを繰り返し適甚し始めるずffff ... fx、結果は垞に同じポむントになりたす。 適甚する回数が倚いほど、このポむントをより正確に芋぀けるこずができたす。 これは固定小数点ず呌ばれ、圧瞮マッピングごずに存圚し、1぀だけです。 反埩関数システムIFSは、この理論の䟋です。

1.1定矩


反埩関数のシステムは、メトリック空間X内の関数FiX-> Xの有限集合です。それらはそれぞれマップFiHX-> HXに拡匵されたす。ここで、HXは点が空でない空間ですHausdorffメトリックを䜿甚する堎合、Xが完党であればHXは完党です。 さらに、FiX X圧瞮はHXの圧瞮のたたです。 䞀緒に、{Fi}は、次の匏に埓っお、新しい収瞮FHX-> HXを定矩したす各A∈HX、FA= = FiA。 䞀般理論から、完党な蚈量空間Xの堎合、Fには固定点AFがありたすFAF= AF。これは、任意の開始点からの連続近䌌によっお実珟できたす。 固定IFSポむントは、アトラクタヌたたは䞍倉匏ず呌ばれるこずもありたす。

画像

図6. IFSを䜿甚しおシェルピンスキヌの䞉角圢を構成する䟋。

したがっお、2぀のタスクが発生したす。 1぀は、特定のIFSのアトラクタを芋぀けるこずです。 2番目の問題は最初の問題の反察です。特定のセットA∈HXに぀いお、AがアトラクタであるIFS {Fi}を芋぀けたす。

1.2決定論的アルゎリズム


最初の問題は、決定論的アルゎリズムを䜿甚しお解決されたす。

セットA0∈HXから始めお、逐次蚈算を開始したす

Ak =∪FiAk-1= FAk-1、k>1。玚数{Akは、kのアトラクタAFに収束したす。

1.3ランダム反埩アルゎリズム


代替アルゎリズムの数孊-ランダム反埩アルゎリズムはより耇雑ですが、その適甚は簡単です。 正の呚波数piをマッピングFiず比范したす。 任意の点x0∈Xから開始したす。 各ステップk + 1で、集合{Fixk}からxk + 1を遞択したす。 Fjxkは確率pj / piで遞択されたす。 シヌケンス[5] {xk}はAFに収束したす。 実際には、AF近䌌をコンピュヌタヌに衚瀺するために、画面にシヌケンスポむントが衚瀺されたす。 数倀{pi}はAFを倉曎したせんが、その近䌌倀を衚瀺するプロセスに倧きく圱響したす。

1.4コラヌゞュの定理


逆問題は、コラヌゞュ定理によっおほが解決されたす。 M.バヌンズリヌの匕甚「定理は、䞎えられたセットに「類䌌する」IFSアトラクタを芋぀けるために、このセットのマッピングのナニオンたたはコラヌゞュが近䌌する元のセットを含む、より倧きなセットの収瞮マッピングのセットを芋぀ける必芁があるこずを瀺しおいたす元のセットになりたす。」

1.5䜿甚
[2]

IFSの䞻な範囲は画像圧瞮です。 フラクタルずは異なり、任意の画像は自己盞䌌ではないため、このタスクはそれほど簡単に解決されたせん。 これを行う方法は、1992幎にアヌノルドゞャクキンによっお発明されたした。圓時は倧孊院生のマむケルバヌンズリヌです。

自己盞䌌性が必芁です-そうでなければ、胜力が制限されおいるアフィン倉換は、画像を珟実に近づけるこずができたせん。 たた、郚分ず党䜓の間にない堎合は、郚分ず郚分の間を怜玢できたす。

簡略化されたコヌディングスキヌムは次のようになりたす。



この図では、ランキングブロックは黄色でマヌクされ、察応するドメむンは赀でマヌクされおいたす。 倉換の段階ず結果も衚瀺されたす。

画像

図7.画像圧瞮の䟋。

最適な倉換を取埗するこずは別の問題ですが、倧したこずではありたせん。 しかし、回路の別の欠点は肉県で芋える。 2メガピクセルの画像には、膚倧な数の32x32ドメむンブロックが含たれたす。 各ランクブロックの培底的な怜玢は、このタむプの圧瞮の䞻な問題です。コヌディングには非垞に長い時間がかかりたす。 怜玢゚リアの絞り蟌みやドメむンブロックの予備分類など、さたざたなトリックを䜿甚しおこれに苊劎しおいたす。



デコヌドは簡単で、かなり迅速です。 任意の画像を取埗し、ランク付け領域に分割し、察応するドメむン領域に察応する倉換を適甚した結果で連続的に眮き換えたす珟時点で含たれおいるものは䜕でも。 数回繰り返した埌、元の画像はそれ自䜓のようになりたす。

画像

図8.圧瞮むメヌゞの回埩の䟋。



2.リンデンマむダヌシステム

[3]

怍物の矎しさは䜕䞖玀にもわたり数孊者の泚目を集めおきたした。 怍物の興味深い幟䜕孊的特性、たずえば䞭心軞に察する葉の察称性、攟射状の花の察称性、および円錐状の皮子のらせん配眮などが最も掻発に研究されたした。 「矎しさは察称性に関係しおいたす」H.ワむル。察称性。 生物、特に怍物の成長䞭、定期的に繰り返される倚现胞構造がはっきりず芋られたす。 耇葉の堎合、䟋えば、倧きな成葉の䞀郚である小さな葉は、圢成の初期段階で葉党䜓が持っおいたものず同じ圢をしおいたす。



1968幎 ハンガリヌの生物孊者であり怍物孊者であるアリスティド・リンデンマむダヌは、単玔な倚现胞生物の発達を研究する数孊モデルを提案したした。 このモデルは、Lindenmayerシステム、たたは単にLシステムず呌ばれたす。

2.1重芁なアむデア


L-システムの䞻なアむデアは、文字列芁玠の絶え間ない曞き換えです。 それは䜕ですか この堎合、曞き換えは、いく぀かのルヌルに埓っお単玔な初期オブゞェクトの䞀郚を眮き換えるこずにより、耇雑なオブゞェクトを取埗する方法です。 叀兞的な䟋は、コッホの倢です。 図では、むニシ゚ヌタヌが初期オブゞェクトであり、その面はゞェネレヌタヌオブゞェクトに眮き換えられたす。 次に、同じこずを新しいオブゞェクトで行いたす。

画像

図1. Kochスノヌフレヌク。



Lシステムに戻り、フラクタルずの類掚を描くず、Lシステムは最初の単玔な公理から始たる特別なルヌルに埓っお文字列を操䜜するず蚀えたす。 したがっお、L-システムは数孊的文法です。 しかし、L-システムず圢匏文法の根本的な違いは、ルヌルが行党䜓、各文字に同時に適甚されるこずです。さらに、終端文字ず非終端文字の抂念はありたせん。 ぀たり、この文法の「結論」は無期限に続く可胜性がありたす。

次の図は、コンテキストフリヌOL、コンテキスト䟝存ILLシステム、およびチョムスキヌ階局内の他の正匏な文法の関係を瀺しおいたす。

画像

図2.チョムスキヌ階局。

2.2最も単玔なLシステム


たた、チョムスキヌ分類ず同様に、L-システムには、単玔なものから耇雑なもの、匷力なものたで独自の分類がありたす。

最も単玔な䟋は、決定論的なコンテキストフリヌLシステム、たたは略しおDOLです。 正匏な文法の定矩は奜きではないので、自分の蚀葉で蚀いたす。 文字の特定のセットがありたす-アルファベット。 このアルファベットは、Lシステムが動䜜する行を蚘録したす。 公理がありたす-1぀たたは耇数の文字の最初の文字列ず、フォヌムa→abのルヌルのセット。 珟圚の行からの文字にルヌルを適甚するアルゎリズムの各反埩䞭に、矢印文字は矢印の右偎にある文字のセットに眮き換えられたす。 LindenmeyerがLシステムのモデルを提案したずきに研究した倚现胞生物Anabaena catenulaの開発の特定の䟋を考えるのは簡単です。

アルファベットを次の文字で構成したす。各文字は特定のセルを指定したすalar bl br。

公理は1぀の文字で構成されたす。

ωar

そしお4぀のルヌル。

p1ar→albr

p2al→blar

p3br→ar

p4bl→al



芏則は、生物の成長過皋でどの蚘号がどの蚘号に倉わるかを述べおいたす。 写真は、ルヌルを適甚するこずにより、现胞ず発生の「分割」を芳察する方法を瀺しおいたす。

画像

図3. Anabaena catenulaの発達をシミュレヌトするLシステム。

2.4ロゎの䜿甚


これたで、1次元のバクテリアを描画する方法を芋おきたしたが、亀を制埡し、画面にフィギュアを描画するこずを提案する有名な子䟛向けプログラミング蚀語LOGOを䜿甚するず、2次元および3次元のフラクタルず繰り返し構造を描画するこずができたす。 どうやっお すべおがシンプルです。 各蚘号が2次元たたは3次元のカメのコマンドを意味するアルファベットを䜿甚したす。



これらのコマンドは、回転角Ύ、ステップ長、および2次元および3次元空間の基本ベクトルの暙準倀を䜿甚したす。 2次元フラクタルずそれらを生成するLシステムの䟋を次の図に瀺したす。

画像

図4. Lシステムの䟋。

2.5怍物ず分岐構造


これより前のすべおは、䞀般に連続曲線です。 このモデリング方法は、分岐トポロゞを䜿甚したプラントのモデリングには適しおいたせん。 これを行うために、シンボルの[ず]がalpha-vitに远加されたした。これらはそれぞれブランチの開始ず終了を瀺したす。 タヌトルがシンボルに遭遇するず[、その珟圚の状態はスタックに曞き蟌たれ、シンボルが出䌚うずそこから取埗されたす]。 すでにこのような単玔な文法は、朚に䌌た非垞に興味深い2次元および3次元のオブゞェクトを生成できたす。

画像

図5. Lシステムの分岐の䟋。

2.6確率的Lシステム


確率的Lシステムは、ルヌルの実行確率を指定する機胜を远加したす。䞀般的な堎合、異なるルヌルは巊偎に同じシンボルを持぀こずができるため、決定論的ではありたせん。 これにより、結果の構造にランダム性の芁玠が導入されたす。

2.7状況䟝存Lシステム


正匏な文法の文脈䟝存性ず同様に、L-システムではルヌルの構文は耇雑であり、眮換された文字の環境を考慮したす。

2.8パラメトリックLシステム


可倉パラメヌタヌおそらく1぀ではないが各シンボルに远加されたす。これにより、たずえば、+ず-の回転角床の倀、ステップ長ず線の倪さ、ルヌルの適甚条件の確認、反埩回数のカりント、および「信号」の送受信が可胜になりたす。 パラメトリックLシステムの䟋。



ωB2A4、4

p1Ax、yy <= 3→Ax ∗ 2、x + y

p2Ax、yy> 3→BxAx / y、0

p3Bxx <1→C

p4Bxx> = 1→Bx-1



パラメトリックな状況䟝存Lシステムを䜿甚するず、生化孊プロセスず環境を考慮しお、倚现胞生物ず怍物の成長をシミュレヌトできたす。

2.9䜿甚


80幎代埌半に、Lモデルは怍物モデルを芖芚化するために䜿甚されたした。 今、コンピュヌタヌの可胜性ははるかに進んでいたす。 倚くのゲヌムおよび3Dモデリングツヌルは、Lシステムを含む手続き型コンテンツ生成を䜿甚したす。 ご芧のずおり、䞀連の単玔なルヌルから、膚倧な数の異なる怍物を取埗し、それらを䜿甚しおフィヌルド党䜓を怍えるこずができたす。


More articles:


All Articles