Hi Piergiorgio,

"Piergiorgio Sartor" <piergiorgio.sartor@nexgo.REMOVETHIS.de> wrote in
message news:sqi861-e31.ln1@lazy.lzy...
> Looking for this things, I found also something else,
> it seems that, in case dithering with noise is required,
> the best noise is not "white", but "blue"...

Yes.  There is a really nifty halftoning technique called the "blue noise
mask" that has been patented and licensed to various printer manufacturers:

http://www.ece.rochester.edu/projects/blue_noise_mask/index.html

It is much prettier and simpler to use than F-S diffusion dithers, and
doesn't suffer from the same clipping (overaccumulation) problems.  The
patent means that I'm not going to use it for anything, but it might be
worth it for someone in the signal processing business to evaluate the
obvious one-dimensional analog as an alternative to noise shaping.

On Wed, 15 Oct 2003 22:10:49 -0400, Jerry Avins <jya@ieee.org> wrote:

>Adjusting according to the MSB of the lopped part only is feedback too.
>If you don't save the rest for later, one bit is the best you can do, as
>you concluded. I first ran into this when accumulating energy over a
>long period of time to calculate the internal temperature of a motor
>accurately enough to know when to shut it down. 16-bit integer quotient
>wasn't precise enough. The values calculated with rounding showed a
>random walk away from The One True Value. Mr. Fixit -- me -- got called
>in, and I came up with the scheme of accumulating the entire 8-bit
>remainder, and adjusting the accumulated quotient whenever the remainder
>register overflowed. (Two's complement with truncating toward negative
>infinity makes that easy -- no need to round.) That's why I called it
>"remainder saving" until Randy's more general "fraction saving" came to
>my attention. However you look at it, it keeps all of the information in
>the original signal as quantized, instead of giving some away in the
>gain divider. When forcing the signal to fewer bits, it keeps the
>original precision on average, yielding the closest possible to how the
>signal would have looked had it been originally sampled with the lower
>bit count.
>
>Had this been clear to me before, I would have trumpeted it loudly. It
>was just one of those things I knew in another context and didn't think
>much about. After all, it was a quick and dirty trick I dreamed up in
>the days before you guys taught me DSP. That said, I'm convinced of its
>utility. I think we're onto something.
>
>Jerry

I think I'm following now, and this is actually what I had in mind.

Cheers,

Eric
Eric Jacobsen
Minister of Algorithms, Intel Corp.
My opinions may not be Intel's opinions.
http://www.ericjacobsen.org

Jerry Avins wrote:

>> As usual Jerry as a long eye... :-)
> 
> Thanks (I think!)

Of course.
Actually I made a typo, should be "has" not "as"...

> Floyd-Steinberg Dithering, being two dimensional, isn't exactly the
> same as my suggestion, but the idea of saving and redistributing an
> error is common to both. For an extreme case of Floyd-Steinberg in
> action -- gray scale to black and white -- see

I think you got exactly the point, in the picture case
it is very convenient to redistribute the error to the
pixels around.

Looking for this things, I found also something else,
it seems that, in case dithering with noise is required,
the best noise is not "white", but "blue"...

> http://www.visgraf.impa.br/Courses/ip00/proj/Dithering1/floyd_steinberg_dithering.html 
> 
> Note that this isn't half-toning. With a true halftone, the dots (or
> holes) vary in size. Here, each pixel is either all black or all white.
> 
> Unless the error is redistributed, the result is equivalent to rounding 
> even when the quantizing level is carefully chosen. 
> http://www.visgraf.impa.br/Courses/ip00/proj/Dithering1/average_dithering.html 
> Shows how much cruder rounding is.

Thanks for the links, very useful.

bye,

-- 

piergiorgio

Piergiorgio Sartor wrote:

> Jerry Avins wrote:
> 
>> I suspect -- another to say that I'm willing to make a wild guess --
>> that fraction saving will work better than a sawtooth, and it's easier
>> to implement in the bargain. It will certainly push most of the added
>> noise to the upper end of the spectrum, and it may minimize it.
> 
> 
> As usual Jerry as a long eye... :-)

Thanks (I think!)
> 
> Just two words:
> 
> Floyd Steinberg

Piergiorgio,

Thanks for pointing me to this.

Floyd-Steinberg Dithering, being two dimensional, isn't exactly the
same as my suggestion, but the idea of saving and redistributing an
error is common to both. For an extreme case of Floyd-Steinberg in
action -- gray scale to black and white -- see
http://www.visgraf.impa.br/Courses/ip00/proj/Dithering1/floyd_steinberg_dithering.html 

Note that this isn't half-toning. With a true halftone, the dots (or
holes) vary in size. Here, each pixel is either all black or all white.

Unless the error is redistributed, the result is equivalent to rounding 
even when the quantizing level is carefully chosen. 
http://www.visgraf.impa.br/Courses/ip00/proj/Dithering1/average_dithering.html 
Shows how much cruder rounding is.
> 
> bye,
> 

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

Jerry Avins wrote:

> I suspect -- another to say that I'm willing to make a wild guess --
> that fraction saving will work better than a sawtooth, and it's easier
> to implement in the bargain. It will certainly push most of the added
> noise to the upper end of the spectrum, and it may minimize it.

As usual Jerry as a long eye... :-)

Just two words:

Floyd Steinberg

bye,

-- 

piergiorgio

robert bristow-johnson wrote:

> In article Xi6jb.56767$mQ2.43304@newsread1.news.atl.earthlink.net, Randy
> Yates at yates@ieee.org wrote on 10/15/2003 03:03:
> 
> 
>>>Randy Yates <yates@ieee.org> wrote in message
>>>news:<iniib.24587$Eo2.10343@newsread2.news.atl.earthlink.net>...
>>>
>>>
>>>>I would say that anyone who isn't using dither when digitizing a signal
>>>>isn't doing digital "right."
>>>
>>>
>>>unless there is something inherent in the algorithm function that it
>>>does no quantization.  two examples: moving sum (not average) filter
>>>or a mean-square function that returns a double word width relative to
>>>that of the input and window coefs.
>>
>>Wouldn't dither be useful in these examples too? E.g., in the moving
>>sum, not dithering may hide an offset that is < 1/2 LSB that would
>>otherwise be picked up. No?
> 
> 
> how would that offset exist in the moving sum filter?  i am assuming that
> there is no quantization.  is my assumption faulty?

I think I see what's happening here Robert. I'm talking about dither in
the input signal, not within the moving sum itself. Let's say the source
has a DC offset that is at 1/4 LSB. If the analog signal is real clean and
there's no dither, then you'll just see zero and when you moving sum you'll
get zero instead of N/4.

> r b-j
> 
> (finally home and detoxing from AES trip to NYC.  and i didn't get killed in
> the ferry accident, but the wind was so bad that the wingtip of the Jet Blue
> A-320 came within 12" of the ground upon landing at Burlington.)

Wow. Glad you're safe buddy.
-- 
%  Randy Yates                  % "...the answer lies within your soul
%% Fuquay-Varina, NC            %       'cause no one knows which side
%%% 919-577-9882                %                   the coin will fall."
%%%% <yates@ieee.org>           %  'Big Wheels', *Out of the Blue*, ELO
http://home.earthlink.net/~yatescr

This is a multi-part message in MIME format.
--------------060709020103080707070008
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit

robert bristow-johnson wrote:

>eric.jacobsen@delete.ieee.org (Eric Jacobsen) wrote in message news:<3f8b2809.432701556@news.west.earthlink.net>...
>  
>
>>On Sun, 12 Oct 2003 01:12:58 -0400, Jerry Avins <jya@ieee.org> wrote:
>>
>>    
>>
>>>Eric Jacobsen wrote:
>>>      
>>>
>> 
>>    
>>
>>>>Jerry, you've stumped me.  What's "fraction saving"?
>>>>        
>>>>
>
>the way i would describe it is: 1st-order noise shaping with a zero
>exactly on z=1 and the quantizer is always in round-down (floor(x))
>mode.  as Jerry says, it is taking whatever bits your quantizer
>dropped, zero extending them, then feeding them back (positively) and
>adding them into the next sample before it is quantized.
>
>
>  
>
>>>The process is similar to remainder saving when accumulating the results 
>>>of successive divisions. We played with that one in a thread some time 
>>>ago. R.B-J. described the process as a way to avoid limit cycles in 
>>>IIRs, I described its use in a lossy accumulator (same thing, really), 
>>>and Randy Yates provided the name. I think it should work wherever 
>>>truncation is needed. Call it "noise shaping" if you like, except 
>>>there's no oversampling.
>>>      
>>>
>
>it is "noise-shaping".
>
>r b-j
>  
>
Robert,
Taking Jerry's description and your comments together, particularly the 
comment about 'noise-shaping',
it occurs to me that the process is virtually the same as delta 
modulation. 

Granted, the quantisation will probably be 16 bits, whereas delta 
modulation quantisation
is commonly one bit, but apart from that, all the elements are the 
same.  The main difference is that the
high-precision signal sample is already digital instead of analog, so I 
refer to it as 'analog-ish'.

The process as described is:
1.  The high-precision ('analog-ish') signal sample is quantised.
2.  The exact value of the quantised sample is subtracted from the 
high-precision ('analog-ish') sample.
3.  The quantised part is stored or transmitted.
4,.  The difference, or 'error' is saved ('integrated'). 
5.  The next high-precision signal sample is then added to the 
integrated error and the process repeats.

I like the idea that Jerry describes of not discarding the left-over 
bits when you truncate, and it
appears to be a big improvement on simple rounding, with or without 
dithering.

Regards,
John



--------------060709020103080707070008
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
  <meta http-equiv="Content-Type" content="text/html;charset=ISO-8859-1">
  <title></title>
</head>
<body text="#000000" bgcolor="#ffffff">
robert bristow-johnson wrote:<br>
<blockquote type="cite"
 cite="mid4cbb922e.0310140622.33673e6c@posting.google.com">
  <pre wrap=""><a class="moz-txt-link-abbreviated" href="mailto:eric.jacobsen@delete.ieee.org">eric.jacobsen@delete.ieee.org</a> (Eric Jacobsen) wrote in message news:<a class="moz-txt-link-rfc2396E" href="mailto:3f8b2809.432701556@news.west.earthlink.net">&lt;3f8b2809.432701556@news.west.earthlink.net&gt;</a>...
  </pre>
  <blockquote type="cite">
    <pre wrap="">On Sun, 12 Oct 2003 01:12:58 -0400, Jerry Avins <a class="moz-txt-link-rfc2396E" href="mailto:jya@ieee.org">&lt;jya@ieee.org&gt;</a> wrote:

    </pre>
    <blockquote type="cite">
      <pre wrap="">Eric Jacobsen wrote:
      </pre>
    </blockquote>
    <pre wrap=""> 
    </pre>
    <blockquote type="cite">
      <blockquote type="cite">
        <pre wrap="">Jerry, you've stumped me.  What's "fraction saving"?
        </pre>
      </blockquote>
    </blockquote>
  </blockquote>
  <pre wrap=""><!---->
the way i would describe it is: 1st-order noise shaping with a zero
exactly on z=1 and the quantizer is always in round-down (floor(x))
mode.  as Jerry says, it is taking whatever bits your quantizer
dropped, zero extending them, then feeding them back (positively) and
adding them into the next sample before it is quantized.


  </pre>
  <blockquote type="cite">
    <blockquote type="cite">
      <pre wrap="">The process is similar to remainder saving when accumulating the results 
of successive divisions. We played with that one in a thread some time 
ago. R.B-J. described the process as a way to avoid limit cycles in 
IIRs, I described its use in a lossy accumulator (same thing, really), 
and Randy Yates provided the name. I think it should work wherever 
truncation is needed. Call it "noise shaping" if you like, except 
there's no oversampling.
      </pre>
    </blockquote>
  </blockquote>
  <pre wrap=""><!---->
it is "noise-shaping".

r b-j
  </pre>
</blockquote>
Robert, <br>
Taking Jerry's description and your comments together, particularly the
comment about 'noise-shaping', <br>
it occurs to me that the process is virtually the same as delta
modulation.&nbsp; <br>
<br>
Granted, the quantisation will probably be 16 bits, whereas delta
modulation quantisation<br>
is commonly one bit, but apart from that, all the elements are the
same.&nbsp; The main difference is that the<br>
high-precision signal sample is already digital instead of analog, so I
refer to it as 'analog-ish'.<br>
<br>
The process as described is:<br>
1.&nbsp; The high-precision ('analog-ish') signal sample is quantised.<br>
2.&nbsp; The exact value of the quantised sample is subtracted from the
high-precision ('analog-ish') sample.<br>
3.&nbsp; The quantised part is stored or transmitted.<br>
4,.&nbsp; The difference, or 'error' is saved ('integrated').&nbsp; <br>
5.&nbsp; The next high-precision signal sample is then added to the
integrated error and the process repeats.<br>
<br>
I like the idea that Jerry describes of not discarding the left-over
bits when you truncate, and it<br>
appears to be a big improvement on simple rounding, with or without
dithering.<br>
<br>
Regards,<br>
John<br>
<br>
<br>
</body>
</html>

--------------060709020103080707070008--

A neat extension gives you more control over the effect of this dithering:
First, make a minimum phase hi-pass filter and calculate its impulse
response.  Then, before quantizing a sample, add that response to the
pending input, scaled to make the quantization error come out to zero for
the current sample before you quantize it.  When you're finished with all
the input, you know that the total error you added to the signal had no
low-frequency components, because you explicitly constructed it out of
high-pass responses.  Many sigma-delta modulators can be characterized this
way.

robert bristow-johnson wrote:

> In article bmkvk1$sfj$2@bob.news.rcn.net, Jerry Avins at jya@ieee.org wrote
> on 10/15/2003 22:26:
> 
> 
   ...
> 
> 
>>Divide by N?
> 
> 
> then it would be a moving *average*, not a moving sum.  of course the moving
> average would normally have quantization and dithering and/or noise-shaping
> would be useful, but if there is no quantization in a digital operation, why
> would either dithering or noise-shaping be necessary?
> 
> r b-j
> 

Why? It wouldn't. Sometimes -- this is one of them, -- I see what I'm 
thinking, instead of what's on the page.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

In article bmkvk1$sfj$2@bob.news.rcn.net, Jerry Avins at jya@ieee.org wrote
on 10/15/2003 22:26:

> robert bristow-johnson wrote:
> 
>> In article Xi6jb.56767$mQ2.43304@newsread1.news.atl.earthlink.net, Randy
>> Yates at yates@ieee.org wrote on 10/15/2003 03:03:
>> 
>> 
>>>> Randy Yates <yates@ieee.org> wrote in message
>>>> news:<iniib.24587$Eo2.10343@newsread2.news.atl.earthlink.net>...
>>>> 
>>>> 
>>>>> I would say that anyone who isn't using dither when digitizing a signal
>>>>> isn't doing digital "right."
>>>> 
>>>> 
>>>> unless there is something inherent in the algorithm function that it
>>>> does no quantization.  two examples: moving sum (not average) filter
>>>> or a mean-square function that returns a double word width relative to
>>>> that of the input and window coefs.
>>> 
>>> Wouldn't dither be useful in these examples too? E.g., in the moving
>>> sum, not dithering may hide an offset that is < 1/2 LSB that would
>>> otherwise be picked up. No?
>> 
>> 
>> how would that offset exist in the moving sum filter?  i am assuming that
>> there is no quantization.  is my assumption faulty?
>> 

> Divide by N?

then it would be a moving *average*, not a moving sum.  of course the moving
average would normally have quantization and dithering and/or noise-shaping
would be useful, but if there is no quantization in a digital operation, why
would either dithering or noise-shaping be necessary?

r b-j