Детектирование и отслеживание множественных объектов в видеопотоке на FPGA

37f62c0eeabb409ebe52ad7db0f0f871.png

В этой статье я хочу рассказать о реализации системы обнаружения и отслеживания множественных объектов в видеопотоке. Данная статья базируется на двух предыдущих: Детектирование движения в видеопотоке на FPGA и Фильтрация изображения методом математической морфологии на FPGA. Захват и первичная обработка изображения осуществляется при помощи методов, описанных в первой статье, а фильтрация изображения описана во второй.

Следуя целям, поставленным в первой статье, я решил реализовать алгоритм отрисовки рамки вокруг обнаруженного объекта. В процессе выполнения этой задачи, я столкнулся с вопросом:, а вокруг какого именно объекта надо рисовать рамку? Объектов, попавших в кадр после фильтрации, может оказаться множество: одни из них маленькие, а другие большие. Если рисовать одну рамку вокруг всех объектов, попавших в кадр, то это делается не сложно, но результат работы такой системы вряд ли кому будет интересен.

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

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

Ниже представлена функциональная схема детектора множественных объектов:
df2a65e6075a49e5bf9c5172e82909a6.png

Детектор состоит из трёх основных блоков: RUN detector, BLOB detector и Bounding box generator. Каждый блок работает в своём клоковом домене и связан с другим блоком посредством асинхронного FIFO.

RUN detector


Входными данными этого блока служат выходные данные из фильтра на основе математической морфологии.
Этот блок ищет во входном потоке последовательности пикселей, состоящие из одних единиц, так называемые RUN-ы. Такое название взято из алгоритма сжатия RLE (Run Length Encoding), применяемого при сжатии JPEG и ему подобных. На картинке ниже показаны несколько видов RUN-ов: class-length, class-start и start-end.
365f1cbffd76493fa54bf5e9fcc68864.png

В нашем детекторе применяется последний (start-end) т.к. он наиболее подходит для нашей системы. В поле start записывается значение начальной позиции последовательности единиц, а в поле end — конечная позиция, затем сформированное поле start-end передаётся на выход RUN детектора и записывается в FIFO. Наряду с RUN-ами для корректной работы следующего блока в FIFO записываются данные конца строки и конца кадра.

Код детектора на языке Verilog

Run detector
module run_detector #(
    parameter RES_X=10'd320,
    parameter RES_Y=10'd240,
    parameter XOFFSET=10'd320,
    parameter YOFFSET=10'd0)
(
    input wire         clk,
    input wire         nRst,
    input wire        data_valid,
    input wire [0:0]        data_in,
    input wire [10:0]    xi,
    input wire [10:0]    yi,
    
    output reg [9:0]        run_start,
    output reg [9:0]        run_end,
    output reg        row_end,
    output reg        frame_end,
    output reg        new_run,
    output reg        rd_req
);

localparam    ST_IDLE=0, ST_RUN_START=1, ST_RUN_END=2, ST_ROW_END=3, ST_FRAME_END=4;
localparam XRES = RES_X + XOFFSET - 1;
localparam YRES = RES_Y + YOFFSET - 1;

reg [2:0] run_state = 0;
reg [9:0] run_start_d;
reg [9:0] run_end_d;

wire row_done_w = ((xi == XRES) && (yi <= YRES)) ? 1'b1:1'b0;
wire frame_done_w = ((xi == XRES) && (yi == YRES)) ? 1'b1:1'b0;

always @(posedge clk or negedge nRst)
    if (!nRst) begin
        run_state <= ST_IDLE;
        run_start <= 10'd0;
        run_end <= 10'd0;
        row_end <= 1'b0;
        frame_end <= 1'b0;
        new_run <= 1'b0;
        rd_req <= 1'b0;
    end else begin
        
        new_run <= 1'b0;
        row_end <= 1'b0;
        frame_end <= 1'b0;
    
        case     (run_state)
        ST_IDLE: begin
            if (data_valid) begin    
                if (data_in) begin
                    run_state <= ST_RUN_START;
                    run_start <= xi[9:0];
                end
            end
        end
        ST_RUN_START: begin
            if (!data_in) begin
                run_state <= ST_RUN_END;
                run_end <= xi[9:0] - 1'b1;
                new_run <= 1'b1;
            end
        end        
        ST_RUN_END: begin
            if (data_in) begin
                run_start <= xi[9:0];
                run_state <= ST_RUN_START;
            end else begin
                run_state <= ST_IDLE;
            end    
        end    
        ST_ROW_END, ST_FRAME_END: begin
            if (!data_valid) begin
                run_state <= ST_IDLE;
            end
        end
        endcase
        
        if (row_done_w || frame_done_w) begin
            run_state <= frame_done_w ? ST_FRAME_END : ST_ROW_END;
            row_end <= row_done_w ? 1'b1 : 1'b0;
            frame_end <= frame_done_w ? 1'b1 : 1'b0;
            
            run_start <= 10'd0;
            run_end <= 10'd0;    
            new_run <= 1'b1;
        end        
    end
