/*================================================================================ NOTE FROM PRASUN CHOUDHURY: This is the first version of the code related to the paper on Bixels that appeared in EGSR'2004. The pix2bix() function is the implementation of Section 6 in the paper and the bix2pixSS() function is the implementation of Section 5 of the paper. The functions evalAt, evalPatch/Scene, putScene, etc (with similar names) implements the patch function computation for every tile based on its boundaries: this is described in Section 4 and Appendix of the paper. Currently, our code is interfaced with a huge image library (its not a standalone application); we are trying to make it a standalone application where one can will only have the above two classes (and the other necessary classes that is uses) along with basic OpenGL (to display) and GLUT (for primitive UI) interface. I will let you know when we are done with the same. Prasun Choudhury (11/2004) ===============================================================================*/ /*============================================================================== BixImg.h: my C++ classes for Bixel Images: images with boundaries. This (base) class describes a image made of 'bixels'. Bixel images add `boundaries' to pixels to define a piecewise-continuous surface; together they define intensity height fields that are smooth everywhere EXCEPT at curved-line 'boundaries', where the surface(s) may have discontinuities in intensities, gradients, or both. You may think of ordinary (pixel-only) images as a sampled representation of a limited-bandwidth signal, a signal that forms a smooth, continuous intensity height field. Bixel image lets you 'cut up' this surface with 'scissor cuts' at boundary lines. The resulting height field contains infinitely sharp step- or ridge-like boundaries that mark precise locations of visually important image features such as silhouettes, shadow boundaries, corners, edges or creases. Bixels store boundary information as if it were another color channel in a pixel, and typically in just 8 more bits per pixel. __SAMPLING RATES:_______ Bixels describe an infinite bandwidth signal, but not an infinitely detailed one; it just adds some sharp discontinuities to pixels. Just as the number of pixels in an image determines the maximum number and density of its intensity variations, the number of bixels determines the maximum number and density of boundaries in an image. A scanline that holds N **pixels** can describe up to N smooth transitions from black-to-white, such as N/2 cycles of a sinusoid. Similarly, a scanline of N **bixels** can describe N discontinuous transitions, such as N/2 cycles of a square wave, and allows users to choose whether a transition is continouous or discontinuous. Bixels can also represent any smooth translation of the pixel-rate- discontinuous transitions it describes. Put another way, for any boundary density at or below 1 boundary per pixel-spacing, we can do arbitrary re- sampling without artifacts, analogous to the Nyquist criterion for sampling continuous signals. In addition, bixels can represent some limited forms of localized higher-density boundaries, such as very tiny diamond-shaped areas centered around a pixel, but the size, shape, and location of these smaller features are constrained by pixel locations (no arbirary re-sampling). Just as with pixels, if you want a higher boundary density, then use enough bixels to sample them! Insufficient PIXEL sampling density has led to strange ad-hoc solutions such as 'font hinting'. Bixels may allow us to eliminate them. __DEFINITIONS:_______ ---Pixel==a point sample of one or more image intensity(color) functions, as measured at an integer x,y location. ---Pixel-center==the integer x,y location of a pixel in the image plane; this is NOT the same as a boundary point!! (see below) ---Tile==a 1x1 area of the x,y plane whose corners are adjacent pixel-centers. Addresses of tiles are given by their lower-left-corner pixel; the tile at (x0,y0) is the area given by (x0 <= x < x0+1, y0 <= y < y0+1). Note that tiles form a complete segmentation of the image plane; any point in the x,y plane will be a member of one and only one tile. ---Boundary point==one point in a 'tile' that is part of one or more boundary curves; boundary curves connect boundary points together. ---Bixel==an ordinary pixel plus some added boundary information. Just as a pixel image is a 2D array of pixels, a bixel image is a 2D array of bixels. The boundary information in each bixel is either empty(no boundary info) or it defines the location and connectivity of just one nearby 'boundary point'. The 'boundary point' for bixel (x0,y0), if it exists, is within the tile with address (x0,y0). Like pixels, bixels use fixed-sized storage fields; each bixel stores--- --one or more pixel intensity values; r,g,b,a,... in CBixImg, these are floating-point values stored in the 'm_pix' Raw3D object; this provides excess precision, any number of fields, & any image size. --subpixel position of boundary point in it's tile, given by (dx,dy), usually 3 bits each, --boundary point connectivity bits (cE,cN); these are packed with the (dx,dy) values and stored in 'm_bix', an Imat (integer matrix)object. If dx,dy are 3 bits each, m_bix holds just 8 bits per pixel. ---Boundary==curve or line where image intensities or gradients on either side are unrelated, and may be discontinuous. Boundary curves are defined by local spline interpolation (linear, quadratic, or cubic) between boundary points. ---Boundary Segment==portion of boundary between two adjacent boundary points. __BIXEL RULES:________ As with ordinary images, nearby pixels are interpolated to determine nearby image intensities,but in a bixel image a pixel value cannot affect intensities on the other side of a boundary. The bixel image format must restrict the set of boundaries it can express to ensure that ALL points in an image have easily determined colors/intensities for any possible boundary set. In other words, we must prevent expression of boundaries that 1) form closed loops that do not enclose any pixel centers, or 2) block all simple paths from an image point to all four of the nearest surrounding pixels, (the 4 tile corners). I chose a simpler and tighter restriction; no pair of NS- or EW-adjacent pixels may be separated by more than one boundary; then each boundary ALWAYS has at least one adjacent pixel on both sides. To enforce the restriction, CBixImg follows these rules: ---No more than one boundary point per tile allowed. ---All boundary segments must begin and end on a boundary point. ---No boundary segments may cross each other (e.g. share a point that is not a boundary point). ---Any tile that contains any part of a boundary curve must ALSO contain its a boundary point in the tile somewhere on that curve; in other words, if a boundary touches a tile, the tile has a boundary point on the curve. ---Boundary segments connect adjacent boundary points, so they MUST connect (boundary points in) two adjacent tiles by crossing the the shared side of those tiles. Segments can't start & stop within the same tile (that would require two boundary points), can't connect non-adjacent tiles, and can't connect tiles corner-to-corner (to avoid 'splitting' a pixel with a boundary. Instead, go to one side of it; e.g. '4-connected' boundaries). ---Only one segment may cross a given tile side. This ensures that both sides of the segment have an adjacent pixel to set intensity, and limits the connectivity of any boundary point to no more than 4 segments. ---Boundary point positions (dx,dy) are quantized (usually to 3 bits each); offset them by 1/2 a quantizing level in x,y so that boundary points cannot be placed exactly on top of pixels. ---Bixel image intensities for all points except those precisely on the boundaries are always interpolated from nearby pixels that are reachable WITHOUT crossing any boundaries. Boundaries may be open (with endpoints) or closed, and more than one boundary curve may meet at the same boundary point. (Points precisely on the boundaries are ambiguous; you may regard them as either undefined, double-valued, or as the mean of the value of adjacent points as is commonly done for continuous Fourier transforms and in the Heaviside step functions used in signal analysis.) __BIXEL ENCODING_______________ Boundary information is kept in a new image plane with a fixed # of bits per pixel, as if there were a boundary 'color' at each pixel. We store only two things per pixel: --the subpixel position of boundary points within a tile (dx,dy) and --connectivity: which tile sides are crossed by a boundary segment. Subpixel position is given by a fixed# of bits for dx,dy, usually 3 each. Because tile sides are shared, we only need to store 2 bits per tile for connectivity; --bit 'L' is true iff a boundary segment crosses the LEFT side of tile, --bit 'B' is true iff a boundary segment crosses the BOTTOM side. To find connectivity on top and right side of tile, examine the stored bits for neighboring pixels. No boundary point can exist in isolation; if a tile has no boundary segment crossing any of its sides, then it's dx,dy values are meaningless. Accordingly, CBixImg class offers no member functions to create a single boundary point--you must create boundary SEGMENTS instead. __BIXEL-to-PIXEL IMAGE CONVERSIONS_____ Very much like antialiased textured-polygon rendering; a bixel image has limited-bandwidth regions(textures) with infinite bandwidth discontinuities (polygonal boundaries) that must be filtered to make an limited-bandwidth pixel-only image. In a one-to-one bixel->pixel conversion, we only need to modify pixels near boundaries, and this may make conversions faster. Tricky! an antialiased pixel-only image will not have the same pixel values stored in a _bixel_ image. Antialiasing applies a pre-filter that smoothes across discontinuities before sampling to make pixels, so that a pixel adjacent to a boundary will be a weighted sum of intensities from BOTH SIDES of the boundary. In a bixel image, pixel values are from samples on only one side of the boundary, and may be different. You need an antialiasing process for best results when you convert from bixels to pixels, and if you have an anti- aliased pixel-only image and boundary information, you need to do the inverse; you need to UNDO (deconvolve) the pixel-only image near boundaries to make a good bixel image. __PIXEL-TO-BIXEL IMAGE CONVERSIONS_____ Given an (antialiased) pixel-only image AND boundary information, perform a constrained deconvolution around the boundaries to estimate BIXEL intensity values, e.g. pixel values that were NOT smoothed across boundaries. ==============================================================================*/ #if !defined(AFX_BIXIMG_H__6BCDCAE1_832F_11D4_AAFB_00C04F794BFF__INCLUDED_) #define AFX_BIXIMG_H__6BCDCAE1_832F_11D4_AAFB_00C04F794BFF__INCLUDED_ #include "..\FPMODEL\polyshape.h" // Added by ClassView #include "..\FPVECMATCLASS\V_VECMAT.H" // Added by ClassView #include "..\FPIMGCLASS\f_raw.h" // Added by ClassView #include // for 'floor()' calls. #if _MSC_VER > 1000 #pragma once #endif // _MSC_VER > 1000 #define DXBITS 15 // # of bits for boundary-point position #define DYBITS 15 #define LINKBITS 2 // # of bits for connectivity #define DXMASK 0x00007FFF // set bits that hold DXBITS,DYBITS,LINKBITS #define DYMASK 0x3FFF8000 #define LINKMASK 0xC0000000 #define LSIDEBIT 0x80000000 // bit for connectivity of left tile side #define BSIDEBIT 0x40000000 // bit for connectivity of bottom tile side. //define tile corner pixels; #define PIX_A 0 // lower-left corner pixel #define PIX_B 1 // lower-right #define PIX_D 2 // upper-left #define PIX_C 3 // upper-right. class CBixImg : public Raw3D { //============================================================================== private: //-----------------DATA----------------- // Keep encoding details encapsulated: use get,put functions instead! // Bixel images are 2D arrays of bixels // indexed from zero by integer x,y. Bixels // have 2 parts; //Base Class: Raw3D //1)---point-sampled intensity fields: // 2D image position indexed by (x,y), and // z selects among one or more intensity // fields(e.g. z=0,1,2,... for R,G,B,...) Imat m_bix; //2)---Bixel-coded boundary information; // fixed-size record at each x,y pixel // location. public: // Decoded boundary geometry: An XY planar CShape m_map; // graph of boundary points connected by // CEdge half edges, as built by calls to // CShape::makePlanarEdge(). The planar // graph form gives fast boundary traversals // and identifies closed regions as faces. //-------DISPLAY CONTROL: BOOL m_showON; // enable/disable all bixel boundary drawing BOOL m_dotsON; // enable/disable 'dots' at boundary points. CVert* m_pVpick; // 'picked' vertex used in bixel editing. Vec2 m_downPt; // mouse position on LButtonDown. private: CVert m_dummyV; // Used only by bixEdit_LButtonDblClick() public: //-----------------FCNS----------------------------- CBixImg(); // void constructor. ~CBixImg(); // destructor: de-alloc memory // virtual void Serialize( CArchive& ar ); // JT: virtual' means serializing CAN'T // EVER be done by base class CObject. //--------------BASIC ACCESS------------------------ int BgetXsize(){return(m_bix.getXsize());}; // read bixel image size. int BgetYsize(){return(m_bix.getYsize());}; // void Bsizer(int xsize, int ysize, int zsize);// set entire bixel image size void BsizerAddBix(void); // set m_bix size to match pixel size. void Bwipe(void); // delete entire image contents void BwipeCopy(CBixImg &src); // delete current contents, copy 'src'. void zeroBounds(void){m_bix.zero();}; // clear/zero out all boundaries. PIXTYPE getPix(int x, int y, int z){ // get, put pixel value at x,y,z; return(get(x,y,z));}; void putPix(PIXTYPE val, int x, int y, int z){ put(x,y,z,val);}; void getPixAll(int x, int y, Matrx& dest); // get, put ALL pixel values at void putPixAll(int x, int y, Matrx& src); // integer) position x,y. void putPixAll3(int x, int y, PIXTYPE val); // write 'val' to 1st 3 fields. Vec2 getBoundPt(int x,int y); // get, put boundary point positions void putBoundPt(Vec2& bpt); int getAllTileBits(int x, int y); // get,put tile's lrbt connectivity bits void putAllTileBits(int x, int y, int lrbt);// (left,right,bottom,top) int getLBTileBits(int x, int y); // get,put ONLY left & bottom tile bits. void putLBTileBits(int x, int y, int lb); int getNSEWbits(int x, int y); // get,put connectivity of pixel at x,y // and to North,South,East,West //---------------USER API---------------------------- void wipeTestShape(void); // test image with boundaries. void makeBixelShape(Raw3D *bptImg, Raw3D *colorImg); void wipeTestShapeIntensity(Raw3D* inputPixel); int countSegments(int xt, int yt);// return # of boundary segments for tile. int findReachableCorner(Vec2 &pt);// From position 'pt', find a tile corner // reachable without crossing a boundary. BOOL isConnected(Vec3& pixA, Vec3& pixB);// TRUE if pixA,pixB share a tile // side that is NOT crossed by a boundary. void evalAt(Vec2& pt, Matrx& out); // Re-sample bixel image at location x,y, // return contents in column vector. void evalSceneAt(Vec2& pt, Matrx& out); // Re-sample bixel image at location // x,y using the putScene function BOOL bix2pix(CBixImg& src); // Use analytic bilinear filtering of // residue to convert bixel image to pixels. BOOL bix2pixSS(CBixImg& src); // Use supersampled bilinear filtering to // convert bixel images into pixels. void bix2pixWeight(CBixImg& src);// Integrate continuous-valued // filter kernels to convert bixel to pixels. BOOL pix2bixSolver(CBixImg& src);// Given a pixel image + added boundaries, // solve for a bixel image that will match // the 'src' pixel image after bix2pix() // conversion. Return TRUE if converged. // Mouse-based bixel boundary editing. CVert* bixPick(PIXTYPE xp,PIXTYPE yp); // return bound. point nearest xp,yp. void bixEdit_LButtonUp(PIXTYPE xpos, PIXTYPE ypos); // select existing pts, void bixEdit_LButtonDown(PIXTYPE xpos, PIXTYPE ypos); void bixEdit_LButtonDblClick(PIXTYPE xpos, PIXTYPE ypos);// make new pt. CVert* bixEdit_ToggleUp(Vec3& pos); // Boundary editing w/ arrow keys. CVert* bixEdit_ToggleDown(Vec3& pos); CVert* bixEdit_ToggleLeft(Vec3& pos); CVert* bixEdit_ToggleRight(Vec3& pos); BOOL bixFileRead(); // Read simple TIFF-like file format // (return FALSE on error). BOOL bixFileWrite(); // Write simple TIFF-like file format BOOL makeMapFromBix(void); // Wipe any existing boundary geometry in // m_map and rebuild it from m_bix contents. BOOL makeBixFromMap(void); // Wipe any existing bixel-coded boundary // data & rebuild it from geometry in m_map. BOOL makeHeightField(CShape& dest); // Wipe any existing contents of 'dest' and // make a polygonal height-field shape from // m_map and stored pixel info; note CShape // has members to permit OpenGL display. BOOL addQuadMap(void); // Insert additional points in m_map using // quadratic local spline interpolation. BOOL addCubicMap(void); // Insert additional points in m_map using // cubic local spline interpolation. void drawBounds(Pic24mfc *pImg,HWND windo, CDC *pDC); // draw bixel boundary points and segments // using Windows GDI calls. (zoomable!) }; class CBixRegion //============================================================================== // CBixRegion reconstructs a bixel region's surface anywhere within a CBixImg // (Recall that CBixImg stores only point-samples and boundaries). // Each CBixRegion object describes a selected piece of the bixel image, a // polynomial 'patch' that smoothly interpolates between the surrounding bixel // values within a boundary-limited portion (a "region") of one selected tile. // Regions are defined by boundary segments and the sides of a tile). // We can enumerate all possible regions in two steps: // --the 16 values of 'lrbt' lists all the different ways that boundary segments // can cut a tile into pieces. Call each of these pieces a 'region'. // --Each region includes at least one tile corner, and remember // that we labeled tile corners A,B,C,D respectively. Accordingly, we can name // each region for a given 'lrbt' value by it's tile-corner letter(s). All // regions for a given lrbt value can be uniquely identified by its 'corner // codes': A_REG, B_REG, C_REG, D_REG. // // Each enumerated region is interpolated by its own smooth polynomial patch // function, by a smoothly-varying, weighted sum of nearby bixels, bixels that // are reachable without crossing a boundary segment. // Now it gets a little tricky: CBixRegion doesn't know or care what these // nearby bixel values actually are, but instead tells you how to blend them // together to evaluate the bixel image at a chosen point within that region. // Any point in the patch can be written as a weighted sum of nearby bixel // values, and each of these weights is found by evaluating a polynomial basis // function. In the extended bilinear method used below, each basis function is // bilinear, of the form 'weight(x,y) = K0 + K1*x + K2*y + K3*xy'. // If we write a column of these equations, one for each bixel that contributes // to a patch, we can combine them into a single matrix expression for the // patch. For example, for lrbt =5, the region touching tile corners A,B,D has // this patch equation: kp5_ABD(x,y) = [A B SE D NW][COEF][VAR], // where A,B,SE,D,NW are bixel values, COEF is a coefficient matrix (whose // values depend only on the connectivity of surrounding bixels, and VAR is the // column vector of variables written [1 x y xy]^T. // The function CBixRegion::putSurface() constructs this 'COEF' matrix for you // from a region's 'patchcode' = lrbt+corner code. Unfortunately, the row // vector of bixels (e.g. [A B SE D NW] above) is different for each region. // For easy evaluation, I use CBixRegion::bixAddr, a 2xN matrix that holds the // addresses of these bixels. For example, for the patch given by kp5_ABD, // the 'bixAddr' matrix's leftmost column is [x0,y0] or pixel A, next // column is [x0+1,y0] for B, next is [x0+1,y0-1] for SE, next is [x0,y0+1] // for D, and finally [x0-1,y0+1] for NW. (in putSurface() code these addresses // are supplied by addrX[],addrY[] arrays to handle 'wraparound' at edges of // pSrc). The bixAddr matrix is updated on any call to putSurface(). // // The patch polynomials are only valid within their bounded regions. All region // bounds are polyhedra (because we're using straight-line boundary segments) // consisting of tile corners, boundary points, and points where boundaries // cross tile sides. CBixRegion describes region boundaries by: // { public: int lrbt; // tile's connectivity bits. private: CBixImg *pSrc; // BixImg object containing our patch. int xtile,ytile; // patch's tile address within pSrc; int patchcode; // Patch selector = lrbt + 16*corner_code, // where corner_code = 0,1,2,3 for region // touching tile sides A,B,C,D. // (See BixTileKernel.mcd) Vec2 bpt; // boundary point within tile. Matrx coef; // Coefficient matrix for basis functions. Imat bixAddr; // Addresses of bixels used in the current // patch; 2xn matrix holds(x,y) pairs. Vec2 tileCut[4]; // coords. where boundary segments cross // edges of tile, in lrbt order. public: CBixRegion(); // Default constructor/destructor ~CBixRegion(); void wipe(); // clear, destroy, empty. void setSource(CBixImg *pImg); // Assign the source Bixel image. CBixImg* getSource(void) {return pSrc;}; int getXtile(void){return xtile;}; // read current tile values. int getYtile(void){return ytile;}; int getPatchcode(void){return patchcode;}; void putCuts(void); // set the tileCut from pSrc bixel values. BOOL putSurface(int x0,int y0, int pcode); // Set patch, evaluate its coefficients int putScene(int x0, int y0, int pcode); // Residue at x0,y0 tile, region 'pcode' BOOL verifyCoef(int x0, int y0, int pcode, BOOL isSurface); // calculate patch or scene by alternate // method; true if 'coef' matrix agrees. BOOL unrefilterTile(int x0, int y0, Matrx& wt); // Find 'wt' to convert bixel-to-pixels void evalPatch(VECTYPE dx, VECTYPE dy, Matrx& out); // Find patch value }; // 'Patchcode' offsets; these identify tile regions cut apart by boundaries // according to one (or more) of the tile corners they touch. #define A_REG 0 // lower left tile corner (i ,j ) #define B_REG 16 // lower right tile corner (i+1,j ) #define C_REG 32 // upper right tile corner (i+1,j+1) #define D_REG 48 // upper left tile corner (i ,j+1) #endif // !defined(AFX_BIXIMG_H__6BCDCAE1_832F_11D4_AAFB_00C04F794BFF__INCLUDED_)