Jump to content
  • Advertisement
Sign in to follow this  
JonW

Arithmetic Coding for Images

This topic is 4852 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I'm working on a custom lossless image for my game using an arithmetic coder. Here is the code that I have so far:
Uint16 m_nCode;					// The present input code value
Uint16 m_nLow;					// Start of the current code range
Uint16 m_nHigh;					// End of the current code range
Uint32 m_nUnderflowBits;		// Number of underflow bits pending

#define BUFFER_SIZE 256
Uint8 buffer[BUFFER_SIZE + 2];	// This is the i/o buffer
Uint8 *m_pCurrentByte;			// Pointer to current byte

Sint32 m_nOutputMask;

Sint32 input_bytes_left;
Sint32 input_bits_left;
Bool m_bPastEof;

Uint16 HiVal[256];
Uint16 LoVal[256];
Uint16 m_nScale;

// When decoding, this routine is called to figure out which symbol
// is presently waiting to be decoded.
Uint16 get_current_count (void)
{
	Uint32 range;
	Uint16 count;

	range = (Uint32)(m_nHigh - m_nLow) + 1;
	count = (Uint16)((((Uint32)(m_nCode - m_nLow) + 1) * m_nScale-1) / range);

	return count;
}

// This routine reads bits in from a file.  This routine is set up to
// allow for two dummy bytes to be read in after the end of file is
// reached.  This is because we have to keep feeding bits into the
// pipeline to be decoded so that the old stuff that is 16 bits upstream
// can be pushed out.
Uint16 input_bit (CFile *stream)
{
	if (input_bits_left == 0)
	{
		m_pCurrentByte++;
		input_bytes_left--;
		input_bits_left = 8;

		if (input_bytes_left == 0)
		{
			input_bytes_left = stream->Read(buffer, BUFFER_SIZE);

			if (input_bytes_left == 0)
			{
				if (m_bPastEof)
				{
					fprintf(stderr, "Bad input file\n");
					exit(-1);
				}

				else
				{
					m_bPastEof = 1;

					// Read two past, since two bits need to be shifted out
					// of high and low to complete word
					input_bytes_left = 2;
				}
			}

			m_pCurrentByte = buffer;
		}
	}

	input_bits_left--;

	// Return the lowest bit
	return ((*m_pCurrentByte >> input_bits_left) & 1);
}

/*
 * Just figuring out what the present symbol is doesn't remove
 * it from the input bit stream.  After the character has been
 * decoded, this routine has to be called to remove it from the
 * input stream.
 */
void remove_symbol_from_stream (CFile *stream, Uint16 low_count, Uint16 high_count)
{
	Uint32 nRange;

	nRange = (m_nHigh - m_nLow) + 1;
	m_nHigh = m_nLow + (Uint16)((nRange * high_count) / m_nScale - 1);
	m_nLow = m_nLow + (Uint16)((nRange * low_count) / m_nScale);

	while (True)
	{
		// The most significant bits match, so shift them out
		if ((m_nHigh & 0x8000) == (m_nLow & 0x8000))
		{
		}

		// If underflow is threatining, shift out the 2nd most significant
		else if ((m_nLow & 0x4000) && !(m_nHigh & 0x4000))
		{
			// Flip second most significant of code
			m_nCode ^= 0x4000;

			// Clear 2 upper bits of low
			m_nLow &= 0x3fff;

			// Change second most significant of high to 1
			m_nHigh |= 0x4000;
		}
		else
		{
			return;
		}

		m_nLow <<= 1;
		m_nHigh <<= 1;
		m_nCode <<= 1;

		// Bring in a new high bit
		m_nHigh |= 1;

		// Bring in a new input bit
		m_nCode += input_bit(stream);
	}
}


Uint8 ReadNextVal (CFile *pFile)
{
	short int count = get_current_count();

	// Find the range the value is in
	for (Uint8 i = 0; i < 256; i++)
	{
		if ( count >= LoVal && count < HiVal)
		{
			remove_symbol_from_stream(pFile, LoVal, HiVal);
			return i;
		}
	}

	return 0;
}

// Create the minimum and maximum probability tables for each color value
void CreateTables (void)
{
	m_nScale = 0;

	for (Sint32 i = 0; i < 256; i++)
	{
		LoVal = m_nScale;

		// Because of filtering, low values are common, and so are
		// high values which represent negative. Give them a higher
		// probability.
		if (i <= 10 || i >= 245)
		{
			HiVal = m_nScale+10;
			m_nScale += 10;
		}

		else if (i <= 20 || i >= 235)
		{
			HiVal = m_nScale+5;
			m_nScale += 5;
		}

		else
		{
			HiVal = m_nScale+1;
			m_nScale += 1;
		}
	}
}

//////////////////////////////////////////////////////////////////////////
// Loads image from given file into pBuffer.
//////////////////////////////////////////////////////////////////////////
Bool LoadIgf (Uint8 **pBuffer, CFile *pFile, Sint32 &nWidth, Sint32 &nHeight)
{
	CreateTables();

	m_nCode = 0;

	for (int i = 0; i < 16; i++)
	{
		m_nCode <<= 1;
		m_nCode += input_bit(pFile);
	}

	m_nLow = 0;
	m_nHigh = 0xffff;

	input_bits_left = 0;
	input_bytes_left = 1;
	m_bPastEof = False;

	nWidth = pFile->ReadWord();
	nHeight = pFile->ReadWord();

	*pBuffer = new Uint8[nWidth*nHeight*3];
	Uint8 *pColor = *pBuffer;

	for (int y = 0; y < nHeight; y++)
	{
		// First pixel in each row is not filtered
		*pColor = ReadNextVal(pFile);
		pColor++;
		*pColor = ReadNextVal(pFile);
		pColor++;
		*pColor = ReadNextVal(pFile);
		pColor++;

		// Read rest of row, filtering as we go
		for (int x = 1; x < nWidth; x++)
		{
			*pColor = (Uint8)(((Uint)*(pColor-3) + ReadNextVal(pFile)) & 0xff);
			pColor++;
			*pColor = (Uint8)(((Uint)*(pColor-3) + ReadNextVal(pFile)) & 0xff);
			pColor++;
			*pColor = (Uint8)(((Uint)*(pColor-3) + ReadNextVal(pFile)) & 0xff);
			pColor++;
		}
	}

	return True;
}

/*
 * The output bit routine just has to set a bit in the current byte
 * if requested to.  After that, it updates the mask.  If the mask
 * shows that the current byte is filled up, it is time to go to the
 * next character in the buffer.  If the next character is past the
 * end of the buffer, it is time to flush the buffer.
 */
void output_bit (CFile *stream, int bit)
{
	// Write the bit if it's a 1 to the next bit position
	if (bit)
	{
		*m_pCurrentByte |= m_nOutputMask;
	}

	// Increase the bit position
	m_nOutputMask >>= 1;

	// We filled this byte
	if (m_nOutputMask == 0)
	{
		m_nOutputMask = 0x80;
		m_pCurrentByte++;

		// Buffer is full, so write it
		if (m_pCurrentByte == (buffer + BUFFER_SIZE))
		{
			stream->Write(buffer, BUFFER_SIZE);
			m_pCurrentByte = buffer;
		}

		// Initialize next byte to 0
		*m_pCurrentByte = 0;
	}
}

// This routine uses a low count, a high count, and a range,
// instead of the more conventional probability ranges.  The encoding
// process takes two steps.  First, the values of high and low are
// updated to take into account the range restriction created by the
// new symbol.  Then, as many bits as possible are shifted out to
// the output stream.  Finally, high and low are stable again and
// the routine returns.
void encode(CFile *stream, Uint16 low_count, Uint16 high_count)
{
	Uint32 range;

	// Add one because high is one under
    range = (m_nHigh-m_nLow) + 1;

	// Make high one under so it continues forever
	m_nHigh = m_nLow + (Uint16)((range * high_count) / m_nScale - 1);

	m_nLow = m_nLow + (Uint16)((range * low_count) / m_nScale);

	// Output common bits between high and low
    while (True)
    {
		// The most significant digit matches, output it
		if ((m_nHigh & 0x8000) == (m_nLow & 0x8000))
		{
			output_bit(stream, m_nHigh & 0x8000);

			while (m_nUnderflowBits > 0)
			{
				output_bit(stream, (~m_nHigh) & 0x8000);
				m_nUnderflowBits--;
			}
		}

		// Test if the numbers are in danger of underflow.
		// The significant bits don't match, and low is approaching high, ex:
		// high = 10000000 low = 01111111
		else if ((m_nLow & 0x4000) && !(m_nHigh & 0x4000))
		{
			m_nUnderflowBits += 1;

			// Clear 2 upper bits of low
			m_nLow &= 0x3fff;

			// Change second most significant of high to 1
			m_nHigh |= 0x4000;
		}

		else
		{
			return;
		}

		m_nLow <<= 1;
		m_nHigh <<= 1;

		// Insert a new one (high continues forever)
		m_nHigh |= 1;
	}
}

