EP O 1 _9 291  B1
matCh iS fOUnd at peIS L_Cg-L_C_2 and L2Cg_L2C_21 Sin Ce theSe eight peIS matCh With the panern 3 in Fig. 9.
_hus, the e_íght pels are replaced by the panern 13 in Fig. 9. This replacement is shown by solid l_in.e 1 02,
Thereby, the pre_proCeSS of the Scan l_ineS L_ and L2 ha_ been COmpleted, aS ShOWn 'in F_ig, 1 O(B)I and the
firSt SCan line L_ ' iS Stored _in the firSt line L_ ' of an oUtpUt bUffef, aS ShoWn in Fjg, 1 OIE). _n the neXt Stepl
5  Shown in Fig, IO(C), the SeCond l_Ine L2' of Fig, IO(B) and the thjrd SCan l_ine L3 Of the Ofiginal jmage data Of
Fig. 8 are combined and Joaded into the input bu_er. The 2 x 4 pel window moves again from the left end
C_ to the la St pel on the rignt C_. When the 2 X 4 pel windOW 81 reaCheS the ejght peIS L2'Cg_L2'C_2 and
L,C,-L,C_2, these e_ight pels match with the panern Q of F_ig. 9, and therefore these eight pels are replaced
by the pattern Q of Fíg. 9. This conversion is shown by sol.íd line I03 in F.ig. IOID), Thereby, the pre-process
IO  of the SCan lines L2' and L3 _in F_ig, 1 O(C) has been completedl and the scan line L2'' of Fig, IO ID) iS Stofed _in
the scan line L3'' of the output buffer as shown in F.ig. IO(E).
The ne Xt Step loadS the SCan l_ine L3' of Fig. 1 OID) and the SCan l_ine Lq Of Fig. 8 intO the inp Ut bUffeF,
Again, the 2 x 8 pel group is sequentially shí_ed and compared with the panerns 1 through 4, and if a
match is found, the eight pel group is replaced by one of the panerns 1 1 through IQ, and the resulting scan
_   _      15  line L3'' ìS Stofed into the OU_pUt bU_er, aS ShOWn.in Fig, IOIE),
The bìt panern in the output buffer is supplied to the compression device which compresses the bit
panern of the output buffer, _in accordance w_ith the two-dimensional coding scheme of the CCITT
Recommendation T.Q, for example.
_             ln the preceding specification, the pre-process in the horizontal d.irection was described. But, the pre-
2o  process.in accordance with the present invention could be used just as well to pre-process bi-level image
data _in the vertical d_irection. In the pre-process operation in the vertical direction, a changing element in
each column in the vertical direction is detected, and the step is pe_ormed which determines whether a
d_istance between the changing element in a first column and a changing element _in a second column is
faIIing within a predetermined range. Further, sim_ilar operational steps as the steps in the descr_ibed
25  embodiments are performed to pre-process the bi-level image data in the ve_ica_l direction.
The embodiments were directed to pre-process the black pels in the data. But, the ínvention could also
be used to pre-process image panerns which are reversed panerns of the panerns shown _in F_igs. 4A, 4C,
5A, 5C. 6A, 6C and the panerns 14 in Fig. 9. In this case, the white pels are treated as the foreground pels
and the black pels are treated as background pels.
3o     lt has been shown that the invention provides for the pre-processing of.image data, which.improves
the effic_iency of subsequent data compression. In other words, the invention reduces the data amount of
the compressed data.                                                        _
CIaims                          '
35     1. A method for processing binary image data supplied from an image supply means in preparation for
compression under a two-dimensional coding scheme, compr_ising the steps of.
a) scann_ing the image data by a moving window compr_is_ing predefined numbers of k picture elements
Ipels) in an image line (k columns) and l lines,
_o     b) detecting transit_ions between runs of elements of different binary values,
c) measuring the absolute value ofthe distance be_een the transitions in subsequent l_ínes or columns
in the window,
d) re-arranging said image data to selectively decrease sa_id distance to a predetermined value. _if saìd
distance _is smaller than a first predetermined d_istance value X, whereby the total number of pels _in each
_5  line of the window remains unchanged, and
e) supplying said re-arranged.image data to a compression means for performing said compression.
.             2. The method according to claim 1 wherein l = 3, comprising the steps of.
a) detecting a first transition.in the image data in a f_irst scan line, a second transition in the image data
.in a second scan line and a third transition in the image data in a third scan line,
_o     b) meaSUring a fjFSt di Stan Ce l__2) betWeen Said fífSt tranSitiOn and Said SeCOnd tfanSit_Ion and a seCond
_          di Stan Ce l_23) b_tWeen sajd SeCOnd and Said thifd transitiOnl
c) re-arranging said image data to selectivelv decrease the smaller one of said first or second d_istances
to a first predetermined value, if at least one distance _is smaller than or equal to a second predetermined
distance value which is larger than sa.id first predetermined value and smaller than said first predetermined
__  distance value X,
d) re-arranging said image data to reduce the smaller of said distances of said distances to said second
predetermined distance value, if both distances are between said second predetermined distance value
and said first predetermined distance value.                                          _
3. The method of claim 2 wherein sa.id second predetermined distance value equals 3.
6o    4. The method of claim 2 wherein sa_id f_irst predetermined value is O. if either said f_irst or said sec_nd
d_istance is 1, and ìs 1, _íf either said first or sa.id second distance is 2 or 3.
5. The method of cla.im 2, wherein k = 3 and l = 3.
6. The method according to claim 1, wherein k = Q and l _ 2.
7. An apparatus for performing the method of one or more of the preceding claims, w_ith means for
6_  StOfíng a W_indOW Of the sCanned image data, chara Cterized by
..                                _,-.    .  7                     .         .