Inter-block data management

An exemplary embodiment of the present invention may divide data into a first of set of blocks and a second set of blocks, and data may be stored from non-overlapping frames surrounding the first set of blocks in memory. The data may be grouped from the non-overlapping frames surrounding the second set of blocks, and the data may be absorbed from the non-overlapping frames surrounding the first set of blocks into the second set of blocks. The data may be processed the first set of blocks and the second set of blocks in parallel.

BACKGROUND

Halftoning is a technique that visually renders continuous-tone graphics or images through the arrangement of dots. Error diffusion is a halftoning technique where error may be distributed to nearby pixels that have yet to be processed. Diffusing error allows for source content to be rendered without distortion or visual discontinuities within the image. The error diffused at one location may depend on, in part, the error diffused at another location. As a result, many error diffusion techniques are implemented in a serial fashion.

DETAILED DESCRIPTION OF SPECIFIC EMBODIMENTS

An embodiment of the present techniques may include a storage means for inter-block data propagation and conjugate grouping for data transfer among sets of blocks. As used herein, inter-block data propagation may refer to propagating data between blocks in a chessboard arrangement. Further, as discussed below, conjugate grouping may refer to grouping block data. An embodiment of the present techniques may provide a means for absorption of data by the conjugate blocks. Additionally, an embodiment of the present techniques includes compact storage which may mitigate data overload at the corners of some conjugate blocks.

Input data can be processed by parallel halftoning techniques which may process two-dimensional input data arrays by segmenting the array into blocks. These blocks may be arranged in a manner similar to the squares of a chessboard and processed in parallel. Issues may arise when the processing of the first set of blocks results in the propagation of data to the second set of blocks. This type of propagation may occur in error diffusion algorithms. As a result, it is important to effectively manage the processing of inter-block data and the propagation of that data.

FIG. 1is a block diagram of a chessboard arrangement100having block sizes of 8×8 pixels according to an embodiment of the present techniques. For ease of description, a first set of blocks may be referred to as white blocks104, while a second set of blocks may be referred to as gray blocks102. In this arrangement100, a pixel corresponds to one square, each block contains sixty-four squares and is an 8×8 block of pixels. Additionally, the gray blocks102and white blocks104may be processed in parallel.

FIG. 2is a process flow diagram200of an overview of a method of inter-block data management according to an embodiment of the present techniques. At reference number202, non-overlapping frames may be stored in memory. A frame may be a set of pixels surrounding the blocks from a first set of blocks. At reference number204, conjugate grouping occurs. Conjugate grouping may group data from multiple portions of the frames surrounding the second set of blocks. At reference number206, conjugate block absorption occurs. Conjugate block absorption may absorb the data within the conjugate groups into the second set of blocks, and allow for “zero-corners” to be used, as described herein. At reference number208, the data within each block in the second set of blocks is processed.

FIG. 3is a process flow diagram300of a method of inter-block data management according to an embodiment of the present techniques. At reference number302, data is divided into groups of blocks. The blocks may be separated into two sets according to the chessboard scheme described herein. At reference number304, data from a first set of blocks is processed in parallel. At reference number306, data from non-overlapping frames surrounding the first set of blocks may be stored in memory.

At reference number308, data from the non-overlapping frames may be grouped around a second set of blocks. At reference number310, the data from the frames grouped around the second set of blocks is absorbed into the second set of blocks. At reference number312, the data within the second set of blocks may be processed in parallel.

FIG. 4is a diagram400of the storage of diagonal striped frames402propagated around white blocks104according to an embodiment of the present techniques. For ease of description, the present techniques are described using full blocks of data, where the data being processed is an image of size N by M pixels, with blocks of size n by m pixels.

When non-overlapping frames are stored, as at reference number202ofFIG. 2and reference number306ofFIG. 3, a global storage space may be set up to store the frames of data propagated outside the border of a first set of blocks. These frames may be of size (n+1) by (m+1) pixels. Additionally, to avoid overlap of these frames, the sparse storage space must be of size [N+2(N/n)+2] by [M+2(M/m)+2] pixels.

For example, the 8×8 pixel blocks illustrated inFIG. 1may have 10×10 pixel frames propagated around the white blocks104, shown as diagonal striped frames402inFIG. 4. Data from surrounding frames may be included in a process referred to herein as conjugate grouping, as described at reference number204(FIG. 2) and reference number308(FIG. 3). During conjugate grouping, the data in the frames that surround the gray blocks102may be composed of data from the portions of the four diagonal striped frames402surrounding white blocks104. A single conjugate group404around one of the gray blocks102is illustrated inFIG. 4. Conjugate grouping may result in a rectangle block of size (n+4) by (m+4) pixels. For example, conjugate group404denotes a conjugate grouping of size 12×12 pixels, and may consist of parts of the diagonal striped frames402from four white blocks104surrounding the gray block102inside of the conjugate group404.

