• Introduction
• The goals and objectives that must be addressed
• Actuality of the subject
• Scientific novelty
• Expected results
• The algorithm of content-dependent scaling
• Conclusions

The application of computer technology in modern life has become widespread. A great number of industries are using computing machines to accelerate the solution of problems. With the advent of powerful graphical workstations, as well as computers, can solve not only mathematical problems, but also to visualize complex processes on the screen, begins a new era in the computer industry.

Computer graphics is used in almost all scientific and engineering disciplines for the clarity of perception and information transfer.

One of the goals of computer graphics is scaling - Change the image size. Then, depending on the type of graphics (raster, vector), scale is produced by different algorithms. If the graphic is vector, the scaling occurs without loss of image quality, when raster, the scaling is a loss of image quality, especially when resized without preserving the aspect ratio.

It is therefore very important to develop improved methods of scaling, in particular content-dependent, based on a preliminary analysis of images.

The aim is to study the existing methods of image scaling, to modernize and optimize these methods, to improve algorithm based on a preliminary analysis of images.

The following problems should be solved during the study:

1. Identification of the major shortcomings of existing algorithms, explore opportunities to address them.
2. Development of the algorithm analyzes the image by its contents and identifying the most and least significant parts of the image.
3. Development of the algorithm, scaling the image on the basis of the analysed data.
4. Software implementation of the algorithm, which provides content-dependent scaling.
5. Analysis and comparison of results obtained using the developed algorithms and existing algorithms.

The goal of scaling - Change the image size - is widely used in various fields. This problem is particularly relevant for the transfer of images to mobile devices, where it can not be displayed in full scale, for placing images on the sites. Increase image is often used for a more detailed review of the fragment in image processing, etc.

The main task of scaling - to save a sufficient image quality. The search for effective ways to implement this algorithm is the subject of research by many scientists around the world. These include:

1. Jeff Etvord (former employee of Vertigo Software, Point Richmond, California). http://www.codinghorror.com/blog/2007/07/better-image-resizing.html
2. Xai Avidan (Mitsubishi Electric Research Labs, North America). http://portal.acm.org/citation.cfm?id=1276377.1276390
3. Ariel Shamir (University of Texas at Austin). http://portal.acm.org/citation.cfm?id=1457515.1409064

Thus, the thesis is quite topical today.

The most common at present algorithms for image scaling does not provide sufficiently high quality when resized. In connection with this planned improvement of the content-dependent scaling algorithm. Expected to improve the temporal and visual performance values of algorithm.

After finishing work on the development of the software system is planned to obtain a workable program project designed for content-dependent image scaling.

Also planned for the complex analysis and comparison of the practical aspects of implementation of various scaling algorithms.

Consider the algorithm of content-dependent scaling Seam Carving - is image resizing algorithm that takes into account the contents of the image (as the authors call - Content-Aware Image Resizing Algorithm). It was first proposed in 2007.^[6]

The method takes into account the contents of images: firstly calculates the importance of different parts of the image, then change in the amount of only those parts which, according to the algorithm are not so important. The main problem of the algorithm: how to determine how important are the parts of the image, how to locate and compress less important parts of the image, etc.

The main steps of the algorithm for horizontal scaling (vertical - the same way):

1. Finding the energy of each point. At this stage you must determine which parts of the image are more important, and what - less important, on the basis of these data the image size will change.
2. Search this vertical chain pixels to the total energy of the pixels that fall within this chain was minimal. The chain of pixels - this is a set of pixels that each row is selected exactly one pixel and neighboring pixels in it are connected by the parties or angles. In finding such a chain may remove it from the image, minimally affecting the content image.
3. After finding the chain with the minimum energy necessary to remove it, if you are reducing the image, or to stretch, if you are an increase.^[7]

Consider the algorithm in more detail.

Step 1. To determine the importance of image pixels their energy must be calculated: the more energy - the more important pixel. There are many ways to calculate the energy. One of the most simple functions gives the best results:

The energy of a pixel is a color change of adjacent pixels, as compared with the pixel. That is, the greater the difference in color between this pixel and its neighbors - the more its energy.

Step 2. After determining the values of the energy necessary to select those pixels whose value is minimal. First we need to define "proper" chain of pixels - a set of points such that every line picture is exactly 1 pixel, and pixels in adjacent lines of "connected" or the sides or angles (Figure 1).

a)                          b)

Figure 1 – An example of "correct" (a) and "incorrect" (b) chains

