[comp.std.internat] CCITT Group 3 question: "early" EOL

andrea@sdd.hp.com (Andrea K. Frankel) (08/30/90)

Here's a question I hope someone reading this group can answer:

CCITT Group 3 encoding has explicit end-of-line codes.  Some implementations
(hardware and software) appear to require all lines to be the same
length, fully encoded up to the row width (which must be specified in
some way external to the encoded file), or else they fail.  

	-  Is this a valid, conforming implementation?  

	-  Or should a robust implementation be able to decode
	Group 3 files where some rows are ended "early" with an EOL 
	(in which case presumably the rest of the row is white)?

(When responding to this question, please give document references and/or
your "credentials" which I can use to establish the credibility of the
argument to the key managers involved.)

Below is a message from an engineer heavily involved in the
implementation, giving his arguments as to why it should be OK to blow
up on "early" EOL's:

> There is an assumed line width when the image is coded. 
> After closer examination of the CCITT Recommendation T.4, I offer the 
> following evidence:
> 
>      Section 2.1 Reads:
> 
>         The following dimensions should be used:
>                          .
>                          .
>                          .
>         and, for equipment which provides A5 and/or A6 facilities:
> 
>         e) optionally, 864 black and white picture elements ....
> 
>         f) optionally, 1216 black and white picture elements ....
> 
>         g) optionally, 1728 black and white picture elements ....
> 
>                          .
>                          .
>                          .
>         Note 2 - In cases e) to h), 1728 pels will always be provided to the
>                  coder.
> 
>         In cases e) and f), the additional pels required are produced by pel
>         processing (i.e., either by picture processing or by adding white pels
>         on each side of the central picture information) prior to coding.
> 
>     My response to this note would be, "Why should white pels be added to the
>     end of the line before coding if during coding, they are ignored and an
>     EOL (end of line) code is issued?"
> 
> Perhaps we SHOULD allow the EOL to occur at any position, but the above 
> arguement must at least put some doubt in our minds about the necessity of 
> handling this situation.
> 
> My next step is to question the Group 3, two-dimensional implementation.  Do
> the same arguements apply here?  Can an EOL be received before the entire
> line has been decoded?  My answer would be "No," and here's why:
> 
>   In Recommendation T.4, Section 4.2.1.3.4:
> 
>       b)  Processing the last picture element
> 
>            The coding of the coding line continues until the position of
>            the imaginary changing element situated just after the last
>            actual element has been coded.  This may be coded as a1 or
>            a2.  Also, if b1 and/or b2 are not detected at any time
>            during the coding of the line, they are positioned on the
>            imaginary changing element situated just after the last
>            actual picture element on the reference line.
> 
> 
>   Furthermore Section 4.2.2 States:
> 
>       TO THE END OF EVERY CODED LINE is added the EOL code word.
> 
>   Finally, the flow diagram for encoding (FIGURE 7/T.4) shows that the entire
>   line must be coded, regardless of pixel color, before the EOL code is
>   added.
> 
> It is clear that two-dimensionally encoded rows, anyway, must be fully
> encoded before an EOL is added.
> 
> The aforementioned flow diagram also shows that in Group 3, 2-D,
> for one-dimensionally encoded lines, the exact same encoding technique for
> Group 3, 1-D is used to encode these lines.  So whatever holds to Group 3, 2-D
> one-dimensionally encoded lines must also hold for Group 3, 1-D encoding, and
> vice versa.
> 
> I can't imagine that the 1-D encoded lines would allow an early EOL when the
> 2-D lines do not.   There is nothing in the spec that says if an EOL is
> received early, the remainder of the line is filled with 0's.  This is 
> simply an assumption.
> 
> Another arguement:
> 
> Let's assume that we can have early EOL's.  What happens when we receive an
> EOL?  Let's forget for the time being that we are decoding for a real device.
> According to our assumption, the line must be zero filled to the end of the 
> actual line length in order to get a true representation of the original
> picture.  Well, what is that "actual line length?"  If we have not specified
> a picture width to work with, there is no way of telling where we should
> fill to, except by imposing other limitations that are device dependent.
> 
> If we are not required to explicily know the picture width for CCITT Group 3,
> 1-D , which we agreed was the case, then how do we know the true 
> dimensions of the image except by requiring that one-dimensional lines are
> fully encoded, both black AND white pixels, before an EOL is sent?
> In order to allow for early EOL's, we would have to explicitly know the
> image width.
> 
> Furthermore:
> 
> If we can send early EOL's, what happens in the case that the entire line
> is white?  We can't just send an EOL, for two reasons:
> 
>   1. Section 4.1.1 reads:
>                                .
>                                .
>                                .
> 
>         In order to ensure that the receiver maintains colour synchronization,
>       all Data lines will begin with a white run length code word....
> 
>   2. Encoding six of these lines in a row would result in the RTC code, 
>      signaling the end of the image.  (An RTC is six EOL's in a row).
> 
> So now we have to say, "OK, we can have early EOL's, but the line must still
> begin with a white run length code word."
> 
> And finally, the AMD chip for G3 encoding/decoding, used in PC boards, 
> requires explicit knowledge of the image width, but does not allow for early
> EOL's.  This chip apparently "sets the standard."


Please email or post your response, but we'd sure like to be able to
figure this out soon!  "adTHANKSvance"

Andrea Frankel, Hewlett Packard, San Diego Technical Graphics Div., R&D Lab
	"wake now!  Discover that you are the song that the morning brings..."
______________________________________________________________________________
Internet : andrea@sdd.hp.com (or andrea%hp-sdd@nosc.mil or @ucsd.edu)
UUCP     : {hplabs|nosc|hpfcla|ucsd}!hp-sdd!andrea 
CSNET    : andrea%hp-sdd@hplabs.csnet
USnail   : 16399 W. Bernardo Drive - Mailstop 61U65, San Diego CA 92127-1899
Voice    : (619) 592-4664

ttl@sti.fi (Timo Lehtinen) (08/30/90)

In article <1990Aug29.194009.6820@sdd.hp.com> andrea@sdd.hp.com (Andrea K. Frankel) writes:
>
>	-  Or should a robust implementation be able to decode
>	Group 3 files where some rows are ended "early" with an EOL 
>	(in which case presumably the rest of the row is white)?

In my opinion Rec. T.4 does not give an explicit answer to this question.
In addition to section 2.1 (which you quoted) the only other lines in the
part of the document that define the one-dimensional coding scheme that
might be relevant to the question at hand are in section 4.1.1. :

	...White runs and black runs alternate. A total of 1728 picture
	elements represent one horizontal scan line of 215 mm length.

The sentence above, the fact that the FAX machines I've tested this feature 
against have all choked on early EOL's and mostly the same reasoning that
you give at the end of your message has lead me to think that an 
implementation that outputs lines with early EOL's s non-conformant.  I've 
only seen early EOL's generated by software tools that are not nessessarily
meant to be used with FAX modems as that. The G3 filters in the PBMPLUS
package behave like this and (if my memory serves) the encode/decode
routines in the ISODE/QUIPU/PHOTO system also produce scan lines shorter
than 1728. (I'm not absolutely sure about the latter one.)

BTW, The newsgroup alt.fax might be a more appropriate place for this 
discussion.

Timo Lehtinen


-- 
       ____/ ___   ___/    /		Kivihaantie 8 C 25
      /           /       /		SF-00310 HELSINKI, Finland
   ____  /       /       /	Phone:	+358 0 573 161, +358 49 424 012
  Stream Technologies Inc.	Fax:	+358 0 571 384

morris@uninet.dec.com (Tom Morris) (09/03/90)

In article <1990Aug29.194009.6820@sdd.hp.com>, andrea@sdd.hp.com 
(Andrea K. Frankel) writes:

[in reference to `early EOLs' in G3 fax encoding]
|> 
|> 	-  Is this a valid, conforming implementation?  
|> 
|> 	-  Or should a robust implementation be able to decode
|> 	Group 3 files where some rows are ended "early" with an EOL 
|> 	(in which case presumably the rest of the row is white)?
|> 

Your two options aren't mutually exclusive.  Do you simply want a `valid,
conforming implementation' or do you want a robust implementation which is
useful to your customers?

I think that this is case where you want to apply different standards for
your encoder and decoder.  The encoder should generate files which conform
to the letter of the law, but your decoder should make all reasonable attempts
to decode anything it is given.  For one thing, if this is a real fax which
came from the error-prone analog world instead of our nice clean digital 
world, there is no guarantee that it hasn't been corrupted in transmission.

If you can assume that you are dealing with an error free image from a known
source, than you can probably take some short cuts which will speed things up,
but you risk getting burned later when you start getting images from a 
different source.

------------------------------------------------------------------------
Tom Morris				morris@casee.enet.dec.com
Digital Equipment,
Centre Technique Europe S.A.R.L		DTN 828-5729
B.P. 129 - Sophia Antipolis 		Tel. +33 92 95 57 29
06561 Valbonne Cedex - France		Fax  +33 93 65 41 58