Image compression technique

• US 5,615,287 A
• Filed: 12/02/1994
• Issued: 03/25/1997
• Est. Priority Date: 12/02/1994
• Status: Expired due to Fees

• Current Assignee: Lawrence Livermore National Security LLC (Government of the United States of America)
• Original Assignee: Regents of the University of California (University of California)
• Inventors: Fu, Chi-Yung, Petrich, Loren I.
• Primary Examiner(s): Couso, Jose L.
• Assistant Examiner(s): Do, Anh Hong
• Application Number:
  US08/348,431
• Time in Patent Office: 844 Days
• Field of Search: 382/232, 382/236, 382/141, 382/199, 382/300, 382/303, 382/308, 382/172, 356/121
• US Class Current: 382/232
• CPC Class Codes: G06T 9/004 Predictors, e.g. intraframe, interframe coding
• CPC Class Codes: G06T 9/007 Transform coding, e.g. discrete cosine transform

Abstract

An image is compressed by identifying edge pixels of the image; creating a filled edge array of pixels each of the pixels in the filled edge array which corresponds to an edge pixel having a value equal to the value of a pixel of the image array selected in response to the edge pixel, and each of the pixels in the filled edge array which does not correspond to an edge pixel having a value which is a weighted average of the values of surrounding pixels in the filled edge array which do correspond to edge pixels; and subtracting the filled edge array from the image array to create a difference array. The edge file and the difference array are then separately compressed and transmitted or stored. The original image is later reconstructed by creating a preliminary array in response to the received edge file, and adding the preliminary array to the received difference array. Filling is accomplished by solving Laplace'"'"'s equation using a multi-grid technique. Contour and difference file coding techniques also are described. The techniques can be used in a method for processing a plurality of images by selecting a respective compression approach for each image, compressing each of the images according to the compression approach selected, and transmitting each of the images as compressed, in correspondence with an indication of the approach selected for the image.

Claims

1. A method for communicating via a transmission medium of limited bandwidth, an image represented by an image array of pixels each having a first value in a computer-readable storage medium, comprising the steps of:

identifying pixels of said image array being edge pixels lying on edges of said image;

creating a filled edge array of pixels each corresponding to a respective pixel in said image array,

each of the pixels in said filled edge array, which corresponds to an edge pixel of said image array, having a first value that is responsive to the first value of at least one pixel of said image array selected in response to the edge pixel,

and each of the pixels in said filled edge array, which does not correspond to an edge pixel of said image array, having a first value that is a function of the first values of at least one of the pixels in said filled edge array which do correspond to edge pixels of said image array;

subtracting said filled edge array from said image array to create a difference array of pixels; and

transmitting signals responsive to said difference array of pixels via said transmission medium.

2. A method according to claim 1, wherein each of said pixels in said image array further has second and third values,

wherein each of the pixels in said filled edge array, which corresponds to an edge pixel of said image array, further has a second value that is responsive to the second value of the at least one pixel of said image array selected in response to the edge pixel, and further has a third value that is responsive to the third value of the at least one pixel of said image array selected in response to the edge pixel,

and wherein each of the pixels in said filled edge array, which do not correspond to an edge pixel of said image array, has a second value that is a function of the second values of at least one of the pixels in said filled edge array which do correspond to edge pixels of said image array, and further has a third value that is a function of the third values of at least one of the pixels in said filled edge array which do correspond to edge pixels of said image array,

and wherein said step of subtracting said filled edge array from said image array comprises the step of subtracting the first, second and third value of each pixel of said filled edge array from respectively the first, second and third value of the corresponding pixel in said image array.

3. A method according to claim 2, wherein said step of identifying said edge pixels comprises the step of identifying adjacent pairs of pixels of said image array between which the absolute value of the spatial derivative of the at least one of the first, second and third values of said pixels, in a dimension perpendicular to a border between the pair of pixels, reaches a maximum larger than a threshold value, each pixel in each of said adjacent pairs being an edge pixel.

