# US 10,762,162 B2 · Apparatus and method of low complexity optimization solver for path smoothing with constraint variation > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,762,162 B2 - Document ID: US10762162B2 - Status: Granted - Kind: B2 - Application number: 16/742,231 - Filed: 2020-01-14 - Published: 2020-05-14 - Granted: 2020-09-01 - Earliest claimed: 2017-11-13 - Assignees: Samsung Electronics Co., Ltd. - Applicants: Samsung Electronics Co., Ltd. - Inventors: Binnan Zhuang; Dongwoon Bai; Jungwon Lee - Web page: https://patentgrep.com/patent/US10762162B2 ## CPC - G06F 17/12: Simultaneous equations {, e.g. systems of linear equations} - G06T 7/246: using feature-based methods, e.g. the tracking of corners or segments - G06F 7/58: Random or pseudo-random number generators - G06F 17/16: Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} - G06T 5/70: Denoising; Smoothing - G06T 7/285: using a sequence of stereo image pairs - G06T 7/85: {Stereo camera calibration} - H04N 13/282: for generating image signals corresponding to three or more geometrical viewpoints, e.g. multi-view systems - H04N 19/00: Methods or arrangements for coding, decoding, compressing or decompressing digital video signals - H04N 23/68: for stable pick-up of the scene, e.g. compensating for camera body vibrations - H04N 23/6812: {based on additional sensors, e.g. acceleration sensors} - H04N 23/683: {performed by a processor, e.g. controlling the readout of an image memory} - G06T 2200/04: involving 3D image data - G06T 2207/10021: Stereoscopic video; Stereoscopic image sequence - G06T 2207/30244: Camera pose - H04N 13/204: using stereoscopic image cameras (stereoscopic photography G03B35/00) - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL - H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION ## Abstract An apparatus and method of low complexity optimization solver for path smoothing with constraint variation are herein disclosed. According to one embodiment, an apparatus includes an L1 central processing unit (CPU) configured to transform an L1 trend filtering problem to a primal-dual linear programming (LP) optimization problem pair; and an L1 arithmetic logic unit (ALU) connected to the L1 CPU and configured to solve a primal problem of the primal-dual LP optimization problem pair with an extended full tableau simplex method. ## Claims ### Claim 1 An apparatus, comprising: an L1 central processing unit (CPU) configured to transform an L1 trend filtering problem to a primal-dual linear programming (LP) optimization problem pair; and an L1 arithmetic logic unit (ALU) connected to the L1 CPU and configured to solve a primal problem of the primal-dual LP optimization problem pair with an extended full tableau simplex method. ### Claim 2 (depends on 1) The apparatus of claim 1, wherein the L1 ALU is further configured to use a previous solution of the primal-dual LP optimization problem pair as a warm start. ### Claim 3 (depends on 1) The apparatus of claim 1, wherein the L1 trend filtering problem is formulated as min z - r th ≤ y ≤ z + r th ⁢ w 0 ⁢  y - z  1 1 + w 1 ⁢  D 1 ⁢ y  1 1 + w 2 ⁢  D 2 ⁢ y  1 1 + w 3 ⁢  D 3 ⁢ y  1 1 where z is a raw data series, w0, w1, w2, and w3 are weights, y is a smoothed output path, Di is an ith order differential matrix, and rth is a threshold vector. ### Claim 4 (depends on 1) The apparatus of claim 1, wherein the L1 ALU is further configured to solve the primal problem of the primal-dual LP optimization problem pair with an extended full tableau simplex method as follows: −cTBB−1b c − cTBB−1A −cTBB−1 B−1b B−1A B−1 where A is a fat matrix, c is a column matrix, B is a basis matrix, T indicates a transposition of a matrix, and b=Ax, and x is a vector. ### Claim 5 (depends on 1) The apparatus of claim 1, wherein the L1 ALU is further configured to solve the primal problem of the primal-dual LP optimization problem pair by updating c using a kth frame input zk, where z is a raw data series and k is an integer, determining if k is equal to 0, initializes the extended full tableau simplex method using simplex initialization if it is determined that k is equal to 0, initializing the extended full tableau simplex method with a warm start of a last update of the extended full tableau simplex method if k is determined to not be equal to 0, determining a current extended full tableau simplex method, determining if a cost c−cBTB−1A is all non-negative, outputting y*=−[−cBTB−1]T if the cost c−cBTB−1A is determined to be all non-negative, determining an entering column j with cj<0 if the cost c−cBTB−1A is not determined to be all non-negative, determining if u=B−1Aj is non-positive, determining an unbounded solution if u=B−1Ai is non-positive, determining an exiting column j that gives a smallest xB(i)/ui among all positive ui if u=B−1Aj is not non-positive, and performing an elementary row operation and updating the extended full tableau simplex method. ### Claim 6 A method, comprising: transforming, by an L1 central processing unit (CPU), an L1 trend filtering problem to a primal-dual linear programming (LP) optimization problem pair; and solving, by an L1 arithmetic logic unit (ALU) connected to the L1 CPU, a primal problem of the primal-dual LP optimization problem pair with an extended full tableau simplex method. ### Claim 7 (depends on 6) The method of claim 6, further comprising using, by the L1 ALU, a previous solution of the primal problem as a warm start. ### Claim 8 (depends on 6) The method of claim 6, further comprising formulating the L1 trend filtering problem as min z - r th ≤ y ≤ z + r th ⁢ w 0 ⁢  y - z  1 1 + w 1 ⁢  D 1 ⁢ y  1 1 + w 2 ⁢  D 2 ⁢ y  1 1 + w 3 ⁢  D 3 ⁢ y  1 1 where z is a raw data series to be smoothed, w0, w1, w2, and w3 are weights, y is the smoothed output path, Di is an ith order differential matrix, and rth is a threshold vector. ### Claim 9 (depends on 6) The method of claim 6, wherein solving, by the L1 ALU connected to the L1 CPU, the primal problem of the primal-dual LP optimization problem pair includes a method as follows: −cTBB−1b c − cTBB−1A −cTBB−1 B−1b B−1A B−1 where A is a fat matrix, c is a column matrix, B is a basis matrix, T indicates a transposition of a matrix, and b=Ax, and x is a vector. ### Claim 10 (depends on 6) The method of claim 6, wherein solving, by the L1 ALU connected to the L1 CPU, the primal problem of the primal-dual problems with the extended full tableau simplex method is comprised of: updating c using a kth frame input zk, where z is a raw data series to be smoothed and k is an integer; determining if k is equal to 0, initializes the extended full tableau simplex method using simplex initialization if it is determined that k is equal to 0; initializing the extended full tableau simplex method with a warm start of a last update of the extended full tableau simplex method if k is determined to not be equal to 0; determining a current extended full tableau simplex method; determining if a cost c−cBTB−1A is all non-negative, outputting y*=−[−cBTB−1]T the cost c−cBTB−1A is determined to be all non-negative; determining an entering column j with cj<0 if the cost c−cBTB−1A is not determined to be all non-negative; determining if u=B−1Aj is non-positive; determining an unbounded solution if u=B−1Aj is non-positive; determining an exiting column j that gives a smallest xB(i)/ui among all positive ui if u=B−1Aj is not non-positive; and performing an elementary row operation and updating the extended full tableau simplex method. ### Claim 11 An apparatus, comprising: an L2 central processing unit (CPU) configured to derive a quadratic programming (QP) problem through dual transformation; and an L2 arithmetic logic unit (ALU) connected to the L2 CPU and configured to solve the QP problem using an alternating direction method of multipliers (ADMM) based solution with closed-form updates. ### Claim 12 (depends on 11) The apparatus of claim 11, wherein the L2 ALU is further configured to use a previous solution of the ADMM based solution as a warm start. ### Claim 13 (depends on 11) The apparatus of claim 11, further comprising an L2 controller configured to formulate an L2 trend filtering problem as min z - r th ≤ y ≤ z + r th ⁢ w 0 ⁢  y - z  2 2 + w 1 ⁢  D 1 ⁢ y  1 1 + w 2 ⁢  D 2 ⁢ y  1 1 + w 3 ⁢  D 3 ⁢ y  1 1 where z is a raw data series, w0, w1, w2, and w3 are weights, y is the smoothed output path, Di is an ith order differential matrix, and rth is a threshold vector. ### Claim 14 (depends on 11) The apparatus of claim 11, wherein the L2 ALU is further configured to derive the quadratic programming (QP) problem through dual transformation. ### Claim 15 (depends on 11) The apparatus of claim 11, wherein the L2 ALU is further configured to solve the QP problem using the ADMM based solution with closed-form updates by updating f using an nth frame input zn, where z is a raw data series, determining if n is equal to 0, randomly initializing a variable x0 and a Lagrange multiplier α0, and setting an iteration number k equal to 0 if n is equal to 0, initializing x0 and α0 using a last update from a previous frame n−1 and setting the iteration number k equal to 0 if n is not equal to 0, determining an ADMM based update according to: x k + 1 = [ 2 ⁢ H + ρ ⁢ ⁢ I ] - 1 ⁢ ( ρ ⁢ ⁢ y k + 1 - α k - f ) y k + 1 = [ x k + 1 ρ ⁢ α k ] γ lb γ ub α k + 1 = α k + ρ ⁡ ( x k + 1 - y k + 1 ) calculating a residual gap according to: rp=|xk−yk|2 rd=|ρ(xk−xk−1)|2 determining if rp