2.1.

Mental Transformation

Mental transformations of space play an important role in everyday tasks such as object recognition, spatial orientation, and motion planning. Such transformations involve both objects in the space as well as the egocentric observer position. Mental rotation is the best understood mental transformation,¹¹ where the time required to judge the similarity between a pair of differently oriented objects of arbitrary shape is proportional to the rotation angle both for two-dimensional (2-D) (image plane) and 3-D rotations, irrespective of the chosen rotation axis. Similar observations have been made for the size scaling and translation (in depth),¹² where the reaction time is shorter than for rotation. Moreover, in combined scaling and rotation¹³ as well as translation and rotation¹² the response time is additive with respect to each component transformation. This may suggest that there are independent routines for such elementary transformations, which jointly form a procedure for handling any sort of movement that preserves the rigid structure of an object.¹² Another observation is that the mental transformation passes through a continuous trajectory of intermediate object positions, not just the beginning and end positions.¹⁴

A more advanced mental transformation is perspective transformation.¹⁵ From our own experience, we know that observing a cinema screen from a moderately off-angle perspective does not reduce perceived quality, even if the retinal image underwent a strong transformation. One explanation for this ability is that humans compensate for the perspective transformation by mentally inverting it.¹⁶

Apparent motion in the forward and backward directions is induced when two 3-D-transformed (e.g., rotated) copies of the same object are presented alternatively at proper rates. As the transformational distance (e.g., rotation angle) increases, the alternation rate must be reduced to maintain the motion illusion. Again, this observation strongly suggests that the underlying transformations require time to go through intermediate stages, a 3-D representation is utilized internally,¹⁷ and elementary transformations are individually sequential-additive.¹⁸

The HVS is able to recover depth and rigid 3-D structure from two views (e.g., binocular vision and apparent motion) irrespective whether the perspective or orthographic projection is used, and adding more views has little impact.¹⁹ This indicates that the HVS might use some perceptual heuristics to derive such information as the structure-from-motion theorem stipulates that at least three views are needed in the case of orthographic projection (or under weak perspective).²⁰

The 3-D internal representation in the HVS and the rigidity hypothesis in correspondence finding, while tracking moving objects, is still a matter of scientific debate. Eagle et al.²¹ have found a preference toward translation in explaining competing motion transformations in a two-frame sequence with little regard for the projective shape transformations.

2.2.

Optical Flow

The idea of optical flow dates back to Gibson⁵ and has become an essential part of computer vision and graphics where it is mostly formalized as a 2-D vector field that maps locations in one image to locations in a second image, taken from a different point in time or space. Beyond the mapping from points to points, Koenderink⁹ conducted a theoretical analysis of elementary transformations, such as expansion/contraction (radial motion), rotation (circular motion), and sheer (two-component deformation), which can be combined with translation into a general affine transformation. Such transformations map differential area to differential area. Electrophysiological recordings have shown that specialized cells in the primate brain are selective for each elementary transformation component alone or combined with translation¹⁰ (refer also to Ref. 8, Ch. 5.8.4). A spatially varying optical flow field does not imply a spatially varying field of transformations: a global rotation that has small displacements in the center and larger displacements in the periphery can serve as an example. For this reason, our perceptual model operates on a field of elementary transformations computed from homographies instead of a dense optical flow. Homography estimation is commonly used in the video-based scene 3-D analysis, and the best results are obtained when multiple views are considered.²⁰

In computer graphics, the use of elementary transformation fields is rare, with the exception of video stabilization and shape modeling. In video stabilization, spatially varying warps of handheld video frames into their stabilized version are performed with a desired camera path. Typically a globally reconstructed homography is applied to the input frame, before the optimization-driven local warping is performed,²² which is conceptually similar to our local homography decomposition step (Sec. 3.2). Notably, the concept of subspace stabilization²³ constructs a lower-dimensional subspace of the 2-D flow field, i.e., a space with a lower number of different flows, i.e., lower entropy. In shape modeling, flow fields are decomposed into elementary transformations to remove all but the desired transformations, i.e., to remain as-rigid-as-possible when seeking to preserve only rotation.²⁴

2.3.

Visual Attention

Moving objects and “pop-out” effects are strong attractors of visual attention.⁷ The classic visual attention model proposed by Itti et al.²⁵ apart from the common neuronal features, such as intensity contrast, color contrast, and pattern orientation can handle also four oriented motion energies (up, down, left, and right). Differently, in our work, we detect saliency of motion, which pops out not just because it is present and the rest is static, but because it is different from other motion in the scene, such as many rotating objects where one rotates differently. As humans understand motion in form of elementary transformations,¹⁰ our analysis is needed to find those differences.

2.4.

Motion Parallax

For a moving viewer, objects at one depth undergo a different flow than objects in their spatial neighborhood at different depth. This effect, called “motion parallax,” is both a depth cue²⁶ and a grouping Gestalt cue.²⁷ In relation with translation and the four elementary transformations over the flow field as derived by Koenderink,⁹ the corresponding motion parallax components can be distinguished: linear motion, expansion or contraction, rotation, shear-deformation, and compression- or expansion-deformation parallax (Ref. 8, Ch. 28.1.3). We propose a motion parallax measure, which approximates each of those components, although in our applications we found that the linear motion parallax plays the key role.

2.5.

Entropy

Information entropy is a measure of complexity in the sense of how much a signal is expected or not.²⁸ If it is expected, the entropy is low, otherwise it is high. In our approach, we are interested in the entropy of transformations, which tells apart uniform transformations from incoherent ones, such as disassembling a puzzle. Assembling the puzzle is hard, not because the transformation is large, but because it is incoherent, i.e., it has a high entropy. This view is supported by studies of human task performance:^29,30 Sorting cards with a low entropy layout can be performed faster than sorting with high entropy. In computer graphics, entropy of luminance is used for the purpose of alignment,³¹ best-view selection,³² light source placement,³³ and feature detection but was not yet applied to transformations.

3.1.

Overview

Our system consists of two layers (Fig. 2). A model layer described in this section and an application layer, described in Sec. 4. Input to the model layer are two images where the second image differs from the first one by a known mapping, which is assumed to be available as a spatially dense optical flow field. This requires either use of optical flow algorithms that support large displacements³⁴ and complex mappings²³ or use of computer-generated optical flow (a.k.a. motion field). Output of our method is a field of perceptually scaled elementary transformations and a field of transformation entropy ready to be used in different applications.

Fig. 2

Flow of our approach

Our approach proceeds as follows (Fig. 2). In the first step (Sec. 3.2), we convert the optical flow field that maps positions to positions into an overcomplete field of local homographies, describing how a differential patch from one image is mapped to the other image. While classic flow only captures translation, the field of homographies also captures effects such as rotation, scaling, shear, and perspective. Next, we factor the local homographies into “elementary” translation, scaling, rotation, shear, and perspective transformations (Sec. 3.3). Also, we compute the local entropy of the transformation field, i.e., how difficult it is to understand the transformation (Sec. 3.4). Finally, the magnitude of elementary transformations is mapped to scalar perceptual units, such that the same value indicates roughly the same sensitivity (Sec. 3.5).

Using the information above allows for several applications. Most importantly, we propose an image difference metric (Sec. 4.1) that is transformation-aware. We model the threshold elevation, which determines how much the smallest perceivable difference between two images increases as a function of transformation strength and complexity, i.e., entropy. The second application is a visual attention model that can detect what transformations are salient (Sec. 4.2). Finally, the amount of perceived parallax in the image pair can be computed from the above information (Sec. 4.3).

3.2.

Homography Estimation

Input is two images with luminances $g_1$ and $g_2(\mathbf{x})\in {\mathbb{R}}^2\to \mathbb{R}$ and $\mathbf{x}$ as spatial location as well as a flow $f(\mathbf{x})\in {\mathbb{R}}^2\to {\mathbb{R}}^2$ from $g_1$ to $g_2$. First, the flow field is converted into a field of homography transformations.²⁰ A homography maps a differential image patch into the second image while optical flow maps single pixel positions to other pixel positions. In human vision research, this Helmholtz decomposition was conceptually proposed by Koenderink⁹ and later confirmed by physiological evidence.¹⁰ Examples of homographies are shown in Fig. 3(a). In our case, homographies are 2-D projective $3\times 3$ matrices. While $2\times 3$ matrices can express translation, rotation, and scaling, the perspective component allows for perspective foreshortening.

Fig. 3

(a) The effect of identity, translation, rotation, scale, shear, and perspective transformations applied to a quad. Edge-aware moving least-squares estimation of a homography $\mathbf{M}(\mathbf{x})$ from a set of points ${\mathbf{x}}^i$ undergoing a flow $f$. (b) Note how pixels from different image content (dark pixels) that undergo a different transformation are not affecting the estimation.

We estimate a field of homographies, i.e., a map that describes for every pixel where its surrounding patch is going. We compute this field $\mathbf{M}(\mathbf{x})\in {\mathbb{R}}^2\to {\mathbb{R}}^{3\times 3}$ by solving a motion discontinuity-aware moving least-squares problem for every pixel using a normalized eight-point algorithm.³⁵ The best transformation $\mathbf{M}(\mathbf{x})$ in the least squares sense minimizes

In the discrete case of Eq. (1), for pixel $\mathbf{x}$ we find one $\mathbf{M}$ that minimizes

We solve this as a homogenenous linear least squares problem in form $\mathbf{B}\mathbf{m}=0$. For one flow direction ${\mathbf{f}}_i$ at position ${\mathbf{y}}_i$ and a matrix $\mathbf{M}$, we require

The procedure is similar to fitting of a single homography in computer vision.²⁰ It is more general, as our flow field is not explained by a rigid camera but needs to find one homography in each pixel. To ensure a consistent and piecewise smooth output we combine a regularizing smooth kernel with an edge-aware component $w$ [Eq. (2)].

We implement the entire estimation in parallel over all pixel locations using graphics hardware (GPUs) allowing us to estimate the homography field in less than 3 s for a high-definition image.

3.3.

Transformation Decomposition

For perceptual scaling the per-pixel transformation $\mathbf{M}$ is decomposed into multiple elementary transformations: translation (${\mathbf{e}}_{\mathrm{t}}$), rotation ($e_{\mathrm{r}}$), uniform scaling ($e_{\mathrm{s}}$), aspect ratio change ($e_{\mathrm{a}}$), shear (${\mathbf{e}}_{\mathrm{h}}$), and perspective (${\mathbf{e}}_{\mathrm{p}}$) (cf. Fig. 4). The relative difficulty of each transformation will later be determined in a perceptual experiment (Sec. 3.5).

Fig. 4

Conversion of an image pair into elementary transformations. Optical flow from A to B (polar representation) is fitted by local homography matrices (here locally applied on ellipses for illustration) to get five elementary transformations (shear left out for simplicity) having eight channels in total.

We assume that our transformations are the result of a 2-D transformation followed by a perspective transformation. This order is arbitrary, but we decided for it, as it is closer to usual understanding of transformations of 3-D objects in a 2-D world. This is motivated by the fact that it is more natural to imagine objects to live in their (perspective) space and move in their 3-D oriented plane before being projected to the image plane than to understand them as 2-D entities undergoing possibly complex nonlinear and nonrigid transformations in the image plane.

The decomposition happens independently for the matrix $\mathbf{M}$ at every pixel location. As $\mathbf{M}$ is unique up to a scalar, we first divide it by one element, which is chosen to be $m_{33}$. In the next five steps, each elementary component $\mathrm{T}$ will be found first by extracting it from $\mathbf{M}$, and then removing it from $\mathbf{M}$ by multiplying with ${\mathrm{T}}^{-1}$.

First, perspective is extracted by computing horizontal and vertical focal length as ${\mathbf{d}}_p={({\mathbf{M}}_{\mathrm{a}}^{\mathrm{T}})}^{-1}·(m_{31},m_{32},0)$ where ${\mathbf{M}}_{\mathrm{a}}$ is the affine part of $\mathbf{M}$. The multiplication removes dependency of ${\mathbf{d}}_p$ on other transformations in $\mathbf{M}$. To define the perceptual measure of the elementary transformation corresponding to the perspective change, we later convert the focal length into the $x$-axis and $y$-axis field of view ${\mathbf{e}}_{\mathrm{p}}=2\arctan ({\mathbf{d}}_p/2)$ expressed in radians. To remove the perspective from $\mathbf{M}$, we multiply it by the inverse of a pure perspective matrix in the form

Second, a 2-D vector of translation transformation ${\mathbf{e}}_{\mathrm{t}}=(m_{13},m_{23})$ in visual angle degrees is found. It is removed from $\mathbf{M}$ by multiplying with the inverse of a translation matrix.

Next, we find the rotation transformation corresponding to the angle $e_{\mathrm{r}}=\arctan 2(m_{21},m_{11})$ in radians and remove it by multiplying with an inverse rotation matrix.

2-D scaling power is recovered as ${\mathbf{d}}_s=\log (m_{11},m_{22})$ and removed from the matrix. For the purpose of later perceptualization, we define a uniform scaling $e_{\mathrm{s}}=\max (|{\mathbf{d}}_{s,x}|,|{\mathbf{d}}_{s,y}|)$ and a change of aspect ratio $e_{\mathrm{a}}=|{\mathbf{d}}_{s,x}-{\mathbf{d}}_{s,y}|$. The assumption is that anisotropic scaling requires more effort to undo than simple isotropic size change and two separate descriptors are, therefore, needed.

The last component is shear defined by a scalar angle as $e_{\mathrm{h}}=\arctan (m_{12})$ in radians.

3.4.

Transformation Field Entropy

Definition Ease and difficulty of dealing with transformations does not only depend on the type and magnitude of a transformation on its own but also as it is often the case in human perception it depends on a context. Compensating for one large coherent translation might be easy compared to compensating for many small and incoherent translations. We model this effect using the notion of transformation entropy of an area in an elementary transformation field. Transformation entropy is high if many different transformations are present in a spatial area, and it is low if it is uniform. Note how entropy is not proportional to the magnitude of transformations in a spatial region but to the incoherence in their probability distribution.

We define the transformation entropy $H$ of an elementary transformation at location $\mathbf{x}$ in a neighborhood $s$ using standard entropy equation as

Fig. 5

Entropy for different transformation fields applied to circular items. One transformation maps to one color. (a) For identity, the histogram has a single peak and entropy is 0. (b) For two transformations the histogram has two peaks and entropy is larger. (c) For three transformations, there are three peaks. Entropy is even larger. (d) In increasingly random fields the histogram flattens and entropy increases.

The probability distribution $p(\omega |\mathbf{x},s)$ of elementary transformations at neighborhood $\mathbf{x}$, $s$ has to be computed using density estimation, i.e.,

Depending on the size of the neighborhood $s$, entropy is more or less localized. If the neighborhood size is varied, entropy changes as well, resulting in a scale space of entropy,³⁷ studied in computer vision as an image structure representation. For our purpose, we pick the entropy scale space maximum as the local entropy of each pixel and do not account for the fact at what scale it occurred. The difficulty of transformations was found to sum linearly.¹¹ For this reason, we sum the entropy of all elementary transformation into a single scalar entropy value.

The decomposition into elementary transformations is the key to the successful computation of entropy; without it, a rotation field would result in a flat histogram as all directions are presented. This would indicate a high entropy, which is wrong. Instead, the HVS would explain the observation using very little information: a single rotation with low entropy.

3.4.1.

Implementation

In the discrete case, the integral to compute the entropy of the pixel $\mathbf{x}$ becomes

Eq. (4)

$$\widehat{H}(\mathbf{x})=-\sum _{j=0}^{n_{\mathrm{b}}}\sum _{k\in \mathcal{N}(s)}K(t_k-{\omega }_j)\log \sum _{k\in \mathcal{N}(s)}K(t_k-{\omega }_j),$$

where ${\omega }_j$ is the center of the $j$’th bin. The inner sums compute the probability of the $j$’th transformation, essentially by inserting the $k$’th transformation from a neighborhood $\mathcal{N}(s)$ of size $s$ into one of $n_{\mathrm{b}}=32$ bins. An example result is shown in Fig. 6.

Fig. 6

Entropy of an image under a puzzle-like flow field. (a) No-transformation yields zero entropy. (b) Low entropy is produced by two coherent transformations despite a high average flow magnitude ($\approx 192\mathrm{px}$). (c) Transformations with increasing incoherence due to pieces that rotate and swap lead to horizontally increasing entropy despite of a low flow magnitude ($\approx 32\mathrm{px}$).

Due to the finite size of our $n_{\mathrm{b}}$ histogram bins and the overlap of the Gaussian kernel $K$, we systematically overestimate the entropy; even when only a single transformation is present, it will cover more than one bin, creating a nonzero entropy. To address this, we estimate the bias in entropy due to a single Dirac pulse and subtract it. We know that 0.99 of the area under a Gaussian distribution is within 3.2 standard deviations $\sigma$. That means that a conservative estimate of response to a Dirac pulse is a uniform distribution of the value between $3.2\sigma$ bins. That yields the entropy $H_{\text{bias}}\approx -3.2\sigma (1/3.2\sigma )\log (1/3.2\sigma )=-\log (1/3.2\sigma )$. For our $\sigma =0.5$ this evaluates to $H_{\text{bias}}=0.2$. We approximate the entropy by subtracting this value

Eq. (5)

$$H(\mathbf{x})=\widehat{H}(\mathbf{x})-H_{\text{bias}}.$$

Computing the entropy [Eq. (5)] in a naïve way would require us to iterate a large neighborhoods $\mathcal{N}(s)$ (up to the entire image) for each pixel $\mathbf{x}$ and every scale $s$. Instead, we use smoothed local histograms³⁸ for this purpose. In the first pass, the 2-D image is converted into a 3-D image with $n$ layers. Layer $i$ contains the discrete smooth probability of that pixel taking this value. Histograms of larger areas as well as their entropy can now be computed in constant time, by constructing a pyramid on the histograms.

3.5.

Perceptual Scaling

All elementary transformations as well as the entropy are physical values and need to be mapped to perceptual qualities. Psychological experiments indicate that elementary transformations such as translation, rotation, and scaling require time (or effort) that is close to linear in the relevant $x$-axis variable^{11,13,17,18,39} and that the effect of multiple elementary transformations is additive.^13,18 A linear relation was also suggested for entropy in Hick’s law.³⁰ Therefore, we scale elementary transformation and entropy using a linear mapping (Fig. 7) and treat them as additive.

Fig. 7

Perceptual scaling: $x$-axis: increasing elementary transformations and entropy. $y$-axis: increasing difficulty/response time.

3.5.1.

Transformation

To find the scaling, an experiment was performed similar to the one that Shepard and Metzler¹¹ conducted for rotation but extended to all elementary transformations as defined in Sec. 3.3, including shear and perspective. Objective of the experiment is to establish a relationship of transformation strength and difficulty, measured in response time increase in the mental transformation tasks.

Subjects were shown two abstract 2-D images (Fig. 8) generated from patterns in Fig. 9. The two patterns were either different or identical. One out of the two patterns was transformed using a single elementary transformation of intensity $e_i$ as listed in the upper part of Table 1. Subjects were asked to indicate as quickly as possible if the two patterns are identical by pressing a key. Auditory feedback was provided to indicate if the answer was correct. The time $t(e_i)$ until the response was recorded for all correct answers where the two patterns were identical up to a transformation. The choice of pattern to transform (left or right), the elementary transformation $i$ and its magnitude $e_i$ were randomized in each trial.

Fig. 8

Some of the stimuli used in our perceptual scaling experiment (Sec. 3.5). The same stimulus under (a) 135 deg rotation requiring 1.4 s mental transformation to undo, (b) 50% scaling (1.1 s), (c) $0.15\pi \mathrm{rad}$ shear (1.2 s), (d) $0.15\pi \mathrm{rad}$ perspective (1.05 s), and (e) 50% aspect ratio change (1.1 s). (f) A counter example of two different stimuli. (g) A hypothetical extension of our experiment for measuring of the entropy factor as a detection time for an identical stimulus in a growing set of masking objects.

Fig. 9

All eight patterns used to generate stimuli for our perceptual scaling experiment (Sec. 3.5).

Table 1

Results of our perceptual scaling experiment (Sec. 3.5). Input domain corresponds to the range of the transformation parameter presented to users. The response time functions were fitted to our data for elementary transformations and theoretically derived for entropy (Fig. 7). Refer to Secs. 3.3 and 3.4 for the definition of input variables and their units.

Transformation	Input domain	Response time fit	R2
Translation	$e_t\in [0,180]\mathrm{deg}$	$t(e_t)=0.00265e_t+0.987$	0.171
Rotation	$e_{\mathrm{r}}\in [0,\pi ]\mathrm{rad}$	$t(e_{\mathrm{r}})=0.00280e_{\mathrm{r}}+1.053$	0.846
Scaling	$e_{\mathrm{s}}\in [0,2]\log .\text{units}$	$t(e_{\mathrm{s}})=0.12100e_{\mathrm{s}}+0.999$	0.933
Aspect	$e_{\mathrm{a}}\in [0,2]\log .\text{units}$	$t(e_{\mathrm{a}})=0.12100e_{\mathrm{a}}+0.984$	0.972
Shear	$e_h\in [0,0.32\pi ]\mathrm{rad}$	$t(e_h)=0.00640e_h+0.973$	0.968
Perspective	$e_p\in [0,0.4\pi ]\mathrm{rad}$	$t(e_p)=0.00342e_p+0.989$	0.805
Entropy	$H\in [0,\infty )\mathrm{bits}$	$t(H)=0.60000\widehat{H}+0.998$	—

Twenty-one subjects (17 M/4 F) completed 414 trials of the experiment in three sessions. For each elementary transformation, we fit a linear function to map strength to response time (Fig. 7). We found a good fit of increasing linear functions of $x$ for all transformations except translation. See Table 1 for the derived model functions. We do not have a definitive answer, why the correlation with translation is lower than for other transformations. A hypothetical explanation is that eye motions can be used to mechanically compensate for translation without mental effort while there is no anatomical option to compensate for rotation, scaling, and so on. An improved design could employ other ways of multiplexing stimuli, e.g., across time, to identify how much translation is cofounded by mental or mechanical aspects, respectively. This agrees with findings for rotation¹¹ or scaling,¹² and our different bias or slope is likely explained by the influence of stimulus complexity also found by Shepard and Metzler.¹¹

