JPH11149554A - Simd calculation of filter based on 3x3 grid rank - Google Patents

Abstract

PROBLEM TO BE SOLVED: To execute a filter processing in a graphic picture so as to remove a picture omission or shot noise while preserving whole picture quality by including a step, etc., for calculating a center filter value after calculating a center value from an aggregation consisting of a max. intermediate value, a min. intermediate value and a center intermediate value. SOLUTION: In the step 130, a min. intermediate row is calculated through the use of three columns and respective elements in the min. intermediate row are calculated so as to be equal to a min. element in the corresponding column. In the step 140, a max. value is calculated from a class of entries consisting of the min. intermediate column so that the max. intermediate value is calculated. In the step 150, the center value is calculated from a class of entries consisting of a center intermediate row so that the center intermediate value is calculated. In the step 160, the min. value is calculated from a class of entries consisting of the max. intermediate row so that the min. intermediate value. In the step 170, the center value is calculated from the aggregation consisting of the max. intermediate value, the min. intermediate value and the center intermediate value so that the center filter value is calculated.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

FIELD OF THE INVENTION The present invention relates generally to graphical filters, and more particularly to an efficient SIMD method for rank-based filter computation for nine elements organized in a 3x3 grid. It concerns the device.

[0002]

2. Description of the Related Art As computers become faster and faster, computer users can use more advanced applications, thereby increasing the demand for higher speeds on their computers. One of the most important application areas today is graphics.

[0003] Graphics often require filtering of two-dimensional raster images. Each input pixel is one of the non-linear filters used to preserve overall image quality while eliminating "shot" noise, missing pixels, and other spurious features in a single pixel range. , Itself and the median of the eight surrounding input pixel values.

[0004]

An example of finding the median of the nine elements is Graphic Gem, edited by Andrew S. Glassner.
s, pages 171 to 175 (copyright 1990,
Academic Press, Inc., Harcourt Brace Jananovich, Pu
blishers, ISBN 0-12-286165-5). The actual code of this algorithm is
It is shown on page 2. This algorithm has the disadvantage that too many comparison operations have to be performed.

A method for determining the median value of nine elements is "R
No. 5,532,948 to Maashiro Kohne, et al., entitled "ank Order Filter," which compares certain values in nine elements,
Since the operation to be performed to determine the median is determined, the control flow is not free (control-flow-free). In contrast, the method disclosed in this patent determines the median of the nine numbers using a free-flowing control method. This is because the operation to be performed does not depend on the nine numerical values. The advantage of the method in which the control flow is free is that a single instruction multiple data (SIMD) is used.
ta) Implementing it in a processor allows more efficient use of the parallelism of the processor than implementing a non-flexible control flow method on the same SIMD processor.

[0006] A method of completely sorting the nine elements using a free-flowing algorithm is described by Donald E. Knuth.
The Art of Computer Programming, Volume 3 (Copyright 1973, Addison-Wesley Publishing Company, I
SBN 0-201-03803-X) on page 228. The method of completely sorting the nine numbers in a 3x3 grid disclosed in this patent specification utilizes the rows and columns shared between adjacent overlapping 3x3 grids to reduce the total number of comparison operations, It is intended to improve the prior art.

[0007] The features and advantages of the present invention will become more apparent from the following detailed description, taken in conjunction with the accompanying drawings. In the drawings, like numbers indicate like parts and corresponding parts.

[0008]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS An optimized method for finding the median of nine numbers, which is significantly less required for comparison operations than required by the prior art and is suitable for parallel vector operations, is disclosed. I do. The calculation of this optimized median is further extended by combining operations for adjacent grids, first shared rows, and further columns, resulting in further performance improvements.

FIG. 1 is a diagram illustrating a two-dimensional raster image as received by an image scanner, digital camera, copier, laser printer, video monitor, and fax machine. Raster images are two-dimensional (2D)
Expressed as a matrix 100, each cell in the matrix represents one pixel in the raster image. As in the standard, a column is a set of matrix cells arranged in a vertical direction, while a row is a set of matrix cells arranged in a horizontal direction.

As noted above, one type of non-linear filter is to replace each raster pixel with the median of itself and eight surrounding pixels. This is called a "median filter". FIG. 2 is a diagram showing a 3 × 3 matrix 110 of pixels used to calculate such a median. 3x3 matrix 11
0 includes three rows 1, 2, 3, where each such row is 3
The three consecutively numbered (1,2,3) columns that contain three elements or pixels similarly contain three elements or pixels each.

FIG. 3 is a flowchart showing a method for determining the median of nine numerical values organized in a 3 × 3 matrix. Beginning at step 120, at step 130 a second 3x3 matrix is formed. The first row (row A) contains the minimum from each of the three columns, the second row (row B) contains the median from each of the three columns, and the third row (row A). C) contains the maximum from each of the three columns. Next, a 3-entry vector (M) is formed. In step 140, the first element in this vector is set as the largest element in the first row (row A), and
At 50, the second element is the center element of the second row (row B), and at step 160, the third element is the smallest element of the third row (row C). Finally, in step 170, the median of the nine numbers organized in a 3x3 grid is calculated and taken as the median of the 3-entry vector (M).

Steps 130, 140, 150, 1
Note that 60 indicates the minimum, median, and maximum operations of the three operands. This is used only for the purpose of illustrating the method disclosed above and is obviously a simplification of the actual method. That is, in these steps, first the first intermediate minimum is calculated to be the minimum of the first and second operands, and then the first intermediate median is calculated to obtain the maximum of the first and second operands. And then calculate the second intermediate median to be the minimum of the first intermediate median and the third operand, and then calculate the maximum of the three operands to be the maximum of the first intermediate median and the third operand. , Then 3
Calculate the operand minimum to determine the first intermediate minimum and the second
The median value is set to the minimum value, and finally the median value of the three operands is calculated to be the maximum value of the first and second median values. 3 unless indicated otherwise in the sentence
Whenever a minimum, median, or maximum value calculation for one operand is indicated herein, the foregoing embodiment is intended.

FIG. 4 shows an example of the method shown in FIG.
It is a figure showing an example which asks for the median of two numerical values. Original 3
The x3 grid 200 has each of its columns sorted (210). Next, a vector 220 is formed from the maximum element in the first row (A), the central element in the second row (B), and the minimum element in the third row (C). The median from this vector 220 is the median 230 of the nine numbers.

FIG. 5 is a diagram of a 4 × 3 matrix 310 representing two overlapping 3 × 3 matrices. 4x such
The three matrix 310 can be used to calculate two vertically adjacent median filtered values. The rows are consecutively 1, 2, 3,
It is numbered four.

FIG. 6 is a flowchart illustrating the optimization of the method of FIG. 3 according to the present invention, which allows the generation of median values for the two overlapping 3 × 3 matrices shown in FIG. First, two new rows are calculated. In step 330, row A contains the smallest element from each column of rows 2 and 3, and row B
Contains the largest element from each column of rows 2 and 3. Note that these calculations can be performed efficiently using minimum and maximum functions. Next, the first intermediate 3x3
Form a matrix. That is, in step 340, the first row (C) contains the minimum value from each of the three columns in rows 1, A, B, and the second row (D) contains the minimum values in rows 1, A, B. It contains the median from each of the three columns, and its third row (E) contains the maximum value from each of the three columns in rows 1, A, B. Next, a first 3-entry intermediate vector (M) is formed. In step 350, the first element (M ₁ ) in this vector is the largest element in the first row (row C), and in step 360,
The second element (M ₂ ) is the center element of the second row (row D),
In step 370, a third element (M ₃₎ is the smallest element of the third row (E). Finally, in step 380, the median for the nine numbers organized in the first overlapping 3x3 matrix is calculated and taken as the central element of the first intermediate vector (M).

This method is the same when calculating the median for nine values in the second overlapping 3 × 3 matrix. Note, however, that the calculations for rows A and B that are shared are shared. This is for rows 2, 3
Is shared between the two 3 × 3 matrices.
First, in step 390, a second intermediate 3x3 matrix is formed. The first row (F) is row 4, A, B
Contains the minimum value from each of the three columns in
Row (G) contains the median from each of the three columns in rows 4, A and B, and its third row (H) shows the maximum from each of the three columns in rows 4, A and B. including. Next, the second
To form an intermediate 3-entry vector (N). In step 400, the first element (N ₁ ) in this vector is the maximum value of the first row (F), and step 41
At 0, the second element (N ₂ ) is the median value of the second row (G), and at step 420, the third element (N ₃ ) is the smallest element of the third row (H). Finally, step 43
At 0, calculate the median for the nine numbers organized in the second overlapping 3x3 matrix and make it the central element of the second intermediate vector (N).

FIG. 7 shows an example of the operation of the method shown in FIG. The original 4 × 3 matrix 450 has its center row (rows 2 and 3) sorted into rows A and B 460. A first 3x3 intermediate matrix 470 is formed by sorting the columns of rows A, B, 1. A second 3x3 intermediate matrix 500 is formed by sorting the columns of rows A, B, and 4. First intermediate vector (M) 480
Is formed from a first 3x3 intermediate matrix 470;
A second intermediate vector (N) 510 is formed from a second 3x3 intermediate matrix 500. Finally, two medians are formed. The first median 490 is formed from the central element in the first intermediate vector (M) 480, and the second median 520 is formed from the central element in the second intermediate vector (N) 510.

FIG. 8 shows the vector length V of the method shown in FIG.
Optimization using vectorization (vectorized optimi
4xV matrix 53 used to indicate
0. 9, 10, and 11 are flowcharts showing the optimization by vectorization of the method shown in FIG. 6 as a whole. FIG. 9 shows the upper operation and the outer loop, while FIGS. 10 and 11 show the vectorization operation performed inside the loop in FIG. still,
It should be noted that FIG. 9 is used similarly to FIGS.

Referring to FIG. 9, at the start, step 5
At 50, the row number index is initialized to zero.
Next, enter the outer loop. At step 560, a check is made as to whether there are any more rows, and if there are no more rows to process, the outer loop is completed and the method ends. Conversely, if there are more rows to process, step 58
At 0, the column number index is initialized to 0. Next, an inner loop is entered to check in step 590 if there are any more columns to process. As long as there are more columns to be processed, the blocks shown in FIGS. 10 and 11 starting at step 620 and ending at step 740 are executed. The functionalities of FIGS. 10 and 11
ty), the column number index is incremented by the vector length (V) in step 750, and then the inner loop is repeated, starting with a check in step 590 for any additional columns to process. I do. If there are no more columns to process, step 760 increments the row number by 2 and repeats the outer loop, starting with a test at step 560 for any other rows to process. .

Referring now to FIG. 10, the inner body starts at step 620 and loads four vector registers. That is, in step 625, row 1 contains:
Load V elements starting at the specified row and column. Here, V is the vector length. Row 2 is loaded with V elements starting at the next row (row +1) and the current column. Row 3 is loaded with V elements starting at the third row (row + 2) and the current column. Row 4 is loaded with V elements starting from the fourth row (row + 3) and the current column.

First, two new rows are calculated. That is,
In step 630, row A contains the smallest element from each column for rows 2 and 3, while row B contains the largest element from each column for rows 2 and 3. Note that these calculations are based on V
SIMD vector min and max functions (SIMDvec) that generate V results in parallel using the pairs of input operands
tor minimum and maximum functions)
Note that it can be calculated efficiently. Next, a first intermediate 3xV matrix is formed. That is, step 64
At 0, its first row (row C) contains the minimum value from each of the V columns in rows 1, A, B, and its second row (row D) in rows 1, A, B It contains the median from each of the V columns, the third row (row E) being row 1, A, B
. Contains the maximum value from each of the V columns.

Next, a first 3-vector intermediate matrix (M) is formed. That is, the first in this matrix
The vector (M ₁ ) contains the largest element, the second vector (M ₂ ) contains the central element, and the third vector (M ₃ ) contains the smallest element. In step 650, when calculating the first vector (M _1), to load the line C _S containing coupled with the first (V-1) number of elements in the row C, and the last one element row Prev_C , Load a row C _SS containing the last two elements of row Prev_C, concatenated with the first (V-2) element of row C, and row M ₁ contains V rows for rows C, C _S , C _SS Is calculated to include the largest element in each of the columns. Similarly,
In step 660, load case, the line D _S including the first (V-1) last one element of the individual elements and the connecting row Prev_D line D to calculate a second vector (M _2), Row Pr connected to the first (V-2) elements of row D
Load row D _SS containing the last two elements of ev_D, and add row M
₂ is calculated to include the central element in each of the V columns for rows D, D _S , and D _SS . Similarly, step 6
At 70, when calculating the third vector (M ₃ ),
Row Prev concatenated with the first (V-1) elements of row E
Load row E _S containing the last one element of _E, load row E _SS containing the last two elements of row Prev_E concatenated with the first (V-2) elements of row E, Row M ₃ is calculated to include the smallest element in each of the V columns for rows E, E _S , and E _SS . Next, at step 680, calculate V medians for the V sets of 9 numbers, organized into a first V overlapping 3x3 matrix,
The first, including rows M ₁ , M ₂ , M ₃ shifted one element to the left
This is the central element of the intermediate matrix (M). Finally, in step 685, row C is saved in vector Prev_C, row D is saved in vector Prev_D, and row E is saved in vector Prev_D.
Save to Prev_E.

The same applies to the method and apparatus used in calculating the median for the V sets of nine numbers in the second set of V overlapping 3x3 matrices. Note, however, that the calculations for shared rows A and B are shared in this calculation. The reason for this sharing is that rows 2, 3
Is shared between two sets of V 3 × 3 matrices. In step 690, a second intermediate 3x3 matrix is first formed. The first row (row F) contains the minimum from each of the three columns in rows 4, A and B, and the second row (row G) from each of the three columns in rows 4, A and B And the third row (row H) contains
Contains the maximum value from each of the three columns in rows 4, A, B.

Next, a second 3-vector intermediate matrix (N) is formed. That is, the first vector (N ₁ ) of this matrix contains the largest element, the second vector (N ₂ ) contains the central element, and the third vector (N ₃ ) contains the smallest element. When calculating the first vector (N ₁ ), step 70
At 0, connected with the first (V-1) number of elements in the row F, loads the row F _S containing the last one element row Prev_F, first row F (V-2) number of Concatenated with the element,
To load the line F _SS, including the last two elements of the line Prev_F,
Row N ₁ is calculated to include the largest element in each of the V columns for rows F, F _S , and F _SS . Similarly, when calculating the second vector (N ₂ ), in step 710, the row Pr connected to the first (V-1) elements of row G
Load row G _S containing the last one element of ev_G, and
Load row G _SS containing the last two elements of row Prev_G concatenated with the first (V-2) elements of row N ₂ , and row N ₂ contains V columns for rows G, G _S , and G _SS Is calculated to include the central element in each of the. Similarly, the third vector (N
When calculating the _3), at step 720, which is connected with the first (V-1) number of elements in the row H, to load the line H _S containing the last one element row prev_h, first row H Last 2 of row Prev_H concatenated with the (V-2) elements of
Load row H _SS containing two elements, row N ₃ contains rows H, H
Calculate to include the smallest element in each of the V columns for _S , H _SS . Next, at step 730, the V medians for the 9 values of the V set, organized into a second V overlapping 3x3 matrix, are calculated and the rows N ₁ , N ₂ shifted left by one element. , N ₃ as the central element of the second intermediate matrix (M). Finally, step 73
At 5, save row F in vector Prev_F, save row G in vector Prev_G, and save row H in vector Prev_H.

