В клеточных автоматов , то Мур окрестность определяется на двумерной квадратной решетке и состоит из центральной ячейки и восемь ячеек , которые его окружают.
Имя
Район назван в честь Эдварда Ф. Мура , пионера теории клеточных автоматов.
Важность
Это один из двух наиболее часто используемых типов соседства, второй - район фон Неймана . Например, в хорошо известной «Игре жизни» Конвея используется район Мура. Это похоже на понятие 8-связанных пикселей в компьютерной графике .
Окрестность ячейки Мура - это сама ячейка и ячейки на расстоянии Чебышева, равном 1.
Концепция может быть расширена до более высоких измерений, например, образуя кубическую окрестность из 26 клеток для клеточного автомата в трех измерениях, как это используется в 3D Life . В размерности d размер квартала составляет 3 d - 1.
В двух измерениях количество ячеек в расширенной окрестности Мура с учетом ее диапазона r равно (2 r + 1) 2 .
Алгоритм
Идея формулировки окрестности Мура состоит в том, чтобы найти контур заданного графа. Эта идея была большой проблемой для большинства аналитиков 18-го века, и в результате на основе графа Мура был создан алгоритм, который позже был назван алгоритмом окрестности Мура.
Ниже приводится формальное описание алгоритма трассировки Мура-Соседа:
Вход : квадратная мозаика T, содержащая компонент P черных ячеек.Выход : последовательность B (b1, b2, ..., bk) граничных пикселей, то есть контура.Определите M (a) как окрестность Мура пикселя a.Пусть p обозначает текущий граничный пиксель.Пусть c обозначает текущий рассматриваемый пиксель, т.е. c находится в M (p).Пусть b обозначает возврат c (то есть соседний пиксель p, который был ранее протестирован) Начните набор B, чтобы быть пустым. От нижней части до верхней и влево , чтобы право не сканировать клетки Т , пока черный пиксель, S, Р найден. Вставьте s в B. Установите текущую граничную точку p на s, т.е. p = s. Пусть b = пиксель, из которого s был введен во время сканирования изображения. Установите c как следующий пиксель по часовой стрелке (от b) в M (p). В то время как с не равняться с делать если с является черным вставить c в B Пусть b = p. Пусть p = c (возврат: переместить текущий пиксель c в пиксель, из которого был введен p). Пусть c = следующий по часовой стрелке пиксель (от b) в M (p). else (переместить текущий пиксель c к следующему пикселю по часовой стрелке в M (p) и обновить обратный путь) Пусть b = c Пусть c = следующий пиксель по часовой стрелке (от b) в M (p). конец Если конец Пока Конец
Условие прекращения
Исходным условием завершения было остановка после посещения начального пикселя во второй раз. Это ограничивает набор контуров, по которым алгоритм будет полностью проходить. Улучшенное условие остановки, предложенное Джейкобом Элиозоффом, - это остановка после второго входа в начальный пиксель в том же направлении, в котором вы его изначально ввели.
Смотрите также
Рекомендации
- Вайсштейн, Эрик В. «Соседство Мура» . MathWorld .
- Тайлер, Тим, район Мура на cell-auto.com