# FlowVid: Taming Imperfect Optical Flows for Consistent Video-to-Video
Synthesis

Feng Liang**footnotemark: * 1, Bichen Wu†††*Work partially done during an
internship at Meta GenAI. 2, Jialiang Wang2, Licheng Yu2, Kunpeng Li2, Yinan
Zhao2, Ishan Misra2,
Jia-Bin Huang2, Peizhao Zhang2, Peter Vajda2, Diana Marculescu1
1The University of Texas at Austin, 2Meta GenAI
<EMAIL_ADDRESS><EMAIL_ADDRESS>
https://jeff-liangf.github.io/projects/flowvid

###### Abstract

Diffusion models have transformed the image-to-image (I2I) synthesis and are
now permeating into videos. However, the advancement of video-to-video (V2V)
synthesis has been hampered by the challenge of maintaining temporal
consistency across video frames. This paper proposes a consistent V2V
synthesis framework by jointly leveraging spatial conditions and temporal
optical flow clues within the source video. Contrary to prior methods that
strictly adhere to optical flow, our approach harnesses its benefits while
handling the imperfection in flow estimation. We encode the optical flow via
warping from the first frame and serve it as a supplementary reference in the
diffusion model. This enables our model for video synthesis by editing the
first frame with any prevalent I2I models and then propagating edits to
successive frames. Our V2V model, FlowVid, demonstrates remarkable properties:
(1) Flexibility: FlowVid works seamlessly with existing I2I models,
facilitating various modifications, including stylization, object swaps, and
local edits. (2) Efficiency: Generation of a 4-second video with 30 FPS and
512$\times$512 resolution takes only 1.5 minutes, which is 3.1$\times$,
7.2$\times$, and 10.5$\times$ faster than CoDeF, Rerender, and TokenFlow,
respectively. (3) High-quality: In user studies, our FlowVid is preferred
45.7% of the time, outperforming CoDeF (3.5%), Rerender (10.2%), and TokenFlow
(40.4%).

Figure 1:  We present FlowVid to synthesize a consistent video given an input
video and a target prompt. Our model supports multiple applications: (1)
global stylization, such as converting the video to 2D anime (2) object swap,
such as turning the panda into a koala bear (3) local edit, such as adding a
pig nose to a panda.

††footnotetext: †Corresponding author. Figure 2: (a) Input video: ’a man is
running on beach’. (b) We edit the 1st frame with ’a man is running on Mars’,
then conduct flow warping from the 1st frame to the 10th and 20th frames
(using input video flow). Flow estimation of legs is inaccurate. (c) Our
FlowVid uses spatial controls to rectify the inaccurate flow. (d) Our
consistent video synthesis results.

##  1 Introduction

Text-guided Video-to-video (V2V) synthesis, which aims to modify the input
video according to given text prompts, has wide applications in various
domains, such as short-video creation and more broadly in the film industry.
Notable advancements have been seen in text-guided Image-to-Image (I2I)
synthesis [4, 14, 43, 31], greatly supported by large pre-trained text-to-
image diffusion models [37, 39, 40]. However, V2V synthesis remains a
formidable task. In contrast to still images, videos encompass an added
temporal dimension. Due to the ambiguity of text, there are countless ways to
edit frames so they align with the target prompt. Consequently, naively
applying I2I models on videos often produces unsatisfactory pixel flickering
between frames.

To improve frame consistency, pioneering studies edit multiple frames jointly
by inflating the image model with spatial-temporal attention [46, 25, 6, 35].
While these methods offer improvements, they do not fully attain the sought-
after temporal consistency. This is because the motion within videos is merely
retained in an _implicit_ manner within the attention module. Furthermore, a
growing body of research employs _explicit_ optical flow guidance from videos.
Specifically, flow is used to derive pixel correspondence, resulting in a
pixel-wise mapping between two frames. The correspondence is later utilized to
obtain occlusion masks for inpainting [49, 19] or to construct a canonical
image [32] However, these hard constraints can be problematic if flow
estimation is inaccurate, which is often observed when the flow is determined
through a pre-trained model [42, 47, 48].

In this paper, we propose to harness the benefits of optical flow while
handling the imperfection in flow estimation. Specifically, we perform flow
warping from the first frame to subsequent frames. These warped frames are
expected to follow the structure of the original frames but contain some
occluded regions (marked as gray), as shown in Figure 2(b). If we use flow as
hard constraints, such as inpainting [49, 19] the occluded regions, the
inaccurate legs estimation would persist, leading to an undesirable outcome.
We seek to include an additional spatial condition, such as a depth map in
Figure 2(c), along with a temporal flow condition. The legs’ position is
correct in spatial conditions, and therefore, the joint spatial-temporal
condition would rectify the imperfect optical flow, resulting in consistent
results in Figure 2(d).

We build a video diffusion model upon an inflated spatial controlled I2I
model. We train the model to predict the input video using spatial conditions
(_e.g_., depth maps) and temporal conditions (flow-warped video). During
generation, we employ an _edit-propagate_ procedure: (1) Edit the first frame
with prevalent I2I models. (2) Propagate the edits throughout the video using
our trained model. The decoupled design allows us to adopt an autoregressive
mechanism: the current batch’s last frame can be the next batch’s first frame,
allowing us to generate lengthy videos.

We train our model with 100k real videos from ShutterStock [1], and it
generalizes well to different types of modifications, such as stylization,
object swaps, and local edits, as seen in Figure 1. Compared with existing V2V
methods, our FlowVid demonstrates significant advantages in terms of
efficiency and quality. Our FlowVid can generate 120 frames (4 seconds at 30
FPS) in high-resolution (512$\times$512) in just 1.5 minutes on one A-100 GPU,
which is 3.1$\times$, 7.2$\times$ and 10.5$\times$ faster than state-of-the-
art methods CoDeF [32] (4.6 minutes) Rerender [49] (10.8 minutes), and
TokenFlow [13] (15.8 minutes). We conducted a user study on 25 DAVIS [34]
videos and designed 115 prompts. Results show that our method is more robust
and achieves a preference rate of 45.7% compared to CoDeF (3.5%) Rerender
(10.2%) and TokenFlow (40.4%)

Our contributions are summarized as follows: (1) We introduce FlowVid, a V2V
synthesis method that harnesses the benefits of optical flow, while delicately
handling the imperfection in flow estimation. (2) Our decoupled edit-propagate
design supports multiple applications, including stylization, object swap, and
local editing. Furthermore, it empowers us to generate lengthy videos via
autoregressive evaluation. (3) Large-scale human evaluation indicates the
efficiency and high generation quality of FlowVid.

##  2 Related Work

###  2.1 Image-to-image Diffusion Models

Benefiting from large-scale pre-trained text-to-image (T2I) diffusion models
[39, 40, 2, 11], progress has been made in text-based image-to-image (I2I)
generation [31, 43, 24, 14, 51, 33, 30, 10]. Beginning with image editing
methods, Prompt-to-prompt [14] and PNP [43] manipulate the attentions in the
diffusion process to edit images according to target prompts. Instruct-pix2pix
[4] goes a step further by training an I2I model that can directly interpret
and follow human instructions. More recently, I2I methods have extended user
control by allowing the inclusion of reference images to precisely define
target image compositions. Notably, ControlNet, T2I-Adapter [31], and Composer
[20] have introduced spatial conditions, such as depth maps, enabling
generated images to replicate the structure of the reference. Our method falls
into this category as we aim to generate a new video while incorporating the
spatial composition in the original one. However, it’s important to note that
simply applying these I2I methods to individual video frames can yield
unsatisfactory results due to the inherent challenge of maintaining
consistency across independently generated frames (per-frame results can be
found in Section 5.2).

###  2.2 Video-to-video Diffusion Models

To jointly generate coherent multiple frames, it is now a common standard to
inflate image models to video: replacing spatial-only attention with spatial-
temporal attention. For instance, Tune-A-Video [46], Vid-to-vid zero [44],
Text2video-zero [25], Pix2Video [6] and FateZero [35] performs cross-frame
attention of each frame on anchor frame, usually the first frame and the
previous frame to preserve appearance consistency. TokenFlow [13] further
explicitly enforces semantic correspondences of diffusion features across
frames to improve consistency. Furthermore, more works are adding spatial
controls, _e.g_., depth map to constraint the generation. Zhang’s ControlVideo
[50] proposes to extend image-based ControlNet to the video domain with full
cross-frame attention. Gen-1 [12], VideoComposer [45], Control-A-Video [7] and
Zhao’s ControlVideo [52] train V2V models with paired spatial controls and
video data. Our method falls in the same category but it also includes the
imperfect temporal flow information into the training process alongside
spatial controls. This addition enhances the overall robustness and
adaptability of our method.

Another line of work is representing video as 2D images, as seen in methods
like layered atlas [23], Text2Live [3], shape-aware-edit [26], and CoDeF [32].
However, these methods often require per-video optimization and they also face
performance degradation when dealing with large motion, which challenges the
creation of image representations.

###  2.3 Optical flow for video-to-video synthesis

The use of optical flow to propagate edits across frames has been explored
even before the advent of diffusion models, as demonstrated by the well-known
Ebsythn [22] approach. In the era of diffusion models, Chu’s Video ControlNet
[9] employs the ground-truth (gt) optical flow from synthetic videos to
enforce temporal consistency among corresponding pixels across frames.
However, it’s important to note that ground-truth flow is typically
unavailable in real-world videos, where flow is commonly estimated using
pretrained models [42, 47, 48]. Recent methods like Rerender [49], MeDM [8],
and Hu’s VideoControlNet [19] use estimated flow to generate occlusion masks
for in-painting. In other words, these methods ”force” the overlapped regions
to remain consistent based on flow estimates. Similarly, CoDeF [32] utilizes
flow to guide the generation of canonical images. These approaches all assume
that flow could be treated as an accurate supervision signal that must be
strictly adhered to. In contrast, our FlowVid recognizes the imperfections
inherent in flow estimation and presents an approach that leverages its
potential without imposing rigid constraints.

##  3 Preliminary

Figure 3: Overview of our FlowVid. (a) Training: we first get the spatial
conditions (predicted depth maps) and estimated optical flow from the input
video. For all frames, we use flow to perform warping from the first frame.
The resulting flow-warped video is expected to have a similar structure as the
input video but with some occluded regions (marked as gray, better zoomed in).
We train a video diffusion model with spatial conditions $c$ and flow
information $f$. (b) Generation: we edit the first frame with existing I2I
models and use the flow in the input video to get the flow warped edited
video. The flow condition spatial condition jointly guides the output video
synthesis.

#### Latent Diffusion Models

Denoising Diffusion Probabilistic Models (DDPM) [16] generate images through a
progressive noise removal process applied to an initial Gaussian noise,
carried out for $T$ time steps. Latent Diffusion models [39] conduct diffusion
process in latent space to make it more efficient. Specifically, an encoder
$\mathcal{E}$ compresses an image $I\in\mathbb{R}^{H\times W\times 3}$ to a
low-resolution latent code $z=\mathcal{E}(I)\in\mathbb{R}^{H/8\times W/8\times
4}$. Given $z_{0}:=z$, the Gaussian noise is gradually added on $z_{0}$ with
time step $t$ to get noisy sample $z_{t}$. Text prompt $\tau$ is also a
commonly used condition. A time-conditional U-Net $\epsilon_{\theta}$ is
trained to reverse the process with the loss function:

$\mathcal{L}_{LDM}=\mathbb{E}_{z_{0},t,\tau,\epsilon\sim\mathcal{N}(0,1)}\|\epsilon-\epsilon_{\theta}(z_{t},t,\tau)\|_{2}^{2}\vspace{-1em}$
(1)

#### ControlNet

ControlNet provides additional spatial conditions, such as canny edge [5] and
depth map [38], to control the generation of images. More specifically,
spatial conditions $C\in\mathbb{R}^{H\times W\times 3}$ are first converted to
latents $c\in\mathbb{R}^{H/8\times W/8\times 4}$ via several learnable
convolutional layers. Spatial latent $c$, added by input latent $z_{t}$, is
passed to a copy of the pre-trained diffusion model, more known as ControlNet.
The ControlNet interacts with the diffusion model in multiple feature
resolutions to add spatial guidance during image generation. ControlNet
rewrites Equation 1 to

$\mathcal{L}_{CN}=\mathbb{E}_{z_{0},t,\tau,c,\epsilon\sim\mathcal{N}(0,1)}\|\epsilon-\epsilon_{\theta}(z_{t},t,\tau,c)\|_{2}^{2}$
(2)

##  4 FlowVid

For video-to-video generation, given an input video with $N$ frames
$\mathcal{I}=\\{I_{1},\dots,I_{N}\\}$ and a text prompt $\tau$, the goal is
transfer it to a new video
$\mathcal{I^{\prime}}=\\{I^{\prime}_{1},\dots,I^{\prime}_{N}\\}$ which adheres
to the provided prompt $\tau^{\prime}$, while keeping consistency across
frame. We first discuss how we inflate the image-to-image diffusion model,
such as ControlNet to video, with spatial-temporal attention [46, 25, 6, 35]
(Section 4.1) Then, we introduce how to incorporate imperfect optical flow as
a condition into our model (Section 4.2). Lastly, we introduce the edit-
propagate design for generation (Section 4.3).

###  4.1 Inflating image U-Net to accommodate video

The latent diffusion models (LDMs) are built upon the architecture of U-Net,
which comprises multiple encoder and decoder blocks. Each block has two
components: a residual convolutional module and a transformer module. The
transformer module, in particular, comprises a spatial self-attention layer, a
cross-attention layer, and a feed-forward network. To extend the U-Net
architecture to accommodate an additional temporal dimension, we first modify
all the 2D layers within the convolutional module to pseudo-3D layers and add
an extra temporal self-attention layer [18]. Following common practice [18,
46, 25, 6, 35], we further adapt the spatial self-attention layer to a
spatial-temporal self-attention layer. For video frame $I_{i}$, the attention
matrix would take the information from the first frame $I_{1}$ and the
previous frame $I_{i-1}$. Specifically, we obtain the query feature from frame
$I_{i}$, while getting the key and value features from $I_{1}$ and $I_{i-1}$.
The $\mathrm{Attention}(Q,K,V)$ of spatial-temporal self-attention could be
written as

$\footnotesize{Q=W^{Q}z_{I_{i}},K=W^{K}\left[z_{I_{1}},z_{I_{i-1}}\right],V=W^{V}\left[z_{I_{1}},z_{I_{i-1}}\right]}$
(3)

where $W^{Q}$, $W^{K}$, and $W^{V}$ are learnable matrices that project the
inputs to query, key, and value. $z_{I_{i}}$ is the latent for frame $I_{i}$.
$\left[\cdot\right]$ denotes concatenation operation. Our model includes an
additional ControlNet U-Net that processes spatial conditions. We discovered
that it suffices only to expand the major U-Net, as the output from the
ControlNet U-Net is integrated into this major U-Net.

###  4.2 Training with joint spatial-temporal conditions

Upon expanding the image model, a straightforward method might be to train the
video model using paired depth-video data. Yet, our empirical analysis
indicates that this leads to sub-optimal results, as detailed in the ablation
study in Section 5.4. We hypothesize that this method neglects the temporal
clue within the video, making the frame consistency hard to maintain. While
some studies, such as Rerender [49] and CoDeF [32], incorporate optical flow
in video synthesis, they typically apply it as a rigid constraint. In
contrast, our approach uses flow as a soft condition, allowing us to manage
the imperfections commonly found in flow estimation.

Given a sequence of frames $\mathcal{I}$, we calculate the flow between the
first frame $I_{1}$ and other frames $I_{i}$, using a pre-trained flow
estimation model UniMatch [48]. We denote the $\mathcal{F}_{1\rightarrow i}$
and $\mathcal{F}_{i\rightarrow 1}$ as the forward and backward flow. Using
forward-backward consistency check [29], we can derive forward and backward
occlusion masks $O^{fwd}_{1\rightarrow i}$ and $O^{bwd}_{i\rightarrow 1}$. Use
backward flow $\mathcal{F}_{i\rightarrow 1}$ and occlusion
$O^{bwd}_{i\rightarrow 1}$, we can perform $Warp$ operation over the first
frame $I_{1}$ to get $I^{W}_{i}$. Intuitively, warped $i^{th}$ frame
$I^{W}_{i}$ has the same layout as the original frame $I_{i}$ but the pixels
are from the first frame $I_{1}$. Due to occlusion, some blank areas could be
in the $I^{W}_{i}$ (marked as gray in Figure 3).

We denote the sequence of warped frames as flow warped video
$\mathcal{I}^{W}=\\{I^{W}_{1},\dots,I^{W}_{N}\\}$. We feed $\mathcal{I}^{W}$
into the same encoder $\mathcal{E}$ to convert it into a latent representation
$f$. This latent representation is then concatenated with the noisy input
$z_{t}$ to serve as conditions. To handle the increased channel dimensions of
$f$, we augment the first layer of the U-Net with additional channels,
initializing these new channels with zero weights. We also integrate this
concatenated flow information into the spatial ControlNet U-Net, reconfiguring
its initial layer to include additional channels. With this introduced flow
information $f$, we modify Equation 2 as:

$\mathcal{L}_{FlowVid}=\mathbb{E}_{z_{0},t,\tau,c,f,\epsilon\sim\mathcal{N}(0,1)}\|\epsilon-\epsilon_{\theta}(z_{t},t,\tau,c,f)\|_{2}^{2}$
(4)

Throughout the development of our experiments, two particular design choices
have been proven crucial for enhancing our final results. First, we opted for
$v$-parameterization [41], rather than the more commonly used
$\epsilon$-parameterization. This finding is consistent with other video
diffusion models, such as Gen-1 [12] and Imagen Video [17] (see ablation in
Section 5.4). Second, incorporating additional elements beyond the flow-warped
video would further improve the performance. Specifically, including the first
frame as a constant video sequence,
$\mathcal{I}^{1st}=\\{I_{1},\dots,I_{1}\\}$, and integrating the occlusion
masks $\mathcal{O}=\\{O^{bwd}_{1\rightarrow 1},\dots,O^{bwd}_{N\rightarrow
1}\\}$ enhanced the overall output quality. We process $\mathcal{I}^{1st}$ by
transforming it into a latent representation and then concatenating it with
the noisy latent, similar to processing $\mathcal{I}^{W}$. For $\mathcal{O}$,
we resize the binary mask to match the latent size before concatenating it
with the noisy latent. Further study is included in Section 5.4.

###  4.3 Generation: edit the first frame then propagate

During the generation, we want to transfer the input video $\mathcal{I}$ to a
new video $\mathcal{I^{\prime}}$ with the target prompt $\tau^{\prime}$. To
effectively leverage the prevalent I2I models, we adopt an edit-propagate
method. This begins with editing the first frame $I_{1}$ using I2I models,
resulting in an edited first frame $I^{\prime}_{1}$. We then propagate the
edits to subsequent $i^{th}$ frame by using the flow
$\mathcal{F}_{i\rightarrow 1}$ and the occlusion mask $O^{bwd}_{i\rightarrow
1}$, derived from the input video $\mathcal{I}$. This process yields the flow-
warped edited video $\mathcal{I^{\prime}}^{W}=\\{I^{\prime
W}_{1},\dots,I^{\prime W}_{N}\\}$. We input $\mathcal{I^{\prime}}^{W}$ into
the same encoder $\mathcal{E}$ and concatenate the resulting flow latent $f$
with a randomly initialized Gaussian noise $z_{T}$ drawn from the normal
distribution $\mathcal{N}$. The spatial conditions from the input video are
also used to guide the structural layout of the synthesized video.
Intuitively, the flow-warped edited video serves as a texture reference while
spatial controls regularize the generation, especially when we have inaccurate
flow. After DDIM denoising, the denoised latent $z_{0}$ is brought back to
pixel space with a decoder $\mathcal{D}$ to get the final output.

Figure 4: Effect of color calibration in autoregressive evaluation. (a) When
the autoregressive evaluation goes from the 1st batch to the 13th batch, the
results without color calibration become gray. (b) The results are more stable
with the proposed color calibration.

In addition to offering the flexibility to select I2I models for initial frame
edits, our model is inherently capable of producing extended video clips in an
autoregressive manner. Once the first $N$ edited frames
$\\{I^{\prime}_{1},\dots,I^{\prime}_{N}\\}$ are generated, the $N^{th}$ frame
$I^{\prime}_{N}$ can be used as the starting point for editing the subsequent
batch of frames $\\{I_{N},\dots,I_{2N-1}\\}$. However, a straightforward
autoregressive approach may lead to a grayish effect, where the generated
images progressively become grayer, see Figure 4(a). We believe this is a
consequence of the lossy nature of the encoder and decoder, a phenomenon also
noted in Rerender [49]. To mitigate this issue, we introduce a simple global
color calibration technique that effectively reduces the graying effect.
Specifically, for each frame $I^{\prime}_{j}$ in the generated sequence
$\\{I^{\prime}_{1},\dots,I^{\prime}_{M(N-1)+1}\\}$, where $M$ is the number of
autoregressive batches, we calibrate its mean and variance to match those of
$I^{\prime}_{1}$. The effect of calibration is shown in Figure 4(b), where the
global color is preserved across autoregressive batches.

$I^{\prime\prime}_{j}=\left(\frac{I^{\prime}_{j}-\text{mean}(I^{\prime}_{j})}{\text{std}(I^{\prime}_{j})}\right)\times\text{std}(I^{\prime}_{1})+\text{mean}(I^{\prime}_{1})$
(5)

Another advantageous strategy we discovered is the integration of self-
attention features from DDIM inversion, a technique also employed in works
like FateZero [35] and TokenFlow [13]. This integration helps preserve the
original structure and motion in the input video. Concretely, we use DDIM
inversion to invert the input video with the original prompt and save the
intermediate self-attention maps at various timesteps, usually 20. During the
generation with the target prompt, we substitute the keys and values in the
self-attention modules with these pre-stored maps. Then, during the generation
process guided by the target prompt, we replace the keys and values within the
self-attention modules with previously saved corresponding maps.

##  5 Experiments

Figure 5: Qualitative comparison with representative V2V models. Our method
stands out in terms of prompt alignment and overall video quality. We highly
encourage readers to refer to video comparisons in our supplementary videos.

###  5.1 Settings

#### Implementation Details

