Pixels

In order for any digital computer processing to be carried out on an image, it must first be stored within the computer in a suitable form that can be manipulated by a computer program. The most practical way of doing this is to divide the image up into a collection of discrete (and usually small) cells, which are known as pixels. Most commonly, the image is divided up into a rectangular grid of pixels, so that each pixel is itself a small rectangle. Once this has been done, each pixel is given a pixel value that represents the color of that pixel. It is assumed that the whole pixel is the same color, and so any color variation that did exist within the area of the pixel before the image was discretized is lost. However, if the area of each pixel is very small, then the discrete nature of the image is often not visible to the human eye.
Other pixel shapes and formations can be used, most notably the hexagonal grid, in which each pixel is a small hexagon. This has some advantages in image processing, including the fact that pixel connectivity is less ambiguously defined than with a square grid, but hexagonal grids are not widely used. Part of the reason is that many image capture systems (e.g. most CCD cameras and scanners) intrinsically discretize the captured image into a rectangular grid in the first instance.

Pixel Values

Each of the pixels that represents an image stored inside a computer has a pixel value which describes how bright that pixel is, and/or what color it should be. In the simplest case of binary images, the pixel value is a 1-bit number indicating either foreground or background. For a grayscale images, the pixel value is a single number that represents the brightness of the pixel. The most common

pixel format is the byte image, where this number is stored as an 8-bit integer giving a range of possible values from 0 to 255. Typically zero is taken to be black, and 255 is taken to be white. Values in between make up the different shades of gray.
To represent color images, separate red, green and blue components must be specified for each pixel (assuming an RGB colorspace), and so the pixel `value' is actually a vector of three numbers. Often the three different components are stored as three separate `grayscale' images known as color planes (one for each of red, green and blue), which have to be recombined when displaying or processing.
Multi-spectral images can contain even more than three components for each pixel, and by extension these are stored in the same kind of way, as a vector pixel value, or as separate color planes.
The actual grayscale or color component intensities for each pixel may not actually be stored explicitly. Often, all that is stored for each pixel is an index into a colormap in which the actual intensity or colors can be looked up.
Although simple 8-bit integers or vectors of 8-bit integers are the most common sorts of pixel values used, some image formats support different types of value, for instance 32-bit signed integers or floating point values. Such values are extremely useful in image processing as they allow processing to be carried out on the image where the resulting pixel values are not necessarily 8-bit integers. If this approach is used then it is usually necessary to set up a colormap which relates particular ranges of pixel values to particular displayed colors.

Pixel Connectivity

The notation of pixel connectivity describes a relation between two or more pixels. For two pixels to be connected they have to fulfill certain conditions on the pixel brightness and spatial adjacency.
First, in order for two pixels to be considered connected, their pixel values must both be from the same set of values V. For a grayscale image, V might be any range of graylevels, e.g. V={22,23,...40}, for a binary image we simple have V={1}.
To formulate the adjacency criterion for connectivity, we first introduce the notation of neighborhood. For a pixel p with the coordinates (x,y) the set of pixels given by:

is called its 4-neighbors. Its 8-neighbors are defined as

From this we can infer the definition for 4- and 8-connectivity:
Two pixels p and q, both having values from a set V are 4-connected if q is from the set Eqn:eqnlan4

and 8-connected if q is from Eqn:eqnlan8

.
General connectivity can either be based on 4- or 8-connectivity; for the following discussion we use 4-connectivity.
A pixel p is connected to a pixel q if p is 4-connected to q or if p is 4-connected to a third pixel which itself is connected to q. Or, in other words, two pixels q and p are connected if there is a path from p and q on which each pixel is 4-connected to the next one.
A set of pixels in an image which are all connected to each other is called a connected component. Finding all connected components in an image and marking each of them with a distinctive label is called connected component labeling.
An example of a binary image with two connected components which are based on 4-connectivity can be seen in Figure 1. If the connectivity were based on 8 -neighbors, the two connected components would merge into one.

Structuring Elements

The field of mathematical morphology provides a number of important image processing operations, including erosion, dilation, opening and closing. All these morphological operators take two pieces of data as input. One is the input image, which may be either binary or grayscale for most of the operators. The other is the structuring element. It is this that determines the precise details of the effect of the operator on the image.
The structuring element is sometimes called the kernel, but we reserve that term for the similar objects used in convolutions.
The structuring element consists of a pattern specified as the coordinates of a number of discrete points relative to some origin. Normally cartesian coordinates are used and so a convenient way of representing the element is as a small image on a rectangular grid. Figure 1 shows a number of different structuring elements of various sizes. In each case the origin is marked by a ring around that point. The origin does not have to be in the center of the structuring element, but often it is. As suggested by the figure, structuring elements that fit into a 3×3 grid with its origin at the center are the most commonly seen type.