endmodule


BLOB detector


Блок-схема алгоритма работы детектора приведена ниже.
786f95838c584c098b101e3ca34e6175.png

Рассмотрим работу детектора подробнее. Детектор, в моей реализации, представляет собой большую синхронную машину состояний. Также для работы детектора используются два модуля блочной памяти: один для хранения RUN-ов (run memory) текущей и предыдущей строки, второй — для хранения свойств обнаруженного объекта (object memory). Всего 32 объекта.

INIT
Работа детектора начинается в состоянии INIT. В этом состоянии инициализируется один из буферов run memory инвалидными значениями меток. Затем детектор переходит в состояние IDLE.

IDLE
В этом состоянии детектор ожидает наличия данных во входном FIFO от RUN детектора, затем переходит в состояние FIND_RUN.

FIND_RUN
Здесь детектор считывает начальную и конечную координату RUN-а из FIFO и переходит в состояние FIND_OVERLAP для поиска пересечений текущего RUN-а с RUN-ами предыдущей строки. Новому RUN-у присваивается инвалидная метка.

FIND_OVERLAP
Данные в памяти run memory распологаются в 2-х рядах — текущем и предыдущем. Каждый новый RUN из FIFO записывается в текущей блок памяти и проходом по всему блоку предыдущей строки, сравнивается на предмет пересечений (перекрытий). На рисунке ниже проиллюстрировано то, как RUN-ы хранятся в run memory.

da8471e737bb4de7b569a5b8328191ad.png

Если считанный из памяти предыдущей строки RUN имеет инвалидную метку, то это означает, что в этом блоке больше нет RUN-ов предыдущей строки, и детектор переходит в состояние CREATE_OBJ для создания нового объекта из текущего RUN-а. Иначе, если пересечение установлено, то из памяти object memory считывается объект по адресу метки RUN-а и детектор переходит в состояние UPDATE_OBJ для обновления свойств уже существующего объекта. Если же у текущего RUN-а метка оказалась не инвалидной, данной ему при чтении из FIFO, то это означает, что этот RUN принадлежит уже какому-то объекту и нашлось пересечение его с другим существующим объектом и эти объекты необходимо слить в один объект, и детектор переходит в состояние MERGE_OBJ.

CREATE_OBJ
Здесь создаётся новый объект, заполняются все его свойства.

  • X start — Начальная координата X
  • X end — Конечная координата X
  • Y start — Начальная координата Y
  • Y end — Конечная координата Y
  • Object mass — Количество пикселей в объекте

Созданный объект сохраняется в object memory по следующему свободному адресу (метке текущего RUN-а). Детектор переходит в состояние IDLE чтения нового RUN-а из FIFO.

UPDATE_OBJ
В этом состоянии свойства существующего объекта из object memory обновляются, вычисляются новые координаты объекта исходя из длины присоединяемого к нему текущего RUN-а. После обновления объекта детектор переходит в состояние FIND_OVERLAP поиска пересечений со следующим RUN-ом из памяти run memory.

MERGE_OBJ
Здесь сливаются два существующих объекта в один, их свойства обновляются и присваиваются первому объекту, а второй объект инвалидируются для исключения его из последующей обработки. После слияния детектор переходит в состояние FIND_OVERLAP поиска пересечений со следующим RUN-ом из памяти run memory.

На рисунке ниже изображено слияние объектов 1 и 2 посредством общего RUN-а, заштрихованного красным цветом.

fd5f84a69abf43bf83d6e5ef3c5c5700.png

FINISH_OBJ
В это состояние детектор переходит каждый раз при считывании из FIFO признака конца строки или конца кадра. В случае признака конца строки, области записи и чтения в run memory меняются местами и детектор переходит в состояние ожидания ввода данных из FIFO. В случае конца кадра, детектор переходит в состояние UPLOAD_DATA выгрузки найденных объектов из памяти object memory в выходное FIFO.

