IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. XX, NO. YY, OCTOBER ZZZZ 1

An Improved Curvature ScaleSpace Corner Detector and a Robust Corner Matching Approach for Transformed Image Identification

Mohammad Awrangjeb*, Member, IEEE, and Guojun Lu, Senior Member, IEEE Monash University, Australia. Phone: +61 3 5122 6138, Fax: +61 3 5122 6879 Email: {Mohammad.Awrangjeb, Guojun.Lu}@infotech.monash.edu.au

Abstract— There are many applications, such as image copy right protection, where transformed images of a given test image need to be identified. The solution to this identification problem consists of two main stages. In stage one, certain representative features, such as corners, are detected in all images. In stage two, the representative features of the test image and the stored images are compared to identify the transformed images for the test image. Curvature scalespace (CSS) corner detectors look for curvature maxima or inflection points on planar curves. However, the arclength used to parameterize the planar curves by the existing CSS detectors is not invariant to geometric transformations such as scaling. As a solution to stage one, this paper presents an improved CSS corner detector using the affinelength parameterization which is relatively invariant to affine transformations. We then present an improved corner matching technique as a solution to the stage two. Finally, we apply the proposed corner detection and matching techniques to identify the transformed images for a given image and report the promising results.

Index Terms— corner detection, corner matching, curvature scalespace, affinelength, transformed image identification.

EDICS: OTHMAPP Multimedia applications, SREOTHR Other, and OTHOTHR Other.

I. INTRODUCTION

I

N many applications, such as image copyright protection [1], one common problem is to identify images which may have undergone unknown transformations. We can define this common problem as the transformed image identification (TII) where the goal is to identify geometric transformed and signal processed images for a given image. So the TII is different from conventional contentbased image retrieval (CBIR) [2], where all images having the same or similar semantic feature, e.g., flower, are considered relevant to each other. The TII consists of two main stages: feature detection and feature matching. In the feature detection stage, a set of representative features, e.g., corners, are detected and represented for all images. In the feature matching stage, the representative features of the test image and the stored images are compared to identify the transformed images for the test image. We will focus on both of the stages of the TII in this paper. In addition, we will concentrate on the performance evaluation metrics.

*corresponding author.

A. Feature Detection

The most challenging problem in current research on image copyright protection is to devise a system that would verify the copyright information in the test image even when the image has undergone unknown geometric transformations. In image copyright protection, some pixels in the original image are used either to calculate the signature [1] or to embed the watermark [3]. However, geometric transformations change the location of those pixels. Consequently, the copyright verifier may fail to track the copyright information in the transformed (test) image. In such cases, if the locations of those pixels are defined with respect to some salient features, e.g., corners which are robust to geometric transformations, the verifier will be able to locate those pixels. Such salient features can be denoted as the reference points to those pixels.

Different types of image features, e.g., corners [3], wavelet maxima points [4], have been extensively used in the last decade in order to obtain robust watermarkingbased copyright protection systems. Corners are visually distinguishable and well localized compared to other image features. The wavelet maximabased watermarking system in [4] could survive only on small geometric distortions, e.g., 2^◦rotation. The reason is that the wavelet features are highly sensitive to geometric operations. In contrast, the cornerbased watermarking system in [3] was shown robust to large geometric distortions.

The featurepoints can also be used to devise blind signaturebased copyright protection system [1]. A corner matching technique can be used to identify the transformed images for a given test image. The transformation matrix can also be estimated to undo the transformation if necessary. In the identified transformed images the signature area can be located using the reference points (corners).

A large number of corner and interestpoint detectors have been proposed in the literature [5]–[10]. They can be broadly classified into three groups: intensitybased [5]–[7], contour based [8]–[10], and modelbased [11], [12] methods. Intensity based methods estimate a measure which is intended to indicate the presence of an interestpoint directly from the image pixel values. Contourbased methods first obtain planar curves using some edge detector and then search for the curvature maxima along those curves. Model or template based methods find corners by fitting the image signal into a predefined model. Corner detectors can also be divided into

IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. XX, NO. YY, OCTOBER ZZZZ 2

two types: singlescale detectors [5] and multiscale detectors [6]–[10]. Singlescale detectors work well if the image has similar size features, but ineffective otherwise; because either fine or coarse scale feature is poorly detected, but images may contain both kinds of features. To improve the effectiveness of corner detection, multiscale corner detectors have been proposed. They are based on the classical scalespace theory [13]–[16].

In this paper, we will focus on the contourbased multiscale corner detectors which are commonly known as curvature scalespace (CSS) detectors. One of the main reasons why we choose the contourbased methods is that along with the detected corners, the contourbased methods make other information, like the curvature zerocrossing points and edges, available for later applications. A corner matching technique based on the available information from the corner detector can be used to identify the transformed images for a given test image. The transformation matrix can also be estimated to undo the transformation if necessary.

The CSS corner detectors look for curvature maxima or inflection points on planar curves. The original CSS detectors [8], [9] and the enhanced version [10] parameterize curves using the arclength which is not invariant to geometric transformations. This paper presents an improved CSS corner detector which is affineresilient (ARCSS detector). A prelim inary version of the ARCSS corner detector was published in [17]. Here we will detail each step of this corner detector (see Section IIB) and present the detailed experimental results (see Section VB.1). The proposed corner detector parameterizes curves with the affinelength which is relatively invariant to affine transformations. A function f is called relatively invariant to a transformation group G if whenever f is transformed to F by a transformation g in G, we obtain F = z.f, where z is a function of g alone. If z ≡1 for all g in G, f is called absolutely invariant [15]. For more detail and rigorous discussions see [18].

Note that the affinelength has been used for affine invariant shape recognitions in the literature [19], [20]. The corner detector and matching technique proposed in this paper are different from them in two aspects. First, existing techniques match shapes using the so called CSS image (see [19] and [20]) and do not explicitly use corner positions for matching. However, we explicitly obtain corner positions on planar curves and use them for matching. Second, their formula of curvature calculation uses up to third order derivatives which has the undesirable effects, since precise approximation of higher order derivatives is a difficult task and often causes instability and errors [19]. In this paper, we will simplify the formula so that only up to secondorder derivatives are used (see Section IIB.1).

B. Feature Matching

The feature (corner) matching technique is normally com putationally intensive and difficult due to following reasons: first, additional corners may be detected in the test image due to noise or clutter; second, desirable corners may be missed in the test image due to noise or occlusion; and finally, the

corner strength represented as some numerical values may be changed by transformations [21]. Although a significant number of solutions have been proposed to this problem, none is general and reliable enough to cope with all possible cases [22].

Corner matching techniques can be broadly classified into two groups. In the first group, each corner is associated with its local neighbourhood and the matching procedure involves neighbourhood matching [6], [23]. These techniques are robust but computationally expensive and require large storage for descriptors. In the second group, each corner is associated with information like its curvature but do not use neighbourhood intensity values for matching [22], [24]–[29]. These techniques are computationally less expensive and require less storage for descriptors.

This paper presents a corner matching technique which be longs to the second category and is robust to geometric trans formations, noising, and lossy compression. We first find the candidate corner matches between two images using absolute curvature values at corner points and affinelengths between corners on the same curve. For each set of three candidate matches, if they are noncollinear on each image and the ratio of areas of corresponding triangles in both of the images is within a specific range, we estimate the transformation matrix between these triangles. Then we transform all corners in the database image using the estimated transformation matrix and match with the test corner set. In rest of the paper, we will call the proposed matching technique as affinelength and triangular area (ALTA) matching technique. Note that a preliminary version of the ALTA matching technique with some initial experimental results was published in [30]. Here we improve it by proposing some speed up steps (see Section IIIB.1), discuss detailed matching results on a large database (see Section VB.2), and present the TII performance (see Section VB.3).

C. Performance Measurements

The existing CSS detectors [8]–[10], [31] did not use proper evaluation metrics for performance evaluation (see Section IVA). They were evaluated based on the human judgement which is hard to establish. Moreover, existing work on matching techniques [22], [24]–[29] did not evaluate and compare their performance using large databases. For the evaluation of corner detection performance, we propose a modified corner matching metric (see average repeatability in Section IVC.1). We carry out a thorough robustness study on large databases considering a wide range of geometric transformations. We evaluate the corner detection performance using average repeatability and localization error. Corner matching performance is evaluated using corner correspon dence and compared with the performance of the existing most promising Delaunay triangulations based matching technique [22]. Finally, the combined performance of the proposed ARCSS corner detector and the ALTA matching technique is evaluated when they are applied to TII. Their combined performance which we call the identification performance in rest of the paper is evaluated using the precisionrecall graph

IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. XX, NO. YY, OCTOBER ZZZZ 3

and compared with the performance of the existing grayscale histogram (GSH) matching technique [2].

Note that corners and edges approximate multiple object shapes in an image and, therefore, our corner matching tech nique using the affinelength between corners on the same curve is somewhat like a global feature matching technique. Many existing CBIR techniques [2] may not be applicable to TII, since the goal of the CBIR is different from that of TII. The GSH matching, which is a global feature (intensity) based CBIR technique, is highly robust to geometric transformations [2], and therefore, is chosen to be compared with the pro posed corner matching technique. Moreover, the shapebased recognition techniques [19], [20] may not be applicable to TII, since they require automatic, efficient, and reliable image segmentation techniques to extract closed contours of multiple objects in the same image. However, it may be impossible since objects in images may be strongly noised, occluded, or cluttered.

D. Paper Organization

