Method and device for specified rank filtering of a digital signal and application to separable two-dimensional median filtering.

(74) Agent (s):

(54) Method and device for filtering a determined rank of a separable two-dimensional.

digital signal and application to median filtering (57) The method comprises iterative sorting operations in a set of values ​​taken by the signal to be filtered of limited dimension or filtering order K, and selection at each iteration step of the value d 'a given rank, the median value being a special case. According to the invention, each sorting operation comprises a first phase during which the oldest value (one-dimensional filtering) or K oldest values ​​(two-dimensional filtering) are extracted from said set; and a second phase during which the same number of new values ​​are reintroduced in a given manner. The device comprises a first memory M ,, a multiplexer I M_x and an OT sorting operator comp osed of cells C, to C_K connected in an ordered cascade, all identical: K cells for unidirectional filtering and K² cells for conventional two-dimensional filtering and 2K cells for separable two-dimensional filtering.

<img file="FR2556902A1_D0001.tif" />

FR 2 556 902

D

Sale of booklets at IMPRIMERIE NATIONALE. 27. rue de la Convention - 75732 PARIS CEDEX 15

METHOD AND DEVICE FOR DETERMINED RANK FILTERING OF A DIGITAL SIGNAL AND APPLICATION TO SEPARABLE TWO-DIMENSIONAL MEDIAN FILTERING.

The present invention relates to a method for filtering a determined rank, in particular for median filtering, of a digital signal and a device for implementing this method.

Filtering of determined rank, arbitrarily referenced r in the following, is a non-linear signal processing technique. It consists in sorting a number of values ​​defined among all the values ​​successively taken by an evolving signal.

In th e case of a one-dimensional signal the filtering of rank r of order K = 2h + 1, where K, h and r are whole numbers, with K £ ..r can be defined mathematically as follows:

If (ap designates the sampled value of a signal, i being an arbitrary index, we consider An = £ a_not ^,..., ^atn + h} "with n arbitrary index, and we defined the filtering of rank (r), noted F, by: F ((a_not)) = (b_not) where (b_not) is the rank value (r) in the ordered set of values ​​A_notIn the case where r = h + 1, the corresponding filtering is said to be median.

In what follows, to fix the ideas, the particular cases described correspond to median filtering.

The latter technique, first applied to the processing of one-dimensional signals, has also been applied to the processing of two-dimensional signals and, in particular, it is widely used in the processing of image signals, for example video type signals.

Unlike linear type filtering methods, median filtering has the advantageous property of smoothing the noise signals tainting the image without blurring the staircase type contours.

Conventionally for the processing of image signals, these are divided into rows and columns and at each intersection of the pels: Py are defined; i and j representing the rows of rows and columns.

The values ​​associated with these pels P., can, for example, represent light intensities.

Also conventionally, in two-dimensional processing of image signals, a square window of K x K values ​​is used for the median filtering of order K. The filtered image is obtained by considering for each pel Py the median values ​​of the intensities pels of the initial image 5, that is to say before filtering, contained in the square neighborhood (K x K) centered on the pel P ^.

Most often the filtering of the type which has just been recalled is carried out by using computers and the sorts and selections involved in this filtering are carried out by the implementation of specialized programs. More specifically, computers of parallel or cellular type architectures are particularly suitable for this type of processing.

This solution however has the drawback of any solution of the pure software type, that is to say a certain slowness even if this drawback can be mitigated by the use of processing of the parallel type.

It has also been proposed to translate the sequences of operations carried out by a computer in the form of a wired solution, that is to say by using networks of elementary specialized modules for signal processing.

This solution assumes that the data to be filtered is accessed in parallel.

There are however data processing programs carrying out median filtering of the serial type, however experience has shown that they were not optimized for median filtering and their translation in wired form leads to redundancy in the hardware used.

The invention sets itself the aim of overcoming the difficulties and disadvantages of the known art.

The invention provides a median filtering method allowing the use of simple, modular and cascadable signal processing circuits, which can be produced in the form of high density integrated semiconductor circuits and which do not have any redundancy of hardware. Furthermore, the increase in the one-dimensional filtering order K does not translate into an increase in the processing time.

Finally, this method is compatible with median filtering of one-dimensional type and filtering of two-dimensional type, as well as with median filtering of simplified two-dimensional type which will be detailed later.

