International Business Machines Corporation

Ronald Barthold Arps

Lalit R Bahl

Ehud Dov Karnin

Mihail Corneliu Constantinescu

Arnold Weinberger

Cormeliu Mihail Constantinescu

A system and associated method automatically and very rapidly determine the dominant periodicity in sequential binary data. The method incorporates a fast binary autocorrelation function used to discover the dominant periodicity in a sequential binary signal, and exploits this information in a periodicity exploiting application, such as using any one or more of a pixel periodicity or an edge periodicity based compression method in order to compress periodic halftoned bitonal images. The method implements four processes: The first process describes setting up the data in a transition-based representation to facilitate an algorithm to quickly find an autocorrelation distribution derived from a sequential binary signal. The second process describes a fast dominant periodicity search algorithm. The third process describes an algorithm that estimates the dominant window for estimating the dominant periodicity within one line of two-dimensional sequential binary signal. The fourth process describes an algorithm that estimates the dominant periodicity within a large region in a two-dimensional sequential binary signal.

System and method of automatically determining the dominant periodicity in sequential binary data

A method and apparatus incorporating a binary function correlation of run edges for compressing periodic halftoned digital images while increasing compression ratios over currently known one- and two-dimensional and adaptive arithmetic methods and decreasing the time required to perform the operation. In one embodiment, the invention horizontally encodes an image's run edges located at or near least &tgr; pixels ahead of a reference run edge in raster sequential image data. After the image is divided into lines of digital bits containing digital information indicative of binary values, the lines are encoded. A value for &tgr;&mdash;where &tgr; is independent of the width of the image and represents the periodicity for an edge of a run&mdash;is selected. Thereafter, run edges located &tgr;&plusmn;n pixels ahead of a designated run edge of a reference run are encoded.

Fast compression of periodic halftoned bitonal images

Method and means for detecting any single errors introduced into an arithmetic data compression code string as a result of coding, transmission, or decoding through testing according to a modulo-n function, n being an odd number not equal to +1 or -1, an arithmetic compression coded data stream C'(s) genmerated by n-scaling an arithmetically recursive function that produces a non-scaled arithmetically data compressed code stream C(s) as a number in the semi-open coding range [0,1].

Concurrent detection of errors in arithmetic data compression coding

An apparatus is disclosed for compressing a p .times. q image array of two-valued (black/white) sample points. The image array points are serially applied to the apparatus in consecutive raster scan lines. In response, the apparatus simultaneously forms two matrices respectively representing a high order p .times. q predictive error array and a p .times. q array of location events (such as the raster leading edges of all objects in the image). Improved compression is achieved by selecting between the more compression efficient of two methods for encoding the position of errors in the prediction error array. These alternative methods are conventional run-length coding and a novel form of reference encoding, used selectively but to significant advantage. Thus, a run-length compression codeword is formed from the count C of non-errors between consecutive errors (in response to the occurrence of each error in the jth bit position of the ith scan line of the predictive error array) upon either C.ltoreq.T, where T is a threshold, or C&gt;T and there being no occurrence of a line difference encoding for the error (where i, j, C and T have positive integers). A line difference codeword with difference value v is generated upon the joint event of C&gt;T and either the single or multiple occurrence of location events in the ith-1 scan line of the location event array within the bit position range of B.ltoreq.r.ltoreq.(j+n), where positive integer B is the greater of function D(T,v) and (j-n), and the number of intervening location events, s, within the bit position range of D(T,v).ltoreq.q&lt;(j-n) not exceeding some limit m (where m, n, q, r and s are positive integers).

Growing community of inventors

San Jose, CA, United States of America

Ronald Barthold Arps