/*
 * At the end of the encoding process, there are still significant
 * bits left in the high and low registers.  We output two bits,
 * plus as many underflow bits as are necessary.
 */
void flush_arithmetic_encoder (CFile *stream)
{
	output_bit(stream, m_nLow & 0x4000);
	m_nUnderflowBits++;
	while (m_nUnderflowBits-- > 0)
		output_bit(stream, (~m_nLow) & 0x4000);
}

void flush_output_bitstream (CFile *stream)
{
    stream->Write(buffer, (m_pCurrentByte - buffer) + 1);
    m_pCurrentByte = buffer;
}

// Write the given image buffer to file
Bool SaveIgf (Uint8 *pBuffer, CFile *pFile, Sint32 &nWidth, Sint32 &nHeight)
{
	m_nLow = 0;
	m_nHigh = 0xffff;
	m_nUnderflowBits = 0;
	m_pCurrentByte = buffer;
	*m_pCurrentByte = 0;
	m_nOutputMask = 0x80;

	CreateTables();

	pFile->WriteWord(nWidth);
	pFile->WriteWord(nHeight);

	Uint8 val;

	for (int y = 0; y < nHeight; y++)
	{
		// Write the first pixel plainly, because there is no pixel to the left
		// to filter from

		val = *pBuffer;
		encode_symbol(pFile, LoVal[val], HiVal[val]);
		pBuffer++;
		val = *pBuffer;
		encode_symbol(pFile, LoVal[val], HiVal[val]);
		pBuffer++;
		val = *pBuffer;
		encode_symbol(pFile, LoVal[val], HiVal[val]);
		pBuffer++;

		// Write rest of row
		for (int x = 1; x < nWidth; x++)
		{
			// Filter each channel as its written (subtract value from prior pixel)

			// Write the red channel
			val = ((Sint)*pBuffer - (Sint)*(pBuffer-3)) & 0xff;
			encode(pFile, LoVal[val], HiVal[val]);
			pBuffer++;

			// Write the blue channel
			val = ((Sint)*pBuffer - (Sint)*(pBuffer-3)) & 0xff;
			encode(pFile, LoVal[val], HiVal[val]);
			pBuffer++;

			// Write the green channel
			val = ((Sint)*pBuffer - (Sint)*(pBuffer-3)) & 0xff;
			encode(pFile, LoVal[val], HiVal[val]);
			pBuffer++;
		}
	}

    flush_arithmetic_encoder(pFile);
    flush_output_bitstream(pFile);

	return True;
}

As you can probably see, I'm filtering each row by subtracting each pixel channel color from the previous pixel's corresponding color, which gives me a value around -10 to 10 that is translated to about 245-255 and 0-10. I then pass the values to a coder, and set the probabilities higher for the usual filtered values. However the program always reaches the exit() call and closes. If I set the probabilities equally (x for the low, x+1 for the high, 256 for the scale) I obviously don't get any compression, but the program doesn't reach the exit line. I have found that although the equal probabilities don't cause the program to close, the images has a strong greenish tinge. This is not from the filtering, as I have tested the filtering without the coding and the coding without the filtering. Any ideas on why this code is acting up is appreciated. I am using the arithmetic coding method from http://dogma.net/markn/articles/arith/part1.htm . Thanks! Jon

Share this post


Link to post
Share on other sites
Advertisement
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!