Tidbits on Image Processing

I got the following stuff from Nitin. His seminar was Text Detection from Videos. This is some basics on Image processing...


In the broadest sense, image processing includes any form of information processing in which the input is an image. Many image processing techniques derive from the application of signal processing techniques to the domain of images — two-dimensional signals such as photographs or video.
Most of the signal processing concepts that apply to one-dimensional signals — such as resolution, dynamic range, bandwidth, filtering, etc. — extend naturally to images as well. However, image processing brings some new concepts — such as connectivity and rotational invariance — that are meaningful or useful only for two-dimensional signals. Also, certain one-dimensional concepts — such as differential operators, edge detection, and domain modulation — become substantially more complicated when extended to two dimensions.
The name image processing is most appropriate when both inputs and outputs are images. The extraction of arbitrary information from images is the domain of image analysis, which includes pattern recognition when the patterns to be identified are in images. In computer vision one seeks to extract more abstract information, such as the 3D description of a scene from video footage of it. The tools and concepts of image processing are also relevant to image synthesis from more abstract models, which is a major branch of computer graphics.
The enormous size of images, compared to other data streams commonly processed by computers, and the need to process images quickly, has led to whole sub-fields on high speed image processing. A few decades ago, image processing was done largely in the analog domain, chiefly by optical devices. Optical methods are inherently parallel, and for that reason they are still essential to holography and a few other applications. However, as computers keep getting faster, analog techniques are being increasingly replaced by digital image processing techniques — which are more versatile, reliable, accurate, and easier to implement. Specialized hardware is still used for digital image processing: computer architectures based on pipelining have been the most commercially successful, but many different massively parallel architectures were developed as well. These architectures, especially pipelined architectures, are still commonly used in video processing systems. However, these days commercial image processing tasks with a processing speed of a few images per second or less are increasingly done by software libraries running on conventional personal computers.

Edge detection

The goal of edge detection is to mark the points in an image at which the intensity changes sharply. Sharp changes in image properties usually reflect important events and changes in world properties. Edge detection is a research field within image processing and feature extraction.
Edge properties
Edges may be viewpoint dependent - these are edges that may change as the viewpoint changes, and typically reflect the geometry of the scene, objects occluding one another and so on, or may be viewpoint independent - these generally reflect properties of the viewed objects such as markings and surface shape. In two dimensions, and higher, the concept of a projection has to be considered.
A typical edge might be (for instance) the border between a block of red color and a block of yellow; in contrast a line can be a small number of pixels of a different color on an otherwise unchanging background. There will be one edge on each side of the line.Edges play quite important role in all applications of image processing


Detecting an edge

Taking an edge to be a change in intensity taking place over a number of pixels, edge detection algorithms generally calculate a derivative of this intensity change. To simplify matters, we can consider the detection of an edge in 1 dimension. In this instance, our data can be a single line of pixel intensities. For instance an edge can clearly be detected between the 4th and 5th pixels in the following 1-dimensional data:
5 7 6 4 152 148 149
[edit]
Calculating the 1st derivative
Many edge-detection operators are based upon the 1st derivative of the intensity - this gives us the intensity gradient of the original data. Using this information we can search an image for peaks in the intensity gradient.
If I(x) represents the intensity of pixel x, and I′(x) represents the first derivative (intensity gradient) at pixel x, we therefore find that:

For higher performance image processing, the 1st derivative can therefore be calculated (in 1D) by convolving the original data with a mask:
−1 0 1
[edit]
Calculating the 2nd derivative
Some other edge-detection operators are based upon the 2nd derivative of the intensity. This is essentially the rate of change in intensity gradient and is best at detecting lines :- as noted above, a line is a double edge, hence we will see an intensity gradient on one side of the line, followed immediately by the opposite gradient on the opposite site. Therefore we can expect to see a very high change in intensity gradient where a line is present in the image. To find lines, we can search the results for zero-crossings of the change in gradient.
If I(x) represents the intensity at point x, and I′′(x) is the second derivative at point x:

Again most algorithms use a convolution mask to quickly process the image data:
+1 −2 +1

Thresholding

Once we have calculated our derivative, the next stage is to apply a threshold, to determine where the results suggest an edge is present. The lower the threshold, the more lines will be detected, and the results become increasingly susceptible to noise, and also to picking out irrelevant features from the image. Conversely a high threshold may miss subtle lines, or sections of lines.
A commonly used compromise is thresholding with hysteresis. This method uses multiple thresholds to find edges. We begin by using the upper threshold to find the start of a line. Once we have a start point, we trace the edge's path through the image pixel by pixel, marking an edge whenever we are above the lower threshold. We stop marking our edge only when the value falls below our lower threshold. This approach makes the assumption that edges are likely to be in continuous lines, and allows us to follow a faint section of an edge we have previously seen, without meaning that every noisy pixel in the image is marked down as an edge.
[edit]
Edge detection operators
• 1st order: Roberts Cross, Prewitt, Sobel, Canny, Spacek
• 2nd Order: Laplacian, Marr-Hildreth
Currently, the Canny operator is most commonly used, followed by Marr-Hildreth. Very many operators have been published but so far none have any significant advantage over the Canny operator in general situations. Work on multi-scale techniques is still very much in the labs.
Retrieved from "http://en.wikipedia.org/wiki/Edge_detection"

Sobel
From Wikipedia, the free encyclopedia.

In image processing, the Sobel operator is a simple edge detection algorithm using the 1st derivative of the intensity information.
The operator uses two 3x3 kernels convolved with the original image to produce a map of intensity gradient. The areas of highest gradient are where the intensity of the image changes rapidly over a few pixels, and are thus likely to represent edges.
Two convolution kernels are needed to detect the first-order derivative of both horizontal and vertical changes in a 2-dimensional image. If we define as the source image, we can compute:

Which can then be combined to give the overall magnitudes using:

Using this information, we can also calculate the gradient's direction:

Where Θ will be 0 for a vertical edge, and will increase for edges anti-clockwise of this.
In mathematics and in particular, functional analysis, convolution is a mathematical operator which takes two functions f and g and produces a third function that in a sense represents the amount of overlap between f and a reversed and translated version of g. A convolution is a kind of very general moving average, as one can see by taking one of the functions to be an indicator function of an interval.


Grayscale
From Wikipedia, the free encyclopedia.

In computing, a grayscale or greyscale digital image is an image in which the value of each pixel is a single sample. Displayed images of this sort are typically composed of shades of gray, varying from black at the weakest intensity to white at the strongest, though in principle the samples could be displayed as shades of any color, or even coded with various colors for different intensities. Grayscale images are distinct from black-and-white images, which in the context of computer imaging are images with only two colors, black and white; grayscale images have many shades of gray in between. In most contexts other than digital imaging, however, the term "black and white" is used in place of "grayscale"; for example, photography in shades of gray is typically called "black-and-white photography". The term monochromatic in some digital imaging contexts is synonymous with grayscale, and in some contexts synonymous with black-and-white.
Grayscale images are often the result of measuring the intensity of light at each pixel in a single band of the electromagnetic spectrum (e.g. visible light).
Grayscale images intended for visual display are typically stored with and 8 bits per sample, which allows 256 intensities (i.e., shades of gray) to be recorded, typically on a non-linear scale. The accuracy provided by this format is barely sufficient to avoid visible banding artifacts, but very convenient for programming. Technical uses (e.g. in medical imaging or remote sensing applications) often require more levels, to make full use of the sensor accuracy (typically 10 or 12 bits per sample) and to guard against roundoff errors in computations. Sixteen bits per sample (65536 levels) appears to be a popular choice for such uses.
In the reality television show Big Brother the photographs of evicted contestants on the "Memory Wall" (Seasons 1-5) and "Memory Board" (Season 6) are shown in Grayscale, while contestants who are still in the game are shown in full color.



Segmentation (image processing)
From Wikipedia, the free encyclopedia.

In image analysis, segmentation is the partition of a digital image into multiple regions (sets of pixels), according to some criterion.
The goal of segmentation is typically to locate certain objects of interest which may be depicted in the image. Segmentation could therefore be seen as a computer vision problem. Unfortunately, many important segmentation algorithms are too simple to solve this problem accurately: they compensate for this limitation with their predictability, generality, and efficiency.
A simple example of segmentation is thresholding a grayscale image with a fixed threshold t: each pixel p is assigned to one of two classes, P0 or P1, depending on whether I(p) < t or I(p) ≥ t.
Some other segmentation algorithms are based on segmenting images into regions of similar texture according to wavelet or Fourier transforms.
Segmentation criteria can be arbitrarily complex, and take into account global as well as local criteria. A common requirement is that each region must be connected in some sense.

An example of a global segmentation criterion is the famous Mumford-Shah functional. This functional measures the degree of match between an image and its segmentation. A segmentation consists of a set of non-overlapping connected regions (the union of which is the image), each of which is smooth and each of which has a piecewise smooth boundary. The functional penalizes deviations from the original image, deviations from smoothness within in each region and the total length of the boundaries of all the regions. Mathematically,
Thresholding is the simplest method of image segmentation. Individual pixels in a grayscale image are marked as 'object' pixels if their value is greater than some threshold value (assuming an object to be brighter than the background) and as 'background' pixels otherwise. Typically, an object pixel is given a value of '1' while a background pixel is given a value of '0'. The key parameter here is obviously the choice of the threshold. Several different methods for choosing a threshold exist. The simplest method would be to choose the mean or median value, the rationale being that if the object pixels are brighter than the background, they should also be brighter than the average. In a noiseless image with uniform background and object values, the mean or median will work beautifully as the threshold, however generally speaking, this will not be the case. A more sophisticated approach might be to create a histogram of the image pixel intensities and use the valley point as the threshold. The histogram approach assumes that there is some average value for the background and object pixels, but that the actual pixel values have some variation around these average values. However, computationally this is not as simple as we'd like, and many image histograms do not have clearly defined valley points. Ideally we're looking for a method for choosing the threshold which is simple, does not require too much prior knowledge of the photo, and works well for noisy images.

Special Yo to Nitin for collecting these stuff!