You should choose a chain in which the sum of the energies of pixels that are in it is minimal. For the retrieval the dynamic programming method should be applied. First, it creates a new array, which is equal to the size of the array with the energies of pixels. In this array for each pixel is recorded amount of the minimum elements of a chain of pixels, which begins at the upper edge of the image and ends at the current pixel.

First you define a pixel of the bottom line of the image belongs to this chain: the desired element will be the smallest value in the array of sums among the elements of the bottom line. Chains, which we are interested comes to an end pixel of the last line. Accordingly, the minimum figure for the whole chain will be selected as the minimum of all minimal chains that end in pixels from the bottom line.

After determining the pixel, which ends the minimum chain, possibly finding a pixel from the penultimate line. As has already been written, from the lower pixel, we can go in only 3 neighboring pixels on the line above: left-top, top, or right-top. Among these pixels we choose a pixel with a minimum value in an array of sums, and go to him. Continue until we reach the top line.

After all these operations will provide a set of pixels that can be changed with minimal losses for the image.

Step 3. Our task - to change the image size. Zoom in and out a little differs, so the first will be considered by a decrease and then increase.

If you want to reduce the width of the image by 1 pixel, then all is simple: there is a vertical chain, as described above, and need simply remove it.

If you need to decrease on a larger value, perform removing the chain as many times as necessary (look for a new chain each time).

An example of reduction is shown in figure 3 and 4.^[7]

Figure 2 – Original image




Figure 3 - Horizontally reduced image




Figure 4 – Vertically reduced image

When increase an image can not simply choose a chain and "stretch" them. Must take as many chains as need to complete the picture to the desired width (as for a normal stretch), but should gradually increase the image: so that at each stage reach the largest possible "not important" parts of the image, and as little as possible "significant". One way to partition into stages such that at each stage of the image is not increased by more than 50%. Example of increase is shown in figures 5 and 6.^[6]

Figure 5 – Original image




Figure 6 – Horizontally increased image

Figure 7 — The process of the image reducing (horse singled out as an immutable object).
Animations created in the program AdobePhotoshop CS2, volume 261 Kb, the size 358x269, 6 frames, 5 cycles of repetition, the delay between shots 1s.

An analysis of existing scaling algorithms identified their main weaknesses. To optimize the scaling method was proposed content-dependent scaling. In the future we plan to improve the algorithm and implement it.

1. Thyssen A. Resize and Scaling. // Examples of ImageMagick Usage (Version 6), 2009. — http://www.imagemagick.org/Usage/resize/
2. Билинейная интерполяция. // Статья википедии — свободной Интернет-энциклопедии — http://ru.wikipedia.org/wiki/Билинейная_интерполяция
3. Бикубическая интерполяция. // Статья википедии — свободной Интернет-энциклопедии — http://ru.wikipedia.org/wiki/Бикубическая_интерполяция
4. Алгоритмы масштабирования пиксельной графики // Статья википедии — свободной Интернет-энциклопедии — http://ru.wikipedia.org/wiki/Алгоритмы_масштабирования_...
5. Ronald E. Crochiere, Lawrence R. Rabiner. Multirate digital signal processing. — Prentice-Hall, 1983. — http://www.flipkart.com/multirate-digital-signal-processing-lawrence-book-0136051626
6. Liquid Rescale. // Content-aware resizing for the GIMP, 2009. — http://liquidrescale.wikidot.com/en:examples
7. Михаил М. Liquid Resize своими руками. — Habradigest, №7, январь 2009. — http://habradigest.ru/hd/habradigest_07.pdf
8. Конник М. Новый метод масштабирования растровых изображений с учётом их содержимого Liquid Rescale. — Записки дебианщика, 2007. — http://mydebianblog.blogspot.com/2007/09/blog-post.html
9. Шеховцов С.О. Контентно-зависимое масштабирование изображений с использованием алгоритма Seam Carving // Искусственный интеллект.— Донецк: ІПШІ МОН і НАН України “Наука і освіта”, 2010.
10. Шеховцов С.О. Анализ недостатков алгоритмов масштабирования. Контентно-зависимое масштабирование // ІУС та КМ-2010 — Матеріали І всеукраїнської науково-технічної конференції студентів, аспірантів та молодих вчених — Донецьк: ДонНТУ, 19-21 травня 2010. — 634с.

The abstract of the Master's work is not complete yet . The final completion in 1st December 2010. Full text of the work and materials on the topic can be obtained from the author or his head after that date.