The rest of the paper is organized as follows. The existing CSS corner detectors along with the proposed improved corner detector are presented in Section II. Section III presents the existing corner matching techniques and the proposed ALTA matching technique. Section IV presents the performance evaluation metrics. Section V presents the performance study. Finally, Section VI concludes the paper.

II. CURVATURE SCALESPACE CORNER DETECTORS

The CSS corner detectors, in general, extract planar curves (open and close contours) from the image using the Canny edge detector [32] and parameterize each curve using the arclength. They then smooth the parameterized curve and calculate the absolute curvature on each point of the smoothed curve at either all scales [8], one [9], or more specific scales [10]. Thereafter, they look for curvature maxima points as corners based on some constraints. If corners are detected at all scales, those which survive in most of the scales are selected [8]. If corners are detected at some specific scales, they are tracked down to the finest scale to improve localization [9], [10].

Since the arclength of a curve is not preserved under geometric transformations like scaling, the existing CSS de tectors [8]–[10], [31] are vulnerable to geometric attacks. The proposed ARCSS corner detector uses the affinelength parameterization which is relatively invariant to affine trans formations.

A. Existing Corner Detectors

The first CSS corner detector by Rattarangsi and Chin [8] analyzed the scalespace of the isolated single and double corners. It had two main drawbacks: high computational complexity because of involving a tree parsing technique and false corner detection due to quantization noise.

The next CSS corner detector by Mokhtarian and Suomela [9] detected corners at a high scale in the CSS using a single

curvaturethreshold and tracked them through multiple lower scales to the lowest scale in order to improve localization. When corners were detected in a very high scale, this method showed high robustness to noise but many true corners were smoothed away. On the other hand, if corners were detected in a low scale it detected many weak corners. Moreover, its performance was limited due to the use of the single threshold with the single smoothing scale, since the curvature value of a point may change when the image is geometrically transformed.

To alleviate these problems, Mokhtarian and Mohanna [10] later proposed the enhanced CSS corner detector where cor ners were detected in multiple (three) scales with different thresholds. In the remaining of this paper, we refer their former method [9] as the CSS detector and later one [10] as the ECSS detector. The ECSS detector, though performed better as they reported in [31], was found less robust than the CSS detector in our robustness tests (see Section VB.1). The corner detector in [33] did not use the scalespace, though the title seemed to be. In fact, it detected corners at a single low scale and did not track to the finest scale. Consequently, it might detect weak corners and suffer from localization problem.

B. Proposed Improved Corner Detector

The arclength was used to parameterize the planar curves by both the existing CSS and ECSS detectors [9], [10]. How ever, the arclength is not invariant to affine transformations. In order to overcome this problem, the arclength was replaced by the affinelength which is relatively invariant to affine transformations [19].

The main difference between the arclength and the affine length parameterizations of planar curves is in sampling. The arclength parameterization used by both the existing CSS and ECSS detectors [9], [10] selects all the points on a curve when the sampleinterval is either 1 (for vertical or horizontal neighbor points) or √

2 (for diagonal neighbor points) pixels. However, as the arclength of a curve is not invariant to geometric transformations, a substantially different set of curve points is selected from the transformed curve when the arclength parameterization is used. In contrast, the affine length parameterization selects only the important points of a curve. It selects more points on the curve segments where the curve makes significant direction changes (e.g., on and near corners) than on the straightline like curve segments. Since the affinelength of a curve is relatively invariant to geometric transformations, it is expected that the affinelength parameter ized curve is more stable and, therefore, leads to more stable curvature estimation than the arclength parameterized curve.

Nevertheless, while the arclength parameterized curvature involves up to second order derivatives [8]–[10], [31], the formula used by [19], [20] to calculate the affinelength param eterized curvature used third order derivatives. We will show below using simple mathematical derivation that the affine length parameterized curvature can also be implemented using second order derivatives like the arclength parameterized curvature. Therefore, the affinelength parameterized curvature can be exploited to extract robust corners with the same

IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. XX, NO. YY, OCTOBER ZZZZ 4

computational cost as the arclength parameterized curvature requires, but with higher accuracy and stability. 1) AffineLength Parameterized Curvature: In this section, we first present the affinelength parameterized curvature func tion which uses up to third order derivatives of original curve point locations. We then simplify it to have only up to second order derivatives. Lower order derivatives help reducing the undesirable effects, e.g., instability and inaccuracy in curvature estimation, associated with higher order derivatives.

For a planar curve Γ(t) = (x(t), y(t)), where t is an arbi trary parameter, the affinelength τ between two points P1 and P2 is [17]

τ = Z P2

P1

3 p

˙ x(t)¨ y(t) −¨ x(t) ˙ y(t)dt, (1)

where ˙ x(t) and ˙ y(t) are first and ¨ x(t) and ¨ y(t) are second order derivatives with respect to t. We can easily show that the affinelength τa of an affine transformed curve is

τa = τ0[sxsy(1 −shxshy)]^1/3, (2)

where τ0 is the affinelength of the original curve, sx and sy are scaling factors and shx and shy are shearing factors along x and y directions respectively. The relation in (2) shows that the affinelength of a curve is absolutely invariant to rotation and translation, but relatively invariant to scaling and shearing. Such a relation does not exist for the arclength of a curve. That means the arclength is not invariant to scaling and shearing, though it is absolutely invariant to rotation and translation [19]. The Euclidean curvature is defined as [8]– [10], [31]:

κ(t) = ^˙ x(t)¨ y(t) −¨ x(t) ˙ y(t)

[ ˙ x²(t) + ˙ y²(t)]^{3/2 .} (3)

Using (3), the curvature is calculated at all the curvepoints. However, when the curve is parameterized using the affine length, the curvature is calculated at a subset of the curve points. We select the subset such that the distance between successive points is affinelength λ. We will discuss more about this sampling (subset selection) procedure in Section IIB.3.b. After sampling, the curvature on the affinelength parameterized curve Γ(τ) = (x(τ), y(τ)) can be calculated according to (3) using

κ(τ) = ^˙ x(τ)¨ y(τ) −¨ x(τ) ˙ y(τ)

[ ˙ x²(τ) + ˙ y²(τ)]^{3/2 .} (4)

We can derive first and second order derivatives of x(τ) and y(τ) in (4) as [19] (Appendix IA):

˙ x(τ) = ˙ x(t)

[ ˙ x(t)¨ y(t) −¨ x(t) ˙ y(t)]^{1/3 ,} (5)

¨ x(τ) = ^3¨ x(t)[ ˙ x(t)¨ y(t) −¨ x(t) ˙ y(t)] −˙ x(t)[ ˙ x(t)˜ y(t) −˜ x(t) ˙ y(t)]

3[ ˙ x(t)¨ y(t) −¨ x(t) ˙ y(t)]^5/3 ,

(6)

˙ y(τ) = ˙ y(t)

[ ˙ x(t)¨ y(t) −¨ x(t) ˙ y(t)]^{1/3 , and} (7)

¨ y(τ) = ^3¨ y(t)[ ˙ x(t)¨ y(t) −¨ x(t) ˙ y(t)] −˙ y(t)[ ˙ x(t)˜ y(t) −˜ x(t) ˙ y(t)]

3[ ˙ x(t)¨ y(t) −¨ x(t) ˙ y(t)]^5/3 ,

(8)

where ˜ x(t) and ˜ y(t) are third order derivatives with respect to t.

We see that the second order derivatives of x(τ) and y(τ) involves up to third order derivatives of x(t) and y(t) as evident from (6) and (8) above. However, by using (5) to (8) we can show that

˙ x(τ)¨ y(τ) −¨ x(τ) ˙ y(τ) = 1. (9)

Hence, the simplified formula of the affinelength parameter ized curvature from (4) using (9) is

κ(τ) = 1

[ ˙ x²(τ) + ˙ y²(τ)]^{3/2 ,} (10)

which uses only first and second order derivatives of x(t) and y(t) as evident from (5) and (7) above. Thus we avoid problems associated with curvature calculation using higher order derivatives. 2) Curve Smoothing: Curve smoothing prior to curvature measurement reduces the effect of noise [9]. To do that, each coordinate of the affinelength parameterized curve Γ(τ) is convolved with a Gaussian function gσ of width σ, which is also known as the smoothingscale or standard deviation of the Gaussian distribution. In the continuous form we have

X(τ, σ) = x(τ) ∗gσ and Y(τ, σ) = y(τ) ∗gσ, (11)

where ∗ denotes the convolution. After smoothing we have the parameterized and smoothed curve Γ(τ, σ) = (X(τ, σ), Y(τ, σ)). The Gaussian convolution property states that differentiation and convolution are commutative. So derivatives of the convolved function can be calculated as

˙ X(τ, σ) = x(τ) ∗˙ gσ and ^˙ Y(τ, σ) = y(τ) ∗˙ gσ. (12)

Since the exact form of ˙ gσ is known, we can calculate the curvature on the smoothed affinelength parameterized curve according to (10) as

κ(τ, σ) = 1

[ ^˙ X²(τ, σ) + ^˙ Y²(τ, σ)]^{3/2 .} (13)

Since the curvature extrema points describe the fundamental features of planar curves, the aim of the proposed ARCSS corner detector is to obtain inflection points using (13) as corners. 3) Corner Detection: The proposed ARCSS corner detector first uses the Canny edge detector [32] to extract edges (planar curves) from grayscale images. Each edge is parameterized using the affinelength and then smoothed using a medium smoothingscale. On each smoothed curve, candidate corners are defined as the local maxima of the absolute curvature. Since the curvature of a strong corner is higher than that of a weak corner, we remove weak corners on an edge if their curvature values are lower than the predefined edge curvature threshold. False corners are eliminated by comparing each curvature maximum with its two neighboring minima. If the curvature of a corner point is less than the double of the curvature of a neighboring minimum it is removed as a false corner [9]. The outline of the proposed corner detector is as follows.

IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. XX, NO. YY, OCTOBER ZZZZ 5

♦Find edge image using the Canny edge detector. ♦Extract edges from the edge image: (i) fill the gaps if they are within a range and select edges and (ii) find Tjunctions and mark them as Tcorners. ♦Parameterize each edge using its affinelength and smooth the parameterized curve using one of three smoothing scales determined based on the number of points on it. ♦Compute absolute curvature on each smoothed curve and find the candidate corners which are the absolute curvature maxima points. ♦For each edge, determine corners by comparing the curvature maxima values to the edge curvaturethreshold and the neighboring minima. ♦Track corners down to the lowest scale considering a small neighborhood to improve localization. ♦Compare Tcorners with the tracked corners and add those Tcorners which are far away from the detected corners.

We detail all the above steps in the following subsections. All the chosen parameter values that we will present below were decided either from the existing work or based on our empirical study presented later in Section VB.1.a.

a. Edge extraction and selection: In the Canny edge detector [32] too many weak and noisy edges are detected when the edge strength threshold is set too low. Conversely, many legitimate edges are missed when the threshold is set too high. In addition, the edge strength may be changed due to geometric transformations. Therefore, in our implementation, we choose the threshold range between 0.2 and 0.7 after experimentation.

Note that the CSS corner detection technique [9] can detect corners on both closed and open curves. Therefore, we do not need to follow any postprocessing, like the level set method in [34], on the extracted curves to obtain close contours. We simply extract planar curves from the Canny edge detector output as follows.

The output of the Canny edge detector is a binary image where ‘1’ represents edgepixel and ‘0’ represents nonedge pixel. Only the edgepixels are tracked to extract curves from the binary image. Initially, all the edgepixels are kept unmarked. If an edgepixel is found while scanning the binary image, it is marked and added to an initially empty curve (length 0). To extend the curve, an unmarked edgepixel is searched in the 3 × 3 neighborhood of each endpoint. If only one unmarked edgepixels are found, it is selected. If more than one such unmarked pixel is found, the one having the lowest Euclidean distance from the curveend is selected. The selected pixel is marked and added to the respective curveend. This process continues until none of the ends can be extended anymore with the remaining unmarked edgepixels. Once the construction of a curve is completed, the rest of the unmarked edgepixels are tracked similarly to construct another curve.

Some of the curves obtained as above are either natural short edges or detected due to strong noises. It is difficult to smooth short curves due to the restriction of the smoothing window size (window size should be smaller than the curve length). Moreover, since the affinelength of a curve is much smaller than its arclength, we need to select edges of reasonable lengths. Thus in our implementation, curves are selected only

when their lengths np meet the following condition:

np > (w + h)/α, (14)

where w and h are width and height of the image and α is called the edgelength controller. If α is small, only long curves are selected; if it is large, short curves are also selected. In our experiments, we set α = 25, and therefore, for an image of size 512 × 512, the minimum np is 42. The above edge extraction setup also helps speeding up the later steps by avoiding a large number of weak and very short edges which may not contain strong corners. If an edge runs through any point within 2 pixels away from an end of another edge, we select that end as a Tjunction and add to the Tcorner set [9].

b. Affinelength parameterization and corner detection: We calculate the affinelength τ of each selected edge Γ(t) and obtain ns = ⌊τ/λ⌋equally distant sample points which con stitute the parameterized curve Γ(τ), where λ is the sample interval in affinelength. Therefore, the distance between two successive points on Γ(τ) is affinelength λ on Γ(t). The gap (in number of pixels) between the sample points mainly depends on the nature of the curve. It is large on almost straightline like curve segments, but small on those segments where the curve makes significant direction changes (e.g., on and near corners). In order to reduce the gap, one may suggest using a small λ for not missing any important corners. We used λ = 0.25, 0.5, 0.75, 1.0 in our experiments and found that all of them gave almost the same corner detection performance (see Section VB.1.a).

Localization of the detected corners is better with smoothing using low sigma values. However, the stability (robustness) of the detected corners is better with smoothing using high sigma values. Moreover, a long curve requires higher smoothing scale than a short curve [10]. In order to make a trade off, we smooth the parameterized curve at one of three medium smoothingscales and corners detected at the smoothed curves are tracked down to the finest scale to improve the localization.

We smooth each parameterized curve using one of three medium smoothingscales determined based on the number of sample points (ns) on it. We set the three smoothingscales as σm = 3, σm+1 = 4, and σm+2 = 5 for short, medium, and long edges respectively and edge curvaturethreshold t = 0.03 for all types of curves. The short, medium, and long edge definitions of parameterized curves are defined by the con straints ns ≤60, 60 < ns ≤120, and ns > 120, respectively. We compute curvature at all points on the smoothed Γ(τ) and absolute curvature maxima points are taken into the candidate corner set. A local maximum point of the absolute curvature function is likely to be a strong corner, but it could also be a weak corner (also called ‘round’ corners in the literature [9]) or a false corner [9] as explained below.

The strong corners are very sharp in nature and visually prominent features on curves. Their localization is very good and curvature values are usually very high. In contrast, the weak corners are flat in nature and visually less significant features on curves. Their localization is very poor since it may be very difficult to point out their exact locations. Furthermore, their curvature values are usually smaller than the strong corners. The false corners are due to noise or high local

IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. XX, NO. YY, OCTOBER ZZZZ 6

variation on the curve. They are usually detected on those curves where there may be no visually prominent corners, for example, on circles. Note that although the notion of corner seems to be intuitively clear, no generally accepted mathematical definition exists, at least for digital curves [35]. Therefore, it is hard to give formal definitions for strong, weak, and false corners and we define them using their apparent characteristics as discussed above.

In the candidate corner set we may have all three types of corners – strong, weak, and false. The later two should be removed from the candidate corner set. We follow the same technique as the CSS detector [9] to remove weak and false corners. Since the curvature of a strong corner should be greater than that of a weak corner, a candidate corner is removed from the candidate corner set if its curvature value is lower than t. To remove false corners, the curvature value of each candidate corner is compared with two of its neighboring minima on the same curve. If the curvature value of a candidate corner is not at least twice of its two neighboring minima, this candidate corner is removed from the candidate corner set [9].

Note corners detected on the smoothed curve obviously suffer from some absolute localization error with respect to the actual corner locations on the nonsmoothed curve. This error can be mitigated in two ways. First, the smoothingscale should be as low as possible. Since, the affinelength of a curve is usually small, the ARCSS detector selects the low sigma value (sigma = 3) for most of the curves. Second, a corner tracking step, which tracks the detected corners in the lower scales, is followed to improve the error. Like other CSS detectors, we also follow a corner tracking step as discussed below.

c. Corner tracking and adding Tcorners: As corners are detected at coarse scales, their localization may not be good. We track the corners on Γ(t) down to the lowest scale by considering a neighborhood of size 3 on each side of each corner. For example, if a corner is detected at the pth point on Γ(τ) at σ = 3, first we track this corner at σ = 2 considering 7 consecutive points, where the pth point is the midpoint. The point having the maximum absolute curvature among these 7 points is the tracked position of that corner at σ = 2 and the next tracking is executed at σ = 1.

In the above corner tracking no threshold is used in the tracking system which only changes the corner positions, not the number of corners. However, corners do not move dramati cally during tracking and only six (neighbors) curvature values around each of the detected corners need to be computed during tracking [9]. As a consequence, corner localization is improved without increasing the computational cost.

Note that in the above multiscale corner tracking, we follow a linear decreasing of smoothingscale. Because we observed that when corners are detected using a small sigma value, the nonlinear decreasing made the procedure expensive by increasing the number of iterations, but did not give better localization performance than the linear decreasing which requires less number of iterations. However, if one uses a large smoothingscale for corner detection, the linear decreasing of sigma in multiscale corner tracking may cause a high

localization error.

Finally, we add Tcorners to the final corner set when there are intersections of curves. There may be an already detected corner on any of the intersecting curves (i.e., at or near a T corner point). A Tcorner is added to the final corner set if there is not an already detected corner in the 5 × 5 pixels neighborhood around it [9]. Such an use of the Euclidean neighborhood should not be a problem because in practice there may be no or only a few of such points in real world images. Ideally, Tcorners should be detected in the affine space. But this is not possible for two reasons. First, the affine length cannot be calculated between points on different curves. Second, at the corner detection stage we need to detect T corners regardless of whether the image has been transformed or not.

III. CORNER MATCHING

The successful application of a corner detector in many applications depends on how to match corners between im ages. The proposed matching technique is robust to both geometric transformations and signal processing attacks. It can be used with contourbased corner detectors. Particularly, here we will use it with our proposed ARCSS corner detector which provides useful information such as curvatures and affine lengths between corners.

A. Existing Matching Techniques

In the second group of corner matching techniques (see Section IB), the matching problem was first formulated as the subgraph isomorphism problem to find the maximal clique [26]. Nevertheless, finding the maximal clique is an NP complete problem [21]. The problem was later formulated as an optimization problem and either a relaxation technique [29] or a binary Hopfield network [27] was applied for cost minimization. A similar approach based on the fuzzy inference procedure was proposed in [28]. Optimization techniques were robust to rotation, translation, and partial occlusion of the object; however, were vulnerable to small scale change and computationally expensive. The solution in [25] used the Hausdorff distance to determine the degree of mismatch between two sets of feature points. However, the Hausdorff distance is too sensitive to noises or outliers and is not invariant to geometric transformations. The method in [24] used a similarity measure based on the corner strength. It first matched local feature groups and then estimated the affine transformation by global matching. But it was vulnerable to downscaling and computationally expensive.

