Click here to Skip to main content
Click here to Skip to main content

Steganography 12 - Regions with different data density

, 12 Jul 2006 CPOL
Rate this:
Please Sign up or sign in to vote.
Define regions inside an image to keep smooth colours free from hidden data.

Introduction

A well known method of steganoanalysis is to search one coloured area of the image for variations. In diffuse areas where every pixel has a different color than its neighbors, variations by hidden bits are hard to detect, but most pictures also contain areas with smooth colors. Look at this one:

  • The blue sky in the upper middle should not contain hidden data, because there are nearly no natural variations in the colors.
  • The clouds have more shades of blue, but anything that's not blue would be easy to find. If any data has to be hidden in the clouds, not more than one bit per pixel should be changed.
  • It is the same with the trees on the right: changing the higher bits would produce light colors, but only dark pixels are allowed here, so the capacity of each pixel is reduced to one or two bits.
  • The boats and the beach on the left side are better. They contain red, yellow, white, blue, green... We can change up to 7 bits in this region, nobody will notice anything.

To escape from simple variations analysis, we'll hide our secret message only in these regions, and with adjusted "bit rates":

Edit and Store Regions

Just as in the preceding examples, we need a carrier bitmap, a secret message, and a key.

The new feature is a Region Editor which lets the user define regions and their capacities.

An easy way to draw a region is to click the points of a polygon. So, we let the user click on the image, and add every clicked point to a polygon. A polygon can be closed with a double click, then the next click starts a new polygon:

private void picImage_MouseUp(object sender, MouseEventArgs e){
   if (e.Button == MouseButtons.Left){
      if (isDoubleClicked){
         //ignore the MouseUp event following a double click
         isDoubleClicked = false;
      }
      else{
           if (!isDrawing){
              //start a new polygon
              isDrawing = true;
              drawingPoints = new ArrayList();
              cleanImage = picImage.Image;
              bufferImage = new Bitmap(cleanImage.Width, cleanImage.Height);
           }

           AddPoint(e.X, e.Y);
      }
   }
}

When a polygon is being closed by a double click, we have to make sure that it does not overlap one of the already existing polygons. If the new polygon intersects another polygon, we merge the two regions. If the pölygon stands alone, we create a new region and add it to the list. ctlRegions is a RegionInfoList, this control displays statistics and input fields for each region.

private void picImage_DoubleClick(object sender, EventArgs e){
   if (drawingPoints.Count > 2){
      isDrawing = false;
      isDoubleClicked = true;

      Point[] points = (Point[])drawingPoints.ToArray(typeof(Point));
      GraphicsPath path = new GraphicsPath();
      path.AddPolygon(points);

      if (!UniteWithIntersectedRegions(path, points)){
         RegionInfo info = new RegionInfo(path, points, picImage.Image.Size);
         drawnRegions.Add(info); //add to regions
         ctlRegions.Add(new RegionInfoListItem(info)); //add to list
      }

      ReDrawImages(true);
   }
}

