Feature analysis using line sweep thinning algorithm

We propose a new thinning algorithm based on line sweep operation. Assuming that the contour of the figure to be thinned has been approximated by polygons, the “events” are then the vertices of the polygons, and the line sweep algorithm searches for pairs of edges lying within each slab. The pairing of edges is useful for detecting both regular and intersection regions. The regular regions can be found at the sites where pairings between edges exist. Intersection regions are those where such relations would cease to exist. A salient feature of our approach is that it finds simultaneously the set of regular regions that attach to the same intersection region. Such a set is thus called an intersection set. The output of our algorithm consists of skeletons as well as intersection sets, both can be used as features for subsequent character recognition. Moreover, the line sweep thinning algorithm is efficient in computation as compared with a pixel-based thinning algorithm which outputs skeletons only     

The contour problem for rectilinear polygons

The union of a set of p, not necessarily disjoint, rectilinear polygons in the plane determines a set of disjoint rectilinear polygons. We present an O(n log n + e) time and O(n) space algorithm to compute the edges of the disjoint polygons, that is, the contour, where n is the total number of vertices in the original polygons and e the total number in the resulting set. This time-and space-optimal algorithm uses the scan-line paradigm as in two previous approaches to this problem for rectangles, but requires a simpler data structure. Moreover, if the given rectilinear polygons are rectilinear convex, the space requirement is reduced to O(p).     

Search for the Intersection Polygon of any Two Polygons: Application to the Garment Industry

One of the biggest problems usually encountered by the clothes manufacturer consists of placing various pattern parts on a rectangular area in such a way that the waste of material between the pieces is minimized.
To bring some automated help in this field, computer programs need first to handle the complicated contours of the pieces. One needs not only to check the overlap of two contiguous patterns, but also to compute their precise area of intersection, allowing in this way the use of some kind of combinatorial optimization.
In a wider context, it is possible to design a general purpose algorithm, able to build the complete structure representing the intersection of two polygons. It is remarkable that the same algorithm can also be used, with only a few modifications, to compute the union and the difference of any two polygons.     

Detection of collapsed buildings caused by the 1999 Izmit,Turkey earthquake through digital analysis of post-event aerial photographs

In this study, the post-earthquake aerial photographs were digitally processed and analysed to detect collapsed buildings caused by the Izmit, Turkey earthquake of 17 August 1999. The selected area of study encloses part of the city of Golcuk, which is one of the urban areas most strongly hit by the earthquake. The analysis relies on the idea that if a building is collapsed, then it will not have corresponding shadows. The boundaries of the buildings were available and stored in a Geographical Information System (GIS) as vector polygons. The vector building polygons were used to match the shadow casting edges of the buildings with their corresponding shadows and to perform analyses in a building-specific manner. The shadow edges of the buildings were detected through a Prewitt edge detection algorithm. For each building, the agreement was then measured between the shadow producing edges of the building polygons and the thresholded edge image based on the percentage of shadow edge pixels. If the computed percentage value was below a preset threshold then the building being assessed was declared as collapsed. Of the 80 collapsed buildings, 74 were detected correctly, providing 92.50% producer's accuracy. The overall accuracy was computed as 96.15%. The results show that the detection of the collapsed buildings through digital analysis of post-earthquake aerial photographs based on shadow information is quite encouraging. It is also demonstrated that determining the optimum threshold value for separating the collapsed from uncollapsed buildings is important.     

Clamping a polygon

Aclamping hand has two opposing parallel edges; the distance between them can vary. We define what it means for the edges of a clamping hand and some edges of a polygon to form aclamp on the polygon. We conjecture that any polygon can be clamped by a hand if its edges are of positive length, but only provide proofs that clamps must exist for convex polygons and for certain polygons composed of two convex chains. The proofs involve extensive case analyses, and it is not obvious how to generalize them.     

What is a pixel?

The total list of processing required to view a pixel includes antialiasing, offset sampling, color space projection, reconstruction filter compensation, compositing, gamma correction, and quantization and dithering. If we look at all these operations we can see a pattern: Almost all of them throw away information. When we filter out high frequencies, quantize intensities into bins, project a continuous color spectrum into three numbers, and represent geometric edges with a single transparency value we can see that an ordinary-hardware pixel, either refreshed on the screen or stored in a file, is simply a bad data compression technique. Any rendering algorithm or image processing operation that converts data to pixels generally loses information about the original data that it uses as input. A few polygons become thousands of pixels; a high-resolution image becomes a low-resolution image. Conversion to pixels for viewing purposes used to be a slow operation, but with faster processors we no longer need to do the image generation offline for speed purposes. We can recalculate the image whenever we need to look at it.     

基于四叉树结构的数字地表模型快速生成算法设计

