Block sampling based method and apparatus for texture synthesis

• US 20020171660A1
• Filed: 05/02/2001
• Published: 11/21/2002
• Est. Priority Date: 05/02/2001
• Status: Active Grant

• 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
• Granted Patent: US 7,023,447 B2
• Time in Patent Office: Days
• 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 transform to produce a plurality of coefficients ordered to correspond to the array of pixels;

defining a plurality of sections within said plurality of coefficients;

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 moving 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 that produce said plurality of coefficients as a multi-resolutional representation of the pixels, 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.

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

extracting edge information from the image 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.

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

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

22. The apparatus 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 apparatus of claim 19 wherein said sections are block shaped.

24. The apparatus of claim 19 wherein said plurality transforms are steerable wavelet transforms that produce said plurality of coefficients as a multi-resolutional representation of the pixels.

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

26. The apparatus 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 apparatus 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 apparatus 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 apparatus 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 apparatus 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.

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.

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 transforms to produce a plurality of coefficients ordered to correspond to the array of pixels, and operable to store said plurality of coefficients in said memory;

said processor operable to define a plurality of sections within said plurality of coefficients 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.

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 transform to produce a plurality of coefficients ordered to correspond to the array of pixels;

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

means for reordering said plurality of sections, and

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