9.5. БЫСТРЫЙ АЛГОРИТМ ПРОРЕЖИВАНИЯ

Алгоритмы, рассмотренные в предыдущих разделах, осуществляют процедуру прореживания, систематически обрабатывая все изображения целиком. Встречаются, однако, такие прикладные задачи, при решении которых хранение изображения в памяти оказывается непрактичным, а прореживание целесообразно проводить более простым способом. Алгоритм 9.4 реализует чрезвычайно простой способ прореживания, но при обработке многих объектов выделить части остова с его помощью не удается. С

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

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

Определение 9.4 а. Вертикальным маршрутом ГСС называется такой маршрут, ширина всех вершин которого меньше значения заданного порога и число вершин которого больше заданного значения

Определение Горизонтальным маршрутом ГСС называется такой маршрут, ширина всех вершин которого больше порогового значения число вершин которого меньше значения а вершины, расположенные по обеим сторонам маршрута, имеют ширину, не меньшую порогового значения — расстояние между линиями просмотра).

Определение 9.4 в. Диагональным маршрутом ГСС с углом наклон называется такой маршрут, все центры вершин которого приближенно коллннеарны (чтобы убедиться в этом, можно воспользоваться одним из алгоритмов, приведенных в гл. 12), угол наклона прямой, проходящей через эти центры, равен ширина всех вершин меньше значения и число вершин больше значения

Пример 9.1. На рис. 9.7, а представлен силуэт изображения и соответствующий ГСС. Видно, что два ребра точно выделены и идентифицированы алгоритмом 9.4. Поскольку ширина всех вершин мала, подмаршрут 1—7 можно считать вертикальным штрихом Вершина 8 сама по себе образует подмаршрут, который можно рассматривать как горизонтальный штрих Если бы вершина 7 не входила в первый подмаршрут, ее можно было бы использовать в качестве вершины, связывающей два выделенных штриха. Пример, приведенный на рис. 9.7, б, иллюстрирует случай, когда с помощью данного алгоритма не удалось выделить криволинейный штрих Вершину 3 как таковую можно было бы считать горизонтальным штрихом, однако, наличие вершины 4 исключают вынесение такого классификационного решения

Алгоритм 9.4. Быстрый алгоритм прореживания

(см. скан)

(см. скан)