Fast JPEG Image Segmentation Algorithm Based on Graph Cuts

fast特征点检测算法用途
fast（Features from Accelerated Segment Test）特征点检
测算法是一种用于计算机视觉和图像处理领域的算法，它的主要用
途包括但不限于以下几个方面：
1. 特征匹配，fast算法可以用于在图像中检测关键点，然后
将这些关键点用于图像配准和特征匹配。

这在目标跟踪、图像拼接
和三维重建等领域都是非常重要的应用。

2. 物体识别，在物体识别和目标检测中，fast算法可以用于
提取图像中的关键点，从而帮助识别和定位物体。

这对于自动驾驶、安防监控等领域有着重要的应用。

3. 视觉SLAM，在视觉SLAM（Simultaneous Localization and Mapping）中，fast算法可以用于提取图像中的特征点，从而进行
环境的建模和相机定位，这对于无人机、机器人和增强现实等应用
具有重要意义。

4. 图像配准，在图像配准中，fast算法可以用于检测图像中
的关键点，然后将这些关键点用于图像的配准和校正，这对于医学
影像处理、遥感图像处理等领域都是非常重要的。

总的来说，fast特征点检测算法在计算机视觉和图像处理领域具有广泛的应用，可以帮助提取图像中的关键信息，从而实现图像配准、目标识别、SLAM等多种应用。

fast特征点提取FAST（Features from Accelerated Segment Test，加速分段测试特征点提取算法）是一种快速、稳定性强的特征点提取算法。

它已被广泛应用于计算机视觉中的目标跟踪、图像配准和3D重建等领域。

下面，我们将详细介绍FAST特征点提取算法的步骤。

第一步：灰度化处理首先，需要将图像转换为灰度图像。

这是因为在彩色图像中，对于每个像素点，都有三个通道的颜色信息（红绿蓝）。

而在灰度图像中，每个像素只有一个通道的灰度值，这样可以加快算法的运算速度。

第二步：选择初始像素点在FAST算法中，每个像素点都可以被视为候选特征点。

然而，我们需要筛选出那些最具代表性的像素点。

为了进行快速筛选，我们先随机选择一个像素点作为初始点。

第三步：确定阈值在FAST算法中，每个像素点都会被计算其周围三层圆环上的像素点是否明显区别于自身的灰度值。

因此，我们需要确定阈值，来判断周围像素点的差异是否足够明显。

具体而言，对于每个像素点，若存在在该像素点相邻的n个像素点中的k个像素点与该像素点的灰度值差异都大于一定阈值T，那么该像素点就可以被认为是一个特征点。

第四步：非极大值抑制在第三步中，我们根据阈值确定了很多可作为特征点的像素点。

但是，这些像素点中可能存在很多冗余的信息，因此我们需要进行非极大值抑制。

具体来说，将所有的特征点按照其周围像素点的差异值排序，选择最突出的n个特征点，并删除与它们距离过近的其他特征点，从而得到n个最具代表性的特征点。

第五步：特征描述在得到了最具代表性的n个特征点之后，我们需要对它们进行描述。

常用的方法是使用SIFT、SURF等算法对特征点进行描述，从而得到特征向量。

FAST特征点提取算法的优势在于速度快、稳定性强，并且适用于大多数的图像。

然而，由于该算法基于像素灰度值的比较，因此对于亮度变化较大的图像，可能会出现一些误差。

此外，FAST算法生成的特征点比较分散，特征描述能力相对较弱。

