Automated method for alignment of document objects

BACKGROUND

The exemplary embodiment relates to document layout. It finds particular application in connection with an automated system and method for aligning objects of a document which takes into account saliency within the object.

Content alignment consists of the organization of the various objects (textual, graphical, and pictorial images) composing a digital document. The purpose of this operation is generally to promote readability and usability of the document by organizing the document object inside a page, so that their content is aligned with the natural eye's scanning patterns.

Graphical designers use intuition and experience in determining where to position text objects and pictorial objects in a document to provide an arrangement which is pleasing to the observer. Where text relates to a pictorial object, the text may be positioned to the left or right of the object, between upper and lower horizontal guidelines corresponding to the top and bottom of the pictorial object. The graphical designer may align the text with a human face, or in the case of an enlarged portrait, the professional designer may align the textual object with the eyes or line of sight of the eyes in the face.

For many applications, such as variable data applications, where either the text or the image may vary in the document, depending on the recipient, such a manually intensive approach may not be cost effective. Automated methods of alignment are available, however, these methods simply center the text between the horizontal guidelines or align it with upper or lower guidelines. Such approaches lack flexibility and can often lead to results which are not aesthetically pleasing to the observer. Object alignment thus remains an operation which is usually performed manually during the document editing.

There remains a need for automated content-based alignment methods which may be utilized in applications such as digital publishing where overall aesthetic quality is highly valued.

<patcit id="pcit0001" dnum="US20090034849A"><text>U.S. Pub. No. 2009/0034849</text></patcit>, discloses an image processing method for cropping first and second images for presentation in a template. The first image has a first feature and the second image has a second feature. The template has first and second image boundary shapes. The method includes determining the locations of the first and second features in the respective images and calculating a constraint on the locations of the first image boundary shape on the first image and the second image boundary shape on the second image. The constraint is based on an alignment criterion specifying the alignment of the first feature in the first image and the second feature in the second image when the first and second images are presented in the template and generating a cropped image combination by placing the first image boundary shape on the first image and the second image boundary shape on the second image according to the constraint.

<patcit id="pcit0002" dnum="US7360157B"><text>U.S. Patent. No. 7,360,157</text></patcit> discloses aligning the contents of document objects on an electronic document page. Organizing a page of document objects so textual content is aligned to natural eye scanning patterns promotes readership and usability. When a user creates a new island of text, the new text can be snapped into alignment with an existing island of text. Invisible guidelines that emanate from textual features in a document object can provide a relative alignment reference that floats with the position of the object on the page. In response to placing a content insertion point ("IP") on an electronic page with an existing document object, the IP can be automatically aligned to the content of the existing document object. A page with several arbitrarily positioned document objects can be automatically rearranged so that the contents of the document objects are each aligned to one another.

The following relate to various methods for saliency detection: <patcit id="pcit0003" dnum="US20080304740A"><text>U.S. Pub. No. 2008/0304740, published December 11, 2008</text></patcit>, entitled Salient Object Detection, by <patcit id="pcit0004" dnum="US20080304708A"><text>Jian Sun, et al.; U.S. Pub. No. 2008/0304708, published December 11, 2008</text></patcit>, entitled DEVICE AND METHOD FOR CREATING A SALIENCY MAP OF AN IMAGE, by <patcit id="pcit0005" dnum="US20080304742A"><text>Olivier Le Meur, et al.; U.S. Pub. No. 2008/0304742, published December 11, 2008</text></patcit>, entitled COMBINING MULTIPLE CUES IN A VISUAL OBJECT DETECTOR, by Jonathan H. Connell; <patcit id="pcit0006" dnum="US20060093184A"><text>U.S. Pub. No. 2006/0093184, published May 4, 2006</text></patcit>, entitled IMAGE PROCESSING APPARATUS, by Motofumi Fukui, et al.; and <patcit id="pcit0007" dnum="US7400761B"><text>U.S. Patent No. 7,400,761, issued July 15, 2008</text></patcit>, entitled CONTRAST-BASED IMAGE ATTENTION ANALYSIS FRAMEWORK, by Ma, et al.

<patcit id="pcit0008" dnum="US20070005356A"><text>U.S. Pub. No. 2007/0005356</text></patcit>, entitled GENERIC VISUAL CATEGORIZATION METHOD AND SYSTEM; <patcit id="pcit0009" dnum="US20070258648A"><text>U.S. Pub. No. 2007/0258648</text></patcit>, entitled GENERIC VISUAL CLASSIFICATION WITH GRADIENT COMPONENTS-BASED DIMENSIONALITY ENHANCEMENT; and <patcit id="pcit0010" dnum="US20080069456A"><text>U.S. Pub. No. 2008/0069456</text></patcit> entitled BAGS OF VISUAL CONTEXT-DEPENDENT WORDS FOR GENERIC VISUAL CATEGORIZATION, all by Florent Perronnin; and <nplcit id="ncit0001" npl-type="s"><text>G. Csurka, C. Dance, L. Fan, J. Willamowski and C. Bray, "Visual Categorization with Bags of Keypoints", ECCV Workshop on Statistical Learning in Computer Vision, 2004</text></nplcit>, disclose systems and methods for categorizing images based on content.

