Computation scheduling and allocation for visual communication is described. In one aspect, multiple frames of video data are encoded by allocating for at least a subset of inter-coded frames, on frame-by-frame basis, computational resources to encode the inter-coded frame. To this end, a computational budget to encode a current inter-coded frame is estimated. The estimate is based on the actual computational costs to encode a previous inter-coded frame of video data. Next, sets of operations associated with encoding the current inter-coded frame are analyzed to determine computational resources to implement the operations. If the computational resources exceed the computational budget, complexity of the operations is reduced until the associated computational resources are less than or equal to the computational budget. At this point, the current inter-coded frame is encoded using the operations and the computational budget. This process is repeated for the remaining inter-coded frames of video data.