CAN CSA-ISO IEC TR 15938-8E-2010 Information technology - Multimedia content description interface - Part 8 Extraction and use of MPEG-7 descriptions - AMENDMENT 5 Extraction and m.pdf

1、Information technology Multimedia content description interface Part 8: Extraction and use of MPEG-7 descriptions AMENDMENT 5: Extraction and matching of image signature toolsAmendment 5:2010 (IDT) toNational Standard of CanadaCAN/CSA-ISO/IEC TR 15938-8-04(ISO/IEC TR 15938-8:2002, IDT)NOT FOR RESALE

2、.PUBLICATION NON DESTINE LA REVENTE.CSA Standards Update ServiceAmendment 5:2010 toCAN/CSA-ISO/IEC TR 15938-8-04December 2010Title:Information technology Mul timedia content description interface Part 8: Extraction and use of MPEG-7 descriptions AMENDMENT 5: Extraction and matching of image signatur

3、e toolsPagination:9 pages (iii preliminary and 6 text)To register for e-mail notification about any updates to this publicationgo to www.shopcsa.caclick on E-mail Services under MY ACCOUNTclick on CSA Standards Update ServiceThe List ID that you will need to register for updates to this publication

4、is 2416193.If you require assistance, please e-mail techsupportcsa.ca or call 416-747-2233.Visit CSAs policy on privacy at www.csagroup.org/legal to find out how we protect your personal information.Reference numberISO/IEC TR 15938-8:2002/Amd.5:2010(E)ISO/IEC 2010TECHNICAL REPORT ISO/IECTR15938-8Fir

5、st edition2002-12-15AMENDMENT 52010-03-15Information technology Multimedia content description interface Part 8: Extraction and use of MPEG-7 descriptions AMENDMENT 5: Extraction and matching of image signature tools Technologies de linformation Interface de description du contenu multimdia Partie 8

6、: Extraction et utilisation des descriptions MPEG-7 AMENDEMENT 5: Extraction et correspondance des outils de signature dimage ISO/IEC TR 15938-8:2002/Amd.5:2010(E) PDF disclaimer This PDF file may contain embedded typefaces. In accordance with Adobes licensing policy, this file may be printed or vie

7、wed but shall not be edited unless the typefaces which are embedded are licensed to and installed on the computer performing the editing. In downloading this file, parties accept therein the responsibility of not infringing Adobes licensing policy. The ISO Central Secretariat accepts no liability in

8、 this area. Adobe is a trademark of Adobe Systems Incorporated. Details of the software products used to create this PDF file can be found in the General Info relative to the file; the PDF-creation parameters were optimized for printing. Every care has been taken to ensure that the file is suitable

9、for use by ISO member bodies. In the unlikely event that a problem relating to it is found, please inform the Central Secretariat at the address given below. COPYRIGHT PROTECTED DOCUMENT ISO/IEC 2010 All rights reserved. Unless otherwise specified, no part of this publication may be reproduced or ut

10、ilized in any form or by any means, electronic or mechanical, including photocopying and microfilm, without permission in writing from either ISO at the address below or ISOs member body in the country of the requester. ISO copyright office Case postale 56 CH-1211 Geneva 20 Tel. + 41 22 749 01 11 Fa

11、x + 41 22 749 09 47 E-mail copyrightiso.org Web www.iso.org ii ISO/IEC 2010 All rights reservedAmendment 5:2010 to CAN/CSA-ISO/IEC TR 15938-8-04ISO/IEC TR 15938-8:2002/Amd.5:2010(E) ISO/IEC 2010 All rights reserved iiiForeword ISO (the International Organization for Standardization) and IEC (the Int

12、ernational Electrotechnical Commission) form the specialized system for worldwide standardization. National bodies that are members of ISO or IEC participate in the development of International Standards through technical committees established by the respective organization to deal with particular

13、fields of technical activity. ISO and IEC technical committees collaborate in fields of mutual interest. Other international organizations, governmental and non-governmental, in liaison with ISO and IEC, also take part in the work. In the field of information technology, ISO and IEC have established

14、 a joint technical committee, ISO/IEC JTC 1. International Standards are drafted in accordance with the rules given in the ISO/IEC Directives, Part 2. The main task of the joint technical committee is to prepare International Standards. Draft International Standards adopted by the joint technical co

15、mmittee are circulated to national bodies for voting. Publication as an International Standard requires approval by at least 75 % of the national bodies casting a vote. Attention is drawn to the possibility that some of the elements of this document may be the subject of patent rights. ISO and IEC s

