Сегодня я расскажу о двух алгоритмах подсчёта количества объектов на изображении. Этот топик предназначен в первую очередь для тех, кто только начинает заниматься обработкой изображений. Для профессионалов ничего нового я не скажу.
В процессе высокоуровневой обработки изображений довольно часто возникает задача подсчёта количества объектов. Конечно, её можно решить с помощью алгоритма рекурсивной пометки областей (метод марок).
Вышеописанный алгоритм необходимо применить к каждому пикселу исходного изображения, меняя метки после каждого найденного объекта. После выполнения алгоритма количество объектов будет равно количеству использованных меток.
Этот алгоритм позволяет не только подсчитать количество объектов, но и отделить их друг от друга. Нетрудно заметить, что этот алгоритм использует рекурсию, а значит, у нас возникает две потенциальных проблемы. Во-первых, скорость работы алгоритма может быть недостаточной для обработки данных в реальном времени, во-вторых, потенциально нам может не хватать размера стека, особенно, если мы говорим о реализации этого алгоритма в железе (ПЛИС).
Второй метод подсчёта объектов основан на вычислении разницы между количеством внешних и внутренних углов. Внешним углом называется окрестность 2*2 пиксела, содержащая три пиксела фона и один пиксел объекта, внутренним углом называется окрестность 2*2 пиксела, содержащая три пиксела объекта и один пиксел фона.
Шаблоны внешних углов:
Шаблоны внутренних углов:
Количество объектов на изображении вычисляется, как четверть разности количества внешних и внутренних углов.
Ресурсы, требуемые для работы этого алгоритма минимальны. В программной реализации требуется однократный проход по всему изображению, а в аппаратной реализации дополнительно потребуется только два счётчика.
Важно понимать, что этот алгоритм корректно работает только при условии, что внутри объекта нет фоновых пикселов. Такие пикселы носят название шум типа «перец» и легко устраняются методами математической морфологии.
И как всегда, вы можете скачать программу, реализующую описанные алгоритмы:
P.S. Если тема интересна, могу написать топик, о реализации алгоритмов обработки изображений на ПЛИС.
В процессе высокоуровневой обработки изображений довольно часто возникает задача подсчёта количества объектов. Конечно, её можно решить с помощью алгоритма рекурсивной пометки областей (метод марок).
пометить (точка, метка)
начало
если (точка не принадлежит фону и не помечена) то
начало
присвоить точке метку(точка, метка);
пометить(точка выше, метка);
пометить(точка ниже, метка);
пометить(точка левее, метка);
пометить(точка правее, метка);
конец
конец
Вышеописанный алгоритм необходимо применить к каждому пикселу исходного изображения, меняя метки после каждого найденного объекта. После выполнения алгоритма количество объектов будет равно количеству использованных меток.
Этот алгоритм позволяет не только подсчитать количество объектов, но и отделить их друг от друга. Нетрудно заметить, что этот алгоритм использует рекурсию, а значит, у нас возникает две потенциальных проблемы. Во-первых, скорость работы алгоритма может быть недостаточной для обработки данных в реальном времени, во-вторых, потенциально нам может не хватать размера стека, особенно, если мы говорим о реализации этого алгоритма в железе (ПЛИС).
Второй метод подсчёта объектов основан на вычислении разницы между количеством внешних и внутренних углов. Внешним углом называется окрестность 2*2 пиксела, содержащая три пиксела фона и один пиксел объекта, внутренним углом называется окрестность 2*2 пиксела, содержащая три пиксела объекта и один пиксел фона.
Шаблоны внешних углов:
Шаблоны внутренних углов:
Количество объектов на изображении вычисляется, как четверть разности количества внешних и внутренних углов.
Ресурсы, требуемые для работы этого алгоритма минимальны. В программной реализации требуется однократный проход по всему изображению, а в аппаратной реализации дополнительно потребуется только два счётчика.
Важно понимать, что этот алгоритм корректно работает только при условии, что внутри объекта нет фоновых пикселов. Такие пикселы носят название шум типа «перец» и легко устраняются методами математической морфологии.
И как всегда, вы можете скачать программу, реализующую описанные алгоритмы:
P.S. Если тема интересна, могу написать топик, о реализации алгоритмов обработки изображений на ПЛИС.
