Edge detection method and apparatus for an image processing system

• US 5,212,740 A
• Filed: 04/02/1991
• Issued: 05/18/1993
• Est. Priority Date: 03/28/1991
• Status: Expired due to Term

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Park, Yong-cheol, Myeong, Chan-kyu, Paek, Jun-gi
• Primary Examiner(s): Mancuso, Joseph
• Application Number:
  US07/679,205
• Time in Patent Office: 777 Days
• Field of Search: 382/22, 382/27, 382/34, 382/41, 382/21, 382/30, 382/50
• US Class Current: 382/266
• CPC Class Codes: G06T 5/20 using local operators
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: H04N 5/142 Edging; Contouring

Abstract

An edge detection apparatus and method for an image processing system are disclosed. The apparatus comprises a conversion means for converting input pixel data into tri-state valves, a matching means for obtaining inner products of tri-state valves and prespecified edge patterns and a decision means for determining the pixel data to be an edge when the pixel data is equal to the tri-state values. The edge detection apparatus can remove noise without an additional low pass filters, simplify the hardware and do real time process.

Claims

1. An edge detection method comprising:

a converting step comprising steps for obtaining a mean value M_i of pixel data Z;

in an n×

n window and converting said pixel data in said n×

n window into tri-state values V_j using said mean value M_i and a predetermined threshold value e ##EQU14## for j=1, 2 . . . , r;

a comparing step for comparing V_j, which is said pixel data represented in tri-state values, with four pre-specified edge patterns W₁, W₂, W₃ and W₄, where ##EQU15## where the superscript T represents the transpose of the matrix; and

decision steps for determining said pixel data to be an edge if V_j is equal to any one of said four pre-specified edge patterns, and otherwise not to be an edge.

2. An edge detection apparatus comprising:

conversion means comprising;

a mean value calculation circuit for obtaining a mean value of pixel data in a 3×

3 window centered by an input pixel of interest and a conversion circuit for B×

B converting said pixel data into tri-state values using said mean value and a predetermined threshold value;

matching means for obtaining inner products of said tri-state values and pre-specified edge patterns; and

decision means for determining said pixel of interest to be an edge when said tri-state values are equal to any one of said edge patterns, and otherwise not to be an edge.

3. An edge detection apparatus claimed in claim 2, wherein said mean value calculating circuit comprises:

a first four-adder group for summing in pairs a first &

second, third &

fourth, sixth &

seventh and eighth &

ninth pixel data while excluding center pixel data;

a second two-adder group for summing in pairs the outputs remaining after discarding a least significant bit from said first adder group; and

a third adder for summing the outputs remaining after discarding a least significant bit from said second adder group and outputting the signal remaining after discarding the least significant bit.

4. An edge detection apparatus as claimed in claim 3, wherein said decision means comprises:

a set of four comparators for respectively inputting the output of four absolute circuits and a given threshold value;

two OR gates for ORing in pairs the outputs of said set of four comparators; and

an OR gate for ORing the outputs of said two OR gates.

5. An edge detection apparatus as claimed in claim 3 wherein said conversion means comprises:

a fourth adder for summing the output of said third adder and said predetermined threshold value;

a fifth adder for summing the output of said third adder and a negative value of said predetermined threshold value;

a first set of eight comparators for comparing the eight pixel data while excluding said center pixel data, with the output of said fourth adder;

a second set of eight comparators for comparing said eight pixel data with the output of said fifth adder;

eight inverters for inverting the respective outputs of said first set of eight comparators and outputting the most significant bit of said tri-state values; and

eight OR gates for respectively ORing the outputs of said eight inverters with those of said second set of eight comparators, and outputting the least significant bit of said tri-state values.

6. An edge detection apparatus as claimed in claim 2, wherein said matching means comprises:

a first inner-product circuit for obtaining the inner product of said tri-state values and a first pre-specified edge pattern;

a second inner-product circuit for obtaining the inner product of said tri-state values and a second pre-specified edge;

a third inner-product circuit for obtaining the inner product of said tri-state values and a third pre-specified edge pattern; and

a fourth inner-product circuit for obtaining the inner product of said tri-state values and a fourth pre-specified edge pattern.

7. An edge detection apparatus as claimed in claim 6, wherein said inner product of said tri-state values and said first pattern comprises:

three inverters for respectively inverting the most significant bit of the first, fourth and seventh values of said tri-state values;

three AND gates for respectively producing the logical products of the outputs of said three inverters and the least significant bits of said first, fourth and seventh values of said tri-state values;

a sixth five-adder group for summing the third, sixth and ninth values of said tri-state values and the outputs of said three AND gates by the use of sign extension; and

an absolute circuit for obtaining the absolute value when the final output of said sixth adder group is negative.

8. An edge detection apparatus as claimed in claim 6, wherein said inner-product circuit of said tri-state values and said second pattern comprises:

three inverters for respectively inverting the most significant bit of the first, second and fourth values of said tri-state values;

three AND gates for respectively producing the logical products of the outputs of said three inverters and the least significant bit of said first, second and third values of said tri-state values;

a seventh five-adder group for summing the seventh, eighth and ninth values of said tri-state values and outputs of said three AND gates by the use of sign extension; and

an absolute circuit for obtaining the absolute value when the final output of said seventh adder group is negative.

9. An edge detection apparatus as claimed in claim 6, wherein said inner product of said tri-state values and said third pattern comprises:

three inverters for respectively inverting the most significant bit of the first, second and fourth values of said tri-state values;

three AND gates for respectively producing the logical products of the outputs of said three inverters and the least significant bit of said first, second and fourth values of said tri-state values;

an eighth five-adder group for summing the sixth, eighth and ninth values of said tri-state values and the outputs of said three AND gates by the use of sign extension; and

an absolute circuit for obtaining the absolute value when the final output of said eighth adder group is negative.

10. An edge detection apparatus as claimed in claim 6, wherein said inner product of said tri-state values and said fourth pattern comprises:

three inverters for respectively inverting the most significant bit of second, third and sixth values of said tri-state values;

three AND gates for respectively producing the logical products of the outputs of said three inverters and the least significant bit of said second, third and sixth values of said tri-state values;

a ninth five-adder group for summing the fourth, seventh and eighth values of said tri-state values and the outputs of said three AND gates by the use of sign extension; and

an absolute circuit for obtaining the absolute value when the final output of said ninth adder group is negative.

11. An edge detection apparatus as claimed in any one of claims 7 or 8 or 9 or 10, wherein said absolute circuit comprises:

an OR gate for ORing the two least significant bits of four input bits;

a first NAND gate for inputting the output of said OR gate and the most significant bit of said four input bits;

a second NAND gate for inputting the most significant bit and the least significant bit of said four input four bits;

a first XNOR gate for inputting the output from said first NAND gate and the second most significant bit of said four input bits; and

a second XNOR gate for inputting the output of said second NAND gate and the second least significant bit of said four input bits,

wherein the output of said first XNOR gate, the output of said second XNOR gate, and the least significant bit of said input data correspond to the most significant bit of said absolute value, the middle significant bit of said absolute value, and the least significant bit of said absolute value, respectively.