4.1.

Image Difference Metric

The most direct application of our transformation decomposition and its perceptual scaling is building an image difference metric. Our metric does both compare luminance patterns in corresponding regions of the image and also evaluates the strength and the complexity of the spatial relation between them. This way it accounts for the difficulty that the same matching task would cause to the HVS. In combination with a chosen traditional image metric our perceptual transformation measure works as a threshold elevation factor that modifies visibility of image differences (Figs. 1 and 10).

Fig. 10

Results of image difference application using the SSIM index. Rows (top to bottom): (I) A real scene photograph with lot of entropy in the right shuffled CD stack. (II) A simple real scene. (III) A comparison of a photograph and a rerendering of a corridor. (IV) A rendering of flying asteroids. (V) A rendering of a bedroom with some pillows moved. (VI) A rendering of rock landscape with some rocks moved. Columns (left to right): (a, b) Two input images. (c) A naive quality metric without alignment results into false-positive values everywhere. (d) Image alignment itself does not account for high entropy, which would prevent an observer from easily comparing individual objects. (e) Our metric predicts such behavior and marks differences there as less visible.

The inputs are two images $g_1$ and $g_2$ and their optical flow $f$ as explained in Sec. 3.2. Initially, the second image $g_2$ is aligned to the first one using the inverse flow $f^{-1}$. Next, the images can be compared using an arbitrary image metric (we experiment with DSSIM⁶), with the only modification that occluded pixels are skipped from all computations. As a result, a map $\widehat{\mathcal{D}}$ is created that contains abstract visual differences [a unitless quality measure in the range from 0 to 1 for $\widehat{\mathcal{D}}(g_1,g_2)=DSSIM(g_1,g_2)$ as used in our examples]. This map does not account for the effect of the transformation strength and entropy while we have seen from our experiments that large or incoherent transformations make comparing two images more difficult.

Next, for every pixel we express the increase of difficulty $d_i=t(e_i)-t(0)$ (response time minus optimal response time, i.e., with no transformation or entropy) due to each elementary transformation: translation ($d_{\mathrm{t}}$), rotation ($d_{\mathrm{r}}$), scale ($d_{\mathrm{s}}$), shear ($d_{\mathrm{h}}$), and perspective ($d_{\mathrm{p}}$) as well as the entropy ($d_{\mathrm{H}}$), resulting in a transformation difficulty factor

The summation is motivated by the finding that response time besides being linear also sums in a linear fashion^12,13 (if scaling adds one second and rotations adds another one, the total time is 2 s).

Finally, we use $\delta$ as a factor masking the otherwise potentially perceivable differences in $\widehat{\mathcal{D}}$

Image transformations that contain local scaling power larger than 0 (zooming) might reveal details in $g_2$ that were not perceivable or not represented in the first image $g_1$. Such differences could be reported as indeed they show something in the second image that was not in the first. However, we decided not to consider such differences as a change from nothing into something might not be a relevant change. This can be achieved by blurring the image $g_2$ with a blur kernel of a bandwidth inversely proportional to the scaling. Occlusions are handled in the same way: No perceived difference is reported for regions only visible in one image.

4.1.1.

Validation

We validate our approach by measuring a human performance in perceiving differences in an image pair and analyzing its correlation with transformation magnitude and entropy. Subjects were shown image pairs that differed by a flow field as well as a change in content. Two image pairs show 3-D renderings of 16 cubes with different textures [see Figs. 11(a) and 11(c)]. The transformation between the image pairs included a change of 3-D viewpoint and a variety of 3-D motions for each cube. Larger transformations were chosen on the right side of the image [Fig. 11(e)] and similar trend also applies to the entropy introduced by swapping several of the cubes in the grid [Fig. 11(f)].

Fig. 11

The validation of our image metric application. An example trial from the user study where a varying degree of geometrical transformation along with a varying distortion intensity is applied to each cube. (a,c) First two rows show the stimuli with the noise and quantization distortion, respectively. (e,f) The third row shows transformation magnitude and entropy measured by our metric for transformation fields shared by both stimuli types. (b,d) The user error rates and (g) our complete difficulty prediction pooled per each cube can be directly compared in the third column. Note that the difficulty metric shown here only measures the transformation influence and therefore is the same for both stimuli. See Sec. 4.1 for the full image metric.

