001/* 002 @Copyright (c) 1998-2015 The Regents of the University of California. 003 All rights reserved. 004 005 Permission is hereby granted, without written agreement and without 006 license or royalty fees, to use, copy, modify, and distribute this 007 software and its documentation for any purpose, provided that the 008 above copyright notice and the following two paragraphs appear in all 009 copies of this software. 010 011 IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY 012 FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES 013 ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF 014 THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF 015 SUCH DAMAGE. 016 017 THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES, 018 INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 019 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE 020 PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF 021 CALIFORNIA HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, 022 ENHANCEMENTS, OR MODIFICATIONS. 023 024 PT_COPYRIGHT_VERSION 2 025 COPYRIGHTENDKEY 026 */ 027package ptolemy.domains.sdf.lib.vq; 028 029import java.io.FileNotFoundException; 030import java.io.IOException; 031import java.io.InputStream; 032import java.net.MalformedURLException; 033import java.net.URL; 034 035import ptolemy.actor.lib.Transformer; 036import ptolemy.data.IntMatrixToken; 037import ptolemy.data.IntToken; 038import ptolemy.data.StringToken; 039import ptolemy.data.Token; 040import ptolemy.data.expr.Parameter; 041import ptolemy.data.type.BaseType; 042import ptolemy.kernel.CompositeEntity; 043import ptolemy.kernel.util.IllegalActionException; 044import ptolemy.kernel.util.NameDuplicationException; 045import ptolemy.kernel.util.Workspace; 046import ptolemy.math.IntegerMatrixMath; 047import ptolemy.util.FileUtilities; 048 049/////////////////////////////////////////////////////////////////// 050//// HTVQEncode 051 052/** 053 This actor encodes a matrix using Hierarchical Table-Lookup Vector 054 Quantization. 055 056 <p>The matrix must be of dimensions that are amenable to this 057 method. (i.e. 2x1, 2x2, 4x2, 4x4, etc.) Instead of performing a 058 full-search vector quantization during execution, all the optimal encoding 059 vectors are calculated before hand and stored in a lookup table. (This is 060 known as Table-lookup Vector Quantization). However, for large vector sizes 061 the lookup tables are unmanageably large. This actor approximates a 062 full search VQ by storing the lookup tables hierarchically. 063 The encoding is broken up into stages, and at each stage a number of 2x1 064 table lookup VQs are performed. For example, 065 starting with a 4x2 vector in the first stage, codebook 0 (which operates 066 on raw pixels) is used 4 times, resulting in a 2x2 vector of codewords. 067 In the second stage, codebook 1 is used twice, resulting in a 2x1 vector. 068 Lastly, a single 2x1 VQ using codebook 2 (which operates on codewords 069 representing 2x2 vectors) returns a single codeword for the 4x2 vector.</p> 070 071 <p>The input is an IntMatrixToken corresponding to the block to be encoded. 072 The values in this matrix are assumed to be between 0 and 255. The output 073 is an IntToken with value between 0 and 255. Integers are used here because 074 of the minimal byte support in Ptolemy or JAVA. 075 The size of the input matrix should be the same as the parameters blockHeight 076 and blockWidth.</p> 077 078 <p>The codebook is specified as a binary file that will be read during 079 initialization. This file actually contains five sets of codebooks and 080 lookups tables. The first set is for 2x1 blocks, the second is for 2x2 081 blocks, etc. (Thus the supplied codebook is only sufficient for block sizes 082 up to 8x4 pixels.) In each set, the codebook precedes the lookup-tables. 083 The codebook consists of all 256 codevectors, row scanned from top to bottom. 084 The lookup table consists of 64K entries (one for each pair of codewords from 085 the previous stage). Each entry in the lookup table is an 8-bit codeword.</p> 086 087 <pre> 088 Stage 0: 2x1 block size 089 codebook = 256 blocks x 2 bytes = 512 bytes 090 lookup tables = 65536 entries x 1 byte = 65536 bytes 091 Stage 1: 2x2 block size 092 codebook = 256 blocks x 4 bytes = 1024 bytes 093 lookup tables = 65536 entries x 1 byte = 65536 bytes 094 Stage 2: 4x2 block size 095 codebook = 256 blocks x 8 bytes = 2048 bytes 096 lookup tables = 65536 entries x 1 byte = 65536 bytes 097 Stage 3: 4x4 block size 098 codebook = 256 blocks x 16 bytes = 4096 bytes 099 lookup tables = 65536 entries x 1 byte = 65536 bytes 100 Stage 4: 8x4 block size 101 codebook = 256 blocks x 32 bytes = 8192 bytes 102 lookup tables = 65536 entries x 1 byte = 65536 bytes 103 </pre> 104 105 <p>The supplied codebook was trained using images from the 106 USC image archive and is suitable for most general applications.</p> 107 108 <p>For more information here are some interesting references: </p> 109 110 <p>A. Gersho and R. M. Gray, <i>Vector Quantization and Signal Compression</i>. 111 Kluwer Academic Publishers, Boston, 1992.</p> 112 113 <p>P. C. Chang, J. May, R. M. Gray, "Hierarchical Vector Quantizers with 114 Table Lookup Encoders," <i> International Conference on Acoustics Speech 115 and Signal Processing</i>, pp. 1452-1455, 1985. </p> 116 117 <p>M. Vishwanath and P. Chou, "An Efficient Algorithm for Hierarchical 118 Compression of Video," <i>International Conference on Image Processing</i>, 119 vol. 3, pp. 275-279, Nov. 1994</p> 120 121 @author Steve Neuendorffer 122 @version $Id$ 123 @since Ptolemy II 0.2 124 @Pt.ProposedRating Yellow (neuendor) 125 @Pt.AcceptedRating Red (neuendor) 126 */ 127public class HTVQEncode extends Transformer { 128 /** Construct an actor in the specified container with the specified 129 * name. 130 * @param container The container. 131 * @param name The name of this adder within the container. 132 * @exception IllegalActionException If the actor cannot be contained 133 * by the proposed container. 134 * @exception NameDuplicationException If the name coincides with 135 * an actor already in the container. 136 */ 137 public HTVQEncode(CompositeEntity container, String name) 138 throws IllegalActionException, NameDuplicationException { 139 super(container, name); 140 141 input.setTypeEquals(BaseType.INT_MATRIX); 142 output.setTypeEquals(BaseType.INT); 143 144 codeBook = new Parameter(this, "codeBook", new StringToken( 145 "/ptolemy/domains/sdf" + "/lib/vq/data/usc_hvq_s5.dat")); 146 codeBook.setTypeEquals(BaseType.STRING); 147 148 blockCount = new Parameter(this, "blockCount", new IntToken("1")); 149 blockCount.setTypeEquals(BaseType.INT); 150 151 blockWidth = new Parameter(this, "blockWidth", new IntToken("4")); 152 blockWidth.setTypeEquals(BaseType.INT); 153 154 blockHeight = new Parameter(this, "blockHeight", new IntToken("2")); 155 blockHeight.setTypeEquals(BaseType.INT); 156 157 input_tokenConsumptionRate = new Parameter(input, 158 "tokenConsumptionRate"); 159 input_tokenConsumptionRate.setTypeEquals(BaseType.INT); 160 input_tokenConsumptionRate.setExpression("blockCount"); 161 162 output_tokenProductionRate = new Parameter(output, 163 "tokenProductionRate"); 164 output_tokenProductionRate.setTypeEquals(BaseType.INT); 165 output_tokenProductionRate.setExpression("blockCount"); 166 } 167 168 /////////////////////////////////////////////////////////////////// 169 //// ports and parameters //// 170 171 /** A Parameter of type String, giving the location of the codebook data 172 * file relative to the root classpath. 173 */ 174 public Parameter codeBook; 175 176 /** The number of blocks to be encoded during each firing. 177 * The default value is one, which will always work, but using a higher 178 * number (such as the number of blocks in a frame) will speed things up. 179 */ 180 public Parameter blockCount; 181 182 /** The width, in pixels, of the block to encode. */ 183 public Parameter blockWidth; 184 185 /** The width, in pixels, of the block to encode. */ 186 public Parameter blockHeight; 187 188 /** The input rate. */ 189 public Parameter input_tokenConsumptionRate; 190 191 /** The output rate. */ 192 public Parameter output_tokenProductionRate; 193 194 /////////////////////////////////////////////////////////////////// 195 //// public methods //// 196 197 /** Clone the actor into the specified workspace. 198 * @param workspace The workspace for the new object. 199 * @return A new actor. 200 * @exception CloneNotSupportedException If a derived class contains 201 * an attribute that cannot be cloned. 202 */ 203 @Override 204 public Object clone(Workspace workspace) throws CloneNotSupportedException { 205 HTVQEncode newObject = (HTVQEncode) super.clone(workspace); 206 newObject.ipbuf_encodep1 = new int[8][8]; 207 newObject.ipbuf_encodep2 = new int[8][8]; 208 newObject._codeBook = new int[6][256][]; 209 newObject._lookupTable = new int[6][65536]; 210 return newObject; 211 } 212 213 /** 214 * Fire this actor. 215 * Consume a codeword on the input, and perform Vector Quantization using 216 * Hierarchical Table-Lookup Vector Quantization. Send the computed 217 * codeword on the output. 218 * @exception IllegalActionException If a contained method throws it. 219 */ 220 @Override 221 public void fire() throws IllegalActionException { 222 super.fire(); 223 int j; 224 _blocks = input.get(0, _blockCount); 225 226 for (j = 0; j < _blockCount; j++) { 227 _codewords[j] = new IntToken(_encode( 228 IntegerMatrixMath.fromMatrixToArray( 229 ((IntMatrixToken) _blocks[j]).intMatrix()), 230 _blockWidth * _blockHeight)); 231 } 232 233 output.send(0, _codewords, _blockCount); 234 } 235 236 /** 237 * Initialize this actor. 238 * Load the codebooks and lookup tables from the file given by the 239 * parameter "codeBook". 240 * @exception IllegalActionException If the parameters do not have 241 * legal values, or the codebook file cannot be read. 242 */ 243 @Override 244 public void initialize() throws IllegalActionException { 245 super.initialize(); 246 247 InputStream source = null; 248 249 _blockCount = ((IntToken) blockCount.getToken()).intValue(); 250 _blockWidth = ((IntToken) blockWidth.getToken()).intValue(); 251 _blockHeight = ((IntToken) blockHeight.getToken()).intValue(); 252 253 _codewords = new IntToken[_blockCount]; 254 _blocks = new ptolemy.data.Token[_blockCount]; 255 256 String filename = ((StringToken) codeBook.getToken()).stringValue(); 257 258 try { 259 if (filename != null) { 260 try { 261 URL dataurl = FileUtilities.nameToURL(filename, null, 262 getClass().getClassLoader()); 263 _debug("HTVQEncode: codebook = " + dataurl); 264 source = dataurl.openStream(); 265 } catch (MalformedURLException e) { 266 System.err.println(e.toString()); 267 } catch (FileNotFoundException e) { 268 System.err.println("HTVQEncode: " + "file not found: " + e); 269 } catch (IOException e) { 270 throw new IllegalActionException("HTVQEncode: error reading" 271 + " input file: " + e.getMessage()); 272 } 273 } 274 275 int i; 276 int j; 277 int x; 278 int size = 1; 279 byte[] temp; 280 281 for (i = 0; i < 5; i++) { 282 size = size * 2; 283 temp = new byte[size]; 284 285 for (j = 0; j < 256; j++) { 286 _codeBook[i][j] = new int[size]; 287 288 if (_fullRead(source, temp) != size) { 289 throw new IllegalActionException( 290 "Error reading " + "codebook file!"); 291 } 292 293 for (x = 0; x < size; x++) { 294 _codeBook[i][j][x] = temp[x] & 255; 295 } 296 } 297 298 temp = new byte[65536]; 299 300 // read in the lookup table. 301 if (_fullRead(source, temp) != 65536) { 302 throw new IllegalActionException( 303 "Error reading " + "codebook file!"); 304 } 305 306 for (x = 0; x < 65536; x++) { 307 _lookupTable[i][x] = temp[x] & 255; 308 } 309 } 310 } catch (Throwable throwable) { 311 throw new IllegalActionException(this, throwable, 312 "Problem reading codebook"); 313 } finally { 314 if (source != null) { 315 try { 316 source.close(); 317 } catch (IOException e) { 318 // Argh... can't we do anything right? 319 } 320 } 321 } 322 } 323 324 /////////////////////////////////////////////////////////////////// 325 //// private methods //// 326 private int _encode(int[] p, int length) { 327 int[][] p5; 328 int[][] p4; 329 int[][] p3; 330 int[][] p2; 331 int[][] p1; 332 int[][] p0; 333 int numberOfStages; 334 int stage = 0; 335 int ip; 336 337 numberOfStages = _stages(length); 338 339 if (numberOfStages > 4) { 340 throw new RuntimeException("Number of stages = " + numberOfStages 341 + ", which is " + "greater than 4"); 342 } 343 344 p5 = ipbuf_encodep1; 345 p4 = ipbuf_encodep2; 346 p3 = ipbuf_encodep1; 347 p2 = ipbuf_encodep2; 348 p1 = ipbuf_encodep1; 349 p0 = ipbuf_encodep2; 350 351 switch (numberOfStages) { 352 case 4: 353 354 // System.arraycopy is faster for large vectors 355 System.arraycopy(p, 0, p5[0], 0, 8); 356 System.arraycopy(p, 8, p5[1], 0, 8); 357 System.arraycopy(p, 16, p5[2], 0, 8); 358 System.arraycopy(p, 24, p5[3], 0, 8); 359 break; 360 361 case 3: 362 System.arraycopy(p, 0, p4[0], 0, 4); 363 System.arraycopy(p, 4, p4[1], 0, 4); 364 System.arraycopy(p, 8, p4[2], 0, 4); 365 System.arraycopy(p, 12, p4[3], 0, 4); 366 break; 367 368 case 2: 369 p3[0][0] = p[0]; 370 p3[0][1] = p[1]; 371 p3[0][2] = p[2]; 372 p3[0][3] = p[3]; 373 p3[1][0] = p[4]; 374 p3[1][1] = p[5]; 375 p3[1][2] = p[6]; 376 p3[1][3] = p[7]; 377 break; 378 379 case 1: 380 p2[0][0] = p[0]; 381 p2[0][1] = p[1]; 382 p2[1][0] = p[2]; 383 p2[1][1] = p[3]; 384 break; 385 386 case 0: 387 p1[0][0] = p[0]; 388 p1[0][1] = p[1]; 389 break; 390 } 391 392 switch (numberOfStages) { 393 case 4: 394 395 //XSIZE = 8, YSIZE = 4 396 ip = ((p5[0][0] & 255) << 8) + (p5[0][1] & 255); 397 p4[0][0] = _lookupTable[stage][ip]; 398 ip = ((p5[0][2] & 255) << 8) + (p5[0][3] & 255); 399 p4[1][0] = _lookupTable[stage][ip]; 400 ip = ((p5[0][4] & 255) << 8) + (p5[0][5] & 255); 401 p4[2][0] = _lookupTable[stage][ip]; 402 ip = ((p5[0][6] & 255) << 8) + (p5[0][7] & 255); 403 p4[3][0] = _lookupTable[stage][ip]; 404 405 ip = ((p5[1][0] & 255) << 8) + (p5[1][1] & 255); 406 p4[0][1] = _lookupTable[stage][ip]; 407 ip = ((p5[1][2] & 255) << 8) + (p5[1][3] & 255); 408 p4[1][1] = _lookupTable[stage][ip]; 409 ip = ((p5[1][4] & 255) << 8) + (p5[1][5] & 255); 410 p4[2][1] = _lookupTable[stage][ip]; 411 ip = ((p5[1][6] & 255) << 8) + (p5[1][7] & 255); 412 p4[3][1] = _lookupTable[stage][ip]; 413 414 ip = ((p5[2][0] & 255) << 8) + (p5[2][1] & 255); 415 p4[0][2] = _lookupTable[stage][ip]; 416 ip = ((p5[2][2] & 255) << 8) + (p5[2][3] & 255); 417 p4[1][2] = _lookupTable[stage][ip]; 418 ip = ((p5[2][4] & 255) << 8) + (p5[2][5] & 255); 419 p4[2][2] = _lookupTable[stage][ip]; 420 ip = ((p5[2][6] & 255) << 8) + (p5[2][7] & 255); 421 p4[3][2] = _lookupTable[stage][ip]; 422 423 ip = ((p5[3][0] & 255) << 8) + (p5[3][1] & 255); 424 p4[0][3] = _lookupTable[stage][ip]; 425 ip = ((p5[3][2] & 255) << 8) + (p5[3][2] & 255); 426 p4[1][3] = _lookupTable[stage][ip]; 427 ip = ((p5[3][4] & 255) << 8) + (p5[3][4] & 255); 428 p4[2][3] = _lookupTable[stage][ip]; 429 ip = ((p5[3][6] & 255) << 8) + (p5[3][6] & 255); 430 p4[3][3] = _lookupTable[stage][ip]; 431 stage++; 432 433 // Fall through to next case 434 case 3: 435 436 //XSIZE = 4, YSIZE = 4 437 ip = ((p4[0][1] & 255) << 8) + (p4[0][0] & 255); 438 p3[0][0] = _lookupTable[stage][ip]; 439 ip = ((p4[0][3] & 255) << 8) + (p4[0][2] & 255); 440 p3[1][0] = _lookupTable[stage][ip]; 441 442 ip = ((p4[1][1] & 255) << 8) + (p4[1][0] & 255); 443 p3[0][1] = _lookupTable[stage][ip]; 444 ip = ((p4[1][3] & 255) << 8) + (p4[1][2] & 255); 445 p3[1][1] = _lookupTable[stage][ip]; 446 447 ip = ((p4[2][1] & 255) << 8) + (p4[2][0] & 255); 448 p3[0][2] = _lookupTable[stage][ip]; 449 ip = ((p4[2][3] & 255) << 8) + (p4[2][2] & 255); 450 p3[1][2] = _lookupTable[stage][ip]; 451 452 ip = ((p4[3][1] & 255) << 8) + (p4[3][0] & 255); 453 p3[0][3] = _lookupTable[stage][ip]; 454 ip = ((p4[3][3] & 255) << 8) + (p4[3][2] & 255); 455 p3[1][3] = _lookupTable[stage][ip]; 456 stage++; 457 458 // Fall through to next case 459 case 2: 460 461 //XSIZE = 4, YSIZE = 2 462 ip = ((p3[0][1] & 255) << 8) + (p3[0][0] & 255); 463 p2[0][0] = _lookupTable[stage][ip]; 464 ip = ((p3[0][3] & 255) << 8) + (p3[0][2] & 255); 465 p2[1][0] = _lookupTable[stage][ip]; 466 467 ip = ((p3[1][1] & 255) << 8) + (p3[1][0] & 255); 468 p2[0][1] = _lookupTable[stage][ip]; 469 ip = ((p3[1][3] & 255) << 8) + (p3[1][2] & 255); 470 p2[1][1] = _lookupTable[stage][ip]; 471 stage++; 472 473 // Fall through to next case 474 case 1: 475 476 //XSIZE = 2, YSIZE = 2 477 ip = ((p2[0][1] & 255) << 8) + (p2[0][0] & 255); 478 p1[0][0] = _lookupTable[stage][ip]; 479 ip = ((p2[1][1] & 255) << 8) + (p2[1][0] & 255); 480 p1[0][1] = _lookupTable[stage][ip]; 481 stage++; 482 483 case 0: 484 485 //XSIZE = 2, YSIZE = 1 486 ip = ((p1[0][1] & 255) << 8) + (p1[0][0] & 255); 487 p0[0][0] = _lookupTable[stage][ip]; 488 stage++; 489 } 490 491 return p0[0][0]; 492 } 493 494 private int _fullRead(InputStream s, byte[] b) throws IOException { 495 int length = 0; 496 int remaining = b.length; 497 int bytesRead = 0; 498 499 while (remaining > 0) { 500 bytesRead = s.read(b, length, remaining); 501 502 if (bytesRead == -1) { 503 throw new IOException("Unexpected EOF"); 504 } 505 506 remaining -= bytesRead; 507 length += bytesRead; 508 } 509 510 return length; 511 } 512 513 /** Given a vector of the given length, compute the codebook stage 514 * appropriate. Basically, compute log base 2 of length, assuming 515 * length is a power of 2. 516 */ 517 private int _stages(int length) { 518 int x = 0; 519 520 if (length < 2) { 521 throw new RuntimeException( 522 "Vector length of " + length + "must be greater than 1"); 523 } 524 525 while (length > 2) { 526 length = length >> 1; 527 x++; 528 } 529 530 return x; 531 } 532 533 /////////////////////////////////////////////////////////////////// 534 //// private variables //// 535 private int[][] ipbuf_encodep1 = new int[8][8]; 536 537 private int[][] ipbuf_encodep2 = new int[8][8]; 538 539 private int[][][] _codeBook = new int[6][256][]; 540 541 private int[][] _lookupTable = new int[6][65536]; 542 543 private IntToken[] _codewords; 544 545 private Token[] _blocks; 546 547 private int _blockCount; 548 549 private int _blockWidth; 550 551 private int _blockHeight; 552}