UPLOAD_DATA
Проходом по всей памяти object memory свойства объектов выгружаются в выходное FIFO. Словом, выгружаемым в FIFO является компоновка адреса объекта и четырёх координат Xstart, Xend, Ystart и Yend. Всего реализовано 32 объекта и этого вполне достаточно для кадра 320×240 пикселей. Но не все найденные объекты будут валидны. Объекты, массой менее 100 пикселей будут выгружены в выходное FIFO как инвалидные и в последствии не будут обработаны генератором рамки. После выгрузки всех объектов детектор стирает всю память object memory и меняет состояние на START, и начинается новый цикл накопления объектов.

Код детектора на языке Verilog

Blob detector
module blob_detector  #(
    parameter RES_X=10'd320,
    parameter RES_Y=10'd240)
(
    input wire             clk,
    input wire             nRst,
    // input RUN FIFO
    input wire             fifo_empty,
    input wire [21:0]    fifo_data,
    output wire            fifo_rd_en,
    // output boxes interface
    output reg            we,
    output reg [47:0]      data_o
);

localparam ST_START = 0, ST_INIT = 1, ST_IDLE = 2, ST_FIND_RUN = 3, ST_FIND_OVERLAP = 4, ST_FIND_OVERLAP_0 = 5,
           ST_CREATE_OBJ = 6, ST_UPDATE_OBJ_2 = 7, ST_UPDATE_OBJ = 8, ST_MERGE_OBJ = 9,
           ST_MERGE_OBJ_2 = 10, ST_FINISH_OBJ = 11, ST_FINISH_OBJ_2 = 12,
           ST_UPLOAD_DATA_START = 13, ST_UPLOAD_DATA = 14, ST_UPLOAD_DATA_END = 15;
           
localparam MAX_RUNS = RES_X >> 1;

//`define DETECTOR_DEBUG_MODE //is using for modeling

// RUN memory
reg [7:0] run_mem_wr_addr = 0;
reg [7:0] run_mem_rd_addr = 0;
reg [7:0] run_mem_saved_addr = 0;
reg run_mem_wr_en = 0;
reg run_mem_flip = 0;

// RUN memory data
wire [9:0] run_rd_start_x;
wire [9:0] run_rd_end_x;
wire [9:0] run_rd_label;
// RUN FIFO data
reg [9:0] run_cur_start_x = 0;
reg [9:0] run_cur_end_x = 0;
reg [9:0] run_cur_label = 0;
wire [1:0] eb;
reg [9:0] free_label = 0;

`define OBJ_MASS_THR            19'd100
`define OBJ_LIMIT            32
`define FRAME_END            fifo_data[21]
`define ROW_CHANGED            fifo_data[20]
`define RUN_EMPTY_LABEL        10'h200
`define EMPY_RUN_SLOT        10'h1FF

// FSM
reg [5:0] blob_detector_fsm_state = 0;
// Internal
reg [9:0] current_row = 0;
reg [9:0] temp_label = 0;
reg frame_end_r = 0;

`ifdef DETECTOR_DEBUG_MODE
// DEBUG
reg create_obj = 0;
reg merge_obj = 0;
reg update_obj = 0;
reg skip_obj = 0;
reg finish_obj = 0;

wire [8:0] rd_ram_addr = {~run_mem_flip, run_mem_rd_addr};
wire [8:0] wr_ram_addr = {run_mem_flip, run_mem_wr_addr};
`endif

// read the input FIFO
assign fifo_rd_en = (!fifo_empty && blob_detector_fsm_state == ST_FIND_RUN);