Figure 1 Some example structuring elements.

Note that each point in the structuring element may have a value. In the simplest structuring elements used with binary images for operations such as erosion, the elements only have one value, conveniently represented as a one. More complicated elements, such as those used with thinning or grayscale morphological operations, may have other pixel values.
An important point to note is that although a rectangular grid is used to represent the structuring element, not every point in that grid is part of the structuring element in general. Hence the elements shown in Figure 1 contain some blanks. In many texts, these blanks are represented as zeros, but this can be confusing and so we avoid it here.
When a morphological operation is carried out, the origin of the structuring element is typically translated to each pixel position in the image in turn, and then the points within the translated structuring element are compared with the underlying image pixel values. The details of this comparison, and the effect of the outcome depend on which morphological operator is being used.

BITMAPFILEHEADER [3.0]

Bitmap File Information
The BITMAPFILEHEADER data structure contains information about the type,
size, and layout of a device-independent bitmap (DIB) file.

typedef struct tag BITMAPFILEHEADER {
WORD bfType;
DWORD bfSize;
WORD bfReserved1;
WORD bfReserved2;
DWORD bfOffBits;
} BITMAPFILEHEADER;

The BITMAPFILEHEADER data structure contains the following fields:

Field Description
bfType Specifies the type of file. It must be BM.
bfSize Specifies the size in DWORDs of the file.
bfReserved1 Is reserved and must be set to zero.
bfReserved2 Is reserved and must be set to zero.
bfOffBits Specifies in bytes the offset from the BITMAPFILEHEADER
of the actual bitmap in the file.

Comments A BITMAPINFO or BITMAPCOREINFO data structure immediately
follows the BITMAPFILEHEADER structure in the DIB file.

BITMAPINFO [3.0]

Device-Indpendent Bitmap Information
The BITMAPINFO structure fully defines the dimensions and color
information for a Windows 3.0 device-independent bitmap.

typedef struct tagBITMAPINFO {
BITMAPINFOHEADER bmiHeader;
RGBQUAD bmiColors[1];
} BITMAPINFO;

The BITMAPINFO structure contains the following fields:

Field Description
bmiHeader Specifies a BITMAPINFOHEADER data structure that
contains information about the dimensions and color format of a device-independent bitmap.
bmiColors Specifies an array of RGBQUAD data structures that
define the colors in the bitmap.

Comments: A Windows 3.0 device-independent bitmap consists of two
distinct parts: a BITMAPINFO data structure that describes the dimensions
and colors of the bitmap, and an array of bytes that define the pixels of
the bitmap. The bits in the array are packed together, but each scan line
must be zero-padded to end on a LONG boundary. Segment boundaries can
appear anywhere in the bitmap, however. The origin of the bitmap is the
lower-left corner.

The biBitCount field of the BITMAPINFOHEADER structure determines the
number of bits which define each pixel and the maximum number of colors
in the bitmap. This field may be set to any of the following values:

Value Meaning
1 The bitmap is monochrome, and the bmiColors field must
contain two entries. Each bit in the bitmap array represents a
pixel. If the bit is clear, the pixel is displayed with the
color of the first entry in the bmiColors table; if the bit is
set, the pixel has the color of the second entry in the table.
4 The bitmap has a maximum of 16 colors, and the bmiColors
field contains up to 16 entries. Each pixel in the bitmap is
represented by a four-bit index into the color table.
For example, if the first byte in the bitmap is 0x1F, then the
byte represents two pixels. The first pixel contains the color
in the second table entry, and the second pixel contains the
color in the 16th table entry.
8 The bitmap has a maximum of 256 colors, and the bmiColors
field contains up to 256 entries. In this case, each byte in the
array represents a single pixel.
24 The bitmap has a maximum of 2^24 colors. The bmiColors
field is NULL, and each three bytes in the bitmap array
represents the relative intensities of red, green, and blue,
respectively, of a pixel.

The biClrUsed field of the BITMAPINFOHEADER structure specifies the number
of color indexes in the color table actually used by the bitmap. If the
biClrUsed field is set to 0, the bitmap uses the maximum number of colors
corresponding to the value of the biBitCount field.

The colors in the bmiColors table should appear in order of importance.

Alternatively, for functions that use device-independent bitmaps, the
bmiColors field can be an array of 16-bit unsigned integers that specify
an index into the currently realized logical palette instead of explicit
RGB values. In this case, an application using the bitmap must call
device-independent bitmap functions with the wUsage parameter set to
DIB_PAL_COLORS.

Note: The bmiColors field should not contain palette indices if the
bitmap is to be stored in a file or transferred to another application.
Unless the application uses the bitmap exclusively and under its complete
control, the bitmap color table should contain explicit RGB values.

BITMAPINFOHEADER [3.0]

Device-Independent Bitmap Format Information
The BITMAPINFOHEADER structure contains information about the dimensions
and color format of a Windows 3.0 device-independent bitmap.

typedef struct tagBITMAPINFOHEADER{
DWORD biSize;
DWORD biWidth;
DWORD biHeight;
WORD biPlanes;
WORD biBitCount
DWORD biCompression;
DWORD biSizeImage;
DWORD biXPelsPerMeter;
DWORD biYPelsPerMeter;
DWORD biClrUsed;
DWORD biClrImportant;
} BITMAPINFOHEADER;

The BITMAPINFOHEADER structure has the following fields:

Field Description
biSize Specifies the number of bytes required by the
BITMAPINFOHEADER structure.
biWidth Specifies the width of the bitmap in pixels.
biHeight Specifies the height of the bitmap in pixels.
biPlanes Specifies the number of planes for the target device and
must be set to 1.
biBitCount Specifies the number of bits per pixel. This value must
be 1, 4, 8, or 24.
biCompression Specifies the type of compression for a compressed
bitmap. It can be one of the following values:.
Value Meaning
BI_RGB Specifies that the bitmap is not
compressed.
BI_RLE8 Specifies a run-length encoded format
for bitmaps with 8 bits per pixel. The
compression format is a two-byte
format consisting of a count byte
followed by a byte containing a color
index. See the following 'Comments'
section for more information.
BI_RLE4 Specifies a run-length encoded format
for bitmaps with 4 bits per pixel. The
compression format is a two-byte
format consisting of a count byte
followed by two word-length color
indexes. See the following 'Comments'
section for more information.
biSizeImage Specifies the size in bytes of the image.
biXPelsPerMeter Specifies the horizontal resolution in pixels per meter of the target device for the bitmap. An application can use this value to select a bitmap from a resource group that best matches the characteristics of the current device. biYPelsPerMeter Specifies the vertical resolution in pixels per meter of the target device for the bitmap.
biClrUsed Specifies the number of color indexes in the color table
actually used by the bitmap. If this value is 0, the
bitmap uses the maximum number of colors corresponding
to the value of the biBitCount field. See the
description of the BITMAPINFO data structure earlier in
this chapter for more information on the maximum sizes
of the color table. If biClrUsed is nonzero, then the
biClrUsed field specifies the actual number of colors
which the graphics engine or device driver will access
if the biBitCount field is less than 24. If the
biBitCount field is set to 24, the biClrUsed field
specifies the size of the reference color table used to
optimize performance of Windows color palettes.
If the bitmap is a 'packed' bitmap (that is, a bitmap in
which the bitmap array immediately follows the
BITMAPINFO header and which is referenced by a single
pointer), the biClrUsed field must be set to 0 or to the
actual size of the color table.
biClrImportant Specifies the number of color indexes that are considered
important for displaying the bitmap. If this value is 0,
then all colors are important.

Comments: The BITMAPINFO data structure combines the
BITMAPINFOHEADER structure and a color table to provide a complete
definition of the dimensions and colors of a Windows 3.0
device-independent bitmap. See the description of the BITMAPINFO data
structure for more information about specifying a Windows 3.0
device-independent bitmap.

An application should use the information stored in the biSize field to
locate the color table in a BITMAPINFO data structure with a method such
as the following:

pColor = ((LPSTR) pBitmapInfo + (WORD) (pBitmapInfo -> biSize))

Bitmap Compression Formats Windows supports formats for compressing
bitmaps that define their colors with 8 bits per pixel and with 4 bits
per pixel. Compression reduces the disk and memory storage required for
the bitmap. The following paragraphs describe these formats.

When the biCompression field is set to BI_RLE8, the bitmap is compressed
using a run-length encoding format for an 8-bit bitmap. This format may
be compressed in either of two modes:

7 Encoded
7 Absolute

Both modes can occur anywhere throughout a single bitmap.

