4.2. Локальные вычисления и итеративная модификация

До сих пор основное внимание уделялось последовательной обработке информации, содержащейся в бинарном изображении. Чтобы повысить скорость обработки и использовать возможности больших интегральных схем (БИС), необходимо также рассмотреть, какие результаты можно получить с помощью параллельно выполняемых локальных операций. Под локальной мы понимаем то, что на вход каждой такой операции поступает информация лишь с небольшого участка изображения.

Имеются два типа вычислений, выполнимых таким образом. Мы можем скомбинировать (сложить) результаты всех локальных операций и завершить тем самым работу в один шаг (рис. 4.5) или создать

Рис. 4.5. Методы локальных вычислений.

Комбинируются выходы отдельных, вычислительных ячеек, каждая из которых соединена с несколькими элементами изображения, лежащими вблизи нее.

новое изображение на основе этих результатов. Последний метод будет рассмотрен в следующем разделе.

4.2.1. Локальные вычисления

Рассмотрим очень простой случай. Каждый из локальных операторов обращается к одному элементу изображения и выдает его значение. После сложения всех таких выходов в качестве результата получим суммарную площадь объектов, находящихся в поле зрения. Таким образом, параллельный способ вычисления площади требует всего одного шага (проблему суммирования всех нулей и единиц мы здесь не рассматриваем).

Какие другие характеристики представимы в виде суммы результатов локальных операций? Например, периметр: достаточно просто подсчитать количество участков на изображении, где рядом с нулями стоят единицы. Имеются два типа локальных операторов (рис. 4.6): операторы одного типа просматривают два соседних элемента, расположенных в одной строке, а операторы другого типа — два соседних элемента, расположенных в одном столбце.

Рис. 4.6. Возможность использования операции ИСКЛЮЧАЮЩЕЕ ИЛИ к двум соседним элементам изображения для выделения участков, находящихся на границе областей.

В обоих случаях результат есть ИСКЛЮЧАЮЩЕЕ ИЛИ двух значений на входе. Сумма всех получаемых выходов представляет собой оценку периметра.

Каждый из двух типов операторов реагирует на два типа шаблонных ситуаций. Здесь показаны два случая, включающие горизонтальный и вертикальный детекторы.

Вычисленный периметр представляет собой лишь приблизительную оценку, поскольку, как правило, дискретное бинарное изображение

строится на основе непрерывного, и при этом границы объектов становятся более изрезанными. Например, оценка длины диагональной прямой в раз больше «истинной»:

Усреднение по всем углам наклона дает среднее значение коэффициента, показывающего, во сколько раз увеличено полученное значение. Оно составляет Разделив на это число, можно улучшить оценку периметра.

Кроме площади и периметра с помощью локальных методов можно вычислить число Эйлера, которое определяется как разность между количеством объектов и количеством отверстий. Например, число Эйлера заглавной буквы равно — 1, поскольку она представляет собой один объект с двумя отверстиями (рис. 4.7). Число Эйлера буквы «i» равно 2, а буквы «n» равно 1 и т. д. Может показаться странным, что число Эйлера рассчитывается с помощью суммирования результатов локальных операций. Например, ни числа объектов, ни числа отверстий таким путем рассчитать нельзя. А их разность, т. е. число Эйлера, можно!

Рис. 4.7. Число Эйлера как разность между числом объектов и числом отверстий. Для этого бинарного изображения число Эйлера равно 4, поскольку на нем 7 объектов и 3 отверстия.

4.2.2. Свойство аддитивности

Мы можем комбинировать бинарные изображения различными путями. Можно осуществить операцию ИЛИ. В результате мы объединим два изображения в одно. Можно осуществить операцию И. В этом случае мы получим пересечение объектов. Нас интересует, как различные характеристики получаемых подобными способами изображений соотносятся с характеристиками исходных изображений. Одна из причин такого интереса связана с надеждой разбить изображение на большое число частей, одновременно обработать все эти части и затем объединить результаты.

Если обозначить исходные изображения через X и (рис. 4.8), то логические операции ИЛИ и И над X и обозначаются соответственно и Площади удовлетворяют соотношению поскольку сумма площадей X и равна площади их объединения плюс площадь тех частей, где они перекрываются. О любой числовой характеристике бинарного изображения, удовлетворяющей этому условию, говорят, что она обладает

Рис. 4.8. (см. скан) Бинарные изображения, рассматриваемые как множества.

Мы можем скомбинировать два бииариых изображения, объединяя или пересекая их как множества. Плошадь объединения двух изображений плюс площадь их пересечения равна сумме площадей исходных изображений X и

Рис. 4.9. Возможность разбиения изображения на полосы, каждую из которых анализировать просто. Для величин, удовлетворяющих свойству аддитивности, значение для всего изображения можно вычислить, исходя из значений для каждой полосы. При этом расчеты допускают пошаговую реализацию: на каждом шаге добавляется лишь одна полоса.

свойством аддитивности. Периметр также удовлетворяет этому свойству, так как сумма периметров объектов X и равна сумме периметров их объединения и пересечения. Оказывается, что число Эйлера также обладает этим свойством. Именно поэтому все три указанные характеристики представимы в виде суммы результатов локальных операций. Свойство аддитивности позволяет нам разбить изображение на небольшие части и получить окончательный ответ путем суммирования результатов операций, выполненных над этими частями. Продемонстрируем эту процедуру на примере числа Эйлера.

Рассмотрим непрерывное бинарное изображение. Выберем направление на нем и назовем его направлением смещения (рис. 4.9). Теперь разобьем изображение на полосы прямыми, ортогональными этому направлению. Любую характеристику, удовлетворяющую свойству аддитивности, можно вычислить пошагово путем добавления на каждом шаге приращения, соответствующего очередной полосе. Если текущую полосу обозначить через а уже пройденную часть изображения — через I, то из свойства аддитивности получим для числа Эйлера Теперь обратимся к вопросу, который мы еще не задавали: какова должна быть ширина полос? Полосы, для которых интереса не представляют. Нам важны «особенные» места, в которых . В случае числа Эйлера они находятся там, где полоса содержит начало нового

Рис. 4.10. Выпуклости и вогнутости в направлении смещения как существенные части областей изображения при вычислении числа Эйлера.

объекта или конец отверстия. Такие части изображения мы будем называть выпуклостями и вогнутостями в направлении смещения соответственно (рис. 4.10). В первом случае число Эйлера изменяется на величину , во втором — на величину (Обратите внимание, что лишь касаются друг друга, и, следовательно, их пересечение будет состоять из отрезков прямых.) Число Эйлера — это просто разность между числом X выпуклостей и числом V вогнутостей в направлении смещения.

Заманчиво использовать аналогию между этой разностью и той, которая фигурирует в определении числа Эйлера. Но число объектов В необязательно равно числу X, а число отверстий Н — числу V.

Рис. 4.11. Число Эйлера как разность между числами выпуклостей и вогнутостей в направлении смещения. Однако это не означает, что они должны совпадать с количеством объектов и отверстий, как иллюстрирует данный пример.

Это легко увидеть на примере объекта, сильно изрезанного в направлении смещения (рис. 4.11). Как X, так и V велики (причем X = V + 1), в то время как Иначе и не может быть, поскольку В и Н по отдельности не удовлетворяют свойству аддитивности и, значит, невычислимы путем суммирования результатов локальных операций.

Наконец, мы должны найти аналогичный метод, который применим к дискретным изображениям. Допустим, что смещение выбрано в направлении с на Тогда необходимо сосчитать число следующих ситуаций:

Например, если изображение состоит из квадрата с квадратным отверстием, то так что как оно и должно быть (рис. 4.12). При выборе другого направления смещения берутся иные маски, однако, естественно, число Эйлера не изменяется (хотя сами значения X и V могут изменяться).

Рис. 4.12. Число Эйлера для данной квадратной области с квадратным отверстием равно нулю (в направлении смещения имеются одна выпуклость и одна вогнутость).