Zhou et al. [22] proposed a novel corner matching technique based on the Delaunay triangulations (DT) which were formed among the detected corners. The corner correspondence was established based on the observation that the interior angles of the Delaunay triangles completely and uniquely characterized the corners and their values were not affected much by rota tion, uniform scale change, and translation. At the matching stage, the most similar triangle pairs were obtained and then their edges were extended circularly until all matching corners were triangulated and mismatching corners were discarded.

IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. XX, NO. YY, OCTOBER ZZZZ 7

Fig. 1: Block diagram for the proposed matching technique.

The DT matching was very much promising; however, it would fail under aspectratio change (nonuniform scaling) and other geometric transformations such as shearing where interior angles of the Delaunay triangles are affected.

B. Proposed Matching Technique

We observed that the absolute curvatures of corners may change due to geometric transformations; however, for many corners they only change slightly (see Fig. 2 and explanation in Section IIIB.1.b). Moreover, the affinelength between two corners on the same curve (see (2) in Section IIB.1) and the triangular area consisting of any three corners as vertices (see (32) in Appendix IC) are relatively invariant to affine transformations. Therefore, in addition to corner positions, the proposed matching procedure uses the affinelength and triangular area invariances and curvature value to establish corner correspondences between two images.

Fig. 1 shows the block diagram for the proposed ALTA matching technique. For two given corner sets A and B of images IA and IB respectively, we first obtain candidate corner matches using curvature values and affinelengths. For each combination of any three candidate matches, if the corners are noncollinear on the respective image plane, we have two triangles – one in each image plane. If the areas of these two triangles are similar (the difference is within the certain threshold), we estimate the transformation matrix g^′

that transforms the triangle in IA into the triangle in IB. Finally, we transform the corners in A using g^′ and find matches within B. We keep track of g^′ over all iterations. The g^′ which gives the highest number of corner matches corresponds to the transformation matrix g we are looking for. The corner matching performance is calculated for this best matching case.

In the above procedure, the candidate corner matches are obtained in two steps. In the first step, we obtain candidate matches (PA, PB) within a specific curvature difference. In the second step, if there are a total of two or more detected corners on both of the curves where PA and PB are detected, we add more candidate corner matches (QA, QB) from the same pair of curves by matching the affinelengths between corners. This means that the affinelength between corners PA and QA on a curve in IA is compared with the affinelength between corners PB and QB on a curve in IB. Notice that PA and

Fig. 2: Minimum number of repeated corners by the ARCSS (affineresilient curvature scalespace) detector in geometric transformations (using the image database mentioned in Sec tion VA.1).

QA denote corners in A and PB and QB denote corners in B. Further notice that both of the similarity measurements (affine length using (2) and triangular area using (32)) depend on the considered ranges of scaling and shearing transformation factors.

We need only three true matching corners to estimate the original transformation matrix g. However, finding true corner matches is the aim of the matching procedure and is not straightforward. The worst case is to consider every possible combination of three corner pairs between IA and IB with the complexity of O(m³n³), where m = |A| and n = |B| (see Appendix IB). Therefore, we apply some strategies to reduce the computational cost. 1) Speeding up the Matching Procedure: If the two images IA and IB are originated from the same image due to some ge ometric transformations or signal processing attacks, the above matching procedure finds the maximum number of true corner matches. The estimated transformation matrix g^′ that causes the highest number of corner matches is an approximation of the original transformation matrix g. This process will be expensive in TII where one test image is compared with all database images to find possible transformed images. We apply the following strategies to reduce the cost:

a. Limiting the number of candidate corner matches: A maximum of three candidate corners are used from each pair of curves between two images. Because we need only three true corner matches to estimate g. If there are two or more corners on the same curve, we obtain maximum two more candidate matches (QA, QB) using the affinelength, for each candidate match (PA, PB) determined previously using the curvature value. The reason is if (PA, PB) is a true match, then we need only two more true matches to determine the transformation; but if it is a false match, we do not want to obtain more false matches based on it.

b. Setting the curvature difference threshold: We need to obtain at least 3 repeated corners to estimate g^′. The absolute curvature value of a corner should not change significantly under geometric transformations. For the transformations con

IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. XX, NO. YY, OCTOBER ZZZZ 8

sidered in Section VA.1, the ARCSS detector offered min imum 3 repeated corners when the curvature difference was greater than 0.06 (see Fig. 2). However, in order to provide a safe margin, we set a threshold Td = 0.2 for the curvature difference when we have minimum 7 repeated corners. Conse quently, two corners will be considered a candidate match only when the difference between their curvature values is within 0.2.

c. Using hash tables: We do not need to obtain a candidate corner match more than once. But the addition of candidate matches based on the affinelength may produce duplicates. We use a hash table to store the candidate corner matches obtained so far. If a new candidate corner match is found and if it is not in the hash table, we store it in the hash table. Moreover, in a later iteration we do not need to consider those combinations of (three) candidate corner matches that we have considered in an earlier iteration to estimate g^′. That means while estimating g^′ in each iteration, at least one of three considered candidate matches should be new. To ensure it, we store the iteration number in which a candidate match is obtained and entered into the hash table. We use the division method [36] for implementing the hash table.

d. Selecting possible transformed images: The number of detected corners between the original and transformed images may differ, but it does not change dramatically. For the database in Section VA.1, the maximum difference in number of detected corners by the ARCSS detector was 31. Consequently, when we apply the matching procedure to TII, we only compare images if the difference in corner numbers between the query and database images is within 40.

e. Selecting top corners: If all the detected corners are con sidered, it may make the procedure too expensive depending on the number of corners in IA and IB. Considering that the corners with the highest curvature values should be the most important and robust, we can speed up the matching process without compromising accuracy by using only a few corners with the highest curvature values. In fact, by selecting only the top few corners based on curvature values, it not only speeds up the iteration but also offers better performance, as discussed later in Section VB.3.

IV. PERFORMANCE EVALUATION METRICS

In this section we will briefly describe some performance evaluation metrics used by the existing corner detectors and matching techniques along with their merits and demerits. Then we will present the metrics that we have used for fair performance comparison. We will also present the metrics which were used for evaluating the TII performance.

A. Existing CSS Corner Detector Evaluation

The performance evaluation of existing CSS corner detec tors [8]–[10], [31] is based on the human judgement. The measurement of consistency of corner numbers and accuracy proposed in [31] were flawed. Moreover, they used only a few of test images, some of which were artificial block images. As a result, their performance measurement may not be suitable for large databases consisting of real world images.

1) Human Visual Inspection: In [8]–[10], [31], both the false positive and false negative probabilities were evaluated by differentiating the set of detected corners from the set of corners pointed out by human visual inspection (HVI). This kind of evaluation is not very much useful for proper robustness tests due to several reasons. First, it is very hard to point out all corner locations by human intuition in natural images containing many corners. Second, human visual system is unable to measure the strength of corners. Consequently, it fails to distinguish between different corners and to sort them out according to their strength. Thirdly, the volume of work with a large image database for HVI prohibits its adoption. Finally, there is no standard procedure e.g., how many people should be involved and how to assess their decisions.

Mokhtarian and Mohanna [31] calculated accuracy by matching corners identified by human eyes to those detected by a corner detector. As accuracy usually indicates the lo calization of the detected corners, such a metric based on the number of the detected corners is flawed. In order to measure accuracy, the locations of the detected corners should be considered instead [37] (see Section IVB.2). 2) Consistency of Corner Numbers: Consistency of corner numbers (CCN) measures the similarity in corner numbers between the original and transformed images. Mokhtarian and Mohanna [31] defined CCN as:

CCN = 100 × 1.1^−|Nt−N0|, (15)

where N0 and Nt are numbers of detected corners in original and transformed images respectively. This metric is severely flawed for the robustness test because if a corner detector detects N points in the original image as corners and com pletely different N points in the transformed image, then N0 = Nt = N and CCN will be 100%. Moreover, it does not consider whether the detected corners are repeated or not. As a result, CCN could not be accepted as a fair and unambiguous metric for the robustness evaluation.

Mokhtarian and Mohanna [31] used both the accuracy and CCN to compare the performance of their CSS and ECSS corner detectors [9], [10]. Therefore, though they showed that the ECSS corner detector performed better than the CSS detector, we found the reverse in our performance study (see Section VB.1.b). 3) Preferred Metrics: In fact, the performance evaluation of corner detectors should be automated and without using any human intuition. For example, they could be evaluated in terms of repeatability and localization error which were previously used for evaluating other types of feature detectors and matching techniques [37]–[39]. We present them in the following section. However, one of them had problems and we propose to modify it to eliminate problems (see Section IVC.1).

B. Existing Corner Matching Evaluation

Many existing corner or interestpoint matching techniques used the repeatability and localization error to evaluate their performance.

IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. XX, NO. YY, OCTOBER ZZZZ 9

1) Repeatability: Repeatability indicates how stable the detected corners are under different geometric transformations and signal processing attacks. It is defined as the percentage of the total observed corners repeated between the original and transformed (and/or signal processed) images. Trajkovic and Hedley [38] estimated repeatability as the ratio R0 of the number of corner matches (between the original and transformed images) Nm to the number of corners in the original image N0. Schmid et al. [39] used the ratio Rt of Nm to the number of detected corners in the transformed image, Nt. Both R0 and Rt are shown in (16).

R0 = ^Nm

N0 and Rt = ^Nm

Nt . (16)

The potential problem with R0 and Rt alone is that they are highly sensitive to false corners. If a corner detector detects all points in the original image as corners, then Nt = Nm and Rt will be 100%. In contrast, if a corner detector detects all points in the transformed image as corners, then N0 = Nm and R0 will be 100%. Consequently, the performance evaluation based on R0 and Rt alone could be ambiguous. 2) Localization Error: Due to the error introduced by the edge detection, corner detection, and pixel value interpolation during transformations, a particular location (cornerpoint) in an original image may not be accurately detected in the transformed image. Therefore, we need to allow some error while estimating the repeatability.

Localization error shows how accurately a detected corner is localized by the detector. Lower localization error indicates the better accuracy. It was measured using the rootmean squareerror (RMSE) of corresponding positions of matching corners in the original and transformed images [6], [37]:

Le =

v u u t ¹

Nm

Nm X

i=1 [(x0i −xti)² + (y0i −yti)²], (17)

where (x0i, y0i) and (xti, yti) are the positions of ith match ing corner in original and transformed images respectively. An RMSE value of maximum 3 pixels was allowed to find the corner matches [37]. If less than 3 pixels error is allowed, then some true corners may be missed leading to low repeatability. However, allowing a high error may consider some neighbor ing corners as repeated corners.

Note the localization error using (17) measures the rela tive error (between the detected corners in the original and transformed images), rather than the absolute localization error which is measured between the actual corner location (ob tained using the ground truth from humans) and the detected corner location in an image. However, as discussed in Section IIB.3.b if a corner detector uses a low smoothingscale and follows a corner tracking step after the corner detection on the smoothed curve, the relative error as well as the absolute error can be minimized.

C. Proposed Evaluation Metrics

We want to measure three types of performance: corner detection performance, corner matching performance, and TII performance. For evaluating detection performance, we modify

existing repeatability metric and use localization error metric directly. For evaluating matching performance, we use the sim ilar metrics as for the detection performance. For evaluating identification performance, we use the precisionrecall graph. 1) Corner Detection Performance Measurement: The per formance of a corner detector is evaluated using repeatability and localization error [37], [39]. For many applications, e.g., image copyright protection, once we have the required number of repeated corners, localization of the repeated corners is very important. The reason is, with the lower localization error the copyright verifier will be able to better localize the target pixel positions by using the repeated corners as reference points. Moreover, in the case of TII, the lower localization error helps estimating the geometric transformation matrix more accurately resulting in better identification performance.

To determine the corner detection performance, we first detect corners in each pair of original and test (geometric transformed and signal processed) images using a corner detector. We know the original transformation matrix. We transform the original corners using the known transformation matrix, prior to finding their repetitions in the test corner set. An RMSE value of maximum 3 pixels was allowed to find a repetition. In Section IVA, we presented the problems with the performance evaluation metrics of existing CSS corner detectors [8]–[10], [31]. For fair and unambiguous comparison we employed the average of R0 and Rt as the average repeatability Ravg defined as

Ravg = ^{R0 + Rt}

2 = ^Nr

2

µ 1

N0 + ¹

Nt

¶ . (18)

where N0 and Nt are the number of corners in the original and test images, respectively, and Nr is the number of repeated corners between them. Note that Ravg is free from drawbacks associated with R0 and Rt alone. We used the same evaluation metric, defined in (17) where Nm = Nr, for evaluating the localization error Le of the repeated corners. 2) Corner Matching Performance Measurement: To deter mine the corner matching performance, we first detect corners in each pair of the original and test (geometric transformed and signal processed) images using the proposed ARCSS detector. The original transformation matrix is not known in this case. However, the proposed corner matching technique provides us an estimated transformation matrix. We transform the original corners using the estimated transformation matrix prior to finding their matches in the test corner set. Again, an RMSE value of maximum 3 pixels was allowed to find a match. We used the same metric like the average repeatability as corner correspondence (CC) between original and test images:

CC = ^Nm

2

µ 1

N0 + ¹

Nt

¶ , (19)

where Nm is the number of corner matches between them. For a pair of images when one is a transformed version of other, Nr ≥Nm, i.e., Ravg ≥CC. We also evaluate the localization error Le of the matched corners using the metric in (17). 3) Transformed Image Identification Performance Measure ment: In TII there are many groups of images and each group contains only geometric transformed and signal processed

IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. XX, NO. YY, OCTOBER ZZZZ 10

images of a particular image. Only images belonging to the same group are considered relevant (true positive match) to each other. In contrast, in the CBIR system all the images having the same or similar semantic features, e.g., red car, are considered relevant to each other and reside in the same group. We use precision and recall [2] collectively to measure the identification performance. Recall measures the system capacity to retrieve the relevant images from the database. It is defined as the ratio between number of retrieved relevant images R and total number of relevant images Rt in the database:

Recall = ^R

Rt . (20)

Precision measures the retrieval accuracy. It is defined as the ratio between R and number of retrieved images Rn:

Precision = ^R

Rn . (21)

In practice, the performance of an information retrieval system is presented using the precisionrecall graph, where the higher the precision and recall values the better the performance is considered.

V. PERFORMANCE STUDY

We carried out the following three performance studies and in each study we compare the proposed technique with one or more existing techniques by using different evaluation metrics discussed in Section IVC:

♦For evaluating corner detection performance we imple mented the proposed ARCSS and existing CSS and ECSS (which were set at their default parameters mentioned in [9], [10], [31]) corner detectors and compare their performance using average repeatability and localization error. ♦For evaluating corner matching performance, we imple mented proposed ALTA and existing DT [22] matching techniques with the proposed ARCSS corner detector and compare their performance using corner correspondence. ♦For evaluating identification performance we apply the proposed ARCSS detector and ALTA matching technique for TII. Their identification performance is compared with that of the existing GSH matching technique using the precisionrecall graph.

A. Databases

We had two datasets of 23 and 100 original images re spectively [40]. The first database was built using the first dataset and used for evaluating corner detection and matching performance. The second database was built using the second dataset and their transformed images and used for evaluating the TII performance. The use of two different databases of different sizes eliminated the bias of the proposed corner detection and matching technique to a particular database.

1) Corner Detection and Matching Database: There were a total of 23 different original 512 × 512 grayscale images [40], including ‘Lab’, ‘Block’, and ‘House’ images used by the CSS and ECSS detectors, in this database. We obtained a total of 8694 transformed images of seven categories as test images:

♦rotation at 18 different angles θ in [−90^◦, +90^◦] at 10^◦

apart, excluding 0^◦; ♦uniform (U) scaling factors sx = sy in [0.5, 2.0] at 0.1 apart, excluding 1.0; ♦nonuniform (NU) scaling factors sx in [0.7, 1.3] and sy in [0.5, 1.8], at 0.1 apart, excluding the cases when sx = sy; ♦combined transformations (rot.scale): θ in [−30^◦, +30^◦] at 10^◦apart, excluding 0^◦, followed by uniform or non uniform scaling factors sx and sy in [0.8, 1.2] at 0.1 apart; ♦JPEG lossy compression at 20 quality factors in [5, 100], at 5 apart; ♦zero mean white Gaussian noise at 10 variances in [0.005, 0.05] at 0.005 apart; and ♦shearing factors shx and shy in [0, 0.012] at 0.002 apart, excluding the one when shx = shy = 0.0.

Therefore, we had a total of 414 rotated, 345 uniform scaled, 2691 nonuniform scaled, 3450 rotated and scaled images. We also had 460 JPEG compressed, 230 Gaussian noised, and 1104 sheared images. Note that transformations comprising rotations were also followed by cropping such that the outer black parts were discarded. Consequently, many detected corners in the original images were cropped off in the transformed images for the transformations involving rotations. 2) TII Database: In this database, there were a total of 100 different original 512 × 512 grayscale images [40] and their 1600 transformed images of five categories:

♦rotation at 4 different angles θ in [5^◦, 20^◦] at 5^◦apart; ♦uniform scale factors sx = sy in [0.85, 1.15] at 0.05 apart, excluding 1.0; ♦combined transformations: [θ, sx, sy] = [5^◦, 0.8, 1.2] and [10^◦, 0.7, 1.1], ♦JPEG lossy compression at quality factors 20 and 25; and ♦zero mean white Gaussian noise with noise variances 0.005 and 0.01.

We had 5 queries for each original image: rotation 10^◦, uni form scale factor 1.05, combined transformation [5^◦, 0.8, 1.2], lossy JPEG compression with quality factor 20, and Gaussian noise with variance 0.005. Therefore, we had a total of 100 groups of images in this database, each group consists of 17 relevant images (16 transformed and 1 original) for a corre sponding query, and a total of 1700 images in the database. Like the previous database we also cropped the rotated images so that the outer black parts were disappeared. This diminishes the bias of large black regions in the rotated images for GSH matching technique. Note that the transformations we used are similar to those provided by the stirMark benchmark [41], which is commonly used for identifying copyright infringe ments.

IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. XX, NO. YY, OCTOBER ZZZZ 11

Fig. 3: Effects of Canny edge detection thresholds changes on the ARCSS (affineresilient curvature scalespace) corner detector: (a) average repeatability and (b) localization error. At each data label the values within the square brackets are low and high thresholds of Canny edge detector and the value outside the bracket is the average number of detected corners by the ARCSS detector. The selected edge detection thresholds are shown using the grey background.

