`Volume 110, Number 3, June 2008
`
`ISSN 1077-3142
`
`www.sciencedirect.com
`
`Computer Vision
`and Image
`Understanding
`
`Chief Editor
`Avinash C. Kak
`
`Area Editors
`Narendra Ahuja
`Yiannis Aloimonos
`Robert Bergevin
`Ruud M.Bolle
`Kevin W. Bowyer
`Kim L. Boyer
`Larry S. Davis
`Jan-Olof Eklundh
`Adrian Hilton
`Radu Horaud
`Jonathan J. Hull
`Katsushi Ikeuchi
`Martin D. Levine
`Chung-ShengLi
`Nikos Paragios
`edeiy ae
`Anand Rangarajan
`John K.Tsotsos
`Jayaram K. Udupa
`Baba ©.Vemuri
`Harry Wechsler
`Daphna Weinshall
`
`Available online at
`
`see
`Di
`"6© S :
`e°
`ocienceDirect
`‘
`.
`
`AVIGILON EX. 2022
`IPR2019-00314
`Page 1 of 18
`
`
`
`Computer Vision and Image Understanding WALL aa
`
`Zé
`
`y/
`
`j
`__s'
`
`Volume 110, Number 3, June 2008
`
`Ad
`4
`9
`{
`r\!wN % ‘
`4
`© 2008 Elsevier Inc. All rights reserved.
`\
`This journal and the individual contributions containedin it are protected under copyright by Elsevier Inc., and the following terms and conditions apply to their
`use:
`4
`al
`Photocopying
`Single photocopies ofsingle articles may be made for personal use as allowed by national copyrightlaws. Permissiqnt ot the Publisher and
`paymentofa fee is required for all other photocopying, including multiple or systematic copying, copying for advertising 6pramotional-purposes, resale, andall
`forms of documentdelivery. Special rates are available for educationalinstitutions that wish to make photocopies for nonprofit educational classroom use.
`Permissions may be soughtdirectly from Elsevier's Rights Departmentin Oxford, UK; phone: (+44) 1865 843830; fax: (+44) 1865 853333; e-mail: permissions@
`elsevier.com. Requests may aiso be completed online via the Elsevier home page(http://www.elsevier.com/locate/permissions).
`In the USA, users may clear permissions and make payments through the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, USA;
`phone: (978) 750-8400; fax: (978) 750-4744; and in the UK through the Copyright Licensing Agency Rapid Clearance Service (CLARCS), 90 Tottenham Court
`Road, London W1P OLP, UK;phone: +44 (0)20 7631 5555; fax: +44 (0)20 7631 5500. Other countries mayhave a local reprographic rights agency for payments.
`Derivative Works Subscribers may reproduce tables of contents or preparelists of articles including abstracts for internal circulation within their institutions.
`Permission of the Publisher is required for resale or distribution outside the institution.
`Permission of the Publisher is required for all other derivative works, including compilations and translations.
`
`Electronic Storage or Usage—Permission of the Publisheris required to store or use electronically any material containedin this journal, including any article or
`part of an article.
`Except as outlined above, no part of this publication may be reproduced,stored in a retrieval system, or transmitted in any form or by any means,electronic,
`mechanical, photocopying, recording, or otherwise, without prior written permission ofthe Publisher.
`Address permission requests to the Elsevier Rights Department at the fax and e-mail addresses noted above.
`Notice No responsibility is assumed by the Publisher for any injury and/or damage to persons or property as a matter of productliability, negligence, or
`otherwise, or from any use or operation of any methods, products, instructions, or ideas contained in the material herein. Because of rapid advances in the medical
`sciences, in particular, independentverification of diagnoses and drug dosages should be made.
`Althoughall advertising material is expected to conformto ethical (medical) standards,inclusion in this publication doesnot constitute a guarantee or endorsement
`of the quality or value of such product or of the claims made of it by its manufacturer.
`
`Publication information: Computer Vision and Image Understanding (ISSN 1077-3142). For 2008, Volumes 109-112 (12 issues) are scheduled for publication.
`Subscription prices are available upon request from the Publisher, from the Regional Sales Office nearest you, or from this journal's website (http://www.
`elsevier.com/locate/cviu). Further information is available on this journal and other Elsevier products through Elsevier's website (http://www.elsevier.com).
`Subscriptions are accepted on a prepaid basis only and are entered on a calendar yearbasis. Issues are sent by standard mail (surface within Europe, air delivery
`outside Europe). Priority rates are available upon request. Claims for missing issues should be made within six monthsof the date of dispatch.
`
`USA mailing notice: Computer Vision and Image Understanding (ISSN 1077-3142) is published monthly by Elsevier Inc. (525 B Street, Suite 1900, San
`Diego, CA 92101-4495, USA). Annual subscription price in the USA $1343.00 (valid in North, Central, and South America), includingair speed delivery.
`Periodicals postage paid at San Diego, CA 92199-9602, USA, andat additional mailing offices. USA POSTMASTER: Send changeof address to Computer
`Vision and Image Understanding, Elsevier, Customer Service Department, 6277 Sea Harbor Drive, Orlando, FL 32887-4800, USA.
`
`Orders, claims, and journal inquiries: Please contact the Customer Service Department at the Regional Sales Office nearest you. Orlando: Elsevier,
`Customer Service Department, 6277 Sea Harbor Drive, Orlando, FL 32887-4800, USA; phone: (+ 1) (877) 839 7126 or (+1) (800) 654 2452 [toll-free
`numbers for customers inside USA] or(+ 1) (407) 345 4020 or (+ 1) (407) 345 4000 [customers outside USA]; fax: (+ 1) (407) 363 1354 or (+ 1) (407) 363
`9661; e-mail: usjcs@elsevier.com or elspes@elsevier.com. Amsterdam: Elsevier, Customer Service Department, PO Box 211, 1000 AE Amsterdam, The
`Netherlands; phone: (+31) (20) 4853757; fax: (+31) (20) 4853432; e-mail: nlinfo-f@elsevier.com. Tokyo: Elsevier, Customer Service Department, 4F
`Higashi-Azabu, 1-ChomeBldg., 1-9-15 Higashi-Azabu, Minato-ku, Tokyo 106-0044, Japan; phone: (+ 81) (3) 5561 5037; fax: (+ 81) (3) 5561 5047; e-mail:
`jp.info@elsevier.com. Singapore: Elsevier, Customer Service Department, 3 Killiney Road, #08-01 Winsland HouseI, Singapore 239519; phone: (+65)
`63490222; fax: (+ 65) 67331510; e-mail: asiainfo@elsevier.com.
`
`Authorinquiries: For inquiries relating to the submission ofarticles (including electronic submission whereavailable), please visit this journal’s homepage
`at http://www.clsevier.com/locate/cviu. You can track acceptedarticles at http://www.elsevier.com/trackarticle and set up e-mail alerts to inform you of
`when an article’s status has changed. Also accessible from here is information on copyright, frequently asked questions, and more. For detailed
`instructions on the preparationofelectronic artwork,please visit http://www.elsevier.com/artworkinstructions. Contact details for questions arising after
`acceptance ofan article, especially those relating to proofs, will be provided by the publisher.
`
`Advertising information: Advertising orders and inquiries should be sent to James Kenney, Advertising/Commercial Sales Department, Elsevier Ltd.,
`84 Theobald’s Road, London WC1X 8RR, United Kingdom; phone: +44 (0) 20 7611 4494; fax: +44 (0) 20 7611 4463; e-mail: j.kenney@elsevier.com.
`
`Printed by The Sheridan Press, Hanover, Pennsylvania, United States of America
`63) The paper used in this publication meets the requirements of ANSI/NISO Z39.48-1992 (Permanence of Paper)P
`
`AVIGILON EX, 2022
`
`IPR2019-00314
`Page 2 of 18
`
`AVIGILON EX. 2022
`IPR2019-00314
`Page 2 of 18
`
`
`
`© 2008 Elsevier Inc. All rights reserved.
`
`This journal and the individual contributions contained in it are protected under copyright by Elsevier Inc., and
`the following terms and conditions apply to their use:
`
`Photocopying Single photocopies of single articles may be made for personal use as allowed by national
`copyright
`laws. Permission of the Publisher and payment of a fee is required for all other photocopying.
`including multiple or systematic copying, copying for advertising or promotional purposes, resale, and all forms
`of document delivery. Special rates are available for educationalinstitutions that wish to make photocopies for
`nonprofit educational classroom use.
`Permissions may be sought directly from Elsevier’s Rights Department in Oxford, UK; phone: (+44) 1865
`843830; fax: (444) 1865 853333; e-mail: permissions@elsevier.com. Requests may also be completed online
`via the Elsevier home page (http://www.elsevier.com/locate/permissions).
`In the USA,users may clear permissions and make payments through the Copyright Clearance Center, Inc., 222
`Rosewood Drive, Danvers, MA 01923, USA; phone: (978) 750-8400; fax: (978) 750-4744; and in the UK
`through the Copyright Licensing Agency Rapid Clearance Service (CLARCS), 90 Tottenham Court Road,
`London W1P OLP, UK;phone: +44 (0)20 7631 5555; fax: +44 (0)20 7631 5500. Other countries may have a
`local reprographic rights agency for payments.
`Derivative Works Subscribers may reproducetables of contents or preparelists of articles including abstracts
`for internal circulation within their institutions. Permission ofthe Publisher is required for resale or distribution
`outside the institution.
`
`Permission of the Publisher is required for all other derivative works, including compilationsand translations.
`Electronic Storage or Usage
`Permission of the Publisher is required to store or use electronically any
`material contained in this journal, including anyarticle or part of an article.
`Except as outlined above, no part of this publication may be reproduced, stored in a retrieval system, or
`transmitted in any formor by any means, electronic, mechanical, photocopying, recording, or otherwise, without
`prior written permission of the Publisher.
`Address permission requests to the Elsevier Rights Departmentat the fax and e-mail addresses noted above.
`Notice No responsibility is assumed by the Publisher for any injury and/or damageto persons or property as a
`matter of product liability, negligence, or otherwise, or from any use or operation of any methods, products,
`instructions, or ideas contained in the material herein. Because of rapid advances in the medical sciences, in
`particular, independentverification of diagnoses and drug dosages should be made.
`inclusion in this
`Although all advertising material
`is expected to conform to ethical (medical) standards,
`publication does not constitute a guarantee or endorsement of the quality or value of such product or of the
`claims madeofit by its manufacturer.
`
`AVIGILONEX. 2022
`
`IPR2019-00314
`Page 3 of 18
`
`AVIGILON EX. 2022
`IPR2019-00314
`Page 3 of 18
`
`
`
`
`
`ELSEVIER
`
`Guest Editorial
`
`Computer Vision and Image Understanding
`
`Volume 110, Number3, June 2008
`CONTENTS
`
`Computer Vision
`and Image _
`Understanding
`
`Special issue on Similarity Matching in Computer Vision and Multimedia
`-- Guest Editors: Nicu Sebe, Qi Tian, Michael S. Lew, Thomas S. Huang
`
`Similarity Matching in Computer Vision and Multimedia
`Nicu Sebe, Qi Tian, Michael S. Lew, Thomas S. Huang ......... 20... cece eee eee eee eee eee enee
`
`309
`
`Special Issue Articles
`
`Indexing through laplacian spectra
`M.Fatih Demirci, Reinier H. van Leuken, Remco C. Veltkamp ........... 0... ee eee rece eee ne enee
`
`Strategies for shape matching using skeletons
`Wooi-Boon Goh... 1. cee eee eee eee eee eee eee eee reer ene renee eee eeees
`
`Speeded-Up Robust Features (SURF)
`Herbert Bay, Andreas Ess, Tinne Tuytelaars, Luc Van Gool........... 02. cece eee eee eee reece
`
`Content based video matching using spatiotemporal volumes
`Arslan Basharat, Yun Zhai, Mubarak Shah. ... 2... 2... cee ee ee ee ee eee teen eee eee eee
`
`Anytime similarity measures for faster alignment
`Rupert Brooks, Tal Arbel, Doina Precup......... 2... eee eee ee ee eee ee eee ee eee eee eens
`
`Locally adaptive subspace and similarity metric learning for visual data clustering and retrieval
`Yun Fu, Zhu Li, Thomas S. Huang, Aggelos K. Katsaggelos. . 2... 2... . ce ee cee ee eee eee eee
`
`Combining visual dictionary, kernel-based similarity and learning strategy for image category retrieval
`Philippe Henri Gosselin, Matthieu Cord, Sylvie Philipp-Foliguet.......... 0.0... 0. ee eee eee eee eens
`
`Measuring novelty and redundancy with multiple modalities in cross-lingual broadcast news
`Xiao Wu, Alexander G. Hauptmann, Chong-Wah Ngo... ......... cee eee ee eee ec eee ee eee eens
`
`312
`
`326
`
`346
`
`360
`
`378
`
`390
`
`403
`
`418
`
`
`
`Abstracted/Indexedin abstract and citation database SCOPUS®.Full text available on ScienceDirect®. |
`
`
`
`
`
`
`
`1077-3142(200806)110:3;1-F
`
`ac
`
`
`
`
`
`
`
`
`
`
`
`AVIGILONEX. 2022
`
`IPR2019-00314
`Page 4 of 18
`
`AVIGILON EX. 2022
`IPR2019-00314
`Page 4 of 18
`
`
`
`Available online at www.sciencedirect.com
`
`Computer Vision and Image Understanding 110 (2008) 346–359
`
`www.elsevier.com/locate/cviu
`
`Speeded-Up Robust Features (SURF)
`
`Herbert Bay a, Andreas Ess a,*, Tinne Tuytelaars b, Luc Van Gool a,b
`
`a ETH Zurich, BIWI, Sternwartstrasse 7, CH-8092 Zurich, Switzerland
`b K.U. Leuven, ESAT-PSI, Kasteelpark Arenberg 10, B-3001 Leuven, Belgium
`
`Received 31 October 2006; accepted 5 September 2007
`Available online 15 December 2007
`
`Abstract
`
`This article presents a novel scale- and rotation-invariant detector and descriptor, coined SURF (Speeded-Up Robust Features).
`SURF approximates or even outperforms previously proposed schemes with respect to repeatability, distinctiveness, and robustness,
`yet can be computed and compared much faster.
`This is achieved by relying on integral images for image convolutions; by building on the strengths of the leading existing detectors
`and descriptors (specifically, using a Hessian matrix-based measure for the detector, and a distribution-based descriptor); and by sim-
`plifying these methods to the essential. This leads to a combination of novel detection, description, and matching steps.
`The paper encompasses a detailed description of the detector and descriptor and then explores the effects of the most important param-
`eters. We conclude the article with SURF’s application to two challenging, yet converse goals: camera calibration as a special case of image
`registration, and object recognition. Our experiments underline SURF’s usefulness in a broad range of topics in computer vision.
`Ó 2007 Elsevier Inc. All rights reserved.
`
`Keywords: Interest points; Local features; Feature description; Camera calibration; Object recognition
`
`1. Introduction
`
`The task of finding point correspondences between two
`images of the same scene or object is part of many com-
`puter vision applications. Image registration, camera cali-
`bration, object recognition, and image retrieval are just a
`few.
`The search for discrete image point correspondences can
`be divided into three main steps. First, ‘interest points’ are
`selected at distinctive locations in the image, such as cor-
`ners, blobs, and T-junctions. The most valuable property
`of an interest point detector is its repeatability. The repeat-
`ability expresses the reliability of a detector for finding the
`same physical interest points under different viewing condi-
`tions. Next, the neighbourhood of every interest point is
`represented by a feature vector. This descriptor has to be
`distinctive and at the same time robust to noise, detection
`
`* Corresponding author.
`E-mail address: aess@vision.ee.ethz.ch (A. Ess).
`
`1077-3142/$ - see front matter Ó 2007 Elsevier Inc. All rights reserved.
`doi:10.1016/j.cviu.2007.09.014
`
`displacements and geometric and photometric deforma-
`tions. Finally, the descriptor vectors are matched between
`different images. The matching is based on a distance
`between the vectors, e.g. the Mahalanobis or Euclidean dis-
`tance. The dimension of the descriptor has a direct impact
`on the time this takes, and less dimensions are desirable for
`fast interest point matching. However, lower dimensional
`feature vectors are in general less distinctive than their
`high-dimensional counterparts.
`It has been our goal to develop both a detector and
`descriptor that, in comparison to the state-of-the-art, are
`fast to compute while not sacrificing performance. In order
`to succeed, one has to strike a balance between the above
`requirements like simplifying the detection scheme while
`keeping it accurate, and reducing the descriptor’s size while
`keeping it sufficiently distinctive.
`A wide variety of detectors and descriptors have already
`been proposed in the literature (e.g. [21,24,27,39,25]). Also,
`detailed comparisons and evaluations on benchmarking
`datasets have been performed [28,30,31]. Our fast detector
`and descriptor,
`called SURF (Speeded-Up Robust
`
`AVIGILON EX. 2022
`IPR2019-00314
`Page 5 of 18
`
`
`
`H. Bay et al. / Computer Vision and Image Understanding 110 (2008) 346–359
`
`347
`
`Features), was introduced in [4]. It is built on the insights
`gained from this previous work. In our experiments on
`these benchmarking datasets, SURF’s detector and
`descriptor are not only faster, but the former is also more
`repeatable and the latter more distinctive.
`We focus on scale and in-plane rotation-invariant detec-
`tors and descriptors. These seem to offer a good compromise
`between feature complexity and robustness to commonly
`occurring photometric deformations. Skew, anisotropic
`scaling, and perspective effects are assumed to be second
`order effects, that are covered to some degree by the overall
`robustness of the descriptor. Note that the descriptor can
`be extended towards affine-invariant regions using affine
`normalisation of the ellipse (cf. [31]), although this will have
`an impact on the computation time. Extending the detector,
`on the other hand, is less straightforward. Concerning the
`photometric deformations, we assume a simple linear model
`with a bias (offset) and contrast change (scale factor). Nei-
`ther detector nor descriptor use colour information.
`The article is structured as follows. In Section 2, we give
`a review over previous work in interest point detection and
`description. In Section 3, we describe the strategy applied
`for fast and robust interest point detection. The input
`image is analysed at different scales in order to guarantee
`invariance to scale changes. The detected interest points
`are provided with a rotation and scale-invariant descriptor
`in Section 4. Furthermore, a simple and efficient first-line
`indexing technique, based on the contrast of the interest
`point with its surrounding, is proposed.
`In Section 5, some of the available parameters and their
`effects are discussed, including the benefits of an upright
`version (not invariant to image rotation). We also investi-
`gate SURF’s performance in two important application
`scenarios. First, we consider a special case of image regis-
`tration, namely the problem of camera calibration for 3D
`reconstruction. Second, we will explore SURF’s applica-
`tion to an object recognition experiment. Both applications
`highlight SURF’s benefits in terms of speed and robustness
`as opposed to other strategies. The article is concluded in
`Section 6.
`
`2. Related work
`
`2.1. Interest point detection
`
`The most widely used detector is probably the Harris
`corner detector [15], proposed back in 1988. It is based
`on the eigenvalues of the second moment matrix. However,
`Harris corners are not scale invariant. Lindeberg [21] intro-
`duced the concept of automatic scale selection. This allows
`to detect interest points in an image, each with their own
`characteristic scale. He experimented with both the deter-
`minant of the Hessian matrix as well as the Laplacian
`(which corresponds to the trace of the Hessian matrix) to
`detect blob-like structures. Mikolajczyk and Schmid [26]
`refined this method, creating robust and scale-invariant
`feature detectors with high repeatability, which they coined
`
`Harris-Laplace and Hessian-Laplace. They used a (scale-
`adapted) Harris measure or the determinant of the Hessian
`matrix to select the location, and the Laplacian to select the
`scale. Focusing on speed, Lowe [23] proposed to approxi-
`mate the Laplacian of Gaussians (LoG) by a Difference
`of Gaussians (DoG) filter.
`Several other scale-invariant interest point detectors
`have been proposed. Examples are the salient region detec-
`tor, proposed by Kadir and Brady [17], which maximises
`the entropy within the region, and the edge-based region
`detector proposed by Jurie and Schmid [16]. They seem less
`amenable to acceleration though. Also several affine-invari-
`ant feature detectors have been proposed that can cope
`with wider viewpoint changes. However, these fall outside
`the scope of this article.
`From studying the existing detectors and from published
`comparisons [29,30], we can conclude that Hessian-based
`detectors are more stable and repeatable than their Harris-
`based counterparts. Moreover, using the determinant of
`the Hessian matrix rather than its trace (the Laplacian)
`seems advantageous, as it fires less on elongated, ill-localised
`structures. We also observed that approximations like the
`DoG can bring speed at a low cost in terms of lost accuracy.
`
`2.2. Interest point description
`
`An even larger variety of feature descriptors has been
`proposed, like Gaussian derivatives [11], moment invari-
`ants
`[32], complex features
`[1],
`steerable filters
`[12],
`phase-based local features [6], and descriptors representing
`the distribution of smaller-scale features within the interest
`point neighbourhood. The latter, introduced by Lowe [24],
`have been shown to outperform the others [28]. This can be
`explained by the fact that they capture a substantial
`amount of information about the spatial intensity patterns,
`while at the same time being robust to small deformations
`or localisation errors. The descriptor in [24], called SIFT
`for short, computes a histogram of local oriented gradients
`around the interest point and stores the bins in a 128D vec-
`tor (8 orientation bins for each of 4 4 location bins).
`Various refinements on this basic scheme have been pro-
`posed. Ke and Sukthankar [18] applied PCA on the gradi-
`ent image around the detected interest point. This PCA-
`SIFT yields a 36D descriptor which is fast for matching,
`but proved to be less distinctive than SIFT in a second
`comparative study by Mikolajczyk and Schmid [30]; and
`applying PCA slows down feature computation. In the
`same paper [30], the authors proposed a variant of SIFT,
`called GLOH, which proved to be even more distinctive
`with the same number of dimensions. However, GLOH is
`computationally more expensive as it uses again PCA for
`data compression.
`The SIFT descriptor still seems the most appealing
`descriptor for practical uses, and hence also the most
`widely used nowadays. It is distinctive and relatively fast,
`which is crucial for on-line applications. Recently, Se
`et al. [37] implemented SIFT on a Field Programmable
`
`AVIGILON EX. 2022
`IPR2019-00314
`Page 6 of 18
`
`
`
`348
`
`H. Bay et al. / Computer Vision and Image Understanding 110 (2008) 346–359
`
`Gate Array (FPGA) and improved its speed by an order of
`magnitude. Meanwhile, Grabner et al. [14] also used inte-
`gral images to approximate SIFT. Their detection step is
`based on difference-of-mean (without interpolation), their
`description step on integral histograms. They achieve
`about the same speed as we do (though the description step
`is constant in speed), but at the cost of reduced quality
`compared to SIFT. Generally, the high dimensionality of
`the descriptor is a drawback of SIFT at the matching step.
`For on-line applications relying only on a regular PC, each
`one of the three steps (detection, description, matching) has
`to be fast.
`An entire body of work is available on speeding up the
`matching step. All of them come at the expense of getting
`an approximative matching. Methods include the best-
`bin-first proposed by Lowe [24], balltrees [35], vocabulary
`trees [34], locality sensitive hashing [9], or redundant bit
`vectors [13]. Complementary to this, we suggest the use
`of the Hessian matrix’s trace to significantly increase the
`matching speed. Together with the descriptor’s low dimen-
`sionality, any matching algorithm is bound to perform
`faster.
`
`3. Interest point detection
`
`Our approach for interest point detection uses a very
`basic Hessian matrix approximation. This lends itself to
`the use of integral images as made popular by Viola and
`Jones [41], which reduces the computation time drastically.
`Integral images fit in the more general framework of box-
`lets, as proposed by Simard et al. [38].
`
`3.1. Integral images
`
`Fig. 1. Using integral images, it takes only three additions and four
`memory accesses to calculate the sum of intensities inside a rectangular
`region of any size.
`
`o2
`
`;
`
`ð2Þ
`
`determinant of the Hessian also for the scale selection, as
`done by Lindeberg [21].
`Given a point x ¼ ðx; yÞ in an image I, the Hessian
`
`
`matrix Hðx; rÞ in x at scale r is defined as follows
`Hðx; rÞ ¼ Lxxðx; rÞ Lxyðx; rÞ
`Lxyðx; rÞ Lyyðx; rÞ
`where Lxxðx; rÞ is the convolution of the Gaussian second
`ox2 gðrÞ with the image I in point x, and
`order derivative
`similarly for Lxyðx; rÞandLyyðx; rÞ.
`Gaussians are optimal for scale-space analysis [19,20],
`but in practice they have to be discretised and cropped
`(Fig. 2,
`left half). This leads to a loss in repeatability
`under image rotations around odd multiples of p
`4. This
`weakness holds for Hessian-based detectors in general.
`Fig. 3 shows the repeatability rate of
`two detectors
`based on the Hessian matrix for pure image rotation.
`The repeatability attains a maximum around multiples
`of p
`2. This is due to the square shape of the filter. Nev-
`ertheless, the detectors still perform well, and the slight
`decrease in performance does not outweigh the advan-
`tage of fast convolutions brought by the discretisation
`and cropping. As real filters are non-ideal in any case,
`and given Lowe’s success with his LoG approximations,
`we push the approximation for the Hessian matrix even
`further with box filters (in the right half of Fig. 2).
`These approximate second order Gaussian derivatives
`and can be evaluated at a very low computational cost
`
`Fig. 2. Left to right: The (discretised and cropped) Gaussian second order
`partial derivative in y- (Lyy ) and xy-direction (Lxy), respectively; our
`approximation for the second order Gaussian partial derivative in y- (Dyy)
`and xy-direction (Dxy ). The grey regions are equal to zero.
`
`ð1Þ
`
`In order to make the article more self-contained, we
`briefly discuss the concept of integral images. They allow
`for fast computation of box type convolution filters. The
`entry of an integral image I RðxÞ at a location x ¼ ðx; yÞT
`represents the sum of all pixels in the input image I within
`a rectangular region formed by the origin and x.
`6y
`6x
`
`Iði; jÞ
`
`Xj
`Xi
`
`i¼0
`
`j¼0
`
`I RðxÞ ¼
`
`Once the integral image has been computed, it takes
`three additions to calculate the sum of the intensities over
`any upright, rectangular area (see Fig. 1). Hence, the calcu-
`lation time is independent of its size. This is important in
`our approach, as we use big filter sizes.
`
`3.2. Hessian matrix-based interest points
`
`We base our detector on the Hessian matrix because of
`its good performance in accuracy. More precisely, we
`detect blob-like structures at locations where the determi-
`nant is maximum. In contrast to the Hessian-Laplace
`detector by Mikolajczyk and Schmid [26], we rely on the
`
`AVIGILON EX. 2022
`IPR2019-00314
`Page 7 of 18
`
`
`
`H. Bay et al. / Computer Vision and Image Understanding 110 (2008) 346–359
`
`349
`
`3.3. Scale space representation
`
`Interest points need to be found at different scales, not
`least because the search of correspondences often requires
`their comparison in images where they are seen at different
`scales. Scale spaces are usually implemented as an image
`pyramid. The images are repeatedly smoothed with a
`Gaussian and then sub-sampled in order to achieve a
`higher level of the pyramid. Lowe [24] subtracts these pyr-
`amid layers in order to get the DoG (Difference of Gaussi-
`ans) images where edges and blobs can be found.
`Due to the use of box filters and integral images, we do
`not have to iteratively apply the same filter to the output of
`a previously filtered layer, but instead can apply box filters
`of any size at exactly the same speed directly on the original
`image and even in parallel (although the latter is not
`exploited here). Therefore, the scale space is analysed by
`up-scaling the filter size rather than iteratively reducing
`the image size, Fig. 4. The output of the 9 9 filter, intro-
`duced in previous section, is considered as the initial scale
`layer, to which we will refer as scale s ¼ 1:2 (approximating
`Gaussian derivatives with r ¼ 1:2). The following layers
`are obtained by filtering the image with gradually bigger
`masks, taking into account the discrete nature of integral
`images and the specific structure of our filters.
`Note that our main motivation for this type of sampling
`is its computational efficiency. Furthermore, as we do not
`have to downsample the image, there is no aliasing. On
`the downside, box filters preserve high-frequency compo-
`nents that can get lost in zoomed-out variants of the same
`scene, which can limit scale-invariance. This was however
`not noticeable in our experiments.
`The scale space is divided into octaves. An octave repre-
`sents a series of filter response maps obtained by convolv-
`ing the same input image with a filter of increasing size. In
`total, an octave encompasses a scaling factor of 2 (which
`implies that one needs to more than double the filter size,
`see below). Each octave is subdivided into a constant num-
`ber of scale levels. Due to the discrete nature of integral
`images, the minimum scale difference between two subse-
`quent scales depends on the length l0 of the positive or neg-
`ative lobes of the partial second order derivative in the
`direction of derivation (x or y), which is set to a third of
`the filter size length. For the 9 9 filter, this length l0 is
`3. For two successive levels, we must increase this size by
`
`Fig. 4. Instead of iteratively reducing the image size (left), the use of
`integral images allows the up-scaling of the filter at constant cost (right).
`
`Fig. 3. Top: Repeatability score for image rotation of up to 180°. Hessian-
`based detectors have in general a lower repeatability score for angles
`around odd multiples of p
`4. Bottom: Sample images from the sequence that
`was used. Fast-Hessian is the more accurate version of our detector (FH-
`15), as explained in Section 3.3.
`
`images. The calculation time therefore is
`using integral
`independent of the filter size. As shown in Section 5
`and Fig. 3, the performance is comparable or better
`than with the discretised and cropped Gaussians.
`The 9 9 box filters in Fig. 2 are approximations of a
`Gaussian with r ¼ 1:2 and represent the lowest scale (i.e.
`highest spatial resolution) for computing the blob response
`maps. We will denote them by Dxx, Dyy, and Dxy. The
`weights applied to the rectangular regions are kept simple
`for computational efficiency. This yields
`ð3Þ
`detðHapproxÞ ¼ DxxDyy ðwDxyÞ2:
`The relative weight w of the filter responses is used to bal-
`ance the expression for the Hessian’s determinant. This is
`needed for the energy conservation between the Gaussian
`kernels and the approximated Gaussian kernels,
`w ¼ j Lxyð1:2ÞjF j Dyyð9ÞjF
`ð4Þ
`¼ 0:912::: ’ 0:9;
`j Lyyð1:2ÞjF j Dxyð9ÞjF
`where j xjF is the Frobenius norm. Notice that for theoret-
`ical correctness, the weighting changes depending on the
`scale. In practice, we keep this factor constant, as this did
`not have a significant
`impact on the results in our
`experiments.
`Furthermore, the filter responses are normalised with
`respect to their size. This guarantees a constant Frobenius
`norm for any filter size, an important aspect for the scale
`space analysis as discussed in the next section.
`The approximated determinant of the Hessian repre-
`sents the blob response in the image at location x. These
`responses are stored in a blob response map over different
`scales, and local maxima are detected as explained in Sec-
`tion 3.4.
`
`AVIGILON EX. 2022
`IPR2019-00314
`Page 8 of 18
`
`
`
`350
`
`H. Bay et al. / Computer Vision and Image Understanding 110 (2008) 346–359
`
`a minimum of 2 pixels (1 pixel on every side) in order to
`keep the size uneven and thus ensure the presence of the
`central pixel. This results in a total increase of the mask size
`by 6 pixels (see Fig. 5). Note that for dimensions different
`from l0 (e.g. the width of the central band for the vertical
`filter in Fig. 5), rescaling the mask introduces rounding-
`off errors. However, since these errors are typically much
`smaller than l0, this is an acceptable approximation.
`The construction of the scale space starts with the 9 9
`filter, which calculates the blob response of the image for
`scale. Then, filters with sizes 15 15,
`the smallest
`21 21, and 27 27 are applied, by which even more than
`a scale change of two has been achieved. But this is needed,
`as a 3D non-maximum suppre