AU733281B2 - Image processing method for mosaic effect with adaptive tessellation - Google Patents

Description

S F Ref: 447060

AUSTRALIA

PATENTS ACT 1990 COMPLETE SPECIFICATION FOR A STANDARD PATENT

ORIGINAL

Name and Address of Applicant: Actual Inventor(s): Address for Service: Invention Title: ASSOCIATED PROVISIONAL 131] Application No(s) PP2649 Canon Kabushiki Kaisha 30-2, Shimomaruko 3-chome Ohta-ku Tokyo 146

JAPAN

Cameron Bolitho Browne Spruson Ferguson, Patent Attorneys Level 33 St Martins Tower, 31 Market Street Sydney, New South Wales, 2000, Australia Image Processing Method for Mosaic Effect with Adaptive Tessellation APPLICATION DETAILS [33] Country

AU

[321 Application Date 27 March 1998 The following statement Is a full description of this invention, including the best method of performing it known to me/us:- 5815

I

IMAGE PROCESSING METHOD FOR MOSAIC EFFECT WITH ADAPTIVE

TESSELLATION

Field of Invention The present invention relates to a method for adaptively tessellating an arbitrary shape, defined by a closed curve, into a set of mosaic tiles.

Background of Invention Mosaic tiles are relatively well known. In essence, an image is constructed using fragments of tiles or glass embedded in a cement mixture. The overall resolution is less than that which might be achieved by, say, painting the image. However, the fragmented appearance of the tiles in itself provides visual interest to an observer.

.I The effect provided by mosaic tiles has been imitated for application to digital images stored on a computer or the like. Typically, a series of control points is generated 15 across a given image, and then joined to form tile edges. Each tile is then provided with a o base colour associated with its position on the image. For example, the colour of a single V pixel corresponding to a central point in the tile may be selected as the colour for the entire tile. Alternatively, some form of colour averaging may be used to produce a single colour.

Some software packages allow a user to manually define control lines corresponding to areas of interest, using a mouse or other input device. The control points and mosaic tiles are then generated on the basis of these control lines. However, this is a relatively labour intensive approach.

(447060) (Open36 CFPunknAU) 1:\elec\cisrapenpen36\CAPAU.doc -2- There is a desire to provide a visually interesting mosaic effect which reduces the randomness of tile placement whilst allowing areas defined by closed curves to be clearly delineated from other areas of an image.

Summary of Invention Accordingly, the present invention provides a method of producing a mosaic effect in an image to be printed or displayed, the method including the steps of: providing a first closed curve; generating regularly spaced boundary points along the first closed curve; filling an area adjacent to the closed curve with generally regularly spaced fill points; generating a series of polygons on the basis of the fill points and the boundary points, thereby to generate a mosaic pattern in the area adjacent to the first closed curve; providing a background grouting image covering substantially all of said area adjacent the first closed curve; and rendering the polygons and said background grouting image for printing, storage or display.

"'.Preferably, the area adjacent to the first closed curve is within the first closed curve. It is further preferred that the method include the step of providing one or more secondary closed curves disposed within the first closed curve. In this case, the area adjacent the first closed curve is bounded internally by the secondary closed curve. The method then further includes a step prior to step of generating regularly spaced secondary boundary points along each of the secondary closed curves, the secondary S. 25 boundary points being triangulated with the boundary points and the fill points during step Preferably, step includes the sub-step of converting at least some of the triangulated polygons into non-triangular polygons.

It is particularly desirable that step includes the sub-steps of: (ii) deriving from each of the boundary points a wavefront extending into an area adjacent the closed curve, the wavefront comprising a series of fill points, each fill point being a predetermined distance from its associated boundary point; (iv) where multiple fill points fall within a predetermined distance of each other, combining the multiple fill points to generate a new fill point; 447060capau.doc -3 using fill points generated by the wavefront and sub-step (iv) as new starting points for a new wavefront; and (vi) iteratively repeating sub-steps (ii) to until the area adjacent the closed curve is filled with approximately equally spaced fill points.

According to another aspect of the present invention there is provided apparatus for producing a mosaic effect in an image to be printed or displayed, the apparatus including: delivery means for providing a first closed curve; point generation means for defining regularly spaced boundary points along the first closed curve; fill means for filling an area adjacent the first closed curve with generally regularly spaced fill points; polygon generation means for generating a series of polygons on the basis of the fill points and the boundary points, thereby to generate a mosaic pattern in the area adjacent the closed curve; and grouting image providing means for providing a background grouting image covering substantially all of said area adjacent the first closed curve.

S.According to still another aspect of the present invention there is provided a computer storage medium bearing one or more computer software programs for execution 20 on a computer, the computer software program or programs including compiled or uncompiled software instructions for implementing a method of producing a mosaic effect in an image to be displayed on a display device, stored or printed, including instructions for implementing the following steps: providing a first closed curve; S 25 generating regularly spaced boundary points along the first closed curve; filling an area adjacent the first closed curve with generally regularly 1":spaced fill points; S(d) generating a series of polygons on the basis of the fill points and the boundary points, thereby to generate a mosaic pattern in the area adjacent the first closed curve; and providing a background grouting image covering substantially all of said area adjacent the first closed curve; and rendering the polygons and said background grouting image for pinting, storage or display.

447060capau.doc -3A- Other preferences and aspects of the invention will be apparent from the associated detailed description and the numbered paragraphs which follow.

Brief Description of Drawings A preferred embodiment of the invention will now be described, by way of example only, with reference to the accompanying drawings, in which: Figure 1 is a source image for use with a preferred form of the invention; Figure 2 shows a first closed curve for use with the preferred embodiment; Figure 3 shows the closed curve of Figure 2 tessellated with a density of 0.5 and using the source image from Figure 1; Figure 4 shows a mosaic tessellation similar to that in Figure 3, with a density of 0.9; *s ooo *oo* *o *o*oo 447060capau.doc 4 Figure 5 shows a mosaic tessellation similar to that shown in Figure 3, in which spacing between the tiles is 0.25; Figure 6 shows a mosaic tessellation similar to that shown in Figure 5, provided with a spacing variation between the polygons of Figure 7 shows a mosaic tessellation similar to that shown in Figure 4, in which the polygons have been rounded with a factor of 0.4; Figure 8 shows a mosaic tessellation similar to that shown in Figure 7, provided with a roundness variation of Figure 9 shows a mosaic tessellation similar to that shown in Figure 4, with the source image rotated by 450; i Figure 10 shows a mosaic tessellation similar to that shown in Figure 9, with the •source image rotated by 900; Figure 11 shows a mosaic tessellation similar to that shown in Figure 4, to which a lighting model has been applied; Figure 12 shows a mosaic tessellation similar to that shown in Figure 11, in which the lighting model has been applied to polygons with a high "roundness" factor.

Figure 13 is a detailed view of a polygon having control points at its comers for adjustment of a roundness factor; Figure 14 shows the polygon of Figure 13 with control points adjusted; Figure 15 is a flow chart of the steps for implementing the preferred embodiment of the invention; and Figure 16 is a schematic diagram of a general-purpose computer programmable to implement the preferred embodiments of the invention.

(447060) (Open36 CFPunknAU) 1:\elc\cisrapen\open36\CAPAU.doc Detailed Description of Preferred Embodiments Referring to the drawings, and particularly to Figures 3, 4 and 15, a preferred embodiment of the invention provides a method, described by flow chart 1500, of adaptively tessellating an area defined by a first closed curve 1 (provided in step 1501).

The method involves generating regularly spaced boundary points 2 along the first closed curve 1 (step 1502), and filling an area 4 adjacent the closed curve with generally regularly spaced fill points 6 (step 1503). The fill points 6 and boundary points 2 are triangulated to generate a series of polygons (step 1504), thereby generating a mosaic pattern in the area adjacent the first closed curve. The polygons are then rendered (step 1506) for printing or display. As described in greater detail below, after triangulation, it is possible to assign colours to each of the resultant polygons (step 1505).

In its simplest form, the preferred embodiment of the invention provides triangular polygons 8, such as those which appear in parts of Figures 3 and 4. However, typically a substantial portion of these triangular polygons 8 will be converted into 15 quadrilateral polygons 9 by means of known processes.

Typically, these processes will leave a small number of triangular polygons in o* areas where quadrilateral polygons would not be suitable such as the triangular polygons 8 left in Figures 3 and 4.

Usually, the closed curve will take the form of a template, such as a shape clipped from an image, or a predetermined character. In the Figures shown, the number is used. The first closed curve 1 is a boundary curve, and the adjacent area 4 is located within that boundary. In this case, the method further includes the step of providing two secondary closed curves 10, which again define a boundary for the area adjacent the first closed curve 1. Regularly spaced secondary boundary points 12 are (447060) (Open36 CFPunknAU) 1:\elec\cisra\open\open36\CAPAU.doc 6 generated, and then triangulated when the fill points 6 and boundary points 2 are triangulated.

The fill points 6 may be generated by any suitable means. However, a preferred approach is to generate a wavefront (not shown) from each of the boundary points 2 and 12, extending into the area adjacent the closed curve 1. Each wavefront comprises a series of fill points, each of which is a predetermined distance from its associated boundary point. In the case where multiple fill points from adjacent waves fall within a predetermined distance of each other, the fill points are combined to generate a new, singular fill point. These new fill points generated by the wavefront are used as new starting points for subsequent wavefronts. The process is iteratively repeated until the entire area 4 is filled with approximately equally spaced fill points 6.

In a preferred embodiment, the invention provides a means of simulating an .i appearance of grout 14 between the tiles, as shown in Figure 5. In a preferred form, this is achieved by providing a background grouting image or texture which covers 0 O 15 substantially all of the area 4 adjacent closed curve 1. The vertices of each polygon 8, 9 are then shifted towards a mid point of that polygon by a predetermined amount. The vertex shifted polygons are then rendered over the background grouting image, such that the background grouting image is visible through gaps 16 created between the polygons 8, 9. Typically, the amount by which the vertices of each polygon 8, 9 are shifted is selectable by a user. Figure 5 illustrates an example in which a spacing value of 0.25 is used. As shown in Figure 6, a random spacing variation factor may be introduced, which simulates the imperfect tiling which might be implemented by a human artist. Once again, this variation is a parameter which may be selected and altered by a user.

Yet another parameter which may be available is a roundness factor. As shown in Figure 7, the roundness factor provides a pebble-like appearance to the tiles 8, 9, (447060) (Open36 CFPunknAU) 1:\elec\cismpenpen36\CAPAU.doc 7 thereby providing yet another visually interesting effect. As best shown in Figures 13 and 14, in a preferred form, corners 18 of the polygons 8, 9 may be rounded by allocating a first control point 20 and a second control point 22 to each corner of each polygon. The first control point 20 is associated with a first side 24 extending away from the corner 18, whilst the second control point 22 is associated with a second side 26 extending away from the corner 18. On the basis of the roundness factor selected by the user, the first control point 20 is moved to a point between the corner 18 and a centre 28 of the first side 24. Similarly, the second control point 22 is moved to a point between the corner 18 and a centre 30 of the second side 26. A rounding function is then applied on the basis of the control points 20 and 22, thereby to provide rounded edges to the polygon. In a particularly preferred embodiment, the rounding function approximates a superellipse.

As with the variable spacing of the polygons, the roundness factor may be subjected to a roundness variation which alters the amount of roundness applied to individual polygons.

As shown in Figure 8, this generates a more "human" pattern and a corresponding 15 visually interesting appearance.

In a particularly preferred form, each of the polygons has an associated base colour, the base colours of the mosaic pattern as a whole presenting a mosaic image. In the preferred form shown in the drawings, the mosaic image is based on a source image 32, such as that shown in Figure 1. The source image may be extracted from an original image (not shown), either manually by means of a user controlled input device, or adaptively by means of colour quantisation, shape analysis, edge detection, or the like.

Typically, the base colour associated with each polygon is ascertained by sampling a corresponding point of the source image 32. Usually, the colour will be sampled from the source image 32 at a point corresponding to the centre of each polygon (447060) (Opcn36 CFPunknAU) 1:\le\cis\open\opcn36\CAPAU.doc 8 8, 9. Alternatively, the colour of each polygon may be determined by calculating an average colour of source image pixels within a region corresponding to that polygon.

When mapping the source image 32 to the polygons, any polygons which fall outside the source image 32 may be remapped by a wrap-around function. This ensures that, even if the source image 32 is transformed by, for example, rotation (as shown in Figures 9 and 10), no tile will be left undefined in terms of its colour.

In a preferred embodiment, the invention may also include the application of a lighting model to the polygons 8, 9, thereby to generate a three-dimensional effect.

Examples of this are shown in Figures 11 and 12, applied to square and rounded tiles respectively. The lighting model may include a specular glint element 34 for each S:.I polygon, as well as a diffuse highlight element 36 and a diffuse shadow element 38.

4O** In one embodiment (not shown), the invention includes the step of providing the effect of missing or scattered tiles. This may be achieved by removing randomly selected tiles from the mosaic, and translating or rotating the positions of randomly selected tiles S' 15 from the remaining group. Tiles to be removed from the mosaic should be selected such 4*S* that tiles immediately adjacent the closed curve have a greater chance of being removed •0,0•0than those adjacent a central portion of the mosaic. Tiles have a progressively lower ease chance of being removed depending upon how far they are from the closed curve.

*O

Scattered tiles can be moved or rotated such that they do not intersect other tiles.

Accordingly, maximum tile scatter should take place in regions of maximum missing tiles, which will typically be adjacent the closed curve. Also, tiles should be scattered by moving them away from adjacent tiles, preferably in a random fashion.

In a preferred embodiment, the present invention is implemented as a computer application program running under WindowsTM, an operating system developed by (447060) (Open36 CFPunknAU) 1:\elec\cisrabopen\open36\CAPAU.doc Microsoft Corporation. However, it will be appreciated that other operating systems, such as UNIXTM, OS/2TM and DOSTM, can also be used The application program has a user interface which includes on-screen menus and other controls that respond to mouse and keyboard input. Where necessary, the application program is configured to transmit data to one or more printers either directly connected to a host computer or accessed over a network. The application program also has the ability to transmit and receive data to a connected digital telecommunications network (for example, the Internet).

In a preferred form, preferred embodiments of the invention are implemented on a conventional general-purpose (host) computer system, such as the computer system 1640 shown in Fig. 16. The application program discussed above (and thereby the preferred embodiments of the invention described with reference to the other drawings) is g implemented as software executed on the computer system 1640.

The computer system 1640 includes a computer module 1641, input devices such as a keyboard 1642 and mouse 1643, and output devices including a printer 1613 and a display device 1611. A modulator-demodulator ("modem") transceiver device 1652 is S used by the computer module 1641 for communication via a telecommunications network, such as a telephone line, Local Area Network or Wide Area Network The modem 1652 can also be used to access the Internet to other telecommunications networks.

The computer module 1641 includes a number of functional components, including (in the embodiment shown): a processor unit 1645; a memory unit 1646 including semiconductor Random Access Memory and Read Only Memory and (447060) (Open36 CFPunknAU) 1:\ele\cisrapen\open36\CAPAU.doc

.J

input/output interfaces including a video interface 1647; an I/O interface 1648 for the keyboard 1642 and mouse 1643; a storage device 1614, including a hard disk drive 1653 and a floppy disk drive 1654; and a CD-ROM drive 1655 for use as a non-volatile source of data.

The components 1645 to 1649 and 1653 to 1655 of the computer module 1641 communicate via an interconnecting bus 1650 in a manner that results in conventional operation of the computer system 1640, as known to those in the relevant art. Examples of computers on which the embodiments can be practised include IBM-PC's and 10 compatibles, and Sun Sparcstations.

•Typically, the application program of the preferred embodiment is resident on a S•hard disk drive 1653 and read and controlled using the processor 1645. Intermediate ee e e storage of the program and the print list and any data fetched from the network may be accomplished using the semiconductor memory 1646, possibly in concert with the hard disk drive 1653. In some instances, the application program may be supplied to the user encoded on a CD-ROM or floppy disk, or alternatively could be read by the user from the network via the modem device 1652.

At least in a preferred embodiment, the present invention provides a means of relatively easily generating a mosaic effect for a given closed curve. By doing so, a visually interesting effect is generated without the need for manual input or relatively small tiles. For these reasons, the present invention represents a commercially significant advance over the prior art.

Although the invention has been described with reference to a number of particular embodiments, it will be appreciated by those skilled in the art that the invention may be embodied in many other forms.

(447060) (Open36 CFPunknAU) I:\elec\cisra\opcn'open36\CAPAU.doc

Claims (17)

1. A method of producing a mosaic effect in an image to be printed or displayed, the method including the steps of: providing a first closed curve; generating regularly spaced boundary points along the first closed curve; filling an area adjacent the first closed curve with generally regularly spaced fill points; generating a series of polygons on the basis of the fill points and the boundary points, thereby to generate a mosaic pattern in the area adjacent the first closed curve; providing a background grouting image covering substantially all of said area adjacent the first closed curve; and rendering the polygons and said background grouting image for printing, storage or display.

2. A method according to claim 1, wherein the area adjacent the first closed curve is within the first closed curve. 20 3. A method according to claim 2, further including the step of providing one or oooo "o :more secondary closed curves disposed within the first closed curve, the area adjacent the .i first closed curve being bounded internally by the secondary closed curves, the method further including a step prior to step of generating regularly spaced secondary i boundary points along each of the secondary closed curves, the secondary boundary 25 points being triangulated with the boundary points and fill points during step oo° *og*

4. A method according to any one of the preceding claims, wherein step (d) :o includes the sub-step of converting at least some of the triangulated polygons into non- triangular polygons. A method according to any one of the preceding claims, wherein step (c) includes the following sub-steps: (iii) deriving from each of said boundary points a wave front extending into an area RAq\ qadjacent the closed curve, the wave front comprising a series of fill points, each fill point 3) being a predetermined distance from its associated boundary point; 447060capau.doc -12- (iv) where multiple fill points fall within a predetermined distance of each other, combining the multiple fill points to generate a new fill point; using fill points generated by the wave front and sub-step (iv) as new starting points for a new wave front; and (vi) iteratively repeating sub-steps (iii) to until the area adjacent the closed curve is filled with approximately equally spaced fill points.

6. A method according to any one of claims 1 to 5, wherein step includes the further sub-steps of: (vii) shifting vertices of each polygon towards a midpoint thereof by a predetermined amount; and (viii) compositing the vertex-shifted polygons over the background grouting image, such that the background grouting image is visible through gaps created between the polygons.

7. A method according to claim 6, wherein the predetermined amount referred to in sub-step (viii) is a parameter, the value of which is selectable by a user.

8. A method according to any one of the preceding claims, further including the 0o0. 20 step of rounding corners of at least some of the polygons. 009: go• o*

9. A method according to claim 8, wherein the step of rounding the comers of the polygons includes the sub-steps of: allocating a first control point and a second control point to each comer of each 25 polygon, the first control point being associated with a first side extending away from the comer and the second control point being associated with a second side extending away from the corner; moving the first control point to a point between the corner and a centre of the first side and moving the second control point to a point between the corner and a centre of the second side; and using a rounding function to round the corner between the first and second control points, for each corner of the polygon. RA 10. A method according to claim 9, wherein the rounding function approximates a 3 superellipse. 447060capau.doc

13- 11. A method according to claim 9 or claim 10, wherein the rounding amount by which the first and second control points are moved along the first and second sides respectively is based on a roundness parameter. 12. A method according to claim 11, wherein the roundness factor is selected by a user from a range of possible values. 13. A method according to any one of claims 9 to 12, wherein the roundness factor represents a proportion of the first and second sides by which the first and second control points respectively are moved.

