Zero Crossing detection

That’s the fundamental code snippet, which will return a list of all zero (to positive value) crossings. It’s up to you to build a stretch routine or whatsoever from it.
My main goal was to implement it in the “Append Tracks Deluxe” plug-in. Eventually it should produce the sound in between the played transitions, just as if you would press a fast forward button, but without a pitch-change (a replacement for pitchift). But the current routine which puts all together is much too slow and thus I won’t post it.

;;indexing
(Defun split (sig size)
(let* ((sr (snd-srate sig)) (split-list (list 0))
(single (snd-from-array 0 sr (vector (/ (float size))))) 
(zero (snd-from-array 0 sr #(0)))
(index (mult  sr (integrate (trigger sig  single))))
(last (sref (sound index) (* (- (snd-length index ny:all) 
1)  (/ sr)))))
(display "" last)
(dotimes (num (truncate last))
(setf split-list (cons (float (sref-inverse index (1+ num))) split-list)))
(reverse (cons (second (snd-extent sig ny:all)) split-list))
)); end split

Size is the number of periods that are skipped i.e. every “size”-th time will be returned. Have fun.

Well it’s pretty quick, but sometimes it seems to slightly miscount.
In tests it appears to sometimes be out by one on “size”, and very occasionally mark positive to negative crossings instead of negative to positive.

Example:

Generate 7 seconds sine tone at 440 Hz with a track sample rate of 44.1 kHz

(print (split s 1000))

returns:
(0 2.27274 4.54546 6.81594 7)

By my reckoning, the 4th value should be 3000/440 = 6.8181818…
The actual value returned is 1 cycle early: 2999/440 = 6.81590909…

I didn’t test your example yet but I encountered similar problems myself, that’s why it isn’t used in the “Align Tracks Deluxe” plug-in for the time being. However, a similar procedure is used to determine the start and end times in order to truncate a sound, where the following correction is applied.

The problem seems to lie in the s-ref-inverse function. After the integration of our “index”-signal above those values could be put out:
(000111223333)
According to the documentation, s-ref-inverse returns the time where a sound’s sample reaches a given value for the first time. From the number above we would expect that a search for 1 returns the time for the forth position. Thats not the case because the sample value must be slightly greater than the value we’re looking for. Here, the function will return 6.xx seconds (at sample-rate 1).
In other words, we must use s-ref-inverse with a slightly smaller value, e.g. 0.9999.
For the code above, we must subtract a little amount from (+1 num). It needs a little experimenting to find the proper value.

Is the problem simply be due to rounding errors, being that some numbers cannot be expressed exactly in single precision float?

It’s difficult to say how much a rounding error influences the result.
A little notice: The code above delivers the times of the first positive sample. The next snippet returns the times of the zero crossing:

;;indexing
(Defun split (sig size)
(let* ((sr (snd-srate sig)) (split-list (list 0))
(single (snd-from-array 0 sr (vector (/ (float size))))) 
(zero (snd-from-array 0 sr #(0)))
(index (mult  sr (integrate (seq (trigger sig single) zero))))
(last (truncate (snd-maxsamp index))))
(display "" last)
(snd-display sig)
(dotimes (num last)
(setf split-list (cons (-(sref-inverse index num ) (/ 1 *sound-srate*)) split-list)))
(reverse (cons (second (snd-extent sig ny:all)) split-list))
)); end split

(setf amount-samples 55 )
(setf sig  (abs-env (seq (s-rest (/ 4 *sound-srate*))
(osc (hz-to-step 4410) (/ amount-samples *sound-srate*) *table* 0))) )
(setf zeros (split sig  1))
(dotimes (num (length zeros))
(format t "~%  Sample #~a, Value ~a" 
(* (nth num zeros) *sound-srate*)
(sref (sound sig) (nth num zeros))))

The numbers returned are very close to zero (the quadrillionth part of the full scale, -290 dB).
It gets interesting when we change the phase of the sine curve of OSC: The value returned is -0.309 whereas the sample to the right would be the same but positive (see values of the sound at the top of the debug screen).
It’s impressive how huge the influence of the phase is on high frequencies. The source of the strange values is the resolution in the time domain i.e. the sample rate. It’s no miracle that in practice a window is used to create smooth cuts at the edges when composing a new sound from parts of our list.
Maybe the results could be slightly improved by choosing the smallest value from two neighbouring samples.
However, I prefer the multiplication with a padded envelope like in your brickwall limiter, Steve).

This is not solving the exact same problem of listing all zeroes, but rather finding the nearest zero to a given time (repeatedly for different times).

Examine the sound once and create some big arrays, but then find your zero crossings in a constant-time, random-access fashion.

Is this a good adaptation of your method?

(defun make-zero-crossing-finder (snd)
  (let* ((srate (snd-srate snd))
	 (blip (snd-from-array 0 srate (vector srate)))
	 (blips (trigger snd blip))
	 (count-of-crossings-snd (integrate blips))
	 (inv-snd (snd-inverse count-of-crossings-snd 0 1))
	 (inv-array (snd-fetch-array inv-snd (snd-length inv-snd ny:all) 1))
	 (inv-array-len (length inv-array))
	 (count-of-crossings-array
	  (snd-fetch-array (snd-copy count-of-crossings-snd)
			   (snd-length count-of-crossings-snd ny:all) 1))
	 (count-of-crossings-len (length count-of-crossings-array)))
    ;; global time
    ;; find the nearest crossing to either side
    ;; or return nil if out of bounds
    #'(lambda (time)
	(let ((index (truncate (* time srate))))
	  (and (>= index 0)
	       (< index count-of-crossings-len)
	       (let ((num (truncate
			   (aref count-of-crossings-array index))))
		 (and (>= num 0)
		      (< num inv-array-len)
		      (let*
			  ((t1 (aref inv-array num))
			   (t2 (if (< (1+ num) (length inv-array))
				   (aref inv-array (1+ num))
				   t1))
			   (diff2 (abs (- time t2)))
			   (diff1 (abs (- time t1))))
			(if (< diff1 diff2) t1 t2)))))))))

Usage:

(let ((finder (make-zero-crossing-finder snd))) ... (funcall finder global-time) ...)

Thank you very much, Paul.
It is maybe worth mentioning that your codelet Returns only negative-positive crossings, i.e. the beginning of a sine-wave-like cycle.
You’ve used a lot snd-fetch-array. Wouldn’t it be easier to use ‘(snd-samples snd ny:all)’?
At least there where the Sound is copied.
Anyway, a fine Little modul.

You know, I love list structures and dislike Arrays.
Lists are much more flexibel and easier to handle.
Arrays - in contrast - have a faster Access and use 4 Bytes less Memory (but still quite a lot about 14).
Here’s my Version of your nearest Zero crossing example.

(defun nigh-zero (sig time &aux *index*)
  (snd-length (snd-trigger sig 
     #'(lambda (t0) (push t0 *index* ) (s-rest 0))) ny:all)
  (sort *index* #'(lambda (a1 a2) 
                       (< (abs (- a1 time)) (abs (- a2 time))))))
(print (nigh-zero (abs-env (hzosc 10)) 0.55))

The returned list is ordered such that the nearest negative-positive crossing is the car of the list (which could of course be returned alone, inorder to free the Memory bound to the list).
Snd-length is only a dummy function to force the Evaluation of snd-trigger.
If another value than ny:all is passed the Sound will be searched up to this length.
one would normally just send a Portion of the Sound to be examined and so I’ve omitted the additional Parameter.

Since I posted, I decided on a revision, based on experiment. It seems I had an off-by-one error, and that the following truly finds the nearest crossings. At least for some selections. You see, the time of the first zero-crossing is not the first but the zeroth element of the array obtained from the snd-inverse sound. Now as you know I have some puzzlement with snd-inverse so perhaps I’ll ultimately have to take the best of three. Perhaps the zeroth element is sometimes zero. So, be warned for now. DIfferences are all in the last let*.

(defun make-zero-crossing-finder (snd)
  (let* ((srate (snd-srate snd))
	 (blip (snd-from-array 0 srate (vector srate)))
	 (blips (trigger snd blip))
	 (count-of-crossings-snd (integrate blips))
	 (inv-snd (snd-inverse count-of-crossings-snd 0 1))
	 (inv-array (snd-fetch-array inv-snd (snd-length inv-snd ny:all) 1))
	 (inv-array-len (length inv-array))
	 (count-of-crossings-array
	  (snd-fetch-array (snd-copy count-of-crossings-snd)
			   (snd-length count-of-crossings-snd ny:all) 1))
	 (count-of-crossings-len (length count-of-crossings-array)))
    ;; global time
    ;; find the nearest crossing to either side
    ;; or return nil if out of bounds
    #'(lambda (time)
	(let ((index (truncate (* time srate))))
	  (and (>= index 0)
	       (< index count-of-crossings-len)
	       (let ((num (truncate
			   (aref count-of-crossings-array index))))
		 (and (>= num 0)
		      (< num inv-array-len)
		      (let*
			  ((t2 (aref inv-array num))
			   (t1 (if (plusp num)
				   (aref inv-array (1- num))
				   t2))
			   (diff2 (abs (- time t2)))
			   (diff1 (abs (- time t1))))
			(if (< diff1 diff2) t1 t2)))))))))

Yes, this only finds rising zero crossings: or to be precise, transitions from non-positive to positive, which is what trigger does. I think the one-line change to give you both non-positive to positive, and non-negative to negative, transitions is:

	 (blips (sum (trigger snd blip) (trigger (prod (-1) snd) blip)))

I learn things from you daily, Robert. I can simplify with snd-samples. I did not know that a behavior could be a lambda with side effects.

Your function may be good to find one nearest zero to one parameter, but not, I think, for repeated examination of one sound.

I did not know that a “behavior” could also be a closure. You gather your list as trigger evaluates. If I could gather an array instead, I could dispense with the integrate step. But I’d have to preallocate enough space, taking snd-length over 2 pessimistically, and will it really beat the use of the built-in C functions?

Wow, it seems snd-fetch-array and snd-samples may differ subtly in how they generate values!

Would you believe that the rewrite with snd-samples caused subtle changes that broke something I wrote to rely on this?

The array count-of-crossings-array contains floating point numbers that are ideally integers but might not be. I wrote debug prints with both versions and dumped the array, and it printed as integers either way. But the value num was sometimes one too few in the broken version.

Change the truncations to roundings and all was well again.

But I am still not satisfied that I have treated all the edge cases.

After more experimentation, I give you a more elaborated version, with more protection against the funny boundary cases. I hope the elegant idea doesn’t get too obscured. I have a more explicit idea now about what behavior of snd-inverse I am depending on. I do not understand the conditions for the (only sometimes) loss of the last sample of its input, but I fully compensate for that problem anyway now.

Updated: Now I even compensate for the lost last sample in integrate! And improved comments.

Update: I still have an off-by-one error in the placement of the crossings. I understand the problem and I am fixing it. I also want to make a zero-crossings iterator that lets you find all the crossings sequentially using similar methods.

(defun make-upward-zero-crossing-finder (snd)
  (let* ((t0 (snd-t0 snd))
	 (srate (snd-srate snd))
	 (half-sample (/ (* 2 srate)))
	 (blip (snd-from-array 0 srate (vector srate)))
	 (blips (trigger snd blip))

	 ;; beware, integrate always puts 0 in the first sample of the result,
	 ;; and neglects the last sample of the input.
	 (count-of-crossings-snd (integrate blips))
	 (count-of-crossings-array (snd-samples count-of-crossings-snd ny:all))
	 (count-of-crossings-len (length count-of-crossings-array))
	 (last-count
	  (and (plusp count-of-crossings-len)
	       (aref count-of-crossings-array (1- count-of-crossings-len))))

	 ;; notes about snd-inverse:  when the given function is not
	 ;; strictly increasing, the inverse is underdetermined.  Behavior
	 ;; of snd-inverse appears to be that the time of the LAST sample
	 ;; for each value the function attains is the answer given
	 ;; by snd-inverse.  I rely on this assumption!
	 ;; Also snd-inverse seems SOMETIMES to neglect the last sample of its
	 ;; input, and sometimes not.
	 (inv-snd (snd-inverse count-of-crossings-snd 0 1))
	 (inv-array (snd-samples inv-snd ny:all))
	 (inv-array-len (length inv-array))
	 (inv-array-len-m1 (1- inv-array-len))

	 ;; trigger is supposed to find transitions from non-positive to
	 ;; positive.  But experiment shows that whenever the first sample
	 ;; is positive, it is also treated as a crossing.  Reject this
	 ;; spurious crossing unless the first sample is negative or "tiny"
	 ;; (arbitrarily defined here).
	 ;; make this an optional argument?
	 (tiny (db-to-linear -55))
	 (bogus-crossing-at-0 (>= (snd-sref snd t0) tiny))

	 ;; Should we pretend there is a crossing at the end?  Deferred
	 ;; calculation to avoid snd-length.  Return a time or nil.
	 ;; This also compensates for the loss of the last sample to integrate.
	 (extra-crossing
	  #'(lambda ()
	      (let ((s-len (snd-length snd ny:all)))
		(and (plusp s-len)
		     (let* ((tn (+ t0 (/ (1- s-len) srate)))
			    (sample (snd-sref snd tn)))
		       (if (plusp sample)
			   (and (> s-len 1)
				(not (plusp
				      (snd-sref snd (- tn (* 2 half-sample)))))
				;; a rising crossing left of the very last
				;; sample, which is non-negative
				(- tn half-sample))
			   (and (> sample (- tiny))
				;; the last sample is slightly negative, so
				;; call it an upward crossing just past the end.
				(+ tn half-sample)))))))))

    ;; return a function that takes global time
    (if (or (< inv-array-len 2)
	    (and bogus-crossing-at-0 (= inv-array-len 2)))
	;; there are no crossings
	#'(lambda (time) nil)

	;; find the nearest crossing to either side
	;; or return nil if out of bounds
	#'(lambda (time)
	    (let* ((tt (- time t0))
		   (index0 (truncate (+ 0.5 (* tt srate)))))
	      ;; bounds check for valid time interval
	      (and (>= index0 0)
		   (< index0 count-of-crossings-len)
		   (let* ( ;; Because of the initial 0 always made by integrate,
			  ;; (aref count-of-crossings-array index0)
			  ;; is the count of upward zero crossings BEFORE
			  ;; index0, not at-or-before.  So add 1 if we can.
			  (index (if (= index0 (1- count-of-crossings-len))
				     ;; oops, we bump against the problem
				     ;; of the lost sample in integrate.
				     ;; do the best we can.
				     index0
				     (1+ index0)))
			  ;; How many (real or bogus) crossings at or before?
			  ;; count-of-crossings array contains what should be
			  ;; integers, computes as floats -- be careful to
			  ;; round off.
			  (num (truncate
				(+ 0.5
				   (aref count-of-crossings-array index))))
			  ;; Time of last sample before the next crossing
			  ;; after index, if it exists, plus a half sample
			  (t-after (if (< num last-count)
				       (+ (aref inv-array num) half-sample)
				       (funcall extra-crossing)))
			  ;; Are there any real crossings at or before index?
			  (should-look-left
			   (not (or (zerop num)
				    (and (= num 1) bogus-crossing-at-0))))
			  ;; Time of the last real sample before the last
			  ;; crossing at or before index, plus a half sample
			  ;; -- or nil:
			  (t-before
			   (and should-look-left
				(+ half-sample (aref inv-array (1- num))))))
		     (if (and t-before
			      (or (not t-after)
				  (< (- time t-before) (- t-after time))))
			 t-before
			 t-after))))))))

Finally, here is a very carefully worked out version, with an option to make a function that finds the nearest crossings to a given time, or a function that is called repeatedly to get an increasing sequence of crossing times.

Upward crossings only.

Thanks to Robert for the idea for avoiding inner loops in Lisp by use of the right Nyquist functions.

Updated: fixed my confusion about whether to subtract half a sample time from calculated times (No!)
Zero Crossings.lsp (6.04 KB)

I decided there was yet more work needed and boundary cases to handle… I’ll move this discussion to New Nyquist Plug-ins.

Here: http://forum.audacityteam.org/viewtopic.php?f=42&t=72185&p=211363#p211363

I decided to avoid snd-fetch-array and snd-samples altogether and just use snd-sref. It turns out snd-samples is prohibitive for even a few minutes’ duration. I might guess that either Nyquist, or the Lisp runtime system, is doing something dumb in the production of a big continuous array in memory, such as growing it linearly instead of exponentially. Something was behaving nonlinearly with length of selection.

A few minutes?
Your code (at least the one listed above, not the lsp file which I’ve not tested yet) crashes for sounds longer than 30 seconds.
And the Output is rather strange, it Returns a half or even whole sample-time too much on the right side. And the reseting to local time confused me a Little, e.g. if you want to Analyse s from 10 s to 11 s, it Returns a value which is multiplied by the sound-srate something like 200.5 insted of 441200.
I can’t see any Advantages for my scripts because I only Need a few crossings which my 5-line code (similar to the one above) Returns perfectly and even faster.
The non-linearity may be due to some Floating Point Errors. I believe there is something mentioned anywhere in the documentation or a tutorial.