为了研究数字地表模型的快速生成方法，在总结传统Delaunay三角化算法的基础上，给出了一个基于四叉树结构的数字地表模型快速生成算法的详细设计，该算法的基本思想是首先利用四叉树结构来对离散点进行分割，然后对四叉树叶节点进行Delaunay三角化，再两两合并四叉树节点三角网的凸壳，以快速生成地表表格网模型，该算法是以四叉树为基本单位为实现限定边和限定多边形的快速嵌入，最后给出了算法在不同情况下的测试结果，并对测试结果进行了具体分析，给出了算法的时间效率分析和空间复杂性分析，实测数据结果表明，该算法有着较好的性能，而且也非常稳定，通过实测结果分析和算法的时间效率分析，可以得到算法的时间效率近似为O(nlog(n）），通过算法的空间复杂性分析可以看出，算法可以自动适应不同的点空间分布情况，而且采用四叉树结构也非常有利于限定边和限定多边形的嵌入。     

Moving Least Squares Coordinates

We propose a new family of barycentric coordinates that have closed‐forms for arbitrary 2D polygons. These coordinates are easy to compute and have linear precision even for open polygons. Not only do these coordinates have linear precision, but we can create coordinates that reproduce polynomials of a set degree m as long as degree m polynomials are specified along the boundary of the polygon. We also show how to extend these coordinates to interpolate derivatives specified on the boundary.     

二值图像中拐点的实时检测算法

鉴于数字图像中的拐点通常成为重要的信息载体,因此准确、稳定和实时地检测出拐点便成为拐点检测算法面临的主要问题,针对该问题,提出了一种新的二值图像中拐点的实时检测算法。该算法与传统基于边界链码的拐点检测算法不同,其是首先构建像素的k(k>8)邻域,并将图像中物体的边界表示为k邻域链码;然后根据曲率定义的差分形式计算各边界点处的曲率;最后通过检测曲率直方图的局部峰值精确定位出拐点,并利用拐角内部像素的颜色统计信息迅速判断出拐点的凸凹性.为验证该算法的效果,给出了该算法与4种已有算法的对比实验.结果表明,该算法不仅稳定性、准确性较高,而且算法简单,实时性强,并适合于嵌入式计算环境。     

LSB steganographic payload location for JPEG-decompressed images

Steganalysis always concentrates on the detection of the existence of the hidden information embedded into some digital multimedia by steganography. This paper presents a novel steganographic payload location method for spatial least significant bit (LSB) steganography with the JPEG-decompressed images used as the cover images. Firstly, we discuss the possibility of recovering the original cover image and compute the probability of successfully recovering. Then, we compute the distributions of the difference values between the estimated cover pixels and stego pixels in the payload-carrying and no-payload-carrying positions. Finally, combining with the theory of hypothesis test, we present a method to locate the payload-carrying pixels of JPEG-decompressed images, which is suitable for both LSB replacement and LSB matching. The experimental results show that: 1) the number of stego images needed to accurately locate all the payload-carrying pixels in the proposed method approaches the lower bound; 2) given the number of stego images, in the proposed method, the number of the payload-carrying pixels precisely located approaches the upper bound; 3) the proposed method performs better than some current state-of-the-art steganographic payload location methods for JPEG-decompressed images.     

Perception‐driven Accelerated Rendering

Advances in computer graphics enable us to create digital images of astonishing complexity and realism. However, processing resources are still a limiting factor. Hence, many costly but desirable aspects of realism are often not accounted for, including global illumination, accurate depth of field and motion blur, spectral effects, etc. especially in real‐time rendering. At the same time, there is a strong trend towards more pixels per display due to larger displays, higher pixel densities or larger fields of view. Further observable trends in current display technology include more bits per pixel (high dynamic range, wider color gamut/fidelity), increasing refresh rates (better motion depiction), and an increasing number of displayed views per pixel (stereo, multi‐view, all the way to holographic or lightfield displays). These developments cause significant unsolved technical challenges due to aspects such as limited compute power and bandwidth. Fortunately, the human visual system has certain limitations, which mean that providing the highest possible visual quality is not always necessary. In this report, we present the key research and models that exploit the limitations of perception to tackle visual quality and workload alike. Moreover, we present the open problems and promising future research targeting the question of how we can minimize the effort to compute and display only the necessary pixels while still offering a user full visual experience.     

Stabbing c-oriented polygons

Given a point and a set of objects in 2-space, the point's stabbing number is the number of objects in the set enclosing it. We introduce the notion of c-oriented objects, that is, objects whose edges are oriented in only a constant number of previously defined directions. We devise time-optimal algorithms for determining the stabbing numbers of points with respect to a set of c-oriented polygons: Given a mixed set of points and polygons of size n we show how to determine the stabbing numbers of all points in O(n log n) time. For a static set of polygons we are able to answer stabbing number queries in O(log n) time. For the second problem the same time bound was achieved previously, but only with much higher space- and preprocessing-costs.     