We train our model with 100k videos from Shutterstock [1]. For each training
video, we sequentially sample 16 frames with interval {2,4,8}, which represent
videos lasting {1,2,4} seconds (taking videos with FPS of 30). The resolution
of all images, including input frames, spatial condition images, and flow
warped frames, is set to 512$\times$512 via center crop. We train the model
with a batch size of 1 per GPU and a total batch size of 8 with 8 GPUs. We
employ AdamW optimizer [28] with a learning rate of 1e-5 for 100k iterations.
As detailed in our method, we train the major U-Net and ControlNet U-Net joint
branches with $v$-parameterization [41]. The training takes four days on one
8-A100-80G node.

During generation, we first generate keyframes with our trained model and then
use an off-the-shelf frame interpolation model, such as RIFE [21], to generate
non-key frames. By default, we produce 16 key frames at an interval of 4,
corresponding to a 2-second clip at 8 FPS. Then, we use RIFE to interpolate
the results to 32 FPS. We employ classifier-free guidance [15] with a scale of
7.5 and use 20 inference sampling steps. Additionally, the Zero SNR noise
scheduler [27] is utilized. We also fuse the self-attention features obtained
during the DDIM inversion of corresponding key frames from the input video,
following FateZero [35]. We evaluate our FlowVid with two different spatial
conditions: canny edge maps [5] and depth maps [38]. A comparison of these
controls can be found in Section 5.4.

#### Evaluation

We select the 25 object-centric videos from the public DAVIS dataset [34],
covering humans, animals, etc. We manually design 115 prompts for these
videos, spanning from stylization to object swap. Besides, we also collect 50
Shutterstock videos [1] with 200 designed prompts. We conduct both qualitative
(see Section 5.2) and quantitative comparisons (see Section 5.3) with state-
of-the-art methods including Rerender [49], CoDeF [32] and TokenFlow [13]. We
use their official codes with the default settings.

###  5.2 Qualitative results

In Figure 5, we qualitatively compare our method with several representative
approaches. Starting with a per-frame baseline directly applying I2I models,
ControlNet, to each frame. Despite using a fixed random seed, this baseline
often results in noticeable flickering, such as in the man’s clothing and the
tiger’s fur. CoDeF [32] produces outputs with significant blurriness when
motion is big in input video, evident in areas like the man’s hands and the
tiger’s face. Rerender [49] often fails to capture large motions, such as the
movement of paddles in the left example. Also, the color of the edited tiger’s
legs tends to blend in with the background. TokenFlow [13] occasionally
struggles to follow the prompt, such as transforming the man into a pirate in
the left example. It also erroneously depicts the tiger with two legs for the
first frame in the right example, leading to flickering in the output video.
In contrast, our method stands out in terms of editing capabilities and
overall video quality, demonstrating superior performance over these methods.
We highly encourage readers to refer to more video comparisons in our
supplementary videos.

###  5.3 Quantitative results

Table 1: Quantitative comparison with existing V2V models. The preference rate indicates the frequency the method is preferred among all the four methods in human evaluation. Runtime shows the time to synthesize a 4-second video with 512$\times$512 resolution on one A-100-80GB. Cost is normalized with our method. | Preference rate | Runtime | Cost $\downarrow$
---|---|---|---
(mean $\pm$ std %) $\uparrow$ |  (mins) $\downarrow$
TokenFlow |  40.4 $\pm$ 5.3 | 15.8 |  10.5 $\times$
Rerender |  10.2 $\pm$ 7.1 | 10.8 |  7.2 $\times$
CoDeF |  3.5 $\pm$ 1.9 | 4.6 |  3.1 $\times$
FlowVid (Ours) |  45.7 $\pm$ 6.4 | 1.5 | 1.0 $\times$

#### User study

We conducted a human evaluation to compare our method with three notable
works: CoDeF [32], Rerender [49], and TokenFlow [13]. The user study involves
25 DAVIS videos and 115 manually designed prompts. Participants are shown four
videos and asked to identify which one has the best quality, considering both
temporal consistency and text alignment. The results, including the average
preference rate and standard deviation from five participants for all methods,
are detailed in Table 1. Our method achieved a preference rate of 45.7%,
outperforming CoDeF (3.5%), Rerender (10.2%), and TokenFlow (40.4%). During
the evaluation, we observed that CoDeF struggles with significant motion in
videos. The blurry constructed canonical images would always lead to
unsatisfactory results. Rerender occasionally experiences color shifts and
bright flickering. TokenFlow sometimes fails to sufficiently alter the video
according to the prompt, resulting in an output similar to the original video.

#### Pipeline runtime

We also compare runtime efficiency with existing methods in Table 1. Video
lengths can vary, resulting in different processing times. Here, we use a
video containing 120 frames (4 seconds video with FPS of 30). The resolution
is set to 512 $\times$ 512\. Both our FlowVid model and Rerender [49] use a
key frame interval of 4. We generate 31 keyframes by applying autoregressive
evaluation twice, followed by RIFE [21] for interpolating the non-key frames.
The total runtime, including image processing, model operation, and frame
interpolation, is approximately 1.5 minutes. This is significantly faster than
CoDeF (4.6 minutes), Rerender (10.8 minutes) and TokenFlow (15.8 minutes),
being 3.1$\times$, 7.2$\times$, and 10.5 $\times$ faster, respectively. CoDeF
requires per-video optimization to construct the canonical image. While
Rerender adopts a sequential method, generating each frame one after the
other, our model utilizes batch processing, allowing for more efficient
handling of multiple frames simultaneously. In the case of TokenFlow, it
requires a large number of DDIM inversion steps (typically around 500) for all
frames to obtain the inverted latent, which is a resource-intensive process.
We further report the runtime breakdown (Figure 10) in the Appendix.

(a) Condition types.

Condition choices | Winning rate $\uparrow$
---|---
(I) | (II) | (III) | (IV)
✓ | $\times$ | $\times$ | $\times$ | 9%
✓ | ✓ | $\times$ | $\times$ | 38%
✓ | ✓ | ✓ | $\times$ | 42 %
(a) Winning rate over our FlowVid (I + II + III + IV).

Figure 6: Ablation study of condition combinations. (a) Four types of
conditions. (b) The different combinations all underperform our final setting
which combines all four conditions.

###  5.4 Ablation study

#### Condition combinations

We study the four types of conditions in Figure 6(a): (I) Spatial controls:
such as depth maps [38]. (II) Flow warped video: frames warped from the first
frame using optical flow. (III) Flow occlusion: masks indicate which parts are
occluded (marked as white). (IV) First frame. We evaluate combinations of
these conditions in Figure 6(b), assessing their effectiveness by their
winning rate against our full model which contains all four conditions. The
spatial-only condition achieved a 9% winning rate, limited by its lack of
temporal information. Including flow warped video significantly improved the
winning rate to 38%, underscoring the importance of temporal guidance. We use
gray pixels to indicate occluded areas, which might blend in with the original
gray colors in the images. To avoid potential confusion, we further include a
binary flow occlusion mask, which better helps the model to tell which part is
occluded or not. The winning rate is further improved to 42%. Finally, we
added the first frame condition to provide better texture guidance,
particularly useful when the occlusion mask is large and few original pixels
remain.

Figure 7: Ablation study of different spatial conditions. Canny edge and depth
map are estimated from the input frame. Canny edge provides more detailed
controls (good for stylization) while depth map provides more editing
flexibility (good for object swap). Figure 8: Ablation study of different
parameterizations. $\epsilon$-prediction often predicts unnatural global color
while $v$-prediction doesn’t. Prompt: ’a man is running on Mars’.

#### Different control type: edge and depth

We study two types of spatial conditions in our FlowVid: canny edge [5] and
depth map [38]. Given an input frame as shown in Figure 7(a), the canny edge
retains more details than the depth map, as seen from the eyes and mouth of
the panda. The strength of spatial control would, in turn, affect the video
editing. For style transfer prompt ’A Chinese ink painting of a panda eating
bamboo’, as shown in Figure 7(c), the output of canny condition could keep the
mouth of the panda in the right position while the depth condition would guess
where the mouth is and result in an open mouth. The flexibility of the depth
map, however, would be beneficial if we are doing object swap with prompt ’A
koala eating bamboo’, as shown in Figure 7(d); the canny edge would put a pair
of panda eyes on the face of the koala due to the strong control, while depth
map would result in a better koala edit. During our evaluation, we found canny
edge works better when we want to keep the structure of the input video as
much as possible, such as stylization. The depth map works better if we have a
larger scene change, such as an object swap, which requires more considerable
editing flexibility.

####  $v$-prediction and $\epsilon$-prediction

While $\epsilon$-prediction is commonly used for parameterization in diffusion
models, we found it may suffer from unnatural global color shifts across
frames, as shown in Figure 8. Even though all these two methods use the same
flow warped video, the $\epsilon$-prediction introduces an unnatural grayer
color. This phenomenon is also found in Imagen-Video [17].

###  5.5 Limitations

Although our FlowVid achieves significant performance, it does have some
limitations. First, our FlowVid heavily relies on the first frame generation,
which should be structurally aligned with the input frame. As shown in Figure
9(a), the edited first frame identifies the hind legs of the elephant as the
front nose. The erroneous nose would propagate to the following frame and
result in an unsatisfactory final prediction. The other challenge is when the
camera or the object moves so fast that large occlusions occur. In this case,
our model would guess, sometimes hallucinate, the missing blank regions. As
shown in Figure 9(b), when the ballerina turns her body and head, the entire
body part is masked out. Our model manages to handle the clothes but turns the
back of the head into the front face, which would be confusing if displayed in
a video.

Figure 9: Limitations of FlowVid. Failure cases include (a) the edited first
frame doesn’t align structurally with the original first frame, and (b) large
occlusions caused by fast motion.

##  6 Conclusion

In this paper, we propose a consistent video-to-video synthesis method using
joint spatial-temporal conditions. In contrast to prior methods that strictly
adhere to optical flow, our approach incorporates flow as a supplementary
reference in synergy with spatial conditions. Our model can adapt existing
image-to-image models to edit the first frame and propagate the edits to
consecutive frames. Our model is also able to generate lengthy videos via
autoregressive evaluation. Both qualitative and quantitative comparisons with
current methods highlight the efficiency and high quality of our proposed
techniques.

##  7 Acknowledgments

We would like to express sincere gratitude to Yurong Jiang, Chenyang Qi,
Zhixing Zhang, Haoyu Ma, Yuchao Gu, Jonas Schult, Hung-Yueh Chiang, Tanvir
Mahmud, Richard Yuan for the constructive discussions.

Feng Liang and Diana Marculescu were supported in part by the ONR Minerva
program, iMAGiNE - the Intelligent Machine Engineering Consortium at UT
Austin, and a UT Cockrell School of Engineering Doctoral Fellowship.

## References

  * Shu [2023] Stock footage video, royalty-free hd, 4k video clips, 2023.
  * Balaji et al. [2022] Yogesh Balaji, Seungjun Nah, Xun Huang, Arash Vahdat, Jiaming Song, Karsten Kreis, Miika Aittala, Timo Aila, Samuli Laine, Bryan Catanzaro, et al.  ediffi: Text-to-image diffusion models with an ensemble of expert denoisers.  _arXiv preprint arXiv:2211.01324_ , 2022.
  * Bar-Tal et al. [2022] Omer Bar-Tal, Dolev Ofri-Amar, Rafail Fridman, Yoni Kasten, and Tali Dekel.  Text2live: Text-driven layered image and video editing.  In _European conference on computer vision_ , pages 707–723. Springer, 2022.
  * Brooks et al. [2023] Tim Brooks, Aleksander Holynski, and Alexei A Efros.  Instructpix2pix: Learning to follow image editing instructions.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 18392–18402, 2023.
  * Canny [1986] John Canny.  A computational approach to edge detection.  _IEEE Transactions on pattern analysis and machine intelligence_ , (6):679–698, 1986.
  * Ceylan et al. [2023] Duygu Ceylan, Chun-Hao P Huang, and Niloy J Mitra.  Pix2video: Video editing using image diffusion.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 23206–23217, 2023.
  * Chen et al. [2023] Weifeng Chen, Jie Wu, Pan Xie, Hefeng Wu, Jiashi Li, Xin Xia, Xuefeng Xiao, and Liang Lin.  Control-a-video: Controllable text-to-video generation with diffusion models.  _arXiv preprint arXiv:2305.13840_ , 2023.
  * Chu et al. [2023a] Ernie Chu, Tzuhsuan Huang, Shuo-Yen Lin, and Jun-Cheng Chen.  Medm: Mediating image diffusion models for video-to-video translation with temporal correspondence guidance.  _arXiv preprint arXiv:2308.10079_ , 2023a.
  * Chu et al. [2023b] Ernie Chu, Shuo-Yen Lin, and Jun-Cheng Chen.  Video controlnet: Towards temporally consistent synthetic-to-real video translation using conditional image diffusion models.  _arXiv preprint arXiv:2305.19193_ , 2023b.
  * Couairon et al. [2022] Guillaume Couairon, Jakob Verbeek, Holger Schwenk, and Matthieu Cord.  Diffedit: Diffusion-based semantic image editing with mask guidance.  _arXiv preprint arXiv:2210.11427_ , 2022.
  * Dai et al. [2023] Xiaoliang Dai, Ji Hou, Chih-Yao Ma, Sam Tsai, Jialiang Wang, Rui Wang, Peizhao Zhang, Simon Vandenhende, Xiaofang Wang, Abhimanyu Dubey, et al.  Emu: Enhancing image generation models using photogenic needles in a haystack.  _arXiv preprint arXiv:2309.15807_ , 2023.
  * Esser et al. [2023] Patrick Esser, Johnathan Chiu, Parmida Atighehchian, Jonathan Granskog, and Anastasis Germanidis.  Structure and content-guided video synthesis with diffusion models.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 7346–7356, 2023.
  * Geyer et al. [2023] Michal Geyer, Omer Bar-Tal, Shai Bagon, and Tali Dekel.  Tokenflow: Consistent diffusion features for consistent video editing.  _arXiv preprint arXiv:2307.10373_ , 2023.
  * Hertz et al. [2022] Amir Hertz, Ron Mokady, Jay Tenenbaum, Kfir Aberman, Yael Pritch, and Daniel Cohen-Or.  Prompt-to-prompt image editing with cross attention control.  _arXiv preprint arXiv:2208.01626_ , 2022.
  * Ho and Salimans [2022] Jonathan Ho and Tim Salimans.  Classifier-free diffusion guidance.  _arXiv preprint arXiv:2207.12598_ , 2022.
  * Ho et al. [2020] Jonathan Ho, Ajay Jain, and Pieter Abbeel.  Denoising diffusion probabilistic models.  _Advances in neural information processing systems_ , 33:6840–6851, 2020.
  * Ho et al. [2022a] Jonathan Ho, William Chan, Chitwan Saharia, Jay Whang, Ruiqi Gao, Alexey Gritsenko, Diederik P Kingma, Ben Poole, Mohammad Norouzi, David J Fleet, et al.  Imagen video: High definition video generation with diffusion models.  _arXiv preprint arXiv:2210.02303_ , 2022a.
  * Ho et al. [2022b] Jonathan Ho, Tim Salimans, Alexey Gritsenko, William Chan, Mohammad Norouzi, and David J Fleet.  Video diffusion models.  _arXiv:2204.03458_ , 2022b.
  * Hu and Xu [2023] Zhihao Hu and Dong Xu.  Videocontrolnet: A motion-guided video-to-video translation framework by using diffusion model with controlnet.  _arXiv preprint arXiv:2307.14073_ , 2023.
  * Huang et al. [2023] Lianghua Huang, Di Chen, Yu Liu, Yujun Shen, Deli Zhao, and Jingren Zhou.  Composer: Creative and controllable image synthesis with composable conditions.  _arXiv preprint arXiv:2302.09778_ , 2023.
  * Huang et al. [2022] Zhewei Huang, Tianyuan Zhang, Wen Heng, Boxin Shi, and Shuchang Zhou.  Real-time intermediate flow estimation for video frame interpolation.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , 2022.
  * Jamriška et al. [2019] Ondřej Jamriška, Šárka Sochorová, Ondřej Texler, Michal Lukáč, Jakub Fišer, Jingwan Lu, Eli Shechtman, and Daniel Sỳkora.  Stylizing video by example.  _ACM Transactions on Graphics (TOG)_ , 38(4):1–11, 2019.
  * Kasten et al. [2021] Yoni Kasten, Dolev Ofri, Oliver Wang, and Tali Dekel.  Layered neural atlases for consistent video editing.  _ACM Transactions on Graphics (TOG)_ , 40(6):1–12, 2021.
  * Kawar et al. [2023] Bahjat Kawar, Shiran Zada, Oran Lang, Omer Tov, Huiwen Chang, Tali Dekel, Inbar Mosseri, and Michal Irani.  Imagic: Text-based real image editing with diffusion models.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 6007–6017, 2023.
  * Khachatryan et al. [2023] Levon Khachatryan, Andranik Movsisyan, Vahram Tadevosyan, Roberto Henschel, Zhangyang Wang, Shant Navasardyan, and Humphrey Shi.  Text2video-zero: Text-to-image diffusion models are zero-shot video generators.  _arXiv preprint arXiv:2303.13439_ , 2023.
  * Lee et al. [2023] Yao-Chih Lee, Ji-Ze Genevieve Jang, Yi-Ting Chen, Elizabeth Qiu, and Jia-Bin Huang.  Shape-aware text-driven layered video editing.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 14317–14326, 2023.
  * Lin et al. [2023] Shanchuan Lin, Bingchen Liu, Jiashi Li, and Xiao Yang.  Common diffusion noise schedules and sample steps are flawed.  _arXiv preprint arXiv:2305.08891_ , 2023.
  * Loshchilov and Hutter [2017] Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization.  _arXiv preprint arXiv:1711.05101_ , 2017.
  * Meister et al. [2018] Simon Meister, Junhwa Hur, and Stefan Roth.  Unflow: Unsupervised learning of optical flow with a bidirectional census loss.  In _Proceedings of the AAAI conference on artificial intelligence_ , 2018.
  * Meng et al. [2021] Chenlin Meng, Yutong He, Yang Song, Jiaming Song, Jiajun Wu, Jun-Yan Zhu, and Stefano Ermon.  Sdedit: Guided image synthesis and editing with stochastic differential equations.  _arXiv preprint arXiv:2108.01073_ , 2021.
  * Mou et al. [2023] Chong Mou, Xintao Wang, Liangbin Xie, Jian Zhang, Zhongang Qi, Ying Shan, and Xiaohu Qie.  T2i-adapter: Learning adapters to dig out more controllable ability for text-to-image diffusion models.  _arXiv preprint arXiv:2302.08453_ , 2023.
  * Ouyang et al. [2023] Hao Ouyang, Qiuyu Wang, Yuxi Xiao, Qingyan Bai, Juntao Zhang, Kecheng Zheng, Xiaowei Zhou, Qifeng Chen, and Yujun Shen.  Codef: Content deformation fields for temporally consistent video processing.  _arXiv preprint arXiv:2308.07926_ , 2023.
  * Parmar et al. [2023] Gaurav Parmar, Krishna Kumar Singh, Richard Zhang, Yijun Li, Jingwan Lu, and Jun-Yan Zhu.  Zero-shot image-to-image translation.  In _ACM SIGGRAPH 2023 Conference Proceedings_ , pages 1–11, 2023.
  * Pont-Tuset et al. [2017] Jordi Pont-Tuset, Federico Perazzi, Sergi Caelles, Pablo Arbeláez, Alex Sorkine-Hornung, and Luc Van Gool.  The 2017 davis challenge on video object segmentation.  _arXiv preprint arXiv:1704.00675_ , 2017.
  * Qi et al. [2023] Chenyang Qi, Xiaodong Cun, Yong Zhang, Chenyang Lei, Xintao Wang, Ying Shan, and Qifeng Chen.  Fatezero: Fusing attentions for zero-shot text-based video editing.  _arXiv preprint arXiv:2303.09535_ , 2023.
  * Radford et al. [2021] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al.  Learning transferable visual models from natural language supervision.  In _International conference on machine learning_ , pages 8748–8763. PMLR, 2021.
  * Ramesh et al. [2022] Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen.  Hierarchical text-conditional image generation with clip latents.  _arXiv preprint arXiv:2204.06125_ , 1(2):3, 2022.
  * Ranftl et al. [2020] René Ranftl, Katrin Lasinger, David Hafner, Konrad Schindler, and Vladlen Koltun.  Towards robust monocular depth estimation: Mixing datasets for zero-shot cross-dataset transfer.  _IEEE transactions on pattern analysis and machine intelligence_ , 44(3):1623–1637, 2020.
  * Rombach et al. [2022] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer.  High-resolution image synthesis with latent diffusion models.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 10684–10695, 2022.
  * Saharia et al. [2022] Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily L Denton, Kamyar Ghasemipour, Raphael Gontijo Lopes, Burcu Karagol Ayan, Tim Salimans, et al.  Photorealistic text-to-image diffusion models with deep language understanding.  _Advances in Neural Information Processing Systems_ , 35:36479–36494, 2022.
  * Salimans and Ho [2022] Tim Salimans and Jonathan Ho.  Progressive distillation for fast sampling of diffusion models.  _arXiv preprint arXiv:2202.00512_ , 2022.
  * Teed and Deng [2020] Zachary Teed and Jia Deng.  Raft: Recurrent all-pairs field transforms for optical flow.  In _Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part II 16_ , pages 402–419. Springer, 2020.
  * Tumanyan et al. [2023] Narek Tumanyan, Michal Geyer, Shai Bagon, and Tali Dekel.  Plug-and-play diffusion features for text-driven image-to-image translation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 1921–1930, 2023.
  * Wang et al. [2023a] Wen Wang, Kangyang Xie, Zide Liu, Hao Chen, Yue Cao, Xinlong Wang, and Chunhua Shen.  Zero-shot video editing using off-the-shelf image diffusion models.  _arXiv preprint arXiv:2303.17599_ , 2023a.
  * Wang et al. [2023b] Xiang Wang, Hangjie Yuan, Shiwei Zhang, Dayou Chen, Jiuniu Wang, Yingya Zhang, Yujun Shen, Deli Zhao, and Jingren Zhou.  Videocomposer: Compositional video synthesis with motion controllability.  _arXiv preprint arXiv:2306.02018_ , 2023b.
  * Wu et al. [2023] Jay Zhangjie Wu, Yixiao Ge, Xintao Wang, Stan Weixian Lei, Yuchao Gu, Yufei Shi, Wynne Hsu, Ying Shan, Xiaohu Qie, and Mike Zheng Shou.  Tune-a-video: One-shot tuning of image diffusion models for text-to-video generation.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 7623–7633, 2023.
  * Xu et al. [2022] Haofei Xu, Jing Zhang, Jianfei Cai, Hamid Rezatofighi, and Dacheng Tao.  Gmflow: Learning optical flow via global matching.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 8121–8130, 2022.
  * Xu et al. [2023] Haofei Xu, Jing Zhang, Jianfei Cai, Hamid Rezatofighi, Fisher Yu, Dacheng Tao, and Andreas Geiger.  Unifying flow, stereo and depth estimation.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2023.
  * Yang et al. [2023] Shuai Yang, Yifan Zhou, Ziwei Liu, and Chen Change Loy.  Rerender a video: Zero-shot text-guided video-to-video translation.  _arXiv preprint arXiv:2306.07954_ , 2023.
  * Zhang et al. [2023a] Yabo Zhang, Yuxiang Wei, Dongsheng Jiang, Xiaopeng Zhang, Wangmeng Zuo, and Qi Tian.  Controlvideo: Training-free controllable text-to-video generation.  _arXiv preprint arXiv:2305.13077_ , 2023a.
  * Zhang et al. [2023b] Zhixing Zhang, Ligong Han, Arnab Ghosh, Dimitris N Metaxas, and Jian Ren.  Sine: Single image editing with text-to-image diffusion models.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 6027–6037, 2023b.
  * Zhao et al. [2023] Min Zhao, Rongzhen Wang, Fan Bao, Chongxuan Li, and Jun Zhu.  Controlvideo: Adding conditional control for one shot text-to-video editing.  _arXiv preprint arXiv:2305.17098_ , 2023.

##  Appendix A Webpage Demo

We highly recommend looking at our demo web by opening the https://jeff-
liangf.github.io/projects/flowvid/ to check the video results.

##  Appendix B Quantitative comparisons

###  B.1 CLIP scores

Inspired by previous research, we utilize CLIP [36] to evaluate the generated
videos’ quality. Specifically, we measure 1) Temporal Consistency (abbreviated
as Tem-Con), which is the mean cosine similarity across all sequential frame
pairs, and 2) Prompt Alignment (abbreviated as Pro-Ali), which calculates the
mean cosine similarity between a given text prompt and all frames in a video.
Our evaluation, detailed in Table 2, includes an analysis of 116 video-prompt
pairs from the DAVIS dataset. Notably, CoDeF [32] and Rerender [49] exhibit
lower scores in both temporal consistency and prompt alignment, aligning with
the findings from our user study. Interestingly, TokenFlow shows superior
performance in maintaining temporal consistency. However, it is important to
note that TokenFlow occasionally underperforms in modifying the video, leading
to outputs that closely resemble the original input. Our approach not only
secures the highest ranking in prompt alignment but also performs commendably
in temporal consistency, achieving second place.

Table 2: CLIP score comparisons. ’Tem-Con’ stands for temporal consistency, and ’Pro-Ali’ stands for prompt alignment. Method |  Tem-Con $\uparrow$ |  Pro-Ali $\uparrow$
---|---|---
CoDeF [32] | 96.98 | 30.83
Rerender [49] | 96.88 | 31.84
TokenFlow [13] | 97.30 | 33.11
Ours | 97.08 | 33.20

###  B.2 Runtime breakdown

We benchmark the runtime with a 512 $\times$ 512 resolution video containing
120 frames (4 seconds video with FPS of 30). Our runtime evaluation was
conducted on a 512 × 512 resolution video comprising 120 frames, equating to a
4-second clip at 30 frames per second (FPS). Both our methods, FlowVid, and
Rerender [49], initially create key frames followed by the interpolation of
non-key frames. For these techniques, we opted for a keyframe interval of 4.
FlowVid demonstrates a marked efficiency in keyframe generation, completing 31
keyframes in just 1.1 minutes, compared to Rerender’s 5.2 minutes. This
significant time disparity is attributed to our batch processing approach in
FlowVid, which handles 16 images simultaneously, unlike Rerender’s sequential,
single-image processing method. In the aspect of frame interpolation, Rerender
employs a reference-based EbSynth method, which relies on input video’s non-
key frames for interpolation guidance. This process is notably time-consuming,
requiring 5.6 minutes to interpolate 90 non-key frames. In contrast, our
method utilizes a non-reference-based approach, RIFE [21], which significantly
accelerates the process. Two other methods are CoDeF [32] and TokenFlow [13],
both of which necessitate per-video preparation. Specifically, CoDeF involves
training a model for reconstructing the canonical image, while TokenFlow
requires a 500-step DDIM inversion process to acquire the latent
representation. CoDeF and TokenFlow require approximately 3.5 minutes and 10.4
minutes, respectively, for this initial preparation phase.

Figure 10: Runtime breakdown of generating a 4-second 512 $\times$ 512
resolution video with 30 FPS. Time is measured on one A100-80GB GPU.


0.5in,1.0in,1.5in,2.0in,2.5in,3.0in,3.5in,4.0in,4.5in,5.0in,5.5in,6.0in, 9 A
dual identity based symbolic understanding of the Gödel’s incompleteness
theorems, P-NP problem, Zeno’s paradox and Continuum Hypothesis

Arun Uday

Abstract: A semantic analysis of formal systems is undertaken, wherein the
duality of their symbolic definition based on the $``$State of Doing$"$ and
$``$State of Being$"$ is brought out. We demonstrate that when these states
are defined in a way that opposes each other, it leads to contradictions. This
results in the incompleteness of formal systems as captured in the Gödel’s
theorems. We then proceed to resolve the P-NP problem, which we show to be a
manifestation of Gödel’s theorem itself. We then discuss the Zeno’s paradox
and relate it to the same aforementioned duality, but as pertaining to
discrete and continuous spaces. We prove an important theorem regarding
representations of irrational numbers in continuous space. We extend the
result to touch upon the Continuum Hypothesis and present a new symbolic
conceptualization of space, which can address both discrete and continuous
requirements. We term this new mathematical framework as $``$hybrid space$"$ .

Keywords: Gödel, P-NP, incompleteness, complexity, Zeno, Continuum Hypothesis

  1. 1)

Gödel’s incompleteness theorems

Ever since Gödel came up with his famous theorems (Gödel [1931]) on
incompleteness of formal systems, there have been numerous interpretations of
them. Our goal here is not to undertake a full analysis of them, which has
already been done by others (Detlefsen [1979], Smith [2007], Berto [2011],
Kennedy [2014]). Rather, we attempt to build a semantic understanding of the
theorems specifically based on the duality of identity states. This will
enable us to establish the causal basis of the theorems.

We begin by stating that any formal system is defined by two semantic identity
states – the $``$State of Doing$"$ and the $``$State of Being$"$ . To cite a
simple analog from common parlance, the identity of a $``$driver$"$ is defined
as a person who drives. The identity of a $``$teacher$"$ is defined as a
person who teaches, etc. In other words, their identity states are defined by
their occupational states. Paradoxes occur when these two states, i.e. who
they are and what they do contradict each other especially when their actions
are self-referenced. This is best illustrated in the famous Russel’s paradox
(Coffa [1979]), concerning the barber who shaves only those who do not shave
themselves. In this case, the barber’s two states are:

     * •

State of Doing: Shaving someone who does not shave himself

     * •

State of Being: Shaves someone who does not shave himself

When the $``$someone$"$ here is referenced to an external person who does not
shave himself, there is no problem. But when the $``$someone$"$ is self-
referenced to the barber himself, it causes a contradiction owing to the
conflicting requirements of the States of Doing and Being.

Now, let us extend this understanding to formal systems. We know that a formal
system is defined by its axioms and rules. These in turn define the set of
theorems, which can be derived from them in the form of proofs of the
theorems. Hence, in a similar manner as the examples above, for a formal
system, its two symbolic states are:

     * •

State of Doing: Proving a proposition (correctly)

     * •

State of Being: Proves a proposition (as being true)

As with the barber example, when the proposition itself is defined as
something that is false and then self-referenced, it causes a contradiction of
the kind P,

P:= $``$PROVE THIS PROPOSITION TO BE FALSE$"$ .

The contradiction arises because if the formal system does a correct job of
the above task, its State of Doing will be – $``$Proving P to be false$"$ .
But if it successfully does that, it implies that $``$P is false$"$ is false,
or in other words P is true and hence its State of Being will be - $``$Proves
P to be true$"$ . Clearly now, there is a contradiction between the system’s
State of Doing and its State of Being. This is what we will term as mutually
opposing dual symbolic states. Gödel basically formalized this in the form of
his famous proof of incompleteness. Through the Gödel numbering system, he was
able to exploit this duality of symbolic states to construct propositions of
the kind P above to demonstrate the incompleteness of any formal system. Since
such propositions cannot be proven to be either true or false, the conclusion
is that the formal system is incomplete. To be clear, not all dual symbolic
identities result in paradoxes, but only mutually contradictory ones. The
intuition underlying this duality will form a key aspect of our analysis,
which we will carry through the rest of the paper. We will also demonstrate
why such contradictions are impossible to avoid through any meta-level
exclusions.

  2. 2)

P-NP problem

Ever since Cook formally introduced the P-NP problem (Cook [1971]), it has
gone on to become one of the most fundamental unsolved problems in theoretical
computer science. However, the history of the problem can be traced to a much
earlier time, indeed to Gödel himself. It was discovered that in 1956, Gödel
in a letter written to von Neumann enquired him about his views on the
complexity of an NP complete problem (Hartmanis [1989)). As is well
documented, the fundamental P-NP question is - if every problem whose solution
can be verified in polynomial time can also be solved in polynomial time. We
will now prove that it cannot be done so.

For this, let us construct a simple example called the $``$Alice Bob game$"$ .
The game is seemingly an easy one. Alice thinks of a sequence of indefinite
length of 0’s and 1’s, which Bob needs to start guessing. The moment he gets a
character wrong, he loses111 The assumption here is that Alice won’t lie,
i.e.- she won’t say that Bob is wrong even though he has correctly guessed the
character that Alice had in her mind . Bob agrees to play the game and they
get started. Bob tries a few times and soon gives up as he is not able to go
beyond guessing a few characters. But, he has a better idea! He writes a
computer program, which will exactly predict the sequence of numbers. He is
convinced of the brilliant logic that he has employed and now approaches Alice
with great aplomb. Alice is however unperturbed. In fact, she goes on to prove
that Bob’s computer program can never predict the exact sequence no matter
what logic he has used. Her proof relies on the familiar Cantor
diagonalization method.

Alice knows which programming language Bob uses for his programs (and it could
be anything as it doesn’t affect the validity of the proof). She conceives of
a list, $L$ of all possible computer programs, which can be written using the
language. This is just a subset of all the permutations of strings that can be
formed using the vocabulary of the language. Since these can be ordered in an
increasing order of their lengths, they will be countably infinite in number.
A subset of these programs will be those that are able to generate sequences
of 0’s and 1’s. Let us say, the ordered list $L^{{}^{\prime}}$ of these
programs is P1, P2, P3, P4 etc.

Clearly, $L^{{}^{\prime}}\subset L$

Now, she envisages the possible outputs that these programs can deliver. These
are captured in the following table wherein C1, C2, C3, C4 $\ldots$ are the
characters of the sequence generated by each of the programs P1, P2, P3, P4
$\ldots$