The subject of the invention is therefore a method of filtering a determined rank of a digital signal consisting of a series of weighted values ​​to be filtered presented according to a time sequence comprising, iteratively, the selection of a first determined number of values ​​of the sequence, the sorting of these values ​​so as to obtain a series of values ​​ordered according to their weights and the selection of the determined rank value of the values ​​thus sorted, characterized in that it comprises, for each iteration, in order, a first phase during which the oldest values, in number equal to a second determined number less than the first, are extracted from the selection of ordered values, the remaining values ​​being kept ordered according to their weight and a second phase during which new values ​​to be filtered are introduced among the remaining values, according to the respective orders of the weights of the new values ​​and of the remaining values, in number equal to said second predetermined number, so as to obtain a new series of ordered values ​​in number equal to said first determined number; and in that a new value of determined rank of the digital signal to be filtered is obtained by selecting, at the end of the second phase, the value of this determined rank of the new sequence of ordered values.

The invention also relates to a device for implementing such a method.

The invention finally relates to a median filtering device of the separable two-dimensional type using such an arrangement.

The invention will be better understood and other features and advantages will appear on reading the description which follows and the appended figures and among which:

- Figures 1 and 2 show an example of signal processing modules used in median filter circuits according to known art;

- Figures 3 and 4 schematically represent a sorting operator used in the device according to the invention;

- Figure 5 schematically shows a complete median filtering device of one-dimensional signals according to the invention;

- Figure 6 shows the detailed architecture of one of the cells of the sorting operator shown in Figures 3 and 4;

- Figure 7 is a table illustrating a particular point of the method of the invention in the context of median filtering of two-dimensional signals;

- Figure 8 schematically illustrates a device for carrying out such filtering;

- Figure 9 schematically illustrates a modified median filtering device of two-dimensional signals.

FIG. 1 represents an elementary sorting module which can be used in a median filtering circuit according to the known art.

Module M has two inputs to which two signals a * and a are transmitted.₂ sorting. The sorting criterion is the value, that is to say the binary weight of each signal.

The module M also has two outputs, an output Sj on which is available a signal a'j representing the least significant input signal and an output S₂ on which a signal is available₂representing the most significant input signal.

We can easily see that if the number of values ​​to be sorted increases, the complexity of the structure of the circuit performing this sorting does not increase linearly, but more rapidly.

By way of example, FIG. 2 illustrates a circuit for sorting four signal values ​​ap to a ^. The number of modules, marked Mj to but identical to the module M in FIG. 1, is equal to five while the number of values ​​to be sorted is only twice that of those to be sorted by the device in FIG. 1.

The entries E ^ to E₂₂ Mj and M modules₂ receive the signals to be sorted a ^ to a ^. The outputs and S₂₂ are connected to the inputs E ^ and ^₂4 ^^esmodules and connections between outputs and Sj₂ Mj and M modules₂, and the inputs E₂^ and Ej ^, modules and are crossed.

