In recent studies of object detection and tracking, neural networks have been widely used, and their accuracy has improved. However, its computational complexity is very high and requires the use of high-end GPUs. In order to achieve realtime inference on edge devices, it is necessary to reduce the computational complexity of the network by scaling it down, but this leads to a loss of accuracy. To avoid this loss of accuracy, a method has been proposed in which object detection is performed using a neural network at regular intervals, and in the frames in between, the detected object positions are interpolated using motion prediction. In this research, we propose a method to improve the accuracy of interpolation even when the camera is moving by using an affine transformation used for image stabilization. We also show its realtime computation method on Jetson TX2, one of the lowest power embedded GPUs. The proposed method enables realtime processing of object detection using Yolov5s and tracking of the detected objects at the edge.

Video stabilization is a technique used to eliminate the shakiness in video. It plays an important role to improve the quality of the videos captured by cameras mounted on drones and autonomous robots, and handheld cameras. In these cases, it is generally required to achieve real-time video stabilization using low-power and low-cost devices. In this research, we focus on software video stabilization, and propose a new implementation method using an embedded GPU. Our target device is Nvidia Jetson Nano, which is one of the smallest and least power consumption embedded GPUs. In our implementation, 1) multi-threads on the CPU on Jetson Nano and the GPU run asynchronously and in parallel to achieve high performance, 2) the size of the search area is minimized to reduce the amount of computation assuming that sufficiently fast processing speed is possible using the GPU, and 3) the data transfer from the global memory of the GPU is minimized to hide the high latency. Our implementation achieves 81.4 fps for full HD videos, and its quality is high enough for practical use.

Mobile stereo matching systems are becoming more important in many applications such as auto-driving and autonomous robots. However, to maintain its low power consumption, mobile platforms have only limited hardware resources. Accurate stereo matching methods require a high computational complexity, and it is difficult to maintain both acceptable accuracy and processing speed on the mobile platforms. To solve this trade-off, in this paper, we propose a novel acceleration approach for a well-known matching algorithm Zero-means Normalized Cross Correlation (ZNCC), and show its effectiveness on a Jetson TX2 embedded GPU. By combining our new approach, Z2- ZNCC, with the Semi-Global Matching (SGM) algorithm, our system achieves a low error rate of 7.76% while keeping 28 fps for 1242×375 pixels images with the maximum disparity of 128 on the KITTI 2015 dataset. This performance is higher than previous state-of-the-art system on the same hardware platform.

In this paper, we propose a low error rate and realtime stereo vision system on G PU. Many stereo vision systems on G PU have been proposed to date. In those systems, the error rates and the processing speed are in trade-off relationship. We propose a real-time stereo vision system on GPU for the high resolution images. This system also maintains a low error rate compared to other fast systems. In our approach, we have implemented the cost aggregation (CA), cross-checking and median filter on GPU in order to realize the real-time processing. Its processing speed is 40 fps for 1436×992 pixels images when the maximum disparity is 145, and its error rate is the lowest among the GPU systems which are faster than 30 fps.

Hyperspectral image classification is one of the most important techniques for analyzing hyperspectral image that have hundreds of spectrum luminance values. For this classification, supervised learning methods are widely used, but in general, they have a trade-off between their accuracy and computational complexity. In this paper, we propose an FPGA implementation of hyperspectral image classification based on a composite kernel method. Because of the large size of hyperspectral images, the data mapping becomes the most critical issue for achieving higher processing speed. Two data mapping approaches are discussed, and one of them that is most suitable for our target images is implemented on an FPGA. Its processing speed for 145×145 pixel images is fast enough for real-time processing, and its accuracy is comparable with other classification algorithms.

Matting is a process of extracting a foreground from background in an image. It is one of the key techniques in many image editing, and many algorithms have been proposed. Robust Matting is one of the powerful matting algorithms. In the Robust Matting, first, a set of pixels in the foreground and background are sampled, and then, for each pixel in the image, its category is determined by comparing it to a number of pairs of a foreground and background sample. Its computational complexity is very high because of a large number of multiply and square operations. In this paper, we propose an FPGA implementation for real-time processing of HD images. In our approach, the image is divided into small blocks and the same pairs of the foreground and background pixels are used for the pixels in the same block in order to reduce the number of the operations. This approach makes it possible to execute multiply operations by simply looking up tables that are dynamically updated block by block.

In this paper, we present an FPGA hardware implementation approach for a phylogenetic tree reconstruction with maximum parsimony algorithm. The algorithm, based on stochastic local search, uses the Indirect Calculation of Tree Lengths and the Incremental Tree Optimization methods. We evaluate and compare our new approach against previous hardware approaches, and against TNT, the fastest available parsimony program. We make this comparison for eight real-world biological datasets. We obtain acceleration rates per tree between 2.60 and 4.68 against a previous approach that does not use incremental optimization; between 2.19 and 4.05 against a previous approach that uses an alternative second-pass optimization; and, between 2.66 and 31.94 against TNT. Our approach is not only faster, but it does not use additional memories during the incremental optimization, as it is the case for a software approach.

