






import numpy as np



def        _lowerCamelCase(      lowerCAmelCase__					:		List[Any]     ,     lowerCAmelCase__					:		Dict="utf-8"     ,     lowerCAmelCase__					:		List[str]="surrogatepass"   ):





				'''simple docstring'''







				SCREAMING_SNAKE_CASE_ :						List[Any]    				= bin(int.from_bytes(text.encode(lowerCAmelCase__     ,     lowerCAmelCase__   )     ,     'big'   )   )[2:]
				return bits.zfill(8 * ((len(lowerCAmelCase__   ) + 7) // 8)   )



def        _lowerCamelCase(      lowerCAmelCase__					:		int     ,     lowerCAmelCase__					:		Dict="utf-8"     ,     lowerCAmelCase__					:		Optional[Any]="surrogatepass"   ):





				'''simple docstring'''







				SCREAMING_SNAKE_CASE_ :						Any    				= int(lowerCAmelCase__     ,     2   )
				return n.to_bytes((n.bit_length() + 7) // 8     ,     'big'   ).decode(lowerCAmelCase__     ,     lowerCAmelCase__   ) or "\0"



def        _lowerCamelCase(      lowerCAmelCase__					:		str     ,     lowerCAmelCase__					:		Union[str, Any]   ):





				'''simple docstring'''







				if size_par + len(lowerCAmelCase__   ) <= 2**size_par - (len(lowerCAmelCase__   ) - 1):
								raise ValueError('size of parity don\'t match with size of data'   )

				SCREAMING_SNAKE_CASE_ :						Tuple    				= []
				SCREAMING_SNAKE_CASE_ :						Dict    				= []
				SCREAMING_SNAKE_CASE_ :						Union[str, Any]    				= [bin(lowerCAmelCase__   )[2:] for x in range(1     ,     size_par + len(lowerCAmelCase__   ) + 1   )]

				# sorted information data for the size of the output data
				SCREAMING_SNAKE_CASE_ :						Any    				= []
				# data position template + parity
				SCREAMING_SNAKE_CASE_ :						Optional[Any]    				= []
				# parity bit counter
				SCREAMING_SNAKE_CASE_ :						Any    				= 0
				# counter position of data bits
				SCREAMING_SNAKE_CASE_ :						List[Any]    				= 0

				for x in range(1     ,     size_par + len(lowerCAmelCase__   ) + 1   ):
								# Performs a template of bit positions - who should be given,
								# and who should be parity
								if qtd_bp < size_par:
												if (np.log(lowerCAmelCase__   ) / np.log(2   )).is_integer():
																data_out_gab.append('P'   )
																SCREAMING_SNAKE_CASE_ :						int    				= qtd_bp + 1
												else:
																data_out_gab.append('D'   )
								else:
												data_out_gab.append('D'   )

								# Sorts the data to the new output size
								if data_out_gab[-1] == "D":
												data_ord.append(data[cont_data]   )
												cont_data += 1
								else:
												data_ord.append(lowerCAmelCase__   )

    # Calculates parity
				SCREAMING_SNAKE_CASE_ :						Union[str, Any]    				= 0  # parity bit counter
				for bp in range(1     ,     size_par + 1   ):
								# Bit counter one for a given parity
								SCREAMING_SNAKE_CASE_ :						Union[str, Any]    				= 0
								# counter to control the loop reading
								SCREAMING_SNAKE_CASE_ :						int    				= 0
								for x in data_ord:
												if x is not None:
																try:
																				SCREAMING_SNAKE_CASE_ :						List[Any]    				= (bin_pos[cont_loop])[-1 * (bp)]
																except IndexError:
																				SCREAMING_SNAKE_CASE_ :						Optional[int]    				= '0'
																if aux == "1" and x == "1":
																				cont_bo += 1
												cont_loop += 1
								parity.append(cont_bo % 2   )

								qtd_bp += 1

				# Mount the message
				SCREAMING_SNAKE_CASE_ :						List[Any]    				= 0  # parity bit counter
				for x in range(0     ,     size_par + len(lowerCAmelCase__   )   ):
								if data_ord[x] is None:
												data_out.append(str(parity[cont_bp]   )   )
												cont_bp += 1
								else:
												data_out.append(data_ord[x]   )

				return data_out



def        _lowerCamelCase(      lowerCAmelCase__					:		Tuple     ,     lowerCAmelCase__					:		Any   ):





				'''simple docstring'''







				SCREAMING_SNAKE_CASE_ :						Optional[Any]    				= []
				# Parity bit counter
				SCREAMING_SNAKE_CASE_ :						Dict    				= 0
				# Counter p data bit reading
				SCREAMING_SNAKE_CASE_ :						Dict    				= 0
				# list of parity received
				SCREAMING_SNAKE_CASE_ :						str    				= []
				SCREAMING_SNAKE_CASE_ :						Optional[Any]    				= []

				for x in range(1     ,     len(lowerCAmelCase__   ) + 1   ):
								# Performs a template of bit positions - who should be given,
								#  and who should be parity
								if qtd_bp < size_par and (np.log(lowerCAmelCase__   ) / np.log(2   )).is_integer():
												data_out_gab.append('P'   )
												SCREAMING_SNAKE_CASE_ :						Optional[int]    				= qtd_bp + 1
								else:
												data_out_gab.append('D'   )

								# Sorts the data to the new output size
								if data_out_gab[-1] == "D":
												data_output.append(data[cont_data]   )
								else:
												parity_received.append(data[cont_data]   )
								cont_data += 1

				# -----------calculates the parity with the data
				SCREAMING_SNAKE_CASE_ :						Dict    				= []
				SCREAMING_SNAKE_CASE_ :						int    				= []
				SCREAMING_SNAKE_CASE_ :						Union[str, Any]    				= [bin(lowerCAmelCase__   )[2:] for x in range(1     ,     size_par + len(lowerCAmelCase__   ) + 1   )]

				#  sorted information data for the size of the output data
				SCREAMING_SNAKE_CASE_ :						List[Any]    				= []
				# Data position feedback + parity
				SCREAMING_SNAKE_CASE_ :						int    				= []
				# Parity bit counter
				SCREAMING_SNAKE_CASE_ :						Union[str, Any]    				= 0
				# Counter p data bit reading
				SCREAMING_SNAKE_CASE_ :						Dict    				= 0

				for x in range(1     ,     size_par + len(lowerCAmelCase__   ) + 1   ):
								# Performs a template position of bits - who should be given,
								# and who should be parity
								if qtd_bp < size_par and (np.log(lowerCAmelCase__   ) / np.log(2   )).is_integer():
												data_out_gab.append('P'   )
												SCREAMING_SNAKE_CASE_ :						List[Any]    				= qtd_bp + 1
								else:
												data_out_gab.append('D'   )

								# Sorts the data to the new output size
								if data_out_gab[-1] == "D":
												data_ord.append(data_output[cont_data]   )
												cont_data += 1
								else:
												data_ord.append(lowerCAmelCase__   )

    # Calculates parity
				SCREAMING_SNAKE_CASE_ :						Tuple    				= 0  # parity bit counter
				for bp in range(1     ,     size_par + 1   ):
								# Bit counter one for a certain parity
								SCREAMING_SNAKE_CASE_ :						Dict    				= 0
								# Counter to control loop reading
								SCREAMING_SNAKE_CASE_ :						str    				= 0
								for x in data_ord:
												if x is not None:
																try:
																				SCREAMING_SNAKE_CASE_ :						int    				= (bin_pos[cont_loop])[-1 * (bp)]
																except IndexError:
																				SCREAMING_SNAKE_CASE_ :						int    				= '0'
																if aux == "1" and x == "1":
																				cont_bo += 1
												cont_loop += 1
								parity.append(str(cont_bo % 2   )   )

								qtd_bp += 1

				# Mount the message
				SCREAMING_SNAKE_CASE_ :						List[Any]    				= 0  # Parity bit counter
				for x in range(0     ,     size_par + len(lowerCAmelCase__   )   ):
								if data_ord[x] is None:
												data_out.append(str(parity[cont_bp]   )   )
												cont_bp += 1
								else:
												data_out.append(data_ord[x]   )

				SCREAMING_SNAKE_CASE_ :						Optional[int]    				= parity_received == parity
				return data_output, ack







from typing import SupportsIndex

import numpy as np
from scipy.ndimage import convolve



def        _lowerCamelCase(      lowerCAmelCase__					:		np.ndarray     ,     lowerCAmelCase__					:		np.ndarray     ,     lowerCAmelCase__					:		np.ndarray   ):





				'''simple docstring'''







				SCREAMING_SNAKE_CASE_ :						List[Any]    				= np.stack((horizontal_flow, vertical_flow)     ,     2   )

				# Create a grid of all pixel coordinates and subtract the flow to get the
				# target pixels coordinates
				SCREAMING_SNAKE_CASE_ :						List[Any]    				= np.stack(
				    np.meshgrid(np.arange(0     ,     image.shape[1]   )     ,     np.arange(0     ,     image.shape[0]   )   )     ,     2   )
				SCREAMING_SNAKE_CASE_ :						List[str]    				= np.round(grid - flow   ).astype(np.intaa   )

				# Find the locations outside of the original image
				SCREAMING_SNAKE_CASE_ :						str    				= (grid < 0) | (grid >= np.array([image.shape[1], image.shape[0]]   ))
				SCREAMING_SNAKE_CASE_ :						Dict    				= 0

				SCREAMING_SNAKE_CASE_ :						Optional[Any]    				= image[grid[:, :, 1], grid[:, :, 0]]

				# Set pixels at invalid locations to 0
				SCREAMING_SNAKE_CASE_ :						Optional[int]    				= 0

				return warped



def        _lowerCamelCase(      lowerCAmelCase__					:		np.ndarray     ,     lowerCAmelCase__					:		np.ndarray     ,     lowerCAmelCase__					:		SupportsIndex     ,     lowerCAmelCase__					:		float | None = None     ,     ):





				'''simple docstring'''







				if alpha is None:
								SCREAMING_SNAKE_CASE_ :						Any    				= 0.1

				# Initialize flow
				SCREAMING_SNAKE_CASE_ :						List[Any]    				= np.zeros_like(lowerCAmelCase__   )
				SCREAMING_SNAKE_CASE_ :						Any    				= np.zeros_like(lowerCAmelCase__   )

				# Prepare kernels for the calculation of the derivatives and the average velocity
				SCREAMING_SNAKE_CASE_ :						Optional[int]    				= np.array([[-1, 1], [-1, 1]]   ) * 0.25
				SCREAMING_SNAKE_CASE_ :						Tuple    				= np.array([[-1, -1], [1, 1]]   ) * 0.25
				SCREAMING_SNAKE_CASE_ :						Optional[int]    				= np.array([[1, 1], [1, 1]]   ) * 0.25
				SCREAMING_SNAKE_CASE_ :						Tuple    				= np.array(
				    [[1 / 12, 1 / 6, 1 / 12], [1 / 6, 0, 1 / 6], [1 / 12, 1 / 6, 1 / 12]]   )

				# Iteratively refine the flow
				for _ in range(lowerCAmelCase__   ):
								SCREAMING_SNAKE_CASE_ :						Union[str, Any]    				= warp(lowerCAmelCase__     ,     lowerCAmelCase__     ,     lowerCAmelCase__   )
								SCREAMING_SNAKE_CASE_ :						Any    				= convolve(lowerCAmelCase__     ,     lowerCAmelCase__   ) + convolve(lowerCAmelCase__     ,     lowerCAmelCase__   )
								SCREAMING_SNAKE_CASE_ :						Optional[int]    				= convolve(lowerCAmelCase__     ,     lowerCAmelCase__   ) + convolve(lowerCAmelCase__     ,     lowerCAmelCase__   )
								SCREAMING_SNAKE_CASE_ :						Optional[int]    				= convolve(lowerCAmelCase__     ,     lowerCAmelCase__   ) + convolve(lowerCAmelCase__     ,     -kernel_t   )

								SCREAMING_SNAKE_CASE_ :						List[str]    				= convolve(lowerCAmelCase__     ,     lowerCAmelCase__   )
								SCREAMING_SNAKE_CASE_ :						Optional[Any]    				= convolve(lowerCAmelCase__     ,     lowerCAmelCase__   )

								# This updates the flow as proposed in the paper (Step 12)
								SCREAMING_SNAKE_CASE_ :						Tuple    				= (
								    derivative_x * avg_horizontal_velocity
								    + derivative_y * avg_vertical_velocity
								    + derivative_t
								)
								SCREAMING_SNAKE_CASE_ :						Optional[int]    				= update / (alpha**2 + derivative_x**2 + derivative_y**2)

								SCREAMING_SNAKE_CASE_ :						List[str]    				= avg_horizontal_velocity - derivative_x * update
								SCREAMING_SNAKE_CASE_ :						Optional[int]    				= avg_vertical_velocity - derivative_y * update

				return horizontal_flow, vertical_flow


if __name__ == "__main__":
				import doctest

				doctest.testmod()