第7卷第1期 智能系统学报 Vol.7 No.1 2012年2月 CAAI Transactions on Intelligent Systems Feh.2012 D0I:10.3969/j.i8sn.1673-4785.201111001 Thermodynamics-inspired inverse halftoning via multiple halftone images SAIKA Yohei,AOKI Toshizumi? (1.Department of Information and Computer Engineering,Gunma National College of Technology,580 Toriba,Maebashi, 371-8530,Japan;2.Department of Natural Science,Gunma National College of Technology,580 Toriba,Maebashi,371- 8530,Japan) Abstract:Based on an analogy between thermodynamics and Bayesian inference,inverse halftoning was formulated using multiple halftone images based on Bayesian inference using the maximizer of the posterior marginal (MPM)estimate.Applying Monte Carlo simulation to a set of snapshots of the Q-Ising model,it was demonstrated that optimal performance is achieved around the Bayes-optimal condition within statistical uncertainty and that the performance of the Bayes-optimal solution is superior to that of the maximum-a- posteriori(MAP)estimation which is a deterministic limit of the MPM estimate.These properties were qualitatively confirmed by the mean-field theory using an infinite-range model established in statistical me- chanics.Additionally,a practical and useful method was constructed using the statistical mechanical itera- tive method via the Bethe approximation.Numerical simulations for a 256-grayscale standard image show that Bethe approximation works as good as the MPM estimation if the parameters are set appropriately. Keywords:inverse halftoning;statistical mechanics;Monte Carlo simulation;Bethe approximation; CLC Number:TP39 Document Code:A Article ID:1643-4785(2012)01-0086-09 1 Introduction of generating a halftone image comprised of a set of black and white dots that are visually similar to the o- Researchers have long used Bayesian inference to riginal image as seen by the human vision system. investigate various issues in information science and Many techniques,such as the organized dither meth- technology such as problems related to image and sig- od671,have been proposed for generating such image. nal processing3.During the last two to three dec- The inverse of digital halftoning,i.e.,"inverse ades,theoretical physicists have studied such prob- halftoning,"is used to reconstruct the original image lems by using an analogy between statistical mechanics from the halftone image,and many techniques have and the maximizer of the posterior marginal (MPM)been proposed for doing this.For an instance, estimate based on Bayesian inference.In the early Wong9 proposed statistical techniques for a halftone stage of development in this field,physicists studied image obtained using the error diffusion method.Then, image restoration and error-correcting codes!4s)to de- Stevensonapplied maximum-a-osterioi(MAP)es- termine the feasibility of applying statistical mechanics timation to inverse halftoning of halftone images conver- to these problems.Researchers have since then applied ted using either a dither method or an error diffusion statistical mechanics to various problems in information method.Recently,Saika et al.(constructed a science and technology. Bayes-optimal solution on the basis of the statistical Researchers have been investigating digital half- mechanics of the Q-Ising model for the inverse halfton- toning print technology7 for many years with the aim ing problem.It uses the MPM estimate based on Bayesian inference.Other researchers have investiga- Received Date:2011-11-01. Corresponding Author:SAIKA Yohei.E-mail:yoheisaika@gmail.com. ted super resolution,another typical problem in infor-
第1期 SAIKA Yohei,et al:Thermodynamics-inspired inverse halftoning via multiple halftone images ·87… mation science and technology.The objective is to con- ven if a uniform model prior is assumed.However,a struct a high-resolution image using multiple low-reso- fatal contour appeared in the images reconstructed u- lution images.Several researchers have triedu sing fewer than 16 halftone images.The contour can be sing Bayesian information processing from the statistical removed by the MPM estimate using fewer than 16 half- mechanical point of view. tone images if an appropriate model of the true prior In this study,a practical and useful method for which can enhance smooth structures is used.A practi- inverse halftoning is proposed.It combines a statistical cal and useful method was then developed for recon- mechanical iterative method and a framework of super structing images based on the Bethe approximation resolution to use multiple halftone images.This ap- which approximates the MPM estimate.Simulation proach was adopted with the hope that statistical me-shows that Bethe approximation reconstructs the origi- chanics of Bayesian information processing would be a-nal image almost as good as Monte Carlo simulation vailable by using an analogy between statistical me-and that only 11~15 iterations are needed to solve the chanics and the MPM estimate based on Bayesian in- self-consistent equations derived from the Bethe ap- ference.In particular,the statistical mechanical itera- proximation. tive method was used based on the Bethe approximation The content of this paper is as follows.The gener- to approximate the MPM estimate established in the al prescription of statistical mechanics and the analogy field of Bayesian information processing.Then,in or- between statistical mechanics and Bayesian inference der to realize inverse halftoning with high image quali- were briefly reviewed,describing the general formula- ty,a framework of super resolution was also applied to tion of inverse halftoning using multiple halftone images multiple halftone images for inverse halftoning.Next,based on the statistical mechanics of the Q-Ising mod- in order to clarify the performance of Bethe approxima-el.The performance of the present method was then tion from the theoretical point of view,the efficiency of examined.Monte Carlo simulation and analytical esti- the MPM estimate for inverse halftoning was examined mation were conducted based on the mean-field theo- using multiple halftone images based on Monte Carlo rys,using the infinite-range model;its statistical per- simulation for a set of snapshots of the Q-Ising model formance for a set of snapshots of the Q-Ising model and the mean-field theory using the infinite-range mod- was estimated along with its performance for a realistic el.First,Applying the Monte Carlo simulation to a set image.Finally,the performance of the presented sta- of snapshots of the 8-grayscale Q-Ising model,the sta- tistical mechanical iterative method based on the Bethe tistical performance of the MPM estimate was clarified approximation was estimated. using 4 halftone images rewritten by the organized dith- er method based on the metric using the mean square 2 General formulation error (MSE).The simulation showed that the optimal 2.1 statistical mechanics performance was achieved around the Bayes-optimal As shown in Fig.1,a principal goal of statistical condition within statistical uncertainty and that the op- mechanics is to clarify thermodynamics of many-body timal performance is superior to that of the MAP esti- systems starting with interactions between microscopic mation,which corresponds to the deterministic limit of elements.In general prescription of statistical mechan- the MPM estimate.These properties were qualitatively ics,thermal average of macroscopic physical quantity confirmed by analytical estimation based on the mean- can be estimated as an ensemble average over all possi- field theory using the infinite-range model.On the oth- ble states using a probability distribution: er hand,from the practical point of view,the perform- (1) ance was investigated based on the Monte Carlo simula- P(1s)=zpl-BIs)】 tion for realistic images,i.e.,a 256-grayscale stand-for a given Hamiltonian H(S).In this equation,a ard image“Lena”with256×256 pixels.The simula- set of the Ising spin statesS is used as a set of typi- tion showed that the MPM estimate can reconstruct the cal microscopic elements.The unit of temperature is original image using more than 36 halftone images,e- taken such that Boltzmann's constant g is unified.As
·88 智能系统学报 第7卷 a result,B =1/T.Normalization factor Z is called the the Bethe approximation.As a recent development of “partition function”: statistical mechanics,researchers have clarified that sta- Z=∑∑…∑exp[-BH({S)]. tistical mechanics serves a framework and various tech- 防 niques for probabilistic information processing based on The probability distribution in Eq.(1)is termed the the analogy (Fig.2)between statistical mechanics and "Boltzmann factor".Using the Gibbs-Boltzmann distri- Bayesian inference using the MPM estimate. bution,the thermal average of macroscopic quantity A(S)can be estimated as Statistical mechanics Bayesian inference Statistical (w=7品多系ep-1s1)1a(1s) Thermodynamics Corresponden9e。 performance Average on Correspondence Posterior Canonical ensemble Macroscopic substance probability Water Electron,Spin Correspondence Bit,Pixel Thermodynamic (Macroscopic)properties Fig.2 Analogy between statistical mechanics of phys- Ensemble average ical system and Bayesian inference of informa- ◆-Canonical ensemble tion system Time average Statistical Molecule mechanics 2.2 general formulation Microscopic elements Here,on the basis of the statistical mechanics of Electron,Spin- the Q-Ising model,the general formulation for inverse Microscopic substance halftoning is shown using multiple halftone images Fig.1 Main goal of statistical mechanics based on Bayesian inference which is obtained through the MPM estimate.As shown in Fig.3,the framework Though it is difficult to calculate this macroscopic is composed of two parts.One is the forward process quantity directly,it can be estimated by using the corresponding to digital halftoning,and the other is the approximation theories such as the mean-field theory and inverse process corresponding to inverse halftoning. Forward process(Digital halftoning) Inverse process(Inverse halftoning) t, {,] (r,} [x2,] Original image Reconstructed image r} {x2 C2. True prior Model prior Pr(,子） Likelihood Pr(z Organized dither method :Pr( Pr ( { T A set of the dithered images The set of the dithered images Fig.3 Framework of inverse halftoning via multiple halftone images
第1期 SAIKA Yohei,et al:Thermodynamics-inspired inverse halftoning via multiple halftone images ·89 tone images(m,n)using the organized dither method and a p x p Bayer threshold array M,. Here,Ty（m,n)=0,1,x,y=1,2,…,L,and m,n=1,2,.,p.Two example threshold arrays are shown in Figs.5(a)and (b).The threshold array (a)Snapshot of (b)256-grayscale (c)Halftone version Q-Ising model with "Lena"image with of (a)created using M.is given by 100x100 pixels 256×256 pixels organized dithe method and 2x2 4M2 M,=4Mo+3U。 4M2+2U2l Bayer threshold array 4M2+Un」 M=9 (3) 0328402341042 4816562450185826 (d)Halftone image (e)Grayscale image (f)Grayscale image created from (b)using obtained using 4 obtained using 64 124443614 466 38 organized dither halftone images under halftone images 60285220623054 method and8×8 Bayes-optimal without using prior Bayer threshold array condition (=1)information(//T =0. 08210 3 351143 33 9 41 MSE/O=0.131149) 124146 51195927491757 25 31119 154773913 45537 157135 6331552361295321 (a)4×4 (b)8×8 Fig.54×4and8×8 Bayer threshold arrays (g)Grayscale image (h)Grayscale image (i)Grayscale image U is an n xn matrix,the elements of which are obtained using 64 obtained using 16 obtained using 16 halftone images with halftone images halftone images and unified.Threshold M,is an integer from 0 to p2-1. JT.=1 (MSE/ without using prior appropriate model Q=0.012455) information (J/T=0,of true prior (T=I The halftone versions of the original images in Figs.4 MSE/0=0.162267)MSE/O-0.122582) (a)and (b)are shown in Figs.3(c)and (d). Fig.4 Original images,halftone versions of the origi- When the original image is converted into the nal images and reconstructed grayscale images (m,n)-th halftone image(m,n),a one-to-one In the first step of the forward process,a set of o- correspondence between each pixel of the original im- riginal grayscale images was considered,where age and the threshold of the Bayer threshold ar- 5y=0,1,…,Q-1andx,y=1,2,…,L.These ray M is first created by making use of the corre- images were generated by the assumed true prior ex- spondence: pressed as a probability distribution: 专，→M(g+m)%p,(y+n)%p, (4) P以)=zm-光： where (x+m)%p denotes a surplus that divides (x+ m)by p,and it is the same with (y+n)%p.Then, 含宫t-w户+(w-门. as shown in Fig.6,a threshold procedure is carried out for each pixel of the original image by the corre- (2) sponding thresholdM: where J,and T:are parameters for tuning "smooth- Tk,w（m,n)= ness"in the pattern of the original image.Fig.4(a) 0(5y-M(x+a%p,y+n%p·Q/p2-1/2). shows a sample of the original image,i.e.,a snapshot 0(.)is a unit-step function given by of the 8-state Q-Ising model on a square lattice.Then, as shown in Fig.4(b),a 256-grayscale standard image 8(x)=0,x<0; 11,x>0. with 256 x 256 pixels,such as "Lena",was used to The halftone images in Figs.4(c)and (d)are visual- investigate the performance for realistic images. ly similar to the original image as seen by the human In the second step of the forward process,each o- vision system although information on the original im- riginal image is rewritten into p'kinds of half- age was lost through the halftone procedure
90 智能系统学报 第7卷 In the inverse halftoning process,the original im- increase in the number of the halftone images. age is reconstructed so as to maximize the posterior r-7 marginal probability.The value of the (x,y)-th pixel 6 in the reconstructed image is given by 51 M61 Restricted range of arg max Pr() gray-level by three halfone images =4 4X4 Bayer-type threshold array 21 08210 M=2 16 124146 电京0 31119 Halfone image 3 5735 25502550 The number of the halftone images 0250255 Comparison 1151141413 25502550 Fig.7 Range of grayscale restricted by the likelihood 1201181714 025300 in Eg.(6)used for the present method 127币19019 Then,the reconstructed image is obtained by 1361289074 256-grayscale original image y=⑧(8，y）, Fig.6 Digital halftoning using 4 x 4 Bayer-type where threshold array w=名Pia1产)， The posterior probability is estimated using the Bayes formula, ()=】 叫e-k+》-0e-k-2. Pr()= To estimate the performance of the present meth- Pr({z})Pr({P2}1{) od,MSE was compared between the original and re- ∑Pr({z)Pr({x2}I{z) constructed images: as well as the assumed model of the true prior along with the likelihood.The model of the true prior ex- sE=A名，-，月 pressed by To estimate the statistical performance,MSE was a)ep averaged over the set of original images: 含-+-s) sE=名(1E)2云会，-6片 3 Performance is used so as to enhance smooth structures appearing in the patter of reconstructed images.Furthermore,a 3.1 Monte Carlo simulation model of the true prior is used,which is assumed to To quantitatively investigate the statistical per- have the same form as the true prior in Eq.(2)so that formance of the present method,a set of the snapshots an MPM estimate is constructed,including the Bayes- of the Q-Ising model was used on the square lattice.A optimal solution.The likelihood that is expressed by set of the snapshots of the 8-grayscale Q-Ising model the conditional probability representing the organized with 100x100 pixels(Fig.4(a))was used for the o- dither method via the Bayer threshold array is also riginal images.The parameters in Eq.(2)were set to used: J,=T,=1.Each original image was converted into four kinds of halftone images by the organized dither Pr({1{1)=ΠΠΠ6(rw,6(g method using the 2 x 2 Bayer-type threshold array in M(x*m%,+0p·Q/p2-1/2).(6) Egs.(3)and (4).Then,20 000 Monte Carlo steps As seen from Fig.7,the likelihood has the prop- were performed using the MPM estimate based on the erty that the possible range of the gray-level z be- Metropolis algorithm. comes narrower at each pixel with the increase in the First,it was determined how MSE depends on number of the halftone images.So,it is expected that parameter T in Eq.(5)for J=1.As shown in Fig.8, the accuracy of the performance is improved with the it is found that the performance of the present method