Encoded mode consists of two bytes: the first byte specifies the number
of consecutive pixels to be drawn using the color index contained in the
second byte. In addition, the first byte of the pair can be set to zero
to indicate an escape that denotes an end of line, end of bitmap, or a
delta. The interpretation of the escape depends on the value of the
second byte of the pair. The following list shows the meaning of the
second byte:

Second Byte
Of Escape
Meaning
0 End of line.
1 End of bitmap.
2 Delta. The two bytes following the escape contain
unsigned values indicating the horizontal and vertical
offset of the next pixel from the current position.

Absolute mode is signalled by the first byte set to zero and the second
byte set to a value between 03H and FFH. In absolute mode, the second
byte represents the number of bytes which follow, each of which contains
the color index of a single pixel. When the second byte is set to 2 or
less, the escape has the same meaning as in encoded mode.
In absolute mode, each run must be aligned on a word boundary.

The following example shows the hexadecimal values of an 8-bit compressed
bitmap:

03 04 05 06 00 03 45 56 67 00 02 78 00 02 05 01
02 78 00 00 09 1E 00 01

This bitmap would expand as follows (two-digit values represent a color
index for a single pixel):

04 04 04
06 06 06 06 06
45 56 67
78 78
move current position 5 right and 1 down
78 78
end of line
1E 1E 1E 1E 1E 1E 1E 1E 1E
end of RLE bitmap

When the biCompression field is set to BI_RLE4, the bitmap is compressed
using a run-length encoding format for a 4-bit bitmap, which also uses
encoded and absolute modes. In encoded mode, the first byte of the pair
contains the number of pixels to be drawn using the color indexes in the
second byte. The second byte contains two color indexes, one in its
high-order nibble (that is, its low-order four bits) and one in its
low-order nibble. The first of the pixels is drawn using the color
specified by the high-order nibble, the second is drawn using the color
in the low-order nibble, the third is drawn with the color in the
high-order nibble, and so on, until all the pixels specified by the
first byte have been drawn.

In absolute mode, the first byte contains zero, the second byte contains
the number of color indexes that follow, and subsequent bytes contain
color indexes in their high- and low-order nibbles, one color index for
each pixel. In absolute mode, each run must be aligned on a word boundary.
The end-of-line, end-of-bitmap, and delta escapes also apply to BI_RLE4.

The following example shows the hexadecimal values of a 4-bit compressed
bitmap:

03 04 05 06 00 06 45 56 67 00 04 78 00 02 05 01
04 78 00 00 09 1E 00 01

This bitmap would expand as follows (single-digit values represent a
color index for a single pixel):

0 4 0
0 6 0 6 0
4 5 5 6 6 7
7 8 7 8
move current position 5 right and 1 down
7 8 7 8
end of line
1 E 1 E 1 E 1 E 1
end of RLE bitmap

RGBQUAD [3.0]

RGB Color Structure
The RGBQUAD data structure describes a color consisting of relative
intensities of red, green, and blue. The bmiColors field of the
BITMAPINFO data structure consists of an array of RGBQUAD data structures.

typedef struct tagRGBQUAD {
BYTE rgbBlue;
BYTE rgbGreen;
BYTE rgbRed;
BYTE rgbReserved;
} RGBQUAD;

The RGBQUAD structure contains the following fields:

Field Description
rgbBlue Specifies the intensity of blue in the color.
rgbGreen Specifies the intensity of green in the color.
rgbRed Specifies the intensity of red in the color.
rgbReserved Is not used and must be set to zero.

#define BI_RGB 0L
#define BI_RLE8 1L
#define BI_RLE4 2L

BITMAPCOREINFO [3.0]

Device-Indpendent Bitmap Information
The BITMAPCOREINFO structure fully defines the dimensions and color
information for a device-independent bitmap that is compatible with
Microsoft OS/2 Presentation Manager versions 1.1 and 1.2 bitmaps.

typedef struct _BITMAPCOREINFO {
BITMAPCOREHEADER bmciHeader;
RGBTRIPLE bmciColors[];
} BITMAPCOREINFO;

The BITMAPCOREINFO structure contains the following fields:

Field Description
bmciHeader Specifies a BITMAPCOREHEADER data structure that
contains information about the dimensions and color
format of a device-independent bitmap.
bmciColors Specifies an array of RGBTRIPLE data structures that
define the colors in the bitmap.

Comments An OS/2 Presentation Manager device-independent bitmap
consists of two distinct parts: a BITMAPCOREINFO data structure that
describes the dimensions and colors of the bitmap, and an array of bytes
which define the pixels of the bitmap. The bits in the array are packed
together, but each scan line must be zero-padded to end on a LONG
boundary. Segment boundaries can appear anywhere in the bitmap, however.
The origin of the bitmap is the lower-left corner.

The bcBitCount field of the BITMAPCOREHEADER structure determines the
number of bits which define each pixel and the maximum number of colors
in the bitmap. This field may be set to any of the following values:

Value Meaning
1 The bitmap is monochrome, and the bmciColors field must
contain two entries. Each bit in the bitmap array represents a
pixel. If the bit is clear, the pixel is displayed with the
color of the first entry in the bmciColors table; if the bit is
set, the pixel has the color of the second entry in the table.
4 The bitmap has a maximum of 16 colors, and the bmciColors
field contains 16 entries. Each pixel in the bitmap is represented
by a four-bit index into the color table.
For example, if the first byte in the bitmap is 0x1F, then the
byte represents two pixels. The first pixel contains the color in
the second table entry, and the second pixel contains the color
in the 16th table entry.
8 The bitmap has a maximum of 256 colors, and the bmciColors
field contains 256 entries. In this case, each byte in the array
represents a single pixel.
24 The bitmap has a maximum of 2^24 colors. The bmciColors
field is NULL, and each three bytes in the bitmap array
represents the relative intensities of red, green, and blue,
respectively, of a pixel.

The colors in the bmciColors table should appear in order of importance.

Alternatively, for functions that use device-independent bitmaps, the
bmciColors field can be an array of 16-bit unsigned integers that
specify an index into the currently realized logical palette instead of
explicit RGB values. In this case, an application using the bitmap must
call device-independent bitmap functions with the wUsage parameter
set to DIB_PAL_COLORS.

Note The bmciColors field should not contain palette indexes if the
bitmap is to be stored in a file or transferred to another application.
Unless the application uses the bitmap exclusively and under its
complete control, the bitmap color table should contain explicit
RGB values.

BITMAPCOREHEADER [3.0]

Device-Independent Bitmap Format Information
The BITMAPCOREHEADER structure contains information about the dimensions
and color format of a device-independent bitmap that is compatible with
Microsoft OS/2 Presentation Manager versions 1.1 and 1.2 bitmaps.

typedef struct tagBITMAPCOREHEADER {
DWORD bcSize;
WORD bcWidth;
WORD bcHeight;
WORD bcPlanes;
WORD bcBitCount;
} BITMAPCOREHEADER;

The BITMAPCOREHEADER structure has the following fields:

Field Description
bcSize Specifies the number of bytes required by the BITMAPCOREHEADER
structure.
bcWidth Specifies the width of the bitmap in pixels.
bcHeight Specifies the height of the bitmap in pixels.
bcPlanes Specifies the number of planes for the target device and
must be set to 1.
bcBitCount Specifies the number of bits per pixel. This value must
be 1, 4, 8, or 24.

Comments The BITMAPCOREINFO data structure combines the
BITMAPCOREHEADER structure and a color table to provide a complete
definition of the dimensions and colors of a device-independent bitmap.
See the description of the BITMAPCOREINFO data structure for more
information about specifying a device-independent bitmap.

An application should use the information stored in the bcSize field to
locate the color table in a BITMAPCOREINFO data structure with a method
such as the following:

pColor = ((LPSTR) pBitmapCoreInfo + (WORD) (pBitmapCoreInfo -> bcSize))

RGBTRIPLE [3.0]

RGB Color Structure
The RGBTRIPLE data structure describes a color consisting of relative
intensities of red, green, and blue. The bmciColors field of the
BITMAPCOREINFO data structure consists of an array of RGBTRIPLE data
structures.

typedef struct tagRGBTRIPLE {
BYTE rgbtBlue;
BYTE rgbtGreen;
BYTE rgbtRed;
} RGBTRIPLE;

The RGBTRIPLE structure contains the following fields:

Field Description
rgbtBlue Specifies the intensity of blue in the color.
rgbtGreen Specifies the intensity of green in the color.
rgbtRed Specifies the intensity of red in the color.

-----------------------------------------------------------------------

Non official comments

How to distinguish between BITMAPINFO and BITMAPCOREINFO when reading
in a BMP file.

After reading the BITMAPFILEHEADER read the next DWORD from the file.
If it is 12 you are reading a BITMAPCOREHEADER, if it is 40 you are
reading a BITMAPINFOHEADER.