4. A method according to claim 1, wherein said step of identifying said edge pixels comprises the step of identifying adjacent pairs of pixels of said image array between which the absolute value of the spatial derivative of the pixel values, in a dimension perpendicular to a border between the pair of pixels, reaches a maximum larger than a threshold value, each pixel in each of said adjacent pairs being an edge pixel.

5. A method according to claim 4, wherein said step of identifying adjacent pairs of pixels comprises the steps of:

identifying all such adjacent pairs of pixels which are adjacent in a first dimension of said image; and

subsequently

identifying all such adjacent pairs of pixels which are adjacent in a second dimension of said image perpendicular to said first dimension of said image.

6. A method according to claim 1, wherein said step of identifying said edge pixels comprises the steps of:

(a) identifying each given pair of horizontally adjacent pixels in said image array for which

(1) the absolute value of a first dot product being the dot product of a 4 pixel by 3 pixel derivative operator and a 4 pixel by 3 pixel sub-array of said image array centered between said given pair of pixels, exceeds a derivative threshold,

(2) the absolute value of the difference between (A) a second dot product being the dot product of a 3 pixel by 3 pixel Laplacian operator and a 3 pixel by 3 pixel sub-array of said image centered at a first pixel of said given pair, and (B) a third dot product being the dot product of said 3 pixel by 3 pixel Laplacian operator and a 3 pixel by 3 pixel sub-array of said image centered at a second pixel of said given pair, exceeds a Laplacian threshold,

(3) said second and third dot products are opposite in sign, and

(4) the sign of the gradient from the first value of said first pixel of said given pair to the first value of said second pixel of said given pair, is opposite the sign of the gradient from said second dot product to said third dot product; and

(b) identifying each particular pair of vertically adjacent pixels in said image array for which

(1) the absolute value of a fourth dot product being the dot product of the transpose of said 4 pixel by 3 pixel derivative operator and a 3 pixel by 4 pixel sub-array of said image array centered between said particular pair of pixels, exceeds said derivative threshold,

(2) the absolute value of the difference between (A) a fifth dot product being the dot product of the transpose of said 3 pixel by 3 pixel Laplacian operator and a 3 pixel by 3 pixel sub-array of said image centered at a first pixel of said particular pair, and (B) a sixth dot product being the dot product of the transpose of said 3 pixel by 3 pixel Laplacian operator and a 3 pixel by 3 pixel sub-array of said image centered at a second pixel of said particular pair, exceeds said Laplacian threshold,

(3) said fifth and sixth dot products are opposite in sign, and

(4) the sign of the gradient from the first value of said first pixel of said particular pair to the first value of said second pixel of said particular pair, is opposite the sign of the gradient from said fifth dot product to said sixth dot product.

7. A method according to claim 1, wherein the at least one pixel of said image array selected in response to each given one of said edge pixels consists of the given edge pixel.

8. A method according to claim 1, wherein the at least one pixel of said image array selected in response to at least one of said edge pixels includes a pixel different from said at least one of said edge pixels.

9. A method according to claim 1, wherein the at least one pixel of said image array selected in response to at least one of said edge pixels comprises a plurality of pixels, and wherein said first value responsive to the first value of said at least one pixel is an average of the first values of the pixels in said plurality of pixels.

10. A method according to claim 1, wherein the at least one pixel of said image array selected in response to each given one of said edge pixels for which a second pixel adjacent to said given edge pixel in a first direction in said image array is also an edge pixel, consists of a pixel which is the lesser of N1 and N2 pixels distant from said given edge pixel in the direction opposite said first direction in said image array, where N1 is a predetermined number and N2 is less than or equal to half the number of pixels from said given edge pixel and the nearest edge pixel to said given edge pixel in the direction opposite said first direction in said image array.