An additional module sorts the signals of the outputs (module M ^) and (module M ^). The signals a'j to a '^ available on the outputs (module M ^), and (module M ^), and S_2Zf (module Mp represent the ordered values ​​a'j to a '^ according to an increasing weight of the input signals ^atr ^aalf ·

The structure which has just been recalled is of the type described in the article by BATCHER published in AFIPS Proc. Spring (Joint Computer Conference, volume 32, April 1968, page 307-314.

The method of the invention which will now be described allows the implementation of circuits, not having these drawbacks. In addition, it optimizes sorting operations.

Indeed, if we consider a median filtering of order K = (2h +1), with K and h whole numbers, as it was recalled, the filtered signal b_not is the median value of the values ​​of signals to be filtered presented sequentially from a set of values ​​of dimension K: A_not = - £ a_not h> ->^atnj—>^atn + h ^ · ·

We can see that if A_not is sorted, i.e. ordered to find a value b, just remove from this set the oldest value η ^r at . and insert in a new set of values ​​A „,, of dimension K nn n + 1 'also, a new value to sort^atn + d₁₊p in I^e correct order, to obtain a new filtered signal value b_{n +}j. An at least partial recovery of the sorting work carried out previously is therefore possible.

The method according to the invention takes advantage of this observation.

The method according to the invention will now be explained from the description of an OT sorting operator, illustrated schematically in FIG. 3, sorting operator constituting one of the essential elements of the median filtering device according to the invention.

This operator essentially comprises cells, Cj to C ^, all identical, arranged in cascade in a linear fashion, and in number equal to the number K previously defined, or order of the median filtering. The structure of these cells will be described in detail later in connection with FIG. 6.

All the cells are connected to an input link of the BE bus type. With regard to digital signals, it is understood that this bus BE comprises a number of links equal to the number of binary elements or bits of the signals conveyed by it. The number of bits depends on the precision desired in signal processing. Typically, the number of bits is 8 or 12.

The signals carried by the input bus BE are distributed in parallel to all the cells Cj to C * ,.

These cells are also connected to an output bus BS. However, as will be described later, this bus serving to extract the median value, there is provided a means of selecting one of the cells, namely the cell of rank (h + 1), K being equal to 2h + 1 .

Finally, all the cells are interconnected by local bidirectional link buses BLj ₂ at BL ^ ^₊p In addition, two additional buses BLq j, on the one hand, and BL ^ ^₊p on the other hand, provide connections with the outside, at entry and exit.

This very regular architecture is perfectly suited to modular construction in the form of semiconductor circuits with high integration density or VLSI according to English terminology.

The operation of each of the cells will be explained using FIG. 4 which diagrammatically illustrates their structure.

Each cell C-, i, being the rank of the cell, essentially comprises a register RC ^ intended to store one of the values ​​to be sorted among K and a comparator FL. Each cell operates in two modes which correspond to two different phases in the sorting process.

More precisely, the cells have a synchronous type operation and for this purpose receive a clock signal of impulse type SHj conveyed by a common link Hp

During a first cycle of the clock signal, the cells are positioned in a first operating mode and in the following cycle they are positioned in a second operating mode. To do this, a mode control signal SMOD is transmitted to all the cells by a MOD link. The two cycles are then repeated regularly.

It is accepted by convention that the indices associated with cells are ordered in increasing order, that is to say that cell C.₊^ at a higher rank than that of cell Cj.

In addition, the signals after sorting, in steady state, are recorded in decreasing order of weight in the registers RC ^ to RC ^ of cells Cj to ^VSK '

In the first operating mode, a signal value to be sorted transmitted in parallel to all the cells by the input bus, BE, and in particular to cell C. of rank i, is compared with the signal value previously recorded. in the RCL register of this CL cell.

If the signal present on the input bus BE has a weight greater than or equal to that of the signal recorded in the register RCj, the signal recorded in the cell of immediately higher rank CL ₊ j is shifted by one position towards the cells of lower ranks, that is to say, by the bus BLj towards the cell CL and recorded in the register RCj of this cell.

According to the convention adopted, and starting from the hypothesis of the function. steady state operation for which the recorded signals have been sorted and ordered in descending order if the signal present on the input bus BE is of greater weight or equal to that of the signal recorded in the register RC., this means that this clause is also true for all signals recorded in cells of higher rank than that of cell Cj. It follows that all the signal values ​​stored in these registers RC. at RCj, will also be shifted by one position. The shift takes place, conveniently during a determined transition of the clock signal SH, so that the shifts are made before the start of the next clock cycle during which the cells operate in a second mode.

Otherwise, for which the signal recorded in the RC register. has a higher weight than that transmitted by the BE input bus, there is no offset. The signal value recorded in the register RCj therefore remains stored in this register.

In the second operating mode, the same comparison is made. If the signal carried by the input bus BE has a weight greater than or equal to that of the recorded signal, an additional comparison is made between the signal recorded in the register RC. j from cell C. j of immediately lower rank, transmitted by the local bus BL. ,. and the signal transmitted by the input bus BE. The least significant value is selected and stored in the RCj register. There is therefore, that is to say a shift of a position, towards the right in FIG. 4, ie towards cell C. of immediately higher rank, for the signal value in the register RC. j, or a substitution for the value of the signal previously stored in the RC register.

Otherwise, there is no transfer or substitution.

As in the first mode, there is in reality a general offset of all the signals of less weight than that of the signal present on the input bus BE but in the opposite direction; this shift also taking place during a determined transition of the clock signal.

Following this operation, the value of the signal present on the input bus is therefore inserted among the (Kl) other signals in a suitable place according to its weight, that is to say according to a rank assigned to the cells. .

At the end of the cycle during which the cell is positioned in the second operating mode, it suffices to select and read the content of the cell of rank (h + 1) to obtain the new median value ^bn + l of the signal values ​​to be filtered stored in the registers RCj to RC ^ in number equal to K.

The median filtering device operating according to the method of the invention therefore comprises as essential element the OT sorting operator composed of Cj cells with two operating modes as just described.

FIG. 5 schematically illustrates the structure of the complete DFM median filtering device according to the invention.

In addition to the sorting operator OT, for which it has been shown, for reasons of simplification, only three cells Cj to Cy, the device also comprises a multiplexer MX with two inputs, a first memory member Mj comprising three positions of memories each constituted by a register Rj to Rj and a second memory member M2 at a memory position: register R_at·

It should be clearly understood, as has been indicated, that a memory position corresponds to a binary word generally composed of several bits, eight bits for example which shift in parallel from one register to another.

R registers_&amp;, Rj to R ^, and more generally Rjà R ^., Are connected in cascade and function as a shift memory. To this end, the memories Mj and M2 are connected to a link H2 carrying a clock signal SH₂ half the frequency of the 5Hj clock signal, the two signals being synchronized with each other. A simple way to obtain such a signal is to use a frequency divider DF, divider by two of the frequency of the signal SHj transmitted by the link Hj. This latter signal is generated by any appropriate means of the known art.

The median filtering device receives on an input E connected to the input of the second memory M₂, sequentially, the values ​​* of signals to be filtered and stores them one by one in the register Ra at each cycle of the clock signal The output of the memory M₂ is connected, on the one hand, to the input of the memory Mj, that is to say to the input of the register Rp and, on the other hand, to one of the two inputs of the multiplexer MX. The other input of this multiplexer MX is connected to the output of the memory Mj and its output is connected to the input bus BE of the sorting operator OT.

Finally, the two-dimensional local bus BLq | is connected to this same output, so as to be able to transmit the signal present on the input bus to the register RC * and the local bus of bidirectional links BL ^ is connected to a potential corresponding to a logical zero, that is to say generally at zero potential. Conventionally, this zero potential represents a zero weight intended to represent a zero value of the signal recorded in the register RC ^, during shifts made when the cells are positioned in their first operating mode of cells Cj to Cy

The operation of the complete device according to the method of the invention will now be explained.

We note a_not a new value of arbitrary rank taken by a one-dimensional signal, value of the signal transmitted to the input E of the device DFM and recorded in the register R of the memory M_ at an arbitrary instant, â x

It is assumed that the device operates in steady state. The registers RCj to RCj store, ordered in descending order, three signal values ​​to be filtered: a_not_p ^atn_2 ^{and a}n_3 had previously been transmitted to the DFM device; a ^ being the oldest and a_not j the most recent of these values.

These three values ​​were also transmitted during previous periods of time, and in order of arrival, to the memory Mp. The logical configuration of the values ​​of signals recorded in the registers R j to R ^ therefore represents the image of this order d arrival of the different ίο values ​​a ^, a_n2, at_not_j; values ​​recorded respectively in the registers R ^, R₂ and Rp

The basic characteristic of the process of the invention is to record, sorted in descending order, the (K = 2h + 1) values ​​to be filtered, a, to a, in the example illustrated. To obtain the median value, it suffices then to select, as has been recalled the order register (h + 1) and to read the content thereof to obtain the median value, b_not, i.e. the RC register₂ in the example shown.

According to another important characteristic, part of the sorting work previously carried out is kept for each cycle. To do this, we extract the oldest of the recorded values, i.e. a_not in the example shown, and we replace it with a new value, a_not, present in the register R_at, which must be inserted in a suitable place in accordance with its weight and the weight of the other recorded values. Following these two operations, the new median value is read again by selecting the rank register (h + 1) as before. At each sorting cycle (Kl), sorted and ordered values ​​are therefore kept.

The removal operation is simply carried out by positioning the cells in their first operating mode.

We do not know the place of the oldest signal value • because it has been sorted and ordered by its weight. However, the simultaneous comparisons and offsets carried out during the operating cycle in the first mode allow the automatic elimination of the recorded signal whose weight is equal to that of the signal present on the input bus. It is therefore sufficient to transmit the oldest signal on the input bus BE, a_R in the example illustrated, value of the signal present in the register R ^ of the memory Mj. When the cells Cj to C ^ are positioned in their first operating mode, the multiplexer which receives the clock signals SH ^ by the link H with a frequency double that of the signals received by the shift memories, and M₂, reads and transmits on its output, during this operating phase, the value of the signal stored in the register R ^, that is to say a_not y which is therefore eliminated, by the game of record-shifts, from the RC register. in which it was stored; i being between 1 and 3 in the example illustrated and more generally between 1 and K, limits included. During this period, the last cell, Qy stores the value zero. In the next clock cycle, C cells_x at C₃ are positioned in their second operating mode. The signal values ​​stored in the registers R_&amp; and Rj to R_not remain unchanged, these registers receiving SH clock signals₂ of frequency half by the link H₂·

It follows that the multiplexer MX, transmits to the input bus BE, during this cycle, the content of the register R_&amp;, i.e. the new value a to filter, n

By the set of offsets which have been previously described in relation to FIG. 4, this new value has_fi is precisely inserted and saved in the place corresponding to its weight.

It is therefore sufficient to obtain the new median value b_{n +}j of the set A, = Γ a, a ,, a - j again select cell n + 1 L. n 'n + 1' n + 2J

VS₂, and more generally the cell of rank (h + 1) for a median filtering of order K = 2h + l.

An RS unit performs this selection, that is to say the addressing of the row cell (h + 1), and transmits to the general output S of the device DFM, the new median value b,.

n + 1

Table I arranged at the end of this description illustrates in more concrete terms, by way of example, the course of operations for a median filtering of order 3 of the arbitrary sequence of the following values, by order of arrival; 5, 10, 7, 8, 3, 1.

The following conventions have been adopted:

. NS: abbreviation of not significant because the permanent regime is not established; 2K clock cycles must be allowed to pass. the figures in column H represent the clock cycles from the instant 0 initialization instant in particular of the memory organs at the logical value 0.

. in the other columns and rows, the values ​​present in the registers, on the buses or on the output S are indicated as referenced in FIG. 5.

. arrows indicate the different data offsets between registers.

An example of a concrete embodiment of a CL cell usable in the median filtering device according to the invention will now be described in detail with reference to FIG. 6.

According to a preferred variant, the processing of the signals and the storage of these are carried out in parallel, but a serial processing is also possible, although slower. Consequently, the internal or intercell connections are carried out, in the example described, using multiconductor connection buses, one conductor per bit of the binary words representing the values ​​of the signals to be filtered.

Each cell Cj includes an RC register. provided with a parallel type output connected to an internal output bus BSj, a parallel type input and a clock input receiving via a serial link HR. conditioned clock signals, signals intended to authorize the loading and storage of the signals present at the input of the register. The output signals are permanently available on the output for reading.

A multiplexer with three parallel type inputs and also parallel type output connected, by an internal bus BXj, to the input of the register RCj, receives on its first input, via a first internal input bus BEp, the signals recorded in the row cell (i-1), ie the upstream cell; on its second input, via a second internal input bus BE ^ j the signals recorded in the row cell (1 + 1), ie the downstream cell; and on its third input, via a third internal BE- ^ input bus, the signals conveyed by the BE input bus of the sorting operator (Figure 5: OT), bus common to all cells. A control input receives control signals conveyed by an internal SC control bus. These signals, with three distinct states, determine a selective link among three possible between the output bus BXj and the three input buses BEp to BE .y

The meetings of the buses BS., BEp and BE ^ form the local bidirectional buses BL ^ j - and BL ^.₊j respectively. Each cell C. also includes a comparator K. which, in reality, is redoubled into a first element Kp, with two inputs of parallel type, making comparisons between the binary words present on the bus BE, on the one hand, and the internal bus BSi, on the other hand, ie the word recorded in the register

RC. ; and a second element K ^, also with two parallel type inputs, making comparisons between the binary words present on the input bus BE and the first internal input bus BE.p Internal input buses BEj ^ and BE ^^reAre the input bus to the first inputs of the comparator elements and K ^, the second inputs being connected to the buses BSj and BEjp respectively.

Each comparator element generates a binary signal, a logic state of which, for example state 1, indicates that the values ​​of the signals present on the first inputs are greater than or equal to those of the signals present on the second inputs, or positive comparison; and the other logical state, for example state 0, the opposite condition or negative comparison.

These two outputs are connected by simple links, LK. ^ And LK ^ s to two inputs of a logic selection circuit LS .. This circuit receives, conveyed by a simple link MOD ^ a SMOD mode control signal conveyed by the MOD common bond to all cells.

This signal takes two logic states, a first logic state, for example state 1, indicates that cell C must operate in its first mode and the second logic state, state 0, that it must operate in the second mode.

In the first operating mode, only the output signal of the comparator element Kj must be taken into account.

The selection logic circuit LS ^ is connected to the bus SC. and generates thereon control signals of the multiplexer such that a connection is established between the BX buses. and BE ^ ·

In addition, an additional binary control signal is generated and transmitted by this same control bus SC to a first input of an AND logic gate. AND type with two inputs. The second input receives, via a simple internal link FL, the clock signals SH ^ conveyed by the link common to all the cells. The output of the gate ETj is connected to the clock input of the register RC by the link HRj.

Depending on the result of the comparison, ie of the additional binary signal, the clock signals are transmitted or not by the AND gate. to the RC register.

If the comparison is negative, the additional control signal takes the logic value 0 and the binary word present on the output of the multiplexer MXj is not loaded in the register RCj in place of the word previously memorized.

Otherwise, the additional control signal takes the logic value 1; the clock signals are transmitted to the register RC and the binary word at the output of the multiplexer MXj loads in the register RC ^. Given the connection established inside the multiplexer, in the first mode of operation, this word is stored in the register of the downstream cell of rank (i + 1).

In the second operating mode, the state of the two output signals generated by the comparator elements Kj and Kj₂, comparison results should be taken into account.

There are three cases to consider.

The first case is a negative comparison indicated by the comparator element Kj, that is to say that the condition: value of the signal present on the bus BE greater than that of the signal stored in the register RC. is not carried out. In this case, as in the first mode, the additional control signal is in logic state 0. The clock signals are not transmitted to the register RCj and the binary word stored in this register is kept.

The second and third cases correspond to a positive comparison indicated by the output signal of the first comparatort Kj

It must then be determined that it is the smallest of the values ​​taken by the signals present on the input bus BE, on the one hand, and the internal input bus BE., On the other hand.

The two logic states 0 and 1 taken by the output signal of the second comparator element Kj₂ correspond to these last two cases.

A first logic state, state 1 for example, indicates that the signal present on the bus BE is larger than the signal present on the bus BE.j, i.e. the signal stored in the upstream cell of rank (i- 1).

In this case, the control signal transmitted to the multiplexer MX. by the bus SCj is such that a connection between the buses BE ^ and BXj is established. Furthermore, the additional control signal is in logic state 1 so that the clock signals are transmitted to the register RC. and the word transmitted by the multiplexer MX. loaded into it, ie the word stored in the upstream cell of rank (Cl).

The third case corresponds to a negative comparison indicated by the second comparator element! logic zero output signal. The control signals transmitted by the bus SCj positions the multiplexer MXj to establish a link between the buses BE ^ and BXj. The additional control signal is in logic state 1 as before. The word on the BE bus ^, ie on the BE input bus, is loaded into the RC register.

It can therefore be seen that the various operations of the first and second modes of operation of the cells can be carried out simply by the structure which has just been described.

To transmit the recorded information to the outside, the internal BS output bus must be connected. to the output bus BS common to the cells using an interface member A., ​​generally of the amplifier type.

In reality, the output bus comprises a unidirectional bus BSD for data transmission connected to the output of the interface member jj and a unidirectional selection bus BSA addressing a single cell, that is to say that of rank (h + 1), according to the convention adopted, so as to transfer the new median value to each two clock cycles.

If the configuration of the OT filtering operator (fig.5) is fixed, i.e. the order K of the fixed median filtering, the address bus is reduced to a single link transmitting a control signal, via an internal link SELj, to a transfer authorization or selection entry which must be provided with the interface member Aj.

Otherwise, if there is a possibility of reconfiguration of the device, therefore of the sorting operator, the latter is provided with an address decoding circuit receiving an address word, each cell being associated with a particular address among K possible addresses. It is also necessary to be able to modify, by circuits not shown, the capacity of the memory member M ^ in order to adapt it to a new filtering order K.

One can also provide a selection conductor per cell, the internal link SEL. shown in Figure 6 constituting the terminal part of this conductor.

In all cases, the selection signals of a particular cell are generated by the RS member (fig. 5) which also provides the interface between the output bus BS and the external environment, this latter function can be performed at using amplifiers.

In order to make a selection of the cell of median rank in appropriate time, synchronization with the clock signals will generally be necessary. The same is true for SMOD mode signals.

The constituent elements of the RC register cells, multiplexers MXp comparator and Kj2 and AND logic gate. can be of all appropriate types of Known Art.

The same is true for LS selection logic circuits. which, although specific to the device of the invention, can be achieved by using conventional logic gates connected to each other to supply control signals from the multiplexer MXj with three instinct states and an additional two-state control signal transmitted to the AND gate, depending on the logic state of three signals: operating mode signal and output signals from the two comparators K. and K ^. The logical functions to be performed have been explained previously.

If the cells are made on the basis of discrete elements, these elements can moreover be integrated circuits or parts of integrated circuits available commercially. However, as has been recalled, and in accordance with an advantageous aspect of the invention, the regular structures, and of the cells and of the sorting operator comprising a number K of these cells, are particularly suitable for large-scale integration. on a single substrate.

To fix the ideas, by using rapid technologies, for example a technology based on fast MOS type transistors, it is possible to obtain processing times, that is to say times corresponding to two clock cycles, of around 100 ns.

As mentioned above, the method according to the invention also lends itself perfectly to carrying out two-dimensional median filtering.

The filtering is then carried out on a square window of K x K signal values ​​to be sorted. To do this, we use in the sorting operator K x K,

cells, ie K cells, instead of K cells for unidirectional median filtering, these cells being however connected in cascade as previously.

The flow of operations is similar to that of sorting operations in the context of unidirectional filtering. The sorting is carried out as above in two stages. The major difference is that K new values ​​instead of one are to be taken into account, ie to order and store while the K oldest values ​​are eliminated.

It naturally follows that the device is, all other parameters remaining constant, K times slower than a unidirectional median filtering device.

Two-dimensional type signals have values ​​depending on two parameters and which can be divided into rows and columns of a two-dimensional matrix table, precisely as a function of these two parameters. This is particularly the case of signals representing an image, an image which can be subdivided into zones all of equal surfaces, distributed in rows and columns, to which we will associate in the following the respective arbitrary indices i and j.

If a. . are the values ​​of the signals to be sorted and b- - the median values ​​*> J_f M after filtering, the diagram in FIG. 7 represents the windows K x K (with K = 3 to fix the ideas) of values ​​recorded in the sorting operator of a two-dimensional device during two successive cycles of clocks corresponding to the operations cells according to the first and second operating modes.

In the illustrated example (K = 3), the nine values ​​present during the first clock cycle have arbitrary indices ï-1, i and i + 1 for the parameter i; and j-1, j and j + 1 for the parameter j.

During the second clock cycle, the oldest values ​​a. ,.

^1-1 dd., a. . . and a. . . . are to be eliminated while three new values ​​a. ,.

1, J-1 1 + J, J-1 1-1,) + / ^ati j + 2 ^{and a}i + l j + 2 ^{go away} entered and inserted among the six remaining values, according to their weights.

An exemplary embodiment of a two-dimensional DFM2D median filtering device is illustrated in FIG. 8.

The general structure of the device illustrated is identical to that of the device illustrated in FIG. 5 two memory organs M₂ and Mp a multiplexer MX ', a frequency divider DF' and a sorting operator OT '.

The main differences lie in the number of memory registers, their interconnections and the number of cells of the sorting operator, it being understood that each cell is identical to those used in an undimensional sorting operator. In a preferred variant each cell has the structure which has just been described in relation to FIG. 6.

Memory M₂ includes as previously only one memory position, namely a buffer register, R receiving sequentially

O binary words each representing a value taken by the signals to be sorted.

The structure of the memory Mj must be such that it allows a distribution in the correct order of the values ​​to be sorted from the window of dimension K x K. To do this, in the illustrated case of a median filtering of order 3x3, three registers with three memory positions each are provided: R ^ to Rp, R₂i to R₂j and R ^ | to R33, each forming a shift register at the rate of clock signals SH '₂ carried by an H bond₂ connected to the output of a frequency divider DF '. This divider DF 'is a divider by six of the frequency of the clock signals SHj transmitted to the multiplexer MX' and to the sorting operator OT '. In the general case the division factor is equal to 2 x K and the number of registers is equal to K, each register having K positions.

As before, the signals at the input and output of the shift registers are transmitted to a multiplexer: MX ', a multiplexer with six inputs in the example illustrated and more generally 2 x K inputs.

At each clock period, the output is connected to one of the inputs; these inputs being scanned cyclically, modulo 2 x K.

In the example illustrated, a complete scanning cycle links the output, that is to say the common input bus BE, successively to the output of the register Rjj - Rj ^, at its input, to the output of the register R ^ - R ^, at its entry, at the exit of the register R ^ j - R33 and at its entry, before the cycle repeats.

According to another aspect specific to the two-dimensional median filtering device DFM2D illustrated in FIG. S, the inputs of the registers are connected to each other by means of delay devices, all identical, Dj and D2 in the example illustrated. These devices transmit on their output a signal present on their input after a time interval equal to the total time necessary to introduce into the device all the values ​​of signals composing a line. These devices can be constituted by delay lines or, preferably, given the synchronous nature of the devices, by shift registers whose number of memory positions corresponds to the number of values ​​to be sorted by a line.

All these arrangements are made so that, during cycle I illustrated in FIG. 7, the values ​​to be filtered include a value

at. . or central value of an arbitrary window of dimensions K xK as well as bj all the values ​​contained in the square neighborhood centered on this value.

During cycle II, three new values ​​are introduced and the three oldest ones eliminated, as it was recalled, so as to obtain a new central value centered on a ^ The window thus moves step by step in a row-column scan so that each value has. whatever i and j become, in turn, the value

b) central of the filter window K x K.

