nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

Cвязанный список: больше треша!

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

Ладно, непосредственные значения заработали, половину написанного переписал (реально код покомпактнее стал), уже вроде разобрался с массивом ярких точек - и потом стёр всё нафиг, чтобы сделать на связанном списке.

И вот теперь уже начинает всё складываться, код упростился, есть ощущение "может взлететь!", но чтобы совсем не закопаться в множестве граничных вариантов, надо сделать ещё один финт ушами.

Такого ужаса вы не найдёте в языках высокого уровня:
	Nil		EQU	-32768
	ActivePoints	dw	APHeadDummyX
	APHeadDummyX	dw	Nil
	APTailDummyX	dw	32767
	AllPoints	dw	Nil

	Heap		dw	Elem0
	Elem0:
	Elem0Next	dw	Elem1
	Elem0X		dw	?
	Elem0Y		dw	?
	Elem0L		dw	?
	Elem0P		dw	?
	Elem1		dw	Elem2,?,?,?,?


Вроде как у нас ActivePoints - это указатель на первый элемент списка найденных точек, и первоначально он должен быть пуст. Однако, указатель не нулевой, и указывает он буквально на следующее слово, что очень пугает, ведь каждый элемент должен занимать 5 слов, а здесь всего 2 слова, а затем уже идёт указатель AllPoints (другой список, ОКОНЧАТЕЛЬНО обнаруженных точек), а потом и вовсе указатель Heap!

Что же здесь творится?
Если коротко: моя жадность не знает границ!

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


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


Получается, что прежде чем добавлять в список новую точку, когда мы её обнаружили на том отрезке, где именно ждали "новой точки" (а не уточнения координат уже найденной), надо проверить: а вдруг она непосредственно примыкает к уже обнаруженной точке слева, или к уже обнаруженной точке справа?

Для этого нужно заглянуть в предыдущий элемент списка, а также в последующий. Но прежде чем это сделать, надо проверить, а точно ли они существуют? Причём отсутствие точки справа ещё можно узнать по "нулевому указателю", а вот отсутствие точки слева проверяется тупо сравнением адреса указателя - если он равен ActivePoints, значит, точки слева нет.

Выходит, что нужно проверить наличие точки слева, и при её наличии проверить "прилегание вплотную", затем проверить наличие точки справа и снова проверить "прилегание" - громоздко оно как-то, и медленно, НЕ ХОЧУ!

Поэтому сделаем, чтобы точки слева и справа БЫЛИ ВСЕГДА, пусть даже и фиктивные. Причём если мы натыкаемся на фиктивную точку, условие "прилегания вплотную" заведомо не выполнится.

Листинг, приведённый выше, и описывает две фиктивные точки, но таким образом, чтобы не отожрать два полноценных элемента в памяти, то бишь 10 слов, 20 байт. А именно, теперь и указатель на список, ActivePoints - это вполне себе элемент:

ActivePoints (отступ 0) - ссылка на следующий элемент,
APHeadDummyX (отступ 1) - координата X левой фиктивной точки, Nil = -32768. Любое значение от 0 до 1023 явно не "прилегает вплотную" к точке, столь смещённой влево!
APTailDummyX (отступ 2) - координата Y левой фиктивной точки, получается 32767, но это абсолютно неважно,
AllPoints    (отступ 3) - яркость левой фиктивной точки, тут значения могут меняться, но и это неважно, мы эту яркость проверять никогда не будем,
Heap         (отступ 4) - "размер" левой фиктивной точки, тоже будет меняться в довольно узком диапазоне по мере "выделения памяти", но и это неважно, каким бы он ни был, он никогда не сможет обеспечить "прилегание" к точке с координатой -32768. 


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

APHeadDummyX (отступ 0) - ссылка на следующий элемент, пустой указатель,
APTailDummyX (отступ 1) - координата X правой фиктивной точки, 32767. Любое значение от 0 до 1023 явно не будет "прилегать вплотную" к этой точке!
...


Главное только аккуратно "освободить" этот список в конце работы. Когда мы пройдём все строки изображения, надо будет "перецепить" весь список ActivePoints в конец списка AllPoints, но в последнем "реальном" элементе переделать ссылку - она указывала на правую фиктивную точку, а нужно сделать пустой указатель. Ещё подумаем, как это лучше всего сделать. Можно и тут попытаться сделать "финт ушами" - тупо заставить эту программу обработать больше строк изображения, чем есть на кадре, так, чтобы на "нижних строках" уже точно ничего нельзя было обнаружить. Зато все эти точки из ActivePoints "естественным путём", в порядке своей Y-координаты перейдут в список AllPoints, и мы получим список всех обнаруженных точек, отсортированный по Y-координате. По крайней мере, для матрицы 1205ХВ014 это выглядит самым подходящим методом, ведь там нам нужно 10 кадров в секунду, а обработать каждый кадр (снять с него все данные) мы сможем за 21 мс в наихудшем случае (если так и застрянем на 25 МГц), а вообще надо стремиться к 10 мс, а то и почти 5 мс, чтобы поменьше было эффекта Rolling Shutter. В общем, совершенно очевидно, что после получения кадра у нас времени вагон - можно и отдохнуть, обрабатывая "пустые строки"...

Вот для лабораторного макета, где вместо этой матрицы стоит китайская аналоговая камера высокой чёткости, может такое и не пройти - пока будем соображать, пойдёт уже следующий кадр! Хотя, их 25 кадров в секунду, можно и действительно половину выкинуть на первых порах. Хотя интереснее было бы максимально всю информацию задействовать, конечно. И с 1205ХВ014 было бы неплохо по мере снижения времени экспозиции (а чем мы ближе - тем ярче отражённый сигнал) успевать делать всё больше и больше кадров за свои отведённые 200 мс, всё-таки усреднение это великая вещь!
Tags: ПЛИС, программки, работа, странные девайсы
Subscribe

Recent Posts from This Journal

  • О вытягивании себя из болота по методу Мюнхгаузена

    Всё готовлюсь к встрече с представителями РКК Энергия, нужно убедить их в моём способе определения положения ВидеоИзмерителя Параметров Сближения на…

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

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

  • Гетто-байк

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

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments