Block sampling based method and apparatus for texture synthesis

• US 7,023,447 B2
• Filed: 05/02/2001
• Issued: 04/04/2006
• Est. Priority Date: 05/02/2001
• Status: Expired due to Fees

• Current Assignee: Eastman Kodak Company, Curators of the University of Missouri (University of Missouri)
• Original Assignee: Eastman Kodak Company
• Inventors: Luo, Jiebo, Yu, Yue, Chen, Chang Wen
• Primary Examiner(s): YANG, RYAN R
• Application Number:
  US09/847,636
• Publication Number:
  US 20020171660A1
• Time in Patent Office: 1,798 Days
• Field of Search: 345582-587, 382/254, 382/240, 382/260, 382/265
• US Class Current: 345/582
• CPC Class Codes: G06T 11/001 Texturing; Colouring; Generation of texture or colour inpainting G06T5/77

Abstract

A novel multi-resolution block sampling based texture analysis/synthesis algorithm. A reference texture is assumed to be sample from a probability function. The synthesis of a similar, but distinctive, synthetic texture is handled in a process and by an apparatus that first estimates and then resamples the probability function. In order to achieve good and fast estimation of the probability function for a reference texture and in order to retain the texel structural information during the synthesis, a novel concept of block sampling and a corresponding novel texture synthesis scheme based on multi-resolution block sampling is employed. As a result of this novel approach, the computational complexity of the present invention is much lower than that of other approaches to the problem. In addition, for textures that exhibit a high degree of directionality, a process, which integrates estimation of dominant texture direction and the synthesis algorithm is employed to handle directional textures. The dominant direction is used to orient and then control the synthesis process so as to preserve the dominant reference image direction.

Claims

1. A method of synthesizing a texture from an array of pixels, comprising the steps of:

decomposing the array of pixels through application of a wavelet transform to produce a plurality of coefficients ordered to correspond to the array of pixels, said coefficients being divided into a plurality of resolution levels;

defining sections of coefficients in each of said resolution levels, to provide a plurality of sections;

reordering said plurality of sections, and performing an inverse transform on said reordered plurality of sections.

2. The method of claim 1 wherein the array of pixels is a reference texture image.

3. The method of claim 1 wherein said reordered plurality of sections are reordered by random selection.

4. The method of claim 1 further comprising the steps of storing said plurality of coefficients in a memory array and wherein said reordering step is accomplished by moving coefficient values within said memory array on a section by section basis.

5. The method of claim 1 wherein the array of pixels is a texture image, and the size of said section is selected to be at least as large as a texel element within the texture image.

6. The method of claim 1 wherein said sections are block shaped.

7. The method of claim 1 wherein said transform is a steerable wavelet transform and said inverse transform is an inverse wavelet transform.

8. The method of claim 7 wherein said plurality of coefficients includes at least a lowpass band representation of the pixels.

9. The method of claim 7 wherein said steerable wavelet transform accomplishes a mapping of the pixels from a spatial domain to coefficients in the wavelet domain and said inverse wavelet transform accomplishes a mapping of said plurality of coefficients from the wavelet domain to pixels in the spatial domain.

10. The method of claim 7 wherein said plurality of sections are sampled and said inverse wavelet transform is applied recursively at all resolution levels of said multi-resolutional representation.

11. The method of claim 1 wherein the array of pixels includes a red pixel array, a green pixel array, and a blue pixel array, forming a color image, further comprising the steps of repeating said decomposing and said performing steps three times, for each of the red pixel array, the green pixel array, and the blue pixel array, while utilizing the same defining and reordering steps for each.

12. The method of claim 1 wherein said texture is scaled to a different size according to a scaling factor, further comprising the steps of:

randomly sampling said plurality of sections and

moving the coefficients to a number of new sections equal to the number of said plurality of sections times said scaling factor.

13. The method of claim 1 wherein said plurality of sections are scaled to a different size according to a scaling factor, further comprising the step of interpolating the coefficient'"'"'s sizes by said factor.

14. A method of synthesizing a directional texture from an image texture having an array of pixels, comprising the steps of:

determining the direction of the image texture;

calculating an offset angle between said determined direction and a reference direction;

rotating the array of pixels according to said offset angle;

decomposing said rotated array of pixels through application of a transform to produce a plurality of coefficients ordered to correspond to said rotated array of pixels;

defining a plurality of sections within of said plurality of coefficients;

reordering said plurality of sections such that they are moved but are constrained to a position along a line parallel to said reference direction;

synthesizing a texture by performing an inverse transform on said reordered plurality of sections, and

rotating said synthesized texture by the negative of said offset angle.

16. The method of claim 14 wherein said determining step further comprises the steps of:

extracting edge information from the image texture; and

determining the direction of the image texture from said edge information.

17. The method of claim 16 wherein said edge information is extracted using a Canny operator.

18. The method of claim 16 wherein said direction is determined using a Hough transform.

15. A method of synthesizing a directional texture from an image texture having an array of pixels, comprising the steps of:

determining the direction of the image texture;

calculating an offset angle between said determined direction and a reference direction;

decomposing said array of pixels through application of a transform to produce a plurality of coefficients ordered to correspond to said array of pixels;

defining a plurality of sections within of said plurality of coefficients;

reordering said plurality of sections such that they are moved but are constrained to a position along a line parallel to said reference direction; and

synthesizing a texture by performing an inverse transform on said reordered plurality of sections.

19. A system for synthesizing a texture from an array of pixels, comprising:

a memory for storing the array of pixels;

a processor coupled to said memory and operable to decompose the array of pixels through application of a wavelet transform to produce a plurality of coefficients ordered to correspond to the array of pixels, said coefficients being divided into a plurality of resolution levels, said processor being operable to store said plurality of coefficients in said memory;

said processor operable to define sections of coefficients in each of said resolution levels, to provide a plurality of said sections in said memory;

said processor operable to reorder said plurality of sections, and said processor operable to synthesize a texture by performing an inverse transform on said reordered said plurality of sections.

20. The system of claim 19 wherein the array of pixels is a reference texture image.

21. The system of claim 19 wherein said processor is operable to reorder said plurality of sections by random selection.

22. The system of claim 19 wherein the array of pixels is a texture image, and said processor is operable to set the size of set source sections to be at least as large as a texel element within the texture image.

23. The system of claim 19 wherein said sections are block shaped.

24. The system of claim 19 wherein said transform is a steerable wavelet transform.

25. The system of claim 24 wherein said plurality of coefficients includes at least a lowpass band representation of the pixels.

26. The system of claim 24 wherein said processor is operable to calculate wavelet transforms that map the pixels from a spatial domain to coefficients in the wavelet domain, and operable to calculate said inverse wavelet transforms so as to map said plurality of coefficients from the wavelet domain to pixels in the spatial domain.

27. The system of claim 19 wherein said processor samples said plurality of sections, said processor is operable to perform said inverse transform recursively at all resolution levels of a multi-resolutional representation.

28. The system of claim 19 wherein the array of pixels includes a red pixel array, a green pixel array, and a blue pixel array, forming a color image, and said processor is further operable to repeat said decomposing and said synthesizing for each of the red pixel array, the green pixel array, and the blue pixel array, while utilizing the same section definitions and reordering for each.

29. The system of claim 19 wherein:

said processor is operable to scale said texture to a different size according to a scaling factor, by randomly sampling said plurality of sections in said memory, and moving the coefficients to a number of destination sections in said memory equal to the number of said plurality of sections times said scaling factor.

30. The system of claim 19 wherein said plurality of sections in said memory are rescaled to a different size according to a scaling factor, and said processor is operable to interpolate the coefficient'"'"'s sizes by said scaling factor.

31. A apparatus for synthesizing a directional texture from an image texture having an array of pixels, comprising:

a memory having the array of pixels stored therein,

a processor coupled to said memory and operable to recall a portion of the array of pixels and determine a direction of the image texture, and operable to calculate an offset angle between said determined direction and a reference direction;

said processor operable to rotate the array of pixels in said memory according to said offset angle;

said processor operable to decompose said rotated array of pixels through application of a plurality of wavelet transforms to produce and store in said memory a plurality of coefficients ordered to correspond to said rotated array of pixels;

said processor operable to define a plurality of source sections of said plurality of coefficients and operable to move the coefficients from said plurality of source sections to a plurality of destination sections in said memory which are reordered, but constrained to a position along a line parallel to said reference direction, and

said processor operable to synthesize a texture by performing a plurality of inverse wavelet transforms on the reordered said plurality of coefficients in said memory, and operable to rotate said synthesized texture in said memory by the negative of said offset angle.

32. The apparatus of claim 31 wherein said processor determines the direction of rotation of the image texture by extracting edge information from the image, and determining the direction of the image texture from said edge information.

33. The apparatus of claim 32 wherein said processor is operable to extract said edge information using a Canny operator.

34. The apparatus of claim 32 wherein said processor is operable to determine said direction using a Hough transform.

35. A system for synthesizing a texture from an array of pixels, comprising:

means for decomposing the array of pixels through application of a wavelet transform to produce a plurality of coefficients ordered to correspond to the array of pixels, said coefficients being divided into a plurality of resolution levels;

means for defining sections of coefficients in each of said resolution levels, to provide a plurality of sections;

means for reordering said plurality of sections, and

means for performing an inverse transform on said reordered plurality of sections.