B. Results and Discussions

We present results and discussions of the three performance studies in this section: corner detection, corner matching, and transformed image identification. Due to space limitation we will present the average results for each of the performance study over the whole respective database. Please see the detailed results on each type of attacks in [40]. 1) Corner Detection Performance: In this section, we first summarize the experimental results of some parameter setting for the proposed ARCSS detector. We then present the com parative results between the proposed ARCSS and existing CSS [9] and ECSS [10] detectors. To present the performance comparison, we first show an example and then present the average results on the whole database discussed in Section VA.1.

a. Summary of ARCSS parameter setting: Many of the parameters used by the ARCSS detector had been originally set by the existing detectors, e.g., 2 pixel gap for detecting Tjunctions by the CSS detector [9]. We have carried out experiments for setting the rest of the parameter values, e.g., Canny edge detection thresholds, edgelength controller,

smoothing scale, sampleinterval, and curvaturethreshold. We summarize and discuss the results below. Note that these thresholds can be used for different image sets and need not be changed once determined.

Fig. 3 shows the effect of Canny edge detection thresholds changes on the ARCSS corner detector. When both the low and high thresholds were set small, the average number of detected corners by the ARCSS detector was quite high, but its robustness was low (low average repeatability and high localization error). The reason is, at lower thresholds the Canny edge detector obtains too many edges, many of which may be weak and noisy. In contrast, when the thresholds were increased, only strong edges were detected; therefore, the robustness of the ARCSS detector increased. However, when the thresholds were increased above low = 0.2 and high = 0.7, the robustness (average repeatability) of the ARCSS detector decreased. Moreover, when higher threshold values were used it missed some legitimate edges (hence, corners). Therefore, we have chosen the Canny edge detection thresholds at low = 0.2 and high = 0.7 as default for the ARCSS detector.

Fig. 4 shows the effect of different parameter changes (edge length controller α, Gaussian smoothingscale σ, sampling interval λ, and curvaturethreshold t) on the ARCSS corner detector. We considered four or five different sets of values for each parameter.

We observed that the localization error increased with the increase of the value of α. Because many short and com paratively weak edges were detected when high values of α were used. Since the average repeatability was the highest at α = 15, we selected this value as default.

When the value of σ was increased, the robustness of the ARCSS detector slightly increased (higher average repeata bility and lower localization error) slightly, as shown in Fig. 4. However, at high σ value it missed some strong corners. Therefore, we have selected the set of σ values 3, 4, and 5, where most of the curves are smoothed using σ = 3.

The affinelength parameterization used by the ARCSS corner detector selects more points on the curve segments where the curve makes significant direction changes (e.g., on and near corners) than on the straightline like segments. A high sampling interval λ selects less number of points on a curve than a low λ value does. To investigate whether λ affects the corner detection performance, we used four different λ values: 0.25, 0.50, 0.75, and 1.00. Fig. 4 shows the average repeatability and localization error in above four cases. Though the average repeatability was slightly increased (better) in the lowest λ value, the localization error also increased slightly (worse). Since, all the four cases offered almost the same average repeatability and λ = 1 offered the lowest localization error, the rest of the experimental results presented hereafter is with λ = 1.0.

The robustness of the ARCSS detector also slightly in creased with the increase of curvaturethreshold t, as shown in Fig. 4, since only the stronger corners are detected with higher t. Since at high t value it missed some strong corners, we have selected t = 0.03 as a trade off.

Fig. 4 also shows that the average repeatability was quite

IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. XX, NO. YY, OCTOBER ZZZZ 12

Fig. 4: Effects of different parameter changes (edgelength controller, Gaussian smoothing scale, sampling interval, and curvaturethreshold on the ARCSS (affineresilient curvature scalespace) corner detector. For each parameter, we had 4 or 5 different sets of values and we showed them in the square brackets above the corresponding bar. The value outside the square bracket above each bar is the average number of detected corners by the ARCSS detector. The selected values for each parameter are shown using the grey background.

low and the localization error was quite high without using different Gaussian smoothingscale and curvaturethreshold. Thus these results show the importance of curve smoothing before corner detection and of using the curvaturethreshold to remove the weak corners.

b. Comparative results: Fig. 5 shows corner detection examples by the existing CSS and ECSS and the proposed ARCSS detectors in ‘Lena’ and ‘Lab’ images. On the curves inside the dotted ellipses in Fig. 5, we see that the ARCSS detector detected fewer weak corners than the CSS and the ECSS detectors.

Fig. 6 shows the average repeatability and localization error under geometric transformations, JPEG compression, and Gaussian noise. It was observed that the ARCSS detector performed the best among the three in terms of both average repeatability and localization in geometric attacks. This is be cause during corner detection while the ARCSS detector uses the affinelength parameterization, both of the CSS and ECSS

detectors use the arclength parameterization. Nevertheless, it showed lower average repeatability than the CSS detector but better localization than both of the CSS and ECSS detectors in JPEG compression and noising. The possible reason is that the CSS detector obtains corners at a higher scale than the other two and, therefore, gains higher noise immunity to signal processing attacks. But as a consequence, it may miss some true corners. In contrast, since the ECSS and ARCSS detectors detect corners at one of the three medium smoothing scales determined based on the parameterized curve length, they may detect some weak corners. However, the ARCSS detector detects fewer weak corners than the ECSS detector, since the former uses the affinelength parameterization.

Although the performance improvement in terms of localizationerror (Fig. 6) by the proposed ARCSS corner detector is not great, it can be considered important in real applications such as copyright protection. The bar chart in Fig. 6(b) shows the average localization error. Some error could be zero pixels (minimum), some could be 3 pixels (maximum), and some could be in between the minimum and maximum. The lower average localization error indicates there were fewer corners with large errors (close to 3 pixels). In a copyright protection system, lower localization error helps minimizing the effect of synchronization error. The lower localization error also leads to more precise estimation of the transformation matrix during corner matching.

Note that in our experiments we found the CSS detector [9] to be more robust than the ECSS detector [10]. However, the opposite was found by Mokhtarian and Mohanna [31] and He and Yung [33]. The reasons of this conflict are as follows. First, the use of higher smoothingscale by the CSS detector makes it more robust than the ECSS detector. While the former uses σ = 4 for all the curves, the ECSS detector uses σ = 3 for most of the curves. Second, the smoothingscale selection according to the arclength by the ECSS detector makes it more sensitive to the geometric transformations under which the arclength of a curve is not preserved [19]. Third, Mokhtarian and Mohanna [31] used the flawed metrics (accuracy and CCN) as we discussed in Sections IVA.1 and IVA.2. Fourth, to measure accuracy they [31] used the ground truth from humans and did not consider the geometric transformed images. Finally, He and Yung [33] also used the ground truth from humans and did not consider the image transformations at all. 2) Corner Matching Performance: In this section, we first present the matching time with and without the speed up procedures for the proposed ALTA matching technique. We then present the detailed comparative results between the ALTA and DT matching techniques.

We observed that the implementation of the speed up procedures significantly improved the running time of the proposed ALTA matching technique (using Intel Pentium 3GHz Processor, 1GB RAM, Windows XP). Without applying the speed up procedures, the running time was 2.016 second for each pair of original and transformed images. By applying all the proposed speed up procedures, other than the selection of the top 15 corners, the matching time was 0.327 second. When we applied all the speed up procedures including the

IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. XX, NO. YY, OCTOBER ZZZZ 13

Fig. 5: Corner detection in original ‘Lena’ and ‘Lab’ images by different corner detectors. Edges were detected using Canny edge detector where Low and High edgedetection thresholds were set at 0.2 and 0.7 respectively and choosing those extracted edges whose length were at least 68 pixels. CSS = curvature scalespace, ECSS = enhanced CSS, ARCSS = affineresilient CSS.

IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. XX, NO. YY, OCTOBER ZZZZ 14

Fig. 6: Overall performance comparison of different corner detectors. CSS = curvature scalespace, ECSS = enhanced CSS, ARCSS = affineresilient CSS, U = uniform, NU = nonuniform, G = Gaussian.

Fig. 7: Overall corner correspondence. ALTA = affinelength and triangular area, DT = Delaunay triangulations, U = uni form, NU = nonuniform, G = Gaussian.

selection of top 15 corners the running time was 0.046 second only. Note that this gain in matching speed was achieved without compromising the matching accuracy.

Fig. 7 shows the overall corner correspondence by the ALTA and DT matching techniques under different geometric trans formations and signal processing attacks. The ALTA method offered significantly higher corner correspondence than the DT method. The maximum corner correspondence by a matching technique will be the average repeatability of the involved detector as discussed in Section IVC.2. By comparing the ARCSS repeatability in Fig. 6 and the corner correspondence in Fig. 7, we see that by estimating the transformation in advance the corner correspondence by the ALTA matching is very close to the average repeatability of the ARCSS detector. In contrast, the DT matching offers a very limited performance.

The significant performance difference in terms of corner correspondence between ALTA and DT methods is due to the following reasons. First, the ALTA matching estimates the affine transformation matrix and transforms the corners of the database image prior to matching with the test corner set. Table I shows the estimated transformation parameters by

the proposed ALTA matching technique under some geometric transformations on ‘Lena’ image. Second, the Delaunay trian gulation is very sensitive to outliers. It is unique for a given set of corners but a corner detector often offers a different set of corners under geometric transformations as well as in noising and lossy compression. Therefore, the sets of triangles between the original and test images differ considerably. Third, the interior angles of Delaunay triangles, used for the similarity measurement by the DT method, change according to the strength of the involved geometric transformation, especially when the image is nonuniformly scaled and sheared (see NU scale, Rot.scale, Shear in Fig. 7). Fourth, true triangle matches may be missed in DT matching if they are not adjacent to any of the already obtained triangle matches. Finally, the DT matching would fail if the initial triangle match is false.

For example, Fig. 8 shows the corner matching examples by the proposed ALTA and existing DT [22] matching techniques. A total of 17 and 12 corners were detected in the original (Figs. 5(a) and 5(e)) and transformed (10^◦rotation, 80% scaling, 1.2% shearing, and cropping to 348 by 356 pixels, Figs. 8(a) and 8(c)(right)) images respectively by the ARCSS detector. The ALTA matching technique estimated the transformation matrix very precisely and found all the 8 true corner matches, as shown in Fig. 8(c). However, the first five most similar triangle matches by the DT matching technique were false, as shown in Fig. 8(d). The sixth most similar triangle match was true, but the DT matching could not find other true matches (as indicated by m in Fig. 8(d)) adjacent to this true match. Consequently, the DT matching technique obtained only 3 true corner matches (vertices of true triangle match 6).

Notice that we also estimated localization error of matching corners. Both of the ALTA and DT matching techniques had almost the same localization error since they were executed with the same corner detector. 3) Identification Performance: In this study, we investi gated the TII performance of the proposed corner detector and matching technique. We compared their identification performance with that of the existing GSH matching technique [2] using the precisionrecall graph.

Therefore, in TII for each query image we need to compare

IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. XX, NO. YY, OCTOBER ZZZZ 15

Fig. 8: Corner matching by proposed ALTA (affinelength and triangular area) and existing DT (Delaunay triangulations) matching techniques. ARCSS = affineresilient curvature scalespace.

IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. XX, NO. YY, OCTOBER ZZZZ 16

TABLE I: Estimated transformation parameters by the proposed ALTA (affinelength and triangular area) matching technique on ‘Lena’.

Attacks sizes θ(^◦) sx sy tx ty

Rotationcrop (θ = 10^◦) 442 × 442 10.29 1.00 1.01 0.41 0.42

Uniform scale (sx = sy = 0.7) 359 × 359 00.36 0.71 0.71 −0.31 −0.09

Nonuniform scale (sx = 0.9, sy = 1.1) 461 × 564 −0.10 0.89 1.10 −0.01 0.78

Rotationscale (θ = 10^◦, sx = 0.9, sy = 0.9) 398 × 398 09.87 0.88 0.87 1.02 −0.82

Rot.scaletrans. (θ = 10^◦, sx = sy = 0.9, tx = 10, ty = −5) 388 × 393 09.87 0.88 0.88 3.52 −5.82

Fig. 9: The TII (transformed image identification) performance (average on five queries mentioned in Section VA.2). ALTA = affinelength and triangular area, GSH = grayscale histogram.

with all of the images in the database. As discussed in Section IIIB.1.e, we can reduce the computational cost by only using the top few corners according to the curvature values. In our experiments, we considered two cases – when all the detected corners were considered and when only top 15 corners with the highest curvature values were considered. We selected top 15 corners based on two observations. First, if more than 15, say 20 or more, were selected, the procedure became more expensive. Second, if less than 15, say 10 or less, were selected, almost the same number of corner matches were found for both relevant and irrelevant images in the database.

Fig. 9 presents the average identification performance on five different queries (mentioned in Section VA.2) by the proposed ALTA matching and the existing GSH matching [2] techniques. While the ALTA matching used the corner cor respondence between query and database images to rank the retrieved images, the histogram matching used the normalized L1 distance [2].

We observed that the ALTA matching procedure offered better performance than the GSH matching technique in most of the cases. Nevertheless, for lower recall values, the GSH matching outperformed the ALTA matching, especially in queries comprising scaling. However, for higher recall values while the precision of the ALTA matching decreased slightly, that of GSH matching dropped significantly in all queries. This might be due to two reasons. First, scaling may preserve the ratio of grayscale intensities but in higher recall values different images may have the similar histogram. Second, when the number of corners was high, there might be many false matches between the irrelevant images.

Instead of considering all the detected corners, when we

considered only the top 15 corners the identification per formance increased considerably. Fig. 9 shows that for top 15 corner matching the precision of the ALTA matching procedure is above 90% which is almost the same for all the recall values but that of GSH matching dropped to 40% at 100% recall.

VI. CONCLUSIONS

The arclength parameterized curvature [31] used by the existing CSS [9] and ECSS [10] detectors uses secondorder derivatives of curvepoint locations. In contrast, the proposed ARCSS corner detector used the affinelength parameterized curvature which usually uses third order derivatives. The higher order derivatives involve more computational cost and cause unstable curvature estimation [19]. However, by math ematical derivations we have shown that the affinelength pa rameterized curvature can also be implemented using second order derivatives. Therefore, the ARCSS detector extracts more robust corners with the similar computational cost as the existing detectors. It outperforms the existing detectors in terms of both average repeatability and localization under geometric transformations. It also possesses better localization than the existing detectors in JPEG compression and Gaussian noise.

The proposed ALTA corner matching technique uses infor mation like curvature values and affinelength between corners on the same curve to obtain candidate corner matches. Then it reduces the searchspace by matching the triangular areas of each combination of any three candidate corner matches before estimating the possible geometric transformation ma trix. Finally, it transforms all the corners in one image using the estimated matrix before finding their matches in the other image. We have compared the proposed method with one of the most promising corner matching methods based on the Delaunay triangulation [22] using a wide range of transformed images. In experiments, the ALTA matching offered signif icantly higher corner correspondence than the DT matching and reached the highest performance of the involved ARCSS corner detector.

The TII performance of the proposed ARCSS corner de tector and ALTA matching procedure was compared with that of the GSH matching technique [2] using the precisionrecall graphs. The average precision (see Fig. 9) by the proposed corner detector and matching technique was always above 90% under all recall values. However, we observed that in spite of taking measures discussed in Section IIIB.1, the proposed ALTA matching technique required more time than the existing GSH technique. Future work will investigate

IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. XX, NO. YY, OCTOBER ZZZZ 17

more timeefficient matching technique and apply both the detector and matching technique along with some copyright protection technique (watermarking [3] or signaturebased [1]) for ownership establishment.

APPENDIX I

SOME MATHEMATICAL DERIVATIONS

A. Derivatives of x(τ) and y(τ)

By differentiating (1) we have

dτ

dt ^{= [ ˙} x(t)¨ y(t) −¨ x(t) ˙ y(t)]^1/3. (22)

So we have

dt

dτ ⁼ 1

[ ˙ x(t)¨ y(t) −¨ x(t) ˙ y(t)]^{1/3 ,} (23)

from which we can derive the first order derivative of x(τ) as

˙ x(τ) = ^dx(τ)

dt = ˙ x(t) 1

[ ˙ x(t)¨ y(t) −¨ x(t) ˙ y(t)]^{1/3 .} (24)

Again differentiating (23) with respect to τ

d²t

dτ ^{2 = −1}

3 ˙ x(t)˜ y(t) −˜ x(t) ˙ y(t)

[ ˙ x(t)¨ y(t) −¨ x(t) ˙ y(t)]^{5/3 ,} (25)

where ˜ x(t) and ˜ y(t) are third order derivatives with respect to t. Therefore, by differentiating (24) with respect to τ and using (23) and (25), the second order derivative of x(τ) is

¨ x(τ) = ^3¨ x(t)[ ˙ x(t)¨ y(t) −¨ x(t) ˙ y(t)] −˙ x(t)[ ˙ x(t)˜ y(t) −˜ x(t) ˙ y(t)]

3[ ˙ x(t)¨ y(t) −¨ x(t) ˙ y(t)]^5/3 (26)

Similarly, we have first and second order derivatives of y(τ) with respect to τ as

˙ y(τ) = ˙ y(t) 1

[ ˙ x(t)¨ y(t) −¨ x(t) ˙ y(t)]^{1/3 and} (27)

¨ y(τ) = ^3¨ y(t)[ ˙ x(t)¨ y(t) −¨ x(t) ˙ y(t)] −˙ y(t)[ ˙ x(t)˜ y(t) −˜ x(t) ˙ y(t)]

3[ ˙ x(t)¨ y(t) −¨ x(t) ˙ y(t)]^5/3 (28)

Using (24), (26)(28) we can easily derive

˙ x(τ)¨ y(τ) −¨ x(τ) ˙ y(τ) = 1. (29)

B. Estimating g^′ and the worst case complexity of ALTA matching

To estimate the transformation matrix g^′ between two given corner sets A and B of cardinalities m = |A| and n = |B|, we need to solve the following equation: · xB yB

¸ = · a b c d

¸ · xA yA

¸ + · e f

¸ , (30)

where (xA, yA) is a point in A and (xB, yB) is a point in B. As g^′ comprises six unknowns (transformations parameters a, b, c, d, e, and f as shown in (30)), we need at least 3 corners. In the worst case, we need to consider all possible cases and, therefore, the complexity is ^mC3×ⁿC3 ≈O(m³n³).

C. Affine invariance of triangular area

The area of a triangle with vertices v1 = (x1, y1), v2 = (x2, y2), and v3 = (x3, y3), when v1 is shifted to the origin, is

∆(v1, v2, v3) = ¹

2^{∥(x2 −x1)(y3 −y1) −(x3 −x1)(y2 −y1)∥.} (31)

Similar to (2), we can obtain the area of an affine transformed triangle as

∆(v1a, v2a, v3a) = ∆(v1, v2, v3)[sxsy(1 −shxshy)], (32)

which implies that the triangle area is also absolutely invariant to rotation and translation, but relatively invariant to scaling and shearing.

REFERENCES

[1] M. Awrangjeb and M. Murshed, “Robust signaturebased geometric invariant copyright protection,” in Proc. Int. Conf. on Image Process., Oct. 2006, pp. 1961–1964. [2] G. Lu, Multimedia Database Management Systems. Norwood: Artech House Inc., 1999. [3] J. S. Seo and C. D. Yoo, “Image watermarking based on invariant regions of scalespace representation,” IEEE Trans. Signal Processing, vol. 54, no. 4, pp. 1537–1549, Apr. 2006. [4] M. Alghoniemy and A. H. Tewfik, “Progressive quantized projection approach to data hiding,” IEEE Trans. Image Processing, vol. 15, no. 2, pp. 459–472, Feb. 2006. [5] C. J. Harris and M. Stephens, “A combined corner and edge detector,” in Proc. Alvey Vis. Conf., Aug.Sep. 1988, pp. 147–151. [6] K. Mikolajczyk and C. Schmid, “Scale & affine invariant interest point detectors,” Int. Journal of Comp. Vision, vol. 60, no. 1, pp. 63–86, Oct. 2004. [7] L. Alvarez and F. Morales, “Affine morphological multiscale analysis of corners and multiple junctions,” Int. Journal of Comp. Vision, vol. 25, no. 2, pp. 95–107, 1997. [8] A. Rattarangsi and R. T. Chin, “Scalebased detection of corners of planar curves,” IEEE Trans. Pattern Anal. Machine Intell., vol. 14, no. 4, pp. 430–449, Apr. 1992. [9] F. Mokhtarian and R. Suomela, “Robust image corner detection through curvature scale space,” IEEE Trans. Pattern Anal. Machine Intell., vol. 20, no. 12, pp. 1376–1381, Dec. 1998. [10] F. Mokhtarian and F. Mohanna, “Enhancing the curvature scale space corner detector,” in Proc. Scandinavian Conference on Image Analysis, Jun. 2001, pp. 145–152. [11] R. Laganiere and T. Vincent, “Wedgebased corner model for widely separated view matching,” in Proc. Int. Conf. on Pat. Recog., vol. 3, Aug. 2002, pp. 672–675. [12] E. D. Sinzinger, “A modelbased approach to junction detection using radial energy,” Pattern Recognition, vol. 41, no. 2, pp. 494–505, Feb. 2008. [13] L. Alvarez, F. Guichard, P.L. Lions, and J.M. Morel, “Axioms and fundamental equations in image processing,” Archive for Rational Me chanics and Analysis, vol. 123, pp. 199–257, 1993. [14] F. Mokhtarian and A. K. Mackworth, “Scalebased description and recognition of planar curves and twodimensional shapes,” IEEE Trans. Pattern Anal. Machine Intell., vol. 8, no. 1, pp. 34–43, 1986. [15] G. Sapiro and A. Tannenbaum, “Affine invariant scalespace,” Int. Journal of Comp. Vision, vol. 11, no. 1, pp. 25–44, Aug. 1993. [16] A. P. Witkin, “Scalespace filtering,” in Proc. Int. Joint Conf. on Artif. Intell., Aug. 1983, pp. 1019–1021. [17] M. Awrangjeb, G. Lu, and M. Murshed, “An affine resilient curvature scalespace corner detector,” in Proc. Int. Conf. on Acoustics, Speech, and Signal Process., vol. 1, Apr 2007, pp. 1233–1236. [18] F. Klein, Elementary mathematics from an advanced standpoint: geom etry. New York: Macmillan Company, 1939. [19] F. Mokhtarian and S. Abbasi, “Affine curvature scale space with affine length parametrisation,” Pattern Analysis and Applications, vol. 4, no. 1, pp. 1–8, 2001. [20] M. Daoudi and S. Matusiak, “New multiscale planar shape invariant representation under a general affine transformations,” in Proc. Int. Conf. on Pattern Recognition, vol. 3, Sep. 2000, pp. 786–789.

IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. XX, NO. YY, OCTOBER ZZZZ 18

[21] E. Davies, Machine Vision: Theory, Algorithms, Practicalities. London: Academic Press, 1990. [22] D. Zhou, G. Li, and Y. Liu, “Effective corner matching based on delaunay triangulation,” in Int. Conf. on Robotics and Automation, vol. 3, Apr.May 2004, pp. 2730–2733. [23] F. Mohanna and F. Mokhtarian, “Robust corner tracking for uncon strained motions,” in Proc. Int. Conf. on Acoustics, Speech, and Signal Process., vol. 5, Apr. 2003, pp. 804–807. [24] I. Jung and S. Lacroix, “A robust interest points matching algorithm,” in Int. Conf. on Computer Vision, vol. 2, Jul. 2001, pp. 538–543. [25] J. You, E. Pissaloux, and H. Cohen, “A hierarchical image matching scheme based on the dynamic detection of interesting points,” in Int. Conf. on Acoustics, Speech, and Signal Process., vol. 4, May 1995, pp. 2467–2470. [26] R. Horaud and T. Skordas, “Stereo correspondence through feature grouping and maximal cliques,” IEEE Trans. Pattern Anal. Machine Intell., vol. 11, no. 11, pp. 1168–1180, Nov. 1989. [27] N. Nasrabadi and W. Li, “Object recognition by a hopfield neural network,” IEEE Trans. on Sys., Man and Cyb., vol. 21, no. 6, pp. 1523– 1535, Nov.Dec. 1991. [28] K. Lee, Y. Kim, H. Myung, J. Kim, and Z. Bien, “A corner matching algorithm with uncertainty handling capability,” in Int. Conf. on Fuzzy Systems, vol. 3, Jul. 1997, pp. 1469–1474. [29] W. Rutkowski, “Recognition of occluded shapes using relaxation,” Comp. Graph. and Img. Process., vol. 19, no. 2, pp. 111–128, Jun. 1982. [30] M. Awrangjeb and G. Lu, “A robust corner matching technique,” in Proc. Int. Conf. on Multimedia & Expo., Jul. 2007, pp. 1483–1486. [31] F. Mokhtarian and F. Mohanna, “Performance evaluation of corner detectors using consistency and accuracy measures,” Computer Vision and Image Understanding, vol. 102, no. 1, pp. 81–94, Apr. 2006. [32] J. Canny, “A computational approach to edge detection,” IEEE Trans. Pattern Anal. Machine Intell., vol. 8, no. 6, pp. 679–698, 1986. [33] X. C. He and N. H. C. Yung, “Curvature scale space corner detector with adaptive threshold and dynamic region of support,” in Proc. Int. Conf. on Pat. Recog., vol. 2, Aug. 2004, pp. 791–794. [34] J. A. Sethian, Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science. Cambridge University Press, 1999. [35] X. Gao, W. Zhang, F. Sattar, R. Venkateswarlu, and E. Sung, “Scale space based corner detection of gray level images using plessey opera tor,” in Proc. Int. Conf. on Info., Comm. and Sig. Proces., Dec. 2005. [36] T. Cormen, C. Leiserson, and R. Rivest, Introduction to Algorithms. London: The MIT Press, 1999. [37] Y. Abdeljaoued and T. Ebrahimi, “Feature point extraction using scale space representation,” in Proc. Int. Conf. on Image Process., vol. 5, Oct. 2004, pp. 3053–3056. [38] M. Trajkovic and M. Hedley, “Fast corner detection,” Image and Vis. Comp., vol. 16, no. 2, pp. 75–87, Feb. 1998. [39] C. Schmid, R. Mohr, and C. Bauckhage, “Evaluation of interest point detectors,” Int. Journal of Comp. Vision, vol. 37, no. 2, pp. 151–172, 2000. [40] M. Awrangjeb. (2007) Database. [Online]. Available: http://personal. gscit.monash.edu.au/^∼awran/pr.html [41] F. A. P. Petitcolas. (2007) Watermarking database. [On line]. Available: http://www.petitcolas.net/fabien/watermarking/image database/index.html

Mohammad Awrangjeb obtained his B.Sc. Engg. degree in Computer Science and Engineering from Bangladesh University of Engineering and Technol ogy (BUET) in 2002 and M.Sc. degree in Com puter Science from National University of Singapore (NUS) in 2004. He joined NUS as a Research Scholar. Before joining NUS he had worked in University of AsiaPacific, Dhaka as a lecturer in Computer Science and Engineering Department and after finishing his M.Sc. he joined American Interna tional University–Bangladesh as a lecturer in Com puter Science Department. He has submitted his Ph.D. thesis with Monash University, Australia, where he had been fully funded. He is currently working as a Research Fellow with the University of Melbourne. His research interest includes feature detection and matching, digital watermarking, multimedia security, biometrics, and network security. He has already published three journal papers and ten conference papers in these areas.

Guojun Lu is currently a Professor at Gippsland School of Information Technology, Monash Uni versity. He has held positions at Loughborough University, National University of Singapore, and Deakin University, after he obtained his PhD in 1990 from Loughborough University and BEng in 1984 from Nanjing Institute of Technology (now South East University). Guojun’s main research interests are in multimedia communications and multimedia information indexing and retrieval. He has published over 120 refereed journal and conference papers in these areas and wrote two books Communication and Computing for Dis tributed Multimedia Systems (Artech House 1996), and Multimedia Database Management Systems (Artech House 1999).