11. A method according to claim 1, wherein the at least one pixel of said image array selected in response to each given one of said edge pixels for which a second pixel adjacent to said given edge pixel in a first direction in said image array is also an edge pixel, comprises a set of the pixels on a line in said image array which extend from the given edge pixel to the lesser of N1 and N2 pixels distant from the given edge pixel in the direction opposite said first direction in said image array, where N1 is a predetermined number and N2 is less than or equal to half the number of pixels from said given edge pixel and the nearest edge pixel to said given edge pixel in the direction opposite said first direction in said image array.

12. A method according to claim 1, wherein the influence on said function of the first value of each edge pixel surrounding each given one of the pixels in said filled edge array which does not correspond to an edge pixel of said image array, decreases as the distance in said image array between said surrounding edge pixel and said given pixel increases.

13. A method according to claim 1, wherein said step of creating a filled edge array comprises the steps of:

fixing the first value of each of the pixels in said filled edge array which corresponds to an edge pixel of said image array, responsively to the first value of said at least one pixel of said image array selected in response to the edge pixel; and

subsequently

solving Laplace'"'"'s equation over the first values of said filled edge array of pixels, taking as boundary conditions the first values of each of the pixels in said filled edge array which corresponds to an edge pixel of said image array.

14. A method according to claim 13, wherein said filled edge array has a size of M pixels in a first dimension and N pixels in a second dimension, and wherein said step of solving Laplace'"'"'s equation comprises the steps of:

preparing a next coarser level array having M/A pixels in said first dimension and N/B pixels in said second dimension, where A and B are predetermined integers at least one of which is greater than 1, each pixel in said next coarser level array corresponding to a respective pixel in said filled edge array, each pixel in said next coarser level array having a first value fixed at the first value of the corresponding pixel in said filled edge array if the corresponding pixel in said filled edge array is fixed, each pixel in said next coarser level array having a first value fixed at a weighted average of the first values of those pixels in a predefined neighborhood of the corresponding pixel in said filled edge array which are fixed if the corresponding pixel in said filled edge array is not fixed but at least one pixel in said neighborhood of the corresponding pixel in said filled edge array is fixed;

solving Laplace'"'"'s equation over the first values of said next coarser level array of pixels, taking as boundary conditions those first values of said next coarser level array which are fixed;

setting the first value of each pixel in said filled edge array which is not fixed, the neighborhood of which pixel includes at least one pixel whose first value is fixed, to a weighted average of the first values of those pixels in said neighborhood which are fixed;

after said step of solving Laplace'"'"'s equation over the first values of said next coarser level array, setting the first value of each pixel in said filled edge array which is not fixed and which corresponds to a pixel of said next coarser level array, the neighborhood of which pixel in said filled edge array includes no pixel whose first value is fixed, to the first value of the corresponding pixel of said next coarser level array;

after said step of solving Laplace'"'"'s equation over the first values of said next coarser level array, setting the first value of each pixel in said filled edge array which is not fixed and which does not correspond to a pixel of said next coarser level array, the neighborhood of which pixel in said filled edge array includes no pixel whose first value is fixed, to a weighted average of the first values of those pixels in said next coarser level array which correspond to a pixel in the neighborhood of the pixel in said filled edge array; and

subsequently

solving Laplace'"'"'s equation over the first values of said filled edge array, taking as boundary conditions those first values of said filled edge array which are fixed, and taking as initial values those first values of said filled edge array which are not fixed.

15. A method according to claim 14, wherein the neighborhood of a given pixel in said filled edge array is predefined as a sub-array of said filled edge array which has 2A-1 pixels in said first dimension and 2B-1 pixels in said second dimension and has said given pixel at its center if A and B are both even and has said given pixel adjacent to said center if at least one of A and B is not even.

16. A method according to claim 14, wherein A=B=2 and wherein the neighborhood of a given pixel in said filled edge array is predefined as a 3 by 3 pixel sub-array of said filled edge array having said given pixel at its center.

