CA1288859C

CA1288859C - Method and apparatus for image data compression

Info

Publication number: CA1288859C
Application number: CA000534823A
Authority: CA
Inventors: Lawrence G. Roberts; Alex E. Henderson
Original assignee: NETEXPRESS SYSTEMS Inc
Current assignee: NETEXPRESS SYSTEMS Inc
Priority date: 1987-04-15
Filing date: 1987-04-15
Publication date: 1991-09-10
Anticipated expiration: 2008-09-10

Abstract

METHOD AND APPARATUS FOR IMAGE DATA COMPRESSION

ABSTRACT OF THE DISCLOSURE
A method and apparatus for selecting a refer-ence scan line for two-dimensional image coding prefer-ably compatible with known facsimile transmission equip-ment are disclosed. Selection of a reference scan line in accordance with the method and apparatus of the in-vention allows data compression for facsimile trans-mission so that the cost for use of the communication link is reduced. More than one previous scan line is considered as a candidate reference scan line. A ref-erence scan line is selected from among a plurality of previous scan lines, for example, the immediately pre-ceding ten scan lines. The preselected or adaptively selected scan line among the multiple prior scan lines, more particularly, the previous scan line which is most similar to the current scan line to be coded, is se-lected as the reference scan line. The reference scan line is then fed with the current scan line to be coded to a two-dimensional data compression coding process so as to yield optimum data compression. This reduces the amount of image data transmitted and lowers the cost of operation of the facsimile transmission apparatus.

Description

S~3 6843~27/DDDDD4 METHOD AND APPARATUS FOR IMAGE DATA COMPRESSION

This invention relates to two-dimensional image coding and, more particularly, to data compression in connection with vertical mode type image coding of image data representing screened images. Specifically, the invention is directed to a method and apparatus for scan line reference selection relative to coding images to enable increased data compression, for example, in connection with facsimile transmission.
Eguipment for telecommunication of images is known. The images can comprise text, as well as pic-torial information, such as illustrations, photographs,and graphic information. Known telecommunication equip-ment comprises a system whereby a transmitter at one location encodes an image, the encoded image is commu-nicated over a communication link, such as a telephone line, to a receiver at another location, and the receiver decodes the image. The image decoded by the receiver corresponds to the image encoded by the transmitter.
Conseguently, a facsimile of the original image is com-municated over a distance from the transmitter to the receiver. Hence, the telecommunication equipment has become ~nown as facsimile transmission equipment.
Facsimile transmission equipment is commer- -cially available from various manufacturers. In order to provide compatibility among the known facsimile trans-mission equipment produced by diffexent manufacturers, various standards have been adopted. Typically, known facsimile transmission eguipment utilizes a ra~ter scan of an image to be coded. Known facsimile transmission equipment is also typically ~tandardized for providing Modified Modified Read (MMR) codin~, as described in "STANDARDIZATION OF GROUP 3 FACSIMILE APPARATUS FOR

.
~ , ' : . ' ; .

.. . . . .
.. .
.

DOCUMENT TRANSMISSION," CCITT Recommendation T.4 (Geneva, 1980). Modified Modified Read coding includes horizon-tal mode coding, and khe "Read'l portion of "Modified Modified Read" represents relative address coding (R~C) also known as vertical mode coding~
On the one hand, the horizontal mode coding technique does not require a reference scan line in connection with coding each scanned line of the image.
On the other hand, the vertical mode coding techni~ue requires a reference scan line for each scanned line of the image as the image data is encoded for transmission at the transmitter. The reference scan line is also required by the vertical mode coding techni~ue when the transmitted image data is decoded at the receiver.
~ hether or not the horizontal or vertical mode coding technique .is utilized is defined by the known CCITT facsimile coding algorithms described in the aforementioned CCITT Recommendation T.4 entitled "STANDARDIZATION OF GROUP 3 FACSIMILE APPARATUS FOR

DOCUMENT TRANSMISSION" (Geneva, 1980). These standards specify conditions under which the vertical mode coding technique may be utilized. If both the reference scan line and the current scan line are used for coding, the process is referred to as vertical mode coding. If the current scan line alone is used for coding, the process is referred to as horizontal mode coding.
Typically, the major cost for operation of known facsimile transmission equipment is the cost of the communication link, such as a telephone line. Pref-erably, the image d ta is compressed by means of the known CCITT facsimile data compression coding algorithms utilizing the vertical mode coding technique prior to facsimile transmission. The purpose of the data com-pression is to reduce the a~nount, more particularly,the number of bits, of image data to be tran~mitted, thereby reducing the operating cost. Presently, the ~L2~181~3S~

amount of image data to be transmitted is of particular concern in the case of pictorial information.
Known facsimile transmission equipment gener-ally requires that a pictorial image be screened priorto coding and transmitting the image. Screening a pic-torial image can be performed in several ways.
Screened pictorial images under a magnifying glass generally comprise either circular or diamond-shaped dots aligned in vertical columns. The size ofeach circle or diamond, or the density of circles or diamonds, in a given area o~ the pictorial image varies as a function of the gray scale for the given area.
Unfortunately, if a screened pictorial image 1~ is to be transmitted, the CCITT facsimile data compres-sion coding algorithms do not operate well, because these algorithms cannot optimally utilize the typical Delta Modulation scheme which is employed whereby the current scan line to be coded is represented by coding only the changes or differences between the current scan line and the reference scan line and the result or difference data comprises the image data which is commu-nicated. Invariably, the CCITT facsimile data compres-sion coding algorithms utilize the Delta Modulation scheme for compressing the current scan line to be coded based on the immediately preceding scan lina. The imme-diately preceding scan line is used as a reference scan line so that the current scan line to be coded can be represented by coding only the changes or differences ~etween the current scan line to be coded and the imme-diately preceding scan line. However, the differences between the current scan line to be coded and the imme-diately preceding scan line can be great. Consequently, the amount of image data transmitted over the communi-cation link can be substantial. This translates to ahigh cost for operation of the facsimile transmission equipment, since the cost for the use of the , ' :, ~2~

communication link is based on the amount of image data which is communicated.
- This invention provides a method and apparatus for selecting a reference scan line for two-dimensional coding, such as vertical mode coding. The reference selection method and apparatus in accordance with the invention provide improved data compression of image data for storage or transmission of the image data, for example, in connection with facsimile transmi~sion utilizing the CCITT facsimile data compression coding algorithms in accordance with the specifications described in "STANDA~DIZATION OF GROUP 3 FACSIMILE APPARATUS FOR DOCUMENT TRANSMISSION," CCITT
Recommendation T.4 (Geneva, 1980). In the exemplary case of facsimile transmission, selection of a reference ~can line in accordance with the method and apparatus of the inven-tion allows improved data compression of image data for facsimile transmission so that the cost for use of the communication link is reduced.
Generally, the invention expands the present binary decision of no reference scan line for horizontal mode coding versus an immediately preceding scan line as reference scan line for vertical mode coding into a determination of no reference scan line for horizontal mode coding versus a reference one scan line back, two scan lines back, or K scan lines back for vertical mode coding. The invention relates to a determination of which of a plurality of preceding scan line is used as a reference scan line for vertical mode coding. The horizontal mode coding, on the oth0r hand, i~
unaffected.
The present invention provides a method for processing image data for data compression, said image data comprising pixel~ and representing a two-dimensional screened image, 4aid image data defining successive input ~can lines, including a first can line, a ~econd saan line immediately preceding ~aid first scan line, and a third ~can line preceding ~aid first scan line, said method comprising the steps of:

establishing said first scan line as a current scan line; and selecting a reference scan line while examining 3aid image data on the basis of the size or frequency of occurrence of said pixels o said image data, said reference scan line being ~elected from among said preceding second scan line and said preceding third scan line, and ~aid current scan line and said reference scan line being for use O in connection with a two-dimen~ional image coding process wherein data compre~s}on is directly related to a pattern relationship between said current scan line and said reference scan line.

In a further aspect, the present invention provides an apparatus for processing image data for data compression, said image data comprising pixels and representing a two-dimensional screened image, said image data defining successive input scan lines, including a first scan line, a second scan line immediately preceding said first scan line, ~0 and a third ~can line preceding said first scan line, said apparatus comprisin~:
means for establishing ~aid first scan line as a current ~can line; and means for selecting a reference scan line while examining said image data on the basis of the size or frequency of occurrence of said pixels of said image data, said reference scan line being selected from among ~aid proceeding second scan line and said preceding third scan line, and ~aid current ~can line and ~aid reerence ~can line being for use in connection with a two-dimensional image coding process wherein data compres~ion i8 directly related to a pattern relationæhip between ~aid current Qcan line and said reference scan line.
In accordance with one embodiment of the invention, reference scan line selection is provided base~ on a recurring pattern which can appear in the image represented by the image data to be coded. A reference scan line is pre~elected based on the recuxring pattern ~ " .

.
.
"" ~ ' ' , present in -the image and reflected in the image data to be coded. The preselected reference scan line can be other than the scan line immediately preceding the cur-rent scan line to be coded.
In accordance with another embodiment of the invention, adaptive reference scan line selection i~
provided. Adaptive reference scan line selection for K
sets of candidate reference scan line image data can be divided into (K + 1) steps. These comprise K steps that produce an estimate of the data compression which results from the use of each candidate reference scan line or of the quality of each candidate re~erence scan line. One embodiment of the estimation process, for example, is the two-dimensional data compression coding process, such as the CCITT facsimile data compression coding process. The estimate is the number of output bits produced by the data compression process. A qual-ity comparison process compares the estimates and passes the best reference scan line and -the current scan line to be coded to the two-dimensional data compression coding process. Another embodiment of the estimation process is to count the number of bits in the image data for each candidate reference scan line that do not match the image data for the current scan line to be coded. This is preferably performed by an exclusive-OR
combination of the image data for each candidate refer-ence scan line with image data for the current scan line to be coded followed by a count of the number of bits haYing a predetermined logic state. The candidate reference scan line that produces the lowest number of bits that do not match is selected as the reference scan line.
In contrast to known facsimile transmission equipment which uses the immediately preceding scan line as a reference scan line for vertical mode coding, the method and apparatus in accordance with the inven-tion can employ other than the immediately preceding ~8~

scan line as the reference scan line. The key feature of the invention resides in the reference scan line selection for the current scan line to be coded. The invention lies in the choice of the reference scan line and how the reference scan line is chosen. Specifically, unlike the known vertical mode coding technique which uses the immediately pxeceding scan line as the refer-ence scan line, the method and apparatus in accordance with the invention provide selection of a reference scan line from among a plurality of preceding scan lines, for example, the immediately preceding ten scan lines.
The scan line among the multiple prior scan lines which yields optimum Delta Modulation is selected as the ref-erence scan line. The image data for the referencescan line is then fed with the image data for the cur-rent scan line to be coded to the two-dimensional data compression coding algorithms, such as the known CCITT
facsimile data compression coding algorithms, so as to yield optimum data compression. This reduces the amount of image data transmitted and lowers the cost of opera-tion of the facsimile transmission apparatus.

The above and other features of the invention and the concomitant advantages will be better understood and appreciated by those skilled in the art in view of the description of the preferred embodiments given below in conjunction with the accompanying drawings. In the d~awings:
Fig. 1 is a schematic representation of an image comprised of textual and pictorial information, the pictorial information being represented by pixels of various sizes, the pixels being shown on an enlarged scale;
Fig. 2 is a schematic representation of an image comprised of textual and pictorial information, the pictorial information being represented by pixels , .
:
.

~ 8 8~ ~ ~

arranged in various densities, the pixels being shown on an enlarged scale;
Fig. 3 is a block diagram of one embodiment of image coding apparatus in accordance with the inven-tion;
Fig~ 4 is a flow chart of an embodiment of reference scan line selection method performed by the image coding apparatus shown in Fig. 3;
Fig. 5 is a block diagram of another embodi-ment of image coding apparatus in accordance with the invention;
Fig. 6 is a flow chart of one embodiment of adaptive reference scan line selection method performed by the image coding apparatus shown in Fig. 5; and Fig. 7 is a flow chart of another embodiment of adaptive reference scan line selection method per-formed by the image coding apparatus shown in Fig. 5.

In accordance with the invention, a plurality of previously scanned lines, any one of which can pro-spectively be used as a reference scan line, is checked before the current scan line is coded by means of a two-dimensional image coding technique, such as the known CCITT facsimile data compression coding algorithms with the vertical mode coding technique. A reference scan line can be preselected based on the presence of a recurring pattern which can appear in the image repre-slented by the image data to be coded. The recurring pattern establishes a pattern relationship between the reference scan line and the current scan line to be coded. In this case, the reference scan line is a pre-determined number of scan lines earlier than the current scan line to be coded and, further, can be other than the scan line immediately preceding the current scan line to be coded. Alternatively, the reference scan line can be adaptively selected based on a check of a .

predetermined number of previous scan lines. Prefer-ably, the ten immediately preceding scan lines are checked. The previous scan line which most closely matches the current scan line to be coded and therefore establishes the nearest pattern relationship is used as the reference scan line for coding the current scan line.
The preselected reference scan line or the most closely matched previous scan line together with the current scan line to be coded are then processed in accordance with a two-dimensional image coding technique, such as the CCITT facsimile data compression coding algorithms with the vertical mode coding technique.
The resulting differences between the current scan line to be coded and the previous scan line used as the reference scan line are minimal. Consequently, when the current scan line to be coded is represented by coding only the changes or differences between the current scan line and the reference scan line by means of Delta Modulation, the difference data is minimal.
As a result, the two-dimensional data compression coding algorithms, such as the known CCITT facsimile data com-pression coding algorithms, produce substantially greater compression of the image data when the reference selec-tion method and apparatus in accordance with the inven-tion are used. Therefore, the amount of image data transmitted is reduced so that the cost of operation of the facsimile transmission apparatus is lowered.
I By way of background, an imàge can generally include two basic categories of information, namely, textual information and/or pictorial information. The case in which both textual information and pictorial information appear on a page of a document is repre-sented in Figs. 1 and 2.
As shown in Fig. 1, textual information isgenerally indicated by the numeral 10. Pictarial in-formation is generally indicated by the numeral 12.

