This page holds the results of Time Domain Lapped Transform (TDLT) optimization problems looking for integer transform coefficients that provide optimal coding gain. Wherever possible the assumptions are stated. Later we should include testing against actual image data to verify the results (see test data [http://people.xiph.org/~tterribe/tmp/subset1-y4m.tar.gz here]).

The coding gain objective used as the objective is taken from slide 13 of Tim's presentation [http://people.xiph.org/~tterribe/pubs/lca2012/auckland/intro_to_video1.pdf An Introduction to Video Coding]

<need figure with block matrix diagrams>

The free parameters are initially just the coefficients p_0,...,p_m,q_0,...,q_m where m=(n/2)-1. We limit these to being dyadic rationals, e.g., x/2^d with d=6, between [-1,1].

Given p's and q's and assuming a linear ramp constrains the s's.

== 4x8 ==

Optimal real-valued coefficients for V:

p0 = -0.18117338915051454

q0 = 0.6331818230771687

CG = 8.60603

{|
!
!p0
!q0
!s0
!s1
!CG
|-
|R=f
| -11/64 -0.171875
| 36/64 0.5625
| 91/64 1.421875
| 85/64 1.328125
|   8.63473
|-
|R=t,D=f
| -12/64 -0.1875
| 41/64 0.640625
| 92/64 1.4375
| 1093/768 1.423177
|   8.60486
|-
|R=t,D=t
| -16/64 -0.25
| 41/64 0.640625
| 92/64 1.4375
| 93/64 1.453125
|   8.59886
|}

== 8x16 ==

Optimal real-valued coefficients for V:

p0 = -0.39460731547057293

p1 = -0.33002212811740816

p2 = -0.12391270981321137

q0 = 0.822154737511288

q1 = 0.632488694485779

q2 = 0.40214668677553894

CG = 9.56867

{|
!
!p0
!p1
!p2
!q0
!q1
!q2
!s0
!s1
!s2
!s3
!CG
|-
|R=f
|-
|R=t,D=f
| -26/64 -0.40625
| -22/64 -0.34375
| -8/64 -0.125
| 53/64 0.828125
| 41/64 0.640625
| 26/64 0.40625
| 11/8 1.375
| 879/768 1.14453125
| 1469/1280 1.14765625
| 275/224 1.2276785714285714
|   9.56627
|-
|R=t,D=t
| -24/64 -0.375
| -20/64 -0.3125
| -4/64 -0.0625
| 53/64 0.828125
| 40/64 0.625
| 24/64 0.375
| 88/64 1.375
| 75/64 1.171875
| 76/64 1.1875
| 76/64 1.1875
|   9.56161
|}

== 16x32 ==

Best-known real-valued coefficients for V (R=t):

p0 = -0.42111473798940136

p1 = -0.4121736499899753

p2 = -0.3350240707669929

p3 = -0.3224547931861314

p4 = -0.25883387978005545

p5 = -0.20951913473498104

p6 = -0.0598657149803332

q0 = 0.9107782439906195

q1 = 0.8109855829278226

q2 = 0.715846584586721

q3 = 0.6135951570714172

q4 = 0.49846644853347627

q5 = 0.3945215834922529

q6 = 0.21822275136248082

CG = 9.81157

{|
!
!p0
!p1
!p2
!p3
!p4
!p5
!p6
!q0
!q1
!q2
!q3
!q4
!q5
!q6
!s0
!s1
!s2
!s3
!s4
!s5
!s6
!s7
!CG
|-
|R=f
|-
|R=t,D=f
| -26/64 -0.40625
| -23/64 -0.359375
| -20/64 -0.3125
| -18/64 -0.28125
| -14/64 -0.21875
| -14/64 -0.21875
| -2/64 -0.03125
| 58/64 0.90625
| 52/64 0.8125
| 45/64 0.703125
| 36/64 0.5625
| 31/64 0.484375
| 23/64 0.359375
| 16/64 0.25
| 3/2 1.5
| 77/64 1.20313
| 373/320 1.16563
| 543/448 1.21205
| 109/96 1.13542
| 1543/1408 1.09588
| 1823/1664 1.09555
| 131/120 1.09167
|   9.79008
|-
|R=t,D=t
|}

TDLT

2012-05-12T22:00:08Z

Derf:

2009-11-15T21:43:45Z

Derf: /* Editorial revisions */

This is a draft document. A work in progress. A scratchpad for ideas. It should not be widely circulated in this form.

= Context =
We received [http://lists.xiph.org/pipermail/theora/2009-November/002996.html an e-mail] from a consultant studying the suitability of Theora for use in "eGovernment", on behalf of the [http://ec.europa.eu/idabc/ IDABC], an EU governmental agency responsible for "Interoperability" with an emphasis on open source. The investigation is in the context of [http://ec.europa.eu/idabc/en/document/7728 European Interoperability Framework], about which there has been [http://www.computerworlduk.com/community/blogs/index.cfm?entryid=2620&blogid=14&pn=1 some real controversy].

The method of assessment is the Common Assessment Method for Standards and Specifications, including the questions below.

= CAMSS Questions =
== Part 4: Market Criteria ==

This group of Market criteria analyses the formal specification in the scope of its market environment, and more precisely it examines the implementations of the formal specification and the market players. This implies identifying to which extent the formal specification benefits from market support and wide adoption, what are its level of maturity and its capacity of reusability.

Market support is evaluated through an analysis of how many products implementing the formal specification exist, what their market share is and who their end-users are. The quality and the completeness (in case of partitioning) of the implementations of the formal specification can also be analysed. Availability of existing or planned mechanisms to assess conformity of implementations to the standard or to the specification could also be identified. The existence of at least one reference implementation (i.e.: mentioning a recognized certification process) - and of which one is an open source implementation - can also be relevant to the assessment. Wide adoption can also be assessed across domains (i.e.: public and private sectors), in an open environment, and/or in a similar field (i.e.: best practices).

A formal specification is mature if it has been in use and development for long enough that most of its initial problems have been overcome and its underlying technology is well understood and well defined. Maturity is also assessed by identifying if all aspects of the formal specification are considered as validated by usage, (i.e.: if the formal specification is partitioned), and if the reported issues have been solved and documented.

Reusability of a formal specification is enabled if it includes guidelines for its implementation in a given context. The identification of successful implementations of the standard or specification should focus on good practices in a similar field. Its incompatibility with related standards or specifications should also be taken into account.

The ideas behind the Market Criteria can also be expressed in the form of the following questions:

=== Market support ===
* Does the standard have strong support in the marketplace?
: Yes. For example, among web browsers, support for Xiph's Ogg, Theora, and Vorbis standards is now included by default in Mozilla Firefox, Google Chrome, and the latest versions of Opera, representing hundreds of millions of installed users just in this market alone.
* What products exist for this formal specification ?
: Theora is a video codec, and as such the required products are encoders, decoders, and transmission systems. All three types of products are widely available for Theora.
* How many implementations of the formal specification are there?
: Xiph does not require implementors to acquire any license before implementing the specification. Therefore, we do not have a definitive count of the number of implementations. In addition to the reference implementation, which has been ported to most modern platforms and highly optimized for x86 and ARM CPUs and TI C64x+ DSPs, we are aware of a number of independent, conformant or mostly-conformant implementations. These include two C decoders (ffmpeg and QTheora), a Java decoder (Jheora), a C# decoder, an FPGA decoder, and an FPGA encoder.
* Are there products from different suppliers in the market that implement this formal specification ?
: Yes. Corporations such as Atari, Canonical, DailyMotion, Elphel, Fluendo, Google, Mozilla, Novell, Opera, Red Hat, Sun Microsystems, Ubisoft, and countless others have supplied products with an implementation of the Theora standard.
* Are there many products readily available from a variety of suppliers?
: Yes. Theora has been deployed in embedded devices, security cameras, video games, video conferencing systems, web browsers, home theater systems, and many other products. A complete, legal, open-source reference implementation can also be downloaded free of charge, including components for all major media frameworks (DirectShow, gstreamer, and Quicktime), giving the plethora of applications which use these frameworks the ability to use the codec.
* What is the market share of the products implementing the formal specification, versus other implementations of competing formal specifications ?
: Theora playback is extremely widely available, covering virtually the entire market of personal computers. Theora is also increasingly available in mobile and embedded devices. Since we do not require licensing for products that implement the specification, we do not have market share numbers that can be compared with competing formal specifications. Because implementations are readily available and free, Theora is included in many products that support multiple codecs, and is sometimes the only video codec included in free software products, which must be freely redistributable.
* Who are the end-users of these products implementing the formal specification?
: The end users are television viewers, video gamers, web surfers, movie makers, business people, video distribution services, and anyone else who interacts with moving pictures.

=== Maturity ===
* Are there any existing or planned mechanisms to assess conformity of the implementations of the formal specification?
: Yes. In addition to a continuous peer review process, we maintain a suite of [http://v2v.cc/~j/theora_testsuite/ test vectors] that allow implementors to assess decoder conformity. We also provide free online developer support and testing for those attempting to make a conforming implementation.
* Is there a reference implementation (i.e.: mentioning a recognized certification process)?
: Yes. Xiph maintains a reference implementation called [http://downloads.xiph.org/releases/theora/ libtheora]. In addition to serving as a reference, libtheora is also highly optimized to achieve the maximum possible speed, accuracy, reliability, efficiency, and video quality. As a result, many implementors of Theora adopt the reference implementation.
* Is there an open source implementation?
: Yes. libtheora is made available under a completely permissive BSD-like license. Its open-source nature also contributes to its quality as a reference implementation, as implementors are welcome to contribute their improvements to the reference. There are also several other open source implementations.
* Does the formal specification show wide adoption?
** across different domains? (I.e.: public and private)
: Yes. In addition to the private companies mentioned in the previous section, Theora has also been specified as the sole format supported by non-profit institutions such as Wikipedia, currently the 6th largest website in the world, or as one of a small number of preferred formats supported by other public organizations, such as the Norwegian government.
** in an open environment?
: Yes. On open/free operating systems such as those distributed by Novell/SuSE, Canonical, and Red Hat, Theora is the primary default video codec.
** in a similar field? (i.e.: can best practices be identified?)
* Has the formal specification been in use and development long enough that most of its initial problems have been overcome?
: Yes. Theora was derived from VP3, which was originally released in May 2000. The Theora specification was completed in 2004. Theora has now been used in a wide variety of applications, on the full spectrum of computing devices.
* Is the underlying technology of the standard well-understood? (e.g., a reference model is welldefined, appropriate concepts of the technology are in widespread use, the technology may have been in use for many years, a formal mathematical model is defined, etc.)
Yes. The underlying technology has been in use for nearly a decade, and most of the concepts have been in widespread use for even longer.
* Is the formal specification based upon technology that has not been well-defined and may be relatively new?
: No. The formal specification is based on technology from the On2 VP3 codec, which is substantially similar to simple block-transform codecs like H.261. This class of codecs is extremely well understood, and has been actively in use for over 20 years.
* Has the formal specification been revised? (Yes/No, Nof)
: Yes. The specification is continuously revised based on user feedback to improve clarity and accuracy.
* Is the formal specification under the auspices of an architectural board? (Yes/No)
: No. Although officially maintained by the Xiph.Org Foundation, anyone is free to join this organization, and one need not even be a member to make contributions.
* Is the formal specification partitioned in its functionality? (Yes/No)
: No. Theora is very deliberately not partitioned, to avoid the confusion created by a "standard" composed of many incompatible "profiles". The Theora standard does not have any optional components. A compliant Theora decoder can correctly process any Theora stream.
** To what extent does each partition participate to its overall functionality? (NN%)
: N/A.
** To what extent is each partition implemented? (NN%) (cf market adoption)
: N/A.

=== Re-usability ===
* Does the formal specification provide guidelines for its implementation in a given organisation?
: Yes. For example, [http://theora.org/doc/Theora.pdf the Theora specification document] provides "non-normative" advice and explanation for implementors of Theora decoders and encoders, including example algorithms for implementing required mathematical transforms. Xiph also maintains [http://wiki.xiph.org/Main_Page a documentation base] for implementors who desire more guidelines beyond the specification itself.
* Can other cases where similar systems implement the formal specification be considered as successful implementations and good practices?
: Xiph.org standards have successfully been implemented by many organisations in a wide variety of environments. We encourage independent implementations and unexpected applications of our standards.
* Is its compatibility with related formal specification documented?
: Yes. For example, [http://theora.org/doc/Theora.pdf the Theora specification] also documents the use of Theora within the [http://www.ietf.org/rfc/rfc3533.txt standard Ogg encapsulation format], and the [http://svn.xiph.org/trunk/theora/doc/draft-ietf-avt-rtp-theora-00.txt TheoraRTP draft specification] explains how to transmit Theora using the [http://tools.ietf.org/html/rfc3550 RTP standard].

== Part 5: Standardisation Criteria ==
From Idabc-camss

Note: Throughout this section, “Organisation” refers to the standardisation/fora/consortia body in charge of the formal specification.

Significant characteristics of the way the organisation operates are for example the way it gives the possibility to stakeholders to influence the evolution of the formal specification, or which conditions it attaches to the use of the formal specification or its implementation. Moreover, it is important to know how the formal specification is defined, supported, and made available, as well as how interaction with stakeholders is managed by the organisation during these steps. Governance of interoperability testing with other formal specifications is also indicative.

The standardisation criteria analyses therefore the following elements:

=== Availability of Documentation ===
The availability of documentation criteria is linked to cost and online availability. Access to all preliminary results documentation can be online, online for members only, offline, offline, for members only or not available. Access can be free or for a fee (which fee?).
: Every Xiph.org standard is permanently available online to everyone at no cost. For example, we invite everyone to download [http://theora.org/doc/Theora.pdf the most up-to-date copy of the Theora specification], and [http://xiph.org/vorbis/doc/Vorbis_I_spec.html the latest revision of Vorbis].

=== Intellectual Property Right ===
The Intellectual Property Rights evaluation criteria relates to the ability for implementers to use the formal specification in products without legal or financial implications. The IPR policy of the organisation is therefore evaluated according to:
* the availability of the IPR or copyright policies of the organisation (available on-line or off-line, or not available);
* the organisation’s governance to disclose any IPR from any contributor (ex-ante, online, offline, for free for all, for a fee for all, for members only, not available);
* the level of IPR set "mandatory" by the organisation (no patent, royalty free patent, patent and RAND with limited liability , patent and classic RAND, patent with explicit licensing, patent with defensive licensing, or none);
: Xiph.org standards have a mandatory requirement that our standards be absolutely free of IPR encumbrance. This means that a standard must either be entirely clear of any known patents, or any patents that read upon the standard must be available under an irrevocable public nonassertion agreement to all people everywhere. For example, see [http://svn.xiph.org/trunk/theora/LICENSE our On2 patent nonassertion warrant].
* the level of IPR "recommended" by the organisation (no patent, royalty free patent, patent and RAND with limited liability, patent and classic RAND, patent with explicit licensing, patent with defensive licensing, or none). [Note: RAND (Reasonable and Non Discriminatory License) is based on a "fairness" concept. Companies agree that if they receive any patents on technologies that become essential to the standard then they agree to allow other groups attempting to implement the standard to use these patents and they agree that the charges for the patents shall be reasonable. "RAND with limited availability" is a version of RAND where the "reasonable charges" have an upper limit.]
: Xiph's mandatory IPR requirements are the most stringent possible, and so our IPR recommendation is necessarily the same as the mandatory requirements.

=== Accessibility ===

The accessibility evaluation criteria describe the importance of equal and safe accessibility by the users of implementations of formal specifications. This aspect can be related to safety (physical safety and conformance safety) and accessibility of physical impaired people (design for all).

Focus is made particularly on accessibility and conformance safety. Conformance testing is testing to determine whether a system meets some specified formal specification. The result can be results from a test suite. Conformance validation is when the conformance test uniquely qualifies a given implementation as conformant or not. Conformance certification is a process that provides a public and easily visible "stamp of approval" that an implementation of a standard validates as conformant.

The following questions allow an assessment of accessibility and conformance safety:
* Does a mechanism that ensures disability support by a formal specification exist? (Y/N)
: Yes. Xiph.org ensures support for users with disabilities by providing specifications for accessible technologies independent of the codec itself. Notable Xiph specifications include [http://wiki.xiph.org/OggKate OggKate] and [http://wiki.xiph.org/index.php/CMML CMML], which provide subtitles for the hearing-impaired, as well as [http://wiki.xiph.org/Ogg_Skeleton Skeleton], which can specify scene description audio tracks for the visually impaired. When Theora is transmitted or stored in an Ogg container, it is automatically compatible with these accessibility measures.
* Is conformance governance always part of a standard? (Y/N)
* Is a conformance test offered to implementers? (Y/N)
* Is conformance validation available to implementers? (Y/N)
* Is conformance certification available? (Y/N)
* Is localisation of a formal specification possible? (Y/N)
: Yes. We welcome anyone who wishes to translate Xiph specifications into other languages. We have no policy requiring that the normative specification be written in English.

=== Interoperability governance ===
The interoperability governance evaluation criteria relates to how interoperability is identified and maintained between interoperable formal specifications. In order to do this, the organisation may provide governance for:
* open identification in formal specifications,
* open negotiation in formal specifications,
* open selection in formal specifications.

=== Meeting and consultation ===
The meeting and consultation evaluation criteria relates to the process of defining a formal specification. As formal specifications are usually defined by committees, and these committees normally consist of members of the organisation, this criteria studies how to become a member and which are the financial barriers for this, as well as how are non-members able to have an influence on the process of defining the formal specification. It analyses:
* if the organisation is open to all types of companies and organisations and to individuals;
: Yes. Xiph welcomes representatives from all companies and organizations.
* if the standardisation process may specifically allow participation of members with limited abilities when relevant;
: Yes. Standardization occurs almost entirely in internet communications channels, allowing participants with disabilities to engage fully in the standards development process. We also encourage nonexperts and students to assist us as they can, and to learn about Xiph technologies by participating in the standards development process.
* if meetings are open to all members;
: Xiph meetings are open to everyone. We place no restrictions on attendance or participation. For example, anyone interesting in contributing to the Theora specification may join [http://lists.xiph.org/pipermail/theora-dev/ the Theora development mailing list].
* if all can participate in the formal specification creation process;
: Yes. All people are welcome to participate in the specification creation process. No dues or fees are required to participate
* if non-members can participate in the formal specification creation process.
: Yes. Xiph does not maintain an explicit list of members, and no one is excluded from contributing to specifications as they are developed.

=== Consensus ===
Consensus is decision making primarily with regard to the approval of formal specifications and review with interest groups (non-members). The consensus evaluation criterion is evaluated with the following questions:
* Does the organisation have a stated objective of reaching consensus when making decisions on standards?
* If consensus is not reached, can the standard be approved? (answers are: cannot be approved but referred back to working group/committee, approved with 75% majority, approved with 66% majority, approved with 51% majority, can be decided by a "director" or similar in the organisation).
* Is there a formal process for external review of standard proposals by interest groups (nonmembers)?
: Since anyone may participate in the development process and make proposals, there is no need for a separate formal process to include proposals by nonmembers.

=== Due Process ===
The due process evaluation criteria relates to the level of respect of each member of the organisation with regard to its rights. More specifically, it must be assured that if a member believes an error has been made in the process of defining a formal specification, it must be possible to appeal this to an independent, higher instance. The question is therefore: can a member formally appeal or raise objections to a procedure or to a technical specification to an independent, higher instance?

=== Changes to the formal specification ===
The suggested changes made to a formal specification need to be presented, evaluated and approved in the same way as the formal specification was first defined. This criteria therefore applies the above criteria to the changes made to the formal specification(availability of documentation, Intellectual Property Right, accessibility, interoperability governance, meeting and consultation, consensus, due process).

=== Support ===
It is critical that the organisation takes responsibility for the formal specification throughout its life span. This can be done in several ways such as for example a regular periodic review of the formal specification. The support criteria relates to the level of commitment the organisation has taken to support the formal specification throughout its life:
* does the organisation provide support until removal of the published formal specification from public domain (Including this process?
: Xiph.org standards are never removed from the public domain. Xiph endeavors to provide support for as long as the standard remains in use.
* does the organisation make the formal specification still available even when in non-maintenance mode?
: Yes. All Xiph.org standards are freely licensed and will always be available.
* does the organisation add new features and keep the formal specification up-to-date?
: Yes. Xiph.org maintains its ecosystem of standards on a continuous basis.
* does the organisation rectify problems identified in initial implementations?
: Yes. Xiph.org maintains [https://trac.xiph.org/report a problem reporting system] that is open to the public, and invites everyone to submit suggestions for improvements. Improvements are made both to the standards documents and to the reference implementations.
* does the organisation only create the formal specification?
: No. Xiph.org also produces high-quality reusable reference implementations of its standards, released under an open license.

This is a draft document. A work in progress. A scratchpad for ideas. It should not be widely circulated in this form.