14. A method according to any one of the preceding claims, wherein each of the polygons has an associated base colour, the base colours of the mosaic pattern as a whole presenting a mosaic image A method according to claim 14, further including a step in which, prior to step the mosaic image is based on a source image. .5 20 16. A method according to claim 15, wherein step includes the sub-step of oooo extracting the source image from an original image, by means of colour quantisation, shape analysis or edge detection. i 17. A method according to claim 15, wherein step includes the sub-step of a user 25 manually extracting the source image from the original image. o oo

18. A method according to any one of claims 15 to 17, wherein the base colour associated with each polygon is ascertained by sampling a corresponding point of the source image.

19. A method according to claim 18, wherein the colour is sampled from the source image at a point corresponding to the centre of each polygon. 447060capau.doc -14- A method according to claim 17, wherein the colour of each polygon is determined by calculating an average colour of the source image pixels within a region corresponding to that polygon.

21. A method according to any one claim 18 to 20, further including the step of remapping tiles which fall outside the source image to a point within the source image, thereby to wrap the source image within the mosaic pattern.

22. Apparatus for producing a mosaic effect in an image to be printed or displayed, the apparatus including: delivery means for providing a first closed curve; point generation means for defining regularly spaced boundary points along the first closed curve; fill means for filling an area adjacent the first closed curve with Is generally regularly spaced fill points; polygon generation means for generating a series of polygons on the basis of the fill points and the boundary points, thereby to generate a mosaic pattern in the area adjacent the closed curve; and grouting image providing means for providing a background grouting "o 20 image covering substantially all of said area adjacent the first closed curve. *o

23. Apparatus according to claim 22, wherein the polygon generation means are t o: configured to convert at least some of the triangulated polygons into non-triangular polygons.

24. Apparatus according to claim 22 or claim 23, wherein the fill means includes: wave front generation means for generating a wave front from each boundary point into the area adjacent the closed curve, the wave front comprising a series of fill points each being a predetermined distance from its associated boundary point; and combining means for combining into a new fill point multiple fill points which fall within a predetermined distance of each other; wherein the wave front generation means uses fill points associated with previously generated wavefronts as starting points for new wavefronts, until the area adjacent the closed curve has been filled with fill points. 447060capau.doc A computer storage medium bearing one or more computer software programs for execution on a computer, the computer software program or programs including compiled or uncompiled software instructions for implementing a method of producing a mosaic effect in an image to be displayed on a display device, stored or printed, including instructions for implementing the following steps: providing a first closed curve; generating regularly spaced boundary points along the first closed curve; filling an area adjacent the first closed curve with generally regularly lo spaced fill points; generating a series of polygons on the basis of the fill points and the boundary points, thereby to generate a mosaic pattern in the area adjacent the first closed curve; and providing a background grouting image covering substantially all of said area adjacent the first closed curve; and rendering the polygons and said background grouting image for printing, storage or display. ooooo

26. A method of producing a mosaic effect in an image to be printed or displayed, 20 the method being substantially as herein described with reference to any one of the o. embodiments of the invention shown in the accompanying drawings. l

27. An apparatus for producing a mosaic effect in an image to be printed or displayed, the apparatus being substantially as herein described with reference Fig. 16 of 25 the accompanying drawings. •go DATED this fifteenth Day of March, 2001 S. Canon Kabushiki Kaisha Patent Attorneys for the Applicant SPRUSON FERGUSON 447060capau.doc