Использование поисковых таблиц
Когда структурообразующие элементы, используемые в операции успех/ неудача, малы, то это преобразование можно вычислить быстрее, если воспользоваться поисковой таблицей LTU (LookUp Table). Метод заключается в предварительном вычислении значений выходных пикселов для дальнейшего использования. Например, всего имеется 29=512 различных конфигураций значений пикселов двоичного изображения 3×3.
Чтобы воспользоваться поисковой таблицей, необходимо присвоить уникальный индекс каждой возможной конфигурации пикселов. Простой способ сделать это, скажем, для случая 3×3, заключается в умножении каждой конфигурации 3×3 поэлементно на матрицу
1 8 64
2 16 128
4 32 256
и в сложности полученных произведений. Эта процедура назначает уникальное значение в интервале от 0 до 511 каждой двоичной окрестностной конфигурации 3×3. Например, окрестности
1 1 0
1 0 1
1 0 1
присваивается число 1(1)+2(1)+4(1)+8(1)+16(0)+32(0)+64(0)+128(1)+256(1)=399, где первые множители являются коэффициентами из предыдущей матрицы, а в скобках стоят значения пикселов, взятые по столбцам.
В пакете IPT имеется две функции makelut и applylut (использование которых будет проиллюстрировано позже в этом параграфе), реализующие эти действия. Функция makelut строит поисковую таблицу на основе некоторой функции, заданной пользователем, а applylut обрабатывает входное изображение с помощью построенной таблицы. Если продолжить рассмотрение случая 3×3, то использование makelut предполагает задание пользовательской функции, которая принимает на входе матрицы 3×3, а возвращает одно значение, обычно 0 или 1. Функция makelut вызывает эту заданную пользователем функцию 512 раз, передавая ей все возможные окрестности 3×3. Она возвращает результат вычислений в виде вектора из 512 элементов.
В качестве иллюстрации мы напишем функцию (назовем ее endpoints.m), которая использует makelut и applylut для обнаружения концевых точек на двоичном изображении. Концевой точкой мы будем называть пиксел переднего плана, у которого имеется в точности один сосед переднего плана. Функция endpoints вычисляет, а затем применяет поисковую таблицу для обнаружения концевых точек входного изображения. Строка программного кода
persistent lut,
которая используется в endpoints, определяет переменную с именем lut и объявляет, что она принадлежит типу persistent (устойчивый). MATLAB «помнит» значение переменных типа persistent в промежутках между вызовами данной функции. При первом вызове функции endpoints переменная lut автоматически инициализируется пустой матрицей ( [ ] ). Когда lut пуста, то функция вызывает makelut, передавая ее манипулятор подфункции endpoints_fcn. Затем функция applylut находит концевые точки с помощью поисковой таблицы. Поисковая таблица хранится в переменной lut типа persistent, поэтому при следующем вызове функции endpoints не придется заново строить эту таблицу.
function g = endpoints(f)
persistent lut
if isempty(lut)
lut = makelut(@endpoint_fcn, 3);
end
g = applylut(f,lut);
function is_end_point = endpoint_fcn(nhood)
is_end_point = nhood(2,2) & (sum(nhood(:)) == 2);
Пример 6. Реализация игры Конвея «жизнь» на основе двоичного изображения и поисковой таблицы.
Интересным приложением поисковых таблиц может служить «игра жизнь» Конвея, в которой участвуют «организмы», существующие на прямоугольной сетке и эволюционирующие из поколения в поколение. Мы воспользуемся ею для иллюстрации достоинства и простоты метода поисковых таблиц. Имеются простые правила, по которым организмы в игре Конвея рождаются, выживают и умирают при переходе от одного «поколения» к следующему.
Генетические правила Конвея определяют метод вычисления следующего поколения (или следующего двоичного изображения) по текущему поколению:
1. Каждый пиксел переднего плана, имеющий двух или трех соседей переднего плана, выживает в следующем поколении.
2. Каждый пиксел переднего плана, имеющий ноль, один или не менее четырех соседей, «умирает» в следующем поколении (т.е. становится фоновым пикселом) по причине его «изоляции» или «перенаселенности».
3. Каждый фоновый пиксел, у которого имеется ровно три соседних пиксела переднего плана, «рождает» пиксел, т.е. он становится пикселом переднего плана.
Все «рождения» и все «смерти» происходят одновременно в процессе вычисления следующего двоичного изображения, определяя очередное поколение «организмов».
Рисунок 14 - а) Изображение морфологического остова. б) Выход функции endpoints. Пикселы этого изображения увеличены для лучшей наглядности.
Для реализации игры «жизнь» с помощью функций makelut и applylut мы сначала напишем функцию, которая применяет генетические законы Конвея к выделенному пикселу и его 3×3 соседям:
function out = conwaylaws(nhood)
num_neighbors = sum(nhood(:)) - nhood(2, 2);
if nhood(2, 2) == 1
if num_neighbors <= 1
out = 0;
elseif num_neighbors >= 4
out = 0;
else
out = 1;
end
else
if num_neighbors == 3
out = 1;
else
out = 0;
end
end
Затем строится поисковая таблица вызовом функции makelut с манипулятором функции conwaylaws в качестве аргумента:
>> lut = makelut ( conwaylaws , 3 ) ;
Множество исходных изображений было придумано для демонстрации различных эффектов, возникающих в поколениях «организмов», подчиняющихся законам эволюции Конвея (см. [Gardner, 1970, 1971]). Рассмотрим, к примеру, начальное изображение, которое называется «конфигурацией чеширского кота»:
>> bw1 = [0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 1 0 0 0
0 0 0 1 1 1 1 0 0 0
0 0 1 0 0 0 0 1 0 0
0 0 1 0 1 1 0 1 0 0
0 0 1 0 0 0 0 1 0 0
0 0 0 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0];
Следующие команды совершают вычисления и показывают три поколения этого изображения:
>> imshow( bw1,'n'), title ('Generation 1')
>> bw2=applylut(bw1,lut);
>> figure, imshow (bw2,'n'); title ('Generation 2')
>> bw3=applylut (bw2,lut);
>> figure, imshow(bw3,'n'); title ('Generation 3')