// RUN memory
alt_ram_30x512 run_ram (
    .clock(clk),
    .data({2'h0, run_cur_start_x, run_cur_end_x, run_cur_label}),
    .rdaddress({~run_mem_flip, run_mem_rd_addr}),
    .wraddress({run_mem_flip, run_mem_wr_addr}),
    .wren(run_mem_wr_en),
    .q({eb, run_rd_start_x, run_rd_end_x, run_rd_label})
);

reg [4:0] obj_wr_addr = 0, obj_rd_addr = 0, obj_saved_rd_addr = 0;
reg obj_mem_wr_en = 0;

// object's fields for writing
reg [9:0] obj_start_x = 0, obj_start_y = 0, obj_end_x = 0, obj_end_y = 0;
reg [21:0] obj_mass = 0;
reg obj_valid = 0, obj_updated = 0;

// object's wires for reading
wire [9:0] obj_rd_start_x, obj_rd_start_y, obj_rd_end_x, obj_rd_end_y;
wire [21:0] obj_rd_mass;
wire obj_rd_valid, obj_rd_updated;

// object detection condition
wire obj_detected_valid = (obj_rd_valid && (obj_rd_mass > `OBJ_MASS_THR));

// Object memory
object_ram obj_ram (
    .clock(clk),
    .data({obj_valid,obj_updated,obj_start_x,obj_end_x,obj_start_y,obj_end_y,obj_mass}),
    .rdaddress(obj_rd_addr),
    .wraddress(obj_wr_addr),
    .wren(obj_mem_wr_en),
    .q({obj_rd_valid,obj_rd_updated,obj_rd_start_x,obj_rd_end_x,obj_rd_start_y,obj_rd_end_y,obj_rd_mass})
);

/*
 * The main detector process
 */
always @(posedge clk or negedge nRst)
    if (!nRst) begin
        blob_detector_fsm_state <= ST_START;
        run_mem_flip <= 1'b0;
        free_label <= 10'd0;
        temp_label <= 10'd0;
        current_row <= 10'd0;
        frame_end_r <= 1'b0;
        run_mem_wr_en <= 1'b0;
        obj_mem_wr_en <= 1'b0;
        we <= 1'b0;
    end else begin
    
        run_mem_wr_en <= 1'b0;
        obj_mem_wr_en <= 1'b0;
        we <= 1'b0;
        
`ifdef DETECTOR_DEBUG_MODE        
        // DEBUG
        create_obj <= 1'b0;
        merge_obj <= 1'b0;
        update_obj <= 1'b0;
        skip_obj <= 1'b0;
        finish_obj <= 1'b0;
`endif        
        case (blob_detector_fsm_state)
        ST_START: begin
            current_row <= 10'd0;
            free_label <= 10'd0;
            run_mem_rd_addr <= 8'd0;
            run_mem_wr_addr <= 8'd0;
            obj_rd_addr <= 5'd0;
            obj_wr_addr <= 5'd0;
            frame_end_r <= 1'b0;
            run_mem_flip <= 1'b0;
            blob_detector_fsm_state <= ST_INIT;
            run_cur_start_x <= `EMPY_RUN_SLOT;
            run_cur_end_x <= `EMPY_RUN_SLOT;
            run_mem_wr_en <= 1'b1;
        end
        ST_INIT: begin
            if (run_mem_wr_addr >= MAX_RUNS) begin
                run_mem_wr_addr <= 8'd0;
                run_mem_flip <= ~run_mem_flip;
                run_mem_wr_en <= 1'b0;
                blob_detector_fsm_state <= ST_IDLE;
            end else begin
                run_mem_wr_addr <= run_mem_wr_addr + 1'b1;
                run_mem_wr_en <= 1'b1;
            end
        end
        ST_IDLE: begin
            if (!fifo_empty) begin
                blob_detector_fsm_state <= ST_FIND_RUN;
            end
        end
        ST_FIND_RUN: begin
            // fifo is already read by now
            // ALWAYS set the empty label to the new run
            temp_label <= `RUN_EMPTY_LABEL;
            run_cur_start_x <= fifo_data[19:10];
            run_cur_end_x <= fifo_data[9:0];
            
            if (`ROW_CHANGED) begin
                frame_end_r <= `FRAME_END;
                blob_detector_fsm_state <= ST_FINISH_OBJ;
            end else begin
                // set first read addres of a RUN
                run_mem_rd_addr <= 8'd0;
                blob_detector_fsm_state <= ST_FIND_OVERLAP_0;
            end
        end
        ST_FIND_OVERLAP_0: begin
            // an empty case (altera's altsyncram is read in 2 cycles, one of them is empty)
            blob_detector_fsm_state <= ST_FIND_OVERLAP;
        end
        ST_FIND_OVERLAP: begin
            if ((run_rd_start_x == `EMPY_RUN_SLOT) || (run_rd_start_x > run_cur_end_x + 1'b1)) begin
                // create new object
                if (temp_label == `RUN_EMPTY_LABEL) begin
                    // asssign the run a free label
                    run_cur_label <= free_label;
                    // ???
                    obj_saved_rd_addr <= obj_rd_addr;
                    obj_rd_addr <= free_label[4:0];
                    // store current run into the memory
                    run_mem_wr_en <= 1'b1;
                    blob_detector_fsm_state <= ST_CREATE_OBJ;
                end else begin
                    // some garbage was read from the FIFO
                    run_mem_rd_addr <= 8'd0;
                    blob_detector_fsm_state <= ST_IDLE;
                end
            end else begin
                // not empty slot in memory
                if (((run_rd_start_x >= run_cur_start_x) && (run_rd_start_x <= run_cur_end_x)) ||
                    ((run_rd_end_x >= run_cur_start_x) && (run_rd_end_x <= run_cur_end_x)) ||
                    ((run_rd_end_x >= run_cur_start_x) && (run_rd_start_x <= run_cur_end_x)) ) begin
                    // overlap
                    if (temp_label == `RUN_EMPTY_LABEL) begin
                        run_cur_label <= run_rd_label;
                        temp_label <= run_rd_label;
                        // write current RUN
                        run_mem_wr_en <= 1'b1;
                        // read the object with the overlaped RUN, save the current read addres
                        obj_saved_rd_addr <= obj_rd_addr + 1'b1;
                        obj_rd_addr <= run_rd_label[4:0];
                        // leave the RUN read address the same
                        run_mem_saved_addr <= run_mem_rd_addr;
                        blob_detector_fsm_state <= ST_UPDATE_OBJ;
                    end else begin
                        // if label exists (we came from UPDATE state)
                        if (temp_label != run_rd_label) begin
                            // merge read RUN and existent object (objects might NOT be overlaped)
                            obj_rd_addr <= run_rd_label[4:0];
                            // goto merge state
                            blob_detector_fsm_state <= ST_MERGE_OBJ;
                        end else begin
                            // otherwise this is the same RUN, skip it
                            run_mem_rd_addr <= run_mem_rd_addr + 1'b1;
                            blob_detector_fsm_state <= ST_FIND_OVERLAP_0;
                        end
                    end
                end else begin
                    // not overlaps, skip it
                    run_mem_rd_addr <= run_mem_rd_addr + 1'b1;
                    blob_detector_fsm_state <= ST_FIND_OVERLAP_0;
                end
            end
        end
        ST_CREATE_OBJ: begin
`ifdef DETECTOR_DEBUG_MODE        
            // DEBUG
            create_obj <= 1'b1;
`endif            
            // the label of the current RUN
            obj_wr_addr <= run_cur_label[4:0];
            // features
            obj_valid <= 1'b1;
            obj_updated <= 1'b1;
            obj_start_x <= run_cur_start_x;
            obj_end_x <= run_cur_end_x;
            obj_start_y <= current_row;
            obj_end_y <= current_row;
            obj_mass <= run_cur_end_x - run_cur_start_x + 1'b1;
            free_label <= free_label + 1'b1;
            // write this OBJ into mem
            obj_mem_wr_en <= 1'b1;
            // increment the next RUN write address
            run_mem_wr_addr <= run_mem_wr_addr + 1'b1;
            // RUN read address starts from the begining
            run_mem_rd_addr <= 8'd0;
            // check the FIFO for the next RUN
            blob_detector_fsm_state <= ST_IDLE;
        end
        ST_UPDATE_OBJ: begin
            // we mut take altsyncram's latency into account (one empty cycle)
            obj_rd_addr <= run_rd_label[4:0];
            blob_detector_fsm_state <= ST_UPDATE_OBJ_2;
        end
        ST_UPDATE_OBJ_2: begin
`ifdef DETECTOR_DEBUG_MODE        
            // DEBUG
            update_obj <= 1'b1;
`endif            
            // update the object if only it was previously valid
            // thus we avoid updating unused objects came from the
            // merge state
            if (obj_rd_valid) begin
                obj_valid <= 1'b1;
                obj_updated <= 1'b1;
                obj_start_x <= (run_cur_start_x < obj_rd_start_x) ? run_cur_start_x : obj_rd_start_x ;
                obj_end_x <= (run_cur_end_x > obj_rd_end_x) ? run_cur_end_x : obj_rd_end_x;
                obj_start_y <= (current_row < obj_rd_start_y) ? current_row : obj_rd_start_y;
                obj_end_y <= (current_row > obj_rd_end_y) ? current_row : obj_rd_end_y;
                obj_mass <= obj_rd_mass + (run_cur_end_x - run_cur_start_x);
                // save updated obj to it's original address
                obj_wr_addr <= obj_rd_addr;
                // restore saved read address
                run_mem_rd_addr <= run_mem_saved_addr;
                // write updated object
                obj_mem_wr_en <= 1'b1;
            end    
`ifdef DETECTOR_DEBUG_MODE            
            else begin
                // just skip this object
                // perhaps it was updated previously or going to be updated on the next RUN
                skip_obj <= 1'b1;
            end
`endif            
            // let store current run into the memory
            blob_detector_fsm_state <= ST_FIND_OVERLAP_0;
            // increment the next RUN write address
            run_mem_wr_addr <= run_mem_wr_addr + 1'b1;
            
        end
        ST_MERGE_OBJ: begin
            // invalidate the (second) object
            // !!!free list MUST be updated ??? I can't figure out how it should be done...
            obj_valid <= 1'b0;
            obj_wr_addr <= run_rd_label[4:0];
            obj_mem_wr_en <= 1'b1;
            
            blob_detector_fsm_state <= ST_MERGE_OBJ_2;
        end
        ST_MERGE_OBJ_2: begin
`ifdef DETECTOR_DEBUG_MODE        
            // DEBUG
            merge_obj <= 1'b1;
`endif            
            if (obj_rd_valid) begin
                obj_valid <= 1'b1;
                obj_start_x <= (obj_start_x < obj_rd_start_x) ? obj_start_x : obj_rd_start_x;
                obj_end_x <= (obj_end_x > obj_rd_end_x) ? obj_end_x : obj_rd_end_x;
                obj_start_y <= (obj_start_y < obj_rd_start_y) ? obj_start_y : obj_rd_start_y;
                obj_end_y <= (obj_end_y > obj_rd_end_y) ? obj_end_y : obj_rd_end_y;
                obj_mass <= obj_mass + obj_rd_mass;
                obj_wr_addr <= temp_label[4:0];
                // write updated (first) object
                obj_mem_wr_en <= 1'b1;
                // read just written object
                obj_rd_addr <= temp_label[4:0];
            end    
            
            blob_detector_fsm_state <= ST_FIND_OVERLAP_0;
            run_mem_rd_addr <= run_mem_rd_addr + 1'b1;
        end
        ST_FINISH_OBJ: begin
            // if there are NO opened objects in the row
            run_cur_start_x <= `EMPY_RUN_SLOT;
            run_cur_end_x <= `EMPY_RUN_SLOT;
            run_mem_rd_addr <= 8'd0;
            blob_detector_fsm_state <= ST_FINISH_OBJ_2;
            run_mem_wr_en <= 1'b1;    
        end
        ST_FINISH_OBJ_2: begin
            run_mem_flip <= ~run_mem_flip;
            run_mem_wr_addr <= 8'd0;
            current_row <= current_row + 1'b1;
            if (frame_end_r) begin
`ifdef DETECTOR_DEBUG_MODE            
                // DEBUG
                finish_obj <= 1'b1;
`endif                
                // do some stuff around bounding boxes
                frame_end_r <= 1'b0;
                obj_rd_addr <= 5'd0;
                obj_saved_rd_addr <= 5'd0;;
                blob_detector_fsm_state <= ST_UPLOAD_DATA_START;
            end else begin
                blob_detector_fsm_state <= ST_IDLE;
            end        
        end
        ST_UPLOAD_DATA_START: begin
            // an empty case (altera's altsyncram is read in 2 cycles, one of them is empty)
            obj_saved_rd_addr <= obj_rd_addr;
            blob_detector_fsm_state <= ST_UPLOAD_DATA;
        end
        ST_UPLOAD_DATA: begin
            if (obj_rd_addr >= (`OBJ_LIMIT - 1)) begin
                blob_detector_fsm_state <= ST_UPLOAD_DATA_END;
            end else begin
                data_o <= {2'h0, obj_saved_rd_addr, obj_detected_valid, obj_rd_start_x, obj_rd_end_x, obj_rd_start_y, obj_rd_end_y};
                //data_o <= {2'h0, obj_saved_rd_addr, obj_rd_valid, obj_rd_start_x, obj_rd_end_x, obj_rd_start_y - 10'd320, obj_rd_end_y - 10'd320};
                //data_o <= {2'h0, obj_saved_rd_addr, 1'b1, 10'd340, 10'd380, 10'd120, 10'd160};
                we <= 1'b1;
                // clean obj memory
                obj_wr_addr <= obj_rd_addr;
                obj_valid <= 1'b0; obj_updated <= 1'b0;
                obj_start_x <= 10'd0; obj_end_x <= 10'd0;
                obj_start_y <= 10'd0; obj_end_y <= 10'd0;
                obj_mass <= 20'd0;
                obj_mem_wr_en <= 1'b1;
                // set box generator's address
                //if (obj_detected_valid) obj_saved_rd_addr <= obj_saved_rd_addr + 1'b1;
                // set the next read address
                obj_rd_addr <= obj_rd_addr + 1'b1;
                blob_detector_fsm_state <= ST_UPLOAD_DATA_START;
            end
        end
        ST_UPLOAD_DATA_END: begin
            obj_rd_addr <= 5'd0;
            blob_detector_fsm_state <= ST_START;
        end
        default: blob_detector_fsm_state <= ST_START;
        
        endcase
    end
endmodule


Наличие промежуточных состояний: FIND_OVERLAP_0, UPDATE_OBJ_2, MERGE_OBJ_2, FINISH_OBJ_2 и UPLOAD_DATA_START связано с чтением 2-х портовой памяти ПЛИС. Выяснилось, что чтение памяти за 1 такт не является возможным, иными словами, выставив адрес в текущем такте, мы не получим валидных данных из памяти в следующем такте, а получим только через один такт т.к. входы мегафункции altsyncram регистровые и синхронны клоку записи. Отсюда и получается запаздывание в 1 такт. Надеюсь, что я правильно это понял :)

Bounding box generator


Этот блок служит для отрисовки прямоугольной рамки вокруг найденного объекта. Так как объектов реализовано в количестве 32, то и генераторов рамки так же 32. Все они соединяются последовательно и каждый из них имеет свой уникальный адрес. Этот адрес совпадает с адресом объекта в object memory модуля Blob detector. При чтении данных из FIFO генератор рамки сравнивает адрес из FIFO со своим уникальным адресом и либо загружает в себя координаты объекта для отрисовки рамки, либо пропускает их.

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

Код box generator-а

Bounding box generator
module box_generator #(
        parameter BADDR = 5'd0,
        parameter COLOR = 16'hF8_00
    )
    (
        input clk,
        input nRst,
        input [4:0] addr,
        input [40:0] data,
        input we,
        input [10:0] hcount,
        input [10:0] vcount,
        input [15:0] pixel_i,
        output wire [15:0] pixel_o
    );
    
reg [10:0] xs = 0,xe = 0,ys = 0,ye = 0;
reg box_valid = 0;
reg [15:0] pixel_r;

wire addr_valid = (addr == BADDR) ? 1'b1 : 1'b0;

    always @(posedge clk or negedge nRst)
        if (!nRst) begin
            xs <= 11'd0; ys <= 11'd0;
            xe <= 11'd0; ye <= 11'd0;    
            box_valid <= 1'b0;
        end else begin
            if (we && addr_valid) begin
                xs = data[39:30];
                xe = data[29:20];
                ys = data[19:10];
                ye = data[9:0];
                box_valid = data[40];
            end
        end
    
    always @(*) begin
        if ((hcount >= xs && hcount <= xe) && (vcount == ys || vcount == ye)) begin
            pixel_r = COLOR;
        end else begin
            if ((hcount == xs || hcount == xe) && (vcount >= ys && vcount <= ye))
                pixel_r = COLOR;
            else
                pixel_r = pixel_i;
        end
    end  
    
assign pixel_o = box_valid ? pixel_r : pixel_i;    
endmodule


Вставка 32-х генераторов рамки последовательно осуществляется посредством оператора generate. Выход каждого предыдущего модуля заведён на вход следующего.
wire [15:0] box_out [0:`OBJ_LIMIT-1];

genvar i;
    generate
        for(i = 0; i < `OBJ_LIMIT; i = i + 1 ) begin : box_gen
            if (i == 0) begin
                box_generator #(
                    .BADDR(i),
                    .COLOR(`CL_RED)
                )
                BOX_GEN (
                    .clk(pix_clk),
                    .nRst(nRst),
                    .addr(box_data[45:41]),
                    .data(box_data[40:0]),
                    .we(box_fifo_rd_en),
                    .hcount(counter_x),
                    .vcount(counter_y),
                    .pixel_i({morph_out[7:3], morph_out[7:2], morph_out[7:3]}),
                    .pixel_o(box_out[0])
                );
            end else begin
                box_generator #(
                    .BADDR(i),
                    .COLOR(`CL_RED)
                )
                BOX_GEN (
                    .clk(pix_clk),
                    .nRst(nRst),
                    .addr(box_data[45:41]),
                    .data(box_data[40:0]),
                    .we(box_fifo_rd_en),
                    .hcount(counter_x),
                    .vcount(counter_y),
                    .pixel_i(box_out[i-1]),
                    .pixel_o(box_out[i])
                );
            end
        end
    еndgenerate

Рассмотренные выше блоки соединяются следующим образом:
wire [9:0] run_start, run_end;
wire row_end, frame_end, new_run;
wire [21:0] run_fifo_data_o;	
wire run_fifo_full, run_fifo_empty, run_fifo_wr_en, run_fifo_rd_en;
	
	run_detector #(
		.RES_X(10'd320), 
		.RES_Y(10'd240),
		.XOFFSET(10'd320),
		.YOFFSET(10'd0)
		) 
	RUN_DETECTOR (
		.clk(pix_clk),
		.nRst(nRst),
		.data_valid(in_frame2),
		.data_in(&morph_out),
		.xi(counter_x),
		.yi(counter_y),
		.run_start(run_start),
		.run_end(run_end),
		.row_end(row_end),
		.frame_end(frame_end),
		.new_run(new_run),
		.rd_req(run_read_req)
	);
	
wire [10:0] run_fifo_rd_used, run_fifo_wr_used;	
wire run_fifo_rd_avail   = |run_fifo_rd_used[10:2];
wire run_fifo_almost_full  = &run_fifo_wr_used[9:2];
	
assign run_fifo_wr_en = (!run_fifo_almost_full && new_run) ? 1'b1: 1'b0;	
	
	alt_fifo_22x512 RUN_FIFO (
		.wrclk(pix_clk),
		.data({frame_end, row_end, run_start, run_end}),
		.aclr(~nRst),
		.rdreq(run_fifo_rd_en),
		.wrreq(run_fifo_wr_en),
		.rdempty(run_fifo_empty),
		.rdclk(clk),
		.wrfull(),
		.q(run_fifo_data_o),
		.rdusedw(run_fifo_rd_used),
		.wrusedw(run_fifo_wr_used)
	);
	
wire box_we;
wire [47:0] box_data;
wire [47:0] box_data_det;

	blob_detector  #(
		.RES_X(10'd320),
		.RES_Y(10'd240)
		)
	BLOB_DET	 (
		.clk(clk),
		.nRst(nRst),
		// input RUN FIFO
		.fifo_empty(run_fifo_empty),
		.fifo_data(run_fifo_data_o),
		.fifo_rd_en(run_fifo_rd_en),
		// output boxes interface
		.we(box_we),
		.data_o(box_data_det)
	);

wire [7:0] box_fifo_rd_used, box_fifo_wr_used;	
wire box_fifo_rd_avail   = |box_fifo_rd_used[7:0];
wire box_fifo_almost_full  = &box_fifo_wr_used[6:2];

wire box_fifo_wr_en  = (box_we && !box_fifo_almost_full) ? 1'b1 : 1'b0;
// read object FIFO right after valid first screen (this might be done anywhere within a frame) 
wire obj_read_ena = ((counter_y == 11'd0) && (counter_x < 10'd32)) ? 1'b1 : 1'b0;
wire box_fifo_rd_en  = box_fifo_rd_avail && obj_read_ena;
	
	dcfifo_41x128 BOX_FIFO (
		.aclr(~nRst),
		.data(box_data_det),
		.rdclk(pix_clk),
		.rdreq(box_fifo_rd_en),
		.wrclk(clk),
		.wrreq(box_fifo_wr_en),
		.q(box_data),
		.rdempty(),
		.rdusedw(box_fifo_rd_used),
		.wrfull(),
		.wrusedw(box_fifo_wr_used)
	);

Результаты


Результат работы детектора множественных объектов представлен на этом видео:

Выводы


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

Материалы по теме


→ Donald G. Bailey Design for Embedded Image Processing on FPGAs
→ FPGA Implementation of a Single Pass Real-Time Blob Analysis Using Run Length Encoding
→ A Resource-Efficient Hardware Architecture for Connected Components Analysis

Комментарии (0)

© Habrahabr.ru