BACKGROUND OF THE INVENTION Field of Invention

[0001] The present invention relates to amethod and apparatus of image processing to detect and enhance edges and to reduce noise in medical imaging, e.g. ultrasound imaging, X-ray, MRI, CT. Specifically, the method and apparatus of the present invention relates to the detection of edges in noisy images and enhancement of such edges.

Description of Related Art

[0002] An object, such as an organ, in an image has borders or edges and image processing can detect these borders or edges. Detection of edges is usually performed with filters 11 as shown in Figures Ia-Ic. However, it is difficult to detect edges in an image with noise (or poor signal to noise ratio) . Edges of noise patterns can be erroneously detected as "edges" rather than the true edges of an object or organ for example. Therefore, a low-pass filter is usually applied to the image before the edge detection in order to reduce noise and to detect the true edges reliably. Alow-pass filtercanbe 3x3, 5x5 or 7x7 ormore insize. Such filters are known in the art and examples are illustrated in FIGS. 2a-2c. After the low-pass filter is applied, edge detection is performed using, for example, the filter shown in Figure Ia. The low-pass filter smoothes the image and reduces noise. However, low-pass filter masks override each other when the filter in Figure Ia is used, resulting in somewhat fuzzy edges as well as spatial errors with respect to the true edges of the original image. What is therefore needed is a method to detect true edges in images containing noise which does not result in the production of fuzzy edges or spatial errors.

SUMMARY OF THE INVENTION

[0003] Accordingly, it is an object of the present invention to provide a method and apparatus of image processing to detect and enhance edges and to reduce noise in medical imaging, e.g. ultrasound imaging, X-ray, MRI, CT. Specifically, the method and apparatus of thepresent invention relates to the detectionof edges

in noisy images and enhancement of such edges.

[0004] In accordance with the present invention, an edge detection filter comprises an array of filter coefficients having an odd number of rows and columns, a first set of zero coefficients extending along a direction traversing the array through a center position to form a first and second side, a second set of positive coefficients extending away from the direction on the first side, and a third set of negative coefficients extending away from the direction on the second side.

[0005] In accordance with the present invention, a method for detecting edges in an image comprises the steps of applying a horizontal edge detection filter to the image to produce a horizontal edge detection result, applying a vertical edge detection filter to the image to produce a vertical edge detection result, and combining the horizontal edge detection result and the vertical edge detection result to detect an edge.

[0006] In accordance with the present invention, a method for applying an edge detection filter to an image comprises the steps of a. providing an image comprised of rows and columns, b. providing anedge detection filter comprising anarrayof filter coefficients having an odd number of rows and columns, a first set of zero coefficients extending along a direction traversing the array through a center position to form a first and second side, a second set of coefficients, equal to 1 extending away from the direction on the first side, and a third set of coefficients equal to -1 extending away fromthe directionon the second side, c. positioning the edge detection filter to a position at a first direction origin and a second direction origin of the image, d. applying the edge detection filterto the image tocalculate apluralityof rowvalues, e. storing each of the plurality of rowvalues in a memory location, f. summing each of the plurality of memory locations to produce a filter output, g. shifting the contents of the plurality of memory locations, h. incrementing the position of the edge detection filter in a first direction; i. repeating steps d through h until a boundary of the image is reached, j . incrementing the position of the edge detection filter in a second direction and resetting

the position to the first direction origin of the image, and h. repeating steps d throughj until aboundaryof the image is reached.

[0007] In accordance with the present invention, an edge detection filter comprises an array of filter coefficients having an odd number of rows and columns, a first set of zero coefficients extending along a direction traversing the array through a center position to form a first and second side, a second set of positive coefficients extending away from the direction on the first side wherein each of the second set of positive coefficients is the product of two predefined coefficients, and a third set of negative coefficients extending away from the direction on the second side whereineachof the thirdset ofnegative coefficients is theproduct of two predefined coefficients.

[0008] In accordance with the present invention, an apparatus for performing edge detection comprises an image comprised of rows and columns, an edge detection filter comprising an array of filter coefficients having an odd number of rows and columns, a first set of zero coefficients extending along a direction traversing the array through a center position to form a first and second side, a second set of coefficients equal to 1 extending away from the direction on the first side, and a third set of coefficients equal to -1 extending away from the direction on the second side, means for applying the edge detection filter to the image to calculate a plurality of row values, means for storing each of the plurality of row values in a memory location, means for summing each of the plurality of memory locations to produce a filter output, andmeans for shifting the contents of the plurality of memory locations.

[0009] In accordance with the present invention, a method for applying an edge detection filter to an image comprises the steps of a. providing an image comprisedof rows and columns, b. providing an edge detection filter comprising an arrayof filter coefficients having an odd number of rows and columns, a first set of zero coefficients extending along a direction traversing the array through a center position to form a first and second side, a second set of coefficients equal to 1 extending away from the direction on the first side, and a third set of coefficients equal to -1

extendingaway fromthedirectionon the second side, c. positioning the edge detection filter to a position at a first direction origin and a second direction origin of the image, d. applying the edge detection filterto the image tocalculate apluralityof rowvalues, e. storing each of the plurality of row values in one of a plurality of memory locations, f. summing each of the plurality of memory locations to produce a filter output and store the filter output in a memory storage device, g. incrementing the position of the edge detection filter in a first direction, h. shifting the contents of the plurality of memory locations to add a new row and create an old row, i. summing a plurality of values comprising the new row to produce a new row value, j . calculating a new filter output by adding the new row value and subtracting an old row value from the filter output, k. storing the new filter output in the memory storage device, 1. repeating steps g through k until a boundary of the image is reached, m. incrementing the position of the edge detection filter in a second direction and resetting the position to the first direction origin of the image, and n. repeating steps d through m until a boundary of the image is reached.

[0010] Accordingly, it is an object of the present invention to provide a method for applying an edge detection filter to an image comprises the steps of a. providing an image comprised of rows and columns, b. providing an edge detection filter comprising an array of filter coefficients having an odd number of rows and columns, a first set of zero coefficients extending along a direction traversing the array through a center position to form a first and second side, a second set of coefficients equal to 1 extending away from the direction on the first side, and a third set of coefficients equal to -1 extending away from the direction on the second side, c. positioning the edge detection filter to aposition at a first direction origin and a second direction origin of the image, d. applying the edge detection filter to the image to calculate a plurality of row values of R _x ,j, e. storing each of the plurality of row values of R _X/J in one of a plurality of memory locations, f. summing each of the plurality of memory locations to produce a filter output of R _x and store the filter output of R _x in a memory storage device, g. incrementing the position of the edge detection filter ina first direction, h. shifting the contents

of the plurality of memory locations to add a new row and create an old row, i. summing a plurality of values comprising the new row to produce a new row value of Rχ,2N ₊ i» j • calculating a filter output for anew filterpositionbyadding together the filteroutput of R _x from a previous filter position and a value of R _x , ₀ , subtracting a value of R _X/N and a value of Rχ,N+i/ and adding a value of Rχ,2N ₊ i# k. storing said new filter output in said memory storage device, 1. repeating steps g through k until a boundary of the image is reached, m. incrementing the position of the edge detection filter in a second direction and resetting the position to the first direction origin of the image, and n. repeating steps d through m until a boundary of the image is reached.

[0011] In accordance with the present invention, a method for applying an edge detection filter to an image comprises the steps of a. providing an image comprised of rows and columns, b. providing an edge detection filter comprising an array of filter coefficients having an odd number of rows and columns, a first set of zero coefficients extending along a direction traversing the array through a center position to form a first and second side, a second set of coefficients equal to 1 extending away from the direction on the first side, and a third set of coefficients equal to -1 extending away fromthe direction on the second side, c. positioning the edge detection filter to a position at a first direction origin and a second direction origin of the image, d. applying the edge detection filter to the image to calculate a plurality of column values of Rγ,i, e. storing each of the plurality of column values of R γ,i in one of a plurality of memory locations, f . summing each of the plurality of memory locations to produce a filter output of Ry and store the filter output of R _γ in a memory storage device, g. incrementing the position of the edge detection filter in a first direction, h. shifting the contents of the plurality of memory locations to add a new column and create an old column, i. summing a plurality of values comprising the new column to produce a new column value of R ^' _Y , _2M+I , j- calculating a filter output for a new filter position by adding together a filter output of R _γ from a previous filter position and a value of Rγ,o, subtracting a value of Rγ,M and a value of Rγ,M+i/ and adding a value of Rγ, ₂ M+i, k. storing said filter output in saidmemory storage device, 1. repeating steps

g through kuntil a boundary of the image is reached, m. incrementing the position of the edge detection filter in a second direction and resetting the position to the first direction origin of the image, and n. repeating steps d through m until a boundary of the image is reached.

BRIEF DESCRIPTION OF THE DRAWINGS

[0012] Figures l(a-c) Prior art edge detection filters

[0013] Figures 2(a-c) Prior art smoothing filters

[0014] Figure 3a A 1x3 edge detection filter common in the art

[0015] Figure 3b A 5x5 low pass filter known in the art

[0016] Figure 3c The result of combining the -1 edge filter coefficient with the 5x5 low-pass filter

[0017] Figure 3d The result of combining the 1 edge filter coefficient with the 5x5 low-pass filter

[0018] Figure 3e The resulting combination of the results of Figures 3c and 3d

[0019] Figure 4 The improved edge detection filter of the present invention

[0020] Figures 5(a-h) Edge detection filters of various directions of the present invention

[0021] Figures 6 (a-b) Edge detection filters of horizontal and vertical directions showing the more general form wherein a coefficient

"a" is employed

[0022] Figures 7 (a-b) Edge detection filters of horizontal and vertical directions using more general form using aij

[0023] Figures 8 (a-b) Edge detection filters of horizontal and vertical directions using more general form using more general form using bibj

[0024] Figure 9a Flow chart of vertical edge detection using (-1,0,1)

[0025] Figure 9b Flow chart of horizontal edge detection using (-1,0,1)

[0026] Figure 10a Flow chart of horizontal edge detection using -a, o,a

[0027] Figure 10b Flow chart of vertical edge detection using -a, 0, a

[0028] Figure 11 Diagram of the relationship between old and new filter positions

[0029] Figure 12 Illustration of the movement of the filter of the present invention

[0030] Figure 13 Block diagram of the vertical edge filter hardware of the present invention

[0031] Figure 14 Diagram of an efficient vertical edge detection filter

[0032] Figure 15 Diagram of the horizontal edge filter hardware of the present invention

[0033] Figure 16 Diagram of an efficient horizontal edge detection filter

[0034] Figure 17 Diagram of the horizontal edge detection filter with filter coefficients bi

[0035] Figure 18 Diagram of the vertical edge detection filter with filter coefficients bi

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT(S) [0036] Edges'of an object or organ have directions. Therefore, edge detection needs to be performed in directions. With reference to FIG. 5a-5h, there is illustrated edge detection filters in 8 directions (-45°, 45°, 67.5°, 22.5°, -67.5°, -22.5°, 0°, 90°, respectively) of the present invention. Each filter is implemented so as to produce the effect of low-pass filtering as the size of each filter is large and is capable of detecting edges reliably with a better signal to noise ratio than that of the prior art.

Yet, unlike the edge detection filter after low-pass filtering of the prior art, the present invention applies the operation of differentiation to image pixels which are not overriding each other. To illustrate this problemof the preprocessing of a low-pass filter, a 1x3 edge detection filter 31 of the horizontal direction, which is a part (or column) of the filter 11 in Figure la, is shown in Figure 3a. Using three columns of the filter 11 yields an effect of averaging and a higher signal to noise ratio of detecting edges. However, for simplicity, the edge detection filter 31 in Figure 3a is used to illustrate the overriding problem. Figure 3b shows a 5x5 low-pass filter 33 which is applied to an image before the edge detection filter 31. Figure 3c shows the combination of the edge filter's 31 coefficient -1 and the low-pass filter 33 while Figure 3d shows the combination of the edge filter' s 31 coefficient 1 and the low-pass filter 33. The filter's 31 coefficient 0 has no effects or no output. Figure 3e shows the overall effect of the edge filter 31 and the low-pass filter 33 on the original image. The center three rows are overridden and the filter coefficients cancel each other and become 0. The center three rows of zero act like an edge detection filter of a spatial resolution of approximately 3 times worse than the original filter of a 1x3 filter having only one row of zeros. Therefore, the detected edge will be fuzzy. To maintain the spatial resolution (sharpness) and registration (position) of the edge, the row of coefficients 0 should be as narrow as possible. Three rows of zeros are two rows too many for coefficients of 0. An improved edge detection filter is shown for the same size array (7x5) in Figure 4. This improved filter 15 is more accurate in detecting the position of the edge than is that of Figure 3e and yet has better signal-to-noise ratio (SNR) in detecting the edge as it has a feature of low-pass filtering in the upper and lower areas surrounding the row of 0. Usually, an edge detection filter is applied to an image with the result of the filter operation assigned to a pixel representing the center of the edge detection filter. Typically, when the edge detection filter is centered on an edge, the value of the center pixel is of a large relative magnitude.

[0037] Referring to Figures 5a-5h, eight edge detection filters of the present invention are shown to illustrate the main

concept of the filterof thepresent invention. Thenumberof filters or directions canbe extended to twenty or more with eight exemplary- filters shown in Figure 5. Twenty filters can be designed with a step of approximately nine degrees in direction. As shown in Figure 5, the filters 51 have coefficients at the intersection of each row and column of an integer value, usually 1, -1 or 0, to provide for quick calculation. Coefficients of 1, -1 or 0 do not require multiplication but, rather, can be applied to an image using only addition and subtraction. However, filter coefficients are not necessarily restricted to integers but can be extended to decimal values (or floating-point numbers) . Filter coefficients of all these filters 51 are symmetrical except the sign (i.e., plus or minus) either vertically, horizontally or in the direction of the edge that the filter is designed to detect. The center positions are all 0. For example, filter coefficients of the center row are all 0 forahorizontal edgedetecting filteras illustratedinFigure 5g. Filter coefficients of the center columnare all 0 foravertical edge detecting filter as shown in Figure 5h. Note that, with the exception of directions of 0°, 90°, 45°, and -45°, the zero coefficients of the edge detection filter 31 are located in the row and column positions aligned with detection direction 57.

[0038] Edge detection filters with many directions are ideal for detecting edges with great accuracy and sensitivity for the directions but somewhat limited for real-time implementation. Each filter requires many calculations for a given image and the number of overall calculations increase with the number of filters. Therefore, an alternative embodiment of the present invention uses only 2 filters of the vertical and horizontal directions. Edges of otherdirections are detectedusing a filter size (2M+1) x (2N+1) as follows

⁾

[0039] M and N are integers and can be equal to each other. Zi, _j is the image value to which the filter is applied at a point (i,j) . R _x and R _γ are the filter outputs. The direction of the edge is determined by

The magnitude or strength of the edge is determined by

[0040] The magnitude of the combined horizontal (R _x ) and vertical (R _y ) edge detection results is indicative of the presence of an edge.

[0041] The use of these 2 edge filters alone speed up the processing by a factor of 10 compared with the use of 20 filters. Furthermore, the use of these 2 edge detection filters makes it possible to further speed up the processing by reducing the number of identical calculations performed at different filter positions. For a filter mask size of about 11x11, this increase in speed can be as much as 10 times as described in the following sections. Therefore, combined with the decrease in the number of filters, the overall increase in the speed can be as much as 100 times. This makes real-time implementation of image processing possible.

[0042] One method employed by the present invention to speed up the calculations required to apply one or more edge filters of the present invention involves iteration. A general form of the edge filter can be expressed by

where, i: x-coordinate, j ; y-coordinate in the filter mask, and M, N are integers, R is the filter output and, W _y are the

filter coefficients at (i,j) while z.. are image values at (i,j) .

[0043] For the horizontal edge f ilter ( 0 degrees or χ-direction) shown in Figure 5g , the f ilter can be expressed as follows ,

And this can be further expressed for each row as follows ,

)

Then the result of each row calculation is summed as follows,

where the center row (j=N+l) coefficient is 0.

[0044] In order to speed up the filter calculation for the whole image area 10 of many filter positions 13, 13 ' as illustrated in Figure 12. Once the filter 15 at the first positionwas calculated, the filter at the next position (as the filter moves one row down) is efficiently calculated by shifting the content of memories by one and calculating only the newest row. This is schematically illustrated in Figure 11. The memory contents are shifted as follows,

[0045] Finally, the newest row is calculated as follows,

Then these terms or the contents of the memories are summed as follows,

[0046] This efficient filter calculation is illustrated in the flow chart shown in Figure 9b. The calculation is illustrated using a horizontal edge detection filter such as one illustrated in Figure 5g. As is illustrated, the methodof performing edge detectionusing the horizontal edge filter consisting of coefficients -1, 0 and 1 begins at the starting column 1, row 1 of an image. First, there is calculated the first row by adding all of the columns in the image corresponding to the columns in the edge detection filter and storing the results in memory #1. Then, the next row j is calculated by adding all corresponding columns in the edge detection filter and storing the result in memory #j . This is repeated until the (2N+l) ^th row is calculated. Once j=2N+l, the memory contents are added or subtracted as necessary depending on the sign of the filter coefficients and the results are summed from memories #1 through #2N+1. The result of this calculation is outputted as the filter output. Next, the memories are shifted as illustrated and described with reference to Figure 11. Returning to Figure 9b, the edge detection filter is then moved downwards on the image by one row. A check is then performed to make sure that the edge detection filter is not out of the image row range of the image. If it is, the filter is moved over by one column and the process is begun once again at the new column and at row 1. In addition, a check is performed to make sure that the edge detection filter is not out of image columns. If this is the case, processing ends. If, the edge detection filter is not out of image rows, the newest row 2N+1 is calculated and the results stored in memory #2N+1. Once again the memory contents of memories #1 through

2N+1 are added or subtracted depending on the sign of the filter coefficients to obtain the filter output result. Electronic circuits shown in Figure 15 efficiently calculate this horizontal edge filter. Image pixel data are read out from image memory and fed to memory #2M+1 and shifted to memory #2M, .. #1. All pixel data forming the image in the same row are summed at the summer 1501 and the summer' s 1501 output is fed to memory #2N+1 and shifted to #N+2, ... #1. The contents of memory #2N+1 to #N+2 are added while the contents of memory #N to #1 are subtracted at the summer in order to calculate the filter output. While illustrated with reference to advancing an edge detection filter vertically from the top to the bottom of an image by single units, then advancing from left to right one unit at a time and repeating the process, the present invention is not so limited. Rather the present invention is drawn broadly to moving in two orthogonal directions, preferably top to bottom, and left to right.

[0047] This can be extended to a more general form of the edge filter of coefficients as shown in Figures 6a-b. "a" can be an integer or floating-point of positive or negative value. A similar efficient filter operation is described in the following section.

[0048] For the horizontal edge direction, after calculating the rows as if all the coefficients are 1, the row results are multiplied by the coefficient of a. Multiplying each row result is more efficient than multiplying each pixel data.

[0049] Once the filter was calculated for the first position, the content of the memories are shifted by one and only the newest row is calculated as the filter moves one row down.

[0050] Only the newest row is calculated as follows

[0051] Then sum these terms as follows:

where a can be 1, -1 or another value.

[0052] This efficient calculation is illustrated by the flowchart shown in Figure 10a.

[0053] The similar iteration technique can be used to calculate R efficiently for a more general filter using α _y .

[0054] This can be ef f iciently calculated as follows

[0055] Once the filter in the first position was calculated, we can only shift the content of memories by one and calculate the newest row as the filter moves orie row down.

[0056] Only the newest row is calculated as follows

[0057] Then sum these terms .

[0058] The filter moves down and the calculation continues until the filter position goes out of the image row or the image boundary. The filter position then moves to the first row of the next column position and continues the same operation.

[0059] For vertical edges, the filter in Figure 5h can be expressed by

[0060] This calculation can be efficiently executed by an iteration technique as described before.

( 3 9 )

[0061] Once the filter in the first position is calculated, the filter in the next position can be calculated by only shifting the contents of memories and calculating only the newest row as follows,

^ and only the newest row is calculated as follows,

[0062] This operation is depicted in Figure 11. Furthermore, the flowchart in Figure 9a describes the iteration method at many positions in the whole image area. The method illustrated in Figure 9a is quite similar to that illustrated above with reference to Figure 9b. The primary difference arises from slightly different calculations regarding the arrangement of the vertical edge filter coefficients -1, 0, 1. It should be emphasized at this point that the present invention is directed to the use of horizontal and vertical edge filters of any size having an arrangement of coefficients such as is illustrated with reference to Figures 5g and 5h. It would be evident to one skilled in the art to expand

the application of any horizontal or vertical edge filter configured as are those defined by the present invention using the same methodology outlined herein. Returning to Figure 9a, the vertical edge filter is applied at column 1, row 1 to the image. There is then calculated the first row through summation by adding or subtracting image pixel values, depending on the filter coefficient values, i.e., -1, Oorl, and further storing the result of the summation in memory #1. Next, there is calculated row j through summation by adding or subtracting image pixel values, depending on the filter coefficient values, i.e., -1, 0 or 1, and further storing the results in memory j . There is then, as before with reference to Figure 9b, performed a check to see if the (2N+1) th row has been calculated. If not, the next row j is calculated and continues to be calculated in an interactive fashion until the

(2N+l)th row is calculated. When j=2N+l, all of the memories are summed from memory #1 to memory #2N+1. The resulting summation results in the filter output. The memories are then shifted as described above with reference to the horizontal edge filter. The filter is moved by one row, a check is performed to see if the filter is out of the image row, and if not, the newest row 2N+1 is calculated through summation by adding or subtracting image pixel values, depending on the filter coefficient values, i.e., -1, O or l, and storing the results in memory #2N+1. Figure 13 illustrates electronic circuits to efficiently calculate this vertical edge filter. All pixels (image) data in the same row are read out from image memory and fed to memory #2M+1 and shifted to memory #2M, ... and #1. The pixel data in the same row are summed or subtracted at the summer. All pixels data of the next row are read out and summed at the summer in the same fashion. This operation continues until the last row of the filter for one filter position. The output

(result) of the summer is fed to memory #2N+1 and shifted to memory #2N, ... and #1. The contents of the memory #2N+1 to 1 are summed to calculate the filter output.

[0063] The filter is moved down by one row position and the filter calculation continues until the filter goes out of the image row or boundary.

[0064] The filter is not limited to -1,0,1 coefficients and

an take a general form using a, or aj as

a can be also 1 or -1 or other values. This can be efficiently- calculated using the iteration technique as described before. The first row to 2N+1 row in the filter mask are calculated as follows,

^ ^{4 8} )

[0065] As the filter is moved down by one row and the iteration operation can be used as follows.

and only the newest row is calculated as follows,

Using a _t

_

I=M 1=2 M +1

^R r,ι = ^" ∑ ^a ι ^z υ ⁺ ∑ ^α 2A/ ₊₂ -, ^z ,M ( ⁵⁵ )

1=1 i=W +2

[0066] As the filter is moved downby one row and the iteration operation can be used as follows.

22NΛ/++1l ( 61 ) and only the newest row is calculated as follows,

-

[0067] Other forms of iteration can be also used to speed up the filter calculation in the whole image area. For example, for the vertical edges, after calculating the filter result inthe first position, the next row position can be calculated by adding the new row to the result of the first position and subtracting the last row in the first position. The vertical edge filter is calculated as follows,

[0068] This result R _γ is stored in memory.

The calculation result of each row expressed below is also stored in memory #1 to #2N+1.

[0069] Next, the filter moves down by one row and the filter of the new position can be calculated as described below. First, the contents of the memories are shifted as follow,

where<- sign indicates storing the right hand term into the left hand term, also R _γo indicates the first row result of the previous

position. in the last operation indicates the newest

calculation result for the newest row. This calculation of the newest row is actually carried out. However, the summing operation requires only one addition and one subtraction of the row results rather than 2N+1 additions of the previous iteration method. The R _γ value from the previous position and stored in the memory is used and updated by the summing operation and stored in

the memory again. This iteration technique can be extended to filter coefficients of a or a _j just like before. This operation of adding the newest row and subtracting the oldest row is best illustrated in Figure 11.

[0070] Figure 14 illustrates electronic circuits comprising memory locations, accumulators, summers, and the like, to efficiently calculate this vertical edge filter. While diagrammed with reference to such physical circuit components, it is recognized that the operations of the present invention can be performed in whole, or in part, by a digital signal processor (DSP) . All pixels (image) data in the same row are read out from image memory and fed to memory #2M+1 and shifted to memory #2M, ... and #1. The pixel data in the same row are summed or subtracted at the summer 141. All pixels data of the next row are read out and summed at the summer in the same fashion. This operation continues until the last row of the filter for one filter position. The output

(result) of the summer is fed to memory #2N+1 and shifted to memory #2N, ... and #0. For the first filter position, the contents of the memory #2N+1 to 1 are summed to calculate the filter output as switches of memory #1 to 2N+1 are all closed but switch of memory #0 is open. For the next filter position, switches of memory #0 and #2N+1 are closed while switches of memory #1 to #2N are open to calculate the new filter output by adding the newest row data

(memory #2N+l)and subtracting the oldest row (memory #0) from the previous filter result (output) or the summer's content.

[0071] Similarly, the horizontal edge filter can be efficiently calculated as follows.

^

[0072] The filter output of the first position is stored in memory. Also, the calculation result of rows are stored in memories #1 to #2N+1. Then the filter is moved down by one row and the filter output in the new position is efficiently calculated as follows. First the contents of memories #1 to #2N+1 are shifted as follows,

( ^{8 1} ^

[0073] Only ^a t the new position is actually calculated and stored in memory #2N+1 while all other terms in the right side are in the memories. R _x value from the previous position and stored in the memory is used andupdatedby the summing operation and stored in the memory again. Electronic circuits shown in Figure 16 efficiently calculates this horizontal edge filter. Image pixel data are read out from image memory and fed to memory #2M+1 and shifted to memory #2M, .. #1. All pixels data in the same row are summed at the summer and the summer' s output is fed to memory #2N+1 and shifted to #N+2, ...and #0. For the first filter position, the contents of memory #2N+1 to #N+2 are added while the contents of memory #N to #1 are subtracted at the summer in order to calculate the filter output. Switches at memories function to achieve this

operation. All switches except memory #N+1 and #0 are closed for the first filter position. Once the filter output is calculated, the new pixel data in the next row enter memory #2M+1 to #1 and summed at the summer and this output or the newest summed row data from the next filter position enters memory #2N+1. Meantime, the contents of memory #2N+1 to 0 are all shifted right by one memory. The filter result (output) or the content of the summer from the previous filter position is then updated for the new position by adding the content of memory #2N+1 and #0 and subtracting the contents of memory #N+1 and #N. Switches function to achieve this operation. Switches at memory #2N+1, #N+1, #N and #0 are closed while all other switches are open.

[0074] This iteration method saves the number of additions. These operations of vertical and horizontal edges can be expanded to have coefficients of a, -a, 0, or aj as before. With these coefficients, the iteration method saves the number of multiplications as well as additions and thus the filter's speed is increased.

[0075] The most general form of the edge detection filter is as follows,

[0076] However, the filter can be of symmetrical form as follows

For the horizontal edge filter,

and

where i = 1 to 2M+1 and j =l to N

and

where i=l to M and j=l to 2N+1.

This horizontal edge filter is illustrated in Figure 7a as an example of 9x9 filter.

[0077] Furthermore, a _i} is split into x and y components for the horizontal edge filter as follows

where i=l to M Also

where j=l to N

Finally the horizontal edge filter can be expressed as follows,

This filter can use the iteration technique for a faster calculation.

[0078] For the vertical edge filter, filter coefficients a _tJ also have symmetry except the sign (plus or minus) .

and

where i= 1 to M and j=l to 2N+1

Also

where i=l to 2M+1 and j=l to N.

This vertical edge filter is illustrated in Figure 7b as an example of 9x9 filter.

Furthermore, a _tJ is split into x and y components for the vertical edge filter as follows

where i=l to M

where j=l to N

Finally the vertical direction filter can be expressed as follows,

Furthermore, this filter can use the iteration technique for a faster calculation.

[0079] In case of the filter with a square mask or M=N, the edge filters of 2 directions need to be equally weighted in the directions and thus

except the center row for the horizontal edge filter and the center column for the vertical edge filter.

Also the same symmetrical properties, which were previously discussed, apply to these coefficients.

Therefore, the edge filters can be expressed as follows.

[0080] This horizontal edge filter is illustrated in Figure 8a as an example of an 9x9 filter. This horizontal edge filter can be efficiently calculated using the electronic circuit shown in Figure 17. Image data are read out from image memory and fed to memory #2M+1 and shifted to memory #2M, .. #1. The contents of these memories are multiplied by coefficients bl, ...,b2M+l and summed at the summer. The output of summer is fed to memory #2N+1 and shifted to memory#2N , ... #0. For the first filter position, the contents

of memory #2N+1 to #1 excluding #N+1 are multiplied by coefficients and summed at the summer to calculate the filter output. For the next filter position, new image data for the newest row are read out from the image memory and fed to memory #2M+1 and shifted and the contents of memory #2M+1 to 1 are multiplied by coefficients and summed at the summer and the summer's output is fed to memory #2N+1. Meantime, the contents of memory #2N+1 to #0 are shifted right by one memory. The filter output or the content of the summer is updated by adding the value of memory#2N+l multiplied by coefficient bl, subtracting the values of memory #N+1 and #N multiplied by bN and adding the value of memory #0 multiplied coefficient bl to the filter output of the previous position (or the summer's content). It's noted that M=N.

[0081] This vertical edge filter is illustrated in Figure 8b as an example of an 9x9 filter. Electronic circuit shown in Figure 18 can efficiently calculate this vertical edge filter. Image data are read out from image memory and fed to memory#2M+l and shifted to #2M to #1. These column pixel data in the same row are multiplied by coefficients and summed (i.e., addedor subtracted) at the summer as shown in Figure 18. The summer's output is fed to memory #2N+1 and shifted right by one memory as more summation data in a row are fed to memory #2N+1. For the first filterposition, the contents of memory #2N+1 to 1 are multiplied and summed at the summer to calculate the filter output. For the next position, the result of the first filter position is used to efficiently calculate the next result. As the new summed data of the newest row for the new filter position is fed to memory#2N+l, all memory contents are shifted right and the new filter output is calculatedby addingmemory #2N+1 content multiplied by coefficient bl and subtracting memory #0 multiplied by bl from the previous filter result or the content of the summer.

[0082] In another embodiment, the filters can move upward starting from the bottom row. In another embodiment, the filter

can move laterally, for example, to the right, starting from the far left column. In another embodiment, the filter can move laterally to the left, starting from the far right column.

[0083] One or more embodiments of the present invention have been described. Nevertheless, it will be understood that various modifications may be made without departing from the spirit and scope of the invention. Accordingly, other embodiments are within the scope of the following claims.