how to count only adjacent(linked) 1's quantity in 7X7 matrix buffer using fpga?

[Altera_Forum]

hello. 

i'm studying image processing using fpga. i attached 7x7 matrix image. yellow is 1 and white is 0. normally i can count all 1's quantity in 7x7 matrix included un-linked 1, but i can't count only adjacent(linked) 1's quantity except un-linked 1. would you let me know how to do? if there are some solution like IP, where can i buy that one? please help me. thank you.  from korea.

[Altera_Forum]

You are perhaps just considering vertical and horizontal neighbors pixels. The first thing that comes to mind is recommend you to change the scan operator that you're currently using, in order to also consider diagonal pixels as connected.

[Altera_Forum]

Have a look at the Lutz Algorithm - Ive seen it implemented in an FPGA before: 

http://comjnl.oxfordjournals.org/content/23/3/262.full.pdf

[Altera_Forum]

--- Quote Start ---  You are perhaps just considering vertical and horizontal neighbors pixels. The first thing that comes to mind is recommend you to change the scan operator that you're currently using, in order to also consider diagonal pixels as connected.  --- Quote End ---    thank you for your answer. you are right. i attached another example matrix. in that case, if i considerate diagonal pixel then yellow('1') q'ty is 7. if i don't considerate diagonal pixel then yellow('1') q'ty is 4. but in my method, i am beginner so just all pixel added using simple way. the result is only 9. that is problem. my wanted value is 4 or 7 but get the 9. restrict condition is time. i have to get the value 4 or 7 within 108us(short time). so i can't using breadth first search algorithm also.

[Altera_Forum]

--- Quote Start ---  Have a look at the Lutz Algorithm - Ive seen it implemented in an FPGA before: http://comjnl.oxfordjournals.org/content/23/3/262.full.pdf  --- Quote End ---    Tricky, thank you so much your answer. i was considerate like breadth first search algorithm. but restrict condition is time. i have to calculate yellow('1') q'ty in 13X13 matrix within 108us(short time). now i am learning linked information that you suggest to me. maybe much time need because i am beginner. if i solve then i will replay. thank you.

[Altera_Forum]

--- Quote Start ---  my wanted value is 4 or 7 but get the 9. restrict condition is time. i have to get the value 4 or 7 within 108us(short time). so i can't using breadth first search algorithm also.  --- Quote End ---    So, what about you give more details, like the code, target device, clock rate, etc...?

[Altera_Forum]

This kind of search Ive seen in a processor before (with the FPGA doing some sort of thresholding) 

But I have seen the search done in an FPGA (at 300 Hz refresh rate).

[Altera_Forum]

--- Quote Start ---  So, what about you give more details, like the code, target device, clock rate, etc...?  --- Quote End ---    thank you for your answer. i attached my code. but just simple code for all 1's pixel count. actually i want to count only linked 1's pixel count. but i can't.  ================================= library ieee; library cycloneive; use ieee.std_logic_1164.all; use ieee.std_logic_unsigned.all; use ieee.numeric_std.all; use cycloneive.all;  entity img_processor is   port(    CLK10KHz : in std_logic;  line_scan_data : in std_logic_vector(4 downto 0);  qty_1_pixel : out std_logic_vector(7 downto 0)    )  end entity;  architecture rtl of img_processor is   type img_array is array(0 to 4) of std_logic_vector(4 downto 0);  signal img : img_array;   begin    process(CLK10KHz)  begin  if CLK10KHz'event and CLK10KHz = '1' then  img(0) <= line_scan_data;  for i in 0 to 3 loop  img(i+1) <= img(i);  end loop;    qty_1_pixel <= ((("0000000"&img( 0)(0) + img( 0)(1) + img( 0)(2)) + ("0000000"&img( 0)(3) + img( 0)(4)))  + (( "0000000"&img( 1)(0) + img( 1)(1) + img( 1)(2)) + ("0000000"&img( 1)(3) + img( 1)(4)))  + (( "0000000"&img( 2)(0) + img( 2)(1) + img( 2)(2)) + ("0000000"&img( 2)(3) + img( 2)(4))))  + ((("0000000"&img( 3)(0) + img( 3)(1) + img( 3)(2)) + ("0000000"&img( 3)(3) + img( 3)(4)))  + (( "0000000"&img( 4)(0) + img( 4)(1) + img( 4)(2)) + ("0000000"&img( 4)(3) + img( 4)(4))));    end process;   end rtl;

