# detection of irregularities in regular dot patterns[精选推荐pdf]

Research Report 93 Tutkimusraportti 93 DETECTION OF IRREGULARITIES IN REGULAR DOT PATTERNS A. Sadovnikov, J. Vartiainen, J.-K. Kämäräinen, L. Lensu, H. Kälviäinen Lappeenranta University of Technology Department of Information Technology P.O. Box 20 FIN-53851 Lappeenranta ISBN 952-214-009-0 ISSN 0783-8069 Lappeenranta 2005 Detection of Irregularities in Regular Dot PatternsA. Sadovnikov, J. Vartiainen, J.-K. Kamarainen, L. Lensu, H. K¨ alvi¨ ainen Department of Information Technology, Lappeenranta University of Technology, P.O.Box 20, FI-53851 Lappeenranta, FinlandAbstractRaster and halftone images are typically generated using small image elements, dots, which are organized and generated into a periodic structure to reproduce de- sired imaging effect. In this study, a periodic image element structure, referred toas a regular dot pattern, is defined, and based on the definition, two methods are introduced to detect irregularities in regular dot patterns. An example application for the methods is an automatic assessment of Heliotest sample prints. Heliotest assessment is used in the paper and printing industry to measure printability of different paper grades. In the experimental part the proposed methods are applied to detect missing elements, dots, from digitized Heliotest samples which are con- sidered to form a regular dot pattern.1IntroductionIn this study, by regular dot patterns it is referred to images which contain similar dots of a same color and the spatial spacing between dots is regular. Local dot presenta- tions, their shape and color, and spatial spacing of dots may vary, but the variation should be substantially small over the whole image. Thus, locations where featuresdeviate significantly from the normal variation are considered as irregular. One of the most typical application area where regular dot patterns would be present is halftone imaging (e.g., [7]). Correspondingly, a method for an accurate detection of dot pattern irregularities would be useful in the quality control of halftone printing, for example,to find the number of missing dots in rotogravure prints [11]. The main motivation for this work is a quality assessment known as Heliotest paper printability test in the paper and printing industry. Heliotest is recognized as a standard quality assessment and it is currently performed manually by laboratory experts. However, a modern industrial environment sets new quality standards and there is an increasing demand for reliable process and quality control automation. That is the main reason why there is com- mon interest in paper and printing companies to develop an accurate and reproducible missing dot detection method.An image processing sub-field which contains the most similar characteristics with regular dot patterns is evidently textures and texture analysis. However, in texture anal- ysis the most typical problem is to distinguish between different types of textures, and thus, proposed approaches favor between-texture type of processing while in irregu- larity detection a within-texture type of processing is needed. Still, there are many proposed texture characteristics and notations which can be used, i.e., dots can be con- sidered as texture atoms and the dot spacing can be represented as spatial interrela-1tionships between atoms [5]. Related research to regular dot patterns and irregularity detection have been done also in fabric defect detection [4], but the given problem set- ting is also too simple for missing dot detection: fabric defect detection is concerned about “Where is something wrong within the given texture”, but in addition to that it isnecessary to find “What is wrong in the given location”. In other words, one needs tofind both locations where there are irregularities, i.e., local dot presentation fails, and what kind of irregularities they are, a partly or completely missing dot or a group of dots. Several image processing methods for missing dot detection have been proposed, e.g., by Langinmaa [8] and Heeschen and Smith [6], but their accuracy cannot meet industrial requirements. In this study, a more comprehensive treatment is given to regular dot patterns and totheirregularitydetectionfromthem. Theregulardotpatternsarefirstdefinedandbasedon the definition two methods are proposed for an accurate irregularity detection. In the experimental part the proposed methods are applied to missing dot detection from rotogravureteststrips(Heliotest)stripswherethemethodsprovidedetectionaccuraciessufficient for the industrial use.2Regular dot patternsIt is worthwhile to define terms dot and pattern in this context. A dot is a particular type of a texture atom; an indivisible atom which can be represented for example by 2-d Gaussian function. A pattern is a set of spatial coordinates, in which dots are reproduced. Whenthepatternexpressessomedegreeofperiodicityitcanbeconsideredas regular. Similar definitions and results are used in solid state physics and especiallyin definitions of crystal lattice structures [1].2.1Pattern regularityRegularity is a property which means that some mnemonic instances follow predefined rules. In the spatial domain regularity typically means that a pattern consists of a periodic or quasi-periodic structure of smaller pattern units or atoms, and thus, it is worthwhile to explore pattern regularity in terms of periodical functions and especiallyvia their Fourier transforms. The following is mainly based on definitions in solid statephysics and is related to Bravais lattice formulations: A Bravais lattice is an infinite array of discrete points with an arrangement and orientation that appears exactly the same, from whichever of the points the array is viewed. A two-dimensional (2-d) Bravais lattice consists of all points with position vectors R of the formR = n1~ a1+ n2~ a2(1)where ~ a1and ~ a2are any two vectors not both on the same line, and n1and n2range through all integer values. The vectors ~ aiare called primitive vectors and are said to generate or span the lattice. It should be noted that the vectors ~ aiare not unique. In Fig. 1 is shown a portion of a two-dimensional Bravais lattice. [1]The definition of Bravais lattice refers to points, but it can also refer to a set of vectors which represent another structure. A point as an atom can also be replaced with any, preferably locally concentrated, structure. A region which includes exactly one lattice point is called a primitive unit cell and~ ainow define spatial relationship ofunit cells. Unit cells can also be defined as non-primitive but in both cases they must2text?text?text?text?text?text?text?text?text?text?text?text?text?text?text?text?a?a?1?2?P?Q? -?-?Figure 1: A two-dimensional Bravais lattice of no particular symmetry, an oblique net. All the net points are linear combinations of two primitive vectors (e.g. P = ~ a1+2~ a2, and Q = −~ a1+~ a2).fill the space without any overlapping. The primitive and non-primitive unit cells are not unique. [1]2.2Fourier transform of 2-d periodic functionsLet us consider a function f (~ r) (where ~ r = (x,y)) in which the spatial domain is a periodic extension of a unit cell. Periodicity can be formally described. Let M be a 2 × 2 matrix which is invertible and such thatf (M ~ m +~ r) = f (~ r)(2)where ~ m is any 2-dimensional integer vector Now, clearly, every point ~ r in the space can be written uniquely as ~ r = M (~ n + ~ u)(3)where ~ n is a 2-dimensional integer vector and ~ u is a vector where each coordinatesatisfies 0 ≤ ui< 1. An unit cell U (M) is the region in space corresponding to all points M~ u. It can be shown that the volume of unit cell is V = |detM|. The set of all points L(M) of the form M~ n is called the lattice induced by M. A point in the space corresponds a point in the unit cell translated by a lattice vector. Note that a sum of two lattice vectors is a lattice vector and the periodicity of function f implies that its value is invariant under translations by multiples of the lattice vector. A matrixˆM can be obtained by inverting and transposing MˆM = M−T.(4)ForˆM new lattice and unit cell can be associated, called the reciprocal lattice L‡ˆM· and the reciprocal unit cell U‡ˆM· , respectively. If we consider wave numberspace, each vector~k is written uniquely as~k =ˆM‡ ~ κ +~ξ· (5)where ~ κ is a 2-dimensional integer vector and~ξ has all ordinates 0 ≤ ξi< 1. The reciprocal lattice vectors span the lattice pointsˆM~ κ. The fundamental result is that the Fourier transform of a periodic function with aunit cell specified by M has a discrete spectrum, peaks located at the reciprocal lattice3points specified byˆM [1]. That is, the wavenumber vectors are constrained to lie at the reciprocal lattice points. The explicit transform and inverse transform formulas areˆfM‡~ k· =1 |detM|Z~ r∈U(M)f (~ r)e−j(~k·~ r)dV (~ r) ,~k ∈ L‡ˆM· (6)and f (~ r) =X~k∈L(ˆM)ˆfM‡~ k· ej~k·~ r.(7)The discrete spectrum can be interpreted as a continuous spectrum consisting of Dirac impulse functions located at the reciprocal lattice pointsˆf‡~ k· =X~ κ∈ZDˆfM‡ˆM~ κ· δ‡~ k −ˆM~ κ· .(8)2.3Fourier transform of 2-d quasi-periodic functionsIn the general case we can take a 2-d image which is approximately periodic (quasi-periodic). Consider a pattern image whose unit cell and lattice structures are specified by M. If this image is unbounded in all directions, and we can consider a function which is periodic (i.e., invariant under translation by a lattice vector), then it is the superposition of waves whose wavenumber vectors are necessarily precisely latticevectors in the reciprocal lattice, specified byˆM = M−T.However, a real image has a finite extent and has imperfections (irregularities). The ideally periodic function is constrained to satisfy certain boundary conditions. We illustrate the consequences of this by considering the situation, where the pattern iscomprised only a finite number of translates of the unit cell. Let V denote the finite region occupied by the pattern, and consider the window function wV(~ r) defined aswV(~ r) =‰1,~ r ∈ V 0,otherwise(9)If f (~ r) is the ideal, truly periodic function (with periodicity specified by M) and fV(~ r) is the truncated functionfV(~ r) = wV(~ r)f (~ r) =‰f (~ r) ,~ r ∈ V 0,otherwise(10)then fV(~ r) has a continuous spectrum given byˆfV‡~ k· =X~ κ∈Z3ˆfM‡ˆM~ κ· ˆ wV‡~ k −ˆM~ κ· (11)where ˆ wVis the Fourier transform of wV. It can be shown that ˆ wVcontains a continuous spectrum which has infinite extent, but which fades out proportionately fast with 1/flflfl~kflflfl. The most important result is that quasi-periodic functions have quasi-discrete spec- tra, with the spectral energy concentrated at points in the reciprocal lattice.42.4Pattern irregularityIn terms of function periodicity, pattern irregularity can be defined as an aperiodic function ε(x,y), with spatial energy | ε |¿| fV|. Finally, the initial 2-d pattern image can be represented asfV(~ r) = wV(~ r)f (~ r) + ε(~ r)(12)and the problem is to separate the regular part wV(~ r)f (~ r) and the irregular part ε(~ r) as accurately as possible.3Extracting regular pattern informationAs it was described in the previous section the formation of model of the ideal regular part of an image is crucial for the irregularity detection; the more accurate model canbe established the more accurate detection and classification of irregularities can be made. The details level needed for the regular part formation is particularly high for ex- ample in Heliotest images [12], and thus, typical texture segmentation methods (e.g.[5]) or defect detection methods (e.g. [4]) cannot provide a sufficient accuracy. One attractive approach to estimate an ideal regular pattern is to form an analytical model and to estimate model parameters based on an input image. This approach has been proposed for example in [4], but this requires a correct and very accurate ana- lytical model, in which case, the parameter estimation may become very unstable and slow. Typically real images do not correspond any analytical models but they contain distortions and noise. Due to these facts it is motivated to use the analytical model only as a restricting bias in the regular pattern formation and allow incompleteness by ex- tracting the regular pattern from an input image itself. This approach has been appliedin the frequency domain self-filtering to emphasize regular patterns [2] and will be the case in the approaches proposed in this study as well. Results from the regular lattices and the reciprocal lattice are applied, but only to estimate appropriate model parame- ters while details are extracted from an input image. What affects to the selection of this approach will be discussed next.3.1Spatial modeling limits of accuracyBefore it is proposed how to extract the ideal regular pattern from an input image it is important to explain why all parameters of the analytical model cannot be directly esti- mated. Different kind of analytical models would be the most obvious solutions since they are commonly used in a regular dot pattern synthesis, e.g., in digital halftoning [7], and also used in defect detection (e.g. [4]). In the context of regular dot patterns the analytical expression in (12) can be used, but the limits of accuracy prevent to estimate the model parameters directly; practical restrictions due to the discrete image resolu- tion which cannot be bypassed. For the same reason, the limited available resolution, a halftone synthesis is not necessarily reversible.In Fig. 2(a) is shown a simplified model of regular dot patterns which can also be used to describe the pattern in Heliotest assessment [11, 12]. Parameters of the model can be divided in the following classes:1. Image geometry parameters, i.e., lattice primitive vectors ~ a1, ~ a2(see Fig 2(a)) and overall lattice shift vector ~ s.52. Unit cell model parameters. For example, in the case of Heliotest it can be a 2-d Gaussian hat (see Fig 2(b)).a?a?2?_?_?1?(a)−505−50500.511.52(b)Figure 2: Simple model of regular dot pattern (Heliotest): (a) 2-d lattice structure (~ a1, ~ a2- primitive vectors); (b) Gaussian dot model (µ,Σ,A).The estimation of all above-mentioned parameters is necessary in order to generate an accurate ideal regular pattern model which can be used in irregularity detection by comparing or subtracting it from the observed image. However, the estimation is not trivial; it can be performed with search or generic optimization methods where a target function to be minimized is for example energy difference between observed image and model. Unfortunately the number of optimized parameters is very high and they cannot be independently optimized.The first step in the pattern modeling is estimation of the lattice parameters (~ a1, ~ a2) representing periodicity (lattice matrix M). These parameters can be derived using a number of techniques: using image autocorrelation space, image texture statistics(gray-level sta