Raster Scan, Random Scan & Image Processing

Posted on Feb 7, 2025 in Business Administration and Innovation Management

Raster Scan Displays

Raster Scan Displays are the most common type of graphics monitor, employing CRT technology, based on television technology. In a raster scan system, the electron beam sweeps across the screen from top to bottom, one row at a time. A pattern of illuminated spots is created by turning the beam intensity on and off as it moves across each row. The refresh buffer, or frame buffer, stores the picture definition as a set of intensity values for all screen points. These stored intensity values are retrieved from the frame buffer and painted on the screen, one row (scan line) at a time. Each screen point is referred to as a pixel. Refreshing in raster scan systems is done at a rate of 60-80 frames per second (Hz). At the end of each scan line, the electron beam returns to the left side of the screen to begin displaying the next scan line; this is known as the horizontal retrace. At the end of each frame, the electron beam returns to the top left corner to begin the next frame.

A key function of the display process is scan conversion, which digitizes a picture definition given in an application program into a set of pixel-intensity values for storage in the refresh buffer. Display processors are used to relieve the CPU from graphics tasks, performing functions like creating different line styles, displaying color areas, and interfacing with input devices such as a mouse or joystick.

Advantages:

• Displays real-life images with different shades.
• Offers a wider color range than random scan displays.

Disadvantages:

• Lower resolution compared to random scan displays.
• Requires more memory.
• Stores data about the intensities of all pixels.

Cathode Ray Tube (CRT)

The primary output device in a graphic system is a video monitor, with most video monitors based on the standard Cathode Ray Tube (CRT) design. An electron gun emits a beam of electrons, which passes through focusing and deflection systems that direct the beam toward specified positions on the phosphor-coated screen. The phosphor emits a small spot of light at each position contacted by the electron beam. Because this light fades rapidly, the picture must be redrawn repeatedly by quickly directing the electron beam back over the same points—a technique used in refresh CRTs.

The primary components of an electron gun are the heated metal cathode and a control grid. Heat is supplied to the cathode, causing electrons to be ‘boiled off’. The intensity of the electron beam is controlled by setting voltage levels on the control grid. The amount of light emitted by the phosphor coating depends on the number of electrons striking the screen; thus, brightness is controlled by varying the voltage on the control grid. A smaller negative voltage on the control grid decreases the number of electrons passing through, while a high negative voltage will stop electrons from passing through.

The focusing system forces the electron beam to converge into a small spot as it strikes the phosphor. Focusing is accomplished with either electric or magnetic fields. Magnetic deflection coils, mounted on the CRT envelope, produce a magnetic field that properly directs the electron beam. One pair of coils accomplishes horizontal deflection, and the other pair handles vertical deflection.

Line Drawing Algorithm

#define Round(a) ((int)(a+0.5))
void lineDDA(int xa, int ya, int xb, int yb) {
    int dx = xb - xa, dy = yb - ya, steps, k;
    float xIncrement, yIncrement, x = xa, y = ya;

    if (abs(dx) > abs(dy))
        steps = abs(dx);
    else
        steps = abs(dy);

    xIncrement = dx / (float)steps;
    yIncrement = dy / (float)steps;

    setPixel(Round(x), Round(y));

    for (k = 0; k < steps; k++) {
        x += xIncrement;
        y += yIncrement;
        setPixel(Round(x), Round(y));
    }
}

Polygons

• Regular Polygons: Number of edges equals the number of angles.
• Convex Polygons: A line generated by taking any two points within the polygon must lie entirely within the polygon.
• Concave Polygons: A line generated by taking any two points within the polygon may lie outside the polygon.

Polygon Inside/Outside Test

This test identifies whether a point is inside or outside a polygon, often used for hollow polygons. Two common methods are:

A) Even-Odd Method:

1. Draw a line from a point P to a distant point outside the object’s coordinate extents.
2. Count the number of edge crossings along the line. If the number of crossings is odd, P is an interior point; otherwise, P is exterior.

B) Winding Number Method:

• Initialize the winding number to 0.
• Draw a line from point P to a distant point beyond the object’s coordinate extents.
• Count edge crossings: add 1 for right-to-left crossings, subtract 1 for left-to-right crossings.
• If the winding number is nonzero, P is an interior point; otherwise, P is exterior.

Scaling

Scaling changes the size of an object by expanding or compressing its dimensions. This is achieved by multiplying the original coordinates (X, Y) by scaling factors (SX, SY) to get the new coordinates (X’, Y’):

X’ = X * SX

Y’ = Y * SY

Translation

Translation repositions an object along a straight-line path. A point (X, Y) is translated by adding translation distances (tx, ty) to get a new position (X’, Y’):

X’ = X + tx

Y’ = Y + ty

The pair (tx, ty) is called the translation vector or shift vector. These equations can also be represented using column vectors:

P = [X, Y]^T, P’ = [X’, Y’]^T, T = [tx, ty]^T

Rotation

Rotation moves an object at a particular angle θ (theta) from its origin. If point P(X, Y) is at angle φ from the horizontal X-coordinate with distance r from the origin, rotating it by angle θ results in a new point P'(X’, Y’):

X’ = X * cos(θ) – Y * sin(θ)

Y’ = X * sin(θ) + Y * cos(θ)

Reflection

Reflection is the mirror image of the original object, equivalent to a rotation operation with a 180° angle. The size of the object does not change in reflection transformation.

Shear

Shear transformation slants the shape of an object. There are two types: X-Shear and Y-Shear.

X-Shear: Preserves the Y coordinate and changes the X coordinate, causing vertical lines to tilt.

Y’ = Y + Shy * X

X’ = X

Y-Shear: Preserves the X coordinate and changes the Y coordinate, causing horizontal lines to transform into lines that slope.

X’ = X + Shx * Y

Y’ = Y

Flood Fill Algorithm

In this method, a seed point inside a region is selected, and either a four-connected or eight-connected approach is used to fill the area with a specified color. Flood fill is suitable for filling areas with multiple color boundaries.

Disadvantages:

• Slow algorithm.
• May fail for large polygons.
• Requires knowledge of surrounding pixels.

Algorithm:

procedure floodfill (x, y, fill_color, old_color: integer)
    if (getpixel (x, y) = old_color) then
        setpixel (x, y, fill_color);
        floodfill (x+1, y, fill_color, old_color);
        floodfill (x-1, y, fill_color, old_color);
        floodfill (x, y+1, fill_color, old_color);
        floodfill (x, y-1, fill_color, old_color);

Flood Fill vs. Boundary Fill

• Flood Fill: Colors an entire area in an enclosed figure through interconnected pixels using a single color. It can use an unpredictable amount of memory and is time-consuming.
• Boundary Fill: Similar to flood fill, but stops when a given color boundary is found. It is more complicated but is a linear algorithm and doesn’t require recursion, making it less time-consuming.

Midpoint Circle Algorithm

1. Input radius r and circle center (xc, yc), and obtain the first point on the circumference of a circle centered on the origin as (x0, y0) = (0, r).
2. Calculate the initial value of the decision parameter as P0 = 5/4 – r.
3. At each xk position, starting at k = 0, perform the following test: If Pk < 0, the next point along the circle centered on (0, 0) is (xk+1, yk) and Pk+1 = Pk + 2xk+1 + 1. Otherwise, the next point along the circle is (xk+1, yk-1) and Pk+1 = Pk + 2xk+1 + 1 – 2yk+1.
4. Determine symmetry points in the other seven octants.
5. Move each calculated pixel position (x, y) onto the circular path centered on (xc, yc) and plot the coordinate values: x = x + xc, y = y + yc.
6. Repeat steps 3 through 5 until x >= y.

Bresenham’s Circle Drawing Algorithm

1. Input radius r and circle center (xc, yc), then set the coordinates for the first point on the circumference of a circle centered on the origin as (x0, y0) = (0, r).
2. Calculate the initial decision parameter as d0 = 3 – 2r.
3. At each xi, from i = 0, perform the following: If di < 0, the next point to plot along the circle centered on (0, 0) is (xi+1, yi) and di+1 = di + 4xi + 6. Otherwise, the next point to plot is (xi+1, yi-1) and di+1 = di + 4(xi – yi) + 10.
4. Determine the symmetry points in the other seven octants.
5. Move each calculated pixel position (x, y) onto the circular path centered at (xc, yc) and plot the coordinate values: x = x + xc, y = y + yc.
6. Repeat steps 3 through 5 until x >= y.

Electrostatic Deflection and Persistence

• When electrostatic deflection is used, two pairs of parallel plates are mounted inside the CRT envelope. One pair controls vertical deflection, and the other controls horizontal deflection.
• Persistence is defined as the time it takes for the emitted light from the screen to decay to one-tenth of its original intensity. Lower persistence phosphors require a higher refresh rate. Graphics monitors typically have a persistence in the range of 10 to 60 microseconds.

Resolution and Aspect Ratio

• Resolution: The maximum number of points that can be displayed without overlap on a CRT. Higher resolution systems are often referred to as high-definition systems.
• Aspect Ratio: The ratio of vertical points to horizontal points necessary to produce equal-length lines in both directions on the screen. It can also be expressed as the ratio of horizontal to vertical points.

Interactive vs. Non-Interactive Computer Graphics

• Interactive Computer Graphics: Involves two-way communication between the computer and the user. The observer can control the image using an input device (e.g., a video game controller).
• Non-Interactive Computer Graphics: Also known as passive computer graphics, where the user has no control over the image. It involves one-way communication, and the image is a product of a static stored program (e.g., images shown on television).

Raster Displays vs. Random Displays

Random Scan Display

Also known as calligraphic displays, vector displays, or stroke displays, random scan displays direct the electron beam only to the parts of the screen where a picture is to be drawn. These monitors draw pictures one line at a time, similar to how a pen plotter operates. The picture definition is stored as a set of line-drawing commands in a refresh display file or refresh buffer. The system cycles through these commands, drawing each component line, and then cycles back to the first command.

Random Scan System: An application program and graphics package are stored in system memory. Graphics commands are translated into a display file, which the display processor accesses to refresh the screen. The display processor, sometimes called a display processing unit or graphics controller, cycles through each command during every refresh cycle. Graphics patterns are drawn by directing the electron beam along the component lines, with lines defined by coordinate endpoints converted to x and y deflection voltages.

Advantages:

• Higher resolution compared to raster scan displays.
• Produces smooth line drawings.
• Requires less memory.

Disadvantages:

• Cannot draw realistic images with different shades.
• Color limitations.

Window to Viewport Transformation

This process transforms 2D world-coordinate objects to device coordinates. Objects inside the world or clipping window are mapped to the viewport, the area on the screen where world coordinates are displayed.

• World Coordinate: Cartesian coordinate system used to define the diagram (e.g., Xwmin, Xwmax, Ywmin, Ywmax).
• Device Coordinate: Screen coordinate system where objects are displayed (e.g., Xvmin, Xvmax, Yvmin, Yvmax).
• Window: Area in world coordinates selected for display.
• Viewport: Area on the device coordinates where graphics are displayed.

Steps:

1. Translate world coordinates to normalized coordinates.
2. Scale normalized coordinates to match the viewport (device coordinate system).
3. Translate to device coordinates (viewport).

Normalized Points:

• On window: (Xw – Xwmin) / (Xwmax – Xwmin), (Yw – Ywmin) / (Ywmax – Ywmin)
• On viewport: (Xv – Xvmin) / (Xvmax – Xvmin), (Yv – Yvmin) / (Yvmax – Yvmin)

Parallel Projection vs. Perspective Projection

Scan Line Algorithm

An image-space method to identify visible surfaces, extending the scan line algorithm for polygon filling. Unlike depth buffer methods, which process one surface at a time, the scan line method processes multiple surfaces simultaneously. It maintains depth information for a single scan line.

Tables Maintained:

• Edge Table: Contains coordinate endpoints, inverse slope of each line, and pointers to the polygon table.
• Polygon Table: Contains plane coefficients, color information, and a flag initialized to false.

Algorithm:

1. For all polygons intersecting a scan line, process faces from left to right.
2. For overlapping faces, determine depth to identify the nearest face and enter its intensities into the refresh buffer.
3. Maintain an active list of edges intersecting the scan line, sorted by increasing x values.

For example, with polygon faces ABCD and EFGH:

• For scanline 1, the Active Edge List is {AB, BC, EH, FG}. Between edges AB and BC, the flag for surface S1 is ON, and its intensity is entered into the refresh buffer. Between BC and EH, both flags are OFF. Between EH and FG, only the flag for S2 is ON, and its intensity is entered.
• For scanline 2, the Active Edge List is {AD, EH, BC, FG}. Depth calculation is performed for overlapping regions.

Perspective Projection

In perspective projection, the distance from the center of projection to the projection plane is finite, mimicking human vision. Objects farther away appear smaller, and nearer objects appear bigger.

• Center of Projection: Point where lines or projections not parallel to the projection plane appear to meet.
• View Plane or Projection Plane: Determined by the view reference point R0(x0, y0, z0) and the view plane normal.
• Location of an Object: Specified by a point P(x, y, z) in world coordinates.

Types of Perspective Projection:

1. One Point Perspective Projection: Occurs when any principal axis intersects with the projection plane.
2. Two Point Perspective Projection: Occurs when the projection plane intersects two principal axes.
3. Three Point Perspective Projection: Occurs when all three axes intersect with the projection plane.

Image Processing

Image processing is a method to perform operations on an image to enhance it or extract useful information. It is a type of signal processing where the input is an image, and the output may be an image or characteristics associated with that image.

Purpose of Image Processing:

1. Visualization: Observe objects that are not visible.
2. Image Sharpening and Restoration: Create a better image.
3. Image Retrieval: Seek an image of interest.
4. Measurement of Pattern: Measure various objects in an image.
5. Image Recognition: Distinguish objects in an image.

Digital Image Processing

Techniques that manipulate digital images using computers.

Advantages:

• Improves visual quality and intensity distribution.
• Allows for image modification with different techniques.
• Reduces data required through image compression.

Disadvantages:

• Requires significant processing power.
• Environmental conditions may degrade image quality.
• Involves various types of redundancy.

Fundamental Steps in Digital Image Processing (DIP)

1. Image Acquisition: Capture the image with a sensor (camera) and digitize it using an analog-to-digital converter if necessary. Sources of illumination include electromagnetic energy spectrum, acoustic, and ultrasonic waves.
2. Image Enhancement: Manipulate the image to make it more suitable for specific applications, such as changing brightness and contrast.
3. Image Restoration: Improve the appearance of an image using objective techniques based on mathematical or probabilistic models of image degradation.
4. Color Image Processing: Use the color of the image to extract features of interest.
5. Wavelets: Foundation for representing images in various degrees of resolution, used for data compression and pyramidal representation.
6. Compression: Techniques for reducing storage or bandwidth required for images.
7. Morphological Processing: Tools for extracting image components useful for representation and description of shape.
8. Image Segmentation: Partition an image into its constituent parts or objects, separating objects from the background.
9. Representation: Decide whether data should be represented as a boundary or a complete region, following segmentation.
10. Object Recognition: Assign a label to an object based on its descriptors.

Components of Image Processing System

• Specialized Image Processing Hardware: Includes a digitizer and hardware for primitive operations, such as an arithmetic logic unit (ALU).
• Computer: Ranges from a PC to a supercomputer.
• Software: Specialized modules for specific tasks, with well-designed packages allowing user-written code.
• Mass Storage: Essential for image processing applications; an uncompressed image of 1024×1024 pixels with 8-bit intensity requires one megabyte of storage.
• Image Displays: Mainly color (preferably flat screen) TV monitors driven by image and graphics display cards.
• Hard Copy Devices: Include laser printers, film cameras, heat-sensitive devices, inkjet units, and digital units like optical and CD-ROM disks.
• Networking: Key consideration is bandwidth due to the large amount of data in image processing.

Applications of Digital Image Processing (DIP)

• Gamma-Ray Imaging
• X-Ray Imaging
• Imaging in the Ultraviolet Band
• Imaging in the Visible and Infrared Band
• Imaging in the Microwave Band
• Imaging in the Radio Band

Sampling and Quantization

To be suitable for digital processing, an image function f(x, y) must be digitized both spatially and in amplitude. The sampling rate determines spatial resolution, while the quantization level determines the number of grey levels.

