A data hiding technique in JPEG compressed domain

T HE SCIENTIST AT THE OTHEREND OFtoday’s data collection machinery—whether a satellite collecting data from a remote sensing platform, a tele-scope scanning the skies, or a micro-scope probing the minute details of a cell—is typically faced with the prob-lem: What do I do with all the data? Scientific instruments can easily gen-erate terabytes and petabytes of data at rates as high as gigabytes per hour. There is a rapidly widening gap between data collection capabilities and the ability to analyze the data. The traditional approach of a lone investi-gator staring at raw data in pursuit of (often hypothesized) phenomena or underlying structure is quickly becom-ing infeasible. The root of the prob-lem is that data size and dimensionali-ty are too large. A scientist can work effectively with a few thousand obser-vations, each having a small number of measurements, say five. Effectively digesting millions of data points, eachwith tens or hundreds of measure-ments, is another matter.When a problem is fully understoodand the scientist knows what to lookfor in the data through well-defined procedures, data volume can be han-dled effectively through data reduc-tion.1By reducing data, a scientist is U s a m a F a y y a d,D a v i d H a u s s l e r,a n dP a u l S t o l o r zTERRYWIDENERMining Scientific DataDigesting millions of data points, each with tens or hun-dreds of measurements—generally beyond a scientist'shuman capability—can be turned over to data miningtechniques for data reduction, which functions as aninterface between the scientist and large datasets.1Data reduction is a term used in science data analysisto refer to the extraction of essential variables of inter-est from raw observations. Particularly appropriatewhen dealing with image datasets, it involves transfor-mation, selection, and normalization operations.COMMUNICATIONS OF THE ACM November 1996/Vol. 39, No. 1151effectively bringing data size down to a range that is analyzable.In scientific investigation, because we are often interested in new knowledge, effective data manipulation and exploratory data analysis looms as one of the biggest hurdles in the way of exploiting the data. In this article, we give an overview of the main issues in the exploitation of scientific datasets through automated methods, pre-sent five case studies in which knowledge discovery in databases (KDD) tools play important and enabling roles, and conclude with future challenges for data mining and KDD techniques in science data analysis.Data Reduction and Data Types D ATA mining and KDD techniques for automated data analysis can and do play an importantrole as an interface between sci-entists and large datasets. Machines are still far from approaching human abilities in the areas of synthesis of new knowledge, hypothesis formation, and creative modeling. The processes of drawing insight and conducting investigative analyses are still clearly in the realm of tasks best left to humans. Howev-er, automating the data reduction procedure is a significant niche suitable for computers. Data reduction involves cataloging, classification, segmentation, parti-tioning of data, and more. It is the most tedious stage of analysis, typ-ically involving manipulation of enormous amounts of data. Once a dataset is reduced (say to a cata-log or other appropriate form), the scientist can proceed to ana-lyze it using more traditional (manual), statistical, or visualiza-tion techniques. The higher lev-els of analysis include theoryformation, hypothesis of newlaws and phenomena, filteringwhat is useful from background,and searching for hypothesesthat require a large amount ofhighly specialized domainknowledge.Data comes in many forms—from measurements in flat files tomixed (e.g., multispectral/multi-modal) data including time series(e.g., sonar signatures and DNAsequences), images, and struc-tured attributes. Most data min-ing algorithms in statistics andKDD [3] (see also Glymour's arti-cle in this special section) aredesigned to work with data in flatfiles of feature vectors.Data types include:Image mon in scienceapplications, image data offersunique advantages in that it isrelatively easy for humans toexplore and digest. On theother hand, image data posesserious challenges on the datamining side. Feature extractionis the dominant problem; usingindividual pixels as features istypically problematic, since asmall portion of an image easilyturns into a high-dimensionalvector.2Time-series and sequence data.Challenges here include extract-ing stationary characteristics ofan entire series, whether or not itis stationary; if it is not stationary(e.g., in the case of DNAsequences), segmentation isneeded to identify and extractnonstationary behavior and tran-sitions between quantitatively Machines arestill far fromapproachinghuman abilitiesin the areas ofsynthesis of newknowledge,hypothesisformation, andcreativemodeling.52November 1996/Vol. 39, No. 11 COMMUNICATIONS OF THE ACMand qualitatively different regimes in the series. An effective means for dealing with sequence data is to infer transition probabilities between process state variables from the observed data. A particularly suc-cessful class of techniques used in this type of mining is hidden Markov models (HMMs) [8], which have been extensively developed in the context of speech recognition. An HMM describes a series of observa-tions by a “hidden’’ stochastic process—a Markov process.In the case of speech, the observations are sounds forming words, and a model represents a hidden ran-dom process that generates certain sequences of sounds, constituting variant pronunciations of a sin-gle word, with high probability. In modeling proteins, a word corresponds to a protein sequence, and a fam-ily of proteins with similar structure or function can be viewed as a set of variant pronunciations of a word. This observation allows a large amount of mathemat-ical and algorithmic HMM machinery developed in the context of speech processing to be adapted and applied to protein modeling, greatly reducing imple-mentation and development time and allowing impressive results to be obtained quickly [5]. Numerical measurements vs. categorical values. While a majority of measurements (e.g., pixels and sensors) are numeric, some notable examples (e.g., protein sequences) consist of categorical measure-ments. The advantage of dealing with numerical data is that the notion of distance between any two data points (feature vectors) is easier than defining dis-tance metrics over categorical-value variables. Many classification and clustering algorithms rely funda-mentally on the existence of a metric distance and the ability to define means and centroids.Structured and sparse data.In some problems, vari-ables may have some structure to them (e.g., hierar-chical attributes or conditional variables that have different meanings under different circumstances). In other cases, different variables are measured for different observations, rendering flat-file representa-tion inappropriate.Reliability of data (sensor vs. model data). Raw sen-sor-derived data is often assimilated to provide a smooth homogeneous data product. For example, regular gridded data is often required in climate stud-ies, even when data points are collected haphazardly, raising the question of data reliability; some data points need to be dealt with especially carefully, as they may not correspond to direct sensor-derived information.Case StudiesFive case studies illustrate the contribution and potential of KDD for science data analysis. For each case, our focus is primarily the application's impact, the reasons why KDD systems succeeded, the limita-tions of techniques, and future challenges.Sky Survey CatalogingThe 2nd Palomar Observatory Sky Survey (POSS-II) took more than six years to complete. The survey con-sisted of 3TB of image data containing an estimated 2 billion sky objects. The 3,000 photographic images are scanned into 16-bit/pixel-resolution digital images at 23,040ϫ23,040 pixels per image. The basic problem is to generate a survey catalog recording the attributes of each object along with its class (e.g., star or galaxy). The attributes are defined by the astronomers.Once basic image segmentation is performed, 40 attributes per object are measured. The problem is identifying the class of each object. Once the class is known, astronomers can conduct all sorts of scientif-ic analyses, like probing galactic structure from star and galaxy counts, modeling evolution of galaxies, and studying the formation of large structure in the universe [13]. To achieve these goals, we developed the Sky Image Cataloging and Analysis Tool (SKI-CAT) system [12].D ETERMINING the classes for faint objectsin the survey is a difficult problem. Themajority of objects in each image arefaint objects whose class cannot bedetermined by visual inspection or clas-sical computational approaches in astronomy. Our goal was to classify objects at least one isophotal mag-nitude fainter than objects classified in previous com-parable surveys. We tackled the problem using decision-tree learning algorithms (see chapter 19 in [3]) to accurately predict the classes of objects. The accuracy of the procedure was verified through a very limited set of high-resolution charged-couple device (CCD) images as ground truth.By extracting rules via statistical optimization over multiple trees (see chapter 19 in [3]), we achieved 94% accuracy in predicting sky object classes. Reliable classification of faint objects increased the number of objects classified (usable for analysis) by 300%. Hence, astronomers could extract much more out of the data in terms of new scientific results [12].SKICAT's classification scheme recently helped aCOMMUNICATIONS OF THE ACM November 1996/Vol. 39, No. 1153team of astronomers discover 16new high red-shift quasars in at least one order of magnitude less observation time [4]. These objects are extremely difficult to find and are some of the farthest (hence oldest) objects in the uni-verse. They provide valuable and rare clues about the early history of the universe.SKICAT was successful for sev-eral reasons:• The astronomers solved the fea-ture extraction problem—the proper transformation from pixel space to feature space.This transformation implicitly encodes a significant amount of prior knowledge.• Within the 40-dimensional fea-ture space, at least eight dimen-sions are needed for accurate classification. Hence, it was dif-ficult for humans to discover which eight of the 40 to use, let alone how to use them in classi-fication. Data mining methods contributed by solving the clas-sification problem.• Manual approaches to classifica-tion were simply not feasible.Astronomers needed an auto-mated classifier to make the most of the data.• Decision-tree methods,although involving blind greedy search (see Fayyad's overview article on the KDD process in this special section) proved to be an effective tool for finding the important dimensions for this problem.Directions being pursued now involve clustering the data.Unusual or unexpected clusters in the data might be indicative of new phenomena, perhaps even a new discovery. A difficulty here is that new classes are likely to be rare in the data (one per millionobservations), so algorithms need to be tuned to looking for small interesting clusters rather than ignoring them as noise or out-liers.Finding Volcanoes on VenusThe Magellan spacecraft orbited the planet Venus for more than five years and used synthetic aperture radar (SAR) to map the surface of the planet, penetrating the gas and cloud cover that per-manently obscures the surface in the optical range. The resulting dataset is a unique high-resolu-tion global map of an entire planet. We have more of the planet Venus mapped at the 75-m/pixel resolution than we do of the Earth’s surface (since most of the Earth’s surface is covered by water). This dataset is uniquely valuable because of its complete-ness and because Venus is the most similar planet to Earth in size. Learning about the geologi-cal evolution of Venus could offer valuable lessons about Earth.The sheer size of the dataset prevents planetary geologists from effectively exploiting its con-tent. The first pass of Venus using the left-looking radar yielded more than 30,000 images at 1,000ϫ1,000 pixels each. To help a group of geologists at Brown University analyze this dataset, the Jet Propulsion Laboratory devel-oped the Adaptive Recognition Tool (JARtool) [1]. The system seeks to automate the search for an important feature on the plan-et—small volcanoes—by training the system via examples. The geol-ogists would label volcanoes on a few (say 30 to 40) images, and the system would then automatically construct a classifier that would proceed to scan the rest of the image database and attempt to54November 1996/Vol. 39, No. 11 COMMUNICATIONS OF THE ACMKDD applications in science may generally be easier than applications in business, finance,or other areas—mainly because science users typically know their data in intimatedetail.locate and measure the planet's estimated 1 million small volcanoes. Note the wide gap between the raw collected data (pixels) and the level at which scien-tists operate (catalogs of objects). In this case, unlike the case with SKICAT, the mapping from pixels to features would have to be done by the system. Hence, little prior knowledge is provided to the data mining system.JARtool uses an approach based on matched filter-ing for focus of attention (triggering on candidates that vaguely resemble volcanoes and having a high false detection rate) followed by feature extraction based on projecting the data onto the dominant eigen-vectors in the training data, and then by classification learning to distinguish true detections from false alarms. The tool matches scientist performance for certain classes of volcanoes (e.g., high-probability vol-canoes vs. those scientists are not sure about) [1]. Lim-itations include sensitivity to variances in illumination, scale, and rotation. This approach does not, however, generalize well to a wider variety of volcanoes.The use of data mining methods here was motivat-ed by several factors:• Scientists did not know much about image process-ing or about the SAR properties. Hence, they could easily label images but could not design rec-ognizers.• As is often the case with cataloging tasks, there is little variation in illumination and orientation of objects of interest, making mapping from pixels to features an easier problem.• The geologists were motivated to work with us; they lacked other easy means for finding small vol-canoes.• The result is to extract valuable data from an extensive dataset. Also, the adaptive approach (training by example) is flexible and would in principle lends itself to reuse in other tasks. D UE to the proliferation of image data-bases and digital libraries, data min-ing systems capable of searching forcontent are becoming a necessity. Indealing with images, the train-by-example approach, or querying for “things that look like this,” is a natural interface, since humans can visually recognize items of interest, but trans-lating those visual intuitions into pixel-level algo-rithmic constraints is difficult to do. Work is proceeding to extend JARtool to other applica-tions, like classification and cataloging of sunspots.Biosequence DatabasesIn its simplest computer form, the human genome is a string of about 3 billion letters containing instances of four letters—A, C, G, and T, representing the four nucleic acids, the constituents of DNA, strung togeth-er to make the chromosomes in our cells. These chro-mosomes contain our genetic heritage, a blueprint for a human being. A large international effort is under way to obtain this string, but obtaining it is not enough; the string has to be interpreted. DNA is first transcribed into RNA and then trans-lated in turn from RNA into pro-teins to form the actualbuilding blocks (chromo-somes) of our makeup. Theproteins do most of the workwithin the cell, and each ofthe approximately 100,000 dif-ferent kinds of protein in ahuman cell has a unique struc-ture and function. Elucidating thestructures and functions of proteins and structural RNA molecules (for humans and for other organ-isms) is the central task of molecular biology.In biosequence databases, there are several press-ing data mining tasks, including:• Find the genes in the DNA sequences of various organisms from among DNA devoted in part to other functions as well. Gene-finding programs, such as GRAIL, GeneID, GeneParser, GenLang, FGENEH, Genie, and EcoParse (see e.g., [6, 7, 9]), use neural nets and other artificial intelli-gence or statistical methods to locate genes in DNA sequences.3Looking for ways to improve the accuracy of these methods is a major thrust of cur-rent research in this area.• Develop methods to search the database for sequences that have higher-order structure or function similar to that of the query sequence, rather than doing a more naive string matching on the sequences themselves. The unique folded structure of each biomolecule (e.g., protein and RNA) is crucial to its function.Two popular systems for modeling proteins, based on the HMM ideas mentioned earlier, are HMMerand SAM. HMMs and their variants have also beenCOMMUNICATIONS OF THE ACM November 1996/Vol. 39, No. 1155applied to the gene-finding problem [6, 7] and to the problem of modeling structural RNA.4The gene-finding methods GeneParser, Genie, and EcoParse,mentioned earlier, are examples of this. RNA analy-sis uses an extension of HMMs called stochastic con-text-free grammars. This extension permits modeling certain types of interactions among letters of a sequence that are distant in the primary structure but adjacent in the folded RNA structure, a function simple HMMs cannot perform.COMPUTER -BASEDanalysis of biose-quences increasingly affects the field of biology. Computational biose-quence analysis and database search-ing tools are now an integrated andessential part of the field, leading to numerous important scientific discoveries in the last few years.Most have resulted from database searches revealing unexpected similarities between molecules previ-ously not known to be related. However, these meth-ods are increasingly important in the direct determination of structure and function of biomol-ecules as well.HMMs and related models have been successful in helping scientists with this task because they provide a solid statistical model flexible enough to incorpo-rate important biological knowledge. The key chal-lenge is to build computer methods that can interpret biosequences using a still more complete integration of biological knowledge and statistical methods at the outset, allowing biologists to operate at a higher level in the interpretation process, where their creativity and insight is of maximum value.Geosciences: Quakefinder and CONQUESTA major problem facing scientists in such domains as remote sensing is the fact that important signals about temporal processes are often buried within noisy image streams, requiring the application of sys-tematic statistical inference concepts in order for raw image data to be transformed into scientific under-standing.One class of problems that exploit inference in this way is the measurement of subtle changes in images. Consider, for example, the case of two images, taken before and after an earthquake. If the earthquake fault motions are much smaller in mag-nitude than the pixel resolution (a relatively com-mon scenario), it is essentially impossible to describe and measure the fault motion by simply comparing the two images manually (or even by naive differenc-ing by computer). However, by repeatedly register-ing different local regions of the two images (a task known to be doable to subpixel precision), it is pos-sible to infer the direction and magnitude of ground motion due to the earthquake. This fundamental concept is broadly applicable to many data mining situations in the geosciences and other fields, includ-ing earthquake detection, continuous monitoring of crustal dynamics and natural hazards, target identifi-cation in noisy images, and more.One example of such a geoscientific data mining system is Quakefinder [10], which automatically detects and measures tectonic activity in the Earth’s crust by examining satellite data. Quakefinder has been used to automatically map the direction and magnitude of ground displacements due to the 1992Landers earthquake in Southern California over a spatial region of several hundred square kilometers at a resolution of 10 m to a (sub-pixel) precision of 1 m. It is implemented on a 256-node Cray T3D par-allel supercomputer to ensure rapid turnaround of scientific results. The issues of developing scalable algorithms and their implementation on scalable platforms addressed here are in fact quite general and are likely to influence the great majority of future data mining efforts geared to the analysis of genuinely massive datasets.In addition to automatically measuring known faults, the system permits a form of automatic knowledge discovery by indicating novel unex-plained tectonic activity away from the primary Landers faults—activity never before observed.Future work will focus on the measurement of con-tinuous processes over many images, instead of simply abrupt behavior seen during earthquakes,and to related image-understanding problems.Analysis of atmospheric data is another classic area in which processing and data collection power has far outstripped our ability to interpret the results. The mismatch is huge between pixel-level data and scientific language that understands such spatiotemporal patterns as cyclones and tornadoes.Cross-disciplinary collaborations attempt to bridge this gap, as exemplified by the team formed by JPL and UCLA to develop COncurrent QUErying Space and Time (CONQUEST) [11].Parallel supercomputers were used in CON-QUEST to implement queries concerning the pres-56November 1996/Vol. 39, No. 11 COMMUNICATIONSOF THE ACMence, duration, and strength of extratropical cyclones and distinctive blocking features in the atmosphere, scanning through this dataset in minutes. Upon extraction, the features are stored in a relational database. This content-based indexing dramatically reduces the time required to search the raw datasets of atmospheric variables when further queries are formulated. The system also features parallel imple-mentations of singular value decomposition and neural network pattern recognition algorithms in order to identify spatiotemporal features as a whole. The long-term hope is that a common set of flexible, extensible, and seamless tools can be applied across a number of scientific domains.Conclusions and ChallengesSeveral issues need to be considered when contem-plating a KDD application in science datasets. Some are common with many other data mining applica-tions (e.g., feature extraction, choice of data mining tasks and methods, and understandability of derived models and patterns) [3]. Some considerations are more important in science applications than in financial or business KDD applications, including: • Ability to use prior knowledge during mining (more documented knowledge is typically avail-able in science applications);• More stringent requirements for accuracy (e.g., better than 90% accuracy was required for SKI-CAT);• Issues of scalability of machines and algorithms (e.g., parallel supercomputers used in scientific applications); and• Ability to deal with minority (low-probability) classes, whose occurrence in the data is rare, asin SKICAT clustering.In conclusion, we point out that KDD applica-tions in science may generally be easier than appli-cations in business, finance, or other areas—mainly because science users typically know their data in intimate detail. This knowledge allows them to intu-itively guess the important transformations. Scien-tists are trained to formalize intuitions into procedures and equations, making migration to computers easier. Background knowledge is usually available in well-documented form (papers and books), providing backup resources when the initial data mining attempts fail. This luxury (sometimes a burden) is not usually available in nonscientific fields.References1.Burl, M.C., Fayyad, U., Perona, P., Smyth, P., and Burl, M.P.Automating the hunt for volcanoes on Venus. In Proceedings of Computer Vision and Pattern Recognition Conference (CVPR-94) (Seattle 1994). IEEE Computer Science Press, Los Alamitos, Calif., 1994, pp. 302–308.2.Chothia, C. One thousand families for the molecular biologist.Nature 357 (1992), 543–544.3.Fayyad, U., Piatetsky-Shapiro, G., Smyth, P., and Uthurusamy,R. Advances in Knowledge Discovery in Databases. MIT Press, Cam-bridge, Mass., 1996.4.Kennefick, J.D., DeCarvalho, R.R., Djorgovski, S.G., Wilber,M.M., Dickinson, E.S., Weir, N., Fayyad, U., and Roden, J.Astron. J. 110, 1 (1995), 78–86.5.Krogh, A., Brown, M., Mian, I.S., Sjolander, K., and Haussler,D. Hidden Markov models in computational biology: Applica-tions to protein modeling. J. Mol. Biol. 235(1994), 1501–1531.6.Krogh, A., Mian, I.S., and Haussler, D. A hidden Markov modelthat finds genes in E. coli DNA. Nucleic Acids Res. 22(1994), 4768–4778.7.Kulp, D., Haussler, D., Reese, M., and Eeckman, F. A general-ized hidden Markov model for the recognition of human genes in DNA. In Proceedings of the Conference on Intelligent Systems in Molecular Biology(1996). AAAI Press, Menlo Park, Calif., 1996.8.Rabiner, L.R. A tutorial on hidden Markov models and select-ed applications in speech recognition. Proc. IEEE 77 (1989), 257–286.9.Snyder, E.E., and Stormo, G.D. Identification of coding regionsin genomic DNA sequences: An application of dynamic pro-gramming and neural networks. Nucleic Acids Res. 21 (1993), 607–613.10.Stolorz, P., and Dean, C. Quakefinder: A scalable data miningsystem for detecting earthquakes from space. In Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining (Portland, Oreg., 1996), AAAI Press, Menlo Park, Calif., 1996.11.Stolorz, P., Nakamura, H. Mesrobian, E., Muntz, R.R., Shek,E.C., Mechoso, C.R., Farrara, J.D. Fast spatiotemporal datamining of large. geophysical datasets. In Proceedings of the 1st International Conference on Knowledge Discovery and Data Mining (Montréal, Aug. 1995), AAAI Press, Menlo Park, Calif. 1995, pp. 300–305.12. Weir, N., Fayyad, U.M., and Djorgovski, S.G. Automatedstar/galaxy classification for digitized POSS-II. Astron. J. 109, 6 (1995), 2401–2412.13.Weir, N., Djorgovski, S.G., and Fayyad, U.M. Initial galaxycounts from digitized POSS-II. Astron. J. 110, 1 (1995), 1–20.Additional references for this article can be found at /research/datamine/CACM-DM-refs/.USA MA FA YYA D is senior researcher at Microsoft and a Distin-guished Visiting Scientist at the Jet Propulsion Laboratory, Califor-nia Institute of Technology. He can be reached at fayyad@.DAVID HAUSSLER is a professor of computer science at the Uni-versity of California, Santa Cruz. He can be reached at haussler@.PAUL STOLORZ is technical group supervisor at the Jet Propul-sion Laboratory, California Institute of Technology. He can be reached at pauls@.Permission to make digital/hard copy of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage, the copyright notice, the title of the publication and its date appear, and notice is given that copying is by permission of ACM, Inc. To copy otherwise, to republish, to post on servers, or to redistribute to lists requires prior specific permission and/or a fee.© ACM 0002-0782/96/1100 $3.50COMMUNICATIONS OF THE ACM November 1996/Vol. 39, No. 1157。

第26卷第5期1997年10月　信息与控制Info rmation and Co ntro lV ol.26,No.5　Oct.,1997JPEG压缩编码的扩充自适应量化器设计†马　钺(中国科学院沈阳自动化研究所　沈阳　110003)摘　要　在JPEG静止图象压缩的基础上,设计了一种扩充的自适应量化器.利用人眼的视觉特征,通过分析M CU块的局部视觉活动性,以M CU活动性函数确定量化因子,并引入亮度掩盖算子调节量化参量.实验结果表明,本文所设计的自适应量化器能减少图象编码主观失真,改善图象质量,获得更好的压缩效果.⒇关键词　JPEG算法,自适应量化,视觉特征1　引言JPEG是连续色调静止图象压缩的国际标准,该标准已广泛应用于计算机和通信等领域,例如电视图象压缩、多媒体通信、多媒体计算机、图象数据库等.JPEG的基本过程是,将源图象YUV象素块经DCT变换成频率矩阵值,然后经量化运算产生压缩频率值的矩阵,再进行熵编码而得到最后的压缩比特流.编码比特流可以数字存储或传输,然后通过一个相反的过程解压缩,再生成象素图象.在JPEG编码处理中,量化过程是至关重要的.量化是将DCT系数进行尺寸变换,并将所得结果截取变为整数值的过程.量化的目的是进一步压缩数据,即丢弃那些无显著视觉意义的信息.量化的策略是对图象内容中较平坦的部分,即对应频域中低频成分,采用较小的量化步长;而图象小的细节,即人眼不太敏感的高频部分,采用较大量化步长,以获得更高的压缩比.JPEG中对DCT系数使用均匀量化器进行量化,其定义为[1]S qi,j=Integ er Ro und(S i,j/ Q i,j),S i,j为量化后的DC T系数,Q i,j为量化权矩阵对应的量化系数.然而这样的量化是线性的,不能精确的反映图象内容局部变化特征,增加了图象编码的主观失真,影响图象质量.JPEG标准内没有包含自适应量化,但是自适应量化可以很显著地提高在给定比特率下的图象质量.从发展趋势来看JPEG标准最可能添加的模块是自适应量化[2].本文在基于JPEG基本系统下,设计了扩充的自适应量化器.它根据图象局部活动性特征和背景亮度来调节量化因子.本文首先提出自适应量化的策略,研究如何用图象局部活动性和背景亮度特征来确定量化因子,然后对模拟实验结果加以讨论.2　自适应量化自适应视觉量化的目的是要调节最终的量化级,以使视觉敏感区域能得到相对细量化,而对视觉不敏感的区域可相对粗量化.本文所设计的量化过程是基于JPEG顺序模式,并对源图象的YUV3个分量中的UV色度分量在水平和垂直方向上进行亚取样.这样编码的M CU⒇1997-02-24收稿†辽宁省科委资助课题(最小编码单元)包含了4个Y分量,1个U分量和1个V分量.JPEG标准对8×8的数据单元给出了缺省量化表,在实际应用中也可以根据需要构造更合适的量化表.本文的自适应量化就是在量化权矩阵的基础上,引入自适应量化因子进行调节,以期提高量化性能.这一量化器部分地引用了M PEG-2TM5[4]的帧内编码量化机制,量化公式如下:S qi,j =int[S i,jq p×Q ij], i,j=1,2,…,8式中S i,j为DCT系数,S q i,j为量化结果,Q i,j为量化权矩阵系数,量化级因子q p由下式给出q p=k×Nact P其中k为该图象可调节的量化等级,Nact P则是反映该M CU复杂程度的归一化活动性函数,其定义为N act P=2×act P+AV Eact P act P+2×AV Eact P式中act P为该M CU的亮度活动性,是其4个亮度子块的象素方差最小值,它反映了M CU的复杂程度;AV Eact P为该帧图象所有8×8亮度块的方差均值,它提升了图象的平均活动性,能准确地反映图象中等活动区视觉特征.注意,在计算AV Eact P时不是严格地按顺序操作模式进行,可使用足够大的缓冲区来存储图象所有DCT系数.M CU活动性函数考虑到人眼的视觉特征,因人眼对高频成份不太敏感,块内容复杂,均方值大时,进行较粗量化;相反当块内细节较少,均方值小时,则进行较精细的量化,从而合理地分配码字.为提高自适应量化的精确度,更细致地反映图象的局部视觉特性,可对M CU进行平坦区、平坦背景下的强边缘区和活动性不一致区的视觉活动性做进一步分析.并首先根据M CU 中4个8×8亮度子块的个别特性,将这些区域从图象中区分出来,根据不同活动区特性对量化因子作适当修正,降低活动不一致区的码字;适当增加平坦区和平坦背景下的强边缘区等视觉敏感区的码字.从而进一步减少量化失真,改善图象质量.以上这些细致量化方案都是以增加编码的计算量为代价的.然而,上面所介绍的M CU活动性定义并未考虑到在不同背景亮度下的视觉敏感性差异.根据人眼的视觉对比灵敏度特征分析[6],可知在人眼对中等亮度背景下的亮度变化较灵敏,而在高亮度区和低暗区极不灵敏.由此引入M CU相对背景亮度的定义B=|14∑4i=1DC i-1024|/1024式中DC i为4个亮度块的DC T直流系数.由于JPEG规定DCT系数值域为[-2048,2047],直流系数实际取值范围为[0,2048],因此本文选取1024为中等亮度值.上式有0≤B≤1,则引入亮度修正算子为B msk=1+B2上式表示,当某M CU的平均亮度接近中间亮度时,B msk≈1;当平均亮度很高或很低时,B msk会有所增加.另外,还可根据在亮背景区和暗背景区的不同,对B msk进行细致调节.综上所述,本文建议的量化计算公式为q p=k×Nact P×B msk380信　息　与　控　制26卷　这一自适应量化因子,充分利用视觉的亮度掩盖原理来调节量化参量,在视觉不敏感的高亮度区和低暗区使量化参量提高,得到较粗的量化;而在中等亮度区量化参量降低,量化较为精细.3　模拟实验结果通过计算机模拟实验,在其他模块完全相同的情况下,分别采用本文提出的自适应量化器与JPEG 一般量化器对两幅图象进行压缩编码.对比实验结果在下面表1中,表明在图象压缩质量基本相同的情况下,自适应量化器可提高近23%的压缩比.同样也可得出,在压缩比相同的情况下,图象压缩质量也可提高.表1　对比实验结果实验图象一般量化器自适应量化器压缩比均方误差压缩比均方误差Girl (128×128×8bits )18.658.8122.758.76Lenna (256×256×8bits )14.3107.4317.7107.284　结束语本文提出了一种JPEG 压缩编码下,扩充的自适应量化策略,通过分析M CU 的局部活动特性,动态调节量化因子,从而达到均匀分布图象编码失真,提高图象质量的目的.在实践中为尽量符合JPEG 标准,在图象压缩数据结构上采用每个M CU 的开头加入二进制码的方式,以通知解码器此时需要对量化权矩阵进行修改的量化因子.参　考　文　献1　W allace G K.The JPEG Still Picture Comp ression m ACM ,34(4):30～442　W illiam B Penn ebaker ,Joan L M itch ell .JPEG Still Image Data Com pres sion Standard .ITP Pres s ,19953　Sherlock B G .A M odel for JPEG Quan tiz ation .ISS IPPNN '944　M PEG,M PEG-2Tes t M odel 5,ISO /IEC JTC1/S C29/W G11/N0400,19935　孙　军等.M PEG-2视频编码的自适应量化器设计.通信学报,1995,16(5):102～1066　姚庆栋等.图形编码基础.北京:人民邮电出版社,1984:36～39A DESIGN OF ADAPTIVE QUA NTIZER FOR JPEG CODI NGM A Yue(Shenyang Institute of Automation ,Ch inese Aca demy of Scien c es ,Shenyang 110003)Abstract Based upon JPEG still imag e co mpressio n standa rd ,an ex panded adaptiv e qua ntizer is pre-sented in this paper.Acco rding to the visual perceptio n,visual activities ar e a naly zed to ex ploit lo cal percep-tual cha racteristic in the M CU.The adaptiv e quantiza tion facto r is decided based on the M CU ac tiv ity func-tio n ,a nd a brig htness masking oper ato r is int roduced to modify the quanti zatio n scales .Ex periment r esult show s tha t the co ding distor tio n is unifor mly decreased w ith the pr oposed qua ntizer,pictur e quality is im-prov ed,and a bet ter coding effec t is acquir ed.Key words JPEG algo rithm,adaptiv e quantizer ,perceptua l charac teristic作者简介马　钺,男,34岁,高级工程师.研究领域为计算机软件工程,图象压缩与应用等.3815期马　钺:JPEG 压缩编码的扩充自适应量化器设计。

Multicamera People Tracking witha Probabilistic Occupancy MapFranc¸ois Fleuret,Je´roˆme Berclaz,Richard Lengagne,and Pascal Fua,Senior Member,IEEE Abstract—Given two to four synchronized video streams taken at eye level and from different angles,we show that we can effectively combine a generative model with dynamic programming to accurately follow up to six individuals across thousands of frames in spite of significant occlusions and lighting changes.In addition,we also derive metrically accurate trajectories for each of them.Our contribution is twofold.First,we demonstrate that our generative model can effectively handle occlusions in each time frame independently,even when the only data available comes from the output of a simple background subtraction algorithm and when the number of individuals is unknown a priori.Second,we show that multiperson tracking can be reliably achieved by processing individual trajectories separately over long sequences,provided that a reasonable heuristic is used to rank these individuals and that we avoid confusing them with one another.Index Terms—Multipeople tracking,multicamera,visual surveillance,probabilistic occupancy map,dynamic programming,Hidden Markov Model.Ç1I NTRODUCTIONI N this paper,we address the problem of keeping track of people who occlude each other using a small number of synchronized videos such as those depicted in Fig.1,which were taken at head level and from very different angles. This is important because this kind of setup is very common for applications such as video surveillance in public places.To this end,we have developed a mathematical framework that allows us to combine a robust approach to estimating the probabilities of occupancy of the ground plane at individual time steps with dynamic programming to track people over time.This results in a fully automated system that can track up to six people in a room for several minutes by using only four cameras,without producing any false positives or false negatives in spite of severe occlusions and lighting variations. As shown in Fig.2,our system also provides location estimates that are accurate to within a few tens of centimeters, and there is no measurable performance decrease if as many as20percent of the images are lost and only a small one if 30percent are.This involves two algorithmic steps:1.We estimate the probabilities of occupancy of theground plane,given the binary images obtained fromthe input images via background subtraction[7].Atthis stage,the algorithm only takes into accountimages acquired at the same time.Its basic ingredientis a generative model that represents humans assimple rectangles that it uses to create synthetic idealimages that we would observe if people were at givenlocations.Under this model of the images,given thetrue occupancy,we approximate the probabilities ofoccupancy at every location as the marginals of aproduct law minimizing the Kullback-Leibler diver-gence from the“true”conditional posterior distribu-tion.This allows us to evaluate the probabilities ofoccupancy at every location as the fixed point of alarge system of equations.2.We then combine these probabilities with a color and amotion model and use the Viterbi algorithm toaccurately follow individuals across thousands offrames[3].To avoid the combinatorial explosion thatwould result from explicitly dealing with the jointposterior distribution of the locations of individuals ineach frame over a fine discretization,we use a greedyapproach:we process trajectories individually oversequences that are long enough so that using areasonable heuristic to choose the order in which theyare processed is sufficient to avoid confusing peoplewith each other.In contrast to most state-of-the-art algorithms that recursively update estimates from frame to frame and may therefore fail catastrophically if difficult conditions persist over several consecutive frames,our algorithm can handle such situations since it computes the global optima of scores summed over many frames.This is what gives it the robustness that Fig.2demonstrates.In short,we combine a mathematically well-founded generative model that works in each frame individually with a simple approach to global optimization.This yields excellent performance by using basic color and motion models that could be further improved.Our contribution is therefore twofold.First,we demonstrate that a generative model can effectively handle occlusions at each time frame independently,even when the input data is of very poor quality,and is therefore easy to obtain.Second,we show that multiperson tracking can be reliably achieved by processing individual trajectories separately over long sequences.. F.Fleuret,J.Berclaz,and P.Fua are with the Ecole Polytechnique Fe´de´ralede Lausanne,Station14,CH-1015Lausanne,Switzerland.E-mail:{francois.fleuret,jerome.berclaz,pascal.fua}@epfl.ch..R.Lengagne is with GE Security-VisioWave,Route de la Pierre22,1024Ecublens,Switzerland.E-mail:richard.lengagne@.Manuscript received14July2006;revised19Jan.2007;accepted28Mar.2007;published online15May2007.Recommended for acceptance by S.Sclaroff.For information on obtaining reprints of this article,please send e-mail to:tpami@,and reference IEEECS Log Number TPAMI-0521-0706.Digital Object Identifier no.10.1109/TPAMI.2007.1174.0162-8828/08/$25.00ß2008IEEE Published by the IEEE Computer SocietyIn the remainder of the paper,we first briefly review related works.We then formulate our problem as estimat-ing the most probable state of a hidden Markov process and propose a model of the visible signal based on an estimate of an occupancy map in every time frame.Finally,we present our results on several long sequences.2R ELATED W ORKState-of-the-art methods can be divided into monocular and multiview approaches that we briefly review in this section.2.1Monocular ApproachesMonocular approaches rely on the input of a single camera to perform tracking.These methods provide a simple and easy-to-deploy setup but must compensate for the lack of 3D information in a single camera view.2.1.1Blob-Based MethodsMany algorithms rely on binary blobs extracted from single video[10],[5],[11].They combine shape analysis and tracking to locate people and maintain appearance models in order to track them,even in the presence of occlusions.The Bayesian Multiple-BLob tracker(BraMBLe)system[12],for example,is a multiblob tracker that generates a blob-likelihood based on a known background model and appearance models of the tracked people.It then uses a particle filter to implement the tracking for an unknown number of people.Approaches that track in a single view prior to computing correspondences across views extend this approach to multi camera setups.However,we view them as falling into the same category because they do not simultaneously exploit the information from multiple views.In[15],the limits of the field of view of each camera are computed in every other camera from motion information.When a person becomes visible in one camera,the system automatically searches for him in other views where he should be visible.In[4],a background/foreground segmentation is performed on calibrated images,followed by human shape extraction from foreground objects and feature point selection extraction. Feature points are tracked in a single view,and the system switches to another view when the current camera no longer has a good view of the person.2.1.2Color-Based MethodsTracking performance can be significantly increased by taking color into account.As shown in[6],the mean-shift pursuit technique based on a dissimilarity measure of color distributions can accurately track deformable objects in real time and in a monocular context.In[16],the images are segmented pixelwise into different classes,thus modeling people by continuously updated Gaussian mixtures.A standard tracking process is then performed using a Bayesian framework,which helps keep track of people,even when there are occlusions.In such a case,models of persons in front keep being updated, whereas the system stops updating occluded ones,which may cause trouble if their appearances have changed noticeably when they re-emerge.More recently,multiple humans have been simulta-neously detected and tracked in crowded scenes[20]by using Monte-Carlo-based methods to estimate their number and positions.In[23],multiple people are also detected and tracked in front of complex backgrounds by using mixture particle filters guided by people models learned by boosting.In[9],multicue3D object tracking is addressed by combining particle-filter-based Bayesian tracking and detection using learned spatiotemporal shapes.This ap-proach leads to impressive results but requires shape, texture,and image depth information as input.Finally, Smith et al.[25]propose a particle-filtering scheme that relies on Markov chain Monte Carlo(MCMC)optimization to handle entrances and departures.It also introduces a finer modeling of interactions between individuals as a product of pairwise potentials.2.2Multiview ApproachesDespite the effectiveness of such methods,the use of multiple cameras soon becomes necessary when one wishes to accurately detect and track multiple people and compute their precise3D locations in a complex environment. Occlusion handling is facilitated by using two sets of stereo color cameras[14].However,in most approaches that only take a set of2D views as input,occlusion is mainly handled by imposing temporal consistency in terms of a motion model,be it Kalman filtering or more general Markov models.As a result,these approaches may not always be able to recover if the process starts diverging.2.2.1Blob-Based MethodsIn[19],Kalman filtering is applied on3D points obtained by fusing in a least squares sense the image-to-world projections of points belonging to binary blobs.Similarly,in[1],a Kalman filter is used to simultaneously track in2D and3D,and objectFig.1.Images from two indoor and two outdoor multicamera video sequences that we use for our experiments.At each time step,we draw a box around people that we detect and assign to them an ID number that follows them throughout thesequence.Fig.2.Cumulative distributions of the position estimate error on a3,800-frame sequence(see Section6.4.1for details).locations are estimated through trajectory prediction during occlusion.In[8],a best hypothesis and a multiple-hypotheses approaches are compared to find people tracks from 3D locations obtained from foreground binary blobs ex-tracted from multiple calibrated views.In[21],a recursive Bayesian estimation approach is used to deal with occlusions while tracking multiple people in multiview.The algorithm tracks objects located in the intersections of2D visual angles,which are extracted from silhouettes obtained from different fixed views.When occlusion ambiguities occur,multiple occlusion hypotheses are generated,given predicted object states and previous hypotheses,and tested using a branch-and-merge strategy. The proposed framework is implemented using a customized particle filter to represent the distribution of object states.Recently,Morariu and Camps[17]proposed a method based on dimensionality reduction to learn a correspondence between the appearance of pedestrians across several views. This approach is able to cope with the severe occlusion in one view by exploiting the appearance of the same pedestrian on another view and the consistence across views.2.2.2Color-Based MethodsMittal and Davis[18]propose a system that segments,detects, and tracks multiple people in a scene by using a wide-baseline setup of up to16synchronized cameras.Intensity informa-tion is directly used to perform single-view pixel classifica-tion and match similarly labeled regions across views to derive3D people locations.Occlusion analysis is performed in two ways:First,during pixel classification,the computa-tion of prior probabilities takes occlusion into account. Second,evidence is gathered across cameras to compute a presence likelihood map on the ground plane that accounts for the visibility of each ground plane point in each view. Ground plane locations are then tracked over time by using a Kalman filter.In[13],individuals are tracked both in image planes and top view.The2D and3D positions of each individual are computed so as to maximize a joint probability defined as the product of a color-based appearance model and2D and 3D motion models derived from a Kalman filter.2.2.3Occupancy Map MethodsRecent techniques explicitly use a discretized occupancy map into which the objects detected in the camera images are back-projected.In[2],the authors rely on a standard detection of stereo disparities,which increase counters associated to square areas on the ground.A mixture of Gaussians is fitted to the resulting score map to estimate the likely location of individuals.This estimate is combined with a Kallman filter to model the motion.In[26],the occupancy map is computed with a standard visual hull procedure.One originality of the approach is to keep for each resulting connex component an upper and lower bound on the number of objects that it can contain. Based on motion consistency,the bounds on the various components are estimated at a certain time frame based on the bounds of the components at the previous time frame that spatially intersect with it.Although our own method shares many features with these techniques,it differs in two important respects that we will highlight:First,we combine the usual color and motion models with a sophisticated approach based on a generative model to estimating the probabilities of occu-pancy,which explicitly handles complex occlusion interac-tions between detected individuals,as will be discussed in Section5.Second,we rely on dynamic programming to ensure greater stability in challenging situations by simul-taneously handling multiple frames.3P ROBLEM F ORMULATIONOur goal is to track an a priori unknown number of people from a few synchronized video streams taken at head level. In this section,we formulate this problem as one of finding the most probable state of a hidden Markov process,given the set of images acquired at each time step,which we will refer to as a temporal frame.We then briefly outline the computation of the relevant probabilities by using the notations summarized in Tables1and2,which we also use in the following two sections to discuss in more details the actual computation of those probabilities.3.1Computing the Optimal TrajectoriesWe process the video sequences by batches of T¼100frames, each of which includes C images,and we compute the most likely trajectory for each individual.To achieve consistency over successive batches,we only keep the result on the first 10frames and slide our temporal window.This is illustrated in Fig.3.We discretize the visible part of the ground plane into a finite number G of regularly spaced2D locations and we introduce a virtual hidden location H that will be used to model entrances and departures from and into the visible area.For a given batch,let L t¼ðL1t;...;L NÃtÞbe the hidden stochastic processes standing for the locations of individuals, whether visible or not.The number NÃstands for the maximum allowable number of individuals in our world.It is large enough so that conditioning on the number of visible ones does not change the probability of a new individual entering the scene.The L n t variables therefore take values in f1;...;G;Hg.Given I t¼ðI1t;...;I C tÞ,the images acquired at time t for 1t T,our task is to find the values of L1;...;L T that maximizePðL1;...;L T j I1;...;I TÞ:ð1ÞAs will be discussed in Section 4.1,we compute this maximum a posteriori in a greedy way,processing one individual at a time,including the hidden ones who can move into the visible scene or not.For each one,the algorithm performs the computation,under the constraint that no individual can be at a visible location occupied by an individual already processed.In theory,this approach could lead to undesirable local minima,for example,by connecting the trajectories of two separate people.However,this does not happen often because our batches are sufficiently long.To further reduce the chances of this,we process individual trajectories in an order that depends on a reliability score so that the most reliable ones are computed first,thereby reducing the potential for confusion when processing the remaining ones. This order also ensures that if an individual remains in the hidden location,then all the other people present in the hidden location will also stay there and,therefore,do not need to be processed.FLEURET ET AL.:MULTICAMERA PEOPLE TRACKING WITH A PROBABILISTIC OCCUPANCY MAP269Our experimental results show that our method does not suffer from the usual weaknesses of greedy algorithms such as a tendency to get caught in bad local minima.We thereforebelieve that it compares very favorably to stochastic optimization techniques in general and more specifically particle filtering,which usually requires careful tuning of metaparameters.3.2Stochastic ModelingWe will show in Section 4.2that since we process individual trajectories,the whole approach only requires us to define avalid motion model P ðL n t þ1j L nt ¼k Þand a sound appearance model P ðI t j L n t ¼k Þ.The motion model P ðL n t þ1j L nt ¼k Þ,which will be intro-duced in Section 4.3,is a distribution into a disc of limited radiusandcenter k ,whichcorresponds toalooseboundonthe maximum speed of a walking human.Entrance into the scene and departure from it are naturally modeled,thanks to the270IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE,VOL.30,NO.2,FEBRUARY 2008TABLE 2Notations (RandomQuantities)Fig.3.Video sequences are processed by batch of 100frames.Only the first 10percent of the optimization result is kept and the rest is discarded.The temporal window is then slid forward and the optimiza-tion is repeated on the new window.TABLE 1Notations (DeterministicQuantities)hiddenlocation H,forwhichweextendthemotionmodel.The probabilities to enter and to leave are similar to the transition probabilities between different ground plane locations.In Section4.4,we will show that the appearance model PðI t j L n t¼kÞcan be decomposed into two terms.The first, described in Section4.5,is a very generic color-histogram-based model for each individual.The second,described in Section5,approximates the marginal conditional probabil-ities of occupancy of the ground plane,given the results of a background subtractionalgorithm,in allviewsacquired atthe same time.This approximation is obtained by minimizing the Kullback-Leibler divergence between a product law and the true posterior.We show that this is equivalent to computing the marginal probabilities of occupancy so that under the product law,the images obtained by putting rectangles of human sizes at occupied locations are likely to be similar to the images actually produced by the background subtraction.This represents a departure from more classical ap-proaches to estimating probabilities of occupancy that rely on computing a visual hull[26].Such approaches tend to be pessimistic and do not exploit trade-offs between the presence of people at different locations.For instance,if due to noise in one camera,a person is not seen in a particular view,then he would be discarded,even if he were seen in all others.By contrast,in our probabilistic framework,sufficient evidence might be present to detect him.Similarly,the presence of someone at a specific location creates an occlusion that hides the presence behind,which is not accounted for by the hull techniques but is by our approach.Since these marginal probabilities are computed indepen-dently at each time step,they say nothing about identity or correspondence with past frames.The appearance similarity is entirely conveyed by the color histograms,which has experimentally proved sufficient for our purposes.4C OMPUTATION OF THE T RAJECTORIESIn Section4.1,we break the global optimization of several people’s trajectories into the estimation of optimal individual trajectories.In Section 4.2,we show how this can be performed using the classical Viterbi’s algorithm based on dynamic programming.This requires a motion model given in Section 4.3and an appearance model described in Section4.4,which combines a color model given in Section4.5 and a sophisticated estimation of the ground plane occu-pancy detailed in Section5.We partition the visible area into a regular grid of G locations,as shown in Figs.5c and6,and from the camera calibration,we define for each camera c a family of rectangular shapes A c1;...;A c G,which correspond to crude human silhouettes of height175cm and width50cm located at every position on the grid.4.1Multiple TrajectoriesRecall that we denote by L n¼ðL n1;...;L n TÞthe trajectory of individual n.Given a batch of T temporal frames I¼ðI1;...;I TÞ,we want to maximize the posterior conditional probability:PðL1¼l1;...;L Nül NÃj IÞ¼PðL1¼l1j IÞY NÃn¼2P L n¼l n j I;L1¼l1;...;L nÀ1¼l nÀ1ÀÁ:ð2ÞSimultaneous optimization of all the L i s would beintractable.Instead,we optimize one trajectory after theother,which amounts to looking for^l1¼arg maxlPðL1¼l j IÞ;ð3Þ^l2¼arg maxlPðL2¼l j I;L1¼^l1Þ;ð4Þ...^l Nüarg maxlPðL Nül j I;L1¼^l1;L2¼^l2;...Þ:ð5ÞNote that under our model,conditioning one trajectory,given other ones,simply means that it will go through noalready occupied location.In other words,PðL n¼l j I;L1¼^l1;...;L nÀ1¼^l nÀ1Þ¼PðL n¼l j I;8k<n;8t;L n t¼^l k tÞ;ð6Þwhich is PðL n¼l j IÞwith a reduced set of the admissiblegrid locations.Such a procedure is recursively correct:If all trajectoriesestimated up to step n are correct,then the conditioning onlyimproves the estimate of the optimal remaining trajectories.This would suffice if the image data were informative enoughso that locations could be unambiguously associated toindividuals.In practice,this is obviously rarely the case.Therefore,this greedy approach to optimization has un-desired side effects.For example,due to partly missinglocalization information for a given trajectory,the algorithmmight mistakenly start following another person’s trajectory.This is especially likely to happen if the tracked individualsare located close to each other.To avoid this kind of failure,we process the images bybatches of T¼100and first extend the trajectories that havebeen found with high confidence,as defined below,in theprevious batches.We then process the lower confidenceones.As a result,a trajectory that was problematic in thepast and is likely to be problematic in the current batch willbe optimized last and,thus,prevented from“stealing”somebody else’s location.Furthermore,this approachincreases the spatial constraints on such a trajectory whenwe finally get around to estimating it.We use as a confidence score the concordance of theestimated trajectories in the previous batches and thelocalization cue provided by the estimation of the probabil-istic occupancy map(POM)described in Section5.Moreprecisely,the score is the number of time frames where theestimated trajectory passes through a local maximum of theestimated probability of occupancy.When the POM does notdetect a person on a few frames,the score will naturallydecrease,indicating a deterioration of the localizationinformation.Since there is a high degree of overlappingbetween successive batches,the challenging segment of atrajectory,which is due to the failure of the backgroundsubtraction or change in illumination,for instance,is met inseveral batches before it actually happens during the10keptframes.Thus,the heuristic would have ranked the corre-sponding individual in the last ones to be processed whensuch problem occurs.FLEURET ET AL.:MULTICAMERA PEOPLE TRACKING WITH A PROBABILISTIC OCCUPANCY MAP2714.2Single TrajectoryLet us now consider only the trajectory L n ¼ðL n 1;...;L nT Þof individual n over T temporal frames.We are looking for thevalues ðl n 1;...;l nT Þin the subset of free locations of f 1;...;G;Hg .The initial location l n 1is either a known visible location if the individual is visible in the first frame of the batch or H if he is not.We therefore seek to maximizeP ðL n 1¼l n 1;...;L n T ¼l nt j I 1;...;I T Þ¼P ðI 1;L n 1¼l n 1;...;I T ;L n T ¼l nT ÞP ðI 1;...;I T Þ:ð7ÞSince the denominator is constant with respect to l n ,we simply maximize the numerator,that is,the probability of both the trajectories and the images.Let us introduce the maximum of the probability of both the observations and the trajectory ending up at location k at time t :Èt ðk Þ¼max l n 1;...;l nt À1P ðI 1;L n 1¼l n 1;...;I t ;L nt ¼k Þ:ð8ÞWe model jointly the processes L n t and I t with a hidden Markov model,that isP ðL n t þ1j L n t ;L n t À1;...Þ¼P ðL n t þ1j L nt Þð9ÞandP ðI t ;I t À1;...j L n t ;L nt À1;...Þ¼YtP ðI t j L n t Þ:ð10ÞUnder such a model,we have the classical recursive expressionÈt ðk Þ¼P ðI t j L n t ¼k Þ|fflfflfflfflfflfflfflfflffl{zfflfflfflfflfflfflfflfflffl}Appearance modelmax P ðL n t ¼k j L nt À1¼ Þ|fflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflffl{zfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflffl}Motion modelÈt À1ð Þð11Þto perform a global search with dynamic programming,which yields the classic Viterbi algorithm.This is straight-forward,since the L n t s are in a finite set of cardinality G þ1.4.3Motion ModelWe chose a very simple and unconstrained motion model:P ðL n t ¼k j L nt À1¼ Þ¼1=Z Áe À k k À k if k k À k c 0otherwise ;&ð12Þwhere the constant tunes the average human walkingspeed,and c limits the maximum allowable speed.This probability is isotropic,decreases with the distance from location k ,and is zero for k k À k greater than a constantmaximum distance.We use a very loose maximum distance cof one square of the grid per frame,which corresponds to a speed of almost 12mph.We also define explicitly the probabilities of transitions to the parts of the scene that are connected to the hidden location H .This is a single door in the indoor sequences and all the contours of the visible area in the outdoor sequences in Fig.1.Thus,entrance and departure of individuals are taken care of naturally by the estimation of the maximum a posteriori trajectories.If there are enough evidence from the images that somebody enters or leaves the room,then this procedure will estimate that the optimal trajectory does so,and a person will be added to or removed from the visible area.4.4Appearance ModelFrom the input images I t ,we use background subtraction to produce binary masks B t such as those in Fig.4.We denote as T t the colors of the pixels inside the blobs and treat the rest of the images as background,which is ignored.Let X tk be a Boolean random variable standing for the presence of an individual at location k of the grid at time t .In Appendix B,we show thatP ðI t j L n t ¼k Þzfflfflfflfflfflfflfflfflffl}|fflfflfflfflfflfflfflfflffl{Appearance model/P ðL n t ¼k j X kt ¼1;T t Þ|fflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflffl{zfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflffl}Color modelP ðX kt ¼1j B t Þ|fflfflfflfflfflfflfflfflfflfflffl{zfflfflfflfflfflfflfflfflfflfflffl}Ground plane occupancy:ð13ÞThe ground plane occupancy term will be discussed in Section 5,and the color model term is computed as follows.4.5Color ModelWe assume that if someone is present at a certain location k ,then his presence influences the color of the pixels located at the intersection of the moving blobs and the rectangle A c k corresponding to the location k .We model that dependency as if the pixels were independent and identically distributed and followed a density in the red,green,and blue (RGB)space associated to the individual.This is far simpler than the color models used in either [18]or [13],which split the body area in several subparts with dedicated color distributions,but has proved sufficient in practice.If an individual n was present in the frames preceding the current batch,then we have an estimation for any camera c of his color distribution c n ,since we have previously collected the pixels in all frames at the locations272IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE,VOL.30,NO.2,FEBRUARY2008Fig.4.The color model relies on a stochastic modeling of the color of the pixels T c t ðk Þsampled in the intersection of the binary image B c t produced bythe background subtraction and the rectangle A ck corresponding to the location k .。

ｍａｒｘ， ｈ ｅ ｍｅ ｇ ｄ ｆａ ｒ ｃｏ ａ ｅｕｓ ｄ ｔ ｌｎ ｔｇ ｎ ｌｓｓｗｉｈ ｔ ｅ ｌ ｅ ｒｃａ ｓｆｅ ａ ｌｄ Ｌｉ ｌ ｅ ｒ ｔｉ ｔ ｅ ｎ ｗ ｒ ｅ ｅ ｔ ｅｖｅ ｔ ｒｃ ｎ ｂ ｅ ｏ ｂ ｉ ｄ ｓｅ ａ ａｙ ｉ ｔ ｈ ｉ ａ ｌｓ ｉ ｒｃ ｌ ｂ ｉ ａ． ｕ ｎ ｉ ｅ ｎ Ｔ ｅｒ ｓ ｌ ｓ ｏ ｓｔ ｔ ｕ ｅｈ ｄａ ｈ ｅ ｅｈｇ ｅｅ ｔ ｎ ａ ｃ ｒｃ ｎ ｆ ｃｅ ｃ ｏ ａ ｉ ｇｗ ｉ ｔ ｅ ｃ ｅ ｓ ｈ ｅ ｕｔ ｈ ｗ ｈａ ｒｍ ｔ ｏ ｃ ｉｖ ｉｈ ｄ ｔｃ ｉ ｃ ｕ ａ ｙａ ｄｅ ｏ ｏ ｉ ｉｎ ｙｃ ｍｐ ｒｎ ｔ ｏ ｈ ｒｓ ｈ ｍｅ ． ｈ Ｋ ｅ ｒ ：ｓｅ ａ ａｙ ｉ ； Ｊ ｙ ｗｏ ｄｓ ｔｇ ｎ ｌ ｓｓ ＰＥＧ ； １ ｌｎ ａ ； ｓａｉｔ ａ ｏ ｅ ｔ Ｍ ａｋ ｖ ｆａｕ ｅ ｉ ｉ ｅ ｒ ｔｔｓｉ ｌ ｂ ｃ ｍ ｍ ｎ ｓ； ｒ ｏ ｅ ｔｒ
、 １ ，． ０ ６ＮＯ １
Ｊ ．１ ａ２ ｎ ０１
中国 科 技 论 文在 线
Ｓ Ｅ ＣＥ Ａ Ｅ ＬＮ ＣＩＮ Ｐ Ｐ Ｒ ＯＮ Ｉ Ｅ
，
第６ 第１ 卷 期
２１年 １ ０１ 月
特征融合的 ＪＥ Ｐ Ｇ图像隐写分析方案
闫 岫，赵 耀 ，倪 蓉 蓉
（． １ 北京交通大学信息科 学研 究所， 北京 １０４ ； ． ００４ ２ 现代信息科 学与网络技术北京市重点实验室，北京 １０４ ） ００４
ｓ ｇ ｎ ｌｓｓｗｉ ５ ｍｏ ｅ ａ ｅ ｔｇ ｎ ｇａ ｈ （ ， ２ ａ ｄ ＯｕＧｕ ｓ． ｃ ｒ ｉｇ ｔ ｈ ｏｒｌｔ ｎｏ ｈ ｔ ａ ａｙ ｉ ｔ Ｆ ， ｄ ｌｂ ｓｄ ｓ ａ ｏ ｒｐ ｙＭＢ１ ＭＢ ｎ ｔ ｅｓ Ａｃ ｏｄｎ ｏｔｅｃ ｒｅａｉ ｎｔｅ ｅ ｈ ｅ ） ｏ