nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

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

Сколько-нибудь наладили "железо", сейчас пора заняться документацией (все вдруг "очнулись" под конец года и хотят ещё бумажек!), но ровно сегодняшний день надо с алгоритмом обнаружения позаниматься.

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

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

Если точка не попала внутрь пятна обнаруженного ранее, но стоит на самой-самой его границе, значит нужно чуть увеличить диаметр ранее обнаруженного пятна и передвинуть координаты центра чуть в сторону новой обнаруженной точки.

И наконец, если яркая точка обнаружена "на почтительном расстоянии" от ранее обнаруженных "пятен", мы добавляем новое "пятно", назначая ему центр по этой новой точке и радиус "номинальный".


Сложности начинаются, когда мы отказываемся каждый раз пробегать по всем обнаруженным пятнам, поэтому решаем применить связанный список, в котором слева направо идут обнаруженные "пятна", которые ещё "представляют интерес" (мы не ушли от них далеко-далеко вниз), и возникает весёлая логика обслуживания этого списка (как добавлять в него пятна и вовремя удалять их), а когда всё это должно делаться "в реальном времени", пока видеопроцессор переваривает входной поток со скоростью 1 пиксель за такт, получается ещё веселее!

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

Вот, на компьютерной модели, берущей картинку, полученную с макета, заработало почти корректно :)
Just13points.png


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


Похоже на правду :) В смысле, столь же криво работает по такого рода картинкам. Не один в один, потому как и исходный материал мог различаться, я ведь до сих пор не сделал, чтобы по ОДНОМУ И ТОМУ ЖЕ КАДРУ приходили и результаты обнаружения (ну или дамп памяти), и сам кадр! Но сильно доводить до ума ИСХОДНЫЙ алгоритм и нет смысла, учитывая, насколько он кривой.

Осталось его подправить!

В первую очередь, мы будем ВСЕГДА начинать с малого диаметра, 3 пикселя. Так что проблема в подборе правильного диаметра отпадёт сама собой. И если поначалу "слияние пятен" казалось чуть ли не "исключительной ситуацией", которая случится скорее при появлении солнышка в кадре, то сейчас это становится ШТАТНОЙ РАБОТОЙ, и именно за счёт слияний мы "анализируем пятно".

Далее, нужно подправить слияние по горизонтали, оно же пока что единственное слияние, которое у нас есть. И вот тут давайте вспомним, что на самом деле алгоритм работает не с окружностями, а квадратами с окружностями в метрике Чебышева, которые выглядят очень супрематично!

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

На данный момент слияние было сделано совсем криво:


Когда справа от пятна обнаруживалась яркая точка, центр пятна мы не сдвигали, только меняли его диаметр, причём в этом ОШИБЛИСЬ В ДВА РАЗА! Поэтому при каждом таком слиянии пятно реально уменьшалось в размерах, и это ни к чему хорошему не привело.

А надо делать вот так:


Если справа от пятна с координатами (X,Y) и диаметром D мы находим точку с координатами (x,y), то попробуем так видоизменить исходное пятно, чтобы вся предыдущая занимаемая им площадь осталась бы при нём, но и ещё оно бы "поглотило" новую точку. Проще всего будет не двигаться по координате Y (супрематичненько!), диаметр D заменить на D'=(x-X+D/2), и координату X заменить на X' = x - D'/2.

Если же точку мы обнаружили слева от пятна (в непосредственной близости), то диаметр D заменяем на D'=(X+D/2-x), и координату X заменяем на X' = x + D'/2.

Как только мы введём хотя эту логику, при D=3, получим такое:


Вообще, на этом изображении должно быть ПЯТЬ пятен. Первый раз, непосредственно на макете, было обнаружено 24 штуки. А сейчас и вовсе 916 штук (!!!)

Граничный случай не рассмотрели подробнее, что происходит, если точка найдена СРАЗУ ЖЕ за пятном с диаметром 3. Тогда D/2 даёт единичку (округление ВНИЗ), и диаметр пятна вовсе не увеличивается, оно лишь дрейфует вправо. Ага, надо делать округление вверх в D/2. После этого получаем так:


612 обнаруженных точек.

Многовато!

С удивлением обнаруживаю, что и сейчас точки "расти" не хотят категорически! Как был диаметр 3 - так и остаётся, как был 5 - так и остаётся 5. Смотрим внимательнее, как заказываются отрезки на обработку. Если было пятно с координатой X и диаметром D, то к следующему разу заказывается один отрезок до X-D/2 (округление вниз), второй: до X-D/2+D. И затем третий будет от этой точки вверх. При D=3, получаем один отрезок до X-1, НЕ ВКЛЮЧАЯ X-1, т.е [0;X-2], следующий (который должен нашу точку выражать): от X-1 до X+1, и третий от X+2 и дальше. Пока что симметрично.

Когда диаметр обновляется до 4, получается веселее: заказывается отрезок до X-3 (как бы не входящий в это пятно), затем от X-2 до X+1 (входит в пятно) и затем от X+2 и дальше. Тут-то и оказывается, что мы обнаруживаем новую точку с координатой X+2, которую как бы надо "слить" с пятном, но как результат, диаметр с 4 "обновляется" до (X+2-X) + 2 = 4, т.е не меняется. Да и центр пятна в итоге остаётся на месте. И в результате распространения пятна вправо не происходит, мы упираемся по координате.

Так что нужно вести себя немножко агрессивнее, и вместо ABS(X-x) + D/2 или даже ABS(X-x) + (D+1)/2 написать ABS(X-x) + D/2 + 1. Вот тогда, глядишь, процесс пойдёт :)

Но не очень-то:


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

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

"Для единообразия" здесь диаметр также обновляется до ABS(Y-y) + D/2 + 1, и вот тогда наконец-то что-то начинает получаться:


(повторение картинки из начала поста)
Всего 13 пятен там, где их должно быть 5.

Причём, два пятна (те, что справа), вообще получились правильно, по одному пятну, причём и центр, и диаметр вполне "угадали", и это без априорных сведений о дальности или предполагаемом диаметре пятен, т.е начали мы с D=3.

А слева у нас случилась вещь, которую я в общем-то уже давно ожидал, и про неё говорил "продумал всего на шаг вперёд, а не на два". Проблема в том, что у нас обнаруживается пятно худо-бедно посередине, а потом на левом краю обнаруживается ещё одно, которое поначалу "изолировано". Но затем оба эти пятна расширяются, а вот слияние двух УЖЕ ОБНАРУЖЕННЫХ ПЯТЕН у нас не было предусмотрено!

Поэтому они так и продолжают сидеть друг поверх друга, и что удивительно, не сильно мешаются.


Продолжение следует...
Tags: ПЛИС, программки, работа, странные девайсы
Subscribe

  • Калифорния спятила

    Купил тут ключ для снятия бонок велосипеда (хитрых гаек, скрепляющих передние звёзды): Весь из себя фирменный, других в магазине не было. Но я…

  • Про интерференционный светофильтр

    В данном приборчике, видеоизмерителе параметров сближения, хочется максимально отгородиться от паразитной засветки, проще говоря от Солнца. Для…

  • Королёвские котики и тепловоз

    Акынский пост - "что вижу, о том пою!" Кот-консьерж ушёл в отпуск: в кои-то веки можно не стоять у входа на проходную, а лежать на солнышке!…

  • Как бы Штиль

    Мне тут отдали даром бензопилу, один из Сафроновцев. Когда он её из сумки начал вытаскивать, я немножко прифигел, неужто новенького Штиля отдаёт??…

  • Топ-топ менеджер с бензопилой

    Опять надо было в РКК Энергию поехать, в Подлипки, а оттуда на работу. Решил и бензопилу прихватить, чтобы спилить всё, что упало неделю назад.…

  • Как продлить агонию велотрансмиссии на 1500+ км

    Последний раз о велосипедных делах отчитывался в середине мая, когда прошёл год "велопробегом по коронавирусу". Уже тогда я "жаловался", что…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 5 comments