मूर प्रतिवेश

मूर प्रतिवेश नौ कक्ष से बना है: केंद्रीय कोशिका और आठ कोशिकाएँ जो इसे घेरती हैं।

सेल्यूलर आटोमेटा में, मूर प्रतिवेश को द्वि-आयामी वर्ग जाली पर परिभाषित किया गया है और यह केंद्रीय कोशिका और उसके चारों ओर आठ कक्ष से बना होता है।

नाम

इस प्रकार से प्रतिवेश का नाम सेलुलर ऑटोमेटा सिद्धांत के अग्रणी एडवर्ड एफ मूर के नाम पर रखा गया है।

महत्व

अतः यह दो सबसे अधिक उपयोग किए जाने वाले प्रतिवेश प्रकारों में से है, जोकि दूसरा वॉन न्यूमैन प्रतिवेश होता है, जोकी कोने की कक्ष को सम्मिलित नहीं किया गया है। और प्रसिद्ध कॉनवे का जीवन का खेल, उदाहरण के लिए, प्रसिद्ध कॉनवे का गेम ऑफ लाइफ, मूर प्रतिवेश का उपयोग करता है। यह कंप्यूटर चित्रलेख में 8 से कनेक्टेड पिक्सल की धारणा के समान होती है।

इस प्रकार से किसी कोशिका का मूर प्रतिवेश स्वयं कोशिका है और 1 की चेबीशेव दूरी पर स्थित कोशिकाएँ होती हैं।

किन्तु अवधारणा को उच्च आयामों तक बढ़ाया जा सकता है, उदाहरण के लिए 3डी लाइफ द्वारा उपयोग किए जाने वाले तीन आयामों में सेलुलर ऑटोमेटन के लिए 26-सेल क्यूबिक प्रतिवेश बनाना। आयाम डी में, जहां $0\leq d,d\in \mathbb {Z}$, आस-प्रतिवेश का आकार 3^d − 1. है

अतः दो आयामों में, विस्तारित मूर प्रतिवेश में कक्ष की संख्या, इसकी सीमा r को देखते हुए (2r + 1)² है

एल्गोरिदम

इस प्रकार से मूर प्रतिवेश के निर्माण के पीछे का विचार किसी दिए गए ग्राफ की रूपरेखा का पता लगाया जाता है और यह विचार 18वीं शताब्दी के अधिकांश विश्लेषकों के लिए उच्च चुनौती मानी जाती थी, और इसके परिणामस्वरूप एल्गोरिथ्म मूर ग्राफ से प्राप्त किया गया था जिसे तत्पश्चात में मूर नेबरहुड एल्गोरिथम कहा गया था ।

अतः मूर-नेबर ट्रेसिंग एल्गोरिथम के लिए स्यूडोकोड का उपयोग किया जाता है।

Input: A square tessellation, T, containing a connected component P of black cells.
Output: A sequence B (b1, b2, ..., bk) of boundary pixels i.e. the contour.
Define M(a) to be the Moore neighborhood of pixel a.
Let p denote the current boundary pixel.
Let c denote the current pixel under consideration i.e. c is in M(p).
Let b denote the backtrack of c (i.e. neighbor pixel of p that was previously tested)
 
Begin
  Set B to be empty.
  From bottom to top and left to right scan the cells of T until a black pixel, s, of P is found.
  Insert s in B.
  Set the current boundary point p to s i.e. p=s
  Let b = the pixel from which s was entered during the image scan.
  Set c to be the next clockwise pixel (from b) in M(p).
  While c not equal to s do
    If c is black
      insert c in B
      Let b = p
      Let p = c
      (backtrack: move the current pixel c to the pixel from which p was entered)
      Let c = next clockwise pixel (from b) in M(p).
    else
      (advance the current pixel c to the next clockwise pixel in M(p) and update backtrack)
      Let b = c
      Let c = next clockwise pixel (from b) in M(p).
    end If
  end While
End

इनपुट:  वर्गाकार टेसलेशन, टी, जिसमें काली कक्ष का  जुड़ा हुआ घटक पी होता है।
आउटपुट: बाउंड्री पिक्सल अर्थात कंटूर का  सीक्वेंस बी (बी1, बी2, ..., बीके)।
एम (ए) को पिक्सेल ए के मूर प्रतिवेश  के रूप में परिभाषित करें।
पी वर्तमान सीमा पिक्सेल को निरूपित करते हैं।
मान लीजिए कि c विचाराधीन वर्तमान पिक्सेल को निरूपित करता है अर्थात c, M(p) में है।
चलो बी सी के बैकट्रैक को दर्शाता है (अर्थात पी के निकटतम पिक्सेल जिसे पहले परीक्षण किया गया था)
 
प्रारंभिक
 B को खाली होने के लिए समुच्चय  करें।
 नीचे से ऊपर और बाएं से दाएं T की कक्ष को तब तक स्कैन करें जब तक कि P का काला पिक्सेल, s न मिल जाए।
 बी में एस डालें।
 वर्तमान सीमा बिंदु p को s अर्थात p=s पर समुच्चय  करें
 चलो b = वह पिक्सेल जिससे छवि स्कैन के समय s अंकित किया गया था।
 एम (पी) में सी को अगले दक्षिणावर्त पिक्सेल (बी से) के रूप में समुच्चय  करें।
 जबकि c न के बराबर s करते हैं
 यदि सी काला है
 बी में सी डालें
 चलो बी = पी
 चलो पी = सी
 (बैकट्रैक: वर्तमान पिक्सेल c को उस पिक्सेल पर ले जाएँ जहाँ से p अंकित किया गया था)
 चलो सी = अगले दक्षिणावर्त पिक्सेल (बी से) एम (पी) में।
 अन्य
 (वर्तमान पिक्सेल c को M(p) में घड़ी की दिशा में अगले पिक्सेल तक आगे बढ़ाएं और बैकट्रैक अपडेट करें)
 चलो बी = सी
 चलो सी = अगले दक्षिणावर्त पिक्सेल (बी से) एम (पी) में।
 यदि अंत
 अंत जबकि
अंत

समाप्ति की स्थिति

चूँकि मूल समाप्ति संकेत दूसरी बार प्रारंभ पिक्सेल पर जाने के पश्चात रोकने की थी। यह समोच्च के समुच्चय को सीमित करता रहता है और एल्गोरिदम पूर्ण रूप से चलेगा। जैकब एलियोसॉफ द्वारा प्रस्तावित उत्तम रोक स्थिति दूसरी बार उसी दिशा में प्रारंभ पिक्सेल में प्रवेश करने के बाद रुकना है, जिस दिशा में आपने मूल रूप से प्रवेश किया था।

यह भी देखें

• प्रतिवेश (ग्राफ सिद्धांत)
• किंग्स ग्राफ
• चेन कोड
• वॉन न्यूमैन प्रतिवेश

संदर्भ

• Weisstein, Eric W. "Moore Neighborhood". MathWorld.
• Tyler, Tim, The Moore neighborhood at cell-auto.com