Void and cluster apparatus and method for generating dither templates

Claim 1

An apparatus comprising: a memory device having locations corresponding to M rows and N columns of elements, said elements having a binary bit pattern of M rows and N columns comprising, said binary bit pattern first type bit elements and second type bit elements, with the type bit element with the greatest number of elements in said pattern array being a majority type element, and the type bit element of least number of elements in said pattern being a minority type element; means for iteratively selecting and moving said minority type elements and said majority type elements between element locations within said pattern memory device, said minority type elements selected in relation to neighboring minority type elements according to a first spatial characteristic, and said majority type elements selected in relation to neighboring minority type elements according to a second, different spatial characteristic, until said minority type elements and said majority type elements have been uniformly distributed to locations within said pattern memory device to provide a modified pattern of first and second type bit elements having homogeneous attributes; and means for providing a modified convolution result for each element of said pattern, including: multiplication means for multiplying the binary element value of said neighboring elements by a spatial domain function to generate a filter result; and summing means for adding said filter result of each of said neighboring elements to produce said modified convolution result for said element.

Claim 2

An apparatus comprising: a memory device having locations corresponding to M rows and N columns of elements, said elements having a binary bit pattern of M rows and N columns comprising, said binary bit pattern first type bit elements and second type bit elements, with the type bit element with the greatest number of elements in said pattern array being a majority type element, and the type bit element of least number of elements in said pattern being a minority type element; means for iteratively selecting and moving said minority type elements and said majority type elements between element locations within said pattern memory device, said minority type elements selected in relation to neighboring minority type elements according to a first spatial characteristic, and said majority type elements selected in relation to neighboring minority type elements according to a second, different spatial characteristic, until said minority type elements and said majority type elements have been uniformly distributed to locations within said pattern memory device to provide a modified pattern of first and second type bit elements having homogeneous attributes; and means for providing a modified convolution result for each element of said pattern, including: multiplication means for multiplying the binary element value of said neighboring elements by a spatial domain function to generate a filter result; and summing means for adding said filter result of each of said neighboring elements to produce said modified convolution result for said element.

Claim 6

An apparatus comprising: a memory device having locations corresponding to M rows and N columns of elements, said elements having a binary bit pattern of M rows and N columns comprising, said binary bit pattern first type bit elements and second type bit elements, with the type bit element with the greatest number of elements in said pattern array being a majority type element, and the type bit element of least number of elements in said pattern being a minority type element; means for iteratively selecting and moving said minority type elements and said majority type elements between element locations within said pattern memory device, said minority type elements selected in relation to neighboring minority type elements according to a first spatial characteristic, and said majority type elements selected in relation to neighboring minority type elements according to a second, different spatial characteristic, until said minority type elements and said majority type elements have been uniformly distributed to locations within said pattern memory device to provide a modified pattern of first and second type bit elements having homooenous attributes; and wherein said first spatial characteristic and said different spatial characteristic are respective modified convolution results for each element in said pattern memory device.

Claim 7

An apparatus comprising: a memory device having locations corresponding to M rows and N columns of elements, said elements having a binary bit pattern of M rows and N columns comprising, said binary bit pattern first type bit elements and second type bit elements, with the type bit element with the greatest number of elements in said pattern array being a majority type element, and the type bit element of least number of elements in said pattern being a minority type element; means for iteratively selecting and moving said minority type elements and said majority type elements between element locations within said pattern memory device, said minority type elements selected in relation to neighboring minority type elements according to a first spatial characteristic, and said majority type elements selected in relation to neighboring minority type elements according to a second, different spatial characteristic, until said minority type elements and said majority type elements have been uniformly distributed to locations within said pattern memory device to provide a modified pattern of first and second type bit elements having homooenous attributes; and wherein said first spatial characteristic and said different spatial characteristic are respective modified convolution results for each element in said pattern memory device.

Claim 10

An apparatus comprising: means for storing a binary bit pattern having M rows and N columns comprising first type bit elements and second type bit elements, wherein the type bit element of greatest number in said pattern is a majority type element, and the type bit element of at least number in said pattern array is a minority type element; means for storing a dither template having M rows and N columns of integer threshold values in a template memory device having corresponding M rows and N columns of element locations; means for iteratively selecting a minority type element from said corresponding location from said pattern, said minority type element at said corresponding location selected in relation to neighboring minority type elements according to a first spatial characteristic, said means for iteratively selecting a minority type element further comprising: means for replacing said minority type element at said corresponding memory location with a majority type element to provide a second pattern array, and concurrently assigning a threshold value to a corresponding element location of said template memory; means for iteratively selecting a majority type element from said pattern, said majority type element selected in relation to neighboring minority type elements according to a second, different spatial characteristic, said means for iteratively selecting a majority type element further comprising: means for replacing said majority type element at said corresponding pattern location with a minority type element to provide a third modified pattern, and concurrently assigning a threshold value to a corresponding element location of said template memory; and means for providing a modified convolution result for each element of said pattern including: multiplication means for multiplying the binarv element value of said neighboring elements by a spatial domain function to generate a filter result; and summing means for adding said filter result of each of said neighboring elements to produce said modified convolution result for said element.

Claim 11

An apparatus comprising: means for storing a binary bit pattern having M rows and N columns comprising first type bit elements and second type bit elements, wherein the type bit element of greatest number in said pattern is a majority type element, and the type bit element of at least number in said pattern array is a minority type element; means for storing a dither template having M rows and N columns of integer threshold values in a template memory device having corresponding M rows and N columns of element locations; means for iteratively selecting a minority type element from said corresponding location from said pattern, said minority type element at said corresponding location selected in relation to neighboring minority type elements according to a first spatial characteristic, said means for iteratively selecting a minority type element further comprising: means for replacing said minority type element at said corresponding memory location with a majority type element to provide a second pattern array, and concurrently assigning a threshold value to a corresponding element location of said template memory; means for iteratively selecting a majority type element from said pattern, said majority type element selected in relation to neighboring minority type elements according to a second, different spatial characteristic, said means for iteratively selecting a majority type element further comprising: means for replacing said majority type element at said corresponding pattern location with a minority type element to provide a third modified pattern, and concurrently assigning a threshold value to a corresponding element location of said template memory; and means for providing a modified convolution result for each element of said pattern including: multiplication means for multiplying the binarv element value of said neighboring elements by a spatial domain function to generate a filter result; and summing means for adding said filter result of each of said neighboring elements to produce said modified convolution result for said element.

Claim 18

An apparatus comprising: a dithering system responsive to input image pixels from an input device having a first plurality of representation levels, including a memory for storing a dither template comprising an M by N array of elements representing a uniform distribution of integer threshold values having homogeneous attributes; means, responsive to said first plurality of representation levels, a second plurality of representation levels of an output device, and to said threshold values of said dither template, for providing a normalized dither matrix comprising normalized threshold values; adding means for adding said input image pixel representation levels to said normalized threshold values to provide summation signals; quantizer means for mapping said summation signals to said second plurality of representation levels to provide output pixels; and means for storing said output pixels.

Claim 19

An apparatus comprising: a dithering system responsive to input image pixels from an input device having a first plurality of representation levels, including a memory for storing a dither template comprising an M by N array of elements representing a uniform distribution of integer threshold values having homogeneous attributes; means, responsive to said first plurality of representation levels, a second plurality of representation levels of an output device, and to said threshold values of said dither template, for providing a normalized dither matrix comprising normalized threshold values; adding means for adding said input image pixel representation levels to said normalized threshold values to provide summation signals; quantizer means for mapping said summation signals to said second plurality of representation levels to provide output pixels; and means for storing said output pixels.

Claim 32

A method comprising the steps of: a. storing in a memory device a pattern having M rows and N columns of locations, said pattern comprising a binary pattern of fist type bit elements and second type bit elements, wherein said type bit element of greatest number in said pattern is a majority type element, and said type bit element of least number in said pattern is a minority-type element; b. iteratively selecting and moving said minority type elements and said majority type elements in said memory device between memory locations, wherein said minority type element location in memory is selected in relation to neighboring minority type elements according to a first spatial characteristic and said majority type element location in memory is selected in relation to neighboring minority type elements according to a second, different spatial characteristic; repeating said step of iteratively selecting and moving until said minority type elements and majority type elements are uniformly distributed at pattern locations in said memory device to provide a modified pattern having homogeneous attributes; and c. calculating a modified convolution result for each element of said pattern, comprising the steps of: c1. multiplying the binary element value of each of said neighboring elements by a spatial domain function to generate a filter result for each of said neighboring elements; and c2. summing said filter result of said neighboring elements to produce said modified convolution result of said element.

Claim 33

A method comprising the steps of: a. storing in a memory device a pattern having M rows and N columns of locations, said pattern comprising a binary pattern of fist type bit elements and second type bit elements, wherein said type bit element of greatest number in said pattern is a majority type element, and said type bit element of least number in said pattern is a minority-type element; b. iteratively selecting and moving said minority type elements and said majority type elements in said memory device between memory locations, wherein said minority type element location in memory is selected in relation to neighboring minority type elements according to a first spatial characteristic and said majority type element location in memory is selected in relation to neighboring minority type elements according to a second, different spatial characteristic; repeating said step of iteratively selecting and moving until said minority type elements and majority type elements are uniformly distributed at pattern locations in said memory device to provide a modified pattern having homogeneous attributes; and c. calculating a modified convolution result for each element of said pattern, comprising the steps of: c1. multiplying the binary element value of each of said neighboring elements by a spatial domain function to generate a filter result for each of said neighboring elements; and c2. summing said filter result of said neighboring elements to produce said modified convolution result of said element.

Claim 41

A method comprising the steps of: a. storing in a memory device a pattern having M rows and N columns of locations, said pattern comprising a binary pattern first type bit elements and second type bit elements, wherein said type bit element of greatest number in said pattern is a majority type element, and said type bit element of least number in said pattern is a minority type element; b. selecting a minority type element location from said pattern, said minority type element location selected in relation to neighboring minority type elements according to said first spatial characteristic, including replacing said minority type element with a majority type element and concurrently assigning a threshold value to a corresponding location of said dither template until no minority type elements remain in said pattern; c. selecting a majority type element location from said pattern, said majority type element location selected in relation to neighboring minority type elements according to said second, different spatial characteristic, including replacing said majority type element with said minority type element and concurrently assigning a threshold value to a corresponding location of said dither template until the number of minority type elements in said pattern exceeds the number of majority type elements in said pattern; d. evaluating the bit type of the majority type element and the minority type element, wherein the type bit element of greatest number in said pattern is a majority type element, and the type bit element of least number in said pattern is a minority type element; and e. selecting a minority type element location from said pattern, said minority type element location selected in relation to neighboring minority type elements according to said first spatial characteristic, including replacing said minority type element with said majority type element and concurrently assigning a threshold value to a corresponding location of said dither template until a threshold value has been assigned to all dither template elements.

Claim 42

A method comprising the steps of: a. storing in a memory device a pattern having M rows and N columns of locations, said pattern comprising a binary pattern first type bit elements and second type bit elements, wherein said type bit element of greatest number in said pattern is a majority type element, and said type bit element of least number in said pattern is a minority type element; b. selecting a minority type element location from said pattern, said minority type element location selected in relation to neighboring minority type elements according to said first spatial characteristic, including replacing said minority type element with a majority type element and concurrently assigning a threshold value to a corresponding location of said dither template until no minority type elements remain in said pattern; c. selecting a majority type element location from said pattern, said majority type element location selected in relation to neighboring minority type elements according to said second, different spatial characteristic, including replacing said majority type element with said minority type element and concurrently assigning a threshold value to a corresponding location of said dither template until the number of minority type elements in said pattern exceeds the number of majority type elements in said pattern; d. evaluating the bit type of the majority type element and the minority type element, wherein the type bit element of greatest number in said pattern is a majority type element, and the type bit element of least number in said pattern is a minority type element; and e. selecting a minority type element location from said pattern, said minority type element location selected in relation to neighboring minority type elements according to said first spatial characteristic, including replacing said minority type element with said majority type element and concurrently assigning a threshold value to a corresponding location of said dither template until a threshold value has been assigned to all dither template elements.

Claim 43

A method comprising the steps of: a. storing in a memory device a pattern having M rows and N columns of locations, said pattern comprising a binary pattern first type bit elements and second type bit elements, wherein said type bit element of greatest number in said pattern is a majority type element, and said type bit element of least number in said pattern is a minority type element; b. selecting a minority type element location from said pattern, said minority type element location selected in relation to neighboring minority type elements according to said first spatial characteristic, including replacing said minority type element with a majority type element and concurrently assigning a threshold value to a corresponding location of said dither template until no minority type elements remain in said pattern c. selecting a majority type element location from said pattern, said majority type element location selected in relation to neighboring minority type elements according to said second, different spatial characteristic, including replacing said majority type element with said minority type element and concurrently assigning a threshold value to a corresponding location of said dither template until the number of minority type elements in said pattern exceeds the number of majority type elements in said pattern; and d. calculating a modified convolution result for each element of said pattern, comprising the steps of: d1. multiplying the binary element value of each of said neighboring elements by a spatial domain function to generate a filter result for each of said neighboring elements; and d2. summing said filter result of said neighboring elements to produce said modified convolution result of said element.

Claim 44

A method comprising the steps of: a. storing in a memory device a pattern having M rows and N columns of locations, said pattern comprising a binary pattern first type bit elements and second type bit elements, wherein said type bit element of greatest number in said pattern is a majority type element, and said type bit element of least number in said pattern is a minority type element; b. selecting a minority type element location from said pattern, said minority type element location selected in relation to neighboring minority type elements according to said first spatial characteristic, including replacing said minority type element with a majority type element and concurrently assigning a threshold value to a corresponding location of said dither template until no minority type elements remain in said pattern c. selecting a majority type element location from said pattern, said majority type element location selected in relation to neighboring minority type elements according to said second, different spatial characteristic, including replacing said majority type element with said minority type element and concurrently assigning a threshold value to a corresponding location of said dither template until the number of minority type elements in said pattern exceeds the number of majority type elements in said pattern; and d. calculating a modified convolution result for each element of said pattern, comprising the steps of: d1. multiplying the binary element value of each of said neighboring elements by a spatial domain function to generate a filter result for each of said neighboring elements; and d2. summing said filter result of said neighboring elements to produce said modified convolution result of said element.