EP-4738253-A1 - HIERARCHICAL MAP RELAXATION FOR INSIDE-OUT LOCATION TRACKING AND MAPPING SYSTEM

EP4738253A1EP 4738253 A1EP4738253 A1EP 4738253A1EP-4738253-A1

Abstract

Techniques for hierarchical map relaxation by an inside-out location tracking system may include generating a pair of image patches comprising PxP patches of corresponding coordinates of a source image and a target image, evaluating the pair of image patches using hierarchical image pyramids, wherein an image in its original resolution is provided at a base level and is downsampled at each level above the base level. Hierarchical map relaxation may include iteratively estimating an error vector between the pair of image patches, finding a local map update vector for minimizing the error vector, expanding the local map update vector into a level below, evaluating the local map update by performing a greedy evaluation at each successive level until the base level, wherein the local map update from above is evaluated, and a final greedy evaluation is performed using another estimated error vector.

Inventors

LONG II, JOHN DAVIS

Assignees

Qwake Technologies, Inc.

Dates

Publication Date: 20260506
Application Date: 20251007

Claims (20)

A method for hierarchical map relaxation by an inside-out location tracking system, the method comprising: receiving as input a bijective mapping of a source image to a target image, the bijective mapping comprising a first hierarchical image pyramid for the source image and a second hierarchical image pyramid for the target image, each of the first and the second hierarchical image pyramids comprising a base level L=0 and N levels above the base level; generating a pair of image patches comprising a first PxP patch of a coordinate of the source image in the top level of the first hierarchical image pyramid and a second PxP patch of a corresponding coordinate mapped in the target image in the top level of the second hierarchical image pyramid, the pair of image patches indicating a pair of intensity values associated with the first PxP patch and the second PxP patch; if a local map update is received from a level above, evaluating the local map update by performing a greedy evaluation; estimating an error vector between the pair of image patches in the top level; finding a local map update vector for minimizing the error vector; expanding the local map update vector into a level below in the second hierarchical image pyramid; repeating the steps of evaluating the local map update, estimating the error vector, finding the local map update vector, and expanding the local map update vector into the level below at each successive level L of the first and the second hierarchical image pyramids; and within the base level, evaluating the local map update from L=1, estimating another error vector, and evaluating another local map update vector.
The method in claim 1, where estimating the error vector comprises taking a numerical derivative of an estimated error vector with respect to the corresponding coordinate of the target image.
The method of claim 1, wherein finding the local map update vector comprises solving a linear system using a special case of Singular Value Decomposition.
The method in claim 1, wherein each level above the base level in each of the first and the second hierarchical image pyramids are downsampled by a predetermined factor from a level below.
The method of claim 1, wherein the greedy evaluation at any given level L comprises comparing the error vector from a level above with an estimated error vector for the given level L, and retaining the error vector from the level above if it is less than the estimated error vector for the given level L.
The method of claim 1, further comprising outputting an image appearance match between the source image and the target image, the image appearance match configured to track non-rigid motion and parallax due to depth in a camera image stream.
The method of claim 5, further comprising providing the image appearance match to a downstream mapping module in a tracking and mapping system for monitoring a group of users in a hazardous environment.
The method of claim 5, further comprising providing the image appearance match to a downstream mapping module in an autonomous navigation system.
The method of claim 5, further comprising providing the image appearance match to a downstream mapping module in a medical imaging system.
The method of claim 5, further comprising providing the image appearance match to a downstream mapping module in a robotics system.
The method of claim 1, wherein the data associated with the first and the second hierarchical image pyramids is stored using an associative data structure.
A system for hierarchical map relaxation for inside-out location tracking, the system comprising: a memory comprising non-transitory computer-readable storage medium configured to store instructions and data, the data being stored in an associative data structure; and a processor communicatively coupled to the memory, the processor configured to execute instructions stored on the non-transitory computer-readable storage medium to: receive as input a bijective mapping of a source image to a target image, the bijective mapping comprising a first hierarchical image pyramid for the source image and a second hierarchical image pyramid for the target image, each of the first and the second hierarchical image pyramids comprising a base level L=0 and N levels above the base level; generate a pair of image patches comprising a first PxP patch of a coordinate of the source image in the top level of the first hierarchical image pyramid and a second PxP patch of a corresponding coordinate mapped in the target image in the top level of the second hierarchical image pyramid, the pair of image patches indicating a pair of intensity values associated with the first PxP patch and the second PxP patch; if a local map update is received from a level above, evaluate the local map update by performing a greedy evaluation; estimate an error vector between the pair of image patches in the top level; find a local map update vector for minimizing the error vector; expand the local map update vector into a level below in the second hierarchical image pyramid; repeat the steps of evaluating the local map update, estimating the error vector, finding the local map update vector, and expanding the local map update vector into the level below at each successive level L of the first and the second hierarchical image pyramids; and within the base level, evaluate the local map update from L=1, estimate another error vector, and evaluate another local map update vector.
The system of claim 11, wherein the associative data structure comprises a tracking grid configured to update information about camera and scene points.
The system of claim 11, wherein the associative data structure comprises a tracking grid configured to eliminate and insert new cameras and scene points.
The system of claim 11, wherein the associative data structure comprises a tracking grid configured to evaluate a quality of a tracked scene point.
The system in claim 11, wherein the data comprises camera data associated with the source image and the target image.
The system of claim 11, wherein the data comprises IMU data associated with the source image and the target image.
The system of claim 11, wherein the data is associated with the first hierarchical image pyramid for the source image and the second hierarchical image pyramid for the target image.
The system of claim 11, wherein the data is associated with the pair of image patches.
The system of claim 11, wherein the data is associated with predetermined thresholds.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS This application is a continuation-in-part to U.S. Patent Application No. 17/685,590 entitled "Estimating Camera Motion Through Visual Tracking In Low Contrast High Motion Single Camera Systems," filed March 3, 2022, which claims the benefit of U.S. Provisional Application No. 63/156,246, filed on March 3, 2021, all of which are hereby incorporated by reference in their entirety. BACKGROUND OF INVENTION In high stress and oftentimes hazardous environments-firefighting, accident scene, search and rescue, disaster relief, oil and gas, fighter pilots, mining, police or military operation, special operations, and the like-workers and other personnel often need to navigate as a team in an environment where it is very difficult, if not impossible, for team members to locate each other through visual or verbal means. Often team members are too dispersed, either due to hazards, obstacles, or size of operating location, to maintain visual or verbal contact. Even where radio contact is available, in many hazardous environments (e.g., fire, military engagement, disaster environments) it may not be possible for a team member to accurately describe their location, particularly relative to others to aid in navigating quickly and efficiently to a desired location. Also, the operating locations might be remote where conventional location tracking technologies (e.g., GPS and cellular) are unreliable (i.e., intermittent or insufficient resolution). Other persons (e.g., jogger, hiker, adventurer) also trek into remote areas and often get lost in locations where conventional location tracking technology is unreliable. While conventional GPS and cellular triangulation methods work well enough within urban environments, they often perform poorly in remote locations or in a disaster situation. Many conventional existing team location tracking and mapping solutions require outside-in location tracking infrastructure, relying on external location services, such as GPS. Outside-in location tracking systems require infrastructure (e.g., GPS satellites, warehouse cameras, emitters, etc.) that is often lacking in these environments. Sparse feature tracking requires high quality images. Known camera-based inside-out team location tracking systems assume high-quality visible light images (i.e., for extracting sparse features, which are used for matching across time in order to estimate camera motion and scene structure). Since the hazardous or disaster environments in which emergency responders and critical workers often need to operate typically do not have access to external location services and cannot accommodate the capture of high-quality visible light images in real time, these conventional solutions are of limited use to them. Thus, there is a need for an improved inside-out location tracking and mapping system. BRIEF SUMMARY The present disclosure provides techniques for hierarchical map relaxation for an inside-out location tracking and mapping system. A method for hierarchical map relaxation for an inside-out location tracking and mapping system may include: receiving as input a bijective mapping of a source image to a target image, the bijective mapping comprising a first hierarchical image pyramid for the source image and a second hierarchical image pyramid for the target image, each of the first and the second hierarchical image pyramids comprising a base level L=0 and N levels above the base level; generating a pair of image patches comprising a first PxP patch of a coordinate of the source image in the top level of the first hierarchical image pyramid and a second PxP patch of a corresponding coordinate mapped in the target image in the top level of the second hierarchical image pyramid, the pair of image patches indicating a pair of intensity values associated with the first PxP patch and the second PxP patch; if a local map update is received from a level above, evaluating the local map update by performing a greedy evaluation; estimating an error vector between the pair of image patches in the top level; finding a local map update vector for minimizing the error vector; expanding the local map update vector into a level below in the second hierarchical image pyramid; repeating the steps of evaluating the local map update, estimating the error vector, finding the local map update vector, and expanding the local map update vector into the level below at each successive level L of the first and the second hierarchical image pyramids; and within the base level, evaluating the local map update from L=1, estimating another error vector, and evaluating another local map update vector. In some examples, estimating the error vector comprises taking a numerical derivative of an estimated error vector with respect to the corresponding coordinate of the target image. In some examples, finding the local map update vector comprises solving a linear system using a special case of Singular Value