BRIEF DESCRIPTION

In accordance with one aspect of the exemplary embodiment, a method for alignment of objects in a document includes, for an input electronic document, identifying at least first and second objects to be aligned on a page of the document. A one dimensional guideline profile is generated for one or both of the first and second objects based on a detection of saliency for the respective object(s). The first and second objects are aligned based on the guideline profile(s) to form a modified document and the modified document is output. In one embodiment the method further comprises generating a first guideline profile for the first object and a second guideline profile for the second object, the aligning the first and second objects being based on the first and second guideline profiles. In a further embodiment the aligning includes convoluting the first and second guideline profiles to identify a peak and aligning the objects based on a location of the peak. In a further embodiment the aligning includes aligning a peak of the first guideline profile with a peak of the second guideline profile. In a further embodiment one of the first and second objects is a fixed object and the other of the first and second objects is a floating object and the alignment includes moving the floating object. In a further embodiment the first object comprises a pictorial object and the second object comprises a text object.

In accordance with another aspect of the exemplary embodiment, an apparatus for alignment of objects in a document includes computer readable memory which stores an object alignment system including an object detector for identifying first and second objects to be aligned within a document, a profile generator for generating a one dimensional guideline profile for at least the first object based on a detection of saliency for the first object, and an alignment generator for generating an alignment of the first and second objects based on the guideline profile. A processor in communication with the memory implements the object alignment system.

In accordance with another aspect of the exemplary embodiment, a computer implemented method for alignment of objects in a document includes identifying objects to be aligned on a page of an electronic document, assigning an object class to each of the objects selected from a plurality of object classes including a pictorial object class and a text object class, for each object to be aligned, selecting a respective saliency detection method based on the assigned object class, applying the selected detection method for each object to be aligned to generate a saliency representation, generating a one dimensional guideline profile for each object to be aligned based on the saliency representation, aligning at least first and second of the objects based on the respective guideline profiles to form a modified document, including translating one of the first and second objects relative to the other of the first and second objects; and outputting the modified document.

BRIEF DESCRIPTION OF THE DRAWINGS

<figref idref="f0001">FIGURE 1</figref> is a schematic view of a document containing a pictorial object and a text object for which an alignment is sought;

<figref idref="f0002">FIGURE 2</figref> is a flow diagram which illustrates a method of alignment of objects in a document, in accordance with one aspect of the exemplary embodiment;

<figref idref="f0003">FIGURE 3</figref> is a functional block diagram of an exemplary apparatus for alignment of objects in a document, in accordance with another aspect of the exemplary embodiment;

<figref idref="f0004">FIGURE 4</figref> illustrates generating a saliency representation for a textual object;

<figref idref="f0005">FIGURE 5</figref> illustrates an exemplary pictorial object;

<figref idref="f0005">FIGURE 6</figref> illustrates generation of a saliency representation in the form of a saliency map for the pictorial object of <figref idref="f0005">FIGURE 5</figref>, when classified as a Non-Person pictorial image, in accordance with one aspect of the exemplary embodiment;

<figref idref="f0005">FIGURE 7</figref> illustrates generation of a guideline profile for the pictorial object of <figref idref="f0005">FIGURE 5</figref>, generated from the saliency map of <figref idref="f0005">FIGURE 6</figref>;

<figref idref="f0006">FIGURE 8</figref> illustrates generation of a guideline profile for a pictorial object classed as Person;

<figref idref="f0007">FIGURE 9</figref> illustrates aligning objects based on their guideline profiles;

<figref idref="f0008">FIGURE 10</figref> illustrates convolution of two guidelines profiles (pictorial object and text object); and

<figref idref="f0009">FIGURE 11</figref> illustrates re-alignment of a text object with a pictorial object classed as person.

DETAILED DESCRIPTION

The exemplary embodiment relates to an apparatus, method, and computer program product for aligning objects in a document. The exemplary alignment method is generic in the sense that it can be used on a multiplicity of document objects characterized by different content, visual aspect, and the like.

