Comparator stack architecture for order statistic filtering of digital imagery
RIGHTS OF THE GOVERNMENT 
     The invention described herein may be manufactured and used by or for the Government of the United States for all governmental purposes without the payment of any royalty. 
    
    
     CROSS REFERENCE TO RELATED APPLICATION 
     This invention is intended for use with a system covered by my copending application titled &#34;A High Performance Architecture for Image Processing&#34;, Ser. No. 07/904,315, filed Jun. 25, 1992, now U.S. Pat. No. 5,262,968, issued Nov. 16, 1993, referred to hereinafter as my Image Processing patent application, and hereby incorporated by reference. 
     BACKGROUND OF THE INVENTION 
     The present invention relates generally to fast parallel sorting of a numerical string, and more particularly to a comparator stack architecture for order statistic filtering of digital imagery. 
     There are many examples of circuit designs that can be used for sorting and deriving the desired order statistic (e.g., Batcher&#39;s odd-even merge sort for parallel circuit design, (see references 1 and 2 below)). However, most all of these methods require the entire string of numbers to be known a priori. Also, most circuit designs related to these methods are for a fixed string length, usually a power of 2. No known design has been built using a comparator stack configuration which allows the sorting of the string to occur automatically as each string value is &#34;pushed&#34; onto the stack. 
     REFERENCES: 
     1. Akl, Selim G., Parallel Sorting Algorithms, Academic Press, 1985. See particularly chapter 2, pages 17-39. 
     2. Knuth, Donald E., The Art of Computer Programming, Vol. 3, Sorting and Searching, Addison-Wesley, 1973. See particularly pages 111-114 and 220-246. 
     3. Roth, C. H., Fundamentals of Logic Design, West Publishing Co. 1979, either the second edition at pages 369-371, or the third edition at pages 400-403. 
     Akl and Knuth show parallel sorting, including Batcher&#39;s odd-even merge sort for parallel circuit design. Roth shows a typical comparator circuit. 
     SUMMARY OF THE INVENTION 
     An objective of the invention is to provide a method and apparatus for order statistic filtering of digital imagery (i.e. in image processing for automatic target recognition). 
     More generally, an objective is to provide a method and circuit for fast sorting or order statistics of a numerical string. 
     The invention relates to a circuit design for determining the order statistics of an arbitrary (length and value) string of numbers as the string is acquired. The circuit is intended for use with the system covered by my Image Processing patent application. This circuit can be connected to each of the fine grain computational cells of that system to provide the desired filtering action (e.g., median filter). The configuration of the circuit is based upon the notion of a stack operation using comparator circuits as positions in the stack. Each comparator circuit has a counter connected to its output line that indicates a &#34;greater than&#34; condition. A hardware pointer indicates the top position of the stack. Then, as a string value is &#34;pushed&#34; onto the top of the stack, the top value is simultaneously compared to the remaining values in the stack. At this time two control conditions are automatically invoked such that the appropriate counters are incremented. The result is the counters now contain the order statistics as the string is read in. Other known procedures used for obtaining the order statistics require the entire string to be known before the sorting action can begin and in most cases the length of the string must be fixed. This design eliminates such requirements. 
     A copy of the circuit described herein can be connected to n output values of the fine grain computational cells of the system shown in my Image Processing patent application to provide the i-th smallest value (order statistic). 
     Many image processing tasks require order statistic filtering; for instance, a median filter to remove impulse noise spikes from an image. In this instance, the output of the filter at each pixel is the n/2 smallest value of an n kernel filter applied to the respective n image pixel values. 
     Scope of the Invention 
     The circuit can be applied to any situation where the numerical string is gathered one value at a time or where the length of the numerical string is undetermined within a fixed upper bound. The circuit is intended for use where image processing requirements may include order statistic filtering. (&#34;Median&#34; is clearly defined as being the value of a middle item in a series containing n items if n is an odd number, e.g. the numerical value of item (n+1)/2 when the items have been assigned order statistics from 1 to n. In a series containing an even number of items, there are two middle numbers, e.g. n/2 and (n+2)/2 in the order statistics, with the value of either being defined as the median, or a numerical value may be interpolated between the values of the two middle items and defined as the median.) 
     ADVANTAGES OF THE INVENTION 
     1. For applications where the string values are derived serially, this is the fastest computational method for generating the order statistics, O(n). The merit of this conceptual design is its simplicity. As n numbers are individually input into the circuit, they are sorted for their order in the string. This allows strings of arbitrary lengths (within the physical upper bound of the stack) to be processed in the same circuit. 
     2. The simplicity of the design allows the physical implementation (VLSI, brass board, etc.) to have widespread application. 
     3. No other known device or design has made this claim of using a comparator stack to gather order statistics. 
    
    
     BRIEF DESCRIPTION OF THE DRAWING 
     FIG. 1 is a block diagram showing a stack of registers, with comparators and counters, for sorting a string of numbers; 
     FIG. 2 is a block diagram of one comparator; 
     FIG. 3 is a functional block diagram of one cell of the comparator of FIG. 2; 
     FIG. 4 is a functional block diagram of an output network for the comparator of FIG. 2; 
     FIG. 5 is a block diagram of a high performance architecture for image processing, as disclosed in the related patent application; and 
     FIG. 6 is chart showing an example of comparator stack operation. 
    
    
     DETAILED DESCRIPTION 
     The invention is disclosed in chapter 5 of a dissertation titled &#34;An Electro-Optical Image Processing System For Automatic Target Recognition&#34; by Patrick C. Coffield, presented to the graduate school of the University of Florida in partial fulfillment of the requirements for the degree of Doctor of Philosophy, University of Florida, 1992. The dissertation is hereby incorporated by reference, and a copy is enclosed with this patent application as filed. 
     The invention is also disclosed in a paper presented under the title &#34;An Architecture for Processing Image Algebra Operations&#34; to the Image Algebra and Mathematical Image Processing Conference of the SPIE International Symposium on Optical Applied Science and Engineering, 19-24 Jul. 1992, San Diego, Calif. The presentation will be published in the conference proceedings Volume Number 1769--Image Algebra and Morphological Image Processing III. The paper is hereby incorporated by reference, and a copy is enclosed with this patent application as filed. 
     There are many different ways of computing the i-th smallest value from a string of n numbers (see reference 2). The string is first sorted from smallest to largest then the value at the i-th smallest position is selected. If the median value is called for, then the nearest middle ([n/2]) position is selected. 
     Using a sequential computer (i.e., single CPU), the fastest known method of sorting has run time complexity of O(n log 2  n). The odd-even merge sort mentioned under BACKGROUND has run time complexity O(log 2  (2n)). While the odd-even merge sort is a very fast parallel network of cross-coupled comparator circuits, the entire fixed length string of numbers must be available before processing. 
     The comparator stack concept described herein has run time complexity O(n). Using the design of a comparator circuit as shown in FIG. 1 (see reference 3 (Roth)), an arbitrary length stack can be arranged as shown in FIG. 2, such that the value that is &#34;pushed&#34; onto the top of the shack (determined by a hardware pointer) can be simultaneously compared to all lower values in the stack. A counter, initialized to zero, is connected to the &#34;greater than&#34; output of each comparator. As a number is &#34;pushed&#34; onto the stack, the following two control conditions will be automatically invoked: 
     1. The counter connected to the top of the stack is incremented. 
     2. If the value at the top of the stack is &#34;less than&#34; the j-th value in the stack, then increment the counter connected to the top of the stack (the &#34;less than&#34; or the &#34;equal to&#34; output of the j-th comparator goes high). Otherwise, increment the counter connected to the j-th value (the &#34;greater than&#34; output of the j-th comparator goes high). 
     Immediately after each number is &#34;pushed&#34; onto the stack the counter values contain the sorted order, thus O(n) time complexity. 
     USE OF THE INVENTION 
     The impact that this invention, when incorporated into the system covered by my Image Processing patent application will have on the image processing community will be substantial. The immediate application will be for military use. The image processing community, however, includes much more than DoD interests; such as: Medical imaging, MRI, blood analysis, cancer research; NASA interests; real-time satellite reconnaissance for NOAA and EPA; manufacturing robotics; speech recognition; and, university level instructional aid to name a few. The physical implementation of the invention can be made available to the low price level, personal computer as well as the workstation market. 
     THE UNIT SHOWN IN FIG. 1 MAY BE USED AS THE ACCUMULATION PROCESSOR 530 OF FIG. 5, which is a block diagram of A HIGH PERFORMANCE ARCHITECTURE FOR IMAGE PROCESSING, as disclosed in the related patent application. 
     EXEMPLARY EMBODIMENT 
     FIG. 1 is a block diagram of an order statistic using stacked registers with parallel comparators. An arithmetic logic unit 110 forms a string of numbers, with each number comprising m binary bits output in parallel on line 10. There are N registers 111-11N. The first register is used as an accumulator, and is also designated as register A. The registers 111-11N are arranged in a stack, with register 111 having an input from line 10 and an output on line 1 to an input of register 112 (register B), register 112 having an output on line 2 to an input of register 113, and so on down to register 11N having an input from the preceding register (not shown). 
     There are (N-1) comparators 122-12N. These comparators are of a type which can compare two m-bit numbers in parallel, with outputs which indicate whether the first number is less than, equal to, or greater than the second number. An output from the accumulator register 111 on line 11 is connected to supply the first m-bit number a to all of the comparators 122-12N. Each of the other registers 112-11N has an output connected to one of the comparators, with register 112 having an output on line 12 to supply the second input number b to comparator 122, register 113 connected to supply the second input number c to register 123, and so on down to register 11N connected to supply the second input number to comparator 12N. The outputs of the comparators 122-12N are connected so that each has a first output (22-2N respectively) which goes high if the first input number has a value less than that of the second input number, and a second output (32-3N respectively) which goes high if the first number has a value which is equal to or greater than that of the second input number. 
     There are N counters 141-14N. The first counter 141 is designated as a top counter, and has (N-1) inputs on the leads 22-2N from the comparators 122-12N. The counters are shown as being connected in a stack arrangement, with the top counter having an output in parallel on line 41 to counter 142, counter 142 having an output on line 42 to counter 143, and so on down to an output on from the penultimate counter (not shown) to the last counter 14N. Each of the counters 142-14N needs to have a circuit which disables its counting input at the left as long as the value stored in the counter is zero. The respective outputs from the N counters are shown connected via lines 51-5N to a select unit 160. These are multiconductor lines which supply the count values in parallel. 
     For the order statistical filtering function, a select unit 160 looks at the values stored in the N counters 141-14N, and supplies an address on line 60 to select one of the registers 111-11N. The selected register will then supply the value of the number stored therein to an m-bit video output line 481. 
     To properly synchronize the operation of the units shown in FIG. 1, it is necessary to provide timing signals from a clock (not shown) to the ALU 110, the registers 111-11N, the counters 141-14N, and the select unit 160. 
     In operation, the arithmetic logic unit 110 supplies a string of digitized binary coded numbers on line 10 to the accumulator register 111. Each number comprises m bits in parallel. As each number of a string is received, the previous number is pushed down via line 1 to the register 112, and in like manner, the number in each register is pushed down to the one below it. 
     Demonstration of Principle 
     FIG. 6 demonstrates the function of the invention by processing an arbitrary string, in this instance, the string: 1, 2, 2, 8, 3, 7, 9, 1, 11. 
     Before the start of each string, all of the registers and counters are cleared to a value of zero. 
     For each value &#34;pushed&#34; onto the stack: 
     1. increment the top counter 
     2. if the top value is less than the j-th value increment the top counter 
     else 
     increment the j-th counter 
     The first operation of incrementing the top counter means that it is reset to a value of &#34;1&#34; for each value pushed onto the stack. This is shown symbolically in FIG. 1 by the value &#34;1&#34; from a block 140 being loaded in parallel into the top counter 141 via a multiconductor line 40. 
     The top row of the table in FIG. 6 shows the value stored in the accumulator register 111, and in parentheses the value in the top counter 141 after the comparison and incrementing of the counters; the second row shows the value in register 112, and the counter value in counter 142, and so on down for the other registers and their associated counters. The first column shows the values stored after the first number is pushed onto the stack, the second column after the second number, and so on across. 
     Referring to the first column of FIG. 6, the first number of the string has a value of &#34;1&#34;, and the counter 141 is loaded to a value of &#34;1&#34;. The leads 22-2N from the comparators are all low, so that the counter 141 remains at a value of &#34;1&#34;. 
     As shown in the second column, the next number in the string has a value of &#34;2&#34;, and the value of &#34;1&#34; is pushed down to register 112. The top counter is again loaded with a value of &#34;1&#34;, and the previous value of &#34;1&#34; is pushed down from the counter 141 to counter 142. The comparator 122 finds that the number a on the line 11 from the register 111 is greater than the number b on the line 12 from the register 112, so the signal on line 22 is low and the signal on line 23 is high. Therefore the value in counter 142 is incremented to a value of &#34;2&#34;, while the value in the top counter 141 remains at &#34;1&#34;. 
     Referring to the third column, the next number loaded into the accumulator register 111 is again a &#34;2&#34;, the previous value of &#34;2&#34; is pushed down to register 112, and the value of &#34;1&#34; is pushed down to register 113. Again the top counter 141 is loaded with a &#34;1&#34;, and the values of &#34;1&#34; and &#34;2&#34; from registers 141 and 142 are pushed down to registers 142 and 143 respectively. Since the value in the accumulator register 111 is equal to the value in register 112 and greater than the value in register 113, the signals on leads 22 and 23 from the comparators 122 and 123 are low, and the signals on leads 32 and 33 are high. Therefore the value in the top counter 141 remains at a value of &#34;1&#34;, and the counters 142 and 143 are incremented to values or &#34;2&#34; and &#34;3&#34; respectively, as shown in the parentheses of the third column. 
     The fourth column shows a value of &#34;8&#34; loaded into the register 111, and the values from the third column each pushed down one row. The counter values from the third column are each pushed down, and then incremented by the signals from the first three comparators, while the value in the top counter remains at a value of &#34;1&#34;. 
     As shown in the fifth column, the stack values in the first four of the registers and the first four of the counters are pushed down one row, and a value of &#34;3&#34; is loaded into the register 111. Since the top value of &#34;3&#34; is less that the value of &#34;8&#34; in register 112, the output of comparator 122 is high on lead 22 and low on lead 32. The value of &#34;3&#34; is less than each of the other stack values in rows 3, 4 and 5, so the top counter 141 is incremented by one to a value of &#34;2&#34;, the count value in the second row is not incremented and remains &#34;1&#34;, and the count values in rows 3, 4 and 5 are each incremented to values of &#34;3&#34;, &#34;4&#34; and &#34;5&#34; respectively. 
     The stack value of &#34;7&#34; loaded at the top of the sixth column is less than one other value, e.g. the value of &#34;8&#34; in the third row, so that the count value at the top is incremented to a value of &#34;2&#34;, the count value associated with the stack value of &#34;8&#34; remains at a value of &#34;1&#34;, and the other values pushed down from the fifth column are each incremented by one. 
     The next stack value of &#34;9&#34; is greater than any of the values below it, so the top counter remains at a value of &#34;1&#34;, and each of the other count values pushed down from the preceding column are each incremented by one. 
     In the eighth column the top stack value having a value of &#34;1&#34; is less than six other values, so the value in the top counter is incremented to &#34;7&#34;, and the next six values are greater than the top value so that the counter values are each incremented by one. The last stack value is equal to the top value, so its counter value is also incremented by one. 
     In the last column, the top stack value of &#34;11&#34; from the input string is greater than all the other values below it, so the top counter retains a value of &#34;1&#34;, while the other counter values pushed down from column eight are all incremented by one. 
     The stack values in the last column are now ranked from the largest number to the smallest, with order statistic values from &#34;1&#34; to &#34;9&#34;. Note that the stack values could be ranked from the smallest to the largest by connecting the &#34;greater than&#34; outputs of the comparators to the top counter 141, and the &#34;lesser than&#34; outputs to the respective counters 142-14N. The &#34;equal to&#34; outputs can be connected to either the top counter, or the respective ones of the other counters, since it does not matter in which order equal numbers are ranked. 
     After the last number in the string has been pushed onto the register stack and ranked in the counters, the select unit 160 in FIG. 1 then selects a predetermined i-th order statistic value. For median filtering, the counter value selected will be the median value, which can be determined by adding one to the maximum rank value and dividing by two. In the example shown in FIG. 6, the median counter value is (9+1)/2=5. The median stack value for this counter value is &#34;3&#34;. The address of the register corresponding to counter is forwarded via a line 60 to all of the registers 111-11N to select the one addressed and supply the value from that register to the video output line 481. 
     If the maximum value stored in the counters is an even number, the value obtained by adding one and dividing by two can be either truncated or rounded up. For example in the eighth column, either counter value of &#34;4&#34; or &#34;5&#34; may be selected, to give a median stack value of &#34;3&#34; or &#34;2&#34;. 
     Design of a Comparator 
     The design of a comparator as shown in FIG. 2 is taken from Roth, &#34;Fundamentals of Logic Design&#34; section 18.2 of the second edition at pages 369-371, or the third edition at pages 400-403. If the numbers to be compared each have n bits, there are n cells 21-28. The most significant bits a 1  and b 1  of each of the numbers a and b is connected to the first cell 21, and the succeeding bits to the other cells down to the least significant bits a n  and b n  connected to the n-th cell 28. A typical cell 300 for the i-th bit is shown in FIG. 3. An output network 400, which is connected following the n-th cell, is shown in FIG. 4. Comparison in FIG. 2 proceeds from left to right. The first cell 21 compares a 1  and b 1  and passes the result on leads x 2  and y 2  to the next cell 22, etc. Finally, x n  and y n  are compared by the last cell 28, and the output network 400 produces signals to indicate if a&lt;b, a=b, or a&gt;b on leads Z1, Z2 and Z3 respectively. 
     A truth table for a typical comparator cell is as follows: 
     
         ______________________________________                                    
a.sub.i b.sub.i =                                                         
x.sub.i                                                                   
    y.sub.i                                                               
           00     01   11   10   z.sub.1                                  
                                      z.sub.2                             
                                           z.sub.3                        
______________________________________                                    
0   0      00     10   00   01   0    1    0    (a &lt; b)                   
0   1      01     01   01   01   0    0    1    (a = b)                   
1   0      10     10   10   10   0    0    1    (a &gt; b)                   
______________________________________                                    
 
    
     The inputs to the left of the first cell must be 
     x 1  =y 1  =0. 
     In the circuit shown in FIG. 3, the input on lead a i  is connected via an inverter 311 to an input of a NAND gate 321, and directly to an input of a NAND gate 322. The input on lead b i  is connected via an inverter 312 to an input of the NAND gate 322, and directly to an input of the NAND gate 321. The outputs of the NAND gates 321 and 322 are connected respectively to inputs of NAND gates 331 and 332. The input on lead x i  is connected via an inverter 301 to inputs of NAND gates 322 and 331, and the input on lead Y i  is connected via an inverter 302 to inputs of NAND gates 321 and 332. The outputs of the gates 331 and 332 are designated x i+1  and y i+1  respectively. 
     The output network shown in FIG. 4 has the input lead x n+1  connected directly to the output lead Z 1  and also to an input of a NOR gate, and the input lead y n+1  connected directly to the output lead Z 3  and also to an input of the NOR gate. The output of the NOR gate is the output lead Z 2 . Note that the output lead Z 2  may be connected either to lead 32 as shown in FIG. 2, or to lead 22, since as noted above in the section &#34;Demonstration of Principle&#34; it does not matter in which order equal numbers are ranked. 
     COMPUTER PROCESSING 
     The invention may be implemented in a digital computer, which could be one having a single processor with sequential operation, but preferably is one having a parallel processor architecture. The registers and counters of FIG. 1 may be separate registers, or designated memory locations. There must be some method or means for pointing to the last number which has been received as the top number at any time during the processing of a string. Also, the top counter needs to be specifically identified and associated with the top number, and then each count value needs to be kept associated with its individual number of the string. Each number of a string may be left in one memory location or processor, or the numbers may be shifted to different memory locations or processors as they are received. The same is true of the count values. 
     The comparison operations may be done with software; but when a parallel processor architecture is used, it is preferred that each processor include a hardware comparator as in FIG. 2 for speed of operation. 
     THE ARCHITECTURE FOR IMAGE PROCESSING 
     FIG. 5 is a block diagram of a high performance architecture for image processing, as disclosed in the related patent application. 
     The logical computer architecture is specifically designed for image and signal processing, and other related computations. As shown in FIG. 5, the architecture is a data flow concept comprising three tightly coupled components: a spatial configuration processor 510 (process S), a weighting processor 520 using a point-wise operation (process W), and a accumulation operation processor 530 (process A). The data flow and image processing operations are directed by the control buffer 540 and pipelined to each of the three processing components. 
     The spatial configuration process is a step-wise discrete convolution of the original input image with each template location. A unit value is assigned to the template element for each convolution. The result of each convolution is simply a shift of the input image element. 
     The output of the spatial configuration processor is combined point-wise in the weighting processor 520, using the appropriate binary associative operator from the algebraic set of operators, with the value of the respective template element. This point-wise operation processor 520 is a typical array processor execution with the binary associative operators assigned to each arithmetic logic unit. 
     The output of the point-wise operation process is now accumulated point-wise, using the appropriate global reduce operator from the algebraic set of operators. Once the final template element is processed in this fashion, the accumulator memory contains the result of the generalized matrix product defined in the algebra. Note, the generalized matrix product is the mathematical formulation for operations such as: general convolution/correlation, additive maximum/minimum, and multiplicative maximum/minimum. These operations along with the direct image-to-image (strictly a point-wise process) unary and binary operations allow for the formulation of all common image processing tasks. Hence, this architecture will control the execution of all necessary operations of the underlying image algebra. 
     For the hybrid electro-optical embodiment, the spatial configuration processor 510 is a Fourier optical correlator design using binary and high resolution (2 8  bits) spatial light modulator technology (e.g. Ferroelectric Liquid Crystal, Smectic A-FLC) and a charged coupled device (CCD) array to provide the output image in digital form, with a high frame switching frequency. It provides a step-wise optical convolution of the original input image with each template location. 
     The weighting processor 520 is a parallel array processor with directly connected input from the CCD array of the spatial configuration processor 510, and with the capability to load a scalar value to each arithmetic logic unit (ALU). Three parallel shift registers are needed for each ALU. Each ALU must have a multiplier, an adder, and a modified comparator. The output image will be the result of combining the input image with the scalar using one of the following operations: +; ·; &lt;; &gt;; (AND); and (OR). 
     It is understood that certain modifications to the invention as described may be made, as might occur to one with skill in the field of the invention, within the scope of the appended claims. Therefore, all embodiments contemplated hereunder which achieve the objects of the present invention have not been shown in complete detail. Other embodiments may be developed without departing from the scope of the appended claims.