मूर प्रतिवेश

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

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

नाम

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

महत्व

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

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

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

यह भी देखें

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

संदर्भ

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