Program |  C1 |  C2 |  C3 |  C4 |  $\ldots$
---|---|---|---|---|---
P1 |  0 |  1 |  0 |  0 |  $\ldots$
P2 |  1 |  1 |  0 |  1 |  $\ldots$
P3 |  0 |  0 |  1 |  1 |  $\ldots$
P4 |  1 |  0 |  1 |  0 |  $\ldots$
P5 |  0 |  1 |  0 |  1 |  $\ldots$
$\ldots$ |  $\ldots$ |  $\ldots$ |  $\ldots$ |  $\ldots$ |  $\ldots$

Now, by using Cantor’s diagonalization logic, Alice is convinced that no
matter what the outputs of P1, P2, P3, P4 etc. are, Bob will never be able to
cover all the choice of sequences that she has. That is because if she were to
reverse the diagonal characters of the matrix above, that string can never
have been outputted by Bob’s program. Hence, since Alice’s set of choices
includes those that Bob’s computer program can never replicate, she concludes
that it can never win the game if it were to be played for an arbitrarily long
period of time. This means that at some point, Bob’s computer is going to
guess wrongly. Let us assume that the length of the sequence then is $n$ . We
will now prove that for this length, the Alice Bob example is actually NP
complete. We will then analyse the methodology and insights derived from this
exercise in the next section to understand the underlying basis for the
result.

For proving NP completeness, we will need to demonstrate the following three
conditions:

     * •

Condition A: Validating the output can be done in polynomial time

     * •

Condition B: Arriving at a solution non-deterministically can be done in
polynomial time

     * •

Condition C: A known NP complete program can be converted to the Alice Bob
example

We will now proceed to resolve each of the above conditions.

     * •

Resolution of Condition A: Given the final output of Bob’s program, checking
the result with Alice’s sequence is obviously a very simple process comprising
of $n$ steps (where $n$ is the length of the string). We need to check whether
each character of Bob’s sequence matches the corresponding character of
Alice’s sequence. Hence, checking is an algorithm executable in polynomial
time

     * •

Resolution of Condition B: Guessing a perfect solution non-deterministically
is again just an $n$ step process comprising of guessing each incremental
character of the sequence

     * •

Resolution of Condition C: For this, we choose the $3$ \- $SAT$ problem, which
we know is NP complete. We need to show that any input to the $3$ \- $SAT$
problem can be converted as an input to the Alice Bob problem. We can do so by
considering each disjunctive clause of the form $l_{1}\bigvee l_{2}\bigvee
l_{3}$ (where $l_{1}$ , $l_{2}$ and $l_{3}$ are the literals) in the $3$ \-
$CNF$ as a character corresponding to the Alice Bob problem with two possible
values. Indeed, the Alice Bob example is just a disguised form of the $3$ \-
$SAT$ problem (as both of them have $2^{n}$ permutations).

To understand why the $3$ \- $SAT$ problem is in NP, let us contrast it with
the $2$ \- $SAT$ problem (which is in P). With $2$ \- $SAT$ , each individual
clause of the form $l_{1}\bigvee l_{2}$ can be expressed in the form of
$a\Rightarrow b$ This is because since every disjunctive clause in the $CNF$
has to be true, it follows that $\sim l_{1}\Rightarrow l_{2}$ and $\sim$
$l_{2}\Rightarrow l_{1}$ . Hence, this is completely deterministic because if
$a$ is true so is $b$ and if $b$ is false so is $a$ . In other words, there is
only one choice for each literal depending on the value of the other literal.
So, to check if a given $2$ \- $CNF$ formula is satisfiable, we only have to
check if there are any conflicting conditions for each of the literals in all
the clauses it appears. In case any such conflicts are detected for a
particular literal, then the whole formula will be unsatisfiable.

On the other hand, in $3$ \- $SAT$ , each clause takes the form of
$a\Rightarrow$ $b\bigvee c$ . Now, if we set $a$ to be true then either $b$ or
$c$ can be true, i.e. there are two possibilities. Therefore for a $3$ \-
$SAT$ $CNF$ formula of size $n$ , there will be $2^{n}$ possibilities. In
general, for any $k$ \- $SAT$ problem, there will be $\left(k-1\right)^{n}$
possibilities (where $n$ is the number of disjunctive clauses in the $CNF$
formula).

Hence, we have proved Alice Bob problem to be NP complete. But, since for this
sequence of length $n$ , Bob’s program failed to yield the correct result (in
polynomial time), this implies that:

P!=NP

  3. 3)

Analysis of the P-NP result

With regard to the methodology adopted above, the one possible objection which
could be raised is that we assumed that for Bob to definitely lose the game,
it will have to be played for an arbitrarily long period of time. Yet, we set
a definite limit to the length of the string $n$ when he loses. We will
address this concern here. The use of Cantor’s diagonalization technique for
the proof alludes to a linkage with the cardinalities of natural and real
number spaces. The key insight here is that the outputs generated by Bob’s
algorithm have a one-to-one mapping to the natural number space while Alice is
able to pick her sequences from the real number space. Herein, lies the
fundamental chasm that all computer programs confront, which is unbridgeable.
Indeed any problem where the result set can be in the real number space can
never be solved in a deterministic manner by computers (which operate in
natural number space) simply because the cardinality of the former is much
larger than the cardinality of the latter. This again is not very hard to
intuitively understand. The very essence of an irrational number (which is a
part of the real number space) is that there is no pattern to the digits. As
such, it is impossible to predict it in a deterministic manner.

Now, the question may be asked as to what about the cases where the output
does not map to the real number space, but to the natural number space. To
simulate this situation, let us replace Alice and Bob with Computer A and
Computer B respectively. Now, both computers are constrained to operate in the
natural number space. However, the question here is if this by itself
fundamentally alters anything, the answer to which is negative. The constraint
imposed on Computer A is merely a result of its physical limitations (such as
memory and processing power), which can have arbitrary improvements with time.
As such, the range of numbers that they can generate is not purely rational,
but what we can term as $``$quasi-irrational$"$ 222 For replicating a truly
random sequences of numbers, we could assume the utilization of a device such
as a Geiger counter . What we mean by this is that an irrational number
abruptly truncated to a certain length due to size constraints does not make
it any more predictable. Hence, it will be the case that even though Computer
A will generate such quasi-irrational numbers, since they don’t fit any
pattern, it will be impossible for Computer B to guess them in a deterministic
manner. Since a determinate algorithm can never be designed to predict a
number that has inherently indeterminate characteristics, the P-NP result we
derived above would hold for this case as well.

The other intuition we would like to draw out here is the connection with
Gödel’s theorems. In fact, the precise logic we employed here can also be used
to prove Gödel’s theorems as demonstrated by Gusfield [2014]. It is proved
therein that there are valid functions which map to the real number space,
which can never be replicated by a computer operating in the rational333 We
will use the terms rational numbers space and natural numbers space
interchangeably as their cardinalities are equal  number space. Hence, such
functions are non-computable leading to the Gödel’s incompleteness result.
This is directly analogous to the Alice Bob example here. In other words, the
underlying basis of both problems is on account of the disparity in the
cardinalities of the two spaces (i.e. real and rational). We have already
demonstrated the causal connection of dual identities to the Gödel’s case.
Hence, is it then possible that there is also a connection between
computability, duality and the real and rational spaces? This is the question
that we will tackle in the subsequent sections. By doing so, we will be able
to explore all the nuances of P-NP problem fully (which will come together in
the final section of this paper).

  4. 4)

Zeno’s paradox

The dichotomy of rational and real numbers was best captured by Zeno, a Greek
philosopher who lived between 490-430 BC, approximately 20 years before
Socrates. He devised a set of paradoxes, which together rule out the
possibilities of space (and time) being either continuous or discrete. There
are several paradoxes he constructed (Salmon [1970]), but we pick one from
each category (i.e. continuous and discrete) for simplicity’s sake.

The so called $``$dichotomy paradox$"$ goes like this – suppose Homer wishes
to walk to the end of a path. Before he can get there, he must get halfway
there. Before he can get halfway there, he must get a quarter of the way
there. Before traveling a quarter, he must travel one-eighth; before an
eighth, one-sixteenth and so on. Since such divisions of intervals can be done
infinite times, it will therefore require infinite tasks for Homer to reach
his destination, which Zeno claims will be impossible for Homer to perform.
Zeno uses this as an example to refute the continuity of space and time.

On the other hand, he uses the so called $``$arrow paradox$"$ to refute the
discreteness of space and time. Herein, Zeno states that for motion to occur,
a moving object such as an arrow in flight must change the position which it
occupies. At any one instant of time, the arrow is where it is occupying a
portion of space equal to itself. It is neither moving to where it is, nor to
where it is not. It cannot move to where it is not, because no time elapses
for it to move there; it cannot move to where it is, because it is already
there. In other words, at every instant of time there is no motion occurring.
If everything is motionless at every instant, and time is entirely composed of
instants, then motion is impossible.

Zeno’s paradoxes have elicited responses from mathematicians and philosophers
alike. Since Zeno pre-dates the era of modern mathematics wherein concepts
such as summation of infinite series and calculus were completely unknown, one
could attempt to resolve this paradox strictly on mathematical terms by
summing up the infinite series of:

$\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\ldots$

which converges to 1. But, most philosophers have rejected such a strictly
mathematical resolution of the paradox as it fails to satisfactorily address
the basic issue of whether an infinite number of tasks, no matter how small
can be accomplished in a finite amount of time. There have been some such as
James [1948] and Whitehead [1948] who have questioned the very rationale
behind representing time as a continuum as each observation itself requires a
minimal length of time. Their arguments rely on the inadequacy of a continuous
space for describing temporal processes. However, others such as Grünbaum
[1968] have argued that strictly from a scientific standpoint, time is indeed
infinitely divisible. Despite this, the need to build a mathematical construct
to adequately address the paradoxes was undeniable resulting in an ongoing
effort towards the same. Vlastos [1967] and McLaughlin and Miller [1992] have
tried to build models based on mapping the full interval of space into finite
number of sub-intervals based on whether an observable event has actually
taken place in that particular interval. In this way, they circumvent the need
to break up an interval into infinitely many intervals. Lee [1965] on the
other hand, questions the very validity of Zeno’s methodology arguing that
successively halving any finite interval of space only yields rational numbers
and not irrational ones and therefore is unable to cover the entire continuity
of space.

It is perhaps fair to say that none of the approaches hitherto adopted have
satisfactorily addressed all the issues concerned. This is because neither
have any of them made their way into mainstream mathematics nor have they
engendered any active ongoing interest in the philosophical community to
continue to probe them. Our approach herein would be to get to the heart of
the matter from a theoretical standpoint and then build a mathematical
construct to address the same, which we will do in the succeeding sections.

  5. 5)

Mapping of real numbers

The shortcomings of our current understanding of real numbers both from
theoretical (Bell [2005], Ehrlich [2013]) as well as philosophical standpoints
(Snapper [1979], Ferreirós [2008]) are well documented. Indeed, it has
prompted some to call it the $``$most fundamental and important problem in
mathematics$"$ 444 Attributable to N J Wildberger who has a series of videos
posted on the internet where he also calls the current theory of real numbers
as a $``$logical sham$"$ . . At the heart of this issue is – how does one
actually define real numbers, and after having done that, what are the
arithmetic principles governing them. One of the popular methodologies for
doing so is based on the so called Dedekind cut (Dedekind [1963]), wherein the
number line is partitioned into two parts – A and B, such that all elements of
A are less than all elements of B, and A contains no greatest element. An
irrational number is defined by such a cut, wherein the number lies in neither
of the two partitions. As an example of a Dedekind cut representing an
irrational number, we may take the positive square root of 2. This can be
defined by the set A = $\\{x\in Q:x<0\vee x^{2}<2\\}$ . The idea here is that
any real number can be uniquely mapped using such sets of rational numbers
engendered from such partitions.

Another such methodology for defining irrational numbers is to think of them
as successive approximations of Cauchy sequences. E.g. – for $\pi$ =
3.14159$\ldots$ the Cauchy sequence would be:

3, 3.1, 3.14, 3.141, 3.1415, 3.14159, $\ldots$ .

But, the question which has probably not been asked till now, which we do so
here is – if such methods of defining an irrational number actually map it to
a point on the number line. And the answer to that as we prove in the theorem
below is - no.

Theorem. An irrational number cannot be represented as a point in the number
line.

Proof. We set the initial stage by first representing all rational numbers as
points in the number line. This is done by first mapping all the natural
numbers, followed by integers and finally fractions based on well-known set
theoretic methods. Since all of these numbers are well ordered, we can create
a well-defined ordered mapping of them on the number line. Using these
mappings of rational numbers, we then attempt to map the rest of the real
numbers, i.e. the irrational numbers. For this, we define an operation called
the $``$point locator operation$"$ $\Gamma$ , which helps map any real number
$x$ to a point on the number line. $\Gamma$ will operate as follows.

We begin by choosing any arbitrary rational number $\alpha_{1}$ , which maps
to a definite point on the number line. If $\alpha_{1}<x$ , we choose a point
which corresponds to a number $\alpha_{2}\ni\alpha_{1}<\alpha_{2}\leq x$ . If
$\alpha_{2}=x$ , $\Gamma$ has been successful in mapping x to a point on the
number line. Else, we repeat the process till the end goal is achieved.

On the other hand, if $\alpha_{1}>x$ , we choose a point which corresponds to
a number $\alpha_{2}\ni\alpha_{1}>\alpha_{2}\geq x$ . If $\alpha_{2}=x$ ,
$\Gamma$ has been successful in mapping x to a point on the number line. Else,
we similarly repeat the process till the end goal is achieved.

If $x$ is a rational number, it is trivial to prove that $\Gamma$ will be
immediately successful as it can just choose the point $\alpha_{2}$ that
precisely maps to $x$ itself.

Next, consider the case where $x$ is an irrational number and $\alpha_{1}<x$ .
Now, $\Gamma$ will choose a point which corresponds to a number
$\alpha_{2}\ni\alpha_{2}>\alpha_{1}\bigwedge\alpha_{2}\leq x$ . But, since we
haven’t mapped any irrational numbers yet,

$\Rightarrow\alpha_{2}$ is also not irrational

$\Rightarrow\alpha_{2}\neq x$ (as $x$ is irrational) $\Rightarrow\alpha_{2}<x$

Now, since there is always a rational number between any two numbers, we can
choose a point which corresponds to a number
$\alpha_{3}\ni\alpha_{3}>\alpha_{2}\bigwedge\alpha_{3}\leq x$

But for the same reason as before, $\alpha_{3}<x$ . Hence, it follows that
even if $\Gamma$ operation is performed repeatedly, it can never map to a
point that will exactly represent $x$ on the number line. The same logic will
hold true even if $\alpha_{1}>x$ .

Hence, since $\Gamma$ has failed to map even a single irrational number, it
follows that none of the irrational numbers can be represented as points in
the number line.

The intuition behind the above theorem must be quite obvious. It is just an
explicit way of stating that methods such as the Dedekind cut and Cauchy
sequence are merely limiting and not precise definitions of irrational
numbers. Nonetheless, this simple yet deep result has not been adequately
absorbed, represented and formalized in the prevailing mathematical setup. The
implication of this result is that we are left with contrasting requirements
for rational and irrational numbers – the former being discrete and
represented by points while the latter being continuous and represented by
regions in space. We will proceed to build a mathematical framework for
harmonising these requirements into a single space. But before that, we will
briefly deal with the topic of Continuum Hypothesis in the next section.

  6. 6)

The Continuum Hypothesis

A complete exposition on the Continuum Hypothesis (CH) is clearly out of scope
for this paper and hence we will not attempt to do it. But, we will touch upon
it here because it prepares a good ground for the mathematical framework that
we will describe in the next section. CH is one of the most important
unresolved problems in set theory. In 1874, Cantor had demonstrated the
difference in cardinalities of the real and rational number spaces (Cantor
[1874]). Cantor proved that while there is a one-to-one correspondence between
the rational numbers and the natural numbers, there is no one-to-one
correspondence between the real numbers and the natural numbers. He thus
concluded that the cardinality of the set of real numbers is larger than the
cardinality of the set of rational numbers. But, he soon went on to seek an
answer to the question of whether there were any other infinite sets of real
numbers that were of intermediate size (Cantor [1878]). In other words,
whether there was an infinite set of real numbers that could not be put into
one-to-one correspondence with the natural numbers and could also not be put
into one-to-one correspondence with the real numbers. The Continuum Hypothesis
is simply the statement that there is no such set of real numbers. Not only
was Cantor unable to resolve this question, but CH also remains an unsolved
problem till date. In fact, it is probably unique in that there are proofs to
demonstrate that it can neither be disproved (Gödel [1940]) nor proved (Cohen
[1963], Cohen [1964]).

For illustrating the possibility of such a space that has characteristics of
both continuous and discrete spaces, consider the following sequence:

0.111528111835111364111739111082111604111027$\ldots$ .

Do you notice anything here? On close inspection it can be seen that the
sequence $``$111$"$ occurs regularly with random three digits interspersed
between two such consecutive instances of 111’s. If this pattern were to
continue indefinitely, it is possible (indeed trivial) to predict the same
with 50$\%$ accuracy. Actually, an even better way of articulating that would
be to say that 50$\%$ of this space can be predicted with 100$\%$ accuracy
(and hence computable), while 50$\%$ can be predicted with 0$\%$ accuracy (and
hence non-computable). But the string as a whole is non-computable since it is
irrational555 These could be termed as $``$pseudo-irrational$"$ numbers as
they appear to be irrational, but on closer inspection, have some level of
predictability. In contrast, $``$quasi-irrational$"$ numbers appear to be
rational, but don’t have any predictability . The question can then be asked
if it is possible to treat such a sequence as a single combination of rational
and real spaces and if so, what is the mathematics underlying it. The answer
to that will be given in the next section.

  7. 7)

Defining the $``$Hybrid Space$"$

Let us begin by articulating the intuition behind the hybrid space, a proposed
symbolic representation of space catering to the dual requirements of real
numbers. Suppose $U$ represents the number line of natural numbers and $V$ is
a continuous space of positive real numbers, i.e. $V\subset$ $R^{+}$

Let us now define a mapping $f$ from each discrete element in $U$ to a
continuous interval in $V$

Hence, $f:u_{i}\rightarrow\left[v_{j},v_{k}\right]where$ $u_{i}\in
U;~{}\left[v_{j},v_{k}\right]\in V$

Our goal with the mapping function is to faithfully map $U$ to $V$ . However,
since $V$ is a continuous space, elements from $U$ can only be mapped to small
intervals and not directly to points in $V.$ Hence, this mapping function $f$
denotes the error in mapping elements from $U$ to $V$ .Greater the interval of
the mapping function, larger will be the error in mapping points onto $V$

Let us now define $++$ as the increment operator in $U$ , which will move any
element in $U$ to the next element there. This will correspondingly move the
mapping in $V$ to the next interval there. In other words, if $u_{i}$ moves to
$u_{t}$ then [ $v_{j},v_{k}$ ] will move to [ $v_{l},v_{m}$ ].

Let us define $u_{t}-u_{i}$ as the $``$virtual distance$"$ and $v_{m}-v_{k}$
as the $``$actual distance$"$

Hence, if we want to map the virtual distance in $U$ to the actual distance in
$V$ , the error will depend on the mapping function $f$ . We will use this
intuition while defining the hybrid space $H$

Now, a hybrid space $H$ is one which has both discrete and continuous elements
in the same space. Hence, unlike the above example where the virtual distance
in $U$ was mapped to the actual distance in $V$ ; in $H$ , both of them will
be mapped to the same space. In this case, let us define the mapping function,
$\mu_{ij}$ in the following manner:

$\mu_{ij}:\left(i,j\right)\rightarrow x_{ij}$ , where $x_{ij},i,j\in H$

Notice here that $x_{ij}$ represents a continuous interval, while $i,j$
represent discrete elements. The intuition here is that through the mapping
function, we are trying to infuse a semantic context of distance to two
disparate points (which lack this semantic context). As such, $x_{ij}$ denotes
the actual distance, while the ordered pair $\left(i,j\right)$ denotes the
virtual distance.

We now need to define how the addition operator will work in this space. The
addition operation should indicate what the actual distance covered will be
for any two pairs of discrete points that are $``$added$"$ to each other. For
this, assume two ordered pairs $\left(i,j\right)$ and $\left(k,l\right)$ which
map to adjacent intervals $x_{ij}$ and $x_{kl}$ . The addition operation is
now defined as follows:

$x_{ij}$ \+ $x_{kl}=\left(j-i\right)+\left(l-k\right)$

Now, if $k=j$ it implies that the mapping from the virtual to actual distances
is perfect without any errors (because $x_{ij}$ and $x_{kl}$ are meant to be
adjacent intervals).

Hence, in such a case,

$x_{ij}$ \+ $x_{kl}=l-i$

i.e. the actual distance is just the difference of the two discrete numbers
(i.e. the higher of the second pair minus the lower of the first pair)

Else, if $k>j,$ we will define a term called convexity $``$ $\complement"$ ,
which will capture the accuracy of mapping as follows:

$\complement=\frac{\left(l-i\right)}{\left(k-j\right)}$

Note that $\complement\in Q,$ and $\complement>1$

The virtual distance is given by $\left(l-i\right)$ whereas the actual
distance is given by $\left(j-i\right)+\left(l-k\right)$

$\therefore$ Actual Distance = Virtual Distance $\left(1-\frac{1}{C}\right)$

Hence, if convexity $\complement$ is $\infty,\Rightarrow$ we have been able to
map the discrete space to continuous space with absolute accuracy. This also
resolves the Zeno’s paradox kind of situations as follows. If the space
concerned is completely determinate, then Homer does not need to subdivide the
space into further subsections to cover the distance. He can travel right
through it from start point to end point because the actual distance is
defined as just the difference between the end and start points. On the other
hand, if $\complement$ $\neq\infty,$ then there will be an error that Homer
will have to live with, which cannot be avoided no matter how he divides the
distance.

Let us now illustrate these workings for the example of the sequence
considered in the earlier section, i.e.

0.111528111835111364111739111082111604111027$\ldots$ .

Herein, two adjacent intervals will be of the form [111xxx], [111xxx]. When
represented visually it can be depicted as follows:

0 3 12 9 xxx 111 xxx 111

The convexity of the above space will be

$=\frac{\left(12-0\right)}{\left(9-3\right)}=2~{}$

However, the advantage of representing the sequence in such a hybrid space is
that a function whose range is in such a space is now computable. That is
because the sequence of adjacent intervals of the form [111xxx] can be mapped
to the natural number space whereas in its original form, the sequence was an
irrational number and hence non-computable666 However, what we gain by
computability, we compromise in accuracy .