FIG. 5Ais a diagram500of conjugate block absorption according to an embodiment of the present techniques. A white frame502within conjugate group404is an intermediate frame into which the portions of the diagonal striped frames402within the conjugate group404may be absorbed, as described at reference number206(FIG. 2), and reference number310(FIG. 3).

FIG. 5Bis a diagram504of a larger view of a conjugate group404according to an embodiment of the present techniques. For most of the white frame502, there is a one-to-one pixel correspondence with the diagonal striped frame402outside of the intermediate white frame502. This correspondence may be noted by arrows506, where each white frame pixel has one arrow from a corresponding diagonal striped frame pixel. Similarly, to propagate the data from the intermediate white frame502into the outer pixels of the gray block102, a similar relationship exists for most pixels where there is a one-to-one relationship. The relationship may be noted by arrows508from the intermediate white frame502to the gray block102. However, the four corners510of the intermediate white frame502have contributions from two diagonal striped frame402pixels. This may be shown by the two arrows506pointing into each corner510of the intermediate white frame502. Similarly, the corners512of the gray block102may absorb data from three white pixels, shown by three arrows508from the white frame502.

FIG. 5Cis a diagram of a larger view of a section514ofFIG. 5Baccording to an embodiment of the present techniques. The pixel at the corner512of gray block102may absorb data from four striped frame402pixels. For example, the pixel at the corner512may absorb data from three pixels in the intermediate white frame502, represented by arrows508a,508b, and508c. The data from the three pixels in the intermediate white frame502represented by arrows508a,508b, and508c, may in turn absorb data four pixels in the diagonal striped frame402, represented by arrows506a,506b,506c, and506d. Accordingly, the corner512of gray block102may, in turn, absorb data from four striped frame pixels. This may result in an overload of data propagated into the corner512of gray blocks102. The overloaded propagation of data into the corners of the gray blocks102may be mitigated by changing the way data is propagated from the white blocks104into the striped frame402by using “zero-corners.” In zero-corners, the value at the corner of each frame402may be set to zero.

FIG. 5Dis a diagram516of the storage of diagonal striped frames402with zero corners propagated around white blocks104according to an embodiment of the present techniques. Each corner518of a diagonal striped frame402has been set to zero, and is no longer striped. As a result, the two pixels between the edges of each diagonal striped frame402, as shown at reference numbers520,522,524,526, and528may be reduced to one pixel where the edges of each diagonal striped frame402are allowed to “overlap” without interference from an adjacent diagonal striped frame402.

FIG. 6Ais a diagram600of conjugate block absorption with zero corners according to an embodiment of the present techniques. The corners602of each striped frame402have been set to zero, and are no longer striped. As a result, the propagated data is stored in a compact fashion where one diagonal striped frame402overlaps with another diagonal striped frame402because neither frame has data in the corners602. In other words, when compared with the diagonal striped frames402inFIG. 5A, the diagonal striped frames402ofFIG. 6have corners that have been set equal to zero, and edges that occupy the same row or column of data as an adjacent diagonal striped frame402. This eliminates the use of an intermediate frame, as shown by the intermediate white frame502ofFIGS. 5A,5B, and5C. Accordingly, the global storage space can now be reduced to size [N+(N/n)+1] by [M 1(M/m)+1] pixels, or 37×28 pixels. Moreover, conjugate grouping may now be a rectangle of size (n+2) by (m+2) pixels. Conjugate block absorption may also be simplified since corners of the gray blocks102may now absorb data from two striped frame402pixels instead of four striped frame402pixels.

FIG. 6Bis a diagram of a larger view of a section604ofFIG. 6Aaccording to an embodiment of the present techniques. The corners606of gray block102absorb data from two striped frame402pixels, represented by two arrows608at each corner606. In this manner, the potential data overload from the striped frames402is mitigated.

Pinwheel Error Diffusion is a parallel approach to the otherwise sequential error diffusion algorithm that may be used with the inter-block data management techniques described herein. For example, the pixels within white blocks104may be processed in the order of an outward spiral, while the pixels in gray blocks may be processed in the order of an inward spiral.

FIG. 7is a diagram700of pinwheel error diffusion applied to zero-corner propagation according to an embodiment of the present techniques. Special error weight filters may be defined for the final four corners702,704,706, and708of the outward spiral710. The spiral710may represent a path of data processing up to the occurrence of the first outer corner702. Data processing may continue following such a path to the remaining corners704,706, and708.

At corner702, the error filter may be represented by three weights a, b, and c. This same set of weights may be at corners704and706. Weights a, b, and c at corner702reflect the diffusion of error into three pixels. Two pixels are within the diagonal striped frame402, while the remaining pixel is within the data block as indicated by the directional arrows for weights a, b, and c. Error is diffused in the same manner at corners704and706. Corner708may use two weights with values e and f as a result of the diffusion of error into the two remaining pixels within the diagonal striped frame402, as indicated by the directional arrows for weights e and f. The third pixel within the data block has been previously processed so no error can be diffused into that pixel. Accordingly, corners702,704,706, and708may distribute error such that non-zero error may be diffused to the diagonal striped frame402.

FIG. 8is a diagram800of an alternative block shape according to an embodiment of the present techniques. The techniques described herein are not limited to square blocks of pixels as rectangular blocks of any shape and size may be used. For example, diagram800shows a rectangular 4×8 blocks with gray blocks802and white blocks804.

FIG. 9is a diagram900of an alternative block shape according to an embodiment of the present techniques. Diagram900has gray blocks902and white blocks904in a striped arrangement.

Using global memory to store frames of propagated data may allow the spatial relationship of the data to be maintained. Conjugate blocks can absorb the inter-block data using a natural addressing scheme, and little or no inter-block process synchronization may be necessary. A common means of communicating information between parallel processes is through a messaging system that may use explicit synchronization or data coherence guarantees. However, the present techniques may use memory writes to an intermediate data buffer as opposed to explicit synchronization or data coherence. Moreover, implementing zero-corners may also reduce global storage, further simplify inter-block data transfer, and mitigate overload on conjugate block corners.

FIG. 10is a block diagram of a system that may provide inter-block data management. The system is generally referred to by the reference number1000. Those of ordinary skill in the art will appreciate that the functional blocks and devices shown inFIG. 10may comprise hardware elements including circuitry, software elements including computer code stored on a tangible, machine-readable medium, or a combination, of both hardware and software elements. Additionally, the functional blocks and devices of the system1000are but one example of functional blocks and devices that may be implemented in an embodiment. Those of ordinary skill in the art would readily be able to define specific functional blocks based on design considerations for a particular electronic device.

The system1000may include a server1002, and one or more client computers1004, in communication over a network1006. As illustrated inFIG. 10, the server1002may include one or more processors1008which may be connected through a bus1010to a display1012, one or more input devices1014, and an output device, such as a printer1016. The input devices1014may include devices such as a mouse or touch screen. When image data is processed using inter-block data management, the image may be rendered using the display1012or printer1016. However, components such as the display1012and the input devices may not be present when the server1002performs inter-block management. The processors1008may include a single core, multiple cores, or a cluster of cores in a cloud computing architecture. The server1002may also be connected through the bus1010to a network interface card (NIC)1018. The NIC1018may connect the server1002to the network1006.

The network1006may be a local area network (LAN), a wide area network (WAN), or another network configuration. The network1006may include routers, switches, modems, or any other kind of interface device used for interconnection. The network1006may connect to several client computers1004. Through the network1006, several client computers1004may connect to the server1002. The client computers1004may be similarly structured as the server1002.

The server1002may have other units operatively coupled to the processor1008through the bus1010. These units may include tangible, computer-readable storage media, such as storage1020. The storage1020may include any combinations of hard drives, read-only memory (ROM), random access memory (RAM), RAM drives, flash drives, optical drives, cache memory, and the like. The storage1020may include chessboard block data1022as used in an embodiment of the present techniques. Additionally, block data1022may include data from non-overlapping frames surrounding a set of blocks. Although the block data1022is shown to reside on server1002, a person of ordinary skill in the art would appreciate that the block data1022may reside on the server1002or any of the client computers1004.

FIG. 11is a block diagram showing a non-transitory, computer-readable medium that stores code for providing inter-block data management according to an embodiment of the present techniques. The non-transitory, computer-readable medium is generally referred to by the reference number1100.

The non-transitory, computer-readable medium1100may correspond to any typical storage device that stores computer-implemented instructions, such as programming code or the like. For example, the non-transitory, computer-readable medium1100may include one or more of a non-volatile memory, a volatile memory, and/or one or more storage devices.

Examples of non-volatile memory include, but are not limited to, electrically erasable programmable read only memory (EEPROM) and read only memory (ROM). Examples of volatile memory include, but are not limited to, static random access memory (SRAM), and dynamic random access memory (DRAM). Examples of storage devices include, but are not limited to, hard disks, compact disc drives, digital versatile disc drives, and flash memory devices.

A processor1102generally retrieves and executes the computer-implemented instructions stored in the non-transitory, computer-readable medium1100for inter-block data management. At block1104, a storage module may be used to store frames. At block1106, a conjugate grouping module may be used to perform conjugate grouping. As described herein, conjugate grouping may group data within the frames from one set of blocks. At block1108, conjugate block absorption module may be used to perform conjugate block absorption. As described herein, conjugate absorption may absorb the data within the frames into the other set of blocks. At block1110, a processing module may be used to process the data within the first set of blocks and the second set of blocks in parallel.