The method employs a measure of saliency in determining an appropriate alignment between two objects, such as a pictorial object and a text object. Saliency detection is seen as a simulation or modeling of the human visual attention mechanism. It is understood that some parts of an image receive more attention from human observers than others. Saliency refers to the "importance" or "attractiveness" of the visual information in an image. The aim of most saliency detection methods is to assign a high saliency to a region or regions of an image that is/are likely to be a main focus of a typical viewer's attention. Many of these methods are based on biological vision models, which aim to estimate which parts of images attract visual attention. Implementation of these methods in computer systems generally fall into one of two main categories: those that give a number of relevant punctual positions, known as interest (or key-point) detectors, such as corner (Harris) or blob (Laplace) detectors and face detectors, and those that give a more continuous map of relevance, such as saliency maps. However, there are also hybrid approaches which aim to provide a combination of the key-point and continuous methods. The exemplary embodiment is not limited to any particular type of saliency detection method. In one embodiment, the detection method is selected based on an evaluation of the type of object (text or pictorial) and/or its content. For example, a saliency map can be a probability map that takes into account the content of the object. In embodiments described herein, two (or more) types of saliency detection may be employed, and the results combined.

Exemplary saliency detection methods which may be used herein include those described in the following references: Above-mentioned <patcit id="pcit0011" dnum="US400277A"><text>U.S. Patent Application Ser. Nos.: 12/400,277</text></patcit>, <patcit id="pcit0012" dnum="US12250248A"><text>12/250,248</text></patcit>, and <patcit id="pcit0013" dnum="US12033434A"><text>12/033,434</text></patcit>; <patcit id="pcit0014" dnum="US20080304740A"><text>U.S. Pub. Nos. 2008/0304740</text></patcit>, <patcit id="pcit0015" dnum="US20080304708A"><text>2008/0304708</text></patcit>, <patcit id="pcit0016" dnum="US20080304742A"><text>2008/0304742</text></patcit>, <patcit id="pcit0017" dnum="US20060093184A"><text>2006/0093184</text></patcit>, <patcit id="pcit0018" dnum="US7400761B"><text>U.S. Patent No. 7,400,761</text></patcit>; and in <nplcit id="ncit0002" npl-type="s"><text>L. Itti, C. Koch, E. Niebur, et al., "A Model of Saliency-Based Visual Attention for Rapid Scene Analysis." IEEE Transactions on Pattern Analysis and Machine Intelligence, 20(11):1254-1259 (1998</text></nplcit>); <nplcit id="ncit0003" npl-type="s"><text>Xiaodi Hou and Liqing Zhang, "Saliency Detection: A Spectral. Residual Approach," IEEE Conf on Computer Vision &amp; Pattern Recognition (2007</text></nplcit>); <nplcit id="ncit0004" npl-type="s"><text>D. Gao and N. Vasconcelos, "Bottom-up saliency is a discriminant process", Proceedings of IEEE Int'l Conf. on Computer Vision (ICCV), Rio de Janeiro, Brazil (2007</text></nplcit>); <nplcit id="ncit0005" npl-type="s"><text>D. Gao, V. Mahadevan and N. Vasconcelos, "The discriminant center-surround hypothesis for bottom-up saliency," Proc. of Neural Information Processing Systems (NIPS), Vancouver, Canada (2007</text></nplcit>); <nplcit id="ncit0006" npl-type="s"><text>Jones, M.J., Rehg, J.M., "Statistical Color Models with Application to Skin Detection," IJCV(46), No. 1, pp. 81-96 (January 2002</text></nplcit>); <nplcit id="ncit0007" npl-type="s"><text>L. Itti and C. Koch, "Computational Modeling of Visual Attention," Nature Reviews Neuroscience, 2(3): 194-203 (2001</text></nplcit>), hereinafter "Itti and Koch"; <nplcit id="ncit0008" npl-type="s"><text>Chen-Hsiu Huang, Chih-Hao Shen, Chun-Hsiang Huang and Ja-Ling Wu, "A MPEG-7 Based Content-aware Album System for Consumer Photographs," Bulletin of the College of Engineering, NTU, No. 90, pp. 3-24 (Feb. 2004</text></nplcit>); <nplcit id="ncit0009" npl-type="s"><text>T. Liu, J. Sun, N. Zheng, X. Tang and H. Shum, "Learning to Detect A Salient Object," CVPR (2007</text></nplcit>); and <nplcit id="ncit0010" npl-type="s"><text>Z. Wang, B. Li, "A Two-Stage Approach to Saliency Detection in Images," In ICASSP 2008 IEEE Intl. Conf. on Acoustics, Speech, and Signal Processing (ICASSP) (March/April 2008</text></nplcit>).

