f032d7e21b815e86a2cc9a4affa9318900cebc73
[vlc.git] / modules / video_filter / deinterlace / algo_ivtc.h
1 /*****************************************************************************
2  * algo_ivtc.h : IVTC (inverse telecine) algorithm for the VLC deinterlacer
3  *****************************************************************************
4  * Copyright (C) 2010-2011 VLC authors and VideoLAN
5  *
6  * Author: Juha Jeronen <juha.jeronen@jyu.fi>
7  *
8  * This program is free software; you can redistribute it and/or modify it
9  * under the terms of the GNU Lesser General Public License as published by
10  * the Free Software Foundation; either version 2.1 of the License, or
11  * (at your option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  * GNU Lesser General Public License for more details.
17  *
18  * You should have received a copy of the GNU Lesser General Public License
19  * along with this program; if not, write to the Free Software Foundation,
20  * Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
21  *****************************************************************************/
22
23 #ifndef VLC_DEINTERLACE_ALGO_IVTC_H
24 #define VLC_DEINTERLACE_ALGO_IVTC_H 1
25
26 /* Forward declarations */
27 struct filter_t;
28 struct picture_t;
29
30 /*****************************************************************************
31  * Data structures
32  *****************************************************************************/
33
34 #define IVTC_NUM_FIELD_PAIRS 7
35 #define IVTC_DETECTION_HISTORY_SIZE 3
36 #define IVTC_LATEST (IVTC_DETECTION_HISTORY_SIZE-1)
37 /**
38  * Algorithm-specific state for IVTC.
39  * @see RenderIVTC()
40  */
41 typedef struct
42 {
43     int i_mode; /**< Detecting, hard TC, or soft TC. @see ivtc_mode */
44     int i_old_mode; /**< @see IVTCSoftTelecineDetect() */
45
46     int i_cadence_pos; /**< Cadence counter, 0..4. Runs when locked on. */
47     int i_tfd; /**< TFF or BFF telecine. Detected from the video. */
48
49     /** Raw low-level detector output.
50      *
51      *  @see IVTCLowLevelDetect()
52      */
53     int pi_scores[IVTC_NUM_FIELD_PAIRS]; /**< Interlace scores. */
54     int pi_motion[IVTC_DETECTION_HISTORY_SIZE]; /**< 8x8 blocks with motion. */
55     int pi_top_rep[IVTC_DETECTION_HISTORY_SIZE]; /**< Hard top field repeat. */
56     int pi_bot_rep[IVTC_DETECTION_HISTORY_SIZE]; /**< Hard bot field repeat. */
57
58     /** Interlace scores of outgoing frames, used for judging IVTC output
59      *  (detecting cadence breaks).
60      *
61      *  @see IVTCOutputOrDropFrame()
62      */
63     int pi_final_scores[IVTC_DETECTION_HISTORY_SIZE];
64
65     /** Cadence position detection history (in ivtc_cadence_pos format).
66      *  Contains the detected cadence position and a corresponding
67      *  reliability flag for each algorithm.
68      *
69      *  s = scores, interlace scores based algorithm, original to this filter.
70      *  v = vektor, hard field repeat based algorithm, inspired by
71      *              the TVTime/Xine IVTC filter by Billy Biggs (Vektor).
72      *
73      *  Each algorithm may also keep internal, opaque data.
74      *
75      *  @see ivtc_cadence_pos
76      *  @see IVTCCadenceDetectAlgoScores()
77      *  @see IVTCCadenceDetectAlgoVektor()
78      */
79     int  pi_s_cadence_pos[IVTC_DETECTION_HISTORY_SIZE];
80     bool pb_s_reliable[IVTC_DETECTION_HISTORY_SIZE];
81     int  pi_v_raw[IVTC_DETECTION_HISTORY_SIZE]; /**< "vektor" algo internal */
82     int  pi_v_cadence_pos[IVTC_DETECTION_HISTORY_SIZE];
83     bool pb_v_reliable[IVTC_DETECTION_HISTORY_SIZE];
84
85     /** Final result, chosen by IVTCCadenceDetectFinalize() from the results
86      *  given by the different detection algorithms.
87      *
88      *  @see IVTCCadenceDetectFinalize()
89      */
90     int pi_cadence_pos_history[IVTC_DETECTION_HISTORY_SIZE];
91
92     /**
93      *  Set by cadence analyzer. Whether the sequence of last
94      *  IVTC_DETECTION_HISTORY_SIZE detected positions, stored in
95      *  pi_cadence_pos_history, looks like a valid telecine.
96      *
97      *  @see IVTCCadenceAnalyze()
98      */
99     bool b_sequence_valid;
100
101     /**
102      *  Set by cadence analyzer. True if detected position = "dea".
103      *  The three entries of this are used for detecting three progressive
104      *  stencil positions in a row, i.e. five progressive frames in a row;
105      *  this triggers exit from hard IVTC.
106      *
107      *  @see IVTCCadenceAnalyze()
108      */
109     bool pb_all_progressives[IVTC_DETECTION_HISTORY_SIZE];
110 } ivtc_sys_t;
111
112 /*****************************************************************************
113  * Functions
114  *****************************************************************************/
115
116 /**
117  * Deinterlace filter. Performs inverse telecine.
118  *
119  * Also known as "film mode" or "3:2 reverse pulldown" in some equipment.
120  *
121  * This filter attempts to reconstruct the original film frames from an
122  * NTSC telecined signal. It is intended for 24fps progressive material
123  * that was telecined to NTSC 60i. For example, most NTSC anime DVDs
124  * are like this.
125  *
126  * There is no input frame parameter, because the input frames
127  * are taken from the history buffer.
128  *
129  * See the file comment for a detailed description of the algorithm.
130  *
131  * @param p_filter The filter instance. Must be non-NULL.
132  * @param[out] p_dst Output frame. Must be allocated by caller.
133  * @return VLC error code (int).
134  * @retval VLC_SUCCESS A film frame was reconstructed to p_dst.
135  * @retval VLC_EGENERIC Frame dropped as part of normal IVTC operation.
136  * @see Deinterlace()
137  * @see ComposeFrame()
138  * @see CalculateInterlaceScore()
139  * @see EstimateNumBlocksWithMotion()
140  */
141 int RenderIVTC( filter_t *p_filter, picture_t *p_dst, picture_t *p_pic );
142
143 /**
144  * Clears the inverse telecine subsystem state.
145  *
146  * Used during initialization and uninitialization
147  * (called from Open() and Flush()).
148  *
149  * @param p_filter The filter instance.
150  * @see RenderIVTC()
151  * @see Open()
152  * @see Flush()
153  */
154 void IVTCClearState( filter_t *p_filter );
155
156 /*****************************************************************************
157  * Extra documentation
158  *****************************************************************************/
159
160 /**
161  * \file
162  * IVTC (inverse telecine) algorithm for the VLC deinterlacer.
163  * Also known as "film mode" or "3:2 reverse pulldown" in some equipment.
164  *
165  * Summary:
166  *
167  * This is a "live IVTC" filter, which attempts to do in realtime what
168  * Transcode's ivtc->decimate->32detect chain does offline. Additionally,
169  * it removes soft telecine. It is an original design, based on some ideas
170  * from Transcode, some from TVTime/Xine, and some original.
171  *
172  * If the input material is pure NTSC telecined film, inverse telecine
173  * will (ideally) exactly recover the original progressive film frames.
174  * The output will run at 4/5 of the original framerate with no loss of
175  * information. Interlacing artifacts are removed, and motion becomes
176  * as smooth as it was on the original film. For soft-telecined material,
177  * on the other hand, the progressive frames alredy exist, so only the
178  * timings are changed such that the output becomes smooth 24fps (or would,
179  * if the output device had an infinite framerate).
180  *
181  * Put in simple terms, this filter is targeted for NTSC movies and
182  * especially anime. Virtually all 1990s and early 2000s anime is
183  * hard-telecined. Because the source material is like that,
184  * IVTC is needed for also virtually all official R1 (US) anime DVDs.
185  *
186  * Note that some anime from the turn of the century (e.g. Silent Mobius
187  * and Sol Bianca) is a hybrid of telecined film and true interlaced
188  * computer-generated effects and camera pans. In this case, applying IVTC
189  * will effectively attempt to reconstruct the frames based on the film
190  * component, but even if this is successful, the framerate reduction will
191  * cause the computer-generated effects to stutter. This is mathematically
192  * unavoidable. Instead of IVTC, a framerate doubling deinterlacer is
193  * recommended for such material. Try "Phosphor", "Bob", or "Linear".
194  *
195  * Fortunately, 30fps true progressive anime is on the rise (e.g. ARIA,
196  * Black Lagoon, Galaxy Angel, Ghost in the Shell: Solid State Society,
197  * Mai Otome, Last Exile, and Rocket Girls). This type requires no
198  * deinterlacer at all.
199  *
200  * Another recent trend is using 24fps computer-generated effects and
201  * telecining them along with the cels (e.g. Kiddy Grade, Str.A.In. and
202  * The Third: The Girl with the Blue Eye). For this group, IVTC is the
203  * correct way to deinterlace, and works properly.
204  *
205  * Soft telecined anime, while rare, also exists. Stellvia of the Universe
206  * and Angel Links are examples of this. Stellvia constantly alternates
207  * between soft and hard telecine - pure CGI sequences are soft-telecined,
208  * while sequences incorporating cel animation are hard-telecined.
209  * This makes it very hard for the cadence detector to lock on,
210  * and indeed Stellvia gives some trouble for the filter.
211  *
212  * To finish the list of different material types, Azumanga Daioh deserves
213  * a special mention. The OP and ED sequences are both 30fps progressive,
214  * while the episodes themselves are hard-telecined. This filter should
215  * mostly work correctly with such material, too. (The beginning of the OP
216  * shows some artifacts, but otherwise both the OP and ED are indeed
217  * rendered progressive. The technical reason is that the filter has been
218  * designed to aggressively reconstruct film frames, which helps in many
219  * cases with hard-telecined material. In very rare cases, this approach may
220  * go wrong, regardless of whether the input is telecined or progressive.)
221  *
222  * Finally, note also that IVTC is the only correct way to deinterlace NTSC
223  * telecined material. Simply applying an interpolating deinterlacing filter
224  * (with no framerate doubling) is harmful for two reasons. First, even if
225  * the filter does not damage already progressive frames, it will lose half
226  * of the available vertical resolution of those frames that are judged
227  * interlaced. Some algorithms combining data from multiple frames may be
228  * able to counter this to an extent, effectively performing something akin
229  * to the frame reconstruction part of IVTC. A more serious problem is that
230  * any motion will stutter, because (even in the ideal case) one out of
231  * every four film frames will be shown twice, while the other three will
232  * be shown only once. Duplicate removal and framerate reduction - which are
233  * part of IVTC - are also needed to properly play back telecined material
234  * on progressive displays at a non-doubled framerate.
235  *
236  * So, try this filter on your NTSC anime DVDs. It just might help.
237  *
238  *
239  * Technical details:
240  *
241  *
242  * First, NTSC hard telecine in a nutshell:
243  *
244  * Film is commonly captured at 24 fps. The framerate must be raised from
245  * 24 fps to 59.94 fields per second, This starts by pretending that the
246  * original framerate is 23.976 fps. When authoring, the audio can be
247  * slowed down by 0.1% to match. Now 59.94 = 5/4 * (2*23.976), which gives
248  * a nice ratio made out of small integers.
249  *
250  * Thus, each group of four film frames must become five frames in the NTSC
251  * video stream. One cannot simply repeat one frame of every four, because
252  * this would result in jerky motion. To slightly soften the jerkiness,
253  * the extra frame is split into two extra fields, inserted at different
254  * times. The content of the extra fields is (in classical telecine)
255  * duplicated as-is from existing fields.
256  *
257  * The field duplication technique is called "3:2 pulldown". The pattern
258  * is called the cadence. The output from 3:2 pulldown looks like this
259  * (if the telecine is TFF, top field first):
260  *
261  * a  b  c  d  e     Telecined frame (actual frames stored on DVD)
262  * T1 T1 T2 T3 T4    *T*op field content
263  * B1 B2 B3 B3 B4    *B*ottom field content
264  *
265  * Numbers 1-4 denote the original film frames. E.g. T1 = top field of
266  * original film frame 1. The field Tb, and one of either Bc or Bd, are
267  * the extra fields inserted in the telecine. With exact duplication, it
268  * of course doesn't matter whether Bc or Bd is the extra field, but
269  * with "full field blended" material (see below) this will affect how to
270  * correctly extract film frame 3.
271  *
272  * See the following web pages for illustrations and discussion:
273  * http://neuron2.net/LVG/telecining1.html
274  * http://arbor.ee.ntu.edu.tw/~jackeikuo/dvd2avi/ivtc/
275  *
276  * Note that film frame 2 has been stored "half and half" into two telecined
277  * frames (b and c). Note also that telecine produces a sequence of
278  * 3 progressive frames (d, e and a) followed by 2 interlaced frames
279  * (b and c).
280  *
281  * The output may also look like this (BFF telecine, bottom field first):
282  *
283  * a' b' c' d' e'
284  * T1 T2 T3 T3 T4
285  * B1 B1 B2 B3 B4
286  *
287  * Now field Bb', and one of either Tc' or Td', are the extra fields.
288  * Again, film frame 2 is stored "half and half" (into b' and c').
289  *
290  * Whether the pattern is like abcde or a'b'c'd'e', depends on the telecine
291  * field dominance (TFF or BFF). This must match the video field dominance,
292  * but is conceptually different. Importantly, there is no temporal
293  * difference between those fields that came from the same film frame.
294  * Also, see the section on soft telecine below.
295  *
296  * In a hard telecine, the TFD and VFD must match for field renderers
297  * (e.g. traditional DVD player + CRT TV) to work correctly; this should be
298  * fairly obvious by considering the above telecine patterns and how a
299  * field renderer displays the material (one field at a time, dominant
300  * field first).
301  *
302  * The VFD may, *correctly*, flip mid-stream, if soft field repeats
303  * (repeat_pict) have been used. They are commonly used in soft telecine
304  * (see below), but also occasional lone field repeats exist in some streams,
305  * e.g., Sol Bianca.
306  *
307  * See e.g.
308  * http://www.cambridgeimaging.co.uk/downloads/Telecine%20field%20dominance.pdf
309  * for discussion. The document discusses mostly PAL, but includes some notes
310  * on NTSC, too.
311  *
312  * The reason for the words "classical telecine" above, when field
313  * duplication was first mentioned, is that there exists a
314  * "full field blended" version, where the added fields are not exact
315  * duplicates, but are blends of the original film frames. This is rare
316  * in NTSC, but some material like this reportedly exists. See
317  * http://www.animemusicvideos.org/guides/avtech/videogetb2a.html
318  * In these cases, the additional fields are a (probably 50%) blend of the
319  * frames between which they have been inserted. Which one of the two
320  * possibilites is the extra field then becomes important.
321  * This filter does NOT support "full field blended" material.
322  *
323  * To summarize, the 3:2 pulldown sequence produces a group of ten fields
324  * out of every four film frames. Only eight of these fields are unique.
325  * To remove the telecine, the duplicate fields must be removed, and the
326  * original progressive frames restored. Additionally, the presentation
327  * timestamps (PTS) must be adjusted, and one frame out of five (containing
328  * no new information) dropped. The duration of each frame in the output
329  * becomes 5/4 of that in the input, i.e. 25% longer.
330  *
331  * Theoretically, this whole mess could be avoided by soft telecining, if the
332  * original material is pure 24fps progressive. By using the stream flags
333  * correctly, the original progressive frames can be stored on the DVD.
334  * In such cases, the DVD player will apply "soft" 3:2 pulldown. See the
335  * following section.
336  *
337  * Also, the mess with cadence detection for hard telecine (see below) could
338  * be avoided by using the progressive frame flag and a five-frame future
339  * buffer, but no one ever sets the flag correctly for hard-telecined
340  * streams. All frames are marked as interlaced, regardless of their cadence
341  * position. This is evil, but sort-of-understandable, given that video
342  * editors often come with "progressive" and "interlaced" editing modes,
343  * but no separate "telecined" mode that could correctly handle this
344  * information.
345  *
346  * In practice, most material with its origins in Asia (including virtually
347  * all official US (R1) anime DVDs) is hard-telecined. Combined with the
348  * turn-of-the-century practice of rendering true interlaced effects
349  * on top of the hard-telecined stream, we have what can only be described
350  * as a monstrosity. Fortunately, recent material is much more consistent,
351  * even though still almost always hard-telecined.
352  *
353  * Finally, note that telecined video is often edited directly in interlaced
354  * form, disregarding safe cut positions as pertains to the telecine sequence
355  * (there are only two: between "d" and "e", or between "e" and the
356  * next "a"). Thus, the telecine sequence will in practice jump erratically
357  * at cuts [**]. An aggressive detection strategy is needed to cope with
358  * this.
359  *
360  * [**] http://users.softlab.ece.ntua.gr/~ttsiod/ivtc.html
361  *
362  *
363  * Note about chroma formats: 4:2:0 is very common at least on anime DVDs.
364  * In the interlaced frames in a hard telecine, the chroma alternates
365  * every chroma line, even if the chroma format is 4:2:0! This means that
366  * if the interlaced picture is viewed as-is, the luma alternates every line,
367  * while the chroma alternates only every two lines of the picture.
368  *
369  * That is, an interlaced frame in a 4:2:0 telecine looks like this
370  * (numbers indicate which film frame the data comes from):
371  *
372  * luma  stored 4:2:0 chroma  displayed chroma
373  * 1111  1111                 1111
374  * 2222                       1111
375  * 1111  2222                 2222
376  * 2222                       2222
377  * ...   ...                  ...
378  *
379  * The deinterlace filter sees the stored 4:2:0 chroma. The "displayed chroma"
380  * is only generated later in the filter chain (probably when YUV is converted
381  * to the display format, if the display does not accept YUV 4:2:0 directly).
382  *
383  *
384  * Next, how NTSC soft telecine works:
385  *
386  * a  b  c  d     Frame index (actual frames stored on DVD)
387  * T1 T2 T3 T4    *T*op field content
388  * B1 B2 B3 B4    *B*ottom field content
389  *
390  * Here the progressive frames are stored as-is. The catch is in the stream
391  * flags. For hard telecine, which was explained above, we have
392  * VFD = constant and nb_fields = 2, just like in a true progressive or
393  * true interlaced stream. Soft telecine, on the other hand, looks like this:
394  *
395  * a  b  c  d
396  * 3  2  3  2     nb_fields
397  * T  B  B  T     *Video* field dominance (for TFF telecine)
398  * B  T  T  B     *Video* field dominance (for BFF telecine)
399  *
400  * Now the video field dominance flipflops every two frames!
401  *
402  * Note that nb_fields = 3 means the frame duration will be 1.5x that of a
403  * normal frame. Often, soft-telecined frames are correctly flagged as
404  * progressive.
405  *
406  * Here the telecining is expected to be done by the player, utilizing the
407  * soft field repeat (repeat_pict) feature. This is indeed what a field
408  * renderer (traditional interlaced equipment, or a framerate doubler)
409  * should do with such a stream.
410  *
411  * In the IVTC filter, our job is to even out the frame durations, but
412  * disregard video field dominance and just pass the progressive pictures
413  * through as-is.
414  *
415  * Fortunately, for soft telecine to work at all, the stream flags must be
416  * set correctly. Thus this type can be detected reliably by reading
417  * nb_fields from three consecutive frames:
418  *
419  * Let P = previous, C = current, N = next. If the frame to be rendered is C,
420  * there are only three relevant nb_fields flag patterns for the three-frame
421  * stencil concerning soft telecine:
422  *
423  * P C N   What is happening:
424  * 2 3 2   Entering soft telecine at frame C, or running inside it already.
425  * 3 2 3   Running inside soft telecine.
426  * 3 2 2   Exiting soft telecine at frame C. C is the last frame that should
427  *         be handled as soft-telecined. (If we do timing adjustments to the
428  *         "3"s only, we can already exit soft telecine mode when we see
429  *         this pattern.)
430  *
431  * Note that the same stream may alternate between soft and hard telecine,
432  * but these cannot occur at the same time. The start and end of the
433  * soft-telecined parts can be read off the stream flags, and the rest of
434  * the stream can be handed to the hard IVTC part of the filter for analysis.
435  *
436  * Finally, note also that a stream may also request a lone field repeat
437  * (a sudden "3" surrounded by "2"s). Fortunately, these can be handled as
438  * a two-frame soft telecine, as they match the first and third
439  * flag patterns above.
440  *
441  * Combinations with several "3"s in a row are not valid for soft or hard
442  * telecine, so if they occur, the frames can be passed through as-is.
443  *
444  *
445  * Cadence detection for hard telecine:
446  *
447  * Consider viewing the TFF and BFF hard telecine sequences through a
448  * three-frame stencil. Again, let P = previous, C = current, N = next.
449  * A brief analysis leads to the following cadence tables.
450  *
451  * PCN                 = stencil position (Previous Current Next),
452  * Dups.               = duplicate fields,
453  * Best field pairs... = combinations of fields which correctly reproduce
454  *                       the original progressive frames,
455  * *                   = see timestamp considerations below for why
456  *                       this particular arrangement.
457  *
458  * For TFF:
459  *
460  * PCN   Dups.     Best field pairs for progressive (correct, theoretical)
461  * abc   TP = TC   TPBP = frame 1, TCBP = frame 1, TNBC = frame 2
462  * bcd   BC = BN   TCBP = frame 2, TNBC = frame 3, TNBN = frame 3
463  * cde   BP = BC   TCBP = frame 3, TCBC = frame 3, TNBN = frame 4
464  * dea   none      TPBP = frame 3, TCBC = frame 4, TNBN = frame 1
465  * eab   TC = TN   TPBP = frame 4, TCBC = frame 1, TNBC = frame 1
466  *
467  * (table cont'd)
468  * PCN   Progressive output*
469  * abc   frame 2 = TNBC (compose TN+BC)
470  * bcd   frame 3 = TNBN (copy N)
471  * cde   frame 4 = TNBN (copy N)
472  * dea   (drop)
473  * eab   frame 1 = TCBC (copy C), or TNBC (compose TN+BC)
474  *
475  * On the rows "dea" and "eab", frame 1 refers to a frame from the next
476  * group of 4. "Compose TN+BC" means to construct a frame using the
477  * top field of N, and the bottom field of C. See ComposeFrame().
478  *
479  * For BFF, swap all B and T, and rearrange the symbol pairs to again
480  * read "TxBx". We have:
481  *
482  * PCN   Dups.     Best field pairs for progressive (correct, theoretical)
483  * abc   BP = BC   TPBP = frame 1, TPBC = frame 1, TCBN = frame 2
484  * bcd   TC = TN   TPBC = frame 2, TCBN = frame 3, TNBN = frame 3
485  * cde   TP = TC   TPBC = frame 3, TCBC = frame 3, TNBN = frame 4
486  * dea   none      TPBP = frame 3, TCBC = frame 4, TNBN = frame 1
487  * eab   BC = BN   TPBP = frame 4, TCBC = frame 1, TCBN = frame 1
488  *
489  * (table cont'd)
490  * PCN   Progressive output*
491  * abc   frame 2 = TCBN (compose TC+BN)
492  * bcd   frame 3 = TNBN (copy N)
493  * cde   frame 4 = TNBN (copy N)
494  * dea   (drop)
495  * eab   frame 1 = TCBC (copy C), or TCBN (compose TC+BN)
496  *
497  * From these cadence tables we can extract two strategies for
498  * cadence detection. We use both.
499  *
500  * Strategy 1: duplicated fields ("vektor").
501  *
502  * Consider that each stencil position has a unique duplicate field
503  * condition. In one unique position, "dea", there is no match; in all
504  * other positions, exactly one. By conservatively filtering the
505  * possibilities based on detected hard field repeats (identical fields
506  * in successive input frames), it is possible to gradually lock on
507  * to the cadence. This kind of strategy is used by the classic IVTC filter
508  * in TVTime/Xine by Billy Biggs (Vektor), hence the name.
509  *
510  * "Conservative" here means that we do not rule anything out, but start at
511  * each stencil position by suggesting the position "dea", and then only add
512  * to the list of possibilities based on field repeats that are detected at
513  * the present stencil position. This estimate is then filtered by ANDing
514  * against a shifted (time-advanced) version of the estimate from the
515  * previous stencil position. Once the detected position becomes unique,
516  * the filter locks on. If the new detection is inconsistent with the
517  * previous one, the detector resets itself and starts from scratch.
518  *
519  * The strategy is very reliable, as it only requires running (fuzzy)
520  * duplicate field detection against the input. It is very good at staying
521  * locked on once it acquires the cadence, and it does so correctly very
522  * often. These are indeed characteristics that can be observed in the
523  * behaviour of the TVTime/Xine filter.
524  *
525  * Note especially that 8fps/12fps animation, common in anime, will cause
526  * spurious hard-repeated fields. The conservative nature of the method
527  * makes it very good at dealing with this - any spurious repeats will only
528  * slow down the lock-on, not completely confuse it. It should also be good
529  * at detecting the presence of a telecine, as neither true interlaced nor
530  * true progressive material should contain any hard field repeats.
531  * (This, however, has not been tested yet.)
532  *
533  * The disadvantages are that at times the method may lock on slowly,
534  * because the detection must be filtered against the history until
535  * a unique solution is found. Resets, if they happen, will also
536  * slow down the lock-on.
537  *
538  * The hard duplicate detection required by this strategy can be made
539  * data-adaptive in several ways. TVTime uses a running average of motion
540  * scores for its history buffer. We utilize a different, original approach.
541  * It is rare, if not nonexistent, that only one field changes between
542  * two valid frames. Thus, if one field changes "much more" than the other
543  * in fieldwise motion detection, the less changed one is probably a
544  * duplicate. Importantly, this works with telecined input, too - the field
545  * that changes "much" may be part of another film frame, while the "less"
546  * changed one is actually a duplicate from the previous film frame.
547  * If both fields change "about as much", then no hard field repeat
548  * is detected.
549  *
550  *
551  * Strategy 2: progressive/interlaced field combinations ("scores").
552  *
553  * We can also form a second strategy, which is not as reliable in practice,
554  * but which locks on faster when it does. This is original to this filter.
555  *
556  * Consider all possible field pairs from two successive frames: TCBC, TCBN,
557  * TNBC, TNBN. After one frame, these become TPBP, TPBC, TCBP, TCBC.
558  * These eight pairs (seven unique, disregarding the duplicate TCBC)
559  * are the exhaustive list of possible field pairs from two successive
560  * frames in the three-frame PCN stencil.
561  *
562  * The above tables list triplets of field pair combinations for each cadence
563  * position, which should produce progressive frames. All the given triplets
564  * are unique in each table alone, although the one at "dea" is
565  * indistinguishable from the case of pure progressive material. It is also
566  * the only one which is not unique across both tables.
567  *
568  * Thus, all sequences of two neighboring triplets are unique across both
569  * tables. (For "neighboring", each table is considered to wrap around from
570  * "eab" back to "abc", i.e. from the last row back to the first row.)
571  * Furthermore, each sequence of three neighboring triplets is redundantly
572  * unique (i.e. is unique, and reduces the chance of false positives).
573  * (In practice, though, we already know which table to consider, from the fact
574  * that TFD and VFD must match. Checking only the relevant table makes the
575  * strategy slightly more robust.)
576  *
577  * The important idea is: *all other* field pair combinations should produce
578  * frames that look interlaced. This includes those combinations present in
579  * the "wrong" (i.e. not current position) rows of the table (insofar as
580  * those combinations are not also present in the "correct" row; by the
581  * uniqueness property, *every* "wrong" row will always contain at least one
582  * combination that differs from those in the "correct" row).
583  *
584  * We generate the artificial frames TCBC, TCBN, TNBC and TNBN (virtually;
585  * no data is actually moved). Two of these are just the frames C and N,
586  * which already exist; the two others correspond to composing the given
587  * field pairs. We then compute the interlace score for each of these frames.
588  * The interlace scores of what are now TPBP, TPBC and TCBP, also needed,
589  * were computed by this same mechanism during the previous input frame.
590  * These can be slided in history and reused.
591  *
592  * We then check, using the computed interlace scores, and taking into
593  * account the video field dominance information, which field combination
594  * triplet given in the appropriate table produces the smallest sum of
595  * interlace scores. Unless we are at PCN = "dea" (which could also be pure
596  * progressive!), this immediately gives us the most likely current cadence
597  * position. Combined with a two-step history, the sequence of three most
598  * likely positions found this way always allows us to make a more or less
599  * reliable detection. (That is, when a reliable detection is possible; if the
600  * video has no motion at all, every detection will report the position "dea".
601  * In anime, still shots are common. Thus we must augment this with a
602  * full-frame motion detection that switches the detector off if no motion
603  * was detected.)
604  *
605  * The detection seems to need four full-frame interlace analyses per frame.
606  * Actually, three are enough, because the previous N is the new C, so we can
607  * slide the already computed result. Also during initialization, we only
608  * need to compute TNBN on the first frame; this has become TPBP when the
609  * third frame is reached. Similarly, we compute TNBN, TNBC and TCBN during
610  * the second frame (just before the filter starts), and these get slided
611  * into TCBC, TCBP and TPBC when the third frame is reached. At that point,
612  * initialization is complete.
613  *
614  * Because we only compare interlace scores against each other, no threshold
615  * is needed in the cadence detector. Thus it, trivially, adapts to the
616  * material automatically.
617  *
618  * The weakness of this approach is that any comb metric detects incorrectly
619  * every now and then. Especially slow vertical camera pans often get treated
620  * wrong, because the messed-up field combination looks less interlaced
621  * according to the comb metric (especially in anime) than the correct one
622  * (which contains, correctly, one-pixel thick cartoon outlines, parts of
623  * which often perfectly horizontal).
624  *
625  * The advantage is that this strategy catches horizontal camera pans
626  * immediately and reliably, while the other strategy may still be trying
627  * to lock on.
628  *
629  *
630  * Frame reconstruction:
631  *
632  * We utilize a hybrid approach. If a valid cadence is locked on, we use the
633  * operation table to decide what to do. This handles those cases correctly,
634  * which would be difficult for the interlace detector alone (e.g. vertical
635  * camera pans). Note that the operations that must be performed for IVTC
636  * include timestamp mangling and frame dropping, which can only be done
637  * reliably on a valid cadence.
638  *
639  * When the cadence fails (we detect this from a sudden upward jump in the
640  * interlace scores of the constructed frames), we reset the "vektor"
641  * detector strategy and fall back to an emergency frame composer, where we
642  * use ideas from Transcode's IVTC.
643  *
644  * In this emergency mode, we simply output the least interlaced frame out of
645  * the combinations TNBN, TNBC and TCBN (where only one of the last two is
646  * tested, based on the stream TFF/BFF information). In this mode, we do not 
647  * touch the timestamps, and just pass all five frames from each group right
648  * through. This introduces some stutter, but in practice it is often not
649  * noticeable. This is because the kind of material that is likely to trip up
650  * the cadence detector usually includes irregular 8fps/12fps motion. With
651  * true 24fps motion, the cadence quickly locks on, and stays locked on.
652  *
653  * Once the cadence locks on again, we resume normal operation based on
654  * the operation table.
655  *
656  *
657  * Timestamp mangling:
658  *
659  * To make five into four we need to extend frame durations by 25%.
660  * Consider the following diagram (times given in 90kHz ticks, rounded to
661  * integers; this is just for illustration, and for comparison with the
662  * "scratch paper" comments in pulldown.c of TVTime/Xine):
663  *
664  * NTSC input (29.97 fps)
665  * a       b       c       d        e        a (from next group) ...
666  * 0    3003    6006    9009    12012    15015
667  * 0      3754      7508       11261     15015
668  * 1         2         3           4         1 (from next group) ...
669  * Film output (23.976 fps)
670  *
671  * Three of the film frames have length 3754, and one has 3753
672  * (it is 1/90000 sec shorter). This rounding was chosen so that the lengths
673  * of the group of four sum to the original 15015.
674  *
675  * From the diagram we get these deltas for presentation timestamp adjustment
676  * (in 90 kHz ticks, for illustration):
677  * (1-a)   (2-b)  (3-c)   (4-d)   (skip)   (1-a) ...
678  *     0   +751   +1502   +2252   (skip)       0 ...
679  *
680  * In fractions of (p_next->date - p_cur->date), regardless of actual
681  * time unit, the deltas are:
682  * (1-a)   (2-b)  (3-c)   (4-d)   (skip)   (1-a) ...
683  *     0   +0.25  +0.50   +0.75   (skip)       0 ...
684  *
685  * This is what we actually use. In our implementation, the values are stored
686  * multiplied by 4, as integers.
687  *
688  * The "current" frame should be displayed at [original time + delta].
689  * E.g., when "current" = b (i.e. PCN = abc), start displaying film frame 2
690  * at time [original time of b + 751 ticks]. So, when we catch the cadence,
691  * we will start mangling the timestamps according to the cadence position
692  * of the "current" frame, using the deltas given above. This will cause
693  * a one-time jerk, most noticeable if the cadence happens to catch at
694  * position "d". (Alternatively, upon lock-on, we could wait until we are
695  * at "a" before switching on IVTC, but this makes the maximal delay
696  * [max. detection + max. wait] = 3 + 4 = 7 input frames, which comes to
697  * 7/30 ~ 0.23 seconds instead of the 3/30 = 0.10 seconds from purely
698  * the detection. The one-time jerk is simpler to implement and gives the
699  * faster lock-on.)
700  *
701  * It is clear that "e" is a safe choice for the dropped frame. This can be
702  * seen from the timings and the cadence tables. First, consider the timings.
703  * If we have only one future frame, "e" is the only one whose PTS, comparing
704  * to the film frames, allows dropping it safely. To see this, consider which
705  * film frame needs to be rendered as each new input frame arrives. Secondly,
706  * consider the cadence tables. It is ok to drop "e", because the same
707  * film frame "1" is available also at the next PCN position "eab".
708  * (As a side note, it is interesting that Vektor's filter drops "b".
709  * See the TVTime sources.)
710  *
711  * When the filter falls out of film mode, the timestamps of the incoming
712  * frames are left untouched. Thus, the output from this filter has a
713  * variable framerate: 4/5 of the input framerate when IVTC is active
714  * (whether hard or soft), and the same framerate as input when it is not
715  * (or when in emergency mode).
716  *
717  *
718  * For other open-source IVTC codes, which may be a useful source for ideas,
719  * see the following:
720  *
721  * The classic filter by Billy Biggs (Vektor). Written in 2001-2003 for
722  * TVTime, and adapted into Xine later. In xine-lib 1.1.19, it is at
723  * src/post/deinterlace/pulldown.*. Also needed are tvtime.*, and speedy.*.
724  *
725  * Transcode's ivtc->decimate->32detect chain by Thanassis Tsiodras.
726  * Written in 2002, added in Transcode 0.6.12. This probably has something
727  * to do with the same chain in MPlayer, considering that MPlayer acquired
728  * an IVTC filter around the same time. In Transcode 1.1.5, the IVTC part is
729  * at filter/filter_ivtc.c. Transcode 1.1.5 sources can be downloaded from
730  * http://developer.berlios.de/project/showfiles.php?group_id=10094
731  */
732
733 #endif