Computer based document handling systems are generally divided into four broad categories: text editors and word processing systems; formatters; syntax directed editors; and specialized tools. Most systems have features from more than one of these four broad categories in addition to any image processing necessary for editing images. An image processor reads an image of a document using an image input unit, stores it in a memory in the form of image data, and subjects the stored image data to editing operations such as addition and deletion. As one of the editing operations, part of the read document is electronically cut and pasted to a predetermined place in another document. In such an electronic cutting and pasting operation, the document image to be cut and the destination document image are displayed either on a single display unit or on separate display units, and a cutting image portion in the document to be cut and a pasting place in the pasting (destination) document are similarly specified by a mouse, for example. In the related art image processor, the cutting image portion and the pasting place are specified by the operator by selecting appropriate positions while looking at the screen. For this reason, it is not possible to cut or paste figures precisely. Particularly, shifts in position are noticeable when the same patterns must be juxtaposed. U.S. Pat. No. 5,224,181 to Tsutsumi entitled “Image processor” and U.S. Pat. No. 5,202,670 to Oha entitled “Image Processing Apparatus” both discuss image processing generally.
For documents in which presentational considerations are important, the documents must be submitted to a formatter for preparation prior to presentation. Formatters are non-interactive tools that process a document to produce either a display independent or a device dependent layout specification. Documents are submitted to formatters in the form of descriptions on file and they carry out the processing and return the overall results after a certain period of time. High-level formatters work on the basis of a logical description of the document. The user is not required to specify the presentation details desired. The user deals with the logical organization of the document, i.e., the different types of elements that appear in the document, such as, for example, section, paragraph, heading, summary, etc. The formatter handles the layout presentation of these elements. Low-level formatters make it possible to include commands within the document description to enable changes in other characteristics of the document, such as, for example, font, spacing, margins and justification. U.S. Pat. No. 5,438,512 to Mantha et al. entitled “Method and apparatus for specifying layout processing of structured documents” is directed to high-level formatters. Mantha discloses a method and apparatus for specifying layout processing of logically structured documents in computer document handling systems. The Mantha method and apparatus allow the specification of the generic logical structure of the structured document in terms of relational attribute grammars.
Most interactive systems allow the user to see the layout of a document as it is being prepared. These interactive systems also separate the logical structure of the documents from the specification of the presentation details. Typically, interactive systems as well as high-level formatters, use a grammatical notation to describe the logical structure of documents. These logical structures are mostly hierarchical in nature and tree structures are used to represent them.
The need for document processing devices which can generate a layout structure of a document by applying a template (i.e., rules for layout) to a logical structure of the document are apparent with the wide use of microprocessors to process and properly render electronically created or digitally scanned documents, or images as more specifically referred to at times. In general, both of the logical development and the layout of an actual output document are important factors of the document. However, the layout is not necessarily important in the process of producing a document. For example, although the layout is necessary once the contents of a document are determined, in some cases the layout is not considered in the initial stage of document production where the logical development is not clear yet. Furthermore, different layouts may be required for one logical development in some cases; for instance, when the same document needs to be distributed to a plurality of persons or sections. Recognizing the above distinction, there have been proposed techniques of generating a layout representing such structures called “layout structure” from a structure called “logical structure” which represents the chapter construction of a document. The process of generating a layout structure from a logical structure is called a layout process, and is performed by a program (layout processing program) that is incorporated in document processing systems.
In order to generate various forms of layout structures from the same logical structure, the operation of a layout processing program needs to be modified. However, in general, a program itself cannot be modified properly by ordinary users because the modification needs expert knowledge. For this reason, there has been employed a technique of altering a program by using parameters such as “page size is A4” and “double column setting” for textual documents. However, according to this technique, the kinds of specifiable parameters are limited to ones that are preset in the program. Furthermore, to control the operation of a layout processing program having many functions it is necessary to specify a large number of parameters which precludes ordinary users from using such a program. To solve the above problems, there have been proposed techniques of controlling a layout processing program by using, rather than simple parameters, a data structure representing a layout template. One of those techniques is a “generic layout structure” prescribed in the international standards “ODA” (ISO8613, Information Processing-Text and Office Systems-Office Document Architecture (ODA) and Interchange Format (1989)). The ODA only sets forth data structures for representing document structures and guidelines for their use, and does not describe actual layout processes. However, it is apparent that the following functions are needed to perform layout operations according to the ODA. The layout process having the following functions is hereinafter referred to as “ODA layout process.”
(1) Layout processing function based on a layout template (generic layout structure)
(2) Layout process selecting function (top-down or bottom-up)
(3) Reuse of a layout result
(4) Category-based layout processing function
The functions (mechanisms) (1)-(4) are not necessarily effected individually, but could be combined when desired. Combining the functions can improve the efficiency of the layout process.
U.S. Pat. No. 5,381,523 issued to Hayashi entitled “Document processing device using partial layout templates” discloses partial layout templates that are prepared for respective partial logical structures of a hierarchical logical structure of a document. Each partial layout template expresses rules for producing a layout of the corresponding partial logical structure. A partial layout generator produces a partial layout structure by recursively calling itself or by calling a content layout system while referring to the partial layout template, and pours the generated partial layout structure into a lowest-rank frame. A layout of the entire logical structure is produced by sequentially performing the partial layout operations. Hayashi also only relates to a document processing device which can generate a layout structure of a single document by applying a template (i.e., rules for layout) to a logical structure of the single document.
With the growing interest in digital photography and the necessity to lay out and view several digital images as a document, a need still exists for a document/image structuring process which would allow a microprocessor to organize the layout of several images on a sheet-like medium. Needed is a technology that enables a user to gang scan (several images on the scanner platen at once) many images and automatically locate each image, crop them, and correct any rotation errors associated with each image. Resulting images can then be stored individually or as a structured image with a user-defined or simple row-column layout which can be created. A detailed description of Structured Images is provided in U.S. Pat. No. 5,485,568 issued to Venable et al. on Jan. 16, 1996, entitled “Structured Image (SI) format for describing complex color raster images.”
There is a need for technology that will automatically generate the digital equivalent of a photographers contact print sheet in which the segmented images will be scaled and distributed on a resulting page such that each image is scaled as large as possible wherein there is a minimum of white space remaining on the rendered page.
As a first constraint to adequately addressing such a need, all images must be scaled by the same amount, i.e., the relative size of each segmented image stays the same. A second constraint should be in forming the equivalent of a bounding box with minimum white space (space uncovered by an rectangle). Once a solution to the above constraints are found, many images may be scaled by the appropriate amount to make a bounding box the same size as the printable area of paper. It is a feature of the present invention to effectively address the constraints in order to accomplish the desired results described above.
Other advantages and salient features of the invention will become apparent from the detailed description which, taken in conjunction with the drawings, disclose the preferred embodiments of the invention.