With reference to <figref idref="f0001">FIGURE 1</figref>, an exemplary page of an electronic document <b>10</b> is graphically illustrated. The document includes a template <b>12,</b> which determines the relationship of height to width of a digital document (or a page of the document), which is to be output, e.g., by printing or displaying on a screen. The digital document <b>10</b> may comprise one or more pages or may comprise a video (sequence of images) in which a text object is to be inserted into each of a sequence of the images. One or more objects <b>14, 16</b> are to be arranged on the document template <b>12,</b> which when printed, form the same page of the document. The objects <b>14, 16,</b> etc. each have a defined boundary (bounding box) with defined height and width (<i>h₁, w₁,</i> and <i>h₂, w₂,</i> respectively). For each object, upper and lower guidelines (<i>UG₁, LG₁, UG₂, LG₂</i>) define the locations of top and bottom edges of the object respectively. The guidelines <i>UG₁</i>, <i>LG₁</i> are spaced by distance <i>h₁,</i> in the case of object <b>14,</b> and guidelines <i>UG₂</i>, <i>LG₂</i> by <i>h₂,</i> in the case of object <b>16.</b> Alternatively or additionally, left and right guidelines define left and right edges of the object, and are spaced by distances <i>w₁</i> and <i>w₂</i>, respectively.

One or more of the objects may be labeled as a fixed object, such as pictorial object <b>14.</b> By "fixed", it is meant that the object is not free to move, horizontally or vertically on the template <b>12.</b> One or more of the objects, such as text object <b>16,</b> is labeled as a floating object, by which it is meant that the object is translatable on the template <b>12,</b> in at least one dimension, here the vertical dimension (i.e., in a direction aligned a side edge of the template which defines the height of the template). However, it is also contemplated that an object may be free to move in more than one dimension, such as mutually perpendicular dimensions, or in a direction which is intermediate horizontal and vertical.

The exemplary method provides an alignment of two or more of the objects, such as the objects <b>14, 16</b> in the document template <b>12</b> which takes into account saliency of one or both of the objects <b>14, 16.</b> The alignment is achieved by translation of a floating object. In the case of a vertical alignment, for example, after alignment, one or both of the upper and lower guidelines of the object having the smaller height (object <b>16</b> in this example) lie between the upper and lower guideless of the object <b>14</b> having the larger height. However, the exact position between upper and lower guidelines <i>UG₁</i> and <i>UG₂</i> is a function of the detected saliency of one or both objects.

The objects <b>14, 16</b> for the document may be already positioned on the template as part of a workflow process, but without any consideration as to their spatial arrangement. For example, the top of the first object <b>14</b> may be automatically aligned with a top of the second object <b>16.</b>

Exemplary object <b>14</b> is a pictorial object. A pictorial object can be a photographic image, which depicts something in the real world. A graphical element can be a graph, chart, line drawing, or the like, and in some embodiments, may be treated like a pictorial object. Both of these types of objects generally have visual features which can be detected through saliency detection methods. As will be appreciated, while the pictorial objects exemplified in the accompanying drawings (<figref idref="f0005">FIGS. 5</figref>, <figref idref="f0006">8</figref>, and <figref idref="f0007">9</figref>) are shown as line drawings, these are intended to represent photographic images (e.g., color photographic images), for which the representative data shown in the FIGURES may be obtained. Object 16 is a text object, which predominantly comprises a text sequence in a natural language which has been generated using characters from a predefined character set and one or more selected fonts. Although text objects may have some salient features, such as enlarged text portions or unusual text, such as equations, in some embodiments, each "on" pixel can be considered as being equal in saliency.

The objects <b>14, 16</b> may be in any suitable format, such as PDF, JPEG, PDF, GIF, JBIG, BMP, TIFF, or other common file format used for images and which may optionally be converted to another suitable format prior to processing. While the exemplary document shown in <figref idref="f0001">FIGURE 1</figref> has a text object 16 and one pictorial object <b>14,</b> it is to be appreciated that the method is applicable to documents with various numbers of each type of object. Each object may comprise an array of pixels, each pixel being associated with a colorant value, or in the case of a multicolor image, with several colorant vales, one for each color separation. The term "pixel" as used herein is intended to denote "picture element" and encompasses image elements of two-dimensional images or of three-dimensional images (which are sometimes also called voxels to emphasize the volumetric nature of the pixels for three-dimensional images). The height h and width w of the objects may be expressed as a number of pixels of the template, as may their x,y coordinates, relative to side and top edges of the template.

<figref idref="f0002">FIGURE 2</figref> illustrates an exemplary method for aligning objects in documents. The method begins at S100 with the input of a digital document containing document objects, such as objects <b>14, 16.</b>

At S102, document objects (pictorial and textual) are automatically detected. Fixed and floating objects are separately identified.

At S104, the detected objects are classified based on their content. In particular, the object is classified according to object type (pictorial, text, etc.) and may be further categorized within these types.

At S106, depending on the types/categories of object detected, a saliency representation of each object is generated, such as a saliency map or other representation. Various detectors may be used, for example, based on a type/category of the object.

At S108, at least one function (guideline profile) indicating a one dimensional (e.g. vertical) saliency of the respective object, is generated based on the output(s) of the saliency detectors.

At S110, a translation of at least a first of the objects relative to a second of the objects is computed based on the guideline profile(s), e.g., by minimizing a cost function determined from the guideline profiles or by bringing maxima of the guideline profiles into alignment.

At S112, a realignment of the objects is performed, by adjusting the relative positions of the objects, based on the function. For example, the text object <b>16</b> is re-positioned to an optimal position relative to the fixed pictorial object <b>14.</b>

At S114, the modified document is output.

The method ends at S116.

<figref idref="f0003">FIGURE 3</figref> illustrates an exemplary apparatus for alignment of objects <b>14, 16</b> in a document, which may be used in performing the exemplary method described above. The apparatus may be embodied in an electronic processing device, such as the illustrated computer <b>20.</b> In other embodiments, the electronic processing device <b>20</b> may include one or more specific or general purpose computing devices, such as a network server, Internet-based server, desk top computer, laptop computer, personal data assistant (PDA), cellular telephone, or the like. The apparatus <b>20</b> includes an input component <b>22,</b> an output component <b>24,</b> a processor <b>26,</b> such as a CPU, and memory <b>28.</b> The computer <b>20</b> is configured to implement an object alignment system <b>30,</b> hosted by the computer <b>20,</b> for aligning objects, such as pictorial and text objects, in an original input document. The object alignment system <b>30</b> may be in the form or software, hardware, or a combination thereof. The exemplary object alignment system <b>30</b> is stored in computer readable memory <b>28</b> (e.g., in a non-volatile portion of computer memory <b>28</b>) and comprises instructions for performing the exemplary method described above with reference to <figref idref="f0002">FIGURE 2</figref>. These instructions are executed by the processor <b>26.</b> Components <b>22, 24, 26, 28</b> of the computer <b>20</b> may be connected for communication with each other by a data/control bus <b>34.</b> Input and output components may be combined or separate components and may include, for example, data input ports, modems, network connections, and the like.

The computer <b>20</b> is configured for receiving a digital document to be processed, such as document <b>10,</b> e.g., via input component <b>22,</b> and storing the document <b>10</b> in memory, such as a volatile portion of computer memory <b>28,</b> while being processed by the object alignment system <b>30.</b> The document 10 is transformed by the object alignment system <b>30,</b> e.g., by rearrangement of the objects within it. The computer <b>20</b> is also configured for storing and/or outputting a modified document <b>36</b> generated from the input document <b>10</b> by the object alignment system <b>30.</b> The modified document <b>36</b> may be output to another component of a workflow processing system (not shown) which performs further operations on the modified document <b>36,</b> and/or to an image output device <b>38, 40.</b> For example, the computer <b>20</b> may include or be in data communication with a printer <b>38,</b> for rendering the document <b>36</b> on print media, such as paper, with colorants, such as inks or toners and/or a display <b>40,</b> such as an LCD screen, for displaying the modified document on a screen.

The document <b>10</b> can be input from any suitable source <b>50,</b> such as another component of a workflow process, which may be resident in the computer <b>20,</b> or an external source, such as a workstation, database, scanner, or memory storage device, such as a disk, memory stick, or the like. In the case of an external source <b>50,</b> it may be temporarily or permanently communicatively linked to the computer <b>20</b> via a wired or wireless link <b>52,</b> such as a cable, telephone line, local area network or wide area network, such as the Internet, through a suitable input/output (I/O) connection <b>22,</b> such as a modem, USB port, or the like.

In the case of a computer <b>20,</b> processor <b>26</b> may be the computer's central processing unit (CPU). However, it is to be appreciated that the exemplary method may be implemented on one or more general purpose computers, special purpose computer(s), a programmed microprocessor or microcontroller and peripheral integrated circuit elements, an ASIC or other integrated circuit, a digital signal processor, a hardwired electronic or logic circuit such as a discrete element circuit, a programmable logic device such as a PLD, PLA, FPGA, or PAL, or the like. In general, any processor, capable of implementing a finite state machine that is in turn capable of implementing the flowchart shown in <figref idref="f0002">FIGURE 2</figref>, can be used to implement the method for alignment of objects.

Memory <b>28</b> may be in the form of separate memories or combined and may be in the form of any type of tangible computer readable medium such as random access memory (RAM), read only memory (ROM), magnetic disk or tape, optical disk, flash memory, holographic memory, or suitable combination thereof.

As shown in <figref idref="f0003">FIGURE 3</figref>, the object alignment system <b>30</b> includes various processing components <b>60, 62, 64, 66, 68</b> for performing the exemplary method.

In particular, an object detector <b>60</b> detects document objects and whether or not they are fixed or floating, with respect to a particular dimension. A saliency detector selector <b>62</b> identifies an appropriate saliency detection method. Selector <b>62</b> communicates with an object type classifier <b>70</b> and an image type classifier <b>72.</b> Classifier <b>70</b> assigns an object type to each object. Classifier <b>72</b> assigns a pictorial image category to objects classed as pictorial images. Both classifiers <b>70, 72</b> may be trained with training sets of objects containing positive and optionally negative examples of the different types and categories of objects. The saliency detector selector <b>62</b> selects the appropriate saliency detection method for each object based on the output of classifiers <b>70, 72.</b> For example, <figref idref="f0003">FIGURE 3</figref> shows three saliency detectors <b>74, 76, 78</b> by way of example. Selector calls the appropriate one of the saliency detectors for each image which generates a saliency representation for the object in question. A profile generator <b>64</b> takes the saliency representation and generates a guideline profile indicating a one dimensional (e.g. vertical) saliency of the respective object based thereon. An alignment generator <b>66</b> computes a translation for one or both objects to bring them into an optimal alignment, based on the guideline profiles.

An object repositioner performs the realignment of the objects, e.g., by storing new coordinates for one or both objects and outputs the modified document. The new coordinates may be stored as tags, such as HTML tags, or in a file which accompanies the document.

Further details of the apparatus and method now follow.

DOCUMENT OBJECT DETECTION:

(S102)

At S102, all objects composing the document are identified and located in the page. For detection of objects within the document, direct and indirect methods exist. If the document is in an open format, such as XSL-FO (Extensible Stylesheet Language Formatting Objects, which is a language for formatting XML data) this step can be carried out directly. Apache FOP, for example, is an open source print formatter driven by XSL formatting objects (XSL-FO) and an output independent formatter. The application reads a formatting object (FO) tree and renders the resulting pages in a specified output format, such as PDF, PS, PCL, AFP, XML, or the like. See, also, <nplcit id="ncit0011" npl-type="s"><text>Xiaofan Lin, Active Document Layout Synthesis, 8th International Conference on Document Analysis and Recognition, Seoul, Korea (2005</text></nplcit>); <nplcit id="ncit0012" npl-type="s"><text>Itti and Koch, "A saliency-based search mechanism for overt and covert shifts of visual attention." Vision Research, v. 40. 1489-1506 (2000</text></nplcit>).

For other documents, indirect methods can be used. Examples of indirect methods are described in <nplcit id="ncit0013" npl-type="s"><text>K.Y. Wong, R.G. Casey, F.M. Wahl, "Document analysis system," IBM Journal of Research and Development (1982</text></nplcit>); and <nplcit id="ncit0014" npl-type="s"><text>George Nagy, "Twenty years of document image analysis in PAMI," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 22, No. 1, (January 2000</text></nplcit>). For example, a document may be binarized into black and white pixels and various features used to characterize each block of black pixels.

For each detected object <b>14, 16,</b> the location of the centre of mass c<i>₁, c₂</i> and the maximum height and width (<i>h₁, w₁</i>, and <i>h₂, w₂,</i> respectively), are determined (<figref idref="f0001">FIG 1</figref>).

DOCUMENT CLASSIFICATION:

(S104)

Each of the objects <b>14, 16</b> may be classified into one of a plurality of classes. In the exemplary embodiment, three main classes are used: text islands, pictorial images (e.g., photographic), and graphic elements. For pictorial images and graphical images, an additional classification step is carried out.

In evaluating the type of the object, a classifier <b>70</b> may be used to assign each object into one of a set of object classes. Alternatively, the object is assigned to a class based on tags associated with the object or document. In this case, S104 comprises reading the tags to identify the class to which the object is to be assigned. While in the exemplary embodiment, three classes are employed: textual, graphical, and pictorial objects, other classes may be used.

For graphical images, the image can be classified using an automatic method such as a Generic Visual Categorizer (GVC). This step can be useful to understand the content of the image and use it as <i>a priori</i> information to tune the next steps better.

For the objects classed as pictorial images, a further investigation may be performed to evaluate the content of the image. For this step, a categorizer <b>72,</b> or set of categorizers, may be trained to assign one of a set of content-based classes to the pictorial image. The categorizer may be pre-trained with images which have been manually labelled according to class. For example, a generic visual classifier (GVC) can be used to classify the images in different categories such as two or more of people, images with no-faces, buildings, sky, seascapes, landscapes, and the like. Exemplary classifiers are disclosed, for example, in above-mentioned <patcit id="pcit0019" dnum="US20070005356A"><text>U.S. Pub. Nos. 2007/0005356</text></patcit>, <patcit id="pcit0020" dnum="US20070258648A"><text>2007/0258648</text></patcit>, and <patcit id="pcit0021" dnum="US20080069456A"><text>2008/0069456</text></patcit>, the disclosures of which are incorporated herein in their entireties by reference. For example, a simplified system may employ three categories, such as sky, people, and no-people (or simply a people/no people classifier).

Each object can thus be tagged with a label representing it object class (graphical, pictorial, or text) and, in the case of a pictorial object, a label representing its content-based category (sky, people, or no-people).

SALIENCY DETECTION:

(S106)

