Hacker News new | past | comments | ask | show | jobs | submit login
Bug or Feature? Unintentionally Intentional Behaviors (xiph.org)
123 points by espadrine on March 26, 2015 | hide | past | favorite | 20 comments

This story I think very neatly points out the difference between verification and validation -- and why it's important to have both of them in a testplan for anything new.

In short, verification asks the question: "does it do what we designed it to do?" For instance, if you have a reference encoder of some kind that is a verbatim translation of a specification, and a high-performance encoder that is designed to squeeze every last drop out of the system, you can verify the high-performance version by comparing the output to the reference; if they're the same, then you know that the high-performance version, at least on some level, works as designed.

If verification compares the design against the implementation, then validation asks the question: "is the design what it needs to be?". The story that xiphmont told here is a validation issue: the implementation is perfectly correct, but it's the design that isn't what he'd hoped for! Although verification often takes more of the time than validation, in my experience, validation often seems to take quite a lot more creativity than verification.

Thanks to Monty for writing this up, and providing such an illustrative example of the difference! It's a useful distinction to have, especially when looking at errors that escaped testing and made it to production.

I've had a lot of these problems where everything is correct but nothing works as intended. Turns out, numerical mathematics excels at making programming more about validation than verification.

Breaking the continuum into pieces breaks your symmetries. For example on a finite rectangular grid, a sphere is not rotationally invariant. Even if your maths is valid in the continuum, for the implementation, you still need to prove that it is valid (i.e. fulfills all desired properties) on a discrete grid.

I have zero experience with video compression, however, the author states that the issues get less severe when the video is rotated by 90˚. I guess the compression algorithm is designed to work irrespective of orientation. Therefore, my humble guess is that they failed to implement the desired symmetry of the continuum in the compression algorithm that acts upon discrete spatial coordinates. Unfortunately, there's no way to recover all symmetries from the continuum on a discrete grid. You always get some kind of artifacts and you can only work to reduce them for the case you are considering.

As you put it, validation requires that you ask the right questions, which is half the ball game.

For anyone that wants to get started hacking on Daala, we keep a list of easy, good first bugs here on GitHub.


It's a really fun project to hack on!

I assume this article is written for people who already know about Daala. I had to search on the name to learn it's a video compression technology. After that the article made more sense, but a 2-3 sentence introduction at the start of the article would help people like me.

Point taken, short intro added.

This article needs to be read by any executive trying to push aggressive ship dates.

It's hard to explain why development is not always easy but I think this provides a pretty sobering example.

I see these two links submitted yesterday (the 2nd very briefly on front page) but no discussion:

https://www.ietf.org/mail-archive/web/video-codec/current/ms... http://www.ietf.org/proceedings/92/slides/slides-92-netvc-0....

Realistic that there could be an industry consensus next generation video codec (like Opus for audio) with Daala as basis?

I hope it will work out. It worked for Opus for WebRTC as a mandatory codec, though I'm not sure if Opus was proposed as mandatory for the audio tag (I think it should).

Xiph used preemptive approach and refuted all accusatoins and patent attacks on Opus as soon as they surfaced, which helped its acceptance in IETF. They plan the same tactic for Daala which hopefully would kill all the FUD. That's in contrast with VPx where Google waited for lawsuits instead of defending it right away and refuting any false accusations.

However IETF acceptance doesn't mean that the likes of Apple will actually start using it. But making it mandatory for the video tag would be a big victory, since those who refuse to support it will be under pressure to follow the standard.

> I'm not sure if Opus was proposed as mandatory for the audio tag (I think it should).



> Status: Rejected Change Description: No spec change. Rationale: See Ian and Adrian's rationale in comment 2 and comment 3.

> #2: Working groups can't force a browser to implement something. Are all the browser vendors willing to implement it? That's what matters.

