nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

Супрематический алгоритм обнаружения (продолжение)

Наконец-то узнал, как называется то, чем я сейчас занимаюсь: BLOB DETECTION. Пошерстил литературу, народ развлекается кто во что горазд, свёртки, вейвлет-преобразования для изучения изображения на разных масштабах, выделение контуров и чего только нет. Чуваки на Pentium II 500 МГц различные методы испытывали, на изображениях 800х640, и получали время обработки от 0,7 до 36 секунд.

Но мне-то надо на 1024х1024 получить время обработки эдак 40 мс (1/25 секунды), при частоте 25 МГц.

В общем, подумалось мне про этих академиков:


Из более простого, наткнулся на видюшки Coding Train (раз, два), где по сути излагается мой "изначальный" алгоритм, ещё не оптимизированный, т.е на каждом пикселе проверяются расстояния до всех ранее обнаруженных пятен. Видно, что оно худо-бедно может работать, хотя поначалу, когда он поставил маленькое "расстояние между пятнами" (примерный аналог моего D1), была та же фигня - огромная толпа отдельных точек, которые у него "объединяться" не умеют.

Ладно, офигительно простого, быстрого и надёжного алгоритма не нашли, попробуем всё-таки свой домучать...

Итак, поначалу на месте 5 пятен обнаруживалось 24. Поковырявшись в алгоритме, удалось "сократить" их количество до 916, потом до 612, после чего, ещё поднапрягшись - до 13 точек.

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


Как мне пока представляется, слияния будут возникать на верхних строках обнаружения пятна, там где длина строки очень резко растёт, из-за "бесконечной производной" выражения



при y=0.

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

по крайней мере, именно такую картину я наблюдал при отладке.

Отсюда вывод: можно не очень сильно заморачиваться с определением "центра нового пятна", как-то хитро выделяя веса. Возьмём среднее арифметическое от центров двух "сливаемых" пятен - и всё тут! А диаметр пусть будет суммой диаметров, что также имеет определённый смысл. Y-координату, возможно, вообще трогать не будем.

В кои-то веки у нас не только будут добавляться новые пятна (переходить из списка Heap "свободных элементов" в список ActivePoints), "выходить из рассмотрения" (переходить из списка ActivePoints в список AllPoints), но ещё и УДАЛЯТЬСЯ (переходить из списка ActivePoints в список Heap).

Слияние двух пятен может произойти, когда одно из них увеличилось в размерах и изменились его координаты, т.е когда оно "поглотило очередную обнаруженную точку". И тут можно схитрить: когда мы проверяем отрезок между двумя пятнами и обнаруживаем там яркую точку, мы сначала проверяем, не слишком ли она близко к пятну слева от себя, а после этого - не слишком ли она близко к пятну справа от себя? Так вот, если вторая проверка понадобилась, значит этим пятнам сливаться ещё рано, потому как иначе точка могла бы принадлежать и тому, и другому! Благодаря этому можно осуществлять слияние только в одном месте, с пятном "справа от себя". Мелочь, а приятно.

Крайне неприятно другое: мы заказывали отрезки для обработки текущей строки, и используем список пятен, чтобы понимать, чему эти отрезки соответствуют. При удалении одного из пятен, нужно не забыть взять "лишние задания" оттуда, иначе всё собьётся! Собственно, уже налетел на это, "ушло в разнос".

Первым делом просто добавил получение "теперь уже ненужных" результатов обработки по правому пятну (которое уже объединилось с левым), чтобы не нарушить порядок. И тут же "с размаху" влетел в другую неприятность: поскольку проверив ЛЕВОЕ пятно, и решив что оно пока никуда не уходит, мы уже выдали задание на следующую строку, ещё ДО ТОГО, как два пятна слились в одно, то при обработке очередного задания может получиться координата, которую обработчик ну никак не ожидал - и у меня нарушается порядок "слева направо" в списке точек!

Тут можно поставить ещё один костыль - проверять координату, что она ровно на том отрезке, который мы ожидали, но это всё-таки костыль.

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

Как обычно, можно эту проблему решать "программно" или "аппаратно". В первом случае не даёшь ACQ (Acquire) при первой возможности, а лишь ставишь какой-то флажок "нам ещё задания нужно выдать по предыдущему пятну", и уже позже, когда уточним координаты этого пятна (то ли путём включения дополнительной точки, то ли слиянием двух пятен) выдадим эти задания, уже скорректированные.

Во втором - придётся вместе с ACQ ввести ещё одну команду, что-то типа UPD, которая не добавляет новое задание на обработку, а замещает собой последнее добавленное.

Традиционно не знаю, что из этого лучше, возможно что сделаю и так, и эдак, но при условии, что оно вообще окажется работоспособным!

Пока что всё у нас "программно", на персоналке, просто алгоритм проверить надо...

Практически "с нахрапу", получилось 8 пятен:



Пять пятен неплохо соответствуют реальным, но всё-таки осталось ещё 3 лишних, все сдвинуты влево и вниз.

Наконец, понаблюдав выполнение по нижнему левому пятну (оно несколько обособлено от других: верхние пятна уже перешли из ActivePoints в AllPoints, а нижнее правое ещё не попадает по нашим строкам), понял: я указал слишком жёсткий критерий для слияния пятен, они уже фактически должны касаться друг друга, но если так произойдёт, то отрезок между ними превратится в "пустой", и тогда мы до слияния точек так и не дойдём!

Как только сделал критерий более адекватный (между пятнами, взятыми "по максимуму", расстояние должно получиться не больше чем D1=3 пикселя, а наверное увеличу и до 4 пикселей), получил очень приятную картинку:




Может показаться опасной близость двух пятен "в центре композиции", дескать, ещё чуть-чуть развернуть мишень - и они тоже могут объединиться в одно пятно. Ничего подобного! Чтобы пятна объединились, между ними тоже должен быть "мостик" из ярких точек, иначе никак. То есть, в принципе алгоритм позволяет им перекрыться, ничего шибко страшного в этом быть не должно!

Осталось за малым - переписать этот алгоритм на ассемблере для QuatCore (точнее, подправить существующий) - и отладить "на железе". Вот это успеть до нового года - вполне реально!
Tags: ПЛИС, программки, работа, странные девайсы
Subscribe

  • Ремонт лыжных мостиков

    Вернулся с сегодняшнего субботника. Очень продуктивно: отремонтировали все ТРИ мостика! Правда, для этого надо было разделиться, благо народу…

  • Гетто-байк

    В субботу во время Великой Октябрьской резни бензопилой умудрился петуха сломать в велосипеде. По счастью, уже на следующий день удалось купить…

  • А всё-таки есть польза от ковариаций

    Вчера опробовал "сценарий", когда варьируем дальность от 1 метра до 11 метров. Получилось, что грамотное усреднение - это взять с огромными весами…

  • Так есть ли толк в ковариационной матрице?

    Задался этим вопросом применительно к своему прибору чуть более 2 недель назад. Рыл носом землю с попеременным успехом ( раз, два, три, четыре),…

  • Big Data, чтоб их ... (4)

    Наконец-то стряхнул пыль с компьютерной модели сближения, добавил в неё код, чтобы мы могли определить интересующие нас точки, и выписать…

  • Потёмкинская деревня - 2

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

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 9 comments