[Altera_Forum]

--- Quote Start ---  This kind of search Ive seen in a processor before (with the FPGA doing some sort of thresholding) But I have seen the search done in an FPGA (at 300 Hz refresh rate).  --- Quote End ---    i appreciate your reply. but i didn't understand meaning of "in a processor" and "sort of thresholding". would you inform to me about "at 300 Hz refresh rate" information that you have seen. thank you.

[Altera_Forum]

I assume the code you have posted is incomplete, because it has syntax errors. 

Your current code is somply the sum of all bits of an array in parrallel. I assume ultimately your input will be an image? this would be streaming only 1 pixel per clock cycle. To check adjacent 1s you're going to need an algorithm to found out whether one is adjacent to another.  And to explain: In a processor - in a CPU Thresholding - taking an image and transforming the raw data by setting specific values to 0 (those that fail to meet some threshold criteria, eg. the luminance value is below a given value) 300 Hz refresh - the frame rate of the image - the pixel rate was 27Mhz.

[Altera_Forum]

--- Quote Start ---  I assume the code you have posted is incomplete, because it has syntax errors. Your current code is somply the sum of all bits of an array in parrallel. I assume ultimately your input will be an image? this would be streaming only 1 pixel per clock cycle. To check adjacent 1s you're going to need an algorithm to found out whether one is adjacent to another.  And to explain: In a processor - in a CPU Thresholding - taking an image and transforming the raw data by setting specific values to 0 (those that fail to meet some threshold criteria, eg. the luminance value is below a given value) 300 Hz refresh - the frame rate of the image - the pixel rate was 27Mhz.  --- Quote End ---    i understand your explain. i have to use fpga for solve. so even though my english is poor i am going to explain to you my problem.  1024-pixel line scan camera is running 10KHz(line rate). i prepare the buffer : std_logic_vector 1023 downto 0. i am processing scan data[8-bit] with threshold value. if scan data[n] is bigger than threshold value, then buffer(n) = '1', or '0'. finally i get the 1024-bit buffer data. line rate is 10KHz. so every 100us, 1024-bit buffer data produced. i save 5-line data using buffer array. and every 100us, buffer array line-shift. i want to count linked 1's quantity in special 5X5 matrix(for example. pixel 0 to 4 and line 0 to 4). i have no idea to solve, so just all matrix pixel data added(your point out is right). would you let me know how to solve?  thank you.

[Altera_Forum]

Your camera line rate might be running at a 10KHz line rate, but the pixel rate is actually 10.24Mhz which is what the camera will be running a. 

You shouldnt be passing whole lines around the system, that is innefficient - why not just process on a pixel bases? Processing on a line basis sounds like a software solution.. FPGA is NOT software.

[Altera_Forum]

--- Quote Start ---  Your camera line rate might be running at a 10KHz line rate, but the pixel rate is actually 10.24Mhz which is what the camera will be running a. You shouldnt be passing whole lines around the system, that is innefficient - why not just process on a pixel bases? Processing on a line basis sounds like a software solution.. FPGA is NOT software.  --- Quote End ---    you are right. camera line rate is about 10KHz and pixel rate about 10MHz. my purpose is counting how many pixel that have over threshold value in every scan(100us) within 5-scan data(5x5 matirx, and total matrix number is 1024 / 5 = 204). so i saved 5-scan data and line shift in every scan period. important thing is that i have to process as almost real time. i thought pc base is not suitable. in every scan period i'm trying to detect how many linked 1's(have over threshold value) pixel in each 204 matrix. please let me know fpga base is possible or not. if impossible then i have to give up. thank you.