The images were distorted by adding noise and color quantization to randomly chosen textured cubes, so that the corresponding cubes could differ either by the presence of distortion or their intensity. The intensities of distortions were chosen so that without the geometrical transformation the artifacts are just visible. Ten subjects were asked to mark the cubes that appear different using a 2-D painting interface in an unlimited time. We record the error rate of each object as a relative number of cases the subjects gave wrong answers, i.e., where there was an image difference that they did not mark and where they marked a distortion while there was none [Figs. 11(b) and 11(d)]. Difficult areas have an error rate of 0.5 (chance level) while areas where the subjects were confident have a value as low as 0. The error rate is averaged over all subjects for one distortion and one scene.

Our transformation difficulty metric consists of the transformation magnitude measures and entropy, and we pool it for each cube by averaging to obtain 16 scalar values [Fig. 11(g)]. As the geometrical layout is the same for both types of distortions and each was setup to have a similar visibility, the assumption is that the subjects would find the same geometrical transformations difficult in both cases. That means that error rates in Figs. 11(b) and 11(d) should be similar and we correlate our metric with both of them together.

We analyzed the correlation of the error rate [Figs. 10(b) and 10(d)] and transformation magnitude and entropy [Figs. 10(e)–10(g)] and found an average Pearson’s $r$ correlation of 0.701 (Table 2), which is significant according to the $t$-test with $p<0.05$. The transformation magnitude has a lower correlation of $r=0.441$ compared to transformation entropy $r=0.749$ (significant for $p<0.05$). This difference could possibly be explained by a design of our experiment. Given an unlimited time, the subjects were eventually able to undo all transformations and resolve all shuffling between the cubes. It may be that the short-term memory requirement made the shuffling problem harder than the one resulting from the transformations. This would increase the importance of entropy for the performance prediction and lead to a higher correlation. A time constrained version of the experiment could answer this question. Another possible explanation points to a relatively low magnitude of transformations applied to our stimuli compared to the entropy introduced by shuffling of many similar cubes. An experiment design with different combinations of both factors could be used to verify this theory. Despite this asymmetry, we conclude that both transformation magnitude and entropy correlates with the ability to detect distortions; in the presence of strong or complex transformation, the increase in human detection error can be fit using a linear model.

Table 2

Correlations of image differences from variants of our metric [Figs. 10(e)–10(g)] and average error rate of our study participants [Figs. 10(b) and 10(d) together] as described in Sec. 4.1. Stars⋆ denote significance according to the t-test with p<0.05.

Metric	Correlation
Only transformation magnitude	0.441
Only transformation entropy	0.749⋆
Our full metric	0.701⋆

The final performance of our approach is limited by the image metric used. The correlation of image metrics and quantitative user responses is low and difficult to measure⁴⁰ even without transformations. Therefore, the evaluation of the full metric, in particular for suprathreshold conditions, is relegated to future work.

4.2.

Saliency

Saliency estimation has a lot of applications in computer graphics (Sec. 2.3). It can substitute for a direct eye tracking and enable image processing optimized for important regions of the image that are more likely to be observed than others. While some other saliency models also consider motion, our method is unique in decomposing motion into elementary transformations (Fig. 12). This allows for an easier detection of a distinct motion patterns that can be obstructed in the original optical flow. Such unique features easily causes a “pop-out” effect, which attracts a user attention, hence it increases saliency.

Fig. 12

Transformation-aware saliency for (a) an input image being deformed into image (b). One patch is salient, as it deforms differently. Only transformation saliency is shown. This “differently,” however, is nontrivial and can only be detected with a transformation representation that captures the human ability to compensate for certain transformations including perspective, such as ours. Other motion saliency methods do not capture this effect (c), but instead consider other parts more salient, following local variations in the flow.

Different from common image saliency, our approach takes two instead of one image as an input. It outputs saliency, e.g., how much attention an image region receives. We largely follow the basic, but popular, model of Itti et al.,²⁵ and replace its motion detection component by our component that detects salient transformations.

First, we compute a feature map for every elementary transformation signal $e_i$ (Sec. 3.3) as

Finally, all conspicuity maps are normalized and averaged to get the final motion saliency score

4.3.

Motion Parallax

Motion parallax is defined by relative retinal motion due to a rigid geometrical transformation of the scene during motion of the object or the observer. Analyzing variance of optical flow directly can easily lead to an overestimation of the relative motion since nonlinear transformations, such as rotation, will yield incoherent optical flow. Our transformation decomposition removes this problem by attributing each elementary transformation to its proper magnitude map $e_i$. This way relative motion can be analyzed more robustly by investigating each map separately.

We propose a measure of motion parallax (Sec. 2.4), which relies on a combination of spatial change of flow (motion contrast) and spatial change of luminance (luminance contrast) (Fig. 13, Middle). First, an elementary transformation is computed for each level of the pyramid. The resulting pyramids contain at every pixel the difference in motion between a pixel and its spatial context of a size that depends on the level. Then, we compute the absolute values of such differences.