In this paper, we describe an FPGA system for the real-time processing of Poisson image Editing. Poisson Image Editing is a powerful method to overlay an image on another image seamlessly. In this method, however, a simple equation is repeatedly applied to each pixel, and this repetition makes its computational complexity very high. In our system, a very deep pipeline is used to apply the equation. One repetition is executed on each stage of the pipeline, and all repetitions are applied to all pixels during one scan of the image. In our current implementation, to reduce the circuit size, a color image is scanned three times, for R-, G-, and B-plane, but its processing speed is still fast enough for real-time processing of HD images.

The box filter is widely used in image processing. Its computational complexity is low, and many other filters can be realized by using different size box filters. The implementation method of the box filter that is widely used in the software programs requires an array to store data, the size of which is filter size × image width. This array often limits the feasibility of the box filter on FPGA, because its size is proportional to the image width. In this paper, we show an implementation method of the box filter that requires less memory. Two types of wide-width but shallow memory are required in this method, but these memory can be efficiently realized on FPGA using distributed RAMs and block RAMs. In this method, the image is scanned in zigzag. The performance is decreased because of the necessity to overlap the zigzag scan, but it is fast enough for practical use. This zigzag scan enable to reduce the memory size to store data, but extra line buffers are required. Our approach is specially effective for applications that calculate cross-correlations for finding the best matching, because the overhead caused by the extra line buffers becomes relatively small in these applications. We show the effectiveness of our method using a stereo vision program based on the cost aggregation with guided filter.

In this paper, we present an alternative and improved FPGA hardware implementation for a phylogenetic tree reconstruction with maximum parsimony algorithm. As in our previous work, the approach is based on a particular stochastic local search algorithm that uses the Indirect Calculation of Tree Lengths method. However, now we use an alternative second-pass optimization method, for the first time, and modify the rearrangement evaluation process. As a result, we reduce the execution time by half for these two steps in the algorithm. We compare execution times against our previous hardware approach for six real-world biological datasets, obtaining an acceleration rate of around 1.2 times faster. We also show a comparison against the phylogenetic software TNT.

Short read mapping is a process to align the short reads, which are fixed-length fragments of the target genome, to a given reference genome to identify the mutations in the target genome. Because of the rapid development of Next Generation Sequencing (NGS) technologies, faster short read mapping is required. In this paper, we propose a variable length hash method to further accelerate FPGA short read mapping systems. In the hash-based short read mapping algorithms, a fixed length sub-string of each short read, called seed, is used as the key. However, many different seeds are mapped into the same hash slots because of the high ununiformity of the human genome, and many fruitless key comparisons are performed. To equalize the slot size, we propose an optimized hash function that changes the bit masks adaptively. With this approach, it is possible to improve the performance of all FPGA short read mapping systems based on hash functions. The performance for the comparison in our FPGA system on a Xilinx XC7VX690T and XC6VLX240T can be improved two-times, and the total performance outperforms any existing FPGA systems.

The computational complexity of the optical flow estimation is very high, and many hardware systems have been proposed. In these systems, Lucas-Kanade, tensor-based, and phase-based method have been widely used. Census-transform, which is widely used in the stereo vision systems, was also implemented in several FPGA systems. In these systems, only one clock cycle is required for calculating one flow as their throughput, and their processing speed is fast enough for real-time processing of high resolution images. GPUs have also been used, and it was reported that the acceleration by FPGAs and GPUs is comparable[1][2]. The main problem in these systems is their low accuracy. The methods described above show high accuracy for the regions with high changes of brightness, but show poor results for uniform regions. This is the common problem with the stereo vision, and the approaches used in the stereo vision can be applied to the optical flow estimation. In this paper, we extend a cost aggregation algorithm[3] for the optical flow estimation, and implement it on FPGA.

In this work, we present an FPGA hardware implementation for a phylogenetic tree reconstruction with maximum parsimony algorithm. We base our approach on a particular stochastic local search algorithm that uses the Indirect Calculation of Tree Lengths method and the Progressive Neighborhood. In our implementation, we define a tree structure, and accelerate the search by parallel and pipeline processing. We show results for six real-world biological datasets. We compare execution times against our previous hardware approach, and TNT, the fastest available parsimony program. Acceleration rates between 34 to 45 per rearrangement, and 2 to 6, for the whole search, are obtained against our previous approach. Acceleration rates between 2 to 4 per rearrangement, and 18 to 112, for the whole search, are obtained against TNT. We estimate that these acceleration rates could increase for even larger datasets.

WalkSAT (WSAT) is a stochastic local search algorithms for Boolean Satisfiability (SAT) and Maximum Boolean Satisfiability (MaxSAT) problems, and it is very suitable for hardware acceleration because of its high inherent parallelism. Formal verification is one of the most important applications of SAT and MaxSAT, however, the size of the formal verification problems is significantly larger than on-chip memory size, and most of the data have to be placed in off-chip DRAM. In this paper, we propose a method to hide the access delay by using on-chip memory banks as a variable-way associative cache memory. The size of data blocks that are frequently fetched from the DRAM considerably varies in the WSAT algorithm. This cache memory aims to hold whole block when it is small enough, and only the head portion when it is large, to hide the DRAM access delay. With this cache memory, up to 60% DRAM access delay can be hidden, and the performance can be improved up to 26%.

Short read mapping is a process to align the short reads, which are fixed-length fragments of the target genome, to a given reference genome to identify the mutations in the target genome. Because of the rapid development of Next Generation Sequencing (NGS) technologies, faster short read mapping is required. In this paper, we propose an FPGA system for the short read mapping based on sort and parallel comparison of seeds. Seeds are fixed-length sub-strings in the short reads used to map the short read to the reference genome efficiently. In our system, (1) seeds are sorted using bucket sort, and the seeds in a bucket are compared in parallel with the candidate locations on the reference genome, (2) in this comparison, one nucleotide substitution, insertion, and deletion are allowed to achieve higher mapping rate, and (3) two stage search by reconfiguration is used to achieve higher performance. The mapping rate and search time by this approach outperforms existing systems.

We are researching ways to support network operators with environments that allow them to perform their jobs more efficiently. Currently the introduction and migration of new network systems are becoming more difficult because a lot of network systems interact with each other. We have been seeking technologies to support operators without changing the existing network system environments. In our last study we proposed Annotation technology. It places additional relevant information on top of any existing Operation Support System(OSS) window by image recognition of the window's contents. Annotation technology aims at helping operators to navigate through existing systems and environments, even those who do not know how to use OSS. In addition to the innovative approach of tracking operation display images, our last study also showed how to reduce image matching calculation costs in a quantitative way. In this paper we show newly implemented functions for intuitive and interactive support. Taken in total, they allow Annotation technology to become highly applicable and robust enough to be put into practical use. We applied the new Annotation technology to practical operation fields in a global environment and evaluated its performances. Operation works were made more efficient with a 2% increase in accuracy rates and no increase in operation time.

In this article, we present a fast and high quality stereo matching algorithm on FPGA using cost aggregation (CA) and fast locally consistent (FLC) dense stereo. In many software programs, global matching algorithms are used in order to obtain accurate disparity maps. Although their error rates are considerably low, their processing speeds are far from that required for real-time processing because of their complex processing sequences. In order to realize real-time processing, many hardware systems have been proposed to date. They have achieved considerably high processing speeds; however, their error rates are not as good as those of software programs, because simple local matching algorithms have been widely used in those systems. In our system, sophisticated local matching algorithms (CA and FLC) that are suitable for FPGA implementation are used to achieve low error rate while maintaining the high processing speed. We evaluate the performance of our circuit on Xilinx Vertex-6 FPGAs. Its error rate is comparable to that of top-level software algorithms, and its processing speed is nearly 2 clock cycles per pixel, which reaches 507.9 fps for 640 480 pixel images.

In this paper, we present a hardware acceleration approach for a phylogenetic tree reconstruction with maximum parsimony algorithm using FPGA. The algorithm is based on a stochastic local search with the progressive tree neighborhood. The hardware architecture is divided in different units, each of which performs a specific task of the algorithm, to take advantage of the parallel processing capabilities of the FPGA. We show results for four real-world biological datasets, and compare them against results from two programs: our C++ implementation and TNT (a program for phylogenetic analysis). High acceleration rates are obtained against our C++ implementation, but not against TNT, which even shows to be faster in some cases. We conclude our work with a discussion on this issue.

The rapid development of Next Generation Sequencing (NGS) has enabled to generate more than 100G base pairs per day from one machine. The produced data are randomly fragmented DNA base pair strings, called short reads, and millions of short reads are mapped onto the reference genomes, which are complete genetic sequences, to reconstruct the sequence of the sample DNA. This short read mapping is becoming the bottle-neck of NGS systems. In this paper, we propose an FPGA system for the mapping based on a hash-index method. In our system, short reads are divided into seeds, which are fixed-length substrings used for the mapping, and the seeds are sorted using buckets. Then, the seeds in each bucket are compared in parallel with the candidate locations. With this approach, many seeds can be compared in massively parallel manner with their candidate locations, and it becomes possible to improve the processing speed by reducing the number of the random accesses to DRAM banks which store the candidate locations. Furthermore, substitutions of the nucleotides in a seed can be allowed in this parallel comparison. This makes it possible to achieve higher matching rates than previous works.

Many hardware systems for stereo vision have been proposed. Their processing speed is very fast, but the algorithms used in them are limited in order to achieve the high processing speed by simplifying the sequences of the memory accesses and operations. The error rates by them can not compete with those by software programs. In this paper, we describe an FPGA implementation of a tree-structured dynamic programming algorithm. The computational complexity of this algorithm is higher than those by previous hardware systems, but the processing speed of our system is still fast enough for real-time applications, and its error rate is competitive with software algorithms.

Corner detection is a fundamental step in the image recognition. In this paper, we propose a new corner detection algorithm based on the circumferential distribution of the edges around each pixel. The computational complexity of this algorithm is high, but this algorithm is suitable for hardware implementation, and we can achieve high performance on an FPGA. Furthermore, this algorithm can detect the directions of all line segments crossing at the corners precisely. This feature makes it easier to detect polygons in the image using the corners. We also show a method for detecting the polygons in the image from the corners. The performance on Xilinx XC4VLX160 is fast enough for real-time applications.

