英文翻译姓名：张衡学号： 1102080234指导教师：孙中桥专业：信息管理与信息系统班级： 2011级时间：2015年6月25日信息管理系信息管理系英文翻译评价表学生姓名张衡性别男学号1102080234外文文献标题Fast Component-Based QR Code Detection in Arbitrarily AcquiredImages外文文献出处以下内容由指导教师填写（打勾“√”选择）评价项目评价结论打勾评价结论打勾评价结论打勾是否外文期刊文献是否与本人论文相关完全相关一般不相关翻译工作量超负荷饱和不饱和翻译态度认真一般不认真翻译进度按计划执行一般未按计划执行翻译训练效果优良中差综合评语（是否完成了规定任务、效果是否符合要求等）指导教师签名：2015年4 月25日制表：李铁治注1：此表与翻译文本一起装订；注2：为了加强学生外语应用能力的训练，每位同学至少选择毕业论文中一篇外文参考文献（10000英文字符），翻译成中文。
外文文献及中文译文不装钉进论文中，只形成单行本放入档案袋即可。
英文原文Fast Component-Based QR Code Detection in Arbitrarily Acquired ImagesAbstract Quick Response (QR) codes are a type of 2D bar- code that is becoming very popular, with several application possibilities. Since they can encode alphanumeric charac- ters, a rich set of information can be made available through encoded URL addresses. In particular, QR codes could be used to aid visually impaired and blind people to access web based voice information systems and services, and au- tonomous robots to acquire context-relevant information. However, in order to be decoded, QR codes need to be prop- erly framed, something that robots, visually impaired and blind people will not be able to do easily without guid- ance. Therefore, any application that aims assisting robots or visually impaired people must have the capability to de- tect QR codes and guide them to properly frame the code. A fast component-based two-stage approach for detecting QR codes in arbitrarily acquired images is proposed in this work. In the first stage, regular components present at three corners of the code are detected, and in the second stage ge- ometrical restrictions among detected components are veri- fied to confirm the presence of a code. Experimental results show a high detection rate, superior to 90 %, at a fast speed compatible with real-time applications.Keywords QR code • Component-based detection • Haar-like features • Cascade classifier 1 IntroductionCompared to traditional 1D barcodes, 2D barcodes can en- code a larger amount of data, including alphanumeric char- acters. QR code, which stands for Quick Response Code, is a type of two-dimensional code introduced by Denso Wave in 1994 [12]. They have been designed to be easily found and to have its size and orientation determined under bad imaging conditions. In addition, ISO/IEC 18004 specifies an error correction scheme that can recover at most 30 % of occluded or damaged symbol area. These features make the QR code an extremely well succeeded technology in the area of barcodes. Figure 1 shows some examples of QR codes.Fig. 1 Samples of QR codeQR codes were initially used by the automotive industry to track vehicle parts during the manufacturing process [12]. Nowadays, QR codes are most commonly used as ―physical hyperlinks‖ (encoded hyperlinks), notably in the advertising industry, to connect places and objects to websites contain- ing additional context relevant information. Applications in education and entertainment [8, 23, 25], data and system se-curity [9, 16, 19], specific service offer [7, 27], among others are also emerging. Another possible application consists in helping visually impaired and blind people, or even robots, in several tasks such as indoor navigation, shopping, read- ing, and much more [2, 11, 13].The existing decoders, easily found for mobile devices, are able to work correctly only if codes are properly framed, with code region corresponding to at least 30 % of the im- age. When exploring an environment, visually impaired or robots will not be able to capture such images unless they are told where those codes are located. Thus, in order to make useful applications for them viable, detecting the presence of a code in an image is a necessary step prior to the decod- ing process.In related literature, the majority of work that mention QR code recognition or detection is actually concerned with improving image quality or determining the exact contours of the code rather than finding (i.e, deciding whether there is or there is not) a QR code symbol in an image [10, 20, 22]. In fact, most of the images considered in those works areimages acquired with the specific intent of capturing only the code symbol.Some few works that deal with the problem of finding QR codes propose solutions that rely on auxiliary informa- tion such as visual cues or RFID tags [11, 28]. Although such approach is possible in controlled environments, it is not practical in general contexts.This work addresses the problem of detecting QR codes in arbitrarily acquired images without relying on auxiliary cues. The aim is not only to detect the presence of code symbols, but also to delimit their position within an image as accurately as possible. That would allow, additionally, to instruct an user or robot to properly approach the camera towards the code.To that end, a component-based, two-stage detection ap- proach is proposed. In the first stage, a square pattern, called finder pattern (FIP), located at three corners of any QR code is detected using a cascaded classifier trained according to the rapid object detection method proposed in [26]. In the second stage, geometrical relationships among detected can- didate finder patterns are analyzed in order to verify if there are subgroups of three of them spatially arranged as three corners of a square region. A report on preliminary results of this approach has been previously published in [3]. In this paper, a reformulated report of the approach and an extended set of results are presented. In particular, a detailed account of the second stage, including a formal description of the component aggregation algorithm, new results obtained with a larger training and test sets, discussions concerning addi- tional parameters that have not been examined in the previ- ous work, and quantitative results, not presented before, on QR code detection performance are presented.This text is organized as follows. In Sect. 2, important structural aspects of QR codes which will be explored in the proposed approach are first described. Then, an overview of the proposed two-stage approach is presented, together with a brief review on Viola-Jones method for rapid object de- tection, used in the first stage of the approach. In Sect. 3, the problem of aggregating information obtained in the first stage of the detection process is expressed in graph-based formalism and a simple algorithm to solve the problem is proposed. The procedure to determine appropriate values for the training parameters of the FIP detector, in an OpenCV implementation of Viola-Jones’ method, is discussed and described in Sect. 4. Then, in Sect. 5 experimental results to assess influence of some parameters in FIP as well as QR code detection, and frame rates achieved in video process- ing are reported. Although extensive experimental variation was carried out, not all possibilities arising from parameter variations were evaluated. Nevertheless, QR code detection rate superior to 90 % was observed on test images, suggest- ing that even better rates can be achieved. Finally, in Sect.6 a summary of the main contributions of this work and some issues for future investigation are listed.2 Component-Based Approach for QR Code DetectionIn this section, some structural aspects of QR codes and detection requirements in a real-time application scenario that have motivated the proposed two-stage approach are first described. Then, an overview of the proposed approach followed by a brief review on Viola-Jones’ method for object detection is presented.2.1 QR CodeA QR code symbol, according to the ISO/IEC standard 18004, has a general structure that comprises data, version information, error correction code words, and the following regions illustrated in Fig. 2:Fig. 2 QR code structure (FIP: Finder Pattern / TP: Timing Pattern /AP: Alignment Pattern)– a quiet zone around the symbol,–three finder patterns (FIP) in the corners,–two timing patterns (TP) between the finder patterns, and– a certain number of alignment patterns (AP) inside the data areaThe internal organization of a code with respect to its structural components may vary depending on the amount of data encoded. The smallest units (black or white squares) that compose a QR code are called modules. There are various versions of the symbols, from 1 to 40, having distinct information storage capabilities that are determined by predefined number of modules in symbol area. Figure 3 shows an example of a version 1 code, highlighting the number of modules. Figure 4 shows additional examples that illustrate the relation between number of modules and number of encoded characters. Note that the alignment patterns occur more times in larger versions of the code.Fig. 3 QR code version 1 is composed of 21×21 modulesFig. 4 Different versions of QR code symbols and respective number of encoded alphanumeric charactersThere is a visually distinctive pattern at three corners of QR codes, known as finder pattern (FIP). FIPs have been specially designed to be found in any search direction as the sequence of black (b) and white (w) pixels along any scan line that passes through its center preserve the special sequence and size ratio w:b:w:bbb:w:b:w, as can be seen in Fig.5.Fig. 5 Black and white pixel proportions in finder patterns for diagonal (d), vertical (v) and horizontal (h) scan lines2.2 Detection RequirementsOne of the first requirements considering real-time applications is fast detection. Moreover, since there is no prior knowledge about the size of a code, another important feature of the detector is scale invariance. In addition, in order to succeed in uncontrolled environments, the detector should be also robust with respect to variation in illumination, rotation, and perspective distortion.In order to establish some limits to the detection task, in this work attention is paid to scale invariance and robustness with respect to variation in illumination condition, while rotations and perspective distortions are assumed to be small.Further than that, it is assumed that QR codes are printed in black and white (or at least dark foreground and light background). Color is not an issue since all processing considers gray tone images.2.3 Overview of the Proposed ApproachDirect detection of the whole code may not be an easy task because the internal structural organization may vary from code to code, depending on code version. Moreover, extraction of features of the code area, such as histograms or frequency information, can be greatly affected by image resolution, code scale, or noise. For instance, algorithms for recognition of QR codes frequently rely on the regularity of scan lines over the FIPs (see Fig. 5) to find them and then determine the exact contours of the code. However, that regularity may be disrupted in low quality images. Thus, in order to deal with unconstrained images, the processing algorithm should not depend on fine details.On the other hand, FIPs are typically the largest structures within a code, have a fixed shape, and appear in exactly three corners of all codes. These characteristics of FIPs suggest a component-based detection approach to the problem of detecting QR codes. The main idea of component-based detection [21] is the detection of parts of the object and then the analysis of detected parts in order to find a coherent arrangement forming the integral object. Arrangement of the parts can take into consideration geometrical restrictions. When the relation between parts can not be easily stated, machine learning based approaches can be used as in [1, 14].Taking the above observations into consideration, the proposed approach for detecting QR codes consists of a twostage method. In the first stage the aim is to detect FIPs, and in the second stage the goal is to integrate information about detected FIPs and decide whether subsets of three of them correspond to a QR code or not.In the first stage, it is desirable to maximize true positives (TP) while maintaining a controlled number of false positives (FP). Thus, for the detection of FIPs, some mechanism to control TP and FP should be available, and the detection process should fulfill the requirements listed above. In particular, it should be fast and invariant to scale and variation of illumination conditions. To meet these requirements, Viola-Jones’ rapid object detection method [26] is proposed for the first stage.In the second stage, the algorithm should be able to find sets of three FIPs that are the corners of a same QR code. To that end, geometrical restrictions as well as size related restrictions are considered, as detailed in Sect. 3.2.4 A Review on Viola-Jones’ Object Detection FrameworkViola-Jones’ object detection framework has the following characteristics:–it uses simple features (Haar-like);–it performs fast computation of features using integral image;–it is based on a cascaded approach to train a classifier: each stage is trained in such a way as to achieve fixed TP and false alarm (FA) rates, using a boosting algorithm;–it is very fast in practice since features are computed rapidly and the cascade is designed to discard the majority of negative samples in its early stages, eliminating the need for calculating responses of all stages to every sample considered.The Viola-Jones framework can be illustrated with the following concise description: The detection process consists in acquiring a complete sample set from the input image and submitting each sample to a cascade classifier whose stages have been trained by a boosting scheme that aggregates weak classifiers made of Haar-like features. These features are calculated in constant time using a matrix called integral image. Below some key concepts are reviewed and the detection process is explained.Sample set A sample consists of a sub-region of the image restricted to a window and the complete sample set of the image is obtained by sliding the window on the image and varying its size from a given minimum to the largest possible size in the image.Cascade classifier A cascade consists of a series of consecutive classifiers (stages) trained to reject samples that do not match the searched pattern while accepting the majority of positive samples and passing them to the next stage. A sample is said to be detected when it is accepted from the first to the last cascade stages, without rejection.Each stage is built from a set of weak classifiers aggregated in a committee by a boosting algorithm and can be seen as an independent classifier designed to obtain a very high hit rate (typically 99 % or more) with an acceptable false alarm rate (typically between 40 % and 60 %). Figure 6 illustrates the concept of a cascade classifier.Fig. 6 Illustration of the cascade approach to detectionBoosting Boosting works in rounds, iteratively training a set of weak classifiers while reweighting the training samples so that ―hard‖ samples will have increased relative importance in the set. In each round the best weak classifier is selected to compose the resulting classifier [15]. Thus, boosting can achieve the specified hit rate and false alarm rate as it increases the weak classifiers in the combination (as long as the features used have enough representational power). Every weak classifier is typically the result of the computation of a Haar-like feature followed by a binary threshold, although they can have more sophisticated forms like simple trees.Haar-like features The features used by the classifiers proposed in [26], inspired from [24], are based on feature prototypes shown in Fig. 7. In [18], this set has been extended with additional 45 degree rotated prototypes, shown in Fig. 8.Fig. 7 Basic feature prototype setFig. 8 Additional rotated feature prototypes in the extended setGiven a square window, all features used are derived from these prototypes by defining its width, height and relative position within the window. Some examples are shown in Fig. 9. Note, for instance, that features in Fig. 9(a) and Fig. 9(b) are both based on the same prototype.Fig. 9 Examples of Haar-like featuresFeature values are computed with respect to a sample that corresponds to a sub-region of the image under a sliding evaluation window. By definition, the value of a feature for each sample is the sum of the pixel values in the white rectangle area subtracted from the corresponding summation in the black rectangle area.3 Aggregation algorithmOnce FIP candidates are detected in the first stage, arrangement of three candidate FIPs that are likely to correspond to the corners of a QR code must be examined in the second stage. In this section, an algorithm that considers size, distance and angle restrictions to perform such examination is proposed. Note that besides these geometrical restrictions, additional information such as the number of overlapping detections or texture around the FIPs could be also used to rule out some subsets or support others. However, taking into consideration the requirement for fast processing, only size, distance, and angle information are considered.The proposed solution for aggregating FIP candidates is presented in Algorithm 1. Lines 1 to 3 correspond to vertex set creation. Lines 4 to 13 correspond to the creation of edges, whenever a pair of vertices satisfy the size and the distance criteria, with respective tolerances. The loop structure from line 14 to 23 is the main part of the algorithm, where cliques of size three whose edges pairwise satisfy the orientation criterion are found. For each edge (u, v), all edges (u, v) that are adjacent to one of its extremities (u) are verified. For each of such pairs of edges (i.e., {(u, v), (u, v)}), first the existence of the third edge (i.e., edge (v, v)) is verified. If the third edge is not there, that means that either the two vertices,v and v do not satisfy the size or distance criteria, or that the third edge has already been processed (in this case, the triplet {u, v, v} is already in the output list). If the third edge (v, v) is present, and if the first two satisfy the orientation condition, then the subset of the three vertices {u, v, v} is added to the output list. Note that there is no need to examine edges that are adjacent to the other extremity (v) since those will be evaluated later. The algorithm endswhen all edges are processed.4 Procedure for Training and Evaluating FIP DetectorsClassifier training and evaluation tools that implement the Viola-Jones’ method are available respectively as opencv-haartraining and opencv-performance utilities in OpenCV 2.0 [4]. For the training of a cascaded classifier, a set of positive samples (cropped image regions containing only a target object) and negative background images (with no target objects) should be provided. For each stage, the training algorithm randomly selects negative samples from the background images that have been misclassified (as positives) by the preceding stages.Another utility available in OpenCV is opencv-createsamples, that allows application of transformations on positive samples with controlled random variations in intensity, rotation and perspective distortion. Examples of transformed samples obtained from a positive sample are shown in Fig. 13.Fig. 13 Examples of samples generated by random transformations on a positive sample4.1 Main Training ParametersThe training process implemented in opencv-haartraining involves several parameters that need to be tuned for each application. Among them, the following parameters have been considered in this work:–Feature set: It can be the basic set shown in Fig. 7 (MODE = Basic) or the basic set in conjunction with the extended set shown in Fig. 8 (MODE = Extended/All).–Symmetry: When the target pattern is symmetrical, the training algorithm can be restricted to consider only half part of the positive samples (SYM = Symmetric/Y) in order to reduce processing time during training, or not (SYM= Asymmetric/N).–Classifier topology: Rather than cascaded stages (MTS = Cascade), it is possible to allow splits (MTS = Tree) that turns the classifier into a simple CART tree [5].–Weak classifier number of splits: A weak classifier in its simplest form is just a single Haar-like feature and a binary threshold. They are combined with other weak classifiers by the boosting algorithm to form a strong classifier corresponding to one stage of the cascade. It is possible to allow weak classifiers to learn more complex relationships in the training pattern by letting them to be not just a single feature (NS = 1) but a simple CART tree with a limited small number of splits (NS > 1). For face detection, empirical observations [17] indicate that there is an increase in cascade performance when splits in the weak classifiers are allowed.–Maximum false alarm rate / Minimum hit rate: Each cascade stage must comply with a maximum false alarm rate (FA) and with a minimum hit rate (HR) for the samples supplied to it in order to be considered trained. A too low false alarm rate requirement may cause the stage to become overly complex diminishing the benefits of the cascade approach. A very high minimum hit rate restriction may have a similar effect.–Number of training samples: The number of positive training samples (SAMPLES).–Size of training samples: All training samples are resized to a fixed dimension (SIZE). For face detection, it has been observed that 20×20 is an appropriate size [17].4.2 Detection Evaluation MetricsA classifier trained using the opencv-haartraining utility can be evaluated using the opencv-performance utility. The performance evaluation utility requires test images with ground-truth data (i.e., positions of the target samples). Such images can be artificially generated by the opencv-createsamples utility, that inserts one target sample in each background image. This, in conjunction to opencv-performance, is useful for automating the performance tests, by providing to them a test set of positive samples and negative background images as the ones provided for training. Figure 14 shows an example of target sample inserted into a background image.Fig. 14 A background image with a FIP inserted around its central positionScaling factor For each position of the image, several samples are obtained by varying the window size from a minimum size to the maximum possible size in that position. Since all samples are resized to the size of the detector, this minimum size should be the SIZE of the detector (i.e. the size of the samples used for training the detector). The scaling factor (SF) determines how window size varies for sampling. For instance, SF = 1.10 means that the size of the processing window will be increased in 10 % at each sampling round in a same position. The larger the scale factor, less samples are considered in each position. Note that the classifier can be considered scale invariant due to this resizing of all samples to a fixed size.Minimum overlapping detections Often more than one sample among those corresponding to small shifts of the window around the target object result in positive detection. In such cases, it is convenient to establish some criteria in order to consolidatemultiple redundant detections into a single detection representing all of them. Naturally, the larger the number of detections that overlap in a given neighborhood, the larger the evidence that there is a target object inthat position. Therefore, a minimum number of overlaps (ND) in the set of overlapping detections can be established as determining a single detection, that is, a set of overlapping detections is considered a detection if and only if the number of detections in the set is at least ND.In the implementation used in this work, two detections are considered overlapping if their position in x and in y coordinates differ by no more than 20 % of the width of the smaller detected sample and their widths differ by no more than 20 %.4.3 Estimation of Training Parameter ValuesViola-Jones framework is widely known and very popular for face detection and the literature concerning the training of the cascade classifier often recommends training practices, parameters and sets, suitable for that application domain [6]. Since FIPs are simpler and much different from face patterns, variation of parameter values for the cascade training of FIP detectors is a subject of study in this work.Due to the large number of parameters in the training process, an exhaustive assessment of possible combinations of parameter values is not feasible. The approach for determining the parameter values used in this work for the cascade training of a FIP detector is similar to the one used in [17] for face detection.The methodology consists in first establishing a sequential order as well as initial values for the parameters to be evaluated. Then, following the established order, the effect of individual parameter variation is assessed while the values of all other parameters are kept fixed. After assessment of a parameter, its initial value is replaced by the best value found, and the assessment proceeds to the next parameter. Although this analysis cannot be considered exhaustive, it provides a very good indication of the parameter variation influence in final detection performance while avoiding the combinatorial explosion that would arise from experimenting all possibilities.Parameter values for training FIP detectors were chosen following the strategy described above. A base set consisting of 380 FIP samples cropped from a variety of different images, and a set of 1500 background images (without QR codes) for the negative samples were divided into training and test sets. All positive samples for training were generated from the 285 FIPs in the base set, applying transformations using the opencv-createsamples utility with intensity variation limited to ±80 and rotation limited in x,y to ±23◦ and in z (perspective) to ±34◦. The test samples were generated from the remaining 95 FIPs applying the same variation in intensity and in x and y, and in z limited to ±23◦. The background images were split into two subsets of equal size (750 images each), being used respectively for training and testing.Initial values of parameters were set to HR = 0.998, ST = 15, SYM = N (Asymmetric), MTS = Cascade, NS =2, FA = 0.5, SAMPLES = 4000 (positives and negatives,4000 each), and SIZE = 20×20. Recall and FP shown for each training is relative to the test set, computed as described in Sect. 4.2 using detector application parameters SF = 1.10 and ND = 1. Dark nodes indicate the values chosen for the respective parameters. Beyond considering just recall and FP, the choice of the best parameter values were made taking into account the simplicity of the resulting classifier and the balance of its cascade (i.e. uniformity of feature quantity among consecutive stages). Moreover, recall values were prioritized over FP because while the FIP aggregation algorithm can not recover undetected FIPs, it does can disregard false FIP detections.5 Experimental ResultsIn this section, experimental results regarding FIP and QR code detection in still images, and frame rates achieved for QR code detection in video images are reported. Some images that illustrate detection results are presented. Additional resulting images can be accessed from URL p.br/demos.5.1 FIP DetectionAfter choosing training parameter values as described in Sect. 4.3, a FIP detector was trained with the chosen parameter values, using a set of 462 positive samples (cropped FIP regions) and 820 background images with no QR codes from where 4000 negative exemplars were randomly sampled for training each stage.The trained FIP detector was evaluated on a validation set A consisting of 74 images containing 222 positive samples (exactly one complete QR code in each image), totally distinct from those in the training set. During this evaluation, the influence on detection performance of two detector application parameters (see Sect. 4.2), scaling factor (SF) and number of overlapping detections (ND), have been analyzed as described below.Scaling factor Figure 17 shows that the scaling factor (SF) directly impacts the quality of results. A wide range of result quality was observed from SF = 1.05 (recall: 0.98 / FP:628) to SF = 1.30 (recall: 0.86 / FP: 93). As the scaling factor is incremented, both recall and FP decrease. Considering that high recall and small FP are desirable, scaling factor of 1.10 as highlighted in the chart (recall: 0.99 / FP: 290) was adopted for the successive experiments.Fig. 17 Recall and FP of the trained FIP detector varying the scaling factor used during FIP detection。
