import { createRandomizer } from '../utils/randomizer' ; import { quadrilateralConvex , matrixInverse33 , smallestTriangleArea , multiplyPointHomographyInhomogenous , checkThreePointsConsistent , checkFourPointsConsistent } from '../utils/geometry' ; import { solveHomography } from '../utils/homography' ; const HOMOGRAPHY_DEFAULT_CAUCHY_SCALE = 0.01 ; const HOMOGRAPHY_DEFAULT_NUM_HYPOTHESES = 1024 ; const HOMOGRAPHY_DEFAULT_MAX_TRIALS = 100 ; const HOMOGRAPHY_DEFAULT_CHUNK_SIZE = 50 ; export const computeHomography = ( options ) => { const { srcPoints , dstPoints , keyframe } = options ; const testPoints = [ [ 0 , 0 ] , [ keyframe . width , 0 ] , [ keyframe . width , keyframe . height ] , [ 0 , keyframe . height ] ] ; const sampleSize = 4 ; if ( srcPoints . length < sampleSize ) return null ; const scale = HOMOGRAPHY_DEFAULT_CAUCHY_SCALE ; const oneOverScale2 = 1.0 / ( scale * scale ) ; const chuckSize = Math . min ( HOMOGRAPHY_DEFAULT_CHUNK_SIZE , srcPoints . length ) ; const randomizer = createRandomizer ( ) ; const perm = [ ] ; for ( let i = 0 ; i < srcPoints . length ; i ++ ) { perm [ i ] = i ; } randomizer . arrayShuffle ( { arr : perm , sampleSize : perm . length } ) ; let trial = 0 ; const Hs = [ ] ; while ( trial < HOMOGRAPHY_DEFAULT_MAX_TRIALS && Hs . length < HOMOGRAPHY_DEFAULT_NUM_HYPOTHESES ) { randomizer . arrayShuffle ( { arr : perm , sampleSize : sampleSize } ) ; trial += 1 ; if ( ! checkFourPointsConsistent ( srcPoints [ perm [ 0 ] ] , srcPoints [ perm [ 1 ] ] , srcPoints [ perm [ 2 ] ] , srcPoints [ perm [ 3 ] ] , dstPoints [ perm [ 0 ] ] , dstPoints [ perm [ 1 ] ] , dstPoints [ perm [ 2 ] ] , dstPoints [ perm [ 3 ] ] ) ) { continue ; } const H = solveHomography ( [ srcPoints [ perm [ 0 ] ] , srcPoints [ perm [ 1 ] ] , srcPoints [ perm [ 2 ] ] , srcPoints [ perm [ 3 ] ] ] , [ dstPoints [ perm [ 0 ] ] , dstPoints [ perm [ 1 ] ] , dstPoints [ perm [ 2 ] ] , dstPoints [ perm [ 3 ] ] ] ) ; if ( H === null ) continue ; if ( ! _checkHomographyPointsGeometricallyConsistent ( { H , testPoints } ) ) { continue ; } Hs . push ( H ) ; } if ( Hs . length === 0 ) return null ; const hypotheses = [ ] ; for ( let i = 0 ; i < Hs . length ; i ++ ) { hypotheses . push ( { H : Hs [ i ] , cost : 0 } ) ; } let curChuckSize = chuckSize ; for ( let i = 0 ; i < srcPoints . length && hypotheses . length > 2 ; i += curChuckSize ) { curChuckSize = Math . min ( chuckSize , srcPoints . length - i ) ; let chuckEnd = i + curChuckSize ; for ( let j = 0 ; j < hypotheses . length ; j ++ ) { for ( let k = i ; k < chuckEnd ; k ++ ) { const cost = _cauchyProjectiveReprojectionCost ( { H : hypotheses [ j ] . H , srcPoint : srcPoints [ k ] , dstPoint : dstPoints [ k ] , oneOverScale2 } ) ; hypotheses [ j ] . cost += cost ; } } hypotheses . sort ( ( h1 , h2 ) => { return h1 . cost - h2 . cost ; } ) ; hypotheses . splice ( - Math . floor ( ( hypotheses . length + 1 ) / 2 ) ) ; } let bestIndex = 0 ; for ( let i = 1 ; i < hypotheses . length ; i ++ ) { if ( hypotheses [ i ] . cost < hypotheses [ bestIndex ] . cost ) bestIndex = i ; } const finalH = _normalizeHomography ( { inH : hypotheses [ bestIndex ] . H } ) ; if ( ! _checkHeuristics ( { H : finalH , testPoints , keyframe } ) ) return null ; return finalH ; } ; const _checkHeuristics = ( { H , testPoints , keyframe } ) => { const HInv = matrixInverse33 ( H , 0.00001 ) ; if ( HInv === null ) return false ; const mp = [ ] ; for ( let i = 0 ; i < testPoints . length ; i ++ ) { mp . push ( multiplyPointHomographyInhomogenous ( testPoints [ i ] , HInv ) ) ; } const smallArea = smallestTriangleArea ( mp [ 0 ] , mp [ 1 ] , mp [ 2 ] , mp [ 3 ] ) ; if ( smallArea < keyframe . width * keyframe . height * 0.0001 ) return false ; if ( ! quadrilateralConvex ( mp [ 0 ] , mp [ 1 ] , mp [ 2 ] , mp [ 3 ] ) ) return false ; return true ; } ; const _normalizeHomography = ( { inH } ) => { const oneOver = 1.0 / inH [ 8 ] ; const H = [ ] ; for ( let i = 0 ; i < 8 ; i ++ ) { H [ i ] = inH [ i ] * oneOver ; } H [ 8 ] = 1.0 ; return H ; } ; const _cauchyProjectiveReprojectionCost = ( { H , srcPoint , dstPoint , oneOverScale2 } ) => { const x = multiplyPointHomographyInhomogenous ( srcPoint , H ) ; const f = [ x [ 0 ] - dstPoint [ 0 ] , x [ 1 ] - dstPoint [ 1 ] ] ; return Math . log ( 1 + ( f [ 0 ] * f [ 0 ] + f [ 1 ] * f [ 1 ] ) * oneOverScale2 ) ; } ; const _checkHomographyPointsGeometricallyConsistent = ( { H , testPoints } ) => { const mappedPoints = [ ] ; for ( let i = 0 ; i < testPoints . length ; i ++ ) { mappedPoints [ i ] = multiplyPointHomographyInhomogenous ( testPoints [ i ] , H ) ; } for ( let i = 0 ; i < testPoints . length ; i ++ ) { const i1 = i ; const i2 = ( i + 1 ) % testPoints . length ; const i3 = ( i + 2 ) % testPoints . length ; if ( ! checkThreePointsConsistent ( testPoints [ i1 ] , testPoints [ i2 ] , testPoints [ i3 ] , mappedPoints [ i1 ] , mappedPoints [ i2 ] , mappedPoints [ i3 ] ) ) return false ; } return true ; } ;