AU2008237612A1 - Interpolated layout - Google Patents

Description

S&F Ref: 864531 AUSTRALIA PATENTS ACT 1990 COMPLETE SPECIFICATION FOR A STANDARD PATENT Name and Address Canon Kabushiki Kaisha, of 30-2, Shimomaruko 3 of Applicant: chome, Ohta-ku, Tokyo, 146, Japan Actual Inventor(s): Ian Robert Boreham Address for Service: Spruson & Ferguson St Martins Tower Level 35 31 Market Street Sydney NSW 2000 (CCN 3710000177) Invention Title: Interpolated layout The following statement is a full description of this invention, including the best method of performing it known to me/us: 5845c(1827554_1) INTERPOLATED LAYOUT TECHNICAL FIELD The present invention relates to software-implemented methods and processes for creation, editing, and printing of documents composed of text and graphics and, in particular, to the creation, editing and printing of dynamically laid-out documents. 5 BACKGROUND Page Layout Laying out a page is the process of determining the position of and size at which items of content, such as text and images, are displayed on a page. At a basic level, this process is typically performed once per document by a graphic designer or other person 10 associated with document creation. However, there are many situations in which a designer must design a page so that the design forms a template that can be used more than once. Variable Data Printing A document may be printed multiple times, but customised for each recipient, 15 by printing some variable data, such as the recipient's name, on the page. In this case, the same layout may be used for each copy of the document, even though each copy has slightly different content. The content consists of static data, which is the same for each copy of the document, and variable data, which is typically drawn from a database. This process of printing multiple documents from a standard template but with variable data 20 is referred to as variable data printing, or VDP. With the rise of digital printing, variable data printing has become more cost-effective and widespread than before. Frequently it is necessary to print a document multiple times, customised for each recipient, but with a modified layout for each. In the case of a customised 1826285_1 863531_speci final -2 catalogue, each document may describe different products to the intended recipient, and the data for the products may not be conducive to using exactly the same layout for each document. The product images may have different aspect ratios or sizes, and one product may have longer descriptive text or more features than another. In this case, 5 using the same layout for each document would require cropping or scaling of images, shrinking of text, or leaving gaps on the page. A better solution is to adapt the layout to the contents, so that the page regions allocated to each content item correspond more closely to the properties of the item. Predesigned templates 10 Another case in which a page might be designed once and the layout used more than once is in designing software application templates for assisting a user in laying out pages. For example, predesigned templates are used in software for designing photograph albums or posters, and allow the user to insert the user's own content into a page that has been previously designed by a professional designer. 15 Dynamic Layout When multiple documents are printed using a standard template, if the same layout (a "static" template) is used for each document, the content from a particular data record may not fit well in that layout. Dynamic layout refers to the process of creating a page whose layout is determined at least in part from the content to be laid out on the 20 page. Instead of specifying a static region in which to insert an image, the template might specify constraints regarding how the image should be placed, and those constraints and the image attributes together determine the actual layout. Dynamic layout can be used in variable data printing and for creating predesigned templates. Variable data printing and graphic design software applications 1826285_1 863531_specifinal -3 with dynamic layout features are commercially available. However, these applications have limited dynamic layout features, unpredictable dynamic layout behaviour, and are difficult to use, due to the need to specify layout constraints or rules. These applications also do not provide the ability for the user to make adjustment to the layout of individual 5 records. Creation of predesigned templates that produce good layouts for user data is also not easy. SUMMARY Disclosed is a method of laying out a set of content items on a page. The method provides a plurality of example page layouts, each example page layout being associated 10 with example content attributes. At least two example page layouts are selected from the plurality of example page layouts based on attributes of the content items in the set and the example content attributes associated with each example page layout. A page layout is then determined for the set of content items, by interpolating between the at least two selected example page layouts. Lastly, the set of content items are laid out on the page 15 using the determined page layout. Typically the example content attributes are derived from a set of example content items arranged to form an example page layout. Desirably the selecting includes using the attributes of the content items in the set to define a point in space representing the set; using the example content attributes 20 associated with each of the plurality of example page layouts to define points in space representing each example page layout; and selecting the at least two example page layouts based on the position in space of their respective representative points and the point representing the set of content items. Typically, the at least two example page layouts are selected by creating simplices whose vertices correspond to the points 1826285_1 863531_specifinal -4 representing each of the plurality of example page layouts, identifying the simplex containing the point representing the set of content items, and selecting the example page layouts corresponding to the vertices of the identified simplex. Desirably the creating of the simplices comprises creating a Delaunay triangulation of the space. If the point 5 representing the set of content items is not contained within a simplex, the method identifies the simplex closest to the point representing the set of content items. Preferably, the determining of the method includes using the attribute of each content item in the set to define a point in space representing the set; using the example content attributes associated with each of the selected example page layouts to define 10 points in space representing the selected page layouts; and interpolating between the at least two selected example page layouts based on weightings, said weightings being determined by the relative position of the point representing the set and each of the points representing the example page layouts. Also desirably for each example page layout, the example content attributes are 15 derived from geometric properties of the example page layout. Other aspects are also disclosed. BRIEF DESCRIPTION OF THE DRAWINGS At least one embodiment of the present invention will now be described with reference to the following drawings, in which: 20 Fig. I shows an example of the requirement for page layout; Fig. 2 is an example of a laid-out page; Fig. 3 shows the interface for drawing or laying out a page using computer software; Fig. 4 is a flow chart of a process for interpolated layout; 1826285_1 863531_specifinal -5 Fig. 5 is a flow chart of a process for template creation; Fig. 6 shows a table of data suitable for laying out a document; Fig. 7 is a flow chart of a process for creating an example page layout for a particular data record; 5 Fig. 8 illustrates the relationship between fields in a data table and regions in a laid-out page; Fig. 9 shows the relationship between fields in a data table and attributes used to determine how a page layout should be interpolated between example page layouts; Fig. 10 shows the relationship between records in a data table and example page 10 layouts for specific records; Fig. 11 is a flow chart of a process for mapping input data regions to example page layouts. Fig. 12 is a flow chart of a process of producing an interpolated page layout for a data record; 15 Fig. 13 is a diagram showing how a space can be triangulated by creating simplices whose vertices are a specified set of points; Fig. 14 is a diagram showing how a point in a triangulated space can fall inside a simplex, on a simplex boundary, or outside all simplices; Fig. 15 is a diagram showing how to determine the barycentric coordinates of a 20 point in a simplex; Fig. 16 illustrates how a linear function value can be interpolated for a point in a simplex; Fig. 17 illustrates how a page layout for a record can be interpolated from example page layouts for other records; 1826285_1 863531_specifinal -6 Figs. 18A, 18B and 18C represent a comparative example that shows the sort of behaviour that could result from other forms of function-fitting; Fig. 19 is a schematic block diagram of a general purpose computer on which the arrangements described may be practised; and 5 Fig. 20 is a schematic representation of an interpolated layout process according to the present disclosure. DETAILED DESCRIPTION INCLUDING BEST MODE Disclosed is a method of laying out pages for given data, based on example page layouts provided for content data with a similar structure. The method may be 10 called "interpolated layout" because, given content data, the method chooses page layouts from the provided example page layouts and interpolates between those example page layouts to produce a new page layout for that given content data. Interpolation is the process of finding values for a function by examining values of the function from surrounding points. For interpolated layout, the input to the layout 15 function is content attribute information taken from content data to be laid out on a page. In one implementation, this content data is taken from a database record. The output of the layout function is the position data of edges, vertices or control points of the regions allocated to content items on the page. These positions are found by interpolating between the corresponding entities in example page layouts 20 created for content data similar to the data of the record to be laid out. In a preferred implementation, linear interpolation is used to find these positions. A generalised schematic representation an interpolated layout process 2000 is seen in Fig. 20. A database 2002 of content items, such as images and text objects, is provided. The content items are divided into individual records of such items, with each 1826285_1 863531_speci final -7 record providing for the generation of a dynamically variable page in which the variability between pages arises from differences in the content items sourced from the database 2002. In the process 2000, a limited number of at least two records of content items are used to generate a corresponding number of example page layouts 2004. 5 Content attribute information 2006 for each example page layout is determined from the content items in the record used to generate each example page layout 2004. In this example, the content attribute information includes aspect ratio (of an image in the record used to generate example page layout 2004) and text size (representing the approximate area of a page that would be occupied by text in the record used to generate 10 example page layout 2004). Other attributes may be determined as required. Using the content attribute information 2006 for each example page layout 2004, a region 2008 is generated to describe the range of values of content attribute information 2006 (i.e. aspect ratio and text size in this example) described by the example page layouts 2004. The region 2008 in this example is shown with four control 15 points indicating that four example page layouts 2004 were in fact used. The region 2008 thus defines an area over which interpolation may be performed for other records of content data to thus form other page layouts. With a minimum of two example page layouts, it will be appreciated that only two points will be defined and the "region" will simply be a line connecting the two points. As seen, content attribute information 2007 20 for a non-example content record #n is then determined, and a page layout 2012 is interpolated 2010 between the example page layouts 2004 using the position of the content attribute information 2007 for content record #n in the region 2008. As such, by creating, and perhaps varying, example page layouts for a limited number of exemplary content records, interpolation may be used to create page layouts for the remainder of the 1826285_1 863531_specifinal -8 content records in the database 2002 such that the created page layouts fall within a layout gamut of the example page layouts 2004. Hardware platform The arrangements described herein may be implemented using a computer 5 system 1900, such as that shown in Fig. 19 wherein the processes and functions, illustrated in Figs. 1 to 18 and 20, may be implemented as software, such as one or more application programs executable within the computer system 1900. In particular, the steps of the methods are effected by instructions in the software that are carried out within the computer system 1900. The instructions may be formed as one or more code 10 modules, each for performing one or more particular tasks. The software may also be divided into two separate parts, of which a first part and the corresponding code modules perform the automatic layout function, and a second part and the corresponding code modules manage an interface between the first part and the user. The software may be stored in a computer readable medium, including the storage devices described below, 15 for example. The software is loaded into the computer system 1900 from the computer readable medium, and then executed by the computer system 1900. A computer readable medium having such software or computer program recorded on it is a computer program product. The use of the computer program product in the computer system 1900 preferably effects an advantageous apparatus for automatically laying out 20 documents. As seen in Fig. 19, the computer system 1900 is formed by a computer module 1901, input devices such as a keyboard 1902 and a mouse pointer device 1903, and output devices including a printer 1915, a display device 1914 and loudspeakers 1917. An external Modulator-Demodulator (Modem) transceiver 1826285_1 863531_speci final -9 device 1916 may be used by the computer module 1901 for communicating to and from a communications network 1920 via a connection 1921. The network 1920 may be a wide-area network (WAN), such as the Internet or a private WAN. Where the connection 1921 is a telephone line, the modem 1916 may be a traditional "dial-up" 5 modem. Alternatively, where the connection 1921 is a high capacity (e.g. cable) connection, the modem 1916 may be a broadband modem. A wireless modem may also be used for wireless connection to the network 1920. The computer module 1901 typically includes at least one processor unit 1905, and a memory unit 1906 for example formed from semiconductor random access 10 memory (RAM) and read only memory (ROM). The module 1901 also includes an number of input/output (1/0) interfaces including an audio-video interface 1907 that couples to the video display 1914 and loudspeakers 1917, an 1/0 interface 1913 for the keyboard 1902 and mouse 1903 and optionally a joystick (not illustrated), and an interface 1908 for the external modem 1916 and printer 1915. In some implementations, 15 the modem 1916 may be incorporated within the computer module 1901, for example within the interface 1908. The computer module 1901 also has a local network interface 1911 which, via a connection 1923, permits coupling of the computer system 1900 to a local computer network 1922, known as a Local Area Network (LAN). As also illustrated, the local network 1922 may also couple to the wide-area network 1920 via a 20 connection 1924, which would typically include a so-called "firewall" device or similar functionality. The interface 1911 may be formed by an EthernetTM circuit card, a wireless Bluetooth or an IEEE 802.11 wireless arrangement. The interfaces 1908 and 1913 may afford both serial and parallel connectivity, the former typically being implemented according to the Universal Serial Bus (USB) 1826285_1 863531_specifinal -10 standards and having corresponding USB connectors (not illustrated). Storage devices 1909 are provided and typically include a hard disk drive (HDD) 1910. Other devices such as a floppy disk drive and a magnetic tape drive (not illustrated) may also be used. An optical disk drive 1912 is typically provided to act as a non-volatile source 5 of data. Portable memory devices, such as optical disks (eg: CD-ROM, DVD), USB RAM, and floppy disks for example may then be used as appropriate sources of data to the system 1900. The components 1905 to 1913 of the computer module 1901 typically communicate via an interconnected bus 1904 and in a manner which results in a 10 conventional mode of operation of the computer system 1900 known to those in the relevant art. Examples of computers on which the described arrangements can be practised include IBM-PC's and compatibles, Sun Sparcstations, Apple MacTM or alike computer systems evolved therefrom. Typically, the application programs discussed above are resident on the hard 15 disk drive 1910 and read and controlled in execution by the processor 1905. Intermediate storage of such programs and any data fetched from the networks 1920 and 1922 may be accomplished using the semiconductor memory 1906, possibly in concert with the hard disk drive 1910. In some instances, the application programs may be supplied to the user encoded on one or more CD-ROM and read via the corresponding 20 drive 1912, or alternatively may be read by the user from the networks 1920 or 1922. Still further, the software can also be loaded into the computer system 1900 from other computer readable media. Computer readable media refers to any storage medium that participates in providing instructions and/or data to the computer system 1900 for execution and/or processing. Examples of such media include floppy disks, magnetic 1826285_1 863531_specifinal - 11 tape, CD-ROM, a hard disk drive, a ROM or integrated circuit, a magneto-optical disk, or a computer readable card such as a PCMCIA card and the like, whether or not such devices are internal or external of the computer module 1901. Examples of computer readable transmission media that may also participate in the provision of instructions 5 and/or data include radio or infra-red transmission channels as well as a network connection to another computer or networked device, and the Internet or Intranets including e-mail transmissions and information recorded on Websites and the like. The second part of the application programs and the corresponding code modules mentioned above may be executed to implement one or more graphical user 10 interfaces (GUIs) to be rendered or otherwise represented upon the display 1914. Through manipulation of the keyboard 1902 and the mouse 1903, a user of the computer system 1900 and the application may manipulate the interface to provide controlling commands and/or input to the applications associated with the GUI(s). Page layout 15 Fig. 1 shows an example of the requirement for page layout. The designer has a blank page 110 on which content items are to be displayed. In this example, the content items include an image 120, a block of body text 130, and a title 140. Page layout is the process of positioning these content items on the page 110. Fig. 2 is an example of a laid-out page 200. Item 210 represents the page 20 background on which content is laid out and which corresponds to the blank page 110 of Fig. 1. A content region 220 is positioned to contain the image 120. In this case, the image content region 220 is rectangular, in order to fit the entire image 120. However, images could be placed in non-rectangular content regions, with excess image areas cropped. A text content region 230 is provided to contain the text 130. This text content 1826285_1 863531_specifinal - 12 region 230 in this example is a non-rectangular polygon, and the text content 130 flows to fill the region. Another text region 240 is provided, in this case as a destination to accommodate the title 140. The region 240 displays its content using a larger font, and is rectangular in shape. 5 Fig. 3 shows a graphical user interface (GUI) 300 for drawing or laying out a page formed using GUI computer software, such as mentioned above. This software is executed on the computer system 1900 shown on Fig. 19 resulting in the GUI 300 being represented upon the display 1914. The GUI 300 is represented visually in a window 310, which is displayed on the video display 1914, perhaps within or associated with 10 other windows associated with other applications. The window 310 contains a menu bar 320, which in turn contains menus 321. The menus provide a means of executing GUI commands to affect the appearance and contents of the page, and to load and save documents. The window 310 also contains a toolbar 330 of tool buttons, being icons selectable using the keyboard 1902 or mouse 1903, and which allow the user to create 15 graphic objects or content regions on the page, or to add content. A rectangular region 340 is being created in the window 310 using a rectangle tool 332, by dragging, using a user interface peripheral such as the mouse 1903, whose on-screen representation is a pointer or cursor 350. Interpolated layout 20 Fig. 4 shows an overall process 400 of interpolated layout according to specific implementation. The process 400 is typically formed by application software executable within the computer 1900 and starts with sub-process 420, by which the human designer creates a template by specifying example page layouts for particular records, using the GUI 300 similar to that shown in Fig. 3. This sub-process 420 is expanded on in Fig. 5. 1826285_1 863531_specifinal - 13 After the template is created, a sub-process 430 determines what ranges of input data are associated with which example page layouts. The sub-process 430 is described in more detail in Fig. 11. Sub-process 440 then produces interpolated page layouts for specific records, 5 using the example records and mappings from sub-processes 420 and 430. The sub process 440 is described in more detail in Fig. 12. Fig. 5 shows the process 420 of template creation according to one implementation. The process 420 starts with step 520 where the application prompts the user to choose an example record via the GUI 300, such as from a database stored on the 10 hard disk drive 1910. Step 530 is then executed by which the user creates an example page layout for the example record, using the GUI 300. Step 530 is described in more detail in Fig. 7. The example page layout is then stored at step 540 in association with the example content attributes of the example record upon which it is based. The storage is typically in the computer memory 1906 or on the hard disk drive 1910. An association 15 between the stored example page layout and the example record can be seen depicted in Fig. 10. If there are more data records for which it is desired to create examples, step 550 affords the user the opportunity to return the process 420 to step 520 by which this may be achieved. Otherwise the process 420 ends at step 599. Fig. 6 is a diagram showing the structure of a table 600 of data, as may be used 20 in some implementations, and which is illustrative of the structure of the content data from which documents are to be formed. In a preferred approach, the content data is stored in records in a database on the hard disk drive 1910 and thus the table 600 is an example representation of such a database. However, an explicit database is not required, as long as the content data used for each page layout has a consistent structure. 1826285_1 863531_specifinal - 14 The example table 600 has a column for each data field, in this case a record number 610, a Text field 620, a Title text field 630 and an Image field 640. The rows represent records 650, each of which contains one entry corresponding to each field. Fig. 7 shows the process 530 of creating an example page layout for a record 5 650. The process 530 starts with step 720 where the application prompts the user to choose a data field to add to the page. In a preferred implementation, this includes the user manipulating the GUI 300 to select a data field using a database browser that accesses the content data database (eg. the table of Fig. 6) stored on the hard disk drive 1910. The application in step 730 accepts via the GUI 300 a user drawing of a content 10 region on the page representing that data field, appropriately sized, shaped and positioned for the content item in that field of the current record 650. Drawing the content regions is performed using tools from a toolbar 330 and menus 321 in the GUI 300 similar to that shown in Fig. 3. In a simple implementation, all content regions are rectangles. However, a more flexible approach also allows the user to create non 15 rectangular polygonal content regions. One preferred arrangement also allows content regions with shapes such as ellipses and parametric curves. In a specific implementation, the user creates example page layouts via a user interface similar to the one shown in Fig. 3. As the user draws the regions in the example page layout, they are stored in the computer memory 1906. 20 In step 740, the application prompts the user to add more data fields to the layout. If accepted by the user, the process 530 returns to step 720, or otherwise ends at step 799. In this way, the user creates associations between data fields and page regions. This is illustrated in Fig. 8. Here, an example page layout 810 contains a text region 1826285_1 863531_specifinal - 15 820, associated with the Text field 620 by an association 821; a title region 830, associated with the Title field 630 by a different association 831; and an image region 840, associated with the Image field 640 by a further association 841. A further type of association required for interpolation is between the data fields 5 and the attributes used as input to the layout interpolation function. The content attributes are numeric values determined from the data in the fields of the data records 650. The content attributes are desirably stored in the HDD 1910, for example associated with the content data, or appended the content data database in an appropriate fashion. 10 Interpolation of page layouts is based on the similarity of a data record to the data records on which the examples are based. The user may choose which attributes of data fields should be used during interpolation, based on the nature of the data, or how it is to be used in the document. Some fields in the data records may not contribute significantly to the interpolation process (for example, they all contain similar-sized 15 content, or they are considered of relatively low importance), and so none of their attributes are used for interpolation. Some fields may have a single content attribute. For example, a text block has a measurable area when laid out. This area changes somewhat as the size and shape of the content region into which the text is placed may vary, but the area value is relatively constant over a fairly wide range of page layouts. 20 The approximate area required to lay out the text can be measured and stored as the content attribute that the text block contributes to the interpolation calculation. An image might have more than one content attribute associated with it. In some cases, the image's aspect ratio might be considered its only content attribute, if the image can be scaled arbitrarily. However, sometimes the size may also be important. Possible content 1826285_1 863531_specifinal - 16 attributes associated with an image field include aspect ratio, height, width and area. Fig. 9 shows how the content items are associated with content attributes 910. In order for interpolation calculations to be performed, every data record that is used to create an example page layout, or that is to be laid out, must contain each of the fields that are 5 associated with content attributes. The text field 620 is associated by an association 921 with a text area content attribute 920 for each record 650. The title field 630 in this example is not associated with any content attribute. The image field 640 is associated by another association 931 with an image aspect ratio content attribute 930, which represents the aspect ratio of the 10 image in the image field 640 of the current record 650. The image field 640 has a further association 941 with an image area content attribute 940, which represents the inherent image area of the image in the image field 640. The content attributes 920, 930 and 940 are each related to an aspect of content and thus form content attribute information associated with each example page layout. 15 Content attributes normally correspond to fields whose content items are displayed in content regions on the laid-out pages. If a particular field content of the content data database is not included on the page, then usually it should not affect the interpolation process. However, the database field content could contain data that is used in another way, such as a background colour. As a result, it is possible to associate 20 a database field with a content attribute even when the field's content is not displayed in a content region. Fig. 10 shows the relationships between data records 650 and example page layouts created using the process 700 described in Fig. 7. In this example, record 1012 is associated by a relationship 1011 with a user-created example page layout 1010. Record 1826285_1 863531_specifinal - 17 1022 is associated by a relationship 1021 with a user-created example page layout 1020. Record 1032 is associated by a relationship 1031 with a user-created example page layout 1030. Record 1042 is associated by a relationship 1041 with a user-created example page layout 1040. The other records do not have example page layouts. As 5 will be appreciated from Fig. 10, each of the example page layouts 1010, 1020, 1030 and 1040 are of essentially the same form (ie. image in the top-right corner of the page, L shaped text around the image, and a title at the bottom of the page) varied only by the manner in which content of the corresponding data record 1012, 1022, 1032 and 1042 is accommodated by the page layout. Also, for each record 610 seen in Fig. 10, the 10 corresponding attribute fields 620, 630 and 640 create, by the associations shown in Fig. 9, a triple of content attribute information associated with the example page layout. Where only two fields are active, a couple or pair of such content attribute information is formed. Where an arbitrary number of such fields are active, a "tuple" of content attribute information is formed. Tuples of content attribute information are used to 15 determine a layout for a page, given multiple example page layouts. Also, as seen in Fig. 10, the content items as laid out in the example page layouts 1010-1040 result in the laid-out components having a range of geometries. For example, an aspect ratio of an image component presented in the example page layouts 1010 - 1040 varies as seen by 1050a - 1050d. The size of text portions can also change. The template (being the 20 collection of examples with associated content attributes from data records) and the interpolation mechanism together specify the layout function being created. Fig. 11 is a flow chart of the process 430 for mapping content attribute regions to example page layouts, as discussed above with reference to Fig. 4. The values of all content attributes for a record can be viewed as a vector of the same dimension as the 1826285_1 863531_specifinal - 18 number of content attributes. Thus, every record corresponds to a point in a space whose dimension corresponds to the number of content attributes. The process 430 is also implemented in software executable by the computer 1900 and starts with step 1120, which triangulates the content attribute space. In a 5 preferred implementation, the computer processor 1905 loads the content attributes from the hard disk drive 1910 into the computer memory 1906, and performs the triangulation process on the content attribute data. Triangulation is the process of dividing an n dimensional space into simplices. A simplex is an n-dimensional analogue of a triangle. Triangulation creates simplices whose vertices are a set of specified points (in this case, 10 the points corresponding to the example page layouts). This process is illustrated in more detail in Fig. 13. In a preferred implementation, the division process creates a Delaunay triangulation of the content attribute space, given the content attribute vectors that correspond to the example page layouts. A Delaunay triangulation is a triangulation in which the circumhypersphere (the hypersphere that passes through all the vertices) of 15 a simplex does not contain vertices of any other simplex in its interior. As such, the triangulation separates the interpolation space into regions, such that no example page layout lies within a region, but rather each example page layout forms a vertex of a region. The regions do not overlap. The next step 1130 operates to associate example page layouts with the vertices 20 of each simplex. Since multiple simplices can each have a vertex at a point corresponding to the attributes of a record used to create an example page layout, that example page layout is associated with the corresponding vertex in each simplex. The associations are stored in the computer memory 1906 or on the computer hard disk drive 1910. After this step, the process 430 ends at step 1199. 1826285_1 863531_specifinal - 19 Fig. 12 is a flow chart of the process 440 for producing an interpolated page layout for a data record, as discussed above with reference to Fig. 4. The process 440 starts by receiving at step 1220 data record content attributes for the new record to be laid out. Typically, the computer processor 1905 reads the content attributes from the 5 database on the hard disk drive 1910 into the computer memory 1906. Then the process continues by finding at step 1230 the simplex containing the point in content attribute space corresponding to the record to be laid out. Next, at step 1240, the process 440 determines which example page layouts contribute to the page layout of the new record, based on the containing simplex, using the associations between example page layouts 10 and vertices created in 1130 and stored in the computer memory 1906 or on the hard disk drive 1910. At step 1250 the process 440 determines a weighting for each example page layout, based on the position of the current record in the containing simplex. Desirably, the interpolation is linear within each simplex, so a point near a vertex has a high weighting for that vertex. Finally, the process 440 calculates at step 1260 the page 15 layout of the new record by combining the example page layouts determined in step 1240 using the weightings calculated in step 1250. The software application then lays out the set of content items on the page using the calculated page layout. The process 440 then ends at step 1299. Fig. 13 is a diagram 1300 showing how a space can be triangulated by creating 20 simplices whose vertices are a specified set of points. A simplex is a region of an n dimensional space defined by (n+1) points. The simplex is formed by all points contained in the convex hull of the (n+1) points. In one-dimensional space, a simplex is a line segment. In two-dimensional space a simplex is a triangular region. In three dimensional space, a simplex is a tetrahedron, and so on. Triangulation is the name 1826285_1 863531_specifinal -20 given to the process of dividing up the convex hull of a set of points in n-dimensional space into simplices. Although the simplices are triangles only in the two-dimensional case, the term triangulation is used for all dimensions. The points form vertices 1310 of the simplices 1330. Facets 1320 of the 5 simplices 1330 are each shared (eg. 1322) between two simplices, unless the facet (eg. 1324) falls on the convex hull of the points 1310. The convex hull is defined in this example as the extremity defined by the outer ones of the facets 1320. Fig. 14 shows how an arbitrary point can be positioned with respect to the simplices 1330. A point in the space can fall inside 1410 a simplex 1330, on the facet 10 1420 of one or two simplices 1330, on a vertex 1430 of one or more simplices, or outside 1440 the convex hull of the simplices 1330. In any Cartesian space, for each vertex of a simplex, there is corresponding opposite facet of the simplex that does not include that vertex. The weighting of a vertex in interpolating a point is calculated as the relative proportion of the perpendicular 15 distance of the point from the opposite facet, to the perpendicular distance of the vertex from the opposite facet. These weightings are referred to as the barycentric coordinates of the point in the simplex, and the sum of the barycentric coordinates is always one. Fig. 15 is a diagram 1500 showing one way to determine the barycentric coordinates of a point P 1410 in a simplex 1330. The simplex 1330 in this example is a 20 triangle, defined by vertices A 1510, B 1520 and C 1530. Each vertex corresponds to one of the example page layouts. The point P 1410 falls inside the simplex 1330. Weightings kA 1550 for several different positions in the simplex 1330 are also shown, indicating what proportion of vertex A 1510 is used in interpolating the page layout for point P 1410. The weighting kA 1550 of vertex A 1510 to be used for interpolating the 1826285_1 863531_speci_final -21 page layout for point P 1410 is calculated as the relative proportion of the perpendicular distance from point P 1410 to the line segment from vertex B 1520 to vertex C 1530, and the perpendicular distance from vertex A 1510 to the line segment from vertex B 1520 to vertex C 1530. The weightings of points B 1520 and C 1530 in interpolating point 5 P 1410 are calculated similarly. Since each vertex corresponds to an example page layout, this approach requires identifying at least two of the example page layouts that are to be used for the interpolation. Fig. 16 is a diagram showing how a linear function value can be interpolated for a point in a simplex. In this example, the domain of the function has two dimensions, Xa 10 and xb, and the function output is a single scalar value, y. The axes 1650 show the relative placement of Xa, Xb and y. The points A 1510, B 1520 and C 1530 form a simplex in the domain. The function values at these points are, respectively, f(A) 1610, f(B) 1620 and f(C) 1630. A point P 1410 in this simplex has barycentric coordinates in terms of the vertices A 1510, B 1520 and C 1530. Applying these as weightings to the 15 function values f(A) 1610, f(B) 1620 and f(C) 1630 and summing them produces the function value f(P) 1640. This value is a linear interpolation between f(A) 1610, f(B) 1620 and f(C) 1630, so it lies on the plane passing through those values. Interpolation for a vector-valued function (a function with multiple output values) is performed the same way for each output value. In the case of interpolation 20 between page layouts, the multiple output values are the coordinates of the edges, vertices or control points of the content regions and other objects on the page. There may be objects on the page that contain static content, and objects that contain no content. For example, boxes, lines, decorative rules and clip-art may be present, and these can also be interpolated between. Fig. 17 is a diagram showing graphically how a 1826285_1 863531_specifinal - 22 page layout for a record can be interpolated from example page layouts for other records. An example page layout 1020 corresponds 1021 to a user defined representation of one data record (seen for example by the title, Title#1), and another example page layout 1030 similarly corresponds 1031 to a representation of another data record (seen for 5 example by the title, Title#2). In the case of Fig. 17, a new page layout 1730 is required to be interpolated for a point halfway between the two records corresponding to those two examples. The interpolation is done on a point-by-point basis. Here an example point 1760 has its position determined by an example point 1740 in example page layout 1020 and another example point 1750 in the other example page layout 1030. The 10 interpolation is performed at the halfway point in this example, and only two examples are used. However, in an n-dimensional input space, up to (n+1) example page layouts can be used, and the weightings for each example depend on the position of the interpolated data record within the simplex defined by the example page layout records. Turning back to Fig. 14, if the input data of a record 1410 to be laid out falls in 15 the interior of a simplex 1330, all of the vertices of that simplex contribute in some proportion to the page layout of that record during interpolation. If the input data of a record 1420 falls on a facet instead of in the interior of a simplex 1330, only vertices on the facet will contribute to the page layout of the record 1420. If the input data of a record 1440 to be laid out falls outside the convex hull of the example record points, the 20 data record point is projected onto the closest point on the convex hull of the example record points, to find the closest point. The interpolation is then performed using the projected point. This is seen in the example of Fig. 14 by the dotted projection line 1442 and the projected point 1444. 1826285_1 863531_specifinal - 23 Advantages of this type offunction-fitting The type of function-fitting described herein has a number of significant advantages. Firstly, certain useful properties of the example page layouts are preserved during interpolation. If a content item (for example, an image) is always shown at the 5 same size, then it will appear at the same size in all page layouts. Similarly, positions of object corners, edges or control points will all remain in the same position if they are the same in each example. Likewise, the horizontal or vertical distances between object edges (vertical or horizontal) will be constant if they are the same in all examples. Moreover, if size, position or relative position values have a maximum value in 10 the examples, then interpolated page layouts will never exceed that maximum. Minimum values will be similarly preserved. These properties are important to achieve an aesthetically pleasing design, and can be explicitly specified in constraint-based layout systems. Using interpolation allows these constraints to be specified implicitly through the examples. 15 These properties are preserved even if the input data for the record to be laid out falls outside the convex hull of the example record data points. This is because the input data point (eg. 1440) is projected onto the convex hull, and the point (eg. 1444) to which the data point 1440 was projected is used to determine the interpolation. Comparative Example 20 Figs. 18A-18C show the sort of behaviour that can result from other forms of function-fitting that use extrapolation for points outside the convex hull of the example data records. Fig. 18A depicts a first example page layout 1810, containing a text region 1811, a second text region 1812, an image region 1813, and a second image region 1814. 1826285_1 863531_speci-final -24 Fig. 18B depicts a second example page layout 1820, containing a text region 1821, a second text region 1822, an image region 1823, and a second image region 1824. Fig. 18C depicts a page layout 1830 generated by a layout function based on the example page layouts 1810 and 1820, containing a text region 1831, a second text region 5 1832, an image region 1833, and a second image region 1834. The generated page layout 1830 has content attributes falling outside the range defined by the example page layouts 1810 and 1820. The interpolation mechanism does not project this point onto the convex hull of the example page layouts 1810 and 1820, and so direct interpolation, as described above, cannot be used. Extrapolation of the large text sizes of 1831 and 1832 10 however causes the first image region 1833 to move off the page, due to the positions of 1813 and 1823 in the examples. The right-hand edges of 1814 and 1824, marked R, are in the same position, so the corresponding edge of 1834 is also in the same position. However, the position of the left edges of 1814 and 1824, marked L, causes the corresponding edge of 1834 to move to the right, past the opposite edge of the region, 15 causing the region to flip. These results (objects displayed off the page, even though all examples show them on the page, and objects flipping) are clearly undesirable and illustrate the unsuitability of extrapolation for page layout. Another desirable property of the form of interpolation described herein is that the page layout of a record depends only on the example page layouts associated with the 20 vertices of the containing (or nearest) simplex. Changes to other example records, or the creation of distant examples do not affect the page layout of the record. There are other forms of function-fitting that could be used. For example, a least-squares best-fit hyperplane can be determined for the specified function values. However, this approach has disadvantages. It does not guarantee that the records used to 1826285_1 863531_speci_final -25 create examples will be laid out exactly as the user laid them out. Also, local behaviour near examples can fall outside the range of behaviour indicated by those examples since the function is being approximated using a hyperplane, and the best fit is determined globally. Also, a change to the function value for any example or the addition of further 5 examples is likely to affect the function behaviour for every point. Since the hyperplane is used to model the example function for all inputs, data records whose attributes fall outside the convex hull of the example records are likely to be laid out badly, because the nature of the hyperplane is for function values to get increasingly extreme the further away the input gets from the examples. 10 Other forms of interpolation may be used. For example, a polynomial surface may be fitted to the example points to allow example records to match the example page layouts. Natural neighbour interpolation, which is also based on triangulation, could alternatively be used. These forms of interpolation provide certain guarantees about curve smoothness which are useful in other fields, but they are not particularly beneficial 15 for page layout interpolation. Because page layouts are viewed independently, rather than as part of a continuum, it is not important that the transition from one simplex to the next be smooth; just that it be continuous. However, producing smoother surfaces using more sophisticated interpolation techniques requires additional processing, resulting in reduced performance. In addition, implicit specification of minimum and maximum 20 positions and offsets is no longer possible. A further disadvantage of smooth interpolation techniques is that the interpolation behaviour within a simplex can change when examples at more distant vertices are changed. Machine-learning techniques such as artificial neural networks are also known to be used to fit functions to example data. Applying these techniques to layout 1826285_1 863531_speci_final - 26 interpolation suffers some of the same problems as the approaches discussed above, such as not matching the user's specified page layout for an example record, and poor behaviour away from the example data. These techniques are also likely to require many examples for training. 5 Extensions There are many ways in which the methods and arrangements disclosed herein can be extended. The described implementation involves the user creating page layouts given real example data, and storing an association between the example page layouts and the content attributes of the example data. However, an alternative approach is to 10 have the user create templates comprising abstract example page layouts, without using real data. The user draws, traces or otherwise creates aesthetically pleasing regions for content within the GUI 300, without using real content, and the content attribute data to associate with the example page layouts is inferred from the example page layouts themselves. For example, if the user draws a text region, the drawn area of the text 15 region is used as a content attribute for that example page layout. Similarly, the size or aspect ratio of a drawn image region could be used as a content attribute for the example page layout. When the page layout of a data record for new content is to be determined from the content and the example page layouts, the content attributes drawn from the content 20 are compared with the attributes inferred from the page layout, and the interpolation process may continue according to the implementations described above. In a variation of this extension, the software application synthesises example content data to be displayed in the content regions, to allow the user to judge the 1826285_1 863531_speci final - 27 aesthetics of the page layout via the GUI 300. For example, a text region could be filled with "Lorem Ipsum" text of an appropriate length. Another extension is to interpolate document features other than position and overall size of objects. Colour, line thickness, transparency, text font size, brightness, 5 saturation and other document features could be interpolated in this way. For example, if one example document contains a yellow object, but the corresponding object on another example document is red, interpolated documents could display the same object in shades of yellow, orange or red. Even features with a discrete nature could be interpolated, with the interpolated values quantised to one of the allowable discrete 10 values. An example of how this might be used is to have a Boolean attribute associated with an object to indicate whether the object should be displayed or not. The object could be used as a decorative "filler" in the space below a column of text, to avoid excess white space in the final document. The position of the object is determined using interpolation according to the above describe implementations, but the "display" 15 attribute is set to "on" in examples with a large space, and to "off' in examples with a small space. During interpolation, points near the example with the object displayed (i.e., examples with a large space) will thus be quantised to switch the object's display attribute to "on", and more distant examples (where the space is small) will be quantised to "off'. 20 Another extension is to allow multiple interpolation functions. For some documents, the user may want to change the page layout significantly (for example, placing one object above another instead of placing them side-by-side) for some content. Simply providing examples in these forms and interpolating between them will produce undesired results, such as overlapping objects, even though none of the examples 1826285_1 863531_specifinal -28 overlapped. In order to allow the user to provide examples with different logical structures for which interpolation is contraindicated, examples could be classified into groups within which interpolation is allowed. Each of these groups may then constitute a distinct layout function. In order to choose which layout function should be used to lay 5 out a particular set of input content items, the user also specifies a layout function expression, which is evaluated for the given data, and whose return value indicates which layout function to use. The combination of the multiple layout functions and the layout function expression form a compound layout function. Typically, each layout function would be responsible for a region of the content attribute space, and the regions 10 for two layout functions would not overlap. In this case, the application software could automatically classify an example as belonging to a given layout function based on the location of its example data in the content attribute space. When the user provides an example that is not consistent with surrounding examples, the application could also create a new layout function containing that example. 15 The preferred implementations use Delaunay triangulation to divide up the space of content attributes, and associate example page layouts with the regions created. However, other mechanisms for dividing the space can be envisaged. Any other (non Delaunay) triangulation mechanism could be used instead to perform a similar function. Other techniques for dividing space, such as quadtrees (and octrees, and higher 20 dimensional analogues of these) or binary space partitioning could also be used as a basis for interpolated layout. 1826285_1 863531_speci_final - 29 INDUSTRIAL APPLICABILITY The arrangements described are applicable to the computer and data processing industries and particularly to the automated or assisted layout of variable data documents and their generation. 5 The foregoing describes only some embodiments of the present invention, and modifications and/or changes can be made thereto without departing from the scope and spirit of the invention, the embodiments being illustrative and not restrictive. (Australia Only) In the context of this specification, the word "comprising" means "including principally but not necessarily solely" or "having" or "including", and 10 not "consisting only of'. Variations of the word "comprising", such as "comprise" and "comprises" have correspondingly varied meanings. 15 1826285_1 863531_speci final

