Image analysis – Image transformation or preprocessing – Changing the image coordinates
Reexamination Certificate
1999-03-01
2003-08-26
Mehta, Bhavesh (Department: 2625)
Image analysis
Image transformation or preprocessing
Changing the image coordinates
C382S305000
Reexamination Certificate
active
06611631
ABSTRACT:
The present invention relates generally to data management and more particularly to methods and apparatus for managing data for rotated or skewed images.
BACKGROUND OF THE INVENTION
The present invention is directed to applications having graphical objects that are sampled images, or slices of sampled images. A sampled image (or image) can be defined in a source space that includes sequentially ordered source samples arranged in source rows. Data management of the image may be complicated by the application of one or more transformations for transforming the source image into a different device space. For example, in a printer or other display device, it is often required to receive a sampled image from some source, store it in an intermediate data store (e.g., a computer's random access memory or a file on a computer's file system), and then render it using a transformation matrix into the device space of a raster device.
The sampled image can be defined in a source space which comprises a two-dimensional orthonormal coordinate system in which the samples of the sampled image form a square lattice. The x-axis in source space is oriented along the fast scan direction of the sampled image, that is, the direction of the typical linear ordering of sequential samples into rows. The y-axis in source space is oriented along the slow scan direction of the sampled image, that is, the direction of the typical linear ordering of sequential rows. In the printer example described above, the image data is often very large, and usually received by the data store in sequential source rows, which may be grouped into slices. A source row is a sequential row of samples in a sampled image, spanning the entire width of the sampled image. A slice is a group of sequential source rows.
The raster device can be defined in a device space which comprises a two-dimensional orthogonal coordinate system in which the raster elements of the raster device form a rectangular lattice. The x-axis in device space is oriented along the fast scan direction of the raster device, that is, the direction of the typical linear ordering of sequential raster elements into rasters (scan lines). The y-axis in device space is oriented along the slow scan direction of the raster device, that is, the direction of the typical linear ordering of sequential rows (scan lines) of rasters.
Rendering is a process for visually displaying a sampled image by converting it into raster elements on a raster device.
The conversion includes an affine coordinate transformation from source space into device space. The transformation may include many forms of “rotation” including translation, scaling, shearing, as well as a conventional rotation, and combinations of these. An affine coordinate transformation is a geometric transformation of a coordinate system (as a translation, rotation, or a uniform stretching) that carries straight lines into straight lines and parallel lines into parallel lines, but may alter distances between points and angles between lines.
When source space and device space are not aligned, then the rendering of a sampled image from the source to the raster device results in a rotated image. A rotated image includes an affine coordinate transformation from source space into device space, such that the x-axis in source space is carried into device space with an orientation not parallel or aligned with the x-axis in device space. The transformation of the source image to device space may result in numerous data management issues.
Many raster devices are managed in bands. The data store required to support the raster elements of a typical four-color halftoned bi-level raster device at 1440 dpi resolution is almost a megabyte per square inch. Thus, to manage an entire A4-size page of raster data for such a device might require approximately a 90 MB data store, which is a prohibitive amount in many applications. However, to manage only a band at a time of raster data takes a much smaller data store; for example a band 512 scan lines high and the width of an A4 page, on the same device, would require approximately only a 3 MB data store.
Banded raster devices are implemented with a variety of techniques, which are fairly well known in the printer industry. Generally speaking during the render process, bands are rendered sequentially, then delivered to the raster device in order. But the graphical objects to be rendered onto the page are not necessarily received by the render engine in the same order as required for sequential band rendering. A display list can be used to store all graphical objects to be rendered onto the page, until it is certain that all objects to be rendered onto a specified band are stored. Then that band may be rendered. In this case, the data store (or image store) may be considered logically part of the display list, although it may be physically part of or separate from the data store used for the display list.
If a sampled image is rendered without rotation, that is with source rows parallel to raster device scan lines, then it is relatively easy to manage the image store incrementally. As each band is rendered, the source slices intersecting that band and not intersecting any other un-rendered bands may be discarded, freeing up a portion of the data store to receive new data.
When the sampled image is rotated, data management of the image data becomes much more difficult. For example, in the nominal worst case the image may be designated to be rotated ninety degrees, so that the source rows are rendered perpendicular to raster device scan lines. In this case, each slice of the source unrotated image intersects potentially many or all bands, and each affected band intersects all slices. There is no opportunity for incremental management of the data store, since as long as any of the image data must be stored, it all must be stored.
Another data management problem may arise when transporting image data from one data store to another. For example, in a distributed system, a process receiving a sampled image may be physically or logically separated from the rendering process. In this case, the image data must be transported from one process to the other, by sending the data over a communication channel, or by exchanging data pointers via a computer technique called inter-process communication (IPC). Regardless of the means of transport, it is often desirable to transport the image data incrementally, where the preferred increment is a band. Where, the image data associated with an output band spans a large number of the source rows associated with the sampled image, the incremental transport requires the maintenance of all of the data in the data store throughout the transport.
Data management can also affect the efficiency of a rendering process. On banded raster devices, image data is typically rendered a scan line at a time. The rendering operation requires sequentially accessing all the image samples intersected by the scan line. When the sampled image is not rotated, the sequential access generally approximates an access to a single source row, and has a high degree of locality of access. In an operation accessing multiple elements of data from a data store, the operation is said to have “locality of access” if each element sequentially accessed is close to (or “local to”) the previously accessed element. The definition of “close to” depends on the physical characteristics of the data store, but generally operations with high degree of locality of access can occur more efficiently and more quickly than operations with a low degree of locality of access. This efficiency results from two common techniques for sequential data access, caching and burst (for computer memory) or buffered (for a file system) accesses. When the image is to be rotated in the rendering process, the “access” spans many (or all) of the source rows resulting in a poor locality of access factor, which may impair the efficiency of the rendering operation.
In summary, sampled image data is typically ordered in sequence
Blair Stuart R.
Borg Lars U.
Foley Matthew J.
Morris John D.
Adobe Systems Incorporated
Mehta Bhavesh
Patel Kanji
LandOfFree
Data management for rotated sampled images does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data management for rotated sampled images, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data management for rotated sampled images will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3105686