Method and apparatus for sorting corner points in a visual image processing system

• US 4,490,848 A
• Filed: 03/31/1982
• Issued: 12/25/1984
• Est. Priority Date: 03/31/1982
• Status: Expired due to Fees

• Current Assignee: General Electric Company
• Original Assignee: General Electric Company
• Inventors: Tomlinson, Harold W. Jr., Beall, Donald L.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US06/363,665
• Time in Patent Office: 1,000 Days
• Field of Search: 382/5, 382/21, 382/23, 382/25, 382/8
• US Class Current: 382/152
• CPC Class Codes: G06T 9/20 Contour coding, e.g. using detection of edges
• CPC Class Codes: G06V 10/469 Contour-based spatial representations, e.g. vector-coding

Abstract

Method and apparatus is disclosed for automatically processing visual images electronically so as to permit intelligent machine analysis of the image content. A special distributed logic system architecture facilitates rapid real time image analysis and the production of reaction control signals in a high speed production line environment, for example. Dedicated decision logic is employed to determine in but a single microinstruction cycle whether a detected corner point of the image should be linked to another already linked chain of such corner points so as to define part of a closed edge contour of the image under examination. This ability to so rapidly classify encoded corner points as either belonging or not belonging to a given set of such corner points which describe a closed edge contour is quite useful in achieving rapid real time image analysis capability. Special dedicated data address indexing circuitry is also employed for most expeditiously retrieving successive address linked data words from a data memory in successive single micro-instruction cycles as required to take full advantage of the high speed dedicated corner point matching circuitry. The dedicated data memory indexing circuitry is provided in addition to the usual program instruction indexing circuitry employed in connection with the instruction register of the associated data processing system.

Claims

1. A feature extractor sorter apparatus for use in a visual image processing system which automatically determines whether newly supplied corner point identifying digital data should be linked to a free end corner point identifying digital data of a given set of other already linked corner point identifying digital data, where each corner point is identified by x, y coordinates and IN and OUT vectors, so as to represent part of a closed edge contour, said apparatus comprising:

microprocessor means for providing Δ

x, Δ

y digital data signals representing the difference Δ

x, Δ

y between x, y coordinates of said newly supplied corner point identifying digital data and the x, y coordinates of said free end corner point identifying digital data of a given set of other already linked corner point identifying digital data;

summing means connected to receive said Δ

x, Δ

y digital data signals and to compute the sum Δ

x+Δ

y of said Δ

x, Δ

y digital data signals and to produce a corresponding Δ

x+Δ

y digital signal;

difference means connected to receive said Δ

x, Δ

y digital data signals and to compute the difference Δ

x-Δ

y of said Δ

x, Δ

y digital data signals and to produce a corresponding Δ

x-Δ

y digital signal;

memory means for storing vector data representing the IN/OUT vectors of said newly supplied corner point identifying digital data and the unconnected OUT/IN vectors of said free end corner point identifying digital data of said given set of other already linked corner point identifying digital data;

vector comparison means connected to said second register means for comparing said IN/OUT and OUT/IN vector data and for producing a gate enabling signal when there is a match between the IN vector data of the newly supplied corner point and the OUT vector data of the free end corner point identifying digital data and when there is a match between the OUT vector data of the newly supplied corner point identifying digital data and the IN vector data of the free end corner point identifying digital data;

vector orientation detection means connected to receive at least some of said vector data and to produce (a) a vertical vector signal if the IN/OUT (OUT/IN) vector data of either said free end corner point identifying digital data or said newly supplied corner point identifying digital data is vertical, (b) a first diagonal vector signal if the IN/OUT (OUT/IN) vector data of either said free end corner point identifying digital data or said newly supplied corner point identifying digital data is along a first predetermined diagonal, and (c) a second diagonal vector signal if the IN/OUT (OUT/IN) vector data of either said free end corner point identifying digital data or said newly supplied corner point identifying digital data is along a second predetermined diagonal; and

logic gate means connected to receive said Δ

x+Δ

y, Δ

x, Δ

x-Δ