> #3 Microsoft doesn't believe HTML5 needs to specify a mandatory to implement codec. The market is quite capable of ensuring that popular formats are supported on the web. Opus did not exist when ISSUE-7 was closed. Who knows what formats might be more popular than this by the time HTML5 gets to Recommendation, or after that. It's also not clear that there will be widespread adoption of Opus for the purposes that <audio> is currently used.

This does not mean Microsoft is for or against supporting Opus with <audio>, just that the spec doesn't need to say anything on this.

Rationale is invalid, since in other instances standard is enforcing something (same WebRTC). And of course MS was brought as the main antagonist. Some apparently just hate when the Web has interoperability.

Well, there are other ways to tell them that this interoperability is important: https://wpdev.uservoice.com/forums/257854-internet-explorer-... (no registration required to vote).

Thanks for the link!

Opus is brilliant, both technically and strategically, but its worth noting that despite technical superiority, there's still not a word out of Apple on the subject, Microsoft (despite co-developing it via their Skype purchase) have dragged their heels on this for a long time and still seem reluctant to use it for non-WebRTC audio, and the various groups surrounding ITU/MPEG are still pushing their royalty bearing alternatives via bundling and backroom deals between patent holders.

Even if this new video codec beats the alternative on several dimensions, it'll be a struggle to get adoption for similar reason of entrenched patent owners and business interests.

I can't really bring myself to blame corporations for following short term private gain, but all the nerds who ignored licencing issues in favour of short term technical superiority deserve some blame for this local minimum we're trapped in.

> I can't really bring myself to blame corporations for following short term private gain

Why not? They should be blamed for it, especially when they sabotage interoperability for such gain. This irritates me the most in these companies.

> the nerds who ignored licensing issues in favour of short term technical superiority deserve some blame for this local minimum we're trapped in.

That's free codecs should be ahead of the competition by a big margin. Daala is not just next generation, it's next next generation, which increases its chances to beat patent encumbered competitors and to actually gain traction. No matter what backroom deals can be proposed, if someone can save tons of money on licensing and get much higher quality, it's a no brainier to do it.

This is the latest in a series of posts on Daala: https://people.xiph.org/~xiphmont/demo/

Years ago we discussed the idea of penalizing errors more if they stick around. So a difference of +2 might be acceptable for a frame or two, but a consistent +2 over several frames should be severely penalized due to the fact that the human visual system is much more likely to notice an artifact that lasts 300 ms versus one that lasts 30. Whereas 10 frames alternating +2 with -2 would be acceptable.

Perhaps that sort of logic is rolled into the rate distortion metrics of Daala? But if so, I suspect this bug would not be.

Well, one has to be careful here. In a static portion of a scene, a consistent error likely to look much better than an error that flips between being too large and too small in alternate frames, since the latter will show up as noise or flicker that was not in the original. That can be more objectionable than simply being slightly wrong. Notably none of the metrics we use for evaluating Daala have any means of measuring this.

The better approach, I think, is some form of "temporal RDO", where you spend more bits on places that will be good predictors of future frames. We discussed the idea in a Theora update in 2010 [0]. x264 implemented it even before then (under the name "mbtree" [1]). It is not yet implemented in Daala, as we do not have two-pass rate control or lookahead yet. It's possible to do one-pass, no-lookahead versions by estimating future prediction efficiency based on the past, but you want one with full lookahead to compare against to make sure those estimates are doing the right thing.

I am not sure temporal RDO would save us here, because the issues described only occur in areas of the frame that are being updated. It still might have, in this case---these things are relative---but we could construct cases where it would fail to do so.

[0] https://people.xiph.org/~xiphmont/demo/theora/demo9.html

[1] http://www.x264.nl/developers/Dark_Shikari/MBtree%20paper.pd...

I pity Daala got delayed to 2016, but on the other hand it should be noticeably better than competition in order to succeed, so it's good they are taking their time.

I don't know what it is, but the xiph.org blog posts always seem so well written and interesting to me. Probably that I perceive the subject matter as magic :)

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact