•First algorithm for removing non-relevant regions in hierarchies of partitions.•Efficient algorithm with O(n log(n)) time complexity.•The regions of the simplified hierarchy are regions or union of ...regions of the initial hierarchies.•Evaluation on natural image analysis and illustrations on hierarchical clustering of data points.•The method can be used as a pre- or post-processing step to enhance the quality of hierarchical segmentation algorithm.
We propose an efficient algorithm that removes unimportant regions from a hierarchical partition tree, while preserving the hierarchical partition structure. Various experiments demonstrate that applying this algorithm on various classification or segmentation problems does indeed improve the results by a large margin. Code is available online at https://github.com/higra/Higra. B. Perret, G. Chierchia, J. Cousty, S.J. F. Guimarães, Y. Kenmochi, L. Najman, Higra: Hierarchical Graph Analysis, SoftwareX, 10, 1--6, ISSN 2019, 2352-7110, 10.1016/j.softx.2019.100335.
•A review of hierarchical segmentation methods, both general and superpixel ones.•Formal categorization of dense and sparse hierarchical segmentation approaches.•Introduction of a new method within ...each aforementioned category.•State-of-the-art superpixel segmentation results combining our methods.
We investigate the intersection between hierarchical and superpixel image segmentation. Two strategies are considered: (i) the classical region merging, that creates a dense hierarchy with a higher number of levels, and (ii) the recursive execution of some superpixel algorithm, which generates a sparse hierarchy with fewer levels. We show that, while dense methods can capture more intermediate or higher-level object information, sparse methods are considerably faster and usually with higher boundary adherence at finer levels. We first formalize the two strategies and present a sparse method, which is faster than its superpixel algorithm and with similar boundary adherence. We then propose a new dense method to be used as post-processing from the intermediate level, as obtained by our sparse method, upwards. This combination results in a unique strategy and the most effective hierarchical segmentation method among the compared state-of-the-art approaches, with efficiency comparable to the fastest superpixel algorithms.
The need for assertive video classification has been increasingly in demand. Especially for detecting endangering situations, it is crucial to have a quick response to avoid triggering more serious ...problems. During this work, we target video classification concerning falls. Our study focuses on the use of high-level descriptors able to correctly characterize the event. These descriptor results will serve as inputs to
a multi-stream architecture of VGG-16 networks. Therefore, our proposal
is based on the analysis of the best combination of high-level extracted features for the binary classification of videos. This approach was tested on three known datasets, and has proven to yield similar results as other more consuming methods found in the literature.
Sketch-based image retrieval (SBIR) lets one express a precise visual query with simple and widespread means. In the SBIR approaches, the challenge consists in representing the image dataset features ...in a structure that allows one to efficiently and effectively retrieve images in a scalable system. We put forward a sketch-based image retrieval solution where sketches and natural image contours are represented and compared, in both, the compressed-domain of wavelet and in the pixel domain. The query is efficiently performed in the wavelet domain, while effectiveness refinements are achieved using the pixel domain to verify the spatial consistency between the sketch strokes and the natural image contours. Also, we present an efficient scheme of inverted lists for sketch-based image retrieval using the compressed-domain of wavelets. Our proposal of indexing presents two main advantages, the amount of the data to compute the query is smaller than the traditional method while it presents a better effectiveness.
Superpixel segmentation consists of partitioning images into regions composed of similar and connected pixels. Its methods have been widely used in many computer vision applications, since it allows ...for reducing the workload, removing redundant information, and preserving regions with meaningful features. Due to the rapid progress in this area, the literature fails to catch up on more recent works among the compared ones and to categorize the methods according to all existing strategies. This work fills this gap by presenting a comprehensive review with a new taxonomy for superpixel segmentation, in which methods are classified according to their processing steps and processing levels of image features. We revisit the recent and popular literature according to our taxonomy and evaluate 23 strategies and a grid segmentation baseline based on nine criteria: connectivity, compactness, delineation, control over the number of superpixels, color homogeneity, robustness, running time, stability, and visual quality. Our experiments show the trends of each approach in superpixel segmentation and discuss individual trade-offs. Finally, we provide a new benchmark for superpixel assessment, available at https://github.com/IMScience-PPGINF-PucMinas/superpixel-benchmark.
Video summarization is a simplification of video content for compacting the video information. The video summarization problem can be transformed into a clustering problem, in which some frames are ...selected to saliently represent the video content. In this work, we use a graph-based hierarchical clustering method for computing a video summary. In fact, the proposed approach, called HSUMM, adopts a hierarchical clustering method to generate a weight map from the frame similarity graph in which the clusters (or connected components of the graph) can easily be inferred. Moreover, the use of this strategy allows the application of a similarity measure between clusters during graph partition, instead of considering only the similarity between isolated frames. We also provide a unified framework for video summarization based on minimum spanning tree and weight maps in which HSUMM could be seen as an instance that uses a minimum spanning tree of frames and a weight map based on hierarchical observation scales computed over that tree. Furthermore, a new evaluation measure that assesses the diversity of opinions among users when they produce a summary for the same video, called Covering, is also proposed. During tests, different strategies for the identification of summary size and for the selection of keyframes were analyzed. Experimental results provide quantitative and qualitative comparison between the new approach and other popular algorithms from the literature, showing that the new algorithm is robust. Concerning quality measures, HSUMM outperforms the compared methods regardless of the visual feature used in terms of F-measure.
•A hierarchical graph partitioning based on optimum cuts is proposed, named UOIFT.•UOIFT can be tailored to different objects, according to their boundary polarity.•UOIFT theoretically encompasses ...the single-linkage algorithm by MST.•UOIFT is robust in relation to illumination variations and inhomogeneity effects.
In this work, a hierarchical graph partitioning based on optimum cuts in graphs is proposed for unsupervised image segmentation, that can be tailored to the target group of objects, according to their boundary polarity, by extending Oriented Image Foresting Transform (OIFT). The proposed method, named UOIFT, theoretically encompasses as a particular case the single-linkage algorithm by minimum spanning tree (MST) and gives superior segmentation results compared to other approaches commonly used in the literature, usually requiring a lower number of image partitions to accurately isolate the desired regions of interest with known polarity. The method is supported by new theoretical results involving the usage of non-monotonic-incremental cost functions in directed graphs and exploits the local contrast of image regions, being robust in relation to illumination variations and inhomogeneity effects. UOIFT is demonstrated using a region adjacency graph of superpixels in medical and natural images.
Remote sensing techniques permit characterizing urban landscapes through urban spectral indices that distinguish built from unbuilt areas. These indices are considered a good proxy for economic ...activity as they reflect the development of the country, state, or municipality. However, urban spectral indices easily confuse built-up areas with bare land, compromising economic estimates. This confusion is associated with the resolution of the satellite image, the spectral index, and the threshold value that classifies pixels as built-up or unbuilt areas. This research introduces the Constrained Double-threshold method that allows for the reduction of this confusion. The method allows constraining the confusion between built and unbuilt areas to a certain percentage (e.g., 10%), reducing this error by 2.9 times and the overall error by 7%. The paper results show that the capacity of the spectral index to estimate economic activity depends more on the confusion between built-up and non-built-up areas than on the overall classification error. The two best-performing spectral indexes showed high explanatory power (R = 0.88; R = 0.86) and prediction (R2 = 90; R2 = 0.62) of the economic activity of the municipalities. The estimated growth in economic activity between 2018 and 2019 obtained from satellite images of 7.2% is consistent with official data for civil construction of 6.9%.
Subsequence identification consists of identifying real positions of a specific video clip in a video stream together with the operations that may be used to transform the former into a subsequence ...from the latter. To cope with this problem, we propose a new approach, considering a bipartite graph matching to measure video clip similarity with a target video stream which has not been preprocessed.
The main contributions of our work are the application of a simple and efficient distance to solve the subsequence identification problem along with the definition of a hit function that identifies precisely which operations were used in query transformation. Experimental results demonstrate that our method performances achieve 90% recall with 93% precision, though it is done without preprocessing of the target video.
Mobile devices have become indispensable to communication over the last decade. In a hypothetical scenario in which conventional forms of connection such as antennas and satellites are not available, ...other forms of information propagation must be used. Ad-hoc broadcasts are strategies for maintaining communication between devices in these situations, however, they require high transmission power. This article proposes the use of priority queues, such as the Fibonacci heap and the binary heap in the Dijkstra algorithm, in order to reduce its computational cost in the search for the smallest network route. From the limitation of the signal strength to reach the nearest device, our results obtained lower transmission power compared to the standard device settings. Simulations show that a fibonacci heap has higher performance than binary heap in networks with higher number of connections. This way, the implementation of the fibonacci heap brings improvements in the computational cost of the algorithm. In addition, we show that the calculation of the smallest route is directly connected to the choice of the path with the lowest transmission power.