y, gate enabling, vertical vector, first diagonal vector and second diagonal vector signals and to produce an identifying control signal output if said gate enabling signal is present and at least any one of the following conditions is also met;

(a) Δ

x+Δ

y=0 and said second diagonal vector signal is present,

(b) Δ

x=0 and said vertical vector signal is present, or

(c) Δ

x-Δ

y=0 and said first diagonal vector signal is present.

2. A feature extractor sorter apparatus as in claim 1 wherein:

said microprocessor means comprises two N bit arithmetic logic units (ALU'"'"'s) each having carry flow input and output signal terminals with a control gate connected in a carry signal circuit between a first of the N bit ALU'"'"'s and a second of the N bit ALU'"'"'s such that said Δ

x, Δ

y digital data signals are simultaneously provided by said first and second N bit ALU'"'"'s respectively when said control gate is disabled from passing carry signals.

3. A feature extraction sorter apparatus as in claim 1 or 2 wherein:

said summing means comprises an N bit parallel adder capable of producing said Δ

x+Δ

y digital signal substantially immediately after being presented with said Δ

x, Δ

y digital data signals; and

said difference means comprises an N bit parallel subtractor capable of producing said Δ

x-Δ

y digital signal substantially immediately after being presented with said Δ

x, Δ

y digital data signals.

4. A feature extractor sorter apparatus as in claim 1 wherein said vector comparison means includes multiplex means connected to said second register means for selectively providing 2M stored bits of vector data representing one of the following pairs of vectors:

(a) the IN vector of the newly supplied corner point and the OUT vector of a free end corner point; and

(b) the OUT vector of the newly supplied corner point and the IN vector of a free end corner point.

5. A feature extractor sorter apparatus as in claim 4 wherein said vector comparison means includes

a 2M bit parallel comparison circuit capable of making M simultaneous comparisons of bit pairs and of producing said gate enabling signal substantially immediately after being supplied with 2M bits of vector data by said multiplex means.

6. A feature extractor sorter apparatus as in claim 5 wherein said vector orientation detection means includes bit comparison gates connected to compare predetermined logical combinations of said 2M bits of vector data provided by said multiplex means.

7. A feature extractor sorter apparatus as in claim 3 wherein said vector comparison means includes multiplex means connected to said second register means for selectively providing 2M stored bits of vector data representing one of the following pairs of vectors:

(a) the IN vector of the newly supplied corner point and the OUT vector of a free end corner point; and

(b) the OUT vector of the newly supplied corner point and the IN vector of a free end corner point.

8. A feature extractor sorter apparatus as in claim 7 wherein said vector comparison means includes

a 2M bit parallel comparison circuit capable of making M simultaneous comparisons of bit pairs and of producing said gate enabling signal substantially immediately after being supplied with 2M bits of vector data by said multiplex means.

9. A feature extractor sorter apparatus as in claim 8 wherein said vector orientation detection means includes bit comparison gates connected to compare predetermined logical combinations of said 2M bits of vector data provided by said multiplex means.

10. A feature extractor sorter apparatus as in claim 1 or 2 further comprising a programmed microprocessor and associated RAM memory capable of executing an instruction in a predetermined instruction cycle time and connected to control said register, summing, difference, second register, vector comparison, vector orientation detection and logic gate means so as to be capable of producing successively said identifying control signal outputs during respectively corresponding successive instruction cycle times such that another identifying control signal output, indicating whether a newly supplied corner point is to be linked to an existing already linked set of corner point identifying data, is produced concurrently as successive data representing the existing free end corner points of such linked sets is recalled from said RAM memory.

11. A feature extractor sorter method for use in a visual image processing system which automatically determines whether newly supplied corner point identifying digital data should be linked to a free end corner point identifying digital data of a given set of other already linked corner point identifying digital data, where each corner point is identified by x, y coordinates and IN and OUT vectors, so as to represent part of a closed edge contour, said method comprising:

providing Δ

x, Δ

y digital data signals representing the difference Δ

x, Δ

y between x, y coordinates of said newly supplied corner point identifying digital data and the x, y coordinates of said free end corner point identifying digital data of a given set of other already linked corner point identifying digital data;

electronically computing the sum Δ

x+Δ

y of said Δ

x, Δ

y digital data signals and producing a corresponding Δ

x+Δ

y digital signal;

electronically computing the difference Δ

x-Δ

y of said Δ

x, Δ

y digital data signals and producing a corresponding Δ

x-Δ

y digital signal;

storing vector data representing the IN/OUT vectors of said newly supplied corner point identifying digital data and the unconnected OUT/IN vectors of the free end corner point identifying digital data of said given set of other already linked corner point identifying digital data;

comparing said IN/OUT and OUT/IN vector data and producing a gate enabling signal when there is a match between the OUT vector of the newly supplied corner point and the OUT vector of the newly supplied corner point and the IN vector of the free end corner point;

producing (a) a vertical vector signal if the IN/OUT (OUT/IN) vector data of either said free end corner point identifying digital data or said newly supplied corner point identifying digital data is vertical, (b) a first diagonal vector signal if the IN/OUT (OUT/IN) vector data of either said free end corner point identifying digital data or said newly supplied corner point identifying digital data is along a first predetermined diagonal, and (c) a second diagonal vector signal if the IN/OUT (OUT/IN) vector data of either said free end corner point identifying digital data or said newly supplied corner point identifying digital data is along a second predetermined diagonal, and producing an identifying control signal output if said gate enabling signal is present and at least any one of the following conditions is also met;

(a) Δ

x+Δ

y=0 and said second diagonal vector signal is present,

(b) Δ

x=0 and said vertical vector signal is present, or,

(c) Δ

x-Δ

y=0 and said first diagonal vector signal is present.

12. A feature extractor sorter method as in claim 11 wherein:

said providing step comprises interruption of a carry signal circuit between a first N bit stage of an 2N bit arithmetic logic unit (ALU) of a 2n bit slice microprocessor and a second N bit stage of said ALU such that said Δ

x, Δ

y digital data signals are simultaneously provided by said first and second N bit stages of the ALU respectively when interruption occurs.

13. A feature extractor sorter method as in claim 11 or 12 wherein:

said first computing step comprises use of an N bit parallel adder capable of producing said Δ

x+Δ

y digital signal substantially immediately after being presented with said Δ

x, Δ

y digital data signals; and

said second computing step comprises use of an N bit parallel subtractor capable of producing said Δ

x-Δ

y digital signal substantially immediately after being presented with said Δ

x, Δ

y digital data signals.

14. A feature extractor sorter method as in claim 11 wherein said comparing step includes selectively providing 2M stored bits of vector data representing one of the following pairs of vectors:

(a) the IN vector of the newly supplied corner point and the OUT vector of a free end corner point; and

(b) the OUT vector of the newly supplied corner point and the IN vector of a free end corner point.

15. A feature extractor sorter method as in claim 14 wherein said comparing step includes

making M simultaneous comparisons of bit pairs and of producing said gate enabling signal substantially immediately after being provided with said 2M bits of vector data.

16. A feature extractor sorter method as in claim 15 wherein said first-mentioned producing step includes comparing predetermined logical combinations of said provided 2M bits of vector data.

17. A feature extractor sorter method as in claim 13 wherein said comparing step includes selectively providing 2M stored bits of vector data representing one of the following pairs of vectors:

(a) the IN vector of the newly supplied corner point and the OUT vector of a free end corner point; and

(b) the OUT vector of the newly supplied corner point and the IN vector of a free end corner point.

18. A feature extractor sorter method as in claim 17 wherein said comparing step includes

making M simultaneous comparisons of bit pairs and of producing said gate enabling signal substantially immediately after being supplied with said 2M bits of vector data.

19. A feature extractor sorter method as in claim 18 wherein said first-mentioned producing step includes comparing predetermined logical combinations of said 2M bits of vector data.

20. A feature extractor sorter method as in claim 11 or 12 further comprising the use of a programmed microprocessor and associated RAM memory capable of executing an instruction in a predetermined instruction cycle time and wherein said identifying control signal output is produced during a single instruction cycle time when data representing an existing free end corner point of an existing already linked set of corner point identifying data and data representing a newly supplied corner point are made available for processing.