We will also now highlight the significance of the convexity term
$\complement$ . For this, consider another similar sequence to the one above
but in this case, the intervals are of the form [111111xxx] (i.e. for every
six 1’s there are three random digits). The convexity of such a space will be
3. Now, if we were to represent both these irrational numbers only in terms of
regions of space, they could be done so as [0.11,0.12]. In other words, both
of them can be represented by a space with lower bound 0.11 and upper bound
0.12. In doing so, one would have believed that they are both subject to the
same level of uncertainty in mapping. However, as we have demonstrated, this
fails to capture all the information we have about these two numbers (i.e.
their convexities). Hence, a complete representation of an irrational number
$x$ will be of the form:

$x\mapsto\left[x_{i},x_{j},\complement\right],$ where $x_{i}$ is the lower
bound, $x_{j}$ is the upper bound and $\complement$ is the convexity.

Finally, we can also visualize a continuous space where different intervals
have different convexities as follows:

X7 X6 X5 X4 X3 X2 X1 C7 C6 C5 C4 C3 C2 C1

(where C1, C2, C3 etc. are the convexities of the virtual intervals x1, x2, x3
etc.)

In such a case, the distance travelled will need to be computed as follows:

If the actual distance of each interval is a constant, it follows that:

$x_{1}\left(1-\frac{1}{C_{1}}\right)=x_{2}\left(1-\frac{1}{C_{2}}\right)=x_{3}\left(1-\frac{1}{C_{3}}\right)\ldots$

From the above, we can deduce that the total actual distance travelled in such
a scenario will be:

=
$x_{1}\left[\frac{\left(1-\frac{1}{C_{1}}\right)}{\left(1-\frac{1}{C_{2}}\right)}+\frac{\left(1-\frac{1}{C_{1}}\right)}{\left(1-\frac{1}{C_{3}}\right)}+\frac{\left(1-\frac{1}{C_{1}}\right)}{\left(1-\frac{1}{C_{4}}\right)}+\ldots\frac{\left(1-\frac{1}{C_{1}}\right)}{\left(1-\frac{1}{C_{n}}\right)}~{}\right]$

= $x_{1}\left[\frac{C_{1}-1}{C_{1}}\right]\sum_{2}^{n}\frac{C_{i}}{C_{i}-1}$

From our previous discussions in Section $2$ , it will also be evident that
for the 2-SAT problem, the convexity of solution space will be $\infty$ ,
while for the 3-SAT problem, it will be 3. This is so because it can be
represented in the form [11x][11x]$\ldots$ (as the introduction of the third
literal in a clause causes the indeterminateness).

  8. 8)

Philosophical implications of hybrid space

We begin by stating the obvious, i.e.- that a number is meant to aid two kinds
of activities – counting and measurement. These correspond to its existence in
the discrete and continuous spaces respectively. We know that in a discrete
space, a number gets defined entirely by recursively executing a certain
incremental rule as we do in a formal system like Peano arithmetic. So, we fix
the origin 0 axiomatically and then define addition as a recursive function
$F$ which maps two numbers to another one as follows:

$a+0=a$ , (1)

$a+F\left(b\right)=F\left(a+b\right)$ (2)

In this way, the entire discrete space gets defined in the form of incremental
steps of the recursive operation. Hence, there is no concept of a distance,
but just a count of the number of operations that need to be performed to
arrive at a number from the origin. Hitherto, such a discrete space has been
treated as completely different from a continuous space, which is
understandable since addition in the discrete space leads to an increase in
plurality, i.e. 2 apples added to 3 apples give 5 distinct apples. In
contrast, addition in continuous space leads to a decrease in plurality.
Adding length 2 to length 3 gives a single length 5. But, on the other hand,
it is also the case that numbers cannot be defined in a mutually exclusively
manner either in the discrete or continuous spaces. That is because for
measuring length, we need a start point and end point in discrete space.
Similarly, for defining a point in discrete space, we need to define how much
distance is covered in each incremental operation. Hence, we need to define a
single symbol which will satisfy both conditions. In other words, the number
$``$5$"$ should stand for both 5 operations from the origin and also distance
5 from the origin.

But, as we demonstrated in the point mapping theorem, irrational numbers
cannot be defined as discrete points and need to be represented by regions in
space. As such, it is possible to view the concept of a number from the dual
identity paradigm we have outlined earlier wherein, the states of a number can
be defined as follows:

     * •

State of Doing: Separates two points by a certain distance

     * •

State of Being: Is a point which is a certain number of hops from the origin
(as defined by a recursive increment function)

It merits mention here that when the underlying principles of quantum
mechanics were first discovered, the notions of quantization and uncertainty
associated with the physical world appeared completely counterintuitive.
However, from our exposition here, such concerns should be completely laid to
rest as these are not just constraints of the physical world, but a logical
requirement of the very construct of space.

  9. 9)

Conclusion

Let us tie in all the various points discussed so far. A semantic
understanding of Gödel’s theorems based on the duality of identity states of
formal systems was developed. However, that is just a part of the whole
picture. To complete the understanding, this needs to be related to the
dichotomy between real and rational number spaces. That will help us answer
the question of why contradictions like Gödel’s incompleteness or Russell’s
paradox can’t be avoided through some meta-level exclusion. It is not possible
to do so for the following reasons:

a) All such cases involve definitions in first order logic, which are based on
negation, e.g. - $``$A formal system which cannot prove [certain
propositions$\ldots$ ]$"$ in the theorems of Gödel, or $"$ A barber who does
not shave [a certain class of people$\ldots$ ]$"$ in the paradox of Russell
etc.

b) Since the formal systems themselves are defined in rational number space, a
negation of the same would map to the real number space (as the complement of
rational number space is the irrational numbers space, which will be included
in any negation)

Hence, we cannot by any means exclude all possibilities of a negative
definition through another meta-level definition (as the meta-level definition
itself can only be constructed in the rational number space). In other words,
since definitions map to the rational number space and negations map to the
real number space, a negation can always be constructed, which cannot be
annulled by another definition (either at first order or at higher orders).
This is exactly the logic that is exploited in all diagonalization techniques
a-la Cantor’s. Hence, such circularities based on negative definitions can
never be broken.

This is where the demonstrated connection between the P-NP problem and the
cardinalities of real and rational number spaces also assumes importance. The
important point to note is that to solve the P-NP problem, we need to
demonstrate that any polynomial time algorithm cannot solve an NP complete
problem. In other words, it is again a problem based on negation, alluding to
a connection with the real number space. This explains the reliance on the
diagonalization technique, which we employed to arrive at the proof. On the
other hand, for reasons just explained earlier, an algorithm for identifying
exclusions itself will be an NP problem as there will not be a deterministic
way of solving it (apart from actually searching for solutions in the real
number space). Hence, non-computability and NP are two facets of the same
problem with a common connection to the real number space. To state in simple
language - a problem becomes non-computable when the solution lies in the real
number space, in which case the only way to solve it is to search for the
solution through all possible alternatives.

But, as the point location theorem demonstrates, the representation of
irrational numbers as points in space is a flawed one. As such, we conclude
that the root cause of most unsolved problems in formal logic is a gap in the
semantic understanding of the very concept of numbers. Specifically, this
refers to the creation of two distinct definitions for rational and real
numbers (i.e. discrete and continuous spaces) disjoint from each other. Hence,
to address this, we have attempted to create a unified framework of numbers
based on both rational and irrational numbers being mapped to a single space
called the $``$hybrid space$"$ . In this notion of hybrid space, both discrete
and continuous elements get defined by a single parameter (called convexity)
based on the degree of determinateness of that element. It is our belief that
if the laws of the physical world are conceptualized on the basis of this
space, many of the outstanding problems in theoretical physics also could get
resolved. That will be the focus of our work going forward.

REFERENCES

Bell, John Lane (2005), $``$The continuous and the infinitesimal in
mathematics and philosophy$"$ , Polimetrica sas

Berto, Francesco (2011), There’s Something About Gödel: The Complete Guide to
the Incompleteness Theorem, John Wiley $\&$ Sons

Cantor, Georg (1874), $``$Über eine Eigenschaft des Inbegriffes aller reellen
algebraischen Zahlen$"$ , Crelles Journal für reine und angewandte Mathematik
77: 258 – 262

Cantor, Georg (1878), $``$Ein Beitrag zurMannigfaltigkeitslehre$"$ , Journal
für reine und angewandte Mathematik 84: 242–258

Coffa, J. Alberto (1979), $``$The Humble Origins of Russell’s Paradox$"$ ,
Russell Nos. 33–34

Cohen, Paul (1963), "The Independence of the Continuum Hypothesis", Proc. Nat.
Acad. Sci. U. S. A. 50: 1143-1148

Cohen, Paul (1964), "The Independence of the Continuum Hypothesis II", Proc.
Nat. Acad. Sci. U. S. A. 51: 105-110

Cook, Stephen (1971), "The complexity of theorem proving procedures",
Proceedings of the Third Annual ACM Symposium on Theory of Computing: 151–158

Dedekind, Richard (1963), $``$Continuity and Irrational Numbers$"$ , Essays on
the Theory of Numbers, New York: Dover

Detlefsen, Michael (1979), $``$On interpreting Gödel’s Second Theorem$"$ ,
Journal of Philosophical Logic 8: 297–313

Ehrlich, Philip (2013), ed. $``$Real numbers, generalizations of the reals,
and theories of continua Vol. 242$"$ , Springer Science $\&$ Business Media

Ferreirós, José (2008), "The crisis in the foundations of mathematics", The
Princeton companion to mathematics: 142-156

Gödel, Kurt (1931), $``$On Formally Undecidable Propositions of Principia
Mathematica and Related Systems$"$ , Translation of the German original
Courier Corporation

Gödel, Kurt (1940), $``$The Consistency of the Continuum-Hypothesis$"$ ,
Princeton University Press

Gusfield, Dan (2014), $``$Gödel for Goldilocks: A Rigorous, Streamlined Proof
of (a variant of) Gödel’s First Incompleteness Theorem$"$ , arXiv:1409.5944

Grünbaum, Adolf (1968), $``$Modern Science and Zeno’s Paradoxes$"$ , George
Allen and Unwin Ltd, London

Hartmanis, Juris (1989), "Gödel, von Neumann, and the P = NP problem",
Bulletin of the European Association for Theoretical Computer Science 38:
101–107

James, William (1948), Some Problems of Philosophy, Longmans, Green $\&$
Co.,Ltd., London

Kennedy, Juliette (ed.) (2014), Interpreting Gödel: Critical essays, Cambridge
University Press

Lee, Harold (1965), "Are Zeno’s Paradoxes Based on a Mistake?", Mind, New
Series 74, no. 296: 563 – 570

McLaughlin, William and Miller, Sylvia (1992), $``$An Epistemological Use of
Nonstandard Analysis to Answer Zeno’s Objections Against Motion$"$ , Synthese
92: 371-384

Salmon, Wesley (ed.) (1970), $"$ Zeno’s Paradoxes$"$ , Bobbs-Merrill: 200—250

Smith, Peter (2007), An Introduction to Gödel’s Theorems, Cambridge University
Press

Snapper, Ernst (1979), "The three crises in mathematics: Logicism,
intuitionism and formalism", Mathematics Magazine 52.4: 207-216

Vlastos, Gregory (1967), $``$Zeno of Elea$"$ , in Edwards, Paul (ed.), The
Encyclopedia of Philosophy, Macmillan, New York, Vol. 8: 369–79

Whitehead, Alfred North (1948), $``$Process and Reality$"$ , Macmillan, New
York