Claims (11)

1. A method of laying out a set of content items on a page, said method comprising the steps of: 5 (a) providing a plurality of example page layouts, each example page layout being associated with example content attributes; (b) selecting at least two example page layouts from the plurality of example page layouts based on attributes of the content items in the set and the example content attributes associated with each example page layout; 10 (c) determining a page layout for the set of content items, by interpolating between the at least two selected example page layouts; and (d) laying out the set of content items on the page using the determined page layout. 15

2. The method according to claim 1, wherein the example content attributes are derived from a set of example content items arranged to form an example page layout.

3. The method according to claim 1, wherein step (b) includes the sub-steps of: (i) using the attributes of the content items in the set to define a point in 20 space representing the set; (ii) using the example content attributes associated with each of the plurality of example page layouts to define points in space representing each example page layout; and 1826285_1 863531_specifinal -31 (iii) selecting the at least two example page layouts based on the position in space of their respective representative points and the point representing the set of content items. 5

4. A method according to claim 3, wherein the at least two example page layouts are selected by creating simplices whose vertices correspond to the points representing each of the plurality of example page layouts, identifying the simplex containing the point representing the set of content items, and selecting the example page layouts corresponding to the vertices of the identified simplex. 10

5. A method according to claim 4, wherein creating simplices comprises creating a Delaunay triangulation of the space.