FIG. 12 shows an example of the operation of the method shown in FIGS. Original 4x6 matrix 790
Means that the two center rows (rows 2 and 3) are rows A and B800
Has been sorted. The inputs to this step include Prev_C, Prev_D, Prev_E700 and Prev_F,
This is the result from the previous run, stored as Prev_G, Prev_H780. A first 3 × 6 intermediate matrix 810 including rows C, D, and E is formed by sorting the columns of rows A, B, and 1. Second 3x including rows F, G, H
The six intermediate matrix 820 is formed by sorting the columns of rows A, B, and 4. The first set of intermediate vectors (M) is the first vector (M ₁ ) 850 containing the largest element in each column from rows C, C _S , C _SS 830, columns D, D
_S , the second including the central element in each column from D _SS 870
Vector (M ₂ ) 890 and rows E, E _S , E _SS 91
A third vector (M) containing the smallest element in each column from 0
₃ ) formed from 930; The second set of intermediate vectors (N) is a first vector (N ₁ ) 860 containing the largest element in each column from rows F, F _S , F _SS 840, columns G, G
_S , the second containing the central element in each column from G _SS 880
Vector (N ₂ ) 900 and rows H, H _S , H _SS 92
A third vector (N
₃ ) formed from 940; The row C _S is obtained by shifting the row C by one element, and the row C _SS is obtained by shifting the row C by two elements.
Note that by saving to _C, the elements are replaced and replaced, entering both rows C _S and C _SS .
This vector naming convention is
Also applies to rows D, E, F, G, H. Finally, two medians are formed. The first V medians 950 are
Formed by selecting the central element in each column from the set of intermediate vectors (M) 850, 890, 930;
The second V medians 960 are formed by selecting the median elements in each column from the second set of intermediate vectors (N) 860,900,940. The first V medians 950 and the second V medians 960 are both:
It has been shifted one element to the left.

FIG. 13 is a diagram of a 3 × 3 matrix 1010 to illustrate a method of completely sorting nine numerical values. FIG. 14 shows a 3 × 3 coefficient matrix 1020 for illustrating a weighted filtering process using nine sorted numerical values.
FIG. FIG. 15 is a diagram of four 3 × 3 matrices showing the operation of the method of completely sorting the nine numerical values organized in a 3 × 3 matrix. It should be noted that the direction of the arrow in each 3x3 matrix shown indicates the order of sorting, the tip of the arrow indicates the direction in which the numerical value increases, and the arrowhead indicates the direction in which the numerical value decreases. First, the columns are sorted (2110). Next, sort the rows (21
20). Third, elements on a line parallel to the Y = X diagonal are sorted (2130). Finally, the elements on the line parallel to the 2 ^* Y = X diagonal are sorted (2140). The resulting 3x3 matrix has its elements sorted in ascending row order. The basic method described below can be modified to produce a matrix sorted in descending order of columns. At that time, the direction of Y = X diagonal sort is reversed, and 2 ^* Y = X diagonal sort is performed, and Y = 2 ^* X
Replace with diagonal sort. Sorting by row order is used in the preferred embodiment because of its improved SIMD vectorization characteristics.