17. A method according to claim 1, further comprising the steps of:

forming an edge file identifying said edge pixels of said image array and the first value of each of said edge pixels; and

transmitting signals responsive to said edge file via said transmission medium.

18. A method according to claim 17, wherein said transmission medium comprises a data storage medium.

19. A method according to claim 17, further comprising the step of encoding said edge file prior to said step of transmitting signals responsive to said edge file, said step of encoding said edge file comprising the steps of:

identifying contours of said image array in response to said edge pixels identified in said step of identifying pixels of said image array lying at edges of said image; and

encoding said contours.

20. A method according to claim 19, wherein said step of encoding said contours comprises the steps of:

representing one of said contours using, for each edge pixel in a contour except a last pixel in said contour, an indication of the first value of the edge pixel and an indication of a direction in said image array of a respective next pixel in said contour;

grouping said indications into symbols; and

Huffman encoding said symbols.

21. A method according to claim 19, wherein said step of encoding said contours comprises the steps of:

fitting at least one of said contours to a best fit curve; and

encoding a parametric description of said curve.

22. A method according to claim 17, further comprising the step of encoding said difference array prior to said step of transmitting signals responsive to said difference array, said step of encoding said difference array comprising the steps of:

decimating said difference array in first and second dimensions of said difference array; and

encoding said decimated difference array.

23. A method according to claim 17, further comprising the step of creating a reconstructed array of pixels in response to said transmitted signals responsive to said edge file and said transmitted signals responsive to said difference array.

24. A method according to claim 23, wherein said step of creating a reconstructed array of pixels comprises the steps of:

creating a preliminary array of pixels in response to said transmitted signals responsive to said edge file, each pixel in said preliminary array corresponding to a respective pixel in said filled edge array, and each pixel in said preliminary array having a respective first value substantially equal to the first value of the corresponding pixel in said filled edge array;

creating a transmitted difference array in response to said transmitted signals responsive to said difference array; and

adding said preliminary array to said transmitted difference array.

25. A method for communicating, via a transmission medium of limited bandwidth, a plurality of images each being represented by a respective image array of pixels in a computer-readable storage medium, comprising the steps of:

selecting a respective compression approach for each of said images from a plurality of available compression approaches including first and second compression approaches;

compressing each of said images according to the compression approach selected for the image; and

transmitting via said transmission medium each of said images as compressed, in correspondence with an indication of the approach selected for the image,

wherein said first compression approach comprises, for a subject image, the steps of;

identifying edge pixels of the image array representing said subject image which lie at edges of said subject image; and

encoding an indication of each of said edge pixels in correspondence with a value of each of said edge pixels.

26. A method according to claim 25, wherein said second compression approach comprises the steps of said first compression approach, and further comprises the steps of:

creating a filled edge array of pixels each corresponding to a respective pixel in the image array representing said subject image,

each of the pixels in said filled edge array, which correspond to an edge pixel of said image array, having a value that is responsive to the value of at least one pixel of said image array selected in response to the edge pixel,

and each of the pixels in said filled edge array, which do not correspond to an edge pixel of said image array, having a value that is a function of the values of at least one of the pixels in said filled edge array which do correspond to edge pixels of said image array;

subtracting said filled edge array from said image array to create a difference array of pixels; and

encoding said difference array.

27. A method according to claim 26, wherein said plurality of available compression approaches includes a third compression approach comprising, for said subject image, the steps of:

decimating in two dimensions the image array representing said subject image; and

encoding said decimated image array.

28. A method according to claim 25, further comprising the steps of:

selecting a reconstruction approach in response to indication, transmitted in correspondence with each of said compressed images, of the compression approach selected for the image; and

developing a reconstructed image in response to each of said transmitted compressed images using the reconstruction approach selected for the image,

wherein the reconstruction approach selected for a subject image which was compressed according to said first compression approach comprises the step of creating a filled edge array of pixels each corresponding to a respective pixel in the image array representing said subject image,

each of the pixels in said filled edge array, which correspond to an edge pixel of said image array, having a value that is equal to the value of a pixel of said image array selected in response to the edge pixel,

and each of the pixels in said filled edge array, which do not correspond to an edge pixel of said image array, having a value that is a function of the values of at least one of the pixels in said filled edge array which do correspond to edge pixels of said image array.

29. A method according to claim 25, wherein one of said images in said plurality of images is part of a larger image.

30. A method for forming a reconstructed image, comprising the steps of:

receiving over a transmission medium having limited bandwidth an indication of pixels in a destination image array which are to be edge pixels lying on edges of said image, and a first value for each of said edge pixels;

forming said destination image array of pixels in a computer-readable storage medium such that each given pixel in said array which is one of said edge pixels has a respective first value substantially equal to the first value received over said transmission medium for a given edge pixel; and

solving Laplace'"'"'s equation over the first values of said destination image array, taking as boundary conditions the first values of each of said edge pixels.

31. A method according to claim 30, further comprising, prior to said step of receiving, the steps of:

identifying said edge pixels in a source image array; and

transmitting over said transmission medium an indication of said identified edge pixels as said indication of pixels in said destination image array which are to be edge pixels lying on edges of said reconstruction image.

32. A method for forming a reconstructed image, comprising the steps of:

receiving over a transmission medium having limited bandwidth an indication of pixels in a destination image array which are to be edge pixels lying on edges of said image, and a first value for each of said edge pixels;

forming said destination image array of pixels in a computer-readable storage medium such that each given pixel in said array which is one of said edge pixels has a respective first value substantially equal to the first value received over said transmission medium for said given edge pixel, and such that each pixel in said destination image array which is not one of said edge pixels has a respective first value which is a function of the first values of edge pixels in said destination image array;

receiving over said transmission medium a difference image array of pixels; and

adding said destination image array and said difference image array.

33. A method according to claim 32, wherein said received difference image array has a coarser grid than said destination image array, further comprising the step of interpolating said difference image array, prior to said step of adding, such that each pixel in said difference image array corresponds to a respective pixel in said destination image array.

34. A method according to claim 33, wherein said step of interpolating comprises a bi-linear interpolation.

35. A method according to claim 32, wherein said step of forming comprises the steps of:

writing the first values to said edge pixels of said destination image array as fixed values; and

solving Laplace'"'"'s equation over the first values of said destination image array, taking as boundary conditions the first values of each of said edge pixels.

36. A method according to claim 35, wherein said destination image array has a size of M pixels in a first dimension and N pixels in a second dimension, and wherein said step of solving Laplace'"'"'s equation comprises the steps of:

preparing a next coarser level array having M/A pixels in said first dimension and N/B pixels in said second dimension, where A and B are predetermined integers at least one of which is greater than 1, each pixel in said next coarser level array corresponding to a respective pixel in said destination image array, each pixel in said next coarser level array having a first value fixed at the first value of the corresponding pixel in said destination image array if the corresponding pixel in said destination image array is fixed, each pixel in said next coarser level array having a first value fixed at a first predefined function of the first values of those pixels in a predefined neighborhood of the corresponding pixel in said destination image array which are fixed if the corresponding pixel in said destination image array is not fixed but at least one pixel in said neighborhood of the corresponding pixel in said destination image array is fixed;

solving Laplace'"'"'s equation over the first values of said next coarser level array of pixels, taking as boundary conditions those first values of said next coarser level array which are fixed;

setting the first value of each pixel in said destination image array which is not fixed, the neighborhood of which pixel includes at least one pixel whose first value is fixed, to a second predefined function of the first values of those pixels in said neighborhood which are fixed;