6. A method according to claim 4, wherein if the point representing the set of 15 content items is not contained within a simplex, identifying the simplex closest to the point representing the set of content items.

7. The method according to claim 1, wherein step (c) includes the sub-steps of: (i) using the attribute of each content item in the set to define a point in 20 space representing the set; (ii) using the example content attributes associated with each of the selected example page layouts to define points in space representing the selected page layouts; and 1826285_1 863531_speci final -32 (iii) interpolating between the at least two selected example page layouts based on weightings, said weightings being determined by the relative position of the point representing the set and each of the points representing the example page layouts. 5

8. A method according to claim 1, wherein for each example page layout, the example content attributes are derived from geometric properties of the example page layout.

9. A method according to claim 1, wherein the plurality of example page layouts 10 belong to one of a plurality of groups of example page layouts, said group being selected based on an attribute of a content item within the set.

10. A computer readable storage medium having a computer program recorded thereon, the program being executable by a computer appratus to lay out a set of content 15 items on a page, said program comprising: code for providing a plurality of example page layouts, each example page layout being associated with example content attributes; code for selecting at least two example page layouts from the plurality of example page layouts based on attributes of the content items in the set and the example 20 content attributes associated with each example page layout; code for determining a page layout for the set of content items, by interpolating between the at least two selected example page layouts; and code for laying out the set of content items on the page using the determined page layout. 1826285_1 863531_specifinal - 33

11. A computer appartus for laying out a set of content items on a page, said program comprising: means for providing a plurality of example page layouts, each example page 5 layout being associated with example content attributes; means for selecting at least two example page layouts from the plurality of example page layouts based on attributes of the content items in the set and the example content attributes associated with each example page layout; means for determining a page layout for the set of content items, by interpolating 10 between the at least two selected example page layouts; and means for laying out the set of content items on the page using the determined page layout. Dated this 30th day of October 2008 15 CANON KABUSHIKI KAISHA Patent Attorneys for the Applicant Spruson&Ferguson 1826285_1 863531_speci final