If another region has been drawn, we have to update the map and the statistics block. ReDrawImages paints the regions onto the source image and the map overview. (The map overview and the gradient brush are not necessary, they're just a nice visual effect.)

/// <summary>Display the source image with the regions on it in [picImage],
/// and only the regions in [picMap]</summary>
/// <param name="updateSummary">true: call UpdateSummary() when finished</param>
private void ReDrawImages(bool updateSummary){
    //create empty images
    Image bufferImageNoBackground =
          new Bitmap(baseImage.Width, baseImage.Height);
    Image bufferImageWithBackground = new
          Bitmap(baseImage.Width, baseImage.Height);

    //get graphics
    Graphics graphicsWithBackground =
             Graphics.FromImage(bufferImageWithBackground);
    Graphics graphicsNoBackground =
             Graphics.FromImage(bufferImageNoBackground);

    //draw/clear backgrounds
    graphicsNoBackground.Clear(Color.White);
    graphicsWithBackground.DrawImage(baseImage, 0, 0,
                  baseImage.Width, baseImage.Height);

    //draw regions
    foreach (RegionInfo info in drawnRegions){

        PathGradientBrush brush =
             new PathGradientBrush(info.Points, WrapMode.Clamp);
        brush.CenterColor = Color.Transparent;

        if (info == selectedRegionInfo){
           //mark the region that's selected in the list
            brush.SurroundColors = new Color[1] { Color.Green };
        }else{
            brush.SurroundColors = new Color[1] { Color.Red };
        }

        //draw the region
        graphicsWithBackground.DrawPolygon(new
                            Pen(Color.Black, 4), info.Points);
        graphicsNoBackground.DrawPolygon(new
                            Pen(Color.Black, 4), info.Points);
        graphicsWithBackground.FillRegion(brush, info.Region);
        graphicsNoBackground.FillRegion(brush, info.Region);
    }

    //clean up
    graphicsWithBackground.Dispose();
    graphicsNoBackground.Dispose();

    //show images
    picImage.Image = bufferImageWithBackground;
    picMap.Image = bufferImageNoBackground;
    picImage.Invalidate();
    picMap.Invalidate();

    //update numbers and errors
    if (updateSummary) { UpdateSummary(); }
}

The map has to be stored in the first pixels of the image so that it can be extracted before the rest of the message. That means, we have to embed a header into the image. When extracting the hidden message, we first have to extract the header, read the region information from it, and then we can extract the actual message from those regions. The header can be spread over all pixels from 0/0 to the first pixel in the topmost region. We won't know where the first region begins before we've extracted the map, so we have to store the index of the first pixel that belongs to any region in the header itself. The coordinates of this pixel are not important, because we'll treat the pixels as one long stream, not as rows and columns. A complete header contains these information:

  1. (Int32) Index (not coordinates!) of the topmost pixel in the first region.
  2. (Int32) Length of the following region data.
  3. For every region:
    1. (Int32) Length (Region.GetRegionData().Data.Length)
    2. (Int32) Capacity (Count of bytes to hide in this region)
    3. (byte) Count of used bits per pixel
    4. (byte[]) Region (Region.GetRegionData().Data)

The length of the header depends on the count and the complexity of the regions. When a new region is added in the Region Editor, we must check the new header's length and the position on the topmost region. If there are not enough pixels left between the image's first pixel and the first region, the header cannot be hidden. In that case, we'll display a warning and disable the "Next" button. The regions that are going to carry the actual message have to be big enough, we'll display another warning if the message does not fit into the regions:

private void UpdateSummary(){
   bool isOkay = true; //no errors yet

   long countPixels = 0; //count of selected pixels
   int capacity = 0; //capacity of all regions

   RegionInfo firstRegion = null; //topmost region - not found yet

   //first pixel inside a region - not found yet
   int firstPixelInRegions = baseImage.Width * baseImage.Height;

   //Int32 beginning of first region +
   //Int32 regions length + Byte bits per pixel
   long mapStreamLength = 65;

   foreach (RegionInfo info in drawnRegions) {
      countPixels += info.CountPixels;
      capacity += info.Capacity;

      mapStreamLength += 64; //Int32 RegionData Length + Int32 Capacity
      mapStreamLength += info.Region.GetRegionData().Data.Length * 8;

      //is this region the first one?
      if ((int)info.PixelIndices[0] < firstPixelInRegions) {
         firstPixelInRegions = (int)info.PixelIndices[0];
         firstRegion = info;
      }
   }

   //pixels in the region
   lblSelectedPixels.Text = countPixels.ToString();

   //percent of the image covered by the region
   lblPercent.Text = (100 * countPixels /
    (baseImage.Width*baseImage.Height)).ToString();

   //capacity
   lblCapacity.Text = capacity.ToString();
   if (capacity == messageLength) {
      SetControlColor(lblCapacity, false);
      errors.SetError(lblCapacity, String.Empty);
   } else {
     SetControlColor(lblCapacity, true);
     errors.SetError(lblCapacity,
       "Overall capacity must be equal to the message's length.");
     isOkay = false;
   }

   //header size
   lblHeaderSize.Text = mapStreamLength.ToString() + " Bits";

   //are there enough pixels left for the header?
   if (firstRegion != null) {
      if (firstPixelInRegions > mapStreamLength) {
         lblHeaderSpace.Text = firstPixelInRegions.ToString() + " Pixels";
         SetControlColor(lblHeaderSpace, false);
      } else {
        isOkay = false;
        lblHeaderSpace.Text = String.Format(
            "{0} Pixels - Please remove the topmost region.",
            firstPixelInRegions);
        SetControlColor(lblHeaderSpace, true);
        selectedRegionInfo = firstRegion;
        ctlRegions.SelectItem(firstRegion);
        ReDrawImages(false);
      }
   } else {
     lblHeaderSpace.Text = "0 - Please define one or more regions";
     SetControlColor(lblHeaderSpace, true);
   }

   btnNext.Enabled = isOkay;
}

private void SetControlColor(Control control, bool isError) {
   if (isError) {
      control.BackColor = Color.DarkRed;
      control.ForeColor = Color.White;
   } else {
     control.BackColor = SystemColors.Control;
     control.ForeColor = SystemColors.ControlText;
   }
}

If the regions are big enough, configured for enough capacity and leaves enough space for the header, UpdateSummary will enable the "Next" button. Now, the map and the message can be hidden.

Embed the Data

Until now, we have done nothing except receiving input data about the carrier image. Now, the interesting part begins! In the earlier articles, we used the key to locate pixels, and simply embedded the message. This won't work anymore. We have specific regions over which the data has to be distributed, and the header should be distributed evenly over the available pixels at the beginning of the image. That means, the bytes from the key stream cannot be used directly as the next offset, but we can use them to initialize a pseudo-random number generator. This number generator can choose the next offset:

When the message is extracted later on, we just have to initialize the System.Ramdom object with the same seed (a value from the key stream), and we'll get the same offsets again. But, we need two values to calculate the intervals: the length of the data we want to hide/extract, and the count of the remaining pixels. Let's hide these two Int32 values in the first 64 pixels so that we can read them easily.

public unsafe void Hide(Stream messageStream, Stream keyStream){
    //make sure that the image has RGB format
    Bitmap image = (Bitmap)carrierFile.Image;
    image = PaletteToRGB(image);

    int pixelOffset = 0, maxOffset = 0, messageValue = 0;
    byte key, messageByte, colorComponent;
    Random random;

    BitmapData bitmapData = image.LockBits(
        new Rectangle(0, 0, image.Width, image.Height),
        ImageLockMode.ReadOnly, PixelFormat.Format24bppRgb);

    //go to the first pixel
    PixelData* pPixel = (PixelData*)bitmapData.Scan0.ToPointer();
    PixelData* pFirstPixel;

    //get the first pixel that belongs to a region
    int firstPixelInRegions = image.Width * image.Height;
    foreach (RegionInfo info in carrierFile.RegionInfo){
        info.PixelIndices.Sort();
        if ((int)info.PixelIndices[0] < firstPixelInRegions){
            firstPixelInRegions = (int)info.PixelIndices[0];
        }
    }

    //hide [firstPixelInRegions]
    HideInt32(firstPixelInRegions, ref pPixel);

    //get map stream
    MemoryStream regionData = new MemoryStream();
    BinaryWriter regionDataWriter = new BinaryWriter(regionData);
    foreach (RegionInfo regionInfo in carrierFile.RegionInfo)
    {
        byte[] regionBytes = PointsToBytes(regionInfo.Points);
        regionDataWriter.Write((Int32)regionBytes.Length);
        regionDataWriter.Write((Int32)regionInfo.Capacity);
        regionDataWriter.Write(regionInfo.CountUsedBitsPerPixel);
        regionDataWriter.Write(regionBytes);
    }
    //go to the beginning of the stream
    regionDataWriter.Flush();
    regionData.Seek(0, SeekOrigin.Begin);

    //hide length of map stream
    HideInt32((Int32)regionData.Length, ref pPixel);

Now that the initial values have been stored, we can distribute the regions map over all the available pixels between pixel 65 and the first region:

    pFirstPixel = pPixel; //don't overwrite already written header

    int regionByte;
    while ((regionByte = regionData.ReadByte()) >= 0){
        key = GetKey(keyStream);
        random = new Random(key);

        for (int regionBitIndex = 0; regionBitIndex < 8; ){

            pixelOffset += random.Next(1,
              (int)((firstPixelInRegions-1 - pixelOffset) /
              ((regionData.Length - regionData.Position + 1)*8))
            );
            pPixel = pFirstPixel + pixelOffset;

            //place [regionBit] in one bit of the colour component

            //rotate color components
            currentColorComponent = (currentColorComponent == 2) ? 0 :
                                                  (currentColorComponent + 1);
            //get value of Red, Green or Blue
            colorComponent = GetColorComponent(pPixel, currentColorComponent);

            //put the bits into the color component
            //and write it back into the bitmap
            CopyBitsToColor(1, (byte)regionByte,
                      ref regionBitIndex, ref colorComponent);
            SetColorComponent(pPixel, currentColorComponent, colorComponent);
        }
    }

Now, we have hidden the regions and everything we need to extract them. It is time to get to the point and hide the secret message.

    //begin with the first pixel of the image
    pPixel = (PixelData*)bitmapData.Scan0.ToPointer();
    pFirstPixel = pPixel;

    foreach (RegionInfo regionInfo in carrierFile.RegionInfo){

        //go to first pixel of this region
        pPixel = (PixelData*)bitmapData.Scan0.ToPointer();
        pPixel += (int)regionInfo.PixelIndices[0];
        pixelOffset = 0;

        for (int n = 0; n < regionInfo.Capacity; n++){

            messageValue = messageStream.ReadByte();
            if (messageValue < 0) { break; } //end of message
            messageByte = (byte)messageValue;

            key = GetKey(keyStream);
            random = new Random(key);

            for (int messageBitIndex = 0; messageBitIndex < 8; ){

                maxOffset = (int)Math.Floor(
                  ((decimal)(regionInfo.CountPixels - pixelOffset - 1) *
                    regionInfo.CountUsedBitsPerPixel)/
                   (decimal)((regionInfo.Capacity - n) * 8)
                );

                pixelOffset += random.Next(1, maxOffset);
                pPixel = pFirstPixel + (int)regionInfo.PixelIndices[pixelOffset];

                //place [messageBit] in one bit of the colour component

                //rotate color components
                currentColorComponent = (currentColorComponent == 2) ? 0 :
                                                      (currentColorComponent + 1);
                //get value of Red, Green or Blue
                colorComponent = GetColorComponent(pPixel, currentColorComponent);

                //put the bits into the color component
                //and write it back into the bitmap
                CopyBitsToColor(
                   regionInfo.CountUsedBitsPerPixel,
                   messageByte, ref messageBitIndex,
                   ref colorComponent);
                SetColorComponent(pPixel, currentColorComponent, colorComponent);
            }
        }
    }

    image.UnlockBits(bitmapData);
    SaveBitmap(image, carrierFile.DestinationFileName);
}

Extract the Data

So, we have an image, and want to read a hidden message from it. We have to read the message's bytes in the same order they have been hidden:

  1. Get the length of the map data
  2. Get the index of the first pixel in the topmost region
  3. Use these values to extract the regions
  4. Use the regions to extract the message

Let's go and get the regions!

/// <summary>Extract the header from an image</summary>
/// <remarks>The header contains information about
///     the regions which carry the message</remarks>
/// <param name="keyStream">Key stream</param>
/// <returns>The extracted regions with all meta data that
///                is needed to extract the message</returns>
public unsafe RegionInfo[] ExtractRegionData(Stream keyStream) {
    byte key, colorComponent;
    PixelData* pPixel;
    PixelData* pFirstPixel;
    int pixelOffset = 0;
    Random random;

    Bitmap image = (Bitmap)carrierFile.Image;

    BitmapData bitmapData = image.LockBits(
        new Rectangle(0, 0, image.Width, image.Height),
        ImageLockMode.ReadOnly, PixelFormat.Format24bppRgb);

    //go to the first pixel
    pPixel = (PixelData*)bitmapData.Scan0.ToPointer();

    //get firstPixelInRegions
    int firstPixelInRegions = ExtractInt32(ref pPixel);

    //get length of region information
    int regionDataLength = ExtractInt32(ref pPixel);

    //get region information

    pFirstPixel = pPixel;
    MemoryStream regionData = new MemoryStream();

    byte regionByte;
    while (regionDataLength > regionData.Length) {
        regionByte = 0;
        key = GetKey(keyStream);
        random = new Random(key);

        for (int regionBitIndex = 0; regionBitIndex < 8; regionBitIndex++) {
            //move to the next pixel
            pixelOffset += random.Next(1,
               (int)(
                 (firstPixelInRegions - 1 - pixelOffset) /
                 ((regionDataLength - regionData.Length) * 8))
               );
            pPixel = pFirstPixel + pixelOffset;

            //rotate color components
            currentColorComponent = (currentColorComponent == 2) ? 0 :
                                                  (currentColorComponent + 1);
            //get value of Red, Green or Blue
            colorComponent = GetColorComponent(pPixel, currentColorComponent);

            //extract one bit and add it to [regionByte]
            AddBit(regionBitIndex, ref regionByte, 0, colorComponent);
        }

        //write the extracted byte
        regionData.WriteByte(regionByte);
    }

    image.UnlockBits(bitmapData);

Now, we have reconstructed the map stream. To do anything useful with it, we have to reconstruct the regions.

    //read regions from [regionData]

    ArrayList regions = new ArrayList();
    BinaryReader regionReader = new BinaryReader(regionData);

    Region anyRegion = new Region(); //dummy region
    RegionData anyRegionData = anyRegion.GetRegionData(); //dummy region data
    Region region; //extracted region
    byte[] regionContent; //extracted region data
    //extracted region header
    int regionLength, regionCapacity;
    byte regionBitsPerPixel;

    regionReader.BaseStream.Seek(0, SeekOrigin.Begin);
    do {
        //If the program crashes here,
        //the image is damaged,
        //it contains no hidden data,
        //or you tried to use a wrong key.
        int regionLength = regionReader.ReadInt32();
        int regionCapacity = regionReader.ReadInt32();
        byte regionBitsPerPixel = regionReader.ReadByte();
        byte[] regionContent = regionReader.ReadBytes(regionLength);

        Point[] regionPoints = BytesToPoints(regionContent);
        GraphicsPath regionPath = new GraphicsPath();
        regionPath.AddPolygon(regionPoints);

        Region region = new Region(regionPath);
        regions.Add(new RegionInfo(region, regionCapacity,
                        regionBitsPerPixel, image.Size));
    } while (regionData.Position < regionData.Length);

    return (RegionInfo[])regions.ToArray(typeof(RegionInfo));
}

We're nearly finished. Now, we know in which regions the message is embedded, how many bytes are hidden in which region, and how many bits per pixel must be extracted from the pixels.

/// <summary>Extract a message</summary>
/// <param name="messageStream">Empty stream to receive
///                    the extracted message</param>
/// <param name="keyStream">Key stream</param>
public unsafe void Extract(Stream messageStream, Stream keyStream) {

    //lock the bitmap, go to the first pixel, and so on
    //...
    //...

    foreach (RegionInfo regionInfo in carrierFile.RegionInfo) {

        //go to first pixel of this region
        pFirstPixel = (PixelData*)bitmapData.Scan0.ToPointer();
        pPixel = pFirstPixel + (int)regionInfo.PixelIndices[0];
        pixelOffset = 0;

        for (int n = 0; n < regionInfo.Capacity; n++) {

            messageByte = 0;
            key = GetKey(keyStream);
            random = new Random(key);

            for (int messageBitIndex = 0; messageBitIndex < 8; ) {
                //move to the next pixel

                maxOffset = (int)Math.Floor(
                  ((decimal)(regionInfo.CountPixels - pixelOffset - 1) *
                    regionInfo.CountUsedBitsPerPixel)/
                   (decimal)((regionInfo.Capacity - n) * 8)
                );

                pixelOffset += random.Next(1, maxOffset);

                pPixel = pFirstPixel +
                         (int)regionInfo.PixelIndices[pixelOffset];

                //rotate color components
                currentColorComponent = (currentColorComponent == 2) ? 0 :
                (currentColorComponent + 1);
                //get value of Red, Green or Blue
                colorComponent = GetColorComponent(pPixel,
                                        currentColorComponent);

                for(int carrierBitIndex=0; carrierBitIndex <
                   regionInfo.CountUsedBitsPerPixel; carrierBitIndex++)
                {
                    AddBit(messageBitIndex, ref messageByte,
                            carrierBitIndex, colorComponent);
                    messageBitIndex++;
                }
            }

            //add the re-constructed byte to the message
            messageStream.WriteByte(messageByte);
        }
    }

    //clean up
    //...
    //...
}

Done! Now, let's display the message and the regions from which it has been read.

That's all we need to escape from people who try to find our hidden message by searching for unexpected variations in uniform parts of the carrier image.

By the way, there is an additional channel for secret messages: if you're sure that the recipient is creative enough to see it, you can draw outlines and letters with the region editor:

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Corinna John
Software Developer
Germany Germany
Corinna lives in Hannover/Germany (CeBIT City) and works as a Delphi developer, though her favorite language is C#.

Comments and Discussions

 
QuestionHow to Dynamic watermark ? Pinmembernikhil94212-Aug-12 16:16 
AnswerRe: How to Dynamic watermark ? PinmemberCorinna John4-Aug-12 2:40 
GeneralBitmap QUAD aren't manged Pinmembernixite25-Aug-07 22:19 
GeneralAuto Hiding Pinmemberjames_dixon_200831-Jul-07 23:37 
GeneralScrollable picture box Pinmemberfirmwaredsp12-Jul-06 11:03 
GeneralRe: Scrollable picture box PinmemberCorinna John12-Jul-06 19:17 
GeneralRe: Scrollable picture box Pinmemberfirmwaredsp12-Jul-06 23:15 
Questioncan you do that? Pinmemberm_ali19-Jun-06 5:53 
hello , nice work but can you make your program found good region to hide Automatic not by user and set the size of data to hide Automatic also
thx
for DCT Steganography i can help you in that , i write that program use DCT to fight MPEG video file compressed.
 
Enginer: Mohamed Ali
AnswerRe: can you do that? Pinmemberjames_dixon_200831-Jul-07 23:44 
GeneralWonderful topic PinmemberPhan Dung2-Jan-05 15:33 
GeneralRe: Wonderful topic PinmemberCorinna John3-Jan-05 5:01 
QuestionCan I get the points or path from a region object ? Pinmembersubzero_ting8-Oct-04 21:25 
AnswerRe: Can I get the points or path from a region object ? PinmemberCorinna John9-Oct-04 0:07 
Questionhow about on dct theory..... is it possible? Pinmemberpsychomath10-Sep-04 3:47 
AnswerRe: how about on dct theory..... is it possible? PinmemberCorinna John10-Sep-04 6:44 
GeneralRe: how about on dct theory..... is it possible? Pinmemberpsychomath10-Sep-04 13:41 
GeneralHI THERE Pinmemberneha_roy15551-Sep-04 3:01 
QuestionVC6 HELP HOW???? Pinmembercnncnn18-Aug-04 20:15 
AnswerRe: VC6 HELP HOW???? PinmemberCorinna John19-Aug-04 6:51 
AnswerRe: VC6 HELP HOW???? Pinmemberfrewah24-Jul-06 10:36 
GeneralProblems... PinmemberHumanOsc10-Aug-04 23:06 
GeneralHello... PinmemberHumanOsc8-Aug-04 2:23 
GeneralRe: Hello... PinmemberCorinna John8-Aug-04 7:10 
GeneralRe: Hello... PinmemberHumanOsc8-Aug-04 23:56 
General... PinsussInverarity3-Aug-04 4:45 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web02 | 2.8.141022.2 | Last Updated 12 Jul 2006
Article Copyright 2004 by Corinna John
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid