Преобразование растровых изображений в векторные

Введение

Преобразование растровой графики в векторную

В компьютерной графике, обводка изображений, преобразование растра в вектор или векторизация растра — это процесс преобразования растровой графики в векторную графику.

Предыстория

Изображение не имеет структуры: это просто совокупность знаков на бумаге, зерен на пленке или пикселей в растровом изображении. Хотя такое изображение полезно, оно имеет определенные ограничения. При достаточном увеличении изображения проявляются его артефакты. Полутоновые точки, зерна пленки и пиксели становятся заметными. Изображения с четкими краями становятся размытыми или зубчатыми. Например, пикселизация. В идеале, векторное изображение лишено этой проблемы. Края и залитые области представлены в виде математических кривых или градиентов, и их можно масштабировать произвольно (хотя, конечно, конечное изображение также должно быть растрировано для отображения, и его качество зависит от качества алгоритма растрирования для заданных входных данных). Задача векторизации — преобразовать двухмерное изображение в двухмерное векторное представление. Это не анализ изображения с целью распознавания или извлечения трехмерной модели, которая может быть на нем изображена; то есть, это не система компьютерного зрения. Для большинства приложений векторизация также не включает оптическое распознавание символов; символы рассматриваются как линии, кривые или залитые объекты, без придания им какого-либо значения. При векторизации сохраняется форма символа, поэтому художественные элементы остаются неизменными. Векторизация — это обратная операция по отношению к растрированию, подобно интеграции по отношению к дифференцированию. И, как и в случае с этими двумя операциями, если растрирование относительно простое и алгоритмичное, то векторизация предполагает восстановление утерянной информации и, следовательно, требует использования эвристических методов. Для векторизации подходят синтетические изображения, такие как карты, мультфильмы, логотипы, клипарты и технические чертежи. Эти изображения могли быть изначально созданы в векторном формате, поскольку они основаны на геометрических фигурах или нарисованы простыми кривыми. Фотографии с непрерывными тонами (например, портреты) не являются хорошими кандидатами для векторизации. Входными данными для векторизации является изображение, которое может быть представлено в различных форматах, таких как фотография, рисунок на бумаге или один из нескольких растровых форматов файлов. Программы, выполняющие преобразование из растрового в векторный формат, могут принимать растровые форматы, такие как TIFF, BMP и PNG. Выходным результатом является векторный формат файла. Распространенные векторные форматы включают SVG, DXF, EPS, EMF и AI. Векторизация может использоваться для обновления изображений или восстановления утраченных работ. Персональные компьютеры часто поставляются с простой программой рисования, которая создает растровый выходной файл. Эти программы позволяют пользователям создавать простые иллюстрации, добавляя текст, рисуя контуры и заливая их определенным цветом. В результирующем растровом изображении сохраняются только результаты этих операций (пиксели); операции рисования и заливки отбрасываются. Векторизация может быть использована для восстановления части утерянной информации. Векторизация также используется для восстановления информации, которая изначально была в векторном формате, но была утеряна или стала недоступной. Например, компания могла заказать логотип в графическом дизайне. Хотя графическая студия использовала векторный формат, клиентская компания могла не получить копию этого формата. В этом случае компания может получить векторный формат, отсканировав и векторизовав бумажную копию логотипа.

An image does not have any structure: it is just a collection of marks on paper, grains in film, or pixels in a bitmap. While such an image is useful, it has some limits. If the image is magnified enough, its artifacts appear. The halftone dots, film grains, and pixels become apparent. Images of sharp edges become fuzzy or jagged. See, for example, pixelation. Ideally, a vector image does not have the same problem. Edges and filled areas are represented as mathematical curves or gradients, and they can be magnified arbitrarily (though of course the final image must also be rasterized in to be rendered, and its quality depends on the quality of the rasterization algorithm for the given inputs). The task in vectorization is to convert a two dimensional image into a two dimensional vector representation of the image. It is not examining the image and attempting to recognize or extract a three dimensional model that may be depicted; i. e. it is not a vision system. For most applications, vectorization also does not involve optical character recognition; characters are treated as lines, curves, or filled objects without attaching any significance to them. In vectorization, the shape of the character is preserved, so artistic embellishments remain. Vectorization is the inverse operation corresponding to rasterization, as integration is to differentiation. And, just as with these other two operations, while rasterization is fairly straightforward and algorithmic, vectorization involves the reconstruction of lost information and therefore requires heuristic methods. Synthetic images such as maps, cartoons, logos, clip art, and technical drawings are suitable for vectorization. Those images could have been originally made as vector images because they are based on geometric shapes or drawn with simple curves. Continuous tone photographs (such as live portraits) are not good candidates for vectorization. The input to vectorization is an image, but an image may come in many forms such as a photograph, a drawing on paper, or one of several raster file formats. Programs that do raster to vector conversion may accept bitmap formats such as TIFF, BMP and PNG. The output is a vector file format. Common vector formats are SVG, DXF, EPS, EMF and AI. Vectorization can be used to update images or recover work. Personal computers often come with a simple paint program that produces a bitmap output file. These programs allow users to make simple illustrations by adding text, drawing outlines, and filling outlines with a specific color. Only the results of these operations (the pixels) are saved in the resulting bitmap; the drawing and filling operations are discarded. Vectorization can be used to recapture some of the information that was lost. Vectorization is also used to recover information that was originally in a vector format but has been lost or has become unavailable. A company may have commissioned a logo from a graphic arts firm. Although the graphics firm used a vector format, the client company may not have received a copy of that format. The company may then acquire a vector format by scanning and vectorizing a paper copy of the logo.

Процесс

Векторизация начинается с изображения.

Руководство

Изображение можно векторизовать вручную. Человек может изучить изображение, выполнить необходимые измерения, а затем создать выходной файл вручную. Так было и в случае с векторизацией технической иллюстрации о нейтрино. Иллюстрация содержит несколько геометрических фигур и много текста; преобразовать фигуры оказалось относительно просто, а векторный формат SVG позволяет легко вводить текст (включая индексы и степени). В исходном изображении не было кривых (за исключением текста), поэтому преобразование было прямолинейным. Кривые усложняют преобразование. Ручную векторизацию сложных форм можно упростить с помощью функции трассировки, встроенной в некоторые программы для редактирования векторной графики. Если изображение еще не представлено в машиночитаемом формате, его необходимо отсканировать в подходящий формат файла. После получения машиночитаемой растровой графики изображение можно импортировать в программу для редактирования графики (например, Adobe Illustrator, CorelDRAW или Inkscape). Затем человек может вручную обвести элементы изображения, используя инструменты редактирования программы. Кривые в исходном изображении можно аппроксимировать линиями, дугами и кривыми Безье. В иллюстративной программе можно регулировать опорные точки сплайнов для точного соответствия. Ручная векторизация возможна, но может быть утомительной. Хотя программы для рисования графики существуют уже давно, художникам может быть неудобно использовать инструменты свободного рисования, даже при использовании графического планшета. Вместо использования программы Пеппер рекомендует сделать первоначальный эскиз на бумаге. Вместо сканирования эскиза и обводки его в компьютере, Пеппер утверждает: "Те, кто хорошо владеет графическим планшетом и стилусом, могут внести следующие изменения непосредственно в CorelDRAW, используя сканирование эскиза в качестве подложки и рисуя поверх него. Я предпочитаю использовать перо и тушь, и световой стол"; большая часть финального изображения была обведена вручную тушью. Позже изображение с линиями было отсканировано с разрешением 600 dpi, очищено в растровом редакторе, а затем автоматически обведено с помощью программы. После того, как черно-белое изображение оказалось в графической программе, были добавлены другие элементы, и фигура была раскрашена. Аналогично, Плох воссоздал дизайн на основе цифровой фотографии. JPEG был импортирован, и некоторые "простые формы" были обведены вручную и раскрашены в программе для рисования графики; более сложные формы обрабатывались иначе. Плох использовал растровый редактор для удаления фона и обрезки более сложных компонентов изображения. Затем он распечатал изображение и обвел его вручную на кальке, чтобы получить четкий черно-белый контур. Этот рисунок был отсканирован, а затем векторизован с помощью программы.

