nabbla (nabbla1) wrote,
nabbla
nabbla1

Category:

Нахождение яркостного центра пятна

Пора, наконец-то, взяться вплотную за видеообработчик!

Возможно, для начала нужно будет немножко сигнал "подрихтовать" - устранить "битые пиксели", если таковые появятся. В этом больших проблем не вижу, по крайней мере, при наших довольно щадящих требованиях по радиационной стойкости. Думаю, поставлю критерий "если яркость пикселя существенно выше или существенно ниже, чем среднее от его соседей, признаём его битым и заменяем на это среднее". Поскольку у любого объектива есть функция рассеяния точки (ФРТ), т.е даже точечный объект никогда не займёт СТРОГО ОДИН ПИКСЕЛЬ, а на самом деле расползётся в площадку, у нас это 3х3 (чтобы субпиксельную точность получить), то оно вполне себе сработает.

А пока о самом сложном, на мой взгляд. Видеообработчику посылаются предполагаемые координаты ярких точек (наших мишеней), некие (x0, y0). И затем, когда он начинает получать текущий кадр строка за строкой, пиксель за пикселем, он должен для всех точек на расстоянии менее R от (x0, y0) найти выражения:


(сумма яркостей всех пикселей),


(сумма яркостей пикселей, помноженных на их горизонтальное смещение от предполагаемого центра)

и

(теперь умножаем на вертикальное смещение от предполагаемого центра)

И затем, уже на QuatCore можно будет получить:

и


это смещение яркостного центра от предполагаемой позиции, измеренное С СУБПИКСЕЛЬНОЙ ТОЧНОСТЬЮ.

Можно было бы посчитать яркостный центр напрямую, заменив x0, y0 на ноль, но тогда промежуточные значения могут получаться ОЧЕНЬ БОЛЬШИМИ. Зная, что пятна имеют хоть сколько-нибудь ограниченный размер, используя "мои" формулы с x0 и y0, можно несколько облегчить себе жизнь.

Поразмышляем, как это реализовать "в железе"...


Ещё пару слов о входящих сюда величинах. Яркость пикселя выражается как 12-битное беззнаковое число, 0 - самый чёрный, 212-1 - самый светлый. Радиус пятна никогда не будет превышать 128 пикселей. Скажем так, реально пятна будут ещё меньше, но при минимальной дальности до мишени, минимальное расстояние между ЦЕНТРАМИ двух пятен будет около 200 пикселей. Я хочу при этом использовать "радиус пятна" около 100 пикселей, чтобы получить максимальную "зону сопровождения", то есть, даже при довольно сильном смещении картинки относительно предыдущего кадра, я устойчиво определю координаты ярких точек, они не выйдут за пределы этих радиусов. Таким образом, величины (i-x0) и (j-y0) будут выражаться 8-битными числами со знаком (дополнительный код). Получающиеся суммы можно будет ещё "ограничить сверху", исходя из реального размера пятен.

Подход "в лоб": поставить два перемножителя и три сумматора - и вперёд!

На новой серии ПЛИС, 5578ТС..., вполне можно так сделать, там есть аппаратные умножители 18х18, в каких-то безумных количествах, выполняющие эту операцию за один такт - вообще не вопрос! Если не получится утрамбоваться в 5576ХС6Т (2880 ЛЭ и никаких тебе перемножителей, и никаких ФАПЧ/PLL), так и поступлю.

Но давайте всё-таки "помучаемся" и подумаем, как это выполнить, если аппаратные перемножители отсутствуют, и новые числа для умножения поступают КАЖДЫЙ ТАКТ, и мы не должны "захлёбываться", на частоте хотя бы 25 МГц, на не самой шустрой ПЛИС. (мотивация: так много ПЛИС, а надеть нечего)

За вертикаль пусть отвечает QuatCore!
Задачу можно сразу же упростить ВДВОЕ, если видеообработчик будет сбрасывать суммы в начале каждой новой строки (а точнее, в начале каждого нового ОТРЕЗКА от x0-R до x0+R) и вычислять лишь две суммы именно ПО ОТРЕЗКУ:


(очевидно, куда без неё!)

и


(т.е нахождение смещения по ГОРИЗОНТАЛИ)

Мотивация очень простая: величина (j-y0) на всём протяжении строки не меняется, а потому элементарно выносится за скобки. И только когда мы закончим весь отрезок, мы полученную сумму яркостей пикселей на нём помножим на (j-y0), причём это может сделать уже QuatCore. Одно дело, справиться с умножением на каждом такте, а другое дело - "одолеть" 2-3 умножения ЗА ВСЮ СТРОКУ.