Since my first posted version I did fix some off by one errors.

I have also decided (elsewhere in the Plug-ins board) to avoid use of snd-fetch-array and snd-samples entirely. This is what seems to crash using modestly large samples.

I wrote it to take and return “global” times in seconds which are suitable for use unchanged in defining labels.

I know I will find this useful, because I am writing some analyzers to make lots of little labels and I want zero-crossing refinement of each.

After some attempts to rewrite SilenceMarker.ny with these routines, it seems it doesn’t really improve performance over loops to snd-fetch. Still I think it will be a programming convenience.

Very large arrays can cause problems - apart from anything else they use a huge amount of memory. The best way to use snd-fetch-array with long selections is to set the array size to a “reasonable” figure, and call it repeatedly as necessary so as to process the track in blocks of samples.

My growing understanding of Nyquist is that Lisp expressions for sounds describe procedures for later evaluation of samples on demand.

I presume that once samples are generated, they are cached for faster repeated access. That’s what the description of snd-length and snd-flatten seems to imply, because it forces evaluation of all samples internally, and the documentation even recommends calling them in some cases where the unevaluated sound may take up even more memory.

But calling snd-length on the minutes-long selection is not so prohibitive. Whatever storage is behind it must not be the same inefficient array that snd-samples constructs.

So I’m wondering how to improve things further by avoiding snd-length. Is there some function that tells me “this time is before the ending time of the sound,” i.e. “more samples follow,” without forcing the computation of the samples?

You will need to give more context to your question.
For sounds that are passed from Audacity [“S”], you have “LEN” and “GET-DURATION” which do not need to be calculated.
In some cases you can defer finding the end by simply processing until the sound becomes NIL (an approach that is frequently used in DSP).