=Paper=
{{Paper
|id=Vol-1981/paper5
|storemode=property
|title=Seam Line Optimization for Remote Sensing Image Mosaicking Based on Graph Shortest
Path Finding
|pdfUrl=https://ceur-ws.org/Vol-1981/paper5.pdf
|volume=Vol-1981
|authors=Andrew Sudorgin
}}
==Seam Line Optimization for Remote Sensing Image Mosaicking Based on Graph Shortest
Path Finding==
https://ceur-ws.org/Vol-1981/paper5.pdf
Seam Line Optimization for Remote Sensing Image
Mosaicking Based on Graph Shortest Path Finding
Andrew Sudorgin
Joint-Stock Company Research Institute of Precision Instruments (JSC RI PI)
Moscow, Russia
andrew.sudorgin@gmail.com
Abstract and, in some sense, contradictory restrictions on the
behavior of the seam line are superimposed in the
Seam line determination is important step of construction of photographic plans and mosaic of im-
remote sensing image mosaicking. Automatic ages: a seam line must not cross high-altitude objects,
seam line selection problem using graph short- seam line must cross linear objects perpendicularly
est path finding is discussed in this paper. and should be inside low-informativeness areas [1]. It
Approaches to graph construction from image is not easy task to satisfy all those criteria completely,
similarity cost function, graph memory lay- especially when editing by hand.
out and parallel seam line optimization using
shortest path on graph are presented. 2 Related Work
Keywords: remote sensing data processing, There are some different approaches for seam line cre-
image mosaic, seamless coverage, optimiza- ation:
tion
• Draw seam line along image borders (no optimiza-
tion);
1 Introduction • Central image area maximization;
Acquisition of holistic image of a certain territory in • Draw seam line inside areas with maximum simi-
the form of a mosaic from various (in the sense of ge- larity.
ometry and brightness-contrast) separate images is an Draw seam line along image borders is used when there
important problem when processing satellite and aerial are no quality demands to resulting image mosaic, or
photos. Wide range of remote sensing equipment with there are strict time limitations. Since brightness and
unique spectral sensitivity, variation of angle of view, geometrical distortions of remote sensing images are
position of the Sun and atmosphere condition, non- minimal in their central areas we can draw seam line
simultaneous image acquisition cause unique deforma- as close to image center as possible using Voronoi poly-
tion of the image of object of interest. Such a large gons [2]. This approach is helps to avoid of image
number of negative factors means that it is practically margin brightness inequality and to include central ar-
impossible to compose the images, both from a geo- eas with minimal geometry distortions to final mosaic.
metric point of view, and from the point of view of However, the first two approaches completely do not
radiometric conditions. One of the solutions of the take into account the properties of the input images.
described problem when seamless mosaic is created is Optimal seam line detection methods are based on
optimal seam line detection within overlapping image the search of the pixels with minimal differences in
regions. brightness, gradient and some other parameters which
To obtain a visually qualitative result that does are calculated from the image overlap regions (inter-
not introduce distortions into the information, strict sections of image pairs in coordinate system of an out-
put image). Seam line being determined is a base
Copyright c by the paper’s authors. Copying permitted for
private and academic purposes.
for united mosaic from several initial images. In this
In: V. Voevodin, A. Simonov (eds.): Proceedings of the
case the visual divergence is significantly eliminated.
GraphHPC-2017 Conference, Moscow State University, Russia, Many approaches bring optimal seam line determi-
02-03-2017, published at http://ceur-ws.org. nation problem to energy function minimization. In
1
some articles normalized cross correlation (NCC) [3,4], where I0 (x, y) and I1 (x, y) denote the brightness on
texture analysis [6, 7], image differences [6], morpho- the first and second overlapping images in the (x, y)
logical analysis [8] are suggested as a energy func- position (here and later we assume that (x, y) is a
tion. In order to create energy cost function some pixel coordinates (row/column) of input images in
authors also use vector roads graph [9] and digital sur- coordinate system of output mosaic and all geome-
face model [10]. The following algorithms are used try transformations, including nonlinear ones, already
as optimization: snake model [6, 11], Dijkstra‘s algo- have been done at geometry align step).
rithm [3,4,5], Floyd-Warshall algorithm, dynamic pro- To define informativeness matrix Wi Moravec [19]
gramming, graph cuts [12, 13]. algorithm is used. According to this algorithm, we
Even though in practice, graph cuts algorithms calculate the changes in the average brightness value
have computational complexity close to linear [14, 15] of the image of a small fragment around the point of
and there are parallel approaches that allow process- interest when the fragment is shifted by one pixel in
ing graphs that are larger than the available RAM four directions (horizontal, vertical and diagonal) and
[16], they remain relatively slow, since a much larger choose among them the minimal value, which is the
amount of RAM is required for the solution. For ex- measure of the informativeness of the image. Thus,
ample, one of the fast realizations of the graph cut al- fragments of the image with a small brightness vari-
gorithm requires memory several times more than the ation are marked as low-informative, and with high
graph itself takes, since it is required to store and pro- variation, as highly informative. Total informativeness
cess not only edge weights, but also forward/backward Wi (x, y) is the sum of each overlapping image informa-
edge capacity and other auxiliary values [17]. tiveness. By drawing a seam line in places with a low
Due to the fact that the solution of optimization value of the Moravec’s operator of interest, we will sat-
problems on graphs is associated with high computa- isfy the requirement [1] of carrying out the seam line
tional complexity, a number of authors try to simplify in places of image with low informativeness.
the structure of the graph, leading to a reduction in In order for the seam line to cross the line objects
the time of solving the problem at the cost of a slight along a line close to the perpendicular and not inter-
degradation in quality [18]. sect the high-altitude objects, we introduce the matrix
The main contribution of this paper is a new ap- of forbidden zones. To create forbidden zone matrix
proach to seam line optimization with low memory Wr (x, y) we rasterize vector lines and polygons, which
consumption and a high degree of parallelism. represent linear extensive and high-altitude objects,
using specially defined penalty coefficients for cross-
3 Approach to Seam Line Optimiza- ing those objects. Due to the fact that the seam line
tion receives an additional penalty when crossing objects
marked in matrix Wr (x, y), the optimization algorithm
To achieve a visual invisibility of the seam line the will try to bypass such objects or cross them along the
value of the pixels of overlapped images must coincide line of the minimum possible length, that for thin elon-
at points with the same coordinates in geographic co- gated objects (roads, rivers) will be perpendicular.
ordinate system (or coordinate system of output image Resultant energy function defined as a weighted
for non georeferenced mosaic). Seam line optimization sum of the particular matrices:
is one of steps of remote sensing image mosaicking.
Normally, it follows after geometry alignment and ra- W (x, y) = αWs (x, y) + βWi (x, y) + γWr (x, y), (2)
diometric correction of input images. We expect that where α, β, γ are the weighting coefficients, which de-
these two steps have already been correctly done, but fined each matrix contribution. In most cases, we can
not ideally due to some reasons and we need to elimi- choose all weights to be the same, but if one wants to
nate the remaining visual inconsistencies. amplify one of the constraints, the corresponding co-
efficient can be increased. For example, if the visual
3.1 Energy Cost Function similarity of images is more important to us, then we
In this article to create optimal seam line we propose increase α, and if it is more important for us to draw
to build energy cost function comprised of three func- the seam line in places with low informativeness, then
tions: the image similarity matrix Ws , the image infor- we increase the β coefficient, if we want to completely
mativeness matrix Wi and the forbidden zone matrix prohibit the intersection of linear and high-altitude ob-
(linear extensive, high-altitude and other visually ob- jects, we can set the coefficient γ close to infinity.
vious foreground objects). The similarity matrix Ws Thereby, seam line, which was delineated along the
is calculated as follows: path with minimal energy cost sum, meet the seam
line principal criteria: do not intersect high-altitude
Ws (x, y) = (I0 (x, y) − I1 (x, y))2 (1) objects, linear objects should be intersected along the
2
shortest distance (perpendicularly), and the other ob- where first term is a memory amount to store graph
ject should be intersected in the areas with maximum nodes, second term is memory amount to store graph
similarity and minimum informativeness. edge pointers and third term is memory for edge
weights, SP tr is node/edge pointer size (usually 4 or 8
3.2 Graph Data Structure Design byte), Se is size of edge weight.
For optimal seam line determination we define energy When we store and use the graph in the described
function as weighted graph. Each node of the graph implicit way, it is possible to reduce memory usage by
SP tr +SP tr Pconn +Se Pconn
represents corresponding energy function matrix ele- Se times. When 8 byte pointers
ment. Let us connect all graph nodes to their neigh- and eight- connected graph are used, it is possible to
bors, here we have two options: four- and eight- con- reduce the RAM usage by a factor of 44 in comparison
nected graph (Figure 1). We define the weight of the with the CSR graph storage type.
edge between energy matrix cells (x1 , y1 ) and (x2 , y2 ) With this approach to storing the graph and when
as the sum of weights in the corresponded nodes mul- combined with the block method of storing the energy
tiplied by the distance between them: matrix W (x, y) in memory, the processor cache is more
efficiently used, since when a graph is traversed, most
ω(x1 y1 → x2 y2 ) = nodes connected by edges are in the adjacent memory
p cells.
[W (x1 , y1 ) + W (x2 , y2 )] (x1 − x2 )2 + (y1 − y2 )2 Moreover, the block storage of the energy matrix
(3) W (x, y) allows us to calculate and load matrix blocks
Thereby energy function matrix of M × N size is rep- as we use at the optimization algorithm, which further
resented by flat graph consisted of M N nodes and reduces the algorithm’s requirement for the amount of
Pconn M N edges (where Pconn is a connection amount memory and allows us to process images larger than
of energy matrix elements). Such a construction of the the available RAM.
graph allows us not to store the graph explicitly, but
to build it as necessary from the energy matrix on the 3.3 Hierarchical Processing
fly. Typical satellite image size is about 50000 × 100000
pixels. When seam line between two images is created,
we deal with the graph of 109 nodes and 1010 edges.
To avoid processing the entire array of data, we
apply a hierarchical approach to image processing.
In the first step, we construct optimal seam line at
the overview level of the original images (Figure 2). To
do this, we calculate the coordinates of the points of
intersection of the image frames in the coordinate sys-
tem of the output image (Vb and Ve ), read input images
from the overview levels of detail, build a coarse en-
a) Four-connectivity b) Eight-connectivity ergy matrix and run the optimization process between
Figure 1: Four- and eight-connectivity of the pixels the graph nodes corresponding to the points of inter-
used to create energy function graph in the overlapped section of the image frames. As a result, we obtain
image regions a coarse approximation of the seam line (blue poly-
line with black vertices). In the case where the image
Let us consider in more detail. The amount of frames are not convex polygons and the intersection
memory required to store the energy function matrix result is a multipolygon, each part of the multipoly-
W (x, y) is: gon is processed independently.
Sw = Se M N, (4) In the second step, we will refine the seam line be-
where Se is the size of one matrix element. Major- tween the vertices of the seam line obtained on an
ity of the Earth remote sensing photos are 16 bit per overview scale. To do this, we construct the fine en-
channel images, therefore it is reasonable to use similar ergy matrix using fragments of input images from the
approach to energy matrix storage data type (Se = 2). detailed level and perform the optimization process
The amount of memory required to store the graph ex- again, taking as the initial and final nodes of the graph,
plicitly in the form of compressed sparse row matrix those that correspond to the vertices of the coarse seam
(CSR) is: line. Note that to carry out the optimization, it is not
necessary to build the entire energy matrix W (x, y),
Scsr = SP tr M N + SP tr Pconn M N + Se Pconn M N, (5) but only the part that is near the coarse approxima-
3
Image #1 Image #2
Ve
Image blocks
that is being
processed
Refinement area
around overview seam-line
Seam-line obtained on an overview scale
Seam-line obtained on a detailed scale
Vb
Seam-line refined on a detailed scale
Figure 2: Optimal seam line determination for two overlapped images
tion of the seam line. Moreover, each image fragment
can be processed in parallel. Data: W (x, y), Vb , Ve
But the new seam lime will have fractures near the Result: S - optimal seam line vertices
vertices of the coarse seam line, because end point ver- 1 D.f ill(inf); P.f ill(inf);
tices of seam lime, are rigidly fixed. To eliminate un- 2 D[Vb ] ← 0;
wanted fractures, we will carry out the third stage of 3 QM LB .insert(0, Vb )
the seam line refinement on a detailed scale. To do 4 while QM LB not empty do
this, we will take as a initial and final nodes of the 5 c ← q.extractM in()
graph, those that correspond to the midpoints of the 6 for p = 0; p < Pconn ; ++p do
segments, obtained in the second step, and we will per- 7 n ← c + Ap
form optimization again. Thus, we obtain a seam line, 8 // Compute edge weight according to (3)
unnoticeable both at the detailed and at the overview 9 ω ← (W (cx , cy ) + W (nx , ny ))length(Ap )
scale (Figure 2). 10 d ← D(cx , cy ) + ω
11 if d < D(nx , ny ) then
3.4 Optimization 12 if P (nx , ny ) is not set then
13 q.insert(d, n)
For optimization we use the shortest path Dijkstra‘s
14 else
algorithm [20] with the Goldberg modification [21].
15 q.decreaseKey(d, n)
The best implementation of Dijkstra’s shortest path
16 end
algorithm with Fibonacci heap has a running time
17 D(nx , ny ) ← d
O(m + nlog(n)), where n is graph node count, m is
18 P (nx , ny ) ← p
graph edge count. Goldberg’s shortest path algorithm
19 end
with multi-level bucket has an average running time
that is linear, and a worst-case time of O(m+nlog(C)) 20 end
21 end
where C is a ratio of the biggest graph edge weight
22 S ← turnBack(P, Ve )
to the smallest nonzero graph edge weight. Since the
graph constructed from the energy matrix has a re- Algorithm 1: Pseudo code of the optimization al-
striction on the maximum weight of the edge, this gives gorithm taking into account structure of the graph
us a significant advantage in the running time.
4
Implementation details taking into account the pro- Data: I1 - first image, I2 - second image
posed structure of the graph are given in the Algorithm Result: S - optimal seam line vertites
1. The input data for the algorithm are energy func- 2 O1 , O2 ← readImageOverview(I1 , I2 );
tion matrix W (x, y) and Vb , Ve – start and end points. 3 Vb , Ve ← computeIntersectionP oints(I1 , I2 );
Note that the coordinates of the corresponding mo- 4 Wcoarse ← computeEnergy(O1 , O2 );
saic pixels are used as pointers to the nodes of the 5 Scoarse ← shortestP ath(Wcoarse , Vb , Ve );
graph. In addition to the input data, the algorithm 7 B ← splitP athT oBlocks(Scoarse );
uses several important internal structures. D(x, y) is 9 for step = 2; step <= 3; ++step do
distance the matrix from the start node to each other. 11 #pragma omp parallel for
The matrix D(x, y) must have a data type that allows 12 for i = 0; i < B.size(); ++i do
storing the sums of the elements of the matrix W (x, y) 13 box ← computeBoundingBox(Bi );
without overflowing. If we assume that the size of 14 Vb , Ve ← computeEndP oints(Bi );
the element of matrix W (x, y) is equal to two bytes, 16 begin #pragma omp critical
then the size of the elements of matrix D(x, y) must 17 F1 , F2 ← readF ineImage(I1 , I2 , box);
be equal to four or eight bytes. A is a possible arc list, 18 end
for four-connectivity case A4 = [←, →, ↑, ↓], and for 19 Wf ine ← computeEnergy(F1 , F2 );
eight-connectivity case A8 = [←, →, ↑, ↓, %, &, -, .], 20 Sf ine,i ← shortestP ath(Wf ine , Vb , Ve );
according to Figure 1. P (x, y) is node’s parent ma- 21 end
trix. Since the graph has an ordered structure and 23 S ← constructP athF romSegments(Sf ine );
each node has four or eight neighbors, we can use the 24 if step == 3 then
arc number in array A as a pointer to the adjacent 25 break;
node. Thus, no more than one byte is needed to store 26 end
the element of the matrix P . QM LB is a multi-level 27 B ← splitP athT oBlocks(S);
bucket data structure. According to the calculations 28 end
in the paper [21], the structure of QM LB requires no 29 return S;
more than O(log(C)) words of memory. Thus, the Algorithm 2: Simplified pseudo code of parallel hi-
total amount of memory necessary for seam line op- erarchical seam line optimization
timization consists of memory sizes for the matrices
W (x, y), D(x, y) and P (x, y), the size of the structure 4 Results
QM LB , can be neglected since log(C) is much smaller Several datasets were used to test hierarchical seam
than the size of the graph in our case. line optimization algorithm:
• Colored (RGB) 8-bit per channel middle resolu-
tion images acquired by Landsat-8 satellite sys-
tem 16000 × 16000 pixels each (Figure 3);
3.5 Parallel Implementation • Colored (RGB) 8-bit per channel high resolution
images acquired by aerial camera 4368×2912 pix-
els each with roads digitized (Figure 5);
We divide the problem into a number of blocks, while
• Panchromatic 16-bit high resolution images ac-
refining the seam line on detailed level, this allow us
quired by Resurs-P satellite system 36000 ×
to process unlimited amount of data and perform par-
105000 pixels size.
allel optimization in each individual blocks of infor-
mation. OpenMP [22] library is used for parallel data The first and second datasets were used to study the
processing. Implementation details are presented in visual quality of the algorithm, and the latter was used
Algorithm 2. Coarse step is done at lines 2-7. After to estimate the performance.
the end of the first step, we divide the received coarse Algorithm was tested on a workstation equipped
seam line into blocks and perform the second and the with a quad-core Intel Core i7 processor and 8 GB
third steps (line 9) of parallel refinement of seam line RAM.
(lines 11-23). Due to the fact that the sizes of the im- Figure 4 shows the output mosaic obtained using
age fragments corresponding to the blocks of the coarse the hierarchical seam line optimization algorithm, it
seam line depend on the shape of the line segment, we can be seen that the seam line is practically indistin-
use the dynamic partition of the problem into parallel guishable both on a coarse scale and on a fine scale.
blocks (line 11). Note, that parallel reading of image The result of the algorithm on high resolution images
data from the disk leads to a decrease in performance, using a vector layer of roads as forbidden zones is
this operation is separated to the critical section (line shown in Figure 6. It can be seen that the seam line
16). crosses the roads as perpendicular as possible. But
5
Figure 4: Output Landsat-8 mosaic (29140×16764 pix-
Figure 3: Middle resolution Landsat-8 images dataset
els size) overview with optimal seam line highlighted
Figure 5: High resolution aerial image dataset with Figure 6: Output mosaic of aerial images with a seam
roads digitized line that bypasses the roads in the optimal way
à
à
100
8
Processing time HsL
Processing time HsL
æ
80
6
60
æ 4-conn. æ
æ 4-conn.
à
à 8-conn. 4 à 8-conn.
40
à à
20 æ
2
à
à
æ
à à æ
0à æ
æ æ æ
106 107 108 109 10 6
10 7
10 8
109
Nodes ð
Nodes ð
a) b)
Figure 7: The dependence of the time of optimal seam line constructing on the number of vertices in the graph,
representing the energy function, (a) one processor with loading entire energy function matrix into memory
(RAM), (b) the proposed algorithm
6
additional restrictions on the seam line in the form of ict.edu.ru/lib/index.php?id_res=4503
forbidden zones lead to the fact that near the zone, (accessed:10.10.2017)
the visual similarity of images on the different sides of
the line is lost. [3] Chon J., Kim H. Seam-line determination for
image mosaicking: A technique minimizing
The dependence of the time for optimal seam line
the maximum local mismatch and the global
constructing on the number of vertices in the graph is
cost. ISPRS Journal of Photogrammetry and
shown in the Figure 7.
Remote Sensing, No. 65 (1), 2010. pp. 8692.
The construction of the seam line for maximum
https://doi.org/10.1016/j.isprsjprs.
size graph, with one-processor version with full data
2009.09.001 (accessed:10.10.2017)
loading into memory was not performed due to high
consumption of memory. As studies have shown, [4] Chon J., Wang J., Slankard T., Ristevski
when constructing an eight-connected graph, the vi- J., High-Quality Seamless Panoramic Im-
sual quality of the seam line is somewhat higher, be- ages. Special Applications of Photogramme-
cause it includes diagonally oriented edges, but the try, ed. Dr. Daniel Carneiro Da Silva, 2012,
processing time increases due to the increase in the InTech http://cdn.intechopen.com/pdfs/
number of edges in the graph and the non-integer 36193.pdf (accessed:10.10.2017)
weight of the diagonal edges. Also on the Figure 7b
it is seen that for the size of graph 109 nodes the pro- [5] Zhao Y., Han T., Feng S., Miao C., Re-
cessing time sharply increases, which is due to the pre- mote Sensing Image Mosaic by Incorporating
dominance of the time of data loading from the hard Segmentation and the Shortest Path. In:
drive over the optimization time. Bian F., Xie Y., Cui X., Zeng Y. (eds) Geo-
Informatics in Resource Management and
Sustainable Ecosystem. Communications in
5 Conclusion Computer and Information Science, vol 398.
In this paper the approach to construct an optimal Springer, Berlin, Heidelberg, 2013 https://
seam line for the Earth remote sensing image mosaic, doi.org/10.1007/978-3-642-45025-9_67
based on the graph shortest path finding is presented. (accessed:10.10.2017)
The construction of an energy function matrix taking [6] Kerschner M., Twin snakes for determining
into account both informativeness and similarity of in- seam lines in orthoimagemosaicking. //
put images is discussed. Graph data structure design IAPRS, Vol. XXXIII, Amsterdam,. 2000. pp.
from an energy matrix is presented, which makes it 1-8. http://geo.tuwien.ac.at/fileadmin/
possible to reduce the amount of RAM. The hierarchi- editors/IPFpublications/mk_isprs2000/
cal parallel implementation of the optimization algo- paper725.pdf (accessed:10.10.2017)
rithm is presented with regard to the proposed graph
data structure. The amount of RAM required for the [7] Adrov V.N., Drakin M.A., Sechin A.Y., High
optimization process is estimated. performance photogrammetric processing on
The proposed hierarchical image processing ap- computer clusters. // International Archives
proach not only allows us to reduce a seam line con- of the Photogrammetry, Remote Sensing
struction time, but also to make seam line unnoticeable and Spatial Information Sciences, Volume
both at the detailed and at the overview scale of the XXXIX-B4, XXII ISPRS Congress. Mel-
output mosaic. Using proposed approach, the time for bourne, Australia. 25 August 01 September
optimal seam line creation was reduced by more than 2012. pp. 109-112. http://dx.doi.org/10.
10 times, which make it possible to produce seamless 5194/isprsarchives-XXXIX-B4-109-2012
image mosaic with minimal CPU time usage. (accessed:10.10.2017)
[8] Bielski C., Grazzini J., Soille P., Automated
References Morphological Image Composition for Mosaic-
ing Large Image Data Sets. // Spatial Data
[1] Federal Service of Geodesy and Cartography of Infrastructures Unit Institute for Environment
Russia., Instruction on photogrammetric work and Sustainability DG Joint Research Centre,
in the creation of digital topographic Maps and European Commission I-21020 Ispra, (Va),
plans, Moscow, 2002. Italy. pp. 1-4. https://doi.org/10.1109/
IGARSS.2007.4423743 (accessed:10.10.2017)
[2] Skvortsov V.A., The Delaunay Trian-
gulation and Its Applications. Tomsk. [9] Wan Y., Wang D., Xiao J., Lai X., Xu J.,
Univ. Press, 2002. 128 p. http://www. Automatic determination of seamlines for
7
aerial image mosaicking based on vector roads [16] Y. Boykov and A. Delong, A Scal-
alone. // ISPRS Journal of Photogrammetry able Graph-Cut Algorithm for N-D Grids.
and Remote Sensing, No. 76, 2013. pp. 1-10. In IEEE Conference on Computer Vision
https://doi.org/10.1016/j.isprsjprs. and Pattern Recognition (CVPR), Anchorage,
2012.11.002 (accessed:10.10.2017) June 2008 https://doi.org/10.1109/CVPR.
2008.4587464 (accessed:10.10.2017)
[10] Chen Q., Sun M., Hu X., Zhang Z. Automatic
Seamline Network Generation for Urban Or- [17] F. R. Schmidt, E. Toppe, D. Cremers,
thophoto Mosaicking with the Use of a Dig- Efficient Planar Graph Cuts with Applica-
ital Surface Model. // Remote Sens. 2014, tions in Computer Vision. IEEE CVPR,
6. pp. 12334-12359. http://www.mdpi.com/ Miami, Florida, June 2009 https://
2072-4292/6/12/12334 (accessed:10.10.2017) doi.org/10.1109/CVPR.2009.5206863 (ac-
cessed:10.10.2017)
[11] Kass M., Witkin A., Terzopoulos D., Snakes:
active contour models. // International Jour- [18] Li Li, Jian Yao, Xiaohu Lu, and Jing Ren.
nal of Computer Vision, 1(4), 1988, 321331 Superpixel-Based Optimal Seamline Detec-
http://web.cs.ucla.edu/~dt/papers/ tion via Graph Cuts for Panoramic Images.
ijcv88/ijcv88.pdf (accessed:10.10.2017) submitted to IEEE International Conference
on Image Processing (ICIP), 2015 http:
[12] Kwatra V., Schodl A., Essa I., Turk G., //cvrs.whu.edu.cn/projects/SSD/papers/
Bobick A., Graphcut Textures: Image and SuperpixelStitching-ICIP2015.pdf (ac-
Video Synthesis Using Graph Cuts. // cessed:10.10.2017)
ACM Transactions on Graphics (TOG)
[19] Moravec H., Towards automatic visual obsta-
- Proceedings of ACM SIGGRAPH 2003,
cle avoidance // Proceedings of the 5-th Inter-
Volume 22 Issue 3, July 2003, pp. 277-
national Joint Conference of Artificial Intelli-
286 http://gamma.cs.unc.edu/kwatra/
gence Cambridge. 1977.
publications/gc-final-lowres.pdf (ac-
cessed:10.10.2017) [20] Dijkstra E.W., A note on two problems in
connexion with graphs // Numerische Mathe-
[13] Li Li, Yao Jian, Lu Xiaohu, Shan Jie., matik, Vol. 1, 1959. P. 269271.
Optimal Seamline Detection for Multiple
Image Mosaicking via Graph Cuts. // IS- [21] Goldberg A.V. A Simple Shortest Path
PRS Journal of Photogrammetry & Remote Algorithm with Linear Average Time. //
Sensing. February 2015. pp. 1-32. http: Proceedings of the 9th European Symposium
//cvrs.whu.edu.cn/publications/2015/ on Algorithms (ESA ’01), Springer Lecture
GraphCutsSeamlineDetection-ISPRS2015. Notes in Computer Science LNCS 2161. 2001.
pdf (accessed:10.10.2017) pp. 230-241. https://doi.org/10.1007/
3-540-44676-1_19 (accessed:10.10.2017)
[14] Boykov, Y., Veksler, O., Zabih, R., Fast
approximate energy minimization via graph [22] OpenMP [2017]. URL: http://openmp.org/
cuts. IEEE Transactions on Pattern Anal- (accessed: 01.02.2017).
ysis and Machine Intelligence 23 (11), pp
12221239. 2001. http://www.cs.cornell.
edu/rdz/Papers/BVZ-pami01-final.pdf
(accessed:10.10.2017)
[15] Boykov Y., Kolmogorov V. An Experimen-
tal Comparison of Min-cut/Max-flow Algo-
rithms for Energy Minimization in Vision. In:
Figueiredo M., Zerubia J., Jain A.K. (eds)
Energy Minimization Methods in Computer
Vision and Pattern Recognition. EMMCVPR
2001. Lecture Notes in Computer Science, vol
2134. Springer, Berlin, Heidelberg https:
//doi.org/10.1007/3-540-44745-8_24 (ac-
cessed:10.10.2017)
8