import { Cumsum } from '../utils/cumsum' ; const SEARCH_SIZE1 = 10 ; const SEARCH_SIZE2 = 2 ; const TEMPLATE_SIZE = 22 ; const TEMPLATE_SD_THRESH = 5.0 ; const MAX_SIM_THRESH = 0.95 ; const MAX_THRESH = 0.9 ; const MIN_THRESH = 0.55 ; const SD_THRESH = 8.0 ; const OCCUPANCY_SIZE = 24 * 2 / 3 ; export const extract = ( image ) => { const { data : imageData , width , height } = image ; const isPixelSelected = [ width * height ] ; for ( let i = 0 ; i < isPixelSelected . length ; i ++ ) { isPixelSelected [ i ] = false ; } const dValue = new Float32Array ( imageData . length ) ; for ( let i = 0 ; i < width ; i ++ ) { dValue [ i ] = - 1 ; dValue [ width * ( height - 1 ) + i ] = - 1 ; } for ( let j = 0 ; j < height ; j ++ ) { dValue [ j * width ] = - 1 ; dValue [ j * width + width - 1 ] = - 1 ; } for ( let i = 1 ; i < width - 1 ; i ++ ) { for ( let j = 1 ; j < height - 1 ; j ++ ) { let pos = i + width * j ; let dx = 0.0 ; let dy = 0.0 ; for ( let k = - 1 ; k <= 1 ; k ++ ) { dx += ( imageData [ pos + width * k + 1 ] - imageData [ pos + width * k - 1 ] ) ; dy += ( imageData [ pos + width + k ] - imageData [ pos - width + k ] ) ; } dx /= ( 3 * 256 ) ; dy /= ( 3 * 256 ) ; dValue [ pos ] = Math . sqrt ( ( dx * dx + dy * dy ) / 2 ) ; } } const dValueHist = new Uint32Array ( 1000 ) ; for ( let i = 0 ; i < 1000 ; i ++ ) dValueHist [ i ] = 0 ; const neighbourOffsets = [ - 1 , 1 , - width , width ] ; let allCount = 0 ; for ( let i = 1 ; i < width - 1 ; i ++ ) { for ( let j = 1 ; j < height - 1 ; j ++ ) { let pos = i + width * j ; let isMax = true ; for ( let d = 0 ; d < neighbourOffsets . length ; d ++ ) { if ( dValue [ pos ] <= dValue [ pos + neighbourOffsets [ d ] ] ) { isMax = false ; break ; } } if ( isMax ) { let k = Math . floor ( dValue [ pos ] * 1000 ) ; if ( k > 999 ) k = 999 ; if ( k < 0 ) k = 0 ; dValueHist [ k ] += 1 ; allCount += 1 ; isPixelSelected [ pos ] = true ; } } } const maxPoints = 0.02 * width * height ; let k = 999 ; let filteredCount = 0 ; while ( k >= 0 ) { filteredCount += dValueHist [ k ] ; if ( filteredCount > maxPoints ) break ; k -- ; } for ( let i = 0 ; i < isPixelSelected . length ; i ++ ) { if ( isPixelSelected [ i ] ) { if ( dValue [ i ] * 1000 < k ) isPixelSelected [ i ] = false ; } } const imageDataSqr = [ ] ; for ( let i = 0 ; i < imageData . length ; i ++ ) { imageDataSqr [ i ] = imageData [ i ] * imageData [ i ] ; } const imageDataCumsum = new Cumsum ( imageData , width , height ) ; const imageDataSqrCumsum = new Cumsum ( imageDataSqr , width , height ) ; const featureMap = new Float32Array ( imageData . length ) ; for ( let i = 0 ; i < width ; i ++ ) { for ( let j = 0 ; j < height ; j ++ ) { const pos = j * width + i ; if ( ! isPixelSelected [ pos ] ) { featureMap [ pos ] = 1.0 ; continue ; } const vlen = _templateVar ( { image , cx : i , cy : j , sdThresh : TEMPLATE_SD_THRESH , imageDataCumsum , imageDataSqrCumsum } ) ; if ( vlen === null ) { featureMap [ pos ] = 1.0 ; continue ; } let max = - 1.0 ; for ( let jj = - SEARCH_SIZE1 ; jj <= SEARCH_SIZE1 ; jj ++ ) { for ( let ii = - SEARCH_SIZE1 ; ii <= SEARCH_SIZE1 ; ii ++ ) { if ( ii * ii + jj * jj <= SEARCH_SIZE2 * SEARCH_SIZE2 ) continue ; const sim = _getSimilarity ( { image , cx : i + ii , cy : j + jj , vlen : vlen , tx : i , ty : j , imageDataCumsum , imageDataSqrCumsum } ) ; if ( sim === null ) continue ; if ( sim > max ) { max = sim ; if ( max > MAX_SIM_THRESH ) break ; } } if ( max > MAX_SIM_THRESH ) break ; } featureMap [ pos ] = max ; } } const coords = _selectFeature ( { image , featureMap , templateSize : TEMPLATE_SIZE , searchSize : SEARCH_SIZE2 , occSize : OCCUPANCY_SIZE , maxSimThresh : MAX_THRESH , minSimThresh : MIN_THRESH , sdThresh : SD_THRESH , imageDataCumsum , imageDataSqrCumsum } ) ; return coords ; } ; const _selectFeature = ( options ) => { let { image , featureMap , templateSize , searchSize , occSize , maxSimThresh , minSimThresh , sdThresh , imageDataCumsum , imageDataSqrCumsum } = options ; const { data : imageData , width , height } = image ; occSize = Math . floor ( Math . min ( image . width , image . height ) / 10 ) ; const divSize = ( templateSize * 2 + 1 ) * 3 ; const xDiv = Math . floor ( width / divSize ) ; const yDiv = Math . floor ( height / divSize ) ; let maxFeatureNum = Math . floor ( width / occSize ) * Math . floor ( height / occSize ) + xDiv * yDiv ; const coords = [ ] ; const image2 = new Float32Array ( imageData . length ) ; for ( let i = 0 ; i < image2 . length ; i ++ ) { image2 [ i ] = featureMap [ i ] ; } let num = 0 ; while ( num < maxFeatureNum ) { let minSim = maxSimThresh ; let cx = - 1 ; let cy = - 1 ; for ( let j = 0 ; j < height ; j ++ ) { for ( let i = 0 ; i < width ; i ++ ) { if ( image2 [ j * width + i ] < minSim ) { minSim = image2 [ j * width + i ] ; cx = i ; cy = j ; } } } if ( cx === - 1 ) break ; const vlen = _templateVar ( { image , cx : cx , cy : cy , sdThresh : 0 , imageDataCumsum , imageDataSqrCumsum } ) ; if ( vlen === null ) { image2 [ cy * width + cx ] = 1.0 ; continue ; } if ( vlen / ( templateSize * 2 + 1 ) < sdThresh ) { image2 [ cy * width + cx ] = 1.0 ; continue ; } let min = 1.0 ; let max = - 1.0 ; for ( let j = - searchSize ; j <= searchSize ; j ++ ) { for ( let i = - searchSize ; i <= searchSize ; i ++ ) { if ( i * i + j * j > searchSize * searchSize ) continue ; if ( i === 0 && j === 0 ) continue ; const sim = _getSimilarity ( { image , vlen , cx : cx + i , cy : cy + j , tx : cx , ty : cy , imageDataCumsum , imageDataSqrCumsum } ) ; if ( sim === null ) continue ; if ( sim < min ) { min = sim ; if ( min < minSimThresh && min < minSim ) break ; } if ( sim > max ) { max = sim ; if ( max > 0.99 ) break ; } } if ( ( min < minSimThresh && min < minSim ) || max > 0.99 ) break ; } if ( ( min < minSimThresh && min < minSim ) || max > 0.99 ) { image2 [ cy * width + cx ] = 1.0 ; continue ; } coords . push ( { x : cx , y : cy } ) ; num += 1 ; for ( let j = - occSize ; j <= occSize ; j ++ ) { for ( let i = - occSize ; i <= occSize ; i ++ ) { if ( cy + j < 0 || cy + j >= height || cx + i < 0 || cx + i >= width ) continue ; image2 [ ( cy + j ) * width + ( cx + i ) ] = 1.0 ; } } } return coords ; } ; const _templateVar = ( { image , cx , cy , sdThresh , imageDataCumsum , imageDataSqrCumsum } ) => { if ( cx - TEMPLATE_SIZE < 0 || cx + TEMPLATE_SIZE >= image . width ) return null ; if ( cy - TEMPLATE_SIZE < 0 || cy + TEMPLATE_SIZE >= image . height ) return null ; const templateWidth = 2 * TEMPLATE_SIZE + 1 ; const nPixels = templateWidth * templateWidth ; let average = imageDataCumsum . query ( cx - TEMPLATE_SIZE , cy - TEMPLATE_SIZE , cx + TEMPLATE_SIZE , cy + TEMPLATE_SIZE ) ; average /= nPixels ; let vlen = imageDataSqrCumsum . query ( cx - TEMPLATE_SIZE , cy - TEMPLATE_SIZE , cx + TEMPLATE_SIZE , cy + TEMPLATE_SIZE ) ; vlen -= 2 * average * imageDataCumsum . query ( cx - TEMPLATE_SIZE , cy - TEMPLATE_SIZE , cx + TEMPLATE_SIZE , cy + TEMPLATE_SIZE ) ; vlen += nPixels * average * average ; if ( vlen / nPixels < sdThresh * sdThresh ) return null ; vlen = Math . sqrt ( vlen ) ; return vlen ; } ; const _getSimilarity = ( options ) => { const { image , cx , cy , vlen , tx , ty , imageDataCumsum , imageDataSqrCumsum } = options ; const { data : imageData , width , height } = image ; const templateSize = TEMPLATE_SIZE ; if ( cx - templateSize < 0 || cx + templateSize >= width ) return null ; if ( cy - templateSize < 0 || cy + templateSize >= height ) return null ; const templateWidth = 2 * templateSize + 1 ; let sx = imageDataCumsum . query ( cx - templateSize , cy - templateSize , cx + templateSize , cy + templateSize ) ; let sxx = imageDataSqrCumsum . query ( cx - templateSize , cy - templateSize , cx + templateSize , cy + templateSize ) ; let sxy = 0 ; let p1 = ( cy - templateSize ) * width + ( cx - templateSize ) ; let p2 = ( ty - templateSize ) * width + ( tx - templateSize ) ; let nextRowOffset = width - templateWidth ; for ( let j = 0 ; j < templateWidth ; j ++ ) { for ( let i = 0 ; i < templateWidth ; i ++ ) { sxy += imageData [ p1 ] * imageData [ p2 ] ; p1 += 1 ; p2 += 1 ; } p1 += nextRowOffset ; p2 += nextRowOffset ; } let templateAverage = imageDataCumsum . query ( tx - templateSize , ty - templateSize , tx + templateSize , ty + templateSize ) ; templateAverage /= templateWidth * templateWidth ; sxy -= templateAverage * sx ; let vlen2 = sxx - sx * sx / ( templateWidth * templateWidth ) ; if ( vlen2 == 0 ) return null ; vlen2 = Math . sqrt ( vlen2 ) ; const sim = 1.0 * sxy / ( vlen * vlen2 ) ; return sim ; } ;