In this paper, we describe an FPGA stereo vision system with lower error rate and high processing speed. In our system, two algorithms, the cost aggregation and fast locally consistent dense stereo, are used to achieve the lower error rate on the pipelined circuit while maintaining the high processing speed. We have evaluated the performance of the circuit on Xilinx Vertex-6 FPGAs. Its error rate is competitive with the top-level software algorithms, and its processing speed is almost 2 clock cycles per pixel, which reaches to 507.4 fps for 640 × 480 pixel images.

Image segmentation is one of the most important steps in image processing. The graph cut is an effective method for the image segmentation. For calculating the graph cut, the max-flow algorithm is widely used, but it requires long computation time. To execute the graph cut in real-time, the acceleration of max-flow algorithm with hardware is necessary. In this paper, we propose an implementation of a max-flow problem for the image segmentation on FPGA. In this system, the push-relabel method and the gap relabeling are used in order to achieve high performance on FPGA. The performance is 20-30 fps for standard benchmark images.

Image segmentation is one of the most important tasks in the image processing, and many algorithms for the segmentation have been proposed. In the segmentation based on the mean-shift, k-means and so on, the image is once over-segmented, and then the small regions are merged. In this paper, we propose a region merging algorithm for hardware systems, in which the data are not managed strictly, and the redundant computation caused by this loose management is hidden by the pipelined and parallel processing. We have implemented the algorithm on Xilinx XC4VLX160, and its performance is about 80 fps for 768 × 512 pixel images.

Image segmentation is one of the most important tasks in the image processing. The level set method is a powerful algorithm for the segmentation. In the level set method, a three-dimensional auxiliary function is used for detecting objects of various shapes. Its computational complexity is, however, very high, and many techniques have been proposed to reduce the computational complexity. In this paper, we describe a new algorithm for the level set method and its FPGA implementation. This algorithm is (1) designed so as to allow deep pipelining on hardware systems, and (2) able to detect all objects in the image, which is difficult for previous level set algorithms. We have implemented the algorithm on Xilinx XC4VLX160, and its performance is about 700 fps for 640 × 480 pixel images.

Formal verification is one of the most important applications of the satisfiability (SAT) problem. WSAT and its variants are one of the best performing stochastic local search algorithms. In this paper, we propose an FPGA solver for SAT-encoded verification problems based on a WSAT algorithm. The size of the verification problems is very large, and most of the data used in the algorithm have to be placed in off-chip DRAMs. The performance of the solver is limited by the throughput and access delay of the DRAMs, not by the parallelism in FPGA. We show how much speed-up is possible under this situation using the memory throughput, memory access delay and the operational frequency of FPGA as parameters.

Mean shift algorithm is a procedure which is often used for color image segmentation. Its computational cost, however, is very high, and many techniques for reducing the cost have been researched. This paper describes an approach for real time processing of a mean shift algorithm using an FPGA. In our approach, the image is scanned from top to bottom (or bottom to top), and L lines around the target line are buffered on the FPGA, and the pixels on the target line can be processed efficiently using the buffered pixels. When the pixels are shifted out of the L lines, they are put in queues, and processed afterward. In our circuit, the processing of several pixels is interleaved to hide the delay caused by the long feedback in the mean shift filter. A technique to reduce the number of on-chip memory banks used for storing the L lines is also introduced. The performances of our circuit for 768×512 pixel images is 50 to 130 fps according to the size of the mean shift filter.

The satisfiability (SAT) problem is to find an assignment of binary values to the variables which satisfy a given clausal normal form (CNF). Many practical application problems can be transformed to SAT problems, and many SAT solvers have been developed. SAT problem is, however, NP-complete and its computational cost is very high. In order to reduce the computational cost, preprocessors are widely used by SAT solvers. In this paper, we describe an approach for implementing a preprocessor (SatELite) on FPGA. In SatELite, the variables and clauses whose values can be uniquely determined from other variables and clauses are eliminated to reduce the search space of the given SAT problem. The algorithms used in SatELite have inherent parallelism, but the data size of the SAT problems is very large, and the performance of the system is limited by the throughput of the off-chip DRAM banks. In our implementation, several clauses are held on the FPGA, and are compared in parallel with a sequence of new clauses. The sequence is cached on the FPGA, and reused in order to hide the access delay to the DRAM banks. The speedup by our system depends on the problem size, however it becomes higher for larger problems.

Contrast limited adaptive histogram equalization (CLAHE) is a technique to enhance the visibility of local details of an image by increasing the contrast in local regions. In CLAHE, the enhancement is controlled to avoid excess amplification of the noises in the local regions. CLAHE computes several histograms of intensity values, each corresponding to a distinct region of the image, distributes the histograms to avoid the excess amplification, and remaps the intensity values using the distributed histograms. In this paper, we propose an approach for real-time computation of CLAHE using an FPGA. In our system, (1) a histogram is generated for each pixel in a image, and the intensity of only the pixel is remapped using the histogram to generate smooth images, and (2) each histogram is speculatively distributed without iterations by feeding back the distribution result of its previous pixel. With this approach, we can achieve real-time processing of HD images.

SAD (sum of absolute differences) is a technique for evaluating the similarity between two same size regions, and widely used in stereovision, optical flow, motion estimation and so on. In these applications, a given image is scanned using a fixed size region (window), and the window is compared with the same size regions in another image. When the window is overlapped for generating a dense map, we have several implementation alternatives; storing the partial sums for reusing them afterward or recalculating them when they become necessary, scanning left to right or top to bottom, and dividing the search space horizontally or vertically. With the combination of these alternatives, we can implement a wide range of circuits. In this paper, we evaluate the performance and the size of those circuits, and makes it clear which circuit fits which type of FPGA.

In this paper, we describe an approach for detecting patterns in various size and angle using FPGA. In many approaches, features of a given pattern which are invariant to scaling and/or rotation are defined in advance, and those features are searched in a given image. These approaches make it possible to narrow down the candidate regions with less computational cost, but the sensitivity depends on how to define the features. In our approach, the image is downscaled by αkand αlalong the x and y axes (k, l = 0, 1, 2, ..., n), and the regions in the downscaled images are compared with several sequences of the templates which are generated from the given pattern using direct cross-correlation. This approach requires high computational cost, but by calculating the cross-correlations incrementally starting from the nonrotated pattern, it becomes possible to detect the rotated patterns in various size and angle with one FPGA.

In this paper, we propose an approach for full-search variable block size motion estimation using an FPGA. In the motion estimation, the current frame is divided to macro-blocks, and the best matching block is searched for each macroblock in the search area of the reference frame. In our approach, the scan direction of the macroblock in the current frame, and the scan direction of the matching in the search area are optimized in order to reduce the access to the off-chip memory banks which stores the reference frame, and the on-chip memory banks which cache the search area. By reducing both memory accesses, it becomes possible to realize high performance on a small size FPGA.

In this paper, we propose an approach for detecting line segments in real-time by merging fixed-size short line segments. In many hardware systems, a Hough Transform has been used for detecting line segments. The Hough Transform is robust to noises, but it requires large memory space, and more space is required for images with higher resolution. Line detection is a primitive task which is frequently used for higher-level image processing. Therefore, it is important to detect the line segments using a small circuit with less on-chip memory. Our circuit based on the merging of fixed-size short line segments is small (9.2K LUTs), and uses only 6 block RAMs. Its performance is 200 fps for 640 × 480 pixel images.

WSAT and its variants are one of the best performing stochastic local search algorithms for the satisfiability (SAT) problem. In this article, we propose an approach for solving large 3-SAT problems on FPGA using a WSAT algorithm. In hardware solvers, it is important to solve large problems efficiently. In WSAT algorithms, an assignment of binary values to the variables that satisfy all clauses is searched by repeatedly choosing a variable in an unsatisfied clause using a heuristic, and flipping its value. In our solver, (1) only the clauses that may be unsatisfied by the flipping are evaluated in parallel to minimize the circuit size, and (2) several independent tries are executed at the same time on the pipelined circuit to achieve high performance. Our FPGA solver can solve larger problems than previous works with less hardware resources, and shows higher performance.

Many applications in image processing have high inherent parallelism. FPGAs have shown very high performance in spite of their low operational frequency by fully extracting the parallelism. In recent micro processors, it also becomes possible to utilize the parallelism using multi-cores which support improved SIMD instructions, though programmers have to use them explicitly to achieve high performance. Recent GPUs support a large number of cores, and have a potential for high performance in many applications. However, the cores are grouped, and data transfer between the groups is very limited. Programming tools for FPGA, SIMD instructions on CPU and a large number of cores on GPU have been developed, but it is still difficult to achieve high performance on these platforms. In this paper, we compare the performance of FPGA, GPU and CPU using three applications in image processing; two-dimensional filters, stereo-vision and k-means clustering, and make it clear which platform is faster under which conditions.

Local contrast enhancement is a technique to enhance the visibility of local details of an image by increasing the contrast in local regions. Adaptive histogram equalization (AHE) is a method for the local contrast enhancement. AHE computes several histograms of intensity values, each corresponding to a distinct region of the image, and uses them to redistribute the intensity values. AHE is very computationally intensive and not acceptable for most applications. In this paper, we propose a method for real-time computation of AHE using an FPGA. In our system, a histogram is generated for each pixel in a image, and the intensity of the pixel is remapped using the histogram. The computational complexity of this approach is very high, but it can generate smooth enhanced images without using interpolation techniques. By reusing partial histograms by temporarily storing them in on-chip memory banks, and by adding/subtracting all bins in the histograms in parallel, we can achieve real-time processing of HD images using an FPGA. This high performance becomes possible because of the very high memory bandwidth of on-chip memory banks of FPGA.