16、hall not be held responsible for identifying any or all such patent rights. Amendment 5 to ISO/IEC TR 15938-8:2002 was prepared by Technical Committee ISO/IEC JTC 1, Information technology, Subcommittee SC 29, Coding of audio, picture, multimedia and hypermedia information. Amendment 5:2010 to CAN/C

17、SA-ISO/IEC TR 15938-8-04ISO/IEC TR 15938-8:2002/Amd.5:2010(E) ISO/IEC 2010 All rights reserved 1Information technology Multimedia content description interface Part 8: Extraction and use of MPEG-7 descriptions AMENDMENT 5: Extraction and matching of image signature tools Add after 4.8: 4.9 Visual Si

18、gnatures 4.9.1 Image Signature The visual content descriptors in ISO/IEC 15938-3 clauses 6 to 9 are very useful when trying to find images with similar content. However, such descriptors are intended to be general and are found to be unsuitable for the task of finding duplicate images. The image sig

19、nature descriptor is robust (unchanging) across a wide range of common editing operations, but is sufficiently different for every item of “original“ content to identify it uniquely and reliably just like human fingerprints. There are three components within the image signature, the first two are gl

20、obal signatures, representing the complete image and the third is composed of a set of local signatures, each representing part of the image. 4.9.1.1 Feature Extraction 11.3.5 and 11.3.6 of ISO/IEC 15938-3:2002/Amd.3:2009 describe the extraction of the image signature. 4.9.1.2 Similarity Matching 4.

21、9.1.2.1 Global Signatures To perform matching between two global signatures 1B and 2B both of length N, the Hamming distance should be taken: 12 1 2(, )H BB B B=, where denotes the exclusive OR (XOR) operator. This can be normalised to the range 0-1 using the normalised Hamming distance: 12 1 21(, )

22、H BB B BN=. Evaluation on test data has shown that for independent images a Hamming distance 12(, )H BB of 147 corresponds to a false alarm rate of less than 0.05 parts per million (ppm). A distance of 169 corresponds to a false alarm rate of 1 ppm. Amendment 5:2010 to CAN/CSA-ISO/IEC TR 15938-8-04I

23、SO/IEC TR 15938-8:2002/Amd.5:2010(E) 2 ISO/IEC 2010 All rights reserved4.9.1.2.2 Local Signatures 1. Form hypotheses of 3 featuresUse 32 out of 80 features2. Apply Geometric ConstraintsFeature direction & ratio of line length3. Form hypotheses of 4 featuresUse all 80 features4. Apply Geometric Const

24、raintRatio of areasFigure AMD5.1 Feature matching is carried out in a four stage process which combines hypothesis forming (using the local signature) and geometric constraints Matching images can be performed by comparing the local signatures which form a part of the image signature. For efficiency

25、 four stages can be used, as shown in Figure AMD5.1, to match local signatures from a pair of images. Hypotheses can be formed in stages one and three. A series of geometric test are performed in stages two and four, these tests should be passed in order for a hypothesis to progress to the next stag

26、e. The stages become increasingly computationally complex so each stage aims to minimise the number of hypotheses that are accepted for subsequent processing. The first stage involves forming hypotheses for potential matching feature points by comparing the first 32 feature points from a first image

27、 with the first 32 feature points from a second image. To perform matching between feature points the local signatures (1B and 2B ) for the feature points can be compared using the Hamming distance: =2121),( BBBBH . A list of feature point pairs with a Hamming distance less than a predefined thresho

28、ld AT is created. A set of hypotheses (candidate pairs of potentially matching features) is generated by taking all combinations of three pairs of matching feature points from the list. A hypothesis is made up of a set of three pairs of feature points (11 2 2 3 3( , ),( , ),( , )ab ab ab ), where 12

29、3,aaa are feature points from a first image and 123,bbb are feature points from a second image. A set of three pairs of feature points is declared a match if the cumulative Hamming distance between the local signatures, of corresponding feature points, is below a constant threshold BT . The set of h

30、ypotheses is ordered by their cumulative distance, with the lowest distance (i.e. highest likelihood of being a match) first. In order to minimise complexity the number of hypotheses may be limited to the hypotheses corresponding to the lowest distance. A second stage applies geometric constraints t

31、o each hypothesis generated from stage one. Two geometric constraints can be applied to reduce false matches, i) feature direction and ii) the ratio of line lengths. A direction, which is quantized into 16 levels as defined in ISO/IEC 15938-3:2002/Amd.3:2009, is associated with each feature, the dir

32、ection for feature na is denoted an . The difference between angles corresponding to features from the same image is taken to ensure that the angle distance measure is unaffected by a rotation. The distance measure addresses the issue of left-right and top-bottom flip modification as is done here us

33、ing these two measures of angle distance Amendment 5:2010 to CAN/CSA-ISO/IEC TR 15938-8-04ISO/IEC TR 15938-8:2002/Amd.5:2010(E) ISO/IEC 2010 All rights reserved 3()()112 12aa bb = and ()()112 12aa bb =+. Thresholds are applied to the two angle distance measures 11, to test whether they are in allowa

34、ble intervals. Allowable values for the angle distances are given by 1q or 116 16qq + or 1q or 116 16qq +, where q is a constant that can be used to vary the sensitivity to changes of angle. The angle distances may also be found between the other pairs of feature points, for example ()()223 23aa bb

35、= and ()()223 23aa bb = +, ()()33131aa bb = and ()()33131aa bb =+. Using the locations of features selected in each hypothesis a ratio of line lengths between the features is used as a constraint. By 12aa we denote the Euclidean length of the line connecting the location of feature 1a to the locatio

36、n of feature 2a . Three feature points 1a , 2a and 3a are used to find the ratio of lines lengths. Three line length ratios are computed 12113aaLaa= , 23231aaLaa= and 31312aaLaa= . Measures of difference between the line length ratios (123,GGG) for two images A and B are defined as: 11111ABABL LGL L

37、=+, 22222ABABL LGL L=+and 33333ABABL LGL L=+where AnL denotes the nthline length ratio from image A and BnL denotes the nthline length ratio from image B. Two thresholds can be applied to the distance measures, one GT to constrain the magnitude of the individual measures and the other HT to constrai

38、n the sum of pairs of distances (12GG+ ,23GG+ ,13GG+ ). Any hypothesis that fails one or more of the tests described above is removed from the set of valid hypotheses. If after testing all hypotheses the set is empty the images can be declared non-matching. If the hypothesis has passed all tests the

39、n it progresses to the next stage to generate four feature hypotheses. The third stage of matching compares all N features from the first image with all N features from the second image. Now, there is already a hypothesis for three feature pairs so the aim is to find a set of hypotheses with four pa

40、irs, hypotheses that add one more feature to the current three feature pair hypothesis. Potential features are found based on the signature distance as in stage one. The set of hypotheses are ordered by the Hamming distance of the local signatures for the fourth feature. In stage four geometric anal

41、ysis can be carried out on the sets of four feature hypotheses to further reduce false acceptance rates. The ratio of lines used in stage two is invariant to similarity transforms. With four features the invariance can be relaxed to the more general affine transformation by using the ratio of areas

42、as described below. This allows tighter thresholds to be set which accept true matches whilst rejecting false matches. Amendment 5:2010 to CAN/CSA-ISO/IEC TR 15938-8-04ISO/IEC TR 15938-8:2002/Amd.5:2010(E) 4 ISO/IEC 2010 All rights reservedFrom a set of four feature locations 123 4(, , , ),aaaa four

43、 triangles may be constructed (123 234 341 412,aaa aaa aaa aaa), the areas of these triangles can be found from ()11112123131()()A ssaasaasaa= , 1 122331()2saaaaaa=+ , 22223234242()()()A ssaasaasaa= , 2233442()saaaaaa=+ , ()33334341314()()()Assasasa= , 3344113()saaaaa=+ , 44441412424()()()Assasasa=

44、, 4411224()saaa aa=+ . Area ratios can then be calculated as 1122AAA= , and the distances between an area ratio 12A of image A and an area ratio 12B for image B can then be found by ()12 1212 1212 12,ABDA BAB=+. Two thresholds CT and DT should be applied to the set of four area ratio distances betwe

45、en the feature sets. The first threshold rejects hypothesis which have any of the area ratios distance above a first threshold CT . The second rejects hypothesis for which the sum of distances is larger than a threshold DT . Table AMD5.1 Suggested threshold values for feature signature matching Thre

46、shold Suggested Value AT 15 BT 38 CT 0.2 DT 0.55 q 1 GT 0.06 HT 0.1 Amendment 5:2010 to CAN/CSA-ISO/IEC TR 15938-8-04ISO/IEC TR 15938-8:2002/Amd.5:2010(E) ISO/IEC 2010 All rights reserved 54.9.1.2.3 Signature Hashing Figure AMD5.2 Matching global image signatures using the 32 bit hash. A 32 bit hash

47、 of the 512 bit global signatures can offer a significant improvement in search speeds, using the process shown in Figure AMD5.2. A 32 bit hash of the global image signatures can be chosen by numerous methods e.g. i) random selection, ii) by analysing robustness to specific modifications or iii) ana

48、lysing the binary entropy of each bit on a large, independent dataset. By analysing and selecting the highest entropy bits 32 suitable bits are chosen, the bitmask is given below. 0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,

49、0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0