• Sampling: Digitizing the coordinate values.
• Quantization: Digitizing the amplitude value, transitioning between continuous values and their digital equivalent.

Resolution

Resolution indicates the number of pixels displayed per inch (or centimeter) for an image.

• Spatial Resolution: Smallest discernible detail in an image, or the number of independent pixel values per inch.
• Grey Level Resolution: Predictable change in shades of grey, equal to the number of bits per pixel (L = 2^k).

Convolution and Correlation

• Convolution: Linear filtering where each output pixel is the weighted sum of neighboring input pixels. The matrix of weights is the convolution kernel (or filter), which is a correlation kernel rotated 180 degrees.
• Correlation: Similar to convolution, but the matrix of weights (correlation kernel) is not rotated.

Cohen-Sutherland Line Clipping Algorithm

1. Assign a region code to each endpoint of the line.
2. If both endpoints have a region code of 0000, the line is completely inside and is kept.
3. If step 2 fails, perform a logical AND operation on both region codes:
   • If the result is not 0000, the line is completely outside.
   • Otherwise, the line is partially inside:
     • Choose an endpoint outside the rectangle.
     • Find the intersection point with the rectangular boundary.
     • Replace the endpoint with the intersection point and update the region code.
     • Repeat step 2 until the line is either trivially accepted or rejected.
4. Repeat step 1 for all lines.

Sutherland-Hodgeman Polygon Clipping Algorithm

Polygon clipping involves four stages: Left clip, Right clip, Top clip, and Bottom clip. Each stage has four cases:

1. If the first vertex is outside and the second is inside, add the second vertex and the intersection point to the output list.
2. If both vertices are inside, add only the second vertex to the output list.
3. If the first vertex is inside and the second is outside, add the intersection point to the output list.
4. If both vertices are outside, add nothing to the output list.

Disadvantage: This algorithm may not properly clip concave polygons, creating an extra line through the window boundary.

Cohen-Sutherland vs. Sutherland-Hodgeman

• Cohen-Sutherland: Used for line clipping, testing lines to see which edges are crossed and clipped.
• Sutherland-Hodgeman: A polygon clipping algorithm processing vertices in order, preparing a sequence of adjusted vertices.

Parallel Projection

In parallel projection, the distance from the center of projection to the projection plane is infinite. Coordinate positions are transformed to the view plane along parallel lines.

1. Orthographic Projection: Projecting lines emerge parallel from the object surface and are perpendicular to the projection plane.
   • Elevation: Front, side, and rear orthographic projections.
   • Plan View: Top orthographic projection.
   • Axonometric Projection: Object is rotated to show multiple sides.
     • Isometric Projection: Three coordinate axes appear equally foreshortened, with 120-degree angles between them.
     • Dimetric Projection: Two adjacent sides and angles are equal.
     • Trimetric Projection: All adjacent sides and angles are unequal.
2. Oblique Projection: Projecting rays emerge parallel from the surface and are incident at an angle other than 90° on the plane.
   • Cavalier Projection: Projecting lines are at 45° to the projection plane, with the length of the reading axis larger than in cabinet projection.
   • Cabinet Projection: Similar to cavalier projection, but the length of the reading axis is half, and the incident angle is 63.4°.

Depth Buffer Algorithm (Z-Buffer Algorithm)

The simplest image-space algorithm, the depth buffer algorithm records the depth of the object closest to the observer for each pixel. It also records the intensity to be displayed.

Algorithm:

1. Initialize the Z-buffer and frame buffer: Z-buffer(x, y) = 0 and frame-buffer(x, y) = Ibackground for all positions.
2. During scan conversion, compare depth values to previously stored values to determine visibility. Calculate the z-value for each (x, y) position on the polygon. If z > Z-buffer(x, y), then set Z-buffer(x, y) = z, frame-buffer(x, y) = Isurface(x, y).
3. Stop.

Ibackground is the background intensity, and Isurface is the surface intensity value. Z-values are calculated using the plane equation Ax + By + Cz + D = 0.

For overlapping regions, such as between EH and BC, calculate the depth from the viewpoint to surfaces S1 and S2, and enter the intensity of the nearest surface into the refresh buffer.