Accurate object contour tracking based on boundary edge selection

In this paper, a novel method for accurate subject tracking, by selecting only tracked subject boundary edges in a video stream with a changing background and moving camera, is proposed. This boundary edge selection is achieved in two steps: (1) removing background edges using edge motion, and from the output of the previous step, (2) selecting boundary edges using a normal direction derivative of the tracked contour. Accurate tracking is based on reduction of the effects of irrelevant edges, by only selecting boundary edge pixels. In order to remove background edges using edge motion, the tracked subject motion is computed and edge motions and edges having different motion directions from the subjects are removed. In selecting boundary edges using the normal contour direction, the image gradient values on every edge pixel are computed, and edge pixels with large gradient values are selected. Multi-level Canny edge maps are used to obtain proper details of a scene. Multi-level edge maps allow tracking, even though the tracked object boundary has complex edges, since the detail level of an edge map for the scene can be adjusted. A process of final routing is deployed in order to obtain a detailed contour. The computed contour is improved by checking against a strong Canny edge map and hiring strong Canny edge pixels around the computed contour using Dijkstra's minimum cost routing. The experimental results demonstrate that the proposed tracking approach is robust enough to handle a complex-textured scene in a mobile camera environment.     

Automatic computation of pebble roundness using digital imagery and discrete geometry

The shape of sedimentary particles is an important property, from which geographical hypotheses related to abrasion, distance of transport, river behavior, etc. can be formulated. In this paper, we use digital image analysis, especially discrete geometry, to automatically compute some shape parameters such as roundness, i.e. a measure of how much the corners and edges of a particle have been worn away.In contrast to previous work in which traditional digital images analysis techniques, such as Fourier transform, are used, we opted for a discrete geometry approach that allowed us to implement Wadell's original index, which is known to be more accurate, but more time consuming to implement in the field.Our implementation of Wadell's original index is highly correlated (92%) with the roundness classes of Krumbein's chart, used as a ground-truth. In addition, we show that other geometrical parameters, which are easier to compute, can be used to provide good approximations of roundness.We also used our shape parameters to study a set of pebbles digital images taken from the Progo basin river network (Indonesia). The results we obtained are in agreement with previous work and open new possibilities for geomorphologists thanks to automatic computation.     

2D and 3D shape retrieval using skeleton filling rate

As an increasing number of digital images are generated, a demand for an efficient and effective image retrieval mechanisms grows. In this work, we present a new skeleton-based algorithm for 2D and 3D shape retrieval. The algorithm starts by drawing circles (spheres for 3D) of increasing radius around skeletons. Since each skeleton corresponds to the center of a maximally inscribed circle (sphere), this process results in circles (spheres) that are partially inside the shape. Computing the ratio between pixels that lie within the shape and the total number of pixels allows us to distinguish shapes with similar skeletons. Experimental evaluation of the proposed approach including a comprehensive comparison with the previous techniques demonstrates both effectiveness and robustness of our algorithm for shape retrieval using several 2D and 3D datasets.     

Multiscale skeletons by image foresting transform and its application to neuromorphometry

The image foresting transform (IFT) reduces optimal image partition problems based on seed pixels to a shortest-path forest problem in a graph, whose solution can be obtained in linear time. Such a strategy has allowed a unified and efficient approach to the design of image processing operators, such as edge tracking, region growing, watershed transforms, distance transforms, and connected filters. This paper presents a fast and simple method based on the IFT to compute multiscale skeletons and shape reconstructions without border shifting. The method also generates one-pixel-wide connected skeletons and the skeleton by influence zones, simultaneously, for objects of arbitrary topologies. The results of the work are illustrated with respect to skeleton quality, execution time, and its application to neuromorphometry.     

A simple method for constructing heptadecagon

It is proved that among the regular polygons with prime edges, only the regular polygons with Fermat prime edges are constructable with compass and straightedge. As 17 is a Fermat prime number, the construction of heptadecagon has been discussing all the time. Many different construction methods are proposed although they are based on the same theory. Simplification of the construction is still a sensible problem. Here, we propose a simple method for constructing regular heptadecagon with the fewest steps. The accumulation of construction errors is also avoided. This method is more applicable than the previous construction.     

Digital Curvature Flow and Its Application for Skeletonization

In this paper, we define digital curvature flow for planar digital objects. We define the principal normal vectors for points on the digital boundary of a binary planar object. Digital curvature flow is defined as the motion of points on the boundary curve according to principal normal vectors. Therefore, digital curvature flow is a digital version of curvature flow. Furthermore, this transformation could also be considered as discrete curvature flow on isotetic polygons, all edges of which are parallel to the axes of an orthogonal coordinate system.