Sobel edge extraction circuit for image processing

• US 4,433,438 A
• Filed: 11/25/1981
• Issued: 02/21/1984
• Est. Priority Date: 11/25/1981
• Status: Expired due to Fees

• Current Assignee: The United States of America As Represented By The Secretary of Agriculture
• Original Assignee: United States Of America As Represented By The Secretary Of The Air Force
• Inventors: Couturier, Guy D.
• Primary Examiner(s): Martin, John C.
• Assistant Examiner(s): Parker, Michael D.
• Application Number:
  US06/324,914
• Time in Patent Office: 818 Days
• Field of Search: 382/41, 382/22, 382/21, 382/43, 382/54, 382/55, 382/6, 364/752, 364/814, 364/807, 364/826, 364/729, 364/725, 364/715, 364/718, 364/736, 364/414, 358/166, 358/96
• US Class Current: 382/266
• CPC Class Codes: G06T 2200/28 involving image processing hardware
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/12 Edge-based segmentation

Abstract

The Sobel square root algorithm S={[(a+2b+c)-(g+2f+e)]² +[(a+2H+g)-(c+2d+e)]² }^1/2, with 8-bit input data from a 3×3 window and 6-bit output is performed on a single VLSI chip, using a square table only 128×13 and a square root table only 1027 or 1032×6 in ROM. The random logic including adders and clock circuits are also on the same chip with the ROM tables.

Claims

1. An image processing device on a single integrated circuit chip for performing the Sobel algorithm S={[(a+2b+c)-(g+2f+e)]² +[(a+2h+g)-(c+2d+e)]² }^1/2 with digitized input data words derived from an image by use of a 3×

3 window in the form

space="preserve" listing-type="tabular">______________________________________ a b c h z d g f e ______________________________________

supplied via input data bus means, said device comprising;

input logic means including input register means and parallel adder means for performing the functions J=(a+2b+c), K=(g+2f+e), L=(a+2h+g), M=(c+2d+e), P=|J-K| and Q=|L-M| which produces words P and Q, the input register means being coupled to said input data bus means;

first memory means storing binary words representing the squares of the binary numbers 0 to 111 1111 with 13 bits per word for the squares using 7-bit addresses, first selection means for selecting the seven least significant bits of each of said words P and Q if the remaining more significant bits are all zero'"'"'s and otherwise selecting the binary number 111 1111 as addresses to produce memory outputs from said first memory means for P² and Q², register means coupled to the first memory means output and adder means coupled thereto to provide a 13-bit word for the value V=(P² +Q²);

second memory means storing binary words of six bits each representing the square root of V, comprising a first memory section of 1024 words with addresses formed from the ten least significant bits of V, and a second memory section with addresses formed from the three most significant bits of V, with second selection means for selecting an output from said first section if the three most significant bits are all zero'"'"'s and otherwise to select an output from said second section, and means to supply the selected output as the Sobel square root value S.

2. A device according to claim 1, wherein said first memory means comprises a read only memory for only one table of 128 words of 13 bits each, wherein said first selection means comprises two multiplexers, one for word P and one for word Q, each having one input for the seven least significant bits, another input for the fixed value 111 1111, and a control input from an OR gate having the said more significant bits as inputs, another multiplexer having inputs from said two multiplexers, and a clock input for selecting the two inputs in sequence, the output being connected for addressing said first memory means so that said one table is used for squaring both words P and Q sequentially, said register means coupled to the first memory output being comprised of latches which are clocked to be loaded sequentially with words P² and Q² in synchronization with the input clocking of said another multiplexer.

3. A device according to claim 1 or 2, wherein in said second memory means, said second memory section comprises an eight-word by six-bit memory, and said second selection means is a multiplexer having two inputs connected respectively to the outputs of said first memory section and said second memory section, with a control input from an OR gate having the three most significant bits as inputs.

4. A device according to claim 3, wherein said input data bus means comprises three buses each having parallel conductors for eight bits, wherein in said input logic means said input register means comprises three latches designated A, H and G connected respectively to the three buses, three latches designated B, Z and F connected respectively to outputs of latches A, H and G, and three latches designated C, D and E connected respectively to outputs of latches B, Z and F, the outputs of latches A, B, C, D, E, F, G and H being connected to the adder means to perform the operations J=(a+2b+c), K=(g+2f+e), L=(a+2h+g) and M=(c+2d+e), the multiplications by two being accomplished by the connections being made so that the data is shifted left one bit;

and wherein in said input logic means the apparatus for performing the operation P=|J-K| comprises one adder connected to subtract K from J, another adder connected to subtract J from K, and a multiplexer with a control input from the sign bit of one of these two adders and data inputs from the other bits of both adders to select the positive result;

the apparatus for performing the operation Q=|L-M| similarly comprising two adders and a multiplexer connected in the same manner, P and Q being each produced on buses for 10 bits.

5. A signal processing device comprising:

input logic means which during each of a sequence of time intervals produces two parallel digital data words P and Q, each having a given number of bits greater than N;

first memory means storing binary words representing the squares of the 2^N binary numbers 0 to (2^N -1) with at least (2N-1) bits per word for the squares using addresses of N bits, first selection means for selecting the N least significant bits of each of said words P and Q if the remaining more significant bits are all zero'"'"'s and otherwise selecting the binary number (2^N -1) as addresses to produce memory outputs from said first memory means for P² and Q², register means coupled to the first memory means output and adder means coupled thereto to provide a word having at least (2N-1) bits for the value V=(P² +Q²);

second memory means storing binary words representing the square root of V of approximately half the number of bits as words in the first memory means, the second memory means being comprised of first and second sections, the first section having addresses formed from a predetermined number of the least significant bits of words V, and the second section having addresses formed from the remaining more significant bits of V, with second selection means for selecting an output from said first section if said remaining more significant bits of V are all zero'"'"'s and otherwise to select an output from said second section, and means to supply the selected output as the output of said device representing √

P² +Q² during each of said time intervals.

6. A device according to claim 5, wherein N equals seven.

7. A device according to claim 5 or 6, for processing the Sobel algorithm S={[(a+2b+c)-(g+2f+e)]² +[(a+2h+g)-(c+2d+e)]² }^1/2, the input logic means comprising register means and arithmetic means to form P=[(a+2b+c)-(g+2f+ e)], and Q=[(a+2h+g)-(c+2d+e)].