For the purposes of description, the pictorial informa-tion 12 is shown greatly magnified relative to the tex-tual information 10. This magnification shows that the pictorial information 12 is represented in a screened form such that the pictorial information comprises an array of diamond-shaped picture elements or pixels 14.
The pictorial information 12 is screened or formatted so that variation of the size of the pixels 14 deter-mines the shade of the various portions of the pictorial information. The shade of the portion of the pictorial information 12 contained within the dotted lines 16, for example, appears darker than the portion of the pictorial information contained within the do-tted lines 18, for example. The pixels 14 can be monochrome as shown in Fig. 1, as well as multi-color in the case of polychrome pictorial information 12.
As shown in Fig. 2I the pictorial information 12 is again shown greatly magnified relative to the textual information 10. This magnification shows that the pictorial information 12 is represented in a screened form such that the pictorial information again comprises an array of diamond-shaped picture elements or pixels 14. However, the pictorial information 12 is screened or formatted so that variation of the density of the pixels 14 determines the shade of the various portions of the pictorial information. The shade of the portion of the pictorial information 12 contained within the dotted lines 16, for example, appears darker than the portion of the pictorial information contained within the dotted lines 18, for example. The pixels 14 can be monochrome as shown in Fig. 2, as well as multi-color in the case of polychrome pictorial information 12.
While the variation in size or density of the pixels 14 corresponds to variation in the shade of the pictorial information 12, by way of comparison, the textual information 10 is typically defined fully with-out the need for variation of shade. Consequently, the textual information 10 is not typically screened as is the pictorial information 12. The textual information 10 can be characterized as characters 20, as compared S to pixels 14 in the case of the pictorial information 12.
In order for an image such as the textual information 10 and the pictorial informa-tion 12 shown in Figs. 1 and 2 to be coded for storage and/or facsim-ile transmission, the image is initially scanned. Thenumber of scan positions or points 22 of the image to be coded can vary. Generally, however, the size of the pixels 14 exceeds the size of the scan points 22 or the frequency of the scan points exceeds the number of pixels by at least a ratio of eight to one in order that the pictorial information 12 can be faithfully reproduced.
For example, the fre~uency of scan points 22 in a ~irst direction 24, ~uch as the horizontal direction, as well as a second direction 26, such as the vertical direction, can be 400 per inch, more particularly/ 400 scan points per inch across the page of the document in the horizon-tal direction by 400 scan points per inch in the ~erti-cal direction.
Typically, the textual information 10 and the pictorial information 12 can be scanned by a raster scan which be~ins at a scan point 22 located at a posi-tion PHl V1 and scans in the horizontal direction 24 across the image to be coded to and including a scan point located at a position PHl VN~ as shown in Figs. 1 and 2. In the case of an international size document on size A4 paper, for example, there can be 4,7~8 scan points 22 across t~e page of the document. Thereafter, the scan continues with a scan point 22 located at a position P~2 V1 across -to and including a scan point located at a position PH2 VN' and so on, until the en-tire page of the document is scanned including the scan point located at the posi*ion PHM VN For the purpose of explanation, the arrays of scan points 22 located at ', ' '.

, ' ' ' ~8~5~ ~

Hl,Vl' PHl,V2~ PHl VN~ etc., in the hori-zontal direction 24 are referred to as scan lines, and the arrays of scan points located at positions PH1 V1' PH2,Vl' PHM,Vl' etc., in the vertical direction 26 are referred to as columns. By way of shorthand nota-tion, the line of scan points 22 located at positions Hl,Vl~ PHl,V2' -- PHl,vN is designated scan line 11;
the line of scan points located at positions PH2 Vl' PH2,V2' -- PH2,VN is designated scan line 12; and so on, with the last line of scan points located at posi-HM,V1~ PHM,V2~ -- PHM VN being designated as scan line lM.
When the image is scarned, the textual infor-mation 10 and the pictorial information 12 are prefer-ably represented in a binary format such that a first logic state, for example, a low logic state or logic zero state, indicates that the particular scan point 22 does not coincide with any portion of a pixel 14 or a character 20. Conversely, a second logic state, for example, a high logic state or logic one state, indi-cates that the scan point 22 coincides with a portion of a pixel 14 or a portion of a character 20. Conse-quently, the image data appears as an array of first and second logic states which constitute the image data ~or the lines l1, 12, ... lM.
In accordance with the known vertical mode coding technique, the immediately preceding scan line is used as a reference scan line for the current scan line to be coded. For example, the scan line l1 is used as the reference scan line when the scan line 12 is coded, the reference scan line 12 is used as the reference scan line when the scan line 13 is coded, and so on. The difference between the two adjacent scan lines used for vertical mode coding, however, can be great. For example, the difference between the image data for the scan line lU and the image data for the 15~ ~

~2 scan line lV is significant, as is the difference between the image data for the scan line lV and the image data for the scan line lw, as is the diff~rence between the image data for the scan line lX and the image data for the scan line lyt as is the difference between the image data for the scan line ly and the image data for the scan line lz, for example.
In accordance with the reference selection method and apparatus of the invention, however, the reference scan line for the current scan line to be coded can be other than the immediately preceding scan line. Therefore, while the difference between the image data for the scan line lz and the image data for the scan line ly is significant, the image data for the scan line læ does not differ significantly from the image data for the scan line lv. Consequently, in ac-cordance with the reference selection method and appa-ratus of the invention, the scan line lV can be used as the reference scan line for the scan line lz to be coded with the result that there is a substantial reduction of the image data to be transmitted in contrast to the known vertical mode coding technique where the scan line ly is used as the reference scan line for the scan line lz to be coded. The reference scan line selection method and apparatus in accordance with the invention respond to the binary coded image data for optimally coding the image data when the two-dimensional coding technique, such as the vertical mode coding technique, i~ utilized for data compression, thereby optimizing the coding metrics.
Fig. 3 is a block diagram of one embodiment of apparatus for selecting a reference scan line in accordance with the invention, the apparatus being gen-erally indicated by the numeral 28. In the embodimentof the reference scan line selection apparatus 28 shown in Fig. 3, a scanner 30 is utilized for scanning the ' ,;

~;~88l~

image to be coded. The ~canner 30 is preferably a charge coupled device (CCD). Preferably, the ~canner 30 i~ a component of the Canon La~er Copier System (Part No. SSF-J7605) manufactured by Canon, Inc., of Japan. The scanner 30 preferably scans 400 scan points per inch in the horizontal direction 24 across the image by 400 lines per inch in the vertical direction 26.
In the case that the image is pictorial infor-mation, such as an illustration or photograph, the image to be coded is either already scre~ned, or the ~canner 30 includes a feature which per~orm~ the ~creening process. The Canon ~canner can digitally screen a pictorial image. The image to be coded, however, does not need to be completely screened, for example, the textual information 10 need not be screened.
The image data ~canned by the scanner 30 appears on a bus 32. The bu~ 32 connect~ the scanner 30 to a memory 35 and a mùltiplexer circuit 36. The image data for a plurality of candidate reference scan line~ i~ stored in the memory 35.
The reference scan line selection apparatus 28 shown in Fig. 3 also include~ a reference scan line ~elector circuit 33. The reference ~can line selector circuit 33 is preRet for ~electing one of the candidate reference scan lines ~tored in the memory 35 for u3e as the reference scan line for the current scan line to be coded.
The reference scan line ~elector circuit 33 is pre~e~ ba~ed on the determination of the presence of a recurring pattern which can appear in the image represented by the image data to be coded. The appearance of recurring pattern~ in the image data to be coded originates from the format for the character~ 20 in the case of the textual information 10 and the ~ize and shape of the pixel~ 14 in the ca~e o the pictorial information 12 which ha~ been ~creened~

,; ., :
.

~B~

Referring again briefly to Figs. 1 and 2, the similarity between the scan line lV and the scan line lz can be seen to be due in part to the symmetrical configuration of the diamond-shaped pixels 14 which comprise the screened pictorial information 12. Inter-estingly, the configuration of the pixels 14 which com-prise the pictorial information 12 that has been screened contributes to the difference between the more proximal scan lines lw, lx, and ly. Recognition of the recurrence of a pattern present in the resultant image data produced in connection with the scan line lV and the scan line lz is one significant factor in the determination of how the reference scan line selector circuit 33 is pre-set.
Another important factor in how the referencescan line selector circuit 33 is preset results from the particular size or frequency of the pixels 14 which comprise the screened pictorial information 12. As described above, the scanner 30 is selectively operated for screening an image to be coded. However, the image can be pre-screened. The reference scan line selector circuit 33 is preset based on analysis of the pictorial information 12 screened by the scanner 30 in the case where the scanner screens the pictorial information and, alternatively, based on analysis of the screening size of pre-screened pictorial information which appears in the image to be coded.
In sun~ary, a determination is made that there is a`recurring pattern present in the image represented by the image data to be coded based on the symmetry of the pixels 14 which comprise the screened pictorial information 12 and the size or freguency of the pixels in light of the particular process utilized for screen-ing the pictorial information. This recurring patternis clearly indicated in ~igs. 1 and 2 by comparison of the scan line lV with the scan line lz. As a result, the reference scan line selector circuit 33 can be ~2~

preset for selecting the candida~e reference scan line stored in the memory 35 which is most similar to the current scan line to be coded in view of the recurring 5 pattern. Therefore, if the scan line lz is the current scan line to be coded, the candidate reference scan line four lines back, more particularly, the scan line lv, is preset as the reference scan line to be selected.
For example, analysis has been made of the screening size of pre-screened pictorial information which appears in commercially available publications, such as magazines and newspapers. The size ranges from two and one-half scan points 22 per pixel 14 to ten scan points per pixel. In the case where the size is two and one-half scan points 22 per pixel 14, the refer-ence scan line selector circuit 33 is preset to select the candidate reference scan line which is two scan lines preceding the current scan line to be coded. In the case where the size is ten scan points 22 per pixel 14, the candidate reference scan line selected is the scan line preceding the current scan line to be coded by nine scan lines.
As shown in Fig. 3, the reference scan line selector circuit 33 is connected to a latch circuit 44 via a bus 46. The latch circuit 44 is connected to the multiplexer circuit 36 via a bus 48. The reference scan line selector circuit 33 enables a given latch included in the latch circuit 44, which corresponds to the latch that controls gating of the image data for the preselected candidate reference scan line from the memory 35 via the multiplexer circuit 36 to a two-dimen-sional data compression circuit 50 via a bus 52.
The current scan line to be coded is fed to the two-dimensional data compression circuit 50 via a bus 55 for codin~ while the preselected candidate refer-ence scan line for the next scan line to be coded is being selected. The coded current scan line, based on ~ 8~3~9 two-dimensional coding with the preselected candidate reference scan line, appears on a bus 54.
Considered in more detail, one embodiment of reference scan line selection method in accordance with the invention is shown in Fig. 4. ~s shown in Fig. 4, a flag is initially cleared, as indicated by the numeral 58. Also, the memory 35 is cleared so that the storage locations included in the memory for the candidate ref-erence scan lines contain the logic zero state (i.e.,the lines are preferably set as white scan lines), as indicated by the numeral 60.
Next, an iterati~e procedure for the determi nation of the reference scan line for each of the scan lines of the image, such as the scan lines l1, 12, ...
lM shown in Figs. 1 and 2, is undertaken. Initially, an index, denoted M to correspond to the lines of the image to ~e coded, is set e~ual to one, as indicated by the numeral 62. Initially, another index, denoted K to correspond to the number of preceding lines which can be used as candidate reference scan lines, is set e~ual to zero, as indicated by the numeral 68.
Thereafter, the image data for the next scan line to be coded, which is initially the scan line l1, 25 is output from the scanner 30, as indicated by the nu- -meral 64. The index K is set equal to (K - 1) to in-dicate that the initial scan line of the image is ~eing coded, as indicated by the numeral 69.
Then, the preselected candidate reference slcan line is selected as the reference scan Iine for the next scan line to be coded. The determination of the reference scan line or the next scan line to be coded is based on the presetting of the reference scan line selector circuit 33.
Since the memory 35 is initially cleared, as indicated by the numeral 60, there are not ten actual candidate reference scan lines until the eleventh line of the image is scanned. Nevertheless, the reference scan line selection method in accordance with the ~2~35~ ~

invention utilizes the in~ormation in the memory 35 as though actual candidate reference scan lines were cur-rently stored in the memory.
The reference scan line is set to the prese-lected reference scan line, as indicated by the numeral 84. The index K is then chec~ed to determine whether or not the memory 35 stores ten actual candidate refer-ence scan lines, as indicated by the numeral 86. If the memory 35 contains ten actual candidate reference scan lines, the tenth scan line back stored in the mem-ory is deleted, as indicated by the numeral 90, and the nex~ scan line to be coded is stored in the memory, as indicated by the numeral 92, whereas if ten actual can-didate reference scan lines are not contained in thememory, the next scan line to be coded is simply stored in the memory, as indicated by the numeral 92.
Next, the next scan line to be coded, for which the preselected candidate reference scan line has just been determined, becomes the current scan line to be coded, as indicated by the numeral 94. The current scan line to be coded is then checked to determine whether or not the current scan line is the final scan line of the image to be coded, as indicated by the nu-meral 96.
If on the one hand the current scan line tobe coded is not the final scan line of the image to be coded, the index M is set equal to (M + 1), as indi-cated by the numeral 98, and the reference scan line f,or the next scan line to be coded is determined analo-gously to the determination as described above, while the current scan line to be coded and the selected ref-erence scan line are fed to the two-dimensional data compression circuit 50, as indicated by the numeral 100. The two-dimensional data compression circuit 50 then codes the current scan line based on the selected reference scan line, as indicated by the numeral 102.

~æ~s If on the other hand the current scan line to be coded corresponds to the final scan line of the image, as indicated by the numeral 96, the flag is set, as indicated by the numeral 104. If the flag is set, the current scan line to be coded and the selected reference scan line are fed to the two-dimensional data compres-sion circuit 50, and the two-dimensional data compres-sion circuit codes the current scan line based on the selected reference scan line, as indicated by the numer-als lO0 and 102, respectively. Thereafter, a determi-nation is made that the ~lag is set, as indicated by the numeral 106, which completes the process.
Fig. 5 is a block diagram of one embodiment of apparatus for adaptively selecting a reference scan line in accordance with the invention, the apparatus being generally indicated by the numeral 29. In the embodiment of the adaptive reference scan line selec-tion apparatus 29 shown in Fig. 5, the scanner 30 is utilized for scanning the image to be coded.
The image data scanned by the scanner 30 ap-pears on the bus 32. The bus 32 connects the scanner 30 to guality estimator circuitry 34 and to the memory 35.
In accordance with the adaptive reference selection apparatus 29 of the invention, the quality estimator circuitry 34 preferably includes a plurality of quality estimator circuits 341' 342' 34K There are preferably at least two ~uality estimator circuits 3~1~ 342~ ~ 34K~ and, preferably, there are ten qual-ity estimator circuits. The quality estimator circuits 341~ 342~ ... 34K are preferably identically structured and also operate identically.
The image data for a plurality of candidate reference scan lines is stored in the memory 35. The memory 35 is connected to the quality estimator circui-try 34 and the multiplexer circuit 36 via the bus 38.
In the case where there is a plurality of ~uality lg estimator circuits 341' 342' 34K~ the image data for the scan line immediately preceding th~ current scan line to be coded appears on a bus 381 at the input to the quality estimator circuit 341~ the image data for the scan line corresponding to the scan line two scan lines back ~i.e., one scan line earlier to the scan line immediately preceding the current scan line to be coded) is connected from the memory 35 to the quality estimator circuit 342 via a bus 382, and the quality estimator circuits 343, 344~ ... 34K similarly receive the image data for the remainder of the previous scan lines 13, 14, ... 1K~ respectively, via the respec-tive buses 383, 384, ... 38K.
The quality estimator circuitry 34 estimates or determines the quality of the candidate reference scan lines vis-a-vis the current scan line to be coded.
This determination can be generally described as ascer-taining the similarity between ~he candidate reference scan line and the current scan line to be coded. In one embodiment of the adaptive reference selection appa-ratus 29 in accordance with the invention, the similar-ity between the candidate reference scan line and the current scan line to be coded can be based on perform-ing a two-dimensional coding technique, such as the vertical mode coding technique described in "STANDARDI-TRANSMISSION," CCITT Recommendation T.4 (Geneva, 1~80).

Generally, the vertical mode coding technigue determines the differences between the scanned image data for the current scan line to be coded with respect to the image data for a reference scan line and, more particularly, each candidate reference scan line in accordance with the adaptive reference selection method and apparatus of the invention, and produces a s.imilar-ity code or signal having one or more bits.

Alternatively, in another embodiment of the adaptive reference selection apparatus 29 in accoxdance with the invention, the quality estimator circuitry 34 can comprise gate array circuitry for performing an exclusive-OR combination of the image data for the cur-rent scan line to be coded with the image data for each candidate reference scan line in order to ascertain the similarity between the current scan line and the candi-date reference scan line. The number of differences isindicated by the number of second logic state signals which appear as a result of the exclusive-OR combination of the image data for the current scan line to be coded with the image data fo~ the candidate reference scan line, which forms a similarity code or signal having one or more bits.
As shown in Fig. 5, the output of the quality estimator circuitry 34 is connected to a quality esti-mate comparator circuit 42 via a bus 40. The outputs of the respective quality estimator circuits 341~ 342~
... 34K are connected via buses 401, 42' ..~ 40K~ re-spectively, to the quality estimate comparator circuit 42 in the case where there is a plurality of quality estimator circuits. The quality estimate comparator circuit 42 determines from the similarity signals pro~
duced by the quality estimator circuitry 34 the candi-date reference scan line 11, 12, ... lK which is most similar to the current scan line to be coded and selects the most similar candidate reference scan line as the rRference scan line to be used in connection with two-dimensional coding, such as vertical mode coding, of the current scan line.
The quality estimate comparator circuit 42 is connected to the latch circuit 44 via the bus 46. The latch circuit 44 is connected to the multiplexer circuit 36 via the bus 48. The quality estimate comparator circuit 42 enables a given latch included in the latch circuit 44, which corresponds to the latch that controls ~:88~

gating of the image data for the most similar candidate reference scan line from the multiplexer circuit 36 to the two-dimensional data compression circuit 50 via the bus 52.
The image data for the current scan line to be coded is preferably fed to the two-dimensional data compression circuit 50 via the bus 381for coding while the reference scan line for the next scan line to be coded is being ascertained. The coded current scan line, based on the two-dimensional coding technique, such as the vertical mode coding techni~ue, with the most similar candidate reference scan line, appears on the bus 54.
In one embodiment, a general purpose program-mable digital computer can be employed for coding the image data produced by the scanner 30. The computer provides a UNIX-based emulation. The reference selec-tion apparatus 29, for example, can be implemented by means of a UNIX-based microcomputer system, such as a DHL 2000 computer.
Adaptive reference scan line selection for K
sets of candidate reference scan line image data can be divided into (K + 1) steps. These comprise K steps that produce an estimate of the data compression which results from the use of each candidate reference scan line or, alternatively, of the quality of each candidate reference scan line.
One embodiment of the estimation process can ,be the two-dimensional data compression coding process, such as the CCITT facsimile data compression coding process ~the estimate is the number of bits produced by the data compression process). A quality comparison process compares the estimates and passes the image data for the best reference scan line and the image data for the current scan line to be coded to the two-dimensional data compression process.

~8~85~ ~

Another embodiment of the estimation process is to count the number of hits in the image ~ata for each candidate reference scan line that do not match the image data for the current scan line to be coded.
This is preferably performed by an exclusive-OR combina-tion of the image data for each candidate reference scan line with the image data for the current scan line to be coded followed by a count of the number of bits having a predetermined logic state. The candidate refer-ence scan line that produces the lowest number of bits which do not match is selected as the reference scan line.
In accordance with the one embodiment of the adaptive reference selection method of the invention, each candidate reference scan line and the current scan line to be coded are processed by the same two-dimen-sional coding technique, such as the vertical mode cod-ing techni~ue, that is utilized for data compression in accordance with the two-dimensional data compression coding algorithms, such as the CCITT facsimile data compression coding algorithms, and the number of bits that is produced is counted. The candidate reference scan line that produces the lowest count of bits is selected as the reerence scan line. This produces the minimum number of output bits for storage or transmis-sion.
Stated differently, the result of the refer-ence scan line selection process is to be fed together wlith the current scan line to be coded to the two-dimen-sional data compression coding process, such as the known CCITT facsimile data compression coding process, which utilizes the two-dimensional coding technique, such as the vertical mode coding tec~migue. I the number of bits which the two-dimensional data compres-sion coding process actually produces is previously determined (i.e., the coding process is performed for each candidate reference scan line and the current scan line to be coded and the number of output bits is ~,.: . : : , ..
: ' ' ' ' :

counted), then the candidate reference scan line that produces the lowest number of bits when used as the reference scan line subsequently produces the minimum number of output bits when fed with the current scan line to be coded to the given data compression process.
This minimizes the amount of image data stGred or trans-mitted.
During the calculation of the number of out-put bits produced by the two-dimensional data compres-sion coding algorithms, such as the CCITT facsimile data compression coding algorithms with vertical mode coding, for each candidate reference scan line with the next scan line to be coded, the image data for -the cur-rent scan line to be coded is routed together with theimage data for its selected reference scan line to and processed by the two-dimensional data compression coding algorithms with two-dimensional coding. The reference scan line for the next scan line to be coded is the candidate reference scan line with respect to which the number of bits produced by the two-dimensional data compression coding algorithms with two-dimensional cod-ing of the image data for that scan line with the image data for the next scan line to be coded is the least.
The calculation is performed for all ten immediately preceding scan lines and selects as the reference scan line the scan line that produces the minimum number of bits. When more than one of the candidate reference scan lines is the same, the most recent of the previous s,can lines, more particularly, the closest physically (spatially), is preferably selected as the reference scan line. However, an extensive amount of circuitry is needed for implementation of the one embodiment of the adaptive reference scan line selection method in accordance with the invention.
Considered in more detail, the one embodiment of the adaptive reference scan line selection method in accordance with the invention is shown in Fig. 6. As r shown in Fig. 6, a flag is initially cleared, as indi-cated by the n~eral 58. Also, the memory 35 is cleared so that -the storage locations included in the memory for the candidate reference scan lines contain the logic zero state (i.e., the scan lines are preferably set as white scan lines), as indicated by the numeral 60.
Next, an iterative procedure for the determi-nation of the reference scan line for each of the scan lines of the image, such as the scan lines 11, 12, ...
1M shown in Figs. 1 and 2, is undertaken. Initially, an index, denoted M to correspond to the scan lines of the image to he coded, is set e~ual to one, as indicated by the numeral 62. Thereafter, the image data for the next scan line to be coded, which is initially the line 11, is output from the scanner 30, as indicated by the numeral 64.
Then, the most similar candidate reference scan line is selected as a reference scan line for the next scan line to be coded. As shown in Fig. 6, the determination of the most similar reference scan line for the next scan line to be coded is illustrated as an iterative procedure, although the sequential iterative procedure can be replaced by a parallel procedure where-by the most similar candidate reference scan line forthe next scan line to be coded is determined simulta-neously, as will be clear from the description which follows in view of Fig. 5.
Initially, a variable, denoted SUM, is set ~qual to zero, as indicated by the numeral 66. Next, another index, denoted K to correspond to the number of preceding scan lines which can be used as candidate reference scan lines, is set e~ual to zero, as indicated by the numeral 68. Thereafter, the index K is set e~ual to (K - 1) to indicate that the immediately preceding scan line to the next scan line to be coded is to be tested as the most similar candidate reference scan line, as indicated by the numeral 70. Consequently, r ~ 3 the reference scan line for the next scan line to be coded is set equal to the immediately preceding scan line, as indicated by the numeral 72.
The quality estimator circuitry 34 is respon-sive to the image data for the immediately preceding scan line and the image data for the next scan line to be coded, which are processed by the two-dimensional data compression coding algorithms, such as the known CCITT facsimile data compression coding algorithms, as indicated by the numeral 74. The result is tested by counting the number of bits produced, as indicated by the numeral 76. Next, a variable, denoted SUMX, is set equal to the number of bits produced by the two-dimen-sional data compression coding algorithms, as indicatedby the numeral 78.
Thereafter, as indicated by the numeral 80, the index K is checked for equality to -1. If the index K e~uals -1, SUM is set equal to SUMX, and the reference scan line is set to the immediately preceding scan line, as indicated by the numerals 82 and 84, respectively.
Then, as indicated by the numeral ~6, the index K is checked for equality to -10 based on the fact that preferably the ten immediately preceding scan lines are used as the candidate reference scan lines in accordance with the adaptive reference scan line selec-tion method of the invention. If the index K does not equal -10, the index K is set e~ual to (K - 1), which in the case of the next iteration through the process ~eans that the candidate reference scan line two scan lines back is tested for being the most similar candi-date reference scan line.
Since the memory 35 is initially cleared, as indicated by the numeral 60, there are not ten actual candidate reference scan lines until the eleventh line of the image is scanned. Nevertheless, the adaptive reference scan line selection method in accordance with the invention utilizes the information in the memory 35 .

5S~ ~

as though actual candidate reference scan lines ~ere currently stored in the memory.
If the index K does not equal -1, which indi-cates that the candidate reference scan line being scru-tinized is not the immediately preceding scan line to the next scan line to be coded, SUM is checked to deter-mine if SUMX is smaller than SUM, as indicated by the numeral 88. I f on the one hand SUMX is smaller than SUM, SUM is set equal to S~X, and the reference scan line is set egual to the candidate reference scan line which when processed with the next scan line to be coded resulted in SUMX being smaller than SUM. If on the other hand SUM is smaller than SUMX, SUM is not set equal to SUMX (i.e., SUM is not changed), and the index K is checked to determine whether or not all desired candidate reference scan lines have been tested for which is most similar to the next scan line to be coded, as indicated by the numeral 86. If the last desired candidate reference scan line has been tested, the image data for the tenth scan line back stored in the memory 35 is deleted, as indicated by the numeral 90, and the image data for the next scan line to be coded is stored in the memory, as indicated by the numeral 92.
Next, the next scan line to be coded, for which the most similar candidate reference scan line has just been determined, becomes the current scan line to be coded, as indicated by the numeral 94. The cur-rent scan line is then checked to determine whether or not the current scan line is the final scan line of the image to be coded, as indicated by the numeral 96.
If on the one hand the current scan line to be coded is hOt the final scan line of the image to be coded, the index M is set equal to (M ~ 1), as indicated by the numeral 98, and the reference scan line for the next scan line to be coded is determined analogously to the determination as described above, whlle the image data for the current scan line to be coded and the image data for the selected reference scan line are fed to ' ' ,, ~

the two-dimensional data compression circuit 50, as indicated by the numeral 100. The two-dimensional data compression circuit 50 then codes the current scan line based on the selected reference scan line, as indicated by the numeral 102.
If on the other hand the current scan line to be coded corresponds to the final line of the image, as indicated by the numeral 96, the flag is set, as in-dicated by the numeral 104. If the flag is set, theimage data for the current scan line to be coded and the image data for the selected reference scan line are fed to the two-dimensional data compression circuit 50, and the two-dimensional data compression circuit codes the current scan line based on the selected reference scan line, as indicated by the numerals 100 and 102, respectively. Thereafter, a determination is made that the flag is set, as indicated by the numeral 106, which completes the process.
In accordance with the other embodiment of the adaptive reference scan line selection method of the invention, the immediately preceding ten scan lines are checked for the one that most closely matches the next scan line to be coded as the current scan line to be coded is being coded. The process performs the ex-clusive-OR of each of the bits of the imagé data for the next scan line to be coded with each of the bits of the respective image data for each of the ten immediate-ly preceding scan lines and determines the sum of the b,its`having a predetermined logic state, for example, a logic one state, for each exclusive-OR combination of the next scan line to be coded with each o~ the immedi-ately preceding ten scan lines. The result o the ex-clusive-OR combination is either a logic zero state or a logic one state. The result of the exclusive-OR com-bination is a logic zero state if the bits match (i.e., the bits are both logic zero state or both logic one state). The result of the exclusive-OR combination is ..

.: ~

~2~ i9 a logic one state if the bits do not match (i.e., one bit is a logic zero state and the other bit is a logic one state). The sum of the exclusive-OR combination therefore represents the number of bits that do not match.
During the determination of the sum of the exclusive-OR combination of the image data for each candidate reference scan line with the image data for the next scan line to be coded, the image da~a for the current scan line to be coded is routed together with the image data for its selected reference scan line to and processed by the two-dimensional data compression coding algorithms, such as the ~nown CCITT facsimile data compression coding algorithms, with two-dimensional coding, such as vertical mode coding. The reference scan line for the next scan line to be coded is the candidate reference scan line with respect to which the sum of the exclusive-OR combination of all the bits in the image data for that scan line with the image data for the next scan line to be coded is the least. The process is conducted for all ten immediately preceding scan lines and selects as the reference scan line the scan line which produces the minimum sum. Bits might not match in different locations with different candi-date reference scan lines. However, if the same result (i.e., quality estimate) is obtained in accordance with more than one of the candidate reference scan lines, the most recent of the previous scan lines, more par-ticularly, the closest physically (spatially), is pref-erably selected as the reference scan line. Typically, the same reference scan line is selected as in the case of the earlier described embodiment. However, the im-plementation in circuitry is less complex.
~onsidered in more detail, the other embodi-ment of the adaptive reference scan line selection method in accordance with the invention is shown in Fig. 7. As shown in Fig. 7, a flag is initially cleared, as indicated by the numeral 58. Also, the memory 35 is cleared so that the storage locations included in the memory for the candidate reference scan lines contain the logic zero state (i.e., the scan lines are prefer-ably set as white scan lines), as indicated by the nu-meral 60.
Next, an iterative procedure ~or the determi-nation of the reference scan line for each of the scan lines of the image, such as the scan lines 11, 12, ...
1M shown in Figs. 1 and 2, is undertaken. Initially, an index, denoted M to correspond to the lines of the image to be coded, is set equal to one, as indicated by the numeral 62. Thereafter, the image data for the next scan line to be coded, which is initially the scan line 11, is output from the scanner 30, as indicated by the numeral 64.
Then, the most similar candidate reference scan line is selected as a reference scan line for the next scan line to be coded. As shown in Fig. 7, the determination of the most similar reference scan line for the next scan line to be coded is illustrated as an iterative procedure, although the sequential iterative procedure can be replaced by a parallel procedure where-by the most similar candidate reference scan line forthe next scan line to be coded is determined simulta-neously, as will be clear from the description which follows in view of Fig. 5.
Initially, a variable, denoted SUM, is set ~qual to zero, as indicated by the numeral 66. Next, another index, denoted K to correspond to the number of preceding scan lines which can be used as candidate reference scan lines, is set equal to zero, as indicated by the numeral 68. Thereafter, the index K is set e~ual to (K - 1) to indicate that~the immediately preceding scan line to the next scan line to be coded is to be tested as the most similar candidate reference scan line, as indicated by the numeral 70. Consequently, " ' ' ' '' ' ' the reference scan line for the next scan line to be coded is set equal to the immediately preceding scan line, as indicated by the numeral 72.
The quality estimator circuitry 34 is respon-sive to the image data for the immediately preceding scan line and the image data for the next scan line to be coded such that an exclusive-OR combination of the image data for the candidate reference scan line and the image data for the next scan line to be coded is performed, as indicated by the numeral 108. Each non-match of a bit in the image data for the candidate ref-erence scan line as compared to the bit in the corres-ponding location in the image data for the next scan line to be coded produces a bit having a logic one state.
The total of the logic one state bits, more particularly, the non-matching bits, produced by the exclusive-OR
combination of the image data for the candidate refer-ence scan line and the image data for the next scan line to be coded is determined, as indicated by the numeral 110, and a variable, denoted SUMX, is set equal to the sum of the logic one state bits, as indicated by the numeral 112.
Thereafter, as indicated by the numeral 80, the index K is checked for equality to -1. If the index K equals -1, SUM is set equal to SUMX, and the reference scan line is set to the immediately preceding scan line, as indicated by the numerals 82 and 84, respectively.
Then, as indicated by the numeral 86, the ~ndex K is checked for equality to -10 based on the fact that preferably the ten immediately preceding scan lines are used as the candidate reference scan lines in accordance with the adaptive reference selection method of the invention. If the index K does not equal -10, the index K is set equal to (K - 1), which in the case of the next iteration throu~h the process means that the candidate reference scan line two lines back is s~ ~

tested for being the most similar candidate reference scan line.
Since the memory 35 is initially cleared, as indicated by the numeral 60, there are not ten actual candidate reference scan lines until the eleventh line of the image is scanned. Nevertheless, the adaptive reference scan line selection method in accordance with the invention utilizes the information in the memory 35 as thou~h actual candidate reference scan lines were currently stored in the memory.
If the index K does not equal -1, which indi-cates that the candidate reference scan line being scru-tinized is not the immediately preceding scan line to the next scan line to be coded, SUM is checked to deter mine if SUMX is smaller than SUM, as indicated by the numeral 88. If on the one hand SUMX is smaller than SUM, SUM is set equal to SUMX, and the reference scan line is set e~ual to the candidate reference scan line which when combined with the next scan line to be coded resulted in SUMX being smaller than SUM. If on the other hand SUM is smaller than SUMX, SUM is not set equal to SUM~ (i.e., SUM is not changed), and the index K is checked to determine whether or not all desired candidate reference scan lines have been tested for which is most similar to the next scan line to be coded, as indicated by the numeral 86. If the last desired candidate reference scan line has been tested, the image data for the tenth scan line back stored in the memory 35 is deleted, as indicated by the numeral 90, and the image data for the next scan line to be coded is stored in the memory, as indicated by the numeral 92.
Next, the next scan line to be coded, for which the most similar candidate reference scan line has just been determined, becomes the current scan line to be coded, as indicated by the numeral 94. The cur-rent scan line to be coded is then checked to determine whether or not the current scan line is the final scan .
.
..

line of the image to be coded, as indicated by the nume-ral 96.
If on the one hand the current scan line to be coded is not the final scan line of the image to be coded, the index M is set equal to (M + 1), as indicated by the numeral 98, and the reference scan line for the next scan line to be coded is determined analogously to the determination as described above, while the image data for the current scan line to be coded and the image data for the selected reference scan line are fed to the two-dimensional data compression circuit 50, as indicated by the numeral 100. The two-dimensional data compression circuit 50 then codes the current scan line based on the selected reference scan line, as indicated by the numeral 102.
If on the other hand the current scan line to be coded corresponds to the final line of the image, as indicated by the numeral ~6, the flag is set, as indi-cated by the numeral 104. If the flag is set, the imagedata for the current scan line to be coded and the image data for the selected reference scan line are fed to the two-dimensional data compression circuit 50, and the two-dimensional data compression cixcuit codes the current scan line based on the selected reference scan line, as indicated by the numerals 100 and 102, respec-tively. Thereafter, a determination is made that the flag is set, as indica-ted by the numeral 106, which completes the process.
l Preferably, the most recent sixteen lines scanned are stored in the reference file in the memory 35 so that the same circuit implementation can be em-ployed at the transmitter and the receiver of the fac-simile transmission apparatus. At the transmitter, where image data is compressed, the next scan line to be encoded, the current scan line to be encoded, and the ten i~mediately preceding scan lines are stored, which totals twelve lines. At the receiver, where the : . ' '', , 8$~3 ~

transmitted image data is decompressed, the next scan line to be decoded, the current scan line to be decoded, and the ten immediately preceding decompressed scan lines, as well as four additional lines for the enlarge-ment and reduction processes, are stored.
The choice of ten for the number of immedi-ately preceding scan lines to be checked as candidate reference scan lines is empirical and is based on analy-sis of the screening size of pre-screened pictorial information which appears in commercially available publications, such as magazines and newspapers. The size ranges from two and one-half scan points 22 per pixel 14 to ten scan points per pi~el. The number of immediately preceding scan lines to be checked as can-didate reference scan lines can be more than ten, how-ever, although the circuit cost increases as more scan lines must be stored and processed.
The method and apparatus in accordance with the invention provide for selecting a reference scan line for two-dimensional coding, such as vertical mode coding, compatible with two-dimensional data compression coding algorithms, such as the CCITT facsimile data compression coding algorithms in accordance with the specifications described in "STANDARDIZATION OF GROUP 3 FACSIMILE APPARATUS FOR DOCUMENT TRANSMISSION, " CCITT
Recommendation T.4 (Geneva, 1980). The reference scan line selection method and apparatus in accordance with the invention are particularly useful for coding an image to allow data compression in connection with fac~
simile transmission, thereby reducing the cost of opera-tion of the facsimile transmission apparatus through a reduction in the cost of use of the communication link.
This provides an improvement over known image coding techniques in connection with data compression, includ-ing the known vertical mode coding technique, and can be applied to any coding technique that uses either previously s-tored image data or a collection of r ~ z~ 3S9 predetermined image data patterns as a reference or compressing image data to be stored or transmitted.
This reduces the amount of storage required or the amount of image data transmitted over a communication link and thus reduces cost.
Although the invention has been described and illustrated in detail, it is to be clearly understood that the same is by way of illustration and example only and is not to be ta~en by way of limitation. Vari-ous modifications not described may occur to those skilled in the art which fall within the spirit of this invention. Consequently, the scope of this invention is better ascertained by reference to the appended claims.

, :

Claims

1. A method for processing image data for data compression, said image data comprising pixels and representing a two-dimensional screened image, said image data defining successive input scan lines, including a first can line, a second scan line immediately preceding said first scan line, and a third scan line preceding said first scan line, said method comprising the steps of:
establishing said first scan line as a current scan line; and selecting a reference scan line while examining said image data on the basis of the size or frequency of occurrence of said pixels of said image data, said reference scan line being selected from among said preceding second scan line and said preceding third scan line, and said current scan line and said reference scan line being for use in connection with a two-dimensional image coding process wherein data compression is directly related to a pattern relationship between said current scan line and said reference scan line.

2. The method of claim 1 wherein said selecting step comprises:
comparing said current scan line with each one of at least two candidate scan lines selected from ones of said input scan lines preceding said current scan line to obtain pattern relationship criteria, said candidate scan lines including said preceding second scan line and said preceding third scan line; and choosing as said reference scan line the one of said candidate scan lines which yields a most desired one of said pattern relationship criteria relative to said current scan line.

3. The method of claim 2 wherein said pattern relationship criteria are correlations between recurring image patterns in said candidate scan lines and said current scan line.

4. The method of claim 2 wherein said pattern relationship criteria are metrics indicative of code representations of said image data.

5. The method of claim 4 wherein said comparing step comprises:
applying a vertical mode coding technique to said current scan line using each of said candidate scan lines as a coding reference for said current scan line to obtain compressed image data comprising output bits; and determining the number of output bits obtained in said applying step of using each of said candidate scan lines as a coding reference for said current scan line; and wherein said choosing step comprises:
selecting as said reference scan lines the candidate scan line for which the least number of output bits was obtained.

6. The method of claim 2 wherein said comparing step comprises:
summing differences between image data of said current scan line and corresponding image data for each said candidate scan line; and wherein said choosing step comprises:
selecting as said reference scan line the candidate scan line yielding the least number of said differences.

7. The method of claim 6 wherein said comparing step further comprises:
exclusive-OR combining image data of each said candidate scan line with corresponding image data of said current scan line.

8. The method of claim 7 wherein said selecting step includes selecting as said reference scan line the candidate scan line producing said least number of said differences and which more closely precedes said current scan line than any other candidate scan line producing said least number of said differences.

9. An apparatus for processing image data for data compression, said image data comprising pixels and representing a two-dimensional screened image, said image data defining successive input scan lines, including a first scan line, a second scan line immediately preceding said first scan line, and a third scan line preceding said first scan line, said apparatus comprising:
means for establishing said first scan line as a current scan line; and means for selecting a reference scan line while examining said image data on the basis of the size or frequency of occurrence of said pixels of said image data, said reference scan line being selected from among said proceeding second scan line and said preceding third scan line, and said current scan line and said reference scan line being for use in connection with a two-dimensional image coding process wherein data compression is directly related to a pattern relationship between said current scan line and said reference scan line.

10. The apparatus of claim 9 wherein said selecting means comprises:
means for comparing said current scan line with each one of at least two candidate scan lines selected from ones of said input scan lines preceding said current scan line to obtain pattern relationship criteria, said candidate scan lines including said preceding second scan line and said preceding third scan line; and means for choosing as said reference scan line the one of said candidate scan lines which yields a most desired one of said pattern relationship criteria relative to said current scan line.

11. The apparatus of claim 10 wherein said pattern relationship criteria are correlations between recurring image patterns in said candidate scan lines and said current scan line.

12. The apparatus of claim 10 wherein said pattern relationship criteria are metrics indicative of code representations of said image data.

13. The apparatus of claim 10 wherein said comparing means comprises:
means for applying a vertical mode coding technique to said current scan line using each of said candidate scan lines as a coding reference for said current scan line to obtain compressed image data comprising output bit; and means for determining the number of output bits obtained by said applying means by using each of said candidate scan lines as a coding reference for said current scan line; and wherein said choosing means comprises:
means for selecting as said reference scan line the candidate scan line for which the least number of output bits was obtained.

14. The apparatus of claim 10 wherein said comparing means comprises:
means for summing differences between image data of said current scan line and corresponding image data for each said candidate scan line; and wherein said choosing means comprises:
means for selecting as said reference scan line the candidate scan line yielding the least number of said differences.

15. The apparatus of claim 14 wherein said comparing means further comprises:
exclusive-OR means operative to combine image data of each said candidate scan line with corresponding image data of each said current scan line.

16. The method of claim 15 wherein said selecting means includes means for selecting as said reference scan line the candidate scan line producing said least number of said difference and which more closely precedes said current scan line than any other candidate scan line producing said least number od said differences.