after said step of solving Laplace'"'"'s equation over the first values of said next coarser level array, setting the first value of each pixel in said destination image array which is not fixed and which corresponds to a pixel of said next coarser level array, the neighborhood of which pixel in said destination image array includes no pixel whose first value is fixed, to the first value of the corresponding pixel of said next coarser level array;

after said step of solving Laplace'"'"'s equation over the first values of said next coarser level array, setting the first value of each pixel in said destination image array which is not fixed and which does not correspond to a pixel of said next coarser level array, the neighborhood of which pixel in said destination image array includes no pixel whose first value is fixed, to a third predefined function of the first values of those pixels in said next coarser level array which correspond to a pixel in the neighborhood of the pixel in said destination image array; and

subsequently

solving Laplace'"'"'s equation over the first values of said destination image array, taking as boundary conditions those first values of said destination image array which are fixed, and taking as initial values those first values of said destination image array which are not fixed.

37. A method according to claim 36, wherein A=B=2, wherein the neighborhood of a given pixel in said destination image array is predefined as a 3 by 3 pixel sub-array of said destination image array having said given pixel at its center, and wherein each of said predefined functions are weighted averages.

38. Apparatus for solving Laplace'"'"'s equation over the values of respective elements in a first array having a size of M elements in a first dimension and N elements in a second dimension, the values of at least some of elements in said first array being fixed, comprising:

means for preparing a second level array having M/A elements in said first dimension and N/B elements in said second dimension, where A and B are predetermined integers at least one of which is greater than 1, each element in said second level array corresponding to a respective element in said first array, each element in said second level array having a value fixed at the value of the corresponding element in said first array if the corresponding element in said first array is fixed, each element in said second level array having a value fixed at a first predefined function of the values of those elements in a predefined neighborhood of the corresponding element in said first array which are fixed if the corresponding element in said first array is not fixed but at least one element in said neighborhood of the corresponding element in said first array is fixed;

means for solving Laplace'"'"'s equation over the values of said second level array of elements, taking as boundary conditions those values of said second level array which are fixed;

means for setting the value of each element in said first array which is not fixed, the neighborhood of which element includes at least one element whose value is fixed, to a second predefined function of the values of those elements in said neighborhood which are fixed;

means for, after solving Laplace'"'"'s equation over the values of said second level array, setting the value of each element in said first array which is not fixed and which corresponds to an element of said second level array, the neighborhood of which element in said first array includes no element whose value is fixed, to the value of the corresponding element of said second level array;

means for, after solving Laplace'"'"'s equation over the values of said second level array, setting the value of each element in said first array which is not fixed and which does not correspond to an element of said second level array, the neighborhood of which element in said first array includes no element whose value is fixed, to a third predefined function of the values of those elements in said second level array which correspond to an element in the neighborhood of the element in said first array; and

means for subsequently solving Laplace'"'"'s equation over the values of said first array, taking as boundary conditions those values of said first array which are fixed, and taking as initial values those values of said first array which are not fixed.

39. Apparatus according to claim 38, wherein the neighborhood of a given element in said first array is predefined as a sub-array of said first array which has 2A-1 elements in said first dimension and 2B-1 elements in said second dimension and has said given element at its center if A and B are both even and has said given element adjacent to said center if at least one of A and B is not even.

40. Apparatus according to claim 38, wherein A=B=2 and wherein the neighborhood of a given element in said first array is predefined as a 3 by 3 element sub-array of said first array having said given element at its center.

41. Apparatus according to claim 38, wherein each of said predefined functions are weighted averages.

42. Apparatus according to claim 38, wherein said means for solving Laplace'"'"'s equation over the values of said second level array of elements, comprises:

means for preparing a third level array having M/A² elements in said first dimension and N/B² elements in said second dimension, each element in said third level array corresponding to a respective element in said second level array, each element in said third level array having a value fixed at the value of the corresponding element in said second level array if the corresponding element in said second level array is fixed, each element in said third level array having a value fixed at said first predefined function of the values of those elements in said neighborhood of the corresponding element in said second level array which are fixed if the corresponding element in said second level array is not fixed but at least one element in said neighborhood of the corresponding element in said second level array is fixed;

means for solving Laplace'"'"'s equation over the values of said third level array of elements, taking as boundary conditions those values of said third level array which are fixed;

means for setting the value of each element in said second level array which is not fixed, the neighborhood of which element includes at least one element whose value is fixed, to said second predefined function of the values of those elements in said neighborhood which are fixed;

means for, after solving Laplace'"'"'s equation over the values of said third level array, setting the value of each element in said second level array which is not fixed and which corresponds to an element of said third level array, the neighborhood of which element in said second level array includes no element whose value is fixed, to the value of the corresponding element of said third level array;

means for, after solving Laplace'"'"'s equation over the values of said third level array, setting the value of each element in said second level array which is not fixed and which does not correspond to an element of said third level array, the neighborhood of which element in said second level array includes no element whose value is fixed, to said third predefined function of the values of those elements in said third level array which correspond to an element in the neighborhood of the element in said second level array; and

means for subsequently solving Laplace'"'"'s equation over the values of said second level array, taking as boundary conditions those values of said second level array which are fixed, and taking as initial values those values of said second level array which are not fixed.

43. Apparatus for solving Laplace'"'"'s equation over the values of respective elements in a first level array having a size of M elements in a first dimension and N elements in a second dimension, the values of at least some of elements in said first level array being fixed, comprising:

means for preparing a second level array having M/2 elements in said first dimension and N/2 elements in said second dimension, each element in said second level array corresponding to a respective element in said first level array, each element in said second level array having a value fixed at the value of the corresponding element in said first level array if the corresponding element in said first level array is fixed, each element in said second level array having a value fixed at a weighted average of the values of those elements in a 3 by 3 element neighborhood of the corresponding element in said first level array which are fixed if the corresponding element in said first level array is not fixed but at least one element in said 3 by 3 element neighborhood of the corresponding element in said first level array is fixed;

means for invoking said means for preparing, repeatedly for successively coarser level arrays until a predefined coarsest level array is prepared;

means for, after said coarsest level array is prepared, solving Laplace'"'"'s equation over the values of said coarsest level array of elements, taking as boundary conditions those values of said coarsest level array which are fixed;

means for setting the value of each element in each level array which is not fixed, the 3 by 3 element neighborhood of which element includes at least one element whose value is fixed, to a weighted average of the values of those elements in said 3 by 3 element neighborhood which are fixed;

means for, after solving Laplace'"'"'s equation over the values of said coarsest level array, setting the value of each element in the next finer level array which is not fixed and which corresponds to an element of said coarsest level array, the 3 by 3 element neighborhood of which element in said next finer level array includes no element whose value is fixed, to the value of the corresponding element of said coarsest level array;

means for, after solving Laplace'"'"'s equation over the values of said coarsest level array, setting the value of each element in said next finer level array which is not fixed and which does not correspond to an element of said coarsest level array, the 3 by 3 element neighborhood of which element in said next finer level array includes no element whose value is fixed, to a weighted average of the values of those elements in said coarsest level array which correspond to an element in the 3 by 3 element neighborhood of the element in said next finer level array;

means for, after setting values in the next finer level array, solving Laplace'"'"'s equation over the values of said next finer level array, taking as boundary conditions those values of said next finer level array which are fixed, and taking as initial values those values of said next finer level array which are not fixed; and

means for invoking the means for setting values in the next finer level array and the means for solving Laplace'"'"'s equation over values of the next finer level array, repeatedly for successively finer level arrays until Laplace'"'"'s equation has been solved over values of the first level array.

44. Apparatus according to claim 43, wherein said coarsest level is predefined as that level having no more than predefined numbers of elements in each dimension.

45. Apparatus according to claim 43, wherein said coarsest level is predefined as the finest level in which the values of all elements are fixed.