This paper describes an implementation of HMMER with FPGA. HMMER is one of the most used software tools for sensitive profile HMM (Hidden Markov Model) searches of biological sequence databases. HMMER is a very CPU-intensive program. In HMMER, the Viterbi algorithm, which is a quadratic dynamic programming algorithm, is used to align a profile HMM and a protein sequence. In the profile HMM, a feedback path from the end of the model to the beginning is allowed, and this loop makes it difficult to process the Viterbi algorithm in parallel. In our approach, the alignment is calculated speculatively in parallel, and when the feedback path is selected in the alignment, the alignment is recalculated from the beginning using the fedback score. According to our experiments, the ratio that the feedback path is selected is very low, and the performance loss by the recalculation is less than a few percent. Another problem for accelerating HMMER using FPGA is the large size of the score tables required for profile HMMs. By crossing the search direction in the quadratic search space and the moving direction of each processing unit in the search space, we can minimize the size of the memory banks for storing the score tables. This optimization technique makes it possible to process all profile HMMs in a database efficiently.

In image processing, FPGAs have shown very high performance in spite of their low operational frequency. This high performance comes from (1) high parallelism in applications in image processing, (2) high ratio of 8 bit operations, and (3) a large number of internal memory banks on FPGAs which can be accessed in parallel. In the recent micro processors, it becomes possible to execute SIMD instructions on 128 bit data in one clock cycle. Furthermore, these processors support multi-cores and large cache memory which can hold all image data for each core. In this paper, we compare the performance of FPGAs with those processors using three applications in image processing; two-dimensional filters, stereo-vision and k-means clustering, and make it clear how fast is an FPGA in image processing, and how many hardware resources are required to achieve the performance.

In this paper, we describe an approach for downscaling images for real-time pattern detection on FPGA. Using FPGAs, we can reconfigure specific circuits for given patterns, and detect various patterns efficiently with less hardware resources. In our approach, a sequence of downscaled images (downscaled by alphak(k = 0, 1, 2, ..., n)) is generated, and regions in each image are compared with fixed size templates in order to detect patterns of various sizes in the original image. In this downscaling process, we need to (1) maintain the quality of the downscaled images, (2) generate them in parallel with the pattern detection, and (3) minimize the unit size and the number of the external memory banks required for the downscaling. In our approach based on an area-averaging method, all downscaled images have the same quality as when generated from the original image, and the computation is completely overlapped with the pattern detection. The downscaling units for alpha3= 1/2 occupy only 3% LUTs of Xilinx XC2V6000, and only one external memory bank is used for downscaling grayscale images.

The watershed transformation is a popular image segmentation technique for gray scale images. In this paper, we describe an implementation method of a watershed algorithm based on connected components on FPGA. In the watershed algorithmbased on connected components, regular memory accesses by raster scans and irregular memory accesses using FIFO and stack are repeated. The irregular memory accesses can not be scheduled in advance, and the memory access delay makes it difficult to achieve high performance on hardware systems. In our implementation, large data structures used in the algorithm are placed in the external memory banks redundantly to allow parallel accesses to them, and are accessed as read or write-only to hide the access delay. Frequently accessed small data structures are placed in the internal memory banks, and the accesses to them are arranged so that the maximum parallelism can be exploited. By this data allocation, the access delay to the external memory banks can be hidden, and eight pixels (or four depending on the phase of the algorithm) can be processed in parallel.

WSAT and its variants are one of the best performing stochastic local search algorithms for the satisfiability (SAT) problem. In this paper, we propose an FPGA solver for very large SAT problems based on a WSAT algorithm. In our solver, parallel and multi-thread processing are combined (1) to fully utilize parallel accesses to external memory banks, and (2) to enhance the utilization of internal memory banks by fully utilizing their dual-port accesses, in order to solve very large problems on the pipelined circuit. Our solver on Xilinx XC2V6000 can solve problems up to 32K variables and 128K clauses, which is more than ten times larger than previous solvers on the same size FPGA.

Multiple sequence alignment problems in computational biology have been focused recently because of the rapid growth of sequence databases. By computing alignment, we can understand similarity among the sequences. In this paper, we describe a compact system with an FPGA board and a host computer for multiple sequence alignment based on Carrillo-Lipman method. In our system, two dimensional dynamic programming is repeatedly applied along other dimensions to realize multidimensional search with a simple and common architecture, and unnecessary parts of the search space for finding the optimal alignment are skipped using Carrillo-Lipman method to reduce the computation time.

The watershed transformation is a popular image segmentation technique for grey scale images. This paper describes a pipeline implementation of a watershed algorithm designed for hardware implementation. In the algorithm, pixels in a given image are repeatedly scanned from top-left to bottom-right, and then from bottom-right to top-left in order to propagate the value of each pixel to its neighbors. In the implementation, w-sets of k-lines are buffered on the FPGA, and the algorithm is repeatedly applied to w-sets, shifting in a new set from the external memory banks and shifting out the oldest set to other external memory banks, w and k can be chosen according to the number of the external memory banks and the size of the FPGA. Therefore, it is possible to realize the best performance on a given hardware platform.