For each detected object, a distribution (guideline profile) is determined. The guideline profile indicates good vertical position(s) for an alignment guideline. Three different methods for determining distributions are contemplated, accordingly to the label of the object:

For Textual Objects, the detector <b>74</b> generates a simple Chi-Squared distribution parameterized accordingly to the dimensions of the object. For example, as shown in <figref idref="f0004">FIGURE 4</figref>, the distribution <b>80</b> can be used as the guideline profile fro text object <b>14.</b> This can be used to approximate the guideline profile for text. Or, the geometric center of the text box can be used.

For Image Objects, classed as No-People: (i.e., for generic images which do not contain faces, a conventional saliency map may be employed (see, for example <nplcit id="ncit0015" npl-type="s"><text>Itti and Koch, "A saliency-based search mechanism for overt and covert shifts of visual attention." Vision Research, v. 40. 1489-1506 (2000</text></nplcit>). For example, <figref idref="f0005">FIGURE 5</figref> shows an exemplary object <b>14,</b> in this case, a pictorial image which has been categorized as no-people. <figref idref="f0005">FIGURE 6</figref> shows a saliency representation of the image forming object <b>14</b> in terms of a saliency map <b>82.</b> The image is divided into small regions. In <figref idref="f0005">FIGURE 6</figref>, for example, a grid is shown which is made up of 32x22 rectangular regions. Each region is assigned a saliency value, which in the illustrated FIGURE, is represented on a graduated scale (e.g., a set of gray scale values) where white indicates high saliency and black, low saliency. The detector <b>74</b> used has placed high saliency values on the regions falling in the bright regularly shaped regions on either side of the statue. A guideline profile <b>84</b> is generated by averaging each row over the horizontal axis to retrieve the vertical guideline profile, as illustrated in <figref idref="f0005">FIGURE 7</figref>. This type of saliency detection method may also be used for graphical elements and pictorial images not assigned to a "people" class. Alternatively, a specifically tailored saliency detector may be used.

For Image Objects that are labelled with the People category, a face detector <b>78</b> may be used, such as a Viola-Jones face detector (see, <nplcit id="ncit0016" npl-type="s"><text>P. Viola and M. Jones. "Robust real-time face detection." International Journal of Computer Vision (IJCV) 57(2) 137-154 (2004</text></nplcit>)). This method assumes that the face is the most salient region of the image. <figref idref="f0006">FIGURE 8</figref>, for example, illustrates a people categorized object <b>14</b> in which a face has been detected (within circle <b>86</b>) A position of the eyes can be retrieved using a simple calculation on the face size (shown by line <b>88</b>). Alternatively, more complex approaches aimed at directly detecting the position of the eyes can be employed (See, for example, <nplcit id="ncit0017" npl-type="b"><text>G.C. Feng, P.C. Yuen, "Multi-cues eye detection on gray intensity image," Pattern Recognition, Elsevier (2001</text></nplcit>)). Once the vertical position of the eyes is detected, a Gaussian distribution <b>90</b> can be centered on the estimated vertical height of the eyes and parameterized in relation to the face size. The Gaussian distribution can be used as the guideline profile.

In other embodiments, a hybrid approach may be employed. For example, two saliency maps are generated, one based on face detection and the other using a conventional saliency map and the results combined to obtain a combined saliency map which is used to generate the profile.

In yet another embodiment, saliency can be detected for all types of pictorial image using the method described in above-mentioned Application Serial No. <patcit id="pcit0022" dnum="US12400277B"><text>12/400,277</text></patcit>. In this approach, the object is compared with objects (images) in a large set of stored objects to retrieve a set of the most similar stored objects. Each stored object has a region of interest manually labeled. Using the regions of interest of the retrieved set of objects as positive (salient) examples, a classifier is trained to classify regions in the object <b>14</b> as salient or non salient, resulting in a saliency map which is content driven.

GUIDELINE PROFILE EVALUATION:

(S108)

As discussed above, for each object <b>14, 16,</b> vertical and horizontal alignment profiles <b>80, 84, 90</b> (guideline profiles) are estimated to facilitate the alignment between two document objects. These profiles consist of distributions indicating the likelihood that an alignment guideline <b>94, 96</b> (<figref idref="f0007">FIGURE 9</figref>) should be placed in a specific vertical position to reflect aesthetic and/or perceptual criteria. In <figref idref="f0007">FIGURE 9</figref>, the alignment guidelines are placed at the distribution maxima. The profile can be smoothed or otherwise processed to ease computation. For example, where there is more than one peak in the distribution, as shown in <figref idref="f0005">FIG 7</figref> (peaks P₁ and P₂), the smaller peak(s) may be omitted from the guideline profile <b>84</b> (<figref idref="f0007">FIGURE 9</figref>).

Alternatively, a convolution <b>98</b> (multiplication) of the two guideline profiles (here guidelines <b>80</b> and <b>84</b>) can be computed as illustrated in <figref idref="f0008">FIGURE 10</figref>, and then the maximum can be evaluated to define the realignment point <b>100.</b> Here, the maximum of the largest peak is taken as the alignment guideline. Note that in <figref idref="f0008">FIGURE 10</figref>, the guideline profiles and convolution are arranged horizontally rather than vertically.

OBJECT RE-ALIGNMENT:

S110, S112

Based on the guidelines profiles, the objects are re-aligned, e.g., by minimizing a cost function.

Object realignment may be carried out by shifting one or both objects relative to the other. If the position of one object is fixed, such as the pictorial object <b>14</b> in <figref idref="f0007">FIGURE 9</figref>, and the other <b>16</b> is free to move (floating), then the floating object is shifted vertically so that its alignment guideline coincides with the alignment guideline of the other object. This can be performed very simply by computing the vertical difference <i>s</i> b etween the two maxima of the two guideline profiles (i.e., the distance between the two alignment guidelines <b>94</b> and <b>96</b>). Then floating object <b>16</b> is moved vertically by a distance <b>s</b> in the direction of arrow <i>A</i> such that the alignment guidelines <b>94</b> and <b>96</b> are horizontally aligned (colinear). The new position of the object <b>16</b> in the document page <b>10</b> is stored. Alternatively, as noted above, the convolution <b>100</b> of the two guidelines can be computed and its maximum used as the realignment point.

While the exemplary embodiment has been described with particular reference to the alignment of a pictorial object with a text object, it is to be appreciated that the method is also applicable to alignment of a first object with a second object, the first and second objects being independently selected from the group consisting of a text object, a pictorial object, a graphical object, a textual object, and objects which are combinations thereof. Further, it is contemplated that a first object may be vertically aligned with a second object and also horizontally aligned with a third object. Further, it is contemplated that a first object may be vertically or horizontally aligned with two or more other objects, for example, by aligning a second object with a first peak of an alignment profile of the first object and aligning a third object with a second peak of the first object's alignment profile. In yet another embodiment, the system may generate a horizontal and a vertical alignment profile for first and second objects and propose either a horizontal or vertical alignment of the two objects based on which fits best on the page. While the borders of the exemplary objects <b>14, 16</b> are spaced apart from each other, in other embodiments it is contemplated that a floating first object may be wholly or partly overlapping a second object, e.g., contained within it.

The method illustrated in <figref idref="f0002">FIGURE 2</figref> may be implemented in a computer program product that may be executed on a computer. The computer program product may be a tangible computer-readable recording medium on which a control program is recorded, such as a disk, hard drive. Common forms of computer-readable media include, for example, floppy disks, flexible disks, hard disks, magnetic tape, or any other magnetic storage medium, CD-ROM, DVD, or any other optical medium, a RAM, a PROM, an EPROM, a FLASH-EPROM, or other memory chip or cartridge, or any other medium from which a computer can read and use. Or the program may be in the form of a transmittable carrier wave in which the control program is embodied as a data signal transmission media, such as acoustic or light waves, such as those generated during radio wave and infrared data communications, and the like.

The exemplary method may be implemented on one or more general purpose computers, special purpose computer(s), a programmed microprocessor or microcontroller and peripheral integrated circuit elements, an ASIC or other integrated circuit, a digital signal processor, a hardwired electronic or logic circuit such as a discrete element circuit, a programmable logic device such as a PLD, PLA, FPGA, or PAL, or the like. In general, any device, capable of implementing a finite state machine that is in turn capable of implementing the flowchart shown in <figref idref="f0002">FIGURE 2</figref>, can be used to implement the method for aligning document objects.

APPLICATIONS

The exemplary system and method find application in variable data applications such as one-to-one personalization and direct mail marketing. Variable document creation poses various challenges to the assurance of a proper aesthetical level due the portion of dynamic content typically included. One challenge is how to treat visual aspects dynamically within the variable data workflow, so that enhancement or management operations are handled in a more context sensitive fashion. The exemplary method helps to address this in the alignment of document objects based on semantic content.

Other applications, such as image and document asset management and document image/ photograph set visualization, and the like can also profit from the alignment of objects (e.g., photofinishing).

Without intending to limit the scope of the exemplary embodiment, the following examples demonstrate the application of the exemplary method.

EXAMPLE

An automated prototype system, developed as described above, was used to compute an appropriate position for a floating text island <b>16</b> for the object <b>14</b> shown in <figref idref="f0006">FIGURE 8</figref>. The system correctly positioned the text island vertically at about eye level of the person, as exemplified approximately in <figref idref="f0009">FIGURE 11</figref>. This is more aesthetically pleasing than a conventional system which may align the tops or bottoms of the objects. It will be appreciated that various of the above-disclosed and other features and functions, or alternatives thereof, may be desirably combined into many other different systems or applications.