
'''simple docstring'''


from typing import SupportsIndex

import numpy as np
from scipy.ndimage import convolve
def 				__magic_name__(					UpperCAmelCase__   :					np.ndarray       ,							UpperCAmelCase__   :					np.ndarray       ,							UpperCAmelCase__   :					np.ndarray  ):
						UpperCamelCase_    :  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
						UpperCamelCase_    :  Tuple				    =    np.stack(
						    np.meshgrid(np.arange(0       ,							image.shape[1]  )       ,							np.arange(0       ,							image.shape[0]  )  )       ,							2  )
						UpperCamelCase_    :  List[Any]				    =    np.round(grid - flow  ).astype(np.intaa  )

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

						UpperCamelCase_    :  int				    =    image[grid[:, :, 1], grid[:, :, 0]]

						# Set pixels at invalid locations to 0
						UpperCamelCase_    :  int				    =    0

						return warped
def 				__magic_name__(					UpperCAmelCase__   :					np.ndarray       ,							UpperCAmelCase__   :					np.ndarray       ,							UpperCAmelCase__   :					SupportsIndex       ,							UpperCAmelCase__   :					float | None = None       ,							):
						if alpha is None:
												UpperCamelCase_    :  Optional[int]				    =    0.1

						# Initialize flow
						UpperCamelCase_    :  List[Any]				    =    np.zeros_like(UpperCAmelCase__  )
						UpperCamelCase_    :  Optional[Any]				    =    np.zeros_like(UpperCAmelCase__  )

						# Prepare kernels for the calculation of the derivatives and the average velocity
						UpperCamelCase_    :  Union[str, Any]				    =    np.array([[-1, 1], [-1, 1]]  ) * 0.25
						UpperCamelCase_    :  Tuple				    =    np.array([[-1, -1], [1, 1]]  ) * 0.25
						UpperCamelCase_    :  int				    =    np.array([[1, 1], [1, 1]]  ) * 0.25
						UpperCamelCase_    :  int				    =    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(UpperCAmelCase__  ):
												UpperCamelCase_    :  List[str]				    =    warp(UpperCAmelCase__       ,							UpperCAmelCase__       ,							UpperCAmelCase__  )
												UpperCamelCase_    :  Dict				    =    convolve(UpperCAmelCase__       ,							UpperCAmelCase__  ) + convolve(UpperCAmelCase__       ,							UpperCAmelCase__  )
												UpperCamelCase_    :  Any				    =    convolve(UpperCAmelCase__       ,							UpperCAmelCase__  ) + convolve(UpperCAmelCase__       ,							UpperCAmelCase__  )
												UpperCamelCase_    :  Dict				    =    convolve(UpperCAmelCase__       ,							UpperCAmelCase__  ) + convolve(UpperCAmelCase__       ,							-kernel_t  )

												UpperCamelCase_    :  Any				    =    convolve(UpperCAmelCase__       ,							UpperCAmelCase__  )
												UpperCamelCase_    :  Dict				    =    convolve(UpperCAmelCase__       ,							UpperCAmelCase__  )

												# This updates the flow as proposed in the paper (Step 12)
												UpperCamelCase_    :  Dict				    =    (
												    derivative_x * avg_horizontal_velocity
												    + derivative_y * avg_vertical_velocity
												    + derivative_t
												)
												UpperCamelCase_    :  List[str]				    =    update / (alpha**2 + derivative_x**2 + derivative_y**2)

												UpperCamelCase_    :  List[Any]				    =    avg_horizontal_velocity - derivative_x * update
												UpperCamelCase_    :  Dict				    =    avg_vertical_velocity - derivative_y * update

						return horizontal_flow, vertical_flow


if __name__ == "__main__":
	import doctest

	doctest.testmod()






'''simple docstring'''


from __future__ import annotations

from typing import Any




class 						__snake_case :




		def __init__(     self				:int ,						_SCREAMING_SNAKE_CASE				:Any ,						_SCREAMING_SNAKE_CASE				:Any)				-> None:  # noqa: A002






								'''simple docstring'''






								UpperCamelCase_    :  Optional[Any]				    =    item
								UpperCamelCase_    :  int				    =    next







class 						__snake_case :




		def __init__(     self				:Optional[Any])				-> None:






								'''simple docstring'''






								UpperCamelCase_    :  Node | None				    =    None
								UpperCamelCase_    :  Tuple				    =    0




		def   _snake_case  (     self				:List[Any] ,						_SCREAMING_SNAKE_CASE				:Any)				-> None:






								'''simple docstring'''






								UpperCamelCase_    :  List[Any]				    =    Node(_SCREAMING_SNAKE_CASE ,						self.head)
								self.size += 1




		def   _snake_case  (     self				:int)				-> Any:






								'''simple docstring'''






								if self.head is None:
														return None
								else:
														UpperCamelCase_    :  Any				    =    self.head.item
														UpperCamelCase_    :  List[str]				    =    self.head.next
														self.size -= 1
														return item




		def   _snake_case  (     self				:int)				-> bool:






								'''simple docstring'''






								return self.head is None




		def __str__(     self				:Any)				-> str:






								'''simple docstring'''






								if self.is_empty():
														return ""
								else:
														UpperCamelCase_    :  List[str]				    =    self.head
														UpperCamelCase_    :  Tuple				    =    """"""
														UpperCamelCase_    :  list[str]				    =    []
														while iterate:
																				item_list.append(str(iterate.item))
																				UpperCamelCase_    :  Tuple				    =    iterate.next

														UpperCamelCase_    :  Optional[int]				    =    """ --> """.join(_SCREAMING_SNAKE_CASE)

														return item_str





		def __len__(     self				:List[Any])				-> int:






								'''simple docstring'''






								return self.size