A HIERARCHICAL IMAGE SEGMENTATION ALGORITHMWei Yu,Jason FrittsWashington University Computer Science Department St.Louis,MO63130Fangting SunIowa State University Computer Science Department Ames,IA50011ABSTRACTThis paper presents a hierarchical image representation that pre-serves spatial relationships,and an image segmentation algorithmthat efficiently constructs this representation.The overall struc-ture of the hierarchical representation assumes a tree-like organi-zation,in which a node at a higher level represents of a group ofnodes from the next lower level.The root node of the represen-tation is the full image,and the leaf nodes are blocks ofpixels(usually or),called blobs.The segmentation algorithm builds this hierarchical representation using an efficientclustering algorithm for grouping nodes progressively into largerobjects.While performing the union of nodes at one level into asingle parent node at the next higher level of the tree,nodes are grouped together according to similarities between their feature vectors,which include such features as color information,orien-tation,texture,size,energy,and neighbor information.The com-putation complexity of the hierarchical image segmentation algo-rithm is,where,are the height and width of the original image.Experimental results show that this algorithm can segment images and extract objects effectively.1.INTRODUCTIONObject extraction via image segmentation plays a key role in many applications.Unfortunately however,it remains a difficult prob-lem.There does not exist a single generic algorithm that works well for all applications.Target applications vary in the necessary degrees of precision,efficiency,and feature information required from image segmentation,so different algorithms are typically bet-ter suited to different applications.For some application areas,like content-based image retrieval(CBIR)and MPEG-4video com-pression,it is desirable to have a segmentation algorithm that pre-serves information regarding the spatial relationships between ob-jects.Toward this end,we present an efficient image segmentation algorithm that generates a hierarchical image representation that preserves these spatial relationships.Compared with most non-hierarchical segmentation algorithms, such as the K-means algorithm used in SIMPLIcity[1],algorithms based on a hierarchical representation preserve the spatial and neigh-boring information among segmented regions.For applications like content-based image retrieval and MPEG-4video compres-sion,the ability to preserve spatial relationships between objects can improve image retrieval and motion estimation efficiency.For content-based image retrieval,segmentation schemes can be used to extract objects and their features from images,and then use the object feature information to increase image retrieval efficiency [2].The additional feature information regarding neighbor rela-tionships between objects can be used to further improve image retrieval for image queries where spatial information about objects in the image is key to effective image recall.For MPEG-4video compression[3],and other content-based video compression schemes,image segmentation is used to divide scenes up into objects.By performing motion estimation and com-pensation on objects,the minimal temporal variations within each object enables higher compression ratios.The added benefit of spatial information could further improve algorithm efficiency,al-lowing potentially simpler and more efficient motion tracking and object occlusion detection.A number of segmentation algorithms for building a hierar-chical image representations have been proposed[4,5,6,7].Al-though these hierarchical segmentation algorithms perform well in some specific areas,all of them suffer from various drawbacks. Nacken[5]and Shen et al.[6]employ methods similar to ours of iteratively grouping nodes in a hierarchical structure.However, their methods can lead to excessive iterations,generating a large number of hierarchy levels.Montanvert et al.[4]use stochastic analysis for image segmentation,but their segmentation results are not unique due to the stochastic decimation applied at each level. Furthermore,all of the above algorithms use only the original pixel values when performing pixel clustering,which Marr argues is not sufficient[8].Finally,none of these prior studies has examined the computation complexity of their algorithms.No data is provided in[4,5,6]regarding computation complexity,and only empirical results are provided by Marr[7].In this paper,we propose an efficient hierarchical image rep-resentation data structure and a powerful image segmentation al-gorithm for constructing this representation.We propose three new enhancements to hierarchical image segmentation to allevi-ate some of the drawbacks of previous approaches.First,we pro-pose an efficient new clustering scheme using a modified UNION-FIND data structure.This algorithm achieves low computation complexity by minimizing both the number of hierarchy levels and the computation complexity for each level of the image hi-erarchy.Second,when clustering nodes from different regions in each level,besides just color information,the algorithm considers a variety of additional features,including the orientation,texture, size,neighbors,and energy.Finally,this algorithm provides aflex-ible scheme for specifying when to stop the clustering procedure. The user can specify either the desired number of objects or the desired feature distance(i.e.the maximum feature distance below which clusters may be combined).Or,if the user specifies neither, a full hierarchical representation of the original image will be con-structed(i.e.with the root node of the tree being a single object corresponding to the whole image).The remainder of this paper is organized as follows.SectionFigure1:Hierarchical Image Representation2summarizes the image representation theory of Marr[8],and discusses the proposed hierarchical image representation and as-sociated image segmentation algorithm.Section3then discusses the specific details of the segmentation algorithm.Section4an-alyzes the computation complexity of the algorithm,and section 5gives some preliminary experimental results.Finally,section6summarizes our conclusions and discusses future work.2.HIERARCHICAL IMAGE REPRESENTATIONIn defining an image representation,it is important to recognize that the intensity values in an image are derived from four mainfactors:geometry,surface reflectance,illumination,and viewpoint. Consequently,it is insufficient to utilize just intensity information during image segmentation.As elaborated by Marr[8],in addi-tion to color intensity information,it is important to define a repre-sentation of both surface reflectance and geometrical organization. The representation should contain features that can be derived re-liably and repeatedly from images,and to which can be assigned values of attributes like orientation,brightness,size,and position.Further,Marr[8]provides some important underlying physical as-sumptions for the surface reflectance function of an image:Ex-istence of surface,Hierarchical organization,Similarity,Spatial continuity,Continuity of discontinuities,and Continuity offlow.Based on these physical assumptions,we propose a hierarchi-cal image representation.This representation embodies a tree-like organization based on the UNION-FIND data structure[9]. The root node represents the full image,and the leaf nodes rep-resent blocks of pixels(usually or),called blobs.This representation defines a hierarchy of levels,where eachlevel consists of two data structures,a weighted graph,and a disjoint-set.Each vertex of represents one region of the original image and has a feature vec-tor characterizing this region.Each set in is composed of one or more nodes,and each node has a pointer to one vertex of .The two data structures are further defined by Cormen et al.[9].specifies the spatial relationship between regions, where two vertices are connected by an edge if and only if their corresponding regions neighbor each other.The weight of each edge defines the degree of the similarity between two regions.In addition to the standard definition for,each vertex ofhas two additional attributes:and,which define the relationship between nodes in two adjacent levels.1:2:3:4:5:while()do 6:for()do7:if()then 8:9:10:if(()then11:12:end if13:end if14:end for15:for()do16:if()then17:18:19:20:end if21:end for22:23:24:25:end while26:final number of objects,,or the maximum feature distance,,for merging regions.Or if not speci-fied,the algorithm will continue until a single root node exists that defines the full image.From this representation,objects and fea-tures can be extracted easily through a top-down traversal of the final hierarchical representation of the image.In each iteration of the while loop,thefirst loop clus-ters neighboring regions of this level according to somevalue(may be defined locally for each level,or globally for all levels).This threshold is usually small,no more than.To ensure low computation complexity,the second loop requires that each single-node set merge with at least one other set in this level.So,before a new level is generated,this loop guarantees that all sets of the current include at least two nodes.Con-sequently,each new level of the hierarchy is guaranteed to have no more than half the number of nodes as the previous level,ensuring fast convergence of the algorithm.Below are the implementation details of subroutines:partitions an image into blobs(usually or),with each blob correspond-ing to a vertex of.Then,the wavelet transform[10]ex-tracts orientation and texture information from each blob,using a similar method to Wang et al.’s[1].Two kinds oforthonormal waveletfilters are used,the Haarfilter and theDaubechies-4filter[10].Finally,nine features are extractedfor each blob:thefirst three are the mean color values ofthe blob;the second three are the orientation values in thehorizontal,vertical,and oblique directions(which also im-plicitly define the texture information in these directions asdemonstrated by Wang et al.[1]);the last three are the de-viations of the color values of this blob.creates and initializes the lowest level’s weighted graph,.Two vertices are connectedby an edge if and only if the two corresponding blobs inthe original image are neighbors of each other.In this pa-per,the Euclidean distance of the feature vectors for twoconnected nodes is calculated and assigned to the edge,andeach feature has the same weight when calculating distance.creates and initializes the disjoint set of the lowest level,such that each set has only one elementand each element points to one vertex of.and are the standard implementations of disjoint-set operations for theUNION-FIND data structure[9].Path compression[11,12]is used in to reduce the computation com-plexity of the set union operations.returns the vertex with the smallest feature distance to among all theneighboring vertices of in.creates a new weighted graph,with a number of nodes, ,equal to the number of sets in.Nodes ofare only connected by an edge if their corresponding sets in were likewise connected.Each vertex of has a feature vector with six mean values and six de-viation values,except the vertices in the lowest level,whichhave only three deviation values(orientation has no devia-tion values in the lowest level).For any,which ismapped from the vertex set of,the mean featurevalues are calculated using Equ.1:blobs,the wavelet transform of each blob requires time,and the time for feature calculation is.The subroutines InitGraph and InitSet needvertices and sets in ini-tially.After the end of one while iteration,the number of nodes in level is at most half of the number of nodes in level,so there are at most[13],whereis a functional inverse of Ackerman’s function and is no more than in general.The subroutine FindNearSib needs time.So the total time needed in one while iteration isand the computation complexity of the whole algorithm is.5.PERFORMANCE EV ALUATIONThe segmentation algorithm has been performed on more than100 reference images from the set used by Wang et al.[1].Four of them are illustrated in Fig.2.Thefirst image is aRGB color image and the others are RGB color images. This implementation used blobs and a stopping condition of=.The was globally set to for all levels.All of the images were segmented into the displayedhierarchical representations using no more thaniterations.(a)Originalimage(b)Segmentedimage(c)Originalimage(d)Segmentedimage(g)Originalimage(h)Segmentedimage(e)Originalimage(f)Segmented imageFigure2:Image Segmentation Results6.CONCLUSION AND FUTURE WORKThis paper examined a hierarchical image representation data struc-ture that perserves spatial information between neighboring ob-jects,and an efficient image segmentation algorithm for construct-ing this representation.The algorithm segments images by itera-tively clustering pixels into a hierarchy,using feature informationsuch as color layout,neighbors,size,energy,texture,and orienta-tion.Thefinal result is a hierarchical representation of the originalimage with each segmented region representing an object.Fea-tures characterizing each object can be obtained easily by travers-ing thefinal representation.This hierarchical image segmentation algorithm makes threecontributions:First,a novel clustering scheme is propopsed thatachieves low computation complexity by minimizing both the num-ber of hierarchy levels and the computation complexity per level.Second,in addition to just pixel intensity information,the algo-rithm also considers the orientation,texture,size,neighbors,andenergy when comparing feature distance during clustering.Fi-nally,this algorithm offers aflexible stopping scheme,allowingthe user to stop early by specifying the desired number of objectsor maximum feature distance objects,or completing a full hierar-chical image representation.In future research,we intend to combine this segmentation al-gorithm with multiple instances learning algorithms[2]for furtherimproving image retrieval and classification precision in the CBIRapplications.We also plan to comprehensively compare our al-gorithm with other hierarchical and non-hierarchical segmentationalgorithms,and explore use of this algorithm,and future varia-tions,with MPEG-4,as well as CBIR.7.REFERENCES[1]J.Z.Wang,J.Li,and G.Wiederhold,“Simplic-ity:Semantics-sensitive integrated matching for picture li-braries,”IEEE Transactions on Pattern Analysis and Ma-chine Intelligence,vol.23,pp.947–963,92001.[2]Q.Zhang,W.Yu,S.A.Goldman,and J.E.Fritts,“Content-based image retrieval using multiple-instance learning,”19thIntl.Conf.on Machine Learning,July2002.[3]P.Salembier and F.Marques,“Region-based representationsof image and video:Segmentation tools for multimedia ser-vices,”IEEE Trans.Circuits Syst.Video Technol.,vol.9,pp.1147–1169,December1999.[4] A.Montanvert,P.Meer,and A.Rosenfeld,“Hierarchicalimage analysis using irregular tessellations,”IEEE Transac-tions on Pattern Analysis and Machine Intelligence,vol.13,no.4,April1991.[5]P.F.M.Nacken,“Image segmentation by connectivity pre-serving relinking in hierarchical graph structures,”PatternRecognition,vol.28,no.6,June1995.[6]X.Shen,M.Spann,and P.F.M.Nacken,“Segmentationof2d and3d images through hierarchical clustering basedon region modelling,”Pattern Recognition,vol.31,no.9,September1998.[7]I.Molina,L.J.Roa,F.Arrebola,and F.Sandoval,“Hier-archical image segmentation based on nearest neighbour re-gion chains,”Electronics Letters,vol.36,no.13,June2000.[8] D.Marr,Vision,W.H.Freeman and Company,San Fran-cisco,California,1982.[9]T.H.Cormen,C.E.Leiserson,and R.L.Rivest,Introductionto Algorithms,MIT Press,Cambridge,MA,1990.[10]I.Daubechies,“Orthonornal bases of compactly supportedwavelets,”Comm.Pure.and Appl.Math.,vol.41,pp.909–996,November1988.[11] A.V.Aho,J.E.Hopcroft,and J.D.Ullman,The Design andAnalysis of Computer Algorithms,Addison-Wesley,MA,1974.[12]R.E.Tarjan,Data Structures and Network Algorithms,CBMS44.SIAM,Philadelphia,Pennsylvania,1983.[13]R.E.Tarjan,“Efficiency of a good by not linear set unionalgorithm,”put.Mach.,vol.22,pp.215–225,1975.。

JPEG图片压缩算法流程详解薛晓利JPEG是Joint Photographic Exports Group的英文缩写，中文称之为联合图像专家小组。

该小组隶属于ISO国际标准化组织，主要负责定制静态数字图像的编码方法，即所谓的JPEG 算法。

JPEG专家组开发了两种基本的压缩算法、两种熵编码方法、四种编码模式。

如下所示：压缩算法：（1）有损的离散余弦变换DCT（Discrete Cosine Transform）（2）无损的预测压缩技术；熵编码方法：（1）Huffman编码；（2）算术编码；编码模式：（1）基于DCT的顺序模式：编码、解码通过一次扫描完成；（2）基于DCT的渐进模式：编码、解码需要多次扫描完成，扫描效果由粗到精，逐级递增；（3）无损模式：基于DPCM，保证解码后完全精确恢复到原图像采样值；（4）层次模式：图像在多个空间分辨率中进行编码，可以根据需要只对低分辨率数据做解码，放弃高分辨率信息；在实际应用中，JPEG图像编码算法使用的大多是离散余弦变换、Huffman编码、顺序编码模式。

这样的方式，被人们称为JPEG的基本系统。

这里介绍的JPEG编码算法的流程，也是针对基本系统而言。

基本系统的JPEG压缩编码算法一共分为11个步骤：颜色模式转换、采样、分块、离散余弦变换（DCT）、Zigzag 扫描排序、量化、DC系数的差分脉冲调制编码、DC系数的中间格式计算、AC系数的游程长度编码、AC系数的中间格式计算、熵编码。

下面，将一一介绍这11个步骤的详细原理和计算过程。

（1）颜色模式转换JPEG采用的是YCrCb颜色空间，而BMP采用的是RGB颜色空间，要想对BMP图片进行压缩，首先需要进行颜色空间的转换。

YCrCb颜色空间中，Y代表亮度，Cr,Cb则代表色度和饱和度(也有人将Cb,Cr两者统称为色度)，三者通常以Y,U,V来表示，即用U代表Cb，用V代表Cr。

RGB和YCrCb之间的转换关系如下所示：Y = 0.299R+0.587G+0.114BCb = -0.1687R-0.3313G+0.5B+128Cr = 0.5R=0.418G-0.0813B+128一般来说，C 值(包括Cb Cr) 应该是一个有符号的数字, 但这里通过加上128，使其变为8位的无符号整数，从而方便数据的存储和计算。