Можно было бы отказаться и от второго умножения, вынеся (i-x0) за скобки. Т.е мы сначала находим суммы пикселей по столбцам, а только потом умножаем на номер столбца. Но это требует возни с памятью со стороны видеообработчика: извлечь из памяти текущую сумму по данному столбцу, прибавить новое значение и занести назад. Причём, у нас по горизонтали может оказаться несколько пятен сразу, и мы должны хранить промежуточные значения для них всех.

Наверное, самым простым вариантом будет завести массив в 1024 элемента (по числу столбцов фотоприёмной матрицы), причём каждое число по-хорошему должно быть шириной в 20 бит, чтобы точно не случилось переполнения, когда суммируешь так много значений, а это потребует 6 блоков внутренней памяти (БВП, они же Embedded Array Blocks) по 512 байт каждый, при том, что в 5576ХС6Т их ВСЕГО ДЕСЯТЬ! По крайней мере, один из них должен уйти на оперативную память для QuatCore, и по крайней мере два - на ПЗУ кода для него же. И ещё 2 штуки - чтобы сохранить предыдущую строку изображения при устранении "битых пикселей", итого 5. Это минимум.

Поэтому я склоняюсь к мысли, что лучше уж умножитель.

Суммирование яркостей
И начинаем с самого простого, нахождения

ПО ОДНОЙ СТРОКЕ.

По "наихудшему случаю", нам нужен 20-битный сумматор, поскольку 12 бит - это для одного пикселя, а если их в строке будет аж 256 штук (от -128 до +127), и все самые яркие - их сумма как раз еле-еле влезет в 20 бит. Да, на деле я рассчитываю на максимальный диаметр 200 (это оценку не меняет, все равно 20 бит), но главное - что размер самого пятна будет гораздо меньше, чем эта зона радиусом в 100 пикселей. Скорее всего, вместо одинарного пятна, будет вообще "созвездие" из 9 штук, по количеству светодиодов подсветки (в уголковом отражателе мы увидем изображение своего осветителя), но всё это может быть размазано, поскольку объектив настроен на гиперфокал, и на 0,5 метров, т.е "перед своим носом", выйдет несколько не в фокусе.

Пожалуй, сделаю размер сумматора "параметризуемым", и потом, по реальным данным его могу несколько подсократить.

Получилась вот такая хреновина:
module PixelAdder12bit (input clk, input sclr, input [11:0] Pixel, output [PixSumWidth-1:0] Q);

parameter PixSumWidth = 20;

localparam CounterWidth = PixSumWidth - 12;

	wire [11:0] Sum;
	reg [11:0] LowerQ = 12'h000;
	wire PlusOne;
	lpm_add_sub Adder (	.dataa (Pixel),
				.datab (LowerQ),
				.cin (1'b0),
				.result (Sum),
				.cout (PlusOne));
	defparam
		Adder.lpm_direction = "ADD",
		Adder.lpm_hint = "ONE_INPUT_IS_CONSTANT=NO,CIN_USED=NO",
		Adder.lpm_representation = "UNSIGNED",
		Adder.lpm_type = "LPM_ADD_SUB",
		Adder.lpm_width = 12;	
		
	always @(posedge clk)
		LowerQ <= sclr? 12'h000 : Sum;
		
	wire [CounterWidth-1:0] CounterOut;
	lpm_counter UpperBits (	.clock (clk),
				.cnt_en (PlusOne),
				.sclr (sclr),
				.Q (CounterOut));
	defparam
		UpperBits.lpm_direction = "UP",
		UpperBits.lpm_port_updown = "PORT_UNUSED",
		UpperBits.lpm_type = "LPM_COUNTER",
		UpperBits.lpm_width = CounterWidth;
		
	assign Q = {CounterOut, LowerQ};
endmodule


Когда у нас только начинается отрезок для суммирования, мы подаём sclr=1 (синхронный сброс), затем подаётся по пикселю за такт - и накапливается их сумма. Дешево и сердито.

Как видно, сумматор у меня всего лишь 12-битный, а для старших 8 бит (или меньше, если параметр поменяю) - СЧЁТЧИК. Разумеется, это из жадности: для каждого бита сумматора нужно 2 ЛЭ, один - непосредственно сумматор, второй - регистр, который хранит результат и позволяет сбросить его. А вот на каждый бит счётчика идёт лишь один ЛЭ.

В итоге такая штука синтезируется в 34 ЛЭ, довольно неплохо. 24 ЛЭ уходит на 12-битный сумматор с накоплением, ещё 8 ЛЭ - на счётчик, а куда ещё 2 ушло - не знаю, но так бывает.

Скорость работы безумная: может на 89 МГц работать! Я уже от таких частот отвык немного...

Пока не проверял, у меня этап "примерки" :)

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


Умножение 12-битного беззнакового числа на 8-битное со знаком сводится к сдвигам и сложениям. И если сдвиги могут "аппаратно" реализовываться просто как правильная коммутация элементов между собой, т.е не отжирать ЛЭ, то от 7 сложений мы никуда не денемся. Это 3 слоя сумматоров. Можно и попробовать, вдруг получится "в лоб"...

Вот результат умножения совершенно точно должен являться 20-битным числом со знаком! Если самый яркий пиксель имеет значение 4095, то при умножении на -128..+127 у нас могут получиться числа в диапазоне -524160..520065, тут ничего не попишешь. (Вот при умножении 12-битного числа СО ЗНАКОМ на 8-битное СО ЗНАКОМ можно было бы одно-единственное значение "насытить" - и уместиться в 19 бит, а знаковое на беззнаковое - интервал всяко пошире). А вот результат суммирования, по моим прикидкам, должен влезать в 26 бит, поскольку радиус будет не более 100, и у нас получается сумма арифметической прогрессии: 4095 * (1+2+3+4+....+100) = 4095 * 5050 (это ещё юный Гаусс вывел) = 20679750, это число умещается в 25 бит, но результат у нас должен быть со знаком (поправка как "в плюс", так и "в минус"), так что 26. Опять же, полагаю, что на самом деле можно подсократить, пятно будет меньше чем 100 пикселей в поперечнике, так что, быть может, сокращу немного. Так что этот параметр тоже сделаем параметризуемым.

Давайте попробуем поставить готовый библиотечный блок.

lpm_mult умеет либо умножать беззнаковое на беззнаковое, либо знаковое на знаковое, и мой вариант, 12x8 сразу же разворачивается в 153 ЛЭ (без знака), либо в 132 ЛЭ (со знаком). Если же я добавлю "фиктивный знак" для пикселей, 13-м битом, это выйдет 141 ЛЭ. В принципе, жить можно. Если поделить на 7 (а мы понимаем, что без 7 сумматоров мы никуда не денемся), получается по 20 ЛЭ на каждый, что вообще-то логично.


Ещё есть altmult_add, так оно выглядит с настройками по умолчанию:


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

Тут уже можно было задать один вход со знаком, второй без знака. Но размер получается больше, 181 ЛЭ. в принципе, похоже на 141 ЛЭ, к которым прицепили регистры на входе и на выходе. Похоже, это оно и есть. Может, пригодится.

И, наконец, есть altmult_accum (MAC), умножение с накоплением. Увы, настроек мало до безобразия: сделать вход обнуления нельзя, что вообще очень странно:


(во всякие more options лез, там этого нет).
Ещё и жрёт как не в себя, 293 ЛЭ, да это ж больше половины моего QuatCore!

Пожалуй, для начала попробую умножитель 13 бит на 8 бит, со знаком.

Получилось как-то так:
//один из наиболее громоздких модулей в видеообработчике.
//X - координата относительно предполагаемого центра пятна, -128..+127 (дополнительный код)
//Pixel - яркость текущего пикселя
//Мы вычисляем сумму X*Pixel, для измерения яркостного центра пятна с субпиксельной точностью
//Выход формируется с задержкой 3 такта (требуется время, пока сигнал пройдёт через несколько сумматоров)
//по приходу sclr сумма сбрасывается, и мы ТУТ ЖЕ можем приняться за следующее пятно.

module HorPixelEstimator (input clk, input sclr, input [7:0] X, input [11:0] Pixel, output [MulPixelWidth-1:0] Q);

parameter MulPixelWidth = 26;
parameter LatchInput = 1'b1;

localparam CounterWidth = MulPixelWidth - 20;

reg [7:0] rX = 1'b0;
reg [11:0] rPixel = 1'b0;

always @(posedge clk) begin
	rX <= X;
	rPixel <= Pixel;
end

wire [7:0] iX = LatchInput? rX : X;
wire [11:0] iPixel = LatchInput? rPixel : Pixel;
	
wire [19:0] MulResult;

lpm_mult	lpm_mult_component (
				.dataa ({1'b0,iPixel}),
				.datab (iX),
				.result (MulResult),
				.aclr (1'b0),
				.clken (1'b1),
				.clock (1'b0),
				.sum (1'b0));
	defparam
		lpm_mult_component.lpm_hint = "MAXIMIZE_SPEED=5",
		lpm_mult_component.lpm_representation = "SIGNED",
		lpm_mult_component.lpm_type = "LPM_MULT",
		lpm_mult_component.lpm_widtha = 13,
		lpm_mult_component.lpm_widthb = 8,
		lpm_mult_component.lpm_widthp = 20;

reg [19:0] rMulResult = 1'b0;

always @(posedge clk)
	rMulResult <= MulResult;
		
reg [19:0] Acc = 1'b0;
wire PlusOne;
wire [19:0] Sum;

lpm_add_sub Adder (.dataa (rMulResult),
					.datab (Acc),
					.cin (1'b0),
					.result (Sum),
					.cout (PlusOne));
	defparam
		Adder.lpm_direction = "ADD",
		Adder.lpm_hint = "ONE_INPUT_IS_CONSTANT=NO,CIN_USED=NO",
		Adder.lpm_representation = "SIGNED",
		Adder.lpm_type = "LPM_ADD_SUB",
		Adder.lpm_width = 20;	
		
always @(posedge clk)
	Acc <= Sum;

wire [CounterWidth-1:0] CounterOut;
	lpm_counter UpperBits (	.clock (clk),
							.cnt_en (PlusOne),
							.sclr (sclr),
							.Q (CounterOut));
	defparam
		UpperBits.lpm_direction = "UP",
		UpperBits.lpm_port_updown = "PORT_UNUSED",
		UpperBits.lpm_type = "LPM_COUNTER",
		UpperBits.lpm_width = CounterWidth;
		
	assign Q = {CounterOut, Acc};

endmodule


Входные данные мы "защёлкиваем", результат умножения тоже "защёлкиваем", и только потом передаём на сумматор. Увы, максимально допустимая скорость работы такой штуки: 15,85 МГц, вместо нужных нам 25 МГц (КАК МИНИМУМ). Можно попробовать пошевелить параметр
lpm_hint = "MAXIMIZE_SPEED=5"
. Это некое указание синтезатору, что нам важнее - скорость работы или занимаемый объём, и по умолчанию выбрана "золотая середина". Документации по этому параметру нет, но если в "мастере мегафункций" выбрать Type of optimization: Speed (вместо Default), то будет MAXIMIZE_SPEED=9. Запускаем синтез - и количество ЛЭ не изменилось, 281, да и максимальная частота осталась той же, 15,85 МГц. Этого я и ожидал: хочешь-не хочешь, а пройти 3 слоя довольно-таки увесистых сумматора за один такт - это действительно долго!

Попробуем ещё один вариант: по умолчанию параметр умножителя LPM_PIPELINE равен нулю, что означает чисто комбинаторную цепь. Попробуем туда поставить другие значения. Если модуль разработан корректно, то регистры будут вставляться МЕЖДУ сумматорами, тем самым уменьшая задержку распространения на одном такте. Нужно ещё подсоединить вход clock к нашему clk (по умолчанию на него подавался ноль), иначе ругается при синтезе.

Для начала, LPM_PIPELINE = 1. Размер возрос до 291 ЛЭ, Зато рабочая частота возросла до 17,33 МГц. Всё равно мало, но видны какие-то изменения. Ладно, LPM_PIPELINE = 2. Элементов внезапно стало даже меньше: 290, и частота возросла до 28,09 МГц. Это нас устраивает.

И ещё проверяем: не зря ли мы "защёлкнули" выход, прежде чем подавать на сумматор (вдруг именно там стоит одна из "внутренних" защёлок умножителя). Как ни страно, без этого регистра у нас стало 270 ЛЭ, при этом частота возросла до 28,25 МГц.

Снова сталкиваемся с ситуацией: лучше не "умничать", не делать за Quartus его работу, а указать ему конкретно, чего я хочу - сам он умудряется сделать лучше, будучи "ближе к железу".

Впрочем, нужно ещё одну коррекцию сделать. Я-то надеялся, что если укажу размер выхода умножителя в 20 бит вместо "рекомендованных" 21 бита, он мне "откусит" самый старший бит, который в моей ситуации (яркость пикселя без знака, координата со знаком) будет лишним. Но по просмотру лога, я обнаружил, что откусывается САМЫЙ МЛАДШИЙ, что не есть хорошо. Так что нужно указать все 21 бит, а потом уже "ручками" задействовать 20 младших из них.

С учётом всех правок, получаем такую штуковину:
//один из наиболее громоздких модулей в видеообработчике.
//X - координата относительно предполагаемого центра пятна, -128..+127 (дополнительный код)
//Pixel - яркость текущего пикселя
//Мы вычисляем сумму X*Pixel, для измерения яркостного центра пятна с субпиксельной точностью
//Выход формируется с задержкой 3 такта (требуется время, пока сигнал пройдёт через несколько сумматоров)
//по приходу sclr сумма сбрасывается, и мы ТУТ ЖЕ можем приняться за следующее пятно.

module HorPixelEstimator (input clk, input sclr, input [7:0] X, input [11:0] Pixel, output [MulPixelWidth-1:0] Q);

parameter MulPixelWidth = 26;
parameter LatchInput = 1'b1;

localparam CounterWidth = MulPixelWidth - 20;

reg [7:0] rX = 1'b0;
reg [11:0] rPixel = 1'b0;

always @(posedge clk) begin
	rX <= X;
	rPixel <= Pixel;
end

wire [7:0] iX = LatchInput? rX : X;
wire [11:0] iPixel = LatchInput? rPixel : Pixel;
	
wire [20:0] MulResult;

lpm_mult	lpm_mult_component (
				.dataa ({1'b0,iPixel}),
				.datab (iX),
				.result (MulResult),
				.aclr (1'b0),
				.clken (1'b1),
				.clock (clk),
				.sum (1'b0));
	defparam
		lpm_mult_component.lpm_hint = "MAXIMIZE_SPEED=9",
		lpm_mult_component.lpm_pipeline = 2,
		lpm_mult_component.lpm_representation = "SIGNED",
		lpm_mult_component.lpm_type = "LPM_MULT",
		lpm_mult_component.lpm_widtha = 13,
		lpm_mult_component.lpm_widthb = 8,
		lpm_mult_component.lpm_widthp = 21;

reg [19:0] Acc = 1'b0;
wire PlusOne;
wire [19:0] Sum;

lpm_add_sub Adder (	.dataa (MulResult[19:0]),
			.datab (Acc),
			.cin (1'b0),
			.result (Sum),
			.cout (PlusOne));
	defparam
		Adder.lpm_direction = "ADD",
		Adder.lpm_hint = "ONE_INPUT_IS_CONSTANT=NO,CIN_USED=NO",
		Adder.lpm_representation = "SIGNED",
		Adder.lpm_type = "LPM_ADD_SUB",
		Adder.lpm_width = 20;	
		
always @(posedge clk)
	Acc <= Sum;

wire [CounterWidth-1:0] CounterOut;
	lpm_counter UpperBits (	.clock (clk),
				.cnt_en (PlusOne),
				.sclr (sclr),
				.Q (CounterOut));
	defparam
		UpperBits.lpm_direction = "UP",
		UpperBits.lpm_port_updown = "PORT_UNUSED",
		UpperBits.lpm_type = "LPM_COUNTER",
		UpperBits.lpm_width = CounterWidth;
		
	assign Q = {CounterOut, Acc};

endmodule


Теперь оно синтезируется в 268 ЛЭ с максимальной частотой в 28,25 МГц. Жить можно.

Регистры-"защёлки" на входе я сделал параметризованными, и пока они включены. В противном случае, вся задержка от входа модуля до ближайшего регистра вошла бы в категорию tsu (set-up), которая "не нормируется". Потом, в общей схеме, возможно эти регистры окажутся лишними, и мы сэкономим ещё почти 20 ЛЭ. Сейчас попробовал отсинтезировать с LatchInput = 0 - вышло 250 ЛЭ и те же самые 28,25 МГц.


Итого, на выполнение "непосредственно вычислений" по нахождению яркостного центра, у нас уходит 34 ЛЭ на первую сумму и 250 ЛЭ на вторую, всего 284 ЛЭ.

Но к этим вычислителям теперь нужна обвязка: они каким-то образом должны передать результаты своей работы в QuatCore, а он, в свою очередь, должен управлять неким блоком, который будет в нужные моменты времени обнулять эти суммы и также пинать QuatCore, когда на выходе формируется результат...
Tags: ПЛИС, программки, работа, странные девайсы
Subscribe

  • Формулы приведения, что б их... (и atan на ТРЁХ умножениях)

    Формулу арктангенса на 4 умножениях ещё немножко оптимизировал с помощью алгоритма Ремеза: Ошибка уменьшилась с 4,9 до 4,65 угловой секунды, и…

  • Алгоритм Ремеза в экселе

    Вот и до него руки дошли, причина станет ясна в следующем посте. Изучать чужие библиотеки было лениво (в том же BOOSTе сам чёрт ногу сломит), писать…

  • atan на ЧЕТЫРЁХ умножениях

    Мишка такой человек — ему обязательно надо, чтоб от всего была польза. Когда у него бывают лишние деньги, он идёт в магазин и покупает какую-нибудь…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 1 comment