A method is described for enumerating the frequencies of DNA subsequences on a system comprising a host computer and a field programmable gate array (FPGA) board with one FPGA. Frequencies of subsequences with lengths of up to K0+ K1+ K2(24 in the current implementation) are enumerated in three phases. In these three phases, subsequences with lengths of up to K0, K0+ K1, and K0+ K1+ K2, respectively, are enumerated; these three phases are executed simultaneously on a pipelined circuit, resulting in high performance. The enumeration of frequent subsequences in databases, which are becoming larger and larger, will enable subsequences that are unique and/or repeatedly used in many parts of the sequences to be found.

The computational complexity of a two-dimensional filter is basicallyO(NtimesN) (Nis the size of the filters), though in some filters in which coefficients can be separated as to x and y axes {separable), the complexity can be reduced to O(N) by decomposing a filter to two one-dimensional filters. The computation time of non-separable filters becomes very long for large N even with hardware systems. In this paper, we propose an approach for applying large non-separable filters on large images using an FPGA. Our current targets are circularly symmetric filters whose coefficients on same concentric circles are the same. In our approach, regular polygons inscribed in those circles are used to approximate them. With this approach, the computational complexity can be reduced to O(N). A circuit based on this approach was implemented on Xilinx XC2V6000. It can apply filters more than N = 127 in one clock cycle to each pixel in an given image, which makes it possible to achieve real-time processing of HD images.

In this paper, we describe a segmentation method of color images based on the k-means clustering. With a k-means clustering algorithm, we can reduce the number of colors in a given image to K while maintaining the quality of the image. Based on these K colors, we can segment color images by recognizing contiguous pixels of the same color as a region. However, the k-means clustering is a very time consuming task, particularly for large size images and large number of clusters. Therefore, in order to use a k-means clustering algorithm for image segmentation, we need to recognize the regions in parallel with the k-means clustering algorithm. In our implementation, the regions can be recognized in parallel with each iteration of the k-means clustering algorithm.

WSAT and its variants are one of the best performing stochastic local search algorithms for the satisfiability (SAT) problem. In this paper, we propose an FPGA solver for large SAT problems based on a WSAT algorithm. In hardware solvers, it is very important to solve large problems efficiently. In previous hardware solvers, all clauses are evaluated in parallel using the evaluators of the same number as the clauses to achieve high performance. In our solver, (1) only the clauses whose values will be changed are evaluated in parallel to minimize the circuit size, and (2) four independent tries are executed at the same time on the pipelined circuit to achieve high performance. Our FPGA solver can solve much larger problems than previous works with less hardware resources, and shows higher performance. The solver on XC2V6000 can solve problems up to 2000 variables and 8500 clauses.

K-means clustering is a very popular clustering technique, which is used in numerous applications. In the simple k-means clustering algorithm, each point in the dataset is compared with centers of all clusters. This comparison is a very time consuming task, particularly for large dataset and large number of clusters. In order to achieve high performance, we need to filter out clusters which have to be compared with each point efficiently. In this paper, we describe an FPGA implementation of k-means clustering for color images. In our implementation, clusters are filtered out using kd-trees which are dynamically generated on the FPGA in each iteration of k-means clustering. With one XC2V6000, the performance for 512 times 512 and 640 times 480 pixel images (24-bit full color RGB) is more than 30 fps, and 20 - 30 fps for 756 times 512 pixel images in average when dividing to 256 clusters

This paper describes an implementation of a parallel and pipelined watershed algorithm on FPGA. In the algorithm, pixels in a given image are repeatedly scanned from top-left to bottom-right, and then from bottom-right to top-left. Because of these simplified memory accesses, N pixels in a given image can be processed in parallel by reading N lines at the same time. However, N is limited by the number of external memory banks that store image data. In our implementation, in order to achieve high performance using an FPGA with limited number of external memory banks, (1) a given image is divided to K regions, (2) several of them are cached on the FPGA, (3) the watershed algorithm is applied on those regions, and (4) the next (or previous) region is loaded to the FPGA during the computation to hide the loading time. In our current implementation on XC2V6000, up to 32 pixels can be processed in parallel. The performance for 512 × 512 pixel images is about 3-4 msec, which is fast enough for real-time applications.

WSAT and its variants are one of the best performing stochastic local search algorithms for the satisfiability (SAT) problem. In this paper, we propose a new FPGA solver for WSAT algorithms. The features of our solver are (1) high parallelism by small size units to evaluate clauses in each instance of the SAT problem, (2) multi-thread execution to achieve high performance, and (3) fast data-downloading for each instance. We implemented the solver for problems up to 256 variables and 1024 clauses on XC2V6000, and it used 45% of slices and live block RAMs. Our implementation shows higher performance over previous SAT solvers on FPGAs.

Alignment problems in computational biology have been focused recently because of the rapid growth of sequence databases. By computing alignment, we can understand similarity among the sequences. Many systems for alignment have been proposed to date, but most of them are designed for two-dimensional alignment (alignment between two sequences). In this paper, we describe a compact system with an off-the-shelf FPGA board and a host computer for more than three-dimensional alignment based on dynamic programming. In our approach, high performance is achieved (1) by configuring optimal circuit for each dimensional alignment, and (2) by two phase search in each dimension by reconfiguration. In order to realize multidimensional search with a common architecture, two-dimensional dynamic programming is repeated along other dimensions. With this approach, we can minimize the size of units for alignment and achieve high parallelism. Our system with one XC2V6000 enables about 300-fold speedup as compared with single Intel Pentium 4 2GHz processor for four-dimensional alignment, and 100-fold speedup for five-dimensional alignment.

In this paper, we describe a compact system for real-time generation of three-dimensional motion fields. Our system consists of one FPGA, two cameras and one host processor. With our system, we can generate dense three-dimensional motion fields (640 /spl times/ 480 vectors in a standard size image) at video-rate from dense optical flow and dense depth map obtained by area-based matching. The performance can be improved up to 840 frames per second in small size (320 /spl times/ 240) images by configuring another circuit, though it requires more amounts of hardware resources. By changing search spaces for optical flow and depth map by reconfiguration, we can control the maximum motion speed which can be detected, and the minimum distance to moving objects in the image, under limited hardware resources.

High performance, low cost and compact specialized hardware for tsume-shogi (shogi problems) has been developed with a field-programmable gate array (FPGA). Developing dedicated hardware systems is an essential approach to improve the playing strength of shogi programs. However, inflexibility and high cost of hardware have been significant problems in development of the systems. An FPGA gives solutions to the problems of hardware implementation. To devise parallel and pipeline architecture of shogi hardware and test the feasibility of an FPGA for shogi, we first implemented a tsume-shogi solver. With the latest FPGA, we successfully implemented all of the highly parallelized modules on a single chip. The hardware tsume-shogi solver achieved about 11 times higher performance than software on Pentium4-2.53 GHz. The devised architecture can be also applied for normal shogi.

We describe a compact circuit for real-time detection of line segments using the line Hough transform (LHT). The LHT is a technique to find out lines in an image. The LHT is robust to noises, but requires long computation time. The circuit calculates: (1) r and /spl theta/ of lines (r is the distance from the origin to a line and /spl theta/ is the angle of the line) by the LHT units in parallel; and (2) start and end points of the lines by the other units which are completely pipelined with the LHT units. With this parallel and pipeline processing, the circuit can detect more than 16384 lines (/spl pi//512 angle steps) in a large size image (640 /spl times/ 480) in real-time. The size of the circuit is 19% of XC2V6000, which makes it possible to implement other circuits for higher level processing of object recognition on the same chip, or the performance can be improved up to four times by using four times of the hardware resources.

After the success of DEEP BLUE in computer chess, shogi, or Japanese chess is a next challenging target in artificial intelligence for game playing. The complexity and huge search space of shogi have been motivating researchers to make shogi programs, but none of them is competent enough to play against human experts. To improve the competence of shogi programs, it is a promising approach to develop dedicated hardware systems. However inflexible architecture and lack of hardware resource have been the significant problems in hardware development. The flexibility and recent progress in the gate size of FPGAs are expected to give solutions to the problems. As a first step to shogi hardware, we implemented modules to generate check and defense moves in tsume-shogi, or mating problems in shogi. With the latest FPGA, we successfully implemented all modules on a single chip and eliminated the bottleneck of memory bandwidth. In this paper we describe a procedure for parallel move generation in tsume-shogi hardware and architecture of the modules implemented on an FPGA. A discussion about the performance of the hardware is also included in the paper. The hardware is roughly estimated to work 10-50 times faster than software.

We describe an operation support system (OSS) architecture for network element (NE) allocation in optical access networks (OANs). Deploying OAN elements to meet all customer demand would be very costly because access networks are extend in many directions. To reduce this cost, it would be necessary to only install enough NEs to meet the current demand, and to allocate suitable elements during the process of service delivery. Because OANs consist of several elements, it is also necessary to control the sequence of element allocation and re-allocation. Therefore, an allocation integration function to control the allocation processes is necessary, as well as functions for each NE allocation. We have developed an OSS architecture that meets these requirements. We have also determined the most efficient allocation process for allocating OAN elements.

In this paper, we show a compiler that generates high speed pipeline circuits for loop and recursive programs written in C programming language, which are the most time exhaustive parts in many application problems. The compiler has following features. First, all operations (except for memory accesses) are divided into cascades of 8-bit width (at maximum) operations in order to achieve high speed clock cycle. Second, in order to fulfil the pipeline, variables that have data feedback dependencies between loop cycles are specially scheduled based on several kinds of optimizing techniques. Furthermore, computations of each loop cycle are speculatively started in every clock cycle even if an array on the same memory bank may be accessed more than once in a loop cycle and there may be data feedback dependencies caused by the array accesses. When the array is accessed more than once, the pipeline is stalled while the array access operations are executed sequentially, and when the feedback dependencies are detected, the speculative computations are cancelled, and restarted after the updates of array are finished. Experiments on simple combinatorial programs showed that the pipeline circuits generated by the compiler run about 39-47 MHz on ALTERA EPF10KA serious (which is as fast as hand optimized circuits), and the speed up by the speculative execution is more than two.