The image can be vectorized manually. A person could look at the image, make some measurements, and then write the output file by hand. That was the case for the vectorization of a technical illustration about neutrinos. The illustration has a few geometric shapes and a lot of text; it was relatively easy to convert the shapes, and the SVG vector format allows the text (even subscripts and superscripts) to be entered easily. The original image did not have any curves (except for the text), so the conversion is straightforward. Curves make the conversion more complicated. Manual vectorization of complicated shapes can be facilitated by the tracing function built into some vector graphics editing programs. If the image is not yet in machine readable form, then it has to be scanned into a usable file format. Once there is a machine readable bitmap, the image can be imported into a graphics editing program (such as Adobe Illustrator, CorelDRAW, or Inkscape). Then a person can manually trace the elements of the image using the program's editing features. Curves in the original image can be approximated with lines, arcs, and Bézier curves. An illustration program allows spline knots to be adjusted for a close fit. Manual vectorization is possible, but it can be tedious. Although graphics drawing programs have been around for a long time, artists may find the freehand drawing facilities awkward even when a drawing tablet is used. Instead of using a program, Pepper recommends making an initial sketch on paper. Instead of scanning the sketch and tracing it freehand in the computer, Pepper states: "Those proficient with a graphic tablet and stylus could make the following changes directly in CorelDRAW by using a scan of the sketch as an underlay and drawing over it. I prefer to use pen and ink, and a light table"; most of the final image was traced by hand in ink. Later the line drawing image was scanned at 600 dpi, cleaned up in a paint program, and then automatically traced with a program. Once the black and white image was in the graphics program, some other elements were added and the figure was colored. Similarly, Ploch recreated a design from a digital photograph. The JPEG was imported and some "basic shapes" were traced by hand and colored in the graphics drawing program; more complex shapes were handled differently. Ploch used a bitmap editor to remove the background and crop the more complex image components. He then printed the image and traced it by hand onto tracing paper to get a clean black and white line drawing. That drawing was scanned and then vectorized with a program.

Автоматический

Некоторые программы автоматизируют процесс векторизации. Примерами таких программ являются Adobe Streamline (снята с производства), Corel's PowerTRACE и Potrace. Некоторые из этих программ имеют интерфейс командной строки, а другие – интерактивные, позволяющие пользователю настраивать параметры преобразования и просматривать результат. Adobe Streamline – это не только интерактивная программа, но и позволяет пользователю вручную редактировать исходное растровое изображение и выходные кривые. Доступ к Corel's PowerTRACE осуществляется через CorelDRAW; CorelDRAW можно использовать для изменения исходного растрового изображения и редактирования выходных кривых. В Adobe Illustrator есть функция для трассировки отдельных кривых. Автоматизированные программы могут давать неоднозначные результаты. Программа (PowerTRACE) была использована для преобразования PNG-карты в SVG. Программа хорошо справилась с границами карты (самой трудоемкой задачей при трассировке), а настройки исключили весь текст (мелкие объекты). Текст был добавлен вручную. Другие преобразования могут пройти не так успешно. Результаты зависят от качества сканирования, разумных настроек и эффективных алгоритмов. Сканированные изображения часто содержат много шума. Растровому изображению может потребоваться значительная обработка для очистки. Удалите случайные метки и заполните линии и области. Совет от Corel: Положите изображение на световой стол, накройте его калькой и вручную обведите нужные контуры. Затем отсканируйте кальку и используйте автоматическую программу для преобразования растра в вектор на этом скане.

Варианты

Существует множество различных стилей и возможностей изображения, и ни один метод векторизации не обеспечивает хороших результатов для всех изображений. Следовательно, программы векторизации имеют множество опций, влияющих на результат. Один из вопросов заключается в преобладающих формах. Если изображение представляет собой бланк для заполнения, то, скорее всего, оно будет состоять только из вертикальных и горизонтальных линий постоянной ширины. Программа векторизации должна это учитывать. С другой стороны, чертеж CAD может содержать линии под любым углом, изогнутые линии и линии разной толщины (толстые для объектов и тонкие для размерных линий). Вместо (или в дополнение к) кривым, изображение может содержать контуры, заполненные одним и тем же цветом. Adobe Streamline позволяет пользователям выбирать комбинацию распознавания линий (горизонтальных и вертикальных линий), распознавания центральной линии или распознавания контуров. Streamline также позволяет отбрасывать небольшие контуры, поскольку они считаются шумом. Пользователь может установить уровень шума в диапазоне от 0 до 1000; контур, содержащий меньше пикселей, чем указанное значение, отбрасывается. Другой вопрос – количество цветов в изображении. Даже изображения, изначально созданные как черно-белые рисунки, могут содержать множество оттенков серого. Некоторые алгоритмы рисования линий используют сглаживание (антиалиасинг); пиксель, полностью покрытый линией, будет черным, а пиксель, покрытый частично, – серым. Если исходное изображение напечатано на бумаге и отсканировано, результат будет аналогичным: крайние пиксели будут серыми. Иногда изображения сжимаются (например, JPEG), и сжатие приводит к появлению оттенков серого. Многие программы векторизации группируют пиксели одного цвета в линии, кривые или контуры. Если каждый возможный цвет группируется в отдельный объект, количество объектов может быть огромным. Вместо этого пользователю предлагается выбрать конечное число цветов (обычно менее 256), изображение преобразуется для использования только этого количества цветов (этот шаг называется квантованием цвета), а затем выполняется векторизация уменьшенного изображения. Для изображений с непрерывными тонами, таких как фотографии, квантование цвета приводит к постеризации. Градиентные заливки также будут постеризованы. Уменьшение количества цветов в изображении часто облегчается с помощью гистограммы. Наиболее распространенные цвета могут быть выбраны в качестве репрезентативных, а остальные цвета отображаются на ближайший репрезентативный цвет. Если количество цветов установлено равным двум, пользователю может быть предложено настроить порог и контрастность. Настройка контрастности ищет значительные изменения цвета пикселя, а не конкретный цвет; следовательно, она может игнорировать плавные цветовые переходы в градиентной заливке. После извлечения контура пользователь может вручную восстановить градиентную заливку. Программа векторизации стремится объединить область одного цвета в один объект. Это можно сделать, точно следуя границам пикселей, но в результате получится граница, состоящая из множества коротких ортогональных линий. Полученное преобразование также будет иметь те же проблемы с пикселизацией, что и растровое изображение при увеличении. Вместо этого программа векторизации должна аппроксимировать границу области линиями и кривыми, которые тесно следуют границам пикселей, но не совпадают с ними точно. Параметр допуска определяет, насколько точно программа должна следовать границам пикселей. Конечным результатом работы многих программ векторизации являются кривые, состоящие из кубических кривых Безье. Граница области аппроксимируется несколькими сегментами кривой. Чтобы кривая была гладкой, соединения двух кривых ограничиваются таким образом, чтобы их касательные совпадали. Одна из проблем заключается в определении того, где кривая изгибается настолько резко, что не должна быть гладкой. Затем гладкие участки кривой аппроксимируются процедурой подгонки кривой Безье. Может использоваться последовательное деление. Эта процедура пытается подогнать кривую к одной кубической кривой; если подгонка удовлетворительна, процедура останавливается. В противном случае она выбирает выгодную точку вдоль кривой и разбивает ее на две части. Затем она подгоняет части, сохраняя касательную в точке соединения. Если подгонка все еще неудовлетворительна, кривая разбивается на большее количество частей. Некоторые векторизаторы являются автономными программами, но многие имеют интерактивные интерфейсы, позволяющие пользователю настраивать параметры программы и быстро просматривать результат. PowerTRACE, например, может отображать исходное изображение и предварительный просмотр преобразованного изображения, чтобы пользователь мог их сравнить; программа также предоставляет информацию, такую как количество кривых.

There are many different image styles and possibilities, and no single vectorization method works well on all images. Consequently, vectorization programs have many options that influence the result. One issue is what the predominant shapes are. If the image is of a fill in form, then it will probably have just vertical and horizontal lines of a constant width. The program's vectorization should take that into account. On the other hand, a CAD drawing may have lines at any angle, there may be curved lines, and there may be several line weights (thick for objects and thin for dimension lines). Instead of (or in addition to) curves, the image may contain outlines filled with the same color. Adobe Streamline allows users to select a combination of line recognition (horizontal and vertical lines), centerline recognition, or outline recognition. Streamline also allows small outline shapes to be thrown out; the notion is such small shapes are noise. The user may set the noise level between 0 and 1000; an outline that has fewer pixels than that setting is discarded. Another issue is the number of colors in the image. Even images that were created as black on white drawings may end up with many shades of gray. Some line drawing routines employ anti aliasing; a pixel completely covered by the line will be black, but a pixel that is only partially covered will be gray. If the original image is on paper and is scanned, there is a similar result: edge pixels will be gray. Sometimes images are compressed (e. g., JPEG images), and the compression will introduce gray levels. Many of the vectorization programs will group same color pixels into lines, curves, or outlined shapes. If each possible color is grouped into its object, there can be an enormous number of objects. Instead, the user is asked to select a finite number of colors (usually less than 256), the image is reduced to using that many colors (this step is color quantization), and then the vectorization is done on the reduced image. For continuous tone images such as photographs, the result of color quantization is posterization. Gradient fills will also be posterized. Reducing the number of colors in an image is often aided by a histogram. The most common colors may be selected as the representatives, and other colors are mapped to their closest representative. When the number of colors is set to two, the user may be asked to make threshold and contrast settings. A contrast setting looks for significant changes in pixel color rather than a particular color; consequently, it may ignore the gradual color variations in a gradient fill. Once the outline has been extracted, the user can manually reintroduce the gradient fill. The vectorization program will want to group a region of the same color into a single object. It can do that by making the region boundary exactly follow the pixel boundaries, but the result will be a boundary of often short orthogonal lines. The resulting conversion will also have the same pixelation problems that a bitmap has when it is magnified. Instead, the vectorization program needs to approximate the region boundary with lines and curves that closely follow the pixel boundaries but are not exactly the pixel boundaries. A tolerance parameter tells the program how closely it should follow the pixel boundaries. The end result of many vectorization programs are curves consisting of cubic Bézier curves. A region boundary is approximated with several curve segments. To keep a curve smooth, the joints of two curves are constrained so the tangents match. One problem is determining where a curve bends so sharply that it should not be smooth. The smooth portions of a curve are then approximated with a Bézier curve fitting procedure. Successive division may be used. Such a fitting procedure tries to fit the curve with a single cubic curve; if the fit is acceptable, then the procedure stops. Otherwise, it selects some advantageous point along the curve and breaks the curve into two parts. It then fits the parts while keeping the joint tangent. If the fit is still unacceptable, then it breaks the curve into more parts. Some vectorizers are standalone programs, but many have interactive interfaces that allow a user to adjust the program parameters and quickly see the result. PowerTRACE, for example, can display the original image and preview the converted image so the user may compare them; the program also reports information such as the number of curves.

Пример

Справа представлена иллюстрация, демонстрирующая работу радулы у моллюсков. Верхняя часть изображения в основном представляет собой схематичное изображение контуров, заполненное линией шириной в один пункт, однако в нижней части раковины и пищи присутствует градиентная сетчатая заливка. Также в верхней левой части раковины имеются художественные мазки кистью. Нижняя часть иллюстрации содержит четыре толщины линий и небольшие символы; цветовое заполнение простое, за исключением градиента на зубчатых линиях. Изображение размером 531×879 пикселей было векторизовано; использовано 50 цветов. Большинство (если не все) линий были утрачены; они преобразовались в черные области, и их фактическая толщина варьировалась. Черный контур вокруг синей пищи в верхней части исчез. Градиентные заливки и мазки кистью были потеряны из-за квантования цвета/постеризации; некоторые мазки исчезли. Некоторые буквы сохранились после векторизации с искажениями, но большинство букв было удалено. Потеря букв не критична, поскольку после преобразования редактирование предполагает удаление аннотаций и замену их текстом, а не кривыми. Тонкие линии, пересекающиеся под малым углом, образовали залитые области, а пересекающиеся контуры залитых областей стали неразличимыми; см. нижний правый угол. Векторизация также имеет некоторые особенности. Многие черные контуры соприкасаются, образуя большие, сложные объекты, а не просто контуры для отдельных областей. Вместо простого фона, прямоугольная белая область разделяет два контурных прямоугольника. Объекты, обозначенные как op, rp и rr, не являются простыми слоями; желаемый результат – наложение rr на rp, которое, в свою очередь, наложено на op.

Домены использования

В системах автоматизированного проектирования (CAD) чертежи (включая планы и схемы) сканируются, векторизуются и сохраняются в виде файлов САПР в процессе, называемом конвертацией из бумажного формата в САПР или конвертацией чертежей. В географических информационных системах (ГИС) спутниковые или аэрофотоснимки векторизуются для создания карт. В графическом дизайне и фотографии графические изображения могут быть векторизованы для более удобного использования и масштабирования. Векторизация часто является первым этапом в решениях OCR для распознавания рукописного текста или подписей. Векторизация наиболее эффективна при работе с одноцветными изображениями без градиентов, например, с подписями.

Непрерывные тоновые изображения

Векторизация обычно не подходит для изображений с плавными тонами, таких как портреты. Результат часто оказывается неудовлетворительным. Например, к JPEG-изображению размером 25 кБ было применено множество различных алгоритмов трассировки изображения. Полученные векторные изображения оказываются как минимум в десять раз больше по размеру и могут демонстрировать выраженный эффект постеризации при использовании небольшого количества цветов.