z 2

If we denote by (K x K) = K = (2h '+ l) the number of cells of the sorting operator OT', the median value is generated, as in the case of unidirectional median filtering by selecting the cell of rank h '+ 1 and reading its content.

In the illustrated example K = 9, the row 5 cell is therefore selected using the RS member, in order to read there a new median value every two clock cycles H2.

The two-dimensional median filtering which has just been described is a true two-dimensional filtering.

In a simplified variant, by modifying the process, it is possible to obtain a pseudo-two-dimensional median filtering of the type which will be called in the following two-dimensional separable median filtering of order K.

This type of filtering has been proposed in known art with the aim of reducing the complexity of the devices used. As the images are divided, as has been recalled, into rows and columns, the main characteristic of this type of filtering is to operate in two stages: unidirectional K-order median filtering along the lines followed by unidirectional filtering of order K along the columns, the order of these two stages being naturally purely arbitrary.

Although theoretically different from conventional two-dimensional median filtering, experience has shown that separable two-dimensional filtering gives results which are sufficiently precise to be able to be used in numerous applications.

The method according to the invention and the devices for implementing this method are also compatible with this type of modified two-dimensional filtering.

Figure 9 illustrates an apparatus for separable two-dimensional median filtering.

It essentially comprises two one-dimensional median filtering devices of order K.

A first device, DF ML, corresponds to the one-dimensional filtering of order K along the lines of an image to be filtered and provides the corresponding median values ​​according to the process described in relation to FIGS. 3 to 5.

A second DFMC device functions as a conventional sorting operator and outputs the median value of the K intermediate median values ​​resulting from the processing carried out by the first DFML device. .

The two devices DFML and DFMC are identical to the devices DFM illustrated in FIG. 5.

These two devices are connected together using delay circuits and an MXLC multiplexer. The output of the first DFML device is connected to the input of a series of delay circuits all having an identical delay equal to one line. The number of these circuits is equal to (Kl).

The output of these delay circuits as well as the output of the first device are transmitted to the inputs of a multiplexer, inputs in number equal to the number K.

A frequency divider DF divides the frequency by K of the clock signals SHj applied to the second device DFMC and to the multiplexer MXLC. The clock signals SH '^ at the output of the divider DF are transmitted by a link H' ^ to the first device DFML.

It can be seen that the overall structure of the DFM2DS median filtering device is less complex than that of the device illustrated in FIG. 8 since there are only 2 K cells instead of the K cells used for conventional two-dimensional sorting.

In summary, the invention has the following advantages:

- a great modularity and a great regularity of architecture which allow an easy installation in semiconductor circuits with deep integration;

- modularity, the complexity of which increases linearly, unlike the architecture of known art;

- simple use of the same basic architecture to implement three distinct functions: one-dimensional median filtering, classic two-dimensional median filtering and separable two-dimensional filtering;

- finally, the processing time is independent of the order K for the unidirectional median filtering and only proportional to K for the two-dimensional median filtering.

The invention is not limited to only the examples of architecture explicitly described to illustrate the invention; all variants within the reach of man, of profession fall within the scope of the invention.

TABLE I

<td>H '</td><td>R 'a</td><td>^R1 '</td><td>^R2</td><td>^R3'</td><td>BE</td><td>RCj '</td><td>rc₂</td><td>RC,</td><td>^BL34</td><td>s</td>

<td> 0</td><td> 0</td><td> 0</td><td> 0</td><td> 0</td><td> 0</td><td></td><td> ^0</td><td> .0</td><td> .0</td><td> 0</td>

<td> 1 2</td><td> 5 5</td><td> 0 0</td><td> 0 0</td><td> 0 0</td><td> 0 5</td><td> 5</td><td></td><td>“F ίθ</td><td> 0</td><td>NS NS</td>

<td> 3 4</td><td> 10 10</td><td> 5 5</td><td> 0 0</td><td> 0 0</td><td> 0 10</td><td> 10</td><td></td><td>oo 5</td><td>0 / Ό</td><td>NS NS</td>

<td> 5</td><td> 7</td><td> 10</td><td> 5</td><td> 0</td><td> 0</td><td> 10</td><td rowspan="2">⁵\ 7</td><td>y</td><td> 0</td><td>NS</td>

<td> 6</td><td> 7</td><td> 10</td><td> 5</td><td> 0</td><td> 7</td><td> 10</td><td></td><td> ,0</td><td>NS</td>

<td> 7</td><td> 8</td><td> 7</td><td> 10</td><td> 5</td><td> 5</td><td> 10</td><td rowspan="2">S</td><td> 0^</td><td> 0</td><td> 7</td>

<td> 8</td><td> 8</td><td> 7</td><td> 10</td><td> 5</td><td> 8</td><td> 10</td><td>'7 's</td><td> .0</td><td> 7</td>

<td> 9</td><td> 3</td><td> 8</td><td> 7</td><td> 10</td><td> 10</td><td> 14</td><td> 7^</td><td></td><td> 0</td><td> 8</td>

<td> 10</td><td> 3</td><td> 8</td><td> 7</td><td> 10</td><td> 3</td><td> 8</td><td> 7</td><td> '³ .</td><td>z0</td><td> 8</td>

<td> 11</td><td> 1</td><td> 3</td><td> 8</td><td> 7</td><td> 7</td><td> 8</td><td></td><td></td><td> 0</td><td> 7</td>

<td> 12</td><td> 1</td><td> 3</td><td> 8</td><td> 7</td><td> 1</td><td> 8</td><td> 3</td><td> 1</td><td> 0</td><td> 7</td>

<td> 13 1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td> 3</td>