Fig. 13

Motion parallax between images A and B.

First, similar to a Laplacian image pyramid,⁵⁵ we build a contrast pyramid ${\mathcal{C}}_i$ for each elementary transformation $e_i$ (Sec. 3.3)

4.3.1.

Adaptive parallax occlusion mapping

Real world objects often exhibit complex surface structures that would be too costly to directly model for computer graphic rendering applications. The huge geometry complexities would quickly surpass the memory capacity or the rendering throughput of any hardware. That is why the objects get simplified and surface details replaced by a single plane. This is efficient but it reduces the realism as both shading and structural details cannot be correctly reproduced [Fig. 14(a)]. The normal mapping⁵⁶ uses additional surface raster to encode normal details, which are then used to reconstruct high frequencies of the shading at cost of a small memory and performance overhead [Fig. 14(b)]. The results are convincing for a static scene but adding a motion reveals that the motion parallax cue is completely missing. The parallax occlusion mapping⁵⁷ (POM) tackles this issue by adding a surface-displacement map and performing a simple ray tracing to determine visibility and occlusions inside the surface plane [Fig. 14(c)]. Although significantly more costly, this effect is popular in current games as it greatly improves the realism. The importance of this effect has also been noticed in head mounted displays for virtual reality applications where the mismatch between head motion and the lack of motion parallax is strongly objectionable. As the computation happens inside the originally flat surface, its outline cannot be modified. That means that the shape of the object can still reveal the underlying simplified model. A remedy for this is provided by the displacement mapping, which uses HW capability of modern GPUs to generate a detail geometry matching the height map on the fly, therefore, without memory footprint [Fig. 14(d)]. As both of the later techniques are quite costly to compute, their use should be driven by a benefit that they bring to the user. We demonstrate how such a decision can be supported by our method on the case of POM.

Fig. 14

Examples of surface mapping techniques used in computer graphics. (a) Classic shading cannot reproduce high frequency details that are not part of the geometry. (b) Normal mapping introduces detail shading variation. (c) POM allows for motion parallax inside the object. (d) Displacement mapping additionally supports changes in the object outline.

In case of the POM, the height field needs to be ray-traced for every pixel, limiting its use in interactive applications, especially on low-power, i.e., mobile devices. Using our approach we can detect where a certain displacement map will actually result in a perceivable motion parallax for a certain view direction when this view is slightly changed and adjust the quality of the effect per-pixel, saving considerable compute time and bandwidth (Fig. 15). To this end, we prerender the displacement map, including texturing for all view directions and compute the motion parallax for a differential motion along each spherical direction for all view directions (refer to the inset in Fig. 15). The result is a lookup function that indicates how much a pixel benefits from POM from a certain view or not. At runtime, we look up the value for a given view direction, and adjust the size of a ray-tracing step for each pixel. That modifies the number of iterations required for evaluation of the effect and, therefore, the required computational time.

Fig. 15

Two frames of an image sequence where we selectively enable POM based on a preprocessing of the displacement map that predicts for which view and illumination a parallax effects is perceivable, decreasing the number of POM ray casting steps by up to 50% and rendering time from 13.5 to 8.9 ms.

4.3.2.

Motion parallax-based viewpoint selection

Motion parallax is an effective depth cue,²⁶ and cinematographers know how to use it to convey the layout of a scene. To our knowledge however, there is not yet an automated way to pick the right camera or object motion, such that the resulting motion parallax is most effective. Consequently, casual users that need to place a camera will have difficulties selecting it effectively.

Using our approach, we can derive an extended view point+motion selection approach (Fig. 16) that, given a 3-D scene, picks a view direction and a change of view position, such that the resulting image pair features optimal motion parallax. The image pair can directly be used in a stereo flip animation or as two key frames of a very slow camera motion, akin to the Ken Burns’ effect in 2-D (Ref. 58, page 512). Optionally, the view position can be fixed, and only the direction of change is suggested, or vice versa. To compute the pair, we use the same approach as for POM. We densely sample the motion parallax of the entire image for the 2-D set of all view directions and their $\phi$ and $\theta$ derivatives in spherical coordinates. We return the pair where the motion parallax is maximal, optionally combined with other viewpoint criteria.

Fig. 16

Selection of two views for an anatomical dataset (UTCT, U Texas), where motion parallax when flipping the two images at the right speed reveals most about the depth layout. The right column shows the spatially varying motion parallax (top), the integrated motion parallax and common viewpoint preference (center), and the images for all view directions (bottom).