Edge Image Description Using Angular Radial PartitioningA.Chalechale, A. Mertins and G. NaghdyIEE Proc.-Vis. Image Signal Processing, 2004Slides by David Anthony TorresComputer Science and Engineering — University of California at San DiegoAngular Radial Partitioning• Partition edge map into angular and radial bin.• Partition into M ×N bins! M radial parts! N angular parts• Index a bin by (k,i)ρ=kR/M, k =1..Mθ=2πi/N, i =1..NImage: I(ρ,θ)Angular Radial Partitioning• Sector feature f(k,i) = # edge pixels in (k,i)• A feature f(k,i) is shifted when we rotate by2 / for 0,1,2,...lN lτπ==• Denote image rotation by Iτ(ρ,θ) = I(ρ,θ-τ)• Feature rotates as wellfτ(k,i) = f(k,i-l)Angular Radial PartitioningTake 1-D Fourier Transform••Take 1-D Fourier TransformTake 1-D Fourier TransformTake 1-D Fourier Transform• Because their power-spectra are the same• Transforms contain rotational invarianceRotational Invariance• Choose {||F(k,u)||} for k=0..M-1 and u=0..N-1 as image features.f(k,i)||F(k,i)||Other approaches…• Moment Generating Functions! Common image analysis technique" Treat the image as a distribution and generate moments." Combine several different moments into a feature vector.Other approaches…• Zernike Moments! Less sensitive to noise.! More powerful in discriminating objects.! Used for shape descriptor in MPEG-7! Based on Zernike orthogonal polynomialsOther approaches…• The Zernike Moment Invariant of an image f• Can approximate the image by• {Anl} are used for image matching.Edge Histogram Methods• Partition image and build local edge histograms.• Histogram of Edge Directions! Partition image into large local regions.! Partition each local region into small image patches.! Quantize each patch as horizontal, vertical, diagonal" Use filters for this.! Collect results into local region histograms.! Perform matching based on histograms.Edge Histogram Methods• Application of Histogram Method: Edge Histogram Descriptor (EHD)! Used in MPEG-7 to calculate frame similarity! Algorithm:" Divide the image into 16 sub-images" Divide each sub-image into blocks" Split block into 4 quadrants" Use 2x2 filter masks to bin each quadrant intovertical, horizontal, 45°diagonal, 135°diagonal, non-directional." Collect a histogram of edge directions for each sub-image. (Gives you 16 x 5=80 bins)" Compare two histograms for similarityImageSub-ImageBlockAngular Radial Transformation • Also used in MPEG-7 to retrieve/encode object information. • Can describe complex objects (such as trademarks)• ART is a transform defined on a unit disc.• Consists of orthonormal sinusoidal basis functions .Angular Radial Transformation• From each image we extract ART coefficients: ψmn• f(ρ,θ) is the image.• Vnm(ρ,θ) is the basis functionAngular Radial Transformation• The basis function:• Consists of an angular component:• And a radial component:Angular Radial Transformation• ART Algorithm" Normalize image to a set dimension" Perform edge detection" Calculate ψmnfor m=0..M, n=0..N according to " Scale coefficients by |ψ00| to normalize." Perform matching on the features ψmn.ResultsPerformance Measure: ANMRR• Use Average Normalized Modified Retrieval Rank (ANMRR)• Incorporates recall, precision and rank information.• Defines as:" Average NMRR score for all queries 1,2,…,QPerformance Measure: ANMRR• NMRR is the normalized MRR score• NG(q) is the number of ground truth images for query q.• K=min( 4NG(q), 2GTM) where GTM is max{NG(q)}Performance Measure: ANMRR• MRR is an adjusted average rank measure• And AVR is the average rank of images in a query" NG(q) is the number of ground truth images for a query q.Performance Measure: ANMRR• A numerical example:Suppose a query q has 10 similar images in the database (NG=10). If we find 6 of the top 20 retrievals (K=20) in the ranks 1,5,8,13,14,18 then:AVR=14.3MRR=8.8NMRR=0.5677• NMRR and ANMRR are always in [0,1]• The smaller the ANMRR the betterTest Inputs:Varying Angular and Radial PartitionsSensitivity to