const kHoughBinDelta = 1 ; export const computeHoughMatches = ( options ) => { const { keywidth , keyheight , querywidth , queryheight , matches } = options ; const maxX = querywidth * 1.2 ; const minX = - maxX ; const maxY = queryheight * 1.2 ; const minY = - maxY ; const numAngleBins = 12 ; const numScaleBins = 10 ; const minScale = - 1 ; const maxScale = 1 ; const scaleK = 10.0 ; const scaleOneOverLogK = 1.0 / Math . log ( scaleK ) ; const maxDim = Math . max ( keywidth , keyheight ) ; const keycenterX = Math . floor ( keywidth / 2 ) ; const keycenterY = Math . floor ( keyheight / 2 ) ; const projectedDims = [ ] ; for ( let i = 0 ; i < matches . length ; i ++ ) { const queryscale = matches [ i ] . querypoint . scale ; const keyscale = matches [ i ] . keypoint . scale ; if ( keyscale == 0 ) console . log ( "ERROR divide zero" ) ; const scale = queryscale / keyscale ; projectedDims . push ( scale * maxDim ) ; } projectedDims . sort ( ( a1 , a2 ) => { return a1 - a2 ; } ) ; const medianProjectedDim = projectedDims [ Math . floor ( projectedDims . length / 2 ) - ( projectedDims . length % 2 == 0 ? 1 : 0 ) - 1 ] ; const binSize = 0.25 * medianProjectedDim ; const numXBins = Math . max ( 5 , Math . ceil ( ( maxX - minX ) / binSize ) ) ; const numYBins = Math . max ( 5 , Math . ceil ( ( maxY - minY ) / binSize ) ) ; const numXYBins = numXBins * numYBins ; const numXYAngleBins = numXYBins * numAngleBins ; const querypointValids = [ ] ; const querypointBinLocations = [ ] ; const votes = { } ; for ( let i = 0 ; i < matches . length ; i ++ ) { const querypoint = matches [ i ] . querypoint ; const keypoint = matches [ i ] . keypoint ; const { x , y , scale , angle } = _mapCorrespondence ( { querypoint , keypoint , keycenterX , keycenterY , scaleOneOverLogK } ) ; if ( x < minX || x >= maxX || y < minY || y >= maxY || angle <= - Math . PI || angle > Math . PI || scale < minScale || scale >= maxScale ) { querypointValids [ i ] = false ; continue ; } let fbinX = numXBins * ( x - minX ) / ( maxX - minX ) ; let fbinY = numYBins * ( y - minY ) / ( maxY - minY ) ; let fbinAngle = numAngleBins * ( angle + Math . PI ) / ( 2.0 * Math . PI ) ; let fbinScale = numScaleBins * ( scale - minScale ) / ( maxScale - minScale ) ; querypointBinLocations [ i ] = { binX : fbinX , binY : fbinY , binAngle : fbinAngle , binScale : fbinScale } ; let binX = Math . floor ( fbinX - 0.5 ) ; let binY = Math . floor ( fbinY - 0.5 ) ; let binScale = Math . floor ( fbinScale - 0.5 ) ; let binAngle = ( Math . floor ( fbinAngle - 0.5 ) + numAngleBins ) % numAngleBins ; if ( binX < 0 || binX + 1 >= numXBins || binY < 0 || binY + 1 >= numYBins || binScale < 0 || binScale + 1 >= numScaleBins ) { querypointValids [ i ] = false ; continue ; } for ( let dx = 0 ; dx < 2 ; dx ++ ) { let binX2 = binX + dx ; for ( let dy = 0 ; dy < 2 ; dy ++ ) { let binY2 = binY + dy ; for ( let dangle = 0 ; dangle < 2 ; dangle ++ ) { let binAngle2 = ( binAngle + dangle ) % numAngleBins ; for ( let dscale = 0 ; dscale < 2 ; dscale ++ ) { let binScale2 = binScale + dscale ; const binIndex = binX2 + binY2 * numXBins + binAngle2 * numXYBins + binScale2 * numXYAngleBins ; if ( votes [ binIndex ] === undefined ) votes [ binIndex ] = 0 ; votes [ binIndex ] += 1 ; } } } } querypointValids [ i ] = true ; } let maxVotes = 0 ; let maxVoteIndex = - 1 ; Object . keys ( votes ) . forEach ( ( index ) => { if ( votes [ index ] > maxVotes ) { maxVotes = votes [ index ] ; maxVoteIndex = index ; } } ) ; if ( maxVotes < 3 ) return [ ] ; const binX = Math . floor ( ( ( maxVoteIndex % numXYAngleBins ) % numXYBins ) % numXBins ) ; const binY = Math . floor ( ( ( ( maxVoteIndex - binX ) % numXYAngleBins ) % numXYBins ) / numXBins ) ; const binAngle = Math . floor ( ( ( maxVoteIndex - binX - ( binY * numXBins ) ) % numXYAngleBins ) / numXYBins ) ; const binScale = Math . floor ( ( maxVoteIndex - binX - ( binY * numXBins ) - ( binAngle * numXYBins ) ) / numXYAngleBins ) ; const houghMatches = [ ] ; for ( let i = 0 ; i < matches . length ; i ++ ) { if ( ! querypointValids [ i ] ) continue ; const queryBins = querypointBinLocations [ i ] ; const distBinX = Math . abs ( queryBins . binX - ( binX + 0.5 ) ) ; if ( distBinX >= kHoughBinDelta ) continue ; const distBinY = Math . abs ( queryBins . binY - ( binY + 0.5 ) ) ; if ( distBinY >= kHoughBinDelta ) continue ; const distBinScale = Math . abs ( queryBins . binScale - ( binScale + 0.5 ) ) ; if ( distBinScale >= kHoughBinDelta ) continue ; const temp = Math . abs ( queryBins . binAngle - ( binAngle + 0.5 ) ) ; const distBinAngle = Math . min ( temp , numAngleBins - temp ) ; if ( distBinAngle >= kHoughBinDelta ) continue ; houghMatches . push ( matches [ i ] ) ; } return houghMatches ; } ; const _mapCorrespondence = ( { querypoint , keypoint , keycenterX , keycenterY , scaleOneOverLogK } ) => { let angle = querypoint . angle - keypoint . angle ; if ( angle <= - Math . PI ) angle += 2 * Math . PI ; else if ( angle > Math . PI ) angle -= 2 * Math . PI ; const scale = querypoint . scale / keypoint . scale ; const cos = scale * Math . cos ( angle ) ; const sin = scale * Math . sin ( angle ) ; const S = [ cos , - sin , sin , cos ] ; const tp = [ S [ 0 ] * keypoint . x + S [ 1 ] * keypoint . y , S [ 2 ] * keypoint . x + S [ 3 ] * keypoint . y ] ; const tx = querypoint . x - tp [ 0 ] ; const ty = querypoint . y - tp [ 1 ] ; return { x : S [ 0 ] * keycenterX + S [ 1 ] * keycenterY + tx , y : S [ 2 ] * keycenterX + S [ 3 ] * keycenterY + ty , angle : angle , scale : Math . log ( scale ) * scaleOneOverLogK } ; } ;