Browse Prior Art Database

Optimal Dither Algorithms on MIMD Parallel Processors

IP.com Disclosure Number: IPCOM000103409D
Publication Date: 2005-Mar-17
Document File: 3 page(s) / 198K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method for an algorithm that optimally implements bi-level image dithering for parallel computing architectures. Benefits include increasing processing speed.

This text was extracted from a Microsoft Word document.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Optimal Dither Algorithms on MIMD Parallel Processors

Disclosed is a method for an algorithm that optimally implements bi-level image dithering for parallel computing architectures. Benefits include increasing processing speed.

Background

Ordered dithering is an approximation technique used to display continuous-tone digital images on output devices that have a limited color or tone range. Ordered dithering is most commonly used in printers to simulate multiple color shades with binary dot values. For example, a printer capable of only printing black dots can simulate multiple shades of gray using ordered dithering. 

The ordered dither algorithm can be stated as follows: For all pixels in an image, compare the current input pixel pi with a variable threshold value given by d(x,y). See Figure 1. The function d(x,y) is commonly implemented as a matrix (i.e. a dither matrix) of fixed values representing some known pattern. The patterns used in the dither matrix determine the characteristics of the image. Many different dither matrices exist; a commonly used dither pattern (Bayer) is shown in Figure 2.

General Description

Parallel processing architectures come in several different forms:

§         Multiprocessor. Multiple CPUs with instruction sets that process a single data value

§         SIMD. A single CPU with the ability to process multiple data values in a single instruction

§         MIMD. Multiple CPUs processing multiple data values simultaneously

For a given parallel processing architecture, an optimal algorithm partitions the workload so that each processing unit processes 1/N the amount of work, where N is the number of processing units. 

In addition to processor architecture, the data throughput for a given parallel processing system must be considered. For example, consider the following. Assume that you have a multi-core signal processor with 32 execution engines. This processor can only read in one 16-bit value per clock cycle and write one 16-bit output value on the same clock cycle. This implies that only a single 16-bit value may be processed per clock cycle, even though the processor is capable of executing 32 instructions simultaneously. In this case, the lower bound for the optimal dither algorithm is determined by data throughput into the signal processor, not the number of processing elements.  The disclosed method’s algorithm applies directly to MIMD architectures...