FIG. 16 completely sorts the nine elements,
9 is a flowchart illustrating a method of calculating a weighted filter value of nine numerical values organized in a 3 × 3 matrix. Upon start, first in step 1040, the second 3x
A three matrix (B) is formed. The first row (B ₁ ) contains the minimum from each of the three columns, and the second row (B ₁ )
₂ ) contains the median value from each of the three columns, and its third row (B ₃ ) contains the maximum value from each of the three columns. next,
In step 1050, a second 3x3 matrix (C) is formed. Its first row (C ₁ ) contains the minimum value from each of the three columns, its second row (C ₂ ) contains the median value from each of the three columns, and its third row (C ₃ ) Contains the maximum value from each of the three columns. Next, elements on a line parallel to the Y = X-ray are sorted. In step 1060, set to the median value of the three central diagonal elements _{(C 13, C 22, C} 31) element D _13, which is set to the minimum value of the three central diagonal elements _{(C 13, C 22, C} 31) Element D ₂₂ ,
And three central diagonal elements _{(C 13, C 22, C} 31) element D ₃₁ which is set to the maximum value of, forming a central diagonal. In step 1070, the two upper diagonal elements (C _12, C ₂₁₎ the minimum value set to the element D ₁₂ and of two upper diagonal elements (C _12, C ₂₁₎ up to set the value element of D _21, To form an upper diagonal line. Step 1
080, two upper diagonal elements (C ₂₃ , C ₃₂ )
D ₂₃ set to the minimum value of, and the element D set to the maximum value of the two upper diagonal elements (C ₂₃ , C ₃₂ )
_{From 32} , a lower diagonal is formed. Next, the elements on the line parallel to the line defined by 2 ^* Y = X are sorted. In step 1090, the two upper diagonal elements (D _13, D ₂₁₎ Min Max set to value elements of the set elements E _13, and two upper diagonal element values (D _13, D ₂₁₎ E ₂₁ To form an upper diagonal line. Step 1
At 100, two upper diagonal elements (D ₂₃ , D ₃₁ )
E ₂₃ set to the minimum value of E and the element E set to the maximum value of the two upper diagonal elements (D ₂₃ , D ₃₁ )
_{From 31} , a lower diagonal is formed. At this point, the original input matrix (A) has been effectively sorted by rank. That is, the first row contains C ₁₁ , D ₁₂ and E ₁₃ , the second row contains E ₂₁ , D ₂₂ and E ₂₃ , and the third row contains E ₃₁ , D ₂₂ and E ₂₃ .
D ₃₂ and C ₃₃ are included. Thus, the sort order of the nine numbers (from smallest to largest) is C ₁₁ , D ₁₂ , E ₁₃ , E ₂₁ ,
The _{D 22, E 23, E 31} , D 32, C 33. Finally, in step 1110, the first weight matrix (K) 102
A weighted filter value is calculated by multiplying each entry in 0 by the corresponding sorted matrix element.

FIG. 17 is a diagram showing an example of the operation of the method shown in FIG. The original matrix (A) 1130 is sorted by column to form a column sort matrix (B) 1140. The column sort matrix (B) 1140 is sorted by rows to form a row sort matrix (C) 1150. The elements from the row sort matrix (C) 1150 on a line parallel to the Y = X line are sorted to form a first diagonal matrix (D) 1160. As a result, 2 ^* Y = X
The elements in the matrix obtained on a line parallel to the line are sorted to form a second diagonal matrix (E) 1170. Finally, the row sort matrix 1150, the first diagonal matrix 1160, and the second diagonal matrix 1
The element selected from 170 is multiplied by the corresponding element in weight matrix 1180 and added to produce a weighted filter value 1
190 is calculated.

FIG. 18 is a diagram of a 4 × 3 matrix 1200 representing two overlapping 3 × 3 matrices. 4x such
The two matrices 1200 are two vertically adjacent,
It can be used to calculate a weighted filter value based on rank. A _1j , A _2j,. . . A _4j
, And the columns are sequentially numbered A _1i , A _2i , and A _3i . The first 3x3 matrix has rows A _1j ,
A _2j and A _3j are included. The second 3x3 matrix includes rows _A2j , _A3j , _A4j .

FIGS. 19 and 20 show the overall structure of FIG.
Two overlapping 3x combined into a 4x3 matrix as shown in Figure 8
17 is a flowchart illustrating optimization of the method shown in FIG. 16 that enables generation of weighted filter values for three matrices. First, two new columns are calculated. That is, in step 1220, the line B comprises minimal elements from each column in the shared row A _2j, A _3j, row C is shared row A _2j, A
_Include the largest element from each column in _3j . Note that these calculations can be performed efficiently using minimum and maximum functions. Next, the first intermediate 3 × 3
A matrix is formed (D). That is, step 1230
, Its first row (D _1j ) contains the minimum value from each of the three columns in rows A _1j , B, C and its second row (D _1j )
_2j ) contains the median from each of the three columns in rows A _1j , B, and C, and the third row (D _3j ) contains the maximum value from each of the three columns in rows A _1j , B, and C. Including. Next, a second intermediate 3 × 3 matrix (E) is formed from the first intermediate 3 × 3 matrix (D). That is, in step 1240, the first column (E _i1 ) contains the minimum from each of the three rows in the first intermediate 3 × 3 matrix (D), and the second column (E _i2 ) contains the first intermediate (E _i2 ). The third column (E _i3 ) contains the minimum value from each of the three rows in the 3 × 3 matrix (D) and the first intermediate 3 × 3 matrix (D)
Contains the maximum from each of the three rows in. Next, Y
= Sort elements on line parallel to X-ray. Step 12
In 50 sets the elements F ₁₃ to the minimum value of the elements _{E 13, E 22, E 31} , sets the elements F ₂₂ to the median value of the elements _{E 13, E 22, E 31} , elements F ₃₁ elements E ₁₃ , E ₂₂ and E ₃₁ are set to the maximum values. In step 1260, the element F ₁₂ elements E _12, set to the minimum value of E _21, elements F ₂₁ elements E _12, E
Set to the maximum value of ₂₁ . In step 1270, sets the elements F ₂₃ to the minimum value of element E _23, E _32, sets the elements F ₃₂ to a maximum value of the elements E _23, E _32. Next, 2 ^* Y = X
Sort elements on a line parallel to the line. Step 1280
In sets the element G ₁₃ to a minimum of elements F _13, F _21, sets the elements G ₂₁ to the maximum value of the elements F _13, F _21. In step 1290, sets the elements G ₂₃ to a minimum of elements F _23, F _31, sets the elements G ₃₁ to the maximum value of the elements F _23, F _31. Finally, in step 1300, the weighted rank criterion filter value obtained for the upper 3x3 grid is calculated to be equal to the sum of the products of each obtained matrix value and the corresponding weight. That is, result = E _{11
^{* K 11 + F 12 * K}} 12 + G 13 * K 13 + G 21 * K 21 + F 22 *
^{_{K 22 + G 23 * K 23}} + G 31 * K 31 + F 32 * K 32 + E 33 * K
It becomes ₃₃ .

Second (lower) overlapping 3x3 grid
The same applies to a method of calculating a weighted filter value for.
The calculation for the shared rows B and C is performed on the upper 3x3 grid.
To be shared between and the calculation of the lower 3x3 grid
Is noted. First, the first intermediate 3x3 matrix
(H) is formed. That is, in step 1310,
The first line (H_1j) Is row A_4j, B, C, three columns
, And its second row (H_2j) Is row A
_4j, B, and C contain the median from each of the three columns.
The third line (H_3j) Is row A_4j, B and C
Contains the maximum value from each of the columns. Next, the first intermediate 3x
From the 3 matrix (H) to the second intermediate 3x3 matrix
(I) is formed. That is, in step 1320,
The first column (I_i1) Is the first intermediate 3x3 matrix
Containing the minimum from each of the three rows in (H),
In the second column (I_i2) Is the first intermediate 3 × 3 matrix (H)
Containing the median from each of the three rows in
Column (I_i3) In the first intermediate 3x3 matrix (H)
Contains the maximum value from each of the three rows. Next, Y = X-ray
Sort elements on a line parallel to. To step 1330
And element J₁₃Is the element I₁₃, I_{twenty two}, I₃₁Set to the minimum
And element J_{twenty two}Is the element I₁₃, I_{twenty two}, I₃₁Set to the median of
Then element J₃₁Is the element I₁₃, I_{twenty two}, I₃₁To the maximum value of
You. In step 1340, the element J₁₂Is the element I₁₂,
I_{twenty one}Set to the minimum value of_{twenty one}Is the element I₁₂, I_{twenty one}Most
Set to a large value. In step 1350, the element J_{twenty three}
Is the element I_{twenty three}, I ₃₂Set to the minimum value of₃₂Is the element I
_{twenty three}, I₃₂Set to the maximum value of. Next, 2^* Y = X-ray flat
Sort elements on a line. Step 1360
And the element L₁₃To element J₁₃, J_{twenty one}Set to the minimum of the element
L_{twenty one}To element J₁₃, J_{twenty one}Set to the maximum value of. Step 1
At 370, the element L_{twenty three}To element J_{twenty three}, J₃₁To the minimum of
Set the element L₃₁To element J_{twenty three}, J₃₁To the maximum value of
You. Finally, in step 1380, the lower 3x3
Weighted rank criterion filter value obtained for the grid
Is the product of each obtained matrix element and the corresponding weight.
Calculate to be equal to the sum. That is, result = I₁₁ ^* K
₁₁+ J₁₂ ^* K₁₂+ L₁₃ ^* K₁₃+ L_{twenty one} ^* K_{twenty one}+ J_{twenty two} ^* K_{twenty two}
+ L_{twenty three} ^* K_{twenty three}+ L₃₁ ^* K₃₁+ J₃₂ ^* K₃₂+ I₃₃ ^* K₃₃When
Become.

FIG. 21 is a diagram showing an example of the operation of the method shown in FIG. 19 and FIG. The original 4 × 3 matrix (A) 1400 shares its two center rows (A _2j , A _3j ). These two shared rows (A _2j , A _3j )
Are sorted into rows B and C1410. An intermediate matrix D 1420 is formed by sorting the columns of the matrix formed from rows A _1j , B, and C. Row A _4j ,
An intermediate matrix H1480 is formed by sorting the columns of the matrix formed from B and C. The intermediate matrix E1430 is formed by sorting the rows in the matrix D1420. Matrix H14
By sorting the rows in 80, an intermediate matrix I 1490 is formed. By sorting the elements parallel to the Y = X diagonal in the intermediate matrix E1430,
A diagonal matrix F1440 is formed. The diagonal matrix J1500 is formed by sorting the elements parallel to the Y = X diagonals in the intermediate matrix I1490. A diagonal matrix G1450 is formed by sorting the elements parallel to the 2 ^* Y = X diagonals in the intermediate matrix F1440. A diagonal matrix L1510 is formed by sorting the elements parallel to the 2 ^* Y = X diagonals in the intermediate matrix J1500. The matrices G1450 and L1510 are
When the matrix 50 is filled with the corresponding elements in the matrices F1440 and E1430, and the matrix L1510 is filled with the corresponding elements in the matrices J1500 and I1490, the 4x3 matrix (A) 1400 is integrated.
The elements from the two original 3x3 matrices that make up
They will be included in sorted order. The weighted filter value 1470 for the upper 3x3 matrix is the matrix G1
The sorted elements in 450 are weighted (K)
Calculated by adding the product multiplied by the corresponding element in 1460. The weighted filter value 1520 for the lower 3x3 matrix is calculated by adding the product of the sorted elements in matrix L1510 multiplied by the corresponding elements in weight matrix (K) 1460.

FIGS. 22 to 25 show a 4 ×
5 is a flow chart showing a vector operation for a complete sort of V and the calculation of a weighted filter value of 2 × V. These four figures are functionally replaced with FIGS. 10 and 11,
Note that it is inserted into the inner loop of FIG. The methods shown in FIGS. 10 and 11 can be viewed as a special optimized case where the weight matrix (K) contains 0 for all elements except the center and 1 for the center.

The inner body starts at step 620,
Load four vector registers. That is, in step 1530, the row A ₁ loads the V-number of elements starting from the specified row and column. Here, V is the vector length. To the line A ₂ is, to load the V-number of elements starting from the next row (row + 1) and the current column. In line A ₃ is,
Load the V elements starting at the third row (row + 2) and the current column. In line A ₄ is the fourth row (row +3)
And V elements starting from the current column.

First, two new rows are calculated. In step 1540, includes a minimal elements from each column for a row B row A _2, A _3, including the maximum elements from each column for a row C row A _2, A _3. These calculations are based on SIMD vectormimic functions that use V pairs of input operands to generate V results in parallel.
It should be noted that the calculation can be performed efficiently by using (nimum and maximum functions). Next, the first intermediate 3
An xV matrix (D) is formed. That is, step 15
At 50, the first row (D ₁ ) includes rows A ₁ , A ₂ ,
The second row (D ₂ ) contains the minimum value from each of the V columns in A _3, and contains the median value from each of the V columns in rows A ₁ , A ₂ , A ₃ , and The third line (D ₃ )
Contains the maximum value from each of the V columns in rows A ₁ , A ₂ , A ₃ . The minimum element of each column for rows A ₁ , A ₂ , A ₃ is calculated by taking the minimum of rows A ₁ , B. The central element of each column for rows A ₁ , B, and C can be calculated by calculating the maximum value of rows A ₁ and B or the minimum value of rows A ₁ and C. The maximum element of each column for a row is calculated by taking the maximum value of rows A ₁ and C.

Next, a first 3-vector intermediate matrix (E _1j ) is formed. That is, the first vector (E ₁₁ ) in this matrix contains the smallest element, the second vector (E ₁₂ ) contains the central element, and the third vector (E ₁₃ ) contains the largest element. In step 1560, when calculating the first vector (E _11), is connected with the first (V-1) number of elements in the row D _1, the line D _1S including the last one element row Prev_D ₁ loaded, linked with the first (V-2) elements in the row D _1, to load the line D _1SS containing the last two elements of the row Prev_D _1, row E ₁₁ is the line D _1, D _1S, Calculate to include the smallest element in each of the V columns for D _1SS , and Row E ₁₂ to include the central element in each of the V columns for rows D ₁ , D _1S , D _1SS , Row E ₁₃
Is calculated to include the largest element in each of the V columns for rows D ₁ , D _1S , D _1SS .

Similarly, when calculating the second 3-vector intermediate matrix (E _2j ), at step 1570, the first (V-1) elements of row D ₂ are concatenated with
Load the line D _2S containing the last one element row Prev_D _2, coupled with the first (V-2) number of elements in the row D _2,
Load row D _2SS containing the last two elements of row Prev_D ₂ and calculate row E ₂₁ to include the smallest element in each of the V columns for rows D ₂ , D _2S , D _2SS , E
₂₂ is calculated to include the central element in each of the V columns for rows D ₂ , D _2S , D _2SS , and row E ₂₃ is
Calculate to include the largest element in each of the V columns for ₂ , _D2S , _D2SS .

Similarly, when calculating the third 3-vector intermediate matrix (E _3j ), in step 1580, the first (V-1) elements of row D ₃ are concatenated with
Load row D _3S containing the last one element of row Prev_D ₃ , concatenated with the first (V−2) elements of row D ₃ ,
Load row D _3SS containing the last two elements of row Prev_D ₃ , and calculate row E ₃₁ to include the smallest element in each of the V columns for rows D ₃ , D _3S , D _3SS , E
₃₂ is calculated to include the central element in each of the V columns for rows D ₃ , D _3S , D _3SS , and row E ₃₃ is
Calculate to include the largest element in each of the V columns for ₃ , _D3S , _D3SS .

Next, a first set of Y = X diagonal matrices
Compute the vector. In step 1590, row F
₁₃ is calculated as including the smallest element in each of the V-number of columns for row _{E 13, E 22, E 31} . Row F ₂₂ are calculated to include the central element in each of the V-number of columns for row _{E 13, E 22, E 31} . Row F _31, the row E _13, E _22,
Calculated as including the maximum element in each of the V-number of columns for E _31. Next, a second set of Y = X diagonal matrix vectors is calculated. In step 1600, the row F ₁₂ are calculated to include the minimum element in each of the V-number of columns for row E _12, E _21, row F _21, the row E _12, E ₂₁
To include the largest element in each of the V columns. Next, a third set of Y = X diagonal matrix vectors is calculated. In step 1610, row F ₂₃
Is calculated to include the smallest element in each of the V columns for rows E ₂₃ and E ₃₂ , and row F ₃₂ is to include the largest element in each of the V columns for rows E ₂₃ and E ₃₂ . calculate.

Next, a first set of 2 ^* Y = X diagonal matrix vectors is calculated. That is, in step 1620, the line G ₁₃ calculated to include the minimum element in each of the V-number of columns for row F _13, F _21, the maximum element in each of the V-number of columns for row F _13, F ₂₁ Row G to include
Calculate ₂₁ . Next, a second set of 2 ^* Y = X diagonal matrix vectors is calculated. That is, in step 1630, the line G ₂₃ calculated to include the minimum element in each of the V-number of columns for row F _23, F _{3 1,} row F _23, F ₃₁
Calculating the line G ₃₁ to include a maximum element in each of the V-number of columns for.

By shifting the sum of the product of the weight matrix (K) and the corresponding sorted vector by one position to the left, a vector of the obtained weighted filter values for the upper 3 × V matrix is calculated. That is, step 16
At 40, the result = K ₁₁ ^* (row) E ₁₁ + K ₁₂ ^* (row)
F ₁₂ + K ₁₃ ^* (row) G ₁₃ + K ₂₁ ^* (row) G ₂₁ + K
₂₂ ^* (row) F ₂₂ + K ₂₃ ^* (row) G ₂₃ + K ₃₁ ^* (row) G ₃₁
+ K ₃₂ ^* (line) F ₃₂ + K ₃₃ ^* (line) E ₃₃ Finally, in step 1650, the row D ₁ vector Prev
Saved in _D _1, save the line D ₂ in vector Prev_D _2, saving the line D ₃ vector Prev_D _3. The same applies to the method and apparatus used to calculate the vector of weighted filter values for the V sets of 9 values in the lower set of V overlapping 3x3 matrices. However,
Note that the calculations for shared rows B and C are shared in this calculation. This sharing shows that rows A ₂ and A ₃ are 2
This is because the set of V 3 × 3 matrices is shared. First, in step 1660, the first intermediate 3x
A V matrix (H) is formed. That is, step 167
0, the first row (H ₁ ) is the row A ₂ , A ₃ , A ₄
, Including the minimum value from each of the V columns in
Row (H ₂ ) contains the median from each of the V columns in rows A ₂ , A ₃ , A ₄ , and the third row (H ₃ ) contains rows A ₂ ,
Contains the maximum value from each of the V columns in A ₃ , A ₄ . By calculating the minimum of rows A ₄ and B,
_2, to calculate the minimum element of each column for A _3, A _4. The central element of each column for rows A ₂ , A ₃ , A ₄ is the row A ₄ ,
It can be calculated by calculating either the maximum value of B or the minimum value of rows A ₄ and C. Row A ₂ , A
The maximum element of each column for ₃ and A ₄ is calculated by calculating the maximum value of rows A ₄ and C.

Next, a first 3-vector intermediate matrix (I _1j ) is formed. The first vector (I ₁₁ ) of this matrix contains the smallest element, the second vector (I ₁₂ ) contains the central element, and the third vector (I ₁₃ ) contains the largest element.
In step 1680, when calculating first vector (I _11), connected with the first (V-1) number of elements in the row H _1, row H _1S including the last one element row prev_h ₁ load, is connected with the first (V-2) number of elements in the row H _1, load the line H _1SS containing the last two elements of the row prev_h _1, row H _1, H _1S, against H _1SS Calculate row I ₁₁ to include the smallest element in each of the V columns,
_1, H _1S, lines I ₁₂ to include a central element in each of the V-number of rows calculated for H _1SS, rows H _1, H _1S, H
Calculating the line I ₁₃ to include a maximum element in each of the V-number of columns for _1SS.

Similarly, in step 1690, the second
To calculate the three-vector intermediate matrix (I _2j ) of, concatenated with the first (V−1) elements of row H ₂ ,
Load the line H _2S containing the last one element row prev_h _2, coupled with the first (V-2) number of elements in the row H ₂ rows
Load row H _2SS containing the last two elements of Prev_H ₂ , calculate row I ₂₁ to include the smallest element in each of the V columns for rows H ₂ , H _2S , H _2SS , and calculate row H ₂ , H
_2S, the line I ₂₂ calculated to include the central element in each of the V-number of columns for H _2SS, row H _2, H _2S, line to include the maximum element in each of the V-number of columns for H _2SS I
Calculate ₂₃ .

Similarly, in step 1700, the third
When calculating of 3-vector intermediate matrix (I _3j), connected with the first (V-1) number of elements in the row H _3,
Load the line H _3S including the last one element row prev_h _3, connected with the first (V-2) number of elements in the row H _3,
Load row H _3SS containing the last two elements of row Prev_H ₃ and calculate row I ₃₁ to include the smallest element in each of the V columns for rows H ₃ , H _3S , H _3SS , ₃ , H
Calculate row I ₃₂ to include the central element in each of the V columns for _3S , H _3SS and row I ₃₂ to include the largest element in each of the V columns for rows H ₃ , H _3S , H _3SS .
Calculate ₃₃ .

Next, the first set of Y = X diagonal matrices
Calculate the vector. That is, in step 1710, the row J ₁₃ calculated to include the minimum element in each of the V-number of columns for row _{I 13, I 22, I 31} , row I _13,
The line J ₂₂ calculated to include a central element in each of the V-number of columns for I _22, I _31, line to include the maximum element in each of the V-number of columns for row I _13, I _22, I ₃₁ J ₃₁
Is calculated. Next, a second set of Y = X diagonal matrices
Calculate the vector. That is, in step 1720, the row J ₁₂ calculated to include the minimum element in each of the V-number of columns for row I _12, I _21, the maximum element in each of the V-number of columns for row I _12, I ₂₁ Line J _{21 to} include
Is calculated. Next, a third set of Y = X diagonal matrices
Compute the vector. That is, in step 1730, the row J ₂₃ calculated to include the minimum element in each of the V-number of columns for row I _23, I _32, the maximum element in each of the V-number of columns for row I _23, I ₃₂ row J ₃₂ so as to include
Is calculated.

Next, a first set of 2 ^* Y = X diagonal matrix vectors is calculated. That is, in step 1740, the line L ₁₃ calculated to include the minimum elements in each of the V column for the row J _13, J _21, the maximum element in each of the V-number of columns for row J _13, J ₂₁ Row L to include
Calculate ₂₁ . Next, a second set of 2 ^* Y = X diagonal matrix vectors is calculated. That is, in step 1750, the line L ₂₃ calculated to include the minimum elements in each of the V column for the row J _23, J _31, the maximum element in each of the V-number of columns for row J _23, J ₃₁ calculating the line L ₃₁ to contain.

By shifting the sum of the products of the weight matrix (K) and the corresponding sorted vectors by one position to the left, a vector of the obtained weighted filter values for the lower 3 × V matrix is calculated. That is, step 17
At 60, the result = K ₁₁ ^* (row) I ₁₁ + K ₁₂ ^* (row)
J ₁₂ + K ₁₃ ^* (row) L ₁₃ + K ₂₁ ^* (row) L ₂₁ + K
₂₂ ^* (row) J ₂₂ + K ₂₃ ^* (row) L ₂₃ + K ₃₁ ^* (row) L ₃₁
+ K ₃₂ ^* (line) J ₃₂ + K ₃₃ ^* (line) I ₃₃ . Finally, in step 1770, the row H ₁ vector Prev
Saved in _H _1, save the line H ₂ vector prev_h _2, saving the line H ₃ vector prev_h _3. Then
The method proceeds to step 740 and repeats the inner loop in FIG.

FIGS. 26 and 27 show the overall structure of FIG.
An example of the operation of the method shown in FIGS. Starting from the input rows A ₁ , A ₂ , A ₃ , A ₄ 1785, in step 1540, the rows B and C 1800 are calculated as the minimum and maximum values of the rows A ₂ and A ₃ . Row Prev_D ₁ ,
Prev_D ₂ , Prev_D ₃ 1780 can be obtained from the previous iteration of inner loop 590. Step 1550
, The rows D ₁ to D ₃ 1810 are calculated as the minimum, median, and maximum of the rows A ₁ , A ₂ , A ₃ . In step 1560, row D ₁ is shifted and saved as rows D _1S , D _1SS 1820 and rows E ₁₁ , E ₁₂ ,
E ₁₃ 1830 is used in calculating the minimum value, the median value, and the maximum value of the rows D ₁ , D _1S , and D _1SS 1820, respectively. In step 1570, row D ₂ is shifted and saved as rows D _2S , D _2SS 1840 and rows E ₂₁ ,
E ₂₂ and E ₂₃ 1850 are added to rows D ₂ , D _2S and D _2SS 1840
It is used when calculating as the minimum value, median value, and maximum value, respectively. In step 1580, row D ₃ is shifted, saved as rows D _3S , D _3SS 1860, and row E 3
₃₁ , E ₃₂ , and E ₃₃ 1870 are added to rows D ₃ , D _3S , and D _3SS 18
It is used when calculating the minimum value, median value, and maximum value of 60, respectively.

Next, the Y = X diagonal elements are sorted. In step 1590, the row _{F 13, F 22, F 31} 1880
Are calculated as the maximum value, the median value, and the maximum value of the rows E ₁₃ , E ₂₂ and E ₃₁ , respectively. In step 1600, row F
₁₂ and F ₂₁ 1890 are calculated as the minimum and maximum values of the rows E ₁₂ and E ₂₁ , respectively. In step 1610, the row F _23, F ₃₂ 1900, calculated respectively as minimum and maximum values of the row E _23, E _32. Following this, 2
^* Sort Y = X diagonal elements. In step 1620, the row G _13, G ₂₁ 1910, calculated respectively as minimum and maximum values of the row F _13, F _21. Step 16
30, rows G ₂₃ and G ₃₁ 1920 are replaced with rows F ₂₃ and F ₃₁
Is calculated as the minimum value and the maximum value, respectively. next,
At step 1640, the corresponding elements from the E, F, and G matrix rows are assigned weight matrix K1790.
Are calculated by adding the products multiplied by the corresponding entries in the above 3xV matrix. Finally, in step _{1650, D 1, D 2,} D 3 , line 1810
As the lines Prev_D ₁ , Prev_D ₂ , Prev_D ₃ ,
D ₁ , D ₂ , D ₃ rows 18 during the next loop iteration
Used when calculating the shift value for 10. Lower 3
The same applies to the calculation of the xV matrix. Row Prev_H ₁ , Prev
_H ₂ , Prev_H ₃ 1940 can be obtained from the immediately preceding iteration of inner loop 590. In step 1670, the rows H ₁ , H ₂ , and H ₃ 1950 are calculated as the minimum value, the median value, and the maximum value of the rows A ₂ , A ₃ , and A ₄ .
In step 1680, row H ₁ is shifted and saved as rows H _1S , H _1SS 1960, and rows I ₁₁ , I ₁₂ ,
I ₁₃ 1970 is used in calculating the minimum value, the median value, and the maximum value of the rows H ₁₁ , H ₁₂ , and H ₁₃ 1960, respectively. In step 1690, row H ₂ is shifted and saved as rows H _2S , H _2SS 1980 and row I ₂₁ ,
I ₂₂ and I ₂₃ 1990 are _{assigned to} rows H ₂ , H _2S and H _2SS 1980
It is used when calculating as the minimum value, median value, and maximum value, respectively. In step 1700, row H ₃ is shifted and saved as rows H _3S , H _3SS 2000 and row I 3
₃₁ , I ₃₂ , and I ₃₃ 2010 are used in calculating the minimum value, the median value, and the maximum value of the rows H ₃ , H _3S , and H _3SS , respectively.

Next, the Y = X diagonal elements are sorted. In step 1710, rows J ₁₃ , J ₂₂ , J ₃₁ 2020
Are calculated as the minimum value, the median value, and the maximum value of the rows I ₁₃ , I ₂₂ , and I ₃₁ , respectively. At step 1720, row J
₁₂ and J ₂₁ 2030 are calculated as the minimum value and the maximum value of the rows I ₁₂ and I ₂₁ , respectively. In step 1730, the rows J ₂₃ and J ₃₂ 2040 are calculated as the minimum and maximum values of the rows I ₂₃ and I ₃₂ , respectively. Following this, 2
^* Sort Y = X diagonal elements. In step 1740, the line L _13, L ₂₁ 2050, calculated respectively as minimum and maximum values of the row J _13, J _21. Step 17
At 50, rows L ₂₃ and L ₃₁ 2060 are replaced with rows J ₂₃ and J ₃₁
Is calculated as the minimum value and the maximum value, respectively. next,
In step 1760, the corresponding elements from the I, J, and L matrix rows are weighted K1790
To calculate the weighted filter vector 2070 for the resulting lower 3xV matrix. Finally, in step _{1770, H 1, H 2,} H 3 , line 1950
As the lines Prev_H ₁ , Prev_H ₂ , Prev_H ₃ ,
H _1, H ₂ during the next iteration of the loop, H ₃ rows 181
Used when calculating the shift value for 0.

Different permutations of the above-described methods will be apparent to those skilled in the art. The methods illustrated in the flowcharts of FIGS. 16, 19 and 20 and FIGS. 22-25 all result in a matrix with the rows sorted in descending order. These methods can reduce and simplify the number of ranks of the calculated elements by eliminating any unnecessary elements using standard optimization techniques. This is because all rank elements were calculated by the method of these figures. One of the results of this simplification
One is the method of calculating the median filter value disclosed above with reference to FIGS. 3, 6, and the flowcharts of FIGS.

FIG. 28 illustrates the use of the disclosed method for efficient calculation of median and weighted filter values for nine elements stored in 3x3, 4x3, 3xV, and 4xV matrices. FIG. 2 is a block diagram illustrating a possible general-purpose computer 20. The general-purpose computer 20 has a computer processor 22 and a memory 24 connected by a bus 26. Memory 24
Means DRAM, SRAM, ROM, FLASH, EEP
Includes relatively high speed machine readable media, such as ROM and bubble memory. The bus is connected to a secondary storage device 30, an external storage device 32, an output device such as a monitor 34, an input device such as a keyboard (with a mouse) 36, and a printer 38. Secondary storage 30 includes machine readable media such as hard disk drivers, magnetic drums, and bubble memory. The external storage device 32 includes a floppy disk, a removable hard drive, a magnetic tape,
It also includes a machine-readable medium such as a D-ROM, and other computers connectable through a communication line.
Here, the distinction provided between the secondary storage device 30 and the external storage device 32 is mainly for convenience in describing the present invention. Thus, it will be appreciated that there is considerable functional overlap between these components. 3x3,4x
An executable version of computer program 33, such as a program that implements the methods disclosed herein for calculating median and weighted filter values for nine elements stored in 3,3xV, and 4xV matrices, is: It can be read from the external storage device 32 and read directly into the memory 34 for execution, or it can be stored on the secondary storage device 30 before being loaded into the memory 34 for execution. The method disclosed here:
Conventional single instruction single data (SIS) as shown in FIG.
D) Using a processor to allow efficient calculation of median and weighted filter values for the nine elements stored in the 3x3, 4x3, 3xV, and 4xV matrices, which are single instruction Many data (SI
It is particularly useful when used with an MD) vector processor. One such SIMD processor that supports maximum and minimum vector operations is the "Data Processing Sys
Michael Gallup, et entitled "tem and Method Thereof"
al. in U.S. Patent No. 5,600,846. This patent is assigned to the assignee of the present application and can be used herein.

Those skilled in the art will recognize that changes and modifications may be made without departing from the spirit of the invention. Accordingly, the present invention is intended to embrace all such modifications and changes as fall within the scope of the appended claims.

[0054] Wherein, elements and steps in the claims are provided with a reference numeral and / or reference numeral, but only to aid readability and understanding. Accordingly, the use of reference numerals and / or reference signs in their own right is not intended to and should not be construed as indicating the order of the components and / or steps in the claims.

[Brief description of the drawings]

Fig. 1 Image scanner, digital camera, copier,
FIG. 2 illustrates a two-dimensional raster image as received by a laser printer, video monitor, and fax machine.

FIG. 2 shows a 3 × 3 matrix of pixels used to calculate a median or weighted rank filter.

FIG. 3 is a flowchart illustrating a method for determining the median of nine numerical values organized in a 3 × 3 matrix according to the present invention.

FIG. 4 is a diagram showing an example of obtaining a median of nine numerical values using the method shown in FIG. 3;

FIG. 5 shows a 4 × 3 matrix representing two overlapping 3 × 3 matrices.

FIG. 6 is a flow chart illustrating the optimization of the method of FIG. 3 according to the present invention, which allows the generation of a median for the two overlapping 3 × 3 matrices shown in FIG. 5;

FIG. 7 is a view showing an example of the operation of the method shown in FIG. 6;

FIG. 8 is a diagram showing a 4 × V matrix used to show optimization by vectorization of the method shown in FIG. 6;

FIG. 9 is a flow chart showing the optimization by vectorization of the method shown in FIG. 6 according to the present invention, in conjunction with FIGS. 10 and 11;

10 is a flow chart showing the optimization by vectorization of the method shown in FIG. 6, according to the present invention, in conjunction with FIGS. 9 and 11. FIG.

FIG. 11 is a flowchart showing the optimization by vectorization of the method shown in FIG. 6 according to the present invention, in conjunction with FIGS. 9 and 10;

FIG. 12 is a diagram showing an example of the operation of the method shown in FIGS. 10 and 11;

FIG. 13 is a diagram of a 3 × 3 matrix to show how to completely sort nine numerical values.

FIG. 14 is a diagram of a 3 × 3 coefficient matrix for illustrating a weighted filtering process using nine sorted numerical values.

FIG. 15 is a diagram of four 3 × 3 matrices illustrating the operation of a method for completely sorting nine numbers organized in a 3 × 3 matrix.

FIG. 16 is a flowchart illustrating a method of completely sorting nine numbers and then calculating a weighted filter value of the nine numbers organized in a 3 × 3 matrix according to the present invention.

FIG. 17 is a diagram showing an example of the operation of the method shown in FIG. 16;

FIG. 18 is a diagram of a 4 × 3 matrix representing two overlapping 3 × 3 matrices.

FIG. 19 is a flowchart, together with FIG. 20, illustrating the optimization of the method shown in FIG. 16 to enable the generation of weighted filter values for two overlapping 3 × 3 matrices combined into the 4 × 3 matrix shown in FIG. 18 in accordance with the present invention. .

FIG. 20 is a flowchart, along with FIG. 19, of an optimization of the method shown in FIG. 16 to enable the generation of weighted filter values for two overlapping 3 × 3 matrices combined into the 4 × 3 matrix shown in FIG. 18 in accordance with the present invention. .

FIG. 21 is a diagram showing an example of the operation of the method shown in FIGS. 19 and 20.

FIG. 22: Complete 4 × V sort and 2 according to the invention
The vector operation for calculating the weighted filter value of xV is shown in FIG.
26 is a flowchart shown together with FIG.

FIG. 23 illustrates a vector operation of a 4 × V perfect sort and calculation of a 2 × V weighted filter value according to the present invention.
2, a flowchart shown together with FIGS. 24 and 25.

FIG. 24 shows a vector operation of a 4 × V perfect sort and calculation of a 2 × V weighted filter value according to the present invention.
2, a flowchart shown together with FIG. 23 and FIG. 25.

FIG. 25 illustrates a vector operation of a 4 × V perfect sort and calculation of a 2 × V weighted filter value according to the present invention.
25 is a flowchart shown together with FIG.

FIG. 26 is a diagram showing an example of the operation of the method shown in FIGS. 22 and 23 together with FIG. 27;

FIG. 27 is a view showing an example of the operation of the method shown in FIGS. 22 and 23 together with FIG. 26;

FIG. 28 is a block diagram illustrating a general-purpose computer that can be used to implement the methods disclosed herein.

[Explanation of symbols]

 Reference Signs List 20 general-purpose computer 22 computer processor 24 memory 26 bus 30 secondary storage device 32 external storage device 33 computer program 34 monitor 36 keyboard 100 two-dimensional matrix 110 3x3 matrix 200 3x3 grid 220 vector 230 median 310 4x3 matrix 450 4x3 matrix 470 First 3x3 intermediate matrix 480 First intermediate vector (M) 490 First median 500 Second 3x3 intermediate matrix 510 Second intermediate vector (N) 520 Second median 530 4xV matrix

[Procedure amendment]

[Submission date] September 24, 1998

[Procedure amendment 1]

[Document name to be amended] Drawing

[Correction target item name] FIG.

[Correction method] Change

[Correction contents]

FIG. 24

Claims (5)

[Claims] 1. A method for calculating a central filter value for a plurality of elements arranged in a 3 × 3 grid (110) stored in a memory (24), said 3 × 3 grid (110) comprising three The 3x3 grid (110) has three columns, i.e., first, second, and third columns, and has three rows, i.e., first, second, and third rows. The method includes: calculating a minimum middle row using three columns, and calculating each element in the minimum middle row to be equal to a minimum element in a corresponding column (130); using the three columns To calculate the middle middle row, and replace each element in the middle middle row by
Calculating 130 to be equal to the central element in the corresponding column; calculating the largest middle row using the three columns;
Calculating each element in the largest middle row to be equal to the largest element in the corresponding column (130); calculating a largest value from a set of entries consisting of the smallest middle row to obtain a largest middle value Calculating the median value by calculating the median value from the set of entries consisting of the median row (140);
0); calculating a minimum intermediate value by calculating a minimum value from a set of entries consisting of the maximum intermediate row (160); and the maximum intermediate value, the minimum intermediate value,
And calculating the median filter value by calculating a median value from the set of median median values (170). 2. An initial minimum row is calculated using three columns, and each element in the initial minimum row is represented by a corresponding column from one of a set of rows including the first row and the second row. Calculating to be equal to the smallest element in; calculating a first initial center row using the three columns, each element in the first initial center row including the first row and the second row. Calculating to be equal to the largest element in the corresponding column from one of the set of rows; and calculating a second initial center row using the three columns, and replacing each element in the second initial center row. Calculating to be equal to a minimum element in a corresponding column from one of a set of rows including the first initial center row and the third row; and calculating the minimum middle row. : In a set of rows consisting of the second initial center row and the initial minimum row Calculating the minimum entry in each column of the set; calculating the middle intermediate row: determining the largest entry in each column in the set of the second initial center row and the initial minimum row. Calculating the largest intermediate row includes: calculating a largest entry in each column in the set of rows consisting of the first initial center row and the third row. The method of claim 1, wherein: 3. An initial maximum row is calculated using three columns, and each element in the initial maximum row is calculated in a corresponding column from one of a set of rows including the first row and the second row. Calculating to be equal to the largest element; first using three columns
Calculate the initial center row and replace each element in the first initial center row with
Calculating to be equal to the smallest element in a corresponding column from one of the set of rows including the first row and the second row; and calculating a second initial center row using the three columns Calculating each element in the second initial center row to be equal to the largest element in a corresponding column from one of the set of rows comprising the first initial center row and the third row; Calculating the minimum middle row includes: calculating a minimum entry in each column in the set of rows consisting of the first initial center row and the third row; Calculating comprises: calculating a minimum entry in each column in the set of rows comprising the second initial center row and the initial maximum row; calculating the maximum center row comprises: the second initial center. Row and the initial maximum row The method of claim 1, comprising calculating a maximum entry in each column in the set of rows. 4. A method for calculating an upper central filter value and a lower central filter value for a plurality of elements arranged in two overlapping 3 × 3 grids (310) stored in a memory (24). T: the two overlapping 3x3
Each of the grids (310) has three rows, each of the two overlapping 3x3 grids (310) has three columns, and a first shared row and a second shared row are the two overlapping 3x3 grids. (310), wherein the upper grid of the two overlapping 3x3 grids (310) has unshared rows on the upper side and the lower grid of the two overlapping 3x3 grids (310) is , Having a non-shared row below, the method comprising: A) calculating a shared minimum row using three columns, and replacing each element in the shared minimum row with the first shared row and the second shared row. (330) calculating to be equal to the smallest element in the corresponding column in the set of rows consisting of: B) calculating a shared maximum row using the three columns; First shared line and before Calculating to be equal to the largest element in the corresponding column in said set of rows consisting of said second shared row (330); C) calculating an upper minimum intermediate row using the three columns; Calculating each element in the middle row to be equal to the smallest element in the corresponding column in the set of rows consisting of the shared minimum row and the upper unshared row (34).
0); D) Calculate the upper middle middle row using the three columns, and replace each element in the upper middle middle row with 1 consisting of the upper unshared row, the first shared row, and the second shared row. Calculating to be equal to the central element in the corresponding column in the set of rows (340); E) calculating an upper maximum middle row using the three columns, and each element in the upper maximum middle row is shared. Calculating to be equal to the largest element in the corresponding column in the set of rows comprising the largest row and said upper unshared row (34)
0); F) calculating an upper maximum intermediate value by calculating a maximum value from a set of elements constituting the upper minimum intermediate row (350); G) forming 1 the upper central intermediate row 1 Calculating an upper median value by calculating a median value from the elements of the set (360); H) calculating a minimum value from a set of elements constituting the upper maximum intermediate row; Calculating a minimum median value (370); I) calculating the median value from a set of elements consisting of the upper maximum median value, the upper minimum median value, and the upper median median value; Calculating a value (380); J) calculating a lower minimum middle row using the three columns, each element in the lower minimum middle row consisting of the shared minimum row and the lower non-shared row. Correspondence within a set of rows Step of calculating to be equal to the smallest element in that column (39
0); K) Calculate the lower middle middle row using the three columns and replace each element in the lower middle middle row with the lower unshared row, the first shared row, and the second shared row. Calculating (390) to be equal to the median element in the corresponding column in the set of rows consisting of: L) calculating the lowermost middle row using the three columns; Calculating an element to be equal to the largest element in the corresponding column in the set of rows consisting of the shared largest row and the lower unshared row (39).
0); M) calculating a lower maximum intermediate value by calculating a maximum value from a set of elements constituting the lower minimum intermediate line (400); N) calculating the lower central intermediate line. Calculating the lower median value by calculating the median value from the set of constituent elements (410); O) calculating the minimum value from the set of elements forming the lower largest intermediate row; Computing a lower minimum median value (420); and P) calculating a median value from a set of elements consisting of the lower maximum median value, the lower minimum median value, and the lower median value. Calculating a lower center filter value by calculating the value (430). 5. A complete sorting of a plurality of elements arranged in two overlapping 3 × 3 grids (1200) stored in a memory (24) so that an upper sorting matrix and a lower sorting matrix are sorted. A method of generating: each of the two overlapping 3x3 grids (1200) has three rows; each of the two overlapping 3x3 grids (1200) has three columns; A row and a second shared row are shared by each of the two overlapping 3x3 grids (1200); an upper grid of the two overlapping 3x3 grids (1200) has an unshared row on an upper side; and the two overlapping 3x3 grids (1200) The lower grid has unshared rows on the lower side, the method comprising: A) calculating a shared minimum row using three columns, and each element in the shared minimum row; Calculating (1220) to be equal to the smallest element in the corresponding column in the set of rows consisting of the first shared row and the second shared row (1220); B) calculating the largest shared row using the three columns Calculating each element in the largest shared row to be equal to the largest element in a corresponding column in the set of rows consisting of the first shared row and the second shared row (1220); C) Calculate the upper minimum intermediate row using three columns, and make each element in the upper minimum intermediate row equal to the minimum element in the corresponding column in the set of rows consisting of the shared minimum row and the upper unshared row. D) calculating the upper middle middle row using the three columns, and replacing each element in the upper middle middle row with the upper non-shared row, the first middle row.
Calculating (1230) equal to the central element in a corresponding row in the set of rows comprising the shared row and said second shared row (1230); E) calculating the uppermost middle row using the three columns; Calculating each element in the uppermost middle row to be equal to the largest element in a corresponding column in the set of rows consisting of the shared largest row and the upper unshared row (1230); F) three columns , And calculate each element in the lower minimum middle row to be equal to the largest element in the corresponding column in the set of rows consisting of the shared minimum row and the lower unshared row. G) Calculate the lower middle middle row using three columns, and replace each element in the lower middle middle row with the lower non-shared row, the first middle row.
Calculating (1310) equal to the central element in a corresponding row in the set of shared rows and said second shared row in the set of rows (1310); H) calculating a lower maximum middle row using the three columns; Calculating each element in the lower largest intermediate row to be equal to the largest element in a corresponding column in a set of rows consisting of the shared largest row and the lower unshared row (1310); I). For each of the three columns, sort each element in each column of a first upper sort matrix consisting of the upper middle intermediate row, the upper middle middle row, and the upper minimum middle row, and a second upper sort Forming a matrix (1240); J) for each of the three columns, a first lower sort comprising the lower largest middle row, the lower middle middle row, and the lower smallest middle row.・ Matrix Sorting each element in each column to form a second lower sort matrix (1320); K) in the second upper sort matrix, each being located on a line parallel to a first diagonal passing through the origin. Sorting a plurality of elements to form a third upper sort matrix (1250, 1260, 1270); L) in the second lower sort matrix, each on a line parallel to a second diagonal passing through the origin. Sorting the located plurality of elements to form a third lower sort matrix (1330, 1340, 1350); M) in the third upper sort matrix, on a line parallel to a third diagonal passing through the origin. N) before sorting a plurality of elements, each located at, thereby forming an upper sort matrix (1280, 290); and N) In the third lower sort matrix, sorting a plurality of elements each located on a line parallel to the fourth diagonal passing through the